陳 力，唐向紅

(貴州大學(xué) 教育部現(xiàn)代制造技術(shù)重點實驗室，貴陽 550003)

0 引言

斷路器在電網(wǎng)控制系統(tǒng)中起著至關(guān)重要的作用，如果它發(fā)生了故障，會給整個系統(tǒng)帶來十分嚴重的后果，因此盡量避免故障的發(fā)生的工作就顯得尤為重要。斷路器的控制器是通過傳感器來采集大量的連續(xù)的不確定的信號，從這些信號中快速的、準確的找出少量的異常的信號，對于整個電網(wǎng)系統(tǒng)而言具有十分重要的意義。

近些年來，人們對于數(shù)據(jù)挖掘技術(shù)的研究越來越深入，數(shù)據(jù)挖掘技術(shù)廣泛的應(yīng)用到各個領(lǐng)域。異常數(shù)據(jù)檢測的基本方法有基于統(tǒng)計的，基于距離的，基于聚類的，基于密度的等。其它的一些數(shù)據(jù)挖掘技術(shù)都是從這些基本的方法中發(fā)展出來的?；诰嚯x的檢測思想［1-2］由于其算法比較的直觀，便于人們的了解和實現(xiàn)而被廣泛應(yīng)用，但是這個方法是在數(shù)據(jù)集的全部空間屬性進行檢測，計算的時間復(fù)雜度較高，在執(zhí)行的效率上略有不足?；诰垲惖牡碾x群點的檢測算法［3-4］的思想是將所有的數(shù)據(jù)根據(jù)數(shù)據(jù)的屬性將數(shù)據(jù)分成一個個聚類，當某些數(shù)據(jù)不屬于這些聚類的時候，則該對象是基于聚類的離群點，在實際的操作過程中，先對所有的數(shù)據(jù)進行聚類劃分，然后再采用離群點檢測算法來挖掘出離群點，由于聚類算法的主要目標并不是發(fā)現(xiàn)離群點，只是發(fā)現(xiàn)聚類，因此此算法的檢測效率很低且針對性較強，適應(yīng)性不強。Breunning 等提出的一種基于密度的算法［5］，這種算法通過引用局部異常因子(LOF)的概念，LOF 表示的是數(shù)據(jù)對象之間一定范圍內(nèi)的領(lǐng)域內(nèi)的分布情況，LOF 的值與所求的數(shù)據(jù)對象數(shù)據(jù)分布的疏密程度有關(guān)，這個算法的計算復(fù)雜度很高，如果所要檢測的數(shù)據(jù)量發(fā)生了變化，就需要重新計算所有的數(shù)據(jù)的LOF 值，因此此算法只適用于靜態(tài)的數(shù)據(jù)檢測。小波包變換技術(shù)［6，7］可以較好的處理非線性信號，但是小波分解存在能量泄露問題，這會嚴重影響故障信號特征的提取。傳統(tǒng)的譜分析技術(shù)［8］，利用傅里葉變換得到信號的頻率分布，并提取特定頻段成份的變化作為特征參數(shù)，但這種方法主要適用于對平穩(wěn)隨機信號的處理，由于斷路器傳感器的工作環(huán)境中存在著強烈的電磁干擾，使得傳感器測得的數(shù)據(jù)中包含著大量非線性的成份，因此采用傅里葉變換會產(chǎn)生很大的誤差。

近些年來，數(shù)據(jù)流挖掘技術(shù)［9］是信息處理領(lǐng)域的熱點話題。而傳統(tǒng)的異常點檢測算法都將大部分的時間用在了處理正常的數(shù)據(jù)上，造成時間復(fù)雜度很高，并且這些算法不能用到實時的、動態(tài)的數(shù)據(jù)上。為了有效的檢測斷路器控制系統(tǒng)中的數(shù)據(jù)流，本文中提出了基于滑動窗口與K-近鄰距離的檢測算法，利用滑動窗口將數(shù)據(jù)分成一段段的數(shù)據(jù)，在時間窗口中利用要檢測的數(shù)據(jù)的有效值來對所有的數(shù)據(jù)進行剪枝，剔除絕大部分的正常數(shù)據(jù)，再利用基于K-近鄰的檢測方法對剩下的數(shù)據(jù)進行檢測。整個算法相對于傳統(tǒng)的算法而言，大大的降低了時間復(fù)雜度，能適用于短路器控制系統(tǒng)中的實時、動態(tài)檢測。

