一種基于局部異常因子（LOF）的k-means算法

陳 靜，王 偉（青島職業(yè)技術(shù)學(xué)院，山東青島，266555）

?

一種基于局部異常因子（LOF）的k-means算法

陳 靜，王 偉
（青島職業(yè)技術(shù)學(xué)院，山東青島，266555）

摘要：聚類分析算法是數(shù)據(jù)挖掘技術(shù)的一個重要分支，目前其研究已經(jīng)廣泛應(yīng)用于教育、金融、零售等眾多領(lǐng)域并取得了較好的效果。本文結(jié)合了基于劃分和密度的聚類思想，提出了一個適用于挖掘任意形狀的、密度不均的、高效的聚類算法。

關(guān)鍵詞：數(shù)據(jù)挖掘；聚類算法；局部異常因子

0 引言

隨著數(shù)據(jù)挖掘技術(shù)應(yīng)用領(lǐng)域越來越廣泛，聚類分析也接受著各種嚴峻的“考驗”：處理的數(shù)據(jù)類型的多樣化，對大數(shù)據(jù)集進行高效處理的迫切需求，對任意形狀聚類的有效識別等等。這些都要求聚類算法能夠具體高效、靈活等特點，因此，尋求一個高效、靈活的聚類算法，是研究人員的當(dāng)務(wù)之急。

1 聚類算法

聚類分析方法是數(shù)據(jù)挖掘技術(shù)應(yīng)用最廣泛的算法之一。在機器學(xué)習(xí)領(lǐng)域，聚類分析算法屬于無指導(dǎo)型學(xué)習(xí)算法。給定一組對象，聚類分析自動地將其聚集成k個集群，每個集群中的對象具有極高的相似度，而屬于不同集群的對象間的相似度很低。因此，聚類分析挖掘算法在科學(xué)和工程的各個領(lǐng)域，包括生物信息學(xué)、市場分析、圖像分析、網(wǎng)絡(luò)搜索等起著極其重要的作用。目前提出了很多聚類算法，例如分割的方法、層次的方法、基于密度的方法等。但是這些聚類方法主要存在如下的問題:

1）符號屬性:大部分聚類方法因為是基于歐氏距離的，所以只能處理數(shù)值屬性的數(shù)據(jù)；

2）初值的選擇對聚類算法的最終結(jié)果有很大的影響；

3）算法對輸入?yún)?shù)存在依賴性。

這些問題的存在使得研究高正確性，低復(fù)雜度的聚類方法迫在眉睫，這也是今后聚類分析的研究方向。因此，本文提出了基于局部異常因子（LOF）的k-means算法，該算法適用于任意形狀、大小和密度的群體聚類。

2 基于局部異常因子（LOF）的k-means算法

基于局部異常因子的初始聚類中心選擇算法，利用了基于線性的運行時間的k-means算法，同時避免了該算法的缺陷。為了獲得任意形狀的簇，將要聚類的任意形狀劃分為凸形，這種方法是基于計算幾何的凸分解的概念。一個凸分解即是一個劃分，如果片重疊，則是覆蓋區(qū)域。根據(jù)形狀的復(fù)雜性，應(yīng)盡量減少中心點的數(shù)目，而且各中心所覆蓋的空間仍能構(gòu)成一個集群。本文采用迭代式的基于局部異常因子（LOF）的k-means方法來尋找近似最優(yōu)中心點。

基于局部異常因子（LOF）的k-means算法的偽代碼如下所示：

LOF-k-means（D，K， mp）:

1.Cinit=seed_center_initialization（D，k，mp）

2.Cseed=K-means（Cinit， k）

3.For every two nearest pairs（Ci， Cj）∈Cseed* Cseed

4.DA（i，j）=density _arrived（Ci，Cj）

5.If DA（i，j）& DA（j，i）is True

6.Merge（Ci， Cj）produced new Cluster Cn

7.Cluster_centers（Cseed，DA）

該算法有三個參數(shù)：D是輸入數(shù)據(jù)集；參數(shù) k代表初始中心點的數(shù)目；mp定義了初始中心點必須滿足的條件——最近鄰點數(shù)，通過限制最近鄰點的數(shù)目來避免選擇離群點為中心。

LOF-k-means算法的第一階段如上偽代碼所描述的第1-2步。這個階段涉及到運行k-means算法的初始中心選擇Cinit，直到收斂為止，得到最終初始中心點集群Cseed。在此步驟中，算法初始仍然是隨機選擇中心點，但是在迭代過程中，使用集群中最接近中心平均值的數(shù)據(jù)點而不是k-means每一次迭代中的平均值。為了避免這種情況，改進后的算法的初始化考慮局部異常因子LOF（Local Outlier Factor），通過局部異常因子LOF來選擇初始聚類中心。

