徐巖柏，景運(yùn)革

運(yùn)城學(xué)院 數(shù)學(xué)與信息技術(shù)學(xué)院，山西 運(yùn)城 044000

現(xiàn)實(shí)生活中，傳感器技術(shù)發(fā)展促進(jìn)了各行各業(yè)產(chǎn)生了大量多源數(shù)據(jù)（分布數(shù)據(jù)），如何發(fā)現(xiàn)多源數(shù)據(jù)中隱含的知識是人工智能方向研究的一個熱點(diǎn)問題。近10多年來，一些研究者已經(jīng)提出了許多處理多源數(shù)據(jù)的形式概念分析方法并運(yùn)用它們?nèi)ソ鉀Q一些實(shí)際問題[1-3]。但是在現(xiàn)實(shí)生活中，多源數(shù)據(jù)大多都包含不確定性的信息，因此利用上述方法不能對多源數(shù)據(jù)進(jìn)行精確化處理及數(shù)據(jù)分析和挖掘。

粗糙集理論為解決上述問題提供了一種新的技術(shù)方案，在沒有任何先驗知識的條件下，能夠解決不一致和不精確多源數(shù)據(jù)知識挖掘和發(fā)現(xiàn)的問題。目前已經(jīng)有很多研究者利用粗糙集理論和數(shù)據(jù)融合技術(shù)去處理多源數(shù)據(jù)知識挖掘的問題[4-8]。但這些算法對于靜態(tài)多源數(shù)據(jù)是有效的?？墒?，如果用上述方法去計算動態(tài)多源數(shù)據(jù)約簡的問題，因為不能有效利用原有的計算結(jié)果，導(dǎo)致求解動態(tài)分布數(shù)據(jù)約簡就會花費(fèi)很多時間，使得計算效率很低。為了克服上述靜態(tài)算法的缺陷，一些研究者把增量學(xué)習(xí)技術(shù)應(yīng)用到粒計算和粗糙集理論中。

增量學(xué)習(xí)技術(shù)可以充分利用原有的計算結(jié)果，避免重復(fù)計算，提高計算效率。目前很多學(xué)者把增量技術(shù)應(yīng)用到求解信息系統(tǒng)約簡的問題中。這些增量方法主要用來去計算信息系統(tǒng)對象、屬性和屬性值發(fā)生變化后的約簡問題。首先，一些學(xué)者針對對象添加到信息系統(tǒng)后如何迅速計算其約簡問題，提出了對象發(fā)生變化后的增量約簡算法[9-11]。其次，另一些學(xué)者針對屬性添加到信息系統(tǒng)后如何快速更新其約簡問題，給出了信息系統(tǒng)增量計算機(jī)制，提出了屬性發(fā)生變化后的增量約簡方法[12-15]。此外，還有一些學(xué)者針對信息系統(tǒng)屬性值發(fā)生改變后如何迅速獲得其約簡問題，提出了屬性值發(fā)生變化后的增量約簡算法[16-18]。綜上分析，雖然研究者提出了很多增量約簡算法，但是這些方法主要用來解決單個信息系統(tǒng)數(shù)據(jù)動態(tài)變化后的約簡問題，而利用增量技術(shù)解決動態(tài)多源數(shù)據(jù)約簡的方法卻報道鮮少。因為多源數(shù)據(jù)來源于不同地方，如何探討多源數(shù)據(jù)之間及多源數(shù)據(jù)與增加數(shù)據(jù)之間的內(nèi)在聯(lián)系及數(shù)據(jù)如何有效融合是計算動態(tài)多源數(shù)據(jù)約簡中的一個難點(diǎn)問題。因此，當(dāng)分布數(shù)據(jù)增加了一些屬性后，本文提出了基于分布數(shù)據(jù)的矩陣增量約簡算法，可以快速實(shí)現(xiàn)動態(tài)多源數(shù)據(jù)的融合，計算動態(tài)多源數(shù)據(jù)的約簡。

1 基于知識粒度分布信息系統(tǒng)約簡算法

本章簡單介紹分布信息系統(tǒng)相關(guān)概念和定義及分布數(shù)據(jù)約簡的方法[19-20]。

1.1 分布信息系統(tǒng)的基礎(chǔ)知識

定義3給出一個分布信息系統(tǒng)DS=(U,A,V,F)=中任意兩個獨(dú)立的子信息系統(tǒng)S i和S j的關(guān)系矩陣為，則DS的知識粒度定義如下：

1.2 分布信息系統(tǒng)非增量約簡算法

2 分布決策信息系統(tǒng)增量約簡算法

2.1 分布決策信息系統(tǒng)增量機(jī)制

2.2 分布系統(tǒng)屬性增加的矩陣增量約簡算法

2.3 時間復(fù)雜度分析

3 仿真實(shí)驗方案

3.1 實(shí)驗軟硬件環(huán)境和實(shí)驗數(shù)據(jù)集

為了驗證本文所提出的矩陣增量約簡算法在獲得動態(tài)多源數(shù)據(jù)約簡時具有很強(qiáng)的計算性能，本文分別用矩陣增量和非增量約簡算法做了一些對比仿真實(shí)驗，并從機(jī)器學(xué)習(xí)網(wǎng)站下載實(shí)驗所用到的UCI數(shù)據(jù)集，數(shù)據(jù)集具體描述如表1所述，由于下載的UCI數(shù)據(jù)是單源數(shù)據(jù)，為了模擬多源數(shù)據(jù)實(shí)驗環(huán)境，把下載的實(shí)驗數(shù)據(jù)分成不同部分，這些不同部分?jǐn)?shù)據(jù)在實(shí)驗中表示多源數(shù)據(jù)，本文為了實(shí)驗的簡單性，把實(shí)驗數(shù)據(jù)分成3部分的多源數(shù)據(jù)。另外，實(shí)驗所用到的軟件及硬件配置描述如表2所述。

表1 UCI數(shù)據(jù)集描述Table 1 Description of UCI date sets

表2 軟件和硬件配置描述Table 2 Description of computer software and hardware configuration

3.2 屬性約簡結(jié)果比較

在對比實(shí)驗過程中，首先把表1中所有數(shù)據(jù)按照條件屬性分成大小相等的兩個數(shù)據(jù)集，把其中一個數(shù)據(jù)集按照對象的40%、30%、30%分成3個數(shù)據(jù)集，作為實(shí)驗中的多源數(shù)據(jù)，把另一個數(shù)據(jù)集按照屬性的20%、40%、60、80%、100%分成5個數(shù)據(jù)集，作為增量的屬性集，依次把這些屬性添加到分布信息系統(tǒng)所有的子信息系統(tǒng)中，然后分別用矩陣增量和非增量約簡算法對它們進(jìn)行測試，兩種方法計算約簡的運(yùn)行時間如圖1中每個子圖所示，圖1中所有子圖的X軸表示增量屬性集的大小，Y軸表示運(yùn)行時間，矩陣非增量和增量約簡算法的運(yùn)行時間分布用圓形藍(lán)色和方形紅色的線表示。

圖1 增量及非增量約簡算法的計算時間結(jié)果比較Fig.1 Comparison between incremental reduction method and non-incremental reduction method on computation time

從圖1結(jié)果可知，矩陣增量計算動態(tài)多源數(shù)約簡的運(yùn)行時間遠(yuǎn)遠(yuǎn)小于非增量約簡算法的運(yùn)行時間，特別是對于較大數(shù)據(jù)集而言，增量約簡算法的計算性能優(yōu)勢更加明顯，說明了增量約簡算法能夠提高計算動態(tài)多源數(shù)據(jù)約簡的效率。

3.3 屬性約簡分類精確度分析比較

為了驗證矩陣增量算法在計算動態(tài)多源數(shù)據(jù)約簡是有效的，本節(jié)先把表1中6個UCI數(shù)據(jù)集依照屬性集分成均勻兩個數(shù)據(jù)集，把其中一個數(shù)據(jù)集按照對象的40%、30%、30%分成3個數(shù)據(jù)集，作為實(shí)驗中的多源數(shù)據(jù)，把另一個數(shù)據(jù)集作為屬性增量數(shù)據(jù)集，并把其添加到分布信息系統(tǒng)所有子信息系統(tǒng)中，然后分別利用矩陣增量和矩陣非增量約簡算法去計算變化后多源數(shù)據(jù)的約簡。并通過貝葉斯分類及10折交叉驗證算法去計算矩陣增量和矩陣非增量約簡算法所獲得屬性約簡的分類精確度，在實(shí)驗過程中，把多源數(shù)據(jù)集隨機(jī)分成10份，其中9份用以訓(xùn)練，另外1份用以測試。為了使實(shí)驗結(jié)果更具有代表性，所以測試過程重復(fù)10次，每次用不同數(shù)據(jù)進(jìn)行測試。計算的分類精確度結(jié)果如表3所示。

表3 比較增量及非增量屬性約簡分類精確度Table 3 Comparison of incremental reduction method and non-incremental reduction method on classification accuracy%

從表3結(jié)果可以看出，矩陣增量和矩陣非增量約簡算法計算所得約簡的分類精確度是非常相近的，說明分布信息系統(tǒng)增量約簡算法不僅可以快速找到動態(tài)分布信息系統(tǒng)的約簡，而且在處理動態(tài)分布信息系統(tǒng)屬性約簡的問題具有較強(qiáng)的計算性能。

4 結(jié)束語

總結(jié)了分布信息系統(tǒng)的矩陣增量約簡算法的主要特點(diǎn)、涉及到的相關(guān)內(nèi)容及未來研究方向如下：

（1）給出了分布信息系統(tǒng)等價關(guān)系矩陣融合的方法及動態(tài)多源數(shù)據(jù)等價關(guān)系矩陣增量融合技術(shù)。

（2）當(dāng)一些屬性增加到分布信息系統(tǒng)后，討論了多源數(shù)據(jù)增加屬性后的分布信息系統(tǒng)的增量機(jī)制和定理。

（3）在分布信息系統(tǒng)增量機(jī)制和定理的基礎(chǔ)上，提出了多源數(shù)據(jù)矩陣增量約簡算法。

（4）分別利用矩陣增量和非增量約簡方法對UCI數(shù)據(jù)集進(jìn)行對比測試，實(shí)驗結(jié)果驗證了矩陣增量約簡算法在運(yùn)行時間上遠(yuǎn)遠(yuǎn)優(yōu)于非增量約簡算法，且兩種方法所得到的分類精確度是非常相近的。

（5）由于多源數(shù)據(jù)對象集和屬性集也會同時發(fā)生變化，如何設(shè)計多源數(shù)據(jù)對象集和屬性集同時變化后的矩陣增量屬性約簡算法是未來研究方向。