数据挖掘导论-ch8

1、数据挖掘集群分析：基本概念和算法数据挖掘集群分析：基本概念和算法第二章第二章数据挖掘简介数据挖掘简介 数据挖掘导论 5/2/2022 1 数据挖掘导论 5/2/2022 2 什么是集群分析？什么是集群分析？l查找对象组，使得组中的对象将彼此相似（或相关），并且与其他组中的对象不同（或不相关）群间距离最大化簇内距离被最小化 数据挖掘导论 5/2/2022 3 聚类分析的应用聚类分析的应用l理解理解 用于浏览的组相关文档，具有类似功能的组基因和蛋白质，或具有相似价格波动的组股票l总结总结 减少大型数据集的大小在澳大利亚聚集降水在澳大利亚聚集降水 数据挖掘导论 5/2/2022 4 什么不是集群分析

2、？什么不是集群分析？l监督分类 有类标签信息l简单分割 按姓氏按字母顺序将学生分成不同的注册组l查询的结果 分组是外部规范的结果l图分区 一些相互关联和协同，但领域不相同 数据挖掘导论 5/2/2022 5 集群的概念可能是模糊的集群的概念可能是模糊的有多少个集群？四个集群两个集群六个集群 数据挖掘导论 5/2/2022 6 集群类型集群类型l聚类是一组聚类l分层和分区集群之间的重要区别l部分聚类 将数据对象划分成非重叠子集（聚类），使得每个数据对象恰好在一个子集中l分层聚类 组织为分层树的一组嵌套集群 数据挖掘导论 5/2/2022 7 分割聚类分割聚类原始的点原始的点分割聚类分割聚类 数据

3、挖掘导论 5/2/2022 8 层次聚类层次聚类p4p1p3p2 p4 p1 p3 p2 p4p1p2p3p4p1 p2p3传统分层聚类传统分层聚类非传统的分层聚类非传统的分层聚类非传统树状图非传统树状图传统树图传统树图 数据挖掘导论 5/2/2022 9 群集集之间的其他区别群集集之间的其他区别l独占与非独占 在非排他性聚类中，点可以属于多个聚类 可以表示多个类或“边界”点l模糊与非模糊 在模糊聚类中，一个点属于每个聚类，其权重在0和1之间 权重必须为1 概率聚类具有类似的特征l部分与完整 在某些情况下，我们只想聚集一些数据l非均质对均质 集群的大小，形状和密度大不相同 数据挖掘导论 5/2

4、/2022 10 集群类型集群类型l 分离良好的集群l 基于中心的集群l 连续簇l 基于密度的聚类l 属性或概念l 由目标函数描述 数据挖掘导论 5/2/2022 11 集群类型：分离集群类型：分离l分离的群集： 集群是一组点，使得集群中的任何点都比集群中的任何点更接近（或更类似于）集群中的每个其他点。3 well-separated clusters 数据挖掘导论 5/2/2022 12 集群类型：基于中心集群类型：基于中心l基于中心 群集是一组对象，使得群集中的对象比群集的“中心”更接近（更类似于）任何其他群集的中心 聚类的中心通常是质心，聚类中所有点的平均值，或聚类的最“代表性”点4个基

5、于中心的集群个基于中心的集群 数据挖掘导论 5/2/2022 13 集群类型：基于连续性集群类型：基于连续性l连续簇（最近邻或传递） 聚类是一组点，使得聚类中的点与不在聚类中的任何点更接近（或更类似于）聚类中的一个或多个其它点。8个连续簇个连续簇 数据挖掘导论 5/2/2022 14 集群类型：基于密度集群类型：基于密度l基于密度 簇是由低密度区域与其它高密度区域分开的点的密集区域。 当集群不规则或交织，并且存在噪声和异常值时使用。6个基于密度的集群个基于密度的集群 数据挖掘导论 5/2/2022 15 集群类型：概念集群集群类型：概念集群l共享财产或概念集群 查找共享一些共同属性或表示特定概

