基于矢量量化碼書的離群點檢測方法

摘 要：利用矢量量化碼書作為數據分類模式最優代表集的特點，提出基于碼書的離群點概念，論證了其與經典統計學關于離群點定義的內在聯系。在基于學習的矢量量化碼書生成算法和最近鄰碼字搜索算法基礎上構造了離群點檢測算法。實驗結果表明了提出的關于離群點定義的合理性和算法的有效性。

關鍵詞：矢量量化； 碼書； 離群點檢測算法

中圖分類號：TP391 文獻標志碼：A 文章編號：1001-3695(2008)08-2322-03

Vector quantization approach to outlier detection

HU Yun1， LI Cun-hua1，SUN Zhi-hui2

(1. Dept. of Computer Science， Huaihai Institute of Technology， Lianyungang Jiangsu 222005， China； 2. School of Computer Science Engineering， Southeast University， Nanjing 210018， China)

Abstract:In vector quantization， the codebook is chosen so as to best represent the distributional structure of the dataset of vectors. This characteristic of codebook is suitable for the purpose of outlier detection. This paper defined the concept codebook-based outlier followed by a dedicated analysis of its relation with the definition from statistical discipline. With this definition， the outliers could be found with a two-phase algorithm. Experiments on real world dataset show that this novel approach is quiet promising both on its rationality and effectivity.

Key words：vector quantization; codebook; outlier detection algorithm

目前，與矢量量化(VQ)技術相關的理論和應用研究十分活躍。由于矢量量化技術能利用矢量數據對象間及矢量各分量間的關聯特性有效地消除信息冗余，從而簡化數據處理的復雜性，使它成為廣泛運用于各類復雜數據壓縮、存儲、傳輸與分析的重要技術。隨著數據挖掘技術的發展，研究者對這一數據處理方法開展了深入而廣泛的探索。傳統地，矢量量化過程首先起始于對事先擇取的訓練數據集的聚類、分類研究；然后，通過訓練數據集的分類模式提取相應的特征矢量集(即碼書)來近似地表達全體數據集的數據分布模式。通過特征矢量數據集的提取，矢量量化技術實現了對后續數據簡約高效的描述與處理手段。顯然，矢量量化技術本身所遵循的“訓練→模式提取→后續數據處理”原理與數據挖掘研究的一般過程相吻合，從而成為開展數據挖掘研究的有效工具。

離群點檢測是數據挖掘研究的重要領域之一，它是從大量數據中發現少量的與常規數據模式具有明顯區別的異常數據模式的過程。通過對離群點的檢測和分析，使人們發現并理解異常模式的起源和機理，隨著數據挖掘應用的普及，離群數據挖掘研究的重要意義已經得到國內外學者的普遍認同，成為一個學科領域交叉、應用前景廣闊的研究主題，相關研究成果已被成功應用于各種風險預警和控制領域。

矢量量化技術與離群點檢測技術間存在內在的聯系。從矢量量化技術碼書的構造過程看，它是從隨機選取的初始碼書開始，通過對訓練數據集所包含的數據分類模式的學習逐步達到優化的過程。這種優化使每個碼字趨向其所表達的數據類的核心而遠離離群點可能出現的稀疏區域，以便使全局失真達到最小。由此可見，離群點總是比正常數據點更遠離其所屬區域的碼字。

本文所提出的問題是在給定碼書的前提下，如何利用其發現后續數據集所包含的新穎數據模式。顯然，這一問題的提出具有十分現實的意義。例如，在基于影像的環境監測應用中，對某一區域所拍攝的圖像的突然改變代表著可能的自然災害或生態環境的變化，及時發現這種變化對研究人員具有十分重要的意義。本文就該問題加以探討，提出基于碼書的離群點定義及其相關的發現算法。

1 相關概念與技術

1.1 矢量量化

典型的矢量量化編碼和解碼過程如圖1所示。矢量量化編碼器根據預定的失真測度在碼書中搜索出與輸入矢量之間失真最小的碼字，并用該碼字的索引簡化地表示矢量化的結果。解碼過程則根據碼字的索引在碼書中查找相應碼字，并利用該碼字重構原始矢量。

