一種多源數(shù)據(jù)融合過程中的實(shí)體關(guān)聯(lián)性計算方法

周 凱, 周 宏

(1.重慶警察學(xué)院信息安全系, 重慶 401331； 2.重慶市公安局網(wǎng)絡(luò)安全保衛(wèi)總隊, 重慶 401120)

0 引言

隨著信息技術(shù)的高速發(fā)展，社會數(shù)據(jù)化程度得到不斷提升，數(shù)據(jù)源的多樣化、數(shù)據(jù)量的巨大化以及數(shù)據(jù)集的關(guān)聯(lián)化為信息的獲取與分析提供了更為有利的條件，通過對多源數(shù)據(jù)進(jìn)行組合或綜合，利用多源數(shù)據(jù)的交叉印證與關(guān)聯(lián)分析，可得到比單一數(shù)據(jù)源更精確、更全面的信息。在當(dāng)前大數(shù)據(jù)時代，針對多源數(shù)據(jù)的融合已成為大數(shù)據(jù)分析處理的關(guān)鍵環(huán)節(jié)[1-5]，尤其在公共安全領(lǐng)域中，基于多數(shù)據(jù)源融合的信息高效查詢和分析，更有利于有價值情報的獲取，為公安辦案提供線索。

然而，由于數(shù)據(jù)管理系統(tǒng)在數(shù)據(jù)采集過程中的記錄不準(zhǔn)、人為操作等原因，錯誤數(shù)據(jù)、過時數(shù)據(jù)等數(shù)據(jù)不一致導(dǎo)致多個數(shù)據(jù)源對同一實(shí)體的聯(lián)系存在沖突，因此，針對數(shù)據(jù)不確定信息的處理一直是多數(shù)據(jù)源融合所面臨的主要問題之一，相關(guān)的解決方法、技術(shù)等學(xué)界已有一些研究。如：Yin等人[6]針對Web數(shù)據(jù)源相互關(guān)聯(lián)的情況，提出了如何從多個數(shù)據(jù)源沖突信息中為每一個真實(shí)對象找出最準(zhǔn)確的描述；王繼奎等人[7]提出了一種非對稱的數(shù)據(jù)值關(guān)聯(lián)度算法，解決了主數(shù)據(jù)集成中常出現(xiàn)的因簡寫、少寫、位置調(diào)換、錯誤書寫等因素引起的多業(yè)務(wù)系統(tǒng)文本數(shù)據(jù)沖突問題；張志強(qiáng)等人[8]考慮到文本數(shù)據(jù)值之間相似性的判斷，并結(jié)合數(shù)據(jù)源可信度及其依賴關(guān)系的計算，提高了從眾多沖突數(shù)據(jù)中找到正確數(shù)據(jù)值的精度。在多數(shù)據(jù)源融合過程中，數(shù)據(jù)沖突的處理涉及到很多具體的方法與技術(shù)，基于不同的系統(tǒng)環(huán)境、數(shù)據(jù)特征等因素，針對實(shí)際的應(yīng)用場景或問題，其方法和技術(shù)不盡相同。

面對在滿足公安應(yīng)用場景及業(yè)務(wù)需求中所遇見的多數(shù)據(jù)源融合過程中同一單值屬性的實(shí)體對象關(guān)聯(lián)多個對象值問題，即實(shí)體對象之間的關(guān)聯(lián)產(chǎn)生多義性問題，本文基于應(yīng)用場景的系統(tǒng)環(huán)境和業(yè)務(wù)數(shù)據(jù)特征，提出了一種結(jié)合時間屬性權(quán)值和數(shù)據(jù)源權(quán)重的多數(shù)據(jù)源DatasourceRank算法，實(shí)現(xiàn)對實(shí)體對象之間真實(shí)度計算。該算法僅對實(shí)體對象相關(guān)聯(lián)的數(shù)據(jù)進(jìn)行計算，以數(shù)據(jù)源為基準(zhǔn)單位，結(jié)合實(shí)體關(guān)系的時間屬性以及各數(shù)據(jù)源權(quán)重，計算實(shí)體對象之間的關(guān)聯(lián)度，從而發(fā)現(xiàn)當(dāng)前的實(shí)體對象之間真實(shí)關(guān)聯(lián)關(guān)系。其優(yōu)點(diǎn)在于，可基于查詢信息實(shí)時進(jìn)行計算，并依據(jù)關(guān)聯(lián)度高低向用戶推薦檢索結(jié)果，為業(yè)務(wù)分析工作提供更加精準(zhǔn)的信息。

1 問題分析與描述

