張 瑤，李蜀瑜，湯 玥

(陜西師范大學 計算機科學學院,陜西 西安 710119)

大數(shù)據(jù)下的多源異構(gòu)知識融合算法研究

張 瑤，李蜀瑜，湯 玥

(陜西師范大學 計算機科學學院,陜西 西安 710119)

在大數(shù)據(jù)環(huán)境下，多源異構(gòu)知識的融合為研究者從眾多分散、異構(gòu)的數(shù)據(jù)源和知識源中挖掘出隱含的、有價值的和尚未被發(fā)現(xiàn)的信息和知識提供了非常有效的手段和方法。針對目前知識融合方法的不足，在對大數(shù)據(jù)環(huán)境下的異構(gòu)知識融合方法進行深入研究的基礎上，將已有的數(shù)據(jù)融合算法合理地移植到知識融合中，設計并構(gòu)造了大數(shù)據(jù)環(huán)境下的多源異構(gòu)知識融合算法。為進一步提高獲取知識的質(zhì)量，依據(jù)知識源粒度的動態(tài)選擇，提出了一種改進的知識源分解-合并算法，以獲得合適粒度大小的知識源集合和盡可能真實可靠的知識?；贖adoop和MapReduce框架所構(gòu)建的實驗平臺對所提算法進行了實驗驗證。實驗結(jié)果表明，所提出的多源異構(gòu)知識融合算法有效可行，并能夠有效顯著地提高多源異構(gòu)知識融合算法的性能。

大數(shù)據(jù)；多源異構(gòu)知識；知識融合；融合算法

0 引 言

在如今的大數(shù)據(jù)時代，數(shù)據(jù)的種類越來越多，數(shù)據(jù)的規(guī)模日益增大。在數(shù)據(jù)這片汪洋大海中，人們往往不知所措，從多而雜的數(shù)據(jù)中抽取出有較高利用價值的知識的需求也變得更加迫切。這不僅是企業(yè)界也是學術界重點關注的話題[1]。在大數(shù)據(jù)環(huán)境下，人類對知識服務的探究，已經(jīng)不僅僅局限于傳統(tǒng)的信息和文獻服務，而是將研究的目光更多投放在用戶的行為、數(shù)量龐大的碎片化信息、用戶之間的關系以及由此而生成的海量的具有實時性的數(shù)據(jù)、機器數(shù)據(jù)和非結(jié)構(gòu)化數(shù)據(jù)等方面[2]。知識服務的意義和內(nèi)容，將在大數(shù)據(jù)的推進下不斷發(fā)生變化，它將更多地面向知識的不斷創(chuàng)新和人類對知識的各方面需求，逐漸轉(zhuǎn)變?yōu)橹R預測型的服務，將大數(shù)據(jù)轉(zhuǎn)變?yōu)檎嬲拇笾腔邸?/p>

知識融合是基于信息融合發(fā)展而成的一個新概念。多源異構(gòu)知識是由知識自身不斷豐富、發(fā)展、創(chuàng)新、演化而成。多源異構(gòu)知識融合自身的價值就在于從眾多分散、異構(gòu)的數(shù)據(jù)源、知識源中挖掘出隱含的、有價值的、尚未被發(fā)現(xiàn)的信息和知識(如規(guī)則、方法、模型、約束、經(jīng)驗等)。知識融合實現(xiàn)的關鍵在于融合方法，直接影響融合后知識的內(nèi)涵、層次以及置信度。

在大數(shù)據(jù)環(huán)境下，由于數(shù)據(jù)的結(jié)構(gòu)差異大、數(shù)據(jù)來源廣、價值密度較低、更新實時等特點，給知識服務帶來了巨大挑戰(zhàn)，而多源異構(gòu)知識的融合為研究者在大數(shù)據(jù)環(huán)境下進行知識獲取、知識組織和利用提供了非常有效的手段和方法。目前的知識融合方法從理論到實踐還有很多不足，為此，就大數(shù)據(jù)環(huán)境下的異構(gòu)知識融合方法展開進一步的深入研究，借鑒數(shù)據(jù)融合方法，提出了多源異構(gòu)知識融合算法，并基于知識源的粒度給出了一種改進方法，同時還進行了實驗驗證。

