基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)技術(shù)述評

崔家旺 李春旺

摘 要：文章通過對CLOD、KIELD等關(guān)聯(lián)數(shù)據(jù)相關(guān)會議、谷歌學術(shù)、IEEE和Springer等數(shù)據(jù)庫基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)技術(shù)文獻的調(diào)研與整理，分析和總結(jié)了基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)技術(shù)發(fā)展現(xiàn)狀和發(fā)展趨勢。研究認為：根據(jù)對關(guān)聯(lián)數(shù)據(jù)的挖掘?qū)哟蔚牟煌瑢z索結(jié)果分為間接挖掘、直接挖掘和鏈接挖掘三類；總體而言，基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)研究仍處于探索階段，相關(guān)研究較少且缺乏統(tǒng)一框架；基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)統(tǒng)一框架的構(gòu)建以及針對關(guān)聯(lián)數(shù)據(jù)知識發(fā)現(xiàn)技術(shù)的完善將是未來研究的重點。

關(guān)鍵詞：關(guān)聯(lián)數(shù)據(jù)；知識發(fā)現(xiàn)；述評

中圖分類號： G302 文獻標識碼： A DOI：10.11968/tsyqb.1003-6938.2016103

Abstract This paper discusses the current status and future directions of the related studies of knowledge discovery technology based on linked data。By Using IEEE，Springer，Google Scholar and other scholarly search engines and collects papers about this subject from related conferences，such as COLD and KIELD，this paper makes a comprehensive study in this subject of research and classifies related papers according to the different knowledge discovery methods. In general，knowledge discovery based on linked data is still in the exploratory stage. There still exists some problems in the knowledge discovery based on linked data， such as the quality problem of linked data；and there is no unified framework for those methods. Getting more convenient knowledge discovery methods based on linked data and building a unified framework for them will be the focus of future research.

Key words linked data； knowledge discovery； review

海量數(shù)據(jù)與知識貧乏導致了數(shù)據(jù)挖掘和知識發(fā)現(xiàn)研究的出現(xiàn)。知識發(fā)現(xiàn)（Knowledge Discovery）源于人工智能和機器學習，是機器學習、 人工智能、數(shù)據(jù)庫和知識庫等眾多學科相互融合而形成的一門適應性強的新興交叉學科。知識是數(shù)據(jù)元素間的關(guān)系或模式，知識發(fā)現(xiàn)就是從大量數(shù)據(jù)中，特別是從異構(gòu)的數(shù)據(jù)平臺中提取出隱含的、未知的、潛在有用的并能被人們理解的規(guī)則與模式，并檢查趨勢、發(fā)掘出事實的高級處理過程[1]。當前有關(guān)知識發(fā)現(xiàn)研究主要集中在：粗糙集理論；概念格和形式概念分析；基于分類、關(guān)聯(lián)規(guī)則、領(lǐng)域知識和圖模型等領(lǐng)域[2]。

關(guān)聯(lián)數(shù)據(jù)的發(fā)布與應用為知識發(fā)現(xiàn)提供了一個新契機，特別是關(guān)聯(lián)數(shù)據(jù)預先建立了大量權(quán)威、準確的關(guān)聯(lián)關(guān)系，每個數(shù)據(jù)對象包括多種屬性和特征，從而為實現(xiàn)跨學科領(lǐng)域、跨數(shù)據(jù)源的精準知識發(fā)現(xiàn)提供有效支撐，使得基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)成為研究熱點。

1 研究現(xiàn)狀

1.1 知識發(fā)現(xiàn)相關(guān)技術(shù)

目前的知識發(fā)現(xiàn)研究主要有兩大分支，即基于數(shù)據(jù)庫的知識發(fā)現(xiàn)與基于文獻的知識發(fā)現(xiàn)。數(shù)據(jù)庫知識發(fā)現(xiàn)主要針對結(jié)構(gòu)化數(shù)據(jù)， 基于文獻的知識發(fā)現(xiàn)主要針對非結(jié)構(gòu)化數(shù)據(jù)。知識發(fā)現(xiàn)的方法有統(tǒng)計方法、機器學習方法與神經(jīng)計算方法。統(tǒng)計方法除了回歸分析（多元回歸、自回歸等）、判別分析（貝葉斯判別、費舍爾判別、非參數(shù)判別等）、聚類分析（系統(tǒng)聚類、動態(tài)聚類等）及探索性分析（主成分分析、相關(guān)分析）等方法以外，還包括模糊集方法、支持向量機方法、粗糙集等方法。常用的機器學習方法包括規(guī)則歸納、決策樹、范例推理、遺傳算法等。常用的神經(jīng)計算方法包括自組織映射網(wǎng)絡(luò)、反傳網(wǎng)絡(luò)等[3]。

基于文獻的知識發(fā)現(xiàn)按照文獻的相關(guān)性分為基于相關(guān)文獻的知識發(fā)現(xiàn)、基于非相關(guān)文獻的知識發(fā)現(xiàn)和基于全文獻的知識發(fā)現(xiàn)[4]。由于計算機直接從非相關(guān)文獻中發(fā)現(xiàn)新知識是非常困難的，應由計算機首先把文獻中的知識單元抽取出來，構(gòu)成知識庫，然后再在知識庫里進行發(fā)現(xiàn)。語義網(wǎng)技術(shù)通過給文檔添加形式化語義信息的方式解決了計算機理解文獻的問題，而關(guān)聯(lián)數(shù)據(jù)是由W3C推薦的語義網(wǎng)最佳實踐。關(guān)聯(lián)數(shù)據(jù)將分散領(lǐng)域中的數(shù)據(jù)通過結(jié)構(gòu)化描述以及數(shù)據(jù)之間的鏈接關(guān)聯(lián)起來，形成全球巨大數(shù)據(jù)空間，即數(shù)據(jù)網(wǎng)絡(luò)。這種數(shù)據(jù)網(wǎng)絡(luò)資源環(huán)境為信息的最大限度共享、重用以及發(fā)行提供了保障，也為人們的知識發(fā)現(xiàn)活動提供了新的機遇[5]。

