基于決策表的模糊粗糙單調依賴算法及其應用*

梁瑾羅飛許玉格

(1.華南理工大學自動化科學與工程學院，廣東廣州510640;2.華南師范大學教育信息技術學院，廣東廣州510631)

粗糙集［1］是用來處理不確定和不完整數(shù)據(jù)信息的數(shù)學工具，模糊集［2］也可以描述信息和知識的不確定性，兩者具有很強的互補性，因此可以把它們結合起來對信息進行不確定性處理.在決策表中，粗糙集挖掘條件屬性和決策屬性之間的依賴關系、約簡屬性，找出哪些條件屬性對決策屬性比較重要，其理論基礎是等價關系.針對等價關系的局限性，人們提出了不同的約簡關系，文獻［3-4］中提出了領域和相容關系，Greco等［5］提出了優(yōu)勢關系，Dubois等［6］提出了模糊等價關系.事實上條件屬性和決策屬性之間往往還存在量的單調依賴關系.例如在生化反應中，條件成分和成品之間在一定范圍內有單調遞增或遞減依賴關系，一般情況下越多的成品需要越多的條件成分，但是否凡是包含成品成分的條件成分都與成品之間有這樣的單調遞增關系呢?顯然不是.有些條件成分雖然包含成品中的成分，但它們并不參與生成成品，當然在某些情況下可以通過確定的生化反應方程較精確地計算出來.但大多數(shù)情況下，生化反應處于一個復雜的環(huán)境中，受到很多物理、化學和生物等不確定因素的影響，因此可以采用模糊粗糙的方法，先計算出條件成分與成品之間的單調遞增或遞減關系，從而精簡掉冗余的條件成分，然后進行相應的分析，即挖掘出哪些條件屬性的變化會影響決策屬性量的變化，并且挖掘出哪些量影響的程度大，得出主要控制哪些條件屬性的量會影響決策屬性量的變化，從而達到控制的目的.

Wu［7］和Chou等［8］分別討論了模糊單調函數(shù)及其在邏輯控制中的應用，文獻［9-12］中討論了Mamdani-Assilians模型和T-S推斷方法的模糊控制單調問題，文獻［13-14］中討論了決策表屬性約簡算法.根據(jù)模糊粗糙集理論，文中提出了一種基于決策表的模糊粗糙單調依賴算法，首先通過區(qū)間映射重新定義了基于決策表的模糊單調依賴概念，用于挖掘條件屬性和決策屬性之間的單調遞增依賴關系，然后證明了相關命題，根據(jù)命題得出相應的結論，并將該算法初步應用到污水處理中.

1 模糊粗糙決策表

1.1 決策表

知識表達系統(tǒng)也稱為信息系統(tǒng)，可以用四元組S=(U，A，V，Q)來表示.其中:論域U為對象的非空有限集合;A為屬性的非空有限集合;為屬性a的值域;Q:U×A→V為信息函數(shù)，它為每個對象的每個屬性賦予一個信息值，即?a∈A，x∈U，Q(x，a)∈Va.當A=C∪D且C∩D=?時，C稱為條件屬性集，D稱為決策屬性集，稱該知識表達系統(tǒng)為決策表［15］.

1.2 模糊隸屬函數(shù)

設論域U上的一個模糊集合A由U上的一個實值函數(shù)來表示，即.對于x∈U，函數(shù)值μA(x)稱為x對于A的隸屬度，而函數(shù)μA稱為A的隸屬函數(shù).模糊集合的運算及性質很多，文中主要使用其交運算，對于y∈U，μA(y)∧μA(x)中的∧表示取下確界［16］.

2 基于決策表的模糊粗糙單調依賴算法

某些知識系統(tǒng)的條件屬性和決策屬性之間不僅存在離散的、有限集合的簡單粗糙決定關系(即僅通過等價關系就可以挖掘出條件屬性和決策屬性的重要依賴關系，從而得出核條件屬性和約簡)，還存在量的單調依賴關系，這種依賴程度決定著某些條件屬性的變化將對決策屬性的變化產(chǎn)生多大影響.某個條件屬性的變化對決策屬性的變化幾乎沒有或僅有較小程度的影響，意味著決策屬性的變化并不依賴于該條件屬性，從而可以挖掘出對決策屬性變化產(chǎn)生重要影響的條件屬性，并通過控制這些條件屬性去影響決策屬性.

