有序不可區(qū)分串的屬性約簡增量更新算法*

梁寶華，嚴(yán)小燕

巢湖學(xué)院 信息工程學(xué)院，合肥 238000

有序不可區(qū)分串的屬性約簡增量更新算法*

梁寶華+，嚴(yán)小燕

巢湖學(xué)院 信息工程學(xué)院，合肥 238000

+Corresponding author:E-mail:liangbh426@126.com

LIANG Baohua,YAN Xiaoyan.Incremental updating algorithm for attribute reduction based on ordered indistinguishable string.Journal of Frontiers of Computer Science and Technology,2017,11(5)：842-850.

屬性約簡;有效元素對;不可區(qū)分串;增量更新

1 引言

為處理模糊、不確定數(shù)據(jù)，1982年波蘭數(shù)學(xué)家Pawlak提出了一個(gè)強(qiáng)有力的數(shù)學(xué)工具——粗糙集理論[1]，它是在無需任何先驗(yàn)知識的前提下處理不精確數(shù)據(jù)，目前已廣泛應(yīng)用于數(shù)據(jù)挖掘、人工智能、金融分析等領(lǐng)域。屬性約簡是粗糙集理論研究的重點(diǎn)內(nèi)容之一，是指用較少的特征描述事物，且不影響事物的區(qū)分能力，剔除不必要的數(shù)據(jù)。為了有效地對數(shù)據(jù)進(jìn)行約簡，廣大研究者提出了很多屬性約簡算法[2-8]，但多數(shù)是針對靜止不變的信息系統(tǒng)。現(xiàn)實(shí)生活中的信息是變化不定的，為了處理多變的信息系統(tǒng)，學(xué)者們相繼提出了少數(shù)增量更新算法[9-15]。官禮和在文獻(xiàn)[9]中設(shè)計(jì)了一種利用差別矩陣的啟發(fā)式增量更新算法，可快速得到最小屬性約簡集，但算法在更新差別元素時(shí)，未能有效剔除無用的元素，消耗大量的時(shí)間資源。胡峰在文獻(xiàn)[10]中設(shè)計(jì)了基于正區(qū)域的增量更新算法，能夠根據(jù)不同元素是否屬于正區(qū)域進(jìn)行準(zhǔn)確定位，根據(jù)具體情況作相應(yīng)處理，有效提高了動態(tài)數(shù)據(jù)的約簡效率，但未能充分利用更新的核，對加入對象屬于負(fù)區(qū)域，或引起數(shù)據(jù)不一致情況未能很好地處理。劉洋博士在文獻(xiàn)[11]中雖然給出了基于差別矩陣增量更新算法，但因未將決策表進(jìn)行化簡，導(dǎo)致算法有很高的時(shí)間、空間復(fù)雜度。增量更新算法，旨在適應(yīng)變化的數(shù)據(jù)集。當(dāng)數(shù)據(jù)集變化后，無需重新將原來的數(shù)據(jù)進(jìn)行約簡，而根據(jù)相應(yīng)變化情況對新增加的數(shù)據(jù)進(jìn)行約簡，既保持約簡集的區(qū)分能力，又減少約簡時(shí)間。多數(shù)差別矩陣的增量更新算法，均是以差別元素最多的屬性為重要屬性，即每次需掃描更多的差別元素；在約簡過程中，傳統(tǒng)算法也未能有效地將已區(qū)分的數(shù)據(jù)過濾，導(dǎo)致消耗大量的系統(tǒng)資源。

為解決差別矩陣類的增量更新算法存在的不足，本文提出每次選擇最少的元素，且選擇最重要的屬性。在約簡過程中，不斷將基數(shù)為1的子劃分有效刪除，加速尋找最小約簡集，有效提高時(shí)間效率。本文工作概括如下：（1）借助文獻(xiàn)[3]中用到的方法求簡化決策表及正、負(fù)區(qū)域集。（2）根據(jù)改進(jìn)差別矩陣定義，給出有效比較元素對定義，并將每個(gè)元素對給予唯一編號。將元素對在條件屬性Ci上取值相同的元素對編號順次連接形成有序表。（3）根據(jù)有序表的長短決定屬性的重要性。（4）當(dāng)有新增對象加入時(shí)，根據(jù)相應(yīng)條件，動態(tài)增刪有序表中信息，可快速得到更新后的約簡集。（5）利用實(shí)例和實(shí)驗(yàn)驗(yàn)證算法的正確性和有效性。

2 粗糙集相關(guān)概念

