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

摘 要：利用矢量量化碼書作為數(shù)據(jù)分類模式最優(yōu)代表集的特點，提出基于碼書的離群點概念，論證了其與經(jīng)典統(tǒng)計學(xué)關(guān)于離群點定義的內(nèi)在聯(lián)系。在基于學(xué)習(xí)的矢量量化碼書生成算法和最近鄰碼字搜索算法基礎(chǔ)上構(gòu)造了離群點檢測算法。實驗結(jié)果表明了提出的關(guān)于離群點定義的合理性和算法的有效性。

關(guān)鍵詞：矢量量化； 碼書； 離群點檢測算法

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

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

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

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

1 相關(guān)概念與技術(shù)

1.1 矢量量化

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

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

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

矢量量化碼字搜索算法是指在碼書已經(jīng)存在的情況下，如何在碼書中搜索與輸入矢量之間失真最小的碼字，即求解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次比較。可以看出，對于大尺寸碼書和高維矢量，窮盡搜索所需的計算量過于龐大。為此，各種快速碼字搜索算法方面的研究成果不斷出現(xiàn)。概括起來，這些搜索算法可以歸結(jié)為五類，即基于不等式判決的算法、變換域碼字搜索算法、金字塔結(jié)構(gòu)碼字搜索算法、自適應(yīng)算法和降比特率搜索算法。在本文后續(xù)的工作中，將采用LVQ (learning vector quantization)算法^[4]實現(xiàn)碼書設(shè)計和碼字的快速搜索。

1.2 離群點及其檢測

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

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

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

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

Knorr的定義是眾多關(guān)于離群點問題研究的基礎(chǔ)和出發(fā)點，它被廣泛運用于各種離群點檢測算法的構(gòu)造。

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

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

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

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

2.1 基于碼書的離群點

定義3 基于碼書的離群點。對于預(yù)先給定的非負值ε>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的直觀解釋為：如果一個矢量與到其最近的碼字之間存在足夠大的差異，則可以認為該矢量來自于與原始訓(xùn)練集不同的數(shù)據(jù)分布模式。對照Hawkins所給出的定義可見，本文提出的關(guān)于離群點的定義方法具有合理性。

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

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

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

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

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

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

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

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

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

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

其中：ε為響應(yīng)閾值。當滿足窗口條件時，對兩個相關(guān)碼字進行如下調(diào)整：

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+ε)

在窗口條件滿足時，權(quán)值修正的規(guī)則為Wj(n+1)=Wj(n)+ε×β(n)×(X-Wj(n))， j∈{C，R}。其中：β(n)的最佳取值為0.1~0.5，可以通過在每次迭代時改變m的值調(diào)整學(xué)習(xí)速率。以下是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.

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

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 實驗結(jié)果

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

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

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

codewordoutliers detectedclass 1，4

detected outliersnormal item

detected as outlierserror

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

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

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

4 結(jié)束語

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

參考文獻：

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

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