基于K-medoids的Chameleon算法分析

韓新新

摘 要：通過(guò)對(duì)現(xiàn)有的Chameleon算法進(jìn)行改進(jìn)，將Chameleon算法與K-medoids算法相結(jié)合，提出了一種新的混合的聚類(lèi)算法。改動(dòng)之處在于：取消Chameleon算法的第一階段的劃分小類(lèi)簇，代替它的是運(yùn)用K-medoids算法對(duì)原始數(shù)據(jù)進(jìn)行初步劃分，將充分接近的對(duì)象作為一個(gè)整體對(duì)待，對(duì)得到的類(lèi)簇直接用Chameleon算法第二階段的合并算法進(jìn)行類(lèi)簇的合并。運(yùn)用多個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測(cè)試，根據(jù)不同的實(shí)驗(yàn)指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，證明改進(jìn)的Chameleon算法有很好的聚類(lèi)效果。

關(guān)鍵詞：聚類(lèi);Chameleon;K-medoids;算法

中圖分類(lèi)號(hào)：TB 文獻(xiàn)標(biāo)識(shí)碼：A doi：10.19311/j.cnki.1672-3198.2019.34.094

1 概論

聚類(lèi)算法時(shí)如今大數(shù)據(jù)時(shí)代的數(shù)據(jù)挖掘領(lǐng)域的一項(xiàng)重要研究?jī)?nèi)容，聚類(lèi)算法是根據(jù)對(duì)象之間的相似度將對(duì)象劃分為不同的組，使得同一組內(nèi)的對(duì)象相似度最大化，而不同組內(nèi)的對(duì)象相似度最小化的方法。

在1999年，Karypis、Han和Kumar提出了Chameleon聚類(lèi)方法。Chameleon聚類(lèi)算法是層次聚類(lèi)算法的一種，該聚類(lèi)算法首先利用基于圖論的方法得到最初的數(shù)據(jù)劃分，然后根據(jù)層次聚類(lèi)算法進(jìn)行簇間組合，使用簇間的接近性和互連性概念以及局部建模來(lái)分類(lèi)出具有任意形狀、大小和密度的簇。在1990年，Kaufman和Rousseeuw提出了K-medoids聚類(lèi)方法。K-medoids算法是一種基于劃分的聚類(lèi)算法，該算法是利用類(lèi)簇中最靠近中心的一個(gè)對(duì)象來(lái)代表該類(lèi)簇，即使用中心作為質(zhì)心代表類(lèi)簇。

本文將K-medoids聚類(lèi)算法的除噪性與Chameleon聚類(lèi)算法能聚類(lèi)任意形狀和大小的類(lèi)簇的優(yōu)點(diǎn)相結(jié)合，改進(jìn)得到一種新的混合聚類(lèi)算法，不僅可以減小孤立點(diǎn)對(duì)類(lèi)簇劃分的影響，還可以發(fā)現(xiàn)任意形狀、大小和密度的類(lèi)簇。實(shí)驗(yàn)結(jié)果表明，與原有的Chameleon聚類(lèi)算法相比較，在數(shù)據(jù)類(lèi)型的適應(yīng)性、聚類(lèi)的完整性以及計(jì)算精度等方面，本文改進(jìn)的Chameleon聚類(lèi)算法有明顯的優(yōu)勢(shì)。

2 基于K-medoids的Chameleon算法

2.1 內(nèi)部接近度和內(nèi)部互連度

假如簇U內(nèi)部有NU個(gè)點(diǎn)，那么簇U的內(nèi)部接近度（Internal Closeness）ICLU就定義為連接簇U的中心點(diǎn)與簇內(nèi)其余點(diǎn)的所有邊的權(quán)值的平均值;簇U的內(nèi)部互連度（Internal inter-Connectivity）ICOU定義為連接簇U的中心點(diǎn)與簇內(nèi)其余點(diǎn)的所有邊的權(quán)值和。

2.2 相對(duì)接近度和相對(duì)互連度

假如簇U內(nèi)部有NU個(gè)點(diǎn)，簇V內(nèi)部有NV個(gè)點(diǎn)，那么簇U和簇V之間的相對(duì)接近度（Relative Closeness）RCLU，V被定義為：先求出簇U和簇V的內(nèi)部接近度（Internal Closeness）的加權(quán)和，然后用加權(quán)和去除簇U和簇V之間的絕對(duì)接近度（Absolute Closeness）ACLU，V。

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

