韓新新

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

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

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

1 概論

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

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

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

2 基于K-medoids的Chameleon算法

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

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

2.2 相對接近度和相對互連度

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

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

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

那么簇U和簇V的相對互連度（Relative Closeness）RCOU，V被定義為：先求出簇U和簇V的內(nèi)部互連度（Internal inter-Connectivity）的加權(quán)和，然后用加權(quán)和去除簇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的中心點的所有邊權(quán)值的和。

2.3 相似度值

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

Metric=RCLU，VRCOU，Vα（3）

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

2.4 聚類算法步驟

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

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

Step2：給定閾值minMetric;

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

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

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

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

3 實驗結(jié)果分析

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

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

4 結(jié)束語

本文針對Chameleon算法需要對最近鄰圖進(jìn)行最小二等劃分這一缺陷，提出了運用K-medoids算法對初始數(shù)據(jù)進(jìn)行聚類得到初始類簇，略去了Chameleon算法中的最近鄰圖的劃分問題。實驗結(jié)果表明：本文提出的改進(jìn)的Chameleon算法改善了Chameleon聚類的第一階段的最近鄰圖的最小二等劃分問題;聚類結(jié)果的熵值、純度和F1值都比原算法的結(jié)果值表現(xiàn)要好。本文研究的不足之處是并沒有在原算法的基礎(chǔ)上提高算法的運算速度，對于提高運算效率這方面的問題仍需要再做進(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算法的聚類算法COCK[J].微電子學(xué)與計算機(jī)，2015，32（12）：173-176.