基于GP算法的知識發(fā)現(xiàn)系統(tǒng)南京建筑工程學院計算中心李亞非

摘要本文提出了一個新的學問發(fā)覺系統(tǒng)。該系統(tǒng)以遺傳編程算法為核心，解決發(fā)覺一組屬于面對對象數(shù)據(jù)庫的對象所具有的共性問題。本文對系統(tǒng)作了扼要的說明，對GP算法進行了描述，并給出了一個試驗例子。

關(guān)鍵詞進化計算遺傳編程學問發(fā)掘

在數(shù)據(jù)庫中發(fā)覺有用的學問是數(shù)據(jù)挖掘（DataMining,DM）的主要任務(wù)，在肯定的狀況下，全部的數(shù)據(jù)庫查詢可以認為是完成這項任務(wù)。我們現(xiàn)在有一套分析和探究數(shù)據(jù)的工具：SQL查詢、OLAP和數(shù)據(jù)挖掘技術(shù)。SQL查詢由關(guān)系代數(shù)所構(gòu)成；OLAP供應了建立在多維數(shù)據(jù)模型基礎(chǔ)上的高水平查詢；而數(shù)據(jù)挖掘供應了最抽象的數(shù)據(jù)分析操作。我們可以認為不同的數(shù)據(jù)挖掘任務(wù)是在高水平上的簡單查詢。數(shù)據(jù)挖掘是機器學習和數(shù)據(jù)庫技術(shù)的交叉學科，DM系統(tǒng)的主要特點是：在數(shù)據(jù)庫中發(fā)覺能夠用某些規(guī)章表述的、隱含的學問；與數(shù)據(jù)庫是緊密集成的；高度自動化的；對學問發(fā)覺的處理是有效率的（尤其對大型數(shù)據(jù)庫）。

這里我們給出一種基于GP（GeneticProgramming，遺傳編程）算法的學問發(fā)覺系統(tǒng)，和通常對數(shù)據(jù)庫的查詢不同的是，這個系統(tǒng)可對特定的對象集產(chǎn)生特定的查詢集，系統(tǒng)自動依據(jù)查詢集訪問數(shù)據(jù)庫，從而發(fā)掘出數(shù)據(jù)庫中隱含的學問。本文將對上述學問發(fā)掘過程進行具體描述，并提出了一種用遺傳編程（GP）來進行數(shù)據(jù)挖掘的方法，GP個體由數(shù)據(jù)庫查詢組成，而這些查詢代表了高水平上的規(guī)章。

1系統(tǒng)基本結(jié)構(gòu)

我們在[1]文給出的學問發(fā)覺系統(tǒng)結(jié)構(gòu)基礎(chǔ)上加以改進，給出如圖1的基于GP算法的學問發(fā)覺系統(tǒng)。

1．1系統(tǒng)結(jié)構(gòu)描述

整個系統(tǒng)由GP引擎、OODBMS（Object-OrientedDatabaseManagementSystem,面對對象數(shù)據(jù)庫管理系統(tǒng)）、學問庫、DB接口和用戶接口組成。系統(tǒng)以一組對象、領(lǐng)域?qū)W問和模式信息作為輸入。依據(jù)所給輸入，GP引擎將產(chǎn)生很多隨機的'查詢，系統(tǒng)將這些查詢應用于OODBMS，OODBMS將返回其結(jié)果。系統(tǒng)用給定的輸入對該返回結(jié)果進行評價，評價是計算個體查詢的適應值的過程。那些能夠匹配所給對象集的查詢或查詢集將被選中，在沒有查詢能夠匹配所給對象集時，那么其最好的查詢將被選中。最終，將能夠最好地描述所給對象集特性的查詢作為輸出。

1．2面對對象的數(shù)據(jù)庫

這里，我們假定一個基于面對對象和函數(shù)的數(shù)據(jù)庫模型（Object-OrientedandFunctionalDataModel,OOFDM），OOFDM具有面對對象和函數(shù)數(shù)據(jù)模式的特性。這種模型要比傳統(tǒng)的關(guān)系數(shù)據(jù)庫模型在表達學問時更加靠近和簡單。OOFDM的基本概念是"將感知到的真實世界作為相互關(guān)系對象的變量，并從不同的更細的層次上觀看這些對象。"[2]函數(shù)數(shù)據(jù)模型可以簡潔地借助函數(shù)的數(shù)學符號來表示數(shù)據(jù)間的關(guān)系。每個類（或?qū)嶓w集）有自己的屬性和值，類與屬性間的關(guān)系是將類中的對象集映射到屬性域的一個函數(shù)。關(guān)系或逆關(guān)系組成了類間的連接。