決策表S=(U,A,V,f)，其中U為論域，A=C?D，C?D=?，C為條件屬性，D為決策屬性，V是A上的值域；f∶A→V是一個(gè)信息函數(shù)；?a∈A,x∈U，有f(x,a)∈Va。

定義1對于B?A決定不可分辨關(guān)系：

可簡化為U/B；U/B的元素為等價(jià)類，含x的等價(jià)類記為：

定義2B?A，用U B表示B的所有等價(jià)類的集合，用[x]B表示在等價(jià)關(guān)系B下包含元素x(x∈U)的等價(jià)類。對于論域給定決策表S=(U,A,V,f)，對于任意子集X?U和不可分辨關(guān)系IND(B)：

定義3條件屬性集C相對于D的正區(qū)域定義為，簡記為UPOS，負(fù)區(qū)域?yàn)閁NEG= U-UPOS。

定義4[12]決策表S的改進(jìn)差別矩陣M={mij}定義為：

其中，UPOS′簡化決策表中正區(qū)域部分，UNEG′為負(fù)區(qū)域部分，簡化決策表是U/C每個(gè)子劃分中取第一個(gè)元素組成的決策表。

定義5對于簡化決策表S′=(U′,A,V,f)，U′為簡化后的論域，U′=UPOS′?UNEG′,UPOS′、UNEG′分別為簡化決策表中的正區(qū)域和負(fù)區(qū)域集，可將相互比較的元素形成元素對Mpair，定義如下：

定理1定義4的改進(jìn)差別矩陣元素與定義5 Mpair的元素對具有等價(jià)性。

證明（1）由改進(jìn)差別矩陣M及Mpair定義可得，M中的a所對應(yīng)的樣本x、y組成的元素對一定能在Mpair中找到。

（2）Mpair中的元素也一定能找到M中所對應(yīng)的(x,y):（以下的a為條件屬性C中的任意一個(gè)）。?(x,y)∈Mpair，當(dāng)x∈UPOS′∧y∈UNEG′時(shí)，假設(shè)找不到任何 f(x,a)≠f(y,a)，因?yàn)?a具有任意性，所以有f(x,C)=f(y,C)，又Mpair中的(x,y)來源于簡化決策，而簡化決策表中無重復(fù)元素，即不存在 f(x,C)= f(y,C)，因此假設(shè)不成立，也即在M中能找到一個(gè)a及相對應(yīng)的(x,y)，使 f(x,a)≠f(y,a)；同理可得，當(dāng)x∈UPOS′∧y∈UPOS′∧f(x,D)≠f(y,D)時(shí)，也能在M中找到一個(gè)a使 f(x,a)≠f(y,a)。

綜合（1）、（2）得M與Mpair元素具有等價(jià)性?！?/p>

定義6設(shè)每個(gè)元素對給定一個(gè)唯一編號，關(guān)于屬性集B的所有不可區(qū)分元素對對應(yīng)的編號形成的有序序列稱不可區(qū)分序號串：

定理2對于簡化決策表S′=(U′,C?D,V,f)，C為條件屬性，設(shè)B?C,b?C-B，則有DisStringB?b?DisStringB。

證明設(shè)?s∈DisStringB?b，編號s所對應(yīng)的兩個(gè)比較樣本分別為x和y,根據(jù)定義6可知，(x,y)∈Mpair且 f(x,B?b)=f(y,B?b)，因?yàn)锽?B?b，所以一定有f(x,B)=f(y,B)。又因?yàn)?s具有任意性，所以有 s∈DisStringB，因此DisStringB?b?DisStringB。 □

性質(zhì)1不可區(qū)分序號串DisStringB長度越短，區(qū)分能力越強(qiáng)。

證明根據(jù)定義5，可得對于一個(gè)給定的決策表，Mpair的元素是一定的?，F(xiàn)DisStringB記錄了條件屬性B關(guān)于Mpair中不可區(qū)分的元素對，若DisStringB組成的字符串長度越短，表明越少的樣本在條件屬性B上不可區(qū)分。相反，可區(qū)分的樣本越多，也即可區(qū)分能力越強(qiáng)。 □

3 有序不可區(qū)分串的屬性約簡增量更新算法

3.1 有序不可區(qū)分串的屬性約簡算法

