涂芳 曾銘 鄧左祥

1.上汽通用五菱汽車股份有限公司 廣西柳州 545007；2.湖南湖大艾盛汽車技術(shù)開發(fā)有限公司 湖南長沙 410221；3.廣西科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 廣西柳州 545006

1 多關(guān)系數(shù)據(jù)挖掘概述

隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展和進(jìn)步，人類社會(huì)已經(jīng)進(jìn)入大數(shù)據(jù)時(shí)代[1]，數(shù)據(jù)在關(guān)系數(shù)據(jù)庫中的存儲(chǔ)，通常以多關(guān)系，也就是多表的形式來存儲(chǔ)。多關(guān)系數(shù)據(jù)挖掘[2]，是在關(guān)系數(shù)據(jù)庫中相互關(guān)聯(lián)的多張表(也就是關(guān)系)上，進(jìn)行知識(shí)學(xué)習(xí)。

對于多關(guān)系進(jìn)行數(shù)據(jù)挖掘來說，一個(gè)傳統(tǒng)方法，就是把多張表集成到一張表中，然后運(yùn)用傳統(tǒng)的數(shù)據(jù)挖掘算法，對集成后的表進(jìn)行挖掘。但是在實(shí)踐中，這種傳統(tǒng)方法，存在著很多問題。這種傳統(tǒng)方法，不但需要大量的計(jì)算，而且有可能丟失數(shù)據(jù)原有的結(jié)構(gòu)特點(diǎn)，造成信息丟失，使得效率、可擴(kuò)展性都很差。因此，有必要尋找一種直接在多關(guān)系上進(jìn)行挖掘的算法，對可以直接在多關(guān)系上進(jìn)行數(shù)據(jù)挖掘的算法進(jìn)行研究，是一個(gè)值得研究的問題，當(dāng)然也會(huì)面臨一些挑戰(zhàn)。多關(guān)系數(shù)據(jù)挖掘的算法，可以減少多關(guān)系數(shù)據(jù)挖掘所需要的時(shí)間和空間，能夠增大效率并具有可擴(kuò)展性。

多關(guān)系數(shù)據(jù)挖掘的任務(wù)，主要包括在多關(guān)系上進(jìn)行分類、在多關(guān)系上進(jìn)行聚類、在多關(guān)系上進(jìn)行關(guān)聯(lián)規(guī)則挖掘。多關(guān)系分類，是一個(gè)在多關(guān)系中，進(jìn)行分類的過程，它基于存儲(chǔ)在多關(guān)系中的信息，并且還可以進(jìn)行預(yù)測。在多關(guān)系分類中，有一個(gè)目標(biāo)關(guān)系，它的元組稱為目標(biāo)元組，它們都有一個(gè)類標(biāo)簽，如果假設(shè)有兩個(gè)類，則可以把一個(gè)類稱為正類，另一個(gè)類稱為負(fù)類。多關(guān)系分類，就是在可以與目標(biāo)關(guān)系進(jìn)行連接操作的關(guān)系中，根據(jù)目標(biāo)關(guān)系中元組的正負(fù)類，來區(qū)別出關(guān)系中正類的元組和負(fù)類的元組。多關(guān)系聚類，就是使用多關(guān)系中數(shù)據(jù)的信息，根據(jù)它們之間的相似度，來把數(shù)據(jù)對象劃分成一系列簇的過程。多關(guān)系關(guān)聯(lián)規(guī)則挖掘，它的目標(biāo)是發(fā)現(xiàn)存在于不同關(guān)系中相互關(guān)聯(lián)的項(xiàng)的模式，進(jìn)而可以產(chǎn)生多關(guān)系關(guān)聯(lián)規(guī)則。

2 鏈接存在于多關(guān)系之中

鏈接在互聯(lián)網(wǎng)有著巨大的作用?；ヂ?lián)網(wǎng)上的網(wǎng)頁，通過鏈接，互相關(guān)聯(lián)在一起，對于數(shù)據(jù)挖掘來說，鏈接同樣有著重要的作用，比如多關(guān)系數(shù)據(jù)挖掘。

