基于濃縮差別矩陣的不完備信息系統(tǒng)的規(guī)則獲取算法研究.pdf

1、隨著科學技術的發(fā)展、網(wǎng)絡的普及，大量的信息都得以保存，人們想要快速的搜索到自己需要的信息變得更加困難。粗糙集理論作為一種較新的軟計算方法，目前在國際上仍然是人工智能理論及其應用領域中的研究熱點之一，由于它是在模糊集、概率論及證據(jù)理論之后出現(xiàn)的又一個處理不確定性的數(shù)學工具，且其能夠有效的在許多科學與工程領域中得以應用，所以,越來越受到人們的重視。
　　粗糙集理論起初主要研究對象是針對完備信息系統(tǒng)的，然而現(xiàn)實生活中的數(shù)據(jù)可能是遺漏型或

2、缺省型的，傳統(tǒng)的粗糙集理論就不能夠再像原來一樣處理這類信息系統(tǒng)了。怎樣利用粗糙集理論來處理這類信息系統(tǒng)成為了國內外學者和專家的研究熱點，他們最先想到兩種辦法來解決這類問題，一種是將完備信息系統(tǒng)中的等價關系理論延伸到不完備信息系統(tǒng)中去，因而產(chǎn)生了容差關系和相似關系等擴展模型;另一種則是通過將不完備信息系統(tǒng)的空缺值補充起來，使它成為完備的信息系統(tǒng)，然后再來處理。
　　規(guī)則獲取是粗糙集理論的一項重要研究內容，它主要包含屬性約簡及屬性值約

3、簡。屬性約簡的目的是為了盡量化簡原始數(shù)據(jù)，且不會改變原始數(shù)據(jù)背后的隱藏規(guī)則及數(shù)據(jù)之間的關系。且屬性約簡的結果也是為了能夠更好的進行屬性值約簡，達到規(guī)則獲取的目的。因而，研究粗糙集理論的多種擴展模型和知識獲取方法在不完備信息系統(tǒng)中有著極其重要的理論與現(xiàn)實意義。
　　本文在前人研究的基礎之上對粗糙集理論中的屬性約簡以及規(guī)則獲取方面進行了研究學習，主要進行了下面三個方面的研究:
　　(1)差別矩陣方法因簡單方便，被許多學者使用。然

4、而，對于現(xiàn)實中所面對的海量數(shù)據(jù)，傳統(tǒng)的差別矩陣方法不僅費時且占用空間大而使得效率不高。有學者使用元素之間相互比較的方法來構造濃縮差別矩陣的算法，其算法時間復雜度達到O(| C‖U|4)，因此，并不適合用來處理大數(shù)據(jù)。也有研究者將差別元素壓縮存儲到FP樹上，減少了存儲的空間，但卻并沒能夠去掉那些無用的元素，為此，我們設計一種改進算法，引入二叉樹的思想，循環(huán)采用短差別元素建立二叉樹，長差別元素依次查找比較的方法，然后在此基礎之上，引入了擴展

5、的二進制差別矩陣，并直接從矩陣中提取規(guī)則，使得新算法的時間復雜度降到了max{O(|C‖U|2),O(|C|2|Upos‖|U|)}。實驗證明，設計的濃縮差別矩陣的規(guī)則獲取算法是高效可行的。
　　(2)由于大型決策表求解差別矩陣時費時且需要用到大量的存儲空間，使得屬性約簡算法的效率不高。為了不僅能降低差別矩陣的存儲空間，還能運用到差別矩陣的思想，引入了區(qū)分對象對集的思想，以知識粒度為啟發(fā)信息，引入分布計數(shù)排序法求容差類，并結合沖突

6、域的思想，使得算法時空復雜度分別降到了max{O(| C‖ U|)，O(| C‖ U/a|2}(a∈C)及max{O(| U|)，O(| U/a|2}(a∈C)。最后實驗證明該算法是一種高效可行的屬性約簡算法。
　　(3)為了降低屬性約簡算法的復雜度，在布爾沖突矩陣的基礎上，定義了一個啟發(fā)函數(shù)，該函數(shù)能求出決策表中條件屬性導致的沖突個數(shù)，同時給出了計算該啟發(fā)函數(shù)的快速算法。然后用該啟發(fā)函數(shù)設計了一個有效的關于不完備決策表的改進的布