傳統(tǒng)的差別矩陣算法，需消耗大量內(nèi)存空間存儲差別信息矩陣。在約簡過程中，每次挑選區(qū)分度最高的屬性加入簡約集，但區(qū)分度最高，意味著可區(qū)分串的長度最長，也即每次掃描的元素對越多，造成時(shí)間的浪費(fèi)。鑒于此，為加速尋找最小約簡集，本文以一種有序不可區(qū)分串為依據(jù)，每個(gè)條件屬性都對應(yīng)一個(gè)不可區(qū)分串，可獨(dú)立存放于內(nèi)存，這樣無需將所有條件屬性的不可區(qū)分串同時(shí)存儲于內(nèi)存，大大減少內(nèi)存消耗。此外，每次選擇最短的不可區(qū)分串，有效減少了掃描對象，降低了時(shí)間、空間消耗。

算法1不可區(qū)分串的屬性約簡算法

算法中，在求MinString?DisStringCi時(shí)，因?yàn)檫@兩個(gè)串均是有序的，所以時(shí)間復(fù)雜度為O(m+n),m、n分別為MinString與DisStringCi的元素個(gè)數(shù)。步驟1時(shí)間復(fù)雜度為O(|C||U|)；步驟2時(shí)間復(fù)雜度為O(|UPOS′||U′|)；步驟3時(shí)間復(fù)雜度可忽略不計(jì)；步驟4時(shí)間復(fù)雜度為O(|C||UPOS′||U′/C|)；步驟5在最好情況下時(shí)間復(fù)雜度為O(|C|min(|DisStringCi|))+O(|C|min(|DisStringCj|))，因?yàn)閨DisStringCi|也即是不可區(qū)分串的長度，最壞情況下是O(|UPOS′||U′|)，所以步驟5的時(shí)間復(fù)雜度為O(|C|min(|DisStringCi|+|DisStringCj|))?？倳r(shí)間復(fù)雜度為max(O(|C||UPOS′||U′/C|),O(|C|min(|DisStringCi|+|DisStringCj|)),其中min(|DisStringCi|+|DisStringCj|)為兩個(gè)較短的不可區(qū)分串。空間資源消耗主要是用來存儲條件屬性的不可區(qū)分串，由于在實(shí)驗(yàn)時(shí)，可將每個(gè)條件屬性的DisStringCi依次取出，無需將所有的DisStringCi同時(shí)駐留內(nèi)存，因?yàn)镈isStringCi的長度不可能超過|UPOS′||U′|，所以空間復(fù)雜度為O(|UPOS′||U′|+max(|DisStringCi|))。

3.2 增量更新算法

3.2.1 增量情況分析

現(xiàn)實(shí)生活中，信息系統(tǒng)的數(shù)據(jù)是不斷變化的。當(dāng)增加數(shù)據(jù)對象時(shí)，如何充分利用前期約簡結(jié)果得到新的約簡集，這一問題引起了多數(shù)研究者的關(guān)注。經(jīng)研究分析，新增對象與改進(jìn)差別矩陣相比，存在以下幾種情況（設(shè)x為原數(shù)據(jù)集對象，y為新增對象）：

（1）?x∈UPOS′，對?Ci∈C有 f(x,Ci)=f(y,Ci)：若 f(x,D)=f(y,D)，則Mpair保持不變；

若 f(x,D)≠f(y,D)，將x變?yōu)閁NEG′，則Mpair中刪除所有UNEG′與x組成的元素對，原來UPOS′與x構(gòu)成的Mpair元素對對應(yīng)的序號加標(biāo)記“*”。

證明?x∈UPOS′，對?Ci∈C有 f(x,Ci)=f(y,Ci)，說明數(shù)據(jù)源中有樣本與y樣本在條件屬性C上取值重復(fù)，設(shè)此樣本為x，若 f(x,D)=f(y,D)，則完全重復(fù)，故加入y不影響約簡結(jié)果，Mpair也不變；若 f(x,D)≠f(y,D)，說明條件屬性值相同，但決策值不同，根據(jù)負(fù)區(qū)域定義可得，因y的加入，使x變?yōu)樨?fù)區(qū)域，x與y任選其一加入負(fù)區(qū)域集，設(shè)取x加入。再根據(jù)Mpair定義得，負(fù)區(qū)域集各元素間無需比較，因x已變?yōu)閁NEG′，所以刪除Mpair中原來與x組成的且?guī)А?”標(biāo)記的元素對，并將Mpair中原來與x構(gòu)成的未加標(biāo)記“*”元素對加標(biāo)記“*”，以便識別新組建的關(guān)系。 □

（2）?x∈UNEG′，對?Ci∈C有 f(x,Ci)=f(y,Ci)，則Mpair不變。

