一種高效的基于數(shù)據(jù)流模型的電力系統(tǒng)實(shí)時(shí)安全評估算法

摘要：安全評估問題是電力系統(tǒng)規(guī)劃和運(yùn)行過程中的一個(gè)很重要的問題。它包括對電力系統(tǒng)進(jìn)行安全評估及在需要的時(shí)候采取及時(shí)的應(yīng)對措施。本文聚焦于該問題并將電力系統(tǒng)的實(shí)時(shí)安全評估問題抽象為一個(gè)數(shù)據(jù)流挖掘模型。VFDT利用Hoeffding不等式解決了數(shù)據(jù)流挖掘問題。Wang等的VFDTb利用線索化二叉樹技術(shù)高效地解決了數(shù)據(jù)流挖掘中連續(xù)屬性問題。在VFDT 和VFDTb的基礎(chǔ)上，我們設(shè)計(jì)實(shí)現(xiàn)了一個(gè)基于AVL樹的高效算法PPSDT，該算法的排序樹的內(nèi)部路徑長度接近于最優(yōu)的NlogN。總體上說，該算法在保持決策樹精度的基礎(chǔ)上，很好的提高了挖掘速度。

關(guān)鍵詞：VFDTVFDTbAVLPSSDT

電力系統(tǒng)作為國民經(jīng)濟(jì)發(fā)展的基礎(chǔ)支柱產(chǎn)業(yè)，作用和地位愈來愈凸現(xiàn)，其安全問題已成為關(guān)乎國家經(jīng)濟(jì)安全運(yùn)行的問題。傳統(tǒng)的基于經(jīng)驗(yàn)和人工的安全保障方法已不能滿足要求。隨著信息技術(shù)水平和電力系統(tǒng)數(shù)字化水平的不斷提高，如何評估其安全狀態(tài)并實(shí)時(shí)采用有效的保障手段已成為理論研究和工程實(shí)踐領(lǐng)域的研究焦點(diǎn)問題。作為一個(gè)非線性的物理系統(tǒng)，其系統(tǒng)復(fù)雜性在不斷增加，導(dǎo)致電力系統(tǒng)的安全評估變得越來越困難。安全評估所需的數(shù)據(jù)是隨著系統(tǒng)的運(yùn)行不斷產(chǎn)生的，其數(shù)據(jù)量很大，并且具有很強(qiáng)的實(shí)時(shí)性，具有數(shù)據(jù)流（Data Stream）的典型特征。令t表示任一時(shí)間戳，at表示在該時(shí)間戳到達(dá)的安全數(shù)據(jù)向量，數(shù)據(jù)流可以表示成{…，at-1，at，at+1，…}。區(qū)別于傳統(tǒng)的數(shù)據(jù)模型，數(shù)據(jù)流模型具有以下3個(gè)特性：①數(shù)據(jù)高速到達(dá)，實(shí)時(shí)性要求高；②數(shù)據(jù)規(guī)模宏大，不可能把所有的數(shù)據(jù)都放入內(nèi)存甚至是硬盤；③數(shù)據(jù)一經(jīng)處理，除非特意保存，否則不能被再次取出處理，或者再次提取數(shù)據(jù)代價(jià)昂貴[2，7]。安全評估問題可以簡化一個(gè)機(jī)器學(xué)習(xí)的分類模型：通過安全評估，將系統(tǒng)當(dāng)前安全狀態(tài)盡興分類。分類是一種非常重要的機(jī)器學(xué)習(xí)技術(shù)，其目的是根據(jù)已有的數(shù)據(jù)集學(xué)習(xí)構(gòu)造一個(gè)分類函數(shù)或分類模型，該分類模型能夠?qū)⑿碌綐颖居成涞揭粋€(gè)具體的類別上。傳統(tǒng)的分類模型包括決策樹、決策規(guī)則、貝葉斯理論分類、反向傳播法、關(guān)聯(lián)分類法、K近鄰分類器、SVM、范例式推理、進(jìn)化算法、粗糙集法及模糊集合法等。其中決策樹模型是最普遍的一種分類模型，它具有很好的可理解性。本文將通過對電力系統(tǒng)運(yùn)行數(shù)據(jù)流進(jìn)行處理，從而構(gòu)造一個(gè)決策樹分類模型以有效地解決電力系統(tǒng)安全評估問題。

