聚类分析广州中医药大学演示文稿

聚类分析广州中医药大学演示文稿目前一页\总数一百三十九页\编于十四点（优选）聚类分析广州中医药大学目前二页\总数一百三十九页\编于十四点聚类是一种无监督分类法:没有预先指定的类别；典型的应用作为一个独立的分析工具，用于了解数据的分布；作为其它算法的一个数据预处理步骤；---异常分析目前三页\总数一百三十九页\编于十四点应用聚类分析的例子市场销售:

帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；土地使用:

在一个陆地观察数据库中标识那些土地使用相似的地区；保险:

对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；城市规划:

根据类型、价格、地理位置等来划分不同类型的住宅；地震研究:

根据地质断层的特点把已观察到的地震中心分成不同的类；目前四页\总数一百三十九页\编于十四点

生物方面，聚类分析可以用来对动物或植物分类，或根据基因功能对其进行分类以获得对人群中所固有的结构更深入的了解。

目前五页\总数一百三十九页\编于十四点什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性

聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决于该方法是能发现某些还是所有的隐含模式；目前六页\总数一百三十九页\编于十四点可伸缩性能够处理不同类型的属性能发现任意形状的簇在决定输入参数的时候，尽量不需要特定的领域知识能够处理噪声和异常对输入数据对象的顺序不敏感能处理高维数据能产生一个好的、能满足用户指定约束的聚类结果结果是可解释的、可理解的和可用的目前七页\总数一百三十九页\编于十四点

6.2聚类分析算法分类

分裂法层次法基于密度类方法基于网格类方法基于模型类方法

目前八页\总数一百三十九页\编于十四点1、分裂法（partitioningmethod）

给定一个有N个元组或者记录的数据集，分裂法将构造K个分组，每个分组就代表一个聚类，K<N,而且这K个分组满足下列几个条件

（1）每个分组至少包含一个数据记录（2）每一个数据记录属于且仅属于一个分组（在某些模糊聚类算法中可以放宽）对于一个给定的K，算法首先给出一个初始的分组方法法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好。好的标准就是：同组记录越来越近，不同组记录越来越好使用这个算法的基本思想有：

K-MEANS算法、KMEDOID算法、CLARANS算法目前九页\总数一百三十九页\编于十四点2、层次法(hierarchicalmethod)

层次方法对给定数据对象集合进行层次的分解。

凝聚----自底向上

分裂-----自顶向下的缺点:一旦一个步骤（合并或分裂）完成，它就不能被撤消，因此而不能更正错误的决定。代表算法有：

BIRCH算法(利用层次方法的平衡迭代归约和聚类）

、CURE算法（利用代表点聚类）目前十页\总数一百三十九页\编于十四点3、基于密度的方法(density-basedmethod)

它与其他方法的根本区别：不是基于各种各样的距离的、而是基于密度的，这样就能克服基于距离的算法只能发现“类圆形”聚类的缺点。其主要思想是：只要临近区域的密度超过某个阈值，就继续聚类。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。代表算法有：

DBSCAN算法（基于高密度连接区域的密度聚类方法）

OPTICS算法、DENCLUE算法目前十一页\总数一百三十九页\编于十四点4、基于网格的方法(grid-basedmethod)

基于网格的聚类方法采用一个网格数据结构。把对象空间量化为有限数目的单元，形成了一个网格结构。优点:处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。代表算法有：

STING算法（统计信息风格）、CLIQUE算法、WAVE-CLUSTER算法

目前十二页\总数一百三十九页\编于十四点5、基于模型的方法(model-basedmethod)

给每个聚类假设一个模型（如密度分布函数），然后去寻找能很好地满足这个模型的数据集。它的潜在的一个假定是：目标数据集是由一系列的概率分布所决定的。通常有两种：统计的方案和神经网络方案目前十三页\总数一百三十九页\编于十四点

ex6.1:在病理分析时发现肺癌患者的头发中微量元素的含量与正常人相比有无异常变化。如果以Cr，Cd及As含量的一个函数作为变量x1:x1=f(Cr，Cd,As)

以Se,Zn含量的另一个函数做为变量x2,则

x2=g(Se,Zn)

在以x1为横坐标，x2为纵坐标的平面上，每个检查者按这些微量元素的含量在该平面上占据一点，其分布情况如下：目前十四页\总数一百三十九页\编于十四点x1 x2健康人群初期患者后期患者目前十五页\总数一百三十九页\编于十四点6．3聚类分析中的数据类型假设一个要进行聚类分析的数据集包含n个对象，这些对象可以是人、房屋、文件等。聚类算法通常都采用以下两种数据结构：

目前十六页\总数一百三十九页\编于十四点两种数据结构数据矩阵(twomodes)差异度矩阵(onemode)目前十七页\总数一百三十九页\编于十四点1．数据矩阵数据矩阵是一个对象—属性结构。它是n个对象组成，例如：人的对象是利用P个属性来进行描述的，如：年龄、高度、重量等。数据矩阵采用关系表形式或nP矩阵来表示，如（6.1)式目前十八页\总数一百三十九页\编于十四点

