基于K-prototypes的混合属性数据聚类算法改进

摘 要：属性数据分为数值型数据和分类型数据，一般情况下对于数值型数据运算前要进行标准化处理，但是对于数值型数据差异大的数据，由于大数掩盖小数的影响，按照K-prototypes聚类算法，数值型数据标准化后而且不对相应的分类数据有任何预处理或者在计算时没有进行任何改变，很可能提高分类数据在聚类中的影响，并且分类型数据并未进一步地细分，不能满足不同要求的混合属性聚类。该文在将数值型数据标准化的基础上，将分类数据细分为二元数据和类型数据，并用相异度系数距离计算分类数据之间的距离，并且赋予二元和类型数据相应的权重，来改进K-prototypes聚类算法，使该算法满足不同要求的混合属性数据聚类，最后通过C#语言，在ArcEngine2010版本上实现。

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

中图分类号：TP311.1 文献标志码：A 文章编号：2095-2945（2024）28-0031-05

Abstract： Attribute data is divided into numerical data and classification data. Generally， numerical data needs to be standardized before operation. However， for data with large differences in numerical data， since the large number hides the influence of decimal numbers， according to the K-prototypes clustering algorithm， after the numerical data is standardized and the waterlogging classification data is not preprocessed or changed during calculation， the influence of classification data in clustering is likely to be improved. Moreover， the classified data has not been further subdivided and cannot meet the different requirements of mixed attribute clustering. Based on standardizing numerical data， this paper divides classified data into binary data and type data， uses dissimilarity coefficient distance to calculate the distance between classified data， and assigns waterlogging weights to the binary and type data to improve the K-prototypes clustering algorithm， so that the algorithm can meet different requirements for mixed attribute data clustering. Finally， it is implemented on ArcEngine2010 version through C# language.

Keywords： K-prototypes algorithm; mixed attributes; type data; dissimilarity coefficient; weighted attributes

聚类分析是人类认识客观事物最朴素、最常用的手段之一，也是人类认识自然最基本、最有效的技能之一[1]。从简单的“物以类聚，人以群分”到用数学工具去提取相关联的信息，聚类分析快速发展成为重要的数据挖掘技术，有效地改变了现代“数据丰富，信息贫乏”的困境[2-3]。

MacQueen于1967年首次提出了K-means聚类算法[4]，但是此算法只能对数值属性进行处理，对其他的分类数据无法处理。1998年，Huang[5]提出了K-modes算法，此算法虽然能够通过匹配差异描述相异性对分类属性数据进行处理，但对于混合属性数据的处理还是存在一定不足。Huang等[6]进一步将K-modes算法在K-prototypes算法中推广应用，用以解决分类属性数据和混合属性数据的聚类问题。

随后又有很多基于K-prototypes算法的改进算法，如2007年赵立江等[7]改进混合属性聚类算法，2010年陈丹等[8]研究一种改进的混合属性聚类算法的初始中心点选择算法，2010年陈韡等[9]基于K-prototypes混合属性数据聚类算法的分类属性相异度，以及2013年白天等[10]的混合属性聚类新方法从全局上把握初始原型，还有2014年刘强等[11]改进的加权K-prototypes算法等，都是从初始点选择或者聚类原型选择以及分类属性相异度计算的基础上进行算法的改进，并未进一步对分类数据划分计算。为此，本文在将数值型数据标准化的基础上，将分类数据细分为二元数据和类型数据，并用相异度系数计算分类数据之间的距离，并且赋予二元和类型数据相应的权重，进一步改进K-prototypes聚类算法，使该算法满足不同要求的混合属性数据聚类，最后通过C#语言，在ArcEngine2010版本上实现。

1 K-prototypes算法