關(guān)系數(shù)據(jù)庫是最流行的結(jié)構(gòu)數(shù)據(jù)的貯存器。在關(guān)系數(shù)據(jù)庫中，多關(guān)系通過實(shí)體——關(guān)系模型相互鏈接在一起。在多關(guān)系中，每個(gè)關(guān)系和每個(gè)關(guān)系之間主鍵和外鍵的對應(yīng)，就是多關(guān)系中鏈接的表現(xiàn)形式之一。如果多關(guān)系數(shù)據(jù)庫中的兩個(gè)關(guān)系，可以通過數(shù)據(jù)庫中物理連接的操作，連接在一起，則這個(gè)關(guān)系就存在鏈接。

許多分類方法(比如神經(jīng)網(wǎng)絡(luò)和支持向量機(jī))，僅僅能夠運(yùn)用在單關(guān)系表格中，也就是說，數(shù)據(jù)存儲(chǔ)在一個(gè)獨(dú)立的表格。然而，在現(xiàn)實(shí)世界中，多關(guān)系數(shù)據(jù)是普遍和大量存在的。有效地運(yùn)用多關(guān)系之間的鏈接，可以實(shí)現(xiàn)多關(guān)系數(shù)據(jù)挖掘，也就是直接在多關(guān)系之中進(jìn)行挖掘，提高挖掘的準(zhǔn)確率和效率。

3 鏈接在多關(guān)系數(shù)據(jù)挖掘中的應(yīng)用

有效地利用多關(guān)系中的鏈接，可以解決多關(guān)系數(shù)據(jù)挖掘的問題，直接從多關(guān)系中挖掘知識(shí)，節(jié)省時(shí)間和空間，提高準(zhǔn)確率、可擴(kuò)展性。一些研究學(xué)者，巧妙地利用多關(guān)系中的鏈接，已經(jīng)提出一些高效的多關(guān)系數(shù)據(jù)挖掘算法。本小節(jié)，通過描述一些多關(guān)系數(shù)據(jù)挖掘的研究成果，來探究鏈接在多關(guān)系數(shù)據(jù)挖掘中的應(yīng)用，包括五個(gè)研究成果，分別是：CrossMine[3]、Graph-NB[4]、CrossClus[5]、LinkClus[6]、Distinct[7]。

3.1 CrossMine：一種有效的在多關(guān)系中分類的算法

傳統(tǒng)的方法，在處理多關(guān)系分類時(shí)，采取物理連接多關(guān)系的方法，例如ILP分類方法。ILP把FOIL作為它的分類算法，為了實(shí)現(xiàn)分類，F(xiàn)OIL需要?jiǎng)?chuàng)建一個(gè)個(gè)規(guī)則，每個(gè)規(guī)則都包含一個(gè)個(gè)謂詞，F(xiàn)OIL通過評估每個(gè)謂詞的好壞，在現(xiàn)有的規(guī)則中，加入最好的謂詞。在這種情況下，需要一個(gè)估計(jì)謂詞的方法，可以用Foil Gain來估計(jì)每一個(gè)謂詞。擁有最大Foil Gain的謂詞，就是最好的謂詞。但是，ILP采用對關(guān)系進(jìn)行物理連接的方法，來計(jì)算出Foil Gain，這就會(huì)造成耗時(shí)大的問題。

CrossMine是一種有效的在多關(guān)系中分類的算法。與ILP類似，CrossMine也同樣要一次一個(gè)地把謂詞加進(jìn)規(guī)則里去，也要計(jì)算出Foil Gain，以找出最好的謂詞。但是，與ILP不同的是，CrossMine不用直接對表進(jìn)行連接，就可以計(jì)算出Foil Gain，它采取的是一種基于多關(guān)系之間鏈接的元組ID傳播的方法。在一般情況下，多關(guān)系數(shù)據(jù)庫的目標(biāo)關(guān)系中的主鍵，代表每個(gè)目標(biāo)元組的ID。CrossMine使用元組ID傳播的方法，在所有活動(dòng)的關(guān)系中(初始情況下，只有目標(biāo)關(guān)系是活動(dòng)關(guān)系)，以及那些可以與活動(dòng)關(guān)系進(jìn)行物理連接的關(guān)系中，尋找擁有最大Foil Gain的謂詞。

