基于異常檢測(cè)的K-means改進(jìn)算法研究

薛晨杰 林婷薇

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

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

DOI：10. 11907/rjdk. 182467

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

0 引言

隨著數(shù)據(jù)挖掘技術(shù)的迅速發(fā)展，日常生活產(chǎn)生的海量數(shù)據(jù)中隱含的信息及商業(yè)價(jià)值越來越多地被挖掘與展現(xiàn)出來。聚類分析是數(shù)據(jù)挖掘中的常用分析方法[1]，其目的是將輸入的數(shù)據(jù)樣本通過聚類找到數(shù)據(jù)特征，然后根據(jù)樣本相似程度將數(shù)據(jù)集合分成若干個(gè)簇，使每一個(gè)簇中的數(shù)據(jù)點(diǎn)達(dá)到最大同質(zhì)化，而使不同簇之間的差異最大化。聚類算法研究歷史悠久，早在1975年Hartigan[2]即在其專著《Clustering Algorithms》中對(duì)聚類算法進(jìn)行了系統(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ù)點(diǎn)到簇中心距離作為優(yōu)化目標(biāo)的函數(shù)聚類方法，但其仍然存在一些缺陷，比如受孤立點(diǎn)、噪聲點(diǎn)以及初始聚類中心影響較大等。因此，學(xué)者們對(duì)此進(jìn)行了大量研究。Metropolis等[8]提出的模擬物理學(xué)上固體退火過程的優(yōu)化算法，有著更好的聚類效果，但會(huì)增加算法復(fù)雜度;Dong 等[9]首先通過二分K-means算法將數(shù)據(jù)集分為 K 個(gè)大類，再利用模擬退火算法優(yōu)化聚類中心，從而提高了聚類準(zhǔn)確度;Bhuyan等[10]提出可用遺傳算法改進(jìn)聚類效果，隨后Jones等[11]、Babu等[12]也相繼提出應(yīng)用遺傳算法改進(jìn)K-means算法初始聚類中心的思路。以上改進(jìn)算法都是基于優(yōu)化算法，與此同時(shí)也有不少學(xué)者基于密度分布情況選擇聚類中心。Katsavounidis等[13]提出一種通過盡可能分散初始聚類中心的解決方法，從而有效避免了被選擇的聚類中心過于密集的情況;Khan等[14]提出的 CCIA 算法，利用數(shù)據(jù)點(diǎn)的均值、標(biāo)準(zhǔn)差、百分位數(shù)等統(tǒng)計(jì)信息提供數(shù)據(jù)點(diǎn)密度分布信息，從而得到初始聚類中心;牛琨等[15]提出基于密度指針的初始聚類中心選擇算法DP，根據(jù)密度差異確定密度指針方向，并計(jì)算出聚集因子，最后將具有較大局部聚集因子的重心作為初始聚類中心。

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

1 K-means聚類算法簡介

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

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

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

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

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

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

2 算法改進(jìn)

針對(duì)K-means算法存在的問題，提出如下改進(jìn)方案：

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

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

2.1 Isolation Forest算法

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

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

算法1 生成樹

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

輸出： 生成的二叉樹

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

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

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

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

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

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

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

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

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

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

2.2 改進(jìn)K-means算法

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

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

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

3 實(shí)驗(yàn)仿真

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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