周 凱, 周 宏

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

0 引言

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

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

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

1 問(wèn)題分析與描述

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

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

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

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

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

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

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

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

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

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

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

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

假設(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)計(jì)算；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ù)。

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

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

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

(2)

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

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

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

(3)

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

(4)

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

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

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

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

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

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

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

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

r←用戶注冊(cè)號(hào)碼發(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

} ∥計(jì)算號(hào)碼發(fā)生變化的時(shí)間間隔

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 ++

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

然后計(jì)算轉(zhuǎn)移矩陣M，利用循環(huán)迭代計(jì)算數(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)

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

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

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

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

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

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

4 結(jié)語(yǔ)

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