多關(guān)系數(shù)據(jù)挖掘方法研究

摘要：目前大多數(shù)數(shù)據(jù)挖掘方法是從單關(guān)系中發(fā)現(xiàn)模式，而多關(guān)系數(shù)據(jù)挖掘（MRDM）則可直接從關(guān)系數(shù)據(jù)庫的多表中抽取有效模式。MRDM可以解決原有命題數(shù)據(jù)挖掘方法不能解決的問題，它不僅有更強(qiáng)的信息表示能力，可以表示和發(fā)現(xiàn)更復(fù)雜的模式，還可以在挖掘進(jìn)程中有效地利用背景知識來提高挖掘效率和準(zhǔn)確率。近年來，借鑒歸納邏輯程序設(shè)計（ILP）技術(shù)，已經(jīng)形成許多多關(guān)系數(shù)據(jù)挖掘方法，如關(guān)系關(guān)聯(lián)規(guī)則挖掘方法、關(guān)系分類聚類方法等。

關(guān)鍵詞：多關(guān)系數(shù)據(jù)挖掘（關(guān)系數(shù)據(jù)挖掘）；歸納邏輯程序設(shè)計；關(guān)系分類回歸；關(guān)系關(guān)聯(lián)規(guī)則；基于距離的關(guān)系方法

中圖法分類號：TP391文獻(xiàn)標(biāo)識碼：A

文章編號：1001－3695(2006)09－0008－05

1 引言

數(shù)據(jù)庫中的知識發(fā)現(xiàn)（KnowledgeDiscoveryinDatabases，KDD）是在數(shù)據(jù)庫中尋找有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過程[17]。相對于數(shù)據(jù)預(yù)處理和模式評價而言，數(shù)據(jù)挖掘是這一過程中的關(guān)鍵環(huán)節(jié)，它是應(yīng)用計算技術(shù)在數(shù)據(jù)中發(fā)現(xiàn)模式的過程。目前，大多數(shù)數(shù)據(jù)挖掘方法是從單關(guān)系中尋找模式，但是現(xiàn)實中的數(shù)據(jù)大多以多關(guān)系的形式存在，這樣就導(dǎo)致在數(shù)據(jù)預(yù)處理上耗費(fèi)了大量時間，比如要進(jìn)行耗時的數(shù)據(jù)庫表的連接和聚合等處理，而且這些處理往往會導(dǎo)致很多有用信息的丟失。

原有的從單關(guān)系中發(fā)現(xiàn)模式的數(shù)據(jù)挖掘方法叫做命題學(xué)習(xí)方法或?qū)傩浴祵W(xué)習(xí)方法，該方法使用命題邏輯表示知識和模式。而關(guān)系數(shù)據(jù)挖掘（RelationalDataMining，RDM）也稱為多關(guān)系數(shù)據(jù)挖掘（MultiRelationalDataMining，MRDM），是在由多個關(guān)系表構(gòu)成的關(guān)系數(shù)據(jù)庫中抽取模式的一個多學(xué)科交叉的領(lǐng)域。它綜合運(yùn)用歸納邏輯程序設(shè)計（InductiveLogicProgramming，ILP）、KDD、機(jī)器學(xué)習(xí)和關(guān)系數(shù)據(jù)庫等方法，致力于直接從多關(guān)系數(shù)據(jù)集中發(fā)現(xiàn)知識的新方法的研究[1]，挖掘由復(fù)雜的結(jié)構(gòu)化對象組成的數(shù)據(jù)集也是該領(lǐng)域的研究方向之一。MRDM不同于基于單關(guān)系的挖掘方法，它可以直接對多關(guān)系數(shù)據(jù)進(jìn)行挖掘，避免了復(fù)雜的預(yù)處理過程和由于壓縮帶來的信息丟失等問題。MRDM使用一階謂詞邏輯來表示知識和模式，具有比命題邏輯更強(qiáng)的表達(dá)能力，因此MRDM可以解決很多原有命題方法不能解決的實際問題，能夠方便地使用背景知識也是MRDM的一個重要特征。

現(xiàn)在，數(shù)據(jù)挖掘中通常使用的模式類型和方法已經(jīng)擴(kuò)展到多關(guān)系的情況下，并形成許多MRDM方法，如關(guān)系關(guān)聯(lián)規(guī)則挖掘方法、關(guān)系分類聚類方法等。這些方法已成功地應(yīng)用到多個領(lǐng)域，包括商務(wù)數(shù)據(jù)分析、生物信息學(xué)、醫(yī)藥設(shè)計以及Web挖掘中的信息抽取等，而最成功的應(yīng)用是在生物信息領(lǐng)域[9]。

2ILP技術(shù)

