概率粗糙集三支決策在線快速計算算法研究

徐健鋒，何宇凡，湯濤，趙志賓

隨著大數據與互聯網加時代的到來，動態流數據成為了一種主流的數據類型，當前已經被廣泛地應用于金融股票交易、天氣和環境監測、計算機網絡監控等眾多領域[1]。在上述應用中，在線計算[2-3]是動態流數據的主要計算形式，其主要特點是實時數據快速地加載入內存，而CPU需要對內存中的實時數據實施快速計算，并且實時反饋計算結果。而傳統的離線計算[4]方式需要外部存儲器積淀數據后再進行科學計算，對于數據實時性和流動性的要求相對較低，因此傳統計算方法不能完全適應在線計算的新要求。研究更加高效的在線計算方法已經成為了當前大數據領域的一項重要課題。

近年來，以SPARK[5]為代表的內存計算平臺的推出與發展，較快推動了動態在線計算的發展。不確定性問題是機器學習領域的經典難題，如何在在線計算過程中進行不確定性問題的動態推理及求解也逐漸成為一項具有挑戰性的新議題。

三支決策理論[6]是基于粒計算粗糙集理論提出和發展起來的一種處理不確定、不完整信息決策的新方法。其初始目的是為粗糙集理論中的3個分類區域，即正域、負域和邊界域，提供合理的決策語義解釋。近年來隨著該理論的深入研究與發展，三支決策被認為是在信息不足或者獲取足夠信息的代價較高背景下的合理選擇。該理論與人類的認知習慣相似，具有認知方面的優勢，近年來，三支決策理論在垃圾郵件過濾[7]、文本挖掘[8]、圖像識別[9]、屬性約簡[10]、聚類[11]等應用領域[12-14]也都取得了廣泛的成果。

目前主要代表性的理論成果包括：基于代價敏感度量的決策粗糙集三支決策[15]、模糊集三支決策[16]、區間集三支決策[17]、概率粗糙集三支決策[18]、博弈粗糙集三支決策[19]、信息熵三支決策[20]、GINI系數三支決策[21]等。

同時針對動態數據環境下的動態計算也是另一項主要研究內容。文獻[22]首次提出一種離線動態計算方法，其對更新后的數據對象進行重新計算，算法執行效率不高。為了提高動態計算的效率，許多學者研究了粗糙集及三支決策的離線增量學習方法。其主要成果有：Liu等[23]提出了一種基于矩陣的動態不完備信息系統的增量方法；Li等[24]通過分析動態數據庫中新數據的不斷更新，提出了基于粗糙集理論的增量學習方法；Zhang等[25]等給出了鄰域粗糙集模型下多對象增加刪除時近似集快速更新的方法；Luo等[26]考慮到信息系統中數據對象動態插入，討論介紹了概率粗糙集模型中條件概率的動態估計策略，進而給出了概率三支近似的增量更新算法。然而研究表明，上述動態學習研究都是以離線計算為研究背景，而以在線計算為背景的動態三支決策研究較少。

本文以上述三支決策動態計算研究為基礎，系統性地研究了在線計算中動態數據變化形式及動態決策的變化規律，提出一種有別于傳統經典計算的三支決策在線快速計算學習方法，并進行實驗驗證。

1 相關工作

1.1 概率粗糙集三支決策模型

概率粗糙集是構造三支決策的基礎原型，首先我們回顧一下概率粗糙集三支決策的相關基本理論[20]。

通過定義2中的(α，β)-正域、負域和邊界域，可分別生成相應的接受、拒絕和延遲決策規則。

1.2 三支決策在線快速計算模型

滑動窗口技術[27-28]可以有效處理動態流數據下的數據挖掘與知識更新問題。在線計算的動態特點是，隨著新數據不斷進入，同時由于內存空間的限制，舊數據也被不斷被刪除，內存中包含的計算數據既增又減。由此，三支決策在線計算的數據變化模式可以用滑動窗口的方式進行描述。

