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

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

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

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

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

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

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

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

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