1 知識融合相關算法研究

目前關于知識融合還沒有一個統(tǒng)一的定義，知識融合的發(fā)展是建立在信息融合的基礎之上的，在最早的時候，人類關于知識融合的研究大多是將它當作知識工程的一個分支，并且和其他有關的內(nèi)容結(jié)合起來。知識融合的研究內(nèi)容與信息融合的研究內(nèi)容有重合部分，所以，在研究知識融合時可以參考信息融合的相關研究結(jié)果[3]。

知識融合算法是知識融合的核心部分。目前，研究人員已經(jīng)提出了有關知識融合的算法，除知識融合的評價算法外，其他的分別為基于D-S理論[4]、模糊集理論[5]、主題圖[6]和語義規(guī)則[7]的知識融合算法。

基于D-S證據(jù)理論的知識融合算法[8]是由韓立巖提出的，該方法首先進行數(shù)學建模，然后實現(xiàn)融合算法，最后對融合結(jié)果進行分析預測。但是這種方法會受到單一故障假設的條件限制。姚路等針對這一不足，提出一種將DSmT與系統(tǒng)建模相結(jié)合的知識融合算法[9]。周芳等利用模糊集理論解決知識融合問題，基于Petri網(wǎng)提出了知識融合的一般模型，并詳細介紹了融合模型中的每個步驟，將知識融合算法應用到實際的企業(yè)相關問題中[10]。魯慧民等在全信息理論[11]的基礎上，通過聯(lián)合擴展主題圖自身的優(yōu)點，提出了基于擴展主題圖相似性算法(ETMSC)[12]。該算法是針對多源知識融合的，與此同時，提出了層次之間相互對應、閾值選取以及實驗確定這三個基本原則。該算法在進行相似性計算時，綜合考慮了語用、語義、語法、知識的含義和知識所處的語義環(huán)境。

這些知識融合算法面向的應用知識都是有針對性的，其中，基于D-S理論的更加側(cè)重關于專家知識的融合，基于語義的則重點是研究非專家的知識融合，基于主題圖的主要研究的是專家知識和非專家知識的融合。目前已有的知識融合算法雖然考慮到知識來源的多樣性，但是具體對每個知識的結(jié)構(gòu)分析得不夠清楚，而且還有一點不足是沒有考慮到源知識本身的可靠性和真實性。從考慮知識的真實概率的角度出發(fā)，結(jié)合大數(shù)據(jù)環(huán)境，提出了一種多源異構(gòu)知識融合算法。

2 多源異構(gòu)知識融合算法

由于知識融合是從不同知識源，如Freebase、YAGO等公開的知識庫以及互聯(lián)網(wǎng)網(wǎng)頁，抽取知識獲得知識三元組，求得知識三元組的真實概率，以做出最佳決策，提供更好的知識服務。而數(shù)據(jù)融合是解決從不同來源的值，并尋找數(shù)據(jù)真值的問題。因此，基于知識融合本身的特點，借鑒已有的數(shù)據(jù)融合算法，將其合理地移植到知識融合中，構(gòu)造大數(shù)據(jù)環(huán)境下的多源異構(gòu)知識融合算法。

2.1多源異構(gòu)知識融合面對的挑戰(zhàn)

數(shù)據(jù)融合是對從不同來源的數(shù)據(jù)、信息，加以聯(lián)合、相關、組織，尋找數(shù)據(jù)真值。與數(shù)據(jù)融合相比，對知識融合提出了三大挑戰(zhàn)。

(1)數(shù)據(jù)融合的輸入為一個二維數(shù)據(jù)矩陣，如圖1(a)所示；而知識融合的輸入是一個三維矩陣，如圖1(b)所示。新增的一維表示提取器，所以矩陣中的每個單元格表示用相應的抽取器從對應的Web源中提取的相應數(shù)據(jù)項的值。錯誤在這個過程的每個階段都有可能發(fā)生，不僅來自于Web源，也可能來自于提取過程中三元組的識別、實體連接和屬性連接。

圖1 數(shù)據(jù)融合和知識融合的輸入

