一種基于屬性變化的增量約簡算法

程 妮

（運城學院公共計算機教學部，山西運城044000）

一種基于屬性變化的增量約簡算法

程 妮

（運城學院公共計算機教學部，山西運城044000）

隨著處理數據工具的發展，許多數據庫的屬性都是動態增加的。當屬性動態增加時，靜態的約簡方法消耗時間巨大，效率不高，針對這個缺陷，文中提出了屬性變化的增量約簡方法，通過增量技術計算增加屬性后的知識粒度，然后在新的知識粒度和原有約簡的基礎上，能夠在較短時間內找到新決策表的約簡，仿真結果表明所提算法是有效的。

屬性約簡;增量學習;知識粒度;決策表;粗糙集

粗糙集是一種新的軟計算工具用來分析和處理各種不確定性的、不精確的數據，已經引起國內外學者廣泛重視，成功地應用到圖像處理、特征選擇、規則提取、知識發現等領域[1]。屬性約簡是粗糙集中的一個重要操作，它就是保持信息系統分類能力不變的情況，把不重要的和刪除冗余的屬性刪掉。最近幾年來很多研究者已經提出了大量約簡方法。王磊[2]根據等價關系矩陣和知識粒度之間的關系，給出了屬性增刪時等價關系矩陣變化的規律，提出了基于知識粒度的矩陣屬性約簡方法；王國胤[3]從信息論觀點出發對粗糙集理論的基本概念和主要運算進行分析討論，提出了基于條件信息熵提出決策表的約簡算法；梁吉業[4]提出了信息量的啟發式屬性約簡算法，并通過實例說明該算法是有效的。上述的約簡方法都為靜態信息系統設計的，在實際中許多信息系統是隨著時間變化而變化的，靜態屬性約簡方法處理動態數據需要重新計算，造成時間和空間耗費巨大，故靜態約簡方法處理動態數據是無效的，為了克服這種缺陷，許多學者提出來增量約簡方法。[5-7]

增量技術是處理動態變化的有效技術，許多研究者已經成功地把增量技術運用到的啟發式屬性約簡中，并取得一定成果。我們發現大多增量約簡知識粒度已經被廣泛地應用到啟發式約簡中，由于很多數據庫的屬性隨著時間的變化而增加，靜態的約簡算法需要消耗大量的時間和空間，為了克服缺陷，提高效率，本文在知識粒度概念的基礎上，提出一種維度增量約簡算法，當決策表的屬性增加時，給出了增量計算知識粒度的相關定理和概念，并通過實驗表明所提算法是有效性。

1 粗糙集的相關知識

定義1[1]：一個信息系統是四元組S=(U,A=C?D,V,f)，其中U是非空有限對象集合，也稱為論域；其中C、D分別為條件屬性集和決策屬性集，其中Va是條件和決策屬性a的值，f：U×C?D→V為信息函數，即a∈C?D，x∈U有f(x,a)∈Va。

定義2[6]：給出一個決策表S=(U,A=C?D,V,f)，論域為U，U∕C={X1,X2,…,Xm}，我們定義的知識粒度為

2 知識粒度約簡算法

2.1 知識粒度基本知識

定義3[5]：給出一個決策表S=(U,A=C?D,V,f)，論域為U，C為條件屬性集，D為決策屬性集，則決策屬性D關于條件屬性C的相對知識粒度被定義為GD(D|C)=GD(C)-GD(C?D)。

定義4[5]：(屬性重要度1)：給出一個決策表S=(U,A=C?D,V,f)，對于?a∈C，屬性a在條件屬性C相對于決策屬性集D的重要性被定義為：

定義5[5]：(屬性重要度2)：給出一個決策表S=(U,A=C?D,V,f)，B?C，對于?a∈C-B，屬性集a在條件屬性C相對于決策屬性集D的重要性被定義為：

定義6[5]：給出一個決策表S=(U,A=C?D,V,f)，對 ?a∈C，若GD(D|C)=GD(D|C-{a})，則稱a是條件屬性C相對于決策屬性集D不必要的屬性，否則稱a是必要的屬性。

性質1給出一個決策表S=(U,A=C?D,V,f)，對?a∈C，屬性a為決策表S的必要的屬性，當且僅當Sig(a,C,D)＞0。

定義7[5]給出一個決策表S=(U,A=C?D,V,f)，決策表S的核為CoreC(D)={a∈C|Sig(a,C,D)＞0}。

定義8[1]給出一個決策表S=(U,A=C?D,V,f)，B?C，B為決策表S的屬性約簡當且僅當：（1）GD(D|B)=GD(D|C) ；（2）對于?a∈B，使得GD(D|B-{a})≠GD(D|C)。

