基于神經(jīng)網(wǎng)絡(luò)的大規(guī)模數(shù)據(jù)集離群點(diǎn)檢測算法

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

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

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

錢景輝等[5]提出了基于多示例學(xué)習(xí)的數(shù)據(jù)集離群點(diǎn)檢測算法，該算法將真實(shí)對象在MIL框架中轉(zhuǎn)變?yōu)槎嗍纠问剑Y(jié)合權(quán)重調(diào)整方法和退化策略對綜合離群點(diǎn)因子進(jìn)行計(jì)算，實(shí)現(xiàn)對離群點(diǎn)的檢測.經(jīng)實(shí)踐證明，相對于其他算法，該算法在數(shù)據(jù)檢測全面性及高效性上有一定程度提高.顧煜炯等[6]設(shè)計(jì)了基于馬氏距離的數(shù)據(jù)集離群點(diǎn)檢測算法，該算法通過階比重采樣方法對大規(guī)模數(shù)據(jù)集中存在的原始數(shù)據(jù)進(jìn)行預(yù)處理，并對數(shù)據(jù)進(jìn)行量綱因子分析，結(jié)合馬氏距離采用多元線性回歸方法構(gòu)建離群點(diǎn)檢測模型，實(shí)現(xiàn)對大規(guī)模數(shù)據(jù)集離群點(diǎn)的檢測.然而大規(guī)模數(shù)據(jù)集下量綱因子分析過程較為復(fù)雜，導(dǎo)致該算法轉(zhuǎn)變數(shù)據(jù)形式所用的時(shí)間較長，存在檢測效率低的問題.為同時(shí)實(shí)現(xiàn)離群點(diǎn)檢測過程的高效性和檢測結(jié)果的準(zhǔn)確性，本研究利用神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)了大規(guī)模數(shù)據(jù)集離群點(diǎn)檢測算法.

1 大規(guī)模數(shù)據(jù)集降維處理

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

(1)

式中，T為數(shù)據(jù)離散度.輸入空間中存在的樣本點(diǎn)，并通過非線性映射函數(shù)φ將其轉(zhuǎn)變?yōu)樘卣骺臻g中存在的樣本點(diǎn)φ(x1)，φ(x2)，…，φ(xk)，…，φ(xM)[7].設(shè)C′為特征空間F中存在的協(xié)方差，可表示為

(2)

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

λ=φ(xk)C′v

(3)

在此基礎(chǔ)上，設(shè)置一個(gè)大小為M×M的矩陣G，在F空間上測試樣本對應(yīng)的投影為

(4)

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

(5)

在此基礎(chǔ)上，采用核主成分分析方法對大規(guī)模數(shù)據(jù)集進(jìn)行降維處理，具體過程如下：

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

2) 通過高斯徑向基核函數(shù)對核矩陣H進(jìn)行計(jì)算，計(jì)算表達(dá)式為

(6)

由式(6)可知，核矩陣與測試樣本對應(yīng)的投影存在直接關(guān)聯(lián)，同時(shí)也受到輸入空間中樣本數(shù)據(jù)的影響.

3) 對核矩陣H進(jìn)行局部修正.

4) 對H所對應(yīng)的特征向量和特征值進(jìn)行計(jì)算.

5) 按照降序?qū)τ?jì)算得到的特征值進(jìn)行排序，并對特征量進(jìn)行調(diào)整.

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

7) 對特征值對應(yīng)的累積貢獻(xiàn)率進(jìn)行計(jì)算，從中提取t個(gè)主分量(β1，β2，…，βt).

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

(7)

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

2 離群點(diǎn)檢測

一般來說，神經(jīng)網(wǎng)絡(luò)中包括輸入層、輸出層和隱含層，由目標(biāo)分類標(biāo)簽個(gè)數(shù)和輸入屬性個(gè)數(shù)決定輸出層神經(jīng)元數(shù)目和輸入神經(jīng)元數(shù)目[11].

假設(shè)p、q分別代表神經(jīng)元在隱含層和輸出層的個(gè)數(shù)，則神經(jīng)網(wǎng)絡(luò)模型可描述為

(8)

(9)

式中：φj(xi)為第j個(gè)節(jié)點(diǎn)在神經(jīng)網(wǎng)絡(luò)中對應(yīng)的輸出；cj為高斯核函數(shù)對應(yīng)的中心量；σj為第j個(gè)節(jié)點(diǎn)在高斯函數(shù)中的寬度；yi為第i個(gè)輸出神經(jīng)元在神經(jīng)網(wǎng)絡(luò)中對應(yīng)的輸出；Wij為第i個(gè)輸出神經(jīng)元與第j個(gè)隱節(jié)點(diǎn)之間存在的連接權(quán)重.

假設(shè)[xi，di]代表一組樣本對，存在于訓(xùn)練過程中，其中，di表示輸入量xi對應(yīng)的目標(biāo)量.通過樣本確定神經(jīng)網(wǎng)絡(luò)中存在的未知參數(shù)，包括輸出層、隱含層和隱節(jié)點(diǎn)中心之間的連接權(quán)值等[12-13].在構(gòu)造神經(jīng)網(wǎng)絡(luò)的過程中，確定隱節(jié)點(diǎn)中心是較為重要的一步.而在所設(shè)計(jì)的基于神經(jīng)網(wǎng)絡(luò)的大規(guī)模數(shù)據(jù)集離群點(diǎn)檢測算法中，通過減法聚類確定隱節(jié)點(diǎn)中心.

