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

◎王晨皓

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

◎王晨皓

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

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

離群點(diǎn)檢測(cè)

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

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

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

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

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

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

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

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

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

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