基于流形學習的異常檢測算法研究

劉凱偉，張冬梅

中國地質大學 計算機學院，武漢 430074

基于流形學習的異常檢測算法研究

劉凱偉，張冬梅

中國地質大學 計算機學院，武漢 430074

1 引言

化探異常識別是成礦預測和資源評價的關鍵。傳統地質統計方法具有無偏、最優等特點，但要求數據呈正態分布，而實際應用往往不符合統計假設；近年來分形理論被大量應用于地球化學異常確定，但基本思路還是采取單元素值來確定背景值，存在需要平滑處理數據以及對樣品中特高品位敏感等問題。因此，尋找能體現地球化學數據空間結構和非線形特征的異常識別方法具有重要的研究價值。

針對地質異常現象的不平穩性，即地理空間的有礦樣本的數目遠遠小于無礦樣本的數目，化探異常識別從本質上來看是一種不均衡數據的分類問題。傳統機器學習分類算法往往基于三點假設[1]：（1）追求最大分類正確率；（2）不同分類錯誤代價相同；（3）數據集中不同類別包含的樣本數目大致相當。在區域化探數據集中有礦、無礦樣本數目并不均衡，不符合上述假設，如果采用傳統研究方法，處理往往會“偏向”多數類樣本即無礦樣本而忽略少數類樣本即有礦樣本，導致將測試樣本全部判別為大類，雖然總體分類正確率很高但小類有礦異常樣本識別率卻非常低。而在成礦識別中，人們更關心的是少數類即有礦樣本的分類正確率，因此有效提高少數類的分類性能是成礦異常識別亟待解決的問題。本研究擬將非均衡數據分類問題引入到區域化探異常識別中。

但是隨著數據維數的不斷增加，面對這些數據集，如何從中發現其中的異常數據仍然是一個難題。為了更好地理解和處理這些高維復雜數據，數據降維技術被廣泛應用。數據降維的目的是找出高維數據中隱藏的低維結構，即將原始高維空間映射到低維空間中。目前，在成礦預測中線性數據降維方法仍然是數據分析處理中使用最為廣泛的降維方法，如主成分分析（Principal Component Analysis，PCA）[2]等。主成分分析從20世紀90年代至今，在成礦預測中取得了較好的效果。2006年，宋明輝等[3]以東昆侖祁漫塔格研究區為實驗區，提出了利用比值分析和主成分分析（PCA）的方法對預測單元進行蝕變遙感異常信息提取，取得了較好的效果。2009年，郭云開[4]等提出一種基于局部能量規則的第二代Curvelet變換和主成分分析（PCA）相結合的影像融合的方法，實驗也表明在異常信息的提取上取得了較好的效果。2010年，王瑞國[5]等以內蒙古錫林郭勒盟布魯特地區為研究區，采用PCA和比值圖像處理方法，進行試驗區的成礦預測，取得了較好的實際運用效果。但是，地學數據如化探數據，往往是非線性的高維數據，利用線性降維方法很難發掘這類數據的內在結構及非線性分布特征。

為了彌補線性降維方法的不足，針對高維數據的非線性特征，近年來出現了很多非線性降維方法。流形學習是典型的非線性降維方法[6]，通過流形學習方法建立高維-低維映射模型，能更加合理地顯示高維數據集的內在結構。因此本文擬將流形學習算法運用在異常檢測中，在非線性降維的同時保持原樣本空間的分布特性，并在此基礎上，將集成學習AdaCost[7]方法嵌入到流形學習算法中，按分類的錯誤率更新樣本的權值，通過關注分類錯誤的樣本，進一步提高少數類樣本的分類性能和異常檢測的準確率。本文以UCI三組不均衡數據以及另外一組的地學數據為研究對象，進行仿真實驗。實驗結果表明本文算法預測結果在評價指標上好于傳統方法，能更準確地找出異常。

2 流形學習算法理論

2.1 流形學習算法

定義1（流形）流形是微分幾何學的一個概念，最早由Riemann在1854年提出，其定義為：設M是一個Hausorff拓撲空間，若M的每一點P都有一個開鄰域U?M，使得U和n維歐氏空間Rn中的一個開子集同胚，則稱M是一個n維拓撲流形，簡稱為n維流形。

