基于貼進度的模糊決策表屬性約簡啟發(fā)式算法

羅秋瑾

（云南財經(jīng)大學統(tǒng)計與數(shù)學學院，昆明 650221）

波蘭科學院院士Pawlak〔1〕教授于1982 年提出的粗糙集理論是處理知識中不完整、不確定性問題的強有力工具，經(jīng)過幾十年的發(fā)展，經(jīng)典的粗糙集模型不斷滲透到其他相關(guān)領(lǐng)域，近年來其廣泛應用于醫(yī)學、金融、專家系統(tǒng)、知識發(fā)現(xiàn)、機器學習、數(shù)據(jù)挖掘、決策分析等多個領(lǐng)域中〔2〕，并且取得了很好的效果，得到了廣泛的關(guān)注。

法國學者Dubois 和Prade〔3〕提出的模糊粗糙集就是為了解決粗糙集離散化過程的信息損失問題。模糊粗糙集將粗糙集和模糊集集成在一起，是粗糙集的擴展，它能同時處理數(shù)據(jù)中的模糊性和粗糙性〔4-5〕。所以，有理由相信在處理復雜環(huán)境中的不確定性時，模糊粗糙集比粗糙集和模糊集更有效。給定一個模糊信息系統(tǒng)，每個模糊條件屬性對決策分類的貢獻不盡相同，有的貢獻非常大，有的貢獻比較小，甚至沒有貢獻。這意味著需要找出對分類起主要作用的條件屬性，刪除其中沒有貢獻的條件屬性，用以提高運算效率，此過程稱為屬性約簡〔6〕。

目前幾乎所有的關(guān)于基于模糊粗糙集的屬性約簡的研究都是從文獻〔7〕開始的，但是由于這種方法完全是從形式上把經(jīng)典粗糙集中相應的方法甚至符號照搬過來，對基于模糊粗糙集的屬性約簡的本質(zhì)沒有清楚的認識，因而導致設(shè)計的屬性約簡算法不收斂。對此，Cheng 等〔8〕通過模糊粗糙集的粒結(jié)構(gòu)引入辨識矩陣的方法來計算屬性約簡，但是通過實例發(fā)現(xiàn)，某些情況下求出核屬性后條件屬性卻無法進行有效約簡。

本文提出一種新的約簡算法，首先利用貼進度生成可辨識矩陣，再由可辨識矩陣得到一種改進的計算相對核屬性的算法，再基于核屬性生成最小約簡的啟發(fā)式算法，最后用實例說明此方法的有效性。

1 基本概念

定義1 設(shè)U 是一個對象集合，A 是一個非空實數(shù)值屬性集合，稱（U，A）是一個模糊信息系統(tǒng)。如果把A 中的屬性分成條件屬性和決策屬性，則稱模糊信息系統(tǒng)為模糊決策系統(tǒng)〔9〕。

貼進度用來刻畫兩個模糊集的接近程度〔9〕。

定義2 設(shè)映射N：F（X）×F（X）→［0，1］滿足以下條件：

（1）?A∈F（X），N（A，A）＝1；

（2）?A，B∈F（X），N（A，B）＝N（B，A）；

（3）若?A，B，C∈F（X），?x∈X 滿足：｜A（x）-C（x）｜≥｜A（x）-B（x）｜，則有N（A，C）≤N（A，B），則稱映射N 為F（X）上的貼進度，稱N（A，B）為A 與B的貼進度。

定義3 設(shè)映射N：F（X）×F（X）→［0，1］，?A，B∈F（X），當X=｛x1，x2，…，xn｝時，令

可以驗證此定義的N（A，B）滿足貼進度定義的3 個條件〔10〕。

利用貼進度定義兩個模糊集的模糊相似關(guān)系〔11〕。

定義4 設(shè)R 是論域U 上的模糊關(guān)系，已知U上的n 個模糊集Ai，i=1，2，…，n，?x，y∈U，定義R（x，y）＝N（A，B）。

定義5 設(shè)（U，R）是模糊信息系統(tǒng)，X?U 是經(jīng)典集合，稱R（X）是X 關(guān)于（U，R）的模糊下近似，其隸屬函數(shù)定義為〔11〕：

定義6 設(shè)U=｛x1，x2，…，xn｝，MD（U，R）是一個n×n 矩陣（cij），稱為（U，R∪D）的可辨識矩陣〔12〕，定義為：

