基于可辨識矩陣的屬性約簡算法及應用

陳志恩， 田彥山， 馬 旭

(寧夏師范學院 數學與計算機科學系,寧夏 固原756000)

1 引 言

粗糙集理論[1-2]由波蘭數學家Pawlak.Z于1982年提出，它是一種新的處理信息系統中不精確、不完整、不一致數據的數學工具，近年來已在數據決策分析、機器學習與模式識別等多個鄰域得到了廣泛的應用[3-4].

屬性約簡[5-7]是粗糙集理論研究的主要內容之一，由于在原始數據集中，往往存在大量冗余和不確定性的信息，嚴重影響到后續數據挖掘和處理的效率.因此，通過刪除冗余屬性，能獲得數據集合的本質信息和保持原始數據分類信息的完整性，從而提高數據的分類質量.目前粗糙集屬性約簡方法的研究已經取得了很多成果,各種高效的啟發式約簡算法相繼被提出,這些啟發式約簡算法主要目的是尋找一個約簡或近似約簡.譬如，鮑迪等針對區間值決策表中對象集動態增加的情況，提出了區間值決策表的正域單增量和組增量啟發式屬性約簡算法[8]；陳曦將新定義的兩種信息熵結合，作為直覺模糊關系下信息系統的信息熵，并以該信息熵為啟發式算子構造了一種屬性約簡算法[9]；陳東曉等基于屬性重要度分別設計了熵協調和熵不協調的決策形式背景下的屬性約簡算法[10]；李萍等以粗糙模糊度為啟發式算子對信息系統進行屬性約簡[11]；鄧大勇等提出可變正區域約簡，允許正區域在一定的范圍內發生變化，從而提高泛化能力[12]；陳志恩等以粒包含度矩陣中隱含的信息作為啟發式算子，設計了一種相容決策信息系統屬性約簡算法[13].

本文針對決策信息系統最大分部約簡問題，從代數角度構建了一種新的啟發式屬性約簡算法.該算法在核屬性集基礎上，將其它屬性按其屬性重要性大小逐次添加到核屬性集中，再根據啟發式算子對新的屬性集做出最大分布約簡的判斷.重復以上步驟，直到找到最大分布約簡.算例分析表明該算法的有效性和可行性.

2 基本概念

設S=(U,A,D)為一決策信息系統.其中U={x1,x2,…,xn}為對象的非空有限集合，即論域；A={a1,a2,…,am}為屬性的非空有限集合；對任意a∈A,都存在映射aj∶U→Vj,Vj稱為屬性a的值域，j=1,2,…,m；任意B?A都對應U上的不可辨識關系

IND(B)={(x,y)∈U×U|?aj∈B,aj(x)=aj(y)},

易見IND(B)為U上的一個等價關系，x基于B的等價類[x]B可表示為[x]B={y∈U|xBy},所有等價類的集合記為U/IND(B),簡記為U/B；決策屬性D導出的劃分為U/D={D1,D2,…,Dr}.

若記

(1)

定義1[14]設S=(U,A,D)為一決策信息系統，B?A,若對任意x∈U， 有σA(x)=σB(x),則稱B為最大分布協調集.若B為最大分布協調集，且B的任何真子集不是最大分布協調集，則稱B為最大分布約簡.

最大分布協調集保持了論域U中每個對象x在劃分U/B下最大決策類不變的性質.

定義2設S=(U,A,D)為一決策信息系統，B(B?A)為S的最大分布協調集,若對任意a∈B,x∈U， 有σB(x)≠σB-{a}(x),則稱a為B中必要的，否則稱a為B中不必要的.B中所有必要屬性組成的集合稱為B的核，記為CORE(B).

如果對每一個a∈B，a都為B中必要的，則稱B為獨立的，否則稱B是依賴的或不獨立的.由此可知若B是最大分布協調集，且B是獨立的.則B是S的一個最大分布約簡.

定理1[14]設S=(U,A,D)為一決策信息系統，B?A,則B為最大分布協調集當且僅當對任意x，y∈U， 當σB(x)≠σA(x)時有[x]B∩[y]B=?.

