基于無監督框架的離群檢測研究

摘 要 離群數據檢測是數據挖掘的一個重要分支，也成為當前研究的熱點。本文對離群數據檢測技術進行了介紹，探討了基于無監督的離群數據檢測技術。對基于統計、基于距離和基于密度的離群檢測方法進行了研究。

關鍵詞 離群數據 數據分析 監督式檢測

基于無監督的離群數據檢測的通常存在一個假設，即離群數據的樣本容量遠遠小于數據集中正常數據或主流數據的樣本容量。實施無監督式的離群數據檢測不需要任何先驗知識，也不需要對標簽數據進行預處理，當發現某個觀察值與正常數據的特征差異較大時，則判斷該數據是離群數據的理由極為充分。基于無監督的離群檢測技術主要分為基于統計的方法和基于最近鄰的方法等。

一、基于統計的離群數據檢測

統計的方法主要是基于對小概率事件的判別來實現對數據樣本異常的鑒別，是目前發展最為成熟的離群數據檢測技術。其主要原理是假定已知的數據集服從某種概率分布，通過不一致檢驗確把那些嚴重偏離分布曲線的記錄標記為離群點。使用基于統計的離群檢測方法的前提是事先獲得數據集的數據分布、分布參數（均值、方差等）和預期的離群數據規模，而這些參數一般獲取比較困難。

基于統計學的離群檢測方法可分為基于分布的檢測方法和基于深度的檢測方法兩類。

基于分布的方法其原理是假設一個標準分布來對數據集進行擬合，在擬合的基礎上觀察數據集的概率分布情況來逐步離群檢測。此類方法的主要缺陷在于難以準確估計多維數據的分布模型。于是Merz（1996）提出了一個以計算機幾何為基礎的基于深度的方法，他通過計算不同層的k-d凸包將外層的對象標記為離群數據。

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

多維離群數據的定義與一元數據集類似，本質上是指具有較低概率的數據。設多維數據集Q=（qij）m€譶，qi=（qi1，qi2，…，qin）為第i個數據對象，m為數據對象個數，n為屬性的維數。可以利用馬氏距離來度量兩個對象間的距離，設Q=（q1，q2，…，qn，）為數據均值，則數據點qi與均值之間的馬氏距離為dists（qi，Q）=（qi，Q）=（qi-Q）S-1（qi-Q）T。其中S為Q的協方差矩陣。該距離與點qi的概率有關，可設一個閾值，當dists（qi，Q）>€%Z時，將qi標記為離群數據進行下一步檢測。

二、基于最近鄰的離群數據檢測

在利用該方法進行離群檢測時，需要計算兩個記錄之間的距離或相似度，可分為兩類：第一類是基于距離，將數據記錄視為多維空間的點，計算記錄與正常數據之間的距離并和某個閾值進行比較來判斷是否為離群數據；第二類是基于密度，對每個記錄估計其相鄰區域的密度，當記錄落入低密度區域則被標記為離群數據。

1、基于距離的離群數據檢測

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

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

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

2、基于密度的離群數據檢測

在基于無監督的離群數據檢測中，當只有一類樣本可以學習時，最簡單也是最直接的方式就是基于密度估計的方法。其主要原理是通過參數或非參數化的方法設定訓練樣本的密度分布模型，根據經驗和實際環境設定密度閾值，通過與閾值的比較來判斷離群數據。

在一元單模數據的離群檢測中，文獻[2]假設樣本服從一元高斯分布：

三、結語

總體來說，無監督式離群檢測方法的優點是不需要先驗知識，操作簡單便于實施。不足是出現誤報的概率較大，時間復雜度高，其性能易受某一密度或距離測度標準影響。在未來的研究中，應更加注重提高檢測的質量和效率。

參考文獻：

[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.

（作者單位：中南財經政法大學信息與安全工程學院）