,,

(蘇州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,江蘇 蘇州 215006)

0 概述

異常檢測旨在從數(shù)據(jù)集中快速有效識別異常點,在金融數(shù)據(jù)分析、網(wǎng)絡(luò)安全、醫(yī)學(xué)疾病與藥物分析領(lǐng)域被廣泛應(yīng)用?；跓o線傳感網(wǎng)和GPRS技術(shù),對物理世界進行感知,則是數(shù)據(jù)挖掘異常檢測領(lǐng)域又一重要研究方向[1]。傳統(tǒng)的異常檢測算法主要分為基于統(tǒng)計的異常點檢測算法、改進的基于距離的異常點檢測算法、基于密度的局部異常點檢測算法[2],它們主要基于統(tǒng)計學(xué)理論,以歐氏距離作為異常評判標(biāo)準(zhǔn)。

基于傳感器技術(shù)的數(shù)據(jù)挖掘能從大量、模糊的復(fù)雜數(shù)據(jù)中提取出潛在的、有價值的信息,而且傳感器網(wǎng)絡(luò)數(shù)據(jù)多以高維形式存在,具有海量、異構(gòu)有噪聲、實時要求性高等特性,這使得傳統(tǒng)的數(shù)據(jù)分析算法檢測出異常點的效果不明顯,而且時間復(fù)雜度過高,具有潛在的局限性。高維數(shù)據(jù)流的異常檢測面臨較多的挑戰(zhàn)。

國內(nèi)外已有大量的學(xué)者針對無線傳感網(wǎng)的數(shù)據(jù)挖掘進行相關(guān)研究并提出一系列方法用于高維數(shù)據(jù)流的異常檢測。如文獻[3]采用K-means算法思想,比較傳感器節(jié)點采集的數(shù)據(jù)點的相似度并劃分聚類,根據(jù)數(shù)據(jù)點與聚類中心的距離區(qū)分正常數(shù)據(jù)與異常數(shù)據(jù),但該方法采集的數(shù)據(jù)點維數(shù)有限,不適合高維數(shù)據(jù)的檢測。文獻[4]提出采用基于模式的聚類算法,分段取模式特征,并結(jié)合K最近鄰算法計算局部異常因子。文獻[5]提出一種快速數(shù)據(jù)流離群點檢測算法FODFP-Stream,通過動態(tài)發(fā)現(xiàn)和維護頻繁模式來計算高維類別屬性數(shù)據(jù)點離群度實現(xiàn)快速有效檢測,但針對數(shù)值屬性和混合屬性數(shù)據(jù)的異常檢測缺乏一定的擴展性。

針對高維空間下的異常點檢測,文獻[6]提出基于角度的異常檢測算法(Angle-based Outlier Detection,ABOD)[6]。在高維空間中,角度比距離更穩(wěn)定,余弦角度方差一定程度上可以反映數(shù)據(jù)的異常度[6-7]。在此基礎(chǔ)上,文獻[8]提出了HODA算法,定義了方差異常因子和網(wǎng)格密度等相關(guān)概念,通過降維和網(wǎng)格劃分處理數(shù)據(jù)集,最后根據(jù)剩余的網(wǎng)格計算異常因子ABOF。雖然該算法準(zhǔn)確率較高,但是算法時間復(fù)雜度仍較高。

高維數(shù)據(jù)流是連續(xù)的時間序列值,正常情況下在一定范圍內(nèi)出現(xiàn)小幅度的波動。某一異常點的出現(xiàn)與上一條數(shù)據(jù)存在一定的偏差,或者從某一時間序列開始,數(shù)據(jù)點偏離最佳數(shù)據(jù)集[9]。針對高維數(shù)據(jù)流的這一特點,本文提出一種改進的基于角度方差的數(shù)據(jù)流異常檢測算法。該算法根據(jù)采集的高維數(shù)據(jù)流特點,利用網(wǎng)格劃分出最佳數(shù)據(jù)集網(wǎng)格和最近數(shù)據(jù)集網(wǎng)格提高算法的運行效率。

1 問題描述及相關(guān)定義

下面簡要介紹相關(guān)知識:

定義1假設(shè)高維數(shù)據(jù)流是一種K元關(guān)系R={rt|rt∈S,t=1,2,…},其中,元組rt(t=1,2,…)連續(xù)到達[10],t為該數(shù)據(jù)點到達時間,K為數(shù)據(jù)的維度。

