發(fā)布時(shí)間：2017-09-15 08:44

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

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

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

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

，

本文編號(hào)：855504