在本應(yīng)用場景中，數(shù)據(jù)平臺中的數(shù)據(jù)源有數(shù)百種，數(shù)據(jù)量多達(dá)兩萬多億條，且每天還以數(shù)十億條的量在不斷增加。但是，數(shù)據(jù)源中的數(shù)據(jù)來源復(fù)雜，質(zhì)量良莠不齊，多存在由于原始記錄不準(zhǔn)、更換號碼、人為操作等原因，造成不同數(shù)據(jù)源中同一個號碼可能關(guān)聯(lián)不同的用戶的情況，見圖1。當(dāng)出現(xiàn)這種情況時，如何高效計算該號碼與每個用戶的關(guān)聯(lián)度，找出當(dāng)前最有可能的使用人就是至關(guān)重要的問題。

圖1 同一號碼在不同數(shù)據(jù)源中與用戶之間的關(guān)聯(lián)關(guān)系

在本應(yīng)用場景中，時間屬性是重要的因素。比如，某個手機(jī)號碼在2002～2006年系甲使用，但2007年至今該號碼被甲銷號后，又由運(yùn)營商分配給乙使用，則該兩組數(shù)據(jù)均為真實(shí)數(shù)據(jù)，但從信息對于業(yè)務(wù)工作的價值度來看，后組數(shù)據(jù)的重要程度明顯要高于前者。

因此，本文主要研究的問題可描述為：給定一批數(shù)據(jù)源集合S={S1,S2,…,Sn}，數(shù)據(jù)源Si(1≤i≤n)中包含一部分與所查詢號碼num有關(guān)聯(lián)的數(shù)據(jù)集Si(num)，O={S1(num),S2(num),S3(num),…}代表所查詢號碼num在多個數(shù)據(jù)源都存在關(guān)聯(lián)數(shù)據(jù)集，通過計算數(shù)據(jù)源Si(1≤i≤n)中所查詢號碼num與相關(guān)聯(lián)用戶usr的概率Pi(num→usr)，并結(jié)合數(shù)據(jù)集中實(shí)體關(guān)系的時間屬性權(quán)值T(usr,num)以及數(shù)據(jù)源權(quán)重D=(D1,D2,…,Dn)，得到多源數(shù)據(jù)環(huán)境下所查詢號碼x與不同實(shí)體對象之間的關(guān)聯(lián)度，并依據(jù)其關(guān)聯(lián)值得到最具時效、準(zhǔn)確度最高的關(guān)聯(lián)對象。

2 基于多數(shù)據(jù)源的實(shí)體關(guān)系關(guān)聯(lián)度計算方法

基于多數(shù)據(jù)源的實(shí)體關(guān)系關(guān)聯(lián)度計算主要涉及實(shí)體關(guān)聯(lián)時間屬性權(quán)值的計算、數(shù)據(jù)源權(quán)重的計算以及所查詢號碼與各用戶關(guān)聯(lián)度的計算，見圖2。同時，針對本應(yīng)用場景，由于各數(shù)據(jù)源之間具有業(yè)務(wù)關(guān)聯(lián)性，因此，對數(shù)據(jù)源權(quán)重的計算借鑒了PageRank算法[9]中網(wǎng)頁權(quán)重的民主表決機(jī)制，利用與該數(shù)據(jù)源有關(guān)聯(lián)關(guān)系的其他數(shù)據(jù)源共同決定該數(shù)據(jù)源的權(quán)重，其能夠適應(yīng)數(shù)據(jù)維度的變化，通過多方投票，能夠較好解決數(shù)據(jù)質(zhì)量良莠不齊的問題。

圖2 實(shí)體關(guān)系關(guān)聯(lián)度計算流程圖

2.1 實(shí)體關(guān)系的時間屬性權(quán)值計算

如前所述，時間屬性是權(quán)衡該類業(yè)務(wù)數(shù)據(jù)中實(shí)體之間關(guān)系價值的重要因素之一，因此，以運(yùn)營商登記的用戶號碼注冊信息為基準(zhǔn)，結(jié)合同一用戶在不同數(shù)據(jù)源中的號碼記錄情況，計算這些號碼對于該用戶的時間權(quán)重。

假設(shè)T(usr,num)為用戶usr與號碼num的時間關(guān)系權(quán)值，當(dāng)用戶usr存在多個號碼注冊記錄信息時，用戶usr與各使用號碼的時間權(quán)值可表示為T(usr,num)={T(usr,num1),…,T(usr,numn)}，T的取值范圍在0.1～1之間，以0.1為單位逐級遞增。

θ(numi,numj)為用戶usr注冊號碼numi與注冊號碼numj的時間間隔。對θ(numi,numj)值進(jìn)行排序、分段統(tǒng)計，區(qū)間所對應(yīng)的θ值越大，用戶與對應(yīng)號碼的時間權(quán)重T越低；相反，θ值越小，T越高。當(dāng)θ值為0時，表示該用戶的號碼穩(wěn)定，未發(fā)生過變化，用戶與號碼的實(shí)體關(guān)系權(quán)重被賦予最大權(quán)值1。