MRDM主要是借鑒ILP的思想和技術(shù)發(fā)展起來的。ILP是機(jī)器學(xué)習(xí)和邏輯編程結(jié)合的產(chǎn)物，主要研究多關(guān)系數(shù)據(jù)挖掘技術(shù)[1]。ILP利用背景知識從給定的實例發(fā)現(xiàn)未知實例的規(guī)律。其基本任務(wù)是學(xué)習(xí)未知關(guān)系的邏輯定義，在SeminalMIS（ILP最有影響力的先驅(qū)之一）系統(tǒng)和FOIL系統(tǒng)（最出名的ILP系統(tǒng)之一）中詳細(xì)闡述了如何歸納定義未知的關(guān)系[18]。近年來，ILP已經(jīng)可以處理所有的數(shù)據(jù)挖掘任務(wù)，如分類、回歸、聚類、預(yù)測和關(guān)聯(lián)規(guī)則分析等。

2．1邏輯程序和數(shù)據(jù)庫

為了在多關(guān)系數(shù)據(jù)表中學(xué)習(xí)有效的模式，ILP方法主要使用基于邏輯編程的語言（一階邏輯的子集），而關(guān)系代數(shù)（關(guān)系數(shù)據(jù)庫的形式化理論基礎(chǔ)）也是一階邏輯的子集（一階邏輯有時候也叫做謂詞邏輯或關(guān)系邏輯），這種一致性使得ILP與關(guān)系數(shù)據(jù)庫間的交互較為容易。

關(guān)系數(shù)據(jù)庫是關(guān)系的集合，在關(guān)系數(shù)據(jù)庫中，關(guān)系可以是數(shù)據(jù)庫中的表，也可以是數(shù)據(jù)庫中的視圖（作為明確的邏輯規(guī)則出現(xiàn)）。后者一般表示能從其他關(guān)系推理得到的關(guān)系，如已經(jīng)定義了父親、母親的關(guān)系，我們能夠擴(kuò)展這種表示，內(nèi)涵地定義祖父、祖母、祖先、表兄弟的關(guān)系。而邏輯程序中的謂詞對應(yīng)于關(guān)系數(shù)據(jù)庫中的關(guān)系，謂詞的變元則對應(yīng)于關(guān)系的屬性，主要的不同是關(guān)系的屬性是有類型的（如關(guān)系數(shù)據(jù)庫中每一屬性都預(yù)先指定所屬類型）[1]。關(guān)系數(shù)據(jù)庫與邏輯編程術(shù)語的對照如表1所示。

表1數(shù)據(jù)庫術(shù)語與邏輯編程術(shù)語的對照表

2．2θ包含[1]

大多數(shù)ILP方法是自頂向下地、從一般到特殊地使用基于θ包含的特化操作來搜索假設(shè)空間。對于ILP而言，θ包含是非常重要的，θ包含為假設(shè)空間提供了概化的次序，結(jié)構(gòu)化了假設(shè)空間；搜索時的剪枝方法以θ包含為基礎(chǔ)；自頂向下的求精圖（RefinementGraphs）的子句構(gòu)造技術(shù)和對求精圖搜索的中止條件的設(shè)定方法等也都以θ包含為基礎(chǔ)。

3多關(guān)系數(shù)據(jù)挖掘方法

根據(jù)表示語言的不同，目前的數(shù)據(jù)挖掘系統(tǒng)可以分為兩類：命題學(xué)習(xí)系統(tǒng)（又稱屬性—值學(xué)習(xí)器）和一階邏輯學(xué)習(xí)系統(tǒng)（又稱關(guān)系學(xué)習(xí)器或多關(guān)系數(shù)據(jù)挖掘系統(tǒng)）[1]。除個別情況外，多關(guān)系數(shù)據(jù)挖掘系統(tǒng)都是基于ILP技術(shù)來擴(kuò)展（Upgrading）原有的命題數(shù)據(jù)挖掘系統(tǒng)而形成的。擴(kuò)展命題學(xué)習(xí)器到關(guān)系學(xué)習(xí)器有很多優(yōu)點：用戶已經(jīng)熟悉了命題學(xué)習(xí)器的使用，理解和使用相應(yīng)的關(guān)系學(xué)習(xí)器也就較為容易；命題學(xué)習(xí)器所使用的一些啟發(fā)式方法和優(yōu)化方法也可以在關(guān)系學(xué)習(xí)器中繼續(xù)使用；命題學(xué)習(xí)器與相應(yīng)的關(guān)系學(xué)習(xí)器變體之間的對應(yīng)關(guān)系使得兩者在相同的數(shù)據(jù)集合上可以得到一致的結(jié)果。

