一种改进的K-Modes聚类算法

来源:用户上传      作者:

　　摘 要：为了改善传统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算法在正确率、类精度和召回率方面相比传统算法都有较大提升，因而有效提升了聚类效果，且该算法可满足数据并行要求，经过并行化改造后可大幅提升算法执行效率。 　　1 传统K-Modes聚类算法
　　为了使目标函数[F]达到最小值，传统K-Modes聚类算法基本步骤如下：
　　Step1：从数据集中随机选择[k]个对象作为初始聚类中心，其中[k]表示聚类过程中的类簇个数。
　　Step2：应用简单0-1匹配方法计算每个对象与各聚类中心（Modes）之间的相异度，并将每个对象分配到相异度最小的类中。
　　Step3：使用基于频率的方法重新计算各个类聚类中心（Modes）的屬性取值，即为类中出现频率最高的属性值。
　　Step4：重复上述Step2和Step3，直到目标函数[F]达到最小值，即每个数据点不再改变所属聚类中心（Modes）时，算法结束。
　　传统K-Modes算法在每轮迭代过程更新Modes时选取出现频率最高的属性值作为代表，在某属性的属性值分布过于分散或相对均等时，可能会导致类中其它重要属性值缺失。以Mushroom数据集为例，该数据集中的数据点被分为poisonous和edible两大类别，一共有22个属性，每个属性又有多个属性值。分析数据集可以发现，在所有poisonous类别的数据点中，在第一维属性中有1 124个数据点取值为convex，972个数据点取值为flat，出现频率最高的属性值占比为55%;在第二维属性中有860个数据点取值为scaly，744个数据点取值为fibrous，548个数据点取值为smooth，最高频率属性值占比仅为40%，其它属性不再一一列出。从数据中可以发现，该数据集中大部分属性的最高频率属性值占比很低，因而不能很好地表示该属性。数值型属性具有天然几何性质，可以采用加权取平均方法获得一个均值，但分类属性并不具备该几何性质，无法求得几个分类属性值的平均值。传统K-modes算法采用舍去其它低频率属性值的方法，因而造成其它重要属性值缺失。上文提到的poisonous类别的数据点第二维属性由scaly、fibrous、smooth共同组成，3个属性值均占了相当大的比例。传统算法只保留scaly属性值，因此造成fibrous、smooth两个重要属性值丢失，在聚类过程中会导致相异度计算不准确，干扰了对其所属类别的判断，严重影响聚类效果。
　　2 基于新度量公式的改进算法
　　2.1 信息熵理论
　　信息熵是由信息论之父Shannon[20]于1948年提出的，其引用热力学中热熵的概念，将排除冗余信息后的平均信息量定义为信息熵。信息熵代表某种信息出现的概率，表示变量概率空间的不确定性。信息熵越大，信息的无序程度也越高，即不确定性越大。在决策树ID3算法[21]中，信息熵被用来衡量节点划分纯度，以便选择最优的分裂属性。
　　2.3 基于预聚类的中心选取
　　本文提出的MAV-K-Modes算法与传统K-Modes算法都是一个NP难优化问题，在多项式时间内只能得到局部最优解。选取的初始中心点不同，得到的最终结果也不同，当初始中心点选取不适当时，算法聚类效果则会降低。MAV-K-Modes算法使用基于多属性值Modes的相异度度量方法，而传统K-Modes算法只能初始化单属性值聚类中心Modes，从而加大了MAV-K-Modes算法受局部最优的影响。因此，本文提出一种基于预聚类的初始中心点选取方法，用于初始化多属性值聚类中心Modes。
　　通过分析多次聚类结果，可以发现有一些数据点由于初始中心点不同，每次聚类结果所属类别也不相同，而有一些数据点则不受初始中心点影响，每次聚类结果都属于同一类簇。将这些数据点分为稳定点和不稳定点两类，通过分析可以发现，不稳定点一般位于类与类之间的边界地带，容易受局部最优解影响而导致类别判断错误，在生成初始类中心Modes时需要将其剔除。因此，本文提出基于预聚类的初始中心点选取方法的目的是通过首先进行的两次聚类结果，分析找到稳定点，并计算出多属性值类中心Modes的组成作为初始中心点。初始中心生成基本步骤如下：
　　Step1：使用随机初始中心点方法进行两次独立的普通K-Modes聚类，并标注数据点所属类别。
　　Step2：统计两次聚类结果中各类别聚类中心的最高频率属性值，并采用简单匹配方法分析出两次聚类结果的[k]个类别对应关系。
　　Step3：通过类别对应关系分别找到所属[k]个不同类簇的稳定数据点，统计分析出[k]个多属性值聚类中心（Modes）的组成，使用式（6）计算出各类属性权重[？jl]，并将[k]个多属性值的聚类中心（Modes）作为初始聚类中心使用。
　　2.4 改进后聚类算法
　　通过分析可以发现，在数据集MushRoom、Vote、Breast-Cancer和Human上，本文提出的MAV-K-Modes聚类算法在正确率、类精度和召回率上均获得了较大提升，聚类效果优于传统K-Modes算法及其它改进算法。MAV-K-Modes算法由于使用了基于预聚类的中心选取方法，在数据预处理阶段需要一些额外的计算开销，所以总迭代次数（预处理迭代次数+算法迭代次数） 略高于其它算法，但尚在可接受范围内。实验结果证明，本文提出的MAV-K-Modes算法可以有效提升分类属性数据的聚类效果。
　　4 结语
　　针对传统K-Modes算法使用0-1简单匹配作为相异度度量方法弱化了类内相似性，忽略了属性之间的差异性，以及单一属性值的Modes忽视了某一属性可能存在多属性值组合、算法受初始中心点影响很大的问题，本文提出MAV-K-Modes算法，采用基于多属性值Modes的相异度度量方法，以防止聚类过程中的重要属性值丢失，强化了类内属性值之间的距离，并使用信息熵作为属性权值以强化属性间的差异，同时针对改进的相异度量方法提出基于预聚类的初始中心点选取方法，以减少局部最优情况发生。使用UCI数据集进行实验，结果表明，改进后的K-Modes算法相比于传统算法及其它改进算法，在正确率、类精度和召回率方面都有较大提升，有效提升了分类属性数据的聚类效果。但本文提出的MAV-K-Modes算法也存在两个问题：一是对于缺失值的处理不在本文研究范围之内，如何补全缺失值以提高聚类效果还有待研究;二是采用基于预聚类的初始中心选取方法会增加一定计算成本。本文提出的改进算法满足数据并行条件，后续可通过研究并行计算框架，进一步提升算法执行效率。 　　参考文献：
　　[1] HAN J. Data mining：concepts and techniques[M]. San Francisco：Morgan Kaufmann Publishers Inc，2005.
　　[2] JAIN A K， DUBES R C. Algorithms for clustering data[J]. Technometrics，1988，32（2）：227-229.
　　[3] HARTIGAN J A， WONG M A. Algorithm AS 136： a K-means clustering algorithm[J]. Journal of the Royal Statistical Society，1979，28（1）：100-108.
　　[4] HUANG Z. Extensions to the K-means Algorithm for clustering large data sets with categorical values[J]. Data Mining & Knowledge Discovery， 1998， 2（3）：283-304.
　　[5] NG M K， LI M J， HUANG J Z， et al. on the impact of dissimilarity measure in K-modes clustering algorithm[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2007， 29（3）：503-7.
　　[6] GOODALL D W. A new similarity index based on probability[J]. Biometrics， 1966， 22（4）：882-907.
　　[7] 趙亮，刘建辉，张昭昭. 基于贝叶斯距离的K-modes聚类算法[J]. 计算机工程与科学， 2017， 39（1）：188-193.
　　[8] IENCO D， PENSA R G， MEO R. Context-based distance learning for categorical data clustering[C].Advances in Intelligent Data Analysis Viii， International Symposium on Intelligent Data Analysis， Ida 2009， Lyon， France， 2009：83-94.
　　[9] JIA H， CHEUNG Y M. A new distance metric for unsupervised learning of categorical data[C].International Joint Conference on Neural Networks. IEEE， 2014：1893-1899.
　　[10] AHMAD A， DEY L. A K-mean clustering algorithm for mixed numeric and categorical data[J]. Data & Knowledge Engineering， 2007， 63（2）：503-527.
　　[11] HSU C C. Generalizing self-organizing map for categorical data[J]. IEEE Transactions on Neural Networks，2006，17（2）：294-304.
　　[12] HSU C C， CHEN Y C. Mining of mixed data with application to catalog marketing[J]. Expert Systems with Applications， 2007， 32（1）：12-23.
　　[13] 李仁侃， 叶东毅. 属性赋权的K-Modes算法优化[J]. 计算机科学与探索， 2012， 6（1）：90-96.
　　[14] JAYABAL Y， RAMANATHAN C. Mutual information based weighted clustering for mixed attributes[C]. ACM Ikdd Conference on Data Sciences. ACM， 2015：136-137.
　　[15] 石隽锋，白妙青. 一种改进的K-Modes聚类算法[J]. 现代电子技术，2015（4）：39-41.
　　[16] 黄苑华，郝志峰，蔡瑞初，等. 基于相互依存冗余度量的K-modes算法[J]. 小型微型计算机系统，2016， 37（8）：1790-1793.
　　[17] 梁吉业，白亮，曹付元. 基于新的距离度量的K-Modes聚类算法[J]. 计算机研究与发展， 2010， 47（10）：1749-1755.
　　[18] SUN Y， ZHU Q， CHEN Z. An iterative initial-points refinement algorithm for categorical data clustering[J]. Pattern Recognition Letters， 2002， 23（7）：875-884.
　　[19] CAO F， LIANG J， BAI L. A new initialization method for categorical data clustering[J]. Expert Systems with Applications， 2009， 36（7）：10223-10228.
　　[20] SHANNON C E. A mathematical theory of communication[J]. Bell Labs Technical Journal， 1948， 27（4）：379-423.
　　[21] 谢妞妞. 决策树算法综述[J]. 软件导刊， 2015， 14（11）：63-65.
　　（责任编辑：黄 健）
转载注明来源:https://www.xzbu.com/8/view-14904365.htm