1．3查詢算子

我們使用下列查詢算子作為其面對對象數(shù)據(jù)庫的查詢語言。

①SELC-1[(謂詞)]該算子選擇全部屬于C-1且滿意謂詞的對象。C-1既可以是一個類名也可以是一個屬于C-1的查詢。謂詞是一個可選項。假如在這個算子里沒有謂詞，它將選擇該類中的全部對象。

②RESC-1謂詞該算子依據(jù)所給謂詞，限制給定集合的對象與另一個類的對象關(guān)聯(lián)。C-1和謂詞同SEL算子，但對于RES的謂詞屬性必需是關(guān)系型的屬性，而對于SEL算子謂詞屬性則必需是非關(guān)系型屬性。

③RELC-1R-rClass-2該算子選擇全部C-1中與C-2中對象有關(guān)聯(lián)的對象。這是一個通過R-r將一個類C-1與另一個類C-2關(guān)聯(lián)起來的關(guān)系算子。R-r可以是一個通過C-1中定義的關(guān)系集中的關(guān)系屬性之一。C-1既可以是一個類名也可以是一個屬于C-1的查詢。C-2必需是一個類名或是一個屬于C-2的查詢，并且通過R-r關(guān)聯(lián)到另一個類C-1。

④G-RELC-1R-rC-2該算子是REL的逆算子，它選擇全部C-2中與C-1中對象有關(guān)聯(lián)的對象。C-1、C-2以及R-r的意義同REL算子。

2GP算法

遺傳編程（GP）屬于進化計算（EvolutionaryComputation，EC）模型的一種。EC是一種借鑒自然界進化機制而產(chǎn)生的并行隨機搜尋算法。進化算法的基本原理是選擇和轉(zhuǎn)變，它區(qū)分于其他搜尋方法有兩個顯著特征：首先這些算法都是基于種群（population）的；其次在種群中個體（indvidual）之間存在競爭。

為搜尋特定的（感愛好的）查詢需要一種工具，這種工具可智能生成一組查詢并以它們是否能導出與用戶給定的同樣的對象集來進行評價。GP算法對這一類問題是很有用的。

2．1函數(shù)集與端點集

一般GP中可生成的程序集是使用者定義的函數(shù)集和端點集。表1給出了相應的函數(shù)集和端點集，其中函數(shù)集由1.3中定義的查詢算子、規(guī)律運算算子以及比較算子所組成。

函數(shù)集{SEL，REL，G-REL，RES}，{UNI，INT，DIF}，{AND，OR，NOT}，{，=，=，，=}端點集類集，屬性集，值集表1函數(shù)集和端點集

在我們的應用中還有一些具有不同句法的查詢算子。每個算子具有不同的句法且假定的數(shù)據(jù)庫是面對對象的。因此，它具有為創(chuàng)建個體而使用的特殊的函數(shù)集（或算子集）和端點集。從而，構(gòu)成種群的全部個體的創(chuàng)建必定受到每個算子的約束[3]。約束可以是算子的句法和查詢的類型，或者是為創(chuàng)建查詢選擇適當屬性值的領(lǐng)域?qū)W問。比較算子和規(guī)律算子只使用于查詢的謂詞。當比較符號操作數(shù)時，僅使用'='。

端點集由CLASS-SET、SLOT-SET和VALUE-SET組成。CLASS-SET由1.2中定義的類名組成，SLOT-SET由每個類的全部屬性構(gòu)成，VALUE-SET由數(shù)值和符號值所構(gòu)成（它們均為屬性值）。數(shù)值由整型或?qū)嵭蛿?shù)構(gòu)成，其數(shù)值范圍由所用數(shù)據(jù)庫模式定義。符號值由字符串表示的符號屬性值構(gòu)成。

2．2創(chuàng)建初始種群