1 相關(guān)定義

定義1:數(shù)據(jù)流DS(Datastream)［5］，針對斷路器控制系統(tǒng)中傳感器采集的數(shù)據(jù)，數(shù)據(jù)流是按時間的先后順序連續(xù)產(chǎn)生的序列數(shù)據(jù)，可以表示為:DS= {(t0，y0)，(t1，y1)，…，(ti，yi)，…}。其中yi是ti時刻所到達的數(shù)據(jù)。

定義2:滑動時間窗口SW(Sliding window)［11］，在一個時間長度為m的時間序列T中，將其劃分為n個時間段的子序列W，W=T0，T1，T2，…Ti，…，Tn-1，每一個時間窗口Ti的寬度都為d。

定義3:數(shù)據(jù)流的有效值D效，在斷路器的控制系統(tǒng)中，傳感器采集的信號(電流或電壓)，根據(jù)這種采集到的諧波信號得到在正常工作的情況下信號的有效值D效，且根據(jù)斷路器機械設(shè)備的特性可以得出基于有效值的一個閾值，用符號EA表示，EA=［D效+D1，D效-D2］.則信號的yi值處于EA的范圍內(nèi)，斷路器會正常工作，否則數(shù)據(jù)點可能為異常數(shù)據(jù)。

定義4:p的K-距離(K-distance(p))［12］，對于任意的自然數(shù)K，定義p的K-距離p和某個對象之間的距離d(p，o)且滿足以下的條件:

(1)至少存在K個對象o，，∈D，使d(p，o，)≦d(p，o);

(2)至多存在K-1 個對象o，，∈D，使d(p，o)＜d(p，o);

定義5:p的K-距離鄰域［12］給定p的K-distance(p)，p的K-距離鄰域包含了所有與p距離不超過Kdistance(p)的對象。

定義6:在當前窗口中，將p的近鄰的數(shù)據(jù)的距離進行排序，到達K-近鄰距離的前n個數(shù)據(jù)為異常點。

2 基于滑動窗口和信號的有效值的閾值EA的剪枝方法

對于數(shù)據(jù)流DS 而言，異常的數(shù)據(jù)是占少部分的、離散的，絕大部分是屬于正常的數(shù)據(jù)。因此我們要想辦法在所有的數(shù)據(jù)中快速的剔除那些絕大部分的正常的數(shù)據(jù)，再對剩下的可能存在的異常的數(shù)據(jù)進行檢測，這樣對于整個數(shù)據(jù)的檢測而言會節(jié)省很多的時間。

斷路器控制系統(tǒng)在實際的運行工程中要檢測的參數(shù)y值與時間t有關(guān)。在這里我們以“電流—時間”為例，時間t是連續(xù)的，電流y值是隨著時間變化的，是離散的。在正常的工作情況下電流的y值都處在電流的有效值的閾值范圍內(nèi)，但是在某些時候電流的y值會超過這個區(qū)域，那么它就有可能是異常點。

在整個數(shù)據(jù)流的剪枝過程中，會計算出每個數(shù)據(jù)點的y值與數(shù)據(jù)的有效值的差值，再查看這個差值是否處在這個閾值范圍內(nèi)，以此為依據(jù)來判斷這個數(shù)據(jù)是否可能是異常點。從上面的過程中可以得出整個剪枝的過程的時間復(fù)雜度，對于數(shù)據(jù)量為n的數(shù)據(jù)，其時間的計算的復(fù)雜度為O(2N)。

計算結(jié)果的存儲:

通過了剪枝過程的剩下的數(shù)據(jù)，在接下來的K-近鄰距離的檢測方法中也需要計算每個數(shù)據(jù)的y值與有效值之間的差值，這樣看來，在整個數(shù)據(jù)的檢測過程中會重復(fù)計算某些數(shù)據(jù)的y值與數(shù)據(jù)的有效值之間的差值，這樣會明顯的增加整個檢測過程的時間復(fù)雜度。

為了解決上面所出現(xiàn)的重復(fù)計算的時間復(fù)雜度，我們可以采用空間換時間的方法來對整個算法過程進行優(yōu)化，在第一歩的剪枝的過程中將那些可能是異常點的數(shù)據(jù)的y值與數(shù)據(jù)的有效值之間的差值，用符號Li表示，通過開辟內(nèi)存空間保存這些差值，在下一步運用K-近鄰的檢測方法的時候，在需要用到這些值的時候直接提取出來。通過這種優(yōu)化，雖然會增加內(nèi)存空間來存儲某些數(shù)據(jù)的Li值，但是這樣會大幅度的減少算法的時間復(fù)雜度。

3 基于滑動時間窗口和數(shù)據(jù)流的有效值的K—距離檢測算法SWRK(Sliding Window RMS K—Distance)的描述

基于斷路器控制系統(tǒng)中傳感器所采集的數(shù)據(jù)的特性，我們可以根據(jù)數(shù)據(jù)流的有效值和采用滑動窗口來對數(shù)據(jù)進行在線檢測。在整個檢測過程中把數(shù)據(jù)流分成一個個的小段數(shù)據(jù)，再分別將這些小段數(shù)據(jù)放到滑動窗口中進行檢測，在滑動窗口中首先對這些數(shù)據(jù)進行一次篩選，剔除其中大部分正常的數(shù)據(jù)，再對剔除剩下的數(shù)據(jù)采用基于K-近鄰距離的方法再進行一次檢測，根據(jù)數(shù)據(jù)的y值到p距離來判斷數(shù)據(jù)是否為異常點。

這里的p數(shù)據(jù)的y值設(shè)定為數(shù)據(jù)流的有效值。

具體的算法如下:

算法:帶滑動窗口的數(shù)據(jù)檢測的SWRK 算法

輸入:數(shù)據(jù)流DS，數(shù)據(jù)流的有效值D效，正整數(shù)K，滑動時間窗口的寬度d。

輸出:當前窗口中到達K-近鄰距離的前n個數(shù)據(jù)點過程:

① 掃描數(shù)據(jù)流并存儲當前時間窗口中的數(shù)據(jù)直到當前窗口滿;

② 對當前窗口的數(shù)據(jù)進行第一次剪枝，并剔除在EA范圍內(nèi)的數(shù)據(jù);

③ 將窗口中可能存在的異常點的數(shù)據(jù)的Li存儲在存儲空間中;

④ 計算當前時間窗口內(nèi)可能存在異常的每個數(shù)據(jù)點的K-距離以及K-距離鄰域;

⑤ 調(diào)用存儲空間中的Li，將其按從大到小的距離進行排序;

⑥ 輸出到達K-近鄰距離的前n個數(shù)據(jù)點;

⑦ 時間窗口在時間軸上滑向下一個單元;

⑧ 重復(fù)①至⑦，直到檢測完所有的數(shù)據(jù)。

4 實驗結(jié)果分析

本節(jié)通過實驗來對SWRK 算法進行精確度和效率的分析。在本節(jié)的實驗中分別采用了真實數(shù)據(jù)和模擬數(shù)據(jù)來對此算法來進行檢驗。所有的實驗實在一臺PC 機上完成的，該PC 機的配置如下:CPU 是Inter Pentium G630，2.7GHZ，2G 的內(nèi)存，操作系統(tǒng)是Windows XP，編程的語言是C++。

4.1 真實數(shù)據(jù)的來源及SWRK 算法中參數(shù)對于算法的影響

