基于遺傳算法的多關系數據挖掘的研究

摘要:多關系數據挖掘的研究領域涉及多個學科，它在由多張表構成的關系數據庫中進行知識發現。遺傳算法是模擬生物的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法。該文將遺傳算法應用于多關系數據挖掘，組合使用Apriori方法可從多張表中高效地挖掘出有意義的關聯規則。

關鍵詞:多關系數據挖掘;遺傳算法;關聯規則;Apriori

中圖分類號:TP311.13文獻標識碼:A 文章編號:1009-3044(2009)26-7333-02

Research on Multi-Relational Data Mining with Genetic Algorithm

SONG Yang， ZHU Yi

(Department of Computer and Information Engineering， Huainan Normal University， Huainan 232001， China)

Abstract: Multi-Relational Data Mining is the multi-disciplinary field dealing with knowledge discovery from relational databases consisting of multiple tables. Genetic algorithm is Adaptive Probabilistic Search Algorithm for Global Optimization， simulating the biological genetics and evolution. This paper applies genetic algorithms to multi-relational data mining， combining Apriori method to efficiently find out meaningful association rules from multiple tables.

Key words: multi-relational data mining; genetic algorithm; association rule; Apriori

數據挖掘是數據庫研究、開發和應用最活躍的分支之一。簡單的說，數據挖掘是從大量數據中提取有趣的模式。傳統的數據挖掘方法都是從單一的數據表中尋找規則，然而，在現實應用中，大部分數據庫都是關系的，把多張表中的數據擠壓進一張表需要花費大量的心思和工夫，還可能造成信息的丟失，上述原因直接推動了多關系數據挖掘研究的興起和發展。

作為一種最有影響的挖掘關聯規則的算法，Apriori的核心思想是找出最大頻繁項集，實際是全局搜索的過程。該文將遺傳算法這種全局優化算法用于多關系數據挖掘，能夠高效地發現有價值的規則。

1 多關系數據挖掘

多關系數據挖掘(Multi-Relational Data Mining，簡稱MRDM)是數據挖掘研究方向熱點研究課題之一，然而，與現有的大多數數據挖掘方法不同的是，多關系數據挖掘不是只在一張單獨的數據表中發掘模式，它是在關系數據庫的多張表中進行知識發現。多關系數據挖掘MRDM也被簡稱為關系數據挖掘RDM [1]。

就像許多的傳統數據挖掘算法都是來自于機器學習領域，許多的多關系數據挖掘算法都是來自于ILP領域。早起的ILP研究集中于從例子中自動地合成Prolog程序，然而近些年來，由于知識發現和數據挖掘的研究的興起，ILP的研究范圍已經覆蓋了整個數據挖掘的領域(包括分類，回歸，聚類，關聯分析等等)，大部分一般的模式類型已經擴展到了相應的關系模式(如關系分類規則，關系回歸樹，關系關聯規則)中，并已有了主要的關系數據挖掘算法(決策樹歸納，基于距離的聚類等等)。

2 遺傳算法

遺傳算法也被稱為基因算法(Genetic Algorithm，簡稱GA)，是20世紀70年代初由美國Michigan大學的Holland教授發展起來的。遺傳算法借鑒了大自然生物進化過程“適者生存”的普遍規律:最能適應環境的種群往往產生更大的后代種群[2]。

遺傳算法將優化問題的解空間映射為遺傳基因空間，把可能的解編碼為染色體，染色體的每一位稱為基因。其基本思想是[2-3]:首先隨機地生成一個初始種群，然后計算每個個體對問題環境的適應度，再根據適應度對染色體進行選擇，抑制適應度低的染色體，激發適應度高的染色體，然后進行交叉、變異等遺傳操作產生下一代種群。如此反復，不斷向更優解進化，最后得到滿足收斂條件的適應問題環境的個體。其主要優點是優化求解過程與梯度信息無關。

3 遺傳算法在多關系數據挖掘中的應用

3.1 擴展的關聯規則

常見模式和關聯規則的發現是數據挖掘最常見的任務。關聯規則是這樣的形式: A→C，箭頭→的意思為蘊含。最常見的例子為“買了A的顧客通常也買了C”。若已知A和C的支持度分別為fA和fC，則關聯規則的置信度定義為CA→C=fC/fA。

涉及到在多張表上進行關系數據挖掘的情形，我們引入擴展的關聯規則的概念[4]。

定義:用 R 表示關系數據庫，P 表示主屬性值的集合，Si(i=1，2，…，n)表示 R 中相關表屬性值的集合，則 P →(S1，S2，…Sn)即是擴展的關聯規則，其含義是:包含 P 的事務也可能包含(S1，S2，… Sn)。

同標準規則相比，擴展規則表現關聯的粒度更細。

