数据挖掘方法聚类分析

数据挖掘方法聚类分析第一页，共六十一页，编辑于2023年，星期三

“物以类聚,人以群分”，科学研究在揭示对象特点及其相互作用的过程中,不惜花费时间和精力进行对象分类，以揭示其中相同和不相同的特征。第二页，共六十一页，编辑于2023年，星期三

聚类分析（ClusterAnalysis）是研究“物以类聚”的一种多元统计方法。国内有人称它为群分析、点群分析、簇群分析、集群分析等。第三页，共六十一页，编辑于2023年，星期三在解剖学研究中，希望能依据骨骼的形状、大小等特征将人类从猿到人分为几个不同的阶段；在临床诊治中，希望能根据耳朵的特征，把正常耳朵划分为几个类别，为临床修复耳缺损时提供参考；在卫生管理学中，希望能根据医院的诊治水平、工作效率等众多指标将医院分成几个类别；在营养学研究中，如何能根据各种运动的耗糖量和耗能量将十几种运动按耗糖量和耗能量进行分类，使营养学家既能对运动员适当的补充能量，又不增加体重。在医学研究中的聚类需求举例：第四页，共六十一页，编辑于2023年，星期三聚类分析的方向：聚类分析(clusteranalysis)是将样本个体或指标变量按其具有的特性进行分类的一种统计分析方法。对样本进行聚类，称为样本(Q型)聚类分析。其目的是将分类不明确的样本按性质相似程度分成若干组，从而发现同类样本的共性和不同类样本间的差异。对指标进行聚类，称为指标（R型）聚类分析。其目的是将分类不明确的指标按性质相似程度分成若干组，从而在尽量不损失信息的条件下，用一组少量的指标来代替原来的多个指标（主成分分析？因子分析？）。第五页，共六十一页，编辑于2023年，星期三在医生医疗质量研究中，有n个医生参加医疗质量评比，每一个医生有k个医疗质量指标被记录。利用聚类分析可以将n个医生按其医疗质量的优劣分成几类，或者把k个医疗质量指标按反映的问题侧重点不同分成几类。在冠心病研究中，观察n个病人的k个观察指标，并利用聚类分析方法分析这n个病人各自属于哪一类别，相似的病人可以采取相似的治疗措施；同时也能将k个指标分类，找出说明病人病情不同方面的指标类，帮助医生更好地全面了解病人病情。例如：第六页，共六十一页，编辑于2023年，星期三聚类分析不同于因素分析：因素分析是根据所有变量间的相关关系提取公共因子；聚类分析是先将最相似的两个变量聚为一小类，再去与最相似的变量或小类合并，如此分层依次进行；聚类分析也不同于判别分析：判别分析是要先知道各种类，然后判断某个案是否属于某一类。第七页，共六十一页，编辑于2023年，星期三聚类分析（聚类）：把总体中性质相近的归为一类，把性质不相近的归为其他类。判别分析（分类）：已知总体分类，判别样本属于总体中的哪一类。第八页，共六十一页，编辑于2023年，星期三问题:如何刻画样本/特征变量间的亲疏关系或相似程度？第九页，共六十一页，编辑于2023年，星期三聚类分析的基本原理聚类分析是一种数值分类方法（即完全是根据数据关系）。要进行聚类分析就要首先建立一个由某些事物属性构成的指标体系，或者说是一个变量组合。入选的每个指标必须能刻画事物属性的某个侧面，所有指标组合起来形成一个完备的指标体系，它们互相配合可以共同刻画事物的特征。所谓完备的指标体系，是说入选的指标是充分的，其它任何新增变量对辨别事物差异无显著性贡献。如果所选指标不完备，则导致分类偏差。

