基于神經網絡的大規模數據集離群點檢測算法

高志宇， 宋學坤， 肖俊生， 閆培玲， 孫新娟

(1. 河南中醫藥大學 信息技術學院， 鄭州 450046； 2.華北水利水電大學 物理與電子學院， 鄭州 450045)

相對于大量常規數據來說，數據集中存在的離群點是一種異常孤立的數據模式[1].通常情況下，數據集中存在的離群點會被作為噪聲而被消除，但部分離群點會存在一些重要的信息[2].離群點檢測是結合可視化、統計學、智能計算、機器學習等多種技術對數據集中存在的離群點進行識別，便于后續的數據處理和分析的算法[3].由于離群點中可能存在有效信息，因此離群檢測在氣象預測、預防電信詐騙、市場分析、醫療保險和預防信用卡欺詐等領域中得到了廣泛的應用，具有重要的現實意義和學術意義[4].

錢景輝等[5]提出了基于多示例學習的數據集離群點檢測算法，該算法將真實對象在MIL框架中轉變為多示例形式，結合權重調整方法和退化策略對綜合離群點因子進行計算，實現對離群點的檢測.經實踐證明，相對于其他算法，該算法在數據檢測全面性及高效性上有一定程度提高.顧煜炯等[6]設計了基于馬氏距離的數據集離群點檢測算法，該算法通過階比重采樣方法對大規模數據集中存在的原始數據進行預處理，并對數據進行量綱因子分析，結合馬氏距離采用多元線性回歸方法構建離群點檢測模型，實現對大規模數據集離群點的檢測.然而大規模數據集下量綱因子分析過程較為復雜，導致該算法轉變數據形式所用的時間較長，存在檢測效率低的問題.為同時實現離群點檢測過程的高效性和檢測結果的準確性，本研究利用神經網絡設計了大規模數據集離群點檢測算法.

1 大規模數據集降維處理

所設計的離群點檢測算法首先采用核主成分分析方法對大規模數據集進行降維處理，去除大規模數據集中存在的冗余數據，進而縮短離群點檢測過程所需的時間，提高檢測效率.

(1)

式中，T為數據離散度.輸入空間中存在的樣本點，并通過非線性映射函數φ將其轉變為特征空間中存在的樣本點φ(x1)，φ(x2)，…，φ(xk)，…，φ(xM)[7].設C′為特征空間F中存在的協方差，可表示為

(2)

結合所得的特征空間協方差C′，可得到特征空間F中存在的特征值為

λ=φ(xk)C′v

(3)

在此基礎上，設置一個大小為M×M的矩陣G，在F空間上測試樣本對應的投影為

(4)

如果在特征空間中，數據無法滿足中心化條件，則要修正矩陣[8-9]，將G用G′進行描述，即

(5)

在此基礎上，采用核主成分分析方法對大規模數據集進行降維處理，具體過程如下：

1) 用M×N維的矩陣A描述數據流中存在的M條數據記錄.

2) 通過高斯徑向基核函數對核矩陣H進行計算，計算表達式為

(6)

由式(6)可知，核矩陣與測試樣本對應的投影存在直接關聯，同時也受到輸入空間中樣本數據的影響.

3) 對核矩陣H進行局部修正.

4) 對H所對應的特征向量和特征值進行計算.

5) 按照降序對計算得到的特征值進行排序，并對特征量進行調整.

6) 通過Gram-Schmidt正交法對特征量進行單位化處理[10].

7) 對特征值對應的累積貢獻率進行計算，從中提取t個主分量(β1，β2，…，βt).

8) 計算核矩陣H特征向量上存在的投影，即

(7)

根據式(7)中對特征量、核矩陣和特征值主分量的計算，獲得降維處理后的大規模數據集.

2 離群點檢測

一般來說，神經網絡中包括輸入層、輸出層和隱含層，由目標分類標簽個數和輸入屬性個數決定輸出層神經元數目和輸入神經元數目[11].

假設p、q分別代表神經元在隱含層和輸出層的個數，則神經網絡模型可描述為

(8)

(9)

式中：φj(xi)為第j個節點在神經網絡中對應的輸出；cj為高斯核函數對應的中心量；σj為第j個節點在高斯函數中的寬度；yi為第i個輸出神經元在神經網絡中對應的輸出；Wij為第i個輸出神經元與第j個隱節點之間存在的連接權重.

假設[xi，di]代表一組樣本對，存在于訓練過程中，其中，di表示輸入量xi對應的目標量.通過樣本確定神經網絡中存在的未知參數，包括輸出層、隱含層和隱節點中心之間的連接權值等[12-13].在構造神經網絡的過程中，確定隱節點中心是較為重要的一步.而在所設計的基于神經網絡的大規模數據集離群點檢測算法中，通過減法聚類確定隱節點中心.