3.2 矩陣分組

本小節，我們來解釋如何挖掘多關系數據。

上表中，Pi(i=1…5)表示產品，Tj(j=1…5)表示交易。如果Pi在Tj中被售出了，則我們在第i列第j行的位置寫1，否則，寫0。

若我們約定最小支持度為60%，則意味著該規則至少生效三次，因此我們將每三筆交易分成一組，如果某些產品在某分組的每筆交易中都被售出了，則提取這些產品和交易形成一條規則。如上表中:(T2，T3，T5)→(P1，P3，P4)， (T1，T3，T5)→(P3，P4)， (T3，T4，T5)→(P4)。下一步合并規則。如上面的示例中，可以將規則(T1，T2，T3)→(P3，P4)，(T1，T3，T5)→(P3，P4)合并得到新規則(T1，T2，T3，T5)→(P3，P4)，其支持率為80%。

這種矩陣分組的方法僅適用于小型數據庫，為了高效地在大型數據庫中進行挖掘，我們使用遺傳算法，以啟發式方法找出那些能夠提取規則的分組，避免過多無用分組的生成。

3.3 用于MRDM的GA

用于多關系數據挖掘的遺傳算法，其核心思想是[4]:每個事務對應一條染色體，事務可以組成個體，在這些個體上執行遺傳操作，包括選擇，交叉以及變異，最后將所有的分組合并，提取出規則的前項。

初始個體的選擇并非采用隨機策略，參照Apriori算法，頻繁1-項集是生成頻繁n-項集的基礎，我們從那些能夠提取出至少包含一個項的規則的事務集中初始化個體。如表1，滿足最小支持度為60%的頻繁1-項集是(P1，P3，P4)，可在包含這些項的事務集中對個體進行初始化。

下面引入一些參數的定義:

染色體適應度CF:反應的是該染色體可能同其他染色體相結合組成規則的可能性。

其中，n 是染色體中基因的數，N 是個體中染色體的數，Bi 是第i個基因的值(0或1)，ti 是第i個基因相對于個體中所有染色體取到值1的數。如個體(T1，T2，T4)，n 為5，N 為3，CF(T4)的值為1/(3-3+1)即1，CF(T1)值為1/(3-2+1)+ 1/(3-3+1)即3/2，CF(T2)值為1/(3-1+1)+ 1/(3-2+1) + 1/(3-3+1)即11/6。

個體適應度IVF:如果個體不能提取出規則，則IVF為0，否則，IVF是規則包含的項數。如個體(T1，T2，T3)能提取出規則(P3，P4)，所以IVF為2。

升級指數UI:表示的是獲取或擴展個體規則的差距，取值負數。UI的值越大，則意味著使用遺傳運算獲取或擴展該規則的可能性越大。如個體(T1，T2，T3)能提取出規則(P3，P4)，但如果T1也售出了P1，則該個體規則能夠被擴展成(P1，P3，P4)，所以該個體UI值為-1。

下面介紹的是基于以上參數的遺傳運算:

選擇:所有IVF比0大的個體，并確保個體的唯一性。

交叉:有兩方面需要考慮，第一，CF取值越大，該染色體入選的可能性越大;第二，檢查是否可在雙親間執行置換染色體的操作以加強其中之一的UI值，如果這類染色體存在，就生成一個新個體。

變異:變異的目的是使個體更易于獲取或擴展規則。變異的過程是要找出包含升級所需基因子集的染色體，也要找出個體規則所包含的項集，通過置換染色體的方式提高UI的值。變異的可能性要依據UI的值，UI的值越大，發生變異的可能性愈大。

4 結束語

在本文中，我們著重介紹了一種將遺傳算法和Apriori算法應用于多關系數據挖掘的方法，遺傳算法負責找出擴展的關聯規則的前項，Apriori算法根據生成規則前項所對應的事務集從其余的相關屬性中挖掘出擴展的關聯規則的后項。該方法可有效地從關系數據庫的多張表中挖掘出重要信息。

參考文獻:

[1] Dzeroski，Saso.Multi-Relational Data Mining: An Introduction[EB/OL].http://www.cs.wisc.edu/EDAM/.

[2] 楊曉華，沈珍瑤.智能算法及其在資源環境系統建模中的應用[M].北京:北京師范大學出版社，2004:13-23.

[3] 萬旺根，崔濱.遺傳進化理論及其在數據挖掘中的應用[EB/OL].http://www.businessanalysis.cn/x/html/66/t-10966.html.

[4] Dou W X，Hu J L.Distributed Multi-Relational Data Mining Based on Genetic Algorithm[EB/OL].http://www.hflab.ips.waseda.ac.jp/~jinglu/Publics/cec08Dou.pdf.