哈希索引的擴(kuò)展置信規(guī)則庫(kù)推理方法

劉莞玲，肖承志，傅仰耿

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350116)

專家系統(tǒng)是人工智能領(lǐng)域最活躍和最廣泛的應(yīng)用領(lǐng)域之一[1]。置信規(guī)則庫(kù)專家系統(tǒng)(Belief Rule Base，BRB)的理論依據(jù)是楊劍波等在2006年以D-S證據(jù)理論[2-3]、決策理論[4]、模糊理論[5]和傳統(tǒng)IF-THEN規(guī)則庫(kù)[6]為基礎(chǔ)而提出的基于證據(jù)推理算法的置信規(guī)則庫(kù)推理方法[7](belief Rule base Inference Methodology using the Evidential Reasoning approach, RIMER)。置信規(guī)則庫(kù)推理的過(guò)程是通過(guò)證據(jù)推理(Evidential Reasoning, ER)算法實(shí)現(xiàn)的[8-9]，相比于神經(jīng)網(wǎng)絡(luò)算法和支持向量機(jī)等“黑箱”方法，RIMER方法的推理過(guò)程具有更好的解釋性和透明性[10]。置信規(guī)則庫(kù)專家系統(tǒng)的一系列參數(shù)以及與規(guī)則相關(guān)的概率設(shè)置需要通過(guò)參數(shù)學(xué)習(xí)來(lái)獲得[11]。參數(shù)訓(xùn)練可以使用Matlab中的FMINCON函數(shù)[12]，或者用文獻(xiàn)[13-14]中提出的基于群智能算法的方法。

為了便于在更一般和更高級(jí)的應(yīng)用場(chǎng)景里，在不同類型的輸入數(shù)據(jù)格式下，能同時(shí)處理不精準(zhǔn)、不完整和具有不確定性的數(shù)據(jù)，Liu等提出了擴(kuò)展置信規(guī)則庫(kù)(Extended Belief Rule Base, EBRB)專家系統(tǒng)[15]。擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)優(yōu)化了系統(tǒng)構(gòu)建的過(guò)程，但推理過(guò)程的效率仍有提高的空間[16]。局部敏感哈希(Locality Sensitive Hashing, LSH)算法是可以處理海量高維數(shù)據(jù)，并且盡量不損失數(shù)據(jù)之間相似性的一種哈希算法[17]。因此，筆者提出基于局部敏感哈希算法對(duì)擴(kuò)展置信規(guī)則庫(kù)建立局部敏感索引來(lái)查找最近鄰規(guī)則的優(yōu)化框架，從而達(dá)到提高效率的目的。

1 擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)

1.1 擴(kuò)展置信規(guī)則庫(kù)的組成與推理

擴(kuò)展置信規(guī)則庫(kù)主要由一組無(wú)序的置信規(guī)則組成，每條規(guī)則包括前提屬性和結(jié)果兩個(gè)部分。這兩個(gè)部分都嵌入了置信度的概念，規(guī)則的前后兩部分都以分布式的結(jié)構(gòu)表示。

擴(kuò)展置信規(guī)則庫(kù)可以表示為R={R1,R2,…,RL}，L表示擴(kuò)展置信規(guī)則庫(kù)中規(guī)則的數(shù)量，第k條規(guī)則可以表示為

IF{A,αk},THEN{(D1,β1,k),(D2,β2,k),…,(DN,βN,k)} 。

(1)

在進(jìn)行系統(tǒng)推理之前，需要構(gòu)建擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)。Liu等提出了一種數(shù)據(jù)驅(qū)動(dòng)的構(gòu)建擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)的方法[16]。根據(jù)輸入數(shù)據(jù)構(gòu)建出置信規(guī)則后，需要設(shè)置每一條置信規(guī)則相對(duì)應(yīng)的規(guī)則權(quán)重θk，以及規(guī)則中每一個(gè)前提屬性的權(quán)重δi[1]。由于規(guī)則之間可能存在不一致性[18]，所以需要對(duì)規(guī)則進(jìn)行相似性度量后，再得出每條規(guī)則的權(quán)重值。

擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)的推理基礎(chǔ)為證據(jù)推理算法，通過(guò)證據(jù)推理算法對(duì)置信規(guī)則的分析來(lái)獲得最終的評(píng)價(jià)等級(jí)。在執(zhí)行證據(jù)推理算法前，需要計(jì)算出規(guī)則相對(duì)于輸入信息的激活權(quán)重，并將結(jié)果置信度轉(zhuǎn)化為基本可信值[1]，再利用證據(jù)推理算法的相關(guān)公式[8-9]，即可獲得推理評(píng)價(jià)等級(jí)的分布式置信度。

1.2 問(wèn)題提出

相比于置信規(guī)則庫(kù)專家系統(tǒng)，擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)可直接將輸入信息轉(zhuǎn)化為有效的置信規(guī)則，避免了置信規(guī)則庫(kù)專家系統(tǒng)預(yù)設(shè)規(guī)則存在的維數(shù)災(zāi)難問(wèn)題[19]。然而，當(dāng)輸入信息過(guò)多而使得規(guī)則數(shù)量增大時(shí)，由于規(guī)則是無(wú)序存儲(chǔ)于擴(kuò)展置信規(guī)則庫(kù)中的，仍然需要遍歷所有的規(guī)則來(lái)計(jì)算規(guī)則的激活權(quán)重，使得推理的準(zhǔn)確率和效率有所下降。為了解決這一問(wèn)題，筆者引入了局部敏感哈希算法對(duì)置信規(guī)則建立哈希索引，以此來(lái)提高效率。

2 基于E2LSH索引的擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)

2.1 歐氏局部敏感哈希算法

歐氏局部敏感哈希算法(Exact Euclidean Locality Sensitive Hashing，E2LSH)是基于P-穩(wěn)定分布(P-Stable)的位置敏感哈希算法。E2LSH是利用了P-Stable在p=2情況下的正態(tài)分布來(lái)實(shí)現(xiàn)的，其函數(shù)族可以表示為

(2)

其中，r是映射空間的分段長(zhǎng)度；b∈(0,r),是一個(gè)隨機(jī)數(shù)；v為置信規(guī)則分布式模型轉(zhuǎn)化而得的歐氏空間數(shù)值向量；a為正態(tài)分布隨機(jī)向量。函數(shù)族中的不同哈希函數(shù)是由不同的a與b值決定的。利用E2LSH，可以對(duì)擴(kuò)展置信規(guī)則庫(kù)中的每一條規(guī)則生成相對(duì)應(yīng)的哈希值，同時(shí)將具有相同的哈希值的規(guī)則放入同一個(gè)哈希桶中，從而構(gòu)造局部敏感哈希索引。

在一般情況下，可以只選用一個(gè)E2LSH哈希函數(shù)構(gòu)造局部敏感索引。為了進(jìn)一步提高準(zhǔn)確率，可以選用y組，每組x個(gè)E2LSH哈希函數(shù)。對(duì)于兩條置信規(guī)則，只要某一組中的所有E2LSH對(duì)這兩條規(guī)則生成的哈希值完全相同時(shí)，就可以判定這兩條規(guī)則為相似規(guī)則。

假設(shè)一個(gè)E2LSH將兩條規(guī)則判定為相似規(guī)則的概率為P，則最終得出的概率公式為

Pi=1-(1-Px)y。

(3)

2.2 基于E2LSH索引的擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)的構(gòu)建步驟

為方便敘述，下文將基于E2LSH的擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)稱為E2LSH-EBRB系統(tǒng)。由于該系統(tǒng)只對(duì)已生成的規(guī)則建立E2LSH索引，所以到規(guī)則生成這一步之前的所有步驟與擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)相同。

