基于GP算法的知識發現系統

基于GP算法的知識發現系統

基于GP算法的知識發現系統

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

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

關鍵詞 進化計算 遺傳編程 知識發掘

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

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

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

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

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

函數集 {SEL，REL，G-REL，RES}，{UNI，INT，DIF}，{AND，OR，NOT}， {

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

基于3GPP LTE 系統的HARQ 算法探究03-03

基于專家系統的個人知識管理03-10

OFDM系統中基于導頻插入的信道估計算法研究03-07

關于基于知識管理的臨床信息系統的研究03-01

基于Visual Basic快速開發現場電視監控系統03-20

基于本體的教學知識庫系統分析03-20

基于DSP的信道譯碼算法優化03-19

基于階梯細化的圖像放大算法03-07

關于基于知識管理的臨床信息系統的研究論文03-31

基于遺傳算法的OD分布03-21