王駿，陸萬榮，胡勇

（昆明能訊科技有限責(zé)任公司，云南 昆明 650200 ）

0 前言

目前在電力行業(yè)中，從采購到生產(chǎn)、從故障到作業(yè)、從管理到實施，所有過程都在信息系統(tǒng)中留下執(zhí)行記錄和跟蹤記錄數(shù)據(jù)[1]。數(shù)據(jù)的不斷積累產(chǎn)生了大量隱形資源，但是也給數(shù)據(jù)存儲和數(shù)據(jù)使用造成了巨大壓力，導(dǎo)致大量的有用信息閑置在數(shù)據(jù)庫中，浪費了存儲空間也失去了數(shù)據(jù)價值。

檢索是從大量數(shù)據(jù)中獲得有用信息的基本手段之一，但是由于數(shù)據(jù)量急速增加，信息檢索使得本就處于巨大壓力下的存儲系統(tǒng)更加得雪上加霜，因此如何高效利用這些數(shù)據(jù)創(chuàng)造更大價值成為了數(shù)據(jù)科學(xué)家和相關(guān)從業(yè)者的研究熱點[2]。知識圖譜是人工智能的三大分支之一，淵源最早可追溯到語義網(wǎng)、邏輯描述和專家系統(tǒng)等，但是直到2012 才正式被谷歌的“Knowledge Graph”項目提出。這一技術(shù)的出現(xiàn)被業(yè)界所關(guān)注，為大數(shù)據(jù)的檢索和相關(guān)應(yīng)用支撐提供了新的解決思路[3-4]。在電力行業(yè)中，劉梓權(quán)、王慧芳等在2018 年基于知識圖譜研究了電力設(shè)備缺陷信息檢索方法[5]；中科院的郭蘊穎在2020 年設(shè)計實現(xiàn)了基于知識圖譜的電網(wǎng)信息搜索引擎[6]；國網(wǎng)北京公司的徐蕙、及洪泉等在2021 年發(fā)表了關(guān)于知識圖譜在智能電網(wǎng)語義搜索的研究成果[7]。

基于知識圖譜在大數(shù)據(jù)信息檢索的研究基礎(chǔ)上，針對檢索條件不全或者只有部分檢索條件極大地降低甚至限制了在圖譜中的信息檢索速度這一問題，本文提出一種基于邏輯圖譜模型快速信息檢索方法，在已有的實例知識圖譜模型上構(gòu)建邏輯圖譜模型，通過邏輯圖譜盡量補全檢索條件，從而提高知識圖譜的信息檢索速度。

1 實體及邏輯知識圖譜構(gòu)建

知識圖譜是一種基于圖的數(shù)據(jù)結(jié)構(gòu)，通常由節(jié)點（Point）和邊（Edge）組成，節(jié)點就是實體，可以將其理解為關(guān)系型數(shù)據(jù)庫中的一條記錄，每一個實體都有全局唯一ID 標(biāo)識，邊表示兩個實體之間的關(guān)系[8]。實體和關(guān)系統(tǒng)統(tǒng)構(gòu)成了知識關(guān)系網(wǎng)絡(luò)，因此知識圖譜更注重從“關(guān)系”的角度去發(fā)現(xiàn)、理解和解決問題。Neo4j 是一個高性能、嵌入式的、基于磁盤的、可自動持久的NoSQL 圖數(shù)據(jù)庫，數(shù)據(jù)結(jié)構(gòu)如圖1 所示。其他的典型NoSQL 還有Redis、HBase、MongoDB 等。

圖1 neo4j圖譜數(shù)據(jù)結(jié)構(gòu)

圖的存儲方式有兩種：一種是鄰接矩陣，一種是鄰接表，這兩種數(shù)據(jù)結(jié)構(gòu)都與圖密度相關(guān)[9]。簡單來說，節(jié)點多、關(guān)系少的稱之為稀疏圖（Sparse Graph），如圖2 左所示；節(jié)點少、關(guān)系多稱之為稠密圖（Dense Graph），如圖2右所示。鄰接矩陣方式使用兩個矩陣存儲圖，一維數(shù)組存儲節(jié)點信息，二維數(shù)組存儲關(guān)系信息。鄰接表使用一維數(shù)組存儲節(jié)點，單鏈表存儲每個節(jié)點的所有鄰接節(jié)點。

圖2 稀疏圖（左）和稠密圖（右）

對于圖1 中的圖可表示為G=(V,E)，其中V表示節(jié)點集合，E表示關(guān)系集合。鄰接矩陣需要記錄每兩個節(jié)點之間的關(guān)系，不論兩者是否存在關(guān)系，所以這種方式的空間復(fù)雜度為：O(|V|2)。而鄰接表，首先需要|V|個列表存儲每個節(jié)點的所有相鄰節(jié)點，因此鄰接表方式存儲的空間復(fù)雜度為：O(|V|+|E|)。綜上分析，鄰接矩陣適合存儲稠密圖，鄰接表更適合稀疏圖。