(6.1)

常称为样本数据矩阵。其中第i个样品p个变量的观测值可以记为向量：

xi=(xi1,xi2,…xip)Tx11…x1f….x1p…………xi1…xif…xip…………xn1…xnf….xnp目前十九页\总数一百三十九页\编于十四点

由于各变量表示样品的各种性质，往往使用不同的度量单位，其观测值也可能相差十分悬殊。这样，绝对值大的变量其影响可能会湮没绝对值小的变量，使后者应有的作用得不到反映。为了确保各变量在分析中的地位相同，往往需要对数据进行标准化变换。目前二十页\总数一百三十九页\编于十四点

标准化测量------给所有属性相同的权值而在一些应用中，用户会有意识地赋予某些属性更大权值以突出其重要性。例如：在对候选篮球选手进行聚类分析时，可能就会给身高属性赋予更大的权值。

目前二十一页\总数一百三十九页\编于十四点常用的标准化手段有:标准差标准化极差标准化极差正轨化如标准差标准化分两步目前二十二页\总数一百三十九页\编于十四点（1）计算绝对偏差均值sj

sj=其中，xlj，X2j，…，xnj是变量j的n个测量值，为变量j的均值；也就是:

＝目前二十三页\总数一百三十九页\编于十四点（2）计算标准化测量值（z-分量）

zij=

其中，绝对偏差均值sj要比标准偏差j更为鲁棒(对含有噪声数据而言)。

目前二十四页\总数一百三十九页\编于十四点2、差异矩阵差异矩阵是一个对象-对象结构。它存放n个对象彼此之间所形成的差异。一般采用nn矩阵表示

(6.2)

0d(2,1)0对称d(3,1)d(3,2)0

…………d(n,1)d(n,2)…….0目前二十五页\总数一百三十九页\编于十四点

其中，d(i，j)表示对象i和对象j之间的差异(或不相似程度)。通常d(i，j)为一个非负数，当对象i和对象j非常相似或彼此“接近”时，该数值接近0，该数值越大，就表示对象i和对象j越不相似。

目前二十六页\总数一百三十九页\编于十四点许多聚类算法都是基于差异矩阵进行聚类分析的。如果数据是以数据矩阵形式给出的，就需要先转换为差异矩阵，才能利用聚类算法进行处理。目前二十七页\总数一百三十九页\编于十四点3、基于数值型数据的差异矩阵计算在标准化之后，或在无需标准化的特定应用中，由数值所描述对象之间的差异(或相似)程度可以通过计算相应两个对象之间距离来确定。最常用的距离计算公式就是欧氏距离具体公式内容如下：

目前二十八页\总数一百三十九页\编于十四点

d(i,j)=[(|xi1-xj1|2+|xi2-xj2|2+…+|xip-xjp|2]1/2(6.3)-----------欧氏距离其中，i=(xi1,xi2,….xip)

j=(xj1,xj2,….xjp)

分别表示一个P维数据对象另一个常用的距离计算方法就是Manhattan距离，它的具体计算公式定义如下：目前二十九页\总数一百三十九页\编于十四点

d(i，,j)＝|xi1-xj1|+|xi2-xj2|+…+|xip-xjp|(6.4)---------------Manhattan距离欧氏距离和Manhattan距离均满足距离函数的有关数学性质(要求)：d(i，j)≥0，表示对象之间距离为非负数的一个数值。·d(i，j)＝0，表示对象自身之间距离为零。，d(i，j)＝d(j，i)，表示对象之间距离是对称函数。d(i，j)≤d(i，h)+d(h，j)，表示对象自身之间距离满足“两边之和不小于第三边”的性质目前三十页\总数一百三十九页\编于十四点相似性度量

例：对于一个4维向量

X1＝｛1,0,1,0｝

X2＝｛2,1,-3,-1｝，这些距离的度量标准L1（X1，X2）＝1+1+4+1＝7，L2（X1，X2）＝（1+1+16+1）1/2＝4.36L3（X1，X2）＝（1+1+64+1）1/3＝4.06。Lk（Xi，Xj）＝（k）1/k目前三十一页\总数一百三十九页\编于十四点

Minkowski距离:

是欧式距离和Manhattan距离的一个推广；计算公式如下：d(i，j)＝[(|xi1-xj1|q+|xi2-xj2|q+…+|xip-xjp|q]1/q(6.5)

其中，q为一个正整数，当q＝1时，它代表Manhattan距离计算公式；当q二2时，它代表欧氏距离计算公式。可以为每个变量赋予一个权值，以表示其所代表属性的重要性还有契比雪夫距离、马氏距离等目前三十二页\总数一百三十九页\编于十四点两个对象间的相似系数也可有多种定义形式如：

夹角余弦法相关系数法等

cov(x,y)))/D(x)D(y)=E(x-E(x))(y-E(y))/D(x)D(y)

