薛晨杰 林婷薇

摘 要：K-means算法作為較為普遍的聚類算法，聚類效果受孤立點、噪聲點和初始聚類中心影響較大。結(jié)合Isolation Forest算法計算數(shù)據(jù)中每個樣本的異常度系數(shù)，根據(jù)離群值過濾比例計算得到異常度系數(shù)閾值，對高度異常值加以隔離，并對隔離后的數(shù)據(jù)集使用平均插值法求得初始聚類中心。運用改進K-means算法對真實數(shù)據(jù)集進行聚類分析，與此同時，通過比較多個離群值過濾比例下的聚類結(jié)果，找到離群值過濾比例的最優(yōu)取值。仿真結(jié)果表明，相比于原始算法，新算法顯著提升了聚類準(zhǔn)確性，聚類效果更佳。

關(guān)鍵詞：K-means算法;聚類算法;異常檢測;異常度系數(shù);離群過濾比例

DOI：10. 11907/rjdk. 182467

中圖分類號：TP312文獻標(biāo)識碼：A文章編號：1672-7800（2019）004-0074-05

0 引言

隨著數(shù)據(jù)挖掘技術(shù)的迅速發(fā)展，日常生活產(chǎn)生的海量數(shù)據(jù)中隱含的信息及商業(yè)價值越來越多地被挖掘與展現(xiàn)出來。聚類分析是數(shù)據(jù)挖掘中的常用分析方法[1]，其目的是將輸入的數(shù)據(jù)樣本通過聚類找到數(shù)據(jù)特征，然后根據(jù)樣本相似程度將數(shù)據(jù)集合分成若干個簇，使每一個簇中的數(shù)據(jù)點達到最大同質(zhì)化，而使不同簇之間的差異最大化。聚類算法研究歷史悠久，早在1975年Hartigan[2]即在其專著《Clustering Algorithms》中對聚類算法進行了系統(tǒng)論述。研究者通過觀察聚類分析結(jié)果可以發(fā)現(xiàn)數(shù)據(jù)中隱藏的聯(lián)系與差異，從而將該數(shù)據(jù)分析結(jié)果作為新研究中的依據(jù)[3]。

K-means[4]聚類算法是目前最基本且被廣泛應(yīng)用的聚類分析方法之一，是由MacQueen總結(jié)Cox[5]、Fisher[6]、Sebestyen[7]等研究成果而提出的一種經(jīng)典的以數(shù)據(jù)點到簇中心距離作為優(yōu)化目標(biāo)的函數(shù)聚類方法，但其仍然存在一些缺陷，比如受孤立點、噪聲點以及初始聚類中心影響較大等。因此，學(xué)者們對此進行了大量研究。Metropolis等[8]提出的模擬物理學(xué)上固體退火過程的優(yōu)化算法，有著更好的聚類效果，但會增加算法復(fù)雜度;Dong 等[9]首先通過二分K-means算法將數(shù)據(jù)集分為 K 個大類，再利用模擬退火算法優(yōu)化聚類中心，從而提高了聚類準(zhǔn)確度;Bhuyan等[10]提出可用遺傳算法改進聚類效果，隨后Jones等[11]、Babu等[12]也相繼提出應(yīng)用遺傳算法改進K-means算法初始聚類中心的思路。以上改進算法都是基于優(yōu)化算法，與此同時也有不少學(xué)者基于密度分布情況選擇聚類中心。Katsavounidis等[13]提出一種通過盡可能分散初始聚類中心的解決方法，從而有效避免了被選擇的聚類中心過于密集的情況;Khan等[14]提出的 CCIA 算法，利用數(shù)據(jù)點的均值、標(biāo)準(zhǔn)差、百分位數(shù)等統(tǒng)計信息提供數(shù)據(jù)點密度分布信息，從而得到初始聚類中心;牛琨等[15]提出基于密度指針的初始聚類中心選擇算法DP，根據(jù)密度差異確定密度指針方向，并計算出聚集因子，最后將具有較大局部聚集因子的重心作為初始聚類中心。