近年來，已經(jīng)有很多命題數(shù)據(jù)挖掘方法被擴(kuò)展到多關(guān)系情況下，例如，著名的FOIL系統(tǒng)是命題規(guī)則歸納程序CN2的擴(kuò)展；另一個出名的ILP系統(tǒng)Progol是AQ的規(guī)則歸納方法的擴(kuò)展[7]；RIBL擴(kuò)展了經(jīng)典的K近鄰算法；SCART和Tilde擴(kuò)展了CART和C4.5中的決策樹范例；WARMR擴(kuò)展了APRIORI；MACCENT擴(kuò)展了最大熵方法；Flipper擴(kuò)展了Cohen早期的Ripper；Koller的概率關(guān)系模型擴(kuò)展了命題的Bayesian網(wǎng)絡(luò)；Kirste和Wrobel的聚類系統(tǒng)則更新由低向上的層次聚類方法到多關(guān)系情況下等[1]。

3．1關(guān)系分類回歸方法

決策樹和回歸樹（模型樹）是兩種最流行的數(shù)據(jù)挖掘模型，但是決策樹模型也有其局限性。在命題表示中訓(xùn)練樣例必須被表示成固定長度的屬性值向量，一個訓(xùn)練數(shù)據(jù)庫就是一個簡單的二維值表，訓(xùn)練樣例內(nèi)部結(jié)構(gòu)方面的信息卻并不能被表示。這使得命題決策樹算法很難在對象的內(nèi)部結(jié)構(gòu)極大影響挖掘結(jié)果的領(lǐng)域中得到應(yīng)用，如化學(xué)、生物學(xué)、自然語言或其他的復(fù)雜系統(tǒng)。同樣命題回歸方法和回歸樹方法也都有其相應(yīng)的局限。

為克服決策樹因為語言表示帶來的局限，SCART將分類樹和回歸樹這兩種統(tǒng)計學(xué)的方法引入到多關(guān)系學(xué)習(xí)領(lǐng)域，它是命題學(xué)習(xí)方法CART的拓展，SCART能夠直接從多關(guān)系數(shù)據(jù)表中發(fā)現(xiàn)知識且能方便地使用背景知識。SCART系統(tǒng)構(gòu)建了一棵樹，這棵樹的每一個節(jié)點包含一個文字（原子文字）或者文字的合取，并為每個葉子節(jié)點賦予一個離散值或數(shù)據(jù)值。受CART剪枝方法的啟發(fā)，SCART還在葉子節(jié)點中加入了線性回歸模型以提高其性能[4]。

實驗顯示SCART的預(yù)測準(zhǔn)確率與其他命題方法不相上下，這顯示關(guān)系分類回歸方法既能提高規(guī)則的可理解性又不會降低預(yù)測的準(zhǔn)確性。關(guān)系決策樹歸納方法是MRDM方法中最快的方法之一[4]，它已經(jīng)被成功地用來解決許多實際問題，如化學(xué)化合物的生物降解能力的預(yù)測等。

3．2關(guān)系關(guān)聯(lián)規(guī)則方法

WARMR是APRIORI（流行的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法）的多關(guān)系變體，兩者發(fā)現(xiàn)頻繁項集的方法和概化候選查詢的方法不同。WARMR默認(rèn)數(shù)據(jù)庫是關(guān)系數(shù)據(jù)庫，模式的類型是SQL查詢，一個模式或查詢匹配數(shù)據(jù)庫是指查詢返回元組不為空。在實際的查詢中，WARMR用Prolog來表示數(shù)據(jù)和模式，如果在程序中查詢成功則證明模式匹配數(shù)據(jù)庫。Prolog形式體系允許在模式中使用變量和多關(guān)系，這極大地擴(kuò)展了模式的表達(dá)能力。Warmode[5]是一種定義聲明偏置的形式化體系，WARMR由它來限定搜索空間大小并指定下一步要使用的Prolog查詢?？傊o定數(shù)據(jù)庫WARMR找出頻繁成功的Prolog查詢（以用戶定義的語言表示），這些查詢接下來或者被表示成多關(guān)系關(guān)聯(lián)規(guī)則，或者形成可信度和置信度均大于用戶定義閾值的查詢擴(kuò)展。

WARMR有極好的靈活性，它通過語言偏置來確定發(fā)現(xiàn)任務(wù)的類型，根據(jù)不同的語言偏置，不改變WARMR的實現(xiàn)。WARMR可以應(yīng)用到不同的發(fā)現(xiàn)任務(wù)中，這些任務(wù)包括在事件序列中發(fā)現(xiàn)片段、從交易序列中搜索序列模式以及更復(fù)雜的其他新任務(wù)。此外，一旦實驗聚焦于某一特定環(huán)境，效率問題可通過重新組織數(shù)據(jù)到某特定形式來提高。另一方面，基于特定任務(wù)開發(fā)的挖掘算法可以通過與WARMR比較來驗證其有效性，一般而言，這些算法在與WARMR產(chǎn)生同樣的輸出時效率應(yīng)該更高。

3．3基于距離的關(guān)系方法

