《数据挖掘方法聚类分析.ppt》由会员分享，可在线阅读，更多相关《数据挖掘方法聚类分析.ppt（61页珍藏版）》请在三一办公上搜索。
1、聚类分析(Cluster Analysis),“物以类聚,人以群分”，科学研究在揭示对象特点及其相互作用的过程中,不惜花费时间和精力进行对象分类，以揭示其中相同和不相同的特征。,聚类分析（Cluster Analysis）是研究“物以类聚”的一种多元统计方法。国内有人称它为群分析、点群分析、簇群分析、集群分析等。,在解剖学研究中，希望能依据骨骼的形状、大小等特征将人类从猿到人分为几个不同的阶段；在临床诊治中，希望能根据耳朵的特征，把正常耳朵划分为几个类别，为临床修复耳缺损时提供参考；在卫生管理学中，希望能根据医院的诊治水平、工作效率等众多指标将医院分成几个类别；在营养学研究中，如何能根据各种运
2、动的耗糖量和耗能量将十几种运动按耗糖量和耗能量进行分类，使营养学家既能对运动员适当的补充能量，又不增加体重。,在医学研究中的聚类需求举例：,聚类分析的方向：,聚类分析(cluster analysis)是将样本个体或指标变量按其具有的特性进行分类的一种统计分析方法。对样本进行聚类，称为样本(Q型)聚类分析。其目的是将分类不明确的样本按性质相似程度分成若干组，从而发现同类样本的共性和不同类样本间的差异。对指标进行聚类，称为指标（R型）聚类分析。其目的是将分类不明确的指标按性质相似程度分成若干组，从而在尽量不损失信息的条件下，用一组少量的指标来代替原来的多个指标（主成分分析？因子分析？）。,在医生
3、医疗质量研究中，有n个医生参加医疗质量评比，每一个医生有k个医疗质量指标被记录。利用聚类分析可以将n个医生按其医疗质量的优劣分成几类，或者把 k个医疗质量指标按反映的问题侧重点不同分成几类。在冠心病研究中，观察n个病人的 k个观察指标，并利用聚类分析方法分析这n个病人各自属于哪一类别，相似的病人可以采取相似的治疗措施；同时也能将k个指标分类，找出说明病人病情不同方面的指标类，帮助医生更好地全面了解病人病情。,例如：,聚类分析不同于因素分析：因素分析是根据所有变量间的相关关系提取公共因子；聚类分析是先将最相似的两个变量聚为一小类，再去与最相似的变量或小类合并，如此分层依次进行；聚类分析也不同于判
4、别分析：判别分析是要先知道各种类，然后判断某个案是否属于某一类。,聚类分析（聚类）：把总体中性质相近的归为一类，把性质不相近的归为其他类。判别分析（分类）：已知总体分类，判别样本属于总体中的哪一类。,问题:,如何刻画样本/特征变量间的亲疏关系或相似程度？,聚类分析的基本原理,聚类分析是一种数值分类方法（即完全是根据数据关系）。要进行聚类分析就要首先建立一个由某些事物属性构成的指标体系，或者说是一个变量组合。入选的每个指标必须能刻画事物属性的某个侧面，所有指标组合起来形成一个完备的指标体系，它们互相配合可以共同刻画事物的特征。所谓完备的指标体系，是说入选的指标是充分的，其它任何新增变量对辨别事物
5、差异无显著性贡献。如果所选指标不完备，则导致分类偏差。简单地说，聚类分析的结果取决于变量的选择和变量值获取的两个方面。变量选择越准确、测量越可靠，得到的分类结果越是能描述事物各类间的本质区别。,聚类分析完全是根据数据情况来进行的。就一个由n个样本、k个特征变量组成的数据文件来说，当对样本进行聚类分析时，相当于对k 维坐标系中的n 个点进行分组，所依据的是它们的距离；当对变量进行聚类分析时，相当于对n维坐标系中的k个点进行分组，所依据的也是点距。所以距离或相似性程度是聚类分析的基础。点距如何计算呢？拿连续测量的变量来说，可以用欧氏距离平方计算：即各变量差值的平方和。,1.聚类分析的前期准备工作,
6、聚类分析是以完备的数据文件为基础的，这一数据文件除观测变量比较完备之外，一般还要求各个观测变量的量纲一致，即各变量取值的数量级一致，否则各变量在描述客观事物某方面特征差异性的作用有被夸大或缩小的可能。所以，聚类分析前要检查各变量的量纲是否一致，不一致则需进行转换，如将各变量均作标准化转换就可保证量纲一致。,2.各数据挖掘工具中聚类分析的主要方法,聚类分析的基本思想是认为我们所研究的样本或指标（变量）之间存在着程度不同的相似性（亲疏关系）。于是根据一批样本的多个观测指标，具体找出一些彼此之间相似程度较大的样本（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样本（或指标）又聚合为另一类，关系
7、密切的聚合到一个小的分类单位，关系疏远的聚合到一个大的分类单位，直到把所有样本（或指标）都聚合完毕，把不同的类型一一划分出来，形成一个由小到大的分类系统。最后把整个分类系统画成一张谱系图，用它把所有样本（或指标）间的亲疏关系表示出来。这种方法是最常用的、最基本的一种，称为系统聚类分析。,聚类分析的统计量,数据,从几何学角度看，上面表中的每一行或每一列都表示了空间中的一个点或一个向量。,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 之间的
8、欧氏距离是：,*距离越小，说明两个样本的性质越相似。*它的取值大小受量纲影响，不稳定。因此，一般使用标准化的距离公式。,令 Xs=(x 1 s x i s x n s)是第 s 个指标变量，Xt=(x 1 t x i t x n t)是第 t 个指标变量，那么，指标变量 Xs和Xt之间的相关系数是：,2、描述两个指标变量之间的相似程度：相似系数,*相关系数越大，说明两个指标变量的性质越相似。*这是一个无量纲统计量。,令类A和类B中各有a和b个样本，D(i,j)为类A中第 i 个样本与类B中第 j 个样本之间的距离；假设D(A,B)为类A和类B之间的距离，那么，常用的几种类间距离定义的方法是：,
9、3、度量类与类之间的距离：类间距离,1）最短距离法，类间距离等于两类中距离最小的一对样本之间的距离，即，D(A,B)=minD(i,j)。2）最长距离法，类间距离等于两类中距离最大的一对样本之间的距离，即，D(A,B)=maxD(i,j)。,3）重心距离法，类间距离等于两类的重心之间的距离，即，D(A,B)=d(Xa,Xb)，其中Xa和Xb分别是类A和类B的重心，即类内所有样本的均值坐标。4）平均距离法，类间距离等于两类中所有样本对之间距离的平均值，即，D(A,B)=sumD(i,j)/(ab)。5）中间距离法，类间距离等于两类中所有样本对之间距离的中间值，即，D(A,B)=medianD(i
10、,j)。,*类间距离越小，说明两个类内的样品性质越相似。,*4、度量类与类之间的相似系数：类间相似系数,令类A和类B中各有a和b个指标变量，Za和Zb分别是由类A和类B中所有指标变量的线性组合构成的新变量（称为类成分），例如：Za=a1 X1+a2 X2 Zb=b1 X3+b2 X4+b3 X5且它们的组合系数使得这两个新变量具有最大的方差，则称Za和Zb之间的相关系数为类A和类B之间的相关系数。,说明：类间相似系数越大，说明两个类内的指标变量性质 越相似。,举例,距离(distance)或称相似度(similarity),两点之间的距离：欧氏距离(Euclidean distance)欧氏距
11、离的平方(squared Euclidean distance)曼哈顿距离(Manhattan distance;City-Block),关于曼哈顿距离,曼哈顿距离两点在南北方向上的距离加上在东西方上的距离，即D（I，J）=|XI-XJ|+|YI-YJ|。对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离因此曼哈顿距离又称为出租车距离。,类间距离:单一连接法(single linkage)：又称最短距离法。完全连接法(complete linkage)：又称最长距离法。平均连接法(average linkage)重心
12、法(centroid method),A,B,C,算法,聚类分析算法，不需要事先知道资料该分成几个已知的类型，而可以依照资料间彼此的相关程度来完成分类分群的目的。此法可概分为：分割算法(Partitioning Algorithms)，层次算法(Hierarchical Algorithms)，密度型算法(Density-Based Algorithms),分割算法,数据由使用者指定分割成K个集群群组。每一个分割(partition)代表一个集群(cluster)，集群是以最佳化分割标准(partitioning criterion)为目标，分割标准的目标函数又称为相似函数(similarit
13、y function)。因此，同一集群的数据对象具有相类似的属性。分割算法中最常见的是k-平均方法（K-means）k-中心点方法（K-medoid）两种方法都是属于启发式(heuristic),K-means算法：集群内资料平均值为集群的中心K-means集群算法，因为其简单易于了解使用的特性，对于球体形状(spherical-shaped)、中小型数据库的数据挖掘有不错的成效，可算是一种常被使用的集群算法。1967年由学者J.B.MacQueen 所提出，也是最早的组群化计算技术。,The K-Means Clustering Method,Example,0,1,2,3,4,5,6,7,
14、8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2Arbitrarily choose K object as initial cluster center,Assign each objects to most similar center,Update the cluster means,Update the cluster means,reassign,reassign,k-平均算法,step1.任意选择k个对象作为初始的类的中心step2.repeatstep3.根据类中文档的平均值,将每个文档(重新)赋给最相近的类step4.更新类的平均值，step5.until 不
15、再发生变化,即没有对象进行被重新分配时过程结束。,K-Means 特点,该算法试图找出使平方误差值最小的k个划分。当结果簇是密集的，而簇与簇之间区分明显时，它的效果较好。算法复杂度O（nkt），其中 t是迭代次数。因此其可扩展性较好，对大数据集处理有较高的效率。算法常以局部最优结束。全局最优要穷举所有可能的划分。缺点：不适合发现非凸面状的簇。不适合大小差别较大的簇。对于噪声和孤立点是敏感的，由于少量的该类数据对平均值产生较大的影响。,有多种变形形式,k-平均方法有多种变形形式，不同改进在于：初始k个平均值的选择相异度的计算计算类平均值产生较好聚类结果的一个有趣策略：首先用层次聚类方法决定结果簇
16、的个数，并找到初始的聚类然后用迭代重定位来改进聚类结果。,K-medoid算法,K-medoid算法：集群内最接近丛集中心者为集群中心。基本上和K-means类似，不同在于K-means是以集群内各对象的平均值为集群的中心点，而K-medoid是以集群内最接近中心位置的对象为集群的中心点，每一回合都只针对扣除作为集群中心对象外的所有剩余对象，重新寻找最近似的集群中心。,与K-means算法只有在步骤三计算各个集群中心点的方式略有不同。将步骤三改为随意由目前不是当作集群中心的资料中，选取一欲取代某一集群中心的对象，如果因为集群中心改变，导致对象重新分配后的结果较好(目标函数值较为理想)，则该随意
17、所选取的对象即取代原先的集群中心，成为新的集群中心,K-medoids算法,两种方法有一共同的缺点，就是事先得表示K值为何。K-means对于处理分群数据有明确集中某些地方的情形，有相当不错的成效，而噪声或者独立特行数据的处理，K-medoid要比K-means来得好。K-means有一个比较大的限制是只适合于数值数据。但从另一个角度而言，K-medoid相对于K-means而言计算较为复杂烦琐。,层次算法,此法主要是将数据对象以树状的层次关系来看待。依层次建构的方式，一般分成两种来进行：凝聚法(Agglomerative)分散法(Divisive),凝聚法(Agglomerative)首先将
18、各个单一对象先独自当成一个丛集，然后再依相似度慢慢地将丛集合并，直到停止条件到达或者只剩一个丛集为止，此种由小量数据慢慢聚集而成的方式，又称为底端向上法(bottom up approach)。,凝聚法(Agglomerative),分散法(Divisive)此法首先将所有对象全部当成一个丛集，然后再依相似度慢慢地丛集分裂，直到停止条件到达或者每个丛集只剩单一对象为止，此种由全部数据逐步分成多个丛集的方式，又称为顶端向下法(top down approach)。,密度型算法,以数据的密度作为同一集群评估的依据。起始时，每个数据代表一个集群，接着对于每个集群内的数据点，根据邻近区域半径及临界值(
19、threshold)，找出其半径所含邻近区域内的数据点。如果数据点大于临界值，将这些邻近区域内的点全部归为同一集群，以此慢慢地合并扩大集群的范围。如果临界值达不到，则考虑放大邻近区域的半径。,密度型算法,此法不受限于数值资料的问题，可适合于任意形状数据分布的集群问题，也可以过滤掉噪声，较适合于大型数据库及较复杂的集群问题。算法时间的复杂度取决于基本单位的数目多寡，正常状况下，其时间复杂度可在有限的时间内完成。,密度型算法,缺点是邻近区域范围、及门坎值大小的设定；此两参数的设定直接关系此算法的效果。,通常为了得到比较合理的分类，首先必须采用适当的指标来定量地描述研究对象之间的同构型。常用的指标为
20、距离。,使用weka进行聚类分析,1.选择聚类器（Clusterer）,点击列在窗口顶部的Clusterer 栏中的聚类算法，将弹出一个用来选择新聚类算法的 GenericObjectEditor 对话框。,2.聚类模式,Cluster Mode 一栏用来决定依据什么来聚类以及如何评价聚类的结果。前三个选项和分类的情形是一样的：Use training set、Supplied test set 和 Percentage split区别在于现在的数据是要聚集到某个类中，而不是预测为某个指定的类别。第四个模式，Classes to clusters evaluation，是要比较所得到的聚类与在
21、数据中预先给出的类别吻合得怎样。和Classify 面板一样，下方下拉框是用来选择作为类别的属性的。在 Cluster mode 之外，有一个 Store clusters for visualization 的勾选框，该框决定了在训练完算法后可否对数据进行可视化。对于非常大的数据集，内存可能成为瓶颈时，不勾选这一栏应该会有所帮助。,3.忽略属性,在对一个数据集聚类时，经常遇到某些属性应该被忽略的情况。Ignore attributes 可以弹出一个小窗口，选择哪些是需要忽略的属性。点击窗口中单个属性将使它高亮显示，按住 SHIFT 键可以连续的选择一串属性，按住 CTRL 键可以决定各个属性
22、被选与否。点击Cancel 按钮取消所作的选择。点击Select 按钮决定接受所作的选择。下一次聚类算法运行时，被选的属性将被忽略。,4.学习聚类,Cluster 面板就像Classify面板那样，有一个Start/Stop 按钮，一个结果文本的区域和一个结果列表。它们的用法都和分类时的一样。右键点击结果列表中的一个条目将弹出一个相似的菜单，只是它仅显示两个可视化选项：Visualize cluster assignments 和Visualize tree。后者在它不可用时会变灰。,现在我们对前面的“bank data”作聚类分析，使用最常见的K均值（K-means）算法。下面我们简单描述一
23、下K均值聚类的步骤。K均值算法首先随机的指定K个簇中心。然后：1)将每个样本分配到距它最近的簇中心，得到K个簇；2)计分别计算各簇中所有样本的均值，把它们作为各簇新的簇中心。重复1)和2)，直到K个簇中心的位置都固定，簇的分配也固定。,上述K均值算法只能处理数值型的属性，遇到分类型的属性时要把它变为若干个取值0和1的属性。WEKA将自动实施这个分类型到数值型的变换，而且WEKA会自动对数值型的数据作标准化。因此，对于原始数据“bank-data.csv”，我们所做的预处理只是删去属性“id”，保存为ARFF格式后，修改属性“children”为分类型。这样得到的数据文件为“bank.arff”
24、，含300条实例。用“Explorer”打开刚才得到的“bank.arff”，并切换到“Cluster”。点“Choose”按钮选择“SimpleKMeans”，这是WEKA中实现K均值的算法。点击旁边的文本框，修改“numClusters”为6，说明我们希望把这300条实例聚成6类，即K=6。下面的“seed”参数是要设置一个随机种子，依此产生一个随机数，用来得到K均值算法中第一次给出的K个簇中心的位置。我们不妨暂时让它就为10。选中“Cluster Mode”的“Use training set”，点击“Start”按钮，观察右边“Clusterer output”给出的聚类结果。也可以在
25、左下角“Result list”中这次产生的结果上点右键，“View in separate window”在新窗口中浏览结果。,结果解释 首先我们注意到结果中有这么一行：Within cluster sum of squared errors:xxxxxxxxx 这是评价聚类好坏的标准，数值越小说明同一簇实例之间的距离越小。也许你得到的数值会不一样；实际上如果把“seed”参数改一下，得到的这个数值就可能会不一样。我们应该多尝试几个seed，并采纳这个数值最小的那个结果。接下来“Cluster centroids:”之后列出了各个簇中心的位置。对于数值型的属性，簇中心就是它的均值（Mean）
26、；分类型的就是它的众数（Mode），也就是说这个属性上取值为众数值的实例最多。对于数值型的属性，还给出了它在各个簇里的标准差（Std Devs）（需要设置参数为“true”）。最后的“Clustered Instances”是各个簇中实例的数目及百分比。为了观察可视化的聚类结果，我们在左下方“Result list”列出的结果上右击，点“Visualize cluster assignments”。弹出的窗口给出了各实例的散点图。最上方的两个框是选择横坐标和纵坐标，第二行的“color”是散点图着色的依据，默认是根据不同的簇“Cluster”给实例标上不同的颜色。可以在这里点“Save”把聚类
27、结果保存成ARFF文件。在这个新的ARFF文件中，“instance_number”属性表示某实例的编号，“Cluster”属性表示聚类算法给出的该实例所在的簇。,可视化,WEKA 的可视化页面可以对当前的关系作二维散点图式的可视化浏览。1.散点图矩阵选择了 Visualize 面板后，会为所有的属性给出一个散点图矩阵，它们会根据所选的class 属性来着色。在这里可以改变每个二维散点图的大小，改变各点的大小，以及随机地抖动（jitter）数据（使得被隐藏的点显示出来）。也可以改变用来着色的属性，可以只选择一组属性的子集放在散点图矩阵中，还可以取出数据的一个子样本。注意这些改变只有在点击了Up
28、date 了按钮之后才会生效。,2.选择单独的二维散点图在散点图矩阵的一个元素上点击后，会弹出一个单独的窗口对所选的散点图进行可视。（前面我们描述了如何在单独的窗口中对某个特定的结果进行可视化例如分类误差这里用了相同的可视化控件。）数据点散布在窗口的主要区域里。上方是两个下拉框选择用来选择打点的坐标轴。左边是用作 x 轴的属性；右边是用作 y 轴的属性。在 x 轴选择器旁边是一个下拉框用来选择着色的方案。它可以根据所选的属性给点着色。在打点区域的下方，有图例来说明每种颜色代表的是什么值。如果这些值是离散的，可以通过点击它们所弹出的新窗口来修改颜色。打点区域的右边有一些水平横条。每一条代表着一个
29、属性，其中的点代表了属性值的分布。这些点随机的在竖直方向散开，使得点的密集程度能被看出来。在这些横条上点击可以改变主图所用的坐标轴。左键点击改变 x 轴的属性；右键点击改变 y 轴的。横条旁边的“X”和“Y”代表了当前的轴用的那个属性（“B”则说明 x 轴和 y 轴都是它）。属性横条的上方是一个标着 Jitter 的游标。它能随机地使得散点图中各点的位置发生偏移，也就是抖动。把它拖动到右边可以增加抖动的幅度，这对识别点的密集程度很有用。如果不使用这样的抖动，几万个点放在一起和单独的一个点看起来会没有区别。,3.选择实例很多时候利用可视化工具选出一个数据的子集是有帮助的。（例如在 classif
30、y 面板的UserClassifier（自定义分类器），可以通过交互式的选取实例来构建一个分类器。）在 y 轴选择按钮的下方是一个下拉按钮，它决定选取实例的方法。可以通过以下四种方式选取数据点：1.Select Instance.点击各数据点会打开一个窗口列出它的属性值，如果点击处的点超过一个，则更多组的属性值也会列出来。2.Rectangle.通过拖动创建一个矩形，选取其中的点。3.Polygon.创建一个形式自由的多边形并选取其中的点。左键点击添加多边形的顶点，右键点击完成顶点设置。起始点和最终点会自动连接起来因此多边形总是闭合的。4.Polyline.可以创建一条折线把它两边的点区分开。左键添加折线顶点，右键结束设置。折线总是打开的（与闭合的多边形相反）。使用 Rectangle，Polygon 或 Polyline 选取了散点图的一个区域后，该区域会变成灰色。这时点击Submit 按钮会移除落在灰色区域之外的所有实例。点击Clear 按钮会清除所选区域而不对图形产生任何影响。如果所有的点都被从图中移除，则Submit 按钮会变成Reset 按钮。这个按钮能使前面所做的移除都被取消，图形回到所有点都在的初始状态。最后，点击Save 按钮可把当前能看到的实例保存到一个新的 ARFF 文件中。,谢谢！,
