泛系單值化在粗糙集決策表分析中的研究

楊嘯，林和，毛連魁，袁曉娟

(蘭州大學(xué) 信息科學(xué)與工程學(xué)院，蘭州 730000)

波蘭數(shù)學(xué)家Z.Pawlak教授提出了用粗糙集理論來研究不完整數(shù)據(jù)、不精確知識(shí)的表達(dá)、學(xué)習(xí)、歸納等，已在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域中得到了較為廣泛的應(yīng)用[1，2]。在粗糙集理論中，等價(jià)關(guān)系將論域分為不同的等價(jià)類，各個(gè)等價(jià)類之間與泛系單值性存在相同的特征，這樣，以泛系觀來看等價(jià)關(guān)系劃分整個(gè)論域的過程與泛系單值化的過程相似。

1 形影關(guān)系與泛系單值化

形影關(guān)系[3]是泛系理論中廣義的對(duì)應(yīng)關(guān)系，如因果關(guān)系、映射關(guān)系等。傳統(tǒng)的粗糙集理論是以等價(jià)關(guān)系為基礎(chǔ)的。通過研究發(fā)現(xiàn)等價(jià)關(guān)系也是一種形影關(guān)系，這樣形影關(guān)系將粗糙集理論和泛系理論巧妙的聯(lián)系起來。把等價(jià)關(guān)系相應(yīng)地轉(zhuǎn)化為形影關(guān)系，有利于對(duì)粗糙集理論及事物的認(rèn)識(shí)和理解。本文所提到的泛系單值化方法亦是建立在形影關(guān)系之上，并且將其應(yīng)用在粗糙集理論中。

針對(duì)復(fù)雜事物之間的單值對(duì)應(yīng)關(guān)系，在多數(shù)情況下是以類類對(duì)應(yīng)進(jìn)行表述，當(dāng)一個(gè)類和另一個(gè)類對(duì)應(yīng)時(shí)，前一個(gè)類的內(nèi)涵就和后一個(gè)類的內(nèi)涵單值對(duì)應(yīng)，此時(shí)，類內(nèi)元素之間的關(guān)系是模糊的，而類間關(guān)系是清晰的，類類對(duì)應(yīng)代替了原來元素和元素的對(duì)應(yīng)，元素和元素之間的關(guān)系復(fù)雜，但清晰；類類間的對(duì)應(yīng)簡(jiǎn)單，但類內(nèi)又模糊。這既是用簡(jiǎn)單、模糊代替了復(fù)雜、清晰。這是人的一種運(yùn)籌策略的顯生，是一種駕簡(jiǎn)馭繁的方法，所以從大量的元素和元素的對(duì)應(yīng)中找出一種單值對(duì)應(yīng)，哪怕這種單值對(duì)應(yīng)是一種廣義化的，也是人的一種認(rèn)識(shí)升華和一種對(duì)規(guī)律的尋求。單值化是可觀控性的基礎(chǔ)，什么時(shí)候單值化可行，什么時(shí)候就有相應(yīng)的可觀控性定理[4]。通過關(guān)系之間的單值化過程，找出類類之間的單值化。只要找出這種單值化對(duì)應(yīng)關(guān)系，它就是事物的一種規(guī)律。

應(yīng)用單值化觀點(diǎn)來分析粗糙集中的相容關(guān)系。

例 1：集合 A={a，b，c，d，e}表示一堆蘋果，其中蘋果有兩種不同的顏色，紅色(red)和綠色(green)。我們通過蘋果與顏色之間的對(duì)應(yīng)關(guān)系來構(gòu)造形影關(guān)系。如圖1所示。

圖1 蘋果與顏色之間構(gòu)造的形影關(guān)系圖Fig.1 The body-shadow relationships between apples and colors

從圖1我們發(fā)現(xiàn)，一個(gè)蘋果可能具有不同的顏色，那么它對(duì)應(yīng)的顏色屬性從圖1來看就不是唯一的，也就不具備單值性，現(xiàn)在我們以蘋果的顏色為基準(zhǔn)，通過下面的變化使其具備單值性。該變化顯化了局部單值化，局部單值化的形就是新的類。這樣，我們就可以得到如圖2所示的結(jié)果。

