知識系統決策規則的動態更新策略及等價矩陣計算

譚天樂

(1.上海航天控制技術研究所，上海 201109； 2. 上海市空間智能控制技術重點實驗室，上海 201109)

0 引言

航天是人工智能技術應用的重要領域，而人工智能在航天的應用可以追溯到20世紀70年代。航天領域中的人工智能系統有很大一部分是基于“符號主義”路線建立的各種專家系統。例如：針對深空探測，NASA在“旅行者”深空探測器上構建了一個包含140余條規則的專家系統DEVICER II[1-2]以快速執行行星觀測任務，“好奇號”火星探測器采用專家系統自主引導相機進行巡視探測；針對航天飛機，NASA先后開發和應用了液氧推進劑裝填專家系統(LOX)、發射前專家系統(PLES)、智能化信息管理系統(IMIS)、基于知識庫的自動測試系統(KATE)、發射過程專家系統(LPS-I)，貨倉規劃使用專家系統(EMPRESS)等；針對空間站，NASA研制了用于環境控制與生命保障專家系統FIXER，我國航天醫學研究所提出了空間站內基于專家系統的人機混合智能系統[3]；在空間遙感觀測上，美國的“地球觀測一號”衛星可以進行地表觀測目標的自主尋找與價值評估；此外也有學者研究了如何在航天器飛行任務規劃中采用專家系統[4]。

專家系統從邏輯思考、表達方法上模擬人類智能活動，基于數學邏輯和推理，實現知識的表達、應用，其主要形式為規則集或規則庫，是人工智能“符號主義”路線的主要理論方法。在專家系統中，知識獲取、規則生成通常依靠專家經驗的總結歸納，知識的學習一直以來是瓶頸問題，在定量分析上專家系統也面臨困難。

專家系統作為人工智能的重要理論基礎和應用技術方法，需要具備自主的知識學習能力，能夠根據學習樣例的變化進行知識的動態自適應學習和更新。在一個以決策規則形式進行知識表達的信息系統中，當產生決策規則的學習樣本發生動態變化時，知識庫中的決策規則需要相應進行調整。如果在樣本集發生變化后對信息系統的所有樣本進行整體的規則獲取，因沒有充分利用過去所獲得的知識，將導致大量不必要的重復運算。因此需要解決當知識系統中樣本發生變化時，基于已有決策規則進行決策規則動態學習和調整的問題。

在對知識系統進行屬性約簡以及求核上，常見的方法有基于區分矩陣/差別矩陣[5-6]、遺傳算法[7]等等。在對知識系統中所有樣本進行決策規則的值約簡，獲取全局決策規則上，國內外已經提出了多種方法[8-10]。在決策規則的動態更新上，文獻[11-17]分別介紹了基于區分矩陣、決策矩陣、基于元信息、基于專家先驗知識等幾種規則動態更新算法或其改進。但這些方法在規則更新過程的知識表達、存儲和計算上仍然不夠簡潔，有些還需要依賴先驗的知識，且討論僅限于樣本增加情況下的規則更新，沒有分析移除學習樣本的情況。

本文在基于決策規則的知識系統中，分析并提出了基于已有的樣本和決策規則，根據學習樣本增/減對決策規則進行動態調整的策略，結合布爾運算提出了知識系統決策規則動態更新的矩陣算法，討論了方法的完備性和一致性，并給出了一個仿真例，驗證了方法的有效性。

1 知識系統決策規則的動態調整邏輯

1.1 知識系統及決策規則的表示

用四元組S=(U,R,V,f)來表述一個知識系統，其中U={x1,x2,…,xn}為一個非空有限的樣本集合，稱為論域。集合中的樣本xj使用屬性ri∈R和相應的屬性值vij∈Vri來描述，Vri是屬性ri的值域集合。屬性值集合V=∪Vri，(ri∈R)。f：U×R→V是一個計算函數或計算方法，它為每個樣本的每個屬性賦予一個信息值，即x∈U，?ri∈R，f(x，ri)∈Vri。一個屬性又稱之為一個等價關系。