證明根據(jù)負(fù)區(qū)域定義得y∈UNEG′。根據(jù)Mpair定義得y無需與負(fù)區(qū)域集的其他元素進(jìn)行比較，而y與正區(qū)域元素比較的情況與x完全相同，由于x與正區(qū)域元素比較的元素對情況已包含在Mpair中，故Mpair不變。 □

（3）?x∈U′,f(x,C)≠f(y,C),則將 y加入到UPOS′中，改變Mpair的值：

證明因?yàn)?x∈U′∧f(x,C)≠f(y,C),所以y在U′中無數(shù)據(jù)與之相對應(yīng)，當(dāng)y加入U(xiǎn)′時(shí)，由UPOS′定義可得y∈UPOS′。根據(jù)Mpair定義得，y與UPOS′中元素構(gòu)成元素對{(x,y)|x∈UPOS′∧f(x,D)≠f(y,D)}，y與UNEG′中元素構(gòu)成元素對{(x,y)|x∈UNEG′}，合并得Mpair?{(x,y)|x∈UPOS′∧f(x,D)≠f(y,D)∨x∈UNEG′}。 □

3.2.2 增量更新算法描述

算法2增量更新算法

算法復(fù)雜度分析：設(shè)新增對象y，在計(jì)算步驟1過程中，當(dāng) f(x,D)=f(y,D)時(shí)，計(jì)算用時(shí)O(|C||UPOS′|)，當(dāng)f(x,D)≠f(y,D)時(shí)，計(jì)算用時(shí)O(|C||UPOS′|)+O(|Mpair|)+ min(O(|Reduce|2|DisString(Ci)|)，O(|Mpair|)為定義5元素對的個(gè)數(shù)，即O(|C||UPOS′||U′|)；步驟2用時(shí)為O(|C||UNEG′|)；計(jì)算步驟3過程中，因新增對象y，所以更新DisStringCi用時(shí)O(|C||UPOS′||U′|)，求最短不可區(qū)分串用時(shí)O(|C||UPOS′| |U′|)+min(O(|Reduce|2|DisStringCi|))。因?yàn)镺(|DisStringCi|)?O(|UPOS′||U′|)，所以算法總的時(shí)間復(fù)雜度為max(O(|C| |UPOS′||U′|),O(|Reduce|2|UPOS′||U′|))。算法的空間消耗主要用來存儲每個(gè)條件屬性的不可區(qū)分串，因?yàn)樵谠L問數(shù)據(jù)時(shí)，可將條件屬性的不可區(qū)分串逐一存取，所以空間復(fù)雜度為O(|UPOS′||U′|)。

文獻(xiàn)[13]算法的時(shí)間、空間復(fù)雜度均為O(|C|2||U′|2)，文獻(xiàn)[14]算法的時(shí)間復(fù)雜度為max(O(|C||U′|),O(|Reduce|2|UPOS′||U′|))，空間復(fù)雜度為O(|C||UPOS′||U′|)。雖然文獻(xiàn)[14]的時(shí)間復(fù)雜度略低于算法2，實(shí)際知識發(fā)現(xiàn)過程中，算法2每次取的是最短的不可區(qū)分串，因此時(shí)間消耗上與文獻(xiàn)[14]相差不大，但其空間復(fù)雜度大大超過算法2。算法2綜合來看，計(jì)算的時(shí)間、空間效果要優(yōu)于文獻(xiàn)[13-14]。

4 示例及實(shí)驗(yàn)分析

下面以決策表S=(U,C,D,V,f)為例進(jìn)行分析，決策表如表1所示。

Table 1 Decision table表1 決策表

4.1 屬性約簡過程示例

簡化決策表S得S′，并根據(jù)文獻(xiàn)[3]計(jì)算S′的正區(qū)域集數(shù)據(jù)對象序號依次為{1,2,3,4,5}、負(fù)區(qū)域?qū)ο笥衶6}。根據(jù)定義4可得到Mpair，并統(tǒng)一編號如表2所示。

Table 2 Element pairs of Mpair表2 Mpair元素對

將U′按條件屬性劃分得：

其中，每個(gè)子劃分中帶下劃線部分的元素決策值相等，根據(jù)定義5得，具有相同決策值的樣本無需比較。將每個(gè)子劃分中的樣本兩兩組成元素對，并根據(jù)Mpair中的元素得到元素對的編號，收集成一個(gè)有序的不可區(qū)分串得：