圖2給我們提供了一種直觀的分解。從這種分解中可以明顯地看出具有相同屬性的元素是可以根據(jù)不同的單值對(duì)應(yīng)劃入不同的等價(jià)類中，劃入相同等價(jià)類的元素必須符合該等價(jià)類對(duì)元素的限制。

2 不相容決策表單值化分析與決策規(guī)則

決策表[2]分為相容決策表與不相容決策表兩類。相容決策表本身就是單值性的，每一個(gè)對(duì)象的條件屬性值組合都是唯一對(duì)應(yīng)著一個(gè)決策屬性值，根據(jù)決策屬性值可以把表中所包含的對(duì)象分成基于決策屬性的等價(jià)類，且不相同等價(jià)類之間沒有交集。在不相容決策表中，一組條件屬性對(duì)應(yīng)多個(gè)不同的決策屬性值，這其實(shí)就是一種多值對(duì)應(yīng)，從而導(dǎo)致了決策規(guī)則的不相容。一般的解決方法就是從不相容的決策表中分解出相容的決策表。不相容決策表由不相容到相容的轉(zhuǎn)化就是一個(gè)典型的單值化過程。下面我們以例2來說明不相容決策表的單值化。

圖2 單值化后的蘋果-顏色形影關(guān)系Fig.2 Single-valued apple-color body-shadow relationships

例2：給出一個(gè)知識(shí)表達(dá)系統(tǒng)S=，其中a，b，c為條件屬性，d，e為決策屬性，如表1所示。

表1 決策表[2]Tab.1 Decision table

圖3 表1中的多值對(duì)應(yīng)關(guān)系Fig.3 Multiple-value relationships in Tab.1

可以把表中每個(gè)對(duì)象的條件屬性值的組合和決策屬性值組合分別看成向量組，顯然這些向量組之間存在著多值對(duì)應(yīng)關(guān)系，表中多值對(duì)應(yīng)關(guān)系如圖3所示。

根據(jù)以上分析可以很明顯的判定該表是一個(gè)不相容決策表。下面我們通過對(duì)表1的單值化來使表相容，如表2、表3、表4所示。

表2 第一個(gè)相容決策表Tab.2 The 1st consistent decision table

表3 第二個(gè)相容決策表Tab.3 The 2nd consistent decision table

表4 第三個(gè)相容決策表Tab.4 The 3rd consistent decision table

通過單值化，把表1分為了三個(gè)表組成的表組，且其中每一個(gè)表都買滿足等價(jià)類單值對(duì)應(yīng)，所以它們都是相容的決策表。由此，也可以分別得出相容的決策規(guī)則。

3 最小條件屬性組合單值化

最小條件屬性組合單值化方法是針對(duì)相容決策表，利用單值化思想，通過對(duì)相同決策屬性值的分組并通過特定規(guī)則得到?jīng)Q策規(guī)則的一種方法。其規(guī)則為：

規(guī)則1：一個(gè)條件屬性存在于任意一個(gè)分組seleT中的每一個(gè)對(duì)象組合中，則該條件屬性是此知識(shí)系統(tǒng)中可以省略的。(此規(guī)則也適用于不相容決策表)

規(guī)則2：任意兩個(gè)分組的 coreT中若存在相同的屬性，則將相同的屬性按照原來對(duì)象的組合放入seleT中。

規(guī)則3：若各組同屬同值集合可由包含屬性較少的集合所包含的屬性分辨，各組多余的屬性按原有對(duì)象的組合放入seleT中。

規(guī)則4：一個(gè)分組 coreT中的條件屬性組合，不能出現(xiàn)在其他分組的seleT中，若出現(xiàn)則，將其放入自己分組的seleT中。

規(guī)則5：若一個(gè)分組的coreT或者seleT為空，則在決策規(guī)則的導(dǎo)出時(shí)，只需要找出其對(duì)于其他決策規(guī)則最小可分辨組合即可。