把K-means及K-modes两种算法相融合，引入参数γ，在聚类过程中能够实现对数值属性以及分类属性的权重的控制[3]。令X={X1，X2，X3，…，Xn}表示具有n个样本的数据集，其中Xi=[Xi1，Xi2，…，Xip，Xi（p+1），…，Xim]表示第i个样本的m个属性值（1至p表示数值型数据属性，p+1至m表示分类型数据属性）。使数据集的初始聚类数为k，V={V1，V2，…，Vk}为对应模的集合，聚类过程中迭代聚类集为C={C1，C2，…，Ck}，Ci=[Ci1，Ci2，…，Cik]：①首先确定类的个数k，并为每个类选择k个初始的聚类原型；②对样本与各原型的距离进行计算，根据计算结果，把样本划分到距离最近的聚类原型相应的聚类中；③重新计算各个聚类相应的聚类原型；④循环③及④，至每个聚类中数据对象趋于稳定，迭代F（X，V）无变化，方可停止。

定义1[5]数值属性的距离测量采用欧几里得距离的平方，样本Xi与模Vl数值属性的距离定义为

d1（Xi，Vl）=∑Xij-Vlj。 （1）

采用海明威距离公式进行类属性距离计算，样本Xi以及模Vl类属性的距离为d2（Xi，Vl）

d2（Xi，Vl）=∑δ（Xij，Vlj）， （2）

式中：当Xij=Vlj时，δ（Xij，Vlj）=1；当Xij≠Vlj时δ（Xij，Vlj）=0。

定义2[5]相异性测量函数计算样本到模的距离，d（Xi，Vl）为样本Xi至模Vl的距离

d（Xi，Vl）=∑Xij－Vlj+γ∑δ（Xij，Vlj）

=d1（Xi，Vl）+γd2（Xi，Vl）

式中：γ表示分类属性的权重值；δ表示分类属性的相异度。

定义3[9]求解聚类优化问题的目标函数（代价函数）

F（X，V）=∑∑uijd（Xi，Vj） ， （4）

∑uij=1；uij∈[0，1] ， （5）

式中：uij为1时，表示样本Xi在类Cl中；uij为0，则不属于类Cl。

1.1 属性数据类型

属性数据类型一般可以分为数值型属性数据和分类型属性数据，同时分类属性数据中又包括值均为0和1类型的数据以及其他类型的数据，由于二元数据值只有0和1，任意2个维度的相同属性值相等的概率一般比较大，所以即使二元属性所赋权重值较小也有很高的相似性，而其他的类型数据同属性相比相等的概率就比较低，所以要相当的权重值才能保证一定的相似性。因此，根据不同专题属性的要求和影响以及分类可操控程度的不同，将分类型数据分为二元属性数据和类型属性数据。

数值型数据比较常见，也是聚类的基础数据类型。对于二元属性数据通常取值只有0和1两个状态，此类属性相似性度量聚类方面通常采用匹配测度，比如农业数据中种植作物的有和无等均可用1和0二元数据表示。而类型数据通常为0，1，2，…，n等整数，分别代表不同数据的不同类别，比如农业数据中地貌类型、作物种类等均可赋予不同的整数来代表不同的类型。

1.2 相似性度量

1.2.1 数值型属性数据

数值型数据相似性测度通常采用距离测度，比如切氏距离、马氏距离、Caberra距离和平均距离等方法。一般情况下，由于数值型数据量纲、来源、量级均不相同，所以计算距离前应进行标准化处理。数据的归一化处理是最典型的，将数据统一映射到[0，1]区间上，常用的标准化方法有离差标准化、标准差标准化等。

1.2.2 二元型属性数据

二元型属性数据相似性度量通常采用匹配测度[1]。对于2个分别包含d维二元属性的空间实体P和Q，其中任一分量pi和qi的比较将构成以下4个变量。

1）f00：pi为0且qi也为0的属性个数；

2）f01：pi为0且qi也为1的属性个数；

3）f10：pi为1且qi也为0的属性个数；

4）f11：pi为1且qi也为1的属性个数。

此时的匹配方法有以下几种简单匹配系数：Jaccard系数、Tanimoto系数、Dice系数以及Kulzinsky系数等，最常用的是Jaccard系数，算法如下：对于2个分别包含d维二元属性的空间实体P和Q，其Jaccard系数记为J（P，Q），即