圖1 在線計算內存數據變化機制模型Fig. 1 Sliding windows online computing model on memory data

基于三支決策理論以及上述在線內存數據變化模型，可以獲取如下動態單對象三支決策在線內存計算變化模型。

可見，決策信息系統在動態環境中，伴隨著數據對象在內存窗口的移入移出變化，必然會導致相關條件分類與決策分類發生相應變化，其條件概率及三支區域必然也會發生變化。本文首先系統地討論在線數據的動態變化情況下條件概率及三支區域的變化，并以此為基礎提出三支決策在線快速計算算法。

2 三支決策在線快速計算方法

上述模型實現了動態流數據在線計算的動態變化機制。在經典計算中，對于信息系統的每一次數據更新，采用等價類的重新劃分與計算，開銷較大?；趦却婊瑒哟翱诘娜Q策動態變化情況需要借鑒增量學習的思想，對于移入移出數據進行同步處理，從而能夠加快三支決策在線計算狀態下條件概率與三支區域的更新速度，保證了動態三支決策更新的實時性與高效性。

2.1 條件概率快速估計方法

如何利用已有的決策知識，實現條件概率的動態估計是基于三支決策知識更新的基礎。

由定義2可知，計算概率粗糙集三支決策的原理是：首先計算每條決策規則的條件概率，然后將每條決策規則的條件概率與三支決策閾值α、β進行比較，然后才能確定每個條件等價類屬于哪個三支決策區域?？梢?，每條決策規則的條件概率計算，是概率粗糙集三支決策的關鍵步驟。

其余變化模式的證明過程與變化模式1類似，在此省略。

證明 若移入對象 x 及移出對象 x遵循變化模式4，則有根據定義1及給定 t +1時刻決策表 IS(t+1)的數據變化公式(1)、(2)，可推斷出 t +1時刻條件概率Pr(Dj(t+1)|Ri(t+1))更新為

其余變化模式的證明過程與變化模式4類似，在此省略。

其余變化模式的證明過程與變化模式5類似，在此省略。通過定理1～3可知，隨著決策系統中數據對象同步移入移出的更新，原有決策規則的條件概率的變化趨勢可以通過局部更新數據的計算進行快速估計。這樣既避免了原有數據對象的重復學習，又利用同步更新大大提高了條件概率的計算效率，實現了三支決策條件概率的在線計算，進而使得三支決策區域的在線更新成為可能。

2.2 三支決策區域在線更新方法

三支決策的在線快速計算，即充分利用t時刻信息系統的獲取的三支決策知識以及t+1時刻變化數據的動態變化信息，快速且準確地計算三支決策的區域變化。其計算的原理是根據2.1節定理1～3獲得的各個決策規則的條件概率變化趨勢及特定條件概率取值，推導出三支決策區域在t+1時刻的變化規律。

其中

其中

其中

③假設p3:成立，由定義2得α，即則接 受域 更 新 為POS(α,β)

①假設n1:成立，由定義2得因為即則拒絕域更新為

②假設n2:

證畢。

式中：

式中：

式中：

證明 證明過程與推論1類似，此處略。證畢。

2.3 三支決策在線快速計算算法

根據2.1節中的定理1～3推導出的概率粗糙集的條件概率變化趨勢，以及2.2節中的三支決策區域的快速計算3種情形展開討論。

本節設計了三支決策在線快速計算算法(online computing algorithm)，并從算法時間復雜度角度與基于三支決策理論的經典計算算法作對比，從理論上分析在線快速計算算法的優勢。

算法1 三支決策在線快速計算算法

輸入 t時刻信息系統 IS(t)={U(t),C(t)∪D(t)}，條件等價類和決策等價類(i=1,2,···,m;j=1,2,···,n)，條件概率Pr(D(jt)|R(it))(i=1,2,···,m;j=1,2,···,n)，三支決策接受域、拒絕域和邊界域 P OS(α,β)(D(jt))、BND(α,β)(D(jt))及NEG(α,β)(D(jt))，新增決策對象 x及被移出對象 x，三支決策閾值 (α，β)。

