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

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

倪丹

广州市城市更新规划研究院广州510000

摘要：本文在将数值型数据标准化的基础上，将分类数据细分为二元数据和类型数据，并用相异度系数距离计算分类数据之间的距离，并且赋予二元和类型数据相应的权重，来改进k-prototypes聚类算法，使该算法满足不同要求的混合属性数据聚类，最后通过C#语言，在ArcEngine2010版本上实现。

关键词：K-prototypes算法；混合属性；类型数据；相异度系数；加权属性

1引言

聚类分析是人类认识客观事物最朴素、最常用的手段之一，也是人类认识自然最基本、最有效的技能之一[1]。从简单的“物以类聚，人以群分”到用数学工具去提取相关联的信息，聚类分析很快的发展到现代的一种非常重要的数据挖掘技术，而且被广泛应用于模式识别、空间数据分析、图像处理和市场营销等研究领域，有效的改变了现代“数据丰富，信息贫乏”的困境[2-3]。

2K-prototypes算法的改进

对于K-prototypes算法中数值型数据进行标准化处理后依然选用欧几里平方来计算距离相异度：

d1(Xi，Vl)=|Xij－Vlj|2（9）

对于二元和类型属性数据则采用相异度系数的方法计算：

d2(Xi，Vl)=J反（P，Q）•（10）

d3(Xi，Vl)=L反（P，Q）•（11）

然后引入参数β和γ来控制二元属性和类型属性在聚类过程中的权重。令X={X1，X2，X3，…，Xn}表示具有n个样本的数据集，其中Xi=［xi1，xi2，…，xip，xi(p+1)，…，xim，xim+1，…，，xiH］表示第i个样本的H个属性值，其中标号为1至p下标的属性为数值型数据属性，p+1到m下标的属性为二元数据属性，m+1到H下标的属性为类型数据属性。令数据集的初始聚类数为k，对应模的集合为V={Vl，V2，…，Vk}，聚类过程中迭代聚类集为C={C1，C2，…，Ck}，Ci=［Ci1，Ci2，…，Cik］。K-prototypes算法是一种基于划分的聚类算法，用模式(Vl，V2，…，Vk)来代替聚类的均值，其算法步骤为:

步骤1确定类的个数k，并为每个类选择k个初始的聚类原型V1，V2，…，Vk;

步骤2按照改进后的K-prototypes聚类公式计算样本到各原型的距离，并将其划分到离它最近的聚类原型所代表的聚类中;

步骤3重新计算聚类原型;

步骤4重复步骤3，步骤4直到各个聚类中数据对象稳定不变，结束。

于是改进后的K-prototypes算法：

d(Xi，Vl)=|Xij－Vlj|2+β*J反（P，Q）•+γ*L反（P，Q）•

=d1(Xi，Vl)+βd2(Xi，Vl)+γd3(Xi，Vl)（12）

其中β和γ分别为二元和类型属性数据的权重值（0~1之间）。

不难看出，当没有分类型数据时，即β=0，γ=0,时，该算法即为K-means算法；当没有二元数据时，即β=γ时，该算法与K-prototypes算法相似，但其实并不相同。

3改进后K-prototypes聚类算法实现与结果分析

3.1设计流程图

数值型数据采用离差标准化，按照改进后的K-prototypes聚类公式计算，如下图所示：

图1改进算法程序技术路线图

3.2计算数据选择计算与结果分析

3.2.1数据选择和计算

属性数据选用全国农业种植统计数据（2368个城、县区，每个区域包含37个数值型数据，12个二元数据，4个类型数据），数值型数据标准化后计算过程如下：

图2程序计算界面图

3.2.2改进方法聚类结果与分析

为了方便比较和分析，本次选择34个代表县区的所有属性数据作为处理对象）。当β=1，γ=1，k=13时，聚类结果如表1所示，随着β和γ值的变化，有变化的聚类个数如图2所示：

表1聚类结果

图3不同β和γ权重值聚类变化图

如图所示表明，标准化后的数值型数据均在0~1之间，经过欧几里平方相加后数据不会太大，分类数据属性相异度距离有效降低了分类数据的两个权重值在聚类过程中在某一范围内大幅度改变聚类结果的影响。因此我们还是要根据不同要求选择合理的权重值。

4结束语

本研究从数据标准化和分类数据细化方面，对属性数据的计算进行改进，特别是将分类数据划分为二元数据和类型数据，满足和方便了用户对不同类型数据的重要性和影响程度进行操控，实现理想的分类结果，对混合属性聚类分析有一定的指导意义。当然，后期还可以对K-prototypes聚类算法的其他多问题和局限进行探讨，比如初始中心点选择，全局性等方面。

参考文献

[1]邓敏,刘启亮,李光强,黄建柏著《空间聚类分析及应用》科学出版社（p-2177.0101）

[2]陈治平,林亚平,彭雅等基于最小无关类的数据挖掘算法J．电子学报200331（11)1750－1754．

[3]孙吉贵,刘杰,赵连宇．聚类算法研究[J].软件学报2008.19(1)48－61．