一种改进的chameleon聚类算法

张灿龙

摘要：为了克服Chameleon聚类算法无法有效的处理混合属性数据的缺点，本文提出一种改进的Chameleon聚类算法。该算法首先采用一种新的两阶段聚类整合算法，适用于处理大规模数据集；其次对聚类分析中计算相似性的欧式距离进行拓广，使新算法能够处理混合属性数据。通过实例验证该算法可以很好的解决含有混合属性的大规模数据集问题。

关键词：Chameleon；大规模数据集；混合属性数据

1 引言

层次聚类中现有Chameleon聚类算法【1】基于对k-平均聚类算法缺点的观察，有效避开人为给出参数k的难题，在合并簇的过程时，层次清楚，有利于发现高质量的任意形状的簇。但现有Chameleon聚类算法处理大规模数据集时有局限性等缺点和难以处理混合属性数据的问题，本文基于前人所研究的D-chameleon聚类算法的基础上【2】，提出一种新的两阶段聚类整合算法（TD-chameleon）适用于处理大规模数据集；对聚类分析中计算相似性的欧式距离进行拓广，使其适用于混合数据之间相似性的计算，从而合理解决TD-chameleon聚类算法无法有效处理混合属性数据的难题。

2 Chameleon聚类算法的改进

2.1 相关定义

Chameleon聚类算法构造k-最近邻图Gk中k值的确定和相似度函数阈值的选取都需要人工进行，很大程度上影响了最后聚类效果。针对上述存在的问题，龙真真等人根据加权图、结构等价相似度和模块度等概念进一步提出一种改进的chameleon聚类算法（D-chameleon），将数据对象转化为加权图，由模块度来决定聚类算法是否终止，很好避免上述阈值的人工选取等难题[3]，D-chameleon算法的部分概念如下进行简单描述。

1加权图

加权图G=（V,E,W)是由非空有穷节点集V，边集E和权值矩阵W构成的三元组。无序偶对表示连接节点与节点的边。如果则，否则。

2结构等价相似度

簇r和簇h间的结构等价相似度为 ，其中，是边的权值，为簇r中的节点个数，为簇h中的节点个数。

3模块度

设某聚类结果将图划分为k个簇，即，。定义一个一维向量，。定义模块度的衡量标准 ，值越大，聚类结果越符合簇内连接紧密，簇间连接稀疏的标准，即聚类效果越好。

4 相似性

 若数据对象和含有不确定属性，则对象之间的距离（距离）定义为：

=

         （1）                      

说明：上式中和分别为不确定数据的中心与半径。由于数值型数据也能看作特殊的不确定数据，如，。所以新提出的距离能同时适用于含有数值型、连续型和不确定型的混合属性数据之间的距离计算。

2.2 TD-chameleon聚类算法改进设计

TD-chameleon聚类算法中有关相似性的计算采用新的距离定义，其算法主要聚类过程描述如下：

Stage1.利用初始聚类算法将数据集划分为大小相同的个簇。聚类过程如下：

1.初始时，单个簇集合为空，向簇中心读入一个新的对象。

2.如已到数据集的末尾，则转到步骤5，否则读入新对象利用新的距离定义计算它与每个已有簇间中心对象的距离，并选取最小距离。

3.若最小距离超过给定的阈值时，则转到步骤4，否则将该对象并入与之最小距离的簇中并更新簇中心，然后转步骤2。其中，在数据集中随机选取若干对象，计算每对对象之间的距离，并且计算这些距离的平均值和方差，阈值的取值在之间。

4.以这个对象为中心去构建一个新的簇，，转到步骤2。

5.初始聚类结束。

Stage2.利用D-chameleon算法对初始划分的结果聚类过程如下：

6.将第一阶段划分得到的每个簇看成一个对象，根据加权图的定义，构建加权图G，初始化簇的个数为，每个对象就是一个簇。

7.计算结构等价相似度，如簇和簇间的结构等价相似度为 ，其中，是边的权值，实际为节点和节点的距离的倒数，为簇中的节点个数，为簇中的节点个数，按结构等价相似度由小到大的顺序，并对结构等价相似度最小的两个簇进行合并，。

8.根据模块度定义公式计算模块度Q。

9.重复进行步骤7和步骤8，不断合并簇，直到模块度Q下降，聚类算法终止，输出聚类结果。

3 实验分析

3.1实验环境

实验所用到的计算机配置为windows旗舰版操作系统，Intel i7双核处理器，8GHz主频和8GB内存，实验数据采用某企业能耗监测数据集，算法是用Java语言在Eclipse软件上进行编写所实现的。

3.2 实验结果分析与比较

K-prototypes算法[4]涵盖了K众数划分聚类和K均值划分聚类这两个算法的不同特点，可以有效的处理混合属性数据，将TD-chameleon算法与K-prototypes算法在Mushroom数据集和KDDCUP99数据集上进行聚类精度[5]比较。Mushroom数据集约含8000多条记录，每个记录都有22个分类属性进行描述。KDDCUP99数据集约含有490多万条模拟记录，每条记录由34个数值型属性和7个分类属性所描述，选用一个大概10%的数据子集来检测算法。在选定的数据集上重复运行6次，每次都要改变记录的顺序，实验结果如表所示。

数据集	聚类算法	平均聚类个数	平均聚类精度
Mushroom	TD-chameleon	22.6	95.32
	K-prototypes	—	91.26
KDDCUP99	TD-chameleon	7.4	93.19
	K-prototypes	—	89.76

测试结果表明TD-chameleon算法在上述两种数据集上的平均聚类精度均高于K-prototypes算法，且聚类效果较好。

4 结语

针对Chameleon聚类算法无法有效的处理混合属性数据的缺点，本文提出一种改进的Chameleon聚类算法。通过实例验证该算法可以很好的处理混合属性数据，且较其他算法在平均聚类精度上有所提高。

参考文献

[1]一种改进CHAMELEON算法的聚类算法COCK[J].朱烨行,李艳玲,杨献文.微电子学与计算机.2015,第12期.

[2]一种改进的Chameleon算法[J].龙真真,张策,刘飞裔.计算机工程.2009,第020期.

[3]基于Hadoop平台的一种改进K-means文本聚类算法[J].潘俊辉,王辉,张强.微型电脑应用.2022,第1期.

[4]一种基于改进模糊聚类算法的自适应典型日选取方法[J]. 邬浩泽,朱晨烜,张贻山.智慧电力.2022,第1期.

[5]一种CHAMELEON改进算法[J].王鹏宇,王国宇,苏天赟.信息通信.2017,第006期.