矢量量化包含兩個基本算法過程，即碼書設計過程和碼字搜索過程。碼書設計是在一定的失真測度意義下，利用預先選定的訓練數據集求解能夠最佳地描述數據分類模式的代表矢量集的過程。顯然，碼書的性能在矢量量化過程中起著決定性的作用。因此，好的碼書設計必須遵循如下兩條準則，即最近鄰準則和最佳碼書準則。可以進一步地解釋為：假設采用平方誤差測度作為失真測度，對給定的具有M個元素的訓練矢量集，碼書設計過程就是尋求把M個訓練矢量分成N類的一種最佳方案(使得全局均方誤差最小)；同時，在獲得最佳分類方案的條件下，選取每個類的最理想代表矢量（通常選擇各類的質心矢量）作為碼書的碼字。

最基礎和直觀的碼書設計方法是窮盡搜索算法。可以證明，從M個元素中求解具有N個碼字的碼書個數為1/N! ∑Ni=0(-1)N-iCiN×iM。通過對所有的碼書進行測試，一定可以求解得到全局最佳的碼書。然而，在N和M較大的情況下，對全部碼書進行測試并選擇是不切實際的。因此，各種碼書設計方法都采取搜索部分碼書的方法得到局部最優或接近全局最優的碼書。其中，LBG算法^[1]是最早提出的基于最優劃分和最佳碼書準則的矢量量化碼書設計算法。此后，各種改進的算法紛紛被提出。此外，研究者基于不同的理論，提出了大量的碼書設計方法，如成對最近鄰算法(pairwise nearest neighbor)^[2]、最大下降法(maximum descent)^[3]、基于神經網絡的方法、基于全局尋優技術的模擬退火算法和基于模糊聚類技術的算法等。

矢量量化碼字搜索算法是指在碼書已經存在的情況下，如何在碼書中搜索與輸入矢量之間失真最小的碼字，即求解Cp，使得d(x，Cp)=min1≤i≤Nd(x，Ci)。顯然，最直觀的搜索算法是窮盡搜索。它通過計算當前矢量與所有碼字之間的失真以查找失真最小的碼字。如果采用平方誤差測度，對于k維矢量，每次失真計算需要k次乘法和2k-1次加法，從而為了對矢量x進行窮盡搜索編碼需要N×K次乘法、N(2k-1)次加法和N-1次比較。可以看出，對于大尺寸碼書和高維矢量，窮盡搜索所需的計算量過于龐大。為此，各種快速碼字搜索算法方面的研究成果不斷出現。概括起來，這些搜索算法可以歸結為五類，即基于不等式判決的算法、變換域碼字搜索算法、金字塔結構碼字搜索算法、自適應算法和降比特率搜索算法。在本文后續的工作中，將采用LVQ (learning vector quantization)算法^[4]實現碼書設計和碼字的快速搜索。

1.2 離群點及其檢測

離群點檢測是從大量常規數據中分離出異常數據的過程。由于離群點往往代表有別于常規的新穎數據模式的出現，離群點檢測在數據挖掘研究中占有重要地位。目前，關于離群點的概念尚沒有公認的形式化定義。事實上，基于不同的觀點或離群點檢測目的不同，離群點的定義也不盡相同。在專業研究領域，Hawkins首先給出了如下的描述性定義^[5]:

定義1 如果一個數據樣本與其他樣本之間存在足以引起懷疑的差異，則稱其為離群點。

顯然，這一定義與人們關于異常事物的理解是一致的。但是，由于它不是一個定量的定義方法，在具體進行離群點檢測時缺乏可操作性。為此，研究者基于不同的應用目的對離群點給出不同的量化定義。例如，以下是Knorr給出的基于距離的定義^[6]:

定義2 給定數據集D和閾值ξ、σ，稱樣本X∈D為離群點。如果存在至多ξ個樣本點位于X的σ距離之內，即|{Y∈D| dist(X，Y)≤σ }|≤ξ。