定義2假設(shè)給定一種Rd空間上的數(shù)據(jù)集S={X1,X2,…,Xi,…,Xn}以及一個樣本點Xp∈S,隨機選擇一對樣本點Xm,Xn∈S{Xp},θmpn為向量mp與pn的角度,所有θmpn的角度方差值為:

VOAp=Var[θmpn]=MOA2(p)-(MOA1(p))2

(1)

其中:

(2)

(3)

定義3最佳數(shù)據(jù)集網(wǎng)格是數(shù)據(jù)流的小規(guī)模數(shù)據(jù)流型。在數(shù)據(jù)空間中,由角度方差在閾值μ內(nèi)的數(shù)據(jù)點被且標(biāo)記為正常數(shù)據(jù)的數(shù)據(jù)點組建成網(wǎng)格。

基于物聯(lián)網(wǎng)技術(shù)采集的數(shù)據(jù)流采集可以感知電梯運行整體狀況。電梯數(shù)據(jù)流模型中有實時狀態(tài)數(shù)據(jù)和維保特征、運行特征等,數(shù)據(jù)來源更豐富,潛在高階特征多,更全面地反映電梯運行健康狀況:

1)電梯基本特征包含了電梯基本信息,包括電梯使用年限和已使用年限、額定速度等。

2)電梯維保特征是電梯維保狀況的重要體現(xiàn),如電梯維保頻次、平均維保時間等。

3)電梯運行特征主要包括當(dāng)月故障次數(shù)、困人次數(shù)和用戶投訴情況等。

4)電梯機械節(jié)點實時狀態(tài),這是電梯特征中最關(guān)鍵的特征。以傳感器和通信技術(shù)為基礎(chǔ),感知電梯各重要機械節(jié)點的實時運行狀態(tài)。

2 改進的高維數(shù)據(jù)流異常檢測算法

本文利用數(shù)據(jù)集網(wǎng)格劃分加快了ABOD算法的計算,同時通過實時更新網(wǎng)格的機制保證數(shù)據(jù)檢測精度;基于此,針對電梯狀態(tài)數(shù)據(jù)先進行預(yù)處理,對數(shù)據(jù)屬性進行篩選,其次將本文改進算法運用于電梯數(shù)據(jù)流的異常分析。

實時數(shù)據(jù)流的檢測需要算法具有較好的及時性和準(zhǔn)確性。本文改進算法的主要思想為:根據(jù)數(shù)據(jù)分布對數(shù)據(jù)流進行劃分,文獻[8]通過對所有的數(shù)據(jù)點進行網(wǎng)格劃分來過濾正常區(qū)域,但這一方法未考慮數(shù)據(jù)流的概念轉(zhuǎn)移問題,在本文算法的執(zhí)行過程中,實時維護一個最佳數(shù)據(jù)網(wǎng)格和最近數(shù)據(jù)網(wǎng)格,據(jù)此對最新采集的高維數(shù)據(jù)計算角度方差異常因子,使得歷史數(shù)據(jù)流中部分?jǐn)?shù)據(jù)參與角度方差因子的計算,計算代價小,滿足實時性要求;對于算法檢測出的異常點,分析導(dǎo)致數(shù)據(jù)異常的主要屬性,確保算法對數(shù)據(jù)異常屬性的識別能力。

如圖1所示,計算正常網(wǎng)格和候選網(wǎng)格中數(shù)據(jù)點的異常因子,HODA算法認為角度方差異常因子小于閾值的數(shù)據(jù)點為異常點。

圖1 數(shù)據(jù)點角度方差

算法高維數(shù)據(jù)流異常檢測

輸入最佳數(shù)據(jù)網(wǎng)格閾值μ,最佳數(shù)據(jù)網(wǎng)格尺度BL,最近數(shù)據(jù)網(wǎng)格尺度RL

輸出異常數(shù)據(jù)集S

1.Best_grid→?,Latest_grid→?

2.for inputXiFrom Datastream,init grids

3.for all Diin best_grid,calculate the XiVOA

4.for allFiin Latest_grid,calculate the XiVOA

5.calculate the averageVOA according to the above VOA value.

6.if VOA of Xi<μ,label Xias normal

7.if number of Di>BL,dequeue the first record

8.else Di=DiU {Xi}

