一種多關(guān)系頻繁模式挖掘算法

摘 要:傳統(tǒng)數(shù)據(jù)挖掘算法在處理多表時，需要物理連接，存在效率不高的問題。為了解決這一問題，提出了一種多關(guān)系頻繁模式挖掘算法。該算法利用元組ID傳播的思想，使多表間無須物理連接，就可以直接挖掘頻繁模式。實驗表明，此算法具有較高的效率。

關(guān)鍵詞:多關(guān)系數(shù)據(jù)挖掘; 頻繁模式; 元組ID傳播

中圖分類號:TP311文獻標志碼:A

文章編號:1001-3695(2009)09-3285-04

doi:10.3969/j.issn.1001-3695.2009.09.024

Multi-relational frequent pattern mining algorithm

DENG Zuo-xiang， LIU Lian-fang1，2 ， LIANG Yi-ping， ZHOU Xiao-ping

(1. School of Computer Electronics Information，Guangxi University， Nanning 530004， China;2. Pingsoft New Technology Co. Ltd. of Nanning， Nanning 530007， China)

Abstract:While dealing with multi-relation， traditional data mining algorithms used the way of physical join. In order to solve this problem， this paper proposed a multi-relational frequent pattern mining algorithm. By taking advantage of tuple ID propagation approach， this algorithm could directly mine frequent pattern inmulti-relation without physical join. Experiment demonstrates that， this algorithm has high efficiency.

Key words:multi-relational data mining; frequent pattern; tuple ID propagation

數(shù)據(jù)挖掘，就是從大型的數(shù)據(jù)庫中提取人們感興趣的知識。大多數(shù)傳統(tǒng)的數(shù)據(jù)挖掘方法只適用于在數(shù)據(jù)庫的單表上進行挖掘。當面對多表時，不得不把這些表物理上連接到一張表中，這樣會出現(xiàn)準確率低、效率低等問題。在這種情況下，多關(guān)系數(shù)據(jù)挖掘應(yīng)運而生[1]。多關(guān)系數(shù)據(jù)挖掘研究直接在數(shù)據(jù)庫多張表上進行挖掘的方法，無須向單表轉(zhuǎn)換。

1 相關(guān)工作

1.1 傳統(tǒng)頻繁模式挖掘算法

挖掘頻繁模式算法最有代表性的是Apriori算法[2]，但是它只適用于單維的、單層的數(shù)據(jù)。在文獻[3]中提出的頻繁模式挖掘算法是一種傳統(tǒng)的單表頻繁模式挖掘算法，雖然適用于多維，但是只能處理單表頻繁模式挖掘，不適用于多表，當面對多表時，首先不得不把多表集成到單表，存在效率低的問題。

1.2 基于ILP的多關(guān)系數(shù)據(jù)挖掘算法

目前大多數(shù)的多關(guān)系數(shù)據(jù)挖掘算法都是借鑒ILP思想[4]發(fā)展起來的。ILP使用邏輯編程語言作為知識表示方式，這種知識表示方式更具表達力，能夠靈活方便地表示關(guān)系學(xué)習(xí)與多關(guān)系數(shù)據(jù)挖掘過程中的多關(guān)系數(shù)據(jù)、背景知識以及涉及多關(guān)系的復(fù)雜模式。此外，ILP方法便于在歸納推理過程中使用背景知識。這些都是ILP思想成為多關(guān)系數(shù)據(jù)挖掘主要方法的直接原因。但ILP思想存在一些缺點:a)處理不確定性和有噪聲數(shù)據(jù)的能力有限;b)ILP使用基于θ包含的操作在假設(shè)空間中進行啟發(fā)式搜索，而θ包含計算實質(zhì)上是一個NP完全問題，這使得ILP思想效率低，可擴展性差。

WARMR[5，6]和FARMER[7]是兩種基于ILP思想的多關(guān)系頻繁模式挖掘算法。WARMR算法的核心思想與Apriori算法相同，采用逐層的、寬度優(yōu)先的搜索策略。FARMER采用一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)——Trie樹來存儲和操縱查詢，Trie樹中從根節(jié)點到葉子節(jié)點的每條路徑都對應(yīng)一個查詢，利用該樹進行查詢的生成和支持度的計算。由于WARMR和FARMER都基于ILP思想，這使得兩者的效率都不高。

1.3 基于元組ID傳播的多關(guān)系數(shù)據(jù)挖掘算法