在數(shù)據(jù)挖掘領(lǐng)域中基于距離的方法假定問題域內(nèi)對象間的相互距離是可計算的，使用基于距離的方法，許多數(shù)據(jù)挖掘任務(wù)能夠以一種簡單而有效的方法來解決。擴(kuò)展基于距離的方法到多關(guān)系情況下，距離概念的擴(kuò)展至關(guān)重要，Emde和Wett－schereck在系統(tǒng)RIBL中提出了一種多關(guān)系距離的定義方法[6]，這種距離的定義能夠馬上在最近鄰分類和層次聚類算法等標(biāo)準(zhǔn)的統(tǒng)計學(xué)方法中應(yīng)用。最初的RIBL是為解決分類問題提出的，RIBL2擴(kuò)展了RIBL的距離定義，它將列表和項作為基本類型，RIBL2已經(jīng)在預(yù)測mRNA信號結(jié)構(gòu)中應(yīng)用。此外，兩個使用RIBL距離定義的分類算法已經(jīng)形成，分別是RDBC和FORC。RDBC使用層次聚類，而FORC采用K均值方法。

RIBL中的多關(guān)系距離定義并不是標(biāo)準(zhǔn)方法（Metric），最近有些文獻(xiàn)提出了一些關(guān)系距離的標(biāo)準(zhǔn)定義方法[16]。雖然已有不少研究成果，但是設(shè)計關(guān)系距離測度仍然是值得深入研究的領(lǐng)域。因為距離和核是緊密相關(guān)的，所以這個研究點與結(jié)構(gòu)化數(shù)據(jù)的核定義也是緊密關(guān)聯(lián)的。但考慮到可伸縮性，基于距離的方法有很多問題需要考慮。

（1）基于實例的學(xué)習(xí)方法在分類之前必須存儲所有的實例（對于優(yōu)化的方法而言也要預(yù)先存放大多數(shù)實例），這要求有巨大的存儲空間。

（2）關(guān)系對象間距離的計算并不像計算歐幾里德距離那么簡單，而且只有要分類時才計算距離，所以不適合于要求較高分類速度的任務(wù)。

（3）對于聚類算法不計算精確的聚類中心，K均值方法的收斂速度太慢?，F(xiàn)有的三種多關(guān)系方法（RIBL2，RDBC，F(xiàn)ORC）僅適合應(yīng)用到含有數(shù)千實例的問題域中，因此要在大規(guī)模數(shù)據(jù)集中應(yīng)用還需要更多的研究。

3．4擴(kuò)展命題學(xué)習(xí)系統(tǒng)到關(guān)系學(xué)習(xí)系統(tǒng)的一般方法

MRDM/ILP方法與命題學(xué)習(xí)方法在很多方面是一致的，特別是它們都在給定的數(shù)據(jù)集上搜尋有效的模式，即它們都將學(xué)習(xí)問題看作是搜索問題。最關(guān)鍵的不同在于數(shù)據(jù)和模式的表示、求精算子/概化關(guān)系、覆蓋測試的不同。得到MRDM系統(tǒng)的方法有多種，可以直接從邏輯原理得到（如PROGOL）；也可以像前面所提到幾類學(xué)習(xí)系統(tǒng)一樣通過擴(kuò)展原有的命題挖掘方法得到。VanLaer和DeRaedt明確給出了提升命題算法來處理多關(guān)系數(shù)據(jù)和模式的方法，其基本思想是保持命題算法的大部分不變，然后用一階謂詞來表示實例和背景知識，采用Prolog表示假設(shè)，使用θ包含搜索假設(shè)空間，引入一個新的聲明偏置或重復(fù)利用原系統(tǒng)的聲明偏置。其中最關(guān)鍵的是要更新關(guān)鍵概念，例如對于規(guī)則歸納，關(guān)鍵的概念是求精算子和覆蓋關(guān)系；對于基于距離的方法，關(guān)鍵的概念是距離。擴(kuò)展命題學(xué)習(xí)系統(tǒng)到關(guān)系學(xué)習(xí)系統(tǒng)的一般步驟如下：

（1）選擇最適合學(xué)習(xí)任務(wù)的命題學(xué)習(xí)系統(tǒng)

這一步的主要任務(wù)是仔細(xì)研究問題域，選擇最適合問題域的命題學(xué)習(xí)系統(tǒng)。接下來就需要擴(kuò)展命題數(shù)據(jù)挖掘方法到多關(guān)系數(shù)據(jù)挖掘方法。

（2）用解釋表示例子（用一階謂詞表示輸入）

這一步中不僅例子被擴(kuò)展為一階邏輯表示，問題域的背景知識也可以用Prolog形成。背景知識可以以各種形式存在，提取特殊值到一個類或區(qū)間中；從存在屬性的合取中抽取新的屬性；概括或聚合幾個事實或元組的值為一個值。

（3）用一階文字替換屬性—值測試并且修改覆蓋測試來擴(kuò)展輸出假設(shè)為關(guān)系表示（關(guān)系化輸出假設(shè)）