1.2 基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)研究進展

以“關(guān)聯(lián)數(shù)據(jù)”“知識發(fā)現(xiàn)”等為關(guān)鍵詞在CNKI數(shù)據(jù)庫中檢索發(fā)現(xiàn)，國內(nèi)基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)研究仍處于起步階段，相關(guān)研究數(shù)量較少且多屬于理論模型研究。如李楠[6]、李俊[7]等分別總結(jié)了基于關(guān)聯(lián)數(shù)據(jù)的數(shù)據(jù)挖掘相關(guān)研究，提出了基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)模型；高勁松等[8]在關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)過程金字塔的基礎(chǔ)上提出了基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)模型；宋麗娜[9]提出了關(guān)聯(lián)數(shù)據(jù)環(huán)境下基于知識地圖的隱形知識發(fā)現(xiàn)模型；劉龍[10]提出了基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)過程模型。

以“consuming linked data”“application of linked data”“Knowledge Discovery”等為關(guān)鍵詞在谷歌學術(shù)、ScienceDirect和Springer等學術(shù)搜索引擎上進行主題檢索，同時總結(jié)了COLD、KIELD和LDOW等關(guān)聯(lián)數(shù)據(jù)會議中有關(guān)知識發(fā)現(xiàn)的文獻。相較國內(nèi)研究，國外基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)方法更為豐富且付諸實踐。根據(jù)對關(guān)聯(lián)數(shù)據(jù)挖掘?qū)哟蔚膮^(qū)別，本文將基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)技術(shù)歸結(jié)為3類：（1）間接挖掘，即通過格式轉(zhuǎn)化將關(guān)聯(lián)數(shù)據(jù)轉(zhuǎn)化或特征提取將關(guān)聯(lián)數(shù)據(jù)轉(zhuǎn)化為適合傳統(tǒng)數(shù)據(jù)挖掘算法的格式，如Venkata Narasimha等提出的Liddm關(guān)聯(lián)數(shù)據(jù)挖掘系統(tǒng)[11]以及Heiko Paulheim等提出的FeGeLOD特征提取器[12]為代表；（2）直接挖掘，利用事務(wù)構(gòu)建、歸納邏輯程序設(shè)計（Inductive logic programming，簡稱ILP）等方法直接對RDF數(shù)據(jù)進行處理，如Reza Ramezani等提出的SWApriori[13]和Gabin Personeni等提出的ILP學習方法[14]是該類的典型研究；（3）鏈接挖掘，即對關(guān)聯(lián)數(shù)據(jù)的屬性鏈和節(jié)點等結(jié)構(gòu)進行挖掘。如Ilaria Tiddi等提出的Dedalo遍歷系統(tǒng)[15-16]、Xiaowei Jiang等提出的頻繁子圖挖掘方法[17]及Kang Li等提出的深度學習方法[18]最具代表性。

2 間接挖掘

數(shù)據(jù)挖掘是基于數(shù)據(jù)庫知識發(fā)現(xiàn)的核心步驟之一，傳統(tǒng)數(shù)據(jù)挖掘技術(shù)主要針對關(guān)系型數(shù)據(jù)庫中的數(shù)據(jù)，而根據(jù)關(guān)聯(lián)數(shù)據(jù)的定義，關(guān)聯(lián)數(shù)據(jù)是采用RDF數(shù)據(jù)模型并利用URI命名數(shù)據(jù)實體的數(shù)據(jù)集合，因此如何將傳統(tǒng)的數(shù)據(jù)挖掘方法應用于關(guān)聯(lián)數(shù)據(jù)成為了一個新的研究熱點。間接挖掘的基本原理是針對不適用于傳統(tǒng)挖掘算法的關(guān)聯(lián)數(shù)據(jù)，通過特征提取或格式轉(zhuǎn)化的方式從關(guān)聯(lián)數(shù)據(jù)中提取出數(shù)值型特征，實現(xiàn)利用傳統(tǒng)數(shù)據(jù)挖掘算法對關(guān)聯(lián)數(shù)據(jù)進行挖掘分析的目標。

2.1 格式轉(zhuǎn)化

Venkata Narasimha等提出的Liddm[11]是一個可以與關(guān)聯(lián)數(shù)據(jù)有效交互的關(guān)聯(lián)數(shù)據(jù)挖掘模型，它支持從不同的數(shù)據(jù)源檢索、整合數(shù)據(jù)，為統(tǒng)計分析調(diào)整數(shù)據(jù)格式并支持數(shù)據(jù)挖掘及成果的可視化。Liddm利用SPARQL查詢從關(guān)聯(lián)數(shù)據(jù)云中獲取數(shù)據(jù)，通過數(shù)據(jù)預處理、數(shù)據(jù)輸入準備和數(shù)據(jù)挖掘等步驟進行關(guān)聯(lián)數(shù)據(jù)挖掘。其中，數(shù)據(jù)查詢結(jié)果以包含若干行和列的表格數(shù)據(jù)表示，行表示檢索到的實例，列表示該實例一個屬性的值。