除了ILP思想，多關(guān)系數(shù)據(jù)挖掘也可以借鑒文獻[8]中提出的元組ID傳播思想。元組ID傳播是一種在多表間建立虛連接的思想，它的定義如下:假設(shè)有兩個關(guān)系R1和R2，R1的主鍵是整數(shù)屬性，這些整數(shù)代表R1中每個元組的ID(如果沒有這樣的主鍵，可以創(chuàng)建一個，表示為R1.ID)。假定關(guān)系R1和R2可以按屬性R1.k和R2.k連接(R1包含R2的主鍵k)。則在R2中增加一列屬性IDset(R1)，對R2的每一個元組t，其在IDset(R1)屬性上的值是，R1中所有可與t連接的元組在R1.ID上的值，即t在IDset(R1)上的值等于∪u∈R1，u.k=t.kR1.ID(u)， R1.ID(u)表示元組u在R1.ID上的值。也就是說，R1中所有元組的ID都傳播到R2可與之連接的元組的屬性IDset(R1)上。

CrossMine[8]是一種基于元組ID傳播思想的多關(guān)系分類算法。CrossMine利用元組ID傳播來評估每個謂詞的foil增益，把最佳謂詞添加到當前規(guī)則中。借助元組ID傳播，CrossMine無須物理連接，大大提高了分類的效率。

Crossclus[9]是一種基于元組ID傳播思想的用戶指導(dǎo)的多關(guān)系聚類算法。在用戶指定某一屬性后，Crossclus利用元組ID傳播來搜索相關(guān)屬性，通過這些屬性計算對象之間的相似度。借助元組ID傳播，Crossclus無須物理連接，聚類效率較高。

MFP[10]是一種基于元組ID傳播的用戶指導(dǎo)的多關(guān)系關(guān)聯(lián)規(guī)則算法。在用戶指定某些屬性后，MFP發(fā)現(xiàn)由這些屬性所產(chǎn)生的關(guān)聯(lián)規(guī)則。借助元組ID傳播，MFP無須物理連接，效率較高。

1.4 本文工作

本文針對傳統(tǒng)的頻繁模式挖掘算法不適用于解決基于ILP思想的多關(guān)系頻繁模式挖掘算法效率低的問題，提出了一種多關(guān)系頻繁模式挖掘算法。借助于元組ID傳播的思想，對表進行虛連接，使算法可以直接在多張表上挖掘出所有頻繁模式，提高了在多關(guān)系中挖掘頻繁模式的效率。

在挖掘多表頻繁項集時，只考慮來自以下兩種情況的表所產(chǎn)生的項集:a)兩個表之間存在主鍵與外鍵的對應(yīng);b)兩個表的主鍵同時是某個第三表的外鍵。不考慮其他情況，因為其他情況在數(shù)據(jù)庫中代表這些表沒有很強的相關(guān)性。

2 術(shù)語定義

定義1 項。包含于任一個表的非主鍵和外鍵屬性的每個不同取值稱為一個項，記為一個屬性和取值對:屬性=取值，或用惟一的一個標志符表示，如用標志符X表示一個項。

定義2 項集。多個項構(gòu)成的集合稱為項集。

定義3 單表項集。項集中的每個項，若都來自同一個表，則稱為單表項集。

定義4 多表項集。項集中的每個項，若涉及多個表，則稱為多表項集。

定義5 支持度計數(shù)。一個項集X的支持度計數(shù)count定義為:如果X是單表項集，count為該表的包含X的元組的個數(shù);如果X是多表項集，將有關(guān)的表進行連接操作后得到連接表，count為連接表中包含X的元組的個數(shù)。

定義6 頻繁項集。由用戶給定一個支持度計數(shù)閾值，所有支持度計數(shù)不小于該閾值的項集稱為頻繁項集。

定義7 多關(guān)系頻繁模式挖掘。給定支持度計數(shù)閾值，發(fā)現(xiàn)存在于一個數(shù)據(jù)庫的多個表中的所有不小于閾值的頻繁項集，包括單表頻繁項集和多表頻繁項集。

3 算法步驟

3.1 預(yù)處理

常見的數(shù)據(jù)庫屬性包括二元屬性、分類屬性、序數(shù)型屬性、區(qū)間標度屬性。由于二元屬性、分類屬性、序數(shù)型屬性的取值是有限的，可以直接進行挖掘。而區(qū)間標度屬性的取值包含有無限多個連續(xù)值，不利于統(tǒng)計計數(shù)，因此必須對其預(yù)處理。

