基于GP算法的知識發(fā)現系統

基于GP算法的知識發(fā)現系統

南京建筑工程學院計算中心  李亞非

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

關鍵詞 進化計算 遺傳編程 知識發(fā)掘

在數據庫中發(fā)現有用的知識是數據挖掘（Data Mining, DM）的主要任務，在一定的情況下，所有的數據庫查詢可以認為是完成這項任務。我們現在有一套分析和探索數據的工具：SQL查詢、OLAP和數據挖掘技術。SQL查詢由關系代數所構成；OLAP提供了建立在多維數據模型基礎上的高水平查詢；而數據挖掘提供了最抽象的數據分析操作。我們可以認為不同的數據挖掘任務是在高水平上的復雜查詢。數據挖掘是機器學習和數據庫技術的交叉學科，DM系統的主要特點是：在數據庫中發(fā)現能夠用某些規(guī)則表述的、隱含的知識；與數據庫是緊密集成的；高度自動化的；對知識發(fā)現的處理是有效率的（尤其對大型數據庫）。

這里我們給出一種基于GP（Genetic Programming，遺傳編程）算法的知識發(fā)現系統，和通常對數據庫的查詢不同的是，這個系統可對特定的對象集產生特定的查詢集，系統自動根據查詢集訪問數據庫，從而發(fā)掘出數據庫中隱含的知識。本文將對上述知識發(fā)掘過程進行詳細描述，并提出了一種用遺傳編程（GP）來進行數據挖掘的方法，GP個體由數據庫查詢組成，而這些查詢代表了高水平上的規(guī)則。

1 系統基本結構
我們在[1]文給出的知識發(fā)現系統結構基礎上加以改進，給出如圖1的基于GP算法的知識發(fā)現系統。

1．1 系統結構描述
整個系統由GP引擎、OODBMS（Object-Oriented Database Management System,面向對象數據庫管理系統）、知識庫、DB接口和用戶接口組成。系統以一組對象、領域知識和模式信息作為輸入。根據所給輸入，GP引擎將產生許多隨機的查詢，系統將這些查詢應用于OODBMS，OODBMS將返回其結果。系統用給定的輸入對該返回結果進行評價，評價是計算個體查詢的適應值的過程。那些能夠匹配所給對象集的查詢或查詢集將被選中，在沒有查詢能夠匹配所給對象集時，那么其最好的查詢將被選中。最后，將能夠最好地描述所給對象集特性的查詢作為輸出。

1．2 面向對象的數據庫
這里，我們假定一個基于面向對象和函數的數據庫模型（Object-Oriented and Functional Data Model, OOFDM），OOFDM具有面向對象和函數數據模式的特性。這種模型要比傳統的關系數據庫模型在表達知識時更加逼近和容易。OOFDM的基本概念是"將感知到的真實世界作為相互關系對象的變量，并從不同的更細的層次上觀察這些對象。"[2]函數數據模型可以簡單地借助函數的數學符號來表示數據間的關系。每個類（或實體集）有自己的屬性和值，類與屬性間的關系是將類中的對象集映射到屬性域的一個函數。關系或逆關系組成了類間的連接。

1．3 查詢算子
我們使用下列查詢算子作為其面向對象數據庫的查詢語言。
①SEL C-1 [(謂詞)] 該算子選擇所有屬于C-1且滿足謂詞的對象。C-1既可以是一個類名也可以是一個屬于C-1的查詢。謂詞是一個可選項。如果在這個算子里沒有謂詞，它將選擇該類中的所有對象。
②RES C-1 謂詞 該算子根據所給謂詞，限制給定集合的對象與另一個類的對象關聯。C-1和謂詞同SEL算子，但對于RES的謂詞屬性必須是關系型的屬性，而對于SEL算子謂詞屬性則必須是非關系型屬性。
③REL C-1 R-r Class-2 該算子選擇所有C-1中與C-2中對象有關聯的對象。這是一個通過R-r 將一個類C-1與另一個類C-2關聯起來的關系算子。R-r可以是一個通過C-1中定義的關系集中的關系屬性之一。C-1既可以是一個類名也可以是一個屬于C-1的查詢。C-2必須是一個類名或是一個屬于C-2的查詢，并且通過R-r關聯到另一個類C-1。
④G-REL C-1 R-r C-2 該算子是REL的逆算子，它選擇所有C-2中與C-1中對象有關聯的對象。C-1、C-2以及R-r的意義同REL算子。

