◎王晨皓

從數(shù)學(xué)的角度初步看離群點檢測算法

◎王晨皓

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

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

離群點檢測

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

離群點檢測算法中的數(shù)學(xué)應(yīng)用

數(shù)學(xué)理論是數(shù)據(jù)分析與預(yù)測的基礎(chǔ)，在大數(shù)據(jù)相關(guān)技術(shù)中，無論是數(shù)據(jù)的采集、取樣、存儲，還是數(shù)據(jù)挖掘與處理，都離不開數(shù)學(xué)模型與數(shù)學(xué)理論的支持，在離群點檢測算法中，更是應(yīng)用了包括統(tǒng)計學(xué)、幾何學(xué)在內(nèi)的大量數(shù)學(xué)理論。

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

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

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

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

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

離群點檢測是數(shù)據(jù)挖掘的重要任務(wù)，隨著大數(shù)據(jù)時代的到來，離群數(shù)據(jù)的檢測與分析在防范網(wǎng)絡(luò)犯罪、分析市場走向等方面發(fā)揮著愈來愈重要的作用。現(xiàn)有的離群點數(shù)據(jù)檢測技術(shù)是基于包括統(tǒng)計學(xué)、幾何學(xué)在內(nèi)的大量數(shù)學(xué)知識和數(shù)學(xué)模型發(fā)展而來的。數(shù)學(xué)理論是離群點數(shù)據(jù)檢測技術(shù)的基礎(chǔ)，新的離群點數(shù)據(jù)檢測技術(shù)的提出必然與提出新的數(shù)學(xué)模型息息相關(guān)，是當前研究人員的研究重點。

（作者單位：鄭州市第四中學(xué)）