在決策表中，假設決策屬性量的變化依賴于某些條件屬性量的變化，因此需要挖掘出對決策屬性量的變化產(chǎn)生重要影響的條件屬性，稱這樣的決策屬性和條件屬性之間有重要的單調依賴關系，但這種依賴關系在決策表中并非一定嚴格單調.把條件屬性值和決策屬性值按單調性劃分為若干個區(qū)間后，如果條件屬性值按區(qū)間與決策屬性值單調映射，那么它們就是依區(qū)間單調依賴.為了區(qū)別于嚴格單調依賴，文中稱這種依賴關系為模糊單調依賴關系.由于單調遞減的依賴關系與單調遞增相類似，因此文中只討論單調遞增的情況.

2.1 映射及嚴格單調依賴

假設對象、決策屬性和條件屬性之間是一一映射關系，條件屬性值集合Ci={xi1，xi2，…，xin}，其中Ci∈C，C={C1，C2，…，Cm}，n和m為待定數(shù)，決策屬性值集合D={y1，y2，…，yn}，對象值集合U'={e1，e2，…，en}，則對任意對象，有xij∈Ci和yj∈D與它相對應.

命題1如果對任意ek，el∈U'，有yk≥yl?xik≥xil，則有xik≥xil?yk≥yl.

證明假設xik≥xil?yk≥yl不成立，那么同時有xik≥xil和yk≤yl.由yl≥yk?xil≥xik，得出xik≤xil，這與xik≥xil相矛盾，因此假設不成立，命題得證.證畢.

根據(jù)上面的設定，決策屬性和條件屬性之間是一一映射的關系，必然存在映射，其中對任意的，也必然存在逆映射同樣存在映射xmk}，同理有逆映射對于某個條件屬性集，存在映射，使得，同樣有逆映射文中僅討論某個條件屬性與某個決策屬性模糊單調遞增的依賴關系.

2.2 區(qū)間劃分及模糊單調關系定義

對決策屬性集合D中的元素值按遞增順序排列后得到新的集合，通過上面定義的映射，可以得到排列后的條件屬性集合因為，所以顯然，如果也是按遞增順序排列的集合，那么決策屬性D和條件屬性C滿足定義1，它們是嚴格單調遞增依賴關系.在實際應用中，由于存在各種干擾因素和誤差，條件屬性和決策屬性之間可能是單調遞增依賴關系，但并非嚴格單調遞增依賴關系，大部分情況是當決策屬性在某個區(qū)間的值大于在另一個區(qū)間的值時，與決策屬性相對應的條件屬性在這個區(qū)間的值也大多大于在相對應的另一個區(qū)間的值.由于是一種模糊的關系，因此，文中稱這種情況下的決策屬性和條件屬性關系為模糊單調遞增依賴關系.下面先討論一種區(qū)間劃分方法，然后再給出模糊單調遞增關系的定義.

假設把決策屬性集D'劃分為p個區(qū)間，考慮到?jīng)Q策屬性值分布的不均勻性，文中等距離設定D'的p個區(qū)間的中心點，把作為相鄰區(qū)間中心點的距離，第一個區(qū)間的中心點記為，第二個區(qū)間的中心點記為ct2(ct2=ct1+dis)，第i個區(qū)間的中心點記為cti，那么第i+1區(qū)間的中心點cti+1=cti+dis，可得到p個區(qū)間中心點的集合{ct1，ct2，…，ctp}.把與中心點集合中某中心點的距離小于等于dis/2的決策屬性值歸為一個區(qū)間:設，且，那么把歸為區(qū)間Ωi，文中稱這種劃分方法為Ψ劃分.D'經(jīng)過Ψ劃分后，得到Ω1，Ω2，…，Ωp，其中Ω1∪Ω2∪…∪Ωp=D'，Ω1∩Ω2∩…∩Ωp=?，對任意的1≤r＜h≤p，有sup(Ωr)≤inf(Ωh)，通過映射f，可得到C'i的區(qū)間劃分為Γ1，Γ2，…，Γp，簡稱為Z劃分，其中對任意Ωk∈{Ω1，Ω2，…，Ωp}，1≤k≤p，有f(Ωk)=Γk∈{Γ1，Γ2，…，Γp}，如果對任意的1≤r＜h≤p，有sup(Γr)≤inf(Γh)，那么決策屬性D與條件屬性Ci明顯滿足定義1，是嚴格單調遞增依賴關系.否則，設num(minΓh≥Γr)表示Γr中某些元素的個數(shù)，而這些元素的值是小于等于Γh的最小值中元素的個數(shù)，可得到定義2.