6、念的集群。. 2个交叉的集群个交叉的集群 数据挖掘导论 5/2/2022 16 聚类类型：目标函数聚类类型：目标函数l由目标函数定义的集群 找到最小化或最大化目标函数的集群。 列举所有可能的方法，将点分成聚类，并通过使用给定的目标函数评估每个潜在的集群的“好”。 （NP问题） 可以有全球或地方目标。u 分层聚类算法通常具有局部目标u 部分算法通常具有全局目标 全局目标函数方法的变化是将数据拟合到参数化模型。u 从数据确定模型的参数。u 混合模型假设数据是多个统计分布的“混合”。 数据挖掘导论 5/2/2022 17 集群类型：目标函数集群类型：目标函数l将聚类问题映射到不同的域，并解决该域中的

7、相关问题 接近矩阵定义加权图，其中节点是被聚类的点，加权边表示点之间的近似 聚类等效于将图形分成连接的组件，每个集群一个 想要最小化群集之间的边缘权重并且最大化群集内的边缘权重 数据挖掘导论 5/2/2022 18 输入数据的特性很重要输入数据的特性很重要l接近度或密度测量的类型这是一个派生的度量，但是聚类的中心l稀疏性说明相似性的类型增加效率l属性类型说明相似性的类型l数据类型说明相似性的类型其他特性，例如自相关l尺寸l噪声和异常值l分发类型 数据挖掘导论 5/2/2022 19 聚类算法聚类算法lK均值及其变体l分层聚类l基于密度的聚类 数据挖掘导论 5/2/2022 20 K-means

8、聚类聚类l分层聚类方法l每个聚类与质心（中心点）相关联l每个点都分配给具有最接近质心的聚类l必须指定群集数Kl基本算法非常简单 数据挖掘导论 5/2/2022 21 K-means聚类聚类 - 详细信息详细信息l初始质心通常是随机选择的。生产的集群从一个运行到另一个运行。l质心是（通常）集群中的点的平均值。l“亲密度”通过欧几里得距离，余弦相似性，相关性等来度量。lK均值将收敛用于上述的共同相似性度量。l大多数收敛发生在前几次迭代中。通常停止条件改变为“直到相对较少的点改变群集”l复杂性为O ( n * K * I * d )n = 点数, K = 聚类数, I = 迭代次数, d = 属性数

9、 数据挖掘导论 5/2/2022 22 两种不同的两种不同的K均值聚类均值聚类-2-1.5-1-0.500.511.5200.511.522.53xy-2-1.5-1-0.500.511.5200.511.522.53xy次优聚类次优聚类-2-1.5-1-0.500.511.5200.511.522.53xy最优聚类最优聚类原始的点 数据挖掘导论 5/2/2022 23 选择初始矩心的重要性选择初始矩心的重要性-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration

10、2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5-2-1.5-1-0.500.511.5200.511.522.53xyIteration 6 数据挖掘导论 5/2/2022 24 选择初始矩心的重要性选择初始矩心的重要性-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.

11、511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5-2-1.5-1-0.500.511.5200.511.522.53xyIteration 6 数据挖掘导论 5/2/2022 25 评估评估K-means集群集群l最常见的度量是平方误差和（SSE） 对于每个点，误差是到最近群集的距离 为了得到SSE，我们计算这些误差并

