基于信息增益的高維數(shù)據(jù)的異常檢測算法

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

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

0 引言

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

1 相關(guān)知識

1.1 聚類算法

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

1.2 初始聚類中心的確定

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

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

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

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

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

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

1.3 信息增益

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

（1）信息熵的計算：

其中訓(xùn)練數(shù)據(jù)集總個數(shù)為|D|，某個分類的個數(shù)為|CK|。

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

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

（3）信息增益的計算：

信息增益越大表示該屬性對數(shù)據(jù)的影響越大，在進(jìn)行數(shù)據(jù)分析時應(yīng)該重點考慮。

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

算法步驟

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

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

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

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

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

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

3 實驗分析

3.1 實驗設(shè)計與結(jié)果分析

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

運用相同的數(shù)據(jù)集，加入了加權(quán)信息熵的方法后進(jìn)行聚類，異常點的個數(shù)為 288?？梢钥闯黾訖?quán)信息熵的辦法在高維數(shù)據(jù)中的異常檢測效果并不理想，在加權(quán)信息熵的基礎(chǔ)上進(jìn)一步計算每個維度的信息增益，并進(jìn)行排序。分別取前10、20、30、40、50、60、70、80、90 維數(shù)據(jù)重新進(jìn)行聚類，計算每一次聚類結(jié)束后的異常點的個數(shù)，分別求出異常點的個數(shù)為337、341、331、269、276、259、264、260、262。異常點的個數(shù)如圖1所示。

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

基于加權(quán)信息熵聚類的過程中，當(dāng)?shù)螖?shù)為 10時異常點的個數(shù)趨于穩(wěn)定，取信息增益前10、20、30、40、50、60、70、80、90 維數(shù)據(jù)進(jìn)行聚類的過程中，迭代次數(shù)分別為16、10、10、9、11、16、20、20、16?？梢钥闯鲈诩訖?quán)信息熵的基礎(chǔ)上運用信息增益取前K個屬性的方法同樣也會增加異常點的個數(shù)，說明本算法對高維數(shù)據(jù)異常點的檢測效率有所提高。將召回率和精確率作為異常檢測性能的評價指標(biāo)。本文所提的算法（前20維）與加權(quán)信息熵的算法進(jìn)行比較，如表1所示，在異常點個數(shù)增多的前提下，召回率跟精確率也有一定的提高。

表1 兩種算法在數(shù)據(jù)集中的實驗對比結(jié)果Tab.1 experimental results of two algorithms in datasets

3.2 實驗小結(jié)

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

4 結(jié)論

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