第11期 王玲等：一种基于密度的模糊自适应聚类算法 ·1563· 同时，DBSCAN算法得到的聚类结果也不相同.例 Accuracy的计算公式如下所示： 如Iis数据集，当min Pts为l0,Eps为0.1时得到 k 的聚类数为5；min Pts为l0,Eps为0.4时得到的聚 am Accuracy =】 (12) 类数为7：min Pts为l0,Eps为0.8时才能得到正确 n 的聚类数.对于其他数据集也有类似的结论，即稍 式中a.表示第m个聚类簇中算法聚类结果和实际 微改动DBSCAN的任意一个参数都会导致聚类结 聚类相一致的样本个数 果发生变化.而且对于不同的数据集，DBSCAN算 从表3中可以看出DFAC算法聚类正确率要高 法的参数取值范围也是不同的，这就导致在未知聚 于FCM和DBSCAN算法，而且DFAC算法能够自适 类数的情况下很难确定参数的取值.例如，对于Is 应地得到每个数据集正确的聚类数.其中对于 数据集min Pts的取值范围是D,l0],Eps的取值范 Wine、Seed和Breast Cancer数据集，DFAC算法聚类 围是D.1,l]:Wime数据集min Pts取值范围是l, 正确率均不低于90%，对Dataset_.3_2和Dataset_5_2 10],Eps的取值范围是0,20]：Seed数据集min 的聚类正确率均为100%，虽然DFAC算法对Iis Pts的取值范围是1,20]，Eps取值范围是D,2],这 的聚类正确率稍低，但仍然高于DBSCAN和FCM 就增加了参数取值的难度.DFAC算法则无需设定 算法 任何参数，而且根据模糊聚类有效性指标可以确定 表3DFAC和DBSCAN算法对各个数据集聚类的平均正确率 最佳的聚类结果，所以DFAC算法具有更好的自适 Table 3 Average accuracy of DFAC and DBSCAN algorithms to each 应性. dataset % 表2 数据集 参数对DBSCAN算法的影响 算法 Breast Table 2 Influence of parameters on DBSCAN algorithm Iris Wine Seed Dataset 3 2 Dataset 5_2 Cancer 数据集 min Pts Eps 聚类数 DBSCAN67.372.366.748.8 66.7 45.7 10 0.1 5 FCM 87.159.090.094.7 91.3 90.5 Iris 10 0.4 4 DFAC89.394.991.095.6 100 100 10 0.8 3 10 10 5 图1和图2分别给出DFAC算法对Dataset_3_2 Wine 10 14 2 和Dataset_.5_2的聚类效果.对各个聚类中的数据 10 20 3 样本分别用不同颜色进行标记，可以清晰地看到 20 1 4 DFAC算法对这两个二维数据集的聚类结果与原始 Seed 20 1.6 2 数据集的聚类完全吻合.图1中每个圆圈表示一个 20 1.5 3 数据样本.从图中每个数据样本的分布位置可以明 20 0.1 6 确地判断该数据集一共有3个聚类簇.图中黄色、 Breast Cancer 20 0.5 5 绿色和紫色点分别表示聚类结果中第一、第二和第 20 1 2 三个聚类簇的样本.可以看出本属于同一个聚类簇 20 0.1 的每个样本聚类结果均正确.图2也可得到类似的 Dataset_3_2 20 0.3 2 结论，黄色、绿色、紫色、黑色和蓝色共形成了5个聚 20 1 类，同样保证了样本聚类结果的正确性. 10 0.1 22 为了进一步验证DFAC对多类数据集的聚类有 Dataset_5_2 10 0.5 效性，这里使用如图3所示的一个二维数据集作为 10 1 5 验证数据集，图中每个黄色点代表一个数据样本. 从图中可以看出该数据集共有20个聚类簇.在选 3.2聚类效果测试 择聚类中心时，根据式(1)得到的不同聚类数对应 为了验证DFAC算法的聚类有效性，在多个数 的模糊聚类有效性指标值如图4所示.从图中可以 据集上进行聚类效果测试并与DBSCAN和FCM 看出当聚类数小于5时，模糊聚类有效性指标上升 (fuzzy c-means),算法的聚类效果进行对比.表3中 趋势明显，当聚类数在5~20之间时糊聚类有效性 给出了DFAC、FCM和DBSCAN算法对各个数据集 指标上升趋势缓慢，聚类数大于20以后模糊聚类有 进行多次聚类的平均正确率.其中算法聚类正确率 效性指标逐渐下降且趋于平稳，因此得到聚类数为第 11 期 王 玲等: 一种基于密度的模糊自适应聚类算法 同时，DBSCAN 算法得到的聚类结果也不相同． 例 如 Iris 数据集，当 min Pts 为 10，Eps 为 0. 1 时得到 的聚类数为 5; min Pts 为 10，Eps 为 0. 4 时得到的聚 类数为 7; min Pts 为 10，Eps 为 0. 8 时才能得到正确 的聚类数． 对于其他数据集也有类似的结论，即稍 微改动 DBSCAN 的任意一个参数都会导致聚类结 果发生变化． 而且对于不同的数据集，DBSCAN 算 法的参数取值范围也是不同的，这就导致在未知聚 类数的情况下很难确定参数的取值． 例如，对于 Iris 数据集 min Pts 的取值范围是［1，10］，Eps 的取值范 围是［0. 1，1］; Wine 数据集 min Pts 取值范围是［1， 10］，Eps 的取值范围是［10，20］; Seed 数据集 min Pts 的取值范围是［1，20］，Eps 取值范围是［1，2］，这 就增加了参数取值的难度． DFAC 算法则无需设定 任何参数，而且根据模糊聚类有效性指标可以确定 最佳的聚类结果，所以 DFAC 算法具有更好的自适 应性． 表 2 参数对 DBSCAN 算法的影响 Table 2 Influence of parameters on DBSCAN algorithm 数据集 min Pts Eps 聚类数 10 0. 1 5 Iris 10 0. 4 4 10 0. 8 3 10 10 5 Wine 10 14 2 10 20 3 20 1 4 Seed 20 1. 6 2 20 1. 5 3 20 0. 1 6 Breast Cancer 20 0. 5 5 20 1 2 20 0. 1 1 Dataset_3_2 20 0. 3 2 20 1 3 10 0. 1 22 Dataset_5_2 10 0. 5 7 10 1 5 3. 2 聚类效果测试 为了验证 DFAC 算法的聚类有效性，在多个数 据集上进行聚类效果测试并与 DBSCAN 和 FCM ( fuzzy c-means) 算法的聚类效果进行对比． 表 3 中 给出了 DFAC、FCM 和 DBSCAN 算法对各个数据集 进行多次聚类的平均正确率． 其中算法聚类正确率 Accuracy［11］的计算公式如下所示: Accuracy = ∑ k m = 1 am n ． ( 12) 式中 am 表示第 m 个聚类簇中算法聚类结果和实际 聚类相一致的样本个数． 从表 3 中可以看出 DFAC 算法聚类正确率要高 于 FCM 和 DBSCAN 算法，而且 DFAC 算法能够自适 应地得到每个数据集正确的聚类数． 其 中 对 于 Wine、Seed 和 Breast Cancer 数据集，DFAC 算法聚类 正确率均不低于 90%，对 Dataset_3_2 和 Dataset_5_2 的聚类正确率均为 100% ，虽然 DFAC 算法对 Iris 的聚类正确率稍低，但仍然高于 DBSCAN 和 FCM 算法． 表 3 DFAC 和 DBSCAN 算法对各个数据集聚类的平均正确率 Table 3 Average accuracy of DFAC and DBSCAN algorithms to each dataset % 算法 数据集 Iris Wine Seed Breast Cancer Dataset_3_2 Dataset_5_2 DBSCAN 67. 3 72. 3 66. 7 48. 8 66. 7 45. 7 FCM 87. 1 59. 0 90. 0 94. 7 91. 3 90. 5 DFAC 89. 3 94. 9 91. 0 95. 6 100 100 图 1 和图 2 分别给出 DFAC 算法对 Dataset_3_2 和 Dataset_5_2 的聚类效果． 对各个聚类中的数据 样本分别用不同颜色进行标记，可以清晰地看到 DFAC 算法对这两个二维数据集的聚类结果与原始 数据集的聚类完全吻合． 图 1 中每个圆圈表示一个 数据样本． 从图中每个数据样本的分布位置可以明 确地判断该数据集一共有 3 个聚类簇． 图中黄色、 绿色和紫色点分别表示聚类结果中第一、第二和第 三个聚类簇的样本． 可以看出本属于同一个聚类簇 的每个样本聚类结果均正确． 图 2 也可得到类似的 结论，黄色、绿色、紫色、黑色和蓝色共形成了 5 个聚 类，同样保证了样本聚类结果的正确性． 为了进一步验证 DFAC 对多类数据集的聚类有 效性，这里使用如图 3 所示的一个二维数据集作为 验证数据集，图中每个黄色点代表一个数据样本． 从图中可以看出该数据集共有 20 个聚类簇． 在选 择聚类中心时，根据式( 1) 得到的不同聚类数对应 的模糊聚类有效性指标值如图 4 所示． 从图中可以 看出当聚类数小于 5 时，模糊聚类有效性指标上升 趋势明显，当聚类数在 5 ～ 20 之间时糊聚类有效性 指标上升趋势缓慢，聚类数大于 20 以后模糊聚类有 效性指标逐渐下降且趋于平稳，因此得到聚类数为 · 3651 ·