一种改进的混合属性数据聚类算法

摘要:K-prototypes算法是处理混合属性数据的主要聚类算法,但是存在对初值敏感、参数依赖和易受“噪声”干扰等问题。为了克服以上缺点,该文对K-prototypes算法的初始中心点选择进行了研究与分析,提出了一种基于近邻法的初始中心点选择策略对算法进行改进,算法先利用近邻法获得初始中心点集和k值,然后进行K-prototypes运算,最后加入识别异常数据点的规则。改进后的算法成功解决了传统K-prototypes算法的缺陷,而且具有更好的分类精度和稳定性。经实验证明,改进算法是正确和有效的,明显优于传统的K-prototypes算法。

关键词:聚类分析;初始中心点;K-原型算法;聚类算法;混合属性数据

中图分类号:TP301文献标识码:A 文章编号:1009-3044(2010)11-2713-04

A K-prototypes Algorithm Based on Improved Initial Center Points

CHEN Dan, WANG Zhen-hua

(Faculty of Computer, Guangdong University of Technology, Guangzhou 510006, China)

Abstract: The K-prototypes is the main clustering algorithm that capable of handling mixed numeric and categorical data. However, K-prototypes sensitive to its initial center points, is parameter-dependent and susceptible to noise interference. In order to overcome them, a method is proposed to build initial center points heuristically through the neighbors of objects, and then calculate according the K-prototypes algorithm's procedures. At last, use a rule to optimize the clustering results which able to identify the abnormal points. The proposed algorithm successfully resolved the defects of the traditional algorithm, improves the accuracy of clustering results and stability of the algorithm. Experiments show the proposed algorithm leads to better accurate and scalable, superior to the traditional K-prototypes.

Key words: Clustering analysis; Initial center points; K-prototypes; Clustering algorithm; mixed numeric and categorical data

聚类是数据挖掘中的一种数据分析技术,具有重要意义和很强的挑战性。其基本原理是将数据划分成有意义的簇,相同簇的对象之间具有较高的相似性,而不同簇的对象之间则相似程度较低。这种数据分析技术广泛应用于模式识别、数据分析、图像处理和商业研究等方面。目前已划分出多种聚类算法,常见的聚类算法有基于划分的K-均值,基于密度的DBSCAN算法,基于层次的BRICH算法等。基于划分的聚类算法K-means简单快速,对处理大数据集,但它是基于欧氏距离的划分,难以满足混合属性集聚类的要求。文献[1-2]对K-means算法进行扩展,先后出现了K-modes算法和K-prototypes算法。K-prototypes算法能够有效地处理混合属性数据集聚类的问题,但它的缺点也很明显:1) 对于不同的初始值,可能会导致不同的聚类结果;2) 需要用户给定初始参数,这些参数的选择需要用户具备大量的先验知识才能确定,而用户通常对数据集缺乏先验知识导致所选参数对聚类结果产生很大的影响;3) 算法非常容易受“噪声”干扰,导致聚类精度下降。

近邻法是由Cover和Hart于1968年提出的,是非参数法中最重要的方法之一。它的原理是以全部训练样本作为代表点,计算测试样本与所有样本的距离,并以最近邻样本的类别作为决策,具有原理直观,方法简单等优点。因此,本文提出了一种基于近邻法的初始中心点选择策略对算法进行改进,利用近邻法,启发式地获得初始中心点和k值。最后用一个基于最小距离的规则来识别异常数据点,防止“噪声”的干扰。

改进后的算法能有效地解决传统K-prototypes算法的缺点,基本特征有三点:1) 在选择初始中心点的时候,采用近邻法,有依据的选择初始中心,避免了传统K-prototypes算法对初值选择的盲目性;2)它可以自动的获取k个聚类,解决了K-prototypes算法k值必须预先给定的问题;3)为了避免算法中的“噪声”干扰,采用了一个基于最大距离的启发式规则,将离聚类中心最远的数据点识别为“异常数据点”;经过实验证明,其聚类后的精度和稳定性要优于原算法。

1 K-prototypes算法

K-prototypes算法是由Huang提出的可以对分类属性和数值属性相混合的数据进行聚类的一种有效算法[2]。其基本思想和K-均值算法类似,只是在K-prototypes算法中定义了一个对数值与分类两种属性都计算的相似性度量,以此作为聚类的目标函数,通过不断更新聚类原型来达到优化目标函数,获得最优聚类效果的目的。

算法描述如下:假定待聚类对象集合为X={X1,X2, …,Xn},由n个观测对象组成,属于混合型数据集,且每个观测对象Xi={Xi1,Xi2, …,Xin}有 个属性,由A1A2, …Am来表示,其中A1A2, …Ap为数字属性,Ap+1A p+2,…Am为可分类属性,属性Aj取值域用Dom(Aj)表示,且xij∈Dom(Aj)。对于可分类属性有Dom(Aj)={aj(1),aj(2), …,aj(nj)},其中nj指属性Aj取值的数目。聚类中心用Z表示,相应的,简单记作Za=(za1,za2, …,zam)。

