12.2.层次聚类及基于密度的

1、层次聚类和基于密度的聚类王成 （副教授）华侨大学计算机学院 主要内容聚类算法分类层次聚类算法基于密度的聚类算法聚类算法分类聚类基于密度凝聚型算法DBSCAN分裂型算法层次方法上图仅是一个大致分类。文献中存在大量的聚类算法，很难提出一个简洁的分类，这些类别本身可能重叠，使一种算法同时具有几种类别的特征。k-MeansK-中心点划分方法划分方法(Partitioning methods)给定n个实例的数据集D，以及要生成的簇数目k，划分算法将实例组织为k个划分(k=n)，每个划分代表一个簇典型的划分算法: k-均值、k-中心点主要内容聚类算法分类层次聚类算法基于密度的聚类算法层次方法(Hierar

2、chical methods)层次聚类算法将实例组成一棵聚类树，可以发现类的层次关系福州厦门福建.杭州浙江华东.石家庄河北.华北中国树状图(Dendrogram)层次方法(Hierarchical methods)篮球新闻足球新闻体育新闻.社会新闻新闻层次方法(Hierarchical methods)凝聚层次聚类(Agglomerative)：采用自底向上策略，首先将每个对象作为单独的一个原子簇，然后合并这些原子簇形成越来越大的簇，直到所有的对象都在一个簇中（层次的最上层），或者达到一个终止条件。绝大多数层次聚类方法属于这一类。分裂层次聚类(Divisive)：采用自顶向下策略，首先将所有对

3、象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一个簇，或者达到某个终止条件，例如达到了某个希望的簇的数目，或者两个最近的簇之间的距离超过了某个阈值。凝聚层次聚类(Agglomerative)abecdabdecdeabcde分裂层次聚类(Divisive)abecdabdecdeabcde和基于划分的聚类的区别？以k-Means为例，如果是针对a,b,c,d,e这5个数据点abecdk=2k=3基于链接的凝聚型层次聚类算法1. 初始时，所有点都是单独的簇(如果有100个数据点，此时就有100个簇)2. 找到距离最近的两个簇，合并它们3. 重复第2步，直到只剩下一个簇(1,2)(6

4、,3)(8,2)(6,1)(3,3)簇C1簇C2但问题是，要怎么计算两个簇之间的距离呢？这样？或是这样？还是这样？如何计算两个簇之间的距离比较合理？四种不同的簇间距离度量最小距离最大距离均值距离平均距离四种不同的簇间距离度量四个广泛采用的簇间距离度量方法如下，其中|p-p|是两个对象或点p和p之间的距离，mi是簇Ci的均值，而ni是簇Ci中对象的数目最小距离(1,2)(6,3)(8,2)(6,1)(3,3)各点间的曼哈顿距离：d(1,2), (6,3) = 6d(1,2), (8,2) = 7d(1,2), (6,1) = 6d(3,3), (6,3) = 3d(3,3), (8,2) = 6

5、d(3,3), (6,1) = 5最小距离？= d(3,3), (6,3) = 3最大距离(1,2)(6,3)(8,2)(6,1)(3,3)各点间的曼哈顿距离：d(1,2), (6,3) = 6d(1,2), (8,2) = 7d(1,2), (6,1) = 6d(3,3), (6,3) = 3d(3,3), (8,2) = 6d(3,3), (6,1) = 5最大距离？= d(1,2), (8,2) = 7均值距离(1,2)(6,3)(8,2)(6,1)(3,3)各点间的曼哈顿距离：d(1,2), (6,3) = 6d(1,2), (8,2) = 7d(1,2), (6,1) = 6d(3,

6、3), (6,3) = 3d(3,3), (8,2) = 6d(3,3), (6,1) = 5均值距离？= d(2, 2.5), (6.67, 2) = 5.17(2,2.5)(6.67,2)平均距离(1,2)(6,3)(8,2)(6,1)(3,3)各点间的曼哈顿距离：d(1,2), (6,3) = 6d(1,2), (8,2) = 7d(1,2), (6,1) = 6d(3,3), (6,3) = 3d(3,3), (8,2) = 6d(3,3), (6,1) = 5平均距离？= (6 + 7 + 6 + 3 + 6 + 5) / (2 * 3)层次方法当算法使用最小距离衡量簇间距离时，称为

7、最近邻聚类算法(nearest-neighbor clustering)，或单链接算法(single-linkage clustering)当算法使用最大距离度量簇间距离时，称为最远邻聚类算法(furthest-neighbor clustering)，或全链接算法(complete-linkage clustering)当算法使用平均距离度量簇间距离时，称为平均链接算法(average-linkage clustering)单链接算法(使用最小距离)1. 初始时，所有点都是单独的簇(如果有100个数据点，此时就有100个簇)2. 找到距离最近(使用最小距离来度量簇间距离)的两个簇，合并它们3

