聚类分析大数据课件.ppt

1、2022年8月6日星期六Data Mining:Concepts and Techniques1数据挖掘数据挖掘:概念与技术概念与技术 第七章第七章 2022年8月6日星期六Data Mining:Concepts and Techniques2第七章第七章 聚类分析聚类分析 什么是聚类分析什么是聚类分析?数据类型及其相似性与非相似性计算数据类型及其相似性与非相似性计算 算法复杂性及近似算法概念算法复杂性及近似算法概念 划分方法划分方法 k-center、k-cluster、k-means、谱聚类NCut 层次方法层次方法 单链接与全链接什么是聚类分析什么是聚类分析?“物以类聚，人以群分。”战

2、国策齐策三周易系辞上 聚类聚类:一个数据对象的集合一个数据对象的集合 同一个聚类中的对象之间具有高度的相似性。不同聚类中的对象之间具有低的相似性。聚类分析聚类分析 把一组数据划分成聚类。聚类是聚类是无监督分类无监督分类:没有预先定义的类。没有预先定义的类。2022年8月6日星期六Data Mining:Concepts and Techniques4应用领域应用领域 图像分割 文档分类；消费市场分析；DNA与生物信息学；离群点（孤立点）分析；2022年8月6日星期六Data Mining:Concepts and Techniques5怎样度量聚类方法怎样度量聚类方法?一个一个 好的聚类方法好

3、的聚类方法 将会产生高质量的聚将会产生高质量的聚类类:优化目标？优化目标？高的聚类内相似性 低的聚类间相似性 聚类方法的质量依赖于它所使用的相似聚类方法的质量依赖于它所使用的相似性的具体定义及具体实施性的具体定义及具体实施.2022年8月6日星期六Data Mining:Concepts and Techniques6对数据挖掘中的聚类方法的要求对数据挖掘中的聚类方法的要求 可扩展性 能够处理不同数据类型 发现任意形状的聚类 参数越少越好 能够处理噪声和孤立点 能够处理高维数据 能够集成用户提出的各种约束 2022年8月6日星期六Data Mining:Concepts and Techniq