1) 通過 x 及 x的等價類從屬關系，更新t+1時刻的條件等價類和決策等價類

在線快速計算中，若給定內存部分信息系統IS，包含m個條件等價類和n個決策等價類，其中，，等價類的計算時間復雜度為。步驟2)評估條件概率變化趨勢，其時間復雜度為，這時可以忽略不計的。步驟3)為更新三支區域，即區域內的對象可能發生轉移，區域未發生變化是最好的情況，在這種情況下兩種算法的時間復雜度均可視為；最壞的情況，此算法中需要轉移對象兩次，以和表示移入對象和被移出對象的條件和決策等價類，則區域更新的時間復雜度為。步驟4)中，在和已知的情況下，重新計算條件概率的時間復雜度幾乎是可以忽略不計的。綜上，在線快速計算的時間復雜度為。

為了說明上述在線三支決策算法的特點與優勢，本文將根據文獻[22]中提出的基于概率粗糙集三支決策理論的經典計算思想，設計三支決策經典計算算法(classical computing algorithm)。

算法2 基于三支決策的經典計算算法

3) 根據定義2重新計算t+1時刻三支決策接受域、拒絕域和邊界域、，。

經典計算算法中，若給定內存部分信息系統IS，包含m個條件等價類和n個決策等價類，其中，，等價類的計算時間復雜度為；重新計算條件概率的時間復雜度為；根據條件概率大小與閾值的比較，更新三支區域的時間復雜度亦為。因此，經典計算算法的時間復雜度為。

經典計算算法：

在線快速計算：

從時間復雜度分析可知，在線快速計算的效率明顯優于經典計算算法。從算法執行過程亦可看出，由于經典計算算法對于決策對象的每一次更新，都進行等價類劃分和條件概率的重新計算，其開銷甚是龐大；而在線計算利用內存滑動窗口模型，同步處理移入移出數據，對當前實時變化的數據進行局部計算，實現條件概率及三支區域的快速估計與更新，其運算效率明顯高于經典計算算法。

綜上，從理論分析可知在線快速計算的運行效率明顯優于經典計算算法。接下來，我們將從實驗的角度評估兩算法的實際表現。

3 實驗與結果

2.3 節通過理論證明了三支決策在線快速計算算法的時間復雜度優于經典計算算法。本章將通過與三支決策經典計算算法的對比實驗來驗證三支決策在線快速計算算法的時間消耗優勢。

本實驗環境為：雙核、4 GB內存的PC，運行Microsoft Windows 7操作系統，算法程序使用Java編程，Java開發包為JDK1.6版本。

3.1 數據集

為了驗證在線快速計算的性能，我們從UCI數據庫中選擇了8個較大數據集，分別為Skin-NoSkin、Shuttle、IRIS、Zoo、Haberman、Breastcancer、Letter、Magic，所有的數據均為數值型或類別型，表1為數據集的基本信息。

表1 數據集基本信息Table 1 The basic information of the eight datasets

3.2 實驗和結果

為排除偶然因素的影響，所有實驗都進行了10次，最終結果是10次實驗的平均值。我們任意設定的三支決策閾值為(0.75，0.3)。

1)算法執行時間對比實驗

假設存儲空間保持為100條記錄，我們比較在線快速計算、經典計算算法的性能時，逐漸增加上述8個數據集在內存中存儲數據的比例。當進入決策信息系統的在線計算數據總量累計達到總數據量的10%～100%時，分別測試不同情況下，兩種算法在三支決策區域更新中的平均執行時間。實驗結果如圖2所示。

圖2 在線快速計算與經典計算算法的平均時間消耗對比Fig. 2 Average elapsed times between online computing algorithm and classical computing algorithm

由圖2顯然可以看出，在每個數據集下，隨著進入內存中動態數據比例的增大，在線快速計算與經典計算算法的平均執行時間亦逐漸增大，但經典計算算法的增幅明顯更大?？梢?，在線快速計算的平均執行時間相對更少。

