基于雙倍距離的孤立點(diǎn)檢測算法研究

楊 臻，張明慧

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

0 引言

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

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

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

2 DTKA算法

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

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

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

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

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

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

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

3 算法的流程

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

4.1 函數(shù)Getkdistance()

4.2 函數(shù)Getnn2k()

4.3 函數(shù)GetDTKA()

5 實(shí)驗(yàn)與分析

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

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

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

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

圖1 DTKA實(shí)驗(yàn)結(jié)果圖

圖2 LOF實(shí)驗(yàn)結(jié)果圖

5.2 時(shí)間復(fù)雜度對(duì)比分析

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

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

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

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

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

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

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

6 結(jié)束語

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

[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] 薛安榮,鞠時(shí)光,何偉華等.局部離群點(diǎn)挖掘算法研究[J].計(jì)算機(jī)學(xué)報(bào),2007,30(8):1455-1463.

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

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

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

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