2 GP算法
遺傳編程（GP）屬于進化計算（Evolutionary Computation，EC）模型的一種。EC是一種借鑒自然界進化機制而產生的并行隨機搜索算法。進化算法的基本原理是選擇和改變，它區(qū)別于其他搜索方法有兩個顯著特征：首先這些算法都是基于種群（population）的；其次在種群中個體（indvidual）之間存在競爭。
為搜索特定的（感興趣的）查詢需要一種工具，這種工具可智能生成一組查詢并以它們是否能導出與用戶給定的同樣的對象集來進行評價。GP算法對這一類問題是很實用的。

2．1 函數集與端點集
一般GP中可生成的程序集是使用者定義的函數集和端點集。表1給出了相應的函數集和端點集，其中函數集由1.3中定義的查詢算子、邏輯運算算子以及比較算子所組成。

函數集 {SEL，REL，G-REL，RES}，{UNI，INT，DIF}，{AND，OR，NOT}， {>，>=，=，<，<=} 端點集類集，屬性集，值集

表1 函數集和端點集

在我們的應用中還有一些具有不同句法的查詢算子。每個算子具有不同的句法且假定的數據庫是面向對象的。因此，它具有為創(chuàng)建個體而使用的特別的函數集（或算子集）和端點集。從而，構成種群的所有個體的創(chuàng)建必然受到每個算子的約束[3]。約束可以是算子的句法和查詢的類型，或者是為創(chuàng)建查詢選擇適當屬性值的領域知識。比較算子和邏輯算子只使用于查詢的謂詞。當比較符號操作數時，僅使用'='。
端點集由CLASS-SET、SLOT-SET和VALUE-SET組成。CLASS-SET由1.2中定義的類名組成，SLOT-SET由每個類的所有屬性構成，VALUE-SET由數值和符號值所構成（它們均為屬性值）。數值由整型或實型數構成，其數值范圍由所用數據庫模式定義。符號值由字符串表示的符號屬性值構成。

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

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

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

2．5 評價（適應函數測量）
我們使用如下的適應函數f來評價種群中的個體查詢i ：
f ( ni , hi ) = T - ( hi * hi ) / ni ,
其中：ni > 0 ， T ≥ hi ， 且 i = 1 ，2 ，… ，種群的大小（T是被確定的對象集的勢，hi是一個個體查詢i 被選中的次數，ni是查詢 i 結果集的勢）。
上述適應函數依賴于hi和ni ，如果一個查詢沒有被選中（hi=0），則函數的值為T，這是最差的一個適應值。另一方面，如果查詢結果能夠很好地匹配提交給系統的對象集，那么它的適應值為0（在這種情況下hi = ni = T ）。如果種群中出現個體適應值遠遠超過種群平均適應值，該個體很快就會在群體中占有絕對的比例，從而出現過早收斂的現象。另一方面，在搜索過程的后期，群體的平均適應值可能會接近群體的最優(yōu)適應值，從而導致搜索目標難以得到改善，出現停滯現象[4]。為了防止上述情況的發(fā)生，我們將對一個個體查詢的例子個數 ni 作為分母。

3 一個例子
我們首先給出一個如表2所示的模擬"售后質量管理函數數據庫"，用它來代表一個基于OOFDM的面向對象數據庫，它包含了客戶及其相關的信息。表3說明了類間的相互聯系。

