第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,0<∑西，<n,i。硬聚 以及基于核心点的MulCA(multilevel core--sets based aggregation)算法[4]等。 类的代表算法有K-means算法s]和Ncuts(normal- 随着信息技术的迅猛发展，数据源开始不断膨 ized cuts)算法[6]。二者都是致力于得到使目标函 胀，数据结构也变得日渐复杂，具有类内相异、类间 数达到最值的最优聚类。K-means算法取误差平方 相似、噪声和重叠现象的数据集层出不穷，这对于计 和函数作为目标函数，对初始聚类中心和异常点较 算机领域中一些易受噪声点和数据集大小影响的经 为敏感，且面对非凸数据集易陷入局部最优。Ncuts 典聚类算法（如K-means、Ncuts等）来说，是一种巨 算法取规范割函数为目标函数，将数据集的聚类问 大的挑战。 题转化为空间中带权无向图的最优划分问题。 在寻求更优的聚类算法的道路上，人们开始将 Ncuts算法可以聚类任意形状的数据，但大数据聚类 其他专业领域的知识同聚类算法相结合，统计思想 问题对其相似性矩阵的存储和特征向量的计算都是 逐步被应用于聚类算法中。早期统计聚类方法有 种挑战。 GMDD算法[1s]和EM算法[16]等。GMDD算法将数 在模糊聚类中，数据点的类别归属是不明确的， 据点和噪声点看作是由不同混合高斯分布生成的点 一个数据点可以属于所有类别。模糊聚类隶属度的 集，利用一个增强的模型模拟估计含有噪声点的原 取值由硬聚类中只能取0或1变为可以取[0,1]的 始模型。EM算法是一种迭代算法，用于含有隐变 任意值，该值用来表示每个数据点属于各个类别的 量的概率参数模型的最大似然估计或极大后验概率 可能性，仍然满足任意数据点对所有类别的隶属度 估计。2004年，针对复杂的图像分割问题，NoCk和 之和为1。代表性的模糊聚类算法有FCM算法[刀 Nielsen提出了统计区域合并算法(statistical region 和PCM(possibilitic C means)算法[8]。FCM算法利 merging,SRM)u7]。具体地，该算法将像素点作为 用数据点对每一类别的隶属度构成了一个隶属矩 最基本的区域，把像素的3个颜色特征看做3组独 阵，然后将算法的目标函数转变为一个与隶属矩阵 立随机变量，对每一组独立随机变量，根据独立有限 相关的函数，通过优化该目标函数完成聚类。为克 差分不等式得出合并的判定准则，利用像素点梯度 服FCM对噪声敏感的缺点，Krishnapuram和Keller 值从小到大的排序获得合并顺序，依据合并准则和 提出了PCM算法。该算法舍弃了FCM算法中每一 合并顺序，结合像素或区域进行迭代生长。通过控 点对各类别隶属度总和为1的约束条件，使得噪声 制每组独立随机变量的个数，SRM算法实现了对复 点具有很小的隶属度值，从而增加了算法对噪声的 杂图像中目标的快速分割和有效提取。 鲁棒性。 受SRM方法的启发，本文提出了一种基于密度 层次聚类算法又称为树聚类算法。它的主要思 的统计合并聚类算法(density-based statistical mer- 想是对给定的数据集依照相似性矩阵进行层次分 ging clustering,DSMC),该算法主要包括2个步骤： 解，使得聚类结果可以由二叉树或系统树图来描述， 1)根据数据点的密度信息获得合并顺序及每 即树状嵌套结构为H={H,H2,…,H,},（q≤ 数据点的k邻域。首先利用数据点的空间位置信 n),n为数据点的个数，当C:∈Hm,CeH,且m>l, 息及多维特征信息，计算数据点之间的相似性得到 有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邻域中的点进行统 要达到的聚类个数。一般地，实验中将数据集真实 的聚类个数取为参数值
数据点进行合并判定，通过遍历所有的稠密点完成 数据的聚类。 其中，为更好地处理噪声点，在步骤 ２ 中只对 α 比例的数据（本文默认 α ＝ ０．９）进行统计 判定，剩余数据点根据临近数据点的类别标号。 根 据这 ２ 个步骤的内容，具体说明 ＤＳＭＣ 算法的聚类 过程如下。 步骤 １：计算数据点的合并顺序并获得数据点 的 ｋ 邻域。 输入：数据集 Ｘ；ｋ 邻域中数据点个数 ｋ。 １） 计 算 数 据 集 中 任 意 两 个 点 距 离， 存 入 矩 阵 Ｄ。 ２）将矩阵 Ｄ 按列进行升序排列，存入矩阵 Ｄ１ ， 其第 ｋ 行按升序排列，得到密度从大到小的顺序 ｄ。 ３）根据顺序 ｄ 确定数据点的 ｋ 邻域。 输出：合并顺序 ｄ；ｋ 邻域矩阵 Ｗ。 步骤 ２：将稠密点与其 ｋ 邻域中的数据点进行 合并判定，然后合并剩余点完成聚类。 输入：数据集 Ｘ；合并顺序 ｄ；ｋ 邻域矩阵 Ｗ。 １）对数据集中 ９０％的数据点（稠密点）进行合 并判定。 ａ）根据合并顺序 ｄ 确定当前稠密点Ｃ１ ( ，然后依 次选定其 ｋ 邻域内的点作为当前合并点Ｃ２ ( ，判断 Ｃ１ ( Ｃ２ ( 的类别归属； ｂ）计算统计判定准则的临界值 ｂ（Ｃ１ ，Ｃ２ ） （推 论 １），若满足统计合并判定准则，则合并Ｃ１ ( Ｃ２ ( ；若不 满足，则进行下一组合并判断，直到遍历完 ｋ 邻域内 所有的点； ｃ）重复步骤 ａ）和 ｂ），直到遍历完数据集 Ｘ 中 所有的稠密点。 ２）对剩余的 １０％的数据点进行近邻合并。 ａ）根据合并顺序 ｄ 确定当前点Ｃ１ ( ； ｂ）判断其 ｋ 邻域内点的分类情况。 若有已分 类的点，且其 ｋ 邻域中属于该类别的点数最多，则将 Ｃ１ ( 归于该类别；若没有已分类的点，则Ｃ１ ( 不作改变； ｃ）重复步骤 ａ）和 ｂ），直到遍历完剩余所有的 数据点。 ３）计算数据集 Ｘ 的分类个数 ｎｂｃｌｕｓｔｅｒ。 输出：聚类个数 ｎｂｃｌｕｓｔｅｒ。 由高斯分布随机生成一个可被分为 ２ 类的数据 集 Ｘ，其含 ４０ 个数据点。 用 ＤＳＭＣ 算法（参数 ｋ 和 Ｑ 取为 ５，１５）对数据集 Ｘ 进行聚类，具体过程如图 ３ 所示。 过程①对于给定的数据集 Ｘ 计算合并顺序， 得到首要稠密点及其 ｋ 邻域；过程②按照数据集的 合并顺序，依次对稠密点和其 ｋ 邻域中的点进行统 计合并判定得到聚类结果；过程③根据临近数据点 的类别对噪声点进行聚类，比较其 ｋ 邻域中各类别 点的个数，将它归为点数最多类别。 图 ３ ＤＳＭＣ 算法的聚类过程 Ｆｉｇ．３ Ｃｌｕｓｔｅｒｉｎｇ ｐｒｏｃｅｓｓ ｏｆ ＤＳＭＣ ａｌｇｏｒｉｔｈｍ ２．２ 计算复杂度分析 由上述聚类过程可知，ＤＳＭＣ 算法的计算量主 要集中于 ２ 个步骤： １）构建数据点的距离度量矩阵； ２）统计合并判定时对稠密点及其 ｋ 邻域的 迭代。 对于步骤 １），给定含有 ｎ 个点的数据集，距离 度量矩阵的计算复杂度为 Ｏ（ｎ ２ ）；对于步骤 ２），遍 历数据集中所有稠密点，将当前稠密点依次与其 ｋ 邻域中的点进行统计合并判定，由于 ｋ 邻域内点的 最大迭代次数为 ｋ，因此，步骤 ２） 的计算复杂度为 Ｏ（ｋｎ）。 一般地，ｋ 的取值远小于 ｎ，则 ＤＳＭＣ 算法 的计算复杂度可近似于距离度量矩阵的计算复杂度 Ｏ（ｎ ２ ）。 ３ 实验比较与评价 将 ＤＳＭＣ 算法同 ３ 种经典聚类算法作比较，它 们分别是通过聚类中心实现的 Ｋ⁃ｍｅａｎｓ 算法、基于 图论的 Ｎｃｕｔｓ 算法和基于密度的 ＤＢＳＣＡＮ 算法。 针 对具有不同形状，不同重叠程度和不同噪声点数的 人工数据集以及部分真实数据集进行实验。 进一步 地，对本文提出的 ＤＳＭＣ 算法的参数选择进行了实 验分析。 由于不同的算法具有不同的参数，在 ３．１ ～ ３．５ 节的实验中，实验参数设置如下： １）Ｋ⁃ｍｅａｎｓ 和 Ｎｃｕｔｓ 算法：只有 １ 个参数，即想 要达到的聚类个数。 一般地，实验中将数据集真实 的聚类个数取为参数值。 ·７１６· 智 能 系 统 学 报 第 １０ 卷