目前三十三页\总数一百三十九页\编于十四点4、其它类型的变量相似性值（1）二值变量一个二值变量仅取0或1值，其中0代表(变量所表示的)状态不存在；1代表相应的状态存在。给定变量smoker，它描述了一个病人是否吸烟情况。如：smoker为1表示病人吸烟，若smoker为0，表示病人不吸烟。如果按照数值变量对二值变量进行处理，常会导致错误的聚类分析结果产生。因此需要采用特定方法计算二值变量所描述对象间的差异(程度)目前三十四页\总数一百三十九页\编于十四点计算方法:

根据二值数据计算差异矩阵；如果认为所有的二值变量的权值均相同，那么就能得到一个22条件表，如下图6．1所示。目前三十五页\总数一百三十九页\编于十四点对象j

对象i

1

0合计

1

q

r

q+r

0

s

t

S+t合计

q+s

r+t

p图6.1目前三十六页\总数一百三十九页\编于十四点表中q表示在对象i和对象j中均取1的二值变量个数，r表示在对象i取1而在对象j中取0的二值变量个数，s表示在对象i中取0而在对象j中取1的二值变量个数,t表示在对象i中取i取0而在对象j中取0的二值变量个数二值变量的总个数为p，那么就有p＝q+r+s+t目前三十七页\总数一百三十九页\编于十四点

如果一个二值变量取0或1所表示的内容同样重要，那么该二值变量就是对称的。如“性别”就是对称变量，因为它究竟是用0还是用1来(编码)表示“男”，“女”并不重要。同样的基于对称二值变量所计算相应的相似(或差异)性称为不变相似性（invariantsimilarity)，因为无论如何对相应二值变量进行编码并不影响到它们相似(或差异)性的计算结果。目前三十八页\总数一百三十九页\编于十四点对于不变相似性(计算)，最常用的描述对象i和对象j之间差异(程度)参数是简单匹配关系数，定义:d(i,j)=(r+s)/(q+r+s+t)(7-9)目前三十九页\总数一百三十九页\编于十四点

如果一个二值变量取0或1所表示内容的重要性是不一样的，那么该二值变量就是非对称的。例如，一个疾病disease-的测试结果可描述为positive或negative。显然这两个(输出)结果的重要性是不一样的、通常将少见的情况用l来表示

(如：HIVpositive)，而将其它情况用0来表示(HIVnegative)目前四十页\总数一百三十九页\编于十四点

给定两个非对称二值变量，如果它们认为取1值比取0值所表示的情况更重要，那么，这样的二值变量就称为是单性的（好象一个状态），最常用的描述对象i和j的差异(程度)参数就是Jaccard相关系数，具体定义:d(i,j)=(r+s)/(q+r+s)(7-10)Sim(i,j)=1-d(i,j)=q/(q+r+s)(Jaccard)目前四十一页\总数一百三十九页\编于十四点

ex7．2二值变量的差异性。假设一个病人记录表如表7-2所示，表中所描述的属性(变量)分别为:name，gender，fever，cough，test-1，test-2，test-3和test-4

其中，name作为(病人)对象的标识，gender(性别)是一个对称二值变量。其它变量则均为非对称变量。目前四十二页\总数一百三十九页\编于十四点

表6.1包含许多二值属性的关系数据表示意描述namegenderfevercoughtest-1test-2test-3test-4Jack

MY(1)N(0)P(1)N(0)N(0)N(0)Mary

FY(1)N(0)P(1)N(0)P(1)N(0)Jim

MY(1)P(1)N(0)N(0)N(0)N(0)…..……….………….目前四十三页\总数一百三十九页\编于十四点对于非对称属性（变量）值，将Y和P设为1，N设为0。根据非对称属性（变量）计算不同对象（病人）之间的距离（差异性），就可利用Jaccard相关系数计算公式（Jaccard）进行目前四十四页\总数一百三十九页\编于十四点

d(Jack,Mary)=(0+1)/(2+0+1)=0.33d(Jack,Jim)=(1+1)/(1+1+1)=0.67d(Jim,Mary)=(1+2)/(1+1+2)=0.75

由于Jim和Mary之间的距离最大，因此不大可能得的是相似病，而Jack,Mary之间的距离最小，因此可能得的是相似病目前四十五页\总数一百三十九页\编于十四点（2）分类变量（符号变量）符号变量是二值变量的一个推广。符号变量可以对两个以上的状态进行描述。例如：地图颜色map_color变量就是一个符号变量，它可以表示五种状态，即红、绿、篮、粉红和黄色。设一个符号变量所取状态个数为M，其中的状态可以用字母、符号，或一个整数集合来表示，如：1，2，…，M。这里整数仅仅是为了方便数据处理而采用的，并不表示任何顺序关系。目前四十六页\总数一百三十九页\编于十四点

对于分类变量，最常用的计算对象i和对象j之间差异(程度)的方法就是简单匹配方法。它的具体定义描述如公式(7-12)所示

d(i,j)=(p-m)/p（7-12)

其中，m表示对象i和对象j中取同样状态的符号变量个数(匹配数)，p为所有的符号变量个数,为增强m的作用，可以给它赋予一定的权值．