數(shù)據(jù)預處理包含數(shù)據(jù)整合、數(shù)據(jù)過濾和數(shù)據(jù)分割等三個步驟。其中，數(shù)據(jù)整合是指將從多個關(guān)聯(lián)數(shù)據(jù)云中多個數(shù)據(jù)源中檢索的數(shù)據(jù)進行整合，整合基于每個數(shù)據(jù)源的共有關(guān)聯(lián)；數(shù)據(jù)過濾指通過人工篩選掉不符合數(shù)據(jù)挖掘需求的實例；數(shù)據(jù)分割指將不同列數(shù)據(jù)分為不同的類。在完成了數(shù)據(jù)的查詢和預處理后，Liddm通過數(shù)據(jù)輸入準備步驟完成數(shù)據(jù)格式的轉(zhuǎn)化。以Weka為例，Weka支持的數(shù)據(jù)輸入格式為ARFF（Artribute-Relation File Format，屬性-關(guān)聯(lián)文件格式），因此可將關(guān)聯(lián)名和屬性轉(zhuǎn)化為ARFF格式后進行挖掘。

類似的研究還包括Petar Ristoski等提出的基于RapidMiner的關(guān)聯(lián)數(shù)據(jù)挖掘方法[19]。與LiDDM相似，RapidMiner也需要終端用戶定義合適的SPARQL查詢來獲取所需數(shù)據(jù)，并將數(shù)據(jù)轉(zhuǎn)化為表格數(shù)據(jù)后進行挖掘。

2.2 特征提取

Heiko Paulheim等基于關(guān)聯(lián)數(shù)據(jù)的特性構(gòu)建了關(guān)聯(lián)數(shù)據(jù)特征提取器FeGeLOD[12]，它可以從關(guān)聯(lián)數(shù)據(jù)中提取數(shù)值型或二值數(shù)據(jù)特征并利用這些特征進行數(shù)據(jù)挖掘。FeGeLOD在Weka的基礎(chǔ)上，針對LOD提出了一系列不同的提取特征方法。特征的提取包含實體識別、實際特征構(gòu)建、特征選擇等三個步驟，其中第二步實際特征構(gòu)建是構(gòu)建關(guān)聯(lián)數(shù)據(jù)挖掘特征的核心步驟。目前FeGeLOD采取了6種不同的特征構(gòu)建策略。第一個構(gòu)造器為一個實體的每個數(shù)據(jù)屬性創(chuàng)建了一個特征。數(shù)據(jù)屬性即元素的值，如城市的名稱或城市的人口數(shù)量；第二個構(gòu)造器僅針對實體本身，即實體有謂詞rdf：type的語句，一個實體可能屬于多個類型或目錄。其余四個構(gòu)造器考慮了實體與其他實體的關(guān)聯(lián)數(shù)。

2.3 技術(shù)分析

截至2016年9月7日，LOD中互相關(guān)聯(lián)的關(guān)聯(lián)數(shù)據(jù)集已達9960個，擁有超過1490億個三元組，這些大量的結(jié)構(gòu)化、語義關(guān)聯(lián)的數(shù)據(jù)具有巨大的潛在價值。間接挖掘方法有效利用了關(guān)聯(lián)數(shù)據(jù)的關(guān)聯(lián)發(fā)現(xiàn)和數(shù)據(jù)整合的特性，通過數(shù)據(jù)集之間的關(guān)聯(lián)幫助人們更為準確、高效的發(fā)現(xiàn)和獲取相關(guān)數(shù)據(jù)。

然而，間接挖掘也存在著一些弊端，首先，間接挖掘需要用戶構(gòu)建數(shù)據(jù)查詢，而構(gòu)建關(guān)聯(lián)數(shù)據(jù)的查詢需要用戶事先對關(guān)聯(lián)數(shù)據(jù)集、SPARQL查詢以及屬性充分了解；其次，傳統(tǒng)挖掘方法往往只針對特定類型的知識，如LiDDM僅支持關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)，由于傳統(tǒng)數(shù)據(jù)挖掘算法本身的局限性，間接挖掘的方式未能深入挖掘關(guān)聯(lián)數(shù)據(jù)內(nèi)數(shù)據(jù)對象間的關(guān)聯(lián)（links）。

3 直接挖掘

相對于間接挖掘，本文將可以直接對關(guān)聯(lián)數(shù)據(jù)進行處理的挖掘方法定義為關(guān)聯(lián)數(shù)據(jù)的直接挖掘。值得注意的是，雖然關(guān)聯(lián)數(shù)據(jù)采用了RDF數(shù)據(jù)模型，但由于關(guān)聯(lián)數(shù)據(jù)的節(jié)點都是唯一的，因此并非所有RDF挖掘方法都適用于關(guān)聯(lián)數(shù)據(jù)。如圖核方法[20-21]適用于多圖的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)，而關(guān)聯(lián)數(shù)據(jù)的挖掘?qū)儆赟ingle-graph型模式挖掘型問題。直接挖掘的典型研究包括事務(wù)（transactions）構(gòu)建和歸納邏輯程序設(shè)計（Inductive Logic Programming，簡稱ILP）等。

3.1 事務(wù)構(gòu)建