對區(qū)間標度屬性預(yù)處理的方法是使用預(yù)定義的概念分層對其進行離散化[11]。例如，在一個職工信息的表中，有income屬性，它屬于區(qū)間標度屬性。在挖掘前，可以使用預(yù)先定義的概念分層對其進行離散化，離散化的數(shù)值可以標記為“0…1000”“1000…2000”“2000…3000”等，將原來的屬性值映射到這些區(qū)間。離散化的數(shù)值屬性具有區(qū)間標記，可以像分類屬性一樣處理(其中，每個區(qū)間看做一類)。

3.2 工作過程

算法的工作過程如下:

a)由用戶設(shè)定支持度計數(shù)的閾值。

b)對任何一對存在主鍵外鍵對應(yīng)的兩個表之間進行元組ID傳播。

c)對每個表的每個屬性(除了主鍵、外鍵、IDset)進行掃描，對該屬性所產(chǎn)生的每個項進行支持度計數(shù)，支持度計數(shù)不小于閾值的項都是1-頻繁項集。為了區(qū)別每個項，把它表示成“表.屬性(值)”的形式。在存儲每個1-頻繁項集時，保存它的三類信息:

(a)該項集的名稱，即“表.屬性(值)”。

(b)該項集的支持度計數(shù)，設(shè)項集名稱為X，則支持度計數(shù)表示為X.count。

(c)包含該項集的所有元組ID的值，也就是保存該表中的包含該項集的所有元組的主鍵值，設(shè)項集名稱為X，表示為X.ID。

d)把每兩個1-頻繁項集組合起來，產(chǎn)生候選2-項集。在產(chǎn)生候選2-項集時，不用考慮同一個表的同一個屬性所產(chǎn)生的項組合而成的2-項集，因為必然沒有哪個元組包含這個2-項集，其支持度計數(shù)必然是0。只考慮組合不同屬性所產(chǎn)生的項。設(shè)有兩個項，分別是X、Y，把它們結(jié)合起來就是2-項集{X，Y}，需要對其進行支持度計數(shù)。根據(jù)X、Y所來自的表，分為以下兩種情況:

(a)如果X、Y來自同一個表，則{X，Y}是單表項集，比較X.ID和Y.ID，在它們當中相同的ID個數(shù)就是2-項集{x，y}的支持度計數(shù)。其中那些相同的ID就是包含{X，Y}的元組的ID。

(b)如果X、Y來自不同的表，則{X，Y}是多表項集，需要看它們所來自的表是否滿足上一節(jié)所說的兩種情況。具體的判斷方法是:這兩個表是否有一個表包含另一個表的IDset，或者這兩個表是否同時包含某個第三方表的IDset。

如果這兩個表是有一個表包含另一個表的IDset，假設(shè)X來自A表，Y來自B表，A表包含B表的IDset，也就是A表包含屬性IDset(B)。從X.ID中對應(yīng)A表的所有元組取出這些元組中的屬性IDset(B)的值，用IDset(B)的值的并集與Y.ID比較，相同的ID個數(shù)就是2-項集{x，y}的支持度計數(shù)。舉一個簡單的例子，假設(shè)X.ID和Y.ID中都包含1，也就是說A表的ID為1的元組包含X，B表的ID為1的元組包含Y，如果A表中ID為1的元組的屬性IDset(B)中有值1，那么就可以為2-項集{X，Y}的支持度計數(shù)加1，因為把A表和B表進行連接操作后，從IDset(B)的值得知，A表中ID為1的元組可以與B表中的ID為1的元組連接，連接后的元組必然包含2-項集{X，Y}。

如果這兩個表是同時包含某個第三方表的IDset，假設(shè)X來自A表，Y來自B表，存在一個C表，A和B表都包含C表的IDset，也就是A和B表都包含屬性IDset(C)。從X.ID中對應(yīng)A表的所有元組取出這些元組中的屬性IDset(C)的值，并取IDset(C)值的并集，設(shè)為a;同樣，從Y.ID中對應(yīng)B表的所有元組，取出這些元組中的屬性IDset(C)的值，并取IDset(C)值的并集，設(shè)為b。比較并集a和b，其中相同的ID個數(shù)就是2-項集{x，y}的支持度計數(shù)。舉一個簡單的例子，假設(shè)X.ID和Y.ID中都包含1，也就是說A表的ID為1的元組包含X，B表的ID為1的元組包含Y，如果A表中ID為1的元組的屬性IDset(C)中有某個值，設(shè)為d，而且B表中ID為1的元組的屬性IDset(C)中也有d的話，那么就可以為2-項集{X，Y}的支持度計數(shù)加1。因為A與C表進行連接操作后，由IDset(C)知，A表ID為1的元組可以與C表ID為d的元組連接，而B表ID為1的元組可以與C表ID為d的元組連接，從而A表中主鍵為1的元組可以與B表中的主鍵為1的元組連接，連接后的元組必然包含2-項集{X，Y}。