定義2（流形學習）流形學習過程定義為：設Y?Rd是一個低維流形，f:Y→RD是一個光滑嵌入，其中D＞d。數據集{yi}是隨機生成的，且經過f映射為觀察空間的數據{xi=f(yi)}。流形學習就是給定觀察樣本集的xi條件下重構f和{yi}。

流形學習算法本質是一種非線性的降維方法，即從高維采樣數據中恢復低維流形結構，并求出相應的嵌入映射，把高維空間中的數據在低維空間中重新表示，以實現維數約簡或者數據簡化。常見的流形學習算法有LLE算法[8]、ISOMAP算法[9]、LE算法[10]等。本文主要采取的是LLE算法。

2.2 LLE算法分析

LLE算法的基本步驟如下：

步驟1給的數據集為X，其中Xi∈RD，i=1，2，…，n，n為樣本總數，D為原始空間維數，搜索數據集中每個Xi的K個最近鄰，{Xi1，Xi2，…，Xik}，Xik∈X，K＜n，對于計算每一個點Xi的近鄰點，一般采用K近鄰或者ξ鄰域。

3 異常分類算法理論基礎

3.1 代價敏感分類

目前的異常分類算法都強調分類的準確率，并且基于這樣一個假設，即所有錯誤分類的代價都是相等的。但在很多實際應用中，不同類型的錯誤往往對應不同的分類代價，例如在100個人中，只有1人患有癌癥，一個非代價敏感學習算法可能將所有人都分到“健康”這一類，雖然準確率很高，但這個模型是無用的，而且把一個癌癥患者診斷為健康的代價也遠遠高于把一個健康人診斷為絕癥的代價。代價敏感分類就是為不同類型的錯誤分配不同的代價，使得在分類時，高代價錯誤產生的數量和錯誤分類的代價總和最小。

3.2 AdaCost算法

AdaCost代價算法是一種高效的誤分類代價敏感算法[11]，它是Adaboost算法的一種改進。AdaCost算法保持了Adaboost算法的核心理論，并在權值調整中加入了代價調整函數使其成為了代價敏感算法。其基本思想是利用大量的弱分類器通過一定方法組合起來，這樣可以得到一個分類性能很強的強分類器。AdaCost算法的具體描述如下所示。

輸入：數據集S={(x1，y1，c1)，…，(xi，yi，ci)，…(xm，ym，cm)}，其中ci∈[0，1]，yi∈{0，1}，迭代次數T，弱分類學習算法WeakLearn；

輸出：強分類器H(x)。

Step 2循環迭代；t＜T時循環：

Step 2.1對帶有權重的訓練樣本用WeakLearn算法進行訓練學習，得到一個弱分類器ht；

Step 2.3如果ξt≥0.5或者εt=0，則令t=1，返回Step 2；

Step 2.4計算加權參數αi=0.5?[ln(1-εt)/εt]，選擇代價調整函數βi=β(sign(yih(xi))，ci)；

Step 2.5更新樣本的權值，Zi為歸一化因子：

wt+1(i)=wt(i)exp[-αiyiht(xi)βi]/Zi

Step 2.6t=t+1。

4 基于流形學習的異常檢測算法

基于流形學習的異常檢測算法首先通過流形學習降維方法生成新的樣本數據，新的樣本數據集的格式與Ada-Cost算法要求輸入的數據集格式完全一致，本文提出的算法具備很好的連貫性。因此可以直接將集成學習AdaCost算法嵌入到新數據集中，按分類的錯誤率更新樣本的權值，進一步提高少數類樣本的分類性能，進而提高異常分類的準確率，檢測出異常。基于流形學習的AdaCost代價敏感算法基本框架如下所示。

輸入：數據集X={x1，x2，…，xn∈RN}，迭代次數T，弱分類學習算法WeakLearn；

輸出：強分類器H(x)。

Step 1根據流形學習的降維算法LLE，生成維數較少的數據樣本。

Step 3循環迭代；t＜T時循環：

Step 3.1對將為后的的數據集用WeakLearn算法進行訓練學習，得到一個弱分類器ht；