(2)希望預測概率可以正確地反映三元組真實的可能性。一個基本要求就是單調(diào)：具有較高預測概率的三元組應該比一個具有較低預測概率的三元組的真實概率要大些。

(3)知識的規(guī)模通常是巨大的。當前在數(shù)據(jù)融合實驗中使用的最大數(shù)據(jù)集包含170 K數(shù)據(jù)源，400 K的數(shù)據(jù)項。知識融合往往需要處理的數(shù)據(jù)的數(shù)量級在各方面都會更大。

2.2融合方法選取標準

現(xiàn)有的數(shù)據(jù)融合方法可以用來解決知識融合的問題。采用了三個標準，從現(xiàn)有的方法中選擇合適的數(shù)據(jù)融合方法。

(1)由于知識融合的目標是計算每個三元組的真實概率，選擇的數(shù)據(jù)融合方法，可以很容易地求出一個有意義概率。

(2)由于知識融合的數(shù)據(jù)規(guī)模比傳統(tǒng)的數(shù)據(jù)融合的數(shù)據(jù)規(guī)模要大三個數(shù)量級，選擇能按比例放大的基于MapReduce[13]框架的方法。

(3)重點放在那些最近研究表明更有效的方法。例如，文獻[14]表明基于貝葉斯方法更優(yōu)于基于Web鏈路等方法。

2.3多源異構(gòu)知識融合方法

按照上述三個標準，選擇了三種數(shù)據(jù)融合方法：VOTE，ACCU和POP ACCU。下面對這三種方法進行簡單的介紹，然后再描述如何使用這三種方法來解決知識融合問題。

VOTE：對于每個數(shù)據(jù)項，VOTE統(tǒng)計每個值的數(shù)據(jù)來源的個數(shù)，并且信任來自最多數(shù)據(jù)源的值。VOTE作為實驗的基準。

ACCU：采用的是貝葉斯分析方法。算法偽代碼如圖2所示。對于每一個提供一組值VS的數(shù)據(jù)源S，S的準確度是VS中所有值的平均概率。對于每個數(shù)據(jù)項D和由D提供的值的集合VD，一個值的概率是使用貝葉斯分析觀測其先驗概率計算所得。ACCU假定：對于每個數(shù)據(jù)項D只有一個真值；有N個均勻分布的假值；數(shù)據(jù)源之間是相互獨立的。

圖2 ACCU算法

POP ACCU：POP ACCU通過去除錯誤的值使均勻分布的假設擴展了ACCU；它從真實數(shù)據(jù)中計算得出分布并將其插入到貝葉斯分析中。文獻[15]已經(jīng)證明POP ACCU是單調(diào)的，也就是說在假設數(shù)據(jù)源和數(shù)據(jù)項都是獨立的條件下，增加一個數(shù)據(jù)源不會降低數(shù)據(jù)融合的質(zhì)量。

2.4多源異構(gòu)知識融合體系

采用以上三種數(shù)據(jù)融合方法解決知識融合問題。

首先，數(shù)據(jù)融合方法的輸入是二維數(shù)據(jù)矩陣，每個數(shù)據(jù)源提供相應數(shù)據(jù)項的值，而知識融合方法的輸入是三維矩陣，包含每個數(shù)據(jù)源通過相應的抽取器抽取得到的對應數(shù)據(jù)項的值。為了減小知識融合輸入的維度，考慮將每對(抽取器，URL)作為數(shù)據(jù)源。有大量的數(shù)據(jù)源表明一個知識三元組不是由Web源提供的，就是由許多不同的抽取器抽取獲得的。

其次，數(shù)據(jù)融合方法的輸出是由每個提供的值的二元決策構(gòu)成的，而知識融合方法的輸出是每個知識三元組的真實概率。對于ACCU和POP ACCU，通過貝葉斯分析計算獲得每個知識三元組的真實概率。對于VOTE，采取的計算概率的方法如下：如果一個數(shù)據(jù)項D=(s,p)總共有n個出處，一個知識三元組T=(s,p,o)有m個出處，則知識三元組的真實概率為p(T)=m/n。

最后，使用基于MapReduce的框架來擴展上述三種方法。知識融合的體系結(jié)構(gòu)如圖3所示。一共有三個階段；每個階段是一個MapReduce的過程，因此以并行的方式進行。