支持度計數(shù)不小于閾值的候選2-項集都是2-頻繁項集。在保存2-頻繁項集時，類似于1-頻繁項集，也需要保存以下三類:

(a)該項集的名稱，因為要區(qū)分出項所在的表的名稱，所以應(yīng)該保存為“表.屬性(值)，表.屬性(值)”。(b)該項集的支持度計數(shù)。

(c)包含該項集的所有元組ID集的值，對于任意一個產(chǎn)生該項集一個支持度的情況，無論是單表項集，還是多表項集，都保存為“表.ID(值)，表.ID(值)”。例如，假設(shè)一個由A表ID為1的元組(包含項X)，以及由B表ID為1的元組(包含項Y)，它們進行連接操作后，包含2-項集{X，Y}，對于這種產(chǎn)生2-項集{X，Y}的一個支持度的情況，把元組ID集的值記為“A.ID(1)，B.ID(1)”。

e)在發(fā)現(xiàn)了2-頻繁項集后，就要找出候選3-項集。利用Apriori算法的性質(zhì)——頻繁項集的所有非空子集也必須是頻繁的。因此，候選3-項集的所有子集都必須是頻繁項集。根據(jù)這一點，產(chǎn)生候選3-項集。為候選3-項集計數(shù)的方法與前面的1-項集和2-項集有所不同，不再通過掃描數(shù)據(jù)庫來計數(shù)，而是通過如下方法來為候選3-項集計數(shù)。

為候選3-項集計數(shù)的方法是:假設(shè)有三個項X、Y、Z，產(chǎn)生了三個2-頻繁項集，分別設(shè)為{X，Y}、{X，Z}、{Y，Z}，包含它們的所有元組ID集的值分別為{X，Y}.ID、{X，Z}.ID、{Y，Z}.ID。分別從{X，Y}.ID、{X，Z}.ID、{Y，Z}.ID中各提取一個元組ID集，分別設(shè)為ID1、ID2、ID3。比較ID1、ID2、ID3，如果在ID1、ID2、ID3中，來自同一個表的ID值都相同的話，那么可以為候選3-項集{X，Y，Z}的計數(shù)加1，且產(chǎn)生該{X，Y，Z}的元組ID集的值，就是ID1、ID2、ID3的并集。循環(huán)地比較{X，Y}.ID、{X，Z}.ID、{Y，Z}.ID中的各個元組ID集，就可以知道{X，Y，Z}的支持度計數(shù)。

舉一個計數(shù)方法的例子，并說明理由。假設(shè)有三個表A，B，C，有三個元組t1、t2、t3，t1屬于A，標志為ID1，t2屬于B，標志為ID2，t3屬于C，標志為ID3，t1包含項X，t2包含項Y，t3包含Z。假設(shè)有三個2-頻繁項集{X，Y}，{X，Z}，{Y，Z}。其中{X，Y}.ID中包含(ID1，ID2)(也就是說，t1和t2連接在一起后，產(chǎn)生了{X，Y}的一個支持度)，{X，Z}.ID中包含(ID1，ID3)，{Y，Z}.ID中包含(ID2，ID3)。如果從{X，Y}.ID、{X，Z}.ID、{Y，Z}.ID中各提取的一個元組ID集分別是(ID1，ID2)，(ID1，ID3)，(ID2，ID3)，由于它們來自同一個表的ID值相等，所以這種情況可以為{X，Y，Z}的計數(shù)加1。因為t1、t2、t3是可以彼此互相連接的，當A、B、C三個表進行連接后，t1、t2、t3必然可以連接成一個元組，這個元組就包含{X，Y，Z}，產(chǎn)生{X，Y，Z}的一個支持度。

支持度計數(shù)不小于閾值的候選3-項集都是3-頻繁項集。需要保存的3-頻繁項集的信息與前面2-頻繁項集是類似的。

f)4-頻繁項集，以及項的個數(shù)大于4的頻繁項集的挖掘方法，與3-頻繁項集類似。