定義3[14]設S=(U,A,D)為一決策信息系統，U/A={C1,C2，…,Cm},記

D*={([x]A,[y]A),σA(x)≠σA(y)},

(2)

用fk(Ci)表示屬性ak關于Ci的取值，則定義

(3)

為Ci與Cj的最大分布可辨識屬性集.稱MA={Dl(Ci,Cj)∶i,j≤m} 為S的最大分布可辨識屬性矩陣,簡稱可辨矩陣.

顯然，MA是對稱矩陣，即Dl(Ci,Cj)=Dl(Cj,Ci)(?i,j≤m} .

3 基于可辨矩陣的屬性約簡算法

3.1 基于可辨矩陣的屬性約簡

決策信息系統的最大分布約簡就是在條件屬性集中尋找一個最小的屬性集，該屬性集與條件屬性全集所確定的最大決策分布完全一致.

定理2設S=(U,A,D)為目標信息系統，MA={Dl(Ci,Cj)∶i,j≤l} 為S的最大分布可辨識屬性矩陣，對任意B?A,記

(4)

其中

若B滿足條件：(i)γ(B)=1；(ii)對任意a∈B,γ(B-{a})=0,則B為S的一個最大分布約簡.

證(i) 若γ(B)=1成立，則對任意Ci,Cj(i,j≤m),使得B∩Dl(Ci,Cj)≠? ,取x,y∈U,使得Ci=[x]A,Cj=[y]A,則有σA(x)≠σA(y),又因為B∩Dl(Ci,Cj)≠? ,則存在ak∈B,必有ak∈Dl(Ci,Cj),于是fk(Ci)≠fk(Cj),從而fk(x)≠fk(y),這說明[x]B∩[y]B=?,于是由定理1知，B為S的一個最大分布協調屬性集.

(ii) 對任意a∈B,γ(B-{a})=0,則存在Ci,Cj,(i,j≤m),使得

(B-{a})∩Dl(Ci,Cj)=? ,

取x,y∈U,使得Ci=[x]A,Cj=[y]A,則有σA(x)≠σA(y).因為(B-{a})∩Dl(Ci,Cj)=? ,則對任意ak∈B,必有ak?Dl(Ci,Cj),于是fk(Ci)=fk(Cj),從而fk(x)=fk(y),這說明

[x]B-{a}∩[y]B-{a}≠?,

由定理1知，B-{a}不是最大分布協調屬性集，再由a的任意性知，B是獨立的.

綜合(i)、(ii)可知，B為S的一個最大分布約簡.

3.2 算法原理和描述

定義4設S=(U,A,D)為目標信息系統，MA={D(Ci,Cj)∶i,j≤l} 為S的最大可辨識屬性矩陣，B=(a1,a2,…,ar) (B?A)為S的一個最大分布約簡，對任意ak∈B(k=1,2,…,r),記

(5)

顯然，ξ(ak)的值越大，則表明屬性ak最大分布決策分類的能力就越強，反之，則越弱.因此可利用ak在最大分布可辨識屬性矩陣中出現的頻數的大小來評價該屬性的重要性.

在上述理論的基礎上，本文以γ(B)為啟發式算子，給出一種決策信息系統S的最大分布約簡算法.該算法以最大分布核屬性集為起點，然后根據定義4，逐次選擇最重要的屬性添加到核屬性集中，再根據定理2對新的屬性集做出最大分布約簡的判斷.重復以上步驟，直到滿足終止條件.具體算法描述如下：

(i) 求核算法

輸入：決策信息系統S=(U,A,D)；

輸出：最大分布核屬性集CORE(A)；

具體步驟：

第1步 賦值CORE(A)=?；

第2步 計算S的最大分布可辨識屬性矩陣MA；

第3步 ?ak∈A,計算γ(A-{ak}),如果γ(A-{ak})≠1,則令CORE(A)=CORE(A)∪{ak},直到遍歷條件屬性全集中的每一個屬性；

第4步 輸出CORE(A),算法結束.

