探究鏈接在多關系數(shù)據(jù)挖掘中的應用

涂芳 曾銘 鄧左祥

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

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

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

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

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

2 鏈接存在于多關系之中

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

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

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

3 鏈接在多關系數(shù)據(jù)挖掘中的應用

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

3.1 CrossMine：一種有效的在多關系中分類的算法

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

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

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

3.2 Graph-NB：一個有效、準確的多關系貝葉斯分類算法

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

3.3 CrossClus：一種在用戶指導下的多關系聚類算法

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

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

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

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

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

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

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

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

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

對象識別與一個比較流行的問題類似，就是對象一致問題，也叫副本探測問題，它的目標是把涉及相同對象卻命名不同的記錄合并起來，比如，找出涉及同一個論文的不同引用名稱。但是，和對象一致問題相比較，對象識別又是一個不同的問題，在對象識別問題中，因為同名對象具有相同的名字，所以不能通過名字來計算同名對象之間的相似度。但是，在對象一致問題中，由于對象的命名不同，因此可以通過名字來計算對象之間的相似度。

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

結語

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