K-prototypes算法的距离函数d由数值型和可分类型两部分组成[3-4]:

d(Xi,Za)=dr(Xi,Za)+rdc(Xi,Za)(1)

其中:γ∈[0,1],为分类属性的权重参数;

dr(Xi,Za)=(xij-zaj)2,由欧式距离度量;

rdc(Xi,Za)= γδ(xij,zaj),

当xij≠zaj时,δ(xij,zaj)=1;

当xij=zaj时,δ(xij,zaj)=0.

K-prototypes算法最小化目标函数[4]:

F(W,Z)=wiad(Xi,Za)(2)

满足:

wia∈[0,1];1≤i≤n;1≤a≤k

wia=1;1≤i≤n

0≤waai≤n;1≤a≤k

综上所述,K-prototypes聚类算法具体步骤如下:

1) 初始化初始聚类数k和聚类中心Z,即从数据集中随机选取k个初始聚类原型;

2) 按照2)式定义的目标函数最小化原则,将数据集中的各个对象划分到离它最近的聚类原型所代表的类中;

3) 对于每个聚类, 重新计算新的聚类原型;

4) 计算每个数据对象对于新的数据原型的差异度,如果离一个数据对象最近的聚类原型不是当前数据对象所属聚类原型,则重新分配这两个聚类的对象;

5) 重复Step 3和Step 4,直到各个聚类中不再有数据对象发生变化。

2对K-prototypes算法的改进

针对上面列出的K-prototypes的不足,该文提出一种基于近邻的初始点选择算法,该算法思想来源于近邻方法[6],可确定初始的中心点集和 值。并在原型算法中加入适当的启发式规则,使算法能够有效地辨识异常数据点,综合这三点改进,算法获得更好的稳定和聚类结果。算法流程图如图1。

2.1 基于近邻方法的初始中心点选择策略

基于近邻方法的初始聚类中心选择策略基本思想为:以全部样本数据作为代表点,计算测试数据点与所有样本之间的距离,如果小于初始阈值,就把该点划分为与测试数据点相同的类,记数变量增1,同时更新最短距离。最后选择邻居数目最多的数据对象作为初始中心点。

样本点 的邻居定义为P=Neigbour(x, θ):

{

判断P是否为x的邻居;

IfDist(P,x)≤θ返回1;

Else 返回0;

}

其中 为两个数据对象的相似度量函数。

算法描述如下:

1) 定义一个初始阀值θ和中心点集Z,Z初始值为空;

2) 从数据集中随机选一个点Q作为起始点;从Q开始递归地按照深度优先方式遍历各点,P=Neigbour(Q, θ) ;如果返回值为1,则判断P属于以Q为中心的聚类,更新阀值θ,并使初始值为0的局部变量m=m+1(用于记录Q的邻居数目);否则退回到前一点继续搜索。遍历数据集中的每一个数据点;

3) 选择邻居数目最多的数据对象作为第一个初始中心点,加入到Z中,初始值为0的全局变量k=k+1;

4) 将原数据集删除中心点及其邻居,如果还有未被聚簇的点,即在这些数据点集中重复执行(2)-(4);

5) 输出初始聚类中心Z和k。

2.2 对异常数据点的识别

聚类算法是将数据集中相似的数据归为一类,因此理论上,一个簇中的所有数据点都应该离簇中心点比较近。然而可能存在一些异常点,它们不属于任何聚簇。为了有效识别这些异常点,在K-prototypes中加入以下启发式规则,在算法进行全局搜索的时候,引导算法避免异常数据点的干扰。

加入的算法启发式规则描述如下:

Min{d(Xi,Za)} ≤ε; 1≤i≤n; 1≤a≤k(3)

其中ε为距离阀值。

算法在最后利用这个启发式规则来检验聚类结果是否满足这个条件,不满足则标记为异常点;如果所有的异常点数目小于阀值ψ,则算法结束;否则,则将所有的异常点归为一类,令k=k+1; 重新迭代,直到所有的异常点数目小于ψ。

2.3 改进后K-prototypes算法步骤

综上所述,改进后的算法描述如下:

输入:待处理数据集S,参数 θ,ε,ψ,γ

输出:k个聚簇

步骤:

Step 1:使用数据预处理技术处理不完整、有噪声的数据集,为后续聚类做准备。

Step 2:使用基于近邻的初始中心点选择方法获得初始中心点集Za=(za1,za2,…,zam)和聚类数k;

Step 3: 按照(2)式的目标函数最小化原则,将数据集中的各个对象划分到离它最近的聚类原型所代表的类中;

Step 4:对于每个聚类,重新计算新的聚类原型Za’;计算每个数据对象 对于新的数据原型Za’的差异度d(x,Za’),如果离一个数据对象最近的聚类原型不是当前数据对象所属聚类原型,则重新分配这两个聚类的对象;

Step 5:重复Step 3和step 4,如果各个聚类无数据对象发生变化,转至Step6;