在知識系統中將樣本根據條件屬性及其取值進行特征描述，按照決策屬性及其取值進行分類。將特征與分類進行對應成為決策規則。知識系統中存在一個最小化的決策規則集，規則集是學習樣本所支持的所有決策規則的約簡，任意一條決策規則均不存在多余的屬性描述，規則集中的決策規則不存在冗余和矛盾，滿足協調一致性，任意兩條決策規則的條件不存在包含關系。

知識系統用決策表的形式表示，決策表的列為屬性，行為樣本。屬性集合R=C∪D，C∩D=?，C為條件屬性子集，用于描述樣本特征，D為決策屬性子集，用于描述樣本分類。

1.2 新增學習樣本時的決策規則調整

知識系統中的決策規則來自于論域空間中的樣本。新的學習樣本帶來新規則，某些舊規則因與新樣本沖突而需要被移除。

若U0為初始論域，Rold為其最小化決策規則集，Unew為新增樣本集合，則U=Unew∪U0為新論域。樣本新增及其規則調整的方法如下：

步驟1：從Rold中找出與Unew中任一樣本矛盾和匹配的規則，將它們從規則集Rold中移除，并將矛盾的規則記錄在規則集Rconf中。

移除與Unew中任一樣本匹配的規則，是避免后續從Unew中獲取的規則冗余。

步驟2：從U0中找出匹配Rconf中任一規則的樣本記錄在集合U′0中，并將它們從U0中移除。

Rconf中的規則雖然被新樣本否定，但生成這些規則的樣本在其他屬性上加強一下，將可能產生新的規則，需要重新進行規則獲取。

步驟3：從規則集Rold中再次移除匹配U′0中任一樣本的規則。

該步驟將避免與后續從U′0中獲取的規則冗余。

步驟4：順序排列Unew、U′0及步驟2得到的U0，以后述矩陣計算獲取Unew∪U′0在U中所能夠產生的新增規則集Rnew。

Rold∪Rnew構成U的最簡規則集Rend。其中Rold為步驟3的結果。

在樣本增加后調整規則集的方法中，步驟1使得最終的規則集與新增樣本不矛盾。步驟2找到U0中受新增樣本各屬性取值約束而需要重新進行規則獲取的樣本集合U′0。步驟3將Rold中匹配U′0的規則移除以避免與步驟4的結果產生冗余。步驟4對新論域中的新增樣本Unew及所有可能需要重新獲取決策規則的樣本U′0在新論域U中進行規則獲取，從而保證了不會產生規則的遺漏。因此最終的規則集不存在冗余、遺漏和不一致。

對于新增樣本時的規則調整的特例，當初始論域為空，新論域完全由新增樣本構成時，規則調整的方法成為對整個論域空間進行規則獲取的全局算法[10]。

1.3 移除學習樣本時的決策規則調整

論域中學習樣本的減少同樣也將導致規則集合的變化。因為學習樣本的移除，一些規則相應的失去了支持依據。同時，移除的樣本可能解除了某些約束。

令U0為初始論域，Rold為其最小化決策規則集。Umov為移除樣本集合，U=U0/Umov為新論域。樣本移除及其規則調整的方法如下：

步驟1：從Rold中找出匹配Umov中任一樣本的規則，將它們從Rold中移除；

步驟2：在U中尋找至少在一個條件屬性值上與某移除樣本相同的樣本記錄在U′中，并將它們從U中移除。

任一保留樣本與任一移除樣本之間在屬性取值上有：

1)所有條件屬性值均不相同，決策屬性值或者相同或者不相同。此類保留樣本產生的決策規則與移除樣本產生的決策規則不可能在規則前部上相同，因此這類樣本不需要重新獲取規則。

2)至少有一個條件屬性值相同，決策屬性值相同或者不相同。此類保留樣本中，又有決策屬性值與移除樣本不一致和一致兩種。前者是移除樣本解除了在取值相同的條件屬性上的約束，需要對這些樣本重新進行規則獲取。后者是移除樣本解除了在取值不同的條件屬性上的約束，需要對這些樣本重新進行規則獲取。綜上，對于此類樣本，都需要重新進行規則的重新獲取。

步驟3：從規則集Rold中再次移除匹配U′中任一樣本的規則。通過該步驟避免與后續從U′中獲取的規則冗余。