J（P，Q）=f11/（f01+f10+f11） 。 （6）

1.2.3 类型属性数据

类型属性数据通常采用一种简单的相似系数，根据二元属性的定义，2个空间实体P和Q，如果这2个实体中的分量（pi和qi）相等的个数为m，分量总个数为n，则类型相似系数L（P，Q）=m/n。

2 属性数据相异度度量

相异度度量是根据混合属性相异度的需要，在相似性度量的基础上建立起来的混合度量方法。

2.1 数值型距离相异度

数值型数据距离相异度，就是在数值上相距的远近，通常采用欧式距离和欧式距离平方等方法，而K-prototypes聚类方法中数值属性数据就是采用欧几里平方的方法计算数值相异度。

当然，计算前要对数据进行标准化处理，处理后一般为小数，处于（0～1）之间，此时K-prototypes聚类算法不仅要计算数值型数据，而且要计算分类型数据，yes或者no型数据转化为二元数据，其他字符串型（非数字）数据转化为类型数据。

2.2 二元型相异度

根据二元型属性数据相似性度量中的匹配系数，不难想到二元相异度系数即为相似度的对立面公式为

J反（P，Q）=1-f11/（f01+f10+f11） 。 （7）

取相异度系数与二元单维属性总个数（Num）的算术平方根相乘作为二元相异度距离，即为J反（P，Q）·。

2.3 类型属性相异度

同样对于类型属性数据相异度系数的定义为

L反（P，Q）=1-m/n 。 （8）

当然取相异度系数与二元单维属性总个数的算术平方根相乘作为类型相异度距离，即为L反（P，Q）·。

3 K-prototypes算法的改进

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

d1（Xi，Vl）=∑Xij－Vlj。 （9）

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

d2（Xi，Vl）=J反（P，Q）·， （10）

d３（Xi，Vl）=Ｌ反（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={V1，V2，…，Vk}，迭代聚类集为C={C1，C2，…，Ck}，Ci= [Ci1，Ci2，…，Cik］，具体步骤：①首先明确类的个数k，并为每个类选择k个初始的聚类原型；②根据改进后的K-prototypes聚类公式，对样本到各原型距离进行计算，依据计算结果，把样本划分到距离最近的聚类原型相应的聚类中；③对聚类原型全部进行重新计算；④循环③及④，直至各个聚类中数据对象趋于稳定不变，方可停止。

于是改进后的K-prototypes算法

式中：β和γ分别为二元和类型属性数据的权重值（0～1）。

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

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

4.1 数据选择和计算

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

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

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

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

5 结束语

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

参考文献：

[1] 邓敏，刘启亮，李光强，等.空间聚类分析及应用[M].北京：科学出版社，2177.0101.

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

[3] CHEN N，CHEN A，ZHOU L X.Fuzzy K-prototypes algorithm for clustering mixed numeric and categorical valued data[J].Journal of Software，2001.12（8）1107－1119．

[4] 孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，2008，19（1）48－61．

[5] HUANG Z. Extensions to the K-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery II，1998（2）283－304．

[6] Huang Z.， Ng M. A fuzzy K-modes algorithm for clustering categorical data[J].IEEE Transacitons on Fuzzy Systems，1999，7（4）：446－452．

[7] 赵立江，黄永青，刘玉龙.改进的混合属性数据聚类算法[J].计算机工程与设计，2007，28（20）：4850－4852．

[8] 陈丹，王振华.一种改进的混合属性数据聚类算法[J].电脑知识与技术，2010，6（11）：2713-2716.

[9] 陈韡，王雷，蒋子云，等.基于K-prototypes的混合属性数据聚类算法[J].计算机应用，2010，30（8）：2003-2005.

[10] 白天，冀进朝，何加亮，等.混合属性数据聚类的新方法[J].吉林大学学报（工学版），2013，43（1）：130-134.

[11] 刘强，邓磊，贾振红，等.一种改进的加权K-prototypes算法[J].激光杂志，2014，35（1）：18-20.