第一階段：Map步驟是根據(jù)相關的數(shù)據(jù)項將輸入所提取的知識三元組進行劃分；Reduce步驟是運用貝葉斯分析方法推導并計算出由相同數(shù)據(jù)項提供的每個知識三元組的真實概率。

第二階段：Map步驟將已經(jīng)由出處獲得的概率的知識三元組進行劃分；Reduce步驟是依據(jù)出處所包含的知識三元組來計算它的準確度。重復前兩個階段直至收斂。

第三階段：Map步驟是劃分所提取的知識三元組；Reduce步驟是將由不同出處得到的相同的知識三元組進行去重，第三階段輸出最終結(jié)果。

圖3 MapReduce實現(xiàn)ACCU和POP ACCU

3 多源異構(gòu)知識融合方法的改進

針對ACCU和POP ACCU的融合方法，從知識源的質(zhì)量角度出發(fā)，提出一種改進算法。該算法可以動態(tài)選擇知識源的粒度大小，得到合適粒度大小的知識源集合，作為以上融合算法的輸入?yún)?shù)，以提高知識三元組真實概率的準確度和有效性。

理想情況下，希望用最好的粒度大小知識源。例如，由于一個網(wǎng)頁可能與其他的網(wǎng)頁有不同的精確度，所以很自然地將每個網(wǎng)頁看作是一個獨立的源。甚至可以定義一個源作為在特定網(wǎng)頁上的特定謂語，這樣可以估算一個關于特定種類的謂詞的網(wǎng)頁可信度。然而，當定義來源過于精準的話，可能有太少可靠的數(shù)據(jù)來估算它們的準確度；相反，可能存在一些數(shù)據(jù)源，它們有太多的數(shù)據(jù)都在最后的粒度上，這樣可能會導致計算瓶頸。

為了解決這個問題，需要動態(tài)選擇知識源的粒度。對于粒度過小的知識源，可以在層次結(jié)構(gòu)上回退到比較粗糙的級別，使得可以借用相關頁面之間的統(tǒng)計強度。對于粒度過大的知識源，可以選擇將其拆分成多個知識源，然后獨立地評估它們的準確度。當做歸并時，目標是在不降低效率的條件下提高評估的統(tǒng)計質(zhì)量。當做分解時，目標是在沒有顯著改變評估結(jié)果的前提下有效提高數(shù)據(jù)偏斜。

為了使效果更精準，把知識源定義為一個特征向量：<網(wǎng)站，謂詞，網(wǎng)頁>，并按照最一般到最特殊的情況進行排序。然后在一個層次結(jié)構(gòu)上安排這些知識源。例如，是的父親，而是的父親。定義以下兩種操作：

分解：當分解一個較大的知識源時，希望可以將其隨機分解為大小相似的子知識源。具體就是，令一個大小固定的知識源M，是期望的最大尺寸，將三元組均勻分布到大小小于最大尺寸的桶，每個桶代表的是一個子知識源。將M設置為一個比較大的值，這樣那些不需要分解的知識源就不會分解，同時不會導致計算瓶頸。

合并：當合并小的知識源時，希望只合并那些有共同特征的知識源，例如這些知識源共有相同的謂詞，或者來自于相同的網(wǎng)站。因此，在結(jié)構(gòu)層次上只合并那些有相同的根源或?qū)儆谕粋€分支的子源，將其設置為一個很小的值，這樣能降低合并的范圍，不需要合并的知識源就不會合并，同時還保持足夠的統(tǒng)計強度。

例如，考慮以下三個知識源：，，，每個只含有兩個特征，不足以用來進行質(zhì)量評估。可以通過移除第二特征把它們合并到它們的父親源，然后得到一個大小一定知識源，該知識源可以為質(zhì)量評估提供很多的知識。

有兩種情況需要考慮：一是當合并了小的知識源，但是得到的父親源可能并沒有期望的大小，它可能還是太小，這時，需要反復迭代合并父親源，以達到期望的大??；二是當合并的結(jié)果過于龐大，大大超出了期望的大小，這時就要將這些合并的源再做分解。用來動態(tài)選擇知識源的粒度大小的知識源分解-合并算法(SplitAndMerge)的偽代碼如下：

