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

陳志恩， 田彥山， 馬 旭

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

1 引 言

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

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

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

2 基本概念

設S=(U,A,D)為一決策信息系統(tǒng).其中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)為一決策信息系統(tǒng)，B?A,若對任意x∈U， 有σA(x)=σB(x),則稱B為最大分布協(xié)調集.若B為最大分布協(xié)調集，且B的任何真子集不是最大分布協(xié)調集，則稱B為最大分布約簡.

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

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

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

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

定義3[14]設S=(U,A,D)為一決策信息系統(tǒng)，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 基于可辨矩陣的屬性約簡

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

定理2設S=(U,A,D)為目標信息系統(tǒng)，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的一個最大分布協(xié)調屬性集.

(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}不是最大分布協(xié)調屬性集，再由a的任意性知，B是獨立的.

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

3.2 算法原理和描述

定義4設S=(U,A,D)為目標信息系統(tǒng)，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在最大分布可辨識屬性矩陣中出現(xiàn)的頻數(shù)的大小來評價該屬性的重要性.

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

(i) 求核算法

輸入：決策信息系統(tǒng)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) 基于可辨矩陣的屬性約簡算法

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

輸出：決策信息系統(tǒng)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步計算核屬性需要循環(huán)遍歷所有屬性，因此時間復雜度為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 算例分析

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

表1 決策信息系統(tǒng)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}.

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

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

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

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

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

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

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

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

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

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

(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 結 論

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

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