武森等：分类属性数据聚类算法HABOS ·1023· 次取得较好的准确率.本文认为该结果较好主要归功 情况.对于Balloon数据集，当聚类数上限参数值小于 于HABOS算法的聚类过程，而CVISFD指标对该数据 等于12时，算法均取得了最好准确率100.0%，当聚类 集的聚类有着较小的贡献，所以CVISFD指标并不是 数上限参数值大于12时，准确率有了较大的波动，但 针对所有数据集都有绝对的指导意义. 由于该数据集对象个数仅为20，若将对象聚为十几个 由于算法使用多类合并规则，因此会有个别类个 类，则丧失了聚类的意义，因此本文认为该波动在实际 数不存在的情况，文中以”表示.对于Soybean和 应用中可以利用人的经验有效地避免 Balloon数据集聚类数上限范围以外非实验内容的情 综上所述，在人为理性的参数值设定下，不同的聚 况，表中以“”表示（下同）： 类数上限参数值对HABOS算法的聚类结果准确率影 从表3中可以看出，对于Voting数据集，聚类数上 响不大，该算法在大部分情况下能够得到聚类效果最 限参数nc的取值变化对聚类结果的影响很小，聚类 好的层次结果.HABOS算法虽然需要人为地输入 结果的准确率没有变化，均选择了效果最好的层次结 nc参数值，但是集合稀疏差异度上限参数对聚类结 果.对于Soybean数据集，当聚类数上限参数取值为2 果的敏感性要远远大于参数ncmm对结果的影响，因此 或3时，将实际最佳聚类个数4排除在外，因此聚类效 HABOS算法对参数ncm较不敏感. 果不佳.但是，当聚类数上限参数值大于等于4时，算 表4为HABOS算法、CABOSFV_C算法与经典K- 法均选择了聚类效果最好的层次，即聚类个数为4的 modes算法基于三个数据集的聚类结果准确率比较. 表3类个数上限参数对聚类结果准确率的影响 表4聚类结果准确率比较 Table 3 Influence of the upper limit parameter of cluster number on the Table 4 Comparison of the accuracy of clustering results accuracy of clustering results Voting数据集 Soybean数据集 Balloon数据集 HABOS CABOSFV_C K-modes 数据集 正确率/% 正确率/% 正确率/% 平均准确率/% 平均准确率/% 平均准确率/% 57.4 100.0 Voting 93.80 81.10 86.60 78.7 100.0 Soybean 100 89.30 80.10 100.0 100.0 Balloon 100 64.60 69.30 5 100.0 100.0 93.8 100.0 100.0 4 结论 7 93.8 100.0 100.0 本文针对CABOSFV._C算法对集合稀疏差异度上 8 93.8 100.0 100.0 限参数具有一定依赖性，从聚结型层次聚类思想的角 9 93.8 100.0 100.0 度出发，结合CVISFD内部评价指标，提出改进算法 10 93.8 100.0 100.0 HABOS.算法首先通过计算任意两个类合并后的集合 11 93.8 100.0 100.0 稀疏差异度，根据多类合并规则将得到集合稀疏差异 12 度最小的类进行合并，然后继续根据多类合并规则将 93.8 100.0 100.0 取得最小集合稀疏差异度的类进行合并，直至所有类 13 93.8 100.0 45.0 被合并成一个类或不能再合并为止.算法还需人为地 14 93.8 100.0 45.0 给定聚类数上限参数ncax,对于聚类个数小于ncmx的 15 93.8 100.0 45.0 层次结果，利用CVISFD评价方法进行启发式度量，自 16 93.8 100.0 动地选择聚类效果最优的结果.该算法可以有效地消 17 93.8 100.0 除集合稀疏差异度上限对聚类结果的影响，从全局角 18 93.8 100.0 度选择最合适的类进行合并 19 93.8 100.0 真实数据实验结果表明：新的内部评价指标 20 93.8 100.0 CVISFD能够较好地进行启发式度量，选择HABOS算 23 法在聚类数上限约束下所能达到的最好聚类结果： 93.8 24 938 HABOS算法的聚类结果对聚类数上限参数nc的敏 感性较低，该参数的选取对聚类结果的影响较小： 25 93.8 HABOS算法在三个数据集上的聚类结果准确率高于 27 93.8 CABOSFV._C算法和经典K-modes算法，且HABOS算 28 93.8 法聚类结果的稳定性也高于其他对比算法.武 森等: 分类属性数据聚类算法 HABOS 次取得较好的准确率． 本文认为该结果较好主要归功 于 HABOS 算法的聚类过程，而 CVISFD 指标对该数据 集的聚类有着较小的贡献，所以 CVISFD 指标并不是 针对所有数据集都有绝对的指导意义． 由于算法使用多类合并规则，因此会有个别类个 数不存在的情况，文中以“—”表示． 对于 Soybean 和 Balloon 数据集聚类数上限范围以外非实验内容的情 况，表中以“/”表示( 下同) ． 从表 3 中可以看出，对于 Voting 数据集，聚类数上 限参数 ncmax的取值变化对聚类结果的影响很小，聚类 结果的准确率没有变化，均选择了效果最好的层次结 果． 对于 Soybean 数据集，当聚类数上限参数取值为 2 或 3 时，将实际最佳聚类个数 4 排除在外，因此聚类效 果不佳． 但是，当聚类数上限参数值大于等于 4 时，算 法均选择了聚类效果最好的层次，即聚类个数为4的 表 3 类个数上限参数对聚类结果准确率的影响 Table 3 Influence of the upper limit parameter of cluster number on the accuracy of clustering results ncmax Voting 数据集 正确率/% Soybean 数据集 正确率/% Balloon 数据集 正确率/% 2 — 57. 4 100. 0 3 — 78. 7 100. 0 4 — 100. 0 100. 0 5 — 100. 0 100. 0 6 93. 8 100. 0 100. 0 7 93. 8 100. 0 100. 0 8 93. 8 100. 0 100. 0 9 93. 8 100. 0 100. 0 10 93. 8 100. 0 100. 0 11 93. 8 100. 0 100. 0 12 93. 8 100. 0 100. 0 13 93. 8 100. 0 45. 0 14 93. 8 100. 0 45. 0 15 93. 8 100. 0 45. 0 16 93. 8 100. 0 ∕ 17 93. 8 100. 0 ∕ 18 93. 8 100. 0 ∕ 19 93. 8 100. 0 ∕ 20 93. 8 100. 0 ∕ 23 93. 8 ∕ ∕ 24 93. 8 ∕ ∕ 25 93. 8 ∕ ∕ 27 93. 8 ∕ ∕ 28 93. 8 ∕ ∕ 情况． 对于 Balloon 数据集，当聚类数上限参数值小于 等于12 时，算法均取得了最好准确率100. 0% ，当聚类 数上限参数值大于 12 时，准确率有了较大的波动，但 由于该数据集对象个数仅为 20，若将对象聚为十几个 类，则丧失了聚类的意义，因此本文认为该波动在实际 应用中可以利用人的经验有效地避免． 综上所述，在人为理性的参数值设定下，不同的聚 类数上限参数值对 HABOS 算法的聚类结果准确率影 响不大，该算法在大部分情况下能够得到聚类效果最 好的 层 次 结 果． HABOS 算法虽然需要人为地输入 ncmax参数值，但是集合稀疏差异度上限参数对聚类结 果的敏感性要远远大于参数 ncmax对结果的影响，因此 HABOS 算法对参数 ncmax较不敏感． 表 4 为 HABOS 算法、CABOSFV_C 算法与经典 K￾modes 算法基于三个数据集的聚类结果准确率比较． 表 4 聚类结果准确率比较 Table 4 Comparison of the accuracy of clustering results 数据集 HABOS 平均准确率/% CABOSFV_C 平均准确率/% K--modes 平均准确率/% Voting 93. 80 81. 10 86. 60 Soybean 100 89. 30 80. 10 Balloon 100 64. 60 69. 30 4 结论 本文针对 CABOSFV_C 算法对集合稀疏差异度上 限参数具有一定依赖性，从聚结型层次聚类思想的角 度出发，结合 CVISFD 内部评价指标，提出改进算法 HABOS． 算法首先通过计算任意两个类合并后的集合 稀疏差异度，根据多类合并规则将得到集合稀疏差异 度最小的类进行合并，然后继续根据多类合并规则将 取得最小集合稀疏差异度的类进行合并，直至所有类 被合并成一个类或不能再合并为止． 算法还需人为地 给定聚类数上限参数 ncmax，对于聚类个数小于 ncmax的 层次结果，利用 CVISFD 评价方法进行启发式度量，自 动地选择聚类效果最优的结果． 该算法可以有效地消 除集合稀疏差异度上限对聚类结果的影响，从全局角 度选择最合适的类进行合并． 真实数据实验结果表明: 新 的 内 部 评 价 指 标 CVISFD 能够较好地进行启发式度量，选择 HABOS 算 法在聚类数上限约束下所能达到的最好聚类结果; HABOS 算法的聚类结果对聚类数上限参数 ncmax的敏 感性较 低，该 参 数 的 选 取 对 聚 类 结 果 的 影 响 较 小; HABOS 算法在三个数据集上的聚类结果准确率高于 CABOSFV_C 算法和经典 K-modes 算法，且 HABOS 算 法聚类结果的稳定性也高于其他对比算法． · 3201 ·