算法的偽碼如下:

算法:在多關(guān)系中挖掘頻繁項集。

輸入:一個多關(guān)系數(shù)據(jù)庫D1，支持度計數(shù)閾值。

輸出:D1中的頻繁項集。

方法:

D2=傳播元組ID(D1);

L1=挖1-項集(D2，支持度計數(shù)閾值);

ifL1≠then L2=挖2-項集(L1，支持度計數(shù)閾值);

for (k=3;Lk-1≠;K++)

{ Ck =apriori_gen(Lk-1) ;

 for each X ∈ Ck

{項集X1，X2，…，Xk  ← X的(k-1)個子(k-1)-頻繁項集;

for eachID1∈X1.ID，…，IDk∈Xk.ID

ifID1，…，IDk的來自相同的表的ID值都相等then

X.count ++;

ifX.count>=支持度計數(shù)閾值then

把X加入Lk，存儲X.count，X.ID;}

}

return L=∪kLk;

Procedure傳播元組ID(D)

for each 關(guān)系R1∈D

for each 關(guān)系R2∈D

ifR2的主鍵在R1中作為外鍵then

把R1的ID傳播到R2;

returnD;

Procedure 挖1-項集(D，支持度計數(shù)閾值)

for each 關(guān)系R∈D

for each 屬性A∈R

if A ≠ 主鍵、外鍵、IDsetthen

為A上的每一個不同的項X進行計數(shù);

ifX.count>=支持度計數(shù)閾值 then

把X加入1-頻繁項集L1，存儲X.count、X.ID;

returnL1;

Procedure 挖2-項集(L1，支持度計數(shù)閾值)

for each1-頻繁項集X∈L1

for each1-頻繁項集Y∈L1

合并X、Y，把{X，Y}加入候選2-項集C2，R1←X所在表，R2←Y所在表;

ifR1=R2then

比較X.ID和Y.ID，相同的ID個數(shù)為項集{X，Y}的計數(shù);

else

if R1、R2中的某一方包含另一方的IDsetthen

取項的ID對應(yīng)的元組的IDset值的并集，與另一個項的ID進行比較，相同的ID個數(shù)為項集{X，Y}的計數(shù);

if R1、R2中都包含某個第三方表的IDsetthen

取X.ID和Y.ID對應(yīng)的元組的IDset值的并集，對兩并集進行比較，相同的ID個數(shù)為項集{X，Y}的計數(shù);

if{X，Y}.count>=支持度計數(shù)閾值then

把{X，Y}加入2-頻繁項集L2，存儲{X，Y}.count、{X，Y}.ID;

return L2;

Procedureapriori_gen(Lk-1)

for each項集l1∈Lk-1

for each項集l2∈Lk-1

