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

陳 靜，王 偉（青島職業技術學院，山東青島，266555）

?

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

陳 靜，王 偉
（青島職業技術學院，山東青島，266555）

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

關鍵詞：數據挖掘；聚類算法；局部異常因子

0 引言

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

1 聚類算法

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

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

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

3）算法對輸入參數存在依賴性。

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

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

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

基于局部異常因子（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）

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

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

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

其中，y為x的mp個點內的一點。因此N（x， mp）包含至少mp個數據點。基于mp的x密度計算如下：

從本質上講，x和相鄰點之間的距離越近，x的密度越高。基于mp的x的平均相對密度（ard）被計算為x的密度比率和其近鄰的平均密度，計算公式如下：

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

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

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

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

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

4 算法實驗分析與驗證

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

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

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

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

5 結束語

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

參考文獻

［1］《數據挖掘中聚類分析算法研究與應用》， 嚴勇， 軟件工程，電子科技大學.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