多源數據矩陣增量約簡算法

徐巖柏，景運革

運城學院 數學與信息技術學院，山西 運城 044000

現實生活中，傳感器技術發展促進了各行各業產生了大量多源數據（分布數據），如何發現多源數據中隱含的知識是人工智能方向研究的一個熱點問題。近10多年來，一些研究者已經提出了許多處理多源數據的形式概念分析方法并運用它們去解決一些實際問題[1-3]。但是在現實生活中，多源數據大多都包含不確定性的信息，因此利用上述方法不能對多源數據進行精確化處理及數據分析和挖掘。

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

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

1 基于知識粒度分布信息系統約簡算法

本章簡單介紹分布信息系統相關概念和定義及分布數據約簡的方法[19-20]。

1.1 分布信息系統的基礎知識

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

1.2 分布信息系統非增量約簡算法

2 分布決策信息系統增量約簡算法

2.1 分布決策信息系統增量機制

2.2 分布系統屬性增加的矩陣增量約簡算法

2.3 時間復雜度分析

3 仿真實驗方案

3.1 實驗軟硬件環境和實驗數據集

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

表1 UCI數據集描述Table 1 Description of UCI date sets

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

3.2 屬性約簡結果比較

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

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

從圖1結果可知，矩陣增量計算動態多源數約簡的運行時間遠遠小于非增量約簡算法的運行時間，特別是對于較大數據集而言，增量約簡算法的計算性能優勢更加明顯，說明了增量約簡算法能夠提高計算動態多源數據約簡的效率。

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

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

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

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

4 結束語

總結了分布信息系統的矩陣增量約簡算法的主要特點、涉及到的相關內容及未來研究方向如下：

（1）給出了分布信息系統等價關系矩陣融合的方法及動態多源數據等價關系矩陣增量融合技術。

（2）當一些屬性增加到分布信息系統后，討論了多源數據增加屬性后的分布信息系統的增量機制和定理。

（3）在分布信息系統增量機制和定理的基礎上，提出了多源數據矩陣增量約簡算法。

（4）分別利用矩陣增量和非增量約簡方法對UCI數據集進行對比測試，實驗結果驗證了矩陣增量約簡算法在運行時間上遠遠優于非增量約簡算法，且兩種方法所得到的分類精確度是非常相近的。

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