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

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

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

近年來，以SPARK[5]為代表的內(nèi)存計算平臺的推出與發(fā)展，較快推動了動態(tài)在線計算的發(fā)展。不確定性問題是機器學(xué)習(xí)領(lǐng)域的經(jīng)典難題，如何在在線計算過程中進行不確定性問題的動態(tài)推理及求解也逐漸成為一項具有挑戰(zhàn)性的新議題。

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

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

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

本文以上述三支決策動態(tài)計算研究為基礎(chǔ)，系統(tǒng)性地研究了在線計算中動態(tài)數(shù)據(jù)變化形式及動態(tài)決策的變化規(guī)律，提出一種有別于傳統(tǒng)經(jīng)典計算的三支決策在線快速計算學(xué)習(xí)方法，并進行實驗驗證。

1 相關(guān)工作

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

概率粗糙集是構(gòu)造三支決策的基礎(chǔ)原型，首先我們回顧一下概率粗糙集三支決策的相關(guān)基本理論[20]。

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

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

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

圖1 在線計算內(nèi)存數(shù)據(jù)變化機制模型Fig. 1 Sliding windows online computing model on memory data

基于三支決策理論以及上述在線內(nèi)存數(shù)據(jù)變化模型，可以獲取如下動態(tài)單對象三支決策在線內(nèi)存計算變化模型。

可見，決策信息系統(tǒng)在動態(tài)環(huán)境中，伴隨著數(shù)據(jù)對象在內(nèi)存窗口的移入移出變化，必然會導(dǎo)致相關(guān)條件分類與決策分類發(fā)生相應(yīng)變化，其條件概率及三支區(qū)域必然也會發(fā)生變化。本文首先系統(tǒng)地討論在線數(shù)據(jù)的動態(tài)變化情況下條件概率及三支區(qū)域的變化，并以此為基礎(chǔ)提出三支決策在線快速計算算法。

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

上述模型實現(xiàn)了動態(tài)流數(shù)據(jù)在線計算的動態(tài)變化機制。在經(jīng)典計算中，對于信息系統(tǒng)的每一次數(shù)據(jù)更新，采用等價類的重新劃分與計算，開銷較大?；趦?nèi)存滑動窗口的三支決策動態(tài)變化情況需要借鑒增量學(xué)習(xí)的思想，對于移入移出數(shù)據(jù)進行同步處理，從而能夠加快三支決策在線計算狀態(tài)下條件概率與三支區(qū)域的更新速度，保證了動態(tài)三支決策更新的實時性與高效性。

2.1 條件概率快速估計方法

如何利用已有的決策知識，實現(xiàn)條件概率的動態(tài)估計是基于三支決策知識更新的基礎(chǔ)。

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

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

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

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

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

2.2 三支決策區(qū)域在線更新方法

三支決策的在線快速計算，即充分利用t時刻信息系統(tǒng)的獲取的三支決策知識以及t+1時刻變化數(shù)據(jù)的動態(tài)變化信息，快速且準(zhǔn)確地計算三支決策的區(qū)域變化。其計算的原理是根據(jù)2.1節(jié)定理1～3獲得的各個決策規(guī)則的條件概率變化趨勢及特定條件概率取值，推導(dǎo)出三支決策區(qū)域在t+1時刻的變化規(guī)律。

其中

其中

其中

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

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

②假設(shè)n2:

證畢。

式中：

式中：

式中：

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

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

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

本節(jié)設(shè)計了三支決策在線快速計算算法(online computing algorithm)，并從算法時間復(fù)雜度角度與基于三支決策理論的經(jīng)典計算算法作對比，從理論上分析在線快速計算算法的優(yōu)勢。

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

輸入 t時刻信息系統(tǒng) 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的等價類從屬關(guān)系，更新t+1時刻的條件等價類和決策等價類

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

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

算法2 基于三支決策的經(jīng)典計算算法

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

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

經(jīng)典計算算法：

在線快速計算：

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

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

3 實驗與結(jié)果

2.3 節(jié)通過理論證明了三支決策在線快速計算算法的時間復(fù)雜度優(yōu)于經(jīng)典計算算法。本章將通過與三支決策經(jīng)典計算算法的對比實驗來驗證三支決策在線快速計算算法的時間消耗優(yōu)勢。

本實驗環(huán)境為：雙核、4 GB內(nèi)存的PC，運行Microsoft Windows 7操作系統(tǒng)，算法程序使用Java編程，Java開發(fā)包為JDK1.6版本。

3.1 數(shù)據(jù)集

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

表1 數(shù)據(jù)集基本信息Table 1 The basic information of the eight datasets

3.2 實驗和結(jié)果

為排除偶然因素的影響，所有實驗都進行了10次，最終結(jié)果是10次實驗的平均值。我們?nèi)我庠O(shè)定的三支決策閾值為(0.75，0.3)。

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

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

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

由圖2顯然可以看出，在每個數(shù)據(jù)集下，隨著進入內(nèi)存中動態(tài)數(shù)據(jù)比例的增大，在線快速計算與經(jīng)典計算算法的平均執(zhí)行時間亦逐漸增大，但經(jīng)典計算算法的增幅明顯更大。可見，在線快速計算的平均執(zhí)行時間相對更少。

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

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

同時，在不同數(shù)據(jù)集上，在線快速計算執(zhí)行時間的均值和方差比經(jīng)典計算算法更小，顯示了其具有更好的效率及穩(wěn)定性。

2)不同內(nèi)存容量算法執(zhí)行時間對比

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

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

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

綜上可知，在不同內(nèi)存空間下，在線快速計算的效率均遠高于經(jīng)典計算算法，且這一優(yōu)勢隨著內(nèi)存空間的增加更加明顯。

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

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

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

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

4 結(jié)束語

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