基于粗糙集的增量式知識獲取算法研究與實現(xiàn).pdf

1、目前的數(shù)據(jù)庫系統(tǒng)可以高效地實現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計等功能，但無法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測未來的發(fā)展趨勢，缺乏挖掘數(shù)據(jù)背后隱藏的知識的手段，導(dǎo)致了“數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象。于是知識發(fā)現(xiàn)(KnowledgeDiscovery in Data，KDD)和數(shù)據(jù)挖掘(Data Mining，DM)技術(shù)應(yīng)運而生。知識發(fā)現(xiàn)是近幾年隨著數(shù)據(jù)庫和人工智能發(fā)展起來的一門新興的數(shù)據(jù)庫技術(shù)。通過知識發(fā)現(xiàn)技術(shù)，我們可以將信息變?yōu)橹?/p>

2、識，從“數(shù)據(jù)礦山”中找到蘊藏的“知識金塊”。因此，研究高效智能的知識發(fā)現(xiàn)方法具有很大的現(xiàn)實意義。 粗糙集理論是1982年由波蘭數(shù)學(xué)家Z．Pawlak教授提出來的，它是一種處理不完整、不確定信息的新型數(shù)學(xué)工具。由于粗糙集理論不需要任何預(yù)備的或額外的有關(guān)數(shù)據(jù)信息，這樣就避免了對知識的主觀評價所帶來的誤差。經(jīng)過20多年的發(fā)展，粗糙集理論不但在理論本身研究方面不斷完善，而且在其它領(lǐng)域中也得到了成功的應(yīng)用，如機器學(xué)習(xí)，決策分析，近似推理，

3、圖像處理，專家系統(tǒng)，過程控制，沖突分析，數(shù)據(jù)庫知識發(fā)現(xiàn)(KDD)，醫(yī)療診斷，金融數(shù)據(jù)分析等方面得到了較為成功的應(yīng)用。 近幾年在粗糙集理論研究中對求解屬性的最小約簡和較小約簡以及求取最簡規(guī)則集的算法已經(jīng)進(jìn)行了一些研究，但這些研究都是針對靜態(tài)數(shù)據(jù)的。而數(shù)據(jù)庫是動態(tài)的，因此許多研究者建議，數(shù)據(jù)庫知識發(fā)現(xiàn)算法應(yīng)該是增量式的。屬性最小約簡的增量式算法以及增量式更新概念格的算法已經(jīng)開始被研究，但對于增量式規(guī)則獲取算法的研究工作還比較少。在以

4、上工作的基礎(chǔ)上，本文研究了基于粗糙集的增量式規(guī)則獲取問題。 本文所做的主要工作有：介紹了粗糙集理論的發(fā)展歷程、特點、應(yīng)用領(lǐng)域和基本理論。給出了決策表中對象“相關(guān)”和“相互獨立”的定義，證明了當(dāng)新對象加入時哪些規(guī)則需要更新，提出了一個基于粗糙集和搜索樹的增量式規(guī)則提取算法。該算法在深度優(yōu)先搜索中將已獲取規(guī)則作為啟發(fā)信息，大大提高了算法的效率；在時間復(fù)雜度不變的條件下，無需建立傳統(tǒng)算法中的差別矩陣，具有較好的空間復(fù)雜度。由于現(xiàn)實中的

5、決策表往往是不一致的，為了能夠提取不確定性規(guī)則，本文引入可變精度粗糙集模型給出了基于可變精度粗糙集的增量式規(guī)則獲取算法。最后，通過實驗對比證明了算法的正確性和有效性。 本文的主要創(chuàng)新點在于： (1) 給出了一個基于粗糙集理論和搜索樹的增量式規(guī)則提取算法(RDBRDFST)。該算法引入啟發(fā)信息，無需建立差別矩陣，具有較好的時空復(fù)雜性。 (2)引入可變精度粗糙集模型給出了基于可變精度粗糙集的增量式規(guī)則獲取算法。該算法