简单地说，聚类分析的结果取决于变量的选择和变量值获取的两个方面。变量选择越准确、测量越可靠，得到的分类结果越是能描述事物各类间的本质区别。第十页，共六十一页，编辑于2023年，星期三聚类分析完全是根据数据情况来进行的。就一个由n个样本、k个特征变量组成的数据文件来说，当对样本进行聚类分析时，相当于对k维坐标系中的n个点进行分组，所依据的是它们的距离；当对变量进行聚类分析时，相当于对n维坐标系中的k个点进行分组，所依据的也是点距。所以距离或相似性程度是聚类分析的基础。点距如何计算呢？拿连续测量的变量来说，可以用欧氏距离平方计算：即各变量差值的平方和。第十一页，共六十一页，编辑于2023年，星期三1.聚类分析的前期准备工作聚类分析是以完备的数据文件为基础的，这一数据文件除观测变量比较完备之外，一般还要求各个观测变量的量纲一致，即各变量取值的数量级一致，否则各变量在描述客观事物某方面特征差异性的作用有被夸大或缩小的可能。所以，聚类分析前要检查各变量的量纲是否一致，不一致则需进行转换，如将各变量均作标准化转换就可保证量纲一致。2.各数据挖掘工具中聚类分析的主要方法第十二页，共六十一页，编辑于2023年，星期三聚类分析的基本思想是认为我们所研究的样本或指标（变量）之间存在着程度不同的相似性（亲疏关系）。于是根据一批样本的多个观测指标，具体找出一些彼此之间相似程度较大的样本（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样本（或指标）又聚合为另一类，关系密切的聚合到一个小的分类单位，关系疏远的聚合到一个大的分类单位，直到把所有样本（或指标）都聚合完毕，把不同的类型一一划分出来，形成一个由小到大的分类系统。最后把整个分类系统画成一张谱系图，用它把所有样本（或指标）间的亲疏关系表示出来。这种方法是最常用的、最基本的一种，称为系统聚类分析。第十三页，共六十一页，编辑于2023年，星期三聚类分析的统计量数据从几何学角度看，上面表中的每一行或每一列都表示了空间中的一个点或一个向量。第十四页，共六十一页，编辑于2023年，星期三1、描述两个样本之间的相似程度:

距离 令Xi=(xi1…xit…xik)是第i个样本观察值，Xj=(xj1…xjt…xjk)是第j个样本观察值，那么，样本Xi和Xj之间的欧氏距离是：* 距离越小，说明两个样本的性质越相似。* 它的取值大小受量纲影响，不稳定。因此，一般使用标准化的距离公式。第十五页，共六十一页，编辑于2023年，星期三令Xs=(x1s…xis…xns)是第s个指标变量，Xt=(x1t…xit…xnt)是第t个指标变量，那么，指标变量Xs和Xt之间的相关系数是：2、描述两个指标变量之间的相似程度：相似系数* 相关系数越大，说明两个指标变量的性质越相似。* 这是一个无量纲统计量。第十六页，共六十一页，编辑于2023年，星期三 令类A和类B中各有a和b个样本，D(i,j)为类A中第i个样本与类B中第j个样本之间的距离；假设D(A,B)为类A和类B之间的距离，那么，常用的几种类间距离定义的方法是：3、度量类与类之间的距离：类间距离1）最短距离法，类间距离等于两类中距离最小的一对样本之间的距离，即，D(A,B)=min{D(i,j)}。2）最长距离法，类间距离等于两类中距离最大的一对样本之间的距离，即，D(A,B)=max{D(i,j)}。第十七页，共六十一页，编辑于2023年，星期三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)}。*类间距离越小，说明两个类内的样品性质越相似。第十八页，共六十一页，编辑于2023年，星期三*4、度量类与类之间的相似系数：类间相似系数 令类A和类B中各有a和b个指标变量，Za和Zb分别是由类A和类B中所有指标变量的线性组合构成的新变量（称为类成分），例如：

Za=a1X1+a2X2Zb=b1X3+b2X4+b3X5

且它们的组合系数使得这两个新变量具有最大的方差，则称Za和Zb之间的相关系数为类A和类B之间的相关系数。说明：类间相似系数越大，说明两个类内的指标变量性质越相似。第十九页，共六十一页，编辑于2023年，星期三举例

第二十页，共六十一页，编辑于2023年，星期三第二十一页，共六十一页，编辑于2023年，星期三第二十二页，共六十一页，编辑于2023年，星期三距离(distance)或称相似度(similarity)两点之间的距离：欧氏距离(Euclideandistance)欧氏距离的平方(squaredEuclideandistance)曼哈顿距离(Manhattandistance;City-Block)A1A2A3第二十三页，共六十一页，编辑于2023年，星期三关于曼哈顿距离