9.if number ofFi>RL,dequeue the first record

10.else Fi=FiU {Xi}

11.else S=S U {Xi}

12.end

其中,步驟3、步驟4是算法的核心步驟,以上步驟的流程如圖2所示。

圖2 算法流程

為使算法運行效率更高,在計算角度方差異常因子之前,算法先由樣本值和最佳數(shù)據(jù)網(wǎng)格閾值篩選出最佳數(shù)據(jù)集區(qū)域。最佳數(shù)據(jù)集網(wǎng)格劃分閾值是一個關(guān)鍵參數(shù)。在取不同值時,最佳數(shù)據(jù)網(wǎng)格抽象的結(jié)果相差很大。當(dāng)過大時,網(wǎng)格劃分粒度過大,網(wǎng)格中數(shù)據(jù)增加,從而加大了計算量,算法優(yōu)化效果不明顯。反之,當(dāng)過小時,最佳數(shù)據(jù)集代表性不強。此時,雖然計算效率提高,但聚類效果也明顯下降。

最佳數(shù)據(jù)集閾值μ、最佳數(shù)據(jù)集尺度BL和最近數(shù)據(jù)集尺度RL是影響算法精度的主要因素,而且不同的尺度和閾值對應(yīng)于不同的算法精度。為了獲得最優(yōu)的尺度和閾值,算法需要進行大量的實際測試。一般而言,每種應(yīng)用產(chǎn)生的數(shù)據(jù)集對應(yīng)于一定的規(guī)律與特性,同時也對應(yīng)了一組最優(yōu)的權(quán)值和閾值[11]。大量實驗結(jié)果表明,只要獲得一組與數(shù)據(jù)集對應(yīng)的最優(yōu)權(quán)值和閾值,算法即可以獲得較高的準(zhǔn)確性。

3 基于改進算法的電梯異常數(shù)據(jù)檢測

3.1 數(shù)據(jù)預(yù)處理

在高維數(shù)據(jù)流分析中,如何從大量復(fù)雜原始特征中去除影響因子小的相關(guān)特征,提取關(guān)鍵特征,對于提高檢測精度和效率必不可少[12]。

1)RTS特征

傳感器采集的電梯各機械部位實時特征在4大數(shù)據(jù)源中所占比重最大,也是最有價值的特征值。在本文項目中,通過傳感器技術(shù)可以采集到的電梯特征值如圖3所示,同一時刻采集電梯共19維特征。

圖3 電梯各部位實時特征值

2)MTS特征

維保特征是電梯檢修和維護狀態(tài)的體現(xiàn)。本文選擇了比較重要的維保周期、維保項目、平均維保時長和維保滿意程度等4個特征。

3)FD特征

電梯基本特征是對電梯主要特征的描述。根據(jù)關(guān)鍵質(zhì)量指標(biāo)[13]選擇了額定載重、電梯層站門數(shù)、折余價值和日平均使用時間等4個關(guān)鍵特征。

4)RTD特征

電梯運行特征是指電梯故障統(tǒng)計特征,包括過去一周電梯故障次數(shù)、困人次數(shù)、被投訴次數(shù)和工單派發(fā)次數(shù)等,這是電梯重要異常特征歷史值。

其中,RTS是無線傳感網(wǎng)采集的電梯各關(guān)鍵部位實時數(shù)據(jù)流,后3類特征值是較為穩(wěn)定的電梯特征值,以周為單位進行統(tǒng)計查詢得到相關(guān)特征。

電梯部分狀態(tài)特征如表1所示。

表1 電梯部分狀態(tài)特征

3.2 電梯高維數(shù)據(jù)流異常檢測

由于電梯數(shù)據(jù)包括實時數(shù)據(jù)流和維保特征、基本特征等較為穩(wěn)定的數(shù)據(jù)值,本文將采集的電梯實時數(shù)據(jù)流進行初始化,將電梯實時狀態(tài)數(shù)據(jù)Xi作為輸入:

1)統(tǒng)計查詢電梯本周的MTS、FD、RTD等特征值,并進行預(yù)處理。

2)實時采集數(shù)據(jù)流,獲得一定的高維數(shù)據(jù)集樣本,根據(jù)樣本值和最佳數(shù)據(jù)集閾值進行初始化,從而構(gòu)造初始最佳數(shù)據(jù)網(wǎng)格和最近數(shù)據(jù)網(wǎng)格。

