关于曼哈顿距离
曼哈顿距离——两点在南北方向上 的距离加上在东西方上的距离， 即D（I，J）=|XI-XJ|+|YI-YJ|。 对于一个具有正南正北、正东正 西方向规则布局的城镇街道，从 一点到达另一点的距离正是在南 北方向上旅行的距离加上在东西 方向上旅行的距离因此曼哈顿距 离又称为出租车距离。
• 类间距离:
Update the cluster means
4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10
reassign
10 9 8
10 9 8 7 6
reassign
K=2
Arbitrarily choose K object as initial cluster center
7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10
– 分割算法 (Partitioning Algorithms)， – 层次算法 (Hierarchical Algorithms)， – 密度型算法 (Density-Based Algorithms)
分割算法
• 数据由使用者指定分割成K个集群群组。每一个 分割 (partition) 代表一个集群(cluster)，集群是以 最佳化分割标准 (partitioning criterion) 为目标， 分割标准的目标函数又称为相似函数 (similarity function)。因此，同一集群的数据对象具有相类 似的属性。 • 分割算法中最常见的是
3）重心距离法，类间距离等于两类的重心之间的距离，即，
D(A, B)=d(Xa, Xb)， 其中Xa和Xb分别是类A和类B的重心，即类内所有样本的 均值坐标。 4）平均距离法，类间距离等于两类中所有样本对之间距离的 平均值，即， D(A, B)={sumD( i, j )} / (ab)。 5）中间距离法，类间距离等于两类中所有样本对之间距离的 中间值，即， D(A, B)=median{D( i, j )}。
替原来的多个指标（主成分分析？因子分析？）。
例如：
• 在医生医疗质量研究中，有n个医生参加医疗质量评比， 每一个医生有k个医疗质量指标被记录。利用聚类分析可 以将n个医生按其医疗质量的优劣分成几类，或者把 k个 医疗质量指标按反映的问题侧重点不同分成几类。
• 在冠心病研究中，观察n个病人的 k个观察指标，并利用
聚类分析方法分析这n个病人各自属于哪一类别，相似 的病人可以采取相似的治疗措施；同时也能将k个指标分 类，找出说明病人病情不同方面的指标类，帮助医生更 好地全面了解病人病情。
• 聚类分析不同于因素分析：
因素分析是根据所有变量间的相关关系提取公共因子； 聚类分析是先将最相似的两个变量聚为一小类，再去与最相似 的变量或小类合并，如此分层依次进行；
量， 那么，指标变量 Xs和Xt之间的相关系数是：
*
相关系数越大，说明两个指标变量的性质越相似。
* 这是一个无量纲统计量。
3、度量类与类之间的距离：类间距离
令类A和类B中各有a和b个样本，D(i ,j)为类A中第 i 个样本
与类B中第 j 个样本之间的距离；假设D(A, B)为类A和类B
之间的距离，那么，常用的几种类间距离定义的方法是： 1）最短距离法，类间距离等于两类中距离最小的一对样 本之间的距离，即， D(A, B)=min{D( i, j )}。 2）最长距离法，类间距离等于两类中距离最大的一对样 本之间的距离，即， D(A, B)=max{D( i, j )}。
聚类分析完全是根据数据情况来进行的。就一个由n个样本、k 个特征变量组成的数据文件来说 ，当对样本进行聚类分析时，相当 于对k 维坐标系中的n 个点进行分组，所依据的是它们的距离 ；当 对变量进行聚类分析时，相当于对n维坐标系中的k个点进行分组， 所依据的也是点距。所以距离或相似性程度是聚类分析的基础。点 距如何计算呢？拿连续测量的变量来说，可以用欧氏距离平方计算： 即各变量差值的平方和。
– – – – 单一连接法(single linkage)：又称最短距离法。 完全连接法(complete linkage)：又称最长距离法。 平均连接法(average linkage) 重心法(centroid method)
C
B A
算法
• 聚类分析算法，不需要事先知道资料该分 成几个已知的类型，而可以依照资料间彼 此的相关程度来完成分类分群的目的。此 法可概分为：
聚类分析的方向：
• 聚类分析(cluster analysis)是将样本个体或指标变量按其具
有的特性进行分类的一种统计分析方法。
o 对样本进行聚类，称为样本(Q型)聚类分析。其目的是将 分类不明确的样本按性质相似程度分成若干组，从而发 现同类样本的共性和不同类样本间的差异。 o 对指标进行聚类，称为指标（R型）聚类分析。其目的 是将分类不明确的指标按性质相似程度分成若干组，从 而在尽量不损失信息的条件下，用一组少量的指标来代
* 类间距离越小，说明两个类内的样品性质越相似。
*4、度量类与类之间的相似系数：类间相似系数
令类A和类B中各有a和b个指标变量，Za和Zb分别是 由类A和类B中所有指标变量的线性组合构成的新变 量（称为类成分），例如： Za = a1 X1 + a2 X2
Zb = b1 X3 + b2 X4 + b3 X5
在医学研究中的聚类需求举例：
o 在解剖学研究中，希望能依据骨骼的形状、大小等特征 将人类从猿到人分为几个不同的阶段； o 在临床诊治中，希望能根据耳朵的特征，把正常耳朵划 分为几个类别，为临床修复耳缺损时提供参考；
o 在卫生管理学中，希望能根据医院的诊治水平、工作效
率等众多指标将医院分成几个类别； o 在营养学研究中，如何能根据各种运动的耗糖量和耗能 量将十几种运动按耗糖量和耗能量进行分类，使营养学 家既能对运动员适当的补充能量，又不增加体重。
1. 聚类分析的前期准备工作 聚类分析是以完备的数据文件为基础的，这一数据文件除观 测变量比较完备之外，一般还要求各个观测变量的量纲一致，即 各变量取值的数量级一致，否则各变量在描述客观事物某方面特 征差异性的作用有被夸大或缩小的可能。 所以，聚类分析前要检查各变量的量纲是否一致，不一致则 需进行转换，如将各变量均作标准化转换就可保证量纲一致。
2. 各数据挖掘工具中聚类分析的主要方法
聚类分析的基本思想是认为我们所研究的样本或指标 （变量）之间存在着程度不同的相似性（亲疏关系）。于是 根据一批样本的多个观测指标，具体找出一些彼此之间相似 程度较大的样本（或指标）聚合为一类，把另外一些彼此之 间相似程度较大的样本（或指标）又聚合为另一类，关系密 切的聚合到一个小的分类单位，关系疏远的聚合到一个大的 分类单位，直到把所有样本（或指标）都聚合完毕，把不同 的类型一一划分出来，形成一个由小到大的分类系统。最后 把整个分类系统画成一张谱系图，用它把所有样本（或指标） 间的亲疏关系表示出来。这种方法是最常用的、最基本的一 种，称为系统聚类分析。
The K-Means Clustering Method
• Example
10
10 9 8 7 6 5
10
9
9
8
8
7
7
6
6
5பைடு நூலகம்
5
4
4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10
Assign each objects to most similar center
3 2 1 0 0 1 2 3 4 5 6 7 8 9 10
* 距离越小，说明两个样本的性质越相似。
* 它的取值大小受量纲影响，不稳定。因此， 一般使用标准化的距离公式。
2、描述两个指标变量之间的相似程度：相似系数
令 Xs =(x 1 s … x i s … x n s )是第 s 个指标变
量， Xt =(x 1 t … x i t … x n t )是第 t 个指标变
且它们的组合系数使得这两个新变量具有最大的方 差，则称Za和Zb之间的相关系数为类A和类B之间的 相关系数。 说明： 类间相似系数越大，说明两个类内的指标变量 性质 越相似。
举例
距离(distance)或称相似度(similarity)
A3
• 两点之间的距离：
A2 A1
– 欧氏距离(Euclidean distance) – 欧氏距离的平方(squared Euclidean distance) – 曼哈顿距离(Manhattan distance ; City-Block)
– k-平均方法（ K-means ） – k-中心点方法（ K-medoid ）
两种方法都是属于启发式 (heuristic)
•
•
•
K-means算法：集群内资料平均值为集群的中 心 K-means集群算法，因为其简单易于了解使用 的特性，对于球体形状 (spherical-shaped)、中 小型数据库的数据挖掘有不错的成效，可算是 一种常被使用的集群算法。 1967年由学者J. B. MacQueen 所提出，也是最 早的组群化计算技术。
聚类分析的统计量
数据
从几何学角度看，上面表中的每一行或每一列 都表示了空间中的一个点或一个向量。
1、描述两个样本之间的相似程度:
距离
令 Xi =(x i 1 … x i t … x i k )是第 i 个样本观察 值， Xj =(x j 1 … x j t … x j k )是第 j 个样本观 察值，那么，样本 Xi 和 Xj 之间的欧氏距离是：
有多种变形形式
• k-平均方法有多种变形形式，不同改进在于：
–初始k个平均值的选择 –相异度的计算 –计算类平均值
• 产生较好聚类结果的一个有趣策略：
–首先用层次聚类方法决定结果簇的个数，并找 到初始的聚类 –然后用迭代重定位来改进聚类结果。