《聚类分析大数据.ppt》由会员分享，可在线阅读，更多相关《聚类分析大数据.ppt（75页珍藏版）》请在课桌文档上搜索。
1、2023年3月31日星期五,1,数据挖掘:概念与技术 第七章,2023年3月31日星期五,2,第七章 聚类分析,什么是聚类分析?数据类型及其相似性与非相似性计算算法复杂性及近似算法概念划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法单链接与全链接,什么是聚类分析?,“物以类聚，人以群分。”战国策齐策三周易系辞上聚类:一个数据对象的集合同一个聚类中的对象之间具有高度的相似性。不同聚类中的对象之间具有低的相似性。聚类分析把一组数据划分成聚类。聚类是无监督分类:没有预先定义的类。,2023年3月31日星期五,4,应用领域,图像分割文档分类；消费市场分析；DNA与生
2、物信息学；离群点（孤立点）分析；,2023年3月31日星期五,5,怎样度量聚类方法?,一个 好的聚类方法 将会产生高质量的聚类:优化目标？高的聚类内相似性低的聚类间相似性 聚类方法的质量依赖于它所使用的相似性的具体定义及具体实施.,2023年3月31日星期五,6,对数据挖掘中的聚类方法的要求,可扩展性能够处理不同数据类型发现任意形状的聚类参数越少越好能够处理噪声和孤立点能够处理高维数据能够集成用户提出的各种约束,2023年3月31日星期五,7,第七章 聚类分析,什么是聚类分析?数据类型及其相似性与非相似性计算算法复杂性及近似算法概念划分方法k-center、k-cluster、k-means、
3、谱聚类NCut层次方法单链接与全链接,2023年3月31日星期五,8,数据结构,数据矩阵(2模)区分矩阵(1模),2023年3月31日星期五,9,数据类型及其相似性与非相似性计算,相似性与非相似性区间值变量:二元变量:标称性,序数性,和比例标度型变量:混合类型的变量:,2023年3月31日星期五,10,区间值变量标准化,数据标准化计算平均绝对偏差:其中计算标准化的度量差(z-score)计算相似性或非相似性时，使用zif.。考虑：一是没有量纲；二是使用这个平均绝对偏差sf比使用标准差f对于孤立点具有更好的鲁棒性。,2023年3月31日星期五,11,距离：常用的非相似性度量,常见的距离有:Min
4、kowski 距离:如果q=1,d 是Manhattan距离若q=2,d 是Euclidean距离:,2023年3月31日星期五,12,二元变量非相似性,二元变量的可能性表简单匹配系数(如果二元变量是对称的):Jaccard系数(若二元变量是不对称的):,对象i,对象 j,2023年3月31日星期五,13,标称型变量非相似性,二元变量的推广，它可以有超过 2的状态数，如Map_Color,可以有 red,yellow,blue,green方法 1:简单匹配m:匹配的数目,p:全部变量的数目方法2:使用一组二元变量对标称型变量的每一个状态设置一个二元变量,2023年3月31日星期五,14,序数型
5、变量非相似性,一个序数型变量可以离散化或连续化。可以象区间标度变量一样处理 用它们的秩rif替换xif,将每一个变量的范围映射到 0,1用计算区间值变量同样的方法计算非相似性,2023年3月31日星期五,15,向量对象间的余弦相似性,对于两个向量对象x,y，余弦度量是一种常用的（特别是在信息检索领域）相似性度量：,2023年3月31日星期五,16,第七章 聚类分析,什么是聚类分析?数据类型及其相似性与非相似性计算算法复杂性及近似算法概念划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法单链接与全链接,2023年3月31日星期五,17,问题的分类,P与NP的通俗
6、解释,P问题：在多项式时间内能解决的问题。NP问题：在多项式时间内能验证的问题。,2023年3月31日星期五,18,NPC与NPHard,NPC问题：所有NP问题能在多项式时间内规约到该问题且该问题本身属于NP问题。NP-Hard问题：所有NP问题能在多项式时间内规约到该问题。,2023年3月31日星期五,19,近似算法,对于一类优化问题及一个算法A，我们说A的近似比或性能比是(n)(1)，如果对于的任意一个实例I，我们有：对于最小化问题，cost(A(I)/cost(opt(I)(n)。对于最大化问题，cost(opt(I)/cost(A(I)(n)。其中A(I)表示算法A对于输入规模为n的
7、实例I给出的一个解，opt(I)表示I的最优解，cost()表示一个解的值或费用。,2023年3月31日星期五,20,2023年3月31日星期五,21,第七章 聚类分析,什么是聚类分析?数据类型及其相似性与非相似性计算算法复杂性及近似算法概念划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法单链接与全链接,2023年3月31日星期五,22,划分方法:基本概念,划分方法:把n个对象划分成k个非空、不相交的聚类。给定 k,根据一定的优化准则找到一个最优划分。枚举所有可能的划分找到全局最优划分？,2023年3月31日星期五,23,可能的聚类方案数,S(n,k)表示把
8、n个对象分成k个聚类的可能的划分方案数，则有：,2023年3月31日星期五,24,庐山真面目,上述递归方程的解实际上是Stirling数：,2023年3月31日星期五,25,S(n,2)=2n-1-1S(15,3)=2375101,S(20,4)=45232115901;S(25,8)=690223721118368580,可用TOP500之首的天河一号进行全局优化？,2023年3月31日星期五,26,天河一号：大场面,2023年3月31日星期五,27,天河一号：敢与姚明试比高,2023年3月31日星期五,28,天河一号有关数据,天河一号由个机柜组成，占地约平方米，总重量约吨。6144个通用处
9、理器，5120个加速处理器，内存总容量98TB，存储容量为2PB。峰值运算速度为每秒4700万亿次、持续运算速度2507万亿次每秒浮点运算。能耗：每小时耗电4040度，24小时满负荷工作耗电接近10万度。,2023年3月31日星期五,29,天河一号其奈我何,把100个对象分成五组的可能方案数：S(100,5)1068天河一号找到最优划分所需的时间：,解决方案：启发式方法与近似算法！,一些定义,P=C1,C2,Ck：n个对象的一个划分，满足条件Ci(i=1,2,k),V=iCi,及Ci Cj=(i j)。d(C)：聚类C的直径，即d(C)=maxd(p,q)|p,q C；相应地，d(P)=max
10、d(Ci)|i=1,2,k为P的直径。r(C)：聚类C的半径，这里的聚类半径是指具有最小半径的一个球（仅考虑球的中心是一个实际对象），它覆盖C的所有对象。相应地，r(P)=maxr(Ci)|i=1,2,k为P的半径。s(C)：聚类C的分离度，即s(C)=mind(p,q)|p C,q C；相应地，s(P)=mind(Ci)|i=1,2,k为P的分离度。,2023年3月31日星期五,30,一些常见的优化准则,k-Center：最大半径最小化,2023年3月31日星期五,31,k-Cluster：最大直径最小化：,k 3:NP-Hard问题!,k 3:NP-Hard问题!,2023年3月31日星期
11、五,32,一些常见的优化准则,k-means：聚类内部距离平方之和的最小化聚类分离度的最大化,P问题!,k 2:NP-Hard问题!,2023年3月31日星期五,33,一些常见的优化准则,MRSD：聚类分离度与聚类直径比值的最大化Wang Jiabing and Chen Jiaye.Clustering to maximize the ratio of split to diameter.In Proc.of the 29th ICML.Edinburgh,Scotland,June 26July 1,pp.241248,2012.,k 3:NP-Hard问题!,2023年3月31日星期五,
12、34,一些常见的优化准则,Ncut：规范割的最小化,NP-hard问题!,2023年3月31日星期五,35,k-Center与k-Cluster,对于一个对象o和一个对象的集合S，定义o与S的距离d(o,S)为o与S中对象之间的距离的最小值。S;随机选一个对象o,S S o;重复以下过程，直到|S|=k;从剩下的对象中选取d(o,S)最大的o加入S中；把每一个对象o分配到S中的最近的对象，形成k个聚类。,近似比,定理：上述算法是一个2-近似算法。证明：r*dk+1 d*2r*d(P)2dk+1 2d*r(P)dk+1 2r*定理：对于任意 0，找到上述问题的一个近似比为（2）的算法是一个NP完
13、全问题，除非P=NP。,2023年3月31日星期五,36,2023年3月31日星期五,37,k-means,k-means算法如下:1.把对象划分成k 个非空子集；2.计算当前划分的每个聚类的质心作为每个聚类的种子点；3.把每一个对象分配到与它最近的种子点所在的聚类4.返回到第2步,当满足某种停止条件时停止。,停止条件,当分配不再发生变化时停止；当前后两次迭代的目标函数值小于某一给定的阈值时；当达到给定的迭代次数时。,2023年3月31日星期五,38,2023年3月31日星期五,39,k-means聚类算法示意,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,
14、9,10,K=2任意选择 K个对象作为初始聚类中心,把每一个对象分配到最相似的中心,更新聚类平均值,更新聚类平均值,重新分配对象,重新分配对象,2023年3月31日星期五,40,示例,对象如下,k=2步骤 1,任意选择两个对象作为种子，如2和4。步骤2,分配剩下的对象。,2023年3月31日星期五,41,示例(续),2023年3月31日星期五,42,示例(续),因此,有2个聚类:1,2,3和4,5,6，两个聚类内部每个对象与对应的聚类中心的平方误差和为步骤3,计算每个聚类的中心Cluster 1:m1=(12+7+13)/3,(8+9+11)/3)=(10.67,9.33)Cluster 2:
15、m2=(23+18+20)/3,(10+23+18)/3)=(20.33,17)步骤4,重新分配对象（停止）。,2023年3月31日星期五,43,示例(续),2023年3月31日星期五,44,基于最小割的聚类算法,最小割(min-cut)min-cut=w(e3,5)+w(e4,6),2023年3月31日星期五,45,Min-Cut I,MINIMUMCUT(G,w,a)while|V|1MINIMUMCUTPHASE(G,w,a)if（当前阶段的cut值比当前的mincut值小）更新mincut值为当前阶段的cut值；,2023年3月31日星期五,46,Min-Cut II,MINIMUMC
16、UTPHASE(G,w,a)A awhile A V把V-A中与 A连接权重最大的点加入A中；存储当前阶段的cut值并收缩G中最后加入A中的两个点;,2023年3月31日星期五,47,NCut,目的：试图克服最小割算法所具有的割的两部分严重不平衡的弱点。,2023年3月31日星期五,48,Normalized Cut II,给定nn的相似性矩阵W，Wij表示对象i和j的相似性，则算法步骤如下：D是一个对角矩阵，即只有对角线有元素，其它位置均为0。其中Dii 为W中对应行的元素之和，i=1,2,.,n，即Dii=W1i+W2i+.+Wni；求解通用特征值及特征向量方程:(D-W)x=Dx；,20
17、23年3月31日星期五,49,Normalized Cut III,设secondvalue及Vector分别为上述方程的第二小特征值及其对应的特征向量；利用Vector向量对对象进行划分。如果需要进一步划分，则重复上述步骤，直到满足要求为止。,2023年3月31日星期五,50,第七章 聚类分析,什么是聚类分析?数据类型及其相似性与非相似性计算算法复杂性及近似算法概念划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法单链接与全链接,2023年3月31日星期五,51,层次聚类,这种方法不需要用户提供聚类的数目k 作为输入。,2023年3月31日星期五,52,层次
18、聚类法：聚类之间的距离,最短与最长距离：若定义两个聚类之间的距离为二者对象之间的最小距离，则该算法也称为单链接算法(Single-Linkage Algorithm，SLA)，也称为最小生成树算法。若定义两个聚类之间的距离为二者对象之间的最大距离，则该算法也称为全链接算法(Complete-Linkage Algorithm，CLA)。,2023年3月31日星期五,53,单链接算法 I,给定5个对象间的距离如下表,2023年3月31日星期五,54,单链接算法 II,步骤1:每个对象当做一个聚类.步骤 2:找出上述5个聚类中最近的两个聚类2和5，因为它们的距离最小:d25=1.所以,2和5凝聚成
19、一个新的聚类2,5.步骤3.计算聚类2,5与聚类 1,3,4的距离D2,51=mind21,d51=min6,7=6D2,53=mind23,d53=min4,5=4D2,54=mind24,d54=min4,5=4,2023年3月31日星期五,55,单链接算法 III,4个聚类 2,5,1,3,4中最近的2个聚类是 1和3.因此,1和3凝聚成一个新的聚类.现在,我们有3个聚类:1,3,2,5,4.步骤4.计算聚类 1,3与 2,5,4之间的距离D1,32,5=mind12,5,d32,5=min6,4=4D1,34=mind14,d34=min3,5=3因此,聚类1,3和 4凝聚成一个新的聚
20、类1,3,4.,2023年3月31日星期五,56,单链接算法 IV,现在,我们得到2个聚类1,3,4和2,5 步骤5.计算1,3,4的2,5聚类 d2,51,3,4=mind2,51,3,d2,54=min4,4=4聚类 1,3,4和2,5凝聚成一个唯一的聚类 1,2,3,4,5.,2023年3月31日星期五,57,单链接算法 V,系统树图 演示了层次聚类的过程 1 2 3 4 5 Steps25134,2023年3月31日星期五,58,SLA与CLA的理论性质,SLA与最小生成树的关系：最大分离度一定等于最小生成树中某条边的值。定理：SLA算法找到了最大分离度。CLA算法是一个k-Clust
21、er的logk-近似算法(2 k n),2023年3月31日星期五,59,聚类分离度,分离度s(P),聚类直径,直径d(P),2023年3月31日星期五,60,MRSD的优化目标,优化目标定理.对于 k 3,MRSD的判定问题是一个 NP-完全问题。,2023年3月31日星期五,61,合并操作,合并操作,2023年3月31日星期五,62,MRSD算法（k=2),2023年3月31日星期五,63,构造图G的最小生成树Tmin 并将边从小到大排序;G=(V,E)G;while(|Tmin|)构造G的最大生成树Tmax;对Tmax 进行2着色得到划分 P;存储最好的解;对Tmin中 的所有权重小于等
22、于s(P)的边(p,q)，合并G 的点对p与q，并从Tmin 中删去边(p,q);返回最好的解;,MRSD的最优性,定理：上述算法返回k=2的最优解，时间复杂性为O(n3),2023年3月31日星期五,64,3/31/2023,示例,左:输入图G.右:G的最小生成树 Tmin.,3/31/2023,示例(Cont.),右:左图的最大生成树 Tmax.Tmax 的2着色产生划分 P=1,2,6,3,4,5:d(P)=6,s(P)=1,and s(P)/d(P)=1/6,3/31/2023,示例(Cont.),中:合并边(1,2)、(5,6)后的图.右:中间图的最大生成树Tmax.Tmax 的2着
23、色产生划分 P=1,2,3,4,5,6:d(P)=7,s(P)=2,and s(P)/d(P)=2/7.,3/31/2023,示例(Cont.),中:合并边(3,4)后的图.右:中间图的最大生成树Tmax.Tmax 的2着色产生划分 P=1,2,3,4,5,6:d(P)=8,s(P)=3,s(P)/d(P)=3/8.,3/31/2023,示例(Cont.),中:合并边(2,3)后的图.右:中间图的最大生成树 Tmax.Tmax 的2着色产生划分 P=1,2,3,4,5,6:d(P)=9,s(P)=5,s(P)/d(P)=5/9.,3/31/2023,示例(Cont.),右:合并边(3,5)的图.|Tmin|=，算法停止.最优划分P=1,2,3,4,5,6，最优值5/9.,3/31/2023,左至右:MRSD,NCut_C,NCut_S,CLA,SLA,3/31/2023,左至右:MRSD,NCut_C,NCut_S,CLA,SLA,3/31/2023,运行时间(Seconds),MATLAB R2009b,NCut_C(eig),NCut_S(eigs),2.6 GHz Pentium Dual-Core with 2G bytes of RAM,3/31/2023,MRSD,3/31/2023,MRSD,