規(guī)則6：由seleT推導(dǎo)出的決策規(guī)則不能與coreT導(dǎo)出的決策規(guī)則有相同的部分，如果存在相同的部分，則將seleT中含有相同部分的條件屬性組合刪除。

下面我們以例3來說明方法規(guī)則的應(yīng)用。

例3：給出一個(gè)知識(shí)表達(dá)系統(tǒng)決策表S=，其中a，b，c，d為條件屬性，e為決策屬性，如表5所示。

表5 決策表[2]Tab.5 Decision table

顯然我們這里給出的決策表是相容決策表，所以接下來所要做的就是將其根據(jù)決策屬性的屬性值對(duì)其進(jìn)行分組求同，結(jié)果如表6所示。

表6 分組后的決策表Tab.6 The decision table by grouping

分組求同后只需要對(duì)coreT和seleT進(jìn)行分析即可。根據(jù)算法規(guī)則2，e0的coreT與e1的coreT有相同部分，所以將相同部分放入 seleT中，如表7所示。

表7 簡(jiǎn)化后的決策表Tab.7 Predigested decision table

根據(jù)規(guī)則2從表7可以很清楚地看出屬性c是可省略條件屬性，將屬性c去掉，相應(yīng)地也簡(jiǎn)化了對(duì)coreT和seleT的分析。

表8 簡(jiǎn)化后的決策表Tab.8 Predigested decision table

通過方法給出的規(guī)則4整理之后，很明顯a1b0→e1是一條決策規(guī)則；d2→e2是一條決策規(guī)則；通過規(guī)則5可以推導(dǎo)出 a0→e0，b1d1→e0和 a1d1→e0是決策規(guī)則。

利用規(guī)則6可以得到一個(gè)決策規(guī)則表，如表9所示。

表9 決策規(guī)則表Tab.9 Decision rules table

通過觀察我們很明顯的發(fā)現(xiàn) a1d1→e0是不符合規(guī)則6的。所以將a1d1從表9中刪除。經(jīng)過上述步驟整理之后可以得到一個(gè)關(guān)于表5的決策規(guī)則組，即：

通過對(duì)上面例子的分析，得到一個(gè)最小的決策規(guī)則組，與表5出處[2]提供給的結(jié)果相符，說明方法是可行的。

4 泛系單值化思想推導(dǎo)決策表決策規(guī)則的算法描述

綜合上面所介紹的兩種泛系單值化方法，我們給出用 ADL[5]描述的算法DecisionRules。

5 結(jié)束語(yǔ)

本文運(yùn)用泛系單值化思想的兩種方法對(duì)粗糙集理論中的決策表及決策規(guī)則問題進(jìn)行分析，給出了一種對(duì)決策表求決策規(guī)則的算法。通過對(duì)實(shí)際例子的應(yīng)用，證明算法是有效可行的，并且比通常我們所應(yīng)用的粗糙集理論中的分析方法簡(jiǎn)潔易用。不難發(fā)現(xiàn)，泛系理論在粗糙集理論中的應(yīng)用，讓粗糙集理論在一定程度上得到了拓展和深化。

[1]Pawlak Z.Rough Set[J].International Journal of Information and Computer Science，1982，11(5)：341-356.

[2]曾黃麟.粗集理論及其應(yīng)用[M].重慶：重慶大學(xué)出版社，1996.

[3]吳學(xué)謀.從泛系看世界[M].北京：中國(guó)人民大學(xué)出版社，1990.

[4]李永禮，林和，劉瑩，等.粗糙集理論中的泛系單值化方法[J].計(jì)算機(jī)科學(xué)，2005，32，(8A)：4-6+23.

[5]劉大有，唐海鷹，孫舒楊，等.數(shù)據(jù)結(jié)構(gòu)[M].高等教育出版社，2001：5-8.

[6]蔣瑜，張娟，林和，等.基于區(qū)分矩陣的決策表相容性的判斷[J].甘肅科學(xué)學(xué)報(bào)，2006，18(2)：59-61.