第10卷第5期 智能系统学报 Vol.10 No.5 2015年10月 CAAI Transactions on Intelligent Systems 0ct.2015 D0I:10.11992/is.201410028 网s络出版地址：htp://ww.cmki.net/kcms/detail/23.1538.tp.20150930.1556.016.html 基于密度的统计合并聚类算法 刘贝贝，马儒宁1，丁军娣2 (1.南京航空航天大学理学院，江苏南京211100：2.南京理工大学计算机科学与技术学院，江苏南京210094) 摘要：针对现有聚类算法处理噪声能力差和速度较慢的问题，提出了一种基于密度的统计合并聚类算法(DSMC)。 该算法将数据点的每一个特征看作一组独立随机变量，根据独立有限差分不等式得出统计合并判定准则：同时，结 合数据点的密度信息，把密度从大到小的排序作为凝聚过程中的合并顺序，实现了各类数据点的统计合并。人工数 据集和真实数据集的实验结果表明，DSMC算法不仅可以处理凸状数据集，对于非凸、重叠、加入噪声的数据集也有 良好的聚类效果，充分表明了该算法的适用性和有效性。 关键词：数据点：密度：随机变量：合并：聚类：噪声 中图分类号：0235：TP311文献标志码：A文章编号：1673-4785(2015)05-0712-10 中文引用格式：刘贝贝，马儒宁，丁军娣.基于密度的统计合并聚类算法[J].智能系统学报，2015,10(5)：712-721. 英文写引用格式：LIU Beibei,MA Runing,DINGJundi.Density-based statistical merging clustering algorithm[J].CAAI Transac- tions on Intelligent Systems,2015,10(5):712-721. Density-based statistical merging clustering algorithm LIU Beibei',MA Runing',DING Jundi2 (1.College of Science,Nanjing University of Aeronautics and Astronautics,Nanjing 211100,China:2.School of Computer Science and Technology,Nanjing University of Science and Technology,Nanjing 210094,China) Abstract:The ability of existing clustering algorithms to deal with noise is poor,and the speed is slow,instead this paper proposes a density-based statistical merging clustering algorithm (DSMC).The new algorithm takes each group of data points as a set of independent random variables,and gathers statistical criteria from the independent bounded difference inequality.Meanwhile,combined with the density information of the data points,the DSMC al- gorithm takes the descending order of the density as the merging order in the process of condensation,and thereby achieves statistical merging of different types of data points.The experimental results with both artificial datasets and real datasets show that the DSMC algorithm can not only deal with convex data set,and also has good clustering effects on nonconvex shaped,overlapped and noisy,data sets.This proves that the algorithm has good applicability and validity. Keywords:data points;density;random variable;merging;clustering algorithm;noise 聚类2]是数据挖掘领域中十分重要的数据分算法，它的主要特点是在对数据集进行分类之前，需 析技术。具体来说，聚类就是将给定的数据集划分 要事先确定聚类个数，然后将数据集划分到确定好 成互不相交的非空子集的过程。由于初始条件和聚的各类别中。根据划分过程中数据点类别归属的明 类准则的不唯一性，使得各种各样的聚类算法应运确性，又可将分割聚类分为硬聚类和模糊聚类4]。 而生。根据算法形成方式的不同，可以将其分为2 硬聚类中数据点的类别归属是明确的。每个数 大类：基于划分的聚类算法和基于层次的聚类算 据点对各类别的隶属度取0或1，即一个数据点必 法[)。基于划分的聚类算法也可以称为分割聚类 须属于某一类别且只能属于该类别。硬聚类的数学 定义描述如下：设给定的数据集为X={x1,x2,…, 收稿日期：201410-21.网络出版日期：2015-09-30. xn}∈Rx,x,(i=1,2,…,n)表示第i个数据点。预 基金项目：国家自然科学基金资助项目(61103058). 通信作者：丁军娣.E-mail:dingjundi2010@njust..cdu.cn. 先确定将X划分为k个子集C={C,C2,…,C}
第 １０ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．５ ２０１５ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１５ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１４１００２８ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０９３０．１５５６．０１６．ｈｔｍｌ 基于密度的统计合并聚类算法 刘贝贝１ ，马儒宁１ ，丁军娣２ （１． 南京航空航天大学 理学院，江苏 南京 ２１１１００； ２． 南京理工大学 计算机科学与技术学院，江苏 南京 ２１００９４） 摘 要：针对现有聚类算法处理噪声能力差和速度较慢的问题，提出了一种基于密度的统计合并聚类算法（ＤＳＭＣ）。 该算法将数据点的每一个特征看作一组独立随机变量，根据独立有限差分不等式得出统计合并判定准则；同时，结 合数据点的密度信息，把密度从大到小的排序作为凝聚过程中的合并顺序，实现了各类数据点的统计合并。 人工数 据集和真实数据集的实验结果表明，ＤＳＭＣ 算法不仅可以处理凸状数据集，对于非凸、重叠、加入噪声的数据集也有 良好的聚类效果，充分表明了该算法的适用性和有效性。 关键词：数据点；密度；随机变量；合并；聚类；噪声 中图分类号：Ｏ２３５；ＴＰ３１１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０５⁃０７１２⁃１０ 中文引用格式：刘贝贝，马儒宁，丁军娣． 基于密度的统计合并聚类算法［Ｊ］． 智能系统学报， ２０１５， １０（５）： ７１２⁃７２１． 英文引用格式：ＬＩＵ Ｂｅｉｂｅｉ， ＭＡ Ｒｕｎｉｎｇ， ＤＩＮＧ Ｊｕｎｄｉ． Ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｓｔａｔｉｓｔｉｃａｌ ｍｅｒｇｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（５）： ７１２⁃７２１． Ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｓｔａｔｉｓｔｉｃａｌ ｍｅｒｇｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ＬＩＵ Ｂｅｉｂｅｉ １ ， ＭＡ Ｒｕｎｉｎｇ １ ， ＤＩＮＧ Ｊｕｎｄｉ ２ （１． Ｃｏｌｌｅｇｅ ｏｆ Ｓｃｉｅｎｃｅ， Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ａｅｒｏｎａｕｔｉｃｓ ａｎｄ Ａｓｔｒｏｎａｕｔｉｃｓ， Ｎａｎｊｉｎｇ ２１１１００， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ ２１００９４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ａｂｉｌｉｔｙ ｏｆ ｅｘｉｓｔｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｔｏ ｄｅａｌ ｗｉｔｈ ｎｏｉｓｅ ｉｓ ｐｏｏｒ， ａｎｄ ｔｈｅ ｓｐｅｅｄ ｉｓ ｓｌｏｗ， ｉｎｓｔｅａｄ ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｓｔａｔｉｓｔｉｃａｌ ｍｅｒｇｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ （ＤＳＭＣ）． Ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｔａｋｅｓ ｅａｃｈ ｇｒｏｕｐ ｏｆ ｄａｔａ ｐｏｉｎｔｓ ａｓ ａ ｓｅｔ ｏｆ ｉｎｄｅｐｅｎｄｅｎｔ ｒａｎｄｏｍ ｖａｒｉａｂｌｅｓ， ａｎｄ ｇａｔｈｅｒｓ ｓｔａｔｉｓｔｉｃａｌ ｃｒｉｔｅｒｉａ ｆｒｏｍ ｔｈｅ ｉｎｄｅｐｅｎｄｅｎｔ ｂｏｕｎｄｅｄ ｄｉｆｆｅｒｅｎｃｅ ｉｎｅｑｕａｌｉｔｙ． Ｍｅａｎｗｈｉｌｅ， ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ｄｅｎｓｉｔｙ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｔｈｅ ｄａｔａ ｐｏｉｎｔｓ， ｔｈｅ ＤＳＭＣ ａｌ⁃ ｇｏｒｉｔｈｍ ｔａｋｅｓ ｔｈｅ ｄｅｓｃｅｎｄｉｎｇ ｏｒｄｅｒ ｏｆ ｔｈｅ ｄｅｎｓｉｔｙ ａｓ ｔｈｅ ｍｅｒｇｉｎｇ ｏｒｄｅｒ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｃｏｎｄｅｎｓａｔｉｏｎ， ａｎｄ ｔｈｅｒｅｂｙ ａｃｈｉｅｖｅｓ ｓｔａｔｉｓｔｉｃａｌ ｍｅｒｇｉｎｇ ｏｆ ｄｉｆｆｅｒｅｎｔ ｔｙｐｅｓ ｏｆ ｄａｔａ ｐｏｉｎｔｓ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｗｉｔｈ ｂｏｔｈ ａｒｔｉｆｉｃｉａｌ ｄａｔａｓｅｔｓ ａｎｄ ｒｅａｌ ｄａｔａｓｅｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ＤＳＭＣ ａｌｇｏｒｉｔｈｍ ｃａｎ ｎｏｔ ｏｎｌｙ ｄｅａｌ ｗｉｔｈ ｃｏｎｖｅｘ ｄａｔａ ｓｅｔ， ａｎｄ ａｌｓｏ ｈａｓ ｇｏｏｄ ｃｌｕｓｔｅｒｉｎｇ ｅｆｆｅｃｔｓ ｏｎ ｎｏｎｃｏｎｖｅｘ ｓｈａｐｅｄ， ｏｖｅｒｌａｐｐｅｄ ａｎｄ ｎｏｉｓｙ， ｄａｔａ ｓｅｔｓ． Ｔｈｉｓ ｐｒｏｖｅｓ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ｇｏｏｄ ａｐｐｌｉｃａｂｉｌｉｔｙ ａｎｄ ｖａｌｉｄｉｔｙ． Ｋｅｙｗｏｒｄｓ：ｄａｔａ ｐｏｉｎｔｓ； ｄｅｎｓｉｔｙ； ｒａｎｄｏｍ ｖａｒｉａｂｌｅ； ｍｅｒｇｉｎｇ； ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ； ｎｏｉｓｅ 收稿日期：２０１４⁃１０⁃２１． 网络出版日期：２０１５⁃０９⁃３０． 基金项目：国家自然科学基金资助项目（６１１０３０５８）． 通信作者：丁军娣． Ｅ⁃ｍａｉｌ： ｄｉｎｇｊｕｎｄｉ２０１０＠ ｎｊｕｓｔ．ｅｄｕ．ｃｎ． 聚类［１⁃２］是数据挖掘领域中十分重要的数据分 析技术。 具体来说，聚类就是将给定的数据集划分 成互不相交的非空子集的过程。 由于初始条件和聚 类准则的不唯一性，使得各种各样的聚类算法应运 而生。 根据算法形成方式的不同，可以将其分为 ２ 大类：基于划分的聚类算法和基于层次的聚类算 法［３］ 。 基于划分的聚类算法也可以称为分割聚类 算法，它的主要特点是在对数据集进行分类之前，需 要事先确定聚类个数，然后将数据集划分到确定好 的各类别中。 根据划分过程中数据点类别归属的明 确性，又可将分割聚类分为硬聚类和模糊聚类［ ４ ］ 。 硬聚类中数据点的类别归属是明确的。 每个数 据点对各类别的隶属度取 ０ 或 １，即一个数据点必 须属于某一类别且只能属于该类别。 硬聚类的数学 定义描述如下：设给定的数据集为 Ｘ ＝ ｛ ｘ１ ，ｘ２ ，…， ｘｎ ｝∈Ｒ ｎ×ｄ ，ｘｉ（ｉ ＝ １，２，…，ｎ）表示第 ｉ 个数据点。 预 先确定将 Ｘ 划分为 ｋ 个子集 Ｃ ＝ ｛Ｃ１ ，Ｃ２ ，…，Ｃｋ ｝
第5期 刘贝贝，等：基于密度的统计合并聚类算法 ·713· (k≤n),则C:满足如下条件：1)C≠⑦，(i=1,2, 凝聚式层次聚类算法[o采用“自底向上”的方 …,k),即每一子集至少含有一个数据点；2)C:∩C= 式进行。一开始将数据集的每个数据点看作一类， ☑，(1≤i≠j≤k),即每个数据点只能属于一个子集： 然后进行一系列的合并操作，直到满足终止条件或 3)UC,=X,即每个数据点必须归属于某一子集。 所有数据点归为一类时停止凝聚。大部分层次聚类 数据点x,(=1,2,…,n)对子集C(i=1,2,…,k)的 算法都是采用凝聚式聚类，代表性的算法有基于代 隶属关系可用隶属函数u:表示，当u:=1时，x:∈ 表点的CURE算法I]、基于稠密点的DBSCAN算 C:,当u=0时，x华C:,其中隶属函数u∈{0,1}且 法I2J、NBC(neighborhood based clustering)算法B] 满足∑4，=1，j,0l, 息及多维特征信息，计算数据点之间的相似性得到 有C:∈C,或C:∩C=对所有i成立，j≠i,m,l= 相似性矩阵，确定每一数据点的k邻域。然后将稠 1,2,…,9。层次聚类算法又分为分裂式和凝聚式 密点与其k邻域中所有点的相似性的最小值作为数 2种。 据点的密度信息，将密度从大到小的排序作为合并 分裂式层次聚类算法采用“自顶向下”的方式 的顺序。 进行。将数据集看作一类，根据类内最大相似性的 2)按照合并顺序依次将稠密点与其k邻域中 原则将数据集逐渐细分，直到满足终止条件或每一 的数据点进行合并判定。将数据点的每个特征看作 个数据点构成一类时停止分裂，例如MONA(mono- 一组独立随机变量，根据独立有限差分不等式得出 thetic analysis)算法[9]和DIANA(divisive analysis) 的合并判定准则判断两点是否合并。当2个数据点 算法[9]等。 对其任意的特征具有相同的期望时，划分为同一类
（ｋ≤ｎ），则 Ｃｉ 满足如下条件：１） Ｃｉ ≠∅，（ ｉ ＝ １，２， …，ｋ），即每一子集至少含有一个数据点；２）Ｃｉ∩Ｃｊ ＝ ∅，（１≤ｉ≠ｊ≤ｋ），即每个数据点只能属于一个子集； ３）∪ｋ ｉ＝１Ｃｉ ＝Ｘ，即每个数据点必须归属于某一子集。 数据点 ｘｊ（ｊ ＝ １，２，…，ｎ）对子集 Ｃｉ（ｉ ＝ １，２，…，ｋ）的 隶属关系可用隶属函数 ｕｉｊ表示，当 ｕｉｊ ＝ １ 时，ｘｊ∈ Ｃｉ，当 ｕｉｊ ＝ ０ 时，ｘｊ∉Ｃｉ，其中隶属函数 ｕｉｊ∈｛０，１｝且 满足 ∑ ｋ ｉ ＝ １ ｕｉｊ ＝ １，∀ｊ，０ ＜ ∑ ｎ ｊ ＝ １ ｕｉｊ ＜ ｎ，∀ｉ。 硬聚 类的代表算法有 Ｋ⁃ｍｅａｎｓ 算法［ ５ ］ 和 Ｎｃｕｔｓ（ ｎｏｒｍａｌ⁃ ｉｚｅｄ ｃｕｔｓ）算法［ ６ ］ 。 二者都是致力于得到使目标函 数达到最值的最优聚类。 Ｋ⁃ｍｅａｎｓ 算法取误差平方 和函数作为目标函数，对初始聚类中心和异常点较 为敏感，且面对非凸数据集易陷入局部最优。 Ｎｃｕｔｓ 算法取规范割函数为目标函数，将数据集的聚类问 题转化 为 空 间 中 带 权 无 向 图 的 最 优 划 分 问 题。 Ｎｃｕｔｓ 算法可以聚类任意形状的数据，但大数据聚类 问题对其相似性矩阵的存储和特征向量的计算都是 种挑战。 在模糊聚类中，数据点的类别归属是不明确的， 一个数据点可以属于所有类别。 模糊聚类隶属度的 取值由硬聚类中只能取 ０ 或 １ 变为可以取［０，１］的 任意值，该值用来表示每个数据点属于各个类别的 可能性，仍然满足任意数据点对所有类别的隶属度 之和为 １。 代表性的模糊聚类算法有 ＦＣＭ 算法［ ７ ］ 和 ＰＣＭ（ｐｏｓｓｉｂｉｌｉｔｉｃ Ｃ ｍｅａｎｓ）算法［ ８ ］ 。 ＦＣＭ 算法利 用数据点对每一类别的隶属度构成了一个隶属矩 阵，然后将算法的目标函数转变为一个与隶属矩阵 相关的函数，通过优化该目标函数完成聚类。 为克 服 ＦＣＭ 对噪声敏感的缺点，Ｋｒｉｓｈｎａｐｕｒａｍ 和 Ｋｅｌｌｅｒ 提出了 ＰＣＭ 算法。 该算法舍弃了 ＦＣＭ 算法中每一 点对各类别隶属度总和为 １ 的约束条件，使得噪声 点具有很小的隶属度值，从而增加了算法对噪声的 鲁棒性。 层次聚类算法又称为树聚类算法。 它的主要思 想是对给定的数据集依照相似性矩阵进行层次分 解，使得聚类结果可以由二叉树或系统树图来描述， 即树状嵌套结构为 Ｈ ＝ ｛Ｈ１ ， Ｈ２ ，…， Ｈｑ ｝，（ ｑ≤ ｎ），ｎ 为数据点的个数，当 Ｃｉ∈Ｈｍ ， Ｃｊ∈Ｈｌ且 ｍ＞ｌ， 有 Ｃｉ∈Ｃｊ或 Ｃｉ∩Ｃｊ ＝ ∅对所有 ｉ 成立，ｊ≠ｉ，ｍ，ｌ ＝ １，２，…，ｑ。 层次聚类算法又分为分裂式和凝聚式 ２ 种。 分裂式层次聚类算法采用“自顶向下” 的方式 进行。 将数据集看作一类，根据类内最大相似性的 原则将数据集逐渐细分，直到满足终止条件或每一 个数据点构成一类时停止分裂，例如 ＭＯＮＡ（ｍｏｎｏ⁃ ｔｈｅｔｉｃ ａｎａｌｙｓｉｓ） 算法［９ ］ 和 ＤＩＡＮＡ（ ｄｉｖｉｓｉｖｅ ａｎａｌｙｓｉｓ） 算法［ ９ ］等。 凝聚式层次聚类算法［１０］ 采用“自底向上”的方 式进行。 一开始将数据集的每个数据点看作一类， 然后进行一系列的合并操作，直到满足终止条件或 所有数据点归为一类时停止凝聚。 大部分层次聚类 算法都是采用凝聚式聚类，代表性的算法有基于代 表点的 ＣＵＲＥ 算法［１１ ］ 、基于稠密点的 ＤＢＳＣＡＮ 算 法［１ ２ ］ 、ＮＢＣ（ｎｅｉｇｈｂｏｒｈｏｏｄ ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ）算法［１３ ］ 、 以及基于核心点的 ＭｕｌＣＡ（ｍｕｌｔｉｌｅｖｅｌ ｃｏｒｅ⁃ｓｅｔｓ ｂａｓｅｄ ａｇｇｒｅｇａｔｉｏｎ）算法［１４ ］等。 随着信息技术的迅猛发展，数据源开始不断膨 胀，数据结构也变得日渐复杂，具有类内相异、类间 相似、噪声和重叠现象的数据集层出不穷，这对于计 算机领域中一些易受噪声点和数据集大小影响的经 典聚类算法（如 Ｋ⁃ｍｅａｎｓ、Ｎｃｕｔｓ 等）来说，是一种巨 大的挑战。 在寻求更优的聚类算法的道路上，人们开始将 其他专业领域的知识同聚类算法相结合，统计思想 逐步被应用于聚类算法中。 早期统计聚类方法有 ＧＭＤＤ 算法［１ ５ ］和 ＥＭ 算法［１ ６ ］等。 ＧＭＤＤ 算法将数 据点和噪声点看作是由不同混合高斯分布生成的点 集，利用一个增强的模型模拟估计含有噪声点的原 始模型。 ＥＭ 算法是一种迭代算法，用于含有隐变 量的概率参数模型的最大似然估计或极大后验概率 估计。 ２００４ 年，针对复杂的图像分割问题，Ｎｏｃｋ 和 Ｎｉｅｌｓｅｎ 提出了统计区域合并算法（ ｓｔａｔｉｓｔｉｃａｌ ｒｅｇｉｏｎ ｍｅｒｇｉｎｇ，ＳＲＭ） ［１ ７ ］ 。 具体地，该算法将像素点作为 最基本的区域，把像素的 ３ 个颜色特征看做 ３ 组独 立随机变量，对每一组独立随机变量，根据独立有限 差分不等式得出合并的判定准则，利用像素点梯度 值从小到大的排序获得合并顺序，依据合并准则和 合并顺序，结合像素或区域进行迭代生长。 通过控 制每组独立随机变量的个数，ＳＲＭ 算法实现了对复 杂图像中目标的快速分割和有效提取。 受 ＳＲＭ 方法的启发，本文提出了一种基于密度 的统计合并聚类算法（ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｓｔａｔｉｓｔｉｃａｌ ｍｅｒ⁃ ｇｉｎｇ ｃｌｕｓｔｅｒｉｎｇ，ＤＳＭＣ），该算法主要包括 ２ 个步骤： １）根据数据点的密度信息获得合并顺序及每 一数据点的 ｋ 邻域。 首先利用数据点的空间位置信 息及多维特征信息，计算数据点之间的相似性得到 相似性矩阵，确定每一数据点的 ｋ 邻域。 然后将稠 密点与其 ｋ 邻域中所有点的相似性的最小值作为数 据点的密度信息，将密度从大到小的排序作为合并 的顺序。 ２） 按照合并顺序依次将稠密点与其 ｋ 邻域中 的数据点进行合并判定。 将数据点的每个特征看作 一组独立随机变量，根据独立有限差分不等式得出 的合并判定准则判断两点是否合并。 当 ２ 个数据点 对其任意的特征具有相同的期望时，划分为同一类 第 ５ 期 刘贝贝，等：基于密度的统计合并聚类算法 ·７１３·
·714 智能系统学报 第10卷 别：当2个数据点对其特征至少有一个期望显著不 该统计模型对数据点及数据点特征的取样是相 同时，划分为不同类别。遍历所有的稠密点，实现对 互独立的。对于Q个独立随机变量的分布没有特 数据集的分类。 定要求，即独立不一定同分布。Q的传统取值一般 相比于上述基于密度的凝聚聚类算法（如DB- 为1，即数据点的每个特征只由一个随机变量表示， SCAN、NBC)DSMC算法在数据点生长合并的过程 但是这一取值对于较小的数据集难以获得可靠的估 中，不仅利用了数据点的密度信息，还利用了根据统 计信息。当Q增大时，数据点的特征可以被描述的 计判定准则得出的数据点每一个特征的差异性信 更加细致，因此，Q成为该算法的重要参数之一。调 息。因此，该算法对噪声具有更好的鲁棒性，也对不 整参数Q,不仅可以改变算法的统计复杂性，还可以 规则形状的数据集和密度不均匀的数据集具有更好 控制分类的精确度。将Q的取值从小调大，可以建 的聚类效果。 立一个层次由粗到细的数据聚类结果。 1 DSM 1.2统计合并判定 DSM算法对数据点的合并由一个特定的统计 1.1统计模型的建立 合并判定准则决定。为了简单起见，先只考虑含有 设给定的数据集为X,包含n个数据点，每个数 一个特征信息的数据集，即一个数据点用一组独立 据点含有多个特征信息，用2={A,B,C,…}表示特 随机变量表示。在此基础上，将得到的结果扩展到 征集合，每个特征的取值范围为[L,U:](i=A,B, 具有更多的特征信息的数据集中。 C,…)。为方便应用，对数据集X作整体移动（特征 为了得出统计合并判定准则，介绍定理如下： 信息整体改变不影响分类)，使得特征的取值范围 定理1（独立有限差分不等式[8]）设X= 变为[0，g](i=A,B,C,…),其中g:=IU,-Ll。 (X1,X2,…,X)是一组独立随机变量，X的取值范 然后，将数据点的每一个特征用Q个独立随机变量 围为A(k=1,2,…,n)。假设存在一个定义在 表示，每一个随机变量对应一个分布。以特征A为 Π4：的实值函数f,当变量X与X'仅在第k个条件 例，其可表示为A=（A1,A2,…,A),随机变量A (G=1,2,…,Q)对应第j个分布。由于Q个独立 不同时，满足fX)-f(X)1≤r4,则Hr≥0，有 随机变量和的取值应属于[0，g:](i=A,B,C,…), PfX)-u≥)≤exp(-2x2/∑.()) 则每一个随机变量的取值为[0，g,/Q](i=A,B,C, 式中：4为f代X)的期望，即μ=EfX)。 …)。这样，一个数据点的特征信息就由多组独立 根据定理1，可以推出给定数据集X中的不同 随机变量表示。 类别的绝对偏差不等式。记C为数据集X中的类 对于给定的数据集X,假设存在具有完美聚类 别（单个数据点可作为一个类别），1C1为类别内数 结果的数据集X·,那么在X·中，最优的聚类结果 据点的个数，C表示类别C与其他类别合并时的代 具有如下性质：1)同一类别中的数据点，对于任意 表点，E(C)表示该类别相关数据点Q个独立随机 给定的数据特征都具有相同的期望：2)不同的类别 变量期望和的期望。 中的数据点，对于任意给定的数据特征至少有一个 期望不同。这一性质在合并判定过程中起到非常重 推论1考虑数据集X中的类别组合(C1,C2), V0<δ≤1，下面不等式成立的概率不超过6： 要的作用。 I(C-C)-E(G-C)l≥ 数据点x的特征A G*a 11 2 当E(A,=∑E(A).xy 式中：g=max(g:)(i=A,B,C,…)。 =E(A).=∑E(A) 属于同一类别 证明已知类别C,中的数据点可由Q1C,I个 数据点的特征A 当E(4A)f∑E(A)xy 属于同一类别 独立随机变量表示，类别C2中的数据点可由Q1C2 个独立随机变量表示。(C-C)为实值函数，由于 =E(A)=∑E(A) C,C分别是C1,C,的代表点，若变动C中的变量， 「的最大取值为g/(Q1C,I),若变动C2中的变 图12个数据点任一特征聚类的统计说明 量，4的最大取值为g/(Q1C2I)。 Fig.I The statistical description of two data points 记rc,=g/(QC,),6,=g/(Q|C,l),则 clustering about any feature ∑()2=Q(IC,le,)2+IC2lr)2)=
别；当 ２ 个数据点对其特征至少有一个期望显著不 同时，划分为不同类别。 遍历所有的稠密点，实现对 数据集的分类。 相比于上述基于密度的凝聚聚类算法（如 ＤＢ⁃ ＳＣＡＮ、ＮＢＣ）ＤＳＭＣ 算法在数据点生长合并的过程 中，不仅利用了数据点的密度信息，还利用了根据统 计判定准则得出的数据点每一个特征的差异性信 息。 因此，该算法对噪声具有更好的鲁棒性，也对不 规则形状的数据集和密度不均匀的数据集具有更好 的聚类效果。 １ ＤＳＭ １．１ 统计模型的建立 设给定的数据集为 Ｘ，包含 ｎ 个数据点，每个数 据点含有多个特征信息，用 Ω＝ ｛Ａ，Ｂ，Ｃ，…｝表示特 征集合，每个特征的取值范围为［ Ｌｉ，Ｕｉ ］ （ ｉ ＝ Ａ，Ｂ， Ｃ，…）。 为方便应用，对数据集 Ｘ 作整体移动（特征 信息整体改变不影响分类），使得特征的取值范围 变为［０， ｇｉ ］ （ ｉ ＝ Ａ，Ｂ，Ｃ，…），其中 ｇｉ ＝ ｜ Ｕｉ －Ｌｉ ｜ 。 然后，将数据点的每一个特征用 Ｑ 个独立随机变量 表示，每一个随机变量对应一个分布。 以特征 Ａ 为 例，其可表示为 Ａ ＝ （Ａ１ ， Ａ２ ，…， ＡＱ ），随机变量 Ａｊ （ｊ ＝ １， ２，…，Ｑ）对应第 ｊ 个分布。 由于 Ｑ 个独立 随机变量和的取值应属于［０， ｇｉ］（ｉ ＝ Ａ，Ｂ，Ｃ，…）， 则每一个随机变量的取值为［０， ｇｉ ／ Ｑ］ （ｉ ＝ Ａ，Ｂ，Ｃ， …）。 这样，一个数据点的特征信息就由多组独立 随机变量表示。 对于给定的数据集 Ｘ，假设存在具有完美聚类 结果的数据集 Ｘ ∗ ，那么在 Ｘ ∗ 中，最优的聚类结果 具有如下性质：１） 同一类别中的数据点，对于任意 给定的数据特征都具有相同的期望；２） 不同的类别 中的数据点，对于任意给定的数据特征至少有一个 期望不同。 这一性质在合并判定过程中起到非常重 要的作用。 图 １ ２ 个数据点任一特征聚类的统计说明 Ｆｉｇ． １ Ｔｈｅ ｓｔａｔｉｓｔｉｃａｌ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｔｗｏ ｄａｔａ ｐｏｉｎｔｓ ｃｌｕｓｔｅｒｉｎｇ ａｂｏｕｔ ａｎｙ ｆｅａｔｕｒｅ 该统计模型对数据点及数据点特征的取样是相 互独立的。 对于 Ｑ 个独立随机变量的分布没有特 定要求，即独立不一定同分布。 Ｑ 的传统取值一般 为 １，即数据点的每个特征只由一个随机变量表示， 但是这一取值对于较小的数据集难以获得可靠的估 计信息。 当 Ｑ 增大时，数据点的特征可以被描述的 更加细致，因此，Ｑ 成为该算法的重要参数之一。 调 整参数 Ｑ，不仅可以改变算法的统计复杂性，还可以 控制分类的精确度。 将 Ｑ 的取值从小调大，可以建 立一个层次由粗到细的数据聚类结果。 １．２ 统计合并判定 ＤＳＭ 算法对数据点的合并由一个特定的统计 合并判定准则决定。 为了简单起见，先只考虑含有 一个特征信息的数据集，即一个数据点用一组独立 随机变量表示。 在此基础上，将得到的结果扩展到 具有更多的特征信息的数据集中。 为了得出统计合并判定准则，介绍定理如下： 定理 １ （ 独立有限差分不等式［１ ８ ］ ） 设 Ｘ ＝ （Ｘ１ ， Ｘ２ ，…， Ｘｎ ）是一组独立随机变量，Ｘｋ的取值范 围为 Ａｋ（ ｋ ＝ １， ２，…， ｎ）。 假设存在一个定义在 ∏ｋＡｋ 的实值函数 ｆ，当变量 Ｘ 与 Ｘ′仅在第 ｋ 个条件 不同时，满足｜ ｆ(Ｘ) －ｆ（Ｘ′） ｜≤ｒｋ，则∀τ≥０，有 Ｐ(ｆ(Ｘ) － μ ≥ τ) ≤ ｅｘｐ － ２τ ２ ／ ∑ｋ ｒｋ ( ) ２ ( ) 式中：μ 为 ｆ（Ｘ）的期望，即 μ ＝Ｅｆ（Ｘ）。 根据定理 １，可以推出给定数据集 Ｘ 中的不同 类别的绝对偏差不等式。 记 Ｃ 为数据集 Ｘ 中的类 别（单个数据点可作为一个类别）， ｜ Ｃ ｜ 为类别内数 据点的个数，Ｃ ( 表示类别 Ｃ 与其他类别合并时的代 表点，Ｅ（Ｃ）表示该类别相关数据点 Ｑ 个独立随机 变量期望和的期望。 推论 １ 考虑数据集 Ｘ 中的类别组合（Ｃ１ ，Ｃ２ ）， ∀０＜δ≤１，下面不等式成立的概率不超过 δ： Ｃ１ ( － Ｃ２ ( ( ) － Ｅ Ｃ１ ( － Ｃ２ ( ( ) ≥ ｇ １ ２Ｑ １ Ｃ１ ＋ １ Ｃ２ æ è ç ö ø ÷ ｌｎ ２ δ 式中：ｇ ＝ｍａｘ ｇｉ ( ) （ｉ ＝ Ａ，Ｂ，Ｃ，…）。 证明 已知类别 Ｃ１ 中的数据点可由 Ｑ ｜ Ｃ１ ｜ 个 独立随机变量表示，类别 Ｃ２ 中的数据点可由 Ｑ｜ Ｃ２ ｜ 个独立随机变量表示。 Ｃ１ ( －Ｃ２ ( ( ) 为实值函数，由于 Ｃ１ ( ，Ｃ２ ( 分别是 Ｃ１ ，Ｃ２ 的代表点，若变动 Ｃ１ 中的变量， ｒｋ 的最大取值为 ｇ ／ （Ｑ ｜ Ｃ１ ｜ ），若变动 Ｃ２ 中的变 量，ｒｋ 的最大取值为 ｇ ／ （Ｑ｜ Ｃ２ ｜ ）。 记 ｒＣ１ ＝ ｇ ／ （Ｑ Ｃ１ ），ｒＣ２ ＝ ｇ ／ （Ｑ Ｃ２ ），则 ∑ｋ ｒｋ ( ) ２ ＝ Ｑ Ｃ１ ｒＣ１ ( ) ２ ＋ Ｃ２ ｒＣ２ ( ) ２ ( ) ＝ ·７１４· 智 能 系 统 学 报 第 １０ 卷
第5期 刘贝贝，等：基于密度的统计合并聚类算法 ·715· 由上述合并顺序的获取过程可以看出，k邻域 大小的选择直接影响了数据点密度的大小，进而影 1(11 2 响了DSMC算法的合并顺序。因此，k邻域的大小 根据定理1，取=gG十Gg血谷>0， 也被看作是DSMC算法的一个重要参数。 则 在该算法中，密度的大小不仅受到k邻域的影 P(I(C-C)-E(G-C)l≥ 响，也会受到距离度量(x,y)的影响。针对不同特 征的数据集，选取合适的f(x,y)可以得到更好的聚 171 类结果。在算法中较为常见的距离度量有欧式距 离，马氏距离，最大/最小值距离等。本文实验中主 2r2 < 要应用一种距离度量，它利用数据点最大特征差异 2 进行排序，使得d=max,eks(max(x:-y:),(i=A, 推论得证。 B,C,…),K(x)表示点x的k邻域。随机生成含 由推论1可知，当δ取值接近于零时（本文 有20个点的数据集，选取k邻域大小为4，利用上 若未特别标明，8取为1/(61X12),类别组合 述距离度量，得到DSMC算法的合并顺序如图2 (C,C2)满足不等式1(C-C3)-E(C,-C)1≤ 所示。 b(C1,C2)的概率接近于1，其中b(C1,C2)= 20TG,7G方：若(G,G)可以合并，说 1 明在数据集X·中2者属于同一类别，则有 E(C,-C,)=0。根据这2个前提条件得到如下统计 合并判定准则： ● M(C1,C2)= |ue,1(G-C)l≤b(C,c) false,其他 当类别组合(C,C,)满足|(C-C)|≤ (a)原图 b(C1,C2)时，则合并(C1,C2);反之则不然。 将该准则扩展到具有多个特征信息的数据集 中，形式如下： ftue,a∈{A,B,…f, M(C,C2上 I(G-Ca)|≤b(C,G) false,其他 1.3合并顺序 建立合适的合并准则后，聚类算法的结果受合 并顺序的影响。与随机选取数据点进行合并判定的 算法不同，DSMC算法利用了数据点的密度信息以 获得合并顺序。获取过程可叙述如下：首先，计算数 (b)k=4时的合并顺序 图2DSMC算法的合并顺序 据集中任意2点之间的距离度量（例如欧式距离、 Fig.2 Merging order of DSMC algorithm 最大/最小距离、马氏距离等)，获得度量矩阵：然 后，确定每一数据点的k邻域，选取k邻域中所有点 2DSMC算法的实现 与稠密点距离度量的最大值，作为稠密点的局部密 度信息：最后，根据获得的局部密度信息，将所有数 2.1DSMC算法的实现细节 据点按密度从大到小排序，得到算法的合并顺序。 通过对DSMC算法的详细介绍可知，DSMC算 在整个算法过程中，基于密度的合并顺序保证了在 法主要通过2个步骤实现：步骤1是根据数据点的 任意2个不同的类别进行合并判定时，其自身已经 密度信息获得合并顺序及每一数据点的k邻域：步 完成所有可能的合并。 骤2是按照合并顺序依次将稠密点与其k邻域中的
ｇ ２ Ｑ １ Ｃ１ ＋ １ Ｃ２ æ è ç ö ø ÷ 根据定理 １，取 τ ＝ ｇ １ ２Ｑ １ Ｃ１ ＋ １ Ｃ２ æ è ç ö ø ÷ｌｎ ２ δ ＞０， 则 Ｐ Ｃ１ ( － Ｃ２ ( ( ) － Ｅ Ｃ１ ( － Ｃ２ ( ( ( ) ≥ ｇ １ ２Ｑ １ Ｃ１ ＋ １ Ｃ２ æ è ç ö ø ÷ ｌｎ ２ δ ö ø ÷ ≤ ｅｘｐ － ２τ ２ ∑ｋ ｒｋ ( ) ２ æ è çç ö ø ÷÷ ＝ δ ２ ＜ δ 推论得证。 由推论 １ 可知，当 δ 取值接近于零时（ 本文 若未 特 别 标 明， δ 取 为 １ ／ （ ６ ｜ Ｘ ｜ ２ ） ， 类 别 组 合 （ Ｃ１ ，Ｃ２ ） 满 足 不 等 式 ｜ Ｃ１ ( －Ｃ２ ( ( ) － Ｅ Ｃ１ ( －Ｃ２ ( ( ) ｜ ≤ ｂ（ Ｃ１ ，Ｃ２ ） 的 概 率 接 近 于 １， 其 中 ｂ Ｃ１ ，Ｃ２ ( ) ＝ ｇ １ ２Ｑ （ １ Ｃ１ ＋ １ Ｃ２ ）ｌｎ ２ δ ；若（Ｃ１ ，Ｃ２ ） 可以合并，说 明在 数 据 集 Ｘ ∗ 中 ２ 者 属 于 同 一 类 别， 则 有 Ｅ（Ｃ１ ( －Ｃ２ ( ）＝ ０。 根据这 ２ 个前提条件得到如下统计 合并判定准则： Ｍ Ｃ１ ，Ｃ２ ( ) ＝ ｔｒｕｅ， Ｃ１ ( － Ｃ１ ( ( ) ≤ ｂ Ｃ１ ，Ｃ２ ( ) ｆａｌｓｅ， 其他 { 当 类 别 组 合 （ Ｃ１ ， Ｃ２ ） 满 足 Ｃ１ ( －Ｃ２ ( ( ) ≤ ｂ（Ｃ１ ，Ｃ２ ）时，则合并（Ｃ１ ，Ｃ２ ）；反之则不然。 将该准则扩展到具有多个特征信息的数据集 中，形式如下： Ｍ Ｃ１，Ｃ２ ( )＝ ｔｒｕｅ， ∀ａ ∈｛Ａ，Ｂ，…｝， Ｃａ１ ( － Ｃａ２ ( ( ) ≤ｂ（Ｃ１，Ｃ２） ｆａｌｓｅ，其他 ì î í ï ï ï ï １．３ 合并顺序 建立合适的合并准则后，聚类算法的结果受合 并顺序的影响。 与随机选取数据点进行合并判定的 算法不同，ＤＳＭＣ 算法利用了数据点的密度信息以 获得合并顺序。 获取过程可叙述如下：首先，计算数 据集中任意 ２ 点之间的距离度量（例如欧式距离、 最大／ 最小距离、马氏距离等），获得度量矩阵；然 后，确定每一数据点的 ｋ 邻域，选取 ｋ 邻域中所有点 与稠密点距离度量的最大值，作为稠密点的局部密 度信息；最后，根据获得的局部密度信息，将所有数 据点按密度从大到小排序，得到算法的合并顺序。 在整个算法过程中，基于密度的合并顺序保证了在 任意 ２ 个不同的类别进行合并判定时，其自身已经 完成所有可能的合并。 由上述合并顺序的获取过程可以看出，ｋ 邻域 大小的选择直接影响了数据点密度的大小，进而影 响了 ＤＳＭＣ 算法的合并顺序。 因此，ｋ 邻域的大小 也被看作是 ＤＳＭＣ 算法的一个重要参数。 在该算法中，密度的大小不仅受到 ｋ 邻域的影 响，也会受到距离度量 ｆ（ ｘ，ｙ）的影响。 针对不同特 征的数据集，选取合适的 ｆ（ｘ，ｙ）可以得到更好的聚 类结果。 在算法中较为常见的距离度量有欧式距 离，马氏距离，最大／ 最小值距离等。 本文实验中主 要应用一种距离度量，它利用数据点最大特征差异 进行排序，使得 ｄ ＝ ｍａｘｙ∈Ｋ（ｘ） ｍａｘ ｘｉ －ｙｉ ( ( ) ) ，（ ｉ ＝ Ａ， Ｂ， Ｃ，…）， Ｋ（ ｘ）表示点 ｘ 的 ｋ 邻域。 随机生成含 有 ２０ 个点的数据集，选取 ｋ 邻域大小为 ４，利用上 述距离度量，得到 ＤＳＭＣ 算法的合并顺序如图 ２ 所示。 （ａ）原图 （ｂ）ｋ ＝ ４ 时的合并顺序 图 ２ ＤＳＭＣ 算法的合并顺序 Ｆｉｇ．２ Ｍｅｒｇｉｎｇ ｏｒｄｅｒ ｏｆ ＤＳＭＣ ａｌｇｏｒｉｔｈｍ ２ ＤＳＭＣ 算法的实现 ２．１ ＤＳＭＣ 算法的实现细节 通过对 ＤＳＭＣ 算法的详细介绍可知，ＤＳＭＣ 算 法主要通过 ２ 个步骤实现：步骤 １ 是根据数据点的 密度信息获得合并顺序及每一数据点的 ｋ 邻域；步 骤 ２ 是按照合并顺序依次将稠密点与其 ｋ 邻域中的 第 ５ 期 刘贝贝，等：基于密度的统计合并聚类算法 ·７１５·
·716 智能系统学报 第10卷 数据点进行合并判定，通过遍历所有的稠密点完成 计合并判定得到聚类结果：过程③根据临近数据点 数据的聚类。其中，为更好地处理噪声点，在步骤2 的类别对噪声点进行聚类，比较其k邻域中各类别 中只对a比例的数据（本文默认α=0.9）进行统计 点的个数，将它归为点数最多类别。 判定，剩余数据点根据临近数据点的类别标号。根 200 200 据这2个步骤的内容，具体说明DSMC算法的聚类 150 150 过程如下。 100 。=.100 步骤1：计算数据点的合并顺序并获得数据点 50 的k邻域。 ①504 %⊙j 输入：数据集X;k邻域中数据点个数k。 1000100 200300-1000100200300 1)计算数据集中任意两个点距离，存入矩 1② 阵D。 2)将矩阵D按列进行升序排列，存入矩阵D, 200 200. 其第k行按升序排列，得到密度从大到小的顺序d。 150 150 3)根据顺序d确定数据点的k邻域。 a.100 。.100 输出：合并顺序d:k邻域矩阵W。 ③50 步骤2：将稠密点与其k邻域中的数据点进行 合并判定，然后合并剩余点完成聚类。 100 0100 200300-1000100200300 x 输入：数据集X;合并顺序d:k邻域矩阵W。 图3DSMC算法的聚类过程 1)对数据集中90%的数据点（稠密点）进行合 Fig.3 Clustering process of DSMC algorithm 并判定。 2.2计算复杂度分析 a)根据合并顺序d确定当前稠密点C,然后依 由上述聚类过程可知，DSMC算法的计算量主 次选定其k邻域内的点作为当前合并点C,判断 要集中于2个步骤： 1)构建数据点的距离度量矩阵： CC的类别归属： 2)统计合并判定时对稠密点及其k邻域的 b)计算统计判定准则的临界值b(C,C2)(推 迭代。 论1)，若满足统计合并判定准则，则合并C,C,:若不 对于步骤1)，给定含有n个点的数据集，距离 满足，则进行下一组合并判断，直到遍历完k邻域内 度量矩阵的计算复杂度为0(n2):对于步骤2)，遍 所有的点： 历数据集中所有稠密点，将当前稠密点依次与其k c)重复步骤a)和b),直到遍历完数据集X中 邻域中的点进行统计合并判定，由于k邻域内点的 所有的稠密点。 最大迭代次数为k,因此，步骤2)的计算复杂度为 2)对剩余的10%的数据点进行近邻合并。 O(km)。一般地，k的取值远小于n,则DSMC算法 的计算复杂度可近似于距离度量矩阵的计算复杂度 a)根据合并顺序d确定当前点C; 0(n2)。 b)判断其k邻域内点的分类情况。若有已分 类的点，且其k邻域中属于该类别的点数最多，则将 3实验比较与评价 C归于该类别：若没有已分类的点，则C,不作改变： 将DSMC算法同3种经典聚类算法作比较，它 c)重复步骤a)和b),直到遍历完剩余所有的 们分别是通过聚类中心实现的K-means算法、基于 数据点。 图论的Ncuts算法和基于密度的DBSCAN算法。针 3)计算数据集X的分类个数nbcluster。 对具有不同形状，不同重叠程度和不同噪声点数的 输出：聚类个数nbcluster. 人工数据集以及部分真实数据集进行实验。进一步 由高斯分布随机生成一个可被分为2类的数据 地，对本文提出的DSMC算法的参数选择进行了实 集X,其含40个数据点。用DSMC算法（参数k和 验分析。 Q取为5,15)对数据集X进行聚类，具体过程如图3 由于不同的算法具有不同的参数，在3.1~3.5 所示。过程①对于给定的数据集X计算合并顺序， 节的实验中，实验参数设置如下： 得到首要稠密点及其k邻域：过程②按照数据集的 1)K-means和Ncuts算法：只有1个参数，即想 合并顺序，依次对稠密点和其k邻域中的点进行统 要达到的聚类个数。一般地，实验中将数据集真实 的聚类个数取为参数值
数据点进行合并判定，通过遍历所有的稠密点完成 数据的聚类。 其中，为更好地处理噪声点，在步骤 ２ 中只对 α 比例的数据（本文默认 α ＝ ０．９）进行统计 判定，剩余数据点根据临近数据点的类别标号。 根 据这 ２ 个步骤的内容，具体说明 ＤＳＭＣ 算法的聚类 过程如下。 步骤 １：计算数据点的合并顺序并获得数据点 的 ｋ 邻域。 输入：数据集 Ｘ；ｋ 邻域中数据点个数 ｋ。 １） 计 算 数 据 集 中 任 意 两 个 点 距 离， 存 入 矩 阵 Ｄ。 ２）将矩阵 Ｄ 按列进行升序排列，存入矩阵 Ｄ１ ， 其第 ｋ 行按升序排列，得到密度从大到小的顺序 ｄ。 ３）根据顺序 ｄ 确定数据点的 ｋ 邻域。 输出：合并顺序 ｄ；ｋ 邻域矩阵 Ｗ。 步骤 ２：将稠密点与其 ｋ 邻域中的数据点进行 合并判定，然后合并剩余点完成聚类。 输入：数据集 Ｘ；合并顺序 ｄ；ｋ 邻域矩阵 Ｗ。 １）对数据集中 ９０％的数据点（稠密点）进行合 并判定。 ａ）根据合并顺序 ｄ 确定当前稠密点Ｃ１ ( ，然后依 次选定其 ｋ 邻域内的点作为当前合并点Ｃ２ ( ，判断 Ｃ１ ( Ｃ２ ( 的类别归属； ｂ）计算统计判定准则的临界值 ｂ（Ｃ１ ，Ｃ２ ） （推 论 １），若满足统计合并判定准则，则合并Ｃ１ ( Ｃ２ ( ；若不 满足，则进行下一组合并判断，直到遍历完 ｋ 邻域内 所有的点； ｃ）重复步骤 ａ）和 ｂ），直到遍历完数据集 Ｘ 中 所有的稠密点。 ２）对剩余的 １０％的数据点进行近邻合并。 ａ）根据合并顺序 ｄ 确定当前点Ｃ１ ( ； ｂ）判断其 ｋ 邻域内点的分类情况。 若有已分 类的点，且其 ｋ 邻域中属于该类别的点数最多，则将 Ｃ１ ( 归于该类别；若没有已分类的点，则Ｃ１ ( 不作改变； ｃ）重复步骤 ａ）和 ｂ），直到遍历完剩余所有的 数据点。 ３）计算数据集 Ｘ 的分类个数 ｎｂｃｌｕｓｔｅｒ。 输出：聚类个数 ｎｂｃｌｕｓｔｅｒ。 由高斯分布随机生成一个可被分为 ２ 类的数据 集 Ｘ，其含 ４０ 个数据点。 用 ＤＳＭＣ 算法（参数 ｋ 和 Ｑ 取为 ５，１５）对数据集 Ｘ 进行聚类，具体过程如图 ３ 所示。 过程①对于给定的数据集 Ｘ 计算合并顺序， 得到首要稠密点及其 ｋ 邻域；过程②按照数据集的 合并顺序，依次对稠密点和其 ｋ 邻域中的点进行统 计合并判定得到聚类结果；过程③根据临近数据点 的类别对噪声点进行聚类，比较其 ｋ 邻域中各类别 点的个数，将它归为点数最多类别。 图 ３ ＤＳＭＣ 算法的聚类过程 Ｆｉｇ．３ Ｃｌｕｓｔｅｒｉｎｇ ｐｒｏｃｅｓｓ ｏｆ ＤＳＭＣ ａｌｇｏｒｉｔｈｍ ２．２ 计算复杂度分析 由上述聚类过程可知，ＤＳＭＣ 算法的计算量主 要集中于 ２ 个步骤： １）构建数据点的距离度量矩阵； ２）统计合并判定时对稠密点及其 ｋ 邻域的 迭代。 对于步骤 １），给定含有 ｎ 个点的数据集，距离 度量矩阵的计算复杂度为 Ｏ（ｎ ２ ）；对于步骤 ２），遍 历数据集中所有稠密点，将当前稠密点依次与其 ｋ 邻域中的点进行统计合并判定，由于 ｋ 邻域内点的 最大迭代次数为 ｋ，因此，步骤 ２） 的计算复杂度为 Ｏ（ｋｎ）。 一般地，ｋ 的取值远小于 ｎ，则 ＤＳＭＣ 算法 的计算复杂度可近似于距离度量矩阵的计算复杂度 Ｏ（ｎ ２ ）。 ３ 实验比较与评价 将 ＤＳＭＣ 算法同 ３ 种经典聚类算法作比较，它 们分别是通过聚类中心实现的 Ｋ⁃ｍｅａｎｓ 算法、基于 图论的 Ｎｃｕｔｓ 算法和基于密度的 ＤＢＳＣＡＮ 算法。 针 对具有不同形状，不同重叠程度和不同噪声点数的 人工数据集以及部分真实数据集进行实验。 进一步 地，对本文提出的 ＤＳＭＣ 算法的参数选择进行了实 验分析。 由于不同的算法具有不同的参数，在 ３．１ ～ ３．５ 节的实验中，实验参数设置如下： １）Ｋ⁃ｍｅａｎｓ 和 Ｎｃｕｔｓ 算法：只有 １ 个参数，即想 要达到的聚类个数。 一般地，实验中将数据集真实 的聚类个数取为参数值。 ·７１６· 智 能 系 统 学 报 第 １０ 卷
第5期 刘贝贝，等：基于密度的统计合并聚类算法 ·717 2)DBSCAN算法：共有2个参数，一个是点的邻 10 域半径r,一个是邻域内点的个数阈值m。在实验 中，m一般取10左右的数，邻域半径r则根据数据 集的直径做决定。 3)DSMC算法：共有2个参数，分别是邻域内点 的个数k和划分尺度参数Q。参数k的取值一般根 10 据数据集中数据点的总个数确定。一般初始值取 200 10左右。对于该方法特有的参数Q,它控制了算法 对数据集的划分细度，即当Q较小时，数据集划分 150 细度小，聚类个数少；当Q较大时，数据集划分细度 100 大，聚类个数多。由于参数Q是一个特征独立随机 变量的个数，因此其取值范围为正整数，实验中具体 -100 100200300 取值根据数据集分类需求进行调整，默认初始值 为1。 (c)DBSCAN算法 31形状不同的人工数据集实验 10 10r 将4种聚类算法(K-means,Ncuts,DBSCAN, 5 DSMC)分别应用于4种不同形状的人工数据集上。 它们通过不同类型的高斯分布随机生成，样本点的 个数从左到右第1行分别为600、900：第2行分别 10 为660（包含60个随机噪声点），1100（包含100个 10 10 随机噪声点)。 200 10 10r 150 =100 -100 100200300 200 (d)DSMC算法 图4算法对不同形状数据集的分类结果比较 Fig.4 Comparison of classification results of algorithms for different shape data sets 对任意形状的数据集都有良好聚类效果的算法 100 100200300 才能称之为好的聚类算法。由图4可以看出，K (a)K-means算法 means和Ncuts算法并不能很好的聚类非凸数据集， 10r 而DBSCAN算法（参数m和r从左到右第1行为8， 0.4:7,0.7:第2行为100,48：15,0.4)和本文提出的 DSMC算法（参数k和Q从左到右第1行为6,200： 8,1:第2行为8,1：8,6)对任意形状数据集的聚类 10 效果都很令人满意，但对于较为稀疏的数据点的聚 类，DSMC算法相对更优。 3.2重叠程度不同的人工数据集实验 对数据重叠的鲁棒性也是判断聚类算法好坏的 标准之一。本节中，通过对重叠程度逐渐增大的2 类不同形状的人工数据集进行实验，比较4种聚类 -100 算法对数据重叠的鲁棒性。其中，团状数据集含有 0 100200300 600个数据点：环状数据集含有1000个数据点。 (b)Ncuts算法
２）ＤＢＳＣＡＮ 算法：共有 ２ 个参数，一个是点的邻 域半径 ｒ，一个是邻域内点的个数阈值 ｍ。 在实验 中，ｍ 一般取 １０ 左右的数，邻域半径 ｒ 则根据数据 集的直径做决定。 ３）ＤＳＭＣ 算法：共有 ２ 个参数，分别是邻域内点 的个数 ｋ 和划分尺度参数 Ｑ。 参数 ｋ 的取值一般根 据数据集中数据点的总个数确定。 一般初始值取 １０ 左右。 对于该方法特有的参数 Ｑ，它控制了算法 对数据集的划分细度，即当 Ｑ 较小时，数据集划分 细度小，聚类个数少；当 Ｑ 较大时，数据集划分细度 大，聚类个数多。 由于参数 Ｑ 是一个特征独立随机 变量的个数，因此其取值范围为正整数，实验中具体 取值根据数据集分类需求进行调整，默认初始值 为 １。 ３．１ 形状不同的人工数据集实验 将 ４ 种聚类算 法 （ Ｋ⁃ｍｅａｎｓ， Ｎｃｕｔｓ， ＤＢＳＣＡＮ， ＤＳＭＣ）分别应用于 ４ 种不同形状的人工数据集上。 它们通过不同类型的高斯分布随机生成，样本点的 个数从左到右第 １ 行分别为 ６００、９００；第 ２ 行分别 为 ６６０（包含 ６０ 个随机噪声点），１ １００（包含 １００ 个 随机噪声点）。 （ａ）Ｋ⁃ｍｅａｎｓ 算法 （ｂ）Ｎｃｕｔｓ 算法 （ｃ）ＤＢＳＣＡＮ 算法 （ｄ）ＤＳＭＣ 算法 图 ４ 算法对不同形状数据集的分类结果比较 Ｆｉｇ．４ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｅｓｕｌｔｓ ｏｆ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄｉｆｆｅｒｅｎｔ ｓｈａｐｅ ｄａｔａ ｓｅｔｓ 对任意形状的数据集都有良好聚类效果的算法 才能称之为好的聚类算法。 由图 ４ 可以看出，Ｋ⁃ ｍｅａｎｓ 和 Ｎｃｕｔｓ 算法并不能很好的聚类非凸数据集， 而 ＤＢＳＣＡＮ 算法（参数 ｍ 和 ｒ 从左到右第 １ 行为 ８， ０．４；７，０．７；第 ２ 行为 １００，４８；１５，０．４）和本文提出的 ＤＳＭＣ 算法（参数 ｋ 和 Ｑ 从左到右第 １ 行为 ６，２００； ８，１；第 ２ 行为 ８，１；８，６）对任意形状数据集的聚类 效果都很令人满意，但对于较为稀疏的数据点的聚 类，ＤＳＭＣ 算法相对更优。 ３．２ 重叠程度不同的人工数据集实验 对数据重叠的鲁棒性也是判断聚类算法好坏的 标准之一。 本节中，通过对重叠程度逐渐增大的 ２ 类不同形状的人工数据集进行实验，比较 ４ 种聚类 算法对数据重叠的鲁棒性。 其中，团状数据集含有 ６００ 个数据点；环状数据集含有 １ ０００ 个数据点。 第 ５ 期 刘贝贝，等：基于密度的统计合并聚类算法 ·７１７·
·718 智能系统学报 第10卷 10 10 6 4 2 0 0 (a)K-means算法 (d)DSMC算法 图5对不同重叠程度的团状和环状数据集的分类结果比较 Fig.5 Comparison of classification results on different de- gree of overlap between group and cyclicdata sets 从图5的实验结果可以看出，对于团状数据集， K-means、Ncuts和DSMC(参数k和Q自上而下依次 取为6,200：6,160)算法都能够很好的处理重叠问 题，而DBSCAN算法（参数m和r自上而下依次取 为8,0.4：10,0.6)虽然对一般的团状数据集聚类效 果显著，但随着数据集重叠程度的逐渐增大，聚类效 2 0 果也开始变差。对于环状数据集，像K-means、.Ncuts 这种无法很好的聚类非凸数据集的算法，对于重叠 0 6 0 2 的环状数据集一样效果不好：而DBSCAN算法（参 数m和r自上而下依次取为15,0.4：10,0.5)对环状 (b)Ncuts算法 数据集的聚类类似于团状数据集，对重叠度较高的 数据集不能很好地聚类；本文提出的DSMC算法 (参数k和Q自上而下依次取为7,15：7,75)对于高 重叠度的环状数据集虽然没有得到完美的聚类结 果，但将内环与外环数据归为2类的结果基本令人 满意。相比其他3种聚类算法而言，DSMC算法对 重叠的鲁棒性较好。 3.3噪声点个数不同的人工数据集实验 随着数据源含有噪声现象的增多，算法对噪声 的处理效果也越来越受到人们的关注。为检验本文 0 提出的DSMC算法对含有噪声的数据集的聚类效 果，对逐渐增加噪声点的两类非凸数据集进行实验。 4 1 其中，第1个数据集含有400个数据点，第2个数据 (c)DBSCAN算法 集含有1000个数据点，自上而下对2个数据集分别 加入100、200、300个噪声点。 图6的实验结果说明，DSMC算法（参数k和Q
（ａ）Ｋ⁃ｍｅａｎｓ 算法 （ｂ）Ｎｃｕｔｓ 算法 （ｃ）ＤＢＳＣＡＮ 算法 （ｄ）ＤＳＭＣ 算法 图 ５ 对不同重叠程度的团状和环状数据集的分类结果比较 Ｆｉｇ．５ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｅｓｕｌｔｓ ｏｎ ｄｉｆｆｅｒｅｎｔ ｄｅ⁃ ｇｒｅｅ ｏｆ ｏｖｅｒｌａｐ ｂｅｔｗｅｅｎ ｇｒｏｕｐ ａｎｄ ｃｙｃｌｉｃｄａｔａ ｓｅｔｓ 从图 ５ 的实验结果可以看出，对于团状数据集， Ｋ⁃ｍｅａｎｓ、Ｎｃｕｔｓ 和 ＤＳＭＣ（参数 ｋ 和 Ｑ 自上而下依次 取为 ６，２００；６，１６０）算法都能够很好的处理重叠问 题，而 ＤＢＳＣＡＮ 算法（参数 ｍ 和 ｒ 自上而下依次取 为 ８，０．４；１０，０．６）虽然对一般的团状数据集聚类效 果显著，但随着数据集重叠程度的逐渐增大，聚类效 果也开始变差。 对于环状数据集，像 Ｋ⁃ｍｅａｎｓ、Ｎｃｕｔｓ 这种无法很好的聚类非凸数据集的算法，对于重叠 的环状数据集一样效果不好；而 ＤＢＳＣＡＮ 算法（参 数 ｍ 和 ｒ 自上而下依次取为 １５，０．４；１０，０．５）对环状 数据集的聚类类似于团状数据集，对重叠度较高的 数据集不能很好地聚类；本文提出的 ＤＳＭＣ 算法 （参数 ｋ 和 Ｑ 自上而下依次取为 ７，１５；７，７５）对于高 重叠度的环状数据集虽然没有得到完美的聚类结 果，但将内环与外环数据归为 ２ 类的结果基本令人 满意。 相比其他 ３ 种聚类算法而言，ＤＳＭＣ 算法对 重叠的鲁棒性较好。 ３．３ 噪声点个数不同的人工数据集实验 随着数据源含有噪声现象的增多，算法对噪声 的处理效果也越来越受到人们的关注。 为检验本文 提出的 ＤＳＭＣ 算法对含有噪声的数据集的聚类效 果，对逐渐增加噪声点的两类非凸数据集进行实验。 其中，第 １ 个数据集含有 ４００ 个数据点，第 ２ 个数据 集含有１ ０００个数据点，自上而下对 ２ 个数据集分别 加入 １００、２００、３００ 个噪声点。 图 ６ 的实验结果说明，ＤＳＭＣ 算法（参数 ｋ 和 Ｑ ·７１８· 智 能 系 统 学 报 第 １０ 卷
第5期 刘贝贝，等：基于密度的统计合并聚类算法 ·719. 自上而下依次取为8,1；16,70：8,70：8,6；7,8；9， 3.5真实数据集实验 20)对数据中的噪声具有良好的鲁棒性。 基于对人工数据集良好的聚类效果，本节继续 200r 应用DSMC算法对真实数据集进行聚类，并同K 150 means、Ncuts、DBSCAN算法的聚类结果作比较。实 100 验对象选自UCI数据库(http:/archive.ics.uci.edu/ 50 m/,加州大学欧文分校提出的用于机器学习的数据 。 库，目前包含223个数据集)中的4个不同的数据 -100 0 100200300 集，分别是iris,wine,seeds,.glass。4个数据集的基 20八 本特征如表1所示。 150 表1真实数据集的特征描述 100 Table 1 Characteristic description of real data sets 50 数据集 样本点数 特征个数 类别数 100 100 200 300 iris 150 4 3 200 wine 178 13 150 100 seeds 210 7 3 50 glass 214 10 6 -100 0 100200300 在实验中，DSMC算法中的参数k和Q自上而 图6DSMC算法对逐渐增加噪声点的数据集聚类结果 下依次取为6,140：8,7：6,180：6,70.DBSCAN算法 Fig.6 Clustering results over the noisy data sets of 中的参数m和r自上而下依次取为11,0.5；7,51：5， DSMC algorithm 1.1:l5,8.由表2可知，DSMC算法对iis、seeds和 glass的聚类效果要好于其他3种聚类算法；对wine 3.4混合形状的人工数据集实验 的聚类虽然不如Ncuts算法，但结果基本令人满意， 为进一步说明DSMC算法的有效性，将该算法 说明DSMC算法对真实数据集也有良好的聚类 应用于混合形状的人工数据集（凸状和非凸状混 结果。 合)，其中，该混合数据集含有1520个数据点，包括 320个噪声点。图7表明，DSMC算法（参数k和Q 表2算法对真实数据集聚类结果的比较 为10,100)对这种密度不均匀的混合数据集也能很 Table 2 Comparison of clustering results on real data sets 好地聚类。 Accuracy/% 数据集 10 DSMC K-means Ncuts DBSCAN iris 97.33 89.33 81.33 75.33 wine 72.47 70.22 79.21 53.37 h4 seeds 90.48 89.05 85.24 89.52 glass 77.57 72.90 46.26 64.95 10 3.6DSMC算法参数分析 图7DSMC算法对混合数据集的聚类结果 DSMC算法中涉及到的2个重要参数分别是独 Fig.7 Clustering results of DSMC algorithm for mixed 立随机变量的个数Q和邻域内数据点的个数k。 data set 独立随机变量的个数Q控制了算法的分类精 确度。在固定k邻域的情况下，随着Q取值的逐渐
自上而下依次取为 ８，１；１６，７０；８，７０；８，６；７，８；９， ２０）对数据中的噪声具有良好的鲁棒性。 图 ６ ＤＳＭＣ 算法对逐渐增加噪声点的数据集聚类结果 Ｆｉｇ． ６ Ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｖｅｒ ｔｈｅ ｎｏｉｓｙ ｄａｔａ ｓｅｔｓ ｏｆ ＤＳＭＣ ａｌｇｏｒｉｔｈｍ ３．４ 混合形状的人工数据集实验 为进一步说明 ＤＳＭＣ 算法的有效性，将该算法 应用于混合形状的人工数据集（凸状和非凸状混 合），其中，该混合数据集含有 １ ５２０ 个数据点，包括 ３２０ 个噪声点。 图 ７ 表明，ＤＳＭＣ 算法（参数 ｋ 和 Ｑ 为 １０，１００）对这种密度不均匀的混合数据集也能很 好地聚类。 图 ７ ＤＳＭＣ 算法对混合数据集的聚类结果 Ｆｉｇ．７ Ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｆ ＤＳＭＣ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｉｘｅｄ ｄａｔａ ｓｅｔ ３．５ 真实数据集实验 基于对人工数据集良好的聚类效果，本节继续 应用 ＤＳＭＣ 算法对真实数据集进行聚类，并同 Ｋ⁃ ｍｅａｎｓ、Ｎｃｕｔｓ、ＤＢＳＣＡＮ 算法的聚类结果作比较。 实 验对象选自 ＵＣＩ 数据库（ｈｔｔｐ： ／ ／ ａｒｃｈｉｖｅ．ｉｃｓ．ｕｃｉ．ｅｄｕ ／ ｍｌ ／ ，加州大学欧文分校提出的用于机器学习的数据 库，目前包含 ２２３ 个数据集）中的 ４ 个不同的数据 集，分别是 ｉｒｉｓ，ｗｉｎｅ，ｓｅｅｄｓ，ｇｌａｓｓ。 ４ 个数据集的基 本特征如表 １ 所示。 表 １ 真实数据集的特征描述 Ｔａｂｌｅ １ Ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｒｅａｌ ｄａｔａ ｓｅｔｓ 数据集 样本点数 特征个数 类别数 ｉｒｉｓ １５０ ４ ３ ｗｉｎｅ １７８ １３ ３ ｓｅｅｄｓ ２１０ ７ ３ ｇｌａｓｓ ２１４ １０ ６ 在实验中，ＤＳＭＣ 算法中的参数 ｋ 和 Ｑ 自上而 下依次取为 ６，１４０；８，７；６，１８０；６，７０． ＤＢＳＣＡＮ 算法 中的参数 ｍ 和 ｒ 自上而下依次取为 １１，０．５；７，５１；５， １．１；１５，８． 由表 ２ 可知，ＤＳＭＣ 算法对 ｉｒｉｓ、ｓｅｅｄｓ 和 ｇｌａｓｓ 的聚类效果要好于其他 ３ 种聚类算法；对 ｗｉｎｅ 的聚类虽然不如 Ｎｃｕｔｓ 算法，但结果基本令人满意， 说明 ＤＳＭＣ 算法对真实数据集也有良好的聚类 结果。 表 ２ 算法对真实数据集聚类结果的比较 Ｔａｂｌｅ ２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｎ ｒｅａｌ ｄａｔａ ｓｅｔｓ 数据集 Ａｃｃｕｒａｃｙ ／ ％ ＤＳＭＣ Ｋ⁃ｍｅａｎｓ Ｎｃｕｔｓ ＤＢＳＣＡＮ ｉｒｉｓ ９７．３３ ８９．３３ ８１．３３ ７５．３３ ｗｉｎｅ ７２．４７ ７０．２２ ７９．２１ ５３．３７ ｓｅｅｄｓ ９０．４８ ８９．０５ ８５．２４ ８９．５２ ｇｌａｓｓ ７７．５７ ７２．９０ ４６．２６ ６４．９５ ３．６ ＤＳＭＣ 算法参数分析 ＤＳＭＣ 算法中涉及到的 ２ 个重要参数分别是独 立随机变量的个数 Ｑ 和邻域内数据点的个数 ｋ。 独立随机变量的个数 Ｑ 控制了算法的分类精 确度。 在固定 ｋ 邻域的情况下，随着 Ｑ 取值的逐渐 第 ５ 期 刘贝贝，等：基于密度的统计合并聚类算法 ·７１９·
·720 智能系统学报 第10卷 增大，聚类个数也会随之增多。图8显示了在固定 150 k的情况下，不同的Q值对环状人工数据集和真实 数据集iis产生的不同聚类效果。对于环状人工数 100 据集，固定k=8,Q取1~16时数据集得到完美聚 50 类，随着Q值的增大，分类更加细化，聚类个数逐渐 0 增多。对于真实数据集iis,固定k=6,Q取1~52 -20 50100 150 时数据集后2类不能被分开，分类正确率低：当Q (a)k=6(1-7) (b)k=2(1-5) 增大至53~252时，后两类被分开，分类正确率增至 140 最大；当Q取252以上，类别数增加，分类正确率 120 下降。 100 80 80 60 40 6 0 0 50100150 (c)k=10(8-18) (d)k=6 0 50 2 100150 40 (a)Q-1(1-16) (b)O=1(1-52) 140 120 20 50100150 100 80 60 (e)k=20(19以上) (Dk=10(7以上) 40 -2 0 2 50.100150 图9固定Q值时，不同k的聚类结果 (c)Q=50(17-52) (d)Q=100(53-251) Fig.9 Clustering results of different k with a fixed value 200r 150 4 结束语 100 6o6a 随着信息技术水平的不断提高，具有噪声和重 50 叠现象的数据源越来越多，仅限于计算机领域的聚 -202 50100150 类方法不能很好地处理该问题。为此，本文提出了 (e)Q=150(53以上) (6Q=500(252以上) 一种同统计思想相结合的快速聚类算法一DSMC算 图8固定k值时，不同Q的聚类结果 法，它使用了一个简单的合并顺序和统计判定准则， Fig.8 Clustering results of different O with a fixed k value 将数据点的每一个特征看作一组独立随机变量，根 邻域内数据点的个数k决定了算法的合并顺 据独立有限差分不等式得出统计合并判定准则，同 序，在固定Q值的情况下，随着k邻域的逐渐增大， 时，结合数据点的密度信息，把密度从大到小的排序 聚类个数会随之减少。图9显示了在固定Q的情 作为凝聚过程中的合并顺序，进而实现各类数据点 况下，将k逐渐增大时的两个数据集聚类效果。对 的统计合并。对人工数据集和真实数据集测试的实 于环状人工数据集，固定Q=1,当k取1~7时，分类 验结果表明，DSMC算法对于非凸状、重叠和加入噪 个数过多，聚类结果并不理想：当k取8~18时，聚 声的数据集都有良好的聚类效果。 类结果稳定且保持较高水平：当k取19以上时，数 据集被聚为一类，结果不理想。对于真实数据集i 在后续的研究工作中，将进一步推广DSMC算 is,同人工数据集类似，当k取53~251时，可获得 法的应用范围，使其能够快速、高效地处理大数据、 稳定的高水平聚类结果。 在线数据等多种型态的复杂聚类问题
增大，聚类个数也会随之增多。 图 ８ 显示了在固定 ｋ 的情况下，不同的 Ｑ 值对环状人工数据集和真实 数据集 ｉｒｉｓ 产生的不同聚类效果。 对于环状人工数 据集，固定 ｋ ＝ ８，Ｑ 取 １ ～ １６ 时数据集得到完美聚 类，随着 Ｑ 值的增大，分类更加细化，聚类个数逐渐 增多。 对于真实数据集 ｉｒｉｓ，固定 ｋ ＝ ６，Ｑ 取 １ ～ ５２ 时数据集后 ２ 类不能被分开，分类正确率低；当 Ｑ 增大至 ５３～２５２ 时，后两类被分开，分类正确率增至 最大；当 Ｑ 取 ２５２ 以上，类别数增加，分类正确率 下降。 图 ８ 固定 ｋ 值时，不同 Ｑ 的聚类结果 Ｆｉｇ．８ Ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｆ ｄｉｆｆｅｒｅｎｔ Ｑ ｗｉｔｈ ａ ｆｉｘｅｄ ｋ ｖａｌｕｅ 邻域内数据点的个数 ｋ 决定了算法的合并顺 序，在固定 Ｑ 值的情况下，随着 ｋ 邻域的逐渐增大， 聚类个数会随之减少。 图 ９ 显示了在固定 Ｑ 的情 况下，将 ｋ 逐渐增大时的两个数据集聚类效果。 对 于环状人工数据集，固定 Ｑ＝ １，当 ｋ 取 １～７ 时，分类 个数过多，聚类结果并不理想；当 ｋ 取 ８ ～ １８ 时，聚 类结果稳定且保持较高水平；当 ｋ 取 １９ 以上时，数 据集被聚为一类，结果不理想。 对于真实数据集 ｉ⁃ ｒｉｓ，同人工数据集类似，当 ｋ 取 ５３ ～ ２５１ 时，可获得 稳定的高水平聚类结果。 图 ９ 固定 Ｑ 值时，不同 ｋ 的聚类结果 Ｆｉｇ．９ Ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｋ ｗｉｔｈ ａ ｆｉｘｅｄ Ｑ ｖａｌｕｅ ４ 结束语 随着信息技术水平的不断提高，具有噪声和重 叠现象的数据源越来越多，仅限于计算机领域的聚 类方法不能很好地处理该问题。 为此，本文提出了 一种同统计思想相结合的快速聚类算法—ＤＳＭＣ 算 法，它使用了一个简单的合并顺序和统计判定准则， 将数据点的每一个特征看作一组独立随机变量，根 据独立有限差分不等式得出统计合并判定准则，同 时，结合数据点的密度信息，把密度从大到小的排序 作为凝聚过程中的合并顺序，进而实现各类数据点 的统计合并。 对人工数据集和真实数据集测试的实 验结果表明，ＤＳＭＣ 算法对于非凸状、重叠和加入噪 声的数据集都有良好的聚类效果。 在后续的研究工作中，将进一步推广 ＤＳＭＣ 算 法的应用范围，使其能够快速、高效地处理大数据、 在线数据等多种型态的复杂聚类问题。 ·７２０· 智 能 系 统 学 报 第 １０ 卷
第5期 刘贝贝，等：基于密度的统计合并聚类算法 ·721. [14]马儒宁，王秀丽，丁军娣.多层核心集凝聚算法[J】.软 参考文献： 件学报，2013,24(3)：490-506. [1]XU Rui,WUNSCHII D.Survey of clustering algorithms[J]. MA Runing,WANG Xiuli,DING Jundi.Multilevel core- IEEE Transactions on Neural Networks,2005,16(3): sets based aggregation clustering algorithm[J].Journal of 645-678. Software,2013,24(3):490-506. [2]JAIN A K,MURTY M N,FLYNN P J.Data clustering:a [15]ZHUANG Xuan,HUANG Yan,PALANIAPPAN K,et al. review[J].Acm Computing Surveys,1999,31(2):264- Gaussian mixture density modeling,decomposition,and 323. applications[J].IEEE Transactions on Image Processing, [3]MURTAGH F,CONTRERAS P.Algorithms for hierarchical 1996,5(9):1293-1302. clustering:an overview [J].Wiley Interdisciplinary Re- [16]MACLACHLAN G J,KRISHNAN T.The EM algorithm views:Data Mining and Knowledge Discovery,2012,2 and extensions[J].Series in Probability Statistics, (1):86-97. 1997.15(1):154-156. [4]TSENG L Y,YANG S B.A genetic approach to the auto- matic clustering problem[J].Pattern Recognition,2001, [17 NOCK R,NIELSEN F.Statistical region merging [J]. 34(2):415-424. IEEE Transactions on Pattern Analysis and Machine Intel- [5]FORGY E W.Cluster analysis of multivariate data:efficien- 1l igence,2004,26(11):1452-1458. cy versus interpretability of classifications[.Biometrics, [18]HABIB M,MCDIARMID C.RAMIREZ-ALFONSIN J,et 1965,21:768-769. al.Probabilistic methods for algorithmic discrete mathemat- [6]SHI J,MALIK J.Normalized cuts and image segmentation ics[M].Berlin:Springer-Verlag,1998:1-54. [J].IEEE Transactions on Pattern Analysis and Machine 作者简介： Intelligence,2000,22(8):888-905. 刘贝贝，女，1990年生，硕士研究 [7]BEZDEK J C,EHRLICH R,FULL W.FCM:The fuzzy c- means clustering algorithm[J].Computers Geosciences, 生，主要研究方向为模式识别。 1984,10(2-3):191-203. [8]KRISHNAPURAM R,KELLER J M.A possibilistic ap- proach to clustering[].IEEE Transactions on Fuzzy Sys- tems,1993,1(2):98-110. [9]ALPERT C J,KAHNG A B.Recent directions in netlist partitioning:a survey[J].Integration,the VLSI Journal, 马儒宁，男，1976年生，副教授，博 1995.19(1):1-81. 士，主要研究方向为应用数学、模式识 [10]ACKERMANN M R,BLOMER J,KUNTZE D,et al. 别。参与完成国家自然科学基金项目 Analysis of agglomerative clustering [J].Algorithmica, 10余项。发表学术论文20余篇，其中 2014,69(1):184-215. [11]GUHA S,RASTOGI R,SHIM K.Cure:an efficient clus- 被SCL,EI收录10余篇。 tering algorithm for large databases[J].Information Sys- tems,2001,26(1):35-58. [12]ESTER M,KRIEGEL H P,SANDER J,et al.A density- 丁军娣，女，1978年生，副教授，博 based algorithm for discovering clusters in large spatial data- 士，中国计算机学会会员，主要研究方 bases with noise [C]//Proceedings of 2nd International 向为模式识别、计算机视觉。主持并完 Conference on Knowledge Discovery and Data Mining.Port- 成国家自然科学基金项目10余项。发 land.USA,1996:226-231. 表学术论文20余篇，其中被SCI,EI收 [13 ZHOU Shuigeng,ZHAO Yue,GUAN Jihong,et al.A 录10余篇。 neighborhood-based clustering algorithm[M]//Advances in Knowledge Discovery and Data Mining.Berlin/Heidelberg: Springer,2005:361-371
参考文献： ［１］ＸＵ Ｒｕｉ， ＷＵＮＳＣＨＩＩ Ｄ． Ｓｕｒｖｅｙ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ， ２００５， １６ （ ３ ）： ６４５⁃６７８． ［２］ＪＡＩＮ Ａ Ｋ， ＭＵＲＴＹ Ｍ Ｎ， ＦＬＹＮＮ Ｐ Ｊ． Ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ： ａ ｒｅｖｉｅｗ［Ｊ］． Ａｃｍ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ， １９９９， ３１（ ２）： ２６４⁃ ３２３． ［３］ＭＵＲＴＡＧＨ Ｆ， ＣＯＮＴＲＥＲＡＳ Ｐ． Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅｒｉｎｇ： ａｎ ｏｖｅｒｖｉｅｗ ［ Ｊ ］． Ｗｉｌｅｙ Ｉｎｔｅｒｄｉｓｃｉｐｌｉｎａｒｙ Ｒｅ⁃ ｖｉｅｗｓ： Ｄａｔａ Ｍｉｎｉｎｇ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ， ２０１２， ２ （１）： ８６⁃９７． ［４］ＴＳＥＮＧ Ｌ Ｙ， ＹＡＮＧ Ｓ Ｂ． Ａ ｇｅｎｅｔｉｃ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ａｕｔｏ⁃ ｍａｔｉｃ ｃｌｕｓｔｅｒｉｎｇ ｐｒｏｂｌｅｍ ［ Ｊ］． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， ２００１， ３４（２）： ４１５⁃４２４． ［５］ＦＯＲＧＹ Ｅ Ｗ． Ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ ｏｆ ｍｕｌｔｉｖａｒｉａｔｅ ｄａｔａ： ｅｆｆｉｃｉｅｎ⁃ ｃｙ ｖｅｒｓｕｓ ｉｎｔｅｒｐｒｅｔａｂｉｌｉｔｙ ｏｆ ｃｌａｓｓｉｆｉｃａｔｉｏｎｓ［ Ｊ］． Ｂｉｏｍｅｔｒｉｃｓ， １９６５， ２１： ７６８⁃７６９． ［６］ ＳＨＩ Ｊ， ＭＡＬＩＫ Ｊ． Ｎｏｒｍａｌｉｚｅｄ ｃｕｔｓ ａｎｄ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０００， ２２（８）： ８８８⁃９０５． ［７］ＢＥＺＤＥＫ Ｊ Ｃ， ＥＨＲＬＩＣＨ Ｒ， ＦＵＬＬ Ｗ． ＦＣＭ： Ｔｈｅ ｆｕｚｚｙ ｃ⁃ ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ｃｏｍｐｕｔｅｒｓ ＆ Ｇｅｏｓｃｉｅｎｃｅｓ， １９８４， １０（２⁃３）： １９１⁃２０３． ［８］ ＫＲＩＳＨＮＡＰＵＲＡＭ Ｒ， ＫＥＬＬＥＲ Ｊ Ｍ． Ａ ｐｏｓｓｉｂｉｌｉｓｔｉｃ ａｐ⁃ ｐｒｏａｃｈ ｔｏ ｃｌｕｓｔｅｒｉｎｇ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｆｕｚｚｙ Ｓｙｓ⁃ ｔｅｍｓ， １９９３， １（２）： ９８⁃１１０． ［９］ ＡＬＰＥＲＴ Ｃ Ｊ， ＫＡＨＮＧ Ａ Ｂ． Ｒｅｃｅｎｔ ｄｉｒｅｃｔｉｏｎｓ ｉｎ ｎｅｔｌｉｓｔ ｐａｒｔｉｔｉｏｎｉｎｇ： ａ ｓｕｒｖｅｙ ［ Ｊ］． Ｉｎｔｅｇｒａｔｉｏｎ， ｔｈｅ ＶＬＳＩ Ｊｏｕｒｎａｌ， １９９５， １９（１）： １⁃８１． ［１０］ ＡＣＫＥＲＭＡＮＮ Ｍ Ｒ， ＢＬÖＭＥＲ Ｊ， ＫＵＮＴＺＥ Ｄ， ｅｔ ａｌ． Ａｎａｌｙｓｉｓ ｏｆ ａｇｇｌｏｍｅｒａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ ］． Ａｌｇｏｒｉｔｈｍｉｃａ， ２０１４， ６９（１）： １８４⁃２１５． ［１１］ＧＵＨＡ Ｓ， ＲＡＳＴＯＧＩ Ｒ， ＳＨＩＭ Ｋ． Ｃｕｒｅ： ａｎ ｅｆｆｉｃｉｅｎｔ ｃｌｕｓ⁃ ｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｌａｒｇｅ ｄａｔａｂａｓｅｓ ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓ⁃ ｔｅｍｓ， ２００１， ２６（１）： ３５⁃５８． ［１２］ＥＳＴＥＲ Ｍ， ＫＲＩＥＧＥＬ Ｈ Ｐ， ＳＡＮＤＥＲ Ｊ， ｅｔ ａｌ． Ａ ｄｅｎｓｉｔｙ⁃ ｂａｓｅｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｉｓｃｏｖｅｒｉｎｇ ｃｌｕｓｔｅｒｓ ｉｎ ｌａｒｇｅ ｓｐａｔｉａｌ ｄａｔａ⁃ ｂａｓｅｓ ｗｉｔｈ ｎｏｉｓｅ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｐｏｒｔ⁃ ｌａｎｄ， ＵＳＡ， １９９６： ２２６⁃２３１． ［１３］ ＺＨＯＵ Ｓｈｕｉｇｅｎｇ， ＺＨＡＯ Ｙｕｅ， ＧＵＡＮ Ｊｉｈｏｎｇ， ｅｔ ａｌ． Ａ ｎｅｉｇｈｂｏｒｈｏｏｄ⁃ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｍ］ ／ ／ Ａｄｖａｎｃｅｓ ｉｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｂｅｒｌｉｎ ／ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００５： ３６１⁃３７１． ［１４］马儒宁， 王秀丽， 丁军娣． 多层核心集凝聚算法［Ｊ］． 软 件学报， ２０１３， ２４（３）： ４９０⁃５０６． ＭＡ Ｒｕｎｉｎｇ， ＷＡＮＧ Ｘｉｕｌｉ， ＤＩＮＧ Ｊｕｎｄｉ． Ｍｕｌｔｉｌｅｖｅｌ ｃｏｒｅ⁃ ｓｅｔｓ ｂａｓｅｄ ａｇｇｒｅｇａｔｉｏｎ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ， ２０１３， ２４（３）： ４９０⁃５０６． ［１５］ＺＨＵＡＮＧ Ｘｕａｎ， ＨＵＡＮＧ Ｙａｎ， ＰＡＬＡＮＩＡＰＰＡＮ Ｋ， ｅｔ ａｌ． Ｇａｕｓｓｉａｎ ｍｉｘｔｕｒｅ ｄｅｎｓｉｔｙ ｍｏｄｅｌｉｎｇ， ｄｅｃｏｍｐｏｓｉｔｉｏｎ， ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， １９９６， ５（９）： １２９３⁃１３０２． ［１６］ ＭＡＣＬＡＣＨＬＡＮ Ｇ Ｊ， ＫＲＩＳＨＮＡＮ Ｔ． Ｔｈｅ ＥＭ ａｌｇｏｒｉｔｈｍ ａｎｄ ｅｘｔｅｎｓｉｏｎｓ ［ Ｊ ］． Ｓｅｒｉｅｓ ｉｎ Ｐｒｏｂａｂｉｌｉｔｙ ＆ Ｓｔａｔｉｓｔｉｃｓ， １９９７， １５（１）： １５４⁃１５６． ［１７］ ＮＯＣＫ Ｒ， ＮＩＥＬＳＥＮ Ｆ． Ｓｔａｔｉｓｔｉｃａｌ ｒｅｇｉｏｎ ｍｅｒｇｉｎｇ ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌ⁃ ｌｉｇｅｎｃｅ， ２００４， ２６（１１）： １４５２⁃１４５８． ［１８］ＨＡＢＩＢ Ｍ， ＭＣＤＩＡＲＭＩＤ Ｃ， ＲＡＭＩＲＥＺ⁃ＡＬＦＯＮＳＩＮ Ｊ， ｅｔ ａｌ． Ｐｒｏｂａｂｉｌｉｓｔｉｃ ｍｅｔｈｏｄｓ ｆｏｒ ａｌｇｏｒｉｔｈｍｉｃ ｄｉｓｃｒｅｔｅ ｍａｔｈｅｍａｔ⁃ ｉｃｓ［Ｍ］． Ｂｅｒｌｉｎ： Ｓｐｒｉｎｇｅｒ⁃Ｖｅｒｌａｇ， １９９８： １⁃５４． 作者简介： 刘贝贝，女， １９９０ 年生， 硕士研究 生，主要研究方向为模式识别。 马儒宁，男，１９７６ 年生，副教授，博 士，主要研究方向为应用数学、模式识 别。 参与完成国家自然科学基金项目 １０ 余项。 发表学术论文 ２０ 余篇，其中 被 ＳＣＩ、ＥＩ 收录 １０ 余篇。 丁军娣，女，１９７８ 年生，副教授，博 士，中国计算机学会会员，主要研究方 向为模式识别、计算机视觉。 主持并完 成国家自然科学基金项目 １０ 余项。 发 表学术论文 ２０ 余篇，其中被 ＳＣＩ、ＥＩ 收 录 １０ 余篇。 第 ５ 期 刘贝贝，等：基于密度的统计合并聚类算法 ·７２１·