構(gòu)建基于E2LSH的局部敏感哈希表的步驟如下：

步驟1 選取y組，每組x個(gè)E2LSH哈希函數(shù)，然后在正態(tài)分布中選取x·y組隨機(jī)變量，構(gòu)造出x·y個(gè)a向量，同時(shí)選取合適的r值，并生成x·y個(gè)b值，這樣即可構(gòu)造出E2LSH函數(shù)族。

步驟2 對(duì)于每一組E2LSH函數(shù)，分別根據(jù)置信規(guī)則數(shù)值向量生成一組哈希值，將這組哈希值相同的置信規(guī)則放入同一個(gè)哈希桶中，并構(gòu)造該組哈希表，最后生成多組互相獨(dú)立的哈希表。

完成局部敏感的哈希索引的構(gòu)建。

2.3 基于E2LSH索引的擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)的規(guī)則搜索

E2LSH-EBEB系統(tǒng)的搜索策略為：利用構(gòu)造的哈希表索引，篩選規(guī)則并計(jì)算輸入信息的哈希值，將滿足與輸入信息的其中一份哈希值相同的規(guī)則篩選出來(lái)，用于激活推理。具體步驟如下：

步驟1 用生成E2LSH哈希函數(shù)族對(duì)輸入信息生成對(duì)應(yīng)于每個(gè)哈希表的哈希值。

步驟2 對(duì)每個(gè)哈希表，將該哈希表中與輸入信息對(duì)應(yīng)于該表的哈希值相同的所有規(guī)則取出。

步驟3 對(duì)取出的多組規(guī)則進(jìn)行去重合并，這些規(guī)則即是通過(guò)哈希表獲得的輸入數(shù)據(jù)的近鄰規(guī)則。如果最終獲得的規(guī)則列表為空，此時(shí)的策略是單獨(dú)為這組輸入遍歷所有的規(guī)則。

2.4 E2LSH-EBRB與擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)的效率比較

E2LSH-EBRB系統(tǒng)在構(gòu)建過(guò)程中，需要額外保存哈希表和哈希函數(shù)，因此構(gòu)建過(guò)程會(huì)增加一些時(shí)間和空間上的額外開(kāi)銷。但在推理過(guò)程中，筆者提出的方法在規(guī)則搜索上的時(shí)間開(kāi)銷顯著減少。

3 實(shí)驗(yàn)驗(yàn)證與分析

3.1 非線性函數(shù)擬合實(shí)驗(yàn)

本實(shí)驗(yàn)過(guò)程中將通過(guò)對(duì)一個(gè)數(shù)學(xué)函數(shù)的擬合來(lái)檢驗(yàn)E2LSH-EBRB系統(tǒng)。在擬合非線性數(shù)學(xué)函數(shù)時(shí)，將比較擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)和E2LSH-EBRB系統(tǒng)的效率和推理準(zhǔn)確性。

選用的非線性數(shù)學(xué)函數(shù)為

f(x)=xcos(x2)-sin(x2), 0.0≤x≤3.0 。

(4)

在構(gòu)建擴(kuò)展置信規(guī)則庫(kù)時(shí)，函數(shù)的輸入值x為前提屬性，并且對(duì)x設(shè)定了7個(gè)均勻分布的參考值{0.0,0.5,1.0,1.5,2.0,2.5,3.0}；同時(shí)，為系統(tǒng)設(shè)定了5個(gè)評(píng)價(jià)等級(jí)，對(duì)應(yīng)的評(píng)價(jià)等級(jí)效用值依次為{-3.5,-2.0,-0.5,1.0,3.0}。設(shè)定好初始等級(jí)參數(shù)后，在x的取值范圍內(nèi)均勻地選擇1 000個(gè)數(shù)值，并根據(jù)數(shù)學(xué)函數(shù)分別計(jì)算出真實(shí)函數(shù)值，然后將這1 000份數(shù)據(jù)作為系統(tǒng)的初始構(gòu)造數(shù)據(jù)，用前文所述的算法構(gòu)建出E2LSH-EBRB系統(tǒng)。在構(gòu)建的系統(tǒng)中，哈希函數(shù)的組數(shù)為22組，每組含有5個(gè)E2LSH哈希函數(shù)，根據(jù)實(shí)驗(yàn)情況，參數(shù)r的取值為0.01。測(cè)試數(shù)據(jù)為在x的取值范圍內(nèi)均勻地選擇1 500個(gè)數(shù)值。在構(gòu)造和測(cè)試過(guò)程中，將以平均絕對(duì)誤差(Mean Absolute Error, MAE)作為評(píng)價(jià)指標(biāo)之一。