1 電力系統(tǒng)相關(guān)安全問題

本文的討論主要聚焦于電力系統(tǒng)的非線性特性所導(dǎo)致的安全問題。雖然這種安全問題不會經(jīng)常發(fā)生，但其潛在的安全問題非常嚴(yán)重并可能導(dǎo)致系統(tǒng)的完全崩潰。

1.1 操作狀態(tài)分類 Liacco[1]將電力系統(tǒng)的安全狀態(tài)分為：預(yù)安全狀態(tài)、緊急狀態(tài)、安全狀態(tài)等幾種狀態(tài)。

預(yù)安全狀態(tài)主要考慮當(dāng)系統(tǒng)處于常態(tài)時(shí)能否處理所有潛在的問題。如不能有效處理的話，預(yù)控制策略將把當(dāng)前狀態(tài)遷移到安全處理狀態(tài)以盡興處理。預(yù)判問題是非常困難且復(fù)雜的，因此預(yù)安全策略往往需要在費(fèi)效比之間做出平衡。緊急狀態(tài)主要考慮系統(tǒng)在出現(xiàn)緊急狀態(tài)時(shí)能否有效工作，這是一個(gè)需要實(shí)時(shí)評估的過程。緊急狀態(tài)安全策略應(yīng)采取快速的動作以避免系統(tǒng)局部或全局中斷。

當(dāng)預(yù)安全操作和緊急控制機(jī)制都沒有湊效，本地自動安全裝置應(yīng)被啟動以避免系統(tǒng)完全崩潰導(dǎo)致嚴(yán)重后果。

1.2 安全問題的分類 引起電力系統(tǒng)安全問題的原因很多（電壓過低，偏差過大等），所采取的應(yīng)急措施也很多（重啟系統(tǒng)，切斷系統(tǒng)）。因此安全問題的分類也很復(fù)雜，安全問題根據(jù)時(shí)間可分為以下幾類：①短暫穩(wěn)定問題。短暫穩(wěn)定考慮電力系統(tǒng)由于大的擾動導(dǎo)致電壓不穩(wěn)的同步恢復(fù)問題。該狀況下，時(shí)間因素很重要，并受操作開關(guān)和控制器件（如高速閥門，高電壓轉(zhuǎn)化器，F(xiàn)ACTS）和基于自動電壓調(diào)整的電壓支持及靜電補(bǔ)償器的性能的影響。該時(shí)間一般假設(shè)為系統(tǒng)在出現(xiàn)最嚴(yán)重問題時(shí)的恢復(fù)時(shí)間。②電壓安全問題。電壓安全問題經(jīng)常性的是由瞬間電壓突變引起的，其出現(xiàn)的幾率甚至比同步丟失還要高。更多的短期電壓不穩(wěn)定安全問題，一般是指1到5分鐘之內(nèi)的電壓不穩(wěn)。該情況下，主要是通過鄰近的自動變壓器進(jìn)行補(bǔ)償。長時(shí)間的電壓不穩(wěn)大都是由負(fù)載需求的改變引起的，因此一般通過負(fù)載的重分布解決。③靜態(tài)穩(wěn)定。它主要考慮傳輸系統(tǒng)的過載問題，其可供解決問題的時(shí)間更長。比如，傳輸線路過載在氣候良好的條件下也可以支持30到60分鐘。

2相關(guān)工作