Step 3.3計算加權參數αi=0.5?[ln(1-εt)/εt]，選擇代價調整函數βi=β(sign(yih(xi))，ci)；

Step 3.4更新樣本的權值，Zi為歸一化因子：

Step 3.5t=t+1；

5 仿真實驗

5.1 實驗數據

為了驗證提出的算法的效果，本文選取UCI數據集中的三組數據以及一組地學化探數據進行仿真實驗，從UCI提供的數據集中選擇了三組非均衡數據集，這些數據集是國際通用、權威的標準測試數據集。

另外還選取云南個舊錫銅多金屬礦床化探數據為研究對象，個舊礦區分布在東北、西北和南北方向多個褶皺斷裂帶的交匯處[12]，個舊地區是錫銅多金屬成礦區。本文選取Sn、Cu、Pb、Zn等39種共計524條1∶20萬系沉淀物進行仿真實驗，其中已經勘明的有礦點41個，無礦點483個，無礦與有礦的不平衡率為11.78（比例為483∶41），是典型非均衡數據集，符合實驗要求。

5.2 仿真實驗環境與評價指標

5.2.1 實驗仿真環境

本實驗使用PC機配置為Pentium?2.92 GHz中央處理器，2 GB內存，操作系統是Windows XP；LLE程序用Matlab語言編制，在Matlab7.0平臺上運行，SMO與AdaCost程序在WEKA平臺上運行。

5.2.2 實驗評價指標

當分類的數據是不均衡數據時，傳統的分類方法往往偏向多數類樣本，這樣會導致少數類的識別率很差，但在實際應用中人們更加關注少數類的分類正確性。因此，單純將分類精度作為不均衡數據的評價指標并不合理。為了更全面地反映化探異常識別的性能，本文主要引入AUC、G-mean復合指標進行評價。復合指標的定義如下：

定義3（G-mean指標）G-mean也稱幾何平均準則，由Kubat和Matwin在1997年提出，是一種有效衡量不平衡數據分類效果的準則。

其中，acc+為少數樣本的精度，acc-多數樣本的精度[1]。如果acc+精度大而acc-精度小，則G-mean值較小；兩者精度都很大且保持平衡時，G-mean值較大。G-mean指標綜合考慮了兩類樣本的精度，能更好地衡量不平衡數據分類器的性能。

定義4（AUC指標）ROC曲線能較全面地描述分類器的性能，由于不能定量分析，采用ROCArea值表示[13-14]。ROCArea值表示ROC曲線下的面積（AUC），其計算公式為：

其中，n+為少數類樣本的個數，n-為多數類樣本的個數。對任一少數類樣本，若分類算法f將其分類為少數類的概率大于多數類的概率，則記值越接近1，模型的預測效果越好。

5.3 仿真實驗過程描述

首先采用線性降維以及流形學習算法對實驗用到的四組數據進行降維處理，將降維后的結果作為新的數據集輸入WEKA平臺，選擇SMO算法作為基分類器，將分類結果同標準SMO算法、基于線性降維的分類算法（PCAAdaCost）、基于流形學習的分類算法（LLE-AdaCost）進行性能對比。

5.4 實驗結果與分析

根據上述實驗設置，分別對UCI數據以及個舊區域化探數據進行仿真實驗。以下是UCI數據與化探數據的實驗結果。

5.4.1 UCI數據集

實驗結果如表1所示，為方便對比，各算法評測指標表現最好的結果背景用深灰色標出，次好的結果用淺灰色標出。

從表1看出對三組UCI數據的實驗，提出的算法在各項評測指標G-mean、AUC的表現均優于采用標準SMO分類器以及基于線性降維的算法，能夠有效地檢測出異常。

表1 測評指標對比表

5.4.2 化探數據

如表1，如果采用標準SMO分類器，少數類（有礦類）樣本的預測效果很差，也就是模型在外推時幾乎沒有識別出有礦樣本，而少數類樣本正是要重點關注的，因此標準SMO分類器幾乎不能滿足實際需求。進一步對比基于線性降維的異常識別算法與本文提出的異常識別算法發現，各項評測指標G-mean、AUC相對基于線性降維的異常識別算法均表現較好，大大提高了少數類樣本的分類精度。這是因為集成AdaCost算法更關注少數類樣本，通過犧牲多數類的準確率來提高少數類的精度，以達到提高分類器實際性能的目的。