ARM（Association Rule Mining，關(guān)聯(lián)規(guī)則挖掘）等傳統(tǒng)的數(shù)據(jù)挖掘算法試圖尋找頻繁項集（Large Itemsets），并在此基礎(chǔ)上生成有趣的關(guān)聯(lián)規(guī)則。在關(guān)聯(lián)數(shù)據(jù)中進行關(guān)聯(lián)規(guī)則的挖掘存在著以下挑戰(zhàn)：數(shù)據(jù)結(jié)構(gòu)的異構(gòu)性、關(guān)聯(lián)數(shù)據(jù)不存在準確定義的事務(wù)、實體間的關(guān)系以及終端用戶在挖掘過程中的角色。為從語義網(wǎng)數(shù)據(jù)中構(gòu)建事務(wù)，Ziawasch Abedjan等提出利用主語、謂詞和對象三元組中的一項組成事務(wù)，用其余兩項的值作為事務(wù)項，并從這些事務(wù)中進行關(guān)聯(lián)規(guī)則的挖掘[22]（見表1）。

在Ziawasch Abedjan的研究基礎(chǔ)上，MA Nematbakhsh 和Reza Ramezani提出了SWApriori挖掘方法，SWApriori以三元組的方式從語義網(wǎng)數(shù)據(jù)集中獲取數(shù)據(jù)并直接從中自動發(fā)現(xiàn)關(guān)聯(lián)規(guī)則[13，23]。SWApriori的基本原理是在輸入數(shù)據(jù)的實例層創(chuàng)建頻繁二項集并將其用于后續(xù)挖掘，這些頻繁二項集由實體和關(guān)聯(lián)組成（實體對應對象，關(guān)聯(lián)對應謂詞）。

SWApriori的挖掘流程為：首先遍歷統(tǒng)計所有對象出現(xiàn)的頻次，選擇出現(xiàn)在三元組中出現(xiàn)頻次大于一定次數(shù)（人工設(shè)定的最小置信度）的高頻對象，然后對這些高頻對象兩兩組合直到產(chǎn)生所有長度為二的可能對象集合。如假設(shè)Saraee、Nematbakhsh 和IUT為高頻對象，則有{Saraee，Nematbakhsh}、{Saraee，IUT}、{Nematbakhsh，IUT}等組合。隨后，算法核實這兩個對象（及對應的兩個關(guān)系）是否被多個公共的主語所參引。因此，主語的數(shù)量是最重要的因素，而它們的值則不被考慮。頻繁二項集合構(gòu)建完成后，采取與Apriori相似的方法生成頻繁多項集和關(guān)聯(lián)規(guī)則。

假如最終挖掘到的頻繁多項集為{（Nematbakhsh + Knows）、 （IUT + Student at）、 （M.Sc. + Degree）}，其中Nematbakhsh、IUT和M.Sc是高頻對象，Knows、Student at和Degree是其分別對應的關(guān)系，生成的關(guān)聯(lián)規(guī)則為：

（1）Student at（IUT），Knows（Nematbakhsh）→Degree （M.Sc.）

（2）Knows（Nematbakhsh），Degree（M.Sc.）→Student at（IUT）

（3）Student at（IUT），Degree（M.Sc.）→Knows（Nematbakhsh）

其中第一條規(guī)則表示，一個在IUT學習且知道Nematbakhsh的人一般具有M.Sc學位。

3.2 歸納邏輯程序設(shè)計

為解決LOD中大量生物醫(yī)學資源缺乏有效挖掘方法的問題，Gabin Personeni等提出利用歸納邏輯程序設(shè)計方法對關(guān)聯(lián)數(shù)據(jù)進行學習[14]。ILP隸屬于機器學習與邏輯程序設(shè)計的交叉領(lǐng)域，它借助邏輯程序設(shè)計已有的理論與方法，在一階邏輯的框架下，試圖克服傳統(tǒng)機器學習存在的問題，建立新的機器學習體系，使機器更好地模擬人的思維。ILP想要完成的任務(wù)是，讓計算機考察具體的事例，然后概括出能夠刻畫這些事例特有屬性的一般性規(guī)則。ILP允許我們從觀察中學習概念的定義，如給定正例集（E+）和負例集（E-）和背景知識（B），目標是生成一系列具有一致性（Y∪B覆蓋或解釋每個正例集）和完備性（Y∩B不覆蓋任何負例集）的規(guī)則或理論T。使用ILP進行基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)具有以下優(yōu)勢：首先，ILP的輸入格式與關(guān)聯(lián)數(shù)據(jù)格式相近；其次，領(lǐng)域知識可以添加到輸入數(shù)據(jù)中并被ILP所學習。

基于ILP的關(guān)聯(lián)數(shù)據(jù)挖掘流程分為基于專家的領(lǐng)域數(shù)據(jù)選擇、數(shù)據(jù)整合以及基于ILP的關(guān)聯(lián)數(shù)據(jù)挖掘等步驟。首先依靠領(lǐng)域?qū)＜医⒘藢嶓w關(guān)系（entity-relationship，簡稱ER）模型，確定了待挖掘數(shù)據(jù)。然后建立LOD與該ER模型之間的映射并利用SPQRQL查詢獲取數(shù)據(jù)，數(shù)據(jù)存儲于建立在實體關(guān)系模型基礎(chǔ)上的關(guān)系數(shù)據(jù)庫中。完成數(shù)據(jù)的準備工作后，作者利用Aleph（A Learning Engine for Proposing Hypotheses，ILP學習引擎）完成了ILP挖掘過程。

3.3 技術(shù)分析

直接挖掘的優(yōu)點除了包括利用關(guān)聯(lián)數(shù)據(jù)的特點更準確、更有效、更便捷的發(fā)現(xiàn)相關(guān)數(shù)據(jù)外，與間接挖掘相比，直接挖掘方法針對關(guān)聯(lián)數(shù)據(jù)自身的特點對已有挖掘方法進行了改進和重構(gòu)，使得這些方法更具有更強的易用性和可拓展性。