本文結(jié)合Isolation Forest算法[16]計算數(shù)據(jù)異常度系數(shù)后對高度異常值加以隔離，并使用平均插值法求得初始聚類中心，以減少孤立點和噪聲點對算法聚類效果的影響，從而對算法加以改進。最后選取若干個現(xiàn)實數(shù)據(jù)集對改進前后的算法進行實驗，并對實驗結(jié)果進行分析檢驗。驗證結(jié)果表明，改進的K-means算法相較于原始算法具有更好的性能及聚類效果。

1 K-means聚類算法簡介

K-means算法選擇期望的簇中心K，通過不斷迭代和重新計算聚類中心，以極小化整個簇內(nèi)方差，將得到緊湊且相互獨立的簇作為算法最終目標(biāo)。利用函數(shù)的求極值方法，調(diào)整迭代次數(shù)閾值獲得最佳聚類效果。

原始K-means算法具體流程如下：

（4）重復(fù)執(zhí)行步驟（2）-（4），直到聚類中心不再發(fā)生變化為止。

K-means算法作為經(jīng)典聚類算法，有著高效簡潔的優(yōu)點，但同時傳統(tǒng)K-means算法也存在較為明顯的缺陷[17]。筆者總結(jié)列出以下兩點較為普遍的缺陷：

（1）孤立點和噪聲點對算法聚類效果影響較大。傳統(tǒng)K-means算法不適合應(yīng)用于樣本差異過大的簇，其對于孤立點和噪聲點數(shù)據(jù)十分敏感，即使是少量孤立數(shù)據(jù)都會對算法性能與結(jié)果造成很大影響，從而使平均值產(chǎn)生偏離。

（2）初始聚類中心選取對聚類效果影響較大[18]。在K-means算法中需要先根據(jù)初始聚類中心確定初始簇的劃分，再對簇進行優(yōu)化。算法聚類結(jié)果對初值選取的依賴性很強，一旦初始聚類中心選擇不佳，可能無法得到最好的聚類結(jié)果。

2 算法改進

針對K-means算法存在的問題，提出如下改進方案：

（1）在使用K-means算法進行聚類之前，首先根據(jù)Isolation Forest異常檢測算法，得到每個數(shù)據(jù)樣本的異常度系數(shù)，將異常度系數(shù)值大于閾值的所有樣本標(biāo)記為異常離群點，然后對這些點進行過濾，在進行簇中心計算時不再使用這些異常數(shù)據(jù)點和離群數(shù)據(jù)點。

（2）在初始化簇中心時，不采用隨機初始化方法，而是首先統(tǒng)計出除異常值和離群值外的數(shù)據(jù)樣本在每個維度上的取值范圍，再根據(jù)需要計算類簇數(shù)，使用平均差值法得到初始聚類中心。

2.1 Isolation Forest算法

Isolation Forest算法采用二叉樹對數(shù)據(jù)進行切分，數(shù)據(jù)點在二叉樹當(dāng)中所處的深度反應(yīng)了該數(shù)據(jù)在集合中的離散程度。該算法性能好、效率高，能有效處理多維數(shù)據(jù)及海量數(shù)據(jù)。算法流程可大致分為以下兩步：①構(gòu)建。抽取一批數(shù)據(jù)樣本，構(gòu)建多棵二叉樹并組合成森林;②計算。綜合每個二叉樹結(jié)果，計算集合中每個數(shù)據(jù)點異常值。

（1）構(gòu)建：對給定的數(shù)據(jù)集D，隨機選擇一個屬性，并在該屬性最大值與最小值之間隨機選擇一個值，將數(shù)據(jù)集中小于該值的數(shù)據(jù)劃分到二叉樹左分支，大于等于該值的數(shù)據(jù)劃分到右分支。重復(fù)上述步驟直到數(shù)據(jù)集只有一條或多條相同記錄，或二叉樹達到限定高度，算法流程如下：

