從數學的角度初步看離群點檢測算法

◎王晨皓

從數學的角度初步看離群點檢測算法

◎王晨皓

目前，大數據技術在全世界范圍內迅猛發展，在金融、電信、交通、醫療等領域得到了廣泛應用，全球包含個人電腦、平板電腦、智能手機、可穿戴終端及物聯網終端等聯網設備將超過500億臺，全年產生的數據總量是一個天文數字，如此數量、多樣化的數據，對各行各業來說存在著巨大的潛在價值，然而由于大數據的4V特性（大體量、多樣性、時效性和精確性）決定了大數據的處理和利用難度高，傳統的數據分析技術無法滿足應用需求，數據挖掘技術應運而生。

數據挖掘是從大量數據中提取出人們所關心的有價值的數據信息，是一門涵蓋了統計學、機器學習、人工智能、圖像處理、數據庫等多門學科的交叉學科，其中數學理論是數據分析與研究的技術。離群點檢測正是數據挖掘的重要任務之一，在完成離群點數據檢測與分析的過程中，應用了大量的數學模型與數學方法，是數學方法針對數據時代新應用的特殊需求的一次新發展。

離群點檢測

離群點數據是與大多數數據在某些特征空間上有所差異的數據，其產生途徑大致有兩種：一是人為誤差或測量設備故障而產生導致的異常數據，會導致數據分析結果的錯漏；二是由另外一種完全不同的機制產生的數據。第一類數據在數據分析中是沒有意義的，它的存在反而會對數據分析的結果產生不良的影響，通過離群點檢測技術剔除此類離群數據是進行數據挖掘的前提。第二類數據在數據分析中占有重要的意義，由于其產生機制的不同，在一些特殊的領域，如電子商務犯罪、疾病診斷、網絡攻防等研究領域，離群點的存在往往蘊含一些特殊的信息，具有極高的研究意義。離群點檢測和分析技術就是采用一定的方法對離群點數據進行查找并分析其成因與屬性的技術。

離群點檢測算法中的數學應用

數學理論是數據分析與預測的基礎，在大數據相關技術中，無論是數據的采集、取樣、存儲，還是數據挖掘與處理，都離不開數學模型與數學理論的支持，在離群點檢測算法中，更是應用了包括統計學、幾何學在內的大量數學理論。

基于統計的離群點檢測。基于統計的離群點檢測算法是基于統計學知識，通過對事件發生的概率判別數據點是否為離群點。這類離群點檢測算法須首先定義數據的概率分布或概率模型，然后將數據特征與概率模型進行一致性檢驗，不符合概率模型的數據為離群點。此算法是最經典的離群點檢測算法，便于理解，實現簡易。其難點在于概率模型的設定往往是根據數據集先驗知識采樣確定的，無法完全確定數據的概率分布，在選擇不同的采集點時選出的離群點不同。另外，此種方法要求待分析數據必須滿足某種已知的概率分布模型（如正態分布、拉普拉斯分布等），模型的參數（如均值、標準差等）難以確定且對分析結果影響較大。利用統計學方法進行離群點檢測具有一定的局限性，比較適合挖掘單變量數值型數據，然而在大數據時代，大部分數據挖掘需求對多元化數據進行分析，發現多維數據的離群點，其概率分布難以符合目前已有的標準概率分布，基于統計的離群點檢測算法難以按照需求發現所有離群點。

基于分形理論的離群點檢測。基于分形理論的離群點檢測算法是采用分形幾何的相關概念，通過數據集的多維特征分進行分形，通過數據集的嵌入維和內在維判別數據點是否為離群點。此種離群點檢測算法采用多維分形維數對多維空間中多樣化的數據進行離群檢測，以推廣GP（Grassberger-Procaccia）算法計算多重分形廣義維數譜，通過關聯積分得出關聯維數。在度量離群點時，首先計算包含離群點的數據集的離群度DIM（D,D）和剔除了目標數據p的數據集的離群度DIM（D-p,D），兩結果相比即為數據p的離群度OD(p,D)，此數值越高，則p為離群點的概率越大。當超過事先設定的權值時，將p設定為離群點。基于分性理論的離群點檢測算法在高維空間上的離群數據挖掘看做最優化分割問題進行處理，有效地解決了多樣化、多特征數據的離群點檢測，但是對每個數據點均需計算計算其離群度，算法時間復雜度高達O(n3)，效率較低。