目前四十七页\总数一百三十九页\编于十四点(3)序数变量（顺序变量）一个离散顺序变量与一个符号变量相似，不同的是(对应M个状态的)M个顺序值是具有按照一定顺序含义的。例如：专业等级(描述)就是顺序变量，它是按照助教、讲师、副教授和教授的顺序进行排列的。一个连续顺序变量看上去就像一组未知范围的连续数据，但它的相对位置要比它的实际数值有意义得多。例如，在足球比赛中，一个球队排列名次常常要比它的实际得分更为重要。目前四十八页\总数一百三十九页\编于十四点顺序变量的数值常常是通过对数值(变量)的离散化而获得的，也就是通过将取值范围分为有限个组而得到的。一个顺序变量可以映射到一个等级(rank)集合上。如：若一个顺序变量f包含Mf个状态，那么这些有序的状态就映射为1，2，…，Mf的等级。目前四十九页\总数一百三十九页\编于十四点

假设变量f为一组描述n个对象顺序变量中的一个。涉及变量f的差异程度计算:(1)第i个对象的f变量值标记为xif，变量f有Mf个有序状态，可以利用等级1，2，…，Mf分别替换相应的xif，得到相应的rif，rif

属于{1，2，…，Mf}。

(2)将每个顺序变量的取值范围映射到[0，1]区间，以便使每个变量的权值相同。目前五十页\总数一百三十九页\编于十四点可以通过将第i个对象中的第f个变量的rif

用以下所计算得到的值来替换：

zif=(rif–1)/(Mf-1)(7-13)

这时可以利用所介绍有关间隔数值变量的任一个距离计算公式，来计算用顺序变量描述的对象间距离，其中用zif来替换第i个对象中的变量f值。目前五十一页\总数一百三十九页\编于十四点(4)比例标度变量

P258目前五十二页\总数一百三十九页\编于十四点(5)混合类型变量

P259目前五十三页\总数一百三十九页\编于十四点(6)向量对象

P260目前五十四页\总数一百三十九页\编于十四点6．4主要聚类方法需要根据应用所涉及的数据类型、聚类的目的以及具体应用要求来选择合适的聚类算法。如果利用聚类分析作为描述性或探索性的工具，那么就可以使用若干聚类算法对同一个数据集进行处理以观察可能获得的有关(数据特征)描述。

目前五十五页\总数一百三十九页\编于十四点一.聚类的特征与聚类间的距离聚类的数学含义:

设G为元素的集合，共有m个元素，记为gi，i=1,2…m,

另外给定一个阈值T>0,则若G中任意两个元素gi和gj之间的距离不大于阈值，即有dij<=T,则称G为类目前五十六页\总数一百三十九页\编于十四点若将类G的元素gi视为随机向量Xi,则可用以下特征来描述类：1、类的重心----各元素的均向量2、类的直径DG=也可定义为类中各元素至类中心的欧氏距离之和目前五十七页\总数一百三十九页\编于十四点二、分层聚类法

聚集法

先将所有研究对象都各自算作一类，将最“靠近”的首先进行聚类，再将这个类和其他类中最“靠近”的结合，继续合并直到所有对象都综合成一类或满足一个阈值条件为止分割法先将所有研究对象看成一大类，然后割成两类，使一类中的对象尽可能“远离”另一类的对象；再将每一类继续这样分割，直到每个对象自成一类或满足一个阈值条件为止

目前五十八页\总数一百三十九页\编于十四点1、最短距离法又称单连接法或最近邻连接法基本思想：类之间的距离用从两个类中抽取的每对样本的最小距离作为距离度量，一旦最近的两个类的距离超过某个任意给定的阈值，算法就自动结束。

目前五十九页\总数一百三十九页\编于十四点类间的距离:D{1,2,3,4}{5,6,7}=min{d15,d16,d17,d25,d26,d27,d35,d36,d37,d45,d46,d47}=d37.1.2.4.3

.5.7.6目前六十页\总数一百三十九页\编于十四点假定5个对象间的距离如下表所示，试用最短距离法聚类并画出树形图编号1234512345004045471550目前六十一页\总数一百三十九页\编于十四点解：先将五个对象都分别看成一个类，由表看出最靠近的两个类是2和5

将2和5合并成一个新类{2，5}

再求{2，5}和1，3，4之间的距离

d{2,5}1=min{d21,d51}=min{6,7}=6d{2,5)3=min{d23,d53}=min{4,5}=4d{2,5)4=min{d24,d54}=min{4,5}=4编号{2,5}134{2,5}134004204350目前六十二页\总数一百三十九页\编于十四点在这4个类中，最靠近的两个类是1和3，合并成{1，3}，再求{1，3}到{2，5}和4的距离d{1,3}{2,5}=min{d1{2,5},d3{2,5}}=4d{1,3}4=min{d14,d34}=3编号{2,5}{1,3}4{2,5}{1,3}4040430目前六十三页\总数一百三十九页\编于十四点编号{2,5}{1,3,4}{2,5}{1,3,4}040目前六十四页\总数一百三十九页\编于十四点

最短距离的树形图

123425134目前六十五页\总数一百三十九页\编于十四点

