1、聚类分析：附加的问题与算法聚类分析：附加的问题与算法第第9章章聚类分析：附加的问题与算法聚类分析：附加的问题与算法 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 2 目录目录l数据、簇和聚类算法的特征数据、簇和聚类算法的特征l基于原型的聚类基于原型的聚类l基于密度的聚类基于密度的聚类l基于图的聚类（基于图的聚类（重点重点）l可伸缩的聚类可伸缩的聚类l生物学应用（生物学应用（重点重点）李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 3 比较比较k均值和均值和DBSCANlK均值聚类所有对象，而均值聚类所有对象，而DBSCAN丢弃噪声丢弃噪声对象。对象。l
2、K均值使用簇的基于原型的概念，而均值使用簇的基于原型的概念，而DBSCAN基于密度的概念。基于密度的概念。lDBSCAN可以处理不同大小和形状的簇。可以处理不同大小和形状的簇。K均值不能。均值不能。lDBSCAN不太受噪声的影响不太受噪声的影响lK均值时间复杂度是均值时间复杂度是O（m），而），而DBSCAN的时间复杂度是的时间复杂度是O（m2）。）。K均值可以用于均值可以用于稀疏的高维数据。稀疏的高维数据。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 4 lDBSCAN不对数据的分布做任何假定。不对数据的分布做任何假定。k均均值假定簇来自球形高斯分布。值假定簇来自球形高
3、斯分布。lK均值可以发现不是明显分离的簇，但是均值可以发现不是明显分离的簇，但是DBSCAN会合并有重叠的簇。会合并有重叠的簇。lDBSCAN产生相同的结果，而产生相同的结果，而k均值通常使均值通常使用随机初始化质心，不会产生相同的结果。用随机初始化质心，不会产生相同的结果。lDBSCAN自动地确定簇个数；对于自动地确定簇个数；对于k均值，均值，簇个数需要作为参数指定。簇个数需要作为参数指定。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 5 对聚类分析有很强影响的数据特性对聚类分析有很强影响的数据特性l高维性高维性 维度增加，体积迅速增加。除非点的个维度增加，体积迅速增加
4、。除非点的个数也增加，否则密度将趋向于数也增加，否则密度将趋向于0.处理该问题的一个方法是使用维归约技处理该问题的一个方法是使用维归约技术术l规模规模 如何处理大型数据集如何处理大型数据集l稀疏性稀疏性 稀疏数据通常由非对称的属性组成，其稀疏数据通常由非对称的属性组成，其中零值没有非零值重要。中零值没有非零值重要。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 6 l噪声和离群点噪声和离群点 可能降低聚类算法的性能，特别是基于可能降低聚类算法的性能，特别是基于原型的算法原型的算法l属性和数据集类型属性和数据集类型 不同的近邻性和密度度量适合于不同类不同的近邻性和密度度量适合
5、于不同类型的数据。型的数据。l尺度尺度 不同的属性，如高度和重量，可能用不不同的属性，如高度和重量，可能用不同的尺度度量。同的尺度度量。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 7 簇特性簇特性l数据分布数据分布l不同形状、大小和密度不同形状、大小和密度l无明显分离的簇无明显分离的簇 当簇接触或重叠当簇接触或重叠 模糊聚类可以处理这一问题模糊聚类可以处理这一问题l簇之间的联系簇之间的联系 在大部分聚类技术中，都不考虑簇之间的联系，如簇在大部分聚类技术中，都不考虑簇之间的联系，如簇的相对位置的相对位置 自组织映射（自组织映射（SOM）。）。l子空间簇子空间簇 簇可能只在
6、维（属性）的一个子集中存在。簇可能只在维（属性）的一个子集中存在。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 8 聚类算法的一般特征聚类算法的一般特征l次序依赖性次序依赖性 簇的质量和个数可能因数据处理的次序不同而显著地簇的质量和个数可能因数据处理的次序不同而显著地变化。如变化。如SOMl非确定性非确定性 每次运行产生不同的结果。每次运行产生不同的结果。l变换聚类问题到其他领域变换聚类问题到其他领域 将聚类问题映射到一个不同的领域。如，基于图的聚将聚类问题映射到一个不同的领域。如，基于图的聚类类l可伸缩性可伸缩性 数据集大时，聚类算法能应对。数据集大时，聚类算法能应对。
7、不能总是假定数据放在内存。这样的算法对于大型数不能总是假定数据放在内存。这样的算法对于大型数据集是不可行的。据集是不可行的。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 9 l参数选择参数选择 选择合适的参数值可能是困难的；因此，通常的态度选择合适的参数值可能是困难的；因此，通常的态度是是“参数越少越好参数越少越好”。l将聚类作为最优化问题处理将聚类作为最优化问题处理 聚类常常被看作优化问题。将点划分成簇，根据用户聚类常常被看作优化问题。将点划分成簇，根据用户指定的目标函数度量，最大化结果簇集合的优良度。指定的目标函数度量，最大化结果簇集合的优良度。如如k均值试图发现簇的
8、集合，使得每个点到最近的簇质均值试图发现簇的集合，使得每个点到最近的簇质心距离的平方和最小。心距离的平方和最小。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 10 目录目录l数据、簇和聚类算法的特征数据、簇和聚类算法的特征l基于原型的聚类基于原型的聚类l基于密度的聚类基于密度的聚类l基于图的聚类（基于图的聚类（重点重点）l可伸缩的聚类可伸缩的聚类l生物学应用（生物学应用（重点重点）李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 11 基于原型的聚类基于原型的聚类l模糊聚类（难点）模糊聚类（难点）l使用混合模型的聚类使用混合模型的聚类l自组织映射自组织映
9、射 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 12 模糊簇模糊簇l1965年，年，Lotfi Zadeh引进模糊集合论（引进模糊集合论（fuzzy set theory）和模糊逻辑（）和模糊逻辑（fuzzy logic）。）。l模糊集合论允许对象以模糊集合论允许对象以0和和1之间的某个隶属度属之间的某个隶属度属于一个集合，而模糊逻辑允许一个陈述以于一个集合，而模糊逻辑允许一个陈述以0和和1之之间的确定度为真。间的确定度为真。l假定我们有一个数据点的集合假定我们有一个数据点的集合X=x1,x2,xm，其中每个点其中每个点xi是一个是一个n维点，即维点，即xi=（xi1,
10、xi2,xin)。模糊簇集。模糊簇集C1,C2,Ck是是X的所有的所有可能模糊子集的一个子集。可能模糊子集的一个子集。l每个点每个点xi和每个簇和每个簇Cj，隶属权值（度），隶属权值（度）wij已经赋已经赋予予0和和1之间的值。之间的值。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 13 模糊伪划分（模糊伪划分（fuzzy psuedo-partition）l给定点给定点xi的所有权值之和为的所有权值之和为1：l每个簇每个簇Cj以非零权值至少包含一个点，但不以非零权值至少包含一个点，但不以权值以权值1包含所有的点包含所有的点kjwij11mwijmi10 李春权 数据挖掘
11、 哈尔滨医科大学 生物信息科学与技术学院 2011 14 模糊模糊c均值算法：均值算法：FCMl算法算法9.1 基本模糊基本模糊c均值算法均值算法 选择一个初始模糊伪划分，即对所有的选择一个初始模糊伪划分，即对所有的wij赋值赋值 Repeat 使用模糊伪划分，计算每个簇的质心使用模糊伪划分，计算每个簇的质心 重新计算模糊伪划分，即重新计算模糊伪划分，即wij Until 质心不发生变化质心不发生变化 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 15 l计算质心计算质心l更新模糊伪划分更新模糊伪划分2121mijiijmijiw xcw2211/(,)1/(,)ijij
12、kiqqdist x cwdist x c 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 16 例子：三个圆形簇上的模糊例子：三个圆形簇上的模糊c均值均值 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 17 优点与局限性优点与局限性lFCM产生指示任意点属于任意簇程度产生指示任意点属于任意簇程度的聚类。的聚类。K均值可以看作FCM的特例。l它比它比K均值算法计算复杂性高。均值算法计算复杂性高。l除此之外，它与除此之外，它与k均值算法具有相同的均值算法具有相同的优点和缺点。优点和缺点。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011
13、18 基于原型的聚类基于原型的聚类l模糊聚类（模糊聚类（难点难点）l使用混合模型的聚类使用混合模型的聚类l自组织映射自组织映射 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 19 混合模型的聚类算法混合模型的聚类算法l估计数据分布：估计数据分布：确定分布：一般假设数据取自高斯确定分布：一般假设数据取自高斯混合分布。然后，对分布的参数进混合分布。然后，对分布的参数进行估计：利用行估计：利用EM算法进行最大似然算法进行最大似然估计估计利用直方图估计分布利用直方图估计分布l对分布进行划分、分离。每个分布对应对分布进行划分、分离。每个分布对应于一个簇。于一个簇。李春权 数据挖掘
14、哈尔滨医科大学 生物信息科学与技术学院 2011 20 例子例子簇簇1簇簇2 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 21 优点和缺点优点和缺点l混合模型比混合模型比k均值或模糊均值或模糊c均值更一般均值更一般，因为它可以使用各种类型的分布。，因为它可以使用各种类型的分布。l利用简单的估计分布的方法（如直方图利用简单的估计分布的方法（如直方图）可能会错误估计数据的原始分布，导）可能会错误估计数据的原始分布，导致结果不好。致结果不好。l利用复杂的方法（如利用复杂的方法（如EM算法），计算算法），计算复杂性会大大增加。复杂性会大大增加。李春权 数据挖掘 哈尔滨医科大学
15、生物信息科学与技术学院 2011 22 基于原型的聚类基于原型的聚类l模糊聚类（模糊聚类（难点难点）l使用混合模型的聚类使用混合模型的聚类l自组织映射自组织映射 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 23 自组织映射自组织映射lKohonen自组织特征映射（自组织特征映射（SOFM或或SOM）是一）是一种基于神经网络观点的聚类和数据可视化技术。种基于神经网络观点的聚类和数据可视化技术。l尽管尽管SOM源于神经网络，但是它可以表示成一种源于神经网络，但是它可以表示成一种基于原型聚类的变形。基于原型聚类的变形。l与其他基于质心的聚类技术一样，与其他基于质心的聚类技术一
16、样，SOM的目标是的目标是发现质心的集合，并将数据集中的每个对象指派发现质心的集合，并将数据集中的每个对象指派到提供该对象最佳近似的质心。用神经网络的术到提供该对象最佳近似的质心。用神经网络的术语，每个质心都与一个神经元相关联。语，每个质心都与一个神经元相关联。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 24 SOM算法算法l初始化质心。初始化质心。lRepeatl 选择下一个对象选择下一个对象l 确定到该对象最近的质心确定到该对象最近的质心l 更新该质心和附近的质心，即在一个特定邻域更新该质心和附近的质心，即在一个特定邻域 内的质心内的质心lUntil 质心改变不多或
17、超过某个域值质心改变不多或超过某个域值l指派每个对象到最近的质心，并返回质心和簇指派每个对象到最近的质心，并返回质心和簇 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 25 使用使用SOM胚胎发育过程聚类胚胎发育过程聚类SOM-SVD 聚类聚类 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 26 目录目录l数据、簇和聚类算法的特征数据、簇和聚类算法的特征l基于原型的聚类基于原型的聚类l基于密度的聚类基于密度的聚类l基于图的聚类（基于图的聚类（重点重点）l可伸缩的聚类可伸缩的聚类l生物学应用（生物学应用（重点重点）李春权 数据挖掘 哈尔滨医科大学 生物
18、信息科学与技术学院 2011 27 基于密度的聚类基于密度的聚类l基于网格的聚类（重点）基于网格的聚类（重点）l子空间聚类子空间聚类lDENCLUE 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 28 例子例子 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 29 基于网格的聚类算法（基于网格的聚类算法（重点重点）l定义一个网格单元集定义一个网格单元集l将对象指派到合适的单元，并计算将对象指派到合适的单元，并计算每个单元的密度每个单元的密度l删除密度低于指定的阈值的单元删除密度低于指定的阈值的单元l由邻近的稠密单元形成簇由邻近的稠密单元形成簇 李春权
19、数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 30 定义网格单元和密度（定义网格单元和密度（重点重点）l定义网格单元定义网格单元对于连续属性，定义网格单元相当对于连续属性，定义网格单元相当于连续属性离散化。于连续属性离散化。l网格单元的密度网格单元的密度该区域中的点数除以区域的体积。该区域中的点数除以区域的体积。如果使用具有相同体积的网格单元如果使用具有相同体积的网格单元，使得每个单元的点数直接度量单，使得每个单元的点数直接度量单元的密度。元的密度。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 31 优点与局限性优点与局限性l算法运行速度较快，可达算法运行速
20、度较快，可达o(mlogm)。这使得它成。这使得它成为许多聚类算法的基础，如为许多聚类算法的基础，如STING、GRIDCLUS、waveCluster、Bang-Clustering、CLIQUE和和MAFIA。l网格单元形状选择影响聚类效果。如矩形网格单网格单元形状选择影响聚类效果。如矩形网格单元不能准确地捕获圆形边界区域的密度。元不能准确地捕获圆形边界区域的密度。l不适合高维数据。不适合高维数据。l密度阈值的选择对算法效果影响较大。如图密度阈值的选择对算法效果影响较大。如图9-10和表和表9-2，如果密度阈值为，如果密度阈值为9，则大簇的，则大簇的4个部分将个部分将丢失。丢失。李春权 数
21、据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 32 基于密度的聚类基于密度的聚类l基于网格的聚类（基于网格的聚类（重点重点）l子空间聚类子空间聚类lDENCLUE 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 33 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 34 CLIQUE算法算法l找出每个属性的一维空间的所有稠密区域。找出每个属性的一维空间的所有稠密区域。lK2lRepeatl 由稠密的由稠密的k-1维单元产生候选稠密维单元产生候选稠密k维单元维单元l 删除点数少于域值的单元删除点数少于域值的单元l kk+1lUntil 不存在候
22、选稠密不存在候选稠密k维单元维单元l通过取邻接的、高密度的单元的并发现簇通过取邻接的、高密度的单元的并发现簇 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 35 CLIQUE的优点与局限性的优点与局限性lCLIQUE最大特点是，它提供了一种搜索子空间发最大特点是，它提供了一种搜索子空间发现簇的有效技术。现簇的有效技术。l由于这种方法基于关联分析的先验原理，它的性质由于这种方法基于关联分析的先验原理，它的性质能够被很好地解释。能够被很好地解释。lCLIQUE的局限性与其他基于密度的方法和的局限性与其他基于密度的方法和Apriori算法相同。如，算法相同。如，CLIQUE发现
23、的簇可以共享对象。发现的簇可以共享对象。允许簇重叠可能大幅度增加簇的个数，并使得解释允许簇重叠可能大幅度增加簇的个数，并使得解释更加困难。更加困难。lApriori具有指数级的复杂度。具有指数级的复杂度。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 36 基于密度的聚类基于密度的聚类l基于网格的聚类（基于网格的聚类（重点重点）l子空间聚类子空间聚类lDENCLUE 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 37 基于密度聚类的一种基于核的方案基于密度聚类的一种基于核的方案 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 38
24、DENCLUE(DENsity CLUstEring)算法算法l对数据点占据的空间推导密度函数对数据点占据的空间推导密度函数l识别局部最大点（即密度吸引点）识别局部最大点（即密度吸引点）l通过沿密度增长最大的方向移动，将每个点通过沿密度增长最大的方向移动，将每个点关联到一个密度吸引点关联到一个密度吸引点l与特定的密度吸引点相关联的那些点构成簇与特定的密度吸引点相关联的那些点构成簇l丢弃密度吸引点的密度小于阈值的簇丢弃密度吸引点的密度小于阈值的簇l合并通过密度大于或等于阈值的点路径连接合并通过密度大于或等于阈值的点路径连接的簇的簇 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 201
25、1 39 核密度估计核密度估计l核密度估计用函数描述数据的分布。核密度估计用函数描述数据的分布。每个点对总密度函数的贡献用一个核每个点对总密度函数的贡献用一个核函数表示。总密度函数仅仅是与每个函数表示。总密度函数仅仅是与每个点相关联的核函数之核点相关联的核函数之核l高斯函数常用作核函数：高斯函数常用作核函数：l基于网格的技术来处理该问题基于网格的技术来处理该问题222/),(tan)(yxcediseyk 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 40 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 41 DENCLUE的优点与局限性的优点与局限性
26、lDENCLUE具有坚实的理论基础（核密度函数和核具有坚实的理论基础（核密度函数和核密度估计）。密度估计）。l因此，提供了比其他基于网格的聚类技术和因此，提供了比其他基于网格的聚类技术和DBSCAN更加灵活、更加精确的计算密度的方法更加灵活、更加精确的计算密度的方法。（。（DBSCAN是是DENCLUE的特例）的特例）l基于核函数的方法是计算昂贵的，但基于核函数的方法是计算昂贵的，但DENCLUE使使用基于网格的技术来处理该问题。用基于网格的技术来处理该问题。l尽管如此，尽管如此，DENCLUE比其他基于密度的聚类计算比其他基于密度的聚类计算开销更大。开销更大。lDENCLUE具有其他基于密度
27、的方法的优缺点。具有其他基于密度的方法的优缺点。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 42 目录目录l数据、簇和聚类算法的特征数据、簇和聚类算法的特征l基于原型的聚类基于原型的聚类l基于密度的聚类基于密度的聚类l基于图的聚类（重点）基于图的聚类（重点）l可伸缩的聚类可伸缩的聚类l生物学应用（生物学应用（重点重点）李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 43 基于图的聚类基于图的聚类l稀疏化稀疏化l最小生成树聚类最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法聚类算法l基于基于SNN密度的聚类密度的
28、聚类 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 44 稀疏化稀疏化lm个数据点的个数据点的mm邻近度矩阵可以用一个稠密图邻近度矩阵可以用一个稠密图表示，每个节点与其他所有点相连，权值反映邻表示，每个节点与其他所有点相连，权值反映邻近性。近性。l尽管每个对象与其他每个对象都有某种程度的近尽管每个对象与其他每个对象都有某种程度的近邻性，但是对于大部分数据集，对象只与少量对邻性，但是对于大部分数据集，对象只与少量对象高度相似，而与大部分其他对象的相似性很弱象高度相似，而与大部分其他对象的相似性很弱。这一性质用来稀疏化邻近度图。这一性质用来稀疏化邻近度图。l稀疏化可以这样进行
29、：断开相似度低于指定阈值稀疏化可以这样进行：断开相似度低于指定阈值的边、或仅保留连接到点的的边、或仅保留连接到点的k个近邻的边。个近邻的边。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 45 l稀疏化是聚类算法的初始化步骤。稀疏化是聚类算法的初始化步骤。lm个数据点的个数据点的mm邻近度矩阵可以用一个稠密图邻近度矩阵可以用一个稠密图表示，每个节点与其他所有点相连，权值反映邻表示，每个节点与其他所有点相连，权值反映邻近性。近性。l稀疏化可以这样进行：断开相似度低于指定阈值稀疏化可以这样进行：断开相似度低于指定阈值的边、或仅保留连接到点的的边、或仅保留连接到点的k个近邻的边。
30、个近邻的边。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 46 稀疏化的好处稀疏化的好处l压缩了数据量压缩了数据量l可以更好的聚类可以更好的聚类降低了噪声和离群点的影响，增强降低了噪声和离群点的影响，增强了簇之间的差别。了簇之间的差别。l可以使用图划分算法可以使用图划分算法 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 47 基于图的聚类基于图的聚类l稀疏化稀疏化l最小生成树聚类最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法聚类算法l基于基于SNN密度的聚类密度的聚类 李春权 数据挖掘 哈尔滨医科大学 生物信
31、息科学与技术学院 2011 48 最小生成树聚类（最小生成树聚类（minimum spanning tree，MST）l计算相异度图的最小生成树计算相异度图的最小生成树lRepeatl 断开对应于最大相异度的边断开对应于最大相异度的边，创建一个新的簇，创建一个新的簇lUntil 只剩下单个簇只剩下单个簇 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 49 最小生成树聚类最小生成树聚类它是一种基于分裂的层次聚类算法它是一种基于分裂的层次聚类算法它可以看作用稀疏化找出簇的方法它可以看作用稀疏化找出簇的方法 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 5
32、0 基于图的聚类基于图的聚类l稀疏化稀疏化l最小生成树聚类最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法聚类算法l基于基于SNN密度的聚类密度的聚类 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 51 OPOSSUM：使用：使用METIS的稀疏相似度最优划分的稀疏相似度最优划分lOPOSSUM（Optimal Partitioning of Sparse Similarities Using METIS）是一种专门为诸如文）是一种专门为诸如文档或购物篮数据等稀疏、高维数据设计的聚类技档或购物篮数据等稀疏、高维数据设计的聚类技术。术
33、。lOPOSSUM聚类算法聚类算法l1：计算稀疏化的相似度图：计算稀疏化的相似度图l2：使用：使用METIS，将相似度图划分成，将相似度图划分成k个不同的分个不同的分支（簇）支（簇）李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 52 lMETIS图划分程序将稀疏图划分为图划分程序将稀疏图划分为k个不同个不同的分支，其中的分支，其中k是用户指定的参数，旨在是用户指定的参数，旨在l（1）最小化分支之间边的权值）最小化分支之间边的权值l（2）实现平衡约束。）实现平衡约束。OPOSSUM使用如下使用如下两种约束中的一种：（两种约束中的一种：（1）每个簇中的对象）每个簇中的对象个数
34、必须粗略相等，或（个数必须粗略相等，或（2）属性值的和必）属性值的和必须粗略相等。须粗略相等。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 53 优点与缺点优点与缺点lOPOSSUM简单、速度快。简单、速度快。l它将数据划分大小粗略相等的簇。根据聚类它将数据划分大小粗略相等的簇。根据聚类的目标这可能看作优点或缺点。的目标这可能看作优点或缺点。l它类似于它类似于Chameleon聚类过程的初始化步聚类过程的初始化步骤。骤。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 54 基于图的聚类基于图的聚类l稀疏化稀疏化l最小生成树聚类最小生成树聚类lOPOSS
35、UMlChameleonlJarvis-Patrick聚类算法聚类算法l基于基于SNN密度的聚类密度的聚类 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 55 聚类难题聚类难题Closeness schemes will merge(a)and(b)(a)(b)(c)(d)Average connectivity schemes will merge(c)and(d)李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 56 Chameleon算法算法l构造构造k-最近邻图最近邻图l使用多层图划分算法划分图使用多层图划分算法划分图lRepeatl 合并相对互
36、连性和相对接近性，最好合并相对互连性和相对接近性，最好 地保持自相似性的簇地保持自相似性的簇lUntil 不再有可以合并的簇不再有可以合并的簇 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 57 确定合并哪些簇确定合并哪些簇l相对接近度（相对接近度（relative closeness，RC）：）：lmi和和mj分别是簇分别是簇ci和和cj的大小。的大小。SEC(ci,cj)是是连接簇连接簇ci和和cj的边的平均权值；的边的平均权值；SEC(ci)是二是二分簇分簇ci的边的平均权值；的边的平均权值；EC表示割边；表示割边；l簇中的点之间的接近程度几乎与原来的每个簇中的点之
37、间的接近程度几乎与原来的每个簇一样。簇一样。)()(),(),(jECjiiiECjiijiECjiCSmmmCSmmmCCSCCRC 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 58 l相对互连度（相对互连度（relative interconnectivity,RI）：）：l其中，其中，EC(Ci,Cj)是连接簇是连接簇Ci和和Cj的边之和；的边之和；EC(Ci)是二分簇是二分簇Ci的割边的最小和；的割边的最小和；EC(Cj)是二分簇是二分簇Cj的割边的最小和。的割边的最小和。l簇中的点之间的连接几乎与原来的每个簇一簇中的点之间的连接几乎与原来的每个簇一样强，两个簇
38、合并。样强，两个簇合并。)()(21),(),(jijijiCECCECCCECCCRI 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 59 聚类效果聚类效果 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 60 聚类效果聚类效果 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 61 优点与局限性优点与局限性lChameleon是一种凝聚聚类技术，它将数据的初是一种凝聚聚类技术，它将数据的初始划分与一种新颖的层次聚类方案相结合。始划分与一种新颖的层次聚类方案相结合。l使用接近性和互连性概念以及簇的局部建模。关使用接近性和互连性概念以
39、及簇的局部建模。关键思想是：仅当合并后的结果簇类似于原来的两键思想是：仅当合并后的结果簇类似于原来的两个簇时，这两个簇才合并。个簇时，这两个簇才合并。lChameleon能够有效地聚类空间数据，即便存在能够有效地聚类空间数据，即便存在噪声和离群点，并且簇具有不同的形状、大小和噪声和离群点，并且簇具有不同的形状、大小和密度。密度。l当划分过程未产生子簇时，当划分过程未产生子簇时，chameleon有问题，有问题，对于高维数据，常常出现这种情况。对于高维数据，常常出现这种情况。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 62 基于图的聚类基于图的聚类l稀疏化稀疏化l最小生成
40、树聚类最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法聚类算法l基于基于SNN密度的聚类密度的聚类 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 63 共享最近邻相似性共享最近邻相似性SNN（shared nearest neighbor）lSNN相似度计算：相似度计算：l找出所有点的找出所有点的k-近邻近邻lIf 两个点两个点x和和y不是相互在对方的不是相互在对方的k-最近邻中最近邻中 then similarity(x,y)0lElsel similarity(x,y)共享的近邻个数共享的近邻个数lEnd if 李春权 数据挖掘
41、 哈尔滨医科大学 生物信息科学与技术学院 2011 64 ijij4消除对象碰巧接近和处理变密度！消除对象碰巧接近和处理变密度！李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 65 SSN相似度特点相似度特点l能处理一个对象碰巧与另一对象相对接近，但属能处理一个对象碰巧与另一对象相对接近，但属于不同的类。在这种情况下，对象一般不共享许于不同的类。在这种情况下，对象一般不共享许多近邻，多近邻，SNN相似度低。相似度低。l能处理变密度簇的问题。一对点之间的能处理变密度簇的问题。一对点之间的SNN相似相似度只依赖于两个对象共享的最近邻的个数。度只依赖于两个对象共享的最近邻的个数。
42、李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 66 Jarvis-Patrick（JP）聚类算法）聚类算法l计算计算SNN相似度图相似度图l使用相似度阈值，稀疏化使用相似度阈值，稀疏化SNN相似度相似度图图l找出稀疏化的找出稀疏化的SNN相似度图的连通分相似度图的连通分支支 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 67 优点与局限性优点与局限性l因为因为JP聚类基于聚类基于SNN相似度概念，它擅长相似度概念，它擅长于处理噪声和离群点，并且能够处理不同大于处理噪声和离群点，并且能够处理不同大小、形状和密度的簇。小、形状和密度的簇。l该算法对高维数
43、据效果良好。该算法对高维数据效果良好。lJP聚类脆弱：它把簇定义为聚类脆弱：它把簇定义为SNN相似度图相似度图的连通分支的连通分支,数据对象集分裂成两个簇还是数据对象集分裂成两个簇还是作为一个簇留下，可能依赖于一条链。作为一个簇留下，可能依赖于一条链。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 68 基于图的聚类基于图的聚类l稀疏化稀疏化l最小生成树聚类最小生成树聚类lOPOSSUMlChameleonlJarvis-Patrick聚类算法聚类算法l基于基于SNN密度的聚类密度的聚类 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 69 基于基于SN
44、N密度的聚类密度的聚类算法：算法：l计算计算SNN相似度图相似度图l以用户指定的参数以用户指定的参数Eps和和MinPts，使用使用DBSCAN聚类聚类 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 70 例子：解释该算法处理高维数据能力例子：解释该算法处理高维数据能力26 SLP Clusters via Shared Nearest Neighbor Clustering(100 NN,1982-1994)longitudelatitude-180-150-120-90-60-30 0 30 60 90 120 150 180 90 60 30 0 -30-60-90
45、13 26 24 25 22 14 16 20 17 18 19 15 23 1 9 6 4 7 10 12 11 3 5 2 8 21 SNN Clusters of SLP.SNN Density of SLP Time Series Datalongitudelatitude-180-150-120-90-60-30 0 30 60 90 120 150 180 90 60 30 0 -30-60-90SNN Density of Points on the Globe.l41年期间，在年期间，在2.5度的经纬度网格的每个点上的月度的经纬度网格的每个点上的月平均海平面气压（平均海平面气压
46、（SLP）李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 71 优点与局限性优点与局限性l基于基于SNN密度的聚类的优点与局限性类似于密度的聚类的优点与局限性类似于JP聚类。聚类。lSNN聚类算法比聚类算法比JP聚类或聚类或DBSCAN更加灵更加灵活。它可以用于高维数据和簇具有不同密度活。它可以用于高维数据和簇具有不同密度的情况。的情况。l不象不象JP聚类简单地使用域值，然后取连通聚类简单地使用域值，然后取连通分支作为簇，基于分支作为簇，基于SNN密度的聚类使用基于密度的聚类使用基于SNN密度和核心点概念的方法。密度和核心点概念的方法。李春权 数据挖掘 哈尔滨医科大学 生物
47、信息科学与技术学院 2011 72 习题习题l稀疏化的好处稀疏化的好处lOPOSSUM聚类算法中重要一个步骤是稀疏化，聚类算法中重要一个步骤是稀疏化，叙述该稀疏化方法叙述该稀疏化方法lChameleon算法使用接近性和互连性概念以及簇算法使用接近性和互连性概念以及簇的局部建模。关键思想是：使用的局部建模。关键思想是：使用_和和_概念，仅当合并后的结果簇概念，仅当合并后的结果簇_原来的两个簇原来的两个簇时，这两个簇才合并。时，这两个簇才合并。lJarvis-Patrick（JP）聚类算法首先计算）聚类算法首先计算_图，然后使用相似度阈值，稀疏化该图找出稀疏图，然后使用相似度阈值，稀疏化该图找出稀
48、疏化图的连通分支。化图的连通分支。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 73 l基于基于SNN密度的聚类不象密度的聚类不象JP聚类简单地使聚类简单地使用域值，然后取用域值，然后取_作为簇，基于作为簇，基于SNN密度的聚类使用基于密度的聚类使用基于SNN密度和密度和_方方法。法。lSNN密度的优势。密度的优势。李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 74 目录目录l数据、簇和聚类算法的特征数据、簇和聚类算法的特征l基于原型的聚类基于原型的聚类l基于密度的聚类基于密度的聚类l基于图的聚类（基于图的聚类（重点重点）l可伸缩的聚类可伸缩的聚类l
49、生物学应用（生物学应用（重点重点）李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 75 CUREl如果运行时间长得不可接受，或者需要的存如果运行时间长得不可接受，或者需要的存储量太大，即使最好的聚类算法也没有多大储量太大，即使最好的聚类算法也没有多大价值。价值。l可伸缩性可以通过如下技术实现：可伸缩性可以通过如下技术实现：多维或空间存取方法多维或空间存取方法 抽样抽样 划分数据对象划分数据对象 汇总汇总 并行与分布计算并行与分布计算 李春权 数据挖掘 哈尔滨医科大学 生物信息科学与技术学院 2011 76 CURE算法算法l由数据集抽取一个随机样本集。由数据集抽取一个随机样
50、本集。l将样本集划分成将样本集划分成p个大小相同的划分。个大小相同的划分。l使用层次聚类算法，将每个划分中的点聚类成使用层次聚类算法，将每个划分中的点聚类成m/pq个簇，得到总共个簇，得到总共m/q个簇。（注：簇增长缓个簇。（注：簇增长缓慢，删除离群点）慢，删除离群点）l使用层次聚类算法对上一步发现的使用层次聚类算法对上一步发现的m/q个簇进行聚个簇进行聚类，直到只剩下类，直到只剩下k个簇。（注：删除离群点）个簇。（注：删除离群点）l将所有剩余的数据点指派到最近的簇。将所有剩余的数据点指派到最近的簇。K是期望的簇个数，是期望的簇个数，m是点的个数，是点的个数，p是划分的个数是划分的个数，而，而
