基于離群點檢測（LOF）的K-means算法*

楊 紅 ，李丹寧 ，王雅潔

（1.貴州大學 大數據與信息工程學院，貴州 貴陽 550025；2.貴州省食品安全檢測應用工程技術研究中心有限公司，貴州 貴陽 550022）

0 引 言

伴隨著大數據時代的發展，各種數據信息呈現出爆炸式的增長，計算機軟硬件的不斷升級，讓各種數據層出不窮，為了更好的利用數據中隱藏的信息，數據挖掘技術順應時代的發展出現在了學者與研究人員的視野。進而聚類分析也再次出現在了潮流的前沿，在圖像處理、模式識別、病毒入侵檢測等等習以為常的地方總是能夠出現蕨類分析的身影。應用廣泛、理論基礎扎實、方便實用等優點，使得聚類分析幾十年來一直是研究者們的心頭所愛。

以劃分為目的的算法更是頻頻出現在各種場合，為人們解決了無數問題。而K-means作為其中最具有代表性的算法，被列入了“十大經典算法”，其產生的價值自然不必都說。雖說K-means 算法易于實現，速度理想，然而人無完人，金無足赤，該算法也理所當然的存在些許不盡如人意的地方：（1）初始聚類中心是隨機產生，進而直接導致聚類結果也存在隨機性，準確性低；（2）聚類個數K值不好確定，K值的選取直接決定了聚類結果的準確度；（3）數據集中離群點的存在也會影響聚類結果，如若將離群點選為初始中心點，不僅僅會降低速度，增加時間復雜度，甚至可能會出現錯誤[1-2]。

很多學者針對K-means存在的不足之處提出了相應的改進方法。楊莉云等[3]提出引入謝林模型，使孤立點能夠自動移動到其鄰居所在位置，消除孤立點，但是此方法對數據集進行了改變，數據集發生了變化。唐澤坤等[4]在K-means算法的基礎上權衡了密度和距離對聚類的影響，對數據進行加權處理，在權值基礎上引入“最小最大原則”選擇初始聚類中心，自動確定類中心個數。以上方法都在一定程度上對算法的聚類結果進行了優化。

1 K-means算法

聚類算法是一種無監督學習算法；何謂的無監督學習？簡而言之，就是輸入的數據沒有標簽，目標是通過對無標簽數據的學習來了解數據之間的內在聯系和本質，為下一步的數據處理及數據分類提供扎實的基礎。其算法步驟如下：

輸入無標簽數據集X，聚類數K；

i：在數據集中隨機選取K個樣本作為初始質心；

ii：分別計算數據集中每個樣本對象Xm到K個質心的歐式距離；

iii：找到與每個樣本對象Xm距離最小的質心ci，同時將該樣本對象Xm歸為與ci相同的簇中；

iv：計算同一簇中的平均值，所得即為新的質心；

v：重復i-iv，直到質心不再發生改變

通常對于歐式空間的樣本數據，以平方誤差和（Sum of Squared Error，SSE）作為聚類的目標函數，同時也可以衡量不同聚類結果的好壞。

表示樣本點x到簇點中心ci的的距離平方和，最優的聚類結果應使得SSE達到最小值[5]。

K-means算法具有執行效率高、易于實現等優點，但是分類效果會受到多種因素的影響，如數據集本身、K值的確定，初始簇中心的確定等等。

為了使最終輸出的聚類效果更加理想，文中提出利用離群點檢測算法先對數據進行預處理，剔除算法檢測出的離群點，然后再用K-means算法對處理過的數據集進行分類。

2 離群點檢測（Local Outlier Factor，LOF）算法

在數據挖掘方面，數據正式使用之前通常要進行預處理，本文便利用離群點檢測算法對數據進行了預處理，既對數據集中的離群點進行篩選，目的是減小異常點對聚類效果的影響，提高算法效率。離群點檢測算法原理介紹如下：

LOF算法相關定義：

（1）d(A,O)點A與點O之間的歐式距離。

（2）第k距離（k-distance）

點A的第k距離dk(A)：dk(A)=d(A,O)，從通俗意義上來講，A的第k距離，就是距離A第k遠的點到A的距離（不包括A本身）。

（3）第k距離領域（k-distance neighborhood）

點A的第k距離領域，就是以A為圓心，以第k距離為半徑的區域以內的所有點（包括圓上的點）。因此A的第k領域點的個數至少是k個。