直接挖掘方法的缺點與間接挖掘相似，間接挖掘算法可以視為調(diào)整關(guān)聯(lián)數(shù)據(jù)以適應傳統(tǒng)挖掘算法，而直接挖掘可以視為改進傳統(tǒng)挖掘算法以適應關(guān)聯(lián)數(shù)據(jù)，就本質(zhì)而言，它們的研究主題都是關(guān)聯(lián)數(shù)據(jù)的數(shù)據(jù)資源，并對關(guān)聯(lián)數(shù)據(jù)的另一重要主題——關(guān)聯(lián)數(shù)據(jù)的鏈接則未做深入的研究。

4 鏈接挖掘

圖是由若干給定的點及連接兩點的線所構(gòu)成的圖形，這種圖形通常用來描述某些事務(wù)之間的某種特定關(guān)系，用點代表事務(wù)，用連接兩點的線表示相應兩個事務(wù)間具有這種關(guān)系。關(guān)聯(lián)數(shù)據(jù)是一個由RDF三元組構(gòu)成的有向圖，圖中的點對應每個資源、邊對應每個屬性（鏈接）。因此，本文將針對關(guān)聯(lián)數(shù)據(jù)的鏈接這一研究主題的挖掘方法定義為鏈接挖掘。由于圖的搜索空間呈指數(shù)級增長，圖的挖掘是一項計算量繁重的任務(wù)，如何選擇有效的挖掘策略對于能否從關(guān)聯(lián)數(shù)據(jù)挖掘出有效知識的質(zhì)量至關(guān)重要。根據(jù)挖掘方法的區(qū)別，我們將鏈接挖掘歸結(jié)為啟發(fā)式關(guān)聯(lián)遍歷挖掘、頻繁子圖挖掘、深度學習等三種類型并分別進行介紹。

4.1 關(guān)聯(lián)遍歷檢索

Ilaria Tiddi等提出了Dedalo啟發(fā)式關(guān)聯(lián)數(shù)據(jù)遍歷挖掘系統(tǒng)，Dedalo可以迭代檢索關(guān)聯(lián)數(shù)據(jù)尋找實體的共性（即共同路徑）從而生成解釋[15-16]。Dedalo的基本思想在于：給定一定數(shù)量的實體，在關(guān)聯(lián)數(shù)據(jù)中尋找這些實體存在共同的路徑（屬性鏈，表示為w→ι）及終值（屬性鏈終端的特定實體，表示為ei），這些路徑加終值便構(gòu)成一條簇的解釋（表示為，expi=w→ι.ei）?；诖怂枷耄珼edalo利用A*算法遍歷關(guān)聯(lián)數(shù)據(jù)尋找簇的解釋。

A*（A-Star）算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是許多其他問題的常用啟發(fā)式算法，對于路徑搜索問題，狀態(tài)就是圖中的節(jié)點，代價就是距離。一條路徑的代價可以用啟發(fā)式的指標f（x）估算，公式為： f（x）=g（x）+h（x），其中g(shù)（x）是過去的路徑開銷函數(shù)，表示起始節(jié)點到當前節(jié)點的已知距離，h（x）是未來路徑開銷函數(shù)，用來估算當前節(jié)點到目標節(jié)點的最佳路徑的距離。在關(guān)聯(lián)數(shù)據(jù)中，待解釋簇內(nèi)的項即初始節(jié)點，每個解釋expi中的實體ei是目標節(jié)點。路徑的開銷通過信息熵估算，熵主要考慮給定路徑的頻率（對應g（x））及其值（對應h（x））的分布。由于在迭代遍歷的過程中，事先不知道目標節(jié)點，因此在第n次迭代中將所有距初始節(jié)點距離為n的節(jié)點都視為目標節(jié)點。

關(guān)聯(lián)數(shù)據(jù)的迭代遍歷包含以下3個步驟：（1）URI參引，通過HTTP協(xié)議獲取初始節(jié)點相關(guān)的所有RDF屬性和屬性值；（2）路徑收集，利用URI參引從每個三元組中獲取的新的屬性Pi添加到已有的路徑中去構(gòu)建新的路徑w→ι，新路徑將通過信息熵行數(shù)進行代價估算；（3）構(gòu)建簇的解釋，在每一輪迭代之前都進行一次解釋的構(gòu)建，并通過F值對解釋進行檢驗。

關(guān)聯(lián)數(shù)據(jù)鏈接挖掘的相關(guān)研究還包括：Vito Claudio Ostuni等提出的基于LOD的SPrank關(guān)聯(lián)推薦算法[24]以及Tommaso Di Noia等提出的利用LOD支持的關(guān)聯(lián)推薦系統(tǒng)[25]，它們的共同特點是利用鏈向特定實體的共有路徑發(fā)現(xiàn)相關(guān)實體。另外，關(guān)聯(lián)數(shù)據(jù)的屬性鏈還被應用于語義相似度[26]和語義距離[27]等的計算。

4.2 頻繁子圖挖掘

