層次聚類算法的改進(jìn)研究

何雨軒

關(guān)鍵詞：層次聚類；聚類；改進(jìn)算法；連通度

1引言

聚類是一種常用的無監(jiān)督機(jī)器學(xué)習(xí)方法，在模式識別、數(shù)據(jù)挖掘、計算機(jī)視覺、自然語言處理等方面都有廣泛的應(yīng)用。聚類算法的種類較多，原理也各不相同。例如，有基于密度、劃分、層次、圖論、網(wǎng)格、深度學(xué)習(xí)的聚類。每種聚類算法都有自己的特點和適用場景。層次聚類就是其中一種較為典型的算法，它常用于財務(wù)分析[1]、社區(qū)健康管理、醫(yī)學(xué)研究、時間序列預(yù)測等。

與其他類型的聚類算法相比，層次聚類具有許多優(yōu)點。首先，它具有檢測“嵌套類簇”的能力。其次，它構(gòu)建了一個樹狀的聚類層次樹，可以顯示連續(xù)步驟的聚類過程。由于類簇可以在二維圖中可視化，因此，用戶可以直觀且容易地理解數(shù)據(jù)集的底層結(jié)構(gòu)。再次，利用樹狀圖也可以很容易地檢測出異常值。最后，它不需要預(yù)先指定類簇的數(shù)量，這是一個非常重要的優(yōu)勢，因為確定簇的數(shù)量是聚類中最難的問題。

層次聚類的特點是聚類過程體現(xiàn)了聚類數(shù)量的漸變，一共有兩種漸變方式：一是聚類數(shù)量從小到大，從最初所有的樣本屬于同一個類簇，逐漸分裂成兩個、三個類簇，一直分裂到每個樣本屬于一個單獨的類簇；二是聚合的方式，最初每個的樣本都各自屬于一個不同的類簇，然后將其中最相似的兩個類簇合并成為一個類簇，接著逐步聚合，直到所有的類簇合并為一個類簇[2]。

層次聚類主流的聚類方式是聚合，當(dāng)前代表性的算法包括AgglomerativeClustering，BIRCH，CURE，ROCK，Chameleon。這些經(jīng)典的層次聚類算法不僅有自己的優(yōu)點，也有明顯的缺陷。例如，非球形的數(shù)據(jù)集聚類準(zhǔn)確性較差，以及時間復(fù)雜度比較高。后來，有一些學(xué)者對經(jīng)典層次聚類做了改進(jìn)，如周維柏等[3]提出了一種改進(jìn)的模糊層次聚類算法：張春英等[4]提出了一種面向不完備數(shù)據(jù)的集對粒層次聚類算法：王志飛等[5]提出了凝聚中心猶豫度恒定的模糊層次聚類算法。這些算法雖然部分解決了層次聚類的問題，但是效果并不是非常好。

本文提出了新的改進(jìn)算法，在各個類簇合并的過程中，通過綜合判斷各個相鄰類簇的相似性，并在不同的階段使用不同的計算方法，從而提升聚類精度的聚類效率。

2經(jīng)典層次聚類算法

目前，常用的層次聚類算法都是用聚合的方式進(jìn)行聚類[6]，如Python下常用的一些層次聚類算法：scipy.cluster.hierarchy.linkage，sklearn.cluster.AgglomerativeClustering。這些算法對包含Ｎ個數(shù)據(jù)的算法的流程如圖1所示。

各個類簇之間距離的計算方式較多，其中包括單鏈接、全鏈接、平均鏈接。具體而言，假設(shè)有兩個類簇Ci，Ci，它們之間的距離用不同方法計算，結(jié)果分別不同。

因為單鏈接方法只考慮兩個類簇中最近的樣本，不考慮其他樣本，所以會導(dǎo)致相似性較差的樣本聚合在一起。全鏈接方法只考慮兩個類簇中最遠(yuǎn)的樣本，導(dǎo)致它只適合球形數(shù)據(jù)的聚類。平均鏈接方法是這兩種方法的折中。

3改進(jìn)層次聚類算法