DisStringC4長度最短，因此取Reduce={C4},Min-String=(2,*4,5,*12)。同理，；選擇C1加入約簡集得Reduce={C1,C4}(C1與C2任選一個(gè))， MinString={*4},，故算法終止，將C2并入Reduce得Reduce={C1,C2,C4}。

4.2 增量更新過程示例

（1）當(dāng)新增對象為y={1,2,2,1,1}時(shí)，對于Ci∈C，存在x2∈UPOS′，使得 f(y,Ci)=f(x2,Ci)，根據(jù)算法步驟1可知，Reduce={C1,C2,C4}不變；當(dāng)新增對象為y={1,1,1,2,1}時(shí)，對于Ci∈C，存在 x1∈UPOS′，使得f(y,Ci)=f(x1,Ci)∧f(x1,D)≠f(y,D)。根據(jù)算法步驟1可知，編號為1、2、3的元素對分別加上標(biāo)記“*”，刪除*4號元素對，UPOS′={2,3,4,5}，UNEG′={1,6}，反向刪除{C2}得DisStringReduce=?，故Reduce={C1,C4}。

（2）當(dāng)新增對象為y={1,2,1,2,4}時(shí)，對于Ci∈C，存在x6∈UNEG′，使得 f(y,Ci)=f(x6,Ci)。根據(jù)算法步驟2可知，屬性約簡Reduce={C1,C4}不變。

（3）當(dāng)新增對象為y={1,1,2,1,0}時(shí)，對?x∈UPOS′,?Ci∈C，使得 f(y,Ci)≠f(x,Ci)。根據(jù)算法步驟3可知，更新Mpair。

Mpair元素對更新結(jié)果如表3所示。

Table 3 Updating element pairs of Mpair表3 Mpair元素對更新

因增加新對象y，使各條件屬性增加了新的不可區(qū)分元素對，根據(jù)算法步驟3可知DisStringC1增加部分為(*14,15,*18)，增加部分為(*14),增加部分為(15,17)，增加部分為(15)。因DisStringReduce=(15)非空，所以更新Reduce。因，所以將屬性C2并入Reduce，更新Reduce={C1,C2,C4}，算法終止。

4.3 實(shí)驗(yàn)比較

為進(jìn)一步驗(yàn)證本文增量更新算法2與其他同類算法的性能，在WindowsXP下,開發(fā)工具為VC6.0，CPU 2.3 GHz，內(nèi)存2 GB環(huán)境下編程。本文選用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的5個(gè)數(shù)據(jù)集測試，具體數(shù)據(jù)集情況如表4所示。D1～D5依次表示UCI中的數(shù)據(jù)集Patient、Cancer、Forest、Car、Mushroom，|U|為數(shù)據(jù)集對象數(shù)，|U′|為簡化后數(shù)據(jù)集對象數(shù)，|C|為條件屬性個(gè)數(shù)，|UPOS′|為正區(qū)域?qū)ο髷?shù)，|Base|為基準(zhǔn)數(shù)。下面分別以雷曉蔚的文獻(xiàn)[13]與錢文彬的文獻(xiàn)[14]及本文算法2，從空間及時(shí)間上進(jìn)行比較。

Table 4 Test dataset表4 測試數(shù)據(jù)集

（1）以UCI數(shù)據(jù)庫中的5個(gè)數(shù)據(jù)集進(jìn)行空間的測試，共進(jìn)行了5次計(jì)算，取平均值。表5表示各算法存儲信息矩陣的元素個(gè)數(shù)。

Table 5 Space comparison of 3 algorithms表5 3種算法的空間比較

從空間資源消耗上說，文獻(xiàn)[13]算法的空間復(fù)雜度為O(|C||U|2)，文獻(xiàn)[14]算法的空間復(fù)雜度為O(|C||U′||UPOS′|)。當(dāng)|U|≈|U′|時(shí)，文獻(xiàn)[13]與文獻(xiàn)[14]算法的復(fù)雜度較接近，但文獻(xiàn)[13]算法未能避免決策值相同元素間的比較，導(dǎo)致空間效率較文獻(xiàn)[14]低。本文算法2的空間消耗不到文獻(xiàn)[14]算法的1/|C|，實(shí)現(xiàn)時(shí)只需存儲最短的不可區(qū)分串。若測試數(shù)據(jù)集中有大量重復(fù)數(shù)據(jù)，效果更加明顯，如數(shù)據(jù)集D1、D4在挖掘時(shí)，算法2中有效剔除了無需區(qū)分對象，使所需空間遠(yuǎn)比文獻(xiàn)[13]的1/|C|小。文獻(xiàn)[13]算法在計(jì)算數(shù)據(jù)集Mushroom約簡時(shí)，由于數(shù)據(jù)量大，屬性多，無法將信息矩陣存入到內(nèi)存，產(chǎn)生溢出。而本文算法2只需少量空間就可得到約簡結(jié)果，節(jié)省大量空間資源。

