基于信息增益的高維數據的異常檢測算法

陳 曉，閻少宏，葛子軒，史冰冰

(1. 華北理工大學 理學院，河北 唐山 063210；2. 河北省數據科學與應用重點實驗室，河北 唐山 063210；3. 唐山市數據科學重點實驗室，河北 唐山 063210；4. 華北理工大學 電氣工程學院，河北 唐山 063210；5. 華北理工大學 人工智能學院，河北 唐山 063210)

0 引言

異常存在于各個領域，比正常攜帶的信息更多也更為重要，這些信息可能是災難性后果的預警或者標志，及時檢測出異常尤為重要[1]。隨著信息技術和網絡技術的發展，數據集變得更加龐大，結構更加復雜，空間維度更高。這些問題導致異常檢測的難度越來越大，同時也會帶來召回率跟精確率下降的問題。文獻[2]提出一種基于偏最小二乘（PLS）法和核向量機（CVM）組合式的異常入侵檢測方法。文獻[3]提出基于 KNN的累積距離的異常檢測方法。文獻[4]提出基于熵和改進的 SVM 多分類器的異常流量檢測方法。文獻[5]提出了一種基于迭代隨機采樣策略的排序算法。文獻[6]提出一種信息熵加權的異常檢測方法。上述算法大多應用于數據維度較小的數據集中，但是隨著維度的不斷增加，高維數據的異常檢測會有精確率跟召回率下降的問題。針對高維屬性對異常檢測帶來的維數災難問題，本文提出一種結合信息增益方法和 Top-k算法的異常檢測方法。

1 相關知識

1.1 聚類算法

聚類算法是一種無監督學習的典型算法，通常在異常檢測中異常類數據較少甚至沒有，因此不能直接借用監督型學習方法[7]。無監督異常檢測方法因其簡單、高效的特點，被廣泛用于大數據中的異常檢測[8]。其中應用最廣泛的是K-means聚類，但是K-means算法存在幾個問題：一是中心初始位置選擇不好會導致迭代次數增多和計算量增大，嚴重影響聚類效果。二是并未考慮數據中不同屬性之間的差異，不同屬性的信息增益占比不均衡。針對以上出現的問題，本文提出改進的聚類算法，通過肘部法則選擇最佳的聚類數，通過 1.2的方法確定初始聚類中心，替代原有的隨機選擇方法。

1.2 初始聚類中心的確定

傳統K-means算法的初始聚類中心是隨機生成的，如果初始聚類中心選擇不好，會導致聚類迭代次數的增多和計算量的增大[9]。為了消除這種影響，在初始數據集中選取兩點直徑距離盡量遠的點構成K個初始聚類中心，并依此完成改進的K-means算法，一定程度消除了以上因素的影響。具體算法流程如下：

輸入：樣本集M，初始聚類中心個數K，聚類中心{}；

Step.1計算樣本集M中的平均值，將此平均值設為樣本中心C；

Step.2計算樣本集M中的每個點到樣本中心C的距離，選擇離樣本中心最遠的那個點C1作為第一個初始聚類中心，此時聚類中心為{C1}；

Step.3計算剩余的M-1個點到C1點的距離，選取最遠的那個點C2，加入初始聚類中心，此時聚類中心為

Step.4重復Step.2-Step.3步直到找到K個初始聚類中心

1.3 信息增益

針對高維數據對異常檢測的檢測率和檢測時間產生不利影響的問題。通過對數據降維保留信息增益占比較大的屬性，更有利于提高異常檢測的準確率，信息增益的計算公式如下：

（1）信息熵的計算：

其中訓練數據集總個數為|D|，某個分類的個數為|CK|。

（2）選定A的條件熵計算：

其中|Di|為選定特征的某個分類的樣本個數，交集|Dik|可以理解在Di條件下某個分類的樣本個數。

（3）信息增益的計算：

信息增益越大表示該屬性對數據的影響越大，在進行數據分析時應該重點考慮。

2 基于信息增益的異常檢測算法

算法步驟

Step.1計算每個屬性的信息增益，用 Top-k算法選擇信息增益排名的前K個屬性，對其他屬性進行裁剪；

Step.2利用肘部法則，對數據集確定合適的初始聚類數；

Step.3利用本文1.2改進后的初始聚類中心的選擇辦法，選擇合適的初始聚類中心；

Step.4在 K-means聚類算法中引入 Step.2、Step.3方法，將數據集聚成M類；

Step.5計算每個簇中的平均距離，以及各個點到聚類中心的距離，如果點到聚類中心的距離大于平均距離，就把該點作為異常點；

Step.6對數據集中的數據取不同的前K個屬性再次重復Step.1～Step.4。

3 實驗分析

3.1 實驗設計與結果分析

實驗運用本文 1.2的方法確定初始聚類中心后運用K-means算法進行聚類，通過歐式距離計算每個點到簇中心距離，如果大于平均距離就把該點定為異常點，實驗結果顯示改進的 K-means聚類后得異常點個數為289。

運用相同的數據集，加入了加權信息熵的方法后進行聚類，異常點的個數為 288。可以看出加權信息熵的辦法在高維數據中的異常檢測效果并不理想，在加權信息熵的基礎上進一步計算每個維度的信息增益，并進行排序。分別取前10、20、30、40、50、60、70、80、90 維數據重新進行聚類，計算每一次聚類結束后的異常點的個數，分別求出異常點的個數為337、341、331、269、276、259、264、260、262。異常點的個數如圖1所示。

圖1 取前M維信息增益的異常點的個數圖Fig.1 shows the number of outliers with the first m-dimensional information gain

基于加權信息熵聚類的過程中，當迭代次數為 10時異常點的個數趨于穩定，取信息增益前10、20、30、40、50、60、70、80、90 維數據進行聚類的過程中，迭代次數分別為16、10、10、9、11、16、20、20、16。可以看出在加權信息熵的基礎上運用信息增益取前K個屬性的方法同樣也會增加異常點的個數，說明本算法對高維數據異常點的檢測效率有所提高。將召回率和精確率作為異常檢測性能的評價指標。本文所提的算法（前20維）與加權信息熵的算法進行比較，如表1所示，在異常點個數增多的前提下，召回率跟精確率也有一定的提高。

表1 兩種算法在數據集中的實驗對比結果Tab.1 experimental results of two algorithms in datasets

3.2 實驗小結

實驗結果表明與加權信息熵的異常檢測算法相比，本文提出的改進算法的召回率和精確率分別提高 53.65%和 29.49%，在異常點個數的檢測上也有明顯的提高。究其原因如下：首先，改進算法引入了信息增益的概念，根據各屬性影響程度的不同，計算出影響異常點檢測中每個屬性的信息增益；其次改進算法選擇了更優的初始中心，在迭代過程中數據對象的異常度計算與其所屬的簇中心相關。從而使得異常計算的結果更加準確，提高了異常檢測的性能。

4 結論

本文根據異常檢測以及聚類的特點在基于信息熵異常檢測算法基礎上改進了結合信息增益和Top-k的異常算法，通過計算數據每個屬性的信息增益，取前K個屬性，忽略掉非重要屬性重新進行聚類，有效的避免了其他屬性對異常檢測的影響，異常檢測的效果更優。實驗結果表明異常點的檢出個數比加權的信息增益算法明顯增多，取得了明顯的效果。但是本算法對非數值型數據的處理較差，如何進一步提升算法效率、處理多種數據類型以及設計不確定性異常的檢測方法是未來的研究重點。