2.2 數(shù)據(jù)源權(quán)重計算

假設(shè)D=(D1,D2,…,Dn)T為n維數(shù)據(jù)源權(quán)重值向量(n為數(shù)據(jù)源總數(shù))，M為轉(zhuǎn)移矩陣。

(1)

其中，mij表示數(shù)據(jù)源i到數(shù)據(jù)源j的概率，由公式(1)計算；eij表示數(shù)據(jù)源i與數(shù)據(jù)源j關(guān)聯(lián)的數(shù)據(jù)條數(shù)；Hi表示數(shù)據(jù)源i與其他數(shù)據(jù)源關(guān)聯(lián)的所有數(shù)據(jù)條數(shù)。

給定一個D的初始值D0，設(shè)初始時，每個數(shù)據(jù)源的數(shù)據(jù)源權(quán)重值為1/n，得到初始向量D0=[1/n1/n… 1/n]。通過多輪迭代求解：Dk=MTDk-1，最后收斂于‖Dk-Dk-1‖<ξ，即差別小于某個閾值，即迭代結(jié)果收斂。

2.3 所查詢號碼與各實(shí)體屬性的關(guān)聯(lián)度計算

由公式(2)計算所查詢號碼num在數(shù)據(jù)源i下與用戶usr的關(guān)聯(lián)概率Pi(num→usr)。

(2)

式中，G表示所查詢號碼num在數(shù)據(jù)源i下與用戶usr關(guān)聯(lián)的總次數(shù)；V表示所查詢號碼num在數(shù)據(jù)源i下存在的所有關(guān)聯(lián)總次數(shù)。

然后，結(jié)合之前所計算得到的時間權(quán)重T(usr,num)和數(shù)據(jù)源權(quán)重Di，對Pi(num→usr)進(jìn)行加權(quán)計算，得到加權(quán)值Wi(num→usr)，見公式(3)。

Wi(num→usr)=Pi(num→usr)×T(usr,num)×Di

(3)

最后，依據(jù)多個數(shù)據(jù)源的信息價值，由公式(4)計算出號碼num與用戶usr的關(guān)聯(lián)度P(num→usr)值。

(4)

基于所查詢號碼與用戶之間關(guān)聯(lián)度的計算結(jié)果進(jìn)行排序，按照關(guān)聯(lián)度值的排名順序向用戶推薦結(jié)果，其中，關(guān)聯(lián)度值最高的關(guān)聯(lián)關(guān)系即為該號碼當(dāng)前最有可能的使用人。

3 實(shí)驗(yàn)結(jié)果與分析

本文使用了1 500條公開電話號碼數(shù)據(jù)作為查詢數(shù)據(jù)，分別基于本文DatasourceRank算法和PageRank算法進(jìn)行關(guān)聯(lián)度值計算并排序，提取其結(jié)果進(jìn)行分析對比驗(yàn)證，其結(jié)果可見表1。

本文提出的DatasourceRank關(guān)聯(lián)度計算算法基于實(shí)際應(yīng)用場景中的數(shù)據(jù)特性，考慮了實(shí)體關(guān)系的時間價值、不同數(shù)據(jù)源權(quán)重等多種影響因素，其準(zhǔn)確率明顯更高，同時，由于其以數(shù)據(jù)源為基準(zhǔn)單位，僅對實(shí)體對象相關(guān)聯(lián)的數(shù)據(jù)進(jìn)行計算，所需要的時間開銷也有所降低。

以其中一個號碼“138*****883”為查詢對象進(jìn)行詳細(xì)分析，從業(yè)務(wù)大數(shù)據(jù)平臺中檢索相關(guān)數(shù)據(jù)，發(fā)現(xiàn)該號碼在4個數(shù)據(jù)源中存在多條記錄數(shù)據(jù)，該號碼與多個用戶之間存在交叉關(guān)聯(lián)性，見圖3，圖中橢圓形表示手機(jī)號碼，方形表示數(shù)據(jù)源，而圓形表示使用過該號碼的人。

圖3 所分析實(shí)體對象存在的關(guān)聯(lián)性

根據(jù)本文的DatasourceRank方法進(jìn)行計算。首先，進(jìn)行實(shí)體關(guān)系時間權(quán)重的計算，主要偽代碼如下：

T←初始化所有關(guān)系的時間權(quán)值均為1

r←用戶注冊號碼發(fā)生變化的記錄

remaider←t.length%10

