程 妮

（運(yùn)城學(xué)院公共計(jì)算機(jī)教學(xué)部，山西運(yùn)城044000）

一種基于屬性變化的增量約簡(jiǎn)算法

程 妮

（運(yùn)城學(xué)院公共計(jì)算機(jī)教學(xué)部，山西運(yùn)城044000）

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

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

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

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

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

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

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

2 知識(shí)粒度約簡(jiǎn)算法

2.1 知識(shí)粒度基本知識(shí)

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

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

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

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

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

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

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

2.2 傳統(tǒng)知識(shí)粒度約簡(jiǎn)算法

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

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

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

輸出：決策表S的屬性約簡(jiǎn)REDC。

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

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

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

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

步驟5：REDC←P，輸出決策表的屬性約簡(jiǎn)REDC。

3 知識(shí)粒度維度增量約簡(jiǎn)算法

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

3.1 計(jì)算知識(shí)粒度增量機(jī)制

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

例1在表1中，論域?yàn)閁={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給出一個(gè)信息系統(tǒng)S=(U,A=C?D,V,f)，U∕C={X1,X2,…,Xm}，P是新增加的屬性集，可得則增加屬性后的知識(shí)粒度為：

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

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

定理3給出一個(gè)信息系統(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,…,，則增加屬性后的相對(duì)知識(shí)粒度為：

3.2 知識(shí)粒度維度增量約簡(jiǎn)算法

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

算法2：一種屬性變化的增量約簡(jiǎn)算法。

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

輸出：決策表增加屬性P后的屬性約簡(jiǎn)RedC?P。

步驟1：B←REDC；計(jì)算新的等價(jià)類,

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

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

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

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

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

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

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

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

4 仿真分析

為了驗(yàn)證所提的增量方法比非增量方法的有效性，我們從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中下載了Lung Cancer和ticdata2000兩個(gè)數(shù)據(jù)集，數(shù)據(jù)描述如表2所示，分別用增量和非增量方法做實(shí)驗(yàn)，并對(duì)兩種方法所花費(fèi)的時(shí)間進(jìn)行了比較，仿真所用的軟件和硬件環(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ù)集描述

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

從圖1可得，增量約簡(jiǎn)的方法所花費(fèi)的時(shí)間遠(yuǎn)遠(yuǎn)小于非增量約簡(jiǎn)的方法所消耗的時(shí)間，驗(yàn)證了所提的增量方法是有效的。

圖1插入多個(gè)屬性集增量和非增量約簡(jiǎn)算法消耗時(shí)間的比較

5 結(jié)語(yǔ)

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

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

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

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

[4]梁吉業(yè),曲開(kāi)社,徐宗本.信息系統(tǒng)的屬性約簡(jiǎn)[J].系統(tǒng)工程理論與實(shí)踐,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]徐章艷，劉作鵬，楊炳魯，等.一個(gè)復(fù)雜度max(O(|C||U|,O(|C|2|U∕C|))的快速約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào),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é)改革項(xiàng)目[J2014106]；運(yùn)城學(xué)院教學(xué)改革項(xiàng)目[JG201429]

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

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