不完備決策系統(tǒng)規(guī)則獲取的相容矩陣算法

汪 凌

安慶師范學(xué)院 經(jīng)濟(jì)與管理學(xué)院，安徽 安慶 246011

1 引言

決策規(guī)則獲取是粗糙集理論及應(yīng)用研究的一個重要內(nèi)容?；诖植诩臎Q策規(guī)則獲取本質(zhì)上是按照屬性特征將對象進(jìn)行分類的問題。目前已有很多文獻(xiàn)研究了不完備信息系統(tǒng)的決策規(guī)則獲取方法。如文獻(xiàn)[1-3]給出了基于決策矩陣的增量式規(guī)則獲取算法，該算法需要計算和保存分辨矩陣的中間環(huán)節(jié)，時間復(fù)雜度較高；文獻(xiàn)[4-5]提出了利用上下近似集來填補空缺值并提取決策規(guī)則的算法，該算法適用于系統(tǒng)中空值較少的情況；文獻(xiàn)[6]提出了基于量化容差關(guān)系的規(guī)則獲取算法，該算法較多地依賴于先驗知識；文獻(xiàn)[7]給出基于相容關(guān)系的不完備信息決策系統(tǒng)規(guī)則提取算法，文獻(xiàn)[8-9]給出了基于廣義決策函數(shù)及擴(kuò)展形式的決策規(guī)則獲取算法等。但這兩種方法都存在一定的局限性，如計算相容矩陣或分配矩陣計算復(fù)雜，占用空間大，以及數(shù)據(jù)集很大時的規(guī)則獲取效果不理想等[10-11]。針對以上問題，本文根據(jù)不完備信息決策系統(tǒng)中相容條件屬性矩陣和決策屬性矩陣的概念，通過計算分析矩陣，提出一種基于相容矩陣的不完備信息決策系統(tǒng)規(guī)則獲取算法，并從理論上對算法進(jìn)行分析。通過實例驗證了該算法的正確性和有效性。

2 算法理論基礎(chǔ)

2.1 不完備信息系統(tǒng)與廣義決策函數(shù)

定義2不完備信息決策系統(tǒng)DS=＜U，C∪D，V，f＞，???B?C，U上的一個相容關(guān)系定義為：

令TB(x)={y∈U|(x，y)∈T(B)}，對于屬性子集B而言，TB(x)是與x可能不可分辨的對象的最大集合。

定義3不完備信息決策系統(tǒng)DS=＜U，C∪D，V，f＞，U={x1，x2，…，xn}，B?C，廣義決策函數(shù) ?B:U→P(Vd)定義為：

?B(x)={i|i=f(y，d)，y∈TB(x)}

其中，P(Vd)表示Vd的冪集，?B(x)表示TB(x)中元素在d上取值集合。

性質(zhì)1不完備信息決策系統(tǒng)DS=＜U，C∪D，V，f＞，對?x∈U，若Card(?C(x))=1，則稱DS是協(xié)調(diào)（或相容、一致）的，否則稱DS是不協(xié)調(diào)（或不相容、不一致）的。

性質(zhì)2[13-14]不完備信息決策系統(tǒng)DS=＜U,C∪D,V,f＞，設(shè)X為具有性質(zhì)∧(c，v)(c∈C，v∈Vc)的實例集合，Y為具有性質(zhì)∨(d，w)(w∈Vd)的實例集合，則：

（1）決策規(guī)則γ:∧(c，v)→∨(d，w)為真當(dāng)且僅當(dāng)X?Y，其中C為規(guī)則條件部分的所有屬性集合。

（2）決策規(guī)則γ:∧(c,v)→∨(d,w)(c∈C,v∈Vc,w∈Vd)是最優(yōu)的當(dāng)且僅當(dāng)該規(guī)則為真且出現(xiàn)在γ中的合取與析取的真子集構(gòu)成的任何規(guī)則均為假。