（2）對UCI數(shù)據(jù)庫中的5個(gè)數(shù)據(jù)集進(jìn)行時(shí)間消耗的測試，Ti為算法需要的時(shí)間，以秒為單位，Ri為約簡后的屬性個(gè)數(shù)，共進(jìn)行了5次計(jì)算，取平均值，并且取每個(gè)原數(shù)據(jù)集80%的數(shù)據(jù)作為基準(zhǔn)數(shù)，其余作為增量部分，結(jié)果如表6所示。

Table 6 Comparison of 3 incremental updating algorithms表6 3種增量更新算法的比較

文獻(xiàn)[13]、文獻(xiàn)[14]及本文算法均利用正、負(fù)區(qū)域模型，計(jì)算動態(tài)更新情況下的約簡集，由表6數(shù)據(jù)可知，約簡結(jié)果基本一致。在數(shù)據(jù)集的維數(shù)及數(shù)據(jù)量較小的情況下，時(shí)間效果不明顯，如D1只有90個(gè)樣例，文獻(xiàn)[13]約簡時(shí)間0.181 s，而文獻(xiàn)[14]約簡時(shí)間0.070 s，本文算法2約簡時(shí)間0.062 s。但隨著數(shù)據(jù)規(guī)模的增大，本文算法2在約簡時(shí)，由于每次取不可區(qū)分串最短的串為選擇重要屬性的依據(jù)，加速了剪枝效果，時(shí)間效果更為明顯。如D5有數(shù)據(jù)8 124條，文獻(xiàn)[13]因不能有效剪枝，所以無法完成約簡過程，產(chǎn)生數(shù)據(jù)溢出現(xiàn)象，而本文算法2只需2.761 s，比文獻(xiàn)[14]的時(shí)間3.012 s稍優(yōu)越。文獻(xiàn)[10]的時(shí)間復(fù)雜度為O(|C2||U|2)，文獻(xiàn)[14]與算法2的時(shí)間復(fù)雜度為max(O(|C||UPOS′||U′|),O(|Red|2|UPOS′||U′|))，與|U′|、|UPOS′|關(guān)系較大，因此|U′|、|UPOS′|的大小嚴(yán)重影響文獻(xiàn)[14]與算法2的運(yùn)算時(shí)間，但對文獻(xiàn)[13]算法時(shí)間影響不大。上述數(shù)據(jù)集中，D4出現(xiàn)大量重復(fù)。表面上看，D4雖然比D3的數(shù)據(jù)量大很多，但運(yùn)算時(shí)間上，文獻(xiàn)[13]明顯沒有文獻(xiàn)[14]和算法2的效果好，因此文獻(xiàn)[14]與本文算法2更適應(yīng)于重復(fù)樣本多的數(shù)據(jù)集約簡。

5 結(jié)束語

關(guān)于屬性約簡算法，多數(shù)只針對靜態(tài)數(shù)據(jù)集的情況?，F(xiàn)實(shí)生活中，數(shù)據(jù)是不斷變化的，當(dāng)有新數(shù)據(jù)加入時(shí)，可能會引起約簡集的變化。為了充分利用前期的約簡結(jié)果，減少大量重復(fù)性的計(jì)算，本文提出比較元素對概念Mpair，并以每個(gè)條件屬性的不可區(qū)分元素對的數(shù)量多少為重要依據(jù)，設(shè)計(jì)一種動態(tài)增量更新算法，根據(jù)加入對象的不同情況，進(jìn)行相應(yīng)處理，動態(tài)更新約簡集。由于每次以最短的不可區(qū)分串為選擇的條件，加速了尋找約簡集的速度，而同類算法均以最長的可區(qū)分元素對為依據(jù)，不能有效剪枝。為更進(jìn)一步加快約簡速度，且適應(yīng)現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)的變化，下一步工作是：研究如何將數(shù)據(jù)集分成n塊，適應(yīng)多處理器的計(jì)算機(jī)運(yùn)行，讓每個(gè)處理器同時(shí)處理，達(dá)到并行處理效果。

[1]Pawlak Z.Rough sets[J].International Journal of Computer and Information Science,1982,11(5):341-356.