為了進一步說明本文算法的效果，分別采用了柱狀圖與折線圖來顯示實驗的結果，如圖1～圖4所示。圖1和圖2是三種方法在G-mean和AUC上的柱狀圖對比圖。圖1和圖2中，橫坐標代表三組標準UCI數據集以及一組地學數據，從左到右分別為Glass、Hepatitis、Sonar、地學數據；藍色代表SMO，綠色代表PCA-AdaCost，紅色代表LLE-AdaCost。圖1和圖3中，縱坐標代表G-mean，圖2和圖4中縱坐標代表AUC。

從圖1～圖4可以看出，本文提出的異常分類算法（LLE-AdaCost）相比于傳統的SOM、PCA-AdaCost，在仿真實驗設置的評價指標上表現較好。進一步，在三組標準UCI數據集上以及另外一組地學數據中可以看出，LLE-AdaCost算法在G-mean上優于其他兩組的有三個，而另一個不是最優的數據集也優于傳統的PCA-AdaCost算法；在AUC上三組標準UCI數據集以及另外一組地學數據中，LLE-AdaCost相對于其他兩種傳統算法全部是最優的，比PCA-AdaCost算法表現更優。這是由于相對于傳統的線性降維方法，通過流形學習建立的高維-低維映射模型，能夠更加合理地顯示高維數據集的內在結構，在非線性降維的同時保持了原樣本空間的分布特性。通過集成的AdaCost算法能夠進一步提高少數類樣本的分類性能和異常檢測的準確率。

圖1 G-mean條形對比圖

圖2 AUC條形對比圖

圖3 G-mean折線對比圖

圖4 AUC折線對比圖

表1顯示，以G-mean為評價標準，LLE-AdaCost算法的數據集Sonar不是最優分類方法，這個數據集中多數類與少數類樣本數目比例為1.14∶1，維數為60，而這個數據集中最優的方法為傳統的SOM。這是由于基于流形學習的代價敏感性學習算法也可能遭遇到Over-Samping的問題，例如過度擬合，這是因為如果給少數類賦以比較大的代價因子等于進一步賦予少數類樣本更大的權值，所以產生了過度擬合，致使分類效果有所下降，從而進一步使異常檢測效果下降。從表1還可以看出，若以AUC為評價標準則，本文的異常分類算法的關于少數類的分類精度得到了大大提高。基于流形學習的異常檢測算法由于流形學習降維算法保證了原始數據結構的完整性，使得降維后的數據符合原始數據的空間分布，分類器的性能得到大大提高。這說明，僅僅以G-measure為評價標準并不能正確地說明分類器的分類效果，以G-mean和AUC為評價標準綜合考慮才能正確評價分類器的分類效果，這樣才能說明分類的正確性以及少數類分類的正確性，進而才能進一步檢測出少數類也就是所說的異常數據。

6 結論

異常數據挖掘在很多領域都具有非常重要的意義，其中少數類的識別即分類性能的提高更令人關注。本文提出了一種新型的基于流形學習的異常檢測算法，利用非線性降維方法，通過建立高維-低維映射關系真實地反映出高維數據的數據特征，同時嵌入的集成學習AdaCost代價敏感算法進一步提高了小類異常樣本識別率。最后，分別對UCI數據集以及不均衡的地學數據進行仿真實驗，實驗結果表明，基于流行學習的AdaCost算法預測的結果較傳統方法精度更高，為礦產資源定量預測與評價提供了新的解決途徑。

[1]Probost F.Machine learning imbalance data sets 101[C]//Proceedings of the AAAI 2000 Workshop on Imbalanced Data Sets，2002.

[2]Jolliffe I T.Principal component analysis[M].New York：Springer， 2002.

[3]宋明輝，潘軍，邢立新.東昆侖祁漫塔格地區找礦預測遙感研究[J].吉林大學學報：地球科學版，2006（S1）.