圖1為擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)對(duì)非線性數(shù)學(xué)函數(shù)的擬合圖，可以發(fā)現(xiàn)擴(kuò)展置信規(guī)則庫(kù)的模擬輸出與函數(shù)的標(biāo)準(zhǔn)輸出有較大的差距。擬合效果不理想，這是由于遍歷規(guī)則的策略對(duì)推理結(jié)果的干擾造成的。圖2為E2LSH-EBRB系統(tǒng)的函數(shù)擬合圖，顯然擬合效果有所提高，且擬合圖像的曲線與標(biāo)準(zhǔn)輸出圖像的曲線基本重合。

圖1 EBRB系統(tǒng)的函數(shù)擬合圖圖2 E2LSH-EBRB系統(tǒng)的函數(shù)擬合圖

表1中比較了擴(kuò)展置信規(guī)則庫(kù)和E2LSH-EBRB對(duì)非線性數(shù)學(xué)函數(shù)擬合的實(shí)驗(yàn)結(jié)果以及運(yùn)行時(shí)間。由表1可知，擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)在函數(shù)擬合過(guò)程中搜索規(guī)則的次數(shù)較多，從而使得系統(tǒng)推理過(guò)程的效率不高；而由于規(guī)則庫(kù)中存在許多與輸入數(shù)據(jù)無(wú)關(guān)聯(lián)的規(guī)則，遍歷時(shí)也會(huì)激活這些規(guī)則，從而對(duì)測(cè)試結(jié)果造成干擾，增大了平均絕對(duì)誤差值。而E2LSH-EBRB篩選出了近鄰規(guī)則參與推理，在提高系統(tǒng)推理的效率的同時(shí)，也提高了系統(tǒng)的準(zhǔn)確率。在不同的r參數(shù)下，E2LSH-EBRB系統(tǒng)的表現(xiàn)也不同，所以需要根據(jù)系統(tǒng)的情況來(lái)確定參數(shù)r的取值，否則或大或小都會(huì)影響推理的效率和準(zhǔn)確率。在擬合公式(4)的實(shí)驗(yàn)中，參數(shù)r的最佳取值為0.010。

表1 函數(shù)擬合效率與準(zhǔn)確率

3.2 輸油管道泄漏仿真實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證E2LSH-EBRB方法解決實(shí)際問(wèn)題的有效性，選擇英國(guó)的一條100多公里長(zhǎng)的輸油管道作為研究對(duì)象[20]，使用該輸油管道的真實(shí)泄漏數(shù)據(jù)對(duì)筆者提出的E2LSH優(yōu)化模型進(jìn)行驗(yàn)證。在輸油管道泄漏的問(wèn)題中，由于管道泄漏將會(huì)使管道中油液的流量和壓力發(fā)生變化，因此可以根據(jù)油管中輸入輸出的油液流量差(Flow Diff,FD)和油液對(duì)管道產(chǎn)生的平均壓力差(Pressure Diff, PD)來(lái)估計(jì)油管泄漏(Leak Size, LS)的大小。