Step 6:利用启发式规则(3)来检验聚类结果,标记异常数据点,如果异常数据点数小于ψ,算法结束;否则将这些异常数据点归为一类,并使k=k+1,转至Step3,反复迭代,直至使异常数据点控制在较小范围内,算法结束。

3 实验结果与分析

为了验证所改进后的K-prototypes算法的有效性和可行性, 实验过程分别采用随机选择初始点的K-prototypes算法和改进后的K-prototypes算法对给定数据集进行测试,并比较分析聚类结果。

系统配置为:Intel 酷睿2 双核 CPU,1G内存,Windows XP,应用Matlab6.5平台进行实验仿真。

3.1 实验1:人造数据实验

为了显示的直观性,我们构造的数据样本共有300个样本,可以划分为3类,分别为A类、B类和C类。每个样本具有2个特征:一个数值型和一个分类型。使用随机选取十组初始聚类中心所得到的最坏与最好结果与优化选取初始聚类中心的算法所得到的结果进行比较。如图2所示。

实验1参数设置:θ=0.20,ε=4.5,ψ=50;γ取0.5。

从图4可以直观地看出,传统K-prototypes算法对于不同的初始聚类中心会得到差别很大的聚类结果;这说明初始聚类中心的选择对算法的分类性能有很大的影响;图5是采用改进后的K-prototypes算法,相比之下,改进后的K-prototypes算法具有更好的分类效果。

3.2 实验2:标准数据库数据实验

实验2采用UCI机器学习库[7]中的真实数据集Voting和Cleve作为聚类对象,其中Voting为分类型数据集,而Cleve为混合类型的数据集,分别用原始K-prototypes算法和改进后的K-prototypes算法对其进行聚类分析,数据集描述如表1所示。

上述数据集Voting、Cleve都包含多个属性,不能直观地显示其聚类结果,故从正确识别率和稳定性两个方面进行分析。

3.2.1 评价标准

为了将原始数据的分类特征与算法得到的聚类结果作比较,本文采用聚类结果正确率作为聚类实验结果的评价标准。

评价聚类效果的指标如下:

E=(n/N) ×100%

其中:n为正确分类的对象数,N为总对象数。E∈[0,1],为正确识别率,其值越大,表明聚类结果越精确;反之,聚类结果误差越大。

4.2.2 聚类性能分析

实验过程中,两个算法的参数设置分别如下:在改进后的K-prototypes算法中,对于Voting,Cleve两个数据集,分别设置阈值θ=0.15,ε=4.5,ψ=70;θ=0.20,ε=4.8,ψ=50,…,每组阈值分别运行5次;γ分别取1,0.7。

将传统算法运行10次,通过打乱数据集的各个数据位置,反复仿真得出以下聚类结果。

表2是对两组实验数据的聚类精度值的对表,从表2可以直观地看出:采用改进后K-prototypes算法进行聚类,得到的聚类精度都在90%以上,比原始K-prototypes算法聚类精度高很多。而采用原始K-prototypes算法聚类得到的结果有时高,有时低,波动比较大,说明原始K-prototypes算法对初始值很敏感,对于不同输入顺序的初始值而得到不同的聚类精度;相比,采用改进后的K-prototypes算法,每组实验的聚类结果波动很小,聚类精度高。由此可证明,改进后的K-prototypes算法成功地解决了原始算法对初始值非常敏感,参数必须预先设定和对易受“噪声” 影响等缺点。因此,实验结果表明:本文提出的基于近邻法的K-prototypes算法在分类精度和稳定性两个方面都是十分有效的。

4 结论

该文提出了一种改进的K-prototypes混合属性数据聚类算法,通过近邻法获取初始中心点集和初始聚类数目,避免了初始中心点选择的盲目性和对聚类数目k值的依赖性;同时加入启发式规则,防止了“噪声点”的干扰。通过实验可以看出该算法成功解决了原K-prototypes算法对初始敏感的缺点,并且自动获取初始中心点集和初始聚类。通过对聚类结果的精度分析和稳定性分析,可看出改进后的算法优于传统的K-prototypes聚类算法。

参考文献:

[1] Ralambondrainy H. A Conceptual Version of the k-means Algorithm[J].Pattern recognition Letters,1995(16):1147-1157.

[2] Huang Zhexue. Extension to the k-means algorithm for clustering large data sets with categorical values[J]. Data Mining and Knowledge Discovery,1998(2):283-304.

[3] 陈宁, 陈安等. 数值型和分类型混合数据的模糊K-prototypes聚类算法[J].软件学报,2001,12(8):1107-1119.

[4] 尹波,何松华.基于PSO的模糊K-prototypes聚类[J].计算机工程与设计,2008(11):2283-2285.

[5] 吴孟书,吴喜之.一种改进的K-prototypes聚类算法[J].统计与决策,2008(5).

[6] Dasarathy B V. Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques[M].Los Alamitos, CA: IEEE Computer Society Press,1991.

[7] Blake C,Keogn E,Merz C.UCI repository of machine learning database,1998[EB/OL].www.ics.uci.edu/~mlearn/ML-Respository. html.