步驟4：順序排列U′及步驟2得到的U，以后述矩陣計算獲取U′在U中所能夠產生的規則集Rnew。

Rold∪Rnew構成論域U0/Umov的最簡規則集Rend，其中的Rold為步驟3的結果。

步驟1使得最終的規則集中不存在僅由移除樣本產生的規則。步驟2找到受移除樣本屬性取值約束的樣本。步驟3將Rold中匹配U′的規則移除以避免與步驟4的結果產生冗余。步驟4對所有可能需要重新獲取決策規則的樣本U′在新論域U中進行規則獲取，從而保證了不會產生規則的遺漏。因此最終的規則集不存在冗余、遺漏和不一致。

2 從部分樣本中獲取規則的矩陣計算

這里給出在論域U中獲取其子集U′?U所支持的決策規則的等價矩陣計算，該算法是文獻[10]中矩陣算法的改進，在規則獲取上更加具有一般性。

2.1 等價矩陣[18]

首先定義等價矩陣。令S=(U，R，V，f)為一個知識系統，樣本子集U′?U，樣本xi∈U′，樣本xj∈U，樣本子集的樣本數Card(U′)=m≤n=Card(U)。

定義1：屬性C?R的m×n維等價矩陣MC=[aij]，MC中的元素aij取值為

式中：i=1，2，…，m；j=1，2，…，n。

即對于樣本xi、xj，如果兩個樣本在屬性或屬性組合C?R上的屬性值一致，即該兩個樣本在屬性或屬性集合C上存在不可區分關系(等價，表示為EC)，則等價矩陣MC|m×n的i行j列元素為1，否則為0。

定義2：令M1=[aij]，M2=[aij′]分別為兩個屬性(或屬性組合)m×n維等價矩陣。等價矩陣M1與M2的交集M1∩M2定義為M1∩M2=[bij]，其中bij為aij與aij′的二元與。

以上定義的矩陣與運算具有以下性質：結合律((M1∩M2)∩M3=M1∩(M2∩M3))、交換律(M1∩M2=M2∩M1)和冪等性(M1∩M1=M1)。

對于知識系統S=(U，R，V，f)，屬性(或屬性子集)C1，C2?R，m×n等價矩陣MC1={aij}，MC2={aij′}，MC1∪C2={bij}滿足MC1∩MC2=MC1∪C2，即

該等價關系構成了決策規則獲取的等價矩陣計算的基礎。

2.2 規則獲取矩陣計算

決策規則的前部可以是條件屬性的各種不同組合。若樣本由q個條件屬性進行描述，不難得到，q個屬性的所有組合的數目為Cq1+Cq2+…+Cqq=2q-1。例如4個屬性{a，b，c，d}，各階組合為：

1階組合：{a}、{b}、{c}、g0gggggg；

2階組合：{ab}、{ac}、{ad}、{bc}、{bd}、{cd}；

3階組合：{abc}、{abd}、{acd}、{bcd}；

4階組合：{abcd}。

因此具有4個條件屬性的知識系統的決策規則在規則前部上有24-1=15種形式。

利用Steinhaus-Johnson-Trotter算法[19]，可以找到條件屬性的所有組合形式。

將包含的條件屬性的數目為k的決策規則稱為k階決策規則，將涉及屬性數為k的等價矩陣稱為k階等價矩陣。

利用等價矩陣對樣本子集U′(m個樣本)在整個樣本集U(n個樣本)中，從條件屬性(或屬性集合)C1?C上進行規則獲取的步驟如下：

步驟1：逐一比較U′中每個樣本i與U中每個樣本j在C1上的取值，計算生成k(k=Card(C1))階條件屬性等價矩陣MC1|m×n。逐一比較U′中每個樣本i與U中每個樣本j在決策屬性D上的取值，計算生成決策屬性等價矩陣MD|m×n。

步驟2：依次對矩陣MC1、MD第i(i=1～m)行的行向量進行與運算。

1)如果與運算的結果不為全零向量且與MC1第i行行向量相等，以樣本xi的屬性C1，D的取值生成規則：

