Rough Set理論及其在數(shù)據(jù)挖掘中的應(yīng)用研究.pdf

1、RoughSet(又稱Rough集、粗集、粗糙集)理論是二十世紀(jì)八十年代發(fā)展起來的一種處理不精確、不確定和模糊數(shù)據(jù)的新型數(shù)學(xué)工具，它能有效地從數(shù)據(jù)本身提供的信息中發(fā)現(xiàn)有效的、潛在的知識(shí)。近年來該理論成功地在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、智能數(shù)據(jù)分析等領(lǐng)域得到了廣泛應(yīng)用，受到了眾多學(xué)者的重視，取得了較大的發(fā)展。 論文就RoughSet理論在數(shù)據(jù)挖掘中的應(yīng)用所涉及到的一些關(guān)鍵技術(shù)問題進(jìn)行了研究。 眾所周知，在大型知識(shí)庫(kù)中，經(jīng)常存在大量

2、的冗余數(shù)據(jù)。冗余數(shù)據(jù)的存在，不僅浪費(fèi)儲(chǔ)存空間，而且干擾了人們做出正確而簡(jiǎn)潔的決策。所謂知識(shí)約簡(jiǎn)，就是在保持知識(shí)庫(kù)的分類或決策能力不變的情況下，刪去其中不相關(guān)或次要的知識(shí)。論文從信息論的角度來研究信息系統(tǒng)的知識(shí)約簡(jiǎn)問題。 論文研究和討論了RoughSet理論的代數(shù)表示和信息表示，并作了較全面、系統(tǒng)的比較和分析，并且發(fā)現(xiàn)一些規(guī)律：①當(dāng)決策表的條件屬性增多時(shí)，決策屬性集相對(duì)條件屬性集的條件熵的變化規(guī)律呈非嚴(yán)格單調(diào)遞減性；②如果知識(shí)約簡(jiǎn)

3、以決策表的核屬性集為起點(diǎn)，那么在向約簡(jiǎn)結(jié)果中添加不能約簡(jiǎn)的非核條件屬性時(shí)，決策屬性集相對(duì)約簡(jiǎn)結(jié)果的條件熵的變化規(guī)律是單調(diào)遞減的；③知識(shí)約簡(jiǎn)后決策表的條件熵等于初始決策表的條件熵。在上述規(guī)律的基礎(chǔ)上，論文提出了兩個(gè)新的基于RoughSet理論的啟發(fā)式知識(shí)約簡(jiǎn)算法：CEBARKCC算法和CEBARKNC算法。然后，論文對(duì)CEBARKCC算法、CEBARKNC算法和基于互信息的知識(shí)約簡(jiǎn)算法(MIBARK算法)的時(shí)間復(fù)雜度從理論和實(shí)驗(yàn)上做了分析

4、與比較，得到結(jié)論：若一個(gè)決策表的核值比較大，則CEBARKCC算法和MIBARK算法的效率要優(yōu)于CEBARKNC算法；反之，則CEBARKNC算法的效率要優(yōu)于CEBARKCC算法和MIBARK算法。并且，實(shí)驗(yàn)結(jié)果表明在大多數(shù)情況下，CEBARKCC算法和CEBARKNC算法能得到最小相對(duì)約簡(jiǎn)。 事實(shí)上，數(shù)據(jù)挖掘的許多對(duì)象信息是不斷增加的，如客戶信息、銷售信息、生產(chǎn)信息、網(wǎng)絡(luò)信息等。另一方面，許多系統(tǒng)要求實(shí)現(xiàn)實(shí)時(shí)在線處理，如入侵檢

5、測(cè)系統(tǒng)、郵件分析系統(tǒng)等。針對(duì)這些應(yīng)用，論文對(duì)增量式的知識(shí)獲取算法進(jìn)行了研究。 論文討論了在新增數(shù)據(jù)時(shí)，新數(shù)據(jù)(樣本)與已有知識(shí)(即規(guī)則集M)的關(guān)系，對(duì)新樣本的分類進(jìn)行了新的定義。并且，發(fā)現(xiàn)在新增樣本時(shí)屬性約簡(jiǎn)及值約簡(jiǎn)的變化規(guī)律，得到三個(gè)定理。這些定理說明：①當(dāng)新增樣本x與M匹配時(shí)，最小規(guī)則集保持不變，也就是說對(duì)于決策表最小化算法的兩個(gè)步驟都不需重新計(jì)算；②如果新樣本x與M部分矛盾或類部分矛盾或類匹配，我們可以通過比較x與新增x前

6、的論域U上各個(gè)樣本在屬性約簡(jiǎn)結(jié)果R的屬性上的值是否相等來判斷屬性約簡(jiǎn)是否改變；③增加新樣本x后的論域U'中屬性約簡(jiǎn)保持不變時(shí)，U中與x不矛盾的樣本之值約簡(jiǎn)保持不變。在這些定理的基礎(chǔ)上，論文提出了一個(gè)新的基于RoughSet理論的增量式知識(shí)獲取算法(IKAA算法)。并且從理論和實(shí)驗(yàn)上對(duì)新算法和傳統(tǒng)的基于RoughSet理論的非增量式知識(shí)獲取算法(NIKAA算法)在復(fù)雜度上做了分析與比較。研究表明：當(dāng)新樣本匹配時(shí)，IKAA算法運(yùn)行時(shí)間在數(shù)量

7、級(jí)上遠(yuǎn)小于NIKAA算法；當(dāng)新樣本是部分矛盾、類匹配、類部分矛盾，且R保持不變時(shí)，IKAA算法運(yùn)行時(shí)間小于NIKAA算法運(yùn)行時(shí)間；當(dāng)新樣本是部分矛盾、類匹配、類部分矛盾，且R變化時(shí)，IKAA算法運(yùn)行時(shí)間略大于NIKAA算法運(yùn)行時(shí)間；當(dāng)新樣本是完全矛盾、類完全矛盾時(shí)，IKAA算法運(yùn)行時(shí)間略大于NIKAA算法運(yùn)行時(shí)間。當(dāng)然，考慮到不同種類的新增樣本的比例，一般而言IKAA算法運(yùn)行時(shí)間顯然是小于NIKAA算法的運(yùn)行時(shí)間。 基于Roug

8、hSet理論的應(yīng)用研究較多，考慮到電子郵件過濾是當(dāng)前研究的熱點(diǎn)，論文擬用RoughSet理論來解決這個(gè)問題。從而提出并分析了電子郵件過濾系統(tǒng)的粗糙集模型；接著，依據(jù)電子郵件過濾系統(tǒng)的粗糙集模型，建立起相應(yīng)的信息模型；然后，提出了基于RoughSet理論的針對(duì)個(gè)人用戶的實(shí)時(shí)電子郵件過濾原型系統(tǒng)，并通過實(shí)驗(yàn)進(jìn)行了驗(yàn)證。研究表明基于RoughSet理論的電子郵件過濾分析是可行的，是該理論在計(jì)算機(jī)網(wǎng)絡(luò)信息安全領(lǐng)域具體應(yīng)用的一次嘗試。 目