基于濃縮差別矩陣的不完備信息系統(tǒng)的屬性約簡算法研究.pdf

1、如何從海量數(shù)據(jù)中提取最有用的信息，對當今的網(wǎng)絡(luò)架構(gòu)和數(shù)據(jù)處理能力來說是一個大的挑戰(zhàn)。Rough Sets理論作為當今數(shù)據(jù)處理中比較新穎的軟計算方法，有效性在眾多科學與工程領(lǐng)域得到證實之后，繼概率論、模糊集及證據(jù)理論之后的又一個處理不確定性的數(shù)學工具，越來越受世人重視。
　　屬性約簡是Rough Sets理論的核心問題之一，它是在不影響信息系統(tǒng)分類能力的情況基礎(chǔ)上，消除冗余數(shù)據(jù)，提取知識庫中未知的、隱含的簡潔的知識，即用最少的屬性組

2、合揭示其潛在的有價值的信息。屬性的組合爆炸是使屬性約簡的求解成為一個NP難問題得最主要原因。隨著大數(shù)據(jù)時代的到來及數(shù)據(jù)庫技術(shù)的迅速發(fā)展，科研機構(gòu)、政府單位、企業(yè)等各大領(lǐng)域數(shù)據(jù)呈指數(shù)遞增且這些大數(shù)據(jù)雜亂無章，也存在很多的強干擾的數(shù)據(jù)。如此的海量數(shù)據(jù)對人類處理數(shù)據(jù)、分析數(shù)據(jù)能力是一個大挑戰(zhàn)，至今屬性約簡的求解仍然沒有一個高效可行的方法，因此求解高效的屬性約簡算法仍是Rough Sets理論的研究熱點。
　　在很多現(xiàn)實情況下，因人類思維

3、的局限性對外界環(huán)境不能做出完整、準確的判斷、數(shù)據(jù)采集技術(shù)有限、傳輸媒體故障、及時間因素的影響（比如，醫(yī)院的診斷系統(tǒng)，對于病員對象集合，病人的一些臨床檢驗結(jié)果屬性值，在給定的時間里是不可能拿到所有的檢驗結(jié)果的），數(shù)據(jù)采集過程中數(shù)據(jù)丟失或數(shù)據(jù)的可信度降低，不完整的數(shù)據(jù)信息會造成數(shù)據(jù)失真，得到的知識規(guī)則也不可靠，不可靠的只是規(guī)則干擾人們做出正確的決策?；趥鹘y(tǒng)的不分明關(guān)系的Rough Sets理論只能處理所有屬性值已知且確定的完備信息系統(tǒng)，不

4、能處理一些數(shù)據(jù)缺失的不完備信息系統(tǒng)。因此在不完備信息系統(tǒng)中研究各種Rough集理論的擴展模型及其知識獲取方法有著極其重要的理論與現(xiàn)實意義。
　　本文基于Rough Sets理論及差別矩陣的方法研究不完備信息系統(tǒng)屬性約簡方法，主要研究工作有以下幾個方面:
　　(1)以不完備決策表為研究對象，引入濃縮差別矩陣的概念，采用布爾與思想，給出了不完備信息系統(tǒng)下基于布爾與的濃縮差別矩陣屬性約簡算法。最后通過一個實例驗證了濃縮差別矩陣在屬

5、性約簡算法中的優(yōu)越性，且通過UCI實驗證明了濃縮差別矩陣的使用價值。
　　(2)差別矩陣方法易懂，易設(shè)計被廣大學者接受并使用。然而，對于大型數(shù)據(jù)而言，計算差別矩陣時不僅費時，而且會占用大量的存儲空間，使得算法的效率不高。有學者利用差別元素間兩兩比較的方法構(gòu)造濃縮差別矩陣的算法，設(shè)計的算法時間復雜度為O(|C‖U|4)，由于時間復雜度過高，不適用大數(shù)據(jù)的處理。還有一些學者將差別元素壓縮存儲在一棵FP樹上，雖然減少了存儲空間，但并沒有

6、去掉那些無用的元素，為此，我們設(shè)計了一種改進的基于二叉樹的不完備濃縮差別矩陣屬性約簡算法算法，采用短差別集插入長差別集依次比較查找的方法，使得新算法的時間復雜度降為O(|C|2|U|2)。
　　(3)在對區(qū)分對象對集進一步研究中，區(qū)分對象對集算法時空復雜度還是不夠理想，為此，在區(qū)分對象對集基礎(chǔ)上，設(shè)計一個能計算區(qū)分對象對集的個數(shù)的函數(shù)，并用該函數(shù)設(shè)計了一個啟發(fā)函數(shù)，同時給出該啟發(fā)函數(shù)的快速算法，利用啟發(fā)函數(shù)設(shè)計了一個高效的不完備決