基于ＳＯＭ的離群數據挖掘集成框架研究
2007-12-31 00:00:00汪加才韓冰青陳大峰
計算機應用研究 2007年10期
摘要：在分析了當前基于距離的離群數據挖掘算法的基礎上，提出了一種基于SOM的離群數據挖掘集成框架，其具有可擴展性、可預測性、交互性、適應性、簡明性等特征。實驗結果表明，基于SOM的離群數據挖掘是有效的。
關鍵詞：離群數據發現；自組織映射；交互式數據挖掘
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2007)10-0044-04
0引言
離群數據挖掘(outlier mining)或稱之為離群點/孤立點發現，用來發現數據集中的小部分對象。這些對象與數據中的一般行為或數據模型有著明顯的不同[1]。其研究成果可廣泛地應用到諸多領域中，包括信用卡詐騙檢測、網絡入侵檢測[2]、電子貿易、醫藥研究、數據清洗等。
早期的離群數據挖掘研究多見于統計領域。基于統計的方法一般只適用于單變量的數據集；雖然某些算法也可以檢測多變量數據，但需要事先指定（假定）數據服從的分布模型。這兩個缺點極大地限制了其應用。
近年來，研究人員又提出了各種各樣的方法[3]。其中，數據庫界所提出的用于離群數據挖掘的方法大致有三種：a）最直接的離群數據挖掘方法是利用數據聚類分析，將聚類后不屬于任何聚簇的數據對象作為離群數據對象[4]。b)基于距離定義離群數據對象[5~7]，一般根據數據對象的最近鄰居來判斷其是否為離群數據。本方法的優點是無須事先知道數據的分布模型，因此可以應用于任何可用某種距離機制量度的特征空間；缺點是定義離群數據對象的參數往往是全局性的。c）針對基于距離的方法存在的問題，提出了基于密度的局部離群數據挖掘方法[8，9]。
Kohonen SOM[10]是一種廣泛應用的聚類算法，可利用其具有的拓撲結構保持、概率分布保持、可視化等優良特性進行交互式可視化離群數據挖掘。本文提出的基于SOM離群數據挖掘框架，使用戶可根據SOM的標記圖和距離矩陣圖[11]選取合適的離群數據挖掘方法，并在SOM上動態選取稀疏分布區域或遠離聚類中心的數據對象(基于SOM的概率分布保持特性)進行深入分析，大大縮小了離群數據挖掘的搜索范圍(基于SOM的拓撲結構保持特性)，提高了效率。它具有可擴展性（scalability）、可預測性(predicatability)、交互性(interactiveness)、適應性(adaptability)、簡明性(conciseness)的SPIAC特征。
1基于距離的離群數據挖掘
基于距離的離群數據(distancebased outlier)取決于數據對象鄰域的定義。即便是對給定的距離量度函數，對離群數據也有不同的定義。
定義1[5] 在包含有N個數據對象的數據集S中，o是離群數據，僅當S中至少有pct部分對象與o的距離大于d。換句話說，如果o在d范圍內有不多于k=N(1-pct)個鄰居，則o是一個帶參數pct和d的DB(pct，d)離群數據。
DB(pct，d)離群數據挖掘方法不要求用戶預先知道數據集服從哪種統計分布模型。實際上，對于恰當定義的pct和d，一個可以被給定的不一致檢驗測出的離群數據同樣可以利用DB(pct，d)檢測出；同時，它克服了基于統計的檢測僅能檢測單個屬性的缺點。
為使計算各點wk值的過程具有可擴展性，文獻[7]提出了HilOut離群數據挖掘算法。該算法采用了先求近似解，然后再從中獲取精確解的策略。為避免直接求解每對點之間的距離，HilOut算法利用Hilbert空間填充曲線將數據集線性化，并基于此線性化數據集上的前驅關系和后繼關系快速地找出各點的k個近似最近鄰。
上述挖掘方法均基于各數據點本身的鄰域來判別其是否是離群數據，其檢測標準是全局的、絕對的。基于LOF(local outlier factor)[8]和LOCI(local correlation integral)[9]的離群數據挖掘方法則通過考查數據點p與其鄰域中其他諸點的差異來反映其離群程度。其檢測標準是局部的、相對的。
定義4[8]數據點p相對于數據點o的k可達距離取p與o的直接距離以及Dk(o)中的較大者。p的局部可達密度為p相對于其k個最近鄰居的k可達距離平均值之倒數。p的局部離群因子LOFk(p)被定義為p的k個最近鄰居局部可達密度的平均值與p本身的局部可達密度之比。
顯然，數據點的局部可達密度越低，或其鄰域的平均局部可達密度越高，則該點的局部離群因子就越大，其離群程度就越強。
2SOM的可視化
2．1SOM及其特征
SOM由輸入層和競爭輸出層組成[10]。將M個輸出神經元排列成規則的二維陣列A。設輸入向量為δ維，對應著δ個輸入神經元。每個輸出神經元均有一權向量與δ個輸入神經元相連接。對于給定輸入向量，訓練過程不僅要調節獲勝單元(與輸入向量距離最近的輸出神經元，也稱為最佳匹配單元)的權向量，還要調節獲勝單元相鄰接的輸出單元的權向量。因此，訓練收斂的SOM可以將高維的輸入空間D按向量間的相似程度映射到低維的輸出空間A中，并具有以下兩個特性：a)拓撲結構保持。將近似的輸入向量映射到A的相近神經元，或反之，A中相近的神經元對應近似的輸入向量。b)概率分布保持。D中輸入向量分布密度高的區域在A中也存在較多的相應神經元。
2．2基于SOM的數據可視化
數據可視化的基本目的是通過有效的圖形特征（位置、形狀、顏色等）使人們容易地從圖形所呈現的大量細節信息中獲取數據特征的定性概念。根據不同的分析目標需求，SOM可以用不同的可視化形式表示，大致可分為SOM標記圖和距離矩陣圖兩類[11]。
2．2．1SOM標記圖
設SOM的輸出層為規則的二維陣列，則可為每個輸出單元做上有意義的標記（如輸出標記、屬性標記、命中標記等），產生SOM標記圖。
1)輸出標記圖SOM理論認為，每個輸出單元可看做為一組相似事例的聚類中心。采用最近鄰分類思想， 輸出單元的輸出標記可以用與其最近鄰的k個事例的輸出表決結果來表示。
2)命中標記圖對于每個事例，可在A中確定對應的獲勝單元。因此，SOM是對事例集D按事例間的相似程度所進行的一個完全劃分，輸出單元所對應的事例子集稱為Voronoi集（簡稱為V集）。將每個輸出單元獲勝次數標注出來，可直觀地觀察輸入空間事例的分布情況。
3)屬性標記圖類似地，可用各V集中的事例來評價δ個屬性中與聚類中心對應權分量的接近程度。最接近的一個或前幾個屬性可以作為該輸出單元的屬性特征。
2．2．2距離矩陣圖
距離矩陣記錄了SOM中相鄰輸出單元間的距離信息，是一種廣為采用的從SOM中探測數據類聚的可視化技術。由于SOM的拓撲結構保持特征，相鄰輸出單元間的距離能反映輸入空間中兩組相鄰的相似事例間的位置關系。在距離矩陣中，每個輸出單元的距離值為其至直接相鄰單元距離的平均值。文獻[12]所定義的U距離矩陣則既有輸出單元至直接相鄰單元間的平均距離，又含有它與各個直接相鄰單元間的個體距離。將不同距離值以不同的顏色、灰度、形狀表示出來，可直觀地觀察數據在SOM上的分布和聚集情況。
3基于SOM的離群數據挖掘
3．1基于距離的離群數據挖掘方法評價
理想的離群數據挖掘方案應該滿足如下的SPIAC特征：a）可擴展性。算法應能高效地從高維的、大量的數據集中發現離群數據。b）可預測性。既可以發現數據集中的離群數據，也可以判斷數據集之外數據的離群程度。c）交互性。不僅能夠正確地識別出離群數據，還應能給出其之所以為離群數據的信息。d）適應性。為發現離群數據而需用戶提供算法運行參數的個數及難易程度。e）簡明性。離群數據定義的簡潔性和挖掘算法實現的簡易性。
前文基于距離的離群數據挖掘方法，均具有定義簡明性的特點；而在可擴展性、交互性、適應性和可預測性等方面存在一定的不足，其根源在于鄰域定義的主觀性和鄰域對象發現的低效率。為使算法具有可擴展性，前文離群數據挖掘方法中提出了基于單元格計數[5]、網格單元計數[9]、劃分刪減[6]、Hilbert空間填充曲線映射[7]等近似求解方案，但大大增加了算法設計與實現的復雜性，損害了結果的準確性和算法實現的簡明性。同時，無論是鄰域半徑參數，還是最近鄰個數參數，應隨求解領域的不同而不同。遺憾的是，利用前文所列方法并不能在運行挖掘算法前得到這些關鍵參數選取的線索。
3．2基于SOM的離群數據挖掘集成框架
實際上，離群數據挖掘僅是數據分析活動中的一個方面。其方法的準確利用及結果的有效獲取建立于用戶對數據分布特征的正確認識。下面所提出的基于SOM的離群數據挖掘集成框架，將以SOM為平臺，指導用戶以交互式、可視化的形式進行數據分布分析與離群數據挖掘。其過程描述如下：
a)規范化數據集D，并隨機生成指定大小或指定比率的抽樣集X。
b)以X為訓練集生成SOM模型。
c)以D為數據源，標注SOM模型，獲取SOM標記圖和距離矩陣圖。
d)利用SOM標注模型，找出輸出層的邊緣單元、群外單元(outstanding cluster，與直接鄰接單元的距離大且命中率小)，將它們的V集作為離群數據候選集。
e)對于邊緣單元或群外單元中的每一數據點，以該單元的V集和其直接鄰接單元的V集作為候選最近鄰集，按前文的離群數據定義進行分析與判斷。
f)對于任一待預測數據，首先確定其最佳匹配單元；然后以該單元的V集和其直接鄰接單元的V集作為候選最近鄰集，按上述定義進行分析與判斷。
g)在SOM上標出所發現的離群數據。用戶可通過LOCI曲線圖等形式逐個分析各數據點。
h)利用步驟c)中得到的屬性標記圖確定各區域的重要屬性列表，并將D、X在此子屬性集上進行投影；然后轉步驟b)以在低維空間中發現離群數據。
3．3基于SOM的離群數據挖掘集成框架評價
用本文提出的SPIAC 指標體系評價該集成框架。
a)可擴展性。以SOM模型快速確定離群數據候選集和候選最近鄰集，大大縮小了搜索空間；以屬性標記圖中的重要屬性列表作為投影向量，可發現隱藏于低維空間中的離群數據，避免了文獻[13]盲目搜索子空間的弊端。
b)可預測性。通過在SOM中尋找最佳匹配單元，以及利用各種SOM標記圖和距離矩陣圖，可快速確定一個新的數據點是否為離群數據及其離群程度，實現預測功能。
c)交互性。SOM提供了展示隱藏于數據集中總體分布信息的途徑，而各數據點的離群指標則從微觀層面上表示了其偏離正常分布或局部分布的程度。基于SOM的數據分析，用戶可動態地選取感興趣數據區域或數據點進行深入分析。
d)適應性。在本框架中用戶可通過各種SOM標記圖和距離矩陣圖探測數據實際分布情況，并選取合適的鄰域半徑和最近鄰數目。同時，由于搜索效率的提高，可以使運行參數的最優化成為可能。
e)簡明性。由于搜索空間的縮小，各種離群數據挖掘算法可以基于其定義直接實現，無須再采用復雜的近似替代方法。
4有效性實驗
為驗證基于SOM的離群數據挖掘，本實驗以Iris數據集作為實驗對象。Iris數據集包括三類事例(1Setosa、2Versicolor、3Virginica，每類各含50個事例)，每個事例均由四個屬性(A1SepalL，A2SepalW，A3PetalL，A4PetalW)描述。SOM輸出層選為6×6的正方形結構，其SOM命中標記圖如圖1(a)所示。取k=5，找出Iris數據集的前10個Dk離群數據和wk離群數據，并在各V集中確定這些離群數據所在單元。其分布情況如圖1(b)(c)所示。一個十分有趣的現象是這些離群數據均分布于邊緣輸出單元。
在圖1的基礎上，以各離群數據所在單元及其直接鄰接單元的V集作為尋找k最近鄰居的局部數據子集。其Dk距離和wk距離(取k最近鄰居距離的平均值)如圖2所示。可見，利用SOM輸出單元的鄰接關系，可以在較小的搜索空間中得到與全域搜索相近的結果。
5結束語
已有的基于距離的離群點挖掘方法都需要進行全空間的鄰域查找操作。為使算法具有可擴展性，往往需采用近似求解方案，這大大增加了算法設計與實現的復雜性，損害了結果的準確性。基于SOM的拓撲結構保持、概率分布保持、可視化等優良特性，本文提出了離群數據挖掘集成框架，可使用戶在數據分析的基礎上，有針對性地選取感興趣區域進行深入分析，具有交互性的特點。同時，由于可在SOM的局部鄰域內尋找k最近鄰居，根據離群數據定義進行算法的設計與實現，使其具有可擴展性、可預測性、簡明性等特征。
參考文獻：
［1］HAN J，KAMBER M.Data mining，concepts and technique[M]. San Francisco: Morgan Kaufmann， 2001.
[2]ESKIN E，AMOLD A，PRERAV M，et al. A geometric framework for unsupervised anomaly detection:detecting intrusions in unlabeled data[C]//Applications of Data Mining in Computer Security.Boston:Kluwer Academic Pablishers，2002.
[3]JIN Wen，TUNG A K H，HAN Jiawei.Mining topn local outliers in large databases[C]//Proc of ACM SIGKDD Int’l Conf on Knowledge Discovery and Data Mining.San Francisco:[s.n.]，2001.
[4]YU D，SHEIKHOLESLAMI G，ZHANG A. Findout:finding outliers in large datasets[J].Knowledge and Information Systems，2002，4(4):387412.
[5]KNORR E，NG R.Algorithms for mining distancebased outliers in large datasets[C]//Proc ofInt’l Conf on Very Large Databases.New York:[s.n.]，1998:392-403.
[6]RAMASWAMY S，RASATOGI R，SHIM K.Efficient algorithms for mining outliers from large data sets[C]//Proc ofACM Int’l Conf Management of Data.Dallas:[s.n.]，2000:427-438.
[7]ANGIULLI F，PIZZUTI C.Outlier mining in large highdimensional data sets[J].IEEE Trans Knowledge and Data Eng，2005，17(2): 203-215.
[8]BREUNIG M M，KRIEGEL H，NG R，et al.LOF:identifying density based local outliers[C]//Proc of ACM Int’l Conf on Managment of Data. Dalles:[s.n.]，2000.
[9]PAPADIMITRIOU S，KITAGAWA，GIBBONS P B.LOCI:fast outlier detection using the local correlation integral[C]//Proc of the 19th International Conference on Data Engineering.Bangalore:[s.n.]，2003:315-326.
[10]KOHONEN T. Selforganizing maps[M]. Berlin:SpringerVerlag，1997.
[11]汪加才，陳奇，趙杰煜，等.VISMiner:一個交互式可視化數據挖掘原型系統[J].計算機工程，2003，29(1):1719.
[12]ULTYSCH A，SIEMON H P.Kohonen’s selforganizing feature maps for exploratory data analysis[C]//Proc ofINNC’90， International Neural Network Conference.Dordrecht， Netherlands:[s.n.]，1990:305-308.
[13]AGGARWAL C，YU P.Outlier detection for high dimensional data[C]//Proc of the SIGMOD.Santa Barbara:ACM Press，2001:37-46.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
