離群檢測(cè)算法研究.pdf

1、離群點(diǎn)是數(shù)據(jù)集中極少數(shù)與主流數(shù)據(jù)顯著不同的數(shù)據(jù)點(diǎn),它們往往比主流數(shù)據(jù)更具價(jià)值。離群檢測(cè)在許多領(lǐng)域都有著廣泛的應(yīng)用,吸引了包括數(shù)據(jù)挖掘、知識(shí)學(xué)習(xí)、統(tǒng)計(jì)學(xué)和信息論等眾多學(xué)科研究人員的共同關(guān)注。多年來,已有基于各種技術(shù)針對(duì)各類數(shù)據(jù)的離群檢測(cè)算法提出,但針對(duì)高維海量數(shù)據(jù)離群點(diǎn)檢測(cè)的時(shí)間復(fù)雜度問題,始終沒有得到較好的解決。基于近鄰檢測(cè)技術(shù)雖具有無需監(jiān)督,不需要對(duì)數(shù)據(jù)的分布作任何假設(shè)等優(yōu)點(diǎn),但需搜索每個(gè)數(shù)據(jù)點(diǎn)的近鄰,導(dǎo)致O(n2)的時(shí)間復(fù)雜度,限制

2、了算法在高維海量數(shù)據(jù)上的應(yīng)用。設(shè)計(jì)既有效又高效的針對(duì)高維海量數(shù)據(jù)的離群點(diǎn)檢測(cè)算法有著重要的理論和實(shí)際意義。
　　剪枝非離群點(diǎn),減小目標(biāo)數(shù)據(jù)集的大小是降低時(shí)間復(fù)雜度的有效手段。如果數(shù)據(jù)對(duì)象的r鄰域內(nèi)鄰居的個(gè)數(shù)達(dá)到k個(gè)以上,則該數(shù)據(jù)對(duì)象不是DB(k,r)離群點(diǎn)。進(jìn)一步地,如果數(shù)據(jù)對(duì)象的r/2鄰域內(nèi)鄰居的個(gè)數(shù)達(dá)到k個(gè)以上,則該鄰域內(nèi)的所有對(duì)象都不是DB(k,r)離群點(diǎn)。利用這一剪枝規(guī)則,可以排除大量的非離群點(diǎn),從而大大減小目標(biāo)數(shù)據(jù)集的大

3、小。只需通過對(duì)數(shù)據(jù)集的一次掃描即可作到這一點(diǎn):以第1個(gè)點(diǎn)為組中心開始,順序掃描數(shù)據(jù)集,凡與某個(gè)組中心的距離小于r/2的即被標(biāo)記為該組,凡與任何組中心的距離都不小于r/2的,自動(dòng)成為新的組中心。掃描結(jié)束后,凡組的大小達(dá)到k的,組內(nèi)所有數(shù)據(jù)點(diǎn)都被剪枝掉。
　　在檢測(cè)TOPn離群點(diǎn)時(shí),剪枝不必要的近鄰搜索,是減小時(shí)間復(fù)雜度的第二種有效手段。以迄今為止找到的n個(gè)候選離群點(diǎn)中的最小k距離為閾值,一旦發(fā)現(xiàn)某個(gè)數(shù)據(jù)點(diǎn)迄今為止已搜索到的k距離比這

4、個(gè)閾值還小時(shí),立即停止k近鄰的搜索,因?yàn)樵擖c(diǎn)沒有機(jī)會(huì)成為TOPn離群點(diǎn)。
　　抽樣也可以減小數(shù)據(jù)空間,是減小時(shí)間復(fù)雜度的第三種有效手段。但傳統(tǒng)的均勻抽樣技術(shù),缺乏伸縮性。密度偏倚的抽樣技術(shù)可以用更小的樣本代表相同的數(shù)據(jù)集,且更具靈活性。如果樣本由離群偏倚抽樣方法所得,則可僅在樣本空間內(nèi)檢測(cè)離群點(diǎn),這等于縮小了目標(biāo)空間的大小。如果樣本由密度偏倚方法抽樣所得,則可僅在樣本空間探索一個(gè)k值較小的近鄰,這等于縮小了k近鄰的搜索空間。此外,

5、數(shù)據(jù)集中的兩個(gè)點(diǎn)關(guān)于同一樣本的距離差一定小于這兩個(gè)點(diǎn)間的距離,利用這一性質(zhì),還可以估算K距離的下界,甚至取代K距離的計(jì)算,以獲得較小的時(shí)間復(fù)雜度?；诔闃拥碾x群檢測(cè)算法僅需對(duì)數(shù)據(jù)集進(jìn)行三次掃描即完成離群點(diǎn)的識(shí)別:第一遍,密度估計(jì);第二遍,完成抽樣;第三遍識(shí)別離群點(diǎn)。
　　條件離群點(diǎn)是近年來提出的一類新的離群點(diǎn),已提出的基于近鄰的條件離群點(diǎn)檢測(cè)算法,因參數(shù)設(shè)置過多,且檢測(cè)結(jié)果受參數(shù)影響太大,有一定操作難度,缺乏應(yīng)用性。通過對(duì)現(xiàn)有算法

6、的改進(jìn),去掉不易設(shè)置的參數(shù),提高了算法的應(yīng)用性。
　　從本質(zhì)上講,一個(gè)數(shù)據(jù)點(diǎn)是否為離群點(diǎn),與數(shù)據(jù)點(diǎn)值的大小無關(guān),與兩個(gè)數(shù)據(jù)點(diǎn)的距離也無關(guān),僅與其值在數(shù)據(jù)集中的分布概率有關(guān)。數(shù)據(jù)點(diǎn)的值在數(shù)據(jù)集中出現(xiàn)的概率越低,其離群程度越大,反之,離群程度則越小。信息熵正是刻畫這一特性的工具。從數(shù)據(jù)集中刪除正常數(shù)據(jù)后熵變大,刪除離群數(shù)據(jù)后熵變小,變小的幅度越大,離群程度越高。但目前已提出的基于信息熵的離群檢測(cè)算法其熵計(jì)算方法過于復(fù)雜,為計(jì)算一個(gè)數(shù)據(jù)