第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}第 １０ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．５ ２０１５ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１５ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１４１００２８ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０９３０．１５５６．０１６．ｈｔｍｌ 基于密度的统计合并聚类算法 刘贝贝１ ，马儒宁１ ，丁军娣２ （１． 南京航空航天大学 理学院，江苏 南京 ２１１１００； ２． 南京理工大学 计算机科学与技术学院，江苏 南京 ２１００９４） 摘 要：针对现有聚类算法处理噪声能力差和速度较慢的问题，提出了一种基于密度的统计合并聚类算法（ＤＳＭＣ）。 该算法将数据点的每一个特征看作一组独立随机变量，根据独立有限差分不等式得出统计合并判定准则；同时，结 合数据点的密度信息，把密度从大到小的排序作为凝聚过程中的合并顺序，实现了各类数据点的统计合并。 人工数 据集和真实数据集的实验结果表明，ＤＳＭＣ 算法不仅可以处理凸状数据集，对于非凸、重叠、加入噪声的数据集也有 良好的聚类效果，充分表明了该算法的适用性和有效性。 关键词：数据点；密度；随机变量；合并；聚类；噪声 中图分类号：Ｏ２３５；ＴＰ３１１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０５⁃０７１２⁃１０ 中文引用格式：刘贝贝，马儒宁，丁军娣． 基于密度的统计合并聚类算法［Ｊ］． 智能系统学报， ２０１５， １０（５）： ７１２⁃７２１． 英文引用格式：ＬＩＵ Ｂｅｉｂｅｉ， ＭＡ Ｒｕｎｉｎｇ， ＤＩＮＧ Ｊｕｎｄｉ． Ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｓｔａｔｉｓｔｉｃａｌ ｍｅｒｇｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（５）： ７１２⁃７２１． Ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｓｔａｔｉｓｔｉｃａｌ ｍｅｒｇｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ＬＩＵ Ｂｅｉｂｅｉ １ ， ＭＡ Ｒｕｎｉｎｇ １ ， ＤＩＮＧ Ｊｕｎｄｉ ２ （１． Ｃｏｌｌｅｇｅ ｏｆ Ｓｃｉｅｎｃｅ， Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ａｅｒｏｎａｕｔｉｃｓ ａｎｄ Ａｓｔｒｏｎａｕｔｉｃｓ， Ｎａｎｊｉｎｇ ２１１１００， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ ２１００９４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ａｂｉｌｉｔｙ ｏｆ ｅｘｉｓｔｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｔｏ ｄｅａｌ ｗｉｔｈ ｎｏｉｓｅ ｉｓ ｐｏｏｒ， ａｎｄ ｔｈｅ ｓｐｅｅｄ ｉｓ ｓｌｏｗ， ｉｎｓｔｅａｄ ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｄｅｎｓｉｔｙ⁃ｂａｓｅｄ ｓｔａｔｉｓｔｉｃａｌ ｍｅｒｇｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ （ＤＳＭＣ）． Ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｔａｋｅｓ ｅａｃｈ ｇｒｏｕｐ ｏｆ ｄａｔａ ｐｏｉｎｔｓ ａｓ ａ ｓｅｔ ｏｆ ｉｎｄｅｐｅｎｄｅｎｔ ｒａｎｄｏｍ ｖａｒｉａｂｌｅｓ， ａｎｄ ｇａｔｈｅｒｓ ｓｔａｔｉｓｔｉｃａｌ ｃｒｉｔｅｒｉａ ｆｒｏｍ ｔｈｅ ｉｎｄｅｐｅｎｄｅｎｔ ｂｏｕｎｄｅｄ ｄｉｆｆｅｒｅｎｃｅ ｉｎｅｑｕａｌｉｔｙ． Ｍｅａｎｗｈｉｌｅ， ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ｄｅｎｓｉｔｙ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｔｈｅ ｄａｔａ ｐｏｉｎｔｓ， ｔｈｅ ＤＳＭＣ ａｌ⁃ ｇｏｒｉｔｈｍ ｔａｋｅｓ ｔｈｅ ｄｅｓｃｅｎｄｉｎｇ ｏｒｄｅｒ ｏｆ ｔｈｅ ｄｅｎｓｉｔｙ ａｓ ｔｈｅ ｍｅｒｇｉｎｇ ｏｒｄｅｒ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｃｏｎｄｅｎｓａｔｉｏｎ， ａｎｄ ｔｈｅｒｅｂｙ ａｃｈｉｅｖｅｓ ｓｔａｔｉｓｔｉｃａｌ ｍｅｒｇｉｎｇ ｏｆ ｄｉｆｆｅｒｅｎｔ ｔｙｐｅｓ ｏｆ ｄａｔａ ｐｏｉｎｔｓ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｗｉｔｈ ｂｏｔｈ ａｒｔｉｆｉｃｉａｌ ｄａｔａｓｅｔｓ ａｎｄ ｒｅａｌ ｄａｔａｓｅｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ＤＳＭＣ ａｌｇｏｒｉｔｈｍ ｃａｎ ｎｏｔ ｏｎｌｙ ｄｅａｌ ｗｉｔｈ ｃｏｎｖｅｘ ｄａｔａ ｓｅｔ， ａｎｄ ａｌｓｏ ｈａｓ ｇｏｏｄ ｃｌｕｓｔｅｒｉｎｇ ｅｆｆｅｃｔｓ ｏｎ ｎｏｎｃｏｎｖｅｘ ｓｈａｐｅｄ， ｏｖｅｒｌａｐｐｅｄ ａｎｄ ｎｏｉｓｙ， ｄａｔａ ｓｅｔｓ． Ｔｈｉｓ ｐｒｏｖｅｓ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ｇｏｏｄ ａｐｐｌｉｃａｂｉｌｉｔｙ ａｎｄ ｖａｌｉｄｉｔｙ． Ｋｅｙｗｏｒｄｓ：ｄａｔａ ｐｏｉｎｔｓ； ｄｅｎｓｉｔｙ； ｒａｎｄｏｍ ｖａｒｉａｂｌｅ； ｍｅｒｇｉｎｇ； ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ； ｎｏｉｓｅ 收稿日期：２０１４⁃１０⁃２１． 网络出版日期：２０１５⁃０９⁃３０． 基金项目：国家自然科学基金资助项目（６１１０３０５８）． 通信作者：丁军娣． Ｅ⁃ｍａｉｌ： ｄｉｎｇｊｕｎｄｉ２０１０＠ ｎｊｕｓｔ．ｅｄｕ．ｃｎ． 聚类［１⁃２］是数据挖掘领域中十分重要的数据分 析技术。 具体来说，聚类就是将给定的数据集划分 成互不相交的非空子集的过程。 由于初始条件和聚 类准则的不唯一性，使得各种各样的聚类算法应运 而生。 根据算法形成方式的不同，可以将其分为 ２ 大类：基于划分的聚类算法和基于层次的聚类算 法［３］ 。 基于划分的聚类算法也可以称为分割聚类 算法，它的主要特点是在对数据集进行分类之前，需 要事先确定聚类个数，然后将数据集划分到确定好 的各类别中。 根据划分过程中数据点类别归属的明 确性，又可将分割聚类分为硬聚类和模糊聚类［ ４ ］ 。 硬聚类中数据点的类别归属是明确的。 每个数 据点对各类别的隶属度取 ０ 或 １，即一个数据点必 须属于某一类别且只能属于该类别。 硬聚类的数学 定义描述如下：设给定的数据集为 Ｘ ＝ ｛ ｘ１ ，ｘ２ ，…， ｘｎ ｝∈Ｒ ｎ×ｄ ，ｘｉ（ｉ ＝ １，２，…，ｎ）表示第 ｉ 个数据点。 预 先确定将 Ｘ 划分为 ｋ 个子集 Ｃ ＝ ｛Ｃ１ ，Ｃ２ ，…，Ｃｋ ｝