基于粗糙集的屬性約簡和核的快速更新算法研究.pdf

1、粗糙集理論是由波蘭科學(xué)家Z.Pawlak在1982年提出的一種處理模糊、不精確知識和不完備信息的數(shù)學(xué)工具。該理論的特點是不需要任何先驗的知識,或者任何附加的信息,就能有效地分析和處理這類數(shù)據(jù),從中發(fā)現(xiàn)隱含的知識,揭示潛在的規(guī)律性,即決策規(guī)則。近年來,粗糙集理論在人工智能和認(rèn)知科學(xué)領(lǐng)域具有重要的地位,特別是在知識發(fā)現(xiàn)、機器學(xué)習(xí)、決策分析、過程控制、模式識別、數(shù)據(jù)挖掘和專家系統(tǒng)等領(lǐng)域得到了廣泛應(yīng)用。在粗糙集理論中,屬性約簡和求核是重要的研究

2、內(nèi)容之一。屬性約簡,就是在保持知識庫(決策表)中分類能力不變的情況下,刪除知識庫中無關(guān)或不重要的屬性,使得知識庫中的知識表示得到簡化,而又不丟失其基本信息,如果能將冗余屬性刪除,則可以減小知識庫規(guī)模,節(jié)約成本,并能提高知識庫中潛在知識的清晰度。由于對知識庫進(jìn)行屬性約簡,很多算法都是以核為基礎(chǔ),然后在核的基礎(chǔ)上逐步得到屬性約簡,因此,研究快速的屬性約簡和求核算法具有重要的理論意義和應(yīng)用價值。目前,現(xiàn)有的大多數(shù)算法均是以靜態(tài)決策表為基礎(chǔ)而設(shè)

3、計的,而針對動態(tài)決策表的算法的研究較少,但實際決策表中的對象通常是動態(tài)變化的,故原來的核和屬性約簡可能已經(jīng)不再是新決策表的核和屬性約簡,為此需要對新決策表進(jìn)行重新計算。在以靜態(tài)決策表為基礎(chǔ)的屬性約簡和求核算法中,對于更新后而變化不大的新決策表而言,將會使得原來算法中大量有用的信息沒有得到有效的利用,特別是對一些實時性要求較高的場合,這種以靜態(tài)決策表為基礎(chǔ)的屬性約簡和求核算法往往不大適用,因此,研究高效的動態(tài)更新算法具有廣泛的實際意義。<

4、br>　　本文首先簡單介紹了粗糙集理論的研究動態(tài)和基礎(chǔ)理論知識,然后系統(tǒng)地概述了現(xiàn)有的基于決策表的常見屬性約簡和求核的模型及相關(guān)算法,其中包括基于正區(qū)域的算法、基于差別矩陣的算法、基于信息熵的算法。
　　本文在學(xué)習(xí)和借鑒已有研究成果的基礎(chǔ)上,主要的創(chuàng)新點如下:1)利用位圖和粒計算技術(shù)提出了一種改進(jìn)的基于正區(qū)域的屬性約簡(Pawlak Reduction)新算法。在該屬性約簡算法中,設(shè)計了一種能減少粒計算數(shù)目的啟發(fā)式信息,有效地減少

5、了不影響屬性約簡結(jié)果的大量計算,并通過實例仿真和實驗結(jié)果表明了新算法的有效性和正確性。2)給出一個簡化二進(jìn)制差別矩陣的屬性約簡定義,從理論上分析證明了該屬性約簡的定義與基于信息熵的屬性約簡的定義是等價的。為求出簡化的二進(jìn)制差別矩陣,采用了一個快速求簡化決策表的算法。在此基礎(chǔ)上,設(shè)計了基于信息熵的簡化二進(jìn)制差別矩陣屬性約簡算法,并分析了算法的時間復(fù)雜度和空間復(fù)雜度分別為max{O(| C|| U|), O(| C|2| U′|2)}和ma

6、x{O(| C|| U′|2), O(| U|)},并通過實例仿真顯示新算法的效率優(yōu)于典型的算法。3)分析了現(xiàn)有的常見求核增量式算法的不足,為了有效地提高動態(tài)決策表的核增量式更新效率,本文首先引入簡化決策表,然后結(jié)合簡化的二進(jìn)制差別矩陣設(shè)計了一種新的基于決策表的核增量式高效更新算法。該算法在更新簡化的二進(jìn)制差別矩陣時,只需在原決策表基礎(chǔ)上對記錄進(jìn)行相應(yīng)的更新,不需要重復(fù)計算原決策表的二進(jìn)制差別矩陣。采用邊更新簡化二進(jìn)制差別矩陣邊計算核,

7、顯著地提高了動態(tài)更新核的效率和靈活性。算法的時間復(fù)雜度和空間復(fù)雜度分別為O(| C|| U′|)和O(| C|| U′p os|| U′|),并通過實例仿真和實驗性能對比表明了新算法的有效性。4)由于對決策表進(jìn)行屬性約簡,很多算法都是以核為基礎(chǔ),然后逐步得到屬性約簡。
　　本文在3)增量式更新核的基礎(chǔ)上,利用位圖技術(shù),并結(jié)合簡化的二進(jìn)制差別矩陣設(shè)計了一種新的基于決策表的屬性約簡增量式快速更新算法,算法的時間復(fù)雜度和空間復(fù)雜度分別為