基于K-medoids的Chameleon算法分析

韩新新

摘 要：通过对现有的Chameleon算法进行改进，将Chameleon算法与K-medoids算法相结合，提出了一种新的混合的聚类算法。改动之处在于：取消Chameleon算法的第一阶段的划分小类簇，代替它的是运用K-medoids算法对原始数据进行初步划分，将充分接近的对象作为一个整体对待，对得到的类簇直接用Chameleon算法第二阶段的合并算法进行类簇的合并。运用多个数据集进行实验测试，根据不同的实验指标对实验结果进行分析，证明改进的Chameleon算法有很好的聚类效果。

关键词：聚类;Chameleon;K-medoids;算法

中图分类号：TB 文献标识码：A doi：10.19311/j.cnki.1672-3198.2019.34.094

1 概论

聚类算法时如今大数据时代的数据挖掘领域的一项重要研究内容，聚类算法是根据对象之间的相似度将对象划分为不同的组，使得同一组内的对象相似度最大化，而不同组内的对象相似度最小化的方法。

在1999年，Karypis、Han和Kumar提出了Chameleon聚類方法。Chameleon聚类算法是层次聚类算法的一种，该聚类算法首先利用基于图论的方法得到最初的数据划分，然后根据层次聚类算法进行簇间组合，使用簇间的接近性和互连性概念以及局部建模来分类出具有任意形状、大小和密度的簇。在1990年，Kaufman和Rousseeuw提出了K-medoids聚类方法。K-medoids算法是一种基于划分的聚类算法，该算法是利用类簇中最靠近中心的一个对象来代表该类簇，即使用中心作为质心代表类簇。

本文将K-medoids聚类算法的除噪性与Chameleon聚类算法能聚类任意形状和大小的类簇的优点相结合，改进得到一种新的混合聚类算法，不仅可以减小孤立点对类簇划分的影响，还可以发现任意形状、大小和密度的类簇。实验结果表明，与原有的Chameleon聚类算法相比较，在数据类型的适应性、聚类的完整性以及计算精度等方面，本文改进的Chameleon聚类算法有明显的优势。

2 基于K-medoids的Chameleon算法

2.1 内部接近度和内部互连度

假如簇U内部有NU个点，那么簇U的内部接近度（Internal Closeness）ICLU就定义为连接簇U的中心点与簇内其余点的所有边的权值的平均值;簇U的内部互连度（Internal inter-Connectivity）ICOU定义为连接簇U的中心点与簇内其余点的所有边的权值和。

2.2 相对接近度和相对互连度

假如簇U内部有NU个点，簇V内部有NV个点，那么簇U和簇V之间的相对接近度（Relative Closeness）RCLU，V被定义为：先求出簇U和簇V的内部接近度（Internal Closeness）的加权和，然后用加权和去除簇U和簇V之间的绝对接近度（Absolute Closeness）ACLU，V。

RCLU，V=ACLU，VNUNU+NV*ICLU+NVNU+NV*ICLV（1）

其中，ACLU，V表示簇U和簇V之间的绝对接近度（Absolute Closeness），其被定义为连接簇U的中心点和簇V的中心点的所有边权值的平均值。

那么簇U和簇V的相对互连度（Relative Closeness）RCOU，V被定义为：先求出簇U和簇V的内部互连度（Internal inter-Connectivity）的加权和，然后用加权和去除簇U和簇V之间的绝对互连度（Absolute inter-Connectivity）ACLU，V。

RCOU，V=ACOU，VNUNU+NV*ICOU+NVNU+NV*ICOV（2）

其中，ACOU，V表示簇U和簇V之间的绝对互连度（Absolute inter-Connectivity），其被定义为连接簇U的中心点和簇V的中心点的所有边权值的和。

2.3 相似度值

相似度值的函数定义是相对接近度与相对互连度的乘积，公式表示如下：

Metric=RCLU，VRCOU，Vα（3）

其中，α是用来调节两个参量的比重的参数。α>1时，表示更加重视相对互连度;α<1时，表示更加重视相对接近度。

2.4 聚类算法步骤

基于K-medoids的Chameleon算法利用K-medoids算法对数据集进行初步划分，然后再利用Chameleon算法对聚类结果进行合并。聚类算法的具体步骤描述如下：

Step1：运用K-medoids算法对数据进行初始划分，得到初始小类簇;

Step2：给定阈值minMetric;

Step3：计算每个簇内的内部接近度和内部互连度;

Step4：计算每个簇与其相邻每个簇之间的相对接近度和相对互连度，计算出相似度值tempMetric，并将只存放在一个列表中;

Step5：从列表中找到最大的tempMetric值，如果它超过阈值minMetric，将此值对应的簇进行合并;

Step6：递归步骤4，直到待合并的簇的列表为空。

3 实验结果分析

通过三个数据集来测试本文改进的Chameleon算法，在表1中对原Chameleon算法和本文改进的Chameleon算法在聚类结果的熵、纯度和F1值三个方面进行了比较。

虽然在运算过程中原算法的运算速度优于我们本文的改进算法，但是由表1可以看出，在熵、纯度和F1值这三个方面，我们改进的算法要显著优于原算法。

4 结束语

本文针对Chameleon算法需要对最近邻图进行最小二等划分这一缺陷，提出了运用K-medoids算法对初始数据进行聚类得到初始类簇，略去了Chameleon算法中的最近邻图的划分问题。实验结果表明：本文提出的改进的Chameleon算法改善了Chameleon聚类的第一阶段的最近邻图的最小二等划分问题;聚类结果的熵值、纯度和F1值都比原算法的结果值表现要好。本文研究的不足之处是并没有在原算法的基础上提高算法的运算速度，对于提高运算效率这方面的问题仍需要再做进一步的研究。

参考文献

[1]Karypis G，Han E and Kumar V.CHAMELEON：A hierarchical clustering algorithm using dynamic modeling[J].COMPUTER，1999，32：68-75.

[2]Leonard K，Peter J.R.Finding Groups in Data：An Introduction to Cluster Analysis[M].John Wiley & Sons，1990.

[3]Guha S，Rastogi R，Shim K：a robust clustering algorithm for categorical attributes[C]//Proceedings of the 15th International Conference on Data Engineering.Washington，DC，USA：IEEE Computer Society，1999：512-521.

[4]朱烨行，李艳玲，杨献文.一种改进CHAMELON算法的聚类算法COCK[J].微电子学与计算机，2015，32（12）：173-176.