基于距離的離群點檢測。基于距離的離群點檢測算法是應用空間幾何模型，將數據看作高維空間中的點，每兩個數據點之間的距離即為這兩個數據的偏差值，離群點即為數據集中與大多數點距離大于規定閾值的點。這種方法通俗易懂，便于理解。通常情況下，數據集D中有不少于p個對象與對象o的距離大于dm，則稱對象o為以參數p和距離dm為參數的離群點，寫作D（p,dm）。在對數據進行離群點檢測時，可以根據數據的規模和特性以及數據處理需要，定義參數p和dm，經過算法計算即可檢測離群點。目前已經成熟的檢測算法有三種：一是基于索引的算法，二是基于單元的算法，三是嵌套—循環算法。在理論上，這幾種算法的時間復雜度最高為O(kn2)，效率較差，但可處理多維數據模型，這類算法的缺點是受閾值限制，且僅能檢測全局離群點。

基于密度的局部離群點檢測。基于密度的局部離群點檢測算法結合多維幾何理論，檢測局部離群點的算法。這種方法將數據對象作為多維空間獨立的點，這些點是有自己的集群的，即多個距離近的數據對象為一數據集。在計算時，通過數據對象周圍單位空間內數據對象的個數（即密度）作為此數據對象是否為離群點的判斷標準。由于取單位空間操作較難達成，在計算時，通常選取與目標對象距離最近的n個數據對象，并計算其與目標對象的距離之和，結果較大的密度低。它與其他離群點檢測算法不同，不僅僅簡單的判斷數據對象是否為離群點，更建立了一種評估數據對象離群程度的標準，即局部離群因子（LOF）。數據對象P的局部離群因子的計算過程如下：（1）計算數據集中所有數據對象到P的距離，通常采用的計算方式有三種：歐幾里得距離、曼哈頓距離和明考斯距離。（2）從上述結果中選出n個，選中其中最大的一個為P的n距離。（3）計算P的距離鄰域，以及被選中的n個數據點的距離。（4）通過距離計算P的局部密度和局部離群因子。LOF算法的主要缺點在于計算復雜度較高，但是經過基于索引的方法優化后，計算復雜度為O(nlogn)，效率得到了較大提高。

基于聚類的離群點檢測。聚類分析是將研究對象的集合按照既定規則分成多個類的過程，是一種將多種數學模型應用化的統計分析方法，現大規模應用于數據挖掘領域。聚類算法可以高效的將數據對象集劃分成為具有多個具有相似特征的微聚類，在劃分完成后，不屬于任何聚類的數據對象即為離群點。基于聚類的離群點檢測算法過程是首先利用聚類算法將給定的數據對象進行運算，得出離群數據對象和聚類，然后判斷離群對象在各個一維子空間內對各個聚類投影的離群情況，得出離群對象的相關信息。這類方法基于線性和K均值（接近線性復雜度均值）的聚類技術可以高效的完成離群點的分類，并將具有相同離群屬性的離群點劃分到同一離群簇，便于分析其離群特性，但同樣的，檢測到的離群點往往非常依賴所用的簇的個數和數據中離群點的存在性，且產生的簇的質量對此類方法產生的離群點的質量影響較大。

離群點檢測是數據挖掘的重要任務，隨著大數據時代的到來，離群數據的檢測與分析在防范網絡犯罪、分析市場走向等方面發揮著愈來愈重要的作用。現有的離群點數據檢測技術是基于包括統計學、幾何學在內的大量數學知識和數學模型發展而來的。數學理論是離群點數據檢測技術的基礎，新的離群點數據檢測技術的提出必然與提出新的數學模型息息相關，是當前研究人員的研究重點。

（作者單位：鄭州市第四中學）