先将五个样本都分别看成是一个簇，最靠近的两个簇是3和4，因为他们具有最小的簇间距离

D（3，4）=5.0。第一步：合并簇3和4，得到新簇集合1,2,（34）,5

练习一单连接算法(最短距离)目前六十六页\总数一百三十九页\编于十四点

更新距离矩阵：

D(1,(34))=min(D(1,3),D(1,4))=min(20.6,22.4)=20.6;D(2,(34))=min(D(2,3),D(2,4))=min(14.1,11.2)=11.2;D(5,(34))=min(D(3,5),D(4,5))=min(25.0,25.5)=25.0.

原有簇1,2,5间的距离不变，修改后的距离矩阵如图所示，在四个簇1,2,(34),5中，最靠近的两个簇是1和5，它们具有最小簇间距离D（1,5）＝7.07。单连接算法目前六十七页\总数一百三十九页\编于十四点

单连接算法目前六十八页\总数一百三十九页\编于十四点

单连接算法单连接树目前六十九页\总数一百三十九页\编于十四点

2、最长距离法又称完全连接法或最远紧邻连接法与最短距离的聚类方法相同区别:类间的距离定义为两类中元素之间距离最大者

目前七十页\总数一百三十九页\编于十四点类间的距离:D{1,2,3,4}{5,6,7}=max{d15,d16,d17,d25,d26,d27,d35,d36,d37,d45,d46,d47}=d16.1.2.4.3

.5.7.6目前七十一页\总数一百三十九页\编于十四点例6.4

假定5个对象间的距离如下表所示，试用最长距离法聚类并画出树形图编号1234512345004045471550目前七十二页\总数一百三十九页\编于十四点解：先将五个对象都分别看成一个类，由表看出最靠近的两个类是2和5

也是将2和5合并成一个新类{2，5}

再求{2，5}和1，3，4之间的距离

d{2,5}1=max{d21,d51}=max{6,7}=7d{2,5)3=min{d23,d53}=max{4,5}=5d{2,5)4=min{d24,d54}=max{4,5}=5编号{2,5}134{2,5}1340705

205350目前七十三页\总数一百三十九页\编于十四点在这4个类中，最靠近的两个类是1和3，合并成{1，3}，编号{2,5}134{2,5}1340705

205350目前七十四页\总数一百三十九页\编于十四点再求{1，3}到{2，5}和4的距离d{1,3}{2,5}=max{d1{2,5},d3{2,5}}=7d{1,3}4=max{d14,d34}=5编号{2,5}{1,3}4{2,5}{1,3}4070550此时:由于两个距离都为5d{1,3}4=5d{2,5}4=5可合并{1,3}和4为{1,3,4}也可合并{2,5}和4为{2,5,4}目前七十五页\总数一百三十九页\编于十四点编号{2,5}{1,3,4}{2,5}{1,3,4}070编号{2,5,4}{1,3}{2,5,4}{1,3}070目前七十六页\总数一百三十九页\编于十四点

最长距离的树形图(a)

123425134目前七十七页\总数一百三十九页\编于十四点

最长距离的树形图(b)

123425413目前七十八页\总数一百三十九页\编于十四点3、中间距离法如假定在聚类的过程中两个类G1和G2合并成一个新类

GN=(G1,G2).则GN和其它任一类G3的距离可定义为G1G2G3三角形中线的平方G3G1G2GN类间距离dG3Gn=d2=1/2[dG3G12+dG3G22

-

(1/2)

dG1G22]注意:中间距离进行聚类时,一般都采用距离的平方目前七十九页\总数一百三十九页\编于十四点例6.5

假定5个对象间的距离如下表所示，试用中间距离法聚类并画出树形图编号1234512345004045471550目前八十页\总数一百三十九页\编于十四点编号12345123450360416091625049125250<1>先把原距离平方目前八十一页\总数一百三十九页\编于十四点解:还是先将{2,5}合并,然后计算{2,5}和1,3,4的距离d{2,5}12=1/2[d212+d512

-

(1/2)

d252]=42.25d{2,5}32=20.25d{2,5}42=20.25编号{2,5}134{2,5}134042.25020.254020.259250<2>目前八十二页\总数一百三十九页\编于十四点编号{2,5}{1,3}4{2,5}{1,3}4030.25

020.25160<3>目前八十三页\总数一百三十九页\编于十四点编号{2,5}{1,3,4}{2,5}{1,3,4}021.250<4>目前八十四页\总数一百三十九页\编于十四点4、重心法两个类之间的距离定义为两类重心间的距离

5、类平均法