曼哈顿距离——两点在南北方向上的距离加上在东西方上的距离，即D（I，J）=|XI-XJ|+|YI-YJ|。对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离因此曼哈顿距离又称为出租车距离。第二十四页，共六十一页，编辑于2023年，星期三类间距离:单一连接法(singlelinkage)：又称最短距离法。完全连接法(completelinkage)：又称最长距离法。平均连接法(averagelinkage)重心法(centroidmethod)第二十五页，共六十一页，编辑于2023年，星期三ABC第二十六页，共六十一页，编辑于2023年，星期三算法聚类分析算法，不需要事先知道资料该分成几个已知的类型，而可以依照资料间彼此的相关程度来完成分类分群的目的。此法可概分为：分割算法(PartitioningAlgorithms)，层次算法(HierarchicalAlgorithms)，密度型算法(Density-BasedAlgorithms)第二十七页，共六十一页，编辑于2023年，星期三分割算法数据由使用者指定分割成K个集群群组。每一个分割(partition)代表一个集群(cluster)，集群是以最佳化分割标准(partitioningcriterion)为目标，分割标准的目标函数又称为相似函数(similarityfunction)。因此，同一集群的数据对象具有相类似的属性。分割算法中最常见的是k-平均方法（K-means）k-中心点方法（K-medoid）两种方法都是属于启发式(heuristic)第二十八页，共六十一页，编辑于2023年，星期三K-means算法：集群内资料平均值为集群的中心K-means集群算法，因为其简单易于了解使用的特性，对于球体形状(spherical-shaped)、中小型数据库的数据挖掘有不错的成效，可算是一种常被使用的集群算法。1967年由学者J.B.MacQueen所提出，也是最早的组群化计算技术。第二十九页，共六十一页，编辑于2023年，星期三TheK-MeansClusteringMethod

Example012345678910012345678910012345678910012345678910K=2ArbitrarilychooseKobjectasinitialclustercenterAssigneachobjectstomostsimilarcenterUpdatetheclustermeansUpdatetheclustermeansreassignreassign第三十页，共六十一页，编辑于2023年，星期三k-平均算法step1.任意选择k个对象作为初始的类的中心step2.repeatstep3.根据类中文档的平均值,将每个文档

(重新)赋给最相近的类step4.更新类的平均值，step5.until不再发生变化,即没有对象进行被重新分配时过程结束。

第三十一页，共六十一页，编辑于2023年，星期三K-Means特点该算法试图找出使平方误差值最小的k个划分。当结果簇是密集的，而簇与簇之间区分明显时，它的效果较好。算法复杂度O（nkt），其中

t是迭代次数。因此其可扩展性较好，对大数据集处理有较高的效率。算法常以局部最优结束。全局最优要穷举所有可能的划分。缺点：不适合发现非凸面状的簇。不适合大小差别较大的簇。对于噪声和孤立点是敏感的，由于少量的该类数据对平均值产生较大的]影响。第三十二页，共六十一页，编辑于2023年，星期三有多种变形形式k-平均方法有多种变形形式，不同改进在于：初始k个平均值的选择相异度的计算计算类平均值产生较好聚类结果的一个有趣策略：首先用层次聚类方法决定结果簇的个数，并找到初始的聚类然后用迭代重定位来改进聚类结果。第三十三页，共六十一页，编辑于2023年，星期三K-medoid算法K-medoid算法：集群内最接近丛集中心者为集群中心。基本上和K-means类似，不同在于K-means是以集群内各对象的平均值为集群的中心点，而K-medoid是以集群内最接近中心位置的对象为集群的中心点，每一回合都只针对扣除作为集群中心对象外的所有剩余对象，重新寻找最近似的集群中心。第三十四页，共六十一页，编辑于2023年，星期三与K-means算法只有在步骤三计算各个集群中心点的方式略有不同。将步骤三改为随意由目前不是当作集群中心的资料中，选取一欲取代某一集群中心的对象，如果因为集群中心改变，导致对象重新分配后的结果较好(目标函数值较为理想)，则该随意所选取的对象即取代原先的集群中心，成为新的集群中心第三十五页，共六十一页，编辑于2023年，星期三K-medoids

算法第三十六页，共六十一页，编辑于2023年，星期三两种方法有一共同的缺点，就是事先得表示K值为何。K-means对于处理分群数据有明确集中某些地方的情形，有相当不错的成效，而噪声或者独立特行数据的处理，

K-medoid要比K-means来得好。K-means有一个比较大的限制是只适合于数值数据。但从另一个角度而言，