由上述定義及性質(zhì)定理可知，對于任意x(x∈U)，最優(yōu)規(guī)則的決策部分為 (d，w1)∨(d，w2)∨…∨(d，wn)，則有{w1，w2，…，wn}=?C(x)。

2.2 條件屬性矩陣和決策屬性矩陣

定義4[15]不完備信息決策系統(tǒng)DS=＜U,C∪D,V,f＞，U={x1，x2，…，xn}，則屬性子集B?C對應(yīng)的相容條件屬性矩陣MB定義為：

其中，mij為相容條件屬性矩陣中第i行j列的元素，i，j=1，2，…，n。

定義5[15]不完備信息決策系統(tǒng)DS=＜U,C∪D,V，f＞，U={x1，x2，…，xn}，DS的決策屬性矩陣 MD定義為：

其中，mij為決策屬性矩陣中第i行j列的元素，i，j=1，2，…，n。顯然，決策屬性矩陣是一主對角線為1的n階對稱矩陣。

條件屬性子集相容矩陣表述的是該條件屬性子集所確定的不完備信息決策系統(tǒng)中所有實例的相容關(guān)系；而決策屬性矩陣表達(dá)的則是所有實例間確定不同決策屬性值的區(qū)分關(guān)系。

在?C、MB及 MD等定義描述的基礎(chǔ)上，可以得出定理1。

定理1不完備信息決策系統(tǒng)DS=＜U，C∪D，V，f＞，U={x1，x2，…，xn}，屬性子集B?C對應(yīng)的相容條件屬性矩陣，決策屬性矩陣 MD=，其中、、(1≤i≤n)是 1×n維向量，上標(biāo)T表示矩陣的轉(zhuǎn)置。若存在的第i行與的第i行相互一致，則存在一條決策規(guī)則：

證明根據(jù)條件屬性矩陣與決策屬性矩陣的定義，如果的第i行與的第i行相互一致，意味著對于條件屬性子集B，對象xi與決策不可分辨類D中的任意對象xj之間都是不相容的。反之，如果在決策屬性類別中存在yk與xi相容，則有yk∈TB(xi)，所以會存在不一致現(xiàn)象，與相互一致矛盾。因此，對于?xj∈TB(xi)，f(xj，d)∈?C(xi)，必然存在一條決策規(guī)則：。

定理1表明，當(dāng)條件屬性子集確定的一個實例的廣義決策函數(shù)值與整個條件屬性集確定的廣義決策函數(shù)值相互一致時，必然能得到一條決策規(guī)則，這實際上給出了從不完備信息決策系統(tǒng)中提取相應(yīng)決策規(guī)則集的方法。

3 不完備決策系統(tǒng)規(guī)則獲取的相容矩陣算法

3.1 算法思想及描述

根據(jù)以上命題和定理，提出一種相容關(guān)系下基于矩陣計算的不完備決策系統(tǒng)規(guī)則獲取算法。該算法通過計算相容屬性矩陣和決策屬性矩陣，當(dāng)條件屬性子集確定的一個實例的廣義決策函數(shù)值與整個條件屬性集確定的廣義決策函數(shù)值相互一致時，就可直接生成一條決策規(guī)則。采用相同的分析處理方法，就可從不完備信息決策系統(tǒng)中提取出全部的決策規(guī)則集。不完備信息決策系統(tǒng)中大數(shù)據(jù)集的決策規(guī)則獲取流程，如圖1所示。

不完備信息決策系統(tǒng)規(guī)則獲取的相容矩陣算法具體過程描述如下所示。

輸入：不完備信息決策系統(tǒng)DS=＜U，C∪D，V，f＞，U={x1，x2，…，xn}，C為條件屬性集，D為決策屬性集。

輸出：DS=＜U，C∪D，V，f＞的所有決策規(guī)則集。

步驟1計算DS中條件屬性C對應(yīng)的相容條件屬性矩陣MC和決策屬性矩陣MD。