算法1 生成樹

輸入： 數(shù)據(jù)樣本集合[D]，當(dāng)前樹高[h]，限定高度[l]

輸出： 生成的二叉樹

1： 檢測樹高是否大于限定高度，D中是否只包含一條數(shù)據(jù)或全部數(shù)據(jù)相同

2： 若是則輸出節(jié)點數(shù)

3： 否則隨機選取包含于樣本集合D的數(shù)據(jù)屬性

4： 隨機在該屬性最大值和最小值之間選取一個參數(shù)值

5： 將樣本中小于該值的劃分到左分支

6： 將樣本中大于該值的劃分到右分支

7： [重復(fù)上述]步驟直到滿足步驟1條件為止

8： 結(jié)束，返回二叉樹

（2）計算：由于異常點對于數(shù)據(jù)集而言十分稀有，所以可以通過根節(jié)點和葉節(jié)點的路徑[h（x）]判斷一個數(shù)據(jù)點[x]是否為異常點，采用公式（3）進行計算。

從異常度系數(shù)公式中可以發(fā)現(xiàn)，數(shù)據(jù)點在每棵樹中的平均路徑越短，公式值越接近1，則表示數(shù)據(jù)是異常點的可能性高;反之，數(shù)據(jù)在每棵樹中平均路徑越長，公式值越接近0，表示數(shù)據(jù)是正常點的可能性較高。如果大部分樣本系數(shù)都趨近于0.5，說明整個數(shù)據(jù)集沒有明顯異常值。

2.2 改進K-means算法

通過使用上述Isolation Forest算法得到每個樣本異度系數(shù)之后，選取所需的類簇數(shù)[k]和離群值過濾比例[r]。離群值過濾比例是指過濾數(shù)據(jù)個數(shù)占總數(shù)據(jù)樣本個數(shù)的百分比，即使用改進K-means算法需要過濾多少比例的離群點后再進行聚類，默認為0.1。由于需要聚類的數(shù)據(jù)樣本集合中的數(shù)據(jù)個數(shù)通常有限，因此直接將離群過濾比例值基于樣本個數(shù)進行隔離，通常會造成隔離數(shù)據(jù)量過大而產(chǎn)生不必要的誤差。針對該問題，筆者根據(jù)異常度系數(shù)[θ]和離群過濾比例r，擬定異常度系數(shù)閾值公式：[t=θmax-（θmax-][θmin）×r]，即對異常度系數(shù)[θ]大于t的數(shù)據(jù)加以隔離，以避免由于隔離數(shù)據(jù)數(shù)目過大造成的誤差。

聚類算法結(jié)果對初值選取的依賴性很強[19]，因此選取優(yōu)質(zhì)的初始聚類中心是改進算法的重要一步。本文通過統(tǒng)計樣本在各維度上的取值范圍，結(jié)合平均插值法思想進行初始聚類中心選取，即盡可能將初值均勻選取在數(shù)據(jù)集合內(nèi)部，減少邊界值對初始聚類中心選取的影響。對于取值范圍為[i，j]的屬性T，根據(jù)所需類簇數(shù)k，應(yīng)用公式（5）計算初始聚類中心。

獲得高質(zhì)量的初值之后，將過濾的異常樣本歸入剩余樣本集合中，進行多次迭代，直至函數(shù)收斂，改進算法如下：

3 實驗仿真

本節(jié)通過對多個真實數(shù)據(jù)集分別使用原始K-means算法及改進后的K-means算法進行聚類，獲得兩種聚類算法得到的結(jié)果并加以對比，再根據(jù)多種聚類效果評估算法對結(jié)果進行評估，直觀展示改進聚類算法的聚類效果。

3.1 數(shù)據(jù)準(zhǔn)備及預(yù)處理

