20 九月 2024Data Mining: Concepts and Techniques1数据挖掘数据挖掘: 概念与技术概念与技术 第七章第七章 20 九月 2024Data Mining: Concepts and Techniques2第七章第七章 聚类分析聚类分析什么是聚类分析什么是聚类分析? ?数据类型及其相似性与非相似性计算数据类型及其相似性与非相似性计算算法复杂性及近似算法概念算法复杂性及近似算法概念划分方法划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法层次方法单链接与全链接什么是聚类分析什么是聚类分析? ?“物以类聚，人以群分。”战国策齐策三周易系辞上聚类聚类: : 一个数据对象的集合一个数据对象的集合同一个聚类中的对象之间具有高度的相似性。不同聚类中的对象之间具有低的相似性。聚类分析聚类分析把一组数据划分成聚类。聚类是聚类是无监督分类无监督分类: : 没有预先定义的类。没有预先定义的类。20 九月 2024Data Mining: Concepts and Techniques4应用领域应用领域 图像分割文档分类；消费市场分析；DNA与生物信息学；离群点（孤立点）分析；20 九月 2024Data Mining: Concepts and Techniques5怎样度量聚类方法怎样度量聚类方法? ?一个一个 好的聚类方法好的聚类方法 将会产生高质量的聚将会产生高质量的聚类类: 优化目标？优化目标？高的聚类内相似性低的聚类间相似性 聚类方法的质量依赖于它所使用的相似性聚类方法的质量依赖于它所使用的相似性的具体定义及具体实施的具体定义及具体实施.20 九月 2024Data Mining: Concepts and Techniques6对数据挖掘中的聚类方法的要求对数据挖掘中的聚类方法的要求 可扩展性能够处理不同数据类型发现任意形状的聚类参数越少越好能够处理噪声和孤立点能够处理高维数据能够集成用户提出的各种约束20 九月 2024Data Mining: Concepts and Techniques7第七章第七章 聚类分析聚类分析什么是聚类分析什么是聚类分析? ?数据类型及其相似性与非相似性计算数据类型及其相似性与非相似性计算算法复杂性及近似算法概念算法复杂性及近似算法概念划分方法划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法层次方法单链接与全链接20 九月 2024Data Mining: Concepts and Techniques8数据结构数据结构数据矩阵数据矩阵(2模)区分矩阵区分矩阵(1模)20 九月 2024Data Mining: Concepts and Techniques9数据类型及其相似性与非相似数据类型及其相似性与非相似性计算性计算相似性与非相似性相似性与非相似性区间值变量区间值变量:二元变量二元变量:标称性标称性, 序数性序数性, 和比例标度型变量和比例标度型变量:混合类型的变量混合类型的变量:20 九月 2024Data Mining: Concepts and Techniques10区间值变量标准化区间值变量标准化数据标准化数据标准化计算平均绝对偏差: 其中计算标准化的度量差 (z-score)计算相似性或非相似性时，使用zif.。考虑：一是没有量纲；二是使用这个平均绝考虑：一是没有量纲；二是使用这个平均绝对偏差对偏差s sf f比使用标准差比使用标准差 f f对于孤立点具有更对于孤立点具有更好的鲁棒性。好的鲁棒性。20 九月 2024Data Mining: Concepts and Techniques11距离：常用的非相似性度量距离：常用的非相似性度量常见的距离有常见的距离有: Minkowski 距离距离:如果如果q = 1, d 是是Manhattan距离距离若若q = 2, d 是是Euclidean距离距离:20 九月 2024Data Mining: Concepts and Techniques12二元变量非相似性二元变量非相似性二元变量的可能性表二元变量的可能性表简单匹配系数简单匹配系数 (如果二元变量是如果二元变量是对称的对称的):Jaccard系数系数 (若二元变量是不对称的若二元变量是不对称的): 对象对象i对象对象 j20 九月 2024Data Mining: Concepts and Techniques13标称型变量非相似性标称型变量非相似性二元变量的推广，它可以有超过二元变量的推广，它可以有超过 2的状态数，如的状态数，如Map_Color,可以有可以有 red, yellow, blue, green方法方法 1: 简单匹配简单匹配m: 匹配的数目, p: 全部变量的数目方法方法2: 使用一组二元变量使用一组二元变量对标称型变量的每一个状态设置一个二元变量20 九月 2024Data Mining: Concepts and Techniques14序数型变量非相似性序数型变量非相似性一个序数型变量可以离散化或连续化。一个序数型变量可以离散化或连续化。可以象区间标度变量一样处理可以象区间标度变量一样处理 用它们的秩rif替换xif,将每一个变量的范围映射到 0, 1用计算区间值变量同样的方法计算非相似性20 九月 2024Data Mining: Concepts and Techniques15向量对象间的余弦相似性向量对象间的余弦相似性对于两个向量对象对于两个向量对象x, y，余弦度量是一种常，余弦度量是一种常用的（特别是在信息检索领域）相似性度量：用的（特别是在信息检索领域）相似性度量：20 九月 2024Data Mining: Concepts and Techniques16第七章第七章 聚类分析聚类分析什么是聚类分析什么是聚类分析? ?数据类型及其相似性与非相似性计算数据类型及其相似性与非相似性计算算法复杂性及近似算法概念算法复杂性及近似算法概念划分方法划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法层次方法单链接与全链接20 九月 202417问题的分类问题的分类P与与NP的通俗解释的通俗解释P P问题：问题：在多项式时间内能解决的问题。NPNP问题：问题：在多项式时间内能验证的问题。20 九月 2024Data Mining: Concepts and Techniques18NPC与与NPHardNPCNPC问题问题：所有NP问题能在多项式时间内规约到该问题且该问题本身属于NP问题。NP-Hard问题：问题：所有NP问题能在多项式时间内规约到该问题。20 九月 2024Data Mining: Concepts and Techniques19近似算法近似算法对于一类优化问题及一个算法A，我们说A的近似比或性能比是(n) ( 1)，如果对于的任意一个实例I，我们有：对于最小化问题，cost(A(I) / cost(opt(I) (n)。对于最大化问题，cost(opt(I) / cost(A(I) (n)。其中A(I)表示算法A对于输入规模为n的实例I给出的一个解，opt(I)表示I的最优解，cost()表示一个解的值或费用。20 九月 2024Data Mining: Concepts and Techniques2020 九月 2024Data Mining: Concepts and Techniques21第七章第七章 聚类分析聚类分析什么是聚类分析什么是聚类分析? ?数据类型及其相似性与非相似性计算数据类型及其相似性与非相似性计算算法复杂性及近似算法概念算法复杂性及近似算法概念划分方法划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法层次方法单链接与全链接20 九月 2024Data Mining: Concepts and Techniques22划分方法划分方法: : 基本概念基本概念划分方法划分方法: 把n个对象划分成k个非空、不相交的聚类。给定给定 k, 根据一定的根据一定的优化准则优化准则找到一个最优找到一个最优划分。划分。枚举所有可能的划分找到全局最优划分 ？ 20 九月 2024Data Mining: Concepts and Techniques23可能的聚类方案数可能的聚类方案数S(n, k)表示把表示把n个对象分成个对象分成k个聚类的可能的划个聚类的可能的划分方案数，则有：分方案数，则有：20 九月 2024Data Mining: Concepts and Techniques24庐山真面目庐山真面目上述递归方程的解实际上是上述递归方程的解实际上是Stirling数：数：20 九月 2024Data Mining: Concepts and Techniques25S(n, 2) = 2n-1 - 1S(15, 3) = 2375101, S(20, 4) = 45232115901;S(25, 8) = 690223721118368580可用可用TOP500之首的天河一号进行全局优化？之首的天河一号进行全局优化？20 九月 2024Data Mining: Concepts and Techniques26天河一号：大场面天河一号：大场面20 九月 2024Data Mining: Concepts and Techniques27天河一号：敢与姚明试比高天河一号：敢与姚明试比高20 九月 2024Data Mining: Concepts and Techniques28天河一号有关数据天河一号有关数据天河一号由个机柜组成，占地约平方米，总重量约吨。6144个通用处理器， 5120个加速处理器，内存总容量98TB，存储容量为2PB 。峰值运算速度为每秒4700万亿次、持续运算速度2507万亿次每秒浮点运算。 能耗：每小时耗电4040度，24小时满负荷工作耗电接近10万度。20 九月 2024Data Mining: Concepts and Techniques29天河一号其奈我何天河一号其奈我何把把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) = 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的分离度。20 九月 2024Data Mining: Concepts and Techniques30一些常见的优化准则一些常见的优化准则k-Center：最大半径最小化20 九月 2024Data Mining: Concepts and Techniques31k-Cluster：最大直径最小化：k 3: NP-Hard问题!k 3: NP-Hard问题!20 九月 2024Data Mining: Concepts and Techniques32一些常见的优化准则一些常见的优化准则k-means：聚类内部距离平方之和的最小化聚类分离度的最大化P问题!k 2: NP-Hard问题!20 九月 2024Data 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.k 3: NP-Hard问题!20 九月 2024Data Mining: Concepts and Techniques34一些常见的优化准则一些常见的优化准则12876543Ncut：规范割的最小化NP-hard问题!20 九月 2024Data 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个聚类。近似比近似比定理：定理：上述算法是一个2-近似算法。证明：证明：r* dk+1 d* 2r* d(P) 2dk+1 2d* r(P) dk+1 2r*定理：定理：对于任意 0，找到上述问题的一个近似比为（2 ）的算法是一个NP完全问题，除非P = NP。20 九月 2024Data Mining: Concepts and Techniques3620 九月 2024Data Mining: Concepts and Techniques37k-means k-means算法如下算法如下:1. 把对象划分成k 个非空子集；2. 计算当前划分的每个聚类的质心作为每个聚类的种子点；3. 把每一个对象分配到与它最近的种子点所在的聚类4. 返回到第2步, 当满足某种停止条件时停止。停止条件停止条件当分配不再发生变化时停止；当前后两次迭代的目标函数值小于某一给定的阈值时；当达到给定的迭代次数时。20 九月 2024Data Mining: Concepts and Techniques3820 九月 2024Data Mining: Concepts and Techniques39k-means聚类聚类算法示意算法示意012345678910012345678910012345678910012345678910K=2任意选择 K个对象作为初始聚类中心把每一个对象分配到最相似的中心更新聚类平均值更新聚类平均值重新分配对象重新分配对象20 九月 2024Data Mining: Concepts and Techniques40示例示例对象如下, k=2步骤 1, 任意选择两个对象作为种子，如2和4。步骤2, 分配剩下的对象。123456(12,8)(7,9)(13,11)(23,10)(18,23)(20,18)20 九月 2024Data Mining: Concepts and Techniques41 示例示例( (续续) )No2 412345625 12540 101 317 194250 7320 九月 2024Data 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, 重新分配对象（停止）。20 九月 2024Data Mining: Concepts and Techniques43示例示例( (续续) )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.8220 九月 2024Data Mining: Concepts and Techniques44基于最小割的聚类算法基于最小割的聚类算法最小割最小割(min-cut)min-cut=w(e3,5)+w(e4,6)1287654320 九月 2024Data Mining: Concepts and Techniques45Min-Cut IMINIMUMCUT(G, w, a)while |V| 1MINIMUMCUTPHASE(G, w, a)if （当前阶段的cut值比当前的mincut值小）更新mincut值为当前阶段的cut值；20 九月 2024Data Mining: Concepts and Techniques46Min-Cut IIMINIMUMCUTPHASE(G, w, a)A awhile A V把V - A中与 A连接权重最大的点加入A中 ；存储当前阶段的cut值并收缩G中最后加入A中的两个点;20 九月 2024Data Mining: Concepts and Techniques47NCut12876543目的：试图克服最小割算法所具有的割的两部分严重不平衡的弱点。20 九月 2024Data 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；20 九月 2024Data Mining: Concepts and Techniques49Normalized Cut III设secondvalue及Vector分别为上述方程的第二小特征值及其对应的特征向量；利用Vector向量对对象进行划分。如果需要进一步划分，则重复上述步骤，直到满足要求为止。20 九月 2024Data Mining: Concepts and Techniques50第七章第七章 聚类分析聚类分析什么是聚类分析什么是聚类分析? ?数据类型及其相似性与非相似性计算数据类型及其相似性与非相似性计算算法复杂性及近似算法概念算法复杂性及近似算法概念划分方法划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法层次方法单链接与全链接20 九月 2024Data 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)20 九月 2024Data Mining: Concepts and Techniques52层次聚类法：聚类之间的距离层次聚类法：聚类之间的距离最短与最长距离：若定义两个聚类之间的距离为二者对象之间的最小距离，则该算法也称为单链接算法(Single-Linkage Algorithm，SLA)，也称为最小生成树算法。若定义两个聚类之间的距离为二者对象之间的最大距离，则该算法也称为全链接算法(Complete-Linkage Algorithm，CLA)。20 九月 2024Data Mining: Concepts and Techniques53单链接算法单链接算法 I给定5个对象间的距离如下表No1 2 3 4 51234506 02 4 03 4 5 07 1 5 5 020 九月 2024Data Mining: Concepts and Techniques54单链接算法单链接算法 II步骤步骤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=6D2,53=mind23, d53=min4,5=4D2,54=mind24, d54=min4,5=4No2,5 1 3 42,513406 04 2 04 3 5 020 九月 2024Data Mining: Concepts and Techniques55单链接算法单链接算法 III4个聚类 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凝聚成一个新的聚类1,3,4.No2,5 1,3 42,51,3404 04 3 020 九月 2024Data Mining: Concepts and Techniques56单链接算法单链接算法 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.No2,5 1,3,42,51,3,404 020 九月 2024Data Mining: Concepts and Techniques57单链接算法单链接算法 V系统树图 演示了层次聚类的过程 1 2 3 4 5 Steps2513420 九月 2024Data Mining: Concepts and Techniques58SLA与与CLA的的理论性质理论性质SLA与最小生成树的关系：与最小生成树的关系：最大分离度一定等于最小生成树中某条边的值。定理：定理：SLA算法找到了最大分离度。CLA算法是一个k-Cluster的logk-近似算法(2 k n)20 九月 2024Data Mining: Concepts and Techniques59聚类分离度聚类分离度分离度分离度s(P)聚类直径聚类直径直径直径d(P)20 九月 2024Data Mining: Concepts and Techniques60MRSD的优化目标的优化目标优化目标优化目标定理定理. 对于对于 k 3, MRSD的判定问题是一个的判定问题是一个 NP-完全问题。完全问题。20 九月 2024Data Mining: Concepts and Techniques61合并操作合并操作合并操作合并操作20 九月 2024Data Mining: Concepts and Techniques62Merge u and vMRSD算法（算法（k=2)20 九月 2024Data 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);返回最好的解;MRSD的最优性的最优性定理：上述算法返回定理：上述算法返回k=2的最优解，时的最优解，时间复杂性为间复杂性为O(n3)20 九月 2024Data Mining: Concepts and Techniques649/20/2024示例示例左左: 输入图输入图G. 右右: G的最小生成树的最小生成树 Tmin . 9/20/2024示例示例(Cont.)右: 左图的最大生成树 Tmax . Tmax 的2着色产生划分 P = 1, 2, 6, 3, 4, 5 : d(P) = 6, s(P) = 1, and s(P) / d(P) = 1/6 9/20/2024示例示例(Cont.)中: 合并边(1, 2)、 (5, 6)后的图. 右: 中间图的最大生成树Tmax. Tmax 的2着色产生划分 P = 1, 2, 3, 4, 5, 6 : d(P) = 7, s(P) = 2, and s(P) / d(P) = 2/7. 合并9/20/2024示例示例(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. 合并9/20/2024示例示例(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. 合并9/20/2024示例示例(Cont.)右: 合并边(3, 5)的图. |Tmin| = ，算法停止. 最优划分P = 1, 2, 3, 4, 5, 6 ，最优值5/9. 合并9/20/2024左至右左至右: MRSD, NCut_C, NCut_S, CLA, SLA9/20/2024左至右左至右: MRSD, NCut_C, NCut_S, CLA, SLA9/20/2024运行时间运行时间 (Seconds)MATLAB R2009b, NCut_C (eig), NCut_S (eigs), 2.6 GHz Pentium MATLAB R2009b, NCut_C (eig), NCut_S (eigs), 2.6 GHz Pentium Dual-Core with 2G bytes of RAM Dual-Core with 2G bytes of RAM 9/20/2024MRSD9/20/2024MRSD