- 相關推薦
智能決策支持系統中的知識表示及基于粗集的知識推理
摘要：當前，智能決策支持系統的實現研究已成為眾多學科領域的研究熱點，特別是伴隨人工智能的發展，不斷有新的理論和方法用于智能決策支持系統的實現。本文探討在智能決策支持系統中的知識表達，討論了屬性在知識表達系統中的作用，決策表格形式的知識表達系統的性質、作用以及根據粗集理論分析處理海量信息中信息的有用特征，通過分析、推理產生最小決策規則。本文最后以EDUDSS中農村小學布局決策為例作實例分析。關鍵詞：智能決策支持系統；粗集；依賴度；知識推理
一引言
知識推理是智能決策支持系統中的核心，即根據所獲得的信息通過數據分析、推理，從而產生合理的決策規則形成有用知識的過程。為了處理智能數據，就需要對知識進行符號表示。知識表達系統就是研究將對象的知識通過指定的對象的基本特征和特征值來描述，以便通過一定的方法從大量浩如煙海的數據中發現有用的知識或決策規則。粗集理論（RoughSet）作為智能信息處理技術的一個新成果，是由波蘭科學家Z.Pawlak教授提出來的對不完整數據進行分析、推理、學習、發現的新方法。根據粗集理論的方法，知識推理就是給定知識表達系統的條件屬性和結果（決策）屬性，求出所有符合該知識的最小決策算法。這里以EDUDSS為例討論如何利用粗集理論從現有小學布局數據中發現適合當地實際情況的決策規則，并用于小學布局的決策。
二粗集理論的基本概念。
粗集理論是基于一個機構關于一些現實和它分辨某些特點、過程、對象等的能力的知識，該理論以觀察和測量所得的數據進行分類的能力為基礎，它認為知識是基于對對象分類的能力，知識直接與真實或抽象世界有關的不同分類模式聯系在一起，這里稱之為論域U（Universe）。
假定給定一個感興趣的對象的論域U，對于任何子集可稱為U中的概念或范疇，并且U中的任何概念族稱為關于U的知識。這些概念也構成了特定論域U的分類。一個U上的分類族定義為一個U上的知識庫，這樣，知識庫表達了一個或一組智能機構的各種基本分類方式。通常情況下，用等價關系來代替分類的概念。
令，且R為一等價關系，當X為某些R基本范疇的并時，稱X是R可定義的，否則X為R不可定義的。R可定義集是論域的子集，它可在知識庫K中被精確定義，而R不可定義集不能在這個知識庫中被定義。R可定義集稱為R精確集，而R的不可定義集稱為R粗集。粗集可以近似地定義，為達到這個目的，使用兩個精確集（粗集的上近似和下近似）和邊界來描述。
X關于R的下近似
X關于R的上近似
X關于R的邊界
posR(X)=R_(X)稱為X的R正域，把negR(X)=U-R_(X)稱為X的R負域。簡單地說，正域posR(X)或X的下近似就是那些對于知識R能完全確定地歸入集合X的對象的集合。類似地，負域negR(X)是那些對于知識R不屬于集合X的元素的集合，它們是X的補集。邊界域是從某種意義上論域的不確定域，對于知識R屬于邊界域的對象不能確定地劃分是屬于X或-X。X的上近似是由那些對于知識R不能排除它們屬于X的可能性的對象構成，從形式上，上近似就是正域和邊界域的并集。
三知識的表示及基于粗集的知識推理及化簡
知識的表示、簡化及核
知識表示可通過知識表達系統來完成，知識表達系統的基本成分是被研究對象的集合，關于這些對象的知識是通過指定對象的屬性和它們的屬性值來描述的。
一個數據表知識表達系統S可表示為S=<U,C,D,V,F>
其中：U表示論域；
C∪D=A是屬性集合，子集C和D分別稱為條件屬性和結果(決策)屬性；
V=Vα1×Vα2×Vα3×…Vαn表示屬性A的值域，Vα表示原子屬性α的值域；
F：U×A→V表示從V×A到V的信息映射，定義Fα：U→Vα。
設屬性集合
定義映射FB：U→VB表示關于屬性B的屬性值。
論域U關于條件屬性C上的R的商集，記為U/RC；
論域U關于決策屬性D上的R的商集，記為U/RD；
定義U/RB中的等價類為事件，則U/RC為條件事件，U/RD為決策事件。
則決策事件關于條件屬性的上近似為
則決策事件關于條件屬性的下近似為
設有兩集合族G、R，其中r是R中的某一等價關系，如pos（R-{r}）（G）=posR（G），則稱r是關于G可省略的，否則為G不可省略的。
如R中的任意元素是不可省略的，稱R是獨立的。設，H是獨立的，若posH（G）=posR（G），則稱H為R的G簡化（Reduction），從定義可知，G關于H和R的下近似是相同的，即維持了與R相同的分類能力。R中所有不可省略關系的交集，稱為R的核（Core），記為core（R），即core（R）＝∩red（R）．核中的屬性是影響分類的重要屬性。
事件依賴性的度量
Ci為U/RC中的條件事件，Dj為U/RD中決策事件，設決策事件依賴于條件事件的程度為映射CFij：Ci→Dj，且CFij=card（Ci∩Dj）/card（Ci）
如條件事件Cj屬于或包含于決策事件Dj的下近似C_（Dj）時，CFij=1；
如條件事件Cj屬于或包含于時，CFij=0。
基于粗集的知識推理
根據前面的介紹，知識表達系統將論域描述為一個二維表格，每一行描述一個對象，每一列描述一個屬性，屬性分別為條件屬性和決策屬性。知識推理的過程，首先要進行條件屬性的化間，消去重復行，然后對每一決策規則進行冗余屬性的簡化。一般情況下，一個知識表達系統的簡化不止一種，這些簡化都維持了與原有條件屬性相同的分類能力，因此要得到使用意義上的最小決策規則就要合理地選擇有效屬性來正確或近似地表征研究的論域。
普通情況下，決策者會擁有對各條件對象的屬性權重的先驗知識，權重用來衡量屬性的相對重要性。在不同的決策環境下，相同的屬性對決策輸出會有不同的影響，即權重對環境敏感。粗集理論中的屬性依賴度即表達了在當前的數據環境下屬性對決策規則的影響，但它不能反映決策者的先驗知識，因此，將二者結合作為選擇有效屬性的準則不失為一種合理的解決方案。
具體實現步驟如下：
Step1：提出論域中各條件屬性和決策屬性組成二維數據視圖即決策規則表；
Step2：確定數據分類標準，將各屬性值以標準化方式表達，消去冗余屬性；
如果該知識表達系統的決策規則不相容，則可將它分為兩個子表，一個表為相容決策表；另一個表為不相容決策表．不相容決策表是由當前信息不能被推理的知識，所以只處理相容決策表。
Step3：計算各屬性在當前數據信息環境下的重要性，及屬性的依賴度；
對于每一子屬性的依賴度,可由前面定義的決策條件事件依賴度取得。
當然，也可以考察posB-｛a｝（C）與posB（C）之商的形式來表達屬性a的重要性。
Step4：依賴度為0的屬性表示去掉該屬性時，分類U/C的正域不受影響，因此，根據先驗權重的排序，消去依賴度為0的且先驗權重最小屬性；
Step5：計算每一決策規則的核和可能的簡化；
Step6：根據一定規則選擇有效決策規則的屬性簡化表，取得最簡規則；
在實際系統中，每一規則可能都會有幾種簡化形式，它們的組合可能會是一個很大的規則集合，對于這樣龐大的解集，在實際系統種使用起來非常麻煩，除非是針對特定案例進行決策。因此，須考慮選擇最有效的屬性子集來進行簡正確或化近似地表達該論域。從實踐經驗中可知，人們在現實中考察一個對象時，往往最愿意取得的屬性是根據先驗知識認為的權重最大的屬性，所以，應從各規則的簡化規則中盡可能選擇包含的權重較大的屬性的簡化來表征該論域的決策規則。這里給出這樣一種實用有效的求解辦法：
設化簡后的決策表屬性集為｛a1,a2,…，am｝，它們先驗權重為p(a1),p(a2),…p(am)
規則i有k種可能的簡化形式，定義每種簡化形式的權重為
其中如果簡化形式中aj為指定值，則O(aj)=1,aj為非指定值則O(aj)=0。取每種權重最大的簡化形式組合得到實用有效的簡化決策規則集。
四．EDUDSS中農村小學布局知識推理
農村小學的布局問題是涉及教育辦學方針和本地實際情況，決策者需要根據現有的信息，通過數據分析、推理、從而產生合理的決策方案。因此我們開發的EDUDSS軟件中，采用了以粗集為主的方法作為知識推理的手段。
下面以一個簡化的例子討論如何用粗集方法對小學布局數據視圖的化簡，從而得出當地小學布局的最小決策算法，用于考察該地其他學校的布局合理性。
根據專家確定的分類標準，將某一地區的六班型小學主要考察指標按下述分類方法標準化，消去重復項，得表1．
平均班額：0：[0，25），1：[25，35），2：[35，55），3：[55，∞）；
生師比：0：[0，15），1：[15，25]，2：[25，∞）；
平均就學距離：0：[0，1.5]，1：[1.5，3]，2：[3.5，∞]；
覆蓋人口：0：[0，500]，1：[500，1500]，2：[1500，∞]；
學校Ｕ
平均班額a
生師比b
平均就學距離c
學校覆蓋人口d
學校分類e
1
0
0
0
2
-
2
0
1
1
1
-
3
1
0
1
1
-
4
1
1
1
1
+
5
1
2
2
0
-
6
2
1
0
2
-
7
2
1
1
1
+
8
3
1
0
2
+
9
3
2
1
1
-
10
3
0
0
2
-
表1
根據決策者和專家先驗知識，得到各屬性權重如下：a=0.35,b=0.3,c=0.2,d=0.15
下面逐一考察各屬性得依賴度，看其是否可省略；
命C={a,b,c,d}，D={e}，得到D對于C的依賴度CF=card(C∩D)/card(C)=1，可見該數據視圖是相容的。對于屬性a，可得D對于屬性a的依賴屬性為CFa=card(Ca∩D)/card(Ca)=5/8。同理，可得CFb=1/2，CFc=0，CFd=0，根據各屬性的權重信息，可得屬性c比屬性d在決策中占的權重更大，因此，保留屬性c消去屬性d。
對消去屬性d的數據視圖，可發現各項屬的依賴度均大于0，因此，各項均不可省略，但是，要得到簡化的決策規則，還須去掉每一決策規則中的不必要條件，即求每項規則的核值。
對于決策規則1，有
F={[1]a,[1]b,[1]c}={{1,2},{1,3,10},{1,6,8,10}},即有[1]{a,b,c}={1},
[1]e={1,2,3,5,6,9,10}。為求出規則1的可省略屬性和可能簡化，下面每次去掉一屬性，看其余屬性子集的交是否在決策屬性子集[1]e之中。
[1]a∩[1]b={1},[1]a∩[1]c={1},[1]b∩[1]c={1,10}，于是可得決策規則1的核為空，它有三種簡化形式a(1)=0,b(1)=0和b(1)=0,c(1)=0以及a(1)=0,c(1)=0。
同理，可求出其他各條規則的核和可能的簡化形式，列于表2和表3
學校Ｕ
平均班額a
生師比b
平均就學距離c
學校分類e
1
X
X
X
-
2
0
X
X
-
3
X
0
X
-
4
1
1
X
+
5
X
X
X
-
6
X
X
X
-
7
2
X
X
+
8
X
1
X
+
9
X
X
X
-
10
X
X
X
-
表2
學校Ｕ
平均班額a
生師比b
平均就學距離c
學校分類e
1
X
0
0
-
1’
0
X
0
-
1’’
0
0
X
-
2
0
X
1
-
2’
0
1
X
-
3
X
0
1
-
3’
1
0
X
-
4
1
1
X
+
5
X
2
2
-
5’
1
X
2
-
5’’
1
2
X
-
6
X
1
0
-
6’
2
X
0
-
7
2
X
1
+
8
3
1
X
+
9
X
2
1
-
9’
3
X
1
-
9’’
3
2
X
-
10
X
0
0
-
10’
3
X
0
-
10’’
3
0
X
-
表3
由表3可以看到，決策規則4、7和8只有一種形式的化簡，決策規則2、3和6有2種形式的化簡，而決策規則1、5、9和10有3種形式的化簡。這樣，該知識表達系統的化簡有(1×1×1)×(2×2×2)×(3×3×3×3）=648種解。
根據前面所述的實用有效的原則，可以得到各規則的各可能簡化權重最大的分別為1’’、2’、3’、4、5’’、6’、7、8、9’’、10’’于是，可得到該地區小學六班型學校布局的如下簡化的實用決策規則：
a0b0∨a0b1∨a1b0∨a1b2∨a2c0∨a3b2∨a3b0→－
a1b1∨a3b1∨a2c1→＋
五結束語
本文探討了智能決策支持系統中通過條件－決策表來表達一個信息系統的知識，在此基礎上利用粗集理論結合決策者的先驗知識進行分析、推理，得到可能的簡化決策規則，然后應用實用有效的原則求得一組合理的決策規則集，從而有效地解決了智能決策支持系統中決策規則的獲取問題。
參考文獻
Pawlak,Z.RoughSets.InternationalJournalofInformationandComputerScience,1982,11
Pawlak,Z.RoughSets:TheoreticalAspectsofReasoningaboutData.KluwerAcademic,1991.
曾黃麟．粗集理論及其應用．重慶大學出版社，1996
王玨，苗奪謙，周育健．關于RoughSet理論與應用綜述．模式識別與人工智能，1996.9．
陳挺．決策分析．科學出版社，1997
Lin,T.Y.,andCercone,N.,Eds.RoughSetsandDataMining.KluwerAcademic.1997.
Mrozek,A.,andPlonka,L.Roughsetsinindustrialapplications.InRoughSetsinKnowledgeDiscovery,Vol.2.L.PolkowskiandA.Skowron,Eds.PhysicaVerlag,1998.
[8]韓禎祥，張琦，文福詮．粗集理論極其應用綜述．控制理論與應用，1999，4.
【智能決策支持系統中的知識表示及基于粗集的知識推理】相關文章：
基于物理知識在初中數學教學中滲透的思考08-19
基于GP算法的知識發現系統08-06
基于GP算法的知識發現系統08-06
人工智能在知識付費產業中的應用研究08-19
對聯中的文史知識08-13
基于SMBus的智能電池系統08-06
基于新木桶理論的虛擬團隊知識共享機制08-07
決策中，品味幸福08-13
粗集方法在KDD系統中的應用與研究08-06