為了驗證SWRK 算法的有效性和準確性，讓其具有說服性，在這里采用在數(shù)據(jù)挖掘領(lǐng)域大家所公認的數(shù)據(jù)集KDD CUP 1999。數(shù)據(jù)集KDD CUP 1999 是網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集，該數(shù)據(jù)集大概包括70000000 多個網(wǎng)絡(luò)連接，每個連接都有41 個特征，且該數(shù)據(jù)集包括5 個大類，由此可見該數(shù)據(jù)集是十分龐大的。要對此數(shù)據(jù)集所有的數(shù)據(jù)都進行檢測，這是不切實際的，也是沒必要的。在這里只需要選取其中的部分數(shù)據(jù)，大約為8 ×103條TCP 連接記錄，每條記錄選擇15 個數(shù)值型屬性，其中包括連接時間、失敗、登陸次數(shù)等。

查看SWRK 算法中參數(shù)對于算法的影響，主要查看其對于算法準確度和效率的影響。首先查看準確度，準確度的表達式如下:

從上文可知，影響SWRK 算法的參數(shù)主要是K和d，首先檢驗參數(shù)K對算法的影響。為了體現(xiàn)實驗的準確性，在這里采用控制變量法，設(shè)定在不同K值情況下滑動時間窗口的寬度d保持一致，同時選取真實數(shù)據(jù)中的每103條TCP 記錄進行一次檢測，實驗的結(jié)果如圖1 所示。

圖1 不同K 值時檢測的準確度

根據(jù)上圖可知，當K＜4 時，算法的準確率比較低，當K＞4 時，算法的準確率就會比較高，隨著K值的增加，準確度也會隨著增加，但是當K值達到一定程度后，準確度又會有所下降。出現(xiàn)這樣的情況的原因是因為在K值比較小的時候，數(shù)據(jù)P的K領(lǐng)域內(nèi)數(shù)據(jù)量很少，這樣就很難判斷這些數(shù)據(jù)中哪些是正常數(shù)據(jù)，哪些是異常數(shù)據(jù);隨著K值的增加，數(shù)據(jù)P的K領(lǐng)域內(nèi)的數(shù)據(jù)量也隨著增加，這時就會比較容易的判斷出這些數(shù)據(jù)中的異常點，但是當K值增加到一定程度之后，算法的準確率又會有所下降，這時它會將某些異常數(shù)據(jù)誤判為正常的數(shù)據(jù)。

檢驗滑動時間窗口寬度d對于算法SWRK 的影響，在這里主要查看在不同時間窗口寬度的情況下，算法的執(zhí)行時間的情況。選擇的實驗數(shù)據(jù)與檢查參數(shù)K對算法影響的數(shù)據(jù)相同，實驗的結(jié)果如圖2 所示:

圖2 不同滑動窗口寬度算法的執(zhí)行時間

從圖2 中可以看出，相對于同一個數(shù)據(jù)量而言，隨著時間窗口寬度的變大，整個算法的執(zhí)行時間會增加。隨著時間窗口的寬度的增加，每個時間窗口中的數(shù)據(jù)量會增加，則要處理的數(shù)據(jù)量也會隨著增加。這樣就導(dǎo)致了整個算法的時間會增加。

4.2 針對真實數(shù)據(jù)檢驗不同算法的優(yōu)劣

為了說明SWRK 算法的執(zhí)行效率，通過與其它兩種不同算法的比較可以體現(xiàn)出來。

使用SOMRNN［12］和OPWA［9］算法來對本文提出的SWRK 算法來進行效率的性能測試。其中SOMRNN 算法是基于反K-距離近鄰的數(shù)據(jù)流異常點檢測。OPWA 算法是基于多個滑動窗口同步計算的數(shù)據(jù)流異常點檢測。這兩個算法的內(nèi)容都與本文的SWRK 算法有關(guān)，比較的有針對性。本次實驗的數(shù)據(jù)與上面實驗所用的數(shù)據(jù)相同，實驗結(jié)果顯示的是在相同數(shù)據(jù)量的情況下，各種算法所執(zhí)行的時間，如圖3 所示。

圖3 不同算法之間執(zhí)行時間的比較

