模式识别：聚类

2020/1/311第6讲：聚类•6.1什么是聚类•6.2聚类算法的评估标准•6.3聚类分析简介•6.4数据挖掘对聚类算法的要求•6.5聚类分析中的数据类型•6.6聚类算法的分类•6.7本讲小结2020/1/3126.1什么是聚类•聚类就是将对物理或抽象对象的集合分组成为由类似的对象组成的多个簇的过程。•聚类生成的组称为簇（Cluster），簇是数据对象的集合。簇内部的任意两个对象之间具有较高的相似度，而属于不同簇的两个对象间具有较高的相异度。•相异度可以根据描述对象的属性值计算，对象间的距离是最常采用的度量指标。2020/1/3136.2聚类算法的评估标准•分类精度：聚类的准确程度•loglikelihood2020/1/3146.3聚类分析简介•聚类分析是数据分析中的一种重要技术，它的应用极为广泛。许多领域中都会涉及聚类分析方法的应用与研究工作，如数据挖掘、统计学、机器学习、模式识别、生物学、空间数据库技术、电子商务等。2020/1/315聚类分析简介（续）•从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。2020/1/316聚类分析简介（续）•从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。2020/1/317聚类分析简介（续）•从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。•就数据挖掘功能而言，聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。•聚类分析还可以作为其他数据挖掘任务（如分类、关联规则）的预处理步骤。•数据挖掘领域主要研究面向大型数据库、数据仓库的高效实用的聚类分析算法。2020/1/3186.4数据挖掘对聚类算法的要求•数据挖掘对聚类算法的典型要求包括：–可伸缩性–处理不同类型属性的能力–发现任意形状的聚类–用于决定输入参数的领域知识最小化–处理噪声数据的能力–对输入记录顺序的不敏感性–高维性–基于约束的聚类–聚类结果的可解释性和实用性2020/1/3196.5聚类分析中的数据类型•聚类分析主要针对的数据类型包括区间标度变量、二元变量、标称变量、序数型变量、比例标度型变量，以及由这些变量类型构成的复合类型。•一些基于内存的聚类算法通常采用数据矩阵和相异度矩阵两种典型的数据结构。2020/1/3110数据矩阵（DataMatrix）•设有n个对象，可用p个变量（属性）描述每个对象，则np矩阵称为数据矩阵。数据矩阵是对象-变量结构的数据表达方式。npnnppxxxxxxxxx2122221112112020/1/3111相异度矩阵（DissimilarityMatrix）•按n个对象两两间的相异度构建n阶矩阵（因为相异度矩阵是对称的，只需写出上三角或下三角即可）：•其中d(i,j)表示对象i与j的相异度，它是一个非负的数值。当对象i和j越相似或“接近”时，d(i,j)值越接近0；而对象i和j越不相同或相距“越远”时，d(i,j)值越大。显然，d(i,j)=d(j,i)，d(i,i)=0。相异度矩阵是对象-对象结构的一种数据表达方式。0)2,()1,(0)2,3()1,3(0)1,2(0ndndddd2020/1/3112对象间距离的计算•设两个p维向量xi=(xi1,xi2,…,xip)T和xj=(xj1,xj2,…,xjp)T分别表示两个对象，有多种形式的距离度量可以采用。–闵可夫斯基（Minkowski）距离–曼哈坦（Manhattan）距离–欧几里得（Euclidean）距离–切比雪夫（Chebyshev）距离–马哈拉诺比斯（Mahalanobis）距离2020/1/31136.6聚类算法的分类•从大体上来看，聚类算法可以划分为如下五种类型：1)基于划分的方法2)基于层次的方法3)基于密度的方法4)基于网格的方法5)基于模型的方法2020/1/3114基于划分的方法•对于一个给定的n个对象或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成k个划分块，每个划分块为一个簇，这就是划分方法。•划分方法满足两个条件：–（1）每个分组至少包含一个对象；–（2）每个对象必属于且仅属于某一个分组。•常见的划分方法有k-均值方法和k-中心点方法。其他方法大都是这两种方法的变形。2020/1/3115基于划分的方法（续）2020/1/3116k-均值算法•k-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标函数最小化，从而使生成的簇尽可能地紧凑和独立。–首先，随机选取k个对象作为初始的k个簇的质心；–然后，将其余对象根据其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。–这个迭代重定位过程不断重复，直到目标函数最小化为止。2020/1/3117k-均值算法（续）•输入期望得到的簇的数目k，n个对象的数据库。•输出使得平方误差准则函数最小化的k个簇。•方法–选择k个对象作为初始的簇的质心；–repeat–计算对象与各个簇的质心的距离，将对象划分到距离其最近的簇；–重新计算每个新簇的均值；–until簇的质心不再变化。2020/1/3118k-均值算法（续）-2-1.5-1-0.500.511.5200.511.522.53xy-2-1.5-1-0.500.511.5200.511.522.53xyIteration1-2-1.5-1-0.500.511.5200.511.522.53xyIteration2-2-1.5-1-0.500.511.5200.511.522.53xyIteration3-2-1.5-1-0.500.511.5200.511.522.53xyIteration4-2-1.5-1-0.500.511.5200.511.522.53xyIteration5-2-1.5-1-0.500.511.5200.511.522.53xyIteration62020/1/3119-2-1.5-1-0.500.511.5200.511.522.53xy-2-1.5-1-0.500.511.5200.511.522.53xyIteration1-2-1.5-1-0.500.511.5200.511.522.53xyIteration2-2-1.5-1-0.500.511.5200.511.522.53xyIteration3-2-1.5-1-0.500.511.5200.511.522.53xyIteration4-2-1.5-1-0.500.511.5200.511.522.53xyIteration5k-均值算法（续）2020/1/3120Howmanyclusters?FourClustersTwoClustersSixClustersk-均值算法（续）2020/1/3121k-均值算法（续）2020/1/3122k-均值算法（续）pqmiiiqpqpdist12)(),(Euclideandistance2020/1/3123k-均值方法的扩展•在初始的k个均值选择、对象相异度计算、簇均值的计算等方面采取不同的策略将得到k-均值算法的很多变形。•k-模方法用模代替簇的均值，用新的相异性度量方法处理对象，用基于频率的方法修改簇的模。•k-原型方法将k-均值和k-模算法集成在一起，用于处理含有数值和分类值属性的数据聚类。•EM算法也对k-均值方法进行了扩展。2020/1/3124k-中心点算法•k-均值算法采用簇的质心来代表一个簇，质心是簇中其他对象的参照点。因此，k-均值算法对孤立点是敏感的，如果具有极大值，就可能大幅度地扭曲数据的分布。•k-中心点算法是为消除这种敏感性提出的，它选择簇中位置最接近簇中心的对象（称为中心点）作为簇的代表点，目标函数仍然可以采用平方误差准则。•采用k-中心点算法有两个好处：–对属性类型没有局限性；–通过簇内主要点的位置来确定选择中心点，对孤立点的敏感性小。2020/1/3125k-中心点算法（续）•首先，随机选择k个对象作为初始的k个簇的代表点，将其余对象根据其与代表点对象的距离分配到最近的簇；•然后，反复用非代表点来代替代表点，以改进聚类质量，聚类质量用一个代价函数来估计，该函数度量对象与代表点对象之间的平均相异度。2020/1/3126k-中心点算法（续）•输入n个对象的数据库，期望得到的簇的数目k•输出使得所有对象与其最近中心点的偏差总和最小化的k个簇•方法–选择k个对象作为初始的簇中心–repeat–对每个对象，计算离其最近的簇中心点，并将对象分配到该中心点代表的簇–随机选取非中心点Orandom–计算用Orandom代替Oj形成新集合的总代价S–如果S0，用Orandom代替Oj，形成新的k个中心点的集合–until不再发生变化2020/1/3127基于层次的方法•层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。•按自底向上层次分解，则称为凝聚的层次聚类。•按自顶向下层次分解，就称为分裂的层次聚类。•典型的例子有：BIRCH、CURE、Chameleon等2020/1/3128凝聚的和分裂的层次聚类•凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。•分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。2020/1/3129距离度量•簇的凝聚或分裂要遵循一定的距离（或相似度）准则。常见的簇间距离度量方法如下：–最小距离（单链接方法）–最大距离（完全链接方法）–平均距离（平均链接方法）–均值的距离（质心方法）•对象间距离函数有欧氏距离、曼哈坦距离、闵可夫斯基距离、马氏距离等。2020/1/3130基于密度的方法•基于密度的方法主要有两类，即基于连通性的算法和基于密度函数的算法。•基于连通性的算法有DBSCAN和OPTICS等。•基于密度函数的算法有DENCLUE等。2020/1/3131基于网格的方法•基于网格的方法首先将空间量化为有限数目的单元，然后在这个量化空间上进行所有的聚类操作。•这类方法的处理时间不受数据对象数目影响，仅依赖于量化空间中每一维上的单元数目，因此处理速度较快。•典型的例子有STING、CLIQUE、WaveCluster2020/1/3132基于模型的方法•基于模型的聚类方法建立在数据符合潜在的概率分布这一假设基础之上。该类方法试图优化给定数据与某些数学模型之间的拟合。主要有统计学方法和神经网络方法等。•典型的例子有：COBWEB、CLASSIT、AutoClass2020/1/31336.7本讲小结•本讲主要讨论了一些基本聚类算法：–基于划分的方法主要包括k-均值算法和k-中心点算法，以及这两种算法的变种等算法。–基于层次的方法主要包括BIRCH、CURE、Chameleon等算法。–基于密度的方法主要包括DBSCAN、OPTICS、DENCLUE等算法。–基于网格的方法主要包括STING、CLIQUE、WaveCluster等算法。–基于模型的方法主要包括COBWEB、CLASSIT、AutoClass等算法。