實驗選擇8個真實數(shù)據(jù)集進行聚類，分別為動物數(shù)據(jù)集、紅酒數(shù)據(jù)集、森林類型數(shù)據(jù)集、鳶尾花數(shù)據(jù)集、小麥種子數(shù)據(jù)集、脊柱數(shù)據(jù)集、ILDP（印度肝臟患者）數(shù)據(jù)集和病樹數(shù)據(jù)集，具體如表1所示。

聚類算法目標(biāo)是實現(xiàn)簇內(nèi)相似度最高且簇之間相似度最低[20]，這是一個集群質(zhì)量內(nèi)部標(biāo)準(zhǔn)，但是良好的內(nèi)部標(biāo)準(zhǔn)并不一定在應(yīng)用中轉(zhuǎn)化效果最好，因此需要對聚類結(jié)果的應(yīng)用效果進行直接評估。本次實驗準(zhǔn)備采用如下幾種評估聚類質(zhì)量算法：

（1）purity是一種簡單、透明的評價方法，每個簇都被分配給最頻繁出現(xiàn)的類，然后通過計算正確數(shù)目測量準(zhǔn)確性，如式（6）所示。

（2）Rand Index假設(shè)數(shù)據(jù)集合中存在N個樣本，則有[N（N-1）2]個集合對，并將同一類樣本分配到同一個簇和不同簇分別定義為TP和FN，將不同類樣本分配到同一個簇和不同簇分別定義為FP和TN。Rand Index計算公式如式（7）所示。

Rand Index存在的缺陷是對假陽性和假陰性給出了相同權(quán)重，分離相似樣本有時比在同一個簇中放置成對的不同樣本效果更差。對此可以使用F測量方法通過選擇一個值對假陰性結(jié)果進行更強的懲罰，從而加大召回權(quán)重，以提高評估準(zhǔn)確性。F測量方法如式（8）-式（10）所示，其中Presicion和Recall數(shù)值分別由P和R表示。

3.2 實驗及結(jié)果分析

本文首先采用動物園數(shù)據(jù)集，該數(shù)據(jù)集包含動物園中生活的101種動物，并根據(jù)動物們具有的如水陸生、胎卵生、哺乳類還是兩棲類、是否有毒等17個特征屬性，將全部動物集分為7個大類。

處理完數(shù)據(jù)集之后，利用改進前后的兩種算法分別對數(shù)據(jù)集進行聚類，設(shè)置離群值過濾比例[r]為0.1，獲得的聚類結(jié)果如圖1、圖2所示。

觀察圖1、圖2可以發(fā)現(xiàn)，原始K-menas算法雖然對數(shù)據(jù)集進行了聚類，但總體仍十分雜亂。運用改進算法進行聚類后，絕大部分相同屬性的樣本被歸到同一類簇中，而不同屬性樣本被分開在不同簇中，分類效果較原始結(jié)果有明顯提升。

僅通過觀察圖得出結(jié)論并不十分可靠，所以采用上文提到的聚類算法評價指標(biāo)對結(jié)果進行評估。分別使用原始K-means算法和改進K-means算法聚類后的結(jié)果進行多項指標(biāo)評估，得到如表2所示評價結(jié)果，其中Pro-Kmeans算法為改進后的K-means算法。

將實驗數(shù)據(jù)繪制成折線圖，如圖3所示。

比較上述聚類算法評價結(jié)果可以發(fā)現(xiàn)，改進K-means算法較原始算法對數(shù)據(jù)集有著更好的聚類效果，算法性能更佳。為驗證算法的改進效果，對剩余的被選數(shù)據(jù)集進行實驗，得到實驗結(jié)果如表3所示。

為使改進算法的結(jié)果更具有說服力，將改進算法中的離群值過濾比例[r]在[0.1，0.5]范圍內(nèi)選取多個不同數(shù)值，根據(jù)不同離群值過濾比例再次對算法聚類效果進行實驗，獲得結(jié)果如表4所示。

將4個數(shù)據(jù)集在不同離群值過濾比例下的F值繪制成折線圖，與對應(yīng)的原始K-means進行對比，如圖4所示。