本文關鍵詞：基于濃縮差別矩陣的不完備信息系統的規(guī)則獲取算法研究

  更多相關文章： 屬性約簡 規(guī)則獲取 濃縮差別矩陣 二叉樹 布爾沖突矩陣

【摘要】：隨著科學技術的發(fā)展、網絡的普及,大量的信息都得以保存,人們想要快速的搜索到自己需要的信息變得更加困難。粗糙集理論作為一種較新的軟計算方法,目前在國際上仍然是人工智能理論及其應用領域中的研究熱點之一,由于它是在模糊集、概率論及證據理論之后出現的又一個處理不確定性的數學工具,且其能夠有效的在許多科學與工程領域中得以應用,所以,越來越受到人們的重視。粗糙集理論起初主要研究對象是針對完備信息系統的,然而現實生活中的數據可能是遺漏型或缺省型的,傳統的粗糙集理論就不能夠再像原來一樣處理這類信息系統了。怎樣利用粗糙集理論來處理這類信息系統成為了國內外學者和專家的研究熱點,他們最先想到兩種辦法來解決這類問題,一種是將完備信息系統中的等價關系理論延伸到不完備信息系統中去,因而產生了容差關系和相似關系等擴展模型；另一種則是通過將不完備信息系統的空缺值補充起來,使它成為完備的信息系統,然后再來處理。規(guī)則獲取是粗糙集理論的一項重要研究內容,它主要包含屬性約簡及屬性值約簡。屬性約簡的目的是為了盡量化簡原始數據,且不會改變原始數據背后的隱藏規(guī)則及數據之問的關系。且屬性約簡的結果也是為了能夠更好的進行屬性值約簡,達到規(guī)則獲取的目的。因而,研究粗糙集理論的多種擴展模型和知識獲取方法在不完備信息系統中有著極其重要的理論與現實意義。本文在前人研究的基礎之上對粗糙集理論中的屬性約簡以及規(guī)則獲取方面進行了研究學習,主要進行了下面三個方面的研究：(1)差別矩陣方法因簡單方便,被許多學者使用。然而,對于現實中所面對的海量數據,傳統的差別矩陣方法不僅費時且占用空間大而使得效率不高。有學者使用元素之間相互比較的方法來構造濃縮差別矩陣的算法,其算法時間復雜度達到O(|C‖U|4),因此,并不適合用來處理大數據。也有研究者將差別元素壓縮存儲到FP樹上,減少了存儲的空間,但卻并沒能夠去掉那些無用的元素,為此,我們設計一種改進算法,引入二叉樹的思想,循環(huán)采用短差別元素建立二義樹,長差別元素依次查找比較的方法,然后在此基礎之上,引入了擴展的二進制差別矩陣,并直接從矩陣中提取規(guī)則,使得新算法的時間復雜度降到了max{O(|C‖U|2),O(|C|2|Upos‖U|)}。實驗證明,設計的濃縮差別矩陣的規(guī)則獲取算法是高效可行的。(2)由于大型決策表求解差別矩陣時費時且需要用到大量的存儲空間,使得屬性約簡算法的效率不高。為了不僅能降低差別矩陣的存儲空間，還能運用到差別矩陣的思想,引入了區(qū)分對象對集的思想,以知識粒度為啟發(fā)信息,引入分布計數排序法求容差類,并結合沖突域的思想,使得算法時空復雜度分別降到了max{O(|C‖U|),O(|C‖U|α|2}(a∈C)及max{O(|U|),O(|U|α|2)}(a∈C)。最后實驗證明該算法是一種高效可行的屬性約簡算法。(3)為了降低屬性約簡算法的復雜度,在布爾沖突矩陣的基礎上,定義了一個啟發(fā)函數,該函數能求出決策表中條件屬性導致的沖突個數,同時給出了計算該啟發(fā)函數的快速算法。然后用該啟發(fā)函數設計了一個有效的關于不完備決策表的改進的布爾沖突矩陣的高效屬性約簡算法,該算法將時間復雜度降到了D(|K‖C‖U|)(|K|=,max{|Tp(xi)‖xi∈U})。最后實驗結果說明了新算法的有效性。
【關鍵詞】：屬性約簡 規(guī)則獲取 濃縮差別矩陣 二叉樹 布爾沖突矩陣
【學位授予單位】：廣西師范大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP18
【目錄】：

• 摘要3-5
• Abstract5-9
• 第1章 緒論9-14
• 1.1 論文研究背景9-10
• 1.2 粗糙集理論概述10-12
• 1.2.1 粗糙集理論的產生與發(fā)展10-11
• 1.2.2 粗糙集理論應用研究現狀11-12
• 1.3 論文的研究意義和目的12
• 1.4 論文的主要創(chuàng)新點12-13
• 1.5 論文的構造情況13-14
• 第2章 粗糙集理論的基本概念14-22
• 2.1 知識的分類和表示14-15
• 2.2 決策表相關的概念15-17
• 2.2.1 完備決策表的相關定義15-16
• 2.2.2 不完備決策表的相關定義16-17
• 2.3 完備決策表的屬性約簡的相關定義17-19
• 2.3.1 基于正區(qū)域模型的相關定義17-18
• 2.3.2 基于差別矩陣模型的相關定義18
• 2.3.3 基于信息熵模型的相關定義18-19
• 2.3.4 基于知識粒度模型的相關定義19
• 2.4 不完備決策系統屬性約簡相關定義19-21
• 2.4.1 基于正區(qū)域模型的相關定義19
• 2.4.2 基于差別矩陣模型的相關定義19-20
• 2.4.3 基于廣義決策函數的相關定義20
• 2.4.4 基于知識粒度模型的相關定義20-21
• 2.5 本章小結21-22
• 第3章 基于濃縮差別矩陣的規(guī)則獲取算法22-36
• 3.1 算法的設計思路22
• 3.2 濃縮差別矩陣屬性約簡及規(guī)則獲取的相關定義22-24
• 3.3 基于濃縮差別矩陣的規(guī)則獲取算法24-29
• 3.4 算法的復雜度分析29
• 3.5 實例驗證29-33
• 3.6 實驗驗證33-35
• 3.7 本章小結35-36
• 第4章 基于沖突域的區(qū)分對象對的屬性約簡算法36-41
• 4.1 算法的設計思路36
• 4.2 基于區(qū)分對象對的屬性約簡相關定義36-37
• 4.3 基于沖突域的區(qū)分對象對的屬性約簡算法37-39
• 4.4 算法的復雜度分析39
• 4.5 實例驗證39-40
• 4.6 實驗驗證40
• 4.7 本章小結40-41
• 第5章 布爾沖突矩陣的高效屬性約簡算法41-48
• 5.1 算法的設計思路41
• 5.2 布爾沖突矩陣的高效屬性約簡算法的相關定義41-43
• 5.3 布爾沖突矩陣的高效屬性約簡算法43-44
• 5.4 算法的復雜度分析44
• 5.5 實例驗證44-45
• 5.6 實驗驗證45-47
• 5.7 本章小結47-48
• 第6章 總結與展望48-50
• 6.1 全文總結48
• 6.2 問題和展望48-50
• 參考文獻50-55
• 攻讀碩士學位期間科研成果55-56
• 致謝56-57

，

本文編號：855504