两个类之间的距离定义为两类中元素两两之间的平均距离目前八十五页\总数一百三十九页\编于十四点前面是基于距离在对变量进行聚类时,一般先求出变量间的相似系数,按照相似系数越大,两个变量越相似的原则聚类,根据分层聚类的思想,聚类过程完全相似目前八十六页\总数一百三十九页\编于十四点下表是24名优秀运动员的七项全能项目得分间的相关系数.对这7项指标进行聚类分析编号x1x2x3x4x5x6x7x1x2x3x4x5x6x71.000.44981.000.6838.46661.000.8466.3296.56751.000.8113.5420.5943.81121.000.3214.2154.6896.3143.32761.000.5706.1498.3726.6790.4957.05561.000目前八十七页\总数一百三十九页\编于十四点改进的层次聚类BIRCH是一个综合的层次聚类方法，它引入了两个概念：聚类特征和聚类特征树（CF树）CURE方法采用了一种新颖的层次聚类算法，该算法选择基于重心和基于代表对象方法之间的中间策略。ROCK方法是一个可选的凝聚的层次聚类算法，适用于分类属性。Chameleon（变色龙）方法是一个在层次聚类中采用动态模型的层次聚类算法目前八十八页\总数一百三十九页\编于十四点三、划分方法（动态聚类法）

最常用也是最知名的划分方法就是k-means算法和k-medoids算法，

1、k-means算法

算法7．1根据聚类中的均值进行聚类划分的k-means算法。输入：聚类个数k，以及包含n个数据对象的数据库。输出：满足方差最小标准的k个聚类。

目前八十九页\总数一百三十九页\编于十四点处理流程：

(1)从n个数据对象任意选择k个对象作为初始聚类中心。

(2)使用欧氏距离将剩余实例赋给距离它们最近的簇中心

(3)使用每簇中的实例计算每个簇对象的均值(中心对象)，计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行分类。

(4)重新计算每个(有变化)聚类的均值(中心对象)，直至新平均值等于上次迭代的平均值，算法结束。

目前九十页\总数一百三十九页\编于十四点

如

:

假设空间数据对象分布如图(a)所示，设是k＝3，也就是需要将数据集划分为3份(聚类)。

目前九十一页\总数一百三十九页\编于十四点根据算法6．1，从数据集中任意选择三个对象作为初始聚类中心(图(a)中这些对象被标上了“+”)，其余对象则根据与这三个聚类中心(对象)的距离，根据最近距离原则，逐个分别聚类到这三个聚类中心所代表的(3个)聚类中，由此获得了如图(a)所示的三个聚类(以虚线圈出)目前九十二页\总数一百三十九页\编于十四点

在完成第一轮聚类之后，各聚类中心发生了变化。继而更新3个聚类的聚类中心(图(b)中这些对象被标上了“十”)，也就是分别根据各聚类中的对象重新计算相应聚类的(对象)均值。根据所获得的3个新聚类中心，以及各对象与这三个聚类中心的距离，(根据最近距离原则)对所有对象进行重新归类。有关变化情况如图(b)所示(已用粗虚线圈出)。目前九十三页\总数一百三十九页\编于十四点图6.2目前九十四页\总数一百三十九页\编于十四点

再次重复上述过程就可获得如图(c)所示的聚类结果(已用实线圈出)，这时由于各聚类中的对象(归属)已不再变化，整个聚类结束。

目前九十五页\总数一百三十九页\编于十四点例6.6k-means算法举例实例xy1234561.01.02.02.03.05.01.54.51.53.52.56.0目前九十六页\总数一百三十九页\编于十四点Step1:设Ｋ＝2,算法任意选择两个点作为初始簇中心，假设算法选择实例１作为第一个簇的中心，即Ｃ１＝（1.0,1.5)实例（２.0,1.5)作为第二个簇的中心，即Ｃ２＝（2.0,1.5)第二步，第一次迭代，分别计算样本实例到C1，C2的欧氏距离：Distance(C1,1)=0.00Distance(C2,1)=1.00Distance(C1,2)=3.00Distance(C2,2)=3.16Distance(C1,3)=1.00Distance(C2,3)=0.08Distance(C1,4)=2.24Distance(C2,4)=2.00Distance(C1,5)=2..24Distance(C2,5)=1.41Distance(C1,6)=6.02Distance(C2,6)=5.41目前九十七页\总数一百三十九页\编于十四点确定C1，C2C1包含实例1(1.0,1.5)和2(1.0，4.5)C2包含实例3，4，5，6Step3：重新计算每个簇的中心对于簇C1：x=(1.0+1.0)/2=1.0y=(1.5+4.5)/2=3.0对于簇C2：x=(2.0+2.0+3.0+5.0)/4=3.0Y=(1.5+3.5+2.5+6.0)/4=3.375因此新的簇中心为：C1=(1.0,3.0)C2=(3.0,3.375)Step4:进行第二次迭代：目前九十八页\总数一百三十九页\编于十四点Distance(C1,1)=1.50Distance(C2,1)=2.74Distance(C1,2)=1.50Distance(C2,2)=2.29Distance(C1,3)=1.80Distance(C2,3)=2.125Distance(C1,4)=1.12Distance(C2,4)=1.01Distance(C1,5)=2..06Distance(C2,5)=0.875Distance(C1,6)=5.00Distance(C2,6)=3.30此时C1包含实例1,2,3C2包含实例4,5,6Step5:对每个簇重新计算新的中心，可得到：

