[發(fā)明專利]異構(gòu)信息網(wǎng)絡(luò)中基于元路徑的節(jié)點(diǎn)查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011260846.0
• 申請(qǐng)日: 2020-11-12
• 公開(kāi)（公告）號(hào): CN112380360B
• 公開(kāi)（公告）日: 2022-03-18
• 發(fā)明（設(shè)計(jì)）人: 湯穎;徐珊
• 申請(qǐng)（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號(hào): G06F16/383
• 分類號(hào): G06F16/383;G06F16/33;G06F16/31;G06F40/242;G06F40/284;G06F40/30
• 代理公司: 杭州天正專利事務(wù)所有限公司 33201
• 代理人: 王兵

1.基于元路徑的異構(gòu)網(wǎng)絡(luò)相似節(jié)點(diǎn)查詢方法，包括以下步驟：

步驟1：生成路徑貪婪樹(shù)；根據(jù)輸入的源節(jié)點(diǎn)和短文本描述對(duì)貪婪樹(shù)進(jìn)行擴(kuò)展；在擴(kuò)展貪婪樹(shù)過(guò)程中進(jìn)行短文本的語(yǔ)義匹配；

1.1構(gòu)建貪婪樹(shù)根節(jié)點(diǎn)；貪婪樹(shù)的對(duì)象結(jié)點(diǎn)包括兩個(gè)部分的信息，一個(gè)是路徑擴(kuò)展過(guò)程中生成的節(jié)點(diǎn)對(duì)列表，其中節(jié)點(diǎn)對(duì)按照字典形式進(jìn)行存儲(chǔ)，將源節(jié)點(diǎn)保存成字典的鍵，目標(biāo)節(jié)點(diǎn)保存成字典的值；另一個(gè)為判斷當(dāng)前貪婪樹(shù)對(duì)象是否還能向下擴(kuò)展的標(biāo)記，當(dāng)標(biāo)記為True時(shí)，表示當(dāng)前對(duì)象可以繼續(xù)向下擴(kuò)展，標(biāo)記為False時(shí)表示當(dāng)前對(duì)象是路徑的終點(diǎn)或達(dá)到了元路徑的長(zhǎng)度閾值，連接貪婪樹(shù)對(duì)象的邊使用異構(gòu)信息網(wǎng)絡(luò)中的邊類型來(lái)標(biāo)注，貪婪樹(shù)的根節(jié)點(diǎn)由于沒(méi)有擴(kuò)展，其中源節(jié)點(diǎn)對(duì)應(yīng)的值為空；

1.2遞歸擴(kuò)展貪婪樹(shù)；在擴(kuò)展貪婪樹(shù)過(guò)程中，根據(jù)貪婪樹(shù)的邊類型判斷下一個(gè)節(jié)點(diǎn)是否為電影節(jié)點(diǎn)；若是電影節(jié)點(diǎn)，則進(jìn)行步驟1.3的語(yǔ)義匹配過(guò)程；若不是電影節(jié)點(diǎn)，則繼續(xù)步驟1.2遞歸擴(kuò)展貪婪樹(shù)過(guò)程，直到目標(biāo)節(jié)點(diǎn)出現(xiàn)在貪婪樹(shù)葉節(jié)點(diǎn)的值列表中，或路徑達(dá)到長(zhǎng)度閾值；

