基于雙倍距離的孤立點檢測算法研究

楊 臻，張明慧

（鄭州師范學(xué)院 信息科學(xué)與技術(shù)學(xué)院，鄭州 450044）

0 引言

隨著信息技術(shù)和互聯(lián)網(wǎng)的日益普及，人們在日常工作中積累了大量數(shù)據(jù)，如何更有效的利用這些數(shù)據(jù)，從數(shù)據(jù)中發(fā)現(xiàn)潛在的、更有價值的知識，是人們目前熱熾期待解決的問題。數(shù)據(jù)挖掘技術(shù)為此提供了有力的技術(shù)支持，其中的孤立點檢測技術(shù)更是以挖掘少數(shù)特例的獨特作用而成為了廣大研究者的興趣焦點。孤立點檢測技術(shù)就是利用一些方法挑選出那些與大部分?jǐn)?shù)據(jù)特征不一致的不同尋常的數(shù)據(jù)，從而進(jìn)一步研究這些數(shù)據(jù)意義的一門技術(shù)。在當(dāng)今社會生活中，孤立點檢測技術(shù)有著重要的現(xiàn)實意義和應(yīng)用價值，被許多行業(yè)比如：冶金、電信、氣象等用來挖掘數(shù)據(jù)背后的深層價值，為決策者決策提供有效的數(shù)據(jù)支撐。

1 概述現(xiàn)有算法

不同數(shù)據(jù)領(lǐng)域的孤立點有著不同的定義和相應(yīng)有效的檢測方法，為了檢測出各種假設(shè)情況下存在的孤立點,廣大研究者提出了多種方法。早期時候的典型算法有Rastogi和Ramaswamy提出的k-th Nearest Neighbor孤立點檢測方法。Breunig和Kriegel[3]則對孤立點的認(rèn)定提出了局部性這一不同的新穎的看法。Malik Agyemang進(jìn)一步提出了LSC算法。近些年來，國內(nèi)許多研究人員也相繼從不同方面對前者的算法加以改進(jìn)和提高，如文獻(xiàn)[7]中提出了反向K-近鄰的檢測算法；文獻(xiàn)[8]中提出了變異系數(shù)的檢測算法等。

2 DTKA算法

本文提出了DTKA算法，具體定義如下：

定義1 對象p的2k-距離近鄰數(shù)nn2k (p)

設(shè)數(shù)據(jù)集中的任意一個對象p，則對象p的nn2k (p)值指的是從起點p開始，到2k-距離范圍內(nèi)的所有對象數(shù)。即：

定義2 對象p的DTKA值DTKA(p)

設(shè)數(shù)據(jù)集中的任意一個對象p，則對象p的DTKA值就是2k-距離近鄰數(shù)與k-距離近鄰數(shù)的比值。即：

其中，|nnk(p)|為對象p的k-距離近鄰數(shù)。

如果DTKA值很小說明對象的鄰域是稀疏的，它的離散度較大，數(shù)據(jù)對象很可能是孤立點，相反，如果DTKA值很大說明對象的鄰域是稠密的，它的離散度較小，對象則不可能是孤立點。

3 算法的流程

4 實現(xiàn)算法的主要函數(shù)

4.1 函數(shù)Getkdistance()

4.2 函數(shù)Getnn2k()

4.3 函數(shù)GetDTKA()

5 實驗與分析

下面通過運行VC++實現(xiàn)的DTKA算法和LOF算法，在數(shù)據(jù)集上進(jìn)行多個對比實驗來從不同方面檢驗算法對孤立點的真實識別情況。需要實驗的數(shù)據(jù)集由文本文件輸入提供。

5.1 準(zhǔn)確性對比分析

準(zhǔn)確性實驗采用的數(shù)據(jù)集是一個已知具有5000個對象的2維數(shù)據(jù)集，其中不僅包含大小不一、形狀各異、密度各不相同的4個類，而且包含任意分布的若干孤立點。參數(shù):k=6。DTKA算法和LOF算法經(jīng)過運行以后，獲得的運行結(jié)果如圖1、圖2所示，其中DTKA識別的孤立點情況如圖1所示，LOF識別的孤立點情況如圖2所示。

從圖1和圖2的對比結(jié)果來看，可以充分認(rèn)定DTKA算法對孤立點的識別能力是準(zhǔn)確的，可以正確檢測出需要的孤立點。

圖1 DTKA實驗結(jié)果圖

圖2 LOF實驗結(jié)果圖

5.2 時間復(fù)雜度對比分析

