劉莞玲，肖承志，傅仰耿

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

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

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

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

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

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

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

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

(1)

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

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

1.2 問題提出

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

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

2.1 歐氏局部敏感哈希算法

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

(2)

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

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

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

Pi=1-(1-Px)y。

(3)

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗驗證與分析

3.1 非線性函數(shù)擬合實驗

本實驗過程中將通過對一個數(shù)學(xué)函數(shù)的擬合來檢驗E2LSH-EBRB系統(tǒng)。在擬合非線性數(shù)學(xué)函數(shù)時，將比較擴展置信規(guī)則庫系統(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)建擴展置信規(guī)則庫時，函數(shù)的輸入值x為前提屬性，并且對x設(shè)定了7個均勻分布的參考值{0.0,0.5,1.0,1.5,2.0,2.5,3.0}；同時，為系統(tǒng)設(shè)定了5個評價等級，對應(yīng)的評價等級效用值依次為{-3.5,-2.0,-0.5,1.0,3.0}。設(shè)定好初始等級參數(shù)后，在x的取值范圍內(nèi)均勻地選擇1 000個數(shù)值，并根據(jù)數(shù)學(xué)函數(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個E2LSH哈希函數(shù)，根據(jù)實驗情況，參數(shù)r的取值為0.01。測試數(shù)據(jù)為在x的取值范圍內(nèi)均勻地選擇1 500個數(shù)值。在構(gòu)造和測試過程中，將以平均絕對誤差(Mean Absolute Error, MAE)作為評價指標(biāo)之一。

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

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

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

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

3.2 輸油管道泄漏仿真實驗

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

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

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

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

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

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

表2中列出了EBRB、BK-EBRB和不同r參數(shù)下的E2LSH-EBRB產(chǎn)生的模擬輸出的實驗結(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時，E2LSH-EBRB系統(tǒng)推理的效率最優(yōu)。在這一參數(shù)下，對比于BK-EBRB組合系統(tǒng)，效率和準(zhǔn)確率的差距并不是很大。

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

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

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

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

4 總 結(jié)

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