學(xué)習(xí)器的輸入部分（例子和背景知識）已經(jīng)被擴(kuò)展為一階表示，接著要將學(xué)習(xí)器的輸出假設(shè)也擴(kuò)展為一階表示，這就要求將命題學(xué)習(xí)器的屬性—值測試和覆蓋測試關(guān)系化。命題形式下的屬性—值測試可以看作是文字的特例，因此可以用文字（可能帶有不止一個變元）代替屬性—值測試，這樣最終得到的假設(shè)就是一階謂詞形式的。為使覆蓋測試可以處理一階謂詞表示的實例，需要修改句法和語法假設(shè)。修改以后，就可以在一階情況下進(jìn)行覆蓋測試。當(dāng)然，一階情況下的覆蓋測試在時間和空間上都比命題方法更復(fù)雜。

（4）用θ包含作為概化框架來構(gòu)建搜索空間

幾乎所有的符號機(jī)器學(xué)習(xí)系統(tǒng)都是通過概化關(guān)系來構(gòu)建搜索空間的。在一階情況下，概化框架相當(dāng)復(fù)雜，可以使用的概化框架有很多：θ包含、反若則命題（InverseImplication）、反向消解（InverseResolution）和逆反后承（InverseEntailment）等。不過大多數(shù)ILP系統(tǒng)使用θ包含。這是因為θ包含具有極好的計算性質(zhì)（反若則命題和反向消解均很難計算而且也很難理解）；θ包含是工作在單個子句層次上的，而不是工作在子句集合上（反向消解則是工作在子句集合上的）[7]，這點與命題系統(tǒng)相似。當(dāng)然當(dāng)學(xué)習(xí)遞歸子句或多謂詞時工作在單個子句層次上或許是有局限性的，不過，在關(guān)系機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域中大多數(shù)實際的應(yīng)用并不包含遞歸規(guī)律。

（5）改造搜索算子

已經(jīng)選擇了概化框架，還需要定義搜索規(guī)則空間的算子，在此可以使用與θ包含概化框架一致的搜索算子。命題情況下典型的特化搜索算子是加一個條件到規(guī)則中。θ包含時，一個條件可以通過兩種方法被加入到子句中，即加入一個文字或者對子句應(yīng)用一個置換。典型的命題概化算子是刪除或釋放規(guī)則中的一個條件，使用θ包含有兩種方法釋放一個子句：刪除一個文字或?qū)ψ泳鋺?yīng)用一個逆向的置換。刪除一個文字是很容易的，但將規(guī)則中的常量概化為變量時就變得相當(dāng)復(fù)雜了。如果實例或項僅被概化一次，只需將實例概化成子句中沒有出現(xiàn)過的變量；如果實例的概化發(fā)生多次，概化就會變得相當(dāng)復(fù)雜。這種概化復(fù)雜性可由一個合適的聲明偏置機(jī)制降低。另一種流行的概化算子是計算兩個子句的LGG（LeastGeneralGeneralization），而使用LGG算子的問題是，在最壞情況下LGG其復(fù)雜性可能會隨著例子數(shù)目指數(shù)級地增長[7]。

（6）使用聲明偏置（DeclarativeBias）限制搜索空間大小

在單關(guān)系情況下模式語言就包含大量模式，多關(guān)系時模式規(guī)模更大，所以必須通過明確的約束來限制模式空間的大小。在關(guān)系學(xué)習(xí)器中可用句法和語義偏置機(jī)制來限定搜索空間，已經(jīng)存在各種限制搜索空間大小的形式化方法[2]，但其基本思想是一致的，都是要限制子句數(shù)量。最直接的方法是限制變量的數(shù)目或子句的文字?jǐn)?shù)目，還可以給出子句的句法限制或用語法規(guī)則說明可接受子句的范圍，也可以通過模式聲明指定子句如何求精。

（7）實現(xiàn)算法

必須要修改的地方前面幾步大都已經(jīng)提到，接下來就是要實現(xiàn)修改后的算法。實現(xiàn)時，原來算法的特征要盡可能多地保留下來，如搜索策略、啟發(fā)式策略、噪聲處理方法、剪枝方法和參數(shù)的設(shè)定等要盡量與原來保持一致。當(dāng)然，一些命題學(xué)習(xí)器特有的方法必須被改變，如命題表示下的數(shù)值屬性的離散化方法不可能直接匹配到一階表示方法中，所以必須修改。

（8）在命題和多關(guān)系數(shù)據(jù)集上評價新系統(tǒng)

①在一個命題問題上測試實施，得到的結(jié)果應(yīng)該與相應(yīng)的命題學(xué)習(xí)器的結(jié)果兼容，理想狀態(tài)下，結(jié)果應(yīng)該是一致的。但在現(xiàn)實情況下，實施上的細(xì)微差別、假設(shè)空間的不同等均會引起結(jié)果的不一致。

