- 相關(guān)推薦
基于GP算法的知識(shí)發(fā)現(xiàn)系統(tǒng)
基于GP算法的知識(shí)發(fā)現(xiàn)系統(tǒng) 南京建筑工程學(xué)院計(jì)算中心 李亞非摘 要 本文提出了一個(gè)新的知識(shí)發(fā)現(xiàn)系統(tǒng)。該系統(tǒng)以遺傳編程算法為核心，解決發(fā)現(xiàn)一組屬于面向?qū)ο髷?shù)據(jù)庫(kù)的對(duì)象所具有的共性問(wèn)題。本文對(duì)系統(tǒng)作了扼要的說(shuō)明，對(duì)GP算法進(jìn)行了描述，并給出了一個(gè)實(shí)驗(yàn)例子。
關(guān)鍵詞 進(jìn)化計(jì)算 遺傳編程 知識(shí)發(fā)掘
在數(shù)據(jù)庫(kù)中發(fā)現(xiàn)有用的知識(shí)是數(shù)據(jù)挖掘（Data Mining, DM）的主要任務(wù)，在一定的情況下，所有的數(shù)據(jù)庫(kù)查詢可以認(rèn)為是完成這項(xiàng)任務(wù)。我們現(xiàn)在有一套分析和探索數(shù)據(jù)的工具：SQL查詢、OLAP和數(shù)據(jù)挖掘技術(shù)。SQL查詢由關(guān)系代數(shù)所構(gòu)成；OLAP提供了建立在多維數(shù)據(jù)模型基礎(chǔ)上的高水平查詢；而數(shù)據(jù)挖掘提供了最抽象的數(shù)據(jù)分析操作。我們可以認(rèn)為不同的數(shù)據(jù)挖掘任務(wù)是在高水平上的復(fù)雜查詢。數(shù)據(jù)挖掘是機(jī)器學(xué)習(xí)和數(shù)據(jù)庫(kù)技術(shù)的交叉學(xué)科，DM系統(tǒng)的主要特點(diǎn)是：在數(shù)據(jù)庫(kù)中發(fā)現(xiàn)能夠用某些規(guī)則表述的、隱含的知識(shí)；與數(shù)據(jù)庫(kù)是緊密集成的；高度自動(dòng)化的；對(duì)知識(shí)發(fā)現(xiàn)的處理是有效率的（尤其對(duì)大型數(shù)據(jù)庫(kù)）。
這里我們給出一種基于GP（Genetic Programming，遺傳編程）算法的知識(shí)發(fā)現(xiàn)系統(tǒng)，和通常對(duì)數(shù)據(jù)庫(kù)的查詢不同的是，這個(gè)系統(tǒng)可對(duì)特定的對(duì)象集產(chǎn)生特定的查詢集，系統(tǒng)自動(dòng)根據(jù)查詢集訪問(wèn)數(shù)據(jù)庫(kù)，從而發(fā)掘出數(shù)據(jù)庫(kù)中隱含的知識(shí)。本文將對(duì)上述知識(shí)發(fā)掘過(guò)程進(jìn)行詳細(xì)描述，并提出了一種用遺傳編程（GP）來(lái)進(jìn)行數(shù)據(jù)挖掘的方法，GP個(gè)體由數(shù)據(jù)庫(kù)查詢組成，而這些查詢代表了高水平上的規(guī)則。
1 系統(tǒng)基本結(jié)構(gòu)
我們?cè)赱1]文給出的知識(shí)發(fā)現(xiàn)系統(tǒng)結(jié)構(gòu)基礎(chǔ)上加以改進(jìn)，給出如圖1的基于GP算法的知識(shí)發(fā)現(xiàn)系統(tǒng)。
1．1 系統(tǒng)結(jié)構(gòu)描述
整個(gè)系統(tǒng)由GP引擎、OODBMS（Object-Oriented Database Management System,面向?qū)ο髷?shù)據(jù)庫(kù)管理系統(tǒng)）、知識(shí)庫(kù)、DB接口和用戶接口組成。系統(tǒng)以一組對(duì)象、領(lǐng)域知識(shí)和模式信息作為輸入。根據(jù)所給輸入，GP引擎將產(chǎn)生許多隨機(jī)的查詢，系統(tǒng)將這些查詢應(yīng)用于OODBMS，OODBMS將返回其結(jié)果。系統(tǒng)用給定的輸入對(duì)該返回結(jié)果進(jìn)行評(píng)價(jià)，評(píng)價(jià)是計(jì)算個(gè)體查詢的適應(yīng)值的過(guò)程。那些能夠匹配所給對(duì)象集的查詢或查詢集將被選中，在沒(méi)有查詢能夠匹配所給對(duì)象集時(shí)，那么其最好的查詢將被選中。最后，將能夠最好地描述所給對(duì)象集特性的查詢作為輸出。
1．2 面向?qū)ο蟮臄?shù)據(jù)庫(kù)
這里，我們假定一個(gè)基于面向?qū)ο蠛秃瘮?shù)的數(shù)據(jù)庫(kù)模型（Object-Oriented and Functional Data Model, OOFDM），OOFDM具有面向?qū)ο蠛秃瘮?shù)數(shù)據(jù)模式的特性。這種模型要比傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)模型在表達(dá)知識(shí)時(shí)更加逼近和容易。OOFDM的基本概念是"將感知到的真實(shí)世界作為相互關(guān)系對(duì)象的變量，并從不同的更細(xì)的層次上觀察這些對(duì)象。"[2]函數(shù)數(shù)據(jù)模型可以簡(jiǎn)單地借助函數(shù)的數(shù)學(xué)符號(hào)來(lái)表示數(shù)據(jù)間的關(guān)系。每個(gè)類（或?qū)嶓w集）有自己的屬性和值，類與屬性間的關(guān)系是將類中的對(duì)象集映射到屬性域的一個(gè)函數(shù)。關(guān)系或逆關(guān)系組成了類間的連接。
1．3 查詢算子
我們使用下列查詢算子作為其面向?qū)ο髷?shù)據(jù)庫(kù)的查詢語(yǔ)言。
①SEL C-1 [(謂詞)] 該算子選擇所有屬于C-1且滿足謂詞的對(duì)象。C-1既可以是一個(gè)類名也可以是一個(gè)屬于C-1的查詢。謂詞是一個(gè)可選項(xiàng)。如果在這個(gè)算子里沒(méi)有謂詞，它將選擇該類中的所有對(duì)象。
②RES C-1 謂詞 該算子根據(jù)所給謂詞，限制給定集合的對(duì)象與另一個(gè)類的對(duì)象關(guān)聯(lián)。C-1和謂詞同SEL算子，但對(duì)于RES的謂詞屬性必須是關(guān)系型的屬性，而對(duì)于SEL算子謂詞屬性則必須是非關(guān)系型屬性。
③REL C-1 R-r Class-2 該算子選擇所有C-1中與C-2中對(duì)象有關(guān)聯(lián)的對(duì)象。這是一個(gè)通過(guò)R-r 將一個(gè)類C-1與另一個(gè)類C-2關(guān)聯(lián)起來(lái)的關(guān)系算子。R-r可以是一個(gè)通過(guò)C-1中定義的關(guān)系集中的關(guān)系屬性之一。C-1既可以是一個(gè)類名也可以是一個(gè)屬于C-1的查詢。C-2必須是一個(gè)類名或是一個(gè)屬于C-2的查詢，并且通過(guò)R-r關(guān)聯(lián)到另一個(gè)類C-1。
④G-REL C-1 R-r C-2 該算子是REL的逆算子，它選擇所有C-2中與C-1中對(duì)象有關(guān)聯(lián)的對(duì)象。C-1、C-2以及R-r的意義同REL算子。
2 GP算法
遺傳編程（GP）屬于進(jìn)化計(jì)算（Evolutionary Computation，EC）模型的一種。EC是一種借鑒自然界進(jìn)化機(jī)制而產(chǎn)生的并行隨機(jī)搜索算法。進(jìn)化算法的基本原理是選擇和改變，它區(qū)別于其他搜索方法有兩個(gè)顯著特征：首先這些算法都是基于種群（population）的；其次在種群中個(gè)體（indvidual）之間存在競(jìng)爭(zhēng)。
為搜索特定的（感興趣的）查詢需要一種工具，這種工具可智能生成一組查詢并以它們是否能導(dǎo)出與用戶給定的同樣的對(duì)象集來(lái)進(jìn)行評(píng)價(jià)。GP算法對(duì)這一類問(wèn)題是很實(shí)用的。
2．1 函數(shù)集與端點(diǎn)集
一般GP中可生成的程序集是使用者定義的函數(shù)集和端點(diǎn)集。表1給出了相應(yīng)的函數(shù)集和端點(diǎn)集，其中函數(shù)集由1.3中定義的查詢算子、邏輯運(yùn)算算子以及比較算子所組成。
【基于GP算法的知識(shí)發(fā)現(xiàn)系統(tǒng)】相關(guān)文章：
基于3GPP LTE 系統(tǒng)的HARQ 算法探究03-03
基于專家系統(tǒng)的個(gè)人知識(shí)管理03-10
OFDM系統(tǒng)中基于導(dǎo)頻插入的信道估計(jì)算法研究03-07
關(guān)于基于知識(shí)管理的臨床信息系統(tǒng)的研究03-01
基于Visual Basic快速開發(fā)現(xiàn)場(chǎng)電視監(jiān)控系統(tǒng)03-20
基于本體的教學(xué)知識(shí)庫(kù)系統(tǒng)分析03-20
基于DSP的信道譯碼算法優(yōu)化03-19
基于階梯細(xì)化的圖像放大算法03-07
關(guān)于基于知識(shí)管理的臨床信息系統(tǒng)的研究論文03-31
基于遺傳算法的OD分布03-21