（1）（cij）=｛R：1-R（xi，xj）≥λi｝，λi=Sim（R）（［xi］D）（xi），λj＝Sim（R）（［xi］D）（xj），如果λi>λj；

（2）（cij）=?，其他。

其中Sim（R）（xi，xj）=∧（1-∨i≠j｜xi-xj｜）。

2 基于貼進度的屬性約簡

基于模糊粗糙集的屬性約簡的基本思想就是保持決策類相對于條件屬性的正域不變的前提條件下，刪除其中不必要或不重要的條件屬性。人們往往期望找到具有最少條件屬性的約簡方法，即最小約簡。然而遺憾的是，已經(jīng)有學者證明了找出一個決策表的最小約簡是NP-hard 問題。導致NPhard 問題的主要原因是屬性的組合爆炸問題。在很多屬性約簡算法中，一般都要求先求出核屬性集，然后再由核屬性通過啟發(fā)式知識擴展到最小約簡。因此，求核成了屬性約簡求解的關(guān)鍵步驟。

2.1 對原算法的一些分析Cheng 等〔8〕通過模糊粗糙集的粒結(jié)構(gòu)引入辨識矩陣的方法，提出計算相對核的方法，CoreD（R）＝｛R：cij=｛R｝｝，i≥1，j≤n，從而得到約簡屬性集為RedD（R）=∪RoreD（R）。但此方法是由經(jīng)典粗糙集照搬到模糊粗糙集，導致方法存在一定的問題。比如通過實例計算，發(fā)現(xiàn)此方法在某些時候無法對條件屬性集進行約簡，即此時RedD（R）=R。所以這時候僅僅根據(jù)相對核屬性得到約簡屬性集的算法就失效了，需要對原方法進行改進。

2.2 改進算法針對以上問題，本文重新定義了基于可辨識矩陣的條件屬性的相對重要度，不僅要考慮矩陣中僅出現(xiàn)的單個屬性，而且還要兼顧該屬性出現(xiàn)的總的頻率數(shù)，由相對重要度計算出相對核屬性后再進而求出相對條件屬性約簡，再計算約簡條件屬性和決策屬性的貼進度，大于預先設(shè)定的某個閾值λ 時，則輸出該約簡。

定義7 設(shè)有模糊決策表（U，A，d），屬性ai∈A相對于決策屬性d 的相對重要性，其中｜ai｜表示在MD（U，R）中cij=ai的頻率數(shù)，｜∪ai｜表示cij中所有包含ai項的頻率數(shù)。

基于貼進度的模糊決策表屬性約簡算法：

輸入：模糊決策表（U，A，D），其中A＝｛a1，a2，…，an｝。

輸出：A 的約簡Red。

（1）計算基于貼進度的可辨識矩陣MD（U，R）；

（2）計算MD（U，R）中γ（ai），取γ（ai）中最大值，令Red=｛ai｝；

（3）將MD（U，R）中含Red 的項全部置為?，再計算γ（ai，aj），其中aj∈A-Red，取γ（ai，aj）中最大值，令Red=｛ai，aj｝；

（4）計算N（Red，d），如果N（Red，d）≥λ，則輸出約簡Red，否則轉(zhuǎn)到步驟（3）。

3 實例說明

表1 是一個模糊決策表，該決策表的論域U=｛x1，x2，…，x6｝，條件屬性集A=｛a1，a2，a3｝和決策屬性｛d｝。

表1 模糊決策表

由決策屬性d 得到兩個劃分分別為：X1=｛x1，x3，x6｝，X2=｛x2，x4，x5｝，則

從而計算出相對核屬性為｛a2｝，再將含a2的項置為?，從而得到

得到相對約簡｛a1，a2｝，此時屬性｛a1，a2｝對于決策屬性集d 的貼進度為0.84>0.8，輸出約簡｛a1，a2｝。

4 結(jié)論

本文引入貼進度提出一種改進的可辨識矩陣的生成算法，進而提出一種新的模糊決策表的屬性約簡算法，將原算法約簡不了的情況進行改進，實驗表明，該算法能降低一定的時間復雜度，并能處理規(guī)模較大的決策表。但模糊決策表類型較為復雜，此算法僅對其中的一種有效，在后續(xù)的研究中將逐步解決其他類型的決策表的屬性約簡問題。