3)傳感器網(wǎng)絡(luò)采集的即時狀態(tài)數(shù)據(jù)Xi和小規(guī)模數(shù)據(jù)流型計算集實時計算該數(shù)據(jù)點的VOA值。

4) 基于VOA值和設(shè)定的最佳數(shù)據(jù)集閾值判斷最新數(shù)據(jù)點的異常情況。

5)若為異常點,則納入異常數(shù)據(jù)集并計算異常屬性,分析導(dǎo)致異常的維度;若為非異常點,則按照先進先出法和最近數(shù)據(jù)集網(wǎng)格尺度對最近數(shù)據(jù)集網(wǎng)格進行更新。

4 實驗結(jié)果與分析

本文方法采用的實驗環(huán)境為計算機Intel(R) Core(TM) i5-3470 CPU @ 3.20 GHz,內(nèi)存8.0 GB。開發(fā)平臺為PyCharm 2015,采用Python語言和pandas等分析包對本文改進的算法和HODA算法進行比較,并對電梯運行狀態(tài)的真實數(shù)據(jù)進行檢測。

本文采用運行時間和準(zhǔn)確率作為算法的評價指標(biāo)[14],準(zhǔn)確率是用來衡量算法的精度。

p=o/c

(4)

其中,o表示預(yù)測異常點集中真實異常點個數(shù),c為算法檢測到的異常點總數(shù)。

實驗1采用入侵檢測數(shù)據(jù)集KddCup99[15]作為測試數(shù)據(jù)集。該數(shù)據(jù)集具有高維的特性,這里分別選擇其中的1 000條、 2 000條、3 000條、5 000條數(shù)據(jù),其中異常記錄為25條。

本文采用KddCup99數(shù)據(jù)集分析算法的及時性和有效性,進行以下實驗:設(shè)置參數(shù)最優(yōu)數(shù)據(jù)網(wǎng)格閾值μ為0.3,最佳數(shù)據(jù)集尺度BL為50,最近數(shù)據(jù)集尺度RL為30;采用ABOD算法、HODA算法與本文算法進行對比,其中HODA算法與本文算法的實驗結(jié)果如表2、圖4所示。

表2 2種算法實驗結(jié)果分析

圖4 不同算法精度對比

針對實驗數(shù)據(jù)集,從表2和圖4可以看出,當(dāng)實驗數(shù)據(jù)集增大時,在算法運行時間上,本文算法比HODA算法更有優(yōu)勢,原因在于HODA算法在計算異常因子時會重新分配數(shù)據(jù)網(wǎng)格,算法的計算復(fù)雜度加大。3種算法精度都呈下降趨勢,但是相比HODA算法本文算法實驗獲得的最優(yōu)參數(shù)能夠保證對高維數(shù)據(jù)異常狀態(tài)的識別能力,相比HODA算法保持較高的精度。

實驗2使用昆山市某電梯公司2016年4月—2016年5月物聯(lián)網(wǎng)平臺數(shù)據(jù)作為實驗數(shù)據(jù)來源,分布于電梯各機械部位的無線傳感器節(jié)點,將采集到的電梯狀態(tài)數(shù)據(jù)通過GRRS發(fā)送到服務(wù)器,其數(shù)據(jù)采集頻率為2 s一次。

圖5是2種算法在不同時刻的運行時間對比,隨著電梯高維數(shù)據(jù)流的陸續(xù)到達,算法數(shù)據(jù)規(guī)模呈指數(shù)增長,可以看出本文異常檢測算法運行所消耗時間均小于相同數(shù)據(jù)規(guī)模下的HODA算法。因為HODA算法在計算角度方差異常因子時需要實時對網(wǎng)格進行劃分后篩選出候選網(wǎng)格,而本文算法維護2個最具代表的網(wǎng)格數(shù)據(jù)集,數(shù)據(jù)規(guī)模越大本文算法在其運行時間上的優(yōu)勢越明顯。

圖5 電梯異常數(shù)據(jù)檢測時間