2.2 傳統知識粒度約簡算法

根據上面定義和概念，我們介紹一種傳統的基于知識粒度的啟發式約簡如算法1所述[2]。

算法1：傳統的基于知識粒度的啟發式約簡方法。

輸入：給出一個決策表S=(U,A=C?D,V,f)；

輸出：決策表S的屬性約簡REDC。

步驟1：計算決策表的核Core,令REDC←Core；

步驟2：如果GD(D|REDC)=GD(D|C)，然后轉到步驟5，否則轉到步驟3；

步驟3：P←REDC，當GD(D|P)≠GD(D|C)，根據定義5計算決策表屬性子集C-P中每個屬性a相對于P的重要性2，依次循環選取最大的屬性重要性a0=max(Sigouteru(a,P,D),a∈P添加到P中，即P←P?{a0}，計算增加a0后的P的知識粒度直到與決策表的知識粒度相等為止；

步驟4：在決策表S中，從后向前依次遍歷P中的每一個屬性a，根據定義3計算P中刪除屬性a后的知識粒度GD(D|P-{a})，如果GD(D|P-a}){=GD(D|C)，則P←P-{a}；

步驟5：REDC←P，輸出決策表的屬性約簡REDC。

3 知識粒度維度增量約簡算法

當決策表的屬性動態增加，用靜態約簡的方法計算增加后的屬性約簡耗費很多的空間和時間，為了克服這個缺陷，提高計算效率，能夠在較短時間內找到增加屬性后的約簡，提出了屬性變化的增量約簡算法。

3.1 計算知識粒度增量機制

為了更好解釋增量定理，下面通過實例來說明增加屬性后等價類的增量變化，給出一個決策表S=(U,A=C?D,V,f)，U∕C={X1,X2,…,Xm}，P是新增加的屬性集，等價類U C中的部分等價類由于增加屬性P后其劃分可能更細，而等價類U C中的另一部分等價類由于增加屬性P后其劃分可能不發生變化，所以我們可得表示增加屬性P后發生細化的等價類，Xi(i=1,2,…,k)表示增加屬性P后沒有變化的等價類。

例1在表1中，論域為U={1,2,3,4,5,6,7,8,9}，U∕C={{1},{2,4},{3,5},{6,7},{8,9}}，增加屬性集P={g,h}，且g={1,0,1,1,1,1,0,1,1}和h={0,1,0,1,1,0,1,0,0}，我們可得U∕C?P={{1},{2},{4},{3},{5},{6},{7},{8,9}}。

定理1給出一個信息系統S=(U,A=C?D,V,f)，U∕C={X1,X2,…,Xm}，P是新增加的屬性集，可得則增加屬性后的知識粒度為：

證明根據定義3我們可得：

定理2給出一個信息系統S=(U,A=C?D,V,f)，U∕C?D={Y1,Y2,…,Ym}，P是新增加的屬性集 ，可 得U∕C?P?D={Y1,Y2,…,Yk,則增加屬性后的知識粒度為：

定理3給出一個信息系統S=(U,A=C?D,V,f)，U∕C={X1,X2,…,Xm}和U∕C?D={Y1,Y2,…,Ym}，P是新增加的屬性集，可得U∕C?P={X1,X2,…,，則增加屬性后的相對知識粒度為：

3.2 知識粒度維度增量約簡算法

根據增量計算知識粒度的定理和概念，我們提出了一種基于知識粒度維度增量約簡算法2描述如下：

算法2：一種屬性變化的增量約簡算法。

輸入：給出一個決策表S=(U,A=C?D,V,f)，增加屬性P前的屬性約簡RedC，新增屬性P；

輸出：決策表增加屬性P后的屬性約簡RedC?P。

步驟1：B←REDC；計算新的等價類,

步驟2：根據定理3，計算增加屬性后新的知識粒度GD(D|C?P)；

步驟3：如果GD(D|B)=GD(D|C?P)，然后轉到步驟6，否則轉到步驟4；

步驟4：當GD(D|B)≠GD(D|C?P)，根據定義5計算決策表屬性子集C?P-B中每個屬性a相對于P的重要性2，依次循環選取最大的屬性重要性a0=max(Sigouter

u(a,B,D),a∈B添加到B中，即B←B?{a0}，計算增加a0后的B的知識粒度直到與增加屬性后決策表的知識粒度相等為止；

步驟5：在決策表S中，從后向前依次遍歷B中的每一個屬性a，根據定義3計算B中刪除屬性a后的知識粒度GD(D|B-{a})，如果GD(D|B-{a})=GD(D|C?P)，則B←B-{a}；

步驟6：REDC?P←B，輸出決策表增加屬性后新的約簡REDC?P。

非增量和增量約簡算法的時間復雜度分析如下，當決策表增加了多個屬性之后，徐章艷[7]在計算知識粒度的復雜度為為條件分類個數，非增量約簡算法中步驟3到步驟4的時間復雜度為增量約簡算法總的時間復雜度為維度增量約簡算法中步驟3到步驟5的時間復雜度為為增加屬性后可以細化的等價類的個數，增量約簡算法總的時間復雜度為非增量和維度增量約簡算法的時間復雜度比較如表1所示：

表1 非增量約簡算法和增量約簡算法時間復雜度比較

4 仿真分析

為了驗證所提的增量方法比非增量方法的有效性，我們從UCI機器學習數據庫中下載了Lung Cancer和ticdata2000兩個數據集，數據描述如表2所示，分別用增量和非增量方法做實驗，并對兩種方法所花費的時間進行了比較，仿真所用的軟件和硬件環境是：Windows 8操作系統，32-bits(JDK1.6.0_20)，CPU Pentium(R)Dual-Core E5800 3.20GHz，內存：Samsung DDR3 SDRAM 4.0GB。

表2 數據集描述

在仿真過程中，我們把每個數據集分成均勻兩個部分，把第一部分作為基本數據集，把另一個數據集按20%、40%、60%、80%、100%依次添加到基本數據集中，比較增量和非增量所消耗的時間，實驗結果如圖1所示，其中縱軸表示所花費的時間，橫軸表示增加的屬性的百分數。

從圖1可得，增量約簡的方法所花費的時間遠遠小于非增量約簡的方法所消耗的時間，驗證了所提的增量方法是有效的。

圖1插入多個屬性集增量和非增量約簡算法消耗時間的比較

5 結語

在現實生活中，許多數據庫的行和列都是動態增加的，由于靜態方法計算屬性約簡需要耗費大量的時間和空間，為了克服缺陷，提高效率，本文在知識粒度概念的基礎上，提出了一種屬性變化的增量啟發約簡算法，當決策表屬性動態增加時，通過增量機制計算增加后的知識粒度，然后在新的知識粒度和原來約簡的基礎上，能夠在較短時間內找到增加屬性后的約簡，表明所提出的增量方法是有效性的，由于決策表屬性值也是動態改變的，所以下一步研究工作是屬性值動態改變的增量式約簡算法。

[1]苖奪謙,范世棟.知識粒度的計算及其應用[J].系統工程理論與實踐,2002,22(1)：48-56.

[2]王磊,葉軍.知識粒度計算的矩陣方法及其在屬性約簡中的應用[J].計算機工程與科學,2013,35(3)：98-102.

[3]王國胤,于洪,楊大春.基于條件熵的決策表約簡[J].軟件學報,2002,25(7)：760-765.

[4]梁吉業,曲開社,徐宗本.信息系統的屬性約簡[J].系統工程理論與實踐,2001,12：76-80.

[5]劉清.Rough set及Rough理 [M].北京：科學出版社,2001：7-16.

[6]YAO Y Y.Probabilistic approaches to rough sets[J].Expert Systems,2003,20(5)：287-297.

[7]徐章艷，劉作鵬，楊炳魯，等.一個復雜度max(O(|C||U|,O(|C|2|U∕C|))的快速約簡算法[J].計算機學報,2006,29(3)：391-398.

An Incremental Reduction Approach with Variation of Attribute Set

CHENG Ni
(Department of Public Computer Teaching,Yuncheng University,Yuncheng Shanxi，044000)

With the rapid development of data processing tools,many data sets in databases increase quickly in attributes.In this paper,we propose incremental reduction approach based on knowledge granularity when multiple attribute are added to decision table.Incremental mechanisms to calculate the new knowledge granularity are first introduced,Then,the proposed incremental method can find the new reduct in a much shorter time based on knowledge granularity and reduct of the original decision table.Finally,the experiments show that the developed algorithm is effective and efficient.

attribute reduction;incremental learning;knowledge granularity;decision table;rough set

TP311

A

1674-0874(2016)01-0003-05

2015-10-24

山西省高等學校教學改革項目[J2014106]；運城學院教學改革項目[JG201429]

程妮（1986-），女，山西運城人，碩士，助教，研究方向：計算機應用技術。

〔責任編輯 高?！?/p>