輸入：S為具有最好粒度的知識源；m/M為期望的最小/最大知識源的大小。

輸出：S'為一個具有期望大小的知識源的集合。

Begin

1：S'←?；//將最終知識源初始化為空集

2：ForS∈Sdo；//遍歷知識源集合中的每個知識源

3：S←S{S}；

4：If |S|>Mthen //知識源大小大于期望的最大值

5：S'←S'∪SPLIT(S)；//進行知識源分解操作

6：else if |S|

7：Spar←GETPARENT(S)；//進行知識源合并操作

8：ifSpar=⊥ then；//已經(jīng)達到了層次結(jié)構(gòu)的頂部

9：S'←S'∪{S}；

10：else

11：S←S∪{Spar}；//繼續(xù)迭代合并

12：else

13：S'←S'∪{S}；

14：ReturnS'；//輸出最后得到新的知識源集

4 實驗結(jié)果與分析

利用文獻[16]中的知識抽取方法獲取實驗數(shù)據(jù)，抽取結(jié)果如表1所示。

表1 知識抽取結(jié)果及抽取質(zhì)量

所涉及的知識一部分是來源于已有的一些高品質(zhì)的知識庫，如Freebase、YAGO等，另一部分是來自于互聯(lián)網(wǎng)上的最新知識。使用Hadoop構(gòu)建知識融合的實驗平臺。另外，為了更好地評估所提出的多源異構(gòu)知識融合方法中不同算法的性能，利用大型Matlab對幾組數(shù)據(jù)進行處理，比較模塊化度并繪制相應的結(jié)果。

首先，給出評價實驗結(jié)果的一個指標：校準曲線。校準曲線繪制的是預測概率與真實概率之間的變化。為了計算真實概率，把知識三元組分成l+1桶：第i(0≤i≤l-1)桶包含預測概率在[i/l,(i+1)/l)知識三元組，第l+1桶包含概率為1的知識三元組。實驗中設l=20，然后計算每個桶的真實概率。理想的情況是預測概率應該與真實概率相同，這樣的理想曲線是由(0,0)到(1,1)。

利用多源異構(gòu)知識融合方法得到知識三元組真實概率的結(jié)果和預測結(jié)果，繪制了校準曲線，如圖4所示。結(jié)果顯示應用POP ACCU的多源異構(gòu)知識融合算法的結(jié)果最貼近理想曲線，效果最好。

圖4 不同融合方法的校準曲線

再將抽取獲得的結(jié)果按照改進方法求得知識三元組的真實概率，并繪制校準曲線，如圖5所示。結(jié)果顯示，改進算法確實可以在一定程度上提高多源異構(gòu)知識融合算法的性能。

圖5 改進后的校準曲線

5 結(jié)束語

多源知識融合是對知識進行融合、處理，進而提高知識的內(nèi)涵、品質(zhì)、置信度。針對目前知識融合方法的不足，結(jié)合大數(shù)據(jù)背景，借鑒數(shù)據(jù)融合算法，提出了一種多源異構(gòu)知識融合算法，以求出知識三元組的真實概率，并依據(jù)知識源的粒度提出了相應的改進算法。應用Hadoop構(gòu)建實驗平臺，并基于MapReduce框架，實現(xiàn)了多源異構(gòu)知識融合算法，并對改進方法進行了實驗驗證。實驗結(jié)果表明，改進算法可以有效提高多源異構(gòu)知識融合算法的性能。

[1] 蘇新寧.面向知識服務的知識組織理論與方法[M].北京:科學出版社,2014.

[2] 唐曉波,魏 巍.知識融合:大數(shù)據(jù)時代知識服務的增長點[J].圖書館學研究,2015(5):9-14.

[3] 緱 錦.知識融合中若干關鍵技術研究[D].杭州:浙江大學,2005.

[4] Valin P,Djiknavorian P,Bosse E.A pragmatic approach for the use of Dempster-Shafer theory in fusing realistic sensor data[J].Journal of Advances in Information Fusion,2010,5(1):32-40.