②在關(guān)系問題中（命題學(xué)習(xí)器不能學(xué)習(xí)的問題）測試實施，最好先在一些人工問題上試驗，因為人工的問題已經(jīng)存在解決方案（人工的獲得或由其他的關(guān)系分類器獲得），在這類問題上做試驗可以很好地考察系統(tǒng)性能（參數(shù)、輸出、學(xué)習(xí)行為和存在的問題等）。

③在現(xiàn)實中用運(yùn)行系統(tǒng)來考核其性能，一個較好的應(yīng)用領(lǐng)域是分子生物學(xué)領(lǐng)域。

（9）基本系統(tǒng)的擴(kuò)展

大多基本的命題系統(tǒng)均存在改進(jìn)的變體，或是加入了新的特征，或是被優(yōu)化，這些也可以在關(guān)系系統(tǒng)中實現(xiàn)。MRDM可以利用命題學(xué)習(xí)器研究的成果來優(yōu)化或特化基本的關(guān)系系統(tǒng)，使其性能更好或更適合一些特定的領(lǐng)域。

至此，就可以將一個命題學(xué)習(xí)器擴(kuò)展為關(guān)系學(xué)習(xí)器。當(dāng)然這種擴(kuò)展并不容易，例如前面提到的定義多關(guān)系數(shù)據(jù)情況下的距離測度的方法就需要相當(dāng)強(qiáng)的洞察力和創(chuàng)造力。效率也是要考慮的重要因素，因為只是關(guān)系模式的評估就具有相當(dāng)高的計算復(fù)雜性，更不必說是在關(guān)系空間中搜索有效的模式了。

關(guān)系學(xué)習(xí)系統(tǒng)迄今為止應(yīng)用最成功的要數(shù)Golem，PROGOL和PPROGOL(ALEPH)[9]，它們能夠被成功地應(yīng)用很大程度上得益于它們將新知識融入學(xué)習(xí)過程的靈活性，系統(tǒng)開發(fā)者與領(lǐng)域?qū)＜抑g的良好合作更是不可缺少的。

4結(jié)論

越來越多的數(shù)據(jù)挖掘應(yīng)用需要對復(fù)雜的結(jié)構(gòu)化類型的數(shù)據(jù)（如基因序列的分析、HTML和XML文檔的分析等）進(jìn)行分析，這就要求使用具有更強(qiáng)表達(dá)能力的模式語言；此外，很多實際應(yīng)用問題原來基于屬性—值的命題學(xué)習(xí)方法根本沒法解決，所有這些都促進(jìn)了MRDM的發(fā)展。目前大多數(shù)MRDM方法都是借鑒ILP技術(shù)形成的，這樣的系統(tǒng)有很多優(yōu)勢：可以擴(kuò)展對數(shù)據(jù)和模型的表示能力，直接處理多表數(shù)據(jù)集，而且MRDM的表示方法與關(guān)系數(shù)據(jù)庫的標(biāo)準(zhǔn)表示方法（以及SQL查詢語言）是完全對應(yīng)的，這使得定義數(shù)據(jù)庫和挖掘算法間的接口相對容易，而不必在數(shù)據(jù)庫模式與學(xué)習(xí)算法之間附加中間的數(shù)據(jù)表示層；MRDM提供了表示和使用背景知識的良好機(jī)制，它也可以使用很多技術(shù)實現(xiàn)學(xué)習(xí)模型前的特征抽取工作；MRDM方法獲得的模式一般都是用符號表示的，很容易為人們所理解；MRDM可以很好地支持演繹數(shù)據(jù)庫。

MRDM方法的出現(xiàn)為KDD的發(fā)展帶來了新的活力，但多關(guān)系數(shù)據(jù)挖掘也存在巨大的挑戰(zhàn)：①效率問題。使用一階謂詞邏輯語言作為模式表示語言使得MRDM系統(tǒng)擁有龐大的搜索空間，而且相關(guān)算法的計算代價也相當(dāng)高，因此只有盡力減少數(shù)據(jù)掃描次數(shù)并努力提高計算效率，MRDM才能在實際中得到充分的應(yīng)用。目前常見的提高M(jìn)RDM效率的方法有兩個，即使用背景知識限制搜索空間大小和采用抽樣方法。②不確定性的表示和處理。需要將概率技術(shù)引入到多關(guān)系領(lǐng)域中，概率關(guān)系模型（PRMs）是解決這個問題的方法之一。

參考文獻(xiàn)：

［1］SDzeroski，NLavrac.RelationalDataMining[M].Berlin:Springer，2001.

［2］SWrobel.InductiveLogicProgrammingforKnowledgeDiscoveryinDatabases[C].RelationalDataMining，Berlin:Springer，2001.74101.

［3］LDeRaedt，HBlockeel，LDehaspe，etal.ThreeCompanionsforDataMininginFirstOrderLogic[C].RelationalDataMining，Sprin－gerVerlag，2001.105139.

