離群檢測算法研究.pdf

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

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

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

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

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

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