[5] Werro N.Fuzzy set theory[M]//Fuzzy classification of online customers.[s.l.]:Springer International Publishing,2015:7-26.

[6] Lu J,Ma J,Zhang G,et al.Theme-based comprehensive evaluation in new product development using fuzzy hierarchical criteria group decision-making method[J].IEEE Transactions on Industrial Electronics,2011,58(6):2236-2246.

[7] Okoye K, Tawil A R H, Naeem U,et al.A semantic rule-based approach towards process mining for personalised adaptive learning[C]//High performance computing & communications,IEEE international symposium on cyberspace safety & security,IEEE international conference on embedded software & systems.[s.l.]:IEEE,2014:929-936.

[8] 韓立巖,周 芳.基于D-S證據(jù)理論的知識融合及其應用[J].北京航空航天大學學報,2006,32(1):65-68.

[9] 姚 路,康劍山,曾 斌.結(jié)合DSmT理論和系統(tǒng)建模的知識融合算法[J].火力與指揮控制,2014,39(12):88-91.

[10] 周 芳,劉玉戰(zhàn),韓立巖.基于模糊集理論的知識融合方法研究[J].北京理工大學學報:社會科學版,2013,15(3):67-73.

[11] 何華燦.人工智能基礎理論研究的重大進展-評鐘義信的專著《高等人工智能原理》[J].智能系統(tǒng)學報,2015(1):163-166.

[12] 魯慧民,馮博琴,李 旭.面向多源知識融合的擴展主題圖相似性算法[J].西安交通大學學報,2010,44(2):20-24.

[13] Odia T,Misra S,Adewumi A.Evaluation of Hadoop/MapReduce framework migration tools[C]//Asia-Pacific world congress on computer science and engineering.[s.l.]:IEEE,2015:1-8.

[14] Li X,Dong X L,Lyons K,et al.Truth finding on the deep web:is the problem solved?[J].Proceedings of the VLDB Endowment,2012,6(2):97-108.

[15] Dong X L,Berti-Equille L,Srivastava D.Truth discovery and copying detection in a dynamic world[J].Proceedings of the VLDB Endowment,2009,2(1):562-573.

[16] Reuss P,Althoff K D,Henkel W,et al.Semi-automatic knowledge extraction from semi-structured and unstructured data within the OMAHA project[C]//International conference on case-based reasoning.[s.l.]:Springer International Publishing,2015:336-350.

Research on Heterogeneous Knowledge Fusion Algorithm underBig Data Environment

ZHANG Yao，LI Shu-yu，TANG Yue

(College of Computer Science,Shaanxi Normal University,Xi’an 710119,China)

In environment of big data,the integration of multi-source heterogeneous knowledge fusion has provided one of the most effective means and methods for researchers to discover the implicit,valuable and undetected knowledge from a lot of knowledge sources that are dispersed and heterogeneous.Aimed at the shortcomings of the current knowledge fusion methods,based on investigations on them under the big data environment,the existing data fusion methods have been employed,which are transplanted to the knowledge fusion reasonably.A kind of algorithm for multi-source heterogeneous knowledge fusion is proposed.In order to further improve the quality of the acquiring knowledge,an improved algorithm based on the dynamic selection of knowledge source granularity is proposed to obtain the appropriate size of the collection of knowledge sources and the true and reliable knowledge as possible.Its experimental verification is conducted based on the experimental platform constructed by Hadoop and MapReduce framework.Experimental results show that it is effective and feasible and effectively improves the performance of multi-source heterogeneous knowledge fusion algorithms.

big data;multi-source heterogeneous knowledge;knowledge fusion;fusion algorithm

2016-10-17

：2017-01-20 < class="emphasis_bold">網(wǎng)絡出版時間

時間：2017-07-11

國家自然科學基金資助項目(41271387)

張 瑤(1992-),女,碩士研究生,研究方向為移動云計算、大數(shù)據(jù)安全等;李蜀瑜，碩士生導師,副教授,博士,研究方向為移動云計算、大數(shù)據(jù)安全等。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1455.060.html

TP302

:A

:1673-629X(2017)09-0012-05

10.3969/j.issn.1673-629X.2017.09.003