K-medoid相对于K-means而言计算较为复杂烦琐。第三十七页，共六十一页，编辑于2023年，星期三层次算法此法主要是将数据对象以树状的层次关系来看待。依层次建构的方式，一般分成两种来进行：凝聚法(Agglomerative)分散法(Divisive)第三十八页，共六十一页，编辑于2023年，星期三凝聚法(Agglomerative)首先将各个单一对象先独自当成一个丛集，然后再依相似度慢慢地将丛集合并，直到停止条件到达或者只剩一个丛集为止，此种由小量数据慢慢聚集而成的方式，又称为底端向上法(bottomupapproach)。第三十九页，共六十一页，编辑于2023年，星期三凝聚法(Agglomerative)12345第四十页，共六十一页，编辑于2023年，星期三分散法(Divisive)此法首先将所有对象全部当成一个丛集，然后再依相似度慢慢地丛集分裂，直到停止条件到达或者每个丛集只剩单一对象为止，此种由全部数据逐步分成多个丛集的方式，又称为顶端向下法(topdownapproach)。第四十一页，共六十一页，编辑于2023年，星期三密度型算法以数据的密度作为同一集群评估的依据。起始时，每个数据代表一个集群，接着对于每个集群内的数据点，根据邻近区域半径及临界值(threshold)，找出其半径所含邻近区域内的数据点。如果数据点大于临界值，将这些邻近区域内的点全部归为同一集群，以此慢慢地合并扩大集群的范围。如果临界值达不到，则考虑放大邻近区域的半径。第四十二页，共六十一页，编辑于2023年，星期三密度型算法此法不受限于数值资料的问题，可适合于任意形状数据分布的集群问题，也可以过滤掉噪声，较适合于大型数据库及较复杂的集群问题。算法时间的复杂度取决于基本单位的数目多寡，正常状况下，其时间复杂度可在有限的时间内完成。第四十三页，共六十一页，编辑于2023年，星期三密度型算法缺点是邻近区域范围、及门坎值大小的设定；此两参数的设定直接关系此算法的效果。第四十四页，共六十一页，编辑于2023年，星期三通常为了得到比较合理的分类，首先必须采用适当的指标来定量地描述研究对象之间的同构型。常用的指标为〝距离〞。第四十五页，共六十一页，编辑于2023年，星期三使用weka进行聚类分析第四十六页，共六十一页，编辑于2023年，星期三1.选择聚类器（Clusterer）

点击列在窗口顶部的Clusterer栏中的

聚类算法，将弹出一个用来选择新聚类算法的GenericObjectEditor对话框。

第四十七页，共六十一页，编辑于2023年，星期三2.聚类模式

ClusterMode一栏用来决定依据什么来聚类以及如何评价聚类的结果。前三个选项和分类的情形是一样的：Usetrainingset、Suppliedtestset和Percentagesplit

——区别在于现在的数据是要聚集到某个类中，而不是预测为某个指定的类别。第四个模式，Classestoclustersevaluation，是要比较所得到的聚类与在数据中预先给出的类别吻合得怎样。和Classify面板一样，下方下拉框是用来选择作为类别的属性的。在Clustermode之外，有一个Storeclustersforvisualization的勾选框，该框决定了在训练完算法后可否对数据进行可视化。对于非常大的数据集，内存可能成为瓶颈时，不勾选这一栏应该会有所帮助。

第四十八页，共六十一页，编辑于2023年，星期三3.忽略属性

在对一个数据集聚类时，经常遇到某些属性应该被忽略的情况。Ignoreattributes可

以弹出一个小窗口，选择哪些是需要忽略的属性。点击窗口中单个属性将使它高亮显示，

按住SHIFT键可以连续的选择一串属性，按住CTRL键可以决定各个属性被选与否。点

击Cancel按钮取消所作的选择。点击Select按钮决定接受所作的选择。下一次聚类

算法运行时，被选的属性将被忽略。

第四十九页，共六十一页，编辑于2023年，星期三4.学习聚类Cluster面板就像Classify面板那样，有一个Start/Stop按钮，一个结果文本的区

域和一个结果列表。它们的用法都和分类时的一样。右键点击结果列表中的一个条目将弹出一个相似的菜单，只是它仅显示两个可视化选项：Visualizeclusterassignments和Visualizetree。后者在它不可用时会变灰。