C1=（1.33,2.50)C2=(3.33,4.00)继续直到类中心不再发生变化目前九十九页\总数一百三十九页\编于十四点

对于初始中心的每种选择，最后都会得到不同的簇配置。这是K-means算法的通病，也就是说：尽管算法能确保实例聚类到一个稳定的状态，但不能保证最佳稳定性。

K-means算法的最优聚类：实例到它们对应簇中心的误差平方和最小。对于给定K值，要找到一个最优聚类，必须根据初始中心的不同选择来重复执行算法。

目前一百页\总数一百三十九页\编于十四点例如，对上表重复应用K-means算法而获得的三类聚类结果：输出结果簇中心簇点均方差

1(2.67,4.67)

2,4,614.50(2.00,1.83)

1,3,5

2(1.5,1.5)

1,315.94(2.75,4.125)2,4,5,6

3(1.8,2.7)1,2,3,4,59.60(5,6)6目前一百零一页\总数一百三十九页\编于十四点k－means聚类算法练习坐标表示5个点｛X1,X2,X3,X4,X5｝作为一个聚类分析的二维样本：X1＝（0,2），X2＝（0,0），X3＝（1.5,0），X4＝（5,0），X5＝（5,2）。假设要求的簇的数量k=2。第1步：由样本的随机分布形成两个簇：C1＝｛X1,X2,X4｝和C2＝｛X3,X5｝。这两个簇的质心M1和M2是：M1＝｛(0+0+5)/3,(2+0+0)/3｝＝｛1.66，0.66｝；M2＝｛（1.5+5）/2，（0+2）/2｝＝｛3.25，1.00｝；目前一百零二页\总数一百三十九页\编于十四点基于质心的k－means聚类算法样本初始随机分布之后，方差是：

e12=[(0-1.66)2+(2-0.66)2]+[(0-1.66)2+(0-0.66)2]+[(5-1.66)2+(0-0.66)2]=19.36；

e22=8.12；总体平方误差是：E2＝e12+e22＝19.36+8.12＝27.48（公式）目前一百零三页\总数一百三十九页\编于十四点基于质心的k－means聚类算法第2步：取距离其中一个质心（M1或M2）最小的距离分配所有样本，簇内样本的重新分布如下：d(M1,X1)=(1.662+1.342)1/2=2.14d(M2,X1)=3.40==>X1∈C1；d(M1,X2)=1.79和d(M2,X2)=3.40==>X2∈C1d(M1,X3)=0.83和d(M2,X3)=2.01==>X3∈C1d(M1,X4)=3.41和d(M2,X4)=2.01==>X4∈C2d(M1,X5)=3.60和d(M2,X5)=2.01==>X5∈C2新簇C1＝｛X1,X2,X3｝和C2＝｛X4,X5｝目前一百零四页\总数一百三十九页\编于十四点基于质心的k－means聚类算法第3步：计算新的质心：M1＝｛0.5，0.67｝；M2＝｛5.0，1.0｝。相应的方差及总体平方误差分别是：e12＝4.17；e22＝2.00；E＝6.17；可以看出第一次迭代后，总体误差显著减小（从值27.48到6.17）。在这个简单的例子中，第一次迭代同时也是最后一次迭代，因为如果继续分析新中心和样本间的距离，样本将会全部分给同样的簇，不将重新分配，算法停止。目前一百零五页\总数一百三十九页\编于十四点

k-means算法复杂度为O(nkt),因而它在处理大数据库时也是相对有效的(具有可扩展性)。这里n为对象个数，k为聚类个数，t为循环次数。目前一百零六页\总数一百三十九页\编于十四点

但是k-means算法只适用于聚类均值有意义的情况。因此在某些应用中，诸如：数据集包含符号属性时，直接应用k-means算法就有困难了。

k-means算法另一个缺点就是用户须事先指定聚类个数k。此外，k-means算法对噪声和异常数据也很敏感，因为这类数据可能会影响到类的均值(计算结果)。目前一百零七页\总数一百三十九页\编于十四点

k-means算法还有一些变化(版本)。它们主要在初始k个聚类中心的选择、差异程度计算和聚类中心均值的计算方法等方面有所不同。

目前一百零八页\总数一百三十九页\编于十四点

数据挖掘的内容经常含有离散数据，传统的方法是转换离散数据为数值值，经常得不出有意义的结果

k-modes算法去除了这个限制，并在保留k-means算法效率的同时将应用范围扩大到离散数据。与k-means算法相比，k-modes算法使用了不同的非相似性度量以及一个基于频率的方式对模式更新

目前一百零九页\总数一百三十九页\编于十四点

非相似性度量：设X，Y是由m个离散属性描述的两个离散对象，X，Y之间的非相似性度量可用两个对象的对应的属性离散值的总不匹配量来定义。

d(X,Y)=（xj,yj)（xj,yj)=0xi=yj1xiyj目前一百一十页\总数一百三十九页\编于十四点

将k-means算法和k-modes算法结合到一起，就可以对采用数值量和符号量描述对象进行聚类分析，从而构成了k-prototypes算法。目前一百一十一页\总数一百三十九页\编于十四点