2.1VFDT VFDT（Very Fast Decision Tree）[3，5]是一種基于Hoeffding不等式針對數(shù)據(jù)流建立分類決策樹的方法，它通過不斷的將葉節(jié)點(diǎn)替換為分支節(jié)點(diǎn)而生成。其中每個(gè)葉節(jié)點(diǎn)都保存有關(guān)于屬性值的統(tǒng)計(jì)信息，這些統(tǒng)計(jì)信息用于計(jì)算基于屬性值的信息增益測試。當(dāng)一個(gè)新樣本到達(dá)后，在沿著決策樹從上到下遍歷的過程中，它在樹的每個(gè)分支節(jié)點(diǎn)都進(jìn)行判斷，根據(jù)屬性取值的不同進(jìn)入不同的分支，最終到達(dá)樹的葉節(jié)點(diǎn)。當(dāng)數(shù)據(jù)到達(dá)葉節(jié)點(diǎn)后，節(jié)點(diǎn)上的統(tǒng)計(jì)信息就被更新，同時(shí)該節(jié)點(diǎn)基于屬性值的統(tǒng)計(jì)測試就被重新計(jì)算。如果統(tǒng)計(jì)信息計(jì)算顯示測試滿足一定的條件，則該葉節(jié)點(diǎn)變?yōu)榉种Ч?jié)點(diǎn)。新的分支節(jié)點(diǎn)根據(jù)屬性的可能取值的數(shù)目產(chǎn)生相應(yīng)數(shù)目的子女節(jié)點(diǎn)。分支節(jié)點(diǎn)只保存該節(jié)點(diǎn)的劃分測試所需要的信息。

2.2VFDTb 基于VFDT，Wang等設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)VFDTb算法[6]。該算法利用排序二叉樹有效處理了連續(xù)屬性，并且使用了更高效的最佳劃分節(jié)點(diǎn)選取方法，從而大大的提高了算法分類速度。

3 算法設(shè)計(jì)及技術(shù)細(xì)節(jié)

在VFDT和VFDTb的基礎(chǔ)上，我們通過平衡二叉樹（AVL樹）技術(shù)實(shí)現(xiàn)了電力系統(tǒng)安全數(shù)據(jù)流的處理算法（PSSDT）。該算法在VFDT基礎(chǔ)框架的基礎(chǔ)上處理離散屬性，通過平衡二叉樹處理連續(xù)屬性，能夠有效解決電力系統(tǒng)的安全評估問題。

3.1 算法框架 AVL樹是具有附加平衡屬性的二叉排序樹，對樹中的任意節(jié)點(diǎn)，左子樹的高度和右子樹的高度最多相差1。對于離散屬性參照VFDT的方法解決。

3.2 新樣本到達(dá)時(shí)的屬性樹更新過程 PSSDT為每個(gè)連續(xù)屬性i維持一個(gè)排序二叉樹結(jié)構(gòu)BST。排序二叉樹的每個(gè)結(jié)點(diǎn)都維持一個(gè)關(guān)鍵碼值keyValue（該值為樣本的屬性i的取值）和一個(gè)維度為k的用于記錄經(jīng)過該結(jié)點(diǎn)的樣本數(shù)目的向量。向量classTotals[k]用于記錄取值為keyValue類別為k的經(jīng)過該結(jié)點(diǎn)的樣本數(shù)。每個(gè)結(jié)點(diǎn)分別為其左右孩子（基于

4 實(shí)驗(yàn)結(jié)果

為驗(yàn)證本文所提出的AVL屬性樹方法對電力系統(tǒng)實(shí)時(shí)安全評估問題處理的有效性。這里設(shè)計(jì)了三組實(shí)驗(yàn)，分別驗(yàn)證算法對連續(xù)屬性處理的有效性、噪聲數(shù)據(jù)對算法的影響和屬性數(shù)目對算法的影響。為了實(shí)驗(yàn)的可比性和簡介，本文將進(jìn)行電力系統(tǒng)實(shí)時(shí)安全評估問題所涉及到的各連續(xù)行為要素抽象為連續(xù)屬性，并將每個(gè)連續(xù)屬性都?xì)w一化為0至1之間的某個(gè)實(shí)數(shù)值。實(shí)驗(yàn)環(huán)境是：奔IV/2.4G的CPU，內(nèi)存大小是1024M，操作系統(tǒng)為Windows XP。實(shí)驗(yàn)采TreeData工具生成的數(shù)據(jù)流。系統(tǒng)所用參數(shù)為：δ=10-7，τ=5%，nmin=300。

