基于無(wú)監(jiān)督框架的離群檢測(cè)研究

摘 要 離群數(shù)據(jù)檢測(cè)是數(shù)據(jù)挖掘的一個(gè)重要分支，也成為當(dāng)前研究的熱點(diǎn)。本文對(duì)離群數(shù)據(jù)檢測(cè)技術(shù)進(jìn)行了介紹，探討了基于無(wú)監(jiān)督的離群數(shù)據(jù)檢測(cè)技術(shù)。對(duì)基于統(tǒng)計(jì)、基于距離和基于密度的離群檢測(cè)方法進(jìn)行了研究。

關(guān)鍵詞 離群數(shù)據(jù) 數(shù)據(jù)分析 監(jiān)督式檢測(cè)

基于無(wú)監(jiān)督的離群數(shù)據(jù)檢測(cè)的通常存在一個(gè)假設(shè)，即離群數(shù)據(jù)的樣本容量遠(yuǎn)遠(yuǎn)小于數(shù)據(jù)集中正常數(shù)據(jù)或主流數(shù)據(jù)的樣本容量。實(shí)施無(wú)監(jiān)督式的離群數(shù)據(jù)檢測(cè)不需要任何先驗(yàn)知識(shí)，也不需要對(duì)標(biāo)簽數(shù)據(jù)進(jìn)行預(yù)處理，當(dāng)發(fā)現(xiàn)某個(gè)觀察值與正常數(shù)據(jù)的特征差異較大時(shí)，則判斷該數(shù)據(jù)是離群數(shù)據(jù)的理由極為充分?；跓o(wú)監(jiān)督的離群檢測(cè)技術(shù)主要分為基于統(tǒng)計(jì)的方法和基于最近鄰的方法等。

一、基于統(tǒng)計(jì)的離群數(shù)據(jù)檢測(cè)

統(tǒng)計(jì)的方法主要是基于對(duì)小概率事件的判別來(lái)實(shí)現(xiàn)對(duì)數(shù)據(jù)樣本異常的鑒別，是目前發(fā)展最為成熟的離群數(shù)據(jù)檢測(cè)技術(shù)。其主要原理是假定已知的數(shù)據(jù)集服從某種概率分布，通過(guò)不一致檢驗(yàn)確把那些嚴(yán)重偏離分布曲線的記錄標(biāo)記為離群點(diǎn)。使用基于統(tǒng)計(jì)的離群檢測(cè)方法的前提是事先獲得數(shù)據(jù)集的數(shù)據(jù)分布、分布參數(shù)（均值、方差等）和預(yù)期的離群數(shù)據(jù)規(guī)模，而這些參數(shù)一般獲取比較困難。

基于統(tǒng)計(jì)學(xué)的離群檢測(cè)方法可分為基于分布的檢測(cè)方法和基于深度的檢測(cè)方法兩類。

基于分布的方法其原理是假設(shè)一個(gè)標(biāo)準(zhǔn)分布來(lái)對(duì)數(shù)據(jù)集進(jìn)行擬合，在擬合的基礎(chǔ)上觀察數(shù)據(jù)集的概率分布情況來(lái)逐步離群檢測(cè)。此類方法的主要缺陷在于難以準(zhǔn)確估計(jì)多維數(shù)據(jù)的分布模型。于是Merz（1996）提出了一個(gè)以計(jì)算機(jī)幾何為基礎(chǔ)的基于深度的方法，他通過(guò)計(jì)算不同層的k-d凸包將外層的對(duì)象標(biāo)記為離群數(shù)據(jù)。

在一元數(shù)據(jù)集的離群檢測(cè)中，給定數(shù)據(jù)集為P=（pij）m€譶，pi=（pi1，pi2，…，pin）為第i個(gè)數(shù)據(jù)對(duì)象，m為數(shù)據(jù)對(duì)象個(gè)數(shù)，n為屬性的維數(shù)，對(duì)于任意j∈{1，2，…，n}，分別就一維子空間L1（j）上的投影數(shù)據(jù)子集進(jìn)行分析，對(duì)能夠反映其屬性的概括性指標(biāo)如位置、不對(duì)稱、可變性以及峰度等進(jìn)行觀察，判斷其是否落入離群范疇。

多維離群數(shù)據(jù)的定義與一元數(shù)據(jù)集類似，本質(zhì)上是指具有較低概率的數(shù)據(jù)。設(shè)多維數(shù)據(jù)集Q=（qij）m€譶，qi=（qi1，qi2，…，qin）為第i個(gè)數(shù)據(jù)對(duì)象，m為數(shù)據(jù)對(duì)象個(gè)數(shù)，n為屬性的維數(shù)。可以利用馬氏距離來(lái)度量?jī)蓚€(gè)對(duì)象間的距離，設(shè)Q=（q1，q2，…，qn，）為數(shù)據(jù)均值，則數(shù)據(jù)點(diǎn)qi與均值之間的馬氏距離為dists（qi，Q）=（qi，Q）=（qi-Q）S-1（qi-Q）T。其中S為Q的協(xié)方差矩陣。該距離與點(diǎn)qi的概率有關(guān)，可設(shè)一個(gè)閾值，當(dāng)dists（qi，Q）>€%Z時(shí)，將qi標(biāo)記為離群數(shù)據(jù)進(jìn)行下一步檢測(cè)。