定義2一個模糊遞增依賴隸屬函數(shù)為

稱μ(Γh，Γr)為Γh相對區(qū)間Γr的模糊遞增依賴程度函數(shù)，其中ε為可選參數(shù)，0＜ε≤1，可以根據(jù)具體情況進行選擇，因此μ(Γh，Γr)=0或ε＜μ(Γh，Γr)≤1.當μ(Γh，Γr)=0時，認為區(qū)間Γh相對區(qū)間Γr沒有發(fā)生模糊遞增的情況，否則稱Γh相對區(qū)間Γr依程度μ(Γh，Γr)模糊遞增，μ(Γh，Γr)值越大，模糊遞增的程度越大.

求出Γ1，Γ2，…，Γp區(qū)間之間模糊遞增依賴隸屬函數(shù)的最小值，作為條件屬性相對決策屬性依區(qū)間劃分Ψ的遞增程度，或說依區(qū)間劃分Z的遞增程度.如果隸屬函數(shù)最小值為0，那么認為相對D'依區(qū)間劃分Ψ沒有遞增，或說依區(qū)間劃分Z沒有遞增.由區(qū)間劃分及定義2可以得出命題2.

命題2如果Γ1，Γ2，…，Γp區(qū)間之間模糊遞增依賴隸屬函數(shù)存在不等于0的最小值，那么該最小值必然是在相鄰的兩個區(qū)間之間產(chǎn)生的.

證明假設1≤i＜j≤p，j≠i+1，μ(Γj，Γi)≠0，并且μ(Γj，Γi)是Z劃分的最小值，則存在i＜k＜j，μ(Γk，Γi)≠0，μ(Γj，Γk)≠0?minΓj≥minΓk，從而推出μ(Γk，Γi)≤μ(Γj，Γi)，因此假設不成立，最小值必然在相鄰的兩個區(qū)間之間產(chǎn)生，記為，表示條件屬性集合依Z劃分所得的模糊遞增程度，也稱為D'依Ψ劃分依賴于的模糊遞增程度，得出文中所需要定義的決策屬性與條件屬性的模糊遞增依賴關系.

2.3 模糊遞增依賴關系的參數(shù)及性質

關于區(qū)間劃分個數(shù)p的討論，如果每個區(qū)間只有一個元素，就變成了研究嚴格單調遞增依賴關系，從而失去了模糊意義，如果把所有元素作為一個區(qū)間也會失去研究意義.如果決策屬性與條件屬性之間確實是單調遞增關系，那么可以認為由于干擾和誤差等因素的影響，沒有出現(xiàn)嚴格單調遞增關系，而是出現(xiàn)了模糊單調遞增關系.這些影響因素的作用是在一定范圍內的，往往在數(shù)值相近的決策屬性值之間映射到條件屬性值后，條件屬性值沒有表現(xiàn)出嚴格單調遞增情況;這種誤差也是在一定范圍內，一定范圍的誤差在一個小區(qū)間內時，對該區(qū)間會產(chǎn)生較大的影響，而當放到一個大的區(qū)間內，產(chǎn)生的影響明顯較小.按照這樣的思路，前面定義的模糊遞增隸屬函數(shù)值會隨著區(qū)間數(shù)p的減小及單個區(qū)間范圍的增大而出現(xiàn)大于等于原來值的趨勢，當然中間可能出現(xiàn)波動，如果出現(xiàn)波動，文中稱誤差在該區(qū)間范圍內作用是不穩(wěn)定的;當p減小到一定值后，由于誤差的作用穩(wěn)定變小，模糊遞增隸屬函數(shù)值會隨p的減小而穩(wěn)定地大于或等于前面的值，這時可稱誤差在該范圍內的作用是穩(wěn)定的.當p=1時，模糊遞增隸屬函數(shù)因為缺少比較對象而失去作用.由以上分析得到命題3.