第五十页，共六十一页，编辑于2023年，星期三现在我们对前面的“bankdata”作聚类分析，使用最常见的K均值（K-means）算法。下面我们简单描述一下K均值聚类的步骤。

K均值算法首先随机的指定K个簇中心。然后：1)将每个样本分配到距它最近的簇中心，得到K个簇；2)计分别计算各簇中所有样本的均值，把它们作为各簇新的簇中心。重复1)和2)，直到K个簇中心的位置都固定，簇的分配也固定。

第五十一页，共六十一页，编辑于2023年，星期三第五十二页，共六十一页，编辑于2023年，星期三第五十三页，共六十一页，编辑于2023年，星期三第五十四页，共六十一页，编辑于2023年，星期三第五十五页，共六十一页，编辑于2023年，星期三上述K均值算法只能处理数值型的属性，遇到分类型的属性时要把它变为若干个取值0和1的属性。WEKA将自动实施这个分类型到数值型的变换，而且WEKA会自动对数值型的数据作标准化。因此，对于原始数据“bank-data.csv”，我们所做的预处理只是删去属性“id”，保存为ARFF格式后，修改属性“children”为分类型。这样得到的数据文件为“bank.arff”，含300条实例。

用“Explorer”打开刚才得到的“bank.arff”，并切换到“Cluster”。点“Choose”按钮选择“SimpleKMeans”，这是WEKA中实现K均值的算法。点击旁边的文本框，修改“numClusters”为6，说明我们希望把这300条实例聚成6类，即K=6。下面的“seed”参数是要设置一个随机种子，依此产生一个随机数，用来得到K均值算法中第一次给出的K个簇中心的位置。我们不妨暂时让它就为10。

选中“ClusterMode”的“Usetrainingset”，点击“Start”按钮，观察右边“Clustereroutput”给出的聚类结果。也可以在左下角“Resultlist”中这次产生的结果上点右键，“Viewinseparatewindow”在新窗口中浏览结果。

第五十六页，共六十一页，编辑于2023年，星期三结果解释

首先我们注意到结果中有这么一行：

Withinclustersumofsquarederrors:xxxxxxxxx

这是评价聚类好坏的标准，数值越小说明同一簇实例之间的距离越小。也许你得到的数值会不一样；实际上如果把“seed”参数改一下，得到的这个数值就可能会不一样。我们应该多尝试几个seed，并采纳这个数值最小的那个结果。

接下来“Clustercentroids:”之后列出了各个簇中心的位置。对于数值型的属性，簇中心就是它的均值（Mean）；分类型的就是它的众数（Mode），也就是说这个属性上取值为众数值的实例最多。对于数值型的属性，还给出了它在各个簇里的标准差（StdDevs）（需要设置参数为“true”）。

最后的“ClusteredInstances”是各个簇中实例的数目及百分比。

为了观察可视化的聚类结果，我们在左下方“Resultlist”列出的结果上右击，点“Visualizeclusterassignments”。弹出的窗口给出了各实例的散点图。最上方的两个框是选择横坐标和纵坐标，第二行的“color”是散点图着色的依据，默认是根据不同的簇“Cluster”给实例标上不同的颜色。

可以在这里点“Save”把聚类结果保存成ARFF文件。在这个新的ARFF文件中，“instance_number”属性表示某实例的编号，“Cluster”属性表示聚类算法给出的该实例所在的簇。

第五十七页，共六十一页，编辑于2023年，星期三可视化

WEKA的可视化页面可以对当前的关系作二维散点图式的可视化浏览。

1.散点图矩阵

选择了Visualize面板后，会为所有的属性给出一个散点图矩阵，它们会根据所选的class属性来着色。在这里可以改变每个二维散点图的大小，改变各点的大小，以及随机地抖动（jitter）数据（使得被隐藏的点显示出来）。也可以改变用来着色的属性，可以只选择一组属性的子集放在散点图矩阵中，还可以取出数据的一个子样本。注意这些改变只有在点击了Update了按钮之后才会生效。

第五十八页，共六十一页，编辑于2023年，星期三2.选择单独的二维散点图

在散点图矩阵的一个元素上点击后，会弹出一个单独的窗口对所选的散点图进行可视。（前面我们描述了如何在单独的窗口中对某个特定的结果进行可视化——例如分类误差——这里用了相同的可视化控件。）数据点散布在窗口的主要区域里。上方是两个