8、. 重复第2步，直到只剩下一个簇如果改成“最大距离”就是全链接算法；而如果改成“平均距离”就是平均链接算法单链接算法 (使用最小距离)D(5,2)B(2,1)C(2,2)A(0,1)E(6,1)ABCDEd(A, B)d(A, C)d(A, D)d(A, E)d(B, C)d(B, D)d(B, E)d(C, D)d(C, E)d(D, E)各簇之间的欧氏距离表C1单链接算法 (使用最小距离)D(5,2)B(2,1)C(2,2)A(0,1)E(6,1)ABCDEd(A, C1)d(A, D)d(A, E)d(C1, D)d(C1, E)d(D, E)各簇之间的欧氏距离表C1C2单链接算法 (使

9、用最小距离)D(5,2)B(2,1)C(2,2)A(0,1)E(6,1)ABCDEd(A, C1)d(A, C2)d(C1, C2)各簇之间的欧氏距离表C1C2C3单链接算法 (使用最小距离)D(5,2)B(2,1)C(2,2)A(0,1)E(6,1)ABCDEd(C3, C2)各簇之间的欧氏距离表C1C2C3全链接算法 (使用最大距离)D(5,2)B(2,1)C(2,2)A(0,1)E(6,1)ABCDEd(A, B)d(A, C)d(A, D)d(A, E)d(B, C)d(B, D)d(B, E)d(C, D)d(C, E)d(D, E)各簇之间的欧氏距离表C1全链接算法 (使用最大距离

10、)D(5,2)B(2,1)C(2,2)A(0,1)E(6,1)ABCDEd(A, C1)d(A, D)d(A, E)d(C1, D)d(C1, E)d(D, E)各簇之间的欧氏距离表C1C2全链接算法 (使用最大距离)D(5,2)B(2,1)C(2,2)A(0,1)E(6,1)ABCDEd(A, C1)d(A, C2)d(C1, C2)各簇之间的欧氏距离表C1C2C3全链接算法 (使用最大距离)D(5,2)B(2,1)C(2,2)A(0,1)E(6,1)ABCDEd(C3, C2)各簇之间的欧氏距离表C1C2C3这个例子中单链接和全链接算法得到的聚类结果是一样的，但计算过程不同，如果换成其它数

11、据集可能就会得到不同的结果基于链接的层次聚类算法评价最小和最大度量代表了簇间距离度量的两个极端。它们趋向对离群点或噪声数据过分敏感例如单链接凝聚型算法中，因使用最小距离来度量簇间距离，所以这两个簇可能会因为第1个簇的离群点而导致两个簇被合并使用均值距离和平均距离是对最小和最大距离之间的一种折中方法，而且可以克服离群点敏感性问题基于链接的层次聚类算法评价一旦一组对象合并，下一步的处理将针对新生成的簇进行，已做的处理不能撤销，簇之间也不能交换对象。如果在某一步没有选择好，就可能导致低质量的聚类结果分裂型层次聚类算法DIANA（Divisive ANAlysis)算法是典型的分裂聚类方法在聚类中，以

12、用户定义的希望得到的簇数目作为结束条件簇的直径：簇中任意两点的距离中的最大值平均相异度：一个点的其它数据点的距离的平均值簇直径ABCD A的平均相异度= d(A, B) + d(A, C) + d(A, D) / 3DIANA输入：n个对象，终止条件簇的数目k。输出：k个簇，达到终止条件规定簇数目。(1) 将所有对象整个当成一个初始簇；(2) 找出平均相异度最大的点p，将其放入splinter group，剩余放入old party；(3) 为old party中的每个点计算: (4) 找到Dh最大的点h，如果Dh是正数，说明h点离splinter group更近， 将h放入splinter

13、group(5) 重复(2)-(4)步直到所有的Dh都是负数， 此时old party和splinter group形成了两个簇(6) 找到直径最大的簇，重复(1)-(4)以将其分裂。(7) 直到簇的数目达到指定的k时，算法中止即找出“最离群”的点放到splinter group中，splinter group中的点将会独立出来形成一个新簇即检查尚未分裂出去的点，看是离splinter group更近还是离原簇更近，如果离splinter group更近，则说明它也要被分裂出去其它高级算法BIRCH: Balanced Iterative Reducing and Clustering usi

14、ng Hierarchies，利用层次方法的平衡迭代归约和聚类 (课后扩展了解)主要内容聚类算法分类层次聚类算法基于密度的聚类算法基于密度的聚类(Density-based clustering)假设有一个盛满清水的浅碟，在其中滴入几滴墨水，你立即就能看到哪些地方有墨水，因为密度不同，墨水和清水对光线的反射是不一样的有很多聚类算法都是基于简单的日常经验的，尤其是在实际生活中，我们根据密度的差异识别物体的边界，从而实现视觉上的模式识别，这就是基于密度的算法的基本思路基于密度的聚类算法将簇看作是数据空间中被低密度区域(代表噪声)分割开的稠密对象区域DBSCANDBSCAN（Density-Base

