摘 要 本文提出了一個新的知識發現系統。該系統以遺傳程式設計演算法為核心，解決發現一組屬於物件導向資料庫的物件所具有的共性問題。本文對系統作了扼要的說明，對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。