為了彌補經(jīng)典層次聚類的缺陷，本文提出了一種改進(jìn)的算法。改進(jìn)算法也是以聚合的方式進(jìn)行聚類，在聚類的過程中，前期使用單鏈接的方法判斷兩個類簇是否可以合并。事實上，在聚類前期，類簇內(nèi)包含的樣本數(shù)量較少，使用單鏈接或者全鏈接方式基本沒有差別。當(dāng)聚類的數(shù)量小于樣本的1/5或者達(dá)到目標(biāo)類簇數(shù)量K的4倍時，聚類使用新的方法判斷兩個類簇是否可以合并。這個新的方法就是連通度。

連通度是兩個類簇之間的距離和密度的綜合衡量，其中距離計算用類簇之間樣本的最小距離表示。至于密度計算，首先以計算出類簇之間最小距離的中心點作為圓心，然后用三倍最小距離作為半徑來計算該圓形內(nèi)部的樣本數(shù)量。

4實驗

為了驗證改進(jìn)算法的有效性，本文設(shè)計了相關(guān)實驗進(jìn)行驗證。實驗環(huán)境的配置如下：計算機(jī)的操作系統(tǒng)為Windowsl0：計算機(jī)的CPU為Intel Core i3-9IOOF3.6GHz;硬盤為2TB；內(nèi)存為8GB。

改進(jìn)的層次聚類算法采用Python3.6編程實現(xiàn)。實驗中，用于對比的經(jīng)典層次聚類算法使用sklearn. cluster. AgglomerativeClustering函數(shù)，并分別用單鏈接、全鏈接、平均鏈接的距離計算方法聚類。

4.1模擬數(shù)據(jù)集的聚類實驗

實驗用的模擬數(shù)據(jù)集選用Aggregation和Spiral。本文提出的改進(jìn)層次聚類算法和經(jīng)典層次聚類算法的單鏈接、全鏈接、平均鏈接方法對Aggregation和Spiral的聚類結(jié)果如表1所列。由表1可知，本文提出的層次聚類改進(jìn)算法效果最好。經(jīng)典層次聚類算法使用的單鏈接方法和全鏈接方法對兩個數(shù)據(jù)集的聚類結(jié)果都較差，使用平均鏈接方法對Aggregation聚類效果尚可，對Spiral的聚類效果較差。

本文提出的改進(jìn)層次聚類算法和經(jīng)典層次聚類算法對數(shù)據(jù)集Aggregation和Spiral的聚類結(jié)果F值如圖3所示。通過對比兩個數(shù)據(jù)集上各種算法的聚類F值可知，改進(jìn)算法比經(jīng)典算法的效率至少提高了18.5%。

4.2真實數(shù)據(jù)集的聚類實驗

真實數(shù)據(jù)集采用了UCI（University ofCalifornialrvine）提供的公開數(shù)據(jù)。這些數(shù)據(jù)是通過在真實世界的測量、收集而獲得，所以更具有參考意義。在UCI數(shù)據(jù)集中，本文選擇了Abalone和Segmentation。

聚類結(jié)果評價指標(biāo)見表2，其中包括調(diào)整蘭德系數(shù)（ARI，Adjusted Rand index）、標(biāo)準(zhǔn)互信息素（NMI，Normalized Mutual Information）、F值、準(zhǔn)確率（Accuracy）。

通過對比表2中的各個聚類指標(biāo)可知，在單鏈接、全鏈接和平均鏈接方法方面，改進(jìn)層次聚類算法明顯優(yōu)于經(jīng)典層次聚類算法。這說明在真實數(shù)據(jù)集上，改進(jìn)層次聚類算法的聚類效果更好。

5結(jié)束語

層次聚類是一種應(yīng)用廣泛的經(jīng)典算法，但是其自身也有明顯的缺陷，如對非球形數(shù)據(jù)聚類效果較差。本文提出了一種改進(jìn)算法，通過在聚類的不同階段使用不同的類簇合并策略來改進(jìn)算法，在聚類的開始階段，使用單鏈接的方法；在聚類的后期，使用連通度的方法。通過對模擬數(shù)據(jù)集Aggregation和Spiral的聚類實驗，以及對真實數(shù)據(jù)集Abalone和Segmentation的聚類實驗，驗證了改進(jìn)算法的有效性。