為了創(chuàng)建一個個體（查詢），首先必需確定特定查詢所返回的對象類型。結(jié)果類型被選擇后，從所選類型返回例子的算子集中隨機地選擇一個算子，這個過程對查詢的每個參數(shù)遞歸地進行。最初，那些句法正確的預定義數(shù)量的查詢被隨機地產(chǎn)生，形成初始種群。

2．3選擇屬性值

由于可選擇范圍大，要從某個查詢的值集中選擇一個屬性值（數(shù)值或符號常數(shù)）是相當困難的。對于一個范圍為[1，10000]的整數(shù)集，隨機選到一個特定整數(shù)的概率僅為1/10000。而對于符號常數(shù)，則需要很強的背景學問。因此，我們僅就發(fā)生在數(shù)據(jù)庫里的范圍選擇屬性值。

2．4繁殖新一代種群

每個個體用預定義的適應函數(shù)來進行評價。較適應的查詢有較高的概率被選來繁殖新種群，這個過程用三個遺傳算子：選擇、雜交和變異來完成。為了產(chǎn)生下一代，選擇算子依據(jù)個體的適應值來選擇個體。我們用一個樹來表示一個查詢，雜交算子用交換兩個父輩的子樹來創(chuàng)建兩個后代。變異算子用一個新的子樹來代替一個父輩的子樹，從而產(chǎn)生一個新的后代。選擇-雜交-變異循環(huán)反復地進行直到終止標準被滿意。

2．5評價（適應函數(shù)測量）

我們使用如下的適應函數(shù)f來評價種群中的個體查詢i：

f(ni,hi)=T-(hi*hi)/ni,

其中：ni0，T≥hi，且i=1，2，…，種群的大?。═是被確定的對象集的勢，hi是一個個體查詢i被選中的次數(shù)，ni是查詢i結(jié)果集的勢）。

上述適應函數(shù)依靠于hi和ni，假如一個查詢沒有被選中（hi=0），則函數(shù)的值為T，這是最差的一個適應值。另一方面，假如查詢結(jié)果能夠很好地匹配提交給系統(tǒng)的對象集，那么它的適應值為0（在這種狀況下hi=ni=T）。假如種群中消失個體適應值遠遠超過種群平均適應值，該個體很快就會在群體中占有肯定的比例，從而消失過早收斂的現(xiàn)象。另一方面，在搜尋過程的后期，群體的平均適應值可能會接近群體的最優(yōu)適應值，從而導致搜尋目標難以得到改善，消失停滯現(xiàn)象[4]。為了防止上述狀況的發(fā)生，我們將對一個個體查詢的例子個數(shù)ni作為分母。

3一個例子

我們首先給出一個如表2所示的模擬"售后質(zhì)量管理函數(shù)數(shù)據(jù)庫"，用它來代表一個基于OOFDM的面對對象數(shù)據(jù)庫，它包含了客戶及其相關(guān)的信息。表3說明白類間的相互聯(lián)系。

類屬性值客戶代碼、電話、名稱、地址、類別、地區(qū)、托付、購買代理商代碼、名稱、地址、電話、信譽等級產(chǎn)品名稱、編號、出廠日期、購買日期、檢驗員修理記錄問題、修理時間、修理次數(shù)、修理員使用培訓否、技術(shù)力氣質(zhì)量問題外觀、電器、機械、裝配表2售后質(zhì)量管理數(shù)據(jù)庫

類客戶代理商產(chǎn)品修理記錄使用質(zhì)量問題客戶+++代理商+產(chǎn)品+++修理記錄+使用++質(zhì)量問題++表3類間的連接表

3．1問題的提出

依據(jù)質(zhì)量管理部門反映，有兩個客戶反饋的產(chǎn)品質(zhì)量問題較為嚴峻，我們盼望通過對數(shù)據(jù)庫的查詢來找出這兩個客戶在購買的產(chǎn)品及使用上所具有的共性。

3．2試驗結(jié)果

在我們的數(shù)據(jù)庫里包含如表2所示的模式組織起來的客戶信息，我們通過用"選擇反

代fafihini完全選中？026.6818.671012N226.5719.7127100N1025.7019.651323N2522.3911.001616N3617.690.002727Y522.850.002727Y93