［4］SKramer，GWidmer.InducingClassificationandRegressionTreesinFirstOrderLogic[C].RelationalDataMining，SpringerVerlag，2001.140159.

［5］LDehaspe，HToivonen.DiscoveryofRelationalAssociationRules[C].RelationalDataMining，SpringerVerlag，2001.189212.

［6］MKirsten，SWrobel，THorvath.DistanceBasedApproachestoRelationalLearningandClustering[C].RelationalDataMining，Sprin－gerVerlag，2001.213232.

［7］VVanLaer，LDeRaedt.HowtoUpgradePropositionalLearnerstoFirstOrderLogic：ACaseStudy[C].RelationalDataMining，Sprin－gerVerlag，2001.235261.

［8］SKramer，NLavrac，PFlach.PropositionalizationApproachestoRelationalDataMining[C].RelationalDataMining，Springer，2001.262291.

［9］SDzeroski.RelationalDataMiningApplications：AnOverview[C].RelationalDataMining，SpringerVerlag，2001.339364.

［10］NLavrac，SDzeroski.InductiveLogicProgramming[EB/OL].EllisHorwood，Chichester.TechniquesandApplications.http：//wwwai.ijs.si/SasoDzeroski/ILPBook/，1994.

［11］LDeRaedt.AdvancesinInductiveLogicProgramming[M].Amsterdam:OSPress，1996.

［12］LDeRaedt.AttributevalueLearningVersusInductiveLogicProgramming：TheMissingLinks(ExtendedAbstract)[C].Berlin:Proceedingsofthe8thInternationalConferenceonInductiveLogicProgramming，1998.18.

［13］SDzeroski，LDeRaedt，SWrobel，etal.Proceedingsofthe1stInternationalWorkshoponMultirelationalDataMining[C].Edmonton:The8thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining，2002.

［14］IBratko.PrologProgrammingforArtificialIntelligence(3rdedition)[M].Harlow:AddisonWesley，2001.

［15］WBuntine.GeneralizedSubsumptionandItsApplicationstoInductionandRedundancy[J].ArtificialIntelligence，1988，36(2)：149176.

［16］JRamon，MBruynooghe.APolynomialTimeComputableMetricBetweenPointSets[J].ActaInformatica，2001，37(10)：765780.

［17］WFrawley，GPiatetskyShapiro，CMatheus.KnowledgeDiscoveryinDatabases：AnOverview[M].GGPiatetskyShapiro，WFrawley.KnowledgeDiscoveryinDatabases，Cambridge:MITPress，1991.127.

［18］JRQuinlan.LearningLogicalDefinitionsfromRelations[J].MachineLearning，1990，5(3)：239266.

［19］NLavrac，SDzeroski，MGrobelnik.LearningNonrecursiveDefinitionsofRelationswithLINUS[C].Berlin:Proceedingsofthe5thEuropeanWorkingSessiononLearning，1991.265281.

［20］JLloyd.FoundationsofLogicProgramming(2ndedition)[M].Berlin:Springer，1987.

［21］HMannila，HToivonen.DiscoveringGeneralizedEpisodesUsingMinimalOccurrences[C].Proceedingsofthe2ndInternationalConferenceonKnowledgeDiscoveryandDataMining，MenloPark:AAAIPress，1996.146151.

［22］SNijssen，JKok.FasterAssociationRulesforMultipleRelations[C].The17thInternationalJointConferenceonArtificialIntelligence，2001.891896.

［23］KnobbeJ，BlockeelH，SiebesA，etal.MultiRelationalDataMi－ning[C].ProceedingsofBenelearn’99，1999.

［24］KnobbeJ，SiebesA，VanderWallen，etal.MultiRelationalDecisionTreeInduction[C].Proceedingsofthe3rdEuropeanConferenceonPrinciplesandPracticeofKnowledgeDiscoveryinDatabases，PKDD’99，1999.

［25］BlockeelH，DeRaedtL.RelationalKnowledgeDiscoveryinDatabases[C].Proceedingsofthe6thInternationalWorkshoponInductiveLogicProgramming，volume1314ofLectureNotesinArtificialIntelligence，SpringerVerlag，1996.199211.

［26］AInokuchi，TWashio，HMotoda.CompleteMiningofFrequentPatternsfromGraphs：MiningGraphData[J].MachineLearning，2003，50(3)：321354.

［27］RMichalski，IMozetic，JHong，etal.TheMultipurposeIncrementalLearningSystemAQ15andItsTestingApplicationonThreeMedicalDomains[C].Proceedingsofthe5thNationalConferenceonArtificialIntelligence，SanMateo:MorganKaufmann，1986.10411045.

［28］ESegal，YBarash，ISimon，etal.FromPromoterSequencetoExpression：AProbabilisticFramework[C].Washington，DC:Procee－dingsofthe6thInternationalConferenceonResearchinComputatio－nalMolecularBiology(RECOMB02)，2002.263273.