其中，ACLU，V表示簇U和簇V之間的絕對(duì)接近度（Absolute Closeness），其被定義為連接簇U的中心點(diǎn)和簇V的中心點(diǎn)的所有邊權(quán)值的平均值。

那么簇U和簇V的相對(duì)互連度（Relative Closeness）RCOU，V被定義為：先求出簇U和簇V的內(nèi)部互連度（Internal inter-Connectivity）的加權(quán)和，然后用加權(quán)和去除簇U和簇V之間的絕對(duì)互連度（Absolute inter-Connectivity）ACLU，V。

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

其中，ACOU，V表示簇U和簇V之間的絕對(duì)互連度（Absolute inter-Connectivity），其被定義為連接簇U的中心點(diǎn)和簇V的中心點(diǎn)的所有邊權(quán)值的和。

2.3 相似度值

相似度值的函數(shù)定義是相對(duì)接近度與相對(duì)互連度的乘積，公式表示如下：

Metric=RCLU，VRCOU，Vα（3）

其中，α是用來(lái)調(diào)節(jié)兩個(gè)參量的比重的參數(shù)。α>1時(shí)，表示更加重視相對(duì)互連度;α<1時(shí)，表示更加重視相對(duì)接近度。

2.4 聚類(lèi)算法步驟

基于K-medoids的Chameleon算法利用K-medoids算法對(duì)數(shù)據(jù)集進(jìn)行初步劃分，然后再利用Chameleon算法對(duì)聚類(lèi)結(jié)果進(jìn)行合并。聚類(lèi)算法的具體步驟描述如下：

Step1：運(yùn)用K-medoids算法對(duì)數(shù)據(jù)進(jìn)行初始劃分，得到初始小類(lèi)簇;

Step2：給定閾值minMetric;

Step3：計(jì)算每個(gè)簇內(nèi)的內(nèi)部接近度和內(nèi)部互連度;

Step4：計(jì)算每個(gè)簇與其相鄰每個(gè)簇之間的相對(duì)接近度和相對(duì)互連度，計(jì)算出相似度值tempMetric，并將只存放在一個(gè)列表中;

Step5：從列表中找到最大的tempMetric值，如果它超過(guò)閾值minMetric，將此值對(duì)應(yīng)的簇進(jìn)行合并;

Step6：遞歸步驟4，直到待合并的簇的列表為空。

3 實(shí)驗(yàn)結(jié)果分析

通過(guò)三個(gè)數(shù)據(jù)集來(lái)測(cè)試本文改進(jìn)的Chameleon算法，在表1中對(duì)原Chameleon算法和本文改進(jìn)的Chameleon算法在聚類(lèi)結(jié)果的熵、純度和F1值三個(gè)方面進(jìn)行了比較。

雖然在運(yùn)算過(guò)程中原算法的運(yùn)算速度優(yōu)于我們本文的改進(jìn)算法，但是由表1可以看出，在熵、純度和F1值這三個(gè)方面，我們改進(jìn)的算法要顯著優(yōu)于原算法。

4 結(jié)束語(yǔ)

本文針對(duì)Chameleon算法需要對(duì)最近鄰圖進(jìn)行最小二等劃分這一缺陷，提出了運(yùn)用K-medoids算法對(duì)初始數(shù)據(jù)進(jìn)行聚類(lèi)得到初始類(lèi)簇，略去了Chameleon算法中的最近鄰圖的劃分問(wèn)題。實(shí)驗(yàn)結(jié)果表明：本文提出的改進(jìn)的Chameleon算法改善了Chameleon聚類(lèi)的第一階段的最近鄰圖的最小二等劃分問(wèn)題;聚類(lèi)結(jié)果的熵值、純度和F1值都比原算法的結(jié)果值表現(xiàn)要好。本文研究的不足之處是并沒(méi)有在原算法的基礎(chǔ)上提高算法的運(yùn)算速度，對(duì)于提高運(yùn)算效率這方面的問(wèn)題仍需要再做進(jìn)一步的研究。

參考文獻(xiàn)

[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]朱燁行，李艷玲，楊獻(xiàn)文.一種改進(jìn)CHAMELON算法的聚類(lèi)算法COCK[J].微電子學(xué)與計(jì)算機(jī)，2015，32（12）：173-176.