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

何雨軒

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

1引言

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

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

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

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

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

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

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

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

因?yàn)閱捂溄臃椒ㄖ豢紤]兩個(gè)類簇中最近的樣本，不考慮其他樣本，所以會(huì)導(dǎo)致相似性較差的樣本聚合在一起。全鏈接方法只考慮兩個(gè)類簇中最遠(yuǎn)的樣本，導(dǎo)致它只適合球形數(shù)據(jù)的聚類。平均鏈接方法是這兩種方法的折中。

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

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

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

4實(shí)驗(yàn)

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

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

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

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

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

4.2真實(shí)數(shù)據(jù)集的聚類實(shí)驗(yàn)

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

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

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

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

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