［29］ESegal，ABattle，DKoller.DecomposingGeneExpressionintoCellularProcesses[A].RBAltman，AKDunker，LHunter，etal.ProceedingsofthePacificSymposiumonBiocomputing[M].Kauai:WorldScientific，2003.89100.

［30］SMuggleton.InductiveLogicProgramming[J].NewGenerationComputing，1991，8(4)：295318.

［31］SMuggleton.InductiveLogicProgramming[M].London:AcademicPress，1992.

［32］SMuggleton.InverseEntailmentandProgol[J].NewGenerationComputing，1995，13(34)：245286.

［33］SMuggleton，CFeng.EfficientInductionofLogicPrograms[C].Ohmsha:Proceedingsofthe1stConferenceonAlgorithmicLearningTheory，1990.368381.

［34］CNedellec，CRouveirol，HAde，etal.DeclarativeBiasinInductiveLogicProgramming[A].LDeRaedt.AdvancesinInductiveLogicProgramming[M].，Amsterdam:IOSPress，1996.82103.

［35］TNiblett.AStudyofGeneralizationinLogicPrograms[C].Pitman:Proceedingsofthe3rdEuropeanWorkingSessiononLearning，1988.131138.

［36］SHNienhuysCheng，RdeWolf.FoundationsofInductiveLogicProgramming[M].Berlin:Springer，1997.

［37］GPlotkin.ANoteonInductiveGeneralization[A].BMeltzer，DMichie.MachineIntelligence[M].Edinburgh:EdinburghUniversityPress，1969.153163.

［38］JRQuinlan.LearningLogicalDefinitionsfromRelations[J].MachineLearning，1990，5(3)：239266.

［39］JRQuinlan.C4.5：ProgramsforMachineLearning[M].SanMateo:MorganKaufmann，1993.

［40］RAgrawal，RSrikant.MiningSequentialPatterns[C].Proceedingsofthe11thInternationalConferenceonDataEngineering，LosAlamitos:IEEEComputerSocietyPress，1995.314.

［41］RAgrawal，HMannila，RSrikant，etal.FastDiscoveryofAssociationRules[A].UFayyad，GPiatetskyShapiro，PSmyth，etal.AdvancesinKnowledgeDiscoveryandDataMining[M].MenloPark:AAAIPress，1996.307328.

［42］HBlockeel，LDeRaedt.TopdownInductionofFirstOrderLogicalDecisionTrees[J].ArtificialIntelligence，1998，101(12)：285297.

［43］IBratko.PrologProgrammingforArtificialIntelligence(3rdedition)[M].Harlow:AddisonWesley，2001.

［44］LBreiman，JHFriedman，RAOlshen，etal.ClassificationandRegressionTrees[M].Belmont:Wadsworth，1984.

［45］PClark，RBoswell.RuleInductionwithCN2：SomeRecentImprovements[C].Proceedingsofthe5thEuropeanWorkingSessiononLearning，Berlin:Springer，1991.151163.

［46］PClark，TNiblett.TheCN2InductionAlgorithm[J].MachineLearning，1989，3(4)：261283.

［47］LDehaspe，HToivonen，RDKing.FindingFrequentSubstructuresinChemicalCompounds[C].Proceedingsofthe4thInternationalConferenceonKnowledgeDiscoveryandDataMining，MenloPark:AAAIPress，1998.3036.

［48］LDehaspe，HToivonen.DiscoveryofFrequentDatalogPatterns[J].DataMiningandKnowledgeDiscovery，1999，3(1)：736.

［49］LDeRaedt，SDzeroski.FirstOrderJkclausalTheoriesarePAClearnable[J].ArtificialIntelligence，1994，70(12)：375392.

［50］SDzeroski，SMuggleton，SRussell.PAClearnAbilityofDeterminateLogicPrograms[C].Proceedingsofthe5thACMWorkshoponComputationalLearningTheory，NewYork:ACMPress，1992.128135.

［51］SDzeroski，SSchulzeKremer，KHeidtke，etal.DiterpeneStructureElucidationfrom13CNMRSpectrawithInductiveLogicProgramming[J].AppliedArtificialIntelligence，1998，12：363383.

［52］SDzeroski，HBlockeel，BKompare，etal.ExperimentsinPredictingBiodegradability[C].Proceedingsofthe9thInternationalWorkshoponInductiveLogicProgramming，Berlin:Springer，1999.8091.

作者簡介：

徐光美（1977），女，山東人，博士研究生，主要研究方向為數(shù)據(jù)挖掘；

楊炳儒(1943)，男，天津人，教授，博導(dǎo)，主要研究方向為知識發(fā)現(xiàn)與推理機(jī)制、柔性建模與系統(tǒng)集成；

張偉（1974），男，山東人，博士研究生，主要研究方向為數(shù)據(jù)挖掘、數(shù)據(jù)庫；

寧淑榮（1976），女，山西人，博士研究生，主要研究方向為人工智能。