1.3對(duì)查詢輸入的短文本和電影文本簡(jiǎn)介進(jìn)行語(yǔ)義匹配；影視信息網(wǎng)絡(luò)是星型結(jié)構(gòu)的網(wǎng)絡(luò)，其中存在一個(gè)中心對(duì)象，其余類型的對(duì)象均與該中心對(duì)象相連，中心對(duì)象的屬性可以影響網(wǎng)絡(luò)中所有類型的關(guān)系；在影視信息網(wǎng)絡(luò)中，該中心對(duì)象是電影，影人之間的聯(lián)系都是通過(guò)電影產(chǎn)生的，同時(shí)電影內(nèi)容中包含豐富的語(yǔ)義，這些語(yǔ)義可以從節(jié)點(diǎn)屬性的角度突出節(jié)點(diǎn)間連接關(guān)系的特點(diǎn)；電影簡(jiǎn)介使用一小段文本概括電影內(nèi)容，可以理解成短文本數(shù)據(jù)；同時(shí)輸入的查詢文本是短文本數(shù)據(jù)，因此找到與查詢時(shí)輸入的短文本查詢語(yǔ)義相似的電影簡(jiǎn)介，可以得到符合查詢語(yǔ)義的電影內(nèi)容，從而生成符合短文本語(yǔ)義的元路徑；對(duì)電影簡(jiǎn)介和用戶輸入的短文本之間的語(yǔ)義匹配步驟包括：

(1)使用基于TextRank的開(kāi)源結(jié)巴分詞算法對(duì)查詢輸入的短文本進(jìn)行分詞；將輸入的短文本記為Q，分詞后每篇文檔由詞序列可表示為[q₀,q₁,…q_i…q_n]，其中q_i為第i個(gè)詞，n為詞序列長(zhǎng)度；

(2)使用定向Skip-Gram模型(Directional Skip-Gram,簡(jiǎn)稱DSG)得到每個(gè)詞的詞向量，記為V_qi；

(3)在得到詞向量后，通過(guò)公式(1)計(jì)算詞向量的均值，得到句向量；

(4)對(duì)電影的文本簡(jiǎn)介進(jìn)行分詞，將一篇電影簡(jiǎn)介記為T,分詞后可以得到詞序列[t₀,…t_j,…t_m]和每個(gè)詞的TF-IDF值作為權(quán)重，權(quán)重序列為[w₀,…w_j,…w_m]；

(5)采用了命名實(shí)體識(shí)別技術(shù)來(lái)處理電影文本簡(jiǎn)介中的人名，將識(shí)別為人名的詞從分詞結(jié)果中刪除；

(6)對(duì)電影簡(jiǎn)介分詞后的詞匯進(jìn)行詞性分析，過(guò)濾掉動(dòng)詞、形容詞、副詞修飾詞，保留名詞；

(7)使用DSG模型得到每個(gè)詞t_j的詞向量V_tj，然后通過(guò)公式(2)計(jì)算加權(quán)平均句向量V_T；

(6)基于余弦相似度度量得到兩段文本的相似性，計(jì)算公式為：

步驟2：確定元路徑序列；首先遍歷貪婪樹(shù)得到邊類型序列，然后按照邊類型序列確定節(jié)點(diǎn)類型序列；對(duì)生成的貪婪樹(shù)進(jìn)行遍歷，從中分離出連接輸入節(jié)點(diǎn)對(duì)的路徑；L為路徑集合，在L中保存所有可能的元路徑邊序列；將根節(jié)點(diǎn)記為第i層的第j個(gè)節(jié)點(diǎn)，此時(shí)i＝0，j＝0；

2.1從根節(jié)點(diǎn)開(kāi)始向下遍歷；根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)，貪婪樹(shù)第i+1層的第j個(gè)節(jié)點(diǎn)為下一節(jié)點(diǎn)，此處j＝0；將連接當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)的邊放入當(dāng)前的路徑序列l(wèi)中，將下一節(jié)點(diǎn)的字典值也就是目標(biāo)節(jié)點(diǎn)集合的長(zhǎng)度記為該節(jié)點(diǎn)的出度；