在圖的集合中發(fā)現(xiàn)一組公共子結(jié)構(gòu)，這樣的任務(wù)稱作頻繁子圖挖掘（frequent subgraph mining），常用的頻繁子圖挖掘方法包括AGM、AcGM、FSG等遞歸發(fā)現(xiàn)頻繁子圖的方法以及gSpan、CloseGraph和FFSM等拓展頻繁邊得到頻繁子圖的方法。由于關(guān)聯(lián)數(shù)據(jù)中關(guān)聯(lián)模式缺乏準確正式的定義和關(guān)聯(lián)數(shù)據(jù)圖結(jié)構(gòu)的復雜性，頻繁子圖挖掘方法難以直接應用到關(guān)聯(lián)數(shù)據(jù)中。針對這一問題，Xiang Zhang和Cuifang Zhao等提出利用Typed Object Graph（類型化對象圖，簡稱TOG）數(shù)據(jù)模型簡化關(guān)聯(lián)數(shù)據(jù)結(jié)構(gòu)并利用基于gSpan的模式挖掘算法從關(guān)聯(lián)數(shù)據(jù)中學習對象的關(guān)聯(lián)模式[28]。TOG圖通過一定的類檢測策略可以為RDF圖的每個實例賦予類型信息獲取（見圖1）。完成TOG圖的構(gòu)建后，對TOG圖進行聚類后利用基于gSpan算法進行關(guān)聯(lián)規(guī)則的挖掘。

在Xiang Zhang 等的研究基礎(chǔ)上，Xiaowei Jiang提出了一種TOG圖壓縮策略進行實例層的關(guān)聯(lián)數(shù)據(jù)語義挖掘[15]由于關(guān)聯(lián)數(shù)據(jù)中存在大量的重復結(jié)構(gòu)和相互依賴結(jié)構(gòu)，因此在挖掘前可以利用這種機構(gòu)特征進行圖的壓縮。根據(jù)關(guān)聯(lián)數(shù)據(jù)的結(jié)構(gòu)特征，作者提出了兩種結(jié)合重復結(jié)構(gòu)和壓縮互相依賴結(jié)構(gòu)等兩種圖壓縮策略。壓縮的核心思想是利用鏈向TOG中一系列高度相關(guān)實例的單個實例代表一個可壓縮的圖結(jié)構(gòu)。在完成了圖的壓縮后，關(guān)聯(lián)數(shù)據(jù)內(nèi)的一些圖結(jié)構(gòu)將變成一些所謂“超節(jié)點（hypernode）”實例的內(nèi)部結(jié)構(gòu)，原始的關(guān)聯(lián)數(shù)據(jù)圖也壓縮為較小的“超圖（hypergraph）”。

4.3 深度學習

深度學習的概念源于人工神經(jīng)網(wǎng)絡(luò)的研究。深度學習通過組合低層特征形成更加抽象的高層表示屬性類別或特征，以發(fā)現(xiàn)數(shù)據(jù)的分布式特征表示。波爾茲曼機（Boltzmann machine，簡稱BM）是Hinton和Sejnowski于1986年提出的一種根植于統(tǒng)計力學的隨機神經(jīng)網(wǎng)絡(luò)。BM具有強大的無監(jiān)督學習能力，能學習數(shù)據(jù)中復雜的規(guī)則。但是，擁有這種學習能力的代價是其訓練（學習）過程耗時。此外，BM所表示的分布不僅無法確切計算，得到該分布的隨機樣本也很困難。于是Sejnowski引入了一種受限波爾茲曼機（Restricted Boltzmann machine model，簡稱RBM）。RBM具有一個可見層和一個隱層，層內(nèi)無連接。RBM具有很好的性質(zhì)，在給定可見層單元狀態(tài)時，各隱單元的激活條件獨立；反之，在給定隱單元狀態(tài)時，可見層單元的激活亦條件獨立。這樣一來盡管RBM所表示的分布仍無法有效計算，但通過Gibbs采樣（Gibbs sampling）可以得到RBM所表示分布的隨機樣本。目前RBM已經(jīng)被成功運用到不同的機器學習問題[29]。

從關(guān)聯(lián)數(shù)據(jù)中學習知識的主要挑戰(zhàn)之一是如何在高效利用節(jié)點屬性的同時利用關(guān)聯(lián)數(shù)據(jù)的關(guān)聯(lián)抽取有效信息。當前對基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)要么采取人工選擇的拓撲統(tǒng)計表示網(wǎng)絡(luò)結(jié)構(gòu)，要么將節(jié)點屬性和網(wǎng)絡(luò)節(jié)點線性映射到一個共享隱含特征空間（shared latent feature space）。但基于統(tǒng)計的方法可能損失網(wǎng)絡(luò)結(jié)構(gòu)中的重要模式，基于線性映射的方法可能無法捕捉到節(jié)點和關(guān)聯(lián)的非線性特征。為解決這些問題，Kang Li、Jing Gao利用深度學習理論，構(gòu)建了基于受限波爾茲曼機對關(guān)聯(lián)數(shù)據(jù)進行表征學習的LRBM（Restricted Boltzmann Machines for Latent Feature Learning in Linked Data，學習關(guān)聯(lián)數(shù)據(jù)潛在特征的受限波爾茲曼機）模型，LRBM利用對比散度（Contrastive Divergence，簡稱CD）進行模型的訓練避免了大規(guī)模的采樣，同時模型可以與傳統(tǒng)RMB進行“疊加”以探索節(jié)點的深層特征和節(jié)點間的高階交互模式[16]。

LRBM不依賴任何主觀選擇的拓撲統(tǒng)計（topological statistics），可以在一個統(tǒng)一框架中同時獲取節(jié)點和屬性的特征，并根據(jù)這些特征構(gòu)建節(jié)點關(guān)聯(lián)以及隱藏單元之間的非線性關(guān)系。模型的核心在于節(jié)點共享隱含特征，這些隱含特征可以用來構(gòu)建節(jié)點、關(guān)聯(lián)關(guān)系和隱含單元的非線性關(guān)系。