Knorr的定義是眾多關于離群點問題研究的基礎和出發點，它被廣泛運用于各種離群點檢測算法的構造。

近年來，基于數據挖掘思想的離群點檢測研究獲得了一系列重要的成果，諸多行之有效的檢測算法在廣泛的應用領域中獲得了應用。 其中較具有代表性的工作有基于深度的算法DEEPLOC^[7]、Knorr等人提出的基于距離的算法FindAllOutsD^[6]、Yu等人的基于小波變換方法的算法FindOut^[8]、Breunig等人提出的帶離群度的離群點檢測算法LOF^[9]等。

在上述各種檢測算法中，由于對離群點的定義不同，所獲得的離群點檢測結果也存在差異。例如， Breunig等人^[9]通過定義一個數據點的局部離群因子LOF(local outlier factor)給出基于數據局部分布特征的離群點，所構造的算法能夠反映數據點相對其周圍正常數據在分布稠密程度上的差異。文獻[10]提出基于聚類的離群點概念，構造的算法能夠檢測一個聚類周圍的異常數據點。盡管各種算法在檢測結果上存在一定差異，但它們均從各自的角度揭示了數據集所包含的異常數據的特征。

本文基于矢量量化的思想提出基于碼書的離群點概念，并利用矢量量化技術，開展離群點檢測方面的研究。

2 基于碼書的離群點及其檢測算法

2.1 基于碼書的離群點

定義3 基于碼書的離群點。對于預先給定的非負值ε>0和碼書C = {Ci， i= 1， 2，…，N }，空間Rk中的矢量x稱為離群點。如果d(x，Cp)=min1≤i≤Nd(x，Ci)>ε。其中：Cp是矢量x的最近鄰碼字；d(·，·)為失真度量。

定義3的直觀解釋為：如果一個矢量與到其最近的碼字之間存在足夠大的差異，則可以認為該矢量來自于與原始訓練集不同的數據分布模式。對照Hawkins所給出的定義可見，本文提出的關于離群點的定義方法具有合理性。

依據碼書設計的準則，全體N個碼字是通過將訓練集進行分類并選擇各個類的質心元素構成的。而空間Rk在基于碼書C的量化器Q的量化下轉換為由N個互不交疊的Voronoi-區域，每個碼字是其所屬Voronoi-塊區域的代表元素，如圖2所示。

為了進一步分析基于碼書離群點定義的合理性，筆者將其與統計回歸分析中判別觀測值異常性的學生化殘差方法^[11]加以比較。

一個給定數據觀測值x相對于全體數據集的學生化殘差表達式為Sr=(x-μ)/Se1-hx。其中：μ為樣本均值；Se為標準差；hx∈[0，1]為觀測值x對回歸系數影響程度的杠桿參數。在本文討論的大規模數據分析的情形下，hx可以取值為0。在統計分析中，Sr取值的大小是判別一個觀測值是否為離群點的關鍵統計量。

為簡單起見，本文考慮全體常規數據點集在空間中構成一個近似（超）球體分布。此時，待分析的離群點為散布并遠離超球體中心的稀疏數據點。在碼書僅包含一個碼字的極限情況下，該碼字C必為最靠近統計均值μ（它未必是數據集中的元素）的訓練數據元。此時，根據定義3計算的失真測度d(x，Cp)與學生化殘差Sr之間具有關系d(x，Cp)=S2r×σ。其中:σ是用于碼書訓練數據集的方差。由此可見，恰當選擇定義3中的閾值ε，定義3與學生化殘差方法具有同樣的對于離群點的判別能力。

在碼書包含多個碼字的情況下，d(x，Cp)表示當前點到最近鄰碼字距離的平方。顯然，d(x，Cp)的值越大，統計量Sr越顯著。這種d(x，Cp)與Sr的正耦合關系揭示了定義3中基于碼書離群點的統計意義。

2.2 基于碼書離群點的檢測算法