offset←0∥偏移量

fori←0 ton-1

forj←iton

{

if r(i).id = r(j).id

t=r(j).time-r(i).time

} ∥計算號碼發(fā)生變化的時間間隔

sort(t) ∥從小到大進(jìn)行排序

fork←1 to 10

{

If (remaider>0)

{

for (t.length/10)*(k-1)+offset to

(t.length/10)*k-1 offset

T=1-0.1*(k-1)

}else

{

for (t.length/10)*(k-1) to (t.length/10)*k-1

T=1-0.1*(k-1)

}

offset ++

}∥基于分段對其關(guān)系賦予不同時間權(quán)重值，以0.1為基本單位，從1到0.1逐級遞減

然后計算轉(zhuǎn)移矩陣M，利用循環(huán)迭代計算數(shù)據(jù)源權(quán)重值，主要偽代碼如下：

D←1.0/num ∥初始化各數(shù)據(jù)源權(quán)值

for i←0 to num

for j←0 to num

{

if i=j

tmpTrans[i][j] ←0

esle

tmpTrans[i][j] ←arrCount.get(i)

} ∥計算關(guān)聯(lián)記錄數(shù)

for i←0 to num

{

sum←0

for i←0 to num

sum += tmpTrans[j][i]

for j←0 to num

arrTrans = tmpTrans[j][i]/sum

} ∥構(gòu)建轉(zhuǎn)移矩陣

do { ∥迭代計算各數(shù)據(jù)源權(quán)值

S=D;

D=arrTrans.multiply(S)

}

While(D與S結(jié)果不相近) ∥如果小數(shù)點(diǎn)后8位不相同,則繼續(xù)迭代

return D; ∥如果前后迭代結(jié)果很接近,則返回D

當(dāng)Dk≈Dk-1時，則表示第k輪迭代過后，Dk和Dk-1非常接近，即D最終收斂，此時計算終止，最終的D就是各數(shù)據(jù)源的權(quán)重值。本實(shí)驗(yàn)中，經(jīng)過18輪迭代達(dá)到收斂。最后，由公式(2)、(3)和(4)計算獲得計算結(jié)果，見表2。

表2 基于DatasourceRank算法的分析結(jié)果

表3是基于PageRank算法所獲得的排序結(jié)果。

將表2與表3對比可以看到，排序結(jié)果發(fā)生了變化，下面針對這些變化進(jìn)行分析：表3中排在第1的關(guān)聯(lián)用戶a在表2中排在了第2，表3的結(jié)果僅依據(jù)各用戶實(shí)體與所檢索號碼的關(guān)聯(lián)記錄頻次進(jìn)行計算和排序，號碼“138*****883”與用戶a的關(guān)聯(lián)記錄數(shù)最多，所以得到的關(guān)聯(lián)度值最高，被排在了第1，但從使用時間屬性上看，用戶b使用此號碼的最后時間明顯要比用戶a晚，從本應(yīng)用的業(yè)務(wù)價值來說，用戶b的價值比用戶a的價值更重要。

表3 基于PageRank算法的分析結(jié)果

使用本文算法進(jìn)行關(guān)聯(lián)度計算排序后，在表2中可見用戶b與號碼“138*****883”的時間關(guān)系和數(shù)據(jù)源業(yè)務(wù)權(quán)重值相對更重要，進(jìn)而基于加權(quán)計算后，得到的總關(guān)聯(lián)度值最高，故用戶b排在了結(jié)果的第一位，其結(jié)果更符合用戶的實(shí)際業(yè)務(wù)分析需求。

4 結(jié)語

本文針對目前存在的多數(shù)據(jù)源融合過程中，同一單值屬性的實(shí)體對象關(guān)聯(lián)多個對象值的問題進(jìn)行分析，基于數(shù)據(jù)管理的業(yè)務(wù)需求及公安應(yīng)用場景，提出了一種結(jié)合實(shí)體關(guān)系時間屬性權(quán)值和數(shù)據(jù)源權(quán)重的計算算法，通過加權(quán)計算的方式計算實(shí)體關(guān)系的關(guān)聯(lián)度值，使用戶在搜索時能迅速準(zhǔn)確地找到當(dāng)前與搜索內(nèi)容最相關(guān)的使用人。實(shí)證分析的結(jié)果表明該算法模型的有效性，對面向多數(shù)據(jù)源業(yè)務(wù)數(shù)據(jù)的情報分析工作提供了新的技術(shù)方法，未來若通過更大規(guī)模的數(shù)據(jù)驗(yàn)證后，可應(yīng)用到真實(shí)的業(yè)務(wù)數(shù)據(jù)關(guān)聯(lián)發(fā)掘檢索系統(tǒng)中。