命題3當p為偶數(shù)且大于等于4時，如果模糊遞增隸屬函數(shù)值不為零，那么以p/2個數(shù)進行Ψ劃分所得的模糊遞增隸屬函數(shù)值必然大于等于以p個數(shù)進行Ψ劃分的模糊遞增隸屬函數(shù)值.

證明設當決策屬性集合D'以p個數(shù)進行Ψ劃分時，可得到?jīng)Q策屬性區(qū)間集合…，Ωp}，通過映射f，可得Z劃分的條件屬性區(qū)間集合ΓCi={Γ1，Γ2，…，Γp}，當決策屬性集合D'以p/2個數(shù)進行Ψ劃分時，可得決策屬性區(qū)間集合，通過映射f，可得Z劃分的條件屬性區(qū)間集合.根據(jù)前面的定義，由于p為偶數(shù)，容易得當1≤k≤p/2－1時設α∧β∧γ.當α≤β≤γ時由于模糊隸屬函數(shù)值不為0，可得minΓ2k+2≥minΓ2k+1≥minΓ2k≥minΓ2k－1，那么有

根據(jù)命題3和前面的分析，可得出命題4.

命題4如果決策屬性確實模糊單調遞增依賴于條件屬性，那么模糊單調遞增隸屬函數(shù)必然是在p=2或p=3時取得最大值;否則，判定決策屬性依決策表不能確定模糊單調遞增依賴于條件屬性.

證明當p=1時，模糊單調遞增隸屬函數(shù)不存在.依命題3，當p=2或p=3時，模糊單調遞增隸屬函數(shù)值必然大于等于p=4或p=6時的值，也大于等于p是2或3的偶數(shù)倍時的值.如果決策屬性和條件屬性確實是單調遞增依賴關系，那么出現(xiàn)模糊單調遞增而不嚴格單調遞增的原因是受到了干擾因素的影響，如果它們之間的單調遞增依賴關系較強，那么受干擾的影響會較小，否則會較大.

一定的干擾因素在小范圍內的影響明顯大于在大范圍內的影響，但當p=2時模糊單調遞增隸屬函數(shù)值并不一定大于等于p=3時的值，這是因為兩個劃分單個區(qū)間的范圍可能相差不是很大，而受干擾的元素在區(qū)間中的分布不均勻，劃分的區(qū)間中心點位置不一樣.在命題3中，p/2所劃分的區(qū)間中心點明顯包含在p中，p=2時的模糊單調遞增隸屬函數(shù)值大于等于p=3時的值是大概率事件，因此如果p=5時的模糊單調遞增隸屬函數(shù)值大于p=2或p=3時的值，而p=5時所劃分的單個區(qū)間范圍小于p=2時所劃分的單個區(qū)間范圍的一半，那么只有兩種可能:(1)決策屬性并非單調遞增依賴于條件屬性;(2)決策表中受干擾的元素過多或者決策屬性和條件屬性之間的單調遞增依賴關系不明顯或強度不夠.由此可判定決策屬性依決策表不能確定模糊單調遞增依賴于條件屬性.

綜合上述分析可得出如下結論:p的值從k'(k'＜n)開始逐漸變小至2時，如果模糊遞增隸屬函數(shù)的值不等于0，且后面的隸屬函數(shù)值大于等于前面的隸屬函數(shù)值，當p=2或p=3時隸屬函數(shù)值最大，則可以認為模糊遞增隸屬函數(shù)值從p=k'開始是穩(wěn)定增大的，且干擾誤差在范圍內是穩(wěn)定的，決策屬性D與條件屬性Ci是模糊單調遞增依賴的，模糊單調遞增程度取決于模糊遞增隸屬函數(shù)值，否則是不單調遞增依賴的.