在減法聚類算法中可以用候選的隱節(jié)點(diǎn)中心代替數(shù)據(jù)對象，設(shè)Pi為中心對應(yīng)的勢，其計(jì)算表達(dá)式為

(10)

式中：r為鄰域分簇中心對應(yīng)的半徑；xc為簇中心數(shù)據(jù).減法聚類算法的具體過程如下：

1) 確定每個(gè)對象對應(yīng)的勢值Pi；

利用上述過程獲得隱節(jié)點(diǎn)中心，通過反向傳播算法在神經(jīng)網(wǎng)絡(luò)中更新連接權(quán)重，在更新權(quán)重的基礎(chǔ)上獲得輸出與輸入在神經(jīng)網(wǎng)絡(luò)中存在的映射關(guān)系[14-15].

(11)

設(shè)E為神經(jīng)網(wǎng)絡(luò)的誤差能量，其計(jì)算表達(dá)式為

(12)

在訓(xùn)練過程中引入調(diào)整項(xiàng)，對誤差函數(shù)進(jìn)行調(diào)整[16]，調(diào)整表達(dá)式為

(13)

在誤差函數(shù)的基礎(chǔ)上構(gòu)建大規(guī)模數(shù)據(jù)集離群點(diǎn)檢測模型，通過檢測模型實(shí)現(xiàn)大規(guī)模數(shù)據(jù)集離群點(diǎn)的檢測，檢測表達(dá)式為

(14)

綜上所述，實(shí)現(xiàn)了對基于神經(jīng)網(wǎng)絡(luò)的大規(guī)模數(shù)據(jù)集離群點(diǎn)檢測算法的設(shè)計(jì).算法具體實(shí)現(xiàn)流程如圖1所示.

圖1 大規(guī)模數(shù)據(jù)集離群點(diǎn)檢測算法運(yùn)行流程Fig.1 Operational process of outlier detection algorithm for large-scale data sets

3 實(shí)驗(yàn)結(jié)果與分析

為證明基于神經(jīng)網(wǎng)絡(luò)大規(guī)模數(shù)據(jù)集離群點(diǎn)檢測算法的整體有效性，設(shè)計(jì)實(shí)驗(yàn)加以驗(yàn)證.實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置情況如表1所示，其中，Communication Database數(shù)據(jù)庫由若干個(gè)可更新的系統(tǒng)表構(gòu)成.

表1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置Tab.1 Experimental environment and parameter settings

本文從檢測耗時(shí)和檢測準(zhǔn)確率兩個(gè)角度，在相同的實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置情況下，對基于神經(jīng)網(wǎng)絡(luò)的大規(guī)模數(shù)據(jù)集離群點(diǎn)檢測算法、基于多示例學(xué)習(xí)的數(shù)據(jù)集離群點(diǎn)檢測算法和基于馬氏距離的數(shù)據(jù)集離群點(diǎn)檢測算法進(jìn)行性能測試.

3.1 檢測準(zhǔn)確率

首先利用高斯函數(shù)結(jié)合降維處理，生成大規(guī)模數(shù)據(jù)集，數(shù)據(jù)集中共含有1 000個(gè)二維數(shù)據(jù)，在其中加入10個(gè)具有較大偏差的離群點(diǎn)，得到一個(gè)包含有1 010個(gè)二維數(shù)據(jù)的仿真數(shù)據(jù)集.然后利用基于神經(jīng)網(wǎng)絡(luò)的檢測算法對其中的離群點(diǎn)進(jìn)行檢測，檢測結(jié)果如圖2所示.

圖2 離群點(diǎn)檢測結(jié)果Fig.2 Outlier detection results

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

圖3 不同算法的檢測準(zhǔn)確率Fig.3 Detection accuracy of different algorithms

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

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

綜合分析圖3、4可知，在多次迭代中，基于神經(jīng)網(wǎng)絡(luò)的檢測算法可有效地對大規(guī)模數(shù)據(jù)集中存在的離群點(diǎn)進(jìn)行檢測，且檢測準(zhǔn)確率始終保持在90%以上，明顯高于2種對比檢測算法.原因在于基于神經(jīng)網(wǎng)絡(luò)的檢測算法在誤差函數(shù)的基礎(chǔ)上構(gòu)建離群點(diǎn)檢測模型，通過調(diào)整誤差能量提高最終的檢測準(zhǔn)確率.

3.2 檢測耗時(shí)

檢測耗時(shí)可以體現(xiàn)不同算法對離群點(diǎn)檢測的效率.利用操作系統(tǒng)后臺自動(dòng)統(tǒng)計(jì)不同算法的檢測過程耗時(shí)，測試結(jié)果如圖5所示.

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

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

4 結(jié) 論

針對當(dāng)前離群點(diǎn)檢測算法存在的檢測效率及檢測準(zhǔn)確率低的問題，本文利用神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)了一種大規(guī)模數(shù)據(jù)集離群點(diǎn)檢測算法.研究發(fā)現(xiàn)：采用核主成分分析方法對數(shù)據(jù)進(jìn)行降維處理，通過去除冗余數(shù)據(jù)和無用數(shù)據(jù)的方式可以有效縮短檢測用時(shí)，且在建立誤差函數(shù)的基礎(chǔ)上通過調(diào)整誤差能量提高最終的檢測準(zhǔn)確率.本文也通過實(shí)驗(yàn)證明了該算法能夠在較短的時(shí)間內(nèi)，準(zhǔn)確地對大規(guī)模數(shù)據(jù)集中離群點(diǎn)進(jìn)行檢測.