作者首先用關(guān)聯(lián)矩陣表示關(guān)聯(lián)數(shù)據(jù)集中的節(jié)點和關(guān)聯(lián)關(guān)系，定義節(jié)點i到節(jié)點j的關(guān)聯(lián)L中節(jié)點i定義為關(guān)聯(lián)的發(fā)送者，節(jié)點j為關(guān)聯(lián)的接收者，并將每個節(jié)點的隱含表示（latent representation）定義為發(fā)送者行為Si和接收者行為Ri兩部分，分別對應節(jié)點的入鏈和出鏈。因此，節(jié)點i的屬性Ai與其隱含發(fā)送者行為Si和接收者行為Ri相關(guān)，且Si和Rj決定了節(jié)點i和j之間的交互。為將節(jié)點屬性A、關(guān)聯(lián)L和隱含特征表示R和S之間的交互建模，作者利用能量函數(shù)建立了一個隱含語義模型（Latent Factor Model，簡稱LFM），利用條件限制波爾茨曼機在模型加入了隱變量h以解決線性映射的問題，同時添加高斯噪聲為關(guān)聯(lián)關(guān)系賦予權(quán)重。最終，LRBM模型可關(guān)聯(lián)數(shù)據(jù)中提取出節(jié)點屬性、隱含特征S和R以及關(guān)聯(lián)關(guān)系的交互特征，并可將其應用到關(guān)聯(lián)預測、節(jié)點分類等知識發(fā)現(xiàn)活動中。

4.4 技術(shù)分析

在關(guān)聯(lián)數(shù)據(jù)集合中，數(shù)據(jù)集合和數(shù)據(jù)對象之間是以某種方式關(guān)聯(lián)的，對象之間的鏈接可能表示某種特定的模式，但這一模式通常很難用傳統(tǒng)的統(tǒng)計模型去獲取，因此，為該挑戰(zhàn)提供解決方案的鏈接挖掘成為了新的研究熱點。這一領(lǐng)域在鏈接分析、超文本和網(wǎng)絡(luò)挖掘、關(guān)系學習和圖挖掘等相關(guān)研究的交叉點上。

關(guān)聯(lián)遍歷挖掘、頻繁子圖挖掘、LRBM等分別利用了圖的遍歷、壓縮和深度學習的方法對關(guān)聯(lián)數(shù)據(jù)的鏈接進行挖掘，為基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)提供了全新的方法和視角，但鏈接挖掘存在的問題是，由于當前研究仍處于探索階段，相關(guān)研究相對比較分散，缺少能將相關(guān)研究和應用統(tǒng)一到一個框架中的綜合體系，這一問題阻礙了已有研究之間的相互交流以及研究成果的拓展和共享。

5 結(jié)語

關(guān)聯(lián)數(shù)據(jù)通過數(shù)據(jù)間的鏈接支持結(jié)構(gòu)化數(shù)據(jù)的關(guān)聯(lián)，這種攜帶語義的關(guān)聯(lián)遍及整個數(shù)據(jù)網(wǎng)絡(luò)，是關(guān)聯(lián)數(shù)據(jù)的核心價值。為實現(xiàn)關(guān)聯(lián)數(shù)據(jù)的價值，早期研究更多的關(guān)注了關(guān)聯(lián)數(shù)據(jù)的構(gòu)建與發(fā)布，而隨著關(guān)聯(lián)數(shù)據(jù)資源的快速發(fā)展，更多的研究開始關(guān)注關(guān)聯(lián)數(shù)據(jù)的應用與消費，這些研究往往集中在“關(guān)聯(lián)數(shù)據(jù)的數(shù)據(jù)資源”和“關(guān)聯(lián)數(shù)據(jù)的關(guān)聯(lián)”等兩個主題。本文所介紹的間接挖掘和直接挖掘主要關(guān)注“關(guān)聯(lián)數(shù)據(jù)的數(shù)據(jù)資源”，這些研究促進了知識發(fā)現(xiàn)與關(guān)聯(lián)數(shù)據(jù)領(lǐng)域之間研究體系上的拓展和融合，一方面有助于從數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的角度去發(fā)揮關(guān)聯(lián)數(shù)據(jù)的潛在價值；另一方面也可以借助數(shù)據(jù)挖掘和知識發(fā)現(xiàn)領(lǐng)域的知識解決關(guān)聯(lián)數(shù)據(jù)存在的問題。鏈接挖掘則更多的關(guān)注了“關(guān)聯(lián)數(shù)據(jù)的關(guān)聯(lián)”主題，圖論、深度學習等學科的引入為基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)提供了全新的視角與方法，雖然當前的研究仍比較分散缺少統(tǒng)一的綜合框架，但這些方法和理論的引入已經(jīng)為基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)提供了新的活力和可能。

總體而言，基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)技術(shù)仍處于快速發(fā)展階段，其作為一種新的知識發(fā)現(xiàn)技術(shù)已經(jīng)體現(xiàn)了巨大的價值。隨著關(guān)聯(lián)數(shù)據(jù)數(shù)量的飛速發(fā)展和對關(guān)聯(lián)數(shù)據(jù)質(zhì)量控制的加強，且已經(jīng)有國內(nèi)外的研究人員開始著手研究基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)統(tǒng)一框架，未來的研究重點將更加傾向于基于關(guān)聯(lián)數(shù)據(jù)知識發(fā)現(xiàn)技術(shù)本身的豐富和完善。

參考文獻：

[1] 苗蔚，李后卿.知識發(fā)現(xiàn)及其實現(xiàn)技術(shù)的研究概述[J].現(xiàn)代情報，2005（1）：12-15.

[2] 李楠.基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)研究[D].北京：中國農(nóng)業(yè)科學院，2012.