步驟3 fori=1ton。

圖1 不完備信息決策系統(tǒng)大數(shù)據(jù)集的規(guī)則獲取流程

（1）取一階相容條件矩陣M{c}的第i行與決策屬性矩陣MD的第i行相交；

（2）若存在 M{c}的第i行與 MD的第i行不一致，nexti，否則轉(zhuǎn)步驟4。

步驟4根據(jù)對象xi的屬性第i行對應(yīng)的屬性cm∈C，dn∈D的取值生成決策規(guī)則：∧(cm=vcm)→∧(dn=vdn)，同時將第i行置為零，提取出所有的一階決策規(guī)則。

步驟6采用類似步驟5的處理方法提取所有三階以上的決策規(guī)則，直至無非零的同階相容矩陣為止，最后輸出所有的決策規(guī)則集。

3.2 算法分析

上述規(guī)則獲取算法中的相容條件屬性矩陣和決策矩陣的生成是執(zhí)行整個算法的基礎(chǔ)。因此，本算法的計算復(fù)雜度主要由步驟1～步驟5決定。

綜合以上分析可知，本算法總的計算復(fù)雜度為O(|U|22|C|)，計算量的增長相對于對象個數(shù)是多項式級的，相對于屬性個數(shù)是成指數(shù)級形式的。

本算法在數(shù)據(jù)計算量上具有較大的優(yōu)勢，矩陣運算將粗糙集規(guī)則提取過程中的復(fù)雜比較過程轉(zhuǎn)換成對簡單的0、1矩陣或向量的操作，而不是對象集的處理。此外，由于決策屬性矩陣只考慮上三角或下三角即可獲取相同結(jié)果，因而本算法能夠減少一半的矩陣計算量，大大提高了算法的效率。

4 實例分析

為了驗證算法的有效性，以某城市交通流狀態(tài)不完備信息決策系統(tǒng)為例計算最小決策規(guī)則集。該不完備信息決策系統(tǒng)如表1所示，其中論域U={x1，x2，…，x6}，條件屬性集C={F，S，D，L}，其中F表示Traffic Flow，S表示 Average Speed，D表示 Vehicle Density，L表示Team Length，決策屬性j5i0abt0b表示Mode。

表1 城市交通交通流狀態(tài)不完備信息決策表

表1所示的不完備信息決策表中，存在多個條件屬性值未知，因此可以根據(jù)上述算法步驟對表1進(jìn)行如下處理：

（1）根據(jù)步驟1，計算不完備信息決策表DS的決策屬性矩陣MD和條件屬性矩陣MC：

（2）根據(jù)步驟2，計算一階相容條件屬性矩陣：

（4）根據(jù)算法步驟5，將（3）中所有非零一階相容條件屬性矩陣兩兩相交，得到如下三個滿足條件的所有二階相容屬性矩陣：

對提取的決策規(guī)則進(jìn)行刪除、合并等步驟操作，得該不完備信息決策表最終的決策規(guī)則集如表2所示。

表2 城市交通流狀態(tài)決策規(guī)則集

決策規(guī)則對應(yīng)的語言描述分別為：

rule1如果該路段或交叉口車輛密度是大，則交通流狀態(tài)為擁擠的；

rule2如果該路段或交叉口車輛密度是小，則交通流狀態(tài)為正常的或暢通的；

rule3如果該路段或交叉口車隊長度是短，則交通流狀態(tài)為正常的。

通過提取以上決策規(guī)則，即可對城市交通流狀態(tài)模式進(jìn)行辨識。將所有決策規(guī)則存儲于城市交通管理決策支持系統(tǒng)中，則可直接判別出任一時刻的交通流狀態(tài)模式。

將相同的數(shù)據(jù)集采用Rosetta Version1.4.41進(jìn)行規(guī)則提取，通過分析比較發(fā)現(xiàn)，兩種算法得到的決策規(guī)則數(shù)基本一致，且該矩陣算法減少了計算量，具有較高的運算效率，實例分析表明了該算法的有效性和實用性。