1.1 實例圖譜構(gòu)建

在Neo4j 圖數(shù)據(jù)庫中，標(biāo)簽（Label）和關(guān)系(Relationship)是層級最高的數(shù)據(jù)結(jié)構(gòu)，在不同的Label 下存儲著對應(yīng)的節(jié)點（Node），每個節(jié)點就是一個實體對象，同時為了更好地描述節(jié)點，每個節(jié)點都有其屬性（Property），全局唯一ID 就是默認(rèn)屬性；Relationship 描述兩個節(jié)點之間的關(guān)系，將本來相互獨立的節(jié)點彼此關(guān)聯(lián)起來，類似所謂的六度理論，就能構(gòu)成一個有復(fù)雜關(guān)系的知識網(wǎng)，同樣地，Relationship 也有屬性，可更詳細(xì)地描述節(jié)點之間的關(guān)系信息。

如表1 所示，記錄了本次構(gòu)建電網(wǎng)信息知識圖譜所需要的數(shù)據(jù)信息（為防止信息泄露部分信息以* 號代替）。在構(gòu)建實例圖譜模型過程中，共使用了19 個大類數(shù)據(jù)，各類Label 下節(jié)點數(shù)量不盡相同，且差異較大，如基準(zhǔn)電壓只有89 各節(jié)點，設(shè)備和用戶電壓Label 的節(jié)點數(shù)都在千萬以上。

表1 實例圖譜數(shù)據(jù)

圖3 展示了一部分電網(wǎng)信息圖譜，圖中每一個球表示一個節(jié)點，代表一個實體，節(jié)點之間顏色相同，表示屬于同一個Label，也就是說在Neo4j 圖譜中不同的Label 用不同的顏色表示。兩個節(jié)點和之間的黑色線條共同組成了一個關(guān)系，關(guān)系可以是有向的也可以是無向的，必須要說明的是，關(guān)系必須存在于節(jié)點與節(jié)點之間。

圖3 實例圖譜模型

1.2 邏輯圖譜構(gòu)建

邏輯圖譜仍然是一個圖譜，由節(jié)點和關(guān)系組成，邏輯圖譜是實例圖譜的高層級映射，認(rèn)為“如果兩個分別屬于Label A 類和Label B 標(biāo)簽的節(jié)點A和B之間存在關(guān)系￠，那么Label A和Label B 也存在關(guān)系￠”。如圖4 所示，是將實例圖譜進行映射后得到的完整邏輯圖譜。該圖譜中的節(jié)點只有一個顏色，表示只有一個Label 和一類Relationship，圖中的19 個節(jié)點分別對應(yīng)表1 中的19 個節(jié)點分別對應(yīng)表1 中的19個Label 名稱，也就是說將實例模型中的Label作為實例圖譜中的節(jié)點，如果某個實例圖譜有幾千或幾萬個類別，將其映射后也只有幾萬個節(jié)點，相比于實例模型中的節(jié)點數(shù)已經(jīng)大幅降低。

圖4 邏輯圖譜模型

2 基于Neo4j的Dijkstra算法

通過實例圖譜映射出高層級的邏輯模型就是為了減少節(jié)點數(shù)，快速找出節(jié)點之間最短路徑上存在的關(guān)系，再將其投射為實例模型所屬Label 節(jié)點之間的關(guān)系，從而補全查詢信息，加速檢索任務(wù)。因此，為了更快找出兩個節(jié)點之間的最短路徑，不能直接使用Cypher 語句查詢路徑，再排序找最短路徑，需要更有效率的方法來實現(xiàn)這一功能。該電網(wǎng)信息知識圖譜中邊（關(guān)系）沒有權(quán)值，并且檢索時也不考慮方向性，因此直接采用1956 年艾茲赫爾·戴克斯特拉提出的Dijkstra 算法[10]通過Python 實現(xiàn)最短路徑查詢。Dijkstra 算法的基本思想是找出源節(jié)點到其他所有節(jié)點的最短路徑，重復(fù)使用廣度優(yōu)先算法和貪心算法，直到遍歷完所有節(jié)點（注：每次遍歷節(jié)點數(shù)量都呈遞減趨勢）。

以圖1 中的圖譜為例，先定義兩個字典S和U，S存儲已經(jīng)求出最短路徑的節(jié)點以及路徑，U存儲未求出最短路徑的節(jié)點。首先初始化S和U：