&(c=vc)? &(d=vd)，c∈C1，d∈D。

依次判斷aij∈MC1(j=1～m)是否為1，若是，將MC1第j行置全“0”。

2)如果與運算的結果為全零向量或與MC1第i行行向量不相等，下一行。

該步驟是通過比較判斷：當樣本i在C1上的取值與樣本j一致(aij=1，不可區分、等價)時，其在D上的取值是否同樣與樣本j一致，且在整個論域中是否具有一致性。若成立，則得到決策規則。同時，為了避免在生成該規則后，在后續利用(k+1)階等價矩陣獲取涉及更多屬性的(k+1)階規則時，產生規則前部存在包含關系的決策規則，在生成該規則后，對k階條件屬性等價矩陣進行調整。

矩陣計算將U′中所有包含條件屬性C1的決策規則獲取出來，規則涉及的條件屬性數為k(k=Card(C1))。

經過矩陣計算，k階條件屬性等價矩陣MC1更新為MC1new。

2.3 高階決策規則的逐步獲取

為了避免決策規則的條件部分存在相互包含，需要從1階決策規則開始，逐步獲取高階決策規則。

由前述，(k+1)階條件屬性等價矩陣可以由k階條件屬性等價矩陣的與運算生成。在獲取k階決策規則過程中，k階條件屬性等價矩陣會因為規則的獲取發生變化，因此，僅1階條件屬性等價矩陣是通過逐一比較樣本子集U′中每個樣本與樣本全集U中每個樣本在條件屬性上的取值得到。后續的高階條件屬性等價矩陣均由更新之后的低一階條件屬性等價矩陣生成。

例如4個條件屬性{a，b，c，d}，各階條件屬性等價矩陣的遞階生成關系如圖1所示。

圖1 條件屬性等價矩陣的遞階生成關系Fig.1 Hierarchical generation relation of conditional attribute equivalent matrix

其他更多條件屬性情況下等價矩陣的遞階生成關系依此類推。

3 計算復雜性分析

知識系統決策規則動態更新的方法和矩陣計算能夠減少不必要的計算量。通過分析可知，決策規則動態更新的矩陣的計算復雜度是O(m×n×2Card(C))。計算量的增長對需要重新獲取規則的樣本的個數是多項式的，對條件屬性個數是指數形式的。

對于決策規則動態更新的特例，當論域完全由新增樣本組成時，新增樣本時的決策規則調整便成為決策規則獲取的全局計算，其計算復雜度為O(n2×2Card(C))。

通常由于需要重新進行規則獲取的樣本數量m?n，與決策規則的全局獲取相比，本節提出的規則動態更新的方法及矩陣計算可以大為減少計算量。

4 仿真示例

1)增加樣本后的規則調整與矩陣計算

表1為一個包含5個樣本的粗糙集信息系統U0={x1，x2，x3，x4，x5}。條件屬性為a、b、c，決策屬性為d。

表1 初始論域U0

初始的最簡決策規則見表2。

表2 初始規則集Rold

設新增樣本集合Unew={x6}，進行增量規則調整，見表3。

表3 新增樣本集合Unew

步驟1：從Rold中移除與新增樣本Unew矛盾和匹配的規則。找到{②，④}，將矛盾規則記錄為Rconf={②，④}。

步驟2：從U0中移除與Rconf中規則相符的樣本。找到U′0={x2，x4，x5}。

步驟3：從規則集Rold中再次移除匹配U′0中任一樣本的規則。本例無。

步驟4：順序排列Unew、U′0及調整后的U0={x1，x3}，構成U={x6，x2，x4，x5，x1，x3}，開始采用矩陣計算獲取Unew∪U′0在U中所能夠產生的新增規則集Rnew。

首先生成1階條件屬性等價矩陣Ma、Mb、Mc和決策屬性等價矩陣Md：

進行1階決策規則的獲取。分別用1階條件屬性等價矩陣與決策屬性等價矩陣進行與運算，得到如下3個矩陣：

依次分別比較Mad和Ma、Mbd和Mb、Mcd和Mc的相同每一行以獲取規則，沒能獲取1階規則。1階矩陣Ma、Mb、Mc不變，MaNew=Ma，MbNew=Mb，McNew=Mc。構造2階條件屬性等價矩陣：