算法FOIL和CrossMine大體上類似，所不同的是，F(xiàn)OIL采用物理連接，CrossMine采用基于多關(guān)系之間鏈接的元組ID傳播。因此，CrossMine在時(shí)間和空間上的花費(fèi)，都比物理連接的FOIL少很多，對于準(zhǔn)確率、效率、可擴(kuò)展性來說，CrossMine也比FOIL要更高。

3.2 Graph-NB：一個(gè)有效、準(zhǔn)確的多關(guān)系貝葉斯分類算法

Graph-NB是一個(gè)有效、準(zhǔn)確的多關(guān)系貝葉斯分類算法。第一，它可以直接地處理多關(guān)系，也就是說，并不需要對關(guān)系進(jìn)行連接操作，就可以分類，節(jié)省時(shí)間和空間。而現(xiàn)有的其他貝葉斯分類法在處理多關(guān)系時(shí)，都必須先對關(guān)系進(jìn)行物理連接，相比之下，Graph-NB避免物理連接，代價(jià)較低。第二，為了充分利用表格之間的鏈接，并且有區(qū)別的對待鏈接到目標(biāo)關(guān)系的不同表，建立一個(gè)語義關(guān)系圖，用來描述關(guān)系，以及避免關(guān)系和關(guān)系之間不必要的連接操作。第三，為了優(yōu)化語義挖掘，使得可以停止一些無用的挖掘，可以對語義關(guān)系圖，采取裁減策略。語義關(guān)系圖是一個(gè)無環(huán)圖(V，E，W)，V代表頂點(diǎn)，每個(gè)頂點(diǎn)對應(yīng)于一個(gè)表，E代表邊，而W代表兩個(gè)表之間的連接屬性。

3.3 CrossClus：一種在用戶指導(dǎo)下的多關(guān)系聚類算法

在多關(guān)系聚類中，傳統(tǒng)的方法，在計(jì)算兩個(gè)對象的相似度時(shí)，是根據(jù)可以與它們進(jìn)行連接操作的元組來判斷的。然而，這種方法有兩個(gè)問題。第一，它根據(jù)連接元組來計(jì)算相似度，因?yàn)橐粋€(gè)多關(guān)系中可以連接的元組通常很多，所以計(jì)算它們代價(jià)是很大的。第二，在一個(gè)數(shù)據(jù)庫中，通常有許許多多的屬性，它們覆蓋許多不同方面的信息，但是僅僅有一小部分是和用戶聚類任務(wù)有關(guān)的，使用這個(gè)方法進(jìn)行聚類的話，所有的屬性都會(huì)不加區(qū)分，這樣子就不太可能產(chǎn)生用戶希望得到的聚類結(jié)果。雖然以上問題，可以通過用戶半指導(dǎo)聚類的方法來解決，但是這個(gè)方法也有不足。因?yàn)檫@個(gè)方法，通常需要用戶擁有比較豐富的知識(shí)，能夠提供高質(zhì)量的測試集，然而，多關(guān)系數(shù)據(jù)的復(fù)雜性，使得用戶有時(shí)候很難提供它。

