譚天樂

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

0 引言

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

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

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

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

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

1 知識系統(tǒng)決策規(guī)則的動態(tài)調(diào)整邏輯

1.1 知識系統(tǒng)及決策規(guī)則的表示

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

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

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

1.2 新增學習樣本時的決策規(guī)則調(diào)整

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

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

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

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

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

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

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

該步驟將避免與后續(xù)從U′0中獲取的規(guī)則冗余。

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

Rold∪Rnew構(gòu)成U的最簡規(guī)則集Rend。其中Rold為步驟3的結(jié)果。

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

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

1.3 移除學習樣本時的決策規(guī)則調(diào)整

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

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

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

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

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

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

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

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

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

Rold∪Rnew構(gòu)成論域U0/Umov的最簡規(guī)則集Rend，其中的Rold為步驟3的結(jié)果。

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

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

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

2.1 等價矩陣[18]

首先定義等價矩陣。令S=(U，R，V，f)為一個知識系統(tǒng)，樣本子集U′?U，樣本xi∈U′，樣本xj∈U，樣本子集的樣本數(shù)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，如果兩個樣本在屬性或?qū)傩越M合C?R上的屬性值一致，即該兩個樣本在屬性或?qū)傩约螩上存在不可區(qū)分關系(等價，表示為EC)，則等價矩陣MC|m×n的i行j列元素為1，否則為0。

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

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

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

該等價關系構(gòu)成了決策規(guī)則獲取的等價矩陣計算的基礎。

2.2 規(guī)則獲取矩陣計算

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

1階組合：{a}、、{c}、sigsqae；

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

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

4階組合：{abcd}。

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

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

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

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

步驟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)如果與運算的結(jié)果不為全零向量且與MC1第i行行向量相等，以樣本xi的屬性C1，D的取值生成規(guī)則：

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

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

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

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

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

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

2.3 高階決策規(guī)則的逐步獲取

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

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

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

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

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

3 計算復雜性分析

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

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

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

4 仿真示例

1)增加樣本后的規(guī)則調(diào)整與矩陣計算

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

表1 初始論域U0

初始的最簡決策規(guī)則見表2。

表2 初始規(guī)則集Rold

設新增樣本集合Unew={x6}，進行增量規(guī)則調(diào)整，見表3。

表3 新增樣本集合Unew

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

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

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

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

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

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

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

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

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

表4 新增規(guī)則集Rnew

構(gòu)造3階條件屬性等價矩陣Mabc為

等價3階矩陣已經(jīng)是全0矩陣,無法再進一步獲取規(guī)則。增量規(guī)則獲取過程結(jié)束。

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

表5 最終的規(guī)則集Rend

2)移除樣本時的規(guī)則調(diào)整與矩陣計算

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

表6 初始論域U0

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

表7 初始規(guī)則集Rold

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

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

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

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

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

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

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

表8 新增規(guī)則集

構(gòu)造2階條件屬性等價矩陣，分別為

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

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

表9 新增規(guī)則

由于有規(guī)則產(chǎn)生，有

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

表10 最終的規(guī)則集Rend

5 結(jié)論

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

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

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

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

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