在減法聚類算法中可以用候選的隱節點中心代替數據對象，設Pi為中心對應的勢，其計算表達式為

(10)

式中：r為鄰域分簇中心對應的半徑；xc為簇中心數據.減法聚類算法的具體過程如下：

1) 確定每個對象對應的勢值Pi；

利用上述過程獲得隱節點中心，通過反向傳播算法在神經網絡中更新連接權重，在更新權重的基礎上獲得輸出與輸入在神經網絡中存在的映射關系[14-15].

(11)

設E為神經網絡的誤差能量，其計算表達式為

(12)

在訓練過程中引入調整項，對誤差函數進行調整[16]，調整表達式為

(13)

在誤差函數的基礎上構建大規模數據集離群點檢測模型，通過檢測模型實現大規模數據集離群點的檢測，檢測表達式為

(14)

綜上所述，實現了對基于神經網絡的大規模數據集離群點檢測算法的設計.算法具體實現流程如圖1所示.

圖1 大規模數據集離群點檢測算法運行流程Fig.1 Operational process of outlier detection algorithm for large-scale data sets

3 實驗結果與分析

為證明基于神經網絡大規模數據集離群點檢測算法的整體有效性，設計實驗加以驗證.實驗環境及參數設置情況如表1所示，其中，Communication Database數據庫由若干個可更新的系統表構成.

表1 實驗環境及參數設置Tab.1 Experimental environment and parameter settings

本文從檢測耗時和檢測準確率兩個角度，在相同的實驗環境和參數設置情況下，對基于神經網絡的大規模數據集離群點檢測算法、基于多示例學習的數據集離群點檢測算法和基于馬氏距離的數據集離群點檢測算法進行性能測試.

3.1 檢測準確率

首先利用高斯函數結合降維處理，生成大規模數據集，數據集中共含有1 000個二維數據，在其中加入10個具有較大偏差的離群點，得到一個包含有1 010個二維數據的仿真數據集.然后利用基于神經網絡的檢測算法對其中的離群點進行檢測，檢測結果如圖2所示.

圖2 離群點檢測結果Fig.2 Outlier detection results

由圖2可知，利用基于神經網絡的檢測算法能夠有效檢測出樣本集中所含的10個離群點，由此，初步證明了該算法的有效性.在此基礎上，利用高斯函數結合降維處理，隨機生成一個新的大規模數據集，新的數據集中共含有10 000個二維數據，然后在其中加入了100個具有較大偏差的離群點，得到一個包含有10 100個二維數據的樣本集.利用此樣本集測試不同檢測算法的檢測準確率，對比結果如圖3所示.

圖3 不同算法的檢測準確率Fig.3 Detection accuracy of different algorithms

測試第500次迭代時不同算法的檢測結果，觀察其未能有效識別出的離散點情況，并以散點圖的形式體現，結果如圖4所示.

圖4 第500次迭代時不同方法檢測結果Fig.4 Test results of different methods at 500th iteration

綜合分析圖3、4可知，在多次迭代中，基于神經網絡的檢測算法可有效地對大規模數據集中存在的離群點進行檢測，且檢測準確率始終保持在90%以上，明顯高于2種對比檢測算法.原因在于基于神經網絡的檢測算法在誤差函數的基礎上構建離群點檢測模型，通過調整誤差能量提高最終的檢測準確率.

3.2 檢測耗時

檢測耗時可以體現不同算法對離群點檢測的效率.利用操作系統后臺自動統計不同算法的檢測過程耗時，測試結果如圖5所示.

圖5 不同算法的檢測時間Fig.5 Detection time of different algorithms

根據圖5可知，在多次迭代中，基于神經網絡的檢測算法對離群點的檢測時間始終低于0.4 min；基于多示例學習的檢測算法在第400次迭代過程中所用的檢測時間高達0.6 min；基于馬氏距離的檢測算法在第200次迭代中所用的檢測時間高達0.8 min.對比這3種檢測算法的測試結果可知，基于神經網絡的檢測算法檢測離群點所用的時間最短，證明該算法檢測效率最高.采用核主成分分析方法對大規模數據集進行了降維處理，去除了大規模數據集中存在的冗余數據和無用數據，因此有效縮短了檢測用時.

4 結 論

針對當前離群點檢測算法存在的檢測效率及檢測準確率低的問題，本文利用神經網絡設計了一種大規模數據集離群點檢測算法.研究發現：采用核主成分分析方法對數據進行降維處理，通過去除冗余數據和無用數據的方式可以有效縮短檢測用時，且在建立誤差函數的基礎上通過調整誤差能量提高最終的檢測準確率.本文也通過實驗證明了該算法能夠在較短的時間內，準確地對大規模數據集中離群點進行檢測.