[3] 化柏林.數(shù)據(jù)挖掘與知識發(fā)現(xiàn)關(guān)系探析[J].情報理論與實踐，2008（4）：507-510.

[4] 張樹良，冷伏海.基于文獻的知識發(fā)現(xiàn)的應用進展研[J].情報學報，2006，25（6）：700-712.

[5] 賈麗梅.基于關(guān)聯(lián)數(shù)據(jù)語義相似度計算研究[D].鄭州：鄭州大學，2014.

[6] 李楠，張學福.基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)模型研究[J].圖書館學研究，2013（1）：73-77，67.

[7] 李俊，黃春毅.關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)研究[J].情報科學，2013（3）：76-81.

[8] 高勁松，李迎迎，劉龍，等.基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)模型構(gòu)建研究[J].情報科學，2016（6）：10-13，18.

[9] 宋麗娜.關(guān)聯(lián)數(shù)據(jù)環(huán)境下基于知識地圖的隱性知識發(fā)現(xiàn)模型研究[D].武漢：華中師范大學，2014.

[10] 劉龍.基于關(guān)聯(lián)數(shù)據(jù)的知識發(fā)現(xiàn)過程模型研究[D].武漢：華中師范大學，2014.

[11] Narasimha V，Kappara P，Ichise R，et al.LiDDM：A Data Mining System for Linked Data[C].Workshop on Linked Data on the Web.CEUR Workshop Proceedings，2011：813.

[12] Paulheim H，F(xiàn)ümkranz J.Unsupervised generation of data mining features from linked open data[C].Proceedings of the 2nd international conference on web intelligence， mining and semantics.ACM，2012：31.

[13] Ramezani R，Saraee M，Nematbakhsh M A.Finding association rules in linked data，a centralization approach[C].21st Iranian Conference on Electrical Engineering（ICEE）.IEEE，2013：1-6.

[14] Personeni G，Daget S，Bonnet C，et al.Mining Linked Open Data：A Case Study with Genes Responsible for Intellectual Disability[C].International Conference on Data Integration in the Life Sciences.Springer International Publishing，2014：16-31.

[15] Tiddi I，d'Aquin M，Motta E.Dedalo：Looking for clusters explanations in a labyrinth of linked data[C].European Semantic Web Conference.Springer International Publishing，2014：333-348.

[16] Tiddi I，d'Aquin M，Motta E.Walking Linked Data：a graph traversal approach to explain clusters[C].Proceedings of the 5th International Conference on Consuming Linked Data-Volume 1264.CEUR-WS.org，2014：73-84.

[17] Jiang X，Zhang X，Gao F，et al.Graph compression strategies for instance-focused semantic mining[C].China Semantic Web Symposium and Web Science Conference.Springer Berlin Heidelberg，2013：50-61.

[18] Li K，Gao J，Guo S，et al.Lrbm： A restricted boltzmann machine based approach for representation learning on linked data[C].Data Mining（ICDM），2014 IEEE International Conference on.IEEE，2014：300-309.

[19] Ristoski P，Bizer C，Paulheim H.Mining the web of linked data with rapidminer[J].Web Semantics：Science，Services and Agents on the World Wide Web，2015（35）：142-151.

[20] L？觟sch U，Bloehdorn S，Rettinger A.Graph kernels for RDF data[M].The Semantic Web：Research and Applications.Springer Berlin Heidelberg，2012.

[21] de Vries G K D，de Rooij S.Substructure counting graph kernels for machine learning from RDF data[J].Web Semantics：Science，Services and Agents on the World Wide Web，2015（35）：71-84.

[22] Abedjan Z，Naumann F.Context and target configurations for mining RDF data[C].Proceedings of the 1st international workshop on Search and mining entity-relationship data.ACM，2011：23-24.

[23] Ramezani R，Saraee M，Nematbakhsh M A.Finding association rules in linked data，a centralization approach[C].21st Iranian Conference on Electrical Engineering（ICEE）.IEEE，2013：1-6.

[24] Ostuni V C，Di Noia T，Di Sciascio E，et al.Top-n recommendations from implicit feedback leveraging linked open data[C].Proceedings of the 7th ACM conference on Recommender systems.ACM，2013：85-92.

[25] Di Noia T，Mirizzi R，Ostuni V C，et al. Linked open data to support content-based recommender systems[C].Proceedings of the 8th International Conference on Semantic Systems.ACM，2012：1-8.

[26] Hulpus I，Prangnawarat N，Hayes C.Path-based semantic relatedness on linked data and its use to word and entity disambiguation[C].International Semantic Web Conference.Springer International Publishing，2015：442-457.

[27] Passant A.Measuring Semantic Distance on Linking Data and Using it for Resources Recommendations[C].AAAI spring symposium：linked data meets artificial intelligence，2010（77）：123.

[28] Zhang X，Zhao C，Wang P，et al.Mining link patterns in linked data[C].International Conference on Web-Age Information Management.Springer Berlin Heidelberg，2012：83-94.

[29] 張春霞，姬楠楠，王冠偉.受限波爾茲曼機[J].工程數(shù)學學報，2015（2）：159-173.

作者簡介：崔家旺（1991-），中國科學院文獻情報中心碩士研究生，研究方向：關(guān)聯(lián)數(shù)據(jù)；李春旺（1996-），中國科學院文獻情報中心研究館員，碩士生導師，研究方向：集成融匯技術(shù)、關(guān)聯(lián)數(shù)據(jù)、智能檢索、學科化服務(wù)、數(shù)字資源長期保存等。