[2]Wang Jue,Wang Ju.Reduction algorithm based on discernibility matrix:the ordered attributes method[J].Journal of Computer Science and Technology,2001,16(6):489-504.

[3]Liang Baohua,Wang Shiyi,Cai Min.Heuristic attribute reduction algorithm based on order table[J].Computer Engineering,2012,38(2):51-53.

[4]Miao Duoqian,Hu Guirong.Aheuristic algorithm for reduction of knowledge[J].Computer Research and Development,1999,36(6):681-684.

[5]Qian Yuhua,Liang Jiye,Pedrycz W,et al.Positive approximation:an accelerator for attribute reduction in rough set theory[J].Artificial Intelligence,2012,174(9/10):597-618.

[6]Ge Hao,Li Longshu,Yang Chuanjian.Improvement to quick attribution reduction algorithm[J].Journal of Chinese Computer Systems,2009,30(2):308-312.

[7]Zhang Qinghua,Xiao Yu.New attribute reduction on information entropy[J].Journal of Frontiers of Computer Science and Technology,2013,7(4):359-367.

[8]Chen Tangmin.Research of the heuristic reduced algorithm based on the separating capacity[J].Chinese Journal of Computers,2006,29(3):480-487.

[9]Guan Lihe,Wang Guoying.An incremental updating algorithm for attribute reduction set of decision tables[J].Journal of Frontiers of Computer Science and Technology,2010, 4(5):436-444.

[10]Hu Feng,Wang Guoyin,Huang Hai,et al.Incremental attribute reduction based on elementary sets[C]//LNCS 3641: Proceedings of the 10th International Conference on Rough Sets,Fuzzy Sets,Data Mining,and Granular Computing, Regina,Canada,Aug 31-Sep 3,2005.Berlin,Heidelberg: Springer,2005:185-193.

[11]Liu Yang,Feng Boqin,Zhou Jiangwei.Complete algorithm of increment for attribute reduction based on discernibility matrix[J].Journal of Xi’an Jiaotong University,2007,41 (2):158-161.

[12]Yang Ming.An incremental updating algorithm of the computation of a core based on the improved discernibility matrix[J].Chinese Journal of Computers,2006,29(3):407-413.

[13]Lei Xiaowei.The matrix approaches of rough sets[J].Computer Engineering andApplications,2006,42(17):73-75.

[14]Qiang Wenbin,Yang Bingru,Xu Zhangyan,et al.Efficient algorithm for dynamic attribute reduction based on a matrix [J].Journal of University of Science and Technology Beijing,2013,35(2):249-255.

[15]Hu Feng,Dai Jin,Wang Guoyin.Incremental algorithms for attribute reduction in decision table[J].Control and Decision,2007,22(3):268-272.

附中文參考文獻(xiàn)：

[3]梁寶華,汪世義,蔡敏.基于順序表的啟發(fā)式屬性約簡算法[J].計(jì)算機(jī)工程,2012,38(2):51-53.

[4]苗奪謙,胡桂榮.知識約簡的一種啟發(fā)式算法[J].計(jì)算機(jī)研究與發(fā)展,1999,36(6):681-684.

[6]葛浩,李龍澍,楊傳健.改進(jìn)的快速屬性約簡算法[J].小型微型計(jì)算機(jī)系統(tǒng),2009,30(2):308-312.

[7]張清華,肖雨.新的信息熵屬性約簡[J].計(jì)算機(jī)科學(xué)與探索,2013,7(4):359-367.

[8]陳堂敏.基于區(qū)分能力大小的啟發(fā)式約簡算法的研究[J].計(jì)算機(jī)學(xué)報(bào),2006,29(3):480-487.

[9]官禮和,王國胤.決策表屬性約簡集的增量式更新算法[J].計(jì)算機(jī)科學(xué)與探索,2010,4(5):436-444.

[11]劉洋,馮博琴,周江衛(wèi).基于差別矩陣的增量式屬性約簡完備算法[J].西安交通大學(xué)學(xué)報(bào),2007,41(2):158-161.

[12]楊明.一種基于改進(jìn)差別矩陣的核增量式更新算法[J].計(jì)算機(jī)學(xué)報(bào),2006,29(3):407-413.

[13]雷曉蔚.粗集理論的矩陣方法[J].計(jì)算機(jī)工程與應(yīng)用, 2006,42(17):73-75.

[14]錢文彬,楊炳儒,徐章艷,等.一種快速的動態(tài)屬性約簡矩陣算法[J].北京科技大學(xué)學(xué)報(bào),2013,35(2):249-255.