對(duì)于本次輸油管道泄漏的仿真實(shí)驗(yàn)，根據(jù)真實(shí)輸油管道從正常狀態(tài)到發(fā)生管道泄漏25%的事故，選取了2 007組數(shù)據(jù)作為本次測(cè)試的數(shù)據(jù)。FD和PD作為擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)的輸入。通過(guò)輸入這兩個(gè)數(shù)值，推理出輸油管道的泄漏情況。LS即為規(guī)則的評(píng)價(jià)等級(jí)部分。在構(gòu)建的系統(tǒng)中，哈希函數(shù)的組數(shù)為5組，每組含有3個(gè)E2LSH哈希函數(shù)，根據(jù)實(shí)驗(yàn)情況，參數(shù)r的取值為0.005。根據(jù)專家經(jīng)驗(yàn)可以得出，F(xiàn)D的8個(gè)前提屬性參考值分別為{-11,-6,-3,-1,0,1,2,3}，PD的7個(gè)前提屬性參考值分別為{-0.061,-0.005,-0.002,0.000,0.005,0.010,0.060}，LS的5個(gè)評(píng)價(jià)等級(jí)參考值分別為{0,2,4,6,8}。構(gòu)建擴(kuò)展置信規(guī)則庫(kù)(EBRB)、BK-EBRB和E2LSH-EBRB的初始構(gòu)造數(shù)據(jù)是按一定比例從2 007組測(cè)試數(shù)據(jù)中選取出的1 500組數(shù)據(jù)。在構(gòu)造和測(cè)試過(guò)程中，將以平均絕對(duì)誤差作為評(píng)價(jià)指標(biāo)之一。

圖3至圖5分別為EBRB系統(tǒng)、BK-EBRB系統(tǒng)和E2LSH-EBEB系統(tǒng)的推理輸出與真實(shí)數(shù)據(jù)的比較。從圖中可以發(fā)現(xiàn)，擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)的輸出與真實(shí)數(shù)據(jù)的差異性是3個(gè)系統(tǒng)中最大的，這是由于無(wú)關(guān)聯(lián)規(guī)則造成的干擾。如圖4所示，BK-EBRB系統(tǒng)在規(guī)則查找上引入了基于BK樹(shù)的樹(shù)形索引優(yōu)化，因而獲得的推理輸出與真實(shí)輸出比較接近。

圖3 EBRB系統(tǒng)輸出和測(cè)試數(shù)據(jù)圖4 BK-EBRB系統(tǒng)輸出和測(cè)試數(shù)據(jù)

圖5 E2LSH-EBRB系統(tǒng)輸出和測(cè)試數(shù)據(jù)

而筆者提出的E2LSH局部敏感哈希優(yōu)化模型在規(guī)則查找上引入了局部敏感索引哈希桶，從而篩選出了與輸入信息近鄰的規(guī)則參與計(jì)算激活權(quán)重，在減少查找的規(guī)則數(shù)的同時(shí)，也避免了無(wú)關(guān)聯(lián)規(guī)則的干擾。所以在圖5中，E2LSH-EBRB系統(tǒng)的輸出與真實(shí)數(shù)據(jù)的輸出能夠很好地?cái)M合。綜合分析可得到，E2LSH-EBRB系統(tǒng)在準(zhǔn)確率上相比于擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)有很大的提高。

表2中列出了EBRB、BK-EBRB和不同r參數(shù)下的E2LSH-EBRB產(chǎn)生的模擬輸出的實(shí)驗(yàn)結(jié)果和各項(xiàng)評(píng)價(jià)指標(biāo)。由表2可知，EBRB系統(tǒng)的效率和準(zhǔn)確率明顯低于BK-EBRB和E2LSH-EBRB。比較和分析不同r參數(shù)下的E2LSH-EBRB可以發(fā)現(xiàn)，當(dāng)r=0.005時(shí)，E2LSH-EBRB系統(tǒng)推理的效率最優(yōu)。在這一參數(shù)下，對(duì)比于BK-EBRB組合系統(tǒng)，效率和準(zhǔn)確率的差距并不是很大。

