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

一种改进的K-Modes聚类算法
摘 要:为了改善传统K-Modes聚类算法相异度度量公式弱化了类内相似性,忽略了属性间差异,以及单一属性值的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 基于新度量公式的改进算法
信息熵理论
信息熵是由信息论之父Shannon[20]于1948年提出的,其引用热力学中热熵的概念,将排除冗余信息后的平均信息量定