孫志明

摘要：總結(jié)密度聚類算法存在的共性問(wèn)題，即聚類之前的參數(shù)設(shè)定困難，據(jù)此提出密度聚類算法的改進(jìn)目標(biāo)。模擬萬(wàn)有引力勢(shì)能的物理模型，結(jié)合核密度估計(jì)的概念，構(gòu)建引力勢(shì)能影響函數(shù)與引力勢(shì)能密度函數(shù)，從而創(chuàng)造引力勢(shì)能聚類算法，該算法能夠克服聚類算法中的參數(shù)設(shè)定困難。詳細(xì)介紹了該算法的基本原理、參數(shù)設(shè)定、聚類評(píng)判依據(jù)，算法步驟，并通過(guò)實(shí)際應(yīng)用案例展示該算法在聚類分析和異常分析中的作用。

關(guān)鍵詞：聚類；密度；引力勢(shì)能；參數(shù)設(shè)定；異常分析

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）08-1889-05

放眼當(dāng)今世界，聚類算法百花齊放。遺憾的是，多數(shù)算法要求用戶在缺乏先驗(yàn)知識(shí)的條件下輸入某些參數(shù)，這些參數(shù)設(shè)定往往帶有盲目性，卻顯著影響聚類結(jié)果。此外，現(xiàn)實(shí)中的數(shù)據(jù)集很難找出全局最優(yōu)參數(shù)能夠反映聚類結(jié)構(gòu)的本質(zhì)特征。

相較之下，密度聚類算法具有許多優(yōu)良特性，例如能發(fā)現(xiàn)任意形狀的簇，適于處理噪聲，對(duì)記錄輸入順序不敏感，容易理解和使用范圍廣泛等等。但在聚類前，仍不免需要輸入一些對(duì)結(jié)果敏感的參數(shù)。該文選擇密度聚類算法作為研究方向，致力于找出更有效的算法模型，解決參數(shù)設(shè)定盲目性的難題。

1 密度聚類算法的共性問(wèn)題

以上分析為密度聚類算法指明了改革方向，該文需要設(shè)計(jì)一種新算法：有能力發(fā)現(xiàn)任意形狀的簇；允許各簇的密度級(jí)別差異懸殊；具有噪聲處理能力；盡可能不依賴輸入?yún)?shù)；由算法自動(dòng)確定聚簇的結(jié)構(gòu)、數(shù)目、形狀、密度和規(guī)模?？偠灾且业揭环N能夠自動(dòng)確定聚類結(jié)構(gòu)的模型，實(shí)現(xiàn)聚類自動(dòng)化。

2 引力勢(shì)能聚類算法

為解決聚類參數(shù)預(yù)設(shè)的困難，前人已針對(duì)多種聚類算法進(jìn)行過(guò)大量改進(jìn)嘗試，但都不算特別成功，看來(lái)僅僅改進(jìn)和修正是很難在聚類自動(dòng)化方面有所突破的。下面介紹的引力勢(shì)能聚類算法（Gravitational Potential Energy Clustering Algorithm，縮寫(xiě)為GPECA），正是從自然界基本規(guī)律中獲得啟發(fā)，創(chuàng)造而成的。

2.1 GPECA基本原理

2.6 GPECA逐步說(shuō)明

STEP1是基于相異度的聚類算法的通用過(guò)程。

STEP4計(jì)算[EC1]和[εC1]是作者經(jīng)多次不同特性的數(shù)據(jù)集聚類試驗(yàn)后總結(jié)出的技巧，該技巧旨在保持同一聚簇成員的統(tǒng)一特性。不直接使用聚簇邊緣成員自身的[Ex]和[εx]參與聚簇判定，可以有效避免極端情況下產(chǎn)生下述錯(cuò)誤：因密度逐漸稀疏過(guò)渡而將兩個(gè)或多個(gè)不同密度區(qū)域連成一片聚簇。

STEP9從定義出發(fā)，最終確定整個(gè)聚類結(jié)構(gòu)和噪聲集合。

2.7 算法性能分析

3 算法驗(yàn)證

評(píng)價(jià)本案例的分析效果：①完成了預(yù)期的分析目標(biāo)；②所獲得的38個(gè)聚類，雖然包含企業(yè)數(shù)目差距懸殊的不同聚類規(guī)模，而且這些聚類難以給出明確的特征定義，但確實(shí)客觀反映了這些重點(diǎn)企業(yè)的整體分布情況和各自特點(diǎn)；③聚類總數(shù)和異常企業(yè)比例在分析人員可接受的范圍之內(nèi)；④采用異常指數(shù)可以進(jìn)一步分析各種不同的異常企業(yè)問(wèn)題究竟出在哪里，但異常原因的歸納還不夠精細(xì)。⑤經(jīng)重點(diǎn)企業(yè)問(wèn)卷調(diào)查和對(duì)有嚴(yán)重偷漏稅嫌疑的部分企業(yè)抽樣稽查，證明上述推斷準(zhǔn)確率超過(guò)90%。

反觀采用DBSCAN分析，若每次設(shè)定不同的[ε]和MinPts參數(shù)，則每次聚類結(jié)果都顯著不同。多次迭代聚類的結(jié)果有：

聚類總數(shù)大于80個(gè)，異常比例49%；或者聚類總數(shù)大于300個(gè)，異常比例28%；或者僅有1個(gè)聚類，異常點(diǎn)僅6個(gè)。這些結(jié)果無(wú)法綜合研究，既不利于分類管理，也不利于異常分析。

綜上，GPECA能很好地完成稅源分類管理、重點(diǎn)稅源監(jiān)控和稅務(wù)稽查選案三項(xiàng)重要工作，在納稅評(píng)估應(yīng)用中非常有效。

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

GPECA是一種新穎的密度聚類算法，它可以基本解決多數(shù)聚類算法中的參數(shù)設(shè)定和全局最優(yōu)參數(shù)選擇問(wèn)題。此外，基于客觀聚類的結(jié)果之上，還能進(jìn)一步進(jìn)行異常分析。本算法適用于對(duì)中型數(shù)據(jù)集執(zhí)行聚類分析和異常分析。

參考文獻(xiàn)：

[1] Soman K P， Diwakar S， Ajay V. Insight into Data Mining： Theory and Practice[M]. India： Prentice Hall of India， 2006.

[2] 張興會(huì).數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘技術(shù)[M].北京：清華大學(xué)出版社，2011.

[3] Ankerst M， Breunig M M， Kriegel H P. Optics： Ordering Points to Identify the Clustering Structure[C]. Proceeding ACM SIGMOD International Conference on Management of Data， Philadelphia， PA， USA， 1999：46-60.

[4] Terrell G R， Scott D t. Variable Kernel Density Estimation. Ann Statistics[C]，1992，1236-1265.

[5] 余小高，余小鵬.基于距離和密度的無(wú)監(jiān)督聚類算法的研究[J].計(jì)算機(jī)應(yīng)用與軟件，2010（7）：122-125.

[6] Ronald Lane Reese. University Physics[M]. Brooks/Cole-Thomson Learning，2002.

[7] Ian H Witten， Frank E. Data Mining： Practical Machine Learning Tools and Techniques[M]. Third Edition， New Zealand， 2011.

[8] Park H S， Jun C H， A simple and fast algorithm for K-medoids clustering， Expert Systems with Applications，2009（2）：3336-3341.

[9] Breunig M M， Kriegel H P， Ng R T， Sander J. LOF： Identifying Density-based Local Outliers[C]， ACM SIGMOD Record 29：93.