基于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.