基于邏輯知識(shí)圖譜的電網(wǎng)信息快速檢索方法

王駿，陸萬(wàn)榮，胡勇

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

0 前言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 實(shí)例圖譜模型

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

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

圖4 邏輯圖譜模型

2 基于Neo4j的Dijkstra算法

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

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

式（1）表示源節(jié)點(diǎn)A到本身的最短路徑為A→A，到其他節(jié)點(diǎn)B、C、D、E、F的距離分別為1、無(wú)窮大、無(wú)窮大、無(wú)窮大，無(wú)窮大表示該節(jié)點(diǎn)與源節(jié)點(diǎn)不可直達(dá)，也稱(chēng)“不可見(jiàn)”。接下來(lái)循環(huán)通過(guò)U更新S，直到S包含所有節(jié)點(diǎn)，從U可見(jiàn)A→B距離最短，所以更新S為式（2）。同時(shí)，以D節(jié)點(diǎn)作為中轉(zhuǎn)站，以判斷條件式（3）更新U，式中U處于當(dāng)前階段，如果滿(mǎn)足任意一條，則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é)點(diǎn)增加，U中節(jié)點(diǎn)減少，最終S包含了所有節(jié)點(diǎn)，U為空，迭代結(jié)束。假設(shè)某個(gè)圖中節(jié)點(diǎn)數(shù)為n，關(guān)系數(shù)為m，平均每個(gè)節(jié)點(diǎn)的關(guān)系數(shù)k=m/n，則Dijkstra 的時(shí)間復(fù)雜度計(jì)算公式為：

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

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

3 實(shí)例分析

為了驗(yàn)證FRM-LG 在信息檢索中速度的優(yōu)勢(shì)，進(jìn)行2 類(lèi)實(shí)例驗(yàn)證，每類(lèi)3 個(gè)實(shí)例，詳細(xì)測(cè)試信息如表3 所示，表中實(shí)體抽取需要通過(guò)NLP 等技術(shù)處理，這里不再贅述；其次，為了解釋更為清晰，且由于篇幅限制和數(shù)據(jù)保護(hù)，表中實(shí)體用對(duì)應(yīng)中文表示。本次實(shí)驗(yàn)檢索運(yùn)行環(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 實(shí)例檢索信息

將每個(gè)檢索場(chǎng)景分別運(yùn)行50 次，分別記錄FRM-LG 檢索方法和實(shí)例圖譜的檢索方法（iRM-CG）的查詢(xún)時(shí)長(zhǎng)，并繪制圖6 和圖7。

圖6 直線路徑檢索

圖7 分叉路徑檢索

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

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

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

4 結(jié)束語(yǔ)

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