此外，為了更加精確地展現在線快速計算的優勢及其穩定性，我們將在占數據總量50%的情況下，從t時刻到t+5時刻，測試兩類算法的平均執行時間并對比其穩定性。結果見表2，單位為ms?？梢杂^察到，對于同一數據集，對比經典計算算法，在線快速計算可以大大節約算法執行時間。

表2 t～t+5時刻算法執行時間Table 2 Experimental results examined from time t to t+5 on UCI datasets ms

同時，在不同數據集上，在線快速計算執行時間的均值和方差比經典計算算法更小，顯示了其具有更好的效率及穩定性。

2)不同內存容量算法執行時間對比

由于在線計算方法以內存計算為依托，內存空間的容量對于三支決策在線快速計算的執行效果是否有影響，是一個值得研究的問題。因此我們選擇以上8個UCI數據集中規模較大且復雜程度較高的Breast-cancer數據集，構造和實驗1相似的對比實驗，但是將內存容量分別為設定為100、500、1 000、2 000條記錄，當上述數據集實施兩種算法實驗的數據總量累計達到總數據量的10%、40%、70%和100%時，分別記錄這兩種算法此時的平均執行時間。

由圖3可以觀察到，在相同實驗數據累積量下，隨著內存空間的增加，經典計算算法的平均執行時間幾乎呈指數級速度增長，而在線快速計算的時間消耗較為平穩。

由算法的時間復雜度可知，隨著決策系統的每一次更新，經典計算算法需要進行所有數據等價類的重新劃分及條件概率的重新計算，此過程每次都需要執行時間復雜度為的步驟，其時間消耗極大，且與內存中的數據量及復雜程度密切相關；而在線快速計算由于只需要對當前實時變化的數據對象進行局部計算，避免了歷史數據的重復學習，最多只需執行時間復雜度為的步驟，大大節省了此更新過程的開銷。

綜上可知，在不同內存空間下，在線快速計算的效率均遠高于經典計算算法，且這一優勢隨著內存空間的增加更加明顯。

3)不同閾值在線快速計算執行時間對比

由于三支決策是一種典型的概率粗糙集參數化模型，實驗結果可能會受參數設置的影響。設置內存空間為100 b，并選取了5對閾值，分別測出在線快速計算在8個數據集下執行完畢平均所需時間，從而驗證在線快速計算的性能與選取閾值的關系。圖4顯示了算法平均執行時間隨不同閾值對的變化趨勢，不難看出，算法的執行時間隨著閾值的改變有輕微的波動，總體來說比較穩定。由此也進一步驗證了在線快速計算的時間復雜度主要取決于動態數據的規模及其復雜程度。

圖3 在線快速計算與經典計算算法在不同內存容量下的平均執行時間Fig. 3 Average elapsed times between online computing algorithm and classical computing algorithm on different memory sizes

圖4 不同閾值對在線快速計算平均執行時間Fig. 4 Average elapsed times on online computing algorithm with different threshold pairs

4 結束語

動態在線計算是一種常見的數據計算方法，本文提出一種內存滑動窗口機制對在線計算的數據變化模式進行統一建模，并根據上述模型，推導出不同類型數據變化模式下的三支決策條件概率及三支區域的變化規律。最后本研究提出一種新型的動態在線快速計算算法，該算法能夠獲得與經典三支決策算法相同的決策結果。由于本算法只需要對當前的變化數據進行局部實時計算，有效避免了歷史數據的重復學習，大大提高了三支決策更新效率。為驗證本文所提出的在線快速計算的優勢，與經典計算算法在8個UCI公共數據集上進行實驗對比。實驗結果表明，在線快速計算比經典計算算法效率更高，穩定性更好。本研究表明，概率粗糙集三支決策領域采用在線計算方法進行快速計算是可行的。我們將在未來的工作中，繼續探討概率粗糙集三支決策的多對象動態在線快速計算以及其在實際在線計算場景中的應用。