第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算法２）ＤＢＳＣＡＮ 算法：共有 ２ 个参数，一个是点的邻 域半径 ｒ，一个是邻域内点的个数阈值 ｍ。 在实验 中，ｍ 一般取 １０ 左右的数，邻域半径 ｒ 则根据数据 集的直径做决定。 ３）ＤＳＭＣ 算法：共有 ２ 个参数，分别是邻域内点 的个数 ｋ 和划分尺度参数 Ｑ。 参数 ｋ 的取值一般根 据数据集中数据点的总个数确定。 一般初始值取 １０ 左右。 对于该方法特有的参数 Ｑ，它控制了算法 对数据集的划分细度，即当 Ｑ 较小时，数据集划分 细度小，聚类个数少；当 Ｑ 较大时，数据集划分细度 大，聚类个数多。 由于参数 Ｑ 是一个特征独立随机 变量的个数，因此其取值范围为正整数，实验中具体 取值根据数据集分类需求进行调整，默认初始值 为 １。 ３．１ 形状不同的人工数据集实验 将 ４ 种聚类算 法 （ Ｋ⁃ｍｅａｎｓ， Ｎｃｕｔｓ， ＤＢＳＣＡＮ， ＤＳＭＣ）分别应用于 ４ 种不同形状的人工数据集上。 它们通过不同类型的高斯分布随机生成，样本点的 个数从左到右第 １ 行分别为 ６００、９００；第 ２ 行分别 为 ６６０（包含 ６０ 个随机噪声点），１ １００（包含 １００ 个 随机噪声点）。 （ａ）Ｋ⁃ｍｅａｎｓ 算法 （ｂ）Ｎｃｕｔｓ 算法 （ｃ）ＤＢＳＣＡＮ 算法 （ｄ）ＤＳＭＣ 算法 图 ４ 算法对不同形状数据集的分类结果比较 Ｆｉｇ．４ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｅｓｕｌｔｓ ｏｆ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄｉｆｆｅｒｅｎｔ ｓｈａｐｅ ｄａｔａ ｓｅｔｓ 对任意形状的数据集都有良好聚类效果的算法 才能称之为好的聚类算法。 由图 ４ 可以看出，Ｋ⁃ ｍｅａｎｓ 和 Ｎｃｕｔｓ 算法并不能很好的聚类非凸数据集， 而 ＤＢＳＣＡＮ 算法（参数 ｍ 和 ｒ 从左到右第 １ 行为 ８， ０．４；７，０．７；第 ２ 行为 １００，４８；１５，０．４）和本文提出的 ＤＳＭＣ 算法（参数 ｋ 和 Ｑ 从左到右第 １ 行为 ６，２００； ８，１；第 ２ 行为 ８，１；８，６）对任意形状数据集的聚类 效果都很令人满意，但对于较为稀疏的数据点的聚 类，ＤＳＭＣ 算法相对更优。 ３．２ 重叠程度不同的人工数据集实验 对数据重叠的鲁棒性也是判断聚类算法好坏的 标准之一。 本节中，通过对重叠程度逐渐增大的 ２ 类不同形状的人工数据集进行实验，比较 ４ 种聚类 算法对数据重叠的鲁棒性。 其中，团状数据集含有 ６００ 个数据点；环状数据集含有 １ ０００ 个数据点。 第 ５ 期 刘贝贝，等：基于密度的统计合并聚类算法 ·７１７·