離群檢測算法研究.pdf

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

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

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

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

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

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