2.2更新當(dāng)前節(jié)點(diǎn)為上一步的下一節(jié)點(diǎn)，下一節(jié)點(diǎn)為貪婪樹(shù)第i+1層第j個(gè)葉節(jié)點(diǎn),此處j＝0；若下一節(jié)點(diǎn)的標(biāo)記為True，將連接當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)的邊放入當(dāng)前的路徑序列l(wèi)中，將下一節(jié)點(diǎn)的字典值也就是目標(biāo)節(jié)點(diǎn)集合的長(zhǎng)度記為該節(jié)點(diǎn)的出度；將當(dāng)前的路徑序列l(wèi)保存在集合L中，并令j＝j(luò)+1，進(jìn)行步驟2.3；否則，判斷下一節(jié)點(diǎn)是否還有擴(kuò)展邊，若有則將連接當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)的邊放入當(dāng)前的路徑序列l(wèi)中，將下一節(jié)點(diǎn)的字典值也就是目標(biāo)節(jié)點(diǎn)集合的長(zhǎng)度記為該節(jié)點(diǎn)的出度；令i＝i+1，j＝0，重復(fù)步驟2.2；若下一節(jié)點(diǎn)沒(méi)有擴(kuò)展邊，令j＝j(luò)+1，進(jìn)行步驟2.3；

2.3更新下一節(jié)點(diǎn)為貪婪樹(shù)第i+1層第j個(gè)葉節(jié)點(diǎn)；若下一節(jié)點(diǎn)的標(biāo)記為True，將連接當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)的邊放入當(dāng)前的路徑序列l(wèi)中，將下一節(jié)點(diǎn)的字典值也就是目標(biāo)節(jié)點(diǎn)集合的長(zhǎng)度記為該節(jié)點(diǎn)的出度；將當(dāng)前的路徑序列l(wèi)保存在集合L中，并令j＝j(luò)+1，進(jìn)行步驟2.3；否則，判斷下一節(jié)點(diǎn)是否還有擴(kuò)展邊，若有則將連接當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)的邊放入當(dāng)前的路徑序列l(wèi)中，將下一節(jié)點(diǎn)的字典值也就是目標(biāo)節(jié)點(diǎn)集合的長(zhǎng)度記為該節(jié)點(diǎn)的出度；令i＝i+1，j＝0，重復(fù)步驟2.2；若下一節(jié)點(diǎn)沒(méi)有擴(kuò)展邊，令j＝j(luò)+1，進(jìn)行步驟2.3；

2.4完成上述遍歷后，得到包含邊類型序列的元路徑集合L＝{l₀,…l_i,…}；對(duì)L中的每條元路徑l_i＝{t₀,…,t_j,…}，根據(jù)其中的邊類型t_j確定節(jié)點(diǎn)類型；最終得到包含節(jié)點(diǎn)類型序列和邊類型序列的完整元路徑；

步驟3：計(jì)算元路徑的重要度；首先根據(jù)影響元路徑重要度的因素，定義元路徑重要度的計(jì)算公式；借助貪婪樹(shù)葉節(jié)點(diǎn)中的實(shí)例節(jié)點(diǎn)數(shù)量，計(jì)算元路徑的重要度，元路徑的重要度計(jì)算公式為：

I_s,t(P)＝S_s,t(P)*R_s,t(P)*Penalty(|P|)(P∈P_s→t)(4)

其中，重要度分為S_s,t(P)，R_s,t(P)和Penalty(|P|)三個(gè)部分；

3.1計(jì)算長(zhǎng)度懲罰函數(shù)；從步驟2得到的元路徑中獲取元 路徑長(zhǎng)度，使用β^|P|作為懲罰函數(shù)，其中β是一個(gè)取值為0.5的衰減系數(shù)；

3.2計(jì)算元路徑稀有度；

稀有度計(jì)算函數(shù)用于評(píng)估在給定異構(gòu)信息網(wǎng)絡(luò)G＝(V，E)中，元路徑P在與輸入的節(jié)點(diǎn)對(duì)s,t相似的其他節(jié)點(diǎn)對(duì)中的稀有程度，使用D_s,t來(lái)表示與輸入節(jié)點(diǎn)對(duì)相似的節(jié)點(diǎn)對(duì)，其定義為：

D_s,t＝D_t∪D_s (5)

其中，

D_t中不包括t,D_s中不包括s，元路徑稀有性可以通過(guò)公式(8)計(jì)算得到；

3.3計(jì)算元路徑強(qiáng)度；元路徑重要度支持函數(shù)為：