（4）可達距離（reach-distance）

點O到點A的第k可達距離定義為：

也就是點O到點A的第k可達距離取dk(A)與d(A,O)兩者之間的較大值。

（5）局部可達密度（local reachability density）

點A的局部可達密度表示為：

表示點A的第k領域內的點的平均可達距離的倒數。

Irdk(A)代表一個密度，密度越高，代表A周圍的點越多，顯而易見，我們認為A越可能與周圍的點屬于同一簇，相反，密度越低越可能是離群點。概括來說就是，局部可達密度與成為離群點的概率成反比。

（6）局部離群因子（Local Outlier Factor）

點A的局部離群因子表示為：

點A的鄰域點Nk(p)的局部可達密度與點A的局部可達密度之比的平均數。

如果這個比值越接近1，說明A的其鄰域點密度差不多，A可能和鄰域同屬一簇；如果這個比值越小于1，說明A的密度高于其鄰域點密度，A為密集點；如果這個比值越大于1，說明A的密度小于其鄰域點密度，A越可能是異常點[6]。

3 LOF-K-means算法介紹

為了優化算法，本文提出了利用離群點檢測算法（LOF）對離群點進行篩選，其算法步驟如下：

輸入：數據集X，聚類數K；

輸出：聚類結果；

i 將LOF算法應用與iris數據集，得到每個數據的局部離群因子，從而得到一個密集點數據集iris-1和一個離群點數據集iris-2；

ii 用K-means算法對數據集iris-1進行聚類，得到該數據集的聚類結果；

iii 將數據集iris-2直接按iris-1的結果進行分類，無需重新計算質心，進行循環；

iv 輸出最終分類結果。

算法流程圖如圖1所示。

在本文提出的算法中也對傳統K-means的準則函數進行了改進，傳統準則函數僅僅考慮到類內的相似性，改進后的準則函數將類與類之間的差異性也做了充分考慮[7]。

其中，SSE1為傳統K-means算法中的準則函數，僅考慮類間相似度，d(ci,cj)為第i個質心和第j個質心間的歐式距離。

SSE2由類間距離和類內距離共同決定。類內距離小的同時類間距離大的聚類結果則是理想的聚類結果。SSE2的值與類內聚類成正比，與類間距離成反比。既分子越小，分母越大，SSE2的值就越小，聚類效果就越好。

圖1 LOF-K-means流程

4 實驗仿真與分析

為驗證文中算法的有效性及合理性，本文選用了UCI標準數據集中的鳶尾花卉數據集（iris）進行仿真實驗。該數據集包含150個數據集，分為3類，每類50個數據，每個數據包含4個屬性，文中利用二維數據集進行實驗，篩選了數據屬性中的前2個屬性，即花萼長度和花瓣寬度。

iris數據集原圖如圖2所示。開始未對數據進行預處理，直接采用K-means對數據集分類，其中k=4，分類結果如圖3所示。

圖2 iris數據集原圖

圖3 iris數據集K-means分類

之后采用離群點檢測算法（LOF）對數據集進行預處理，篩選并剔除原數據集10%（15個）的離群點之后再利用K-means分類，結果如圖4所示。

圖4 LOF分類結果

本文采用質心兩兩之間距離的平均值來衡量類間的離散程度，質心之間的距離越大說明類間的離散程度越大，聚類效果越好，仿真結果如表1所示，由表1的數據可以看出，本文的算法比傳統的K-means算法得出的分類效果類間距離更大，類間離散效果更理想。

表1 4個質心兩兩之間距離的平均值

同時以平方誤差和（SSE）作為目標函數來評價類內聚合度。兩種算法得到的聚類效果分析數據如表2所示，由表2可知，從整體來看，本文算法得到的SSE小于傳統K-means算法得到的SSE，4種聚類結果的平方誤差和分別在原來的基礎上提高了41%、29%、46%、40%，類內聚合度平均提高了39%。由此來看本文采用的算法在提高類內聚合度上表現良好，可以在較大程度上使類內的聚合效果更加理想。

表2 兩種算法SSE比較

5 結 語

本文提出了將離群點檢測算法與K-means算法相結合，對數據集進行預處理之后再進行分類的算法，巧妙地避免了離群點對聚類效果帶來的不良影響，同時對傳統的準則函數進行了改進，本文采用的準則函數不僅考慮到了類內的相似度，也考慮到了類與類之間的差異性，使得聚類結果進一步優化。