算法性能高低的一個重要衡量指標(biāo)是時間復(fù)雜度。時間復(fù)雜度的大小是由算法的關(guān)鍵部分來綜合決定的。算法第1個主要的運算是在計算每個對象的k-距離過程，因此時間復(fù)雜度為o(kn)。第2個主要的運算是在計算每個對象的K-距離近鄰數(shù),因此時間復(fù)雜度是o(n2)。第3個主要的運算是在是根據(jù)排過序的DTKA值確定前n個孤立點對象過程,因此時間復(fù)雜度為o(nN)，n＜＜N?？傊?，經(jīng)過上述分析得出本算法主要時間復(fù)雜度是o(kn2)，表明DTKA算法的執(zhí)行時間與k存在一次函數(shù)關(guān)系，與n存在平方關(guān)系，其中k代表每個數(shù)據(jù)對象的最近鄰數(shù)，n代表數(shù)據(jù)集中的數(shù)據(jù)對象數(shù)目。

從以上分析結(jié)果來看，DTKA算法的時間復(fù)雜度不比LOF算法高，可以認(rèn)為是符合要求的，可行的。

5.3 執(zhí)行時間對比分析

下面通過測試DTKA算法在隨著數(shù)據(jù)對象數(shù)量增加的情況下的執(zhí)行時間的變化規(guī)律，深入檢驗其執(zhí)行效率。該實驗采用的數(shù)據(jù)集是一個具有12000個記錄的集合，數(shù)據(jù)對象增量變化的范圍從2000到12000，每個對象的最近鄰數(shù)為 K=100，則當(dāng)數(shù)據(jù)規(guī)模分別獲取不同值，并且每次加2000個數(shù)據(jù)對象，即N等于2000，4000，…，12000時，算法在隨著數(shù)據(jù)對象數(shù)量增加的情況下執(zhí)行時間的變化情況如圖3所示。

圖3 不同數(shù)據(jù)規(guī)模的執(zhí)行時間

從圖3中可以看出: DTKA算法運行時所花費的時間是受數(shù)據(jù)規(guī)模直接影響的，但是變化是漸進(jìn)增加的，變化趨勢近似拋物線規(guī)律，并且在相同數(shù)據(jù)規(guī)模情況下DTKA算法的運行時間少于LOF算法。

通過以上多方面的深入實驗分析，可以認(rèn)定DTKA算法能夠高效準(zhǔn)確地檢測出數(shù)據(jù)集中的異常數(shù)據(jù)。

6 結(jié)束語

本文提出的數(shù)據(jù)挖掘技術(shù)方面的DTKA算法，改進(jìn)了對于孤立點的判定方法，詳細(xì)給出了算法的定義，介紹了算法的主要計算流程，實現(xiàn)算法的主要函數(shù)。最后進(jìn)行了大量的實驗，而且對實驗結(jié)果做了深入系統(tǒng)的分析，并于典型算法LOF對比研究，實驗結(jié)論充分表明DTKA算法能有效進(jìn)行孤立點檢測，并且在執(zhí)行時間上少于LOF,解決了傳統(tǒng)算法檢測的缺陷。該算法的合理性、優(yōu)越性在冶金、天氣預(yù)報等數(shù)據(jù)挖掘技術(shù)研究領(lǐng)域有著廣闊的應(yīng)用前景和實際的研究價值。

[1] E.Knorr,R.Ng.A lgorithms for M ining Distance-based Outliers in Large Data Sets[C].Proceedings of the VLDB Conference,1998.392-403.

[2] MALIK A,EZEIFE CI. LSC-m ine: A lgorithm for M ining Local Outliers[A].Proceedings of the 15th Information Resource Management Association (IRMA) International Conference[C].2004.5-8.

[3] Breunig M.M.,K riegel H.–P. ,Ng R.T. ,and Sander J.OPTICS -OF:Identifying local outliers[C]1In Proceedings of 3rd European Conference on Principles of Data M ining and Know ledge Discovery ,Prague,1999.

[4] 薛安榮,鞠時光,何偉華等.局部離群點挖掘算法研究[J].計算機(jī)學(xué)報,2007,30(8):1455-1463.

[5] 盧啟程,鄒平.數(shù)據(jù)挖掘的研究與應(yīng)用進(jìn)展[J].昆明理工大學(xué)學(xué)報.2002,27(5):62-66.

[6] 康塔尼克:數(shù)據(jù)挖掘:概念、模型、方法和算法[M].北京:清華大學(xué)出版社,2003.

[7] 岳峰,聚類的邊界點檢測算法研究,[學(xué)位論文].鄭州大學(xué),2007.

[8] 薛麗香等.基于變異系數(shù)的邊界點檢測算法[J].模式識別與人工智能.2009.05.