[15]胡峰,代勁,王國胤.一種決策表增量屬性約簡算法[J].控制與決策,2007,22(3):268-272.

LIANG Baohua was born in 1973.He received the M.S.degree from Guangxi Normal University in 2007.Now he is an associate professor at Chaohu University.His research interests include data mining and rough set,etc.

梁寶華（1973—），男，安徽無為人，2007年于廣西師范大學(xué)獲得碩士學(xué)位，現(xiàn)為巢湖學(xué)院副教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，粗糙集等。

YAN Xiaoyan was born in 1984.She is a lecturer at Chaohu University.Her research interests include computer network and artificial intelligence,etc.

嚴(yán)小燕（1984—），女，安徽廬江人，碩士，巢湖學(xué)院講師，主要研究領(lǐng)域計(jì)算機(jī)網(wǎng)絡(luò)，人工智能等。

歡迎訂閱2017年《計(jì)算機(jī)科學(xué)與探索》、《計(jì)算機(jī)工程與應(yīng)用》

《計(jì)算機(jī)科學(xué)與探索》為月刊,大16開,單價(jià)48元,全年12期總訂價(jià)576元,郵發(fā)代號：82-560。郵局匯款地址：

北京619信箱26分箱《計(jì)算機(jī)科學(xué)與探索》編輯部(收) 郵編：100083

《計(jì)算機(jī)工程與應(yīng)用》為半月刊,大16開,每月1日、15日出版,單價(jià)45元,全年24期總訂價(jià)1080元,郵發(fā)代號：82-605。

郵局匯款地址：

北京619信箱26分箱《計(jì)算機(jī)工程與應(yīng)用》編輯部(收) 郵編：100083

歡迎到各地郵局或編輯部訂閱。個(gè)人從編輯部直接訂閱可享受8折優(yōu)惠！

發(fā)行部

電話：(010)89055541

Incremental UpdatingAlgorithm forAttribute Reduction Based on Ordered Indistinguishable String*

LIANG Baohua+,YAN Xiaoyan
College of Information Engineering,Chaohu University,Hefei 238000,China

When some new objects are added to the decision table,the attribute reduction sets will be changed.To ensure the correctness of the results,it is necessary to update the attribute reduction dynamically.Usually,the important attribute is selected which depends on the quantity of distinguishable elements in discernibility matrix algorithm. The most distinguishable information attribute is merged into reduction set every time,so the time complexity is high.Firstly,this paper proposes the definitions of effective element pair and indistinguishable string,selects the important attribute according to the length of indistinguishable string and proves the effectiveness.Secondly,this paper analyzes the different cases of added object,and updates the attribute reduction of simplified decision table according to the corresponding conditions dynamically.Then this paper designs the incremental updating algorithm based on ordered indistinguishable string.At last,the example analysis and experimental comparison show that the algorithms are feasible and effective.

attribute reduction;effective element pair;indistinguishable string;incremental updating

10.3778/j.issn.1673-9418.1602039

A

TP181

*The National Natural Science Foundation of China under Grant No.60573174(國家自然科學(xué)基金);the Outstanding Young Backbone Talent Visiting Foundation of Anhui University under Grant No.gxfx2017100(安徽省高校優(yōu)秀青年骨干人才訪學(xué)項(xiàng)目);the Natural Science Foundation ofAnhui Province under Grant No.KJ2013Z231(安徽省自然科學(xué)基金).

Received 2016-02,Accepted 2016-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-08-01,http://www.cnki.net/kcms/detail/11.5602.TP.20160801.1406.002.html

摘 要：當(dāng)有新增對象加入到?jīng)Q策表時(shí)，已有的屬性約簡將會發(fā)生變化，為保證約簡結(jié)果的正確性，需對其進(jìn)行動態(tài)更新。差別矩陣算法通常以可區(qū)分元素的多少作為屬性重要性的依據(jù)，每次選擇可區(qū)分信息最多的屬性加入約簡集，導(dǎo)致有較高的時(shí)間復(fù)雜度。為此，提出了有效比較元素對及不可區(qū)分串定義，以不可區(qū)分串長短為屬性重要性選擇的依據(jù)，并證明了其有效性；然后分析了增量更新的不同情況，將新增對象加入簡化決策表，按相應(yīng)條件動態(tài)變化約簡集，由此設(shè)計(jì)了基于有序不可區(qū)分串的增量更新算法；最后通過實(shí)驗(yàn)比較和實(shí)例分析了增量更新算法的可行性和有效性。