2．k-medoids算法

k-means算法对异常数据很敏感。

medoid设置一个参考点代替k-means算法中的各聚类的均值(作为聚类中心--medoid)。从而可以根据各对象与各参考点之间的距离(差异性)之和最小化的原则，继续应用划分方法。目前一百一十二页\总数一百三十九页\编于十四点

基本策略：首先任意为每个聚类找到一个代表对象(medoid)而确定n个数据对象的k个聚类，(也需要循环进行)其它对象则根据它们与这些聚类代表的距离分别归属到各相应聚类中(仍然是最小距离原则)。如果替换一个聚类代表能够改善所获聚类质量的话，用一个新对象替换老聚类对象。

目前一百一十三页\总数一百三十九页\编于十四点

基于：各对象与其聚类代表间距离的成本函数来对聚类质量进行评估。为了确定任一个非聚类代表对象orandom是否可以替换当前一个聚类代表oj需要根据以下四种情况对各非聚类代表对象p进行检查。目前一百一十四页\总数一百三十九页\编于十四点

(1)如图7-4(a)所示，若对象p当前属于oj(所代表的聚类)，且如果用orandom

替换oj

作为新聚类代表，而p更接近其它oi，则将p归类到oi(所代表的聚类)中。

(2)如图7-4(b)所示，若对象P当前属于oj(所代表的聚类)，且如果用orandom

替换oj

作为新聚类代表，而p就更接近orandom

，那么就将p归类到orandom(所代表的聚类)中。目前一百一十五页\总数一百三十九页\编于十四点6-3目前一百一十六页\总数一百三十九页\编于十四点

(3)如图7-4(a)所示，若对象p当前属于oi(所代表的聚类)(ij)，且如果用orandom

替换oj

作为新聚类代表，而p仍最接近oi，那么p的归类不发生变化。

(4)如图7-4(b)所示，若对象p当前属于oi(所代表的聚类)(ij)，且如果用orandom

替换oj

作为新聚类代表，而p就更接近orandom

，那么就将p归类到orandom(所代表的聚类)中。目前一百一十七页\总数一百三十九页\编于十四点6.4目前一百一十八页\总数一百三十九页\编于十四点

图7-3和图7-4分别示意描述了上述k-medoids聚类算法的四种主要处理情况。每次对对象进行重新归类，都会使得构成成本函数的方差发生变化。因此，成本函数能够计算出聚类代表替换前后的方差变化。通过替换不合适的代表来使距离方差发生变化的累计就构成了成本函数的输出值。目前一百一十九页\总数一百三十九页\编于十四点替换规则

(1)若整个输出成本为负值，那么就用Orandom替换oj，以便能够减少实际的方差E。(2)若整个输出成本为正值，那么就认为当前的oj是可接受的，本次循环就无需变动。目前一百二十页\总数一百三十九页\编于十四点

算法7．2

根据聚类的中心对象(聚类代表)进行聚类划分的k-medoids算法。

输入：聚类个数k，以及包含n个数据对象的数据库。输出：满足基于各聚类中心对象的方差最小标准的k个聚类。

目前一百二十一页\总数一百三十九页\编于十四点处理流程：

(1)从n个数据对象任意选择k个对象作为初始聚类(中心)代表。

(2)循环(3)到(5)直到每个聚类不再发生变化为止。

(3)依据每个聚类的中心代表对象，以及最小距离重新对相应对象进行划分。

(4)任意选择一个非中心对象Orandom；计算其与中心对象oj交换的整个成本S。

(5)若S为负值则交换Orandom与oj以构成新聚类的k个中心对象。目前一百二十二页\总数一百三十九页\编于十四点

k-medoids聚类算法比k-means聚类算法在处理异常数据和噪声数据方面更为鲁棒，因为与聚类均值相比，一个聚类中心的代表对象要较少受到异常数据或极端数据的影响。但是前者的处理时间要比后者更大。两个算法都需要用户事先指定所需聚类个数k。目前一百二十三页\总数一百三十九页\编于十四点

PAM(PartitioningAroundMedoids--围绕中心对象进行划分)方法是最初提出的k-medoids聚类算法之一。它在初始选择k个聚类中心对象之后，不断循环对每两个对象(一个为非中心对象，一个为中心对象)进行分析，以便选择出更好的聚类中心代表对象。并根据每组对象分析计算所获得的聚类质量。若一个中心对象oj被替换后导致方差迅速减少，那么就进行替换。对于较大的n与k值这样的计算开销也非常大。

PAM算法的计算复杂性为O(k(n-k)2)

目前一百二十四页\总数一百三十九页\编于十四点像PAM方法这样典型的k-medoids聚类算法，在小数据集上可以工作得很好；但是对于大数据库则处理效果并不理想。为此.目前一百二十五页\总数一百三十九页\编于十四点四.大数据库的划分方法

CLARA是由Kaufman和Rousseeuw为处理大数据量而开发的。CLARA(Cluste—ringLARgeApplication)不是在整个数据集上发现代表对象，而是从数据集的样本中发现代表对象，从而来有效处理