在2.1節討論的基礎上，筆者轉而討論基于矢量量化方法的離群點檢測問題。基于矢量量化的離群點檢測算法包括矢量量化碼書求解、基于失真度的離群點檢測兩個獨立的階段。在碼書生成的第一階段，運用碼書生成算法和預先選擇的已知分類模式的訓練數據集求得碼書，為離群點檢測做好準備；在第二階段，采用最近鄰搜索算法從待處理的數據集中過濾離群數據點。為了求解碼書，本文采用基于學習矢量量化的LVQ3算法。為此，需要對LVQ3算法作簡要介紹。

學習矢量量化（LVQ）是Kohonen^[4]提出的基于競爭網絡結構的有監督學習碼書設計算法。它利用獎懲迭代機制，在初始碼書的基礎上通過訓練求得最佳碼書。LVQ算法的神經網絡利用訓練樣本對碼書進行初始化，然后采用Winner-takes-it-all規則以尋找獲勝單元。LVQ的改進算法包括LVQ2、LVQ3等。其主要思路是通過引入次獲勝神經元來增加獲得權值訓練的神經元個數，從而提高矢量量化的效率并加速正確的數據分類。其中，LVQ2將輸入向量到獲勝神經元C與次獲勝神經元之間R的距離分別定義為DC和DR，用一個窗來標志：

dC/dR=1-ε

dR/dC=1+ε

其中：ε為響應閾值。當滿足窗口條件時，對兩個相關碼字進行如下調整：

WR(n+1)=WR(n)+η[X-WR(n)]

WC(n+1)=WC(n)-η[X-WC(n)]

在LVQ3中，上述窗口條件改進為

max(dC/dR，dR/dC)>(1-ε)/(1+ε)

在窗口條件滿足時，權值修正的規則為Wj(n+1)=Wj(n)+ε×β(n)×(X-Wj(n))， j∈{C，R}。其中：β(n)的最佳取值為0.1~0.5，可以通過在每次迭代時改變m的值調整學習速率。以下是LVQ3算法的偽代碼：

Procedure codebook generation:

Input: training dataset D， initial codebook C， window width epsilon， learning rate alpha

Output: codebook C

For each x in D，

Find the two closest codewords C1， C2 and

compute distances d1，d2;

If following condition is fulfilled:

min(d1/d2， d2/d1) > (1- epsilon) / (1+ epsilon) then

If x belongs to the same class of one of the C1 and C2， codebook is updated as follows (let C1 belong to the same class as x):

C1 (t+1) = C1 (t) + alpha * (x(t) - C1 (t))

C2 (t+1) = C2 (t) - alpha * (x(t) - C2 (t))

If both C1 and C2 belong to the same class as x， codebook is updated as follows:

C1(t+1)=C1(t)+epsilon*alpha*(x(t)-C1(t))

C2(t+1)=C2(t)+epsilon*alpha*(x(t)-C2 (t))

Otherwise updating is not performed.

在上述碼書生成階段完成后，采用最近鄰搜索算法從待處理的數據集中過濾離群數據點。具體算法如下：

Procedure outlier detection:

Input: dataset D， codebook C， threshold sigma

Output: Outlier data x

while D has unread vector，

x=getcurrentvector(D)，

for each codeword in C，

distortion Computation(x，c)，

update max_distortion(x) if needed，

if max_distortion(x) > sigma，

output x as outlier.

3 實驗結果

為了驗證本文提出的離群點檢測算法的有效性，針對多個測試數據集進行了實驗，分別研究本文提出的算法在離群點檢測精度檢測的時間效率。

a)利用小規模的淋巴系造影數據集(lymphography dataset)在不同碼書大小和失真閾值下的檢測結果的精度。淋巴系造影數據集包含148條由18個屬性（類別標記除外）構成的數據記錄，共分為四類，各類記錄條數分別為2，81，61和4。由于類別1和4僅占全部數據集的4%，可以視為異常數據。實驗中，首先將數據進行歸一化處理并選擇100條來自類別2、3的記錄利用LVQ3算法訓練并得到碼書；利用其余的48條數據(包含類別1、4中的6條記錄)作為測試數據進行檢驗。表1為在不同碼書大小條件下選取ε=0.3時檢測離群數據的數目及誤判百分比。

