版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、粗糙集理論是波蘭數(shù)學(xué)家Z.Pawlak于1982年提出的一種分析不完整、不確定、不精確數(shù)據(jù)的有效的數(shù)學(xué)理論。它與其它處理不確定或不精確問題理論有著最為顯著的區(qū)別,那就是不需要提供問題所需處理的數(shù)據(jù)集合之外的任何先驗信息,就可以直接對數(shù)據(jù)進行分析和推理,從中發(fā)現(xiàn)其隱含的知識,揭示其潛在的規(guī)律。近年來,粗糙集理論在模式識別、機器學(xué)習(xí)等領(lǐng)域中取得良好的成果和廣泛的應(yīng)用。它作為一種較新的數(shù)據(jù)分析與處理工具,已經(jīng)越來越受到學(xué)術(shù)界的重視,其中的一個
2、研究熱點是有效算法的研究及應(yīng)用。目前,主要有屬性約簡算法,決策規(guī)則提取算法,與粗糙集有關(guān)的神經(jīng)網(wǎng)絡(luò)和遺傳算法等。其中,屬性約簡算法是粗糙集理論及應(yīng)用的重要研究內(nèi)容之一。到目前為止,已有許多學(xué)者通過設(shè)計啟發(fā)信息,給出了較好的用差別矩陣設(shè)計基于正區(qū)域的屬性約簡算法,這種設(shè)計思想直觀簡潔。但是存儲差別矩陣需要較大的存儲空間,對于大規(guī)模數(shù)據(jù)集的處理,這種設(shè)計方法并不理想。并且,由于差別矩陣中存在大量的重復(fù)的和無用的差別元素,而這些重復(fù)的和無用的
3、差別元素既占用存儲空間,又在計算屬性約簡時浪費時間。因此,若能不生成這些重復(fù)的元素,則可以大大提高屬性約簡算法的效率。
本文對粗糙集理論的基本概念,目前各種屬性約簡算法及求所有屬性約簡算法進行了探討與分析,指出現(xiàn)有算法的優(yōu)點與不足。針對存在的問題和不足,以元素在簡化差別矩陣中出現(xiàn)的頻率作為啟發(fā)式信息,設(shè)計出一種基于Skowron差別矩陣的高效屬性約簡算法。再提出了一種新的數(shù)據(jù)結(jié)構(gòu)——壓縮樹(C_Tree),然后用這種新型的數(shù)據(jù)
4、結(jié)構(gòu)設(shè)計出相應(yīng)的算法,并通過實例和實驗證明本文所提出的新算法的可行性與有效性。
具體而言,主要研究工作如下:
(1)簡述粗糙集理論及其發(fā)展現(xiàn)狀,介紹屬性約簡及其算法與所有屬性約簡及其算法的研究現(xiàn)狀,并分析其優(yōu)缺點。同時,也介紹了粗糙集理論的基本概念。
(2)從現(xiàn)有的基于差別矩陣的屬性約簡算法出發(fā),以屬性在簡化差別矩陣中出現(xiàn)的頻率作為啟發(fā)式信息,設(shè)計出一種基于Skowron差別矩陣的高效屬性約簡算法。其時間和
5、空間復(fù)雜度分別降低到O(| C|| U|)+ O(| C|2| U/ C|)和O(| U|)。并用實例說明了這個新算法的有效性和可行性。
(3)結(jié)合FP樹(頻繁模式樹)的思想,設(shè)計出一種新型的數(shù)據(jù)結(jié)構(gòu)——壓縮樹(C_Tree)。在壓縮樹中,不但可以完全刪除差別矩陣中所有重復(fù)的差別元素,而且可以完全刪除無用的差別元素。這樣,不僅減少大量的存儲空間,還可以大大提高屬性約簡算法的效率。
(4)基于壓縮樹(C_Tree),設(shè)
6、計出快速的屬性約簡算法,該算法不用計算差別矩陣中大量的重復(fù)差別元素和無用差別元素,算法效率較高,尤其適用于大型數(shù)據(jù)庫的處理。分析了算法在最壞情況下的時間復(fù)雜度和空間復(fù)雜度分別為max{O(| C|| U|), O(| C|| U/ C|| POS C( D)/ C|)}和max{O(| U|, O(| N1|)}。其中|C|表示條件屬性的個數(shù),|U|表示決策表中對象的個數(shù),|N1|表示壓縮樹(C_Tree)中的節(jié)點數(shù)。用實例說明,并用實
7、驗證明了其有效性和可行性。
(5)對于基于壓縮樹(C_Tree)求所有屬性約簡算法,該算法不用計算差別矩陣中大量的重復(fù)差別元素和無用差別元素,算法效率得到大大的提高。分析了該算法在最壞情況下的時間復(fù)雜度和空間復(fù)雜度分別為max{O(| C|| U|), O(| C|2| U/ C|| POS C( D)/ C|)和max{O(| U|, O(| N1|)}。其中|C|表示條件屬性的個數(shù),|U|表示決策表中對象的個數(shù),|N1|表
8、示壓縮樹(C_Tree)中的節(jié)點數(shù)。用實例說明該算法的有效性和可行性。
本論文主要有以下創(chuàng)新點:
(1)以屬性在簡化差別矩陣中出現(xiàn)的頻率作為啟發(fā)式信息,設(shè)計出一種基于Skowron差別矩陣的高效屬性約簡算法,其時間和空間復(fù)雜度分別降低到O(| C|| U|)+O(| C|2| U/ C|)和O(| U|)。
(2)指出了當(dāng)前的用差別矩陣設(shè)計基于正區(qū)域的屬性算法研究中,沒有刪除由不同等價類產(chǎn)生的重復(fù)差別元素,
9、也不能刪除所有無用的差別元素。從而影響了屬性約簡算法的效率。
(3)針對本文提出的問題,結(jié)合FP樹(頻繁模式樹)思想,設(shè)計出一種新型的數(shù)據(jù)結(jié)構(gòu)——壓縮樹(C_Tree)。用壓縮樹存儲差別矩陣中的差別元素,不但可以完全刪除差別矩陣中所有重復(fù)的差別元素,而且可以完全刪除無用的差別元素。
(4)利用壓縮樹,設(shè)計出一種快速的屬性約簡算法和一種高效的完備屬性約簡算法。
本文所提出的新型數(shù)據(jù)結(jié)構(gòu)以FP樹(頻繁模式樹)構(gòu)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 基于決策樹和信息熵的屬性約簡算法研究.pdf
- 基于屬性重要度的屬性約簡算法研究.pdf
- 基于決策樹的屬性約簡方法研究.pdf
- 基于粗糙集屬性約簡的決策樹分類算法的研究.pdf
- 基于Rough Set的屬性約簡算法研究.pdf
- 基于進化算法的屬性約簡方法研究.pdf
- 規(guī)則約簡及屬性約簡算法研究.pdf
- 基于信息熵的屬性約簡算法研究.pdf
- 基于區(qū)分矩陣的屬性約簡算法研究.pdf
- 基于粗糙集理論的屬性約簡與決策樹分類算法研究.pdf
- 基于知識粒度的動態(tài)屬性約簡算法研究.pdf
- 基于遺傳蟻群算法的屬性約簡研究.pdf
- 基于粗糙集屬性約簡算法的研究.pdf
- 基于粗糙集的屬性約簡和決策規(guī)則約簡算法.pdf
- 基于遺傳算法的屬性約簡算法研究與實現(xiàn).pdf
- 屬性約簡算法的研究與實現(xiàn).pdf
- 基于信息熵的屬性約簡算法研究與實現(xiàn).pdf
- 基于分塊差別矩陣的增量屬性約簡算法研究.pdf
- 屬性增加時基于矩陣方法的增量屬性約簡算法
- 概念格屬性約簡算法研究.pdf
評論
0/150
提交評論