15、d Spatial Clustering of Applications with Noise），针对有噪声应用的基于密度的空间聚类它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据中发现任意形状的簇。DBSCAN-邻域：给定数据点在半径内的区域核心点：如果一个点的-邻域至少包含至少MinPts个点，则称该点为核心点，MinPts = Min Points，为一个人为指定的参数pq给定MinPts = 5，则p为核心点，q不是核心点若给定MinPts = 3，则p, q皆是核心点DBSCAN直接密度可达：q是一个核心点，如果p是在q的-邻域内，我

16、们说p从q出发是直接密度可达的密度可达：如果存在一个对象链p1，p2，pn，p1=q，pn=p，对piD（1=i=n），pi+1是从pi关于和MitPts直接密度可达的，则对象p是从对象q关于和MinPts密度可达的设MinPts=3，则p, q是核心对象，从p出发直接密度可达q，从q出发直接密度可达m，因此从p出发密度可达mpqmDBSCAN密度相连： 如果集合D中存在一个点o，从o关于和MinPts密度可达p和q，那么p和q是关于和MinPts密度相连的设MinPts=3，从A出发密度可达B和C，因此B和C是密度相连的DBSCAN一个基于密度的簇是基于密度可达性的最大的密度相连点的集合。不

17、包含在任何簇中的点被认为是“噪声”边界点不是核心点，但落在某个核心点的邻域内噪声就是那些既不是边界点也不是核心点的对象DBSCAN设MinPts=3图中哪些点是核心点？P和M是什么关系？P和Q是什么关系？从Q出发密度可达P吗？R和S的关系是？解答：M、P、S、O、R的邻域内均包含3个以上的点，因此它们都是核心点；从P出发直接密度可达M；从P出发密度可达Q；Q不是核心点，因此从Q出发密度不可达P；从O出发密度可达S和R，因此S和R是密度相连的；DBSCANDBSCAN 算法根据以上的定义在数据库中发现簇和噪声。簇可等价于集合D中，这个簇核心点密度可达的所有对象的集合DBSCAN通过检查数据集中每

18、个点的邻域来寻找聚类。如果一个点p的邻域包含多于MinPts个点，则创建一个p作为核心点的新簇C。然后，从C中寻找未被处理点q的邻域，如果q的邻域包含多MinPts个点，则还未包含在C中的q的邻域内的点被加入到簇中，并且这些点的邻域将在下一步中进行检测。这个过程反复执行，当没有新的点可以被添加到任何簇时，该过程结束DBSCAN算法描述输入：包含n个对象的数据集，半径，最少数目MinPts输出：所有生成的簇，达到密度要求1. 重复 2. 从数据集中抽取一个未处理过的点 3. 若抽出的点是核心点，则找出所有该点密度可达的点，形成一个簇 4. 若抽出的点是边缘点(非核心点)，跳出本次循环，寻找下一点

19、5. 直到所有点都被处理DBSCAN算法举例指定=1，MinPts=41. 选择数据集中的第一个点， 假设是点(2, 1)由于在以它为圆心的，以1为半径的圆内包含2个点(小于4)，因此它不是核心点，选择下一个点DBSCAN算法举例指定=1，MinPts=42. 选择下一个点，假设是点(5, 1)由于在以它为圆心的，以1为半径的圆内包含2个点(小于4)，因此它不是核心点，跳过DBSCAN算法举例指定=1，MinPts=43. 选择下一个点，假设是点(1, 2)由于在以它为圆心的，以1为半径的圆内包含3个点(小于4)，因此它不是核心点，跳过DBSCAN算法举例指定=1，MinPts=44. 选择下

20、一个点，假设是点(2, 2)由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，将其邻域内的点(直接密度可达)都聚成一个新簇。然后再寻找从它出发间接密度可达的点(通过检查它邻域中的其它点)，也将它们加到簇中。DBSCAN算法举例指定=1，MinPts=45. 选择下一个点，假设是点(3, 2)， 因为它已被分配到簇中，忽略6. 选择下一个点，假设是点(4, 2)由于在以它为圆心的，以1为半径的圆内包含3个点(小于4)，因此它不是核心点，选择下一个点DBSCAN算法举例指定=1，MinPts=47. 选择下一个点，假设是点(5, 2)由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发直接密度可达的点，聚出新簇。再检查其邻域内的其它点，但因为它们都不是核心点，因此没有间接可达的点了。DBSCAN算法举例指定=1，MinPts=48. 继续选择其它未选择的点但因为此时它们都已经被分配到簇中去了，所以都会忽略掉。所有点检查完后，算法结束。得到两个簇。DBSCAN评价能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，有效地处理数据集中的噪声数据，数据输入顺序不敏感k-MeansDBSCANDBSCAN评价确定参数，MinPts困难，若选取不当，将造成聚类质量下降真实的高维数据集常常具有非常倾斜的分布，全局密度参数不能刻画其内