查準(zhǔn)率采用被檢測出的實際異常點數(shù)目與檢測到可疑異常點數(shù)目之比進行度量。實驗過程中電梯產(chǎn)生12次不同程度的異常事件,根據(jù)圖6中2種算法平均查準(zhǔn)率的對比可知,本文算法的查準(zhǔn)率要優(yōu)于HODA算法。這是因為對于數(shù)據(jù)流中的最新數(shù)據(jù)點HODA算法需要重新進行網(wǎng)格劃分,當(dāng)數(shù)據(jù)集規(guī)模較大、維數(shù)較高時,該方法的候選網(wǎng)格增多,會將較多非異常的數(shù)據(jù)誤以為是異常狀態(tài)值。且本文算法采用最新數(shù)據(jù)集網(wǎng)格,可以有效地解決數(shù)據(jù)流的概念轉(zhuǎn)移問題,使得算法的查準(zhǔn)率得到保證。

圖6 電梯異常數(shù)據(jù)查準(zhǔn)率

5 結(jié)束語

本文基于角度分布的高維數(shù)據(jù)異常檢測方法,提出一種改進的異常檢測算法。在數(shù)據(jù)流檢測過程中,對數(shù)據(jù)集進行重要網(wǎng)格劃分和維護,降低角度方差計算代價,并且通過最近數(shù)據(jù)集的設(shè)定解決數(shù)據(jù)流中的概念轉(zhuǎn)移問題。實驗結(jié)果表明,該算法能有效識別高維數(shù)據(jù)流中的異常點,相比HODA算法,時間復(fù)雜度更低,適合于高維數(shù)據(jù)流的異常檢測。如何根據(jù)數(shù)據(jù)流的特點對閾值自適應(yīng),是下一步研究的內(nèi)容。

[1] 曹東磊,曹建農(nóng),金蓓弘.一種無線傳感網(wǎng)絡(luò)中事件區(qū)域檢測的容錯算法[J].計算機學(xué)報,2007,30(10):1770-1776.

[2] DING J,WANG L,SHEN D,et al.An Anomaly Detection System on Big Data[J].Natural Science Journal of Hainan Universdity,2015(1):121-127.

[3] 費 歡,李光輝.基于K-means聚類的WSN異常數(shù)據(jù)檢測算法[J].計算機工程,2015,41(7):124-128.

[4] 凌 駿,尹博學(xué),李 晟,等.基于監(jiān)控數(shù)據(jù)的MySQL異常檢測算法[J].計算機工程,2015,41(11):41-46.

[5] 周曉云,孫志揮,張柏禮,等.高維類別屬性數(shù)據(jù)流離群點快速檢測算法[J].軟件學(xué)報,2007,18(4):933-942.

[6] KRIEGEL H P,VHUBERT M,ZIMEK A.Angle-based Outlier Detection in High Dimensional Data[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2008:444-452.

[7] PHAM N,PAGH R.A Near-linear Time Approximation for Angle-based Outlier Detection in High Dimensional Data[C]//Proceeding of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2012:877-885.

[8] 陳圣楠,錢紅燕,李 偉.基于角度方差的多層次高維數(shù)據(jù)異常檢測算法[J].計算機應(yīng)用研究,2016,33(11):3383-3386.

[9] ZHANG Y,HAMM N,MERATNIA N.Statistics-based Outlier Detection for Wireless Sensor Networks[J].International Journal of Geo graphical Information Science,2012,26(8):1373-1392.

[10] 樸昌浩,黃 至,蘇 嶺,等.基于角度分布的高維數(shù)據(jù)流異常點檢測算法[J].上海交通大學(xué)學(xué)報,2014,48(5):647-652.

[11] KRIEGEL H P,HUBERT M S,ZIMEK A.Angle-based Outlier Detection Inhigh-dimensional Data[C]//Proceedings of IEEE KDD’08.Washington D.C.,USA:IEEE Press,2008:444-452.

[12] 劉 靖.復(fù)雜數(shù)據(jù)類型的離群檢測方法研究[D].廣州:華南理工大學(xué),2014.

[13] SIMUNDIC A.Quality Indicators[J].Biochemia Medica,2008,18(3):311-319.

[14] FELDMAN D,SCHIDT M,SOHLER C.Turning Big Data Into Tiny Data:Constant-sizecoresets for K-means,PCA and Projective Clustering[C]//Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms.Washington D.C.,USA:IEEE Press,2013:1434-1453.

[15] 陳冠華,馬秀莉,楊冬青,等.面向高維數(shù)據(jù)的低冗余Top-k異常點發(fā)現(xiàn)方法[J].計算機研究與發(fā)展,2010,47(5):788-795.