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

?

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

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

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

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

0 引言

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

1 聚類(lèi)算法

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

1）符號(hào)屬性:大部分聚類(lèi)方法因?yàn)槭腔跉W氏距離的，所以只能處理數(shù)值屬性的數(shù)據(jù)；

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

3）算法對(duì)輸入?yún)?shù)存在依賴(lài)性。

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

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

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

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

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

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

對(duì)于點(diǎn)x∈D，給定一個(gè)最小閾值mp，定義x點(diǎn)附近的鄰近點(diǎn)如下：

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

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

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

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

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

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

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

4 算法實(shí)驗(yàn)分析與驗(yàn)證

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

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)

［1］《數(shù)據(jù)挖掘中聚類(lèi)分析算法研究與應(yīng)用》， 嚴(yán)勇， 軟件工程，電子科技大學(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