分別用2階條件屬性等價矩陣與決策屬性矩陣Md進行與運算，得到如下3個矩陣：

依次分別比較Mabd和Mab、Mbcd和Mbc、Macd和Mac的相同每一行以獲取規則，利用Macd、Mbcd找到了2階規則⑤～⑧，見表4。

表4 新增規則集Rnew

構造3階條件屬性等價矩陣Mabc為

等價3階矩陣已經是全0矩陣,無法再進一步獲取規則。增量規則獲取過程結束。

Rold與獲得的新增規則Rnew共同組成規則集見表5。

表5 最終的規則集Rend

2)移除樣本時的規則調整與矩陣計算

表6為一個包含6個對象的粗糙集信息系統U0={x1，x2，x3，x4，x5，x6}。條件屬性為a、b、c，決策屬性為d。

表6 初始論域U0

設待刪除對象集合Umov={x3}。初始的最簡決策規則見表7。

表7 初始規則集Rold

步驟1：從Rold中找出匹配Umov中任一樣本的規則，找到規則{②}，將其從Rold中移除。

步驟2：在U=U0/Umov中尋找至少在一個條件屬性值上與x3相同的樣本，找到{x1，x2，x4，x5}，記錄在U′中，并將它們從U中移除。

步驟3：從規則集Rold中再次移除匹配U′中任一樣本的規則。移除規則{①，③，⑤，⑥}。

步驟4：順序排列U′及步驟2得到的U，得到{x1，x2，x4，x5，x6}，開始采用矩陣計算獲取U′在U中所能夠產生的規則集Rnew。

首先生成1階條件屬性等價矩陣Ma、Mb、Mc和決策屬性等價矩陣Md，分別為

進行1階決策規則獲取。分別用1階條件屬性等價矩陣與決策屬性等價矩陣進行與運算，得到如下矩陣：

依次分別比較Mad和Ma、Mbd和Mb、Mcd和Mc的相同每一行以獲取規則。利用Mbd從對象x4找到1階規則，見表8。

表8 新增規則集

構造2階條件屬性等價矩陣，分別為

分別用2階條件屬性等價矩陣與決策屬性矩陣Md進行與運算，得到如下矩陣：

依次分別比較Mabd和Mab、Mbcd和Mbc、Macd和Mac的相同每一行以獲取規則，利用Macd找到了2階規則⑧～⑩，見表9。

表9 新增規則

由于有規則產生，有

3階條件屬性矩陣已經是全0矩陣，無法再進一步提取規則。最終的決策規則見表10。

表10 最終的規則集Rend

5 結論

本文所提出的決策規則動態更新方法和等價矩陣計算方法使得知識系統具有了隨樣本變化進行自我學習和完善的能力，為專家系統、決策支持系統以及基于知識的控制系統等智能系統中知識的獲取、動態調整提供了方法。使得專家系統在構建知識庫時可以擺脫對專家經驗知識的依賴，同時可以適應不斷變化的大數據集，未來可以廣泛應用于航天領域中信號分析、故障診斷、規劃決策、操控與服務等專家系統的自動生成

由本文所介紹的方法可知，樣本增加和移除情況下對決策規則集進行更新的邏輯和方法有較大的差異。移除樣本時知識系統的調整更新策略更為復雜，意味著在知識系統中遺忘比學習的難度要大。

基于等價矩陣的矩陣計算將決策規則獲取的過程與樣本條件屬性的物理含義及具體取值進行了分離，基于0、1布爾邏輯運算的決策規則獲取過程在計算過程表達、數據信息存儲、計算上較為簡易方便和高效。計算的大部分過程都可以采用分布式存儲和并行計算的方式完成。

文中所提出的方法對于冗余和不相容(矛盾)樣本具有較好的魯棒性。冗余的樣本不會產生冗余的規則，矛盾的樣本不會產生矛盾的規則。

當初始論域為空，新論域完全由新增樣本構成時，決策規則的更新方法及等價矩陣計算成為對整個論域空間進行決策規則獲取的全局方法。