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

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

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

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

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

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

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