二、基于最近鄰的離群數(shù)據(jù)檢測(cè)

在利用該方法進(jìn)行離群檢測(cè)時(shí)，需要計(jì)算兩個(gè)記錄之間的距離或相似度，可分為兩類：第一類是基于距離，將數(shù)據(jù)記錄視為多維空間的點(diǎn)，計(jì)算記錄與正常數(shù)據(jù)之間的距離并和某個(gè)閾值進(jìn)行比較來(lái)判斷是否為離群數(shù)據(jù)；第二類是基于密度，對(duì)每個(gè)記錄估計(jì)其相鄰區(qū)域的密度，當(dāng)記錄落入低密度區(qū)域則被標(biāo)記為離群數(shù)據(jù)。

1、基于距離的離群數(shù)據(jù)檢測(cè)

基于距離的離群數(shù)據(jù)最早由Knorr和Ng（1998）提出，S.Ramaswamy（2000）和S.D.Bay（2003）等人對(duì)此進(jìn)行了改進(jìn)。其原理可用以下定義描述：

定義2.1.1 已知數(shù)據(jù)集X，X={x1，x2，…，xn}，o為數(shù)據(jù)對(duì)象，如果數(shù)據(jù)集i中有pct部分?jǐn)?shù)據(jù)Y，Y€H裍，y∈Y遠(yuǎn)離于對(duì)象o及與之距離為的鄰域，稱o為基于距離的離群數(shù)據(jù)，表示為DB（pct，1）。

基于距離的離群數(shù)據(jù)檢測(cè)技術(shù)包含并改進(jìn)了基于統(tǒng)計(jì)的思想，其優(yōu)勢(shì)在于當(dāng)數(shù)據(jù)集難以估計(jì)出概率分布模型時(shí)，依然能檢測(cè)出離群數(shù)據(jù)，而且在高維空間中算法效率較高。在實(shí)施檢測(cè)時(shí)，事先給出數(shù)據(jù)對(duì)象間距離的測(cè)度，一旦給定參數(shù)pct和1即可實(shí)施離群檢測(cè)。一般采用歐氏距離、曼哈頓距離和蘭氏距離作為距離測(cè)度?；诰嚯x的離群數(shù)據(jù)檢測(cè)技術(shù)的最大缺陷在于確定參數(shù)pct和1比較困難，致使輸出結(jié)果不穩(wěn)定，需要多次輸入pct和1測(cè)試，增加了算法的復(fù)雜度。為克服該缺陷，引入距離和（distance sum-based）的概念。其與DB（pct，1）不同的是，該方法的原理是測(cè)量數(shù)據(jù)集中n個(gè)數(shù)據(jù)記錄兩兩之間的距離1ij，形成距離矩陣R，令pi=1ij，值越大，pi則對(duì)象i與其他對(duì)象的距離越遠(yuǎn)，若設(shè)預(yù)期的離群點(diǎn)個(gè)數(shù)為X，則距離和最大的X個(gè)對(duì)象即可被判定為離群數(shù)據(jù)。

2、基于密度的離群數(shù)據(jù)檢測(cè)

在基于無(wú)監(jiān)督的離群數(shù)據(jù)檢測(cè)中，當(dāng)只有一類樣本可以學(xué)習(xí)時(shí)，最簡(jiǎn)單也是最直接的方式就是基于密度估計(jì)的方法。其主要原理是通過(guò)參數(shù)或非參數(shù)化的方法設(shè)定訓(xùn)練樣本的密度分布模型，根據(jù)經(jīng)驗(yàn)和實(shí)際環(huán)境設(shè)定密度閾值，通過(guò)與閾值的比較來(lái)判斷離群數(shù)據(jù)。

在一元單模數(shù)據(jù)的離群檢測(cè)中，文獻(xiàn)[2]假設(shè)樣本服從一元高斯分布：

三、結(jié)語(yǔ)

總體來(lái)說(shuō)，無(wú)監(jiān)督式離群檢測(cè)方法的優(yōu)點(diǎn)是不需要先驗(yàn)知識(shí)，操作簡(jiǎn)單便于實(shí)施。不足是出現(xiàn)誤報(bào)的概率較大，時(shí)間復(fù)雜度高，其性能易受某一密度或距離測(cè)度標(biāo)準(zhǔn)影響。在未來(lái)的研究中，應(yīng)更加注重提高檢測(cè)的質(zhì)量和效率。

參考文獻(xiàn)：

[1] S Ramaswamy，R Rastogi，K Shim.Efficient Algorithms for Mining Outliers from Large Data Sets[C].In：Proceedings of the ACM SIGMOD Conference，2000：473-438.

[2]DUAD R，HART P，STORK D.Pattern classification[M].2nd ed.New York：John Wiley Sons，2001.

（作者單位：中南財(cái)經(jīng)政法大學(xué)信息與安全工程學(xué)院）