粗糙集并行約簡算法研究.pdf

1、粗糙集理論利用上近似集和下近似集的概念解決了經(jīng)典邏輯理論中模糊概念的可計算性問題，因此它在處理不完全、不精確數(shù)據(jù)時有其獨到的優(yōu)勢:1）粗糙集理論不需要先驗知識;2）相對其它不確定性理論更加客觀、精確;3）同其它不確定性理論有很強的互補性。正是因為這些優(yōu)點，從提出之日起近三十年來，粗糙集理論得到了充分的研究和廣泛的應用。
　　 經(jīng)過多年的發(fā)展，粗糙集理論的有效性得到了充分的驗證，理論框架也日趨完備，但如何在一個動態(tài)變化的數(shù)據(jù)集中求

2、得一個穩(wěn)定的約簡這一難題一直未能得到很好的解決。雖然動態(tài)約簡理論的出現(xiàn)為解決這個難題指明了一個很好的方向，但是由于其時間復雜度是指數(shù)級的，動態(tài)約簡算法只能在那些條件屬性較少的數(shù)據(jù)上求約簡，而且由于動態(tài)約簡算法本身不完備，得到的約簡結(jié)果有可能為空，這大大限制了它的應用范圍。
　　 為了解決如何在較小的時間復雜度之內(nèi)找到盡可能穩(wěn)定的約簡這一難題，鄧大勇提出了并行約簡理論。并行約簡算法和動態(tài)約簡算法類似，都是將一個決策系統(tǒng)拓展成若干個

3、子決策表，然后再將子表的約簡結(jié)果進行整合，最終得到一個盡可能穩(wěn)定的約簡。和動態(tài)約簡窮舉式搜索子決策表的全部約簡然后進行結(jié)果整合不同的是，并行約簡可以利用啟發(fā)式信息作為判斷屬性優(yōu)劣的標準，在計算過程中就能夠判斷出條件屬性的好壞，因而不需要計算子表的全部約簡，所以并行約簡算法的時間復雜度是多項式級的。而且并行約簡是一個完備的理論，它在定義層面就已經(jīng)避免了約簡結(jié)果為空這種情況的出現(xiàn)。除此之外，并行約簡相比動態(tài)約簡還有一個優(yōu)點就是它可以利用粗糙

4、集理論所有已取得的成果。
　　 本文對并行約簡理論進行了深入研究，提出了一種改進的并行約簡算法，新算法的時間復雜度不變但得到的約簡結(jié)果長度更小。然后我們將并行約簡由代數(shù)意義拓展到信息論意義下，提出了信息論意義下的并行約簡概念及其相應算法，并探討了它的相關性質(zhì)。最后我們探討了并行約簡和動態(tài)約簡之間的一致性和差異性，將它們進行了統(tǒng)一。具體而言，本文做了如下工作:
　　 (1)第1章對粗糙集理論進行了簡單的綜述;第2章引入了粗

5、糙集理論的一些基本概念和知識，比較分析了三種比較簡單常用且與并行約簡算法相關的決策表屬性約簡算法。
　　 (2)第3章深入研究了鄧大勇提出的并行約簡概念及其相應算法。因為基本概念和算法框架都是以代數(shù)論知識為基礎構(gòu)建起來的，所以第3章中介紹的并行約簡又叫代數(shù)意義下的并行約簡。
　　 (3)第4章提出了一種改進的代數(shù)并行約簡算法，優(yōu)化了原算法的屬性挑選策略，改進后的算法時間復雜度不變但求得的約簡結(jié)果更加精簡、穩(wěn)定。雖然在理論

6、上改進后的算法和改進前算法具有相同的時間復雜度，但由于約簡結(jié)果更加精簡、算法迭代次數(shù)更少，實際實驗時改進后的算法的時間開銷比改進前的算法小了不少。
　　 (4)第5章將并行約簡理論由代數(shù)論拓展到了信息論，用信息論中的概念和知識定義了信息論意義下的并行約簡概念。信息論意義下的并行約簡算法沿用了代數(shù)論意義下的并行約簡算法的算法框架，只是屬性重要度的衡量方式和算法的截止條件做了變化，因此該算法的時間復雜度和代數(shù)意義下的并行約簡相同。信