if (l1[1]=l2[1])∧…∧(l1[k-1]

{c=l1l2 ;

ifhas_infrequent_subset(c， Lk-1)then

刪除c;

else把c加入 Ck;}

return Ck;

Procedurehas_infrequent_subset(c， Lk-1)

for each(k-1)-subsets ∈ c

ifsLk-1thenreturntrue;

return 1;

4 實驗

本文使用PKDD CUP 1999中的包含八個表的金融數(shù)據(jù)庫(http://lisp.vse.cz/pkdd99/Challenge/chall.ht)，作為實驗數(shù)據(jù)集，做兩個實驗。

實驗環(huán)境:

操作系統(tǒng)為Windows XP Professional;內(nèi)存為512 MB;CPU為Pentium 4 3.0 GHz;平臺為Borland C++ Builder 6.0。

實驗1

目的:比較多關(guān)系頻繁模式挖掘算法和物理連接多表并采用傳統(tǒng)的單表頻繁模式挖掘算法的運行時間。

過程:從數(shù)據(jù)集中選擇兩個表(loan、account)，進行裁剪，保留200個元組;設(shè)定支持度閾值為4%，也就是支持度計數(shù)閾值為200×4%=8。

結(jié)果:運行時間對比如表1所示。從實驗結(jié)果可以看到，本文提出的算法有較高的效率。

表1 兩種方法的運行時間比較

方法運行時間/s

多關(guān)系頻繁模式挖掘算法6.933

傳統(tǒng)方法12.412

實驗2

目的:分別在表的個數(shù)、元組個數(shù)、支持度變化的情況下，比較運行時間的變化。

過程:保持元組個數(shù)不變(對八個表都進行裁剪，使每個表都只保留200個元組)、支持度不變(設(shè)定支持度閾值為4%，也就是支持度計數(shù)閾值為200×4%=8)，改變表的個數(shù)(分別從八個表中選擇其中的兩個表(loan、account)、四個表(loan、account、order、transaction)、六個表(loan、account、order、transaction、district、disposition)，以及全部八個表)，作為算法的輸入，得出它們的運行時間。

結(jié)果:運行時間變化如圖1所示。從圖1可以看到，隨著表的個數(shù)的不斷增加，運行時間不斷增加，并且增長速度越來越快。

過程:保持表的個數(shù)不變(選擇loan、account兩個表)、元組個數(shù)不變(對兩個表都進行裁剪，使每個表都只保留500個元組)，改變支持度(設(shè)定三個支持度閾值2%、4%、6%)，作為算法的輸入，得出它們的運行時間。

結(jié)果:運行時間變化如圖2所示。從圖2可以看出，隨著支持度閾值的不斷增加，運行時間不斷下降。

過程:保持表的個數(shù)不變(選擇loan、account、district三個表)、支持度不變(設(shè)定支持度閾值為4%)，改變元組的個數(shù)(對三個表都進行裁剪，使三個表分別都保留50、100、200、300、400、500個元組)，作為算法的輸入，得出它們的運行時間。

結(jié)果:運行時間變化如圖3所示。從圖3可以看出，隨著每張表的元組的個數(shù)的不斷增加，運行時間不斷增加，并且增長速度越來越快。

5 結(jié)束語

由于傳統(tǒng)的數(shù)據(jù)挖掘方法在處理多關(guān)系頻繁模式挖掘時，不得不首先通過物理連接的方法把多表集成到單表，效率低;而基于ILP的多關(guān)系數(shù)據(jù)挖掘算法也存在效率低、可擴展性差的問題。本文提出了一種多關(guān)系頻繁模式挖掘算法，其利用了元組ID傳播的思想，在多關(guān)系上建立虛連接，可以直接在多關(guān)系上挖掘頻繁項集。實驗表明，本文提出的算法具有較高的效率。今后，可以繼續(xù)借助元組ID傳播的思想，對多關(guān)系數(shù)據(jù)挖掘的各個任務(wù)作進一步研究。

參考文獻:

[1]DZEROSKI S， LAVRAC N. Relational data mining[M]. Berlin:Springer，2001.

[2]AGRAWAL R， SRIKANT R. Fast algorithms for mining association rules[C]//Proc of International Conference on Very Large Data Bases. Santiago:[s.n.]， 1994:487-499.

[3]KAMBER M， HAN Jia-wei， CHIANG J Y. Metarule-guided mining of multi-dimensional association rules using data cubes[C]//Proc of International Conference on Knowledge Discovery and Data Ming. New-port Beach:[s.n.]， 1997:207-210.

[4]LAVRAC N， DZEROSKI S. Inductive logic programming:techniques and applications[M].New York: Ellis Horwood，1994.

[5]DEHASPE L. Mining association rules in multiple relations[C]//Proc of the 7th International Workshop on Inductive Logic Programming. Berlin:Springer，1997:125-132.

[6]DEHAPE L. Frequent pattern discovery in first-order logic[D]. Belgium:Katholieke University Leuven，1998.

[7]NIJSSEN S， KOK J. Faster association rules for multiple relations[C]//Proc of the 17th International Conference on Artificial Intelligence. 2001:891-896.

[8]YIN Xiao-xin， HAN Jia-wei， YANG Jiong， et al. CrossMine:efficient classification across multiple database relations[C]//Proc of International Conference on Data Engineering. Boston:[s.n.]， 2004:399-410.

[9]YIN Xiao-xin， HAN Jia-wei， YU P S. Cross-relational clustering with user’s guidance[C]//Proc of the 11th ACM SIGKDD Conference on Knowledge Discovery in Data Mining. Chicago:[s.n.]， 2005.

[10]郭景峰，邊偉峰，霍崢，等. 一種基于用戶指導(dǎo)的多關(guān)系關(guān)聯(lián)規(guī)則挖掘算法[J]. 計算機研究與發(fā)展，2007，44(增刊):22-26.

[11]HAN Jia-wei， KAMBER M. 數(shù)據(jù)挖掘:概念與技術(shù)[M].范明，孟小峰，譯. 2版. 北京:機械工業(yè)出版社，2007:164-165.