表1 對淋巴系造影數據集在不同碼書大小條件下檢測的離群點個數 number of

codewordoutliers detectedclass 1，4

detected outliersnormal item

detected as outlierserror

rate/%422612258146816.7167612本實驗表明，通過選擇合適的失真閾值，算法總能檢測出與訓練數據模式有明顯區別的異常點，但是，離群點檢測的精度與碼書的大小密切相關。當碼書過小時，由于類的內聚度弱而導致對類團外圍數據的誤判，通過提高碼字的數量，可以逐步提高檢測的精度。

檢驗在不同失真閾值條件下，利用KDDCup’99數據集驗證檢測結果向數據集所包含的實際離群點個數的逼近趨勢。該數據集包含近五百萬條網絡入侵偵測數據記錄，由7個分類屬性和34個數值型字段組成。從該數據集中隨機選取10 000條正常訪問記錄并對各數值型字段歸一化后作為訓練集，另取10 000條(其中包含126條攻擊記錄)作為測試數據，采用本文算法在碼字個數分別為64、128和256時，研究算法檢測的離群點數隨失真閾值變化的關系，如圖3所示。

實驗在驗證了本文所提出方法有效性的同時，說明了碼書的大小對于檢測精度的影響。當碼書較大時，離群點相對與正常點的區分度顯著提高。此外，失真度閾值（e）的選擇也十分重要，當e選擇合理時，異常的數據點與正常數據點具有明確的區分度，從而可以有效地加以區分。

4 結束語

離群點檢測的任務是從常規數據模式中有效地鑒別新穎的數據模式，而碼書作為表征數據分布模式的代表元集合具有優越的數據模式鑒別能力。本文提出基于碼書的離群點概念并給出了一種有效的離群點檢測方法，是矢量量化技術在新領域應用的有益嘗試。實驗證明了該方法的有效性，有關該定義及相應的離群點檢測算法仍需要進一步加以探討和改進。

參考文獻：

[1]LINDE Y， BUZO A， GRAY R M. An algorithm for vector quantizer design[J]. IEEE Trans on Communications， 1980， 28(1)：702-710.

[2] KAUKORANTA T， FRANTI P， NEVALAINNEM O. Vector quantization by lazy pairwise nearest neighbormethod[J]. Opt Eng， 1999， 28(11)：1862-1868.

[3]MA C K， CHAN C K. Maximum descent method for image vector quantization[J]. Electron Letter， 1991， 27 (12)：1772-1773.

[4]KOHONEN T. The self organizing map[J]. 1990， 78(9)：1464-1480.

[5]HAWKINS D. Identification of outliers[M]. London: Chapman and Hall， 1980.

[6]KNORR E M， NG R T. Algorithms for mining distance-based outliers in large datasets[C]// Proc of the 24th Int Conf on Very Large Data Bases. New York:[s.n.]， 1998：392-403.

[7]JOHNSON T， KWOK I， NG R. Fast computation of 2-dimensional depth contours[C]// Proc of the 4th Int’l Conf on Knowledge Discovery and Data Mining.New York: ACM Press，1998：224-228.

[8]YU D， SHEIKHOLESLANMI G， ZHANG A. Findout: finding out-liers in very large datasets[EB/OL]. http:// www.cse.buffalo.edu/tech-reports/.

[9]BREUNIG M M， KRIEGEL H， NG R T. LOF: identifying density-based local outliers[C]// Proc of ACM SIGMOD Int’l Conf on Mana-gement of Data. Dallas: ACM Press， 2000:93-104.

[10]HE Z Y， XU X F， DENG S C. Squeezer: an efficient algorithm for clustering categorical data[J]. Journal of Computer Science and Technology， 2002， 17(5): 611-624.

[11]TAMHANE A C. A note on the use of residuals for detecting an out-lier in linear regression[J]. Biometrika， 1982， 69(2): 488-489.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文