CrossClus可以解決上述問題。它只需要用戶提供聚類的任務(wù)，包括聚類的目標(biāo)關(guān)系，以及一個(gè)或者多個(gè)指定屬性。在用戶指定聚類任務(wù)后，CrossClus搜尋一些相關(guān)屬性，這些相關(guān)屬性，是與用戶指定的屬性有關(guān)聯(lián)的屬性。在搜尋相關(guān)屬性的過程中，CrossClus使用啟發(fā)式算法，在這種情況下，需要確定哪些屬性是相關(guān)屬性，相關(guān)屬性的選擇，是基于用戶指定屬性的。從根本上說，如果兩個(gè)屬性聚類元組的方式非常不同，則它們的相似性就低，而且不太可能相關(guān)，反過來，如果聚類的方式相似，它們相似性就會(huì)高，就有可能相關(guān)。所以，要找出相關(guān)屬性，就要找出與用戶指定屬性具有一定相似度的屬性。因此，需要一種計(jì)算方法，來計(jì)算相似度，相似度是用戶指導(dǎo)的屬性和其他屬性之間的相關(guān)屬性?？傊?，為了達(dá)到聚類的目的，CrossClus最終選擇的是一系列具有高相關(guān)，但是卻不冗余的屬性。

Crossclus使用相似向量，來計(jì)算屬性之間的相似度。在找相關(guān)屬性的過程中，為了找到所有可以與目標(biāo)關(guān)系的元組進(jìn)行連接關(guān)系的元組，CrossClus采用元組ID傳播的方法，運(yùn)用多關(guān)系之間的鏈接，進(jìn)行虛連接，節(jié)省時(shí)間和空間。

3.4 LinkClus：一種運(yùn)用多樣的語義鏈接的有效聚類算法

在進(jìn)行多關(guān)系聚類時(shí)，傳統(tǒng)的方法，在計(jì)算相似度時(shí)，需要計(jì)算兩兩對象之間的相似度。在這個(gè)方法中，兩個(gè)對象的相似度，遞歸的定義為鏈接到這兩個(gè)對象的所有對象之間，兩兩相似度的平均值。比如說，如果需要計(jì)算兩個(gè)研究學(xué)者的相似度，假設(shè)他們都在某些會(huì)議上發(fā)表過論文，那么，這兩個(gè)研究學(xué)者的相似度，可以用這些會(huì)議之間，兩兩相似度的平均值來計(jì)算。雖然這個(gè)傳統(tǒng)方法很有用，但是它的代價(jià)是很高的。不管是什么對象，它都迭代的計(jì)算兩兩對象之間的相似度，無論在空間上和時(shí)間上，時(shí)間復(fù)雜度和空間復(fù)雜度都很大。

為了減小多關(guān)系聚類的時(shí)間復(fù)雜度和空間復(fù)雜度，實(shí)現(xiàn)高質(zhì)量的聚類，Linkclus設(shè)計(jì)出一種樹形的數(shù)據(jù)結(jié)構(gòu)Simtree，以多粒度的方式來存儲(chǔ)相似度，可以用來存儲(chǔ)和計(jì)算對象之間的相似度。它是一種通過鏈接來計(jì)算相似度的方法，通過存儲(chǔ)比較有意義的相似度，壓縮一些沒有意義的相似度，有效地節(jié)省空間和時(shí)間。

在Simtree中，不需要計(jì)算兩兩對象之間的相似度，只需要計(jì)算一部分對象之間的相似度，節(jié)省空間和時(shí)間。雖然只計(jì)算一部分對象之間的相似度，但是任意兩兩對象之間的相似度，依然可以通過樹形結(jié)構(gòu)Simtree中的鏈接得到。Simtree構(gòu)造樹形結(jié)構(gòu)的思想，來源于現(xiàn)實(shí)生活，現(xiàn)實(shí)生活中，許多對象的等級結(jié)構(gòu)，是自然存在的。比如，動(dòng)植物的等級結(jié)構(gòu)，或者商品的等級結(jié)構(gòu)等。在某些超市中就存在商品的等級結(jié)構(gòu)，比如全部的商品，包括食品、電器和服裝等，而電器又包括電視、冰箱、洗衣機(jī)等，更進(jìn)一步，電視又包括各種各樣品牌的電視。如果用Simtree來表示沃爾瑪超市的商品，則需要計(jì)算冰箱和電視的總體相似度，以及每個(gè)冰箱和每個(gè)冰箱之間的相似度，但是每個(gè)冰箱和每個(gè)電視的相似度，就不再需要計(jì)算，因?yàn)樗梢酝ㄟ^上述兩個(gè)相似度推導(dǎo)得到。