從圖中可以得出SOMRNN 算法所用的時間最多，SWRK 算法所用的時間最少。SOMRNN 算法所用的時間最多，因為在整個算法的過程中，它絕大部分的時間都用在了計算數(shù)據(jù)之間的距離上，計算時間復(fù)雜度很高。OPWA 算法要比SOMRNN 算法優(yōu)越，這是因為OPWA 算法在計算數(shù)據(jù)的聚集程度的時候是同步進行的，雖然這樣做會增加內(nèi)存空間，但是從時間的角度來看，可以為整個算法過程節(jié)約大量的時間。這兩個算法與本文中的SWRK 算法相比較，在這兩個算法執(zhí)行的過程中沒有剪枝過程，因此它們絕大部分的時間都用在了計算正常的數(shù)據(jù)上面，從而導(dǎo)致了這兩個算法的時間復(fù)雜度要高于SWRK 算法。

為了體現(xiàn)本文SWRK 算法的準確度，采用在不同K值和不同算法的情況下進行試驗，運用SOMRNN 算法和lncLOF 算法和SWRK 算法進行比較。lncLOF 算法動態(tài)環(huán)境下局部異常的增量挖掘算法。在SOMRNN 算法和lncLOF 算法中都用到了參數(shù)K，這樣使得本次試驗的結(jié)果更具有說服力。這里所用到的實驗數(shù)據(jù)與上一個實驗所用到的數(shù)據(jù)相同。實驗所得的結(jié)果如圖4 所示:

從圖4 可以看出，本文的SWRK 算法的準確度是最高的。SWRK 算法通過時間滑動窗口，將動態(tài)的數(shù)據(jù)轉(zhuǎn)化成了靜態(tài)的數(shù)據(jù)，當窗口中數(shù)據(jù)滿了之后，當前時間窗口的數(shù)據(jù)量就不會再發(fā)生變化，從而就提高了此算法的準確度;在SOMRNN 算法中判斷數(shù)據(jù)是否異常是根據(jù)K-近鄰個數(shù)的趨勢來確定的，數(shù)據(jù)量的變化就影響了整個數(shù)據(jù)點之間K—距離的變化;lncLOF 算法雖然考慮到了K-距離變化的這個因素，但是數(shù)據(jù)量的變化任然影響到了整個數(shù)據(jù)的計算。因為這些因素的影響，本文中所提到的SWRK 算法的準確度高于其他兩種算法。

4.3 模擬的實驗數(shù)據(jù)的實驗

假設(shè)斷路器控制系統(tǒng)中要檢測的某一電流信號，其表達式如下:

從表達式中可以看出要檢測的電流信號的周T=0.02s，頻率f=50Hz，在這里選取0s 到0.6s 的波形圖，如圖5 所示。

圖5 I(t)的波形圖

從圖形可以看出，該波形所顯示的數(shù)據(jù)是正常的數(shù)據(jù)，不存在異常點。此時認為的給此信號施加一個沖擊信號m(t)，是原始的信號產(chǎn)生異常點。此時m(t)信號時一個均值為0，方差為60 的高斯函數(shù)，m(t)所發(fā)生的區(qū)間為［0.2，0.25］，此時電流信號的數(shù)據(jù)流變?yōu)槿缦滤?

此時信號的波形圖如圖6 所示。

圖6 Y(t)的波形圖

利用如上圖所示的數(shù)據(jù)流來對本文中的SWRK算法來進行性能檢測。在此次試驗中運用SOMRNN算法和lncLOF［13］算法來與SWRK 算法相比較，所做的實驗是在相同的K值的情況下比較這三個算法的效率。根據(jù)4.1 節(jié)做所做的關(guān)于K值大小對于檢測數(shù)據(jù)的影響，在這里設(shè)定K值的大小為6。

運用這三個算法分別對信號Y(t)進行檢測，實驗的結(jié)果如圖7 所示。

圖7 不同算法的執(zhí)行時間