2.4 算法的步驟

1)用二維數(shù)組存放決策表D［n，m+1］，其中第m+1列為決策屬性，第1至m列為條件屬性.

2)對決策屬性按從小到大的順序進行排列，交換相應的行，即對第m+1列的值按從小到大排序，交換對應的行.

3)考察第i個條件屬性值與決策屬性值的模糊單調遞增依賴關系.{Selectp＜n;

for(L=pto 2)

{初始化存放模糊單調遞增隸屬函數(shù)的數(shù)組;

求區(qū)間距離和區(qū)間中心點;

forv=1 ton∥劃分區(qū)間，并求相應的隸屬函數(shù){映射到條件屬性i，并劃分區(qū)間;

forw=1 toL－1

{求相鄰區(qū)間的隸屬函數(shù)值;

求這次劃分的隸屬函數(shù)值;}}}}4)判斷是否是模糊單調遞增關系，求出最大的模糊隸屬函數(shù)值及其對應的索引號.

5)求出p→2過程中模糊單調遞增隸屬函數(shù)值開始穩(wěn)定遞增的p值.

6)求出干擾因素的穩(wěn)定作用范圍.

該算法的時間復雜度主要集中在步驟2)的排序和步驟3)中，由于步驟3)存在三重循環(huán)，因此算法的時間復雜度為O(n3).

3 算法在污水處理中的應用

采用文中算法對UCI的污水數(shù)據(jù)［17］進行挖掘，找出與輸出因素有模糊單調遞增關系的輸入因素及其依賴程度，從而通過控制輸入來達到控制輸出的目的.由于UCI污水數(shù)據(jù)中存在不完備的數(shù)據(jù)，因此文中先過濾掉不完備的數(shù)據(jù)，提取出完備的決策表，得到246×38的完備數(shù)據(jù)信息表.其中樣本數(shù)據(jù)對象個數(shù)為246，對象屬性個數(shù)為38，前22個屬性為對象的輸入數(shù)據(jù)屬性(文中將它們作為決策表的條件屬性)，第23至29個屬性為對象的輸出數(shù)據(jù)屬性(文中將它們作為決策表的決策屬性).第24個數(shù)據(jù)屬性DBO-S是污水處理輸出的一個重要考察指標，文中把它作為唯一的決策屬性，考察22個輸入的條件屬性與該決策屬性的模糊單調遞增依賴關系.由于有一個樣本數(shù)據(jù)的DBO-S值是其它樣本數(shù)據(jù)的3倍，因此文中把該樣本作為噪聲樣本過濾掉，剩下245個樣本數(shù)據(jù).采用前面的模糊遞增函數(shù)和文中算法通過Matlab進行仿真計算，部分結果如表1所示.其中當模糊單調遞增依賴函數(shù)取最大值時參數(shù)ε設為0.1，表1中列出的條件屬性模糊單調遞增依賴函數(shù)最大值大多大于0.1，第21個屬性SED-D除外，但該屬性體現(xiàn)了模糊遞增隸屬函數(shù)的最大值也可能出現(xiàn)在p=3時.

從表1中可以發(fā)現(xiàn)，文中算法的仿真結果與前面的理論分析結果相一致，表明輸出的生物需氧量與輸入工廠的生物需氧量、化學需氧量和懸浮固體有模糊遞增依賴關系，并與一沉池的輸入生物需氧量和沉淀物、二沉池的生物需氧量和懸浮固體有模糊遞增依賴關系，依賴程度為μmax，而其它的條件屬性與決策屬性不存在明顯的模糊遞增依賴關系，因此通過控制這些量的輸入即可達到控制輸出生物需氧量的目的.很明顯，文中算法還可以應用于其它工業(yè)和社會決策表的數(shù)據(jù)挖掘，并產(chǎn)生相應的控制策略.

表1 DBO-S與條件屬性的模糊單調遞增依賴關系1)Table 1 Fuzzy monotone increasing dependent relationship between DBO-S and condition attributes

4 結語

