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

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

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

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

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

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

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

例 1：集合 A={a，b，c，d，e}表示一堆蘋果，其中蘋果有兩種不同的顏色，紅色(red)和綠色(green)。我們通過蘋果與顏色之間的對應(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)，一個蘋果可能具有不同的顏色，那么它對應(yīng)的顏色屬性從圖1來看就不是唯一的，也就不具備單值性，現(xiàn)在我們以蘋果的顏色為基準(zhǔn)，通過下面的變化使其具備單值性。該變化顯化了局部單值化，局部單值化的形就是新的類。這樣，我們就可以得到如圖2所示的結(jié)果。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表7 簡化后的決策表Tab.7 Predigested decision table

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

表8 簡化后的決策表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可以得到一個決策規(guī)則表，如表9所示。

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

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

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

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

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

5 結(jié)束語

本文運(yùn)用泛系單值化思想的兩種方法對粗糙集理論中的決策表及決策規(guī)則問題進(jìn)行分析，給出了一種對決策表求決策規(guī)則的算法。通過對實(shí)際例子的應(yīng)用，證明算法是有效可行的，并且比通常我們所應(yīng)用的粗糙集理論中的分析方法簡潔易用。不難發(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].北京：中國人民大學(xué)出版社，1990.

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

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

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