(ii) 基于可辨矩陣的屬性約簡算法

輸入：決策信息系統S=(U,A,D)；

輸出：決策信息系統S的一個最大分布約簡B；

具體步驟：

第1步 計算S的最大分布可辨識屬性矩陣MA及CORE(A)；

第2步 ?ak∈ACORE(A),計算ξ(ak)；

第3步 令B=CORE(A)；

第4步 計算γ(B),如果γ(B)=1,則轉到第6步，否則轉到第5步；

第6步 輸出B,算法結束.

在求核算法中，第2步計算可辨識矩陣MA的時間復雜度為O(|A||U|2),第3步計算核屬性需要循環遍歷所有屬性，因此時間復雜度為O(|A||U|)；在基于可辨矩陣的屬性約簡算法中，第1步算法的時間復雜度為O(|A||U|2),第2步計算ξ(ak)的時間復雜度為O((|A|-|CORE(A)|)|U|),第3、4、5、6步皆為賦值操作，其時間復雜度為O(|1|).因此，計算基于可辨矩陣的屬性約簡最終時間復雜度為O(|A||U|2).

4 算例分析

給定一個決策信息系統S=(U,A,D),其中A={a1,a2,a3,a4}為條件屬性，D=g0gggggg為決策屬性(見表1).求解該決策信息系統的最大分布約簡.

表1 決策信息系統S

在表1中，由等價關系可得

U/D={D1，D2},其中D1={x1,x4,x6,x8},D2={x2,x3,x5,x7}；

U/A={C1，C2，C3，C4},其中C1={x1,x3,x5},C2={x2,x6,x8},C3={x4},C4={x7}.

按照基于可辨矩陣的屬性約簡算法步驟：

首先，根據公式(1)計算論域中每個對象的最大決策分布(為了簡化表示，用σA(Ci)代替σA(xk),其中xk∈Ci)為σA(C1)={D2},σA(C2)={D2},σA(C3)={D1},σA(C4)={D2}；

根據公式(2)計算：D*={(C1,C2), (C1,C3), (C2,C4), (C3,C4)}.

根據公式(3)計算得S的分布可辨識屬性矩陣為

其次，根據公式(4),?ak∈A,計算γ(A-{ak})得

γ(A-{a1})=γ(A-{a3})=γ(A-{a4})=1,γ(A-{a2})=0,

從而得核屬性集CORE(A)={a2},ACORE(A)={a1,a3,a4}；

第三，根據公式(5),?ak∈ACORE(A),分別計算ξ(ak)得：ξ(a1)=ξ(a4)=7,ξ(a3)=6；

第四，令B=CORE(A),計算得γ(B)=0,然后將a1(或a4)添加到核屬性中去，并令B={a2,a1}(或B={a2,a4})，經計算γ(B)=1,從而算法結束，于是得{a2,a1}和{a2,a4}即為該決策信息系統S的兩個最大分布約簡.

根據最大分布約簡{a2,a1},得到四組簡化的最大分布決策規則表達式為

(a1,1)∧(a2,3)→(d,0)； (a1,2)∧(a2,3)→(d,1)；
(a1,3)∧(a2,3)→(d,1)； (a1,3)∧(a2,1)→(d,0).

5 結 論

傳統的屬性約簡是在可辨識屬性矩陣基礎上，通過析取運算逐一消去所有Dl(Ci,Cj)中重復的元素，最后找到最大分布約簡標準最小表達式.本文從代數的角度構建了一種新的啟發式屬性約簡算法.該算法在最大分布可辨識屬性矩陣基礎上，以最大分布核屬性集為起點，然后利用單個屬性在可辨識屬性矩陣中出現的頻數來評價該屬性的重要性，并逐次選擇最重要的屬性添加到核屬性集中，再根據啟發式算子對新的屬性集做出最大分布約簡的判斷.重復以上步驟，直到找到最大分布約簡.該算法簡化了屬性約簡過程，提高了屬性約簡的速度.

致謝作者非常感謝相關文獻對本文的啟發以及審稿專家提出的寶貴意見.