在模糊粗糙決策表的理論基礎上，文中提出了基于決策表的模糊粗糙單調算法.首先通過區(qū)間映射定義了模糊單調依賴關系的概念，討論了模糊單調遞增依賴關系的參數(shù)及性質，并證明了相關命題，然后將該算法應用到污水處理中，取得了良好的效果.文中算法通過模糊單調關系挖掘出對決策輸出的變化有重要影響的條件輸入屬性，等價關系等已有方法不容易在輸入與輸出之間建立模糊單調關系，而模糊單調關系在復雜的輸入輸出環(huán)境中比等價關系和嚴格單調關系更加普遍，因此文中算法是對模糊粗糙集理論的豐富和發(fā)展，改善了已有方法不容易在輸入與輸出之間建立模糊單調關系的局限性，今后將進一步完善文中算法，并將其應用于醫(yī)療(如檢查某藥物對某些癥狀的治療效果)等其它方面.

［1］Pawlak Z.Rough sets［J］.International Journal of Computer and Information Sciences，1982，11(5):341-356.

［2］Zadeh L.Fuzzy sets［J］.Information and Control，1965，8(3):338-353.

［3］Polkowski L，Skowron A，Zytkow J.Rough foundations for rough sets［M］∥Lin T Y，Wildberger A M.Soft compu-ting:rough sets，fuzzy logic，neural networks，uncertainty management，and knowledge discovery.San Diego:Society of Computer Simulation，1995:142-149.

［4］Lin TY.Neighborhood systems and approximation in relational databases and knowledge bases［C］∥Proceedings of the Fourth International Symposium on Methodologies of Intelligent Systems(Poster Session).Charlotte:Oak Ridge National Laboratory，1989:75-86.

［5］Greco Salvator，Matarazzo Benedetto，Slowinski Roman.Rough sets theory formulticriteria decision analysis［J］.European Journal of Operational Research，2001，129(1):1-47.

［6］Dubois D，Prade H.Rough fuzzy sets and fuzzy rough sets［J］.International Journal of General Systems，1990，17(2/3):191-209.

［7］Wu C J.Guaranteed accurate fuzzy controllers formonotone functions［J］.Fuzzy Sets and Systems，1997，92(1):71-82.

［8］Chou Te-shun，Lee Edward T.Fuzzy monotone functions and applications［C］∥Proceedings of IEEE International Conference on Fuzzy Systems，IEEE World Congress on Computational Intelligence.Anchorage:IEEE，1998:829-834.

［9］Van Broekhoven Ester，De Baets Bernard.Monotone Mamdani-Assilian models under mean of maxima defuzzification［J］.Fuzzy Sets and Systems，2008，159(21):2819-2844.

［10］Grigorenko Olga.Degree of monotonicity in aggregation process［C］∥Proceedings of IEEE International Conference on Fuzzy Systems.Barcelona:IEEE，2010:1080-1087.

［11］Van Broekhoven Ester，De Baets Bernard.Only smooth rule bases can generate monotone Mamdani-Assilian models under center-of-gravity defuzzification［J］.IEEE Transactions on Fuzzy Systems，2009，17(5):1157-1174.

［12］Seki Hirosato，Ishii Hiroaki，Mizumoto Masaharu.On the monotonicity of fuzzy-inference methods related to T-S inferencemethod［J］.IEEE Transactions on Fuzzy Systems，2010，18(3):629-634.

［13］Ye Mingquan，Wu Changrong.Decision table decomposition using core attributes partition for attribute reduction［C］∥Proceedings of the 5th International Conference on Computer Science＆Education.Hefei:IEEE，2010:23-26.

［14］Zhang Shuhong，Sun Jianxun.Continuous value attri-bute decision table analysis method based on fuzzy set and rough set theory［C］∥Proceedings of the Sixth International Conference on Fuzzy Systems and Knowledge Discovery.Tianjin:IEEE，2009:75-79.

［15］張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法［M］.北京:科學出版社，2001:19-30.

［16］陳水利，李敬功，王向公.模糊集理論及其應用［M］.北京:科學出版社，2005:2-23.

［17］Frank A，Asuncion A.{UCI}machine learning repository［DB/OL］.(1993-06-01)［2010-10-01］.http:∥archive.ics.uci.edu/ml/datasets/Water+Treatment+Plant.