S_s,t(P)＝Strength(P)*MNIs_s,t(P) (9)

其中，MNIs(p)計(jì)算元路徑P中的最小實(shí)例數(shù)，計(jì)算如公式(10)所示，p_i為元路徑上第i個(gè)節(jié)點(diǎn)的實(shí)例數(shù)量；

Strength(p)計(jì)算元路徑P的強(qiáng)度系數(shù)，公式(11)定義了計(jì)算方法；假設(shè)由公式(10)得到的擁有最小實(shí)例數(shù)的節(jié)點(diǎn)為A，節(jié)點(diǎn)A的出度為O(A)，節(jié)點(diǎn)A的入度為I(A)；當(dāng)節(jié)點(diǎn)A為電影節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)A的出度通過(guò)公式(12)計(jì)算得到，p_A為節(jié)點(diǎn)A的實(shí)例集合；由節(jié)點(diǎn)A實(shí)例集合中的每個(gè)節(jié)點(diǎn)的向量與短文本向量的相似度求和得到節(jié)點(diǎn)A的出度；

當(dāng)A＝Movie時(shí),

3.4計(jì)算元路徑重要度；通過(guò)步驟3.1，3.2，3.3分別計(jì)算得到元路徑長(zhǎng)度衰減系數(shù)，稀有度和強(qiáng)度后，根據(jù)公式(4)計(jì)算最終的元路徑重要度；

步驟4：結(jié)合多條元路徑生成查詢實(shí)例；符合元路徑語(yǔ)義的實(shí)例節(jié)點(diǎn)對(duì)在元路徑的語(yǔ)義上具有較高的相似性；因此要得到查詢結(jié)果實(shí)例，只需要找到在每一條元路徑語(yǔ)義上都有較高相似性的節(jié)點(diǎn)對(duì)；

4.1計(jì)算節(jié)點(diǎn)對(duì)基于元路徑的相似性；節(jié)點(diǎn)對(duì)根據(jù)不同元路徑的相似性計(jì)算公式為：

其中，ρ_ei(v_i,C_i+1)表示類型為C_i+1，根據(jù)邊e_i連接到節(jié)點(diǎn)v_i的節(jié)點(diǎn)x的集合；P^i...n表示元路徑中從節(jié)點(diǎn)C_i到C_n的子序列，α為固定參數(shù)，設(shè)置為0.5；當(dāng)節(jié)點(diǎn)x的類型C_i+1為電影時(shí)，使用電影文本簡(jiǎn)介和查詢短文本的相似度和∑sim(V_x，V_Q)來(lái)替代公式(13)中的|ρ_ei(v_i,C_i+1)|；

4.2計(jì)算節(jié)點(diǎn)對(duì)實(shí)體s和t之間的相似性；使用線性聚合函數(shù)計(jì)算實(shí)體s和t之間的相似性σ(s,t|P)，將元路徑對(duì)應(yīng)的重要度作為相似性的權(quán)重，聚合函數(shù)為：

其中，I_j表示不同元路徑P_j對(duì)應(yīng)的重要度；

4.3根據(jù)相似性矩陣得到查詢實(shí)例；得到基于元路徑的節(jié)點(diǎn)相似性后，為每條元路徑計(jì)算一個(gè)相似性矩陣；若影人節(jié)點(diǎn)的數(shù)量為m，相似性矩陣的大小為m×m，將元路徑P的相似性矩陣記為S_p：

每條元路徑第一次被生成時(shí)，就構(gòu)建好相應(yīng)的相似性矩陣，這些矩陣可以被重復(fù)利用，每次結(jié)合多條元路徑進(jìn)行查詢時(shí)，只需要選取對(duì)應(yīng)元路徑的相似性矩陣，記錄所有矩陣相同位置處值不為0的索引和值，根據(jù)索引即可得到滿足所有元路徑語(yǔ)義的節(jié)點(diǎn)對(duì)，計(jì)算這些節(jié)點(diǎn)對(duì)的相似性，即可得到查詢結(jié)果。