對于點x∈D，給定一個最小閾值mp，定義x點附近的鄰近點如下：

其中，y為x的mp個點內(nèi)的一點。因此N（x， mp）包含至少mp個數(shù)據(jù)點?；趍p的x密度計算如下：

從本質(zhì)上講，x和相鄰點之間的距離越近，x的密度越高?；趍p的x的平均相對密度（ard）被計算為x的密度比率和其近鄰的平均密度，計算公式如下：

最后，局部異常因子LOF定義為平均相對密度的倒數(shù)。

LOF值更為準(zhǔn)確地表示了一個點在何種程度上屬于離群點。一個屬于某一集群的點，其LOF值約等于1，這是由于它的密度與它鄰近點的密度大致相同。

圖4.1 基于LOF的初始聚類中心選擇Fig. 4.1 LOF-based Clustering Seed Selection

圖4.1所示為基于LOF選擇初始中心點的結(jié)果展示。

為了獲得高質(zhì)量的聚類結(jié)果，相鄰的兩個集群會進行合并操作以得到最終的k個自然集群。假設(shè)點A被選擇作為一個偽中心點。為了將點B分配到除以A為中心點的集群中，應(yīng)該存在另一個中心點比cdistmin距離更接近于B。距離B點的任何小于cdistmin的值都屬于集群B。如果數(shù)據(jù)集被分布到一個二維區(qū)域A，則K的值可由給出，其中式是一個對中心點周圍聚類面積的近似值，無需精確地進行計算。

4 算法實驗分析與驗證

本文提出的LOF-K-means算法由C++語言實現(xiàn)。采用監(jiān)督度量機制，通過一個已知的先驗的真實聚類同時結(jié)合聚類純度來評價聚類結(jié)果的質(zhì)量。給定真實的集群Ct=｛c1，c2，…，cl｝，由LOFK-means算法產(chǎn)生的聚類Cs=｛s1，s2，…，sm｝，純度由以下公式給出：

其中，N為數(shù)據(jù)集中包含的點數(shù)，純度的取值范圍在［0，1］，一個完美聚類其純度值為1。

聚類質(zhì)量實驗選擇在數(shù)據(jù)集DS-4上進行。圖4.2為改進后算法在定義的不同聚類中心個數(shù)時的純度得分。實驗設(shè)置的聚類中心個數(shù)從60到540不等，從圖中可以看出，基于LOF的聚類算法的聚類質(zhì)量受初始參數(shù)K的影響不大，其純度得分均在0.8以上，均可以達到良好的聚類效果。這一點，也是基于LOF的聚類算法優(yōu)于其它算法之處。

圖4.2 基于不同K值的聚類質(zhì)量Fig. 4.2 Cluster quality based on Varying of seedclusters

5 結(jié)束語

聚類分析是數(shù)據(jù)挖掘的一個重要的研究領(lǐng)域，國內(nèi)外都對其研究及應(yīng)用傾注了大量的關(guān)注。為了得到更加精確的聚類結(jié)果，更準(zhǔn)確地應(yīng)用于實際業(yè)務(wù)當(dāng)中，研究者對聚類分析算法在各個方面都進行了大量的改進，更不乏將其它領(lǐng)域的算法應(yīng)用于聚類分析算法，將兩者或多個算法結(jié)合，這也表明，將算法進行融會貫通，應(yīng)用于特定行業(yè)，也是未來聚類分析研究的熱門方向。

參考文獻

［1］《數(shù)據(jù)挖掘中聚類分析算法研究與應(yīng)用》， 嚴勇， 軟件工程，電子科技大學(xué).2007

［2］Sack JR， Urrutia J（2000）Handbook of computational geometry. North-Holland， Amsterdam.

［3］Chazelle B， Palios L（1994）Decomposition algorithms in geometry. In： Bajaj C（ed）Algebraic geometry and its applications. Springer， Berlin：419-447.

A k-means algorithm based on local outlier factor（LOF）

Chen Jing，Wang Wei
（Qingdao Technical College，Qingdao，Shandong，266555）

Abstract：Cluster analysis is an important research field in data mining，at present，the research has been applied to the financial， retail and other fields， and have achieved good results.This paper studied partition and density clustering algorithm， proposed a new algorithm which is suitable for mining arbitrary shape and uneven density.

Keywords：Data Mining；Clustering algorithm；Local Outlier Factor