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

程 妮

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

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

程 妮

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

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

屬性約簡;增量學(xué)習(xí);知識粒度;決策表;粗糙集

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

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

1 粗糙集的相關(guān)知識

定義1[1]：一個信息系統(tǒng)是四元組S=(U,A=C?D,V,f)，其中U是非空有限對象集合，也稱為論域；其中C、D分別為條件屬性集和決策屬性集，其中Va是條件和決策屬性a的值，f：U×C?D→V為信息函數(shù)，即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關(guān)于條件屬性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是必要的屬性。

性質(zhì)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 傳統(tǒng)知識粒度約簡算法

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

算法1：傳統(tǒng)的基于知識粒度的啟發(fā)式約簡方法。

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

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

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

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

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

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

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

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

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

3.1 計算知識粒度增量機制

為了更好解釋增量定理，下面通過實例來說明增加屬性后等價類的增量變化，給出一個決策表S=(U,A=C?D,V,f)，U∕C={X1,X2,…,Xm}，P是新增加的屬性集，等價類U C中的部分等價類由于增加屬性P后其劃分可能更細，而等價類U C中的另一部分等價類由于增加屬性P后其劃分可能不發(fā)生變化，所以我們可得表示增加屬性P后發(fā)生細化的等價類，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給出一個信息系統(tǒng)S=(U,A=C?D,V,f)，U∕C={X1,X2,…,Xm}，P是新增加的屬性集，可得則增加屬性后的知識粒度為：

證明根據(jù)定義3我們可得：

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

定理3給出一個信息系統(tǒng)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 知識粒度維度增量約簡算法

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真分析

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

表2 數(shù)據(jù)集描述

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

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

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

5 結(jié)語

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

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

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

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

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

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

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

[7]徐章艷，劉作鵬，楊炳魯，等.一個復(fù)雜度max(O(|C||U|,O(|C|2|U∕C|))的快速約簡算法[J].計算機學(xué)報,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

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

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

〔責(zé)任編輯 高?！?/p>