式（1）表示源節(jié)點A到本身的最短路徑為A→A，到其他節(jié)點B、C、D、E、F的距離分別為1、無窮大、無窮大、無窮大，無窮大表示該節(jié)點與源節(jié)點不可直達(dá)，也稱“不可見”。接下來循環(huán)通過U更新S，直到S包含所有節(jié)點，從U可見A→B距離最短，所以更新S為式（2）。同時，以D節(jié)點作為中轉(zhuǎn)站，以判斷條件式（3）更新U，式中U處于當(dāng)前階段，如果滿足任意一條，則U更新為U[i]=(|A→B|+|B→i|)，|A→B| 和|B→i| 分別表示A到B的最短距離和B到i的最短距離。按照這中方式不斷更新S和U，直至遍歷結(jié)束。

以圖1 為Graph 的Dijkstra 算法流程如圖5所示：

圖5 Dijkstra算法流程

每次迭代S中節(jié)點增加，U中節(jié)點減少，最終S包含了所有節(jié)點，U為空，迭代結(jié)束。假設(shè)某個圖中節(jié)點數(shù)為n，關(guān)系數(shù)為m，平均每個節(jié)點的關(guān)系數(shù)k=m/n，則Dijkstra 的時間復(fù)雜度計算公式為：

式中，TEM表示獲取最短路徑的時間，TD表示刪除需要的時間，TDK表示修改所需時間，按照四種不同的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，時間復(fù)雜度如表2所示，使用優(yōu)先隊列的方式節(jié)約了每次尋找最短路徑節(jié)點的開銷，增加了更新節(jié)點的開銷。因此稀疏圖適合于優(yōu)先隊列，稠密圖適合于循環(huán)遍歷。

表2 時間復(fù)雜度比較

3 實例分析

為了驗證FRM-LG 在信息檢索中速度的優(yōu)勢，進行2 類實例驗證，每類3 個實例，詳細(xì)測試信息如表3 所示，表中實體抽取需要通過NLP 等技術(shù)處理，這里不再贅述；其次，為了解釋更為清晰，且由于篇幅限制和數(shù)據(jù)保護，表中實體用對應(yīng)中文表示。本次實驗檢索運行環(huán)境為：CentOS Linux release 7.5.1804 (Core)，16G 內(nèi)存， Intel(R) Xeon(R) Silver 4210 CPU@ 2.20GHz， 基于Windows10，8.0G 內(nèi)存，Inter(R) Core(TM) i-9750H CPU @ 2.60GHZ，Anaconda3，Python3.6 執(zhí)行完成。

表3 實例檢索信息

將每個檢索場景分別運行50 次，分別記錄FRM-LG 檢索方法和實例圖譜的檢索方法（iRM-CG）的查詢時長，并繪制圖6 和圖7。

圖6 直線路徑檢索

圖7 分叉路徑檢索

首先，從兩種方法分別在檢索3、檢索2 和檢索4 的運行時長對比可以直接看出，F(xiàn)RMLG 的檢索速度相比iRM-CG 明顯提高。檢索1、檢索5 和檢索6 圖中僅展示了FRM-LG 方法的運行結(jié)果，主要原因是iRM-CG 檢索超時，未得到檢索結(jié)果。綜上對比分析結(jié)果證明了FRMLG 方法的有效性，并且還發(fā)現(xiàn)，如果檢索量比較大，iRM-CG 方法根本不能得到檢索結(jié)果，更談不上速度如何。

文中在邏輯圖譜上最短路徑搜索使用了Dijkstra 算法，圖8 展示了檢索1 和檢索6 分別在使用Dijkstra 算法和暴力法的情況下記錄了50 次迭代的運行情況，從圖中發(fā)現(xiàn)，不論是否使用Dijkstra 算法搜索最短路徑，檢索用時幾乎不變，圖中曲線也是幾乎重合。究其原因，本次實驗的實例模型，僅有19 個Label，映射至邏輯模型只有19 個節(jié)點，因此不能體現(xiàn)出Dijkstra 算法在最短路徑搜索上的優(yōu)越性。

圖8 Dijkstra算法與暴力搜索比較

4 結(jié)束語

本文提出了基于邏輯圖譜模型快速信息檢索方法，通過將原Neo4j 實例圖譜中的Label映射，搭建一個邏輯圖譜模型，兩個模型相結(jié)合，先在邏輯圖譜上進行最短路徑搜索，利用搜索結(jié)果補全查詢條件，從而提高在實例模型上的檢索速度。從6 個檢索場景的實驗結(jié)果也證明了該方法的有效性，能夠極大提高檢索速度。未來將構(gòu)建更為齊全的圖譜模型，增加節(jié)點的類別，來證明Dijkstra 算法在FRM-LG 方法中的積極作用。