從上圖可知，在這三個算法中，執(zhí)行效率最低的是lncLOF 算法，執(zhí)行效率最高的是SWRK 算法。出現(xiàn)這樣結(jié)果的原因是因為在SOMRNN 算法和lncLOF 算法中整個算法的大部分時間都花在了計算正常數(shù)據(jù)上面，因此相比較而言SWRK 算法的效率最高。SOMRNN 算法相比于lncLOF 算法而言，它在數(shù)據(jù)上所計算的時間會低于lncLOF 算法，SOMRNN 算法在檢測的過程中，掃描的次數(shù)要少于lncLOF 算法。

5 結(jié)束語

本文提出了基于滑動時間窗口和K-近鄰距離的SWRK 檢測算法。該算法是在傳統(tǒng)的基于K-近鄰距離的檢測方法上，利用滑動時間窗口與數(shù)據(jù)流的有效值，對當前滑動窗口中的所有數(shù)據(jù)進行剪枝，并在這一過程中保存下一過程中所需要的數(shù)據(jù)，這樣大大的降低了整個算法的時間復(fù)雜度。通過實驗可以證明SWRK 算法在數(shù)據(jù)檢測的準確度和效率上，都比其它的一些算法優(yōu)越，因此此算法可以運用到斷路器控制系統(tǒng)中的異常數(shù)據(jù)檢測中來。SWRK 算法還存在著一些缺陷，在檢測數(shù)據(jù)的準確度上還有待提高，需要進一步的研究對其優(yōu)化。

［1］KnorrE，Ng R. Algorithms for mining distance-based outliers in large datasets［C］. Proceedings of the24th VLDB Conference，1998，392 -403.

［2］KnorrE，NgR. A unified approach for mining outliers:properties and computation［C］. Proceedings of Knowledge Discovery and Data Mining (KDD 97)，1997，219 -222.

［3］NgR T，Han J.Efficient and effective clustering methods for spatial data mining［C］. Proceedings of the20th VLDB Conference，1944，144 -155.

［4］GeorgeK，HanEui2Hong (Sam)，VipinK. CHAMEL EON:ahierarchical clustering algorithm using dynamic modeling［J］. IEEE Computer:Special Issue on Data Analysis and M ining，1999，32(8):68 -75.

［5］M Breunig，Hans-Peter Kriegel，R Nget al·LOF:Identifying density-based local outliers ·The ACM SIGMOD 2000 Int’l Confon Management of Data，Dalles，TX，2000.

［6］曾令全，李斌，劉明軍.Morlet 小波包絡(luò)分析在齒輪箱故障診斷中的應(yīng)用［J］. 組合機床與自動化加工技術(shù)2012(7):61 -63，67.

［7］崔勇.小波包變換和RBF 網(wǎng)絡(luò)在風電機組傳動鏈故障診斷的應(yīng)用研究［J］. 組合機床與自動化加工技術(shù)，2013(10):95 -97.

［8］王欣，周元鈞，馬齊爽. 基于FFT 和專家系統(tǒng)的BLDCM系統(tǒng)故障檢測與識別［J］.北京航空航天大學(xué)學(xué)報，2013，39(4):564 -568.

［9］周心林，趙雷.數(shù)據(jù)流上多滑動窗口聚集查詢的優(yōu)化算法［J］.小型微型計算機系統(tǒng)，2013，34(4):774 -777.

［10］ANGIULLI F，F(xiàn)ASSETTI F. Very efficient mining of distance-based outliers［C］ / / Proceedings of the Sixteenth ACM Conference on Conference on Information and Knowledge Management. New York:ACM Press，2007.

［11］王偉平，李建中，張冬冬，等.基于滑動窗口的數(shù)據(jù)流連續(xù)JA 查詢的處理方法［J］.軟件學(xué)報，2006，17(4):740-749.

［12］張慮平，梁永欣. 基于反k 近鄰的流數(shù)據(jù)離群點挖掘算法［J］.計算機工程，2009，35(12):11 -13.

［13］楊風召，朱揚勇，施伯樂. IncLOF_動態(tài)環(huán)境下局部異常的增量挖掘算法［J］. 計算機研究與發(fā)展，2004，41(3):447 -484.