類屬性值 客戶代碼、電話、名稱、地址、類別、地區(qū)、委托、購買 代理商代碼、名稱、地址、電話、信譽等級 產品名稱、編號、出廠日期、購買日期、檢驗員 維修記錄問題、維修時間、維修次數、維修員 使用培訓否、技術力量 質量問題外觀、電器、機械、裝配

表2 售后質量管理數據庫

類客戶代理商產品維修記錄使用質量問題 客戶   + +   +   代理商 +           產品 +       + + 維修記錄           + 使用 +   +       質量問題     + +    

表3 類間的連接表

3．1 問題的提出
根據質量管理部門反映，有兩個客戶反饋的產品質量問題較為嚴重，我們希望通過對數據庫的查詢來找出這兩個客戶在購買的產品及使用上所具有的共性。

3．2 實驗結果
在我們的數據庫里包含如表2所示的模式組織起來的客戶信息，我們通過用"選擇反

代 fa fi hi ni 完全選中？ 0 26.68 18.67 10 12 N 2 26.57 19.71 27 100 N 10 25.70 19.65 13 23 N 25 22.39 11.00 16 16 N 36 17.69 0.00 27 27 Y 52 2.85 0.00 27 27 Y 93 2.17 0.00 27 27 Y 199 2.59 0.00 27 27 Y

( T = 27 , P = 100 , 代數 = 200 )

映質量問題達到或超過3次的客戶"的查詢，即：
（G-REL（RES 產品（≥送交維修 3））購買 by 客戶）
得到27個例子的對象集{"客戶C5"，"客戶B2"，… }。將這個對象集提交給系統，查詢的發(fā)掘過程以100個隨機產生的查詢開始。表2顯示了發(fā)掘出的每一代最好的查詢摘要。fi，hi和ni分別是最佳查詢i的適應值、被選中次數和結果集的勢，fa為平均標準適應值（fa = (∑fi)/P,P是種群的大小，(∑fi)為種群適應值的和）。
在第52代時，我們已經得到了相當好的結果。此時，平均適應值已由第0代的26.68降到2.85。其最好的查詢被完全選中，查詢可敘述為"選擇反映質量問題達到或超過3次的客戶，并且購買的產品的出廠日期為97年11月以后到98年5月以前。"即：
（G-REL
（RES 產品（≥送交維修 3））
購買 by 客戶
（SEL 產品 （OR（< 出廠日期 98年5月）（> 出廠日期 97年11月 ）））
如果不考慮所使用的是模擬數據的話，可以說我們已經發(fā)現了蘊藏在數據庫中的知識了。

4 小結
本文在知識發(fā)掘系統的框架上引入了GP算法，并以一個實驗例子為背景，說明使用GP算法產生最佳查詢方法的有效性，展示了該系統的應用潛力。我們將進一步把該思想導入到關系型數據庫，在實踐中完善系統。

參考文獻

1 李亞非，夏安邦 . 一種新的知識發(fā)現系統架構 . 東南大學學報 . 1998（6A）: 8~11
2 Gray , Peter M D . Object-Oriented Database/A Semantic Data Model Approach . Englewood Cliff ,NJ. Printice Hall, 1992
3 Koza , John R .Genetic Programming/Automatic Discovery of Reusable Program . Cambridge ,MA. The MIT Press , 1995
4 潘正君，康立山，陳玉屏. 演化計算 .北京：清華大學出版社，1998

【基于GP算法的知識發(fā)現系統】相關文章：

基于GP算法的知識發(fā)現系統08-06

CCD測量系統中基于自適應相關算法的動態(tài)目標跟蹤08-06

基于DSP的信道譯碼算法優(yōu)化08-06

基于Visual Basic快速開發(fā)現場電視監(jiān)控系統08-06

基于Visual Basic快速開發(fā)現場電視監(jiān)控系統04-12

智能決策支持系統中的知識表示及基于粗集的知識推理08-06

基于SMBus的智能電池系統08-06

基于DSP的自動對焦系統08-06

基于RTLinux的實時控制系統08-06