贾彬 梁毅 苏航

摘 要：为了改善传统K-Modes聚类算法相异度度量公式弱化了类内相似性，忽略了属性间差异，以及单一属性值的Modes忽视了某一属性可能存在多属性值组合，且算法受初始中心点影响很大的缺点，基于多属性值Modes的相异度度量方法提出MAV-K-Modes算法，并采用一种基于预聚类的初始中心选取方法。使用UCI数据集进行实验，结果表明，MAV-K-Modes算法相比于传统K-Modes算法，其正确率、类精度和召回率都有明显提升，且MAV-K-Modes算法适合于并行化改造。

关键词：聚类算法;相异度度量;初始中心点;多属性值Modes;K-Modes

DOI：10. 11907/rjdk. 182651

中图分类号：TP312

文献标识码：A文章编号：1672-7800（2019）006-0060-05

Abstract：The dissimilarity measure method of traditional K-Modes clustering algorithm suffers from some shortcomings， such as weakening the similarity within a class， ignoring the difference between attributes， and the Modes with single attribute value neglects that a property may have multiple attribute value combinations， and the algorithm is greatly affected by the initial center points. A MAV-K-Modes algorithm is proposed based on the dissimilarity measure method of multi-attribute value Modes， and an initial center selection method based on pre-clustering is adopted. The results of experiments using UCI datasets show that the MAV-K-Modes algorithm has a significant improvement in accuracy rate， precision rate and recall rate compared with the traditional K-Modes algorithms， and the MAV-K-Modes algorithm is suitable for parallel transformation.

Key Words： clustering algorithm; dissimilarity measure; initial center points; multi-attribute value Modes; K-Modes

0 引言

近年来随着互联网的快速发展，信息量以前所未有的速度迅猛增长。聚类算法[1]作为一种有效的数据挖掘工具，其应用十分广泛，目前已成为国内外学者的研究热点。聚类算法的核心是将一个数据集划分成几个子集，并使同一子集中的元素尽可能相似，且不同子集中的元素尽可能相异。聚类算法用来训练的样本标记信息是未知的，因而也被称作无监督学习方法[2]，需要通过学习探究数据内在性质及规律。

基于划分的K-Means算法[3]是一种用于处理大数据集的有效且应用广泛的聚类算法，但该算法只能处理数值型数据，而大多数实际数据集不仅包括数值型数据，还包括大量分类属性数据（Categorical Data）。Huang[4]提出一种K-Modes算法，对K-Means算法进行拓展，使其可以处理分类属性数据。算法采用简单0-1匹配机制度量两数据点在某一属性下的距离，目标函数定义为所有数据点与所属聚类中心Modes相异度量总和。该相异度度量方法弱化了类中相似性，也忽略了属性之间权重的差异性。传统算法在聚类过程中使用基于频度的方法修正聚类中心Modes在每个属性中的取值，但每个属性只保留最高频率属性值的聚类中心Modes，会造成其它较高频率的重要属性值丢失，导致准确率降低。K-Modes算法受初始中心点选取的影响也很大，容易使目标函数陷入局部最优，导致整体聚类效果下降。

针对传统K-Modes算法的不足，很多学者都提出了改进方法。针对相异度度量公式问题，Ng[5]、Goodall[6]、赵亮[7]、DinoIenco[8]提出新的类内属性距离計算公式，但只强化了类内相似性，而未考虑属性间的差异性;HongJia[9]、Ahamad[10]、Hsu[11-12]、李仁侃[13]、Jayabal[14]提出的方法只考虑了不同属性的权重计算;石隽锋[15]定义一种基于期望熵的新目标函数;黄苑华[16]提出基于结构相似性的方法，但计算代价较大，且不易于进行数据并行处理;梁吉业、白亮[17]在提出基于粗糙集的相异度量方法的同时，也考虑了类内相似性与属性权重的差异，但当属性具有很多值时，粗糙隶属度的计算量很大。针对初始选点问题，Huang[4]提出将最频繁的属性值均匀分配到初始Modes中;Sun[18]将Bradley的迭代初始点优化算法应用到算法中;Cao[19]结合距离和密度提出一种初始中心选择方法。但这些选点方法只适用于单属性值Modes的初始化。

由于以上改进方法均未考虑聚类中心Modes每个属性只能取单属性值的问题，且K-Modes算法受初始中心点选取影响很大，容易陷入局部最优，导致整体聚类效果下降，因此本文提出一种MAV-K-Modes算法。使用基于多属性值Modes的相异度度量方法，可有效防止重要属性值丢失，并强化同一属性内属性值的相似性，突出不同属性的差异性，使相异度度量更加准确。新的多属性值Modes相异度度量方法使用信息熵[20]计算属性权重，以强化属性间的差异，而新的类内属性距离计算公式强化了类内相似性。同时，针对多属性值聚类中心Modes提出一种基于预聚类的初始选点方法，通过统计分析预聚类结果，得到各类的多属性值聚类中心Modes作为初始中心点，以减少局部最优情况的发生。实验结果表明，MAV-K-Modes算法在正确率、类精度和召回率方面相比传统算法都有较大提升，因而有效提升了聚类效果，且该算法可满足数据并行要求，经过并行化改造后可大幅提升算法执行效率。