5 結(jié)論

決策規(guī)則獲取是粗糙集理論及應(yīng)用研究的一個重要內(nèi)容?，F(xiàn)有的決策規(guī)則獲取算法的低效性一定程度上限制了粗糙集理論的廣泛應(yīng)用，因而尋求高效的規(guī)則獲取算法具有重要意義。本文基于相容關(guān)系下的條件矩陣和決策矩陣，提出一種基于相容矩陣運算的不完備決策系統(tǒng)規(guī)則獲取算法。該算法在提取規(guī)則時減少了矩陣生成的比較次數(shù)，降低了矩陣占用空間，通過比較向量大小即可快速求出大數(shù)據(jù)集的全部決策規(guī)則集，因而大大提高了規(guī)則獲取效率，對于基于規(guī)則獲取的系統(tǒng)辨識而言具有較強(qiáng)的實用價值。

[1]Liu Yong，Xu Congfu，Li Xuelan，et al.A dynamic incremental rule extracting algorithm based on the improved discernibility matrix[C]//Proceedings of the IEEE International Conference on Information Reuse and Integration.NV，USA.2003.NJ，USA：IEEE Computer Society Press，2003：93-97.

[2]李春生，尹旭日，陳世福.基于Rough集的規(guī)則學(xué)習(xí)研究[J].小型微型計算機(jī)系統(tǒng)，2001，22（8）：982-984.

[3]Kryszkiewicz M.Rules in incomplete information system[J].Information Science，1999，113：271-292.

[4]Leung Y，Wu W.Knowledge acquisition in incomplete information system：a rough set approach[J].European Journal of Operational Research，2006，168：164-180.

[5]Hong Tzungpei，Tseng Lihui，Wang Shyueliang.Learning rules from incomplete training examples by rough sets[J].Expect Systems with Applications，2002，22（4）：258-293.

[6]Stefanowski J，Tsoukias A.Valued tolerance and decision rules[M]//Ziarko W，Yao Y.Rough Sets and Current Trends in Computing.Berlin：Springer，2002：271-278.

[7]Ziarko W.Variable precision rough set model[J].Journal of Computer and System Sciences，1993，46（1）：39-59.

[8]黃兵，周獻(xiàn)中.不完備信息系統(tǒng)分配約簡與規(guī)則提取的矩陣算法[J].計算機(jī)工程，2005，31（17）：20-22.

[9]Mollestad T，Skowron A.A rough set framework for data mining of propositional defalut rules[C]//Proc of the 9th International Symposium on Methodologies of Intelligent Systems，1996：448-457.

[10]尹旭日，陳世福.一種基于Rough集的缺損規(guī)則挖掘算法[J].計算機(jī)研究與發(fā)展，2000，12（37）：1441-1445.

[11]Komorowski J.ROSETTA：a rough set toolkit for analysis of data[C]//Proc of the 3rd International Joint Conference on Infromation Sciences.SanJose，Calfornia，USA，1997.North Calfornia，USA：Durham，1997，3：403-407.

[12]Wu Weizhi，Mi Jusheng，Zhang Wenxiu.A new rough set approach to knowledge discovery in incomplete information systems[C]//IEEE Proc of the 2nd International Conference on Machine Learning and Cybernetics，2003：1713-1718.

[13]Pawlak Z.Drawing conclusions from data-the rough set way[J].International Journal of Intelligent Systems，2001，16：3-11.

[14]Hu X H.Knowledge discovery in database：an attributeoriented rough setapproach[D].Regina：University of Regina，1995.

[15]Ziarko W，Hu N.Rule discovery from databases with decision matrices[C]//Proc of the International Conference on Methodologies for Intelligent System（ISMIS96），Zakopane，Poland，1996.Heidelberg，Germany：Springer-Verlag，1996：653-662.