12、求和 x是簇Ci中的数据点，mi是簇Ci的代表点u 可以显示mi对应于集群的中心（平均） 给定两个簇，我们可以选择具有最小误差的那个 减少SSE的一个简单方法是增加K，即簇的数目u 具有较小K的良好聚类可以具有比具有较高K的较差聚类更低的SSEKiCxiixmdistSSE12),( 数据挖掘导论 5/2/2022 26 选择初始质心的重要性选择初始质心的重要性.-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200

13、.511.522.53xyIteration 3-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5 数据挖掘导论 5/2/2022 27 选择初始质心的重要性选择初始质心的重要性.-2-1.5-1-0.500.511.5200.511.522.53xyIteration 1-2-1.5-1-0.500.511.5200.511.522.53xyIteration 2-2-1.5-1-0.500.511.5200.511.522.53xyIteration 3

14、-2-1.5-1-0.500.511.5200.511.522.53xyIteration 4-2-1.5-1-0.500.511.5200.511.522.53xyIteration 5 数据挖掘导论 5/2/2022 28 Problems with Selecting Initial PointslIf there are K real clusters then the chance of selecting one centroid from each cluster is small. Chance is relatively small when K is largeIf clu

15、sters are the same size, n, thenFor example, if K = 10, then probability = 10!/1010 = 0.00036Sometimes the initial centroids will readjust themselves in right way, and sometimes they dontConsider an example of five pairs of clusters 数据挖掘导论 5/2/2022 29 10个集群示例个集群示例05101520-6-4-202468xyIteration 10510

16、1520-6-4-202468xyIteration 205101520-6-4-202468xyIteration 305101520-6-4-202468xyIteration 4从每对簇的一个簇中的两个初始质心开始从每对簇的一个簇中的两个初始质心开始 数据挖掘导论 5/2/2022 30 10个集群示例个集群示例05101520-6-4-202468xyIteration 105101520-6-4-202468xyIteration 205101520-6-4-202468xyIteration 305101520-6-4-202468xyIteration 4从每对簇的一个簇中的两个

17、初始质心开始从每对簇的一个簇中的两个初始质心开始 数据挖掘导论 5/2/2022 31 10个集群示例个集群示例从具有三个初始质心的一些簇对开始，而其他只有一个。从具有三个初始质心的一些簇对开始，而其他只有一个。05101520-6-4-202468xyIteration 105101520-6-4-202468xyIteration 205101520-6-4-202468xyIteration 305101520-6-4-202468xyIteration 4 数据挖掘导论 5/2/2022 32 10个集群示例个集群示例从具有三个初始质心的一些簇对开始，而其他只有一个。从具有三个初始质心

18、的一些簇对开始，而其他只有一个。05101520-6-4-202468xyIteration 105101520-6-4-202468xyIteration 205101520-6-4-202468xyIteration 305101520-6-4-202468xyIteration 4 数据挖掘导论 5/2/2022 33 初始中心问题的解决方案初始中心问题的解决方案l多次运行 有帮助，但概率不一定会在你的那边l示例并使用分层聚类来确定初始质心l选择多于k个初始质心，然后在这些初始质心中进行选择 选择最广泛分隔l后期处理l平分K均值 不易受初始化问题影响 数据挖掘导论 5/2/2022 34

19、 处理空集群处理空集群l基本K-means算法可以产生空集群l几种策略 选择对SSE贡献最大的点 从具有最高SSE的集群中选择一个点 如果有几个空集群，以上可以重复几次 数据挖掘导论 5/2/2022 35 增量更新中心增量更新中心l在基本K-means算法中，在将所有点都分配给质心之后更新质心l另一种方法是在每次分配后更新质心（增量法） 每个分配更新零或两个质心 更贵 引入顺序依赖 永远不要得到一个空集群 可以使用“权重”来改变影响 数据挖掘导论 5/2/2022 36 预处理和后处理预处理和后处理l预处理 规范化数据 消除异常值l后期处理 消除可能代表异常值的小集群 分裂“松散”簇，即具有

20、相对高的SSE的簇 合并“接近”并且具有相对低的SSE的集群 可以在群集过程中使用这些步骤u ISODATA 数据挖掘导论 5/2/2022 37 平分平分K均值均值l平分K-means算法可以产生分区或层次聚类的K均值的变体 数据挖掘导论 5/2/2022 38 平分平分K-means示例示例 数据挖掘导论 5/2/2022 39 K-means的限制的限制l当集群不同时，K均值存在问题 尺寸 密度 非球状形状l当数据包含异常值时，K-means存在问题 数据挖掘导论 5/2/2022 40 K-means的限制：不同的大小的限制：不同的大小Original PointsK-means (3

21、 Clusters) 数据挖掘导论 5/2/2022 41 K-means的限制：不同的密度的限制：不同的密度Original PointsK-means (3 Clusters) 数据挖掘导论 5/2/2022 42 K-means的局限性：非球形形状的局限性：非球形形状Original PointsK-means (2 Clusters) 数据挖掘导论 5/2/2022 43 克服克服K均值限制均值限制Original PointsK-means Clusters一个解决方案是使用许多集群。查找集群的一部分，但需要放在一起。 数据挖掘导论 5/2/2022 44 克服克服K均值限制均值限制

22、Original PointsK-means Clusters 数据挖掘导论 5/2/2022 45 克服克服K均值限制均值限制Original PointsK-means Clusters 数据挖掘导论 5/2/2022 46 层次聚类层次聚类l生成组织为分层树的一组嵌套集群l可以可视化为树状图 一个树形图，记录合并或分割的序列13254600.050.10.150.212345612345 数据挖掘导论 5/2/2022 47 层次聚类的优点层次聚类的优点l不必假设任何特定数量的集群 任何所需数量的簇可以通过在适当水平“切割”树状图获得l它们可以对应于有意义的分类法 生物科学（例如，动物王

23、国，系统发育重建，.） 数据挖掘导论 5/2/2022 48 层次聚类层次聚类l两种主要类型的层次聚类 聚集： u 从点作为单个集群开始u 在每个步骤，合并最近的一对簇直到只剩下一个簇（或k簇） 分歧： u 从一个全包的集群开始u 在每个步骤，拆分一个集群，直到每个集群包含一个点（或有k个集群）l传统的分层算法使用相似性或距离矩阵 一次合并或拆分一个群集 数据挖掘导论 5/2/2022 49 聚集聚类算法聚集聚类算法l更流行的层次聚类技术l基本算法很简单1.计算接近矩阵2.让每个数据点是一个集群3.重复重复4.合并两个最接近的簇5.更新接近矩阵6.直到只剩下一个群集 l键操作是计算两个簇的接近

24、度定义集群之间的距离的不同方法区分不同的算法 数据挖掘导论 5/2/2022 50 开始情境l从单个点的簇和邻近矩阵开始p1p3p5p4p2p1p2p3p4p5. . .相似矩阵相似矩阵 数据挖掘导论 5/2/2022 51 中级情况中级情况l在一些合并步骤之后，我们有一些集群C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5相似矩阵相似矩阵 数据挖掘导论 5/2/2022 52 中级情况中级情况l我们想合并两个最近的聚类（C2和C5）并更新邻近矩阵。C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5相似矩阵相似矩阵 数据挖掘导论 5/2/2022 53 合并后合并后l问题

25、是“我们如何更新邻近矩阵？”C1C4C2 U C5C3? ? ? ? ?C2 U C5C1C1C3C4C2 U C5C3C4相似矩阵相似矩阵 数据挖掘导论 5/2/2022 54 如何定义群集间相似性如何定义群集间相似性 errorp1p3p5p4p2p1p2p3p4p5. . .相似相似?l最小值l最大值l组平均l矩心之间的距离l由目标函数驱动的其他方法 Ward的方法使用平方误差相似矩阵相似矩阵 数据挖掘导论 5/2/2022 55 如何定义群集间相似性如何定义群集间相似性 p1p3p5p4p2p1p2p3p4p5. . .相似矩阵相似矩阵l最小值l最大值l组平均l矩心之间的距离l由目标函

26、数驱动的其他方法 Ward的方法使用平方误差 数据挖掘导论 5/2/2022 56 如何定义群集间相似性如何定义群集间相似性 p1p3p5p4p2p1p2p3p4p5. . .相似矩阵相似矩阵l最小值l最大值l组平均l矩心之间的距离l由目标函数驱动的其他方法 Ward的方法使用平方误差 数据挖掘导论 5/2/2022 57 如何定义群集间相似性如何定义群集间相似性 p1p3p5p4p2p1p2p3p4p5. . .相似矩阵相似矩阵l最小值l最大值l组平均l矩心之间的距离l由目标函数驱动的其他方法 Ward的方法使用平方误差 数据挖掘导论 5/2/2022 58 How to Define In

27、ter-Cluster Similarity p1p3p5p4p2p1p2p3p4p5. . .相似矩阵相似矩阵 l最小值l最大值l组平均l矩心之间的距离l由目标函数驱动的其他方法 Ward的方法使用平方误差 数据挖掘导论 5/2/2022 59 集群相似性：最小值或单链路集群相似性：最小值或单链路l两个簇的相似性基于不同簇中的两个最相似（最接近）点 由一对点确定，即由邻近图中的一个链接确定。I1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.6

28、0 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0012345 数据挖掘导论 5/2/2022 60 层次聚类：层次聚类：MIN嵌套集群嵌套集群树状图树状图1234561234536254100.050.10.150.2 数据挖掘导论 5/2/2022 61 MIN的优点的优点原始的点原始的点两个集群两个集群可以处理非椭圆形状可以处理非椭圆形状 数据挖掘导论 5/2/2022 62 MIN的缺点的缺点原始的点原始的点两个集群两个集群对噪声和异常值敏感对噪声和异常值敏感 数据挖掘导论 5/2/2022 63 集群相似性：集群相似性：MAX或完全链接或完全链接l两

29、个簇的相似性基于不同簇中的两个最不相似的点 由两个集群中的所有点对确定I1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0012345 数据挖掘导论 5/2/2022 64 分层聚类：分层聚类：MAX嵌套集群嵌套集群树状图树状图36412500.050.10.150.20.250.30.350.412345612534 数据挖掘导论 5/2/2022 65 MA

30、X的优点的优点原始的点原始的点两个集群两个集群不易受噪声和异常值影响不易受噪声和异常值影响 数据挖掘导论 5/2/2022 66 MAX的缺点的缺点原始的点原始的点两个集群两个集群 往往打破大集群往往打破大集群 偏向球状星团偏向球状星团 数据挖掘导论 5/2/2022 67 集群相似性：组平均集群相似性：组平均l两个聚类的接近度是两个聚类中的点之间的成对接近的平均值l需要使用平均连接可扩展性，因为总接近度有利于大集群|Cluster|Cluster)p,pproximity()Cluster,Clusterproximity(jiClusterpClusterpjijijjiiI1I2I3I4

31、I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0012345 数据挖掘导论 5/2/2022 68 分层聚类：组平均分层聚类：组平均嵌套集群嵌套集群树状图树状图36412500.050.10.150.20.2512345612534 数据挖掘导论 5/2/2022 69 分层聚类：组平均分层聚类：组平均l单链路和完全链路之间的妥协l优点 不易受噪声和异常值影响l缺点 偏向球

32、状星团 数据挖掘导论 5/2/2022 70 群集相似性：群集相似性：Ward的方法的方法l两个群集的相似性基于当两个群集合并时的平方误差的增加 与组平均值相似，如果点之间的距离是距离平方l不易受噪声和异常值影响l偏向球状星团l均值的分层模拟 可用于初始化K均值 数据挖掘导论 5/2/2022 71 分层聚类：比较分层聚类：比较组平均组平均Ward的方法的方法12345612534MINMAX123456125341234561253412345612345 数据挖掘导论 5/2/2022 72 分层聚类：时间和空间要求分层聚类：时间和空间要求lO(N2) 空间复杂度，因为它使用邻近矩阵。 N

33、 是点数。lO(N3) 在许多情况下的时间复杂度 有N个步骤，并且在每个步骤，必须更新和搜索大小， N2 ，邻近矩阵 对于一些方法，时间复杂度可以减少到O(N2 log(N) ) 数据挖掘导论 5/2/2022 73 层次聚类：问题和局限性层次聚类：问题和局限性l一旦决定组合两个集群，就不能撤销l没有目标函数被直接最小化l不同的方案具有以下一个或多个问题： 对噪声和异常值的敏感性 难以处理不同大小的簇和凸形 分离大集群 数据挖掘导论 5/2/2022 74 MST：分裂层次聚类：分裂层次聚类l构建MST（最小生成树） 从包含任何点的树开始 在连续的步骤中，寻找最接近的点对(p, q) ，使得一

34、个点(p)在当前树中，而另一个(q)不在 将q添加到树中，并在p和q之间放置一条边 数据挖掘导论 5/2/2022 75 MST：分裂层次聚类：分裂层次聚类l使用MST构建集群的层次结构 数据挖掘导论 5/2/2022 76 DBSCANlDBSCAN是基于密度的算法。密度=指定半径内的点数(Eps)如果点在Eps中具有多于指定数量的点(MinPts)则点是核心点u这些是在集群内部的点边界点在Eps中少于MinPts，但在核心点附近噪声点是不是核心点或边界点的任何点。 数据挖掘导论 5/2/2022 77 DBSCAN:核心，边界和噪声点核心，边界和噪声点 数据挖掘导论 5/2/2022 78

35、 DBSCAN算法算法l消除噪点l对剩余点执行聚类 数据挖掘导论 5/2/2022 79 DBSCAN: 核心，边界和噪声点核心，边界和噪声点原始的点原始的点点类型：点类型：核心核心，边界边界和和噪声噪声Eps = 10, MinPts = 4 数据挖掘导论 5/2/2022 80 当当DBSCAN工作良好工作良好原始的点原始的点聚类聚类 抗噪声抗噪声 可以处理不同形状和大小的集群可以处理不同形状和大小的集群 数据挖掘导论 5/2/2022 81 当当DBSCAN不工作不工作原始的点原始的点(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) 变化密度变化密度

36、高维数据高维数据 数据挖掘导论 5/2/2022 82 DBSCAN: 确定确定 EPS and MinPtsl想法是，对于集群中的点，它们的第k个最近邻居在大致相同的距离l噪声点具有在更远距离处的第k个最近邻l因此，绘制每个点到其第k个最近邻的排序距离 数据挖掘导论 5/2/2022 83 集群有效性集群有效性l对于监督分类，我们有各种各样的措施来评估我们的模型是多么好 精度，精度，回调l对于聚类分析，类似的问题是如何评估所得到的聚类的“好处”？l但“群集在眼前的人”！l那么为什么我们要评价它们呢？ 避免在噪声中找到模式 比较聚类算法 比较两组集群 比较两个集群 数据挖掘导论 5/2/202

37、2 84 随机数据中找到的簇随机数据中找到的簇00.20.40.60.8100.10.20.30.40.50.60.70.80.91xy随机点随机点00.20.40.60.8100.10.20.30.40.50.60.70.80.91xyK-means00.20.40.60.8100.10.20.30.40.50.60.70.80.91xyDBSCAN00.20.40.60.8100.10.20.30.40.50.60.70.80.91xy完整链接完整链接 数据挖掘导论 5/2/2022 85 1.确定一组数据的聚类趋势，即，区分数据中是否实际存在非随机结构。 2.将聚类分析的结果与外部已知的

38、结果（例如，与外部给定的类标签）进行比较。3.评估聚类分析的结果在不参考外部信息的情况下适合数据的程度。 - 仅使用数据4.比较两个不同的聚类分析集的结果以确定哪个更好。5.确定集群的“正确”数量。对于2,3和4，我们可以进一步区分我们是要评估整个聚类还是单个聚类。集群验证的不同方面集群验证的不同方面 数据挖掘导论 5/2/2022 86 l用于判断聚类有效性的各个方面的数值度量被分类为以下三种类型。 外部索引：用于测量集群标签与外部提供的类标签匹配的程度。u熵 内部索引：用于在不考虑外部信息的情况下测量聚类结构的好坏。 u平方误差和(SSE) 相对索引：用于比较两个不同的聚类或聚类。 u通常

39、，对于该函数使用外部或内部索引，例如SSE或熵l有时，这些被称为标准而不是索引 然而，有时候标准是一般策略，指数是实现标准的数值度量。集群有效性的测度集群有效性的测度 数据挖掘导论 5/2/2022 87 l两个矩阵接近矩阵“发生率”矩阵u每个数据点有一行和一列u如果相关联的点对属于同一群集，则条目为1u如果相关联的点对属于不同的集群，则条目为0l计算两个矩阵之间的相关性由于矩阵是对称的，因此仅需要计算n(n-1) / 2个条目之间的相关性。l高相关性指示属于相同聚类的点彼此接近。 l不是一些密度或基于连续性的群集的好度量。通过相关测量集群有效性通过相关测量集群有效性 数据挖掘导论 5/2/2

40、022 88 通过相关测量集群有效性通过相关测量集群有效性l以下两个数据集的K均值聚类的发生率和接近矩阵的相关性。 00.20.40.60.8100.10.20.30.40.50.60.70.80.91xy00.20.40.60.8100.10.20.30.40.50.60.70.80.91xyCorr = -0.9235Corr = -0.5810 数据挖掘导论 5/2/2022 89 l对于聚类标签排序相似性矩阵并且可视地检查。使用集群验证的相似性矩阵使用集群验证的相似性矩阵00.20.40.60.8100.10.20.30.40.50.60.70.80.91xyPointsPoints2

41、0406080100102030405060708090100Similarity00.10.20.30.40.50.60.70.80.91 数据挖掘导论 5/2/2022 90 使用集群验证的相似性矩阵使用集群验证的相似性矩阵l随机数据中的簇并不那么脆弱PointsPoints20406080100102030405060708090100Similarity00.10.20.30.40.50.60.70.80.91DBSCAN00.20.40.60.8100.10.20.30.40.50.60.70.80.91xy 数据挖掘导论 5/2/2022 91 PointsPoints204060

42、80100102030405060708090100Similarity00.10.20.30.40.50.60.70.80.91使用集群验证的相似性矩阵使用集群验证的相似性矩阵l随机数据中的簇并不那么脆弱K-means00.20.40.60.8100.10.20.30.40.50.60.70.80.91xy 数据挖掘导论 5/2/2022 92 使用集群验证的相似性矩阵使用集群验证的相似性矩阵l随机数据中的簇并不那么脆弱00.20.40.60.8100.10.20.30.40.50.60.70.80.91xyPointsPoints204060801001020304050607080901

43、00Similarity00.10.20.30.40.50.60.70.80.91Complete Link 数据挖掘导论 5/2/2022 93 使用集群验证的相似性矩阵使用集群验证的相似性矩阵1 235647DBSCAN00.10.20.30.40.50.60.70.80.915001000150020002500300050010001500200025003000 数据挖掘导论 5/2/2022 94 l更复杂的图形中的集群没有很好地分离l内部索引：用于在不考虑外部信息的情况下测量聚类结构的好坏 SSElSSE有利于比较两个集群或两个集群（平均SSE）l也可以用来估计集群的数量内部方法

44、：内部方法：SSE2 5 1015202530012345678910KSSE51015-6-4-20246 数据挖掘导论 5/2/2022 95 内部方法：内部方法：SSElSSE曲线为更复杂的数据集1 235647SSE of clusters found using K-means 数据挖掘导论 5/2/2022 96 l需要一个框架来解释任何措施。例如，如果我们的评价方法的价值，10，是好，公平还是穷？l统计提供了集群有效性的框架聚类结果越“非典型”，它越可能代表数据中的有效结构可以将由随机数据或聚类产生的索引的值与聚类结果的值进行比较。u如果索引的值不太可能，则集群结果是有效的这些方法更复杂，更难理解。l为了比较两个不同的聚类分析集的结果，框架不太必要。然而，存在两个指数值之间的差是否显着