表2 油管泄漏測(cè)試效率與準(zhǔn)確率

表3中給出了當(dāng)E2LSH哈希函數(shù)的組數(shù)和每組的函數(shù)數(shù)量不同的情況下，E2LSH-EBRB系統(tǒng)的各項(xiàng)測(cè)試指標(biāo)。由表3可以發(fā)現(xiàn)，當(dāng)哈希函數(shù)的組數(shù)和每組的函數(shù)數(shù)量增加時(shí)，由于產(chǎn)生了更多的相互獨(dú)立的哈希表，因此每次搜索哈希表時(shí)所用的時(shí)間會(huì)有所增加。但隨著數(shù)量的增加，系統(tǒng)推理的準(zhǔn)確率呈上升趨勢(shì)。影響因素有兩個(gè)方面，一方面是多個(gè)相互獨(dú)立的哈希表互相影響，減小了各自漏判近鄰規(guī)則的概率；另一方面，由于單個(gè)哈希表中采取了AND優(yōu)化，哈希函數(shù)數(shù)量的增加可以減少對(duì)近鄰規(guī)則誤判的概率，兩個(gè)因素相互影響，從而提高了系統(tǒng)的準(zhǔn)確率。

表3 不同參數(shù)下的E2LSH-EBRB測(cè)試效率與準(zhǔn)確率

因此，在實(shí)際應(yīng)用中，需要根據(jù)應(yīng)用情況對(duì)推理精度和推理效率的要求來(lái)選取哈希函數(shù)的組數(shù)和每組的函數(shù)數(shù)量。對(duì)于碰撞概率為0.5的情況，在選取哈希函數(shù)的組數(shù)和每組的函數(shù)數(shù)量后，應(yīng)滿足轉(zhuǎn)化后的碰撞概率保持為0.5不變。

4 總 結(jié)

針對(duì)擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)在推理過(guò)程中由于規(guī)則是無(wú)序的，且計(jì)算規(guī)則的激活權(quán)重時(shí)須遍歷所有規(guī)則，導(dǎo)致系統(tǒng)的推理效率不高的問(wèn)題，引入了基于正態(tài)分布的局部敏感哈希算法(E2LSH)。該算法為擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)的所有規(guī)則建立局部敏感的哈希索引表，通過(guò)查找索引哈希桶篩選出較少的近鄰規(guī)則來(lái)計(jì)算激活權(quán)重。相比于遍歷所有規(guī)則的擴(kuò)展置信規(guī)則庫(kù)系統(tǒng)，E2LSH-EBEB系統(tǒng)在推理效率上有了很大的提升；同時(shí)，也去除了無(wú)關(guān)聯(lián)規(guī)則對(duì)推理結(jié)果的干擾，提高了算法的推理準(zhǔn)確率。在實(shí)驗(yàn)部分，選用非線性函數(shù)的擬合實(shí)驗(yàn)和輸油管道的泄漏檢測(cè)仿真實(shí)驗(yàn)，證明了E2LSH索引優(yōu)化算法的有效性，并且說(shuō)明了不同的參數(shù)選取對(duì)E2LSH索引優(yōu)化模型的影響。筆者提出的方法在選取單一E2LSH函數(shù)時(shí)會(huì)對(duì)推理結(jié)果的準(zhǔn)確率造成較小的影響，但在采用多組E2LSH情況下，會(huì)大大減少碰撞概率，提高系統(tǒng)的穩(wěn)定性。未來(lái)將進(jìn)一步了解各參數(shù)的最優(yōu)選取方式，對(duì)比其他局部敏感哈希算法的優(yōu)劣，并對(duì)建立局部敏感索引的模型進(jìn)行更深層次優(yōu)化，提出更準(zhǔn)確、高效的推理方法。