4.1 算法對連續(xù)屬性處理的有效性 第一組實(shí)驗(yàn)結(jié)果說明，該算法能夠有效解決電力系統(tǒng)實(shí)時(shí)安全評估的連續(xù)屬性處理問題。

4.2 噪聲數(shù)據(jù)對算法的影響 上一組實(shí)驗(yàn)驗(yàn)證了算法對電力實(shí)時(shí)安全評估問題的連續(xù)屬性處理的有效性，但算法是假設(shè)不存在噪聲數(shù)據(jù)的，算法在不同比率的噪聲數(shù)據(jù)情況下性能如何？本文設(shè)計(jì)了第二組實(shí)驗(yàn)用于驗(yàn)證算法在噪聲比例為0，5%，10%，15%等情況下的性能。第二組實(shí)驗(yàn)說明顯示算法在各種噪聲數(shù)據(jù)比率下都能很快的收斂到最終的決策樹。

4.3 連續(xù)屬性數(shù)目對算法的影響 連續(xù)屬性數(shù)目的大小直接影響了算法所處理數(shù)據(jù)量的大小，進(jìn)而影響到算法的性能，算法在不同連續(xù)屬性數(shù)目下性能如何，特別是內(nèi)存占用如何？第三組實(shí)驗(yàn)結(jié)果說明算法的內(nèi)存占用是趨于穩(wěn)定的。

5 結(jié)束語

通過將電力系統(tǒng)的實(shí)時(shí)安全評估問題所涉及的描述屬性轉(zhuǎn)換為連續(xù)屬性和離散屬性，本文將該問題抽象為一個(gè)數(shù)據(jù)流模型。在VFDT和VFDTb的基礎(chǔ)上，本文設(shè)計(jì)實(shí)現(xiàn)了高效的處理連續(xù)屬性的AVL樹，實(shí)驗(yàn)顯示算法能夠有效處理連續(xù)屬性問題，并且在不同的噪聲數(shù)據(jù)比率和連續(xù)屬性項(xiàng)目情形下算法都具有很好的收斂性。

電力系統(tǒng)的實(shí)時(shí)安全評估問題是個(gè)非常復(fù)雜的研究熱點(diǎn)問題，本文在該方向做了有益的嘗試，但安全評估問題涉及的要素很多，特別是電力系統(tǒng)的安全評估問題有其自身的特點(diǎn)，這需要我們在下一步的工作中加以研究解決。

參考文獻(xiàn)：

[1]Wehenkel，L.，Machine learning approaches to power-system security assessment，Volume 12，Issue 5，1997 Page(s):60-72

[2]B.Babcock，S.Babu，M.Datar，R.Motawani，and J.Widom.Models and Issues in Data Stream Systems.In PODS，2002.

[3]P.Domingos and G.Hulten.Mining High-Speed Data Streams.In Proceedings of the Association for Computing Machinery Sixth International Conference on Knowledge Discovery and Data Mining，pages 71--80，2000.

[4]J.Gama，R.Rocha and P.Medas.Accurate Decision Trees for Mining High-Speed Data Streams. Proceedings of the Ninth International Conference on Knowledge Discovery and Data Mining，Edited by P.Domingos and C.Faloutsos，ACM Press，2003.

[5]G.Hulten，L.Spencer，and P.Domingos.Mining Time-Changing Data Streams.ACM SIGKDD 2001.

[6]Tao Wang，Zhoujun Li，Xiaohua Hu，Yuejin Yan and Huowang Chen.A New Decision Tree Classification Method for Mining High-Speed Data Streams Based on Threaded Binary Search Trees. In Proceedings of High Performance Data Mining and Application (HPDMA`07)，Workshop of PAKDD`07，Nanjing，China.Lecture Notes in Artificial Intelligence，Springer-Verlag，2007，pp.256-267.

[7]王濤，李舟軍，顏躍進(jìn)，陳火旺.數(shù)據(jù)流挖掘分類技術(shù)綜述. 計(jì)算機(jī)研究與發(fā)展，2007，44（11）.