3.5 Distinct：一種在多關(guān)系中區(qū)別同名對象的對象識(shí)別算法

在現(xiàn)實(shí)世界中，許多對象有可能有著相同的名字，如果不區(qū)別這些同名，可能會(huì)造成一些迷惑和誤解。比如，在計(jì)算機(jī)領(lǐng)域的論文數(shù)據(jù)庫DBLP中，就有許多同名作者，但是實(shí)際上不是同一個(gè)人，只是同名同姓。區(qū)別同名對象是一個(gè)重要的工作，Distinct是一種在多關(guān)系中區(qū)別同名對象的對象識(shí)別算法，它可以用來區(qū)別同名對象，具有較高的準(zhǔn)確率。

對象識(shí)別與一個(gè)比較流行的問題類似，就是對象一致問題，也叫副本探測問題，它的目標(biāo)是把涉及相同對象卻命名不同的記錄合并起來，比如，找出涉及同一個(gè)論文的不同引用名稱。但是，和對象一致問題相比較，對象識(shí)別又是一個(gè)不同的問題，在對象識(shí)別問題中，因?yàn)橥麑ο缶哂邢嗤拿?，所以不能通過名字來計(jì)算同名對象之間的相似度。但是，在對象一致問題中，由于對象的命名不同，因此可以通過名字來計(jì)算對象之間的相似度。

由于同名對象具有相同的名字，僅僅依靠名字來區(qū)別同名對象，是不可能的，因此，需要另外一種方法來區(qū)別同名對象。在多關(guān)系中，運(yùn)用鏈接是一個(gè)非常有用的區(qū)別同名對象的手段，Distinct運(yùn)用鏈接來區(qū)分同名對象。如果兩個(gè)對象存在關(guān)聯(lián)，則這兩個(gè)對象就存在鏈接。比如，一篇論文的所有作者之間，都是存在關(guān)聯(lián)，因此存在鏈接的。一組同名對象，如果是同一個(gè)對象，它們的鏈接，通常存在相同點(diǎn)，以一個(gè)比較固定的方式存在。比如，假設(shè)兩篇論文出現(xiàn)同名作者，如果他們是同一個(gè)人，則通常會(huì)鏈接到另一個(gè)同名的共同作者，簡單地說，這兩篇論文如果出現(xiàn)兩個(gè)同名作者，則這兩個(gè)同名作者，都很大可能分別是同一個(gè)人。另一方面，如果同名對象不是同一個(gè)人，同名對象的鏈接通常也不相同。比如，假設(shè)兩篇論文出現(xiàn)同名作者，但是其他作者都不相同，這兩個(gè)同名作者，就有一定的可能，不是同一個(gè)人，只是同名同姓的兩個(gè)人。為了提高區(qū)別同名對象的準(zhǔn)確率，Distinct定義兩個(gè)對象之間鏈接的總體強(qiáng)度，定義為在一定的步數(shù)內(nèi)，從一個(gè)對象鏈接到另外一個(gè)對象的可能性。

結(jié)語

在多關(guān)系數(shù)據(jù)挖掘中，已有的一些研究成果證實(shí)，在多關(guān)系中巧妙地利用鏈接，可以研究出高效的多關(guān)系數(shù)據(jù)挖掘算法。鏈接在多關(guān)系中的作用是非常大的，可以節(jié)省空間和時(shí)間，提高準(zhǔn)確率，有很大的可擴(kuò)展性。今后，數(shù)據(jù)挖掘的研究學(xué)者，可以繼續(xù)利用多關(guān)系中的鏈接，研究其他高效的多關(guān)系數(shù)據(jù)挖掘算法。