基于分類模型的知識發(fā)現(xiàn)機理和方法研究.pdf

1、知識發(fā)現(xiàn)(KDD，KnowledgeDiscoveryinDatabases)是從數(shù)據(jù)中獲取知識的一種智能信息處理技術(shù)。本論文在深入分析國內(nèi)外相關(guān)研究成果的基礎(chǔ)上，首先利用粒度計算理論，獨立于具體算法，展開對基于分類模型的知識發(fā)現(xiàn)機理的研究，以探討信息系統(tǒng)中知識形成的一般性規(guī)律和內(nèi)在機制，并由此分析KDD研究中若干問題及其存在的根源。然后，在充分研究多種面向KDD的計算方法的基礎(chǔ)上，提出新的理論和方法，對個性化知識發(fā)現(xiàn)、效率和準(zhǔn)確率問題

2、以及KDD算法的早熟收斂等問題展開了研究，形成一套有效的解決方法，拓展了傳統(tǒng)的知識發(fā)現(xiàn)方法。本文的主要工作及創(chuàng)新性成果如下： 提出并構(gòu)造信息系統(tǒng)的知識粒度空間——超粒度空間(SGS)和全粒度空間(AllGS)，找到了定義于超粒度空間之上的格和布爾代數(shù)。利用格的性質(zhì)，得到了全粒度空間的結(jié)構(gòu)模型——超樹，其節(jié)點代表全粒度空間中的粒度。布爾代數(shù)、格和超樹及其有關(guān)性質(zhì)，進一步豐富和完善了KDD的幾何和代數(shù)理論體系，初步形成了信息系統(tǒng)知識

3、空間的數(shù)學(xué)模型和拓?fù)浣Y(jié)構(gòu)。在現(xiàn)有決策邏輯語言的基礎(chǔ)上，定義用于粒度描述的正基語言，提出并研究“全粒度空間+正基語言，，的粒度計算模型，找到了正基語言系統(tǒng)、全粒度空間和基本概念空間的關(guān)系，證明了這種關(guān)系是正基語言系統(tǒng)到全粒度空間的一個滿射。進而分析了知識的形成機理和個性化知識發(fā)現(xiàn)問題存在的根源，把知識發(fā)現(xiàn)歸結(jié)為，在全粒度空間(或超樹)中搜索各目標(biāo)概念的最佳粒度表示并形成其有效描述的過程。顯然，該過程是基于提出的模型，而粒度空間、超樹、格和

4、布爾代數(shù)等的有關(guān)性質(zhì)由此而得到完美的結(jié)合并在搜索過程中發(fā)揮重要的啟發(fā)作用。同時，分析了一些KDD算法存在早熟收斂、局部知識產(chǎn)生的原因等，提出本文解決方法的基本思路。 基于RS理論提出完備的個性化屬性約簡算法——DA-FPR算法。該算法的特點是，首先構(gòu)造分辨矩陣的極小全空間以及基于空間的Θ_簡化運算和x_子化運算；然后在用戶偏好的作用下，通過交替用運這兩種運算(交替次數(shù)不超過條件屬性集的大小)，逐步去除用戶不感興趣的條件屬性，最終

5、使得極小全空間收斂于單目空間；最后可由單目空間直接得到所需的約簡。實驗表明，極小全空間的規(guī)模與訓(xùn)練集規(guī)模幾乎無正比關(guān)系，算法時間開銷主要是用于構(gòu)建極小全空間；而之后的操作基本上是基于條件屬性集合的簡單運算，其時間開銷與前面相比，是非常小的，所以算法具有較高的效率；并在與已有方法對比的基礎(chǔ)上證實了算法的有效性。文中還從理論上證明了DA-FPR算法的有效性、收斂性和完備性。 提出規(guī)則約簡算法——DA-FPDR算法和決策算法極小化算法

6、——PA-MRS算法。前者對每一條規(guī)則去除其中用戶不感興趣的屬性-值對，后者則進一步去掉用戶不感興趣的整條規(guī)則。這樣，與DA-FPR算法一起，這三個算法的有機結(jié)合就構(gòu)成了個性化知識發(fā)現(xiàn)的一個完整的解決方法——PKDA算法。PKDA算法通過層層去除用戶不感興趣信息的方法，最終發(fā)現(xiàn)符合用戶需要的個性化知識。從而為當(dāng)前KDD領(lǐng)域中的研究熱點之一——“發(fā)現(xiàn)用戶感興趣的知識”，作出貢獻。 從分析進化計算的產(chǎn)生根源入手，探討了以人類進化為核

7、心的文化進化機制，首次提出粒度進化計算(GEC)，它包括群進化和超群進化，是兩者的有機結(jié)合。如果說進化計算是模擬達爾文生物進化機制而發(fā)展起來的一種計算方法，那么粒度進化計算則是在模仿文化進化機制的基礎(chǔ)上，綜合了Agent技術(shù)以及粒度計算、進化計算的理論和方法而提出的一種智能計算方法。較之生物進化，文化進化速度快、效果佳，其中必蘊藏著非常有效的機制。所以探討這種進化機制有望為一些復(fù)雜問題的解決提供一種新的方法。 針對KDD算法存在

8、的早熟收斂性和低效性等問題，在深入分析基于進化計算的KDD算法研究進展和研究成果的基礎(chǔ)上，利用粒度進化的基本思想，以MAS為支撐技術(shù)，提出并設(shè)計了面向分類問題的粒度進化算法(GEA)。GEA算法不但能夠把復(fù)雜的搜索問題轉(zhuǎn)化為若干個簡單的搜索問題，減少問題的計算復(fù)雜性，加快收斂過程，提高算法效率，而且使得在進化過程中把Michigan方法和Pittsburgh方法的優(yōu)點有機地結(jié)合起來，有效保持個體的多樣性，減少算法陷入局部最優(yōu)的機會，提高

9、其全局搜索能力。實驗表明，粒度進化算法在這面的性能優(yōu)于已有方法。 總之，本文基于分類模型利用粒度計算的基本原理，研究信息系統(tǒng)知識空間的結(jié)構(gòu)特性和代數(shù)性質(zhì)，從而分析知識的形成機理，進一步豐富和完善知識發(fā)現(xiàn)的理論體系。在深入研究現(xiàn)有的知識發(fā)現(xiàn)方法的基礎(chǔ)上，對“發(fā)現(xiàn)用戶感興趣的知識”、知識發(fā)現(xiàn)算法的早熟收斂和局部知識的產(chǎn)生問題，以及效率和分類準(zhǔn)確率問題等進行了研究，提出相應(yīng)的解決方法。文中，對提出的重要定理和性質(zhì)，都作了論證和說明；對