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

一种改进的混合属性数据聚类算法
AK-prototypesAlgorithmBasedonImprovedInitial
CenterPoints
CHENDan,WANGZhen-hua
(FacultyofComputer,Gu
算法描述如下：假定待聚类对象集合为X={X1,X2，…,Xn},
由n个观测对象组成,属于混合型数据集,且每个观测对象
Xi={Xi1,Xi2,…,Xin}有个属性，由A1A2,•••Am来表示，其中
A1A2,•••Ap为数字属性,Ap+1Ap+2,••・Am为可分类属性,属性Aj取值域用Dom(Aj)表示，且xijGDom(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)
其中：Y€[0,1],为分类属性的权重参数；
dr(Xi,Za)=(xij-zaj)2,由欧式距离度量;
rdc(Xi,Za尸丫5(xij,zaj),
当xij*zaj时，8(xij,zaj)=1;
当xij=zaj时，8(xij,zaj)=0.
K-prototypes算法最小化目标函数[4]:
F(W,Z)=wiad(Xi,Za)(2)
满足:
wiaG[0,1]；1<i<n;1<a<k
wia=1;1<i<n
0<waai<n;1<a<k
综上所述,K-prototypes聚类算法具体步骤如下:
初始化初始聚类数k和聚类中心Z,即从数据集中随机选
取k个初始聚类原型;
按照2)式定义的目标函数最小化原则,将数据集中的各
个对象划分到离它最近的聚类原型所代表的类中;
对于每个聚类,重新计算新的聚类原型;
计算每个数据对象对于新的数据原型的差异度,如果离
一个数据对象最近的聚类原型不是当前数据对象所属聚类原型,
则重新分配这两个聚类的对象;
重复Step3和Step4,直到各个聚类中不再有数据对象
发生变化。
对K-prototypes算法的改进
针对上面列出的K-prototypes的不足,该文提出一种基于
近邻的初始点选择算法,该算法思想来源于近邻方法[6],可确定
初始的中心点集和值。并在原型算法中加入适当的启发式规则
使算法能够有效地辨识异常数据点,综合这三点改进,算法获得
更好的稳定和聚类结果。算法流程图如图1。
基于近邻方法的初始中心点选择策略
基于近邻方法的初始聚类中心选择策略基本思想为:以全部
样本数据作为代表点,计算测试数据点与所有样本之间的距离,
如果小于初始阈值,就把该点划分为与测试数据点相同的类,记
数变量增1,同时更新最短距离。最后选择邻居数目最多的数据
对象作为初始中心点。
样本点的邻居定义为P=Neigbour(x,6):
{
判断P是否为x的邻居;
IfDist(P,x)<6返回1;
Else返回0;
}
其中为两个数据对象的相似度量函数。
算法描述如下:
1)定义一个初始阀值e和中心点集z,z初始值为空；
2)从数据集中随机选一个点Q作为起始点；从。开始递归地
按照深度优先方式遍历各点，P=Neigbour(Q,6);如果返回值为1,则判断P属于以Q为中心的聚类，更新阀值6，并使初始值为0的局部变量m=m+1用于记录Q的邻居数目);否则退回到前一点继续搜索。遍历数据集中的每一个数据点;
选择邻居数目最多的数据对象作为第一个初始中心点,加入到Z中，初始值为0的全局变量k=k+1;
将原数据集删除中心点及其邻居,如果还有未被聚簇的
点,即在这些数据点集中重复执行(2)-(4);
输出初始聚类中心z和k。
对异常数据点的识别
聚类算法是将数据集中相似的数据归为一类,因此理论上,
一个簇中的所有数据点都应该离簇中心点比较近。然而可能存在一些异常点,它们不属于任何聚簇。为了有效识别这些异常点,在K-prototypes中加入以下启发式规则,在算法进行全局搜索的时候,引导算法避免异常数据点的干扰。
加入的算法启发式规则描述如下:
Min{d(Xi,Za)}<£;1<i<n;1<a<k(3)
其中£为距离阀值。
算法在最后利用这个启发式规则来检验聚类结果是否满足
这个条件,不满足则标记为异常点;如果所有的异常点数目小于
阀值小,则算法结束；否则，则将所有的异常点归为一类,令k=k+1;重新迭代，直到所有的异常点数目小于小。
改进后K-prototypes算法步骤
综上所述,改