[4]郭云開，董勝光，彭悅.基于Curvelet變換和PCA相結合的方法提取地質構造信息[J].測繪通報，2010（4）.

[5]王瑞國，于濤，李軍，等.內蒙古錫林郭勒盟布魯特地區遙感礦化信息提取及應用[J].測繪與空間地理信息，2010，34（4）.

[6]de Silva V，Tenenbaum J B.Global versus local methods in nonlineardimensionalityreduction[C]//Proceedingsofthe Conference on Neural Information Processing Systems，2003：705-712.

[7]Fan W，Stolfo S J，Zhang J，et al.AdaCost：miss-classification cost-sensitive boosting[C]//Proceedings of the 16th International Conference on Machine Learning，1999：97-105.

[8]Roweis Sam T，Saul Lawrence K.Nonlinear dimensionality reduction by locally linear embedding[J].Science，2000，290（22）：2323-2326.

[9]Tenenbaum J B，Silva V，Langford J C.A global geometirc framework for nonlinear dimensionality reduction[J].Science，2000，290（22）：2319-2323.

[10]Belkin M，Niyogi P.Laplacian eigenmaps for dimensionality reductionanddatarepresentation[J].NeuralComputation，2003，15（6）：1373-1396.

[11]Friedman J H，Olshen R A，Stone C J，et al.Classification and regression trees[M].[S.l.]：American Statistical Association，1986.

[12]劉才澤，胡光道.個舊地區化探數據的各向異性及東西礦區的對比研究[J].地質與勘探，2007，43（6）：81-85.

[13]Fawcet T.ROC graphs；notes and practical considerations for researchers[J].Machine Learning，2004（3）：1-38.

[14]張曉龍，江川.基于AUC的SVM多類分類方法的研究[J].計算機工程與應用，2007，43（14）：166-169.

LIU Kaiwei,ZHANG Dongmei

School of Computer Science,China University of Geosciences,Wuhan 430074,China

Anomaly detection has important significance in many fields.Essentially speaking,the recognition of geochemical anomalies is the problem of imbalanced data classification.The main problems faced by anomaly identification is the processing problems of high-dimensional data,manifold learning is a nonlinear dimensionality reduction method that can reasonably reduce the data dimension.Therefore this paper proposes an anomaly detection algorithm based on the manifold learning,through manifold learning to achieve the dimension reduction,the new algorithm combines AdaCost technology of integrated learning,to improve classification performance.The new algorithm is based on the simulation experiment on the research objection of polymetallic deposits such as tin and copper from Gejiu,Yunnan province.The experimental results show that predicted results for the new algorithm delineating regional geochemical anomalies are better than traditional methods,which can more accurately identify the forming-ore abnormality.

anomaly detection;unbalanced data;manifold learning;cost-sensitive learning

化探異常識別是成礦預測的重要依據。化探異常識別本質上是一不均衡數據的分類問題。異常識別過程中面臨的主要問題是高維數據的處理問題，流形學習通過非線性降維方法實現維數約簡。提出了一種基于流形學習的異常識別算法，通過流形學習進行維數約簡，結合AdaCost技術，以改善不平衡數據的分類性能。以某錫銅多金屬礦床的數據為研究對象進行仿真實驗，實驗結果表明該算法能夠更準確地圈定區域化探異常，為成礦預測與評價提供了新的解決途徑。

異常檢測分類；不均衡數據；流形學習；代價敏感學習

A

TP181

10.3778/j.issn.1002-8331.1111-0210

LIU Kaiwei,ZHANG Dongmei.Manifold learning-based anomaly detection algorithm.Computer Engineering and Applications,2013,49（13）：105-109.

國家自然科學基金（No.40972206）；中央高校基本科研業務費專項資金資助項目（No.1323520909）。

劉凱偉（1987—），男，碩士研究生，主要研究領域為數據挖掘與智能計算；張冬梅（1972—），女，博士，教授，主要研究領域為科學計算可視化，智能計算，智能信息處理等。E-mail：373907551@qq.com

2011-11-16

2012-02-17

1002-8331（2013）13-0105-05

CNKI出版日期：2012-04-25http://www.cnki.net/kcms/detail/11.2127.TP.20120425.1721.064.html