4、ues7第七章第七章 聚类分析聚类分析 什么是聚类分析什么是聚类分析?数据类型及其相似性与非相似性计算数据类型及其相似性与非相似性计算 算法复杂性及近似算法概念算法复杂性及近似算法概念 划分方法划分方法 k-center、k-cluster、k-means、谱聚类NCut 层次方法层次方法 单链接与全链接2022年8月6日星期六Data Mining:Concepts and Techniques8数据结构数据结构 数据矩阵数据矩阵(2模)区分矩阵区分矩阵(1模)npx.nfx.n1x.ipx.ifx.i1x.1px.1fx.11x 0.)2,()1,(:)2,3().ndnd0dd(3,10

5、d(2,1)02022年8月6日星期六Data Mining:Concepts and Techniques9数据类型及其相似性与非相似数据类型及其相似性与非相似性计算性计算 相似性与非相似性相似性与非相似性 区间值变量区间值变量:二元变量二元变量:标称性标称性,序数性序数性,和比例标度型变量和比例标度型变量:混合类型的变量混合类型的变量:2022年8月6日星期六Data Mining:Concepts and Techniques10区间值变量标准化区间值变量标准化 数据标准化数据标准化 计算平均绝对偏差:其中 计算标准化的度量差(z-score)计算相似性或非相似性时，使用zif.。考虑：

6、一是没有量纲；二是使用这个平均绝考虑：一是没有量纲；二是使用这个平均绝对偏差对偏差s sf f比使用标准差比使用标准差 f f对于孤立点具有更对于孤立点具有更好的鲁棒性。好的鲁棒性。.).211nffffxx(xn m|)|.|(|121fnffffffmxmxmxnsffififsmx z2022年8月6日星期六Data Mining:Concepts and Techniques11距离：常用的非相似性度量距离：常用的非相似性度量 常见的距离有常见的距离有:Minkowski 距离距离:如果如果q=1,d 是是Manhattan距离距离 若若q=2,d 是是Euclidean距离距离:qq

7、ppqqjxixjxixjxixjid)|.|(|),(2211|.|),(2211ppjxixjxixjxixjid)|.|(|),(2222211ppjxixjxixjxixjid2022年8月6日星期六Data Mining:Concepts and Techniques12二元变量非相似性二元变量非相似性 二元变量的可能性表二元变量的可能性表 简单匹配系数简单匹配系数(如果二元变量是如果二元变量是对称的对称的):Jaccard系数系数(若二元变量是不对称的若二元变量是不对称的):dcbacb jid),(pdbcasumdcdcbabasum0101cbacb jid),(对象对象i对

8、象对象 j2022年8月6日星期六Data Mining:Concepts and Techniques13标称型变量非相似性标称型变量非相似性 二元变量的推广，它可以有超过二元变量的推广，它可以有超过 2的状态数，如的状态数，如Map_Color,可以有可以有 red,yellow,blue,green 方法方法 1:简单匹配简单匹配 m:匹配的数目,p:全部变量的数目 方法方法2:使用一组二元变量使用一组二元变量 对标称型变量的每一个状态设置一个二元变量pmpjid),(2022年8月6日星期六Data Mining:Concepts and Techniques14序数型变量非相似性序数

9、型变量非相似性 一个序数型变量可以离散化或连续化。一个序数型变量可以离散化或连续化。可以象区间标度变量一样处理可以象区间标度变量一样处理 用它们的秩rif替换xif,将每一个变量的范围映射到 0,1 用计算区间值变量同样的方法计算非相似性11fififMrz,.,1fifMr2022年8月6日星期六Data Mining:Concepts and Techniques15向量对象间的余弦相似性向量对象间的余弦相似性 对于两个向量对象对于两个向量对象x,y，余弦度量是一种常，余弦度量是一种常用的（特别是在信息检索领域）相似性度用的（特别是在信息检索领域）相似性度量：量：22|),(yxyxyxs

10、T2022年8月6日星期六Data Mining:Concepts and Techniques16第七章第七章 聚类分析聚类分析 什么是聚类分析什么是聚类分析?数据类型及其相似性与非相似性计算数据类型及其相似性与非相似性计算 算法复杂性及近似算法概念算法复杂性及近似算法概念 划分方法划分方法 k-center、k-cluster、k-means、谱聚类NCut 层次方法层次方法 单链接与全链接2022年8月6日星期六17问题的分类问题的分类P与与NP的通俗解释的通俗解释 P P问题：问题：在多项式时间内能解决的问题。NPNP问题：问题：在多项式时间内能验证的问题。2022年8月6日星期六Da

11、ta Mining:Concepts and Techniques18NPC与与NPHard NPCNPC问题问题：所有NP问题能在多项式时间内规约到该问题且该问题本身属于NP问题。NP-Hard问题：问题：所有NP问题能在多项式时间内规约到该问题。2022年8月6日星期六Data Mining:Concepts and Techniques19近似算法近似算法 对于一类优化问题及一个算法A，我们说A的近似比或性能比是(n)(1)，如果对于的任意一个实例I，我们有：对于最小化问题，cost(A(I)/cost(opt(I)(n)。对于最大化问题，cost(opt(I)/cost(A(I)(n)

12、。其中A(I)表示算法A对于输入规模为n的实例I给出的一个解，opt(I)表示I的最优解，cost()表示一个解的值或费用。2022年8月6日星期六Data Mining:Concepts and Techniques202022年8月6日星期六Data Mining:Concepts and Techniques21第七章第七章 聚类分析聚类分析 什么是聚类分析什么是聚类分析?数据类型及其相似性与非相似性计算数据类型及其相似性与非相似性计算 算法复杂性及近似算法概念算法复杂性及近似算法概念 划分方法划分方法 k-center、k-cluster、k-means、谱聚类NCut 层次方法层次方

13、法 单链接与全链接2022年8月6日星期六Data Mining:Concepts and Techniques22划分方法划分方法:基本概念基本概念 划分方法划分方法:把n个对象划分成k个非空、不相交的聚类。给定给定 k,根据一定的根据一定的优化准则优化准则找到一个最优找到一个最优划分。划分。枚举所有可能的划分找到全局最优划分？2022年8月6日星期六Data Mining:Concepts and Techniques23可能的聚类方案数可能的聚类方案数 S(n,k)表示把表示把n个对象分成个对象分成k个聚类的可能的划个聚类的可能的划分方案数，则有：分方案数，则有：elseknSknkSn

14、knkkknS)1,1(),1(0111),(2022年8月6日星期六Data Mining:Concepts and Techniques24庐山真面目庐山真面目 上述递归方程的解实际上是上述递归方程的解实际上是Stirling数：数：nkiikiikkknS0)1(!1),(2022年8月6日星期六Data Mining:Concepts and Techniques25 S(n,2)=2n-1-1 S(15,3)=2375101,S(20,4)=45232115901;S(25,8)=690223721118368580可用可用TOP500之首的天河一号进行全局优化？之首的天河一号进行全

15、局优化？2022年8月6日星期六Data Mining:Concepts and Techniques26天河一号：大场面天河一号：大场面2022年8月6日星期六Data Mining:Concepts and Techniques27天河一号：敢与姚明试比高天河一号：敢与姚明试比高2022年8月6日星期六Data Mining:Concepts and Techniques28天河一号有关数据天河一号有关数据 天河一号由个机柜组成，占地约平方米，总重量约吨。6144个通用处理器，5120个加速处理器，内存总容量98TB，存储容量为2PB。峰值运算速度为每秒4700万亿次、持续运算速度2507

16、万亿次每秒浮点运算。能耗：每小时耗电4040度，24小时满负荷工作耗电接近10万度。2022年8月6日星期六Data Mining:Concepts and Techniques29天河一号其奈我何天河一号其奈我何 把把100个对象分成五组的可能方案数：个对象分成五组的可能方案数：S(100,5)1068 天河一号找到最优划分所需的时间：天河一号找到最优划分所需的时间：年千万亿年3441568)1(1035.636524360010510T解决方案：启发式方法与近似算法！一些定义一些定义 P=C1,C2,Ck：n个对象的一个划分划分，满足条件Ci (i=1,2,k),V=iCi,及Ci Cj=

17、(i j)。d(C)：聚类C的直径直径，即d(C)=maxd(p,q)|p,q C；相应地，d(P)=maxd(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的分离度。2022年8月6日星期六Data Mining:Concepts and Techniques30一些常见的优化准则一些常见的优

18、化准则 k-Center：最大半径最小化2022年8月6日星期六Data Mining:Concepts and Techniques31)(minPrknPP k-Cluster：最大直径最小化：)(minPdknPPk 3:NP-Hard问题!k 3:NP-Hard问题!2022年8月6日星期六Data Mining:Concepts and Techniques32一些常见的优化准则一些常见的优化准则 k-means：聚类内部距离平方之和的最小化 聚类分离度的最大化kiCoCPPiiknmod12),(minP问题!)(maxPsknPP k 2:NP-Hard问题!2022年8月6日星

19、期六Data Mining:Concepts and Techniques33一些常见的优化准则一些常见的优化准则 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.d(P)s(P)PPknmaxk 3:NP-Hard问题!2022年8月6日星期六Data Mining:Concepts and

20、Techniques34一些常见的优化准则一些常见的优化准则)()(cutBWcutcutW(Acutmin2nPP12876543Ncut：规范割的最小化NP-hard问题!2022年8月6日星期六Data Mining:Concepts and Techniques35k-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个聚类。近似比近似比 定理

21、：定理：上述算法是一个2-近似算法。证明：证明：r*dk+1 d*2r*d(P)2dk+1 2d*r(P)dk+1 2r*定理：定理：对于任意 0，找到上述问题的一个近似比为（2 ）的算法是一个NP完全问题，除非P=NP。2022年8月6日星期六Data Mining:Concepts and Techniques362022年8月6日星期六Data Mining:Concepts and Techniques37k-means k-means算法如下算法如下:1.把对象划分成k 个非空子集；2.计算当前划分的每个聚类的质心作为每个聚类的种子点；3.把每一个对象分配到与它最近的种子点所在的聚类

22、 4.返回到第2步,当满足某种停止条件时停止。停止条件停止条件 当分配不再发生变化时停止；当前后两次迭代的目标函数值小于某一给定的阈值时；当达到给定的迭代次数时。2022年8月6日星期六Data Mining:Concepts and Techniques382022年8月6日星期六Data Mining:Concepts and Techniques39k-means聚类聚类算法示意算法示意012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345

23、678910012345678910K=2任意选择 K个对象作为初始聚类中心把每一个对象分配到最相似的中心更新聚类平均值更新聚类平均值重新分配对象重新分配对象2022年8月6日星期六Data Mining:Concepts and Techniques40示例示例 对象如下,k=2 步骤 1,任意选择两个对象作为种子，如2和4。步骤2,分配剩下的对象。123456(12,8)(7,9)(13,11)(23,10)(18,23)(20,18)2022年8月6日星期六Data Mining:Concepts and Techniques41 示例示例(续续)No2 412345625 12540

24、101 317 194250 732022年8月6日星期六Data Mining:Concepts and Techniques42示例示例(续续)因此,有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:m2=(23+18+20)/3,(10+23+18)/3)=(20.33,17)步骤4,重新分配对象（停止）。2022年8月6日星期六Data Mining:Concepts and Techniques43示例

25、示例(续续)NoM1(10.67,9.33)M2(20.33,17)1234563.54 150.3113.76 241.8 8.24 89.68149.82 56.1240.56 41.47162.31 2.822022年8月6日星期六Data Mining:Concepts and Techniques44基于最小割的聚类算法基于最小割的聚类算法 最小割最小割(min-cut)min-cut=w(e3,5)+w(e4,6)128765432022年8月6日星期六Data Mining:Concepts and Techniques45Min-Cut I MINIMUMCUT(G,w,a)w

26、hile|V|1 MINIMUMCUTPHASE(G,w,a)if（当前阶段的cut值比当前的mincut值小）更新mincut值为当前阶段的cut值；2022年8月6日星期六Data Mining:Concepts and Techniques46Min-Cut II MINIMUMCUTPHASE(G,w,a)A a while A V 把V-A中与 A连接权重最大的点加入A中；存储当前阶段的cut值并收缩G中最后加入A中的两个点;2022年8月6日星期六Data Mining:Concepts and Techniques47NCut)()(cutBWcutcutW(Acutmin2nP

27、P12876543目的：试图克服最小割算法所具有的割的两部分严重不平衡的弱点。2022年8月6日星期六Data Mining:Concepts and Techniques48Normalized Cut II 给定nn的相似性矩阵W，Wij表示对象i和j的相似性，则算法步骤如下：D是一个对角矩阵，即只有对角线有元素，其它位置均为0。其中Dii 为W中对应行的元素之和，i=1,2,.,n，即Dii=W1i+W2i+.+Wni；求解通用特征值及特征向量方程:(D-W)x=Dx；2022年8月6日星期六Data Mining:Concepts and Techniques49Normalized

28、Cut III 设secondvalue及Vector分别为上述方程的第二小特征值及其对应的特征向量；利用Vector向量对对象进行划分。如果需要进一步划分，则重复上述步骤，直到满足要求为止。2022年8月6日星期六Data Mining:Concepts and Techniques50第七章第七章 聚类分析聚类分析 什么是聚类分析什么是聚类分析?数据类型及其相似性与非相似性计算数据类型及其相似性与非相似性计算 算法复杂性及近似算法概念算法复杂性及近似算法概念 划分方法划分方法 k-center、k-cluster、k-means、谱聚类NCut 层次方法层次方法 单链接与全链接2022年8

29、月6日星期六Data Mining:Concepts and Techniques51层次聚类层次聚类 这种方法不需要用户提供聚类的数目k 作为输入。Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0凝聚法凝聚法(AGNES)分裂法分裂法(DIANA)2022年8月6日星期六Data Mining:Concepts and Techniques52层次聚类法：聚类之间的距离层次聚类法：聚类之间的距离 最短与最长距离：若定义两个聚类之间的距离为二者对象之间的最小距离，则该算法也

30、称为单链接算法(Single-Linkage Algorithm，SLA)，也称为最小生成树算法。若定义两个聚类之间的距离为二者对象之间的最大距离，则该算法也称为全链接算法(Complete-Linkage Algorithm，CLA)。2022年8月6日星期六Data Mining:Concepts and Techniques53单链接算法单链接算法 I 给定5个对象间的距离如下表No1 2 3 4 51234506 02 4 03 4 5 07 1 5 5 02022年8月6日星期六Data Mining:Concepts and Techniques54单链接算法单链接算法 II 步骤

31、步骤1 1:每个对象当做一个聚类.步骤步骤 2 2:找出上述5个聚类中最近的两个聚类2和5，因为它们的距离最小:d25=1.所以,2和5凝聚成一个新的聚类2,5.步骤步骤3 3.计算聚类2,5与聚类 1,3,4的距离 D2,51=mind21,d51=min6,7=6 D2,53=mind23,d53=min4,5=4 D2,54=mind24,d54=min4,5=4No2,5 1 3 42,513406 04 2 04 3 5 02022年8月6日星期六Data Mining:Concepts and Techniques55单链接算法单链接算法 III 4个聚类 2,5,1,3,4中最近

32、的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=4 D1,34=mind14,d34=min3,5=3 因此,聚类1,3和 4凝聚成一个新的聚类1,3,4.No2,5 1,3 42,51,3404 04 3 02022年8月6日星期六Data Mining:Concepts and Techniques56单链接算法单链接算法 IV 现在,我们得到2个聚类1,3,4和2,5 步骤步骤5.计算1,3,4的2,5聚类 d2,51,3,4=

33、mind2,51,3,d2,54=min4,4=4 聚类 1,3,4和2,5凝聚成一个唯一的聚类 1,2,3,4,5.No2,5 1,3,42,51,3,404 02022年8月6日星期六Data Mining:Concepts and Techniques57单链接算法单链接算法 V系统树图 演示了层次聚类的过程 1 2 3 4 5 Steps 2 5 1 3 42022年8月6日星期六Data Mining:Concepts and Techniques58SLA与与CLA的的理论性质理论性质 SLA与最小生成树的关系：与最小生成树的关系：最大分离度一定等于最小生成树中某条边的值。定理：定

34、理：SLA算法找到了最大分离度。CLA算法是一个k-Cluster的logk-近似算法(2 k n)2022年8月6日星期六Data Mining:Concepts and Techniques59聚类分离度聚类分离度 分离度分离度s(P)聚类直径聚类直径 直径直径d(P)2022年8月6日星期六Data Mining:Concepts and Techniques60MRSD的优化目标的优化目标优化目标优化目标定理定理.对于对于 k 3,MRSD的判定问题是一个的判定问题是一个 NP-完全问题。完全问题。2022年8月6日星期六Data Mining:Concepts and Techniq

35、ues61合并操作合并操作 合并操作合并操作2022年8月6日星期六Data Mining:Concepts and Techniques62Merge u and vMRSD算法（算法（k=2)2022年8月6日星期六Data Mining:Concepts and Techniques63 构造图G的最小生成树Tmin 并将边从小到大排序;G=(V,E)G;while(|Tmin|)构造G的最大生成树Tmax;对Tmax 进行2着色得到划分 P;存储最好的解;对Tmin中 的所有权重小于等于s(P)的边(p,q)，合并G 的点对p与q，并从Tmin 中删去边(p,q);返回最好的解;MRS

36、D的最优性的最优性 定理：上述算法返回定理：上述算法返回k=2的最优解，时的最优解，时间复杂性为间复杂性为O(n3)2022年8月6日星期六Data Mining:Concepts and Techniques648/6/2022示例示例左左:输入图输入图G.右右:G的最小生成树的最小生成树 Tmin.8/6/2022示例示例(Cont.)右:左图的最大生成树 Tmax.Tmax 的2着色产生划分 P=1,2,6,3,4,5:d(P)=6,s(P)=1,and s(P)/d(P)=1/6 8/6/2022示例示例(Cont.)中:合并边(1,2)、(5,6)后的图.右:中间图的最大生成树Tma

37、x.Tmax 的2着色产生划分 P=1,2,3,4,5,6:d(P)=7,s(P)=2,and s(P)/d(P)=2/7.合并8/6/2022示例示例(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.合并8/6/2022示例示例(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.合并8/6/2022示例示例(Cont.)右:合并边(3,5)的图.|Tmin|=，算法停止.最优划分P=1,2,3,4,5,6，最优值5/9.合并8/6/2022左至右左至右:MRSD,NCut_C,NCut_S,CLA,SLA8/6/2022左至右左至右:MRSD,NCut_C,NCut_S,CLA,SLA8/6/2022运行时间运行时间(Seconds)8/6/2022MRSD8/6/2022MRSD