徐巖柏，景運(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ù)中隱含的知識(shí)是人工智能方向研究的一個(gè)熱點(diǎn)問題。近10多年來，一些研究者已經(jīng)提出了許多處理多源數(shù)據(jù)的形式概念分析方法并運(yùn)用它們?nèi)ソ鉀Q一些實(shí)際問題[1-3]。但是在現(xiàn)實(shí)生活中，多源數(shù)據(jù)大多都包含不確定性的信息，因此利用上述方法不能對(duì)多源數(shù)據(jù)進(jìn)行精確化處理及數(shù)據(jù)分析和挖掘。

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)方案

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

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

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

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

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

3.3 屬性約簡(jiǎn)分類精確度分析比較

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

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

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

4 結(jié)束語

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

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

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

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

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

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