基于多尺度屬性粒策略的快速正域約簡(jiǎn)算法

陳曼如　張楠　童向榮　東野升龍　楊文靜

摘要：傳統(tǒng)啟發(fā)式正域?qū)傩约s簡(jiǎn)算法在每次迭代的過(guò)程中需要添加當(dāng)前正域依賴(lài)度最大的屬性進(jìn)入已選定的特征屬性子集，算法迭代次數(shù)多且效率低，難以應(yīng)用于高維大規(guī)模數(shù)據(jù)集的特征選擇中。針對(duì)上述問(wèn)題，研究決策系統(tǒng)中正域之間的單調(diào)關(guān)系，給出了多尺度屬性粒（MSAG）的形式化描述，提出了一種基于多尺度屬性粒的快速正域約簡(jiǎn)算法（MAG-QPR）。由于多尺度屬性粒包含多個(gè)屬性，可以對(duì)已選定的特征屬性子集提供較大的正域，因此，通過(guò)每次迭代添加MSAG，可以達(dá)到減少迭代次數(shù)和使選定的特征屬性子集能更快地趨近于條件屬性全集的正域分辨能力的目的，從而提高了啟發(fā)式正域約簡(jiǎn)算法的效率。在實(shí)驗(yàn)部分，選取8組UCI數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，對(duì)于數(shù)據(jù)集Lung Cancer、Flag和German，MAG-QPR與基于正向近似的正域保持屬性約簡(jiǎn)算法 （FSPA-PR）、基于正向近似的條件熵屬性約簡(jiǎn)算法（FSPA-SCE）、后向貪婪正域保持屬性約簡(jiǎn)算法 （BGRAP） 和后向貪婪啟發(fā)式廣義決策保持屬性約簡(jiǎn)算法（BGRAG）的運(yùn)行時(shí)間加速比分別為9.64、15.70、5.03、2.50;3.93、7.55、1.69、4.57;3.61、6.49、1.30、9.51。實(shí)驗(yàn)結(jié)果表明，所提算法MAG-QPR提高了算法效率，具有更好的分類(lèi)精度。

關(guān)鍵詞：屬性約簡(jiǎn);粗糙集;多尺度屬性粒;正域約簡(jiǎn);快速約簡(jiǎn)算法

中圖分類(lèi)號(hào)： TP181;TP301.4文獻(xiàn)標(biāo)志碼：A英文標(biāo)題

Multi-scale attribute granule based quick positive region reduction algorithm

CHEN Manru1，2， ZHANG Nan1，2*， TONG Xiangrong1，2， DONGYE Shenglong1，2， YANG Wenjing1，2

（1. Key Lab for Data Science and Intelligence Technology of Shandong Higher Education Institutes

（Yantai University）， Yantai Shandong 264005， China;

2. School of Computer Science and Control Engineering， Yantai University， Yantai Shandong 264005， China）

Abstract： In classical heuristic attribute reduction algorithm for positive region， the attribute with the maximum dependency degree of the current positive domain should be added into the selected feature attribute subset in each iteration， leading to the large number of iterations and the low efficiency of the algorithm， and making the algorithm hard to be applied in the feature selection of high-dimensional and large-scale datasets. In order to solve the problems， the monotonic relationship between the positive regions in a decision system was studied and the formal description for the Multi-Scale Attribute Granule （MSAG） was given， and a Multi-scale Attribute Granule based Quick Positive Region reduction algorithm （MAG-QPR） was proposed. Each MSAG contains several attributes and can provide a large positive region for the selected feature attribute subset. As a result， adding MSAG in each iteration can reduce the number of the iteration and make the selected feature attribute subset more quickly approach to the positive region resolving ability of the condition attribute universal set. Therefore， the computational efficiency of the heuristic attribute reduction algorithm for positive region is improved. With 8 UCI datasets used for experiments， on the datasets Lung Cancer， Flag and German， the running time acceleration ratios of MAG-QPR to the general improved Feature Selection algorithm based on the Positive Approximation-Positive Region （FSPA-PR）， the general improved Feature Selection algorithm based on the Positive Approximation-Shannons Conditional Entropy （FSPA-SCE）， the Backward Greedy Reduction Algorithm for positive region Preservation （BGRAP） and the Backward Greedy Reduction Algorithm for Generalized decision preservation （BGRAG） are 9.64， 15.70， 5.03， 2.50; 3.93， 7.55， 1.69， 4.57; and 3.61， 6.49， 1.30， 9.51 respectively. The experimental results show that， the proposed algorithm MAG-QPR can improve the algorithm efficiency and has better classification accuracy.英文關(guān)鍵詞

Key words： attribute reduction; rough set; multi-scale attribute granule; positive region reduction; quick reduction algorithm

0引言

粗糙集理論（rough set theory）[1-2]是一種描述不精確、不確定性信息的形式化工具。目前已經(jīng)廣泛地應(yīng)用于機(jī)器學(xué)習(xí)、模式識(shí)別和數(shù)據(jù)挖掘等研究領(lǐng)域。屬性約簡(jiǎn)（attribute reduction）[3-9]是粗糙集與粒計(jì)算研究的重要問(wèn)題之一，受到眾多學(xué)者的廣泛關(guān)注與深入研究。隨著大規(guī)模高維數(shù)據(jù)集中數(shù)據(jù)量的迅速膨脹，數(shù)據(jù)的冗余特征（屬性）也伴隨增多，這會(huì)嚴(yán)重降低計(jì)算機(jī)的計(jì)算效率，增加計(jì)算機(jī)存儲(chǔ)的負(fù)擔(dān)，降低數(shù)據(jù)分類(lèi)模型的泛化、預(yù)測(cè)能力。因此，找到與原始數(shù)據(jù)集具有相同分辨能力（或分類(lèi)能力）的特征子集顯得尤為重要。在粗糙集與粒計(jì)算研究中，這樣的特征（屬性）子集的選擇過(guò)程被稱(chēng)為屬性約簡(jiǎn)，或?qū)傩裕ㄗ蛹┻x擇。

粗糙集中現(xiàn)有的屬性約簡(jiǎn)方法主要分為基于差別矩陣的約簡(jiǎn)方法和基于啟發(fā)式的約簡(jiǎn)方法。為了求取給定數(shù)據(jù)集的所有特征子集（約簡(jiǎn)），文獻(xiàn)[10]較早地給出了差別矩陣（discernibility matrix）的形式化描述， 但由于差別矩陣求解約簡(jiǎn)需要將差別函數(shù)中的主合取范式（Conjunctive Normal Form， CNF）轉(zhuǎn)換為主析取范式（Disjunctive Normal Form， DNF），因此，通過(guò)差別矩陣求解約簡(jiǎn)是一個(gè)NP-hard問(wèn)題。當(dāng)數(shù)據(jù)集中數(shù)據(jù)量增加時(shí)，基于差別矩陣的約簡(jiǎn)效率會(huì)急劇降低。相較于基于Skowron差別矩陣的約簡(jiǎn)方法，基于啟發(fā)式的約簡(jiǎn)方法可以通過(guò)啟發(fā)式的搜索策略得到一個(gè)約簡(jiǎn)結(jié)果。相同數(shù)據(jù)量下，其算法效率優(yōu)于基于差別矩陣的約簡(jiǎn)方法。因?yàn)楝F(xiàn)代社會(huì)信息化程度的日益提高，數(shù)據(jù)量的急速增加，對(duì)信息時(shí)效性的需求變得愈加強(qiáng)烈，為了更高效、快捷地求取屬性約簡(jiǎn)，眾多學(xué)者展開(kāi)了深入的討論、分析。文獻(xiàn)[11]設(shè)計(jì)了論域劃分的快速求解辦法并提出了一種新的屬性約簡(jiǎn)方法。文獻(xiàn)[12]通過(guò)刪除啟發(fā)式搜索迭代過(guò)程中的部分對(duì)象（粗粒度下的正域），構(gòu)造了基于正向貪婪的屬性約簡(jiǎn)加速算法框架。在該框架下，分別提出了正區(qū)域保持不變、條件信息熵保持不變、梁的條件信息熵保持不變、組合熵保持不變的四種加速算法。實(shí)驗(yàn)結(jié)果表明，采用該框架可以有效地提高四種算法的屬性約簡(jiǎn)效率。除了考慮迭代過(guò)程中刪除的正區(qū)域?qū)ο?，文獻(xiàn)[13]還在屬性約簡(jiǎn)的迭代過(guò)程中刪除了不必要的特征集合，提出了一種快速的啟發(fā)式屬性約簡(jiǎn)框架。文獻(xiàn)[14]通過(guò)給出一種求解等價(jià)類(lèi)的快速排序算法，設(shè)計(jì)了一種算法復(fù)雜度為O（|C|2|U|）的沖突域?qū)傩约s簡(jiǎn)方法。文獻(xiàn)[15]通過(guò)對(duì)論域中所有對(duì)象進(jìn)行抽樣，提出了基于樣例選取的差別矩陣屬性約簡(jiǎn)算法ISDMAR，實(shí)驗(yàn)證明ISDMAR能在保持分類(lèi)精度不降低的情況下有效提高約簡(jiǎn)算法效率?？紤]到文獻(xiàn)[15]中提出的算法是基于差別矩陣的，在大規(guī)模數(shù)據(jù)集合中效率較低，文獻(xiàn)[16]基于啟發(fā)式的論域?qū)ο蟪闃訉傩约s簡(jiǎn)算法，大幅降低了算法運(yùn)行的時(shí)間，提高了算法的效率。文獻(xiàn)[17]與文獻(xiàn)[18]分別對(duì)變精度粗糙集模型（Variable Precision Rough Set Model， VPRSM）近似集的動(dòng)態(tài)更新和動(dòng)態(tài)更新在決策系統(tǒng)中規(guī)則的應(yīng)用先后進(jìn)行了研究。文獻(xiàn)[19]根據(jù)相關(guān)分辨度的概念設(shè)計(jì)了一種新的屬性約簡(jiǎn)貪心算法。在不完備信息系統(tǒng)，文獻(xiàn)[20]提出了兩種單調(diào)的啟發(fā)式信息，由兩種啟發(fā)式信息分別提出了基于不可分辨關(guān)系的快速約簡(jiǎn)算法ARIR（Attribute Reduction algorithm based on the Indiscernibility Relation）和基于分辨關(guān)系的快速約簡(jiǎn)算法ARDR（Attribute Reduction algorithm based on the Discernibility Relation）。為了降低計(jì)算正區(qū)域所占用的時(shí)間，文獻(xiàn)[21]給出了屬性依賴(lài)度計(jì)算的快速算法，該算法能有效地降低算法在內(nèi)存中的占用率，從而降低算法運(yùn)行時(shí)間。文獻(xiàn)[22]對(duì)主要屬性約簡(jiǎn)方法的復(fù)雜度、完備性進(jìn)行了有效的分析。文獻(xiàn)[23-24]在動(dòng)態(tài)變化數(shù)據(jù)值下提出了一種組增量式屬性約簡(jiǎn)算法使得算法更高效。

第12期 陳曼如等：基于多尺度屬性粒策略的快速正域約簡(jiǎn)算法計(jì)算機(jī)應(yīng)用 第39卷綜上，現(xiàn)有加速啟發(fā)式算法的方法有優(yōu)化等價(jià)類(lèi)劃分、正向近似加速機(jī)制、優(yōu)化啟發(fā)因子等，在迭代過(guò)程中計(jì)算候選屬性子集時(shí)很少有學(xué)者進(jìn)行優(yōu)化研究。本文研究了決策系統(tǒng)中正域之間的單調(diào)關(guān)系，給出了多尺度屬性粒的形式化描述，提出了一種基于多尺度屬性粒策略的快速正域約簡(jiǎn)算法（Multi-scale Attribute Granule based Quick Positive Region reduction algorithm， MAG-QPR）。該算法通過(guò)在啟發(fā)式屬性約簡(jiǎn)的每次迭代中添加多屬性粒，達(dá)到減少迭代次數(shù)并使得選定的特征屬性子集能更快地趨近于完整的條件屬性集正域分辨能力的目的，從而加快了啟發(fā)式正域約簡(jiǎn)算法速度，進(jìn)而提高算法效率。

1基礎(chǔ)知識(shí)

本章將介紹與本文研究相關(guān)的粗糙集基本概念和定理，更加詳細(xì)的內(nèi)容請(qǐng)參見(jiàn)文獻(xiàn)[1]。

定義1[3]信息表（信息系統(tǒng)）。InS可以形式化為一個(gè)二元組InS=（O，A）。在InS中，論域O表示對(duì)象（樣本）的集合;屬性集A表示屬性（特征）的集合。

若屬性集A由C與D兩個(gè)交集為空的非空集合組成，C為條件屬性集，D為決策屬性集，則InS是被稱(chēng)為一個(gè)決策表（決策系統(tǒng)），表示為Des=（O，C∪D）。經(jīng)典粗糙集中，討論的決策屬性集D通常只包含一個(gè)決策屬性，即D=j5i0abt0b。

定義2[3]給定的信息表InS=（O，A），論域O={o1， o2，…， on}，oi， oj∈O，對(duì)于QC，定義Q上的不可分辨二元關(guān)系為：

IR（Q）={（oi，oj）|（oi，oj）∈U2，m∈Q，f（ui，m）=f（uj，m）}

易得IR（Q）滿足IR（Q）=∩m∈QIR（{m}），且IR（Q）是一個(gè)等價(jià)關(guān)系。

[oi]IND（Q）={oj|oj∈U且m∈Q， f（oi，m）=f（oj， m）}是關(guān)于屬性集Q包含對(duì)象oi的等價(jià)類(lèi)，商集O/IR（Q）={[oi]IND（Q）|oi∈O}。

在不引起混淆的情況下，IR（Q）可用Q來(lái)表示。

定義3[3]給定的信息表InS=（O，A），若SO，QA，則定義S的下、上近似集為：

Q（S）=∪{[o]Q|[o]QS}

Q（S）=∪{[o]Q|[o]Q∩S≠}

對(duì)于QC與SO， S的下近似集由相對(duì)于Q的確定屬于S的對(duì)象構(gòu)成，S的上近似是由相對(duì)于Q的可能屬于S的對(duì)象組成。由定義3易得，上近似集Q（S）包含下近似集Q（S）。

根據(jù)上述定義給出以下定義：

PSQ（S）=Q（S）

NGQ（S）=O-Q（S）

BNQ（S）=Q（S）-Q（S）

其中：PSQ（S）是S關(guān)于Q屬性集的正域，由屬性集Q下確定屬于集合S里的對(duì)象構(gòu)成;NGQ（S）為S關(guān)于屬性集Q的負(fù)域，由屬性集Q下確定不屬于集合S的對(duì)象構(gòu)成;BNQ（S）是S關(guān)于Q屬性集的邊界域，由屬性集Q下不確定屬于集合S的對(duì)象構(gòu)成。

PSQ（S）、BNQ（S）和NGQ（S）的關(guān)系如圖1所示。

定義4[3]給定的決策表DeS=（O，C∪D），對(duì)QC，論域?qū)的劃分表示為U/D，Dj∈U/D。關(guān)于屬性集Q的決策下近似和上近似集定義為：

Q（D）=∪{[o]Q|[o]QDj}

Q（D）=∪{[o]Q|[o]Q∩Dj≠}

PSQ（D）=Q（D）是關(guān)于屬性集Q的決策屬性D的正域。

定義5[3]給定的決策表DeS=（O，C∪D），QC是一個(gè)DeS的正域約簡(jiǎn)（a reduct for positive region），當(dāng)且僅當(dāng)Q滿足如下兩個(gè)條件：

1）|PSQ（D）|=|PSC（D）|;

2）PQ，|PSp（D）|<|PSQ（D）|。

例1表1是給定的決策表，論域O={o1， o2，…， o8}，條件屬性集C={a1，a2，a3，a4}，決策屬性集D=j5i0abt0b。

2本文算法MAG-QPR

基于迭代中一次添加多個(gè)屬性的策略，本節(jié)提出了一種新的快速正域約簡(jiǎn)算法，并對(duì)算法復(fù)雜度進(jìn)行了分析。

定理1[12]給定的決策表DeS=（O，C∪D），若PQC，則PSP（D）PSQ（D）。

定理2[12]給定的決策表DeS=（O，C∪D），若PiC，則：

PSOPi+1（D）=PSOPi（D）∪PSOi+1Pi+1（D）

其中，O1=O且Oi+1=O-PSOPi（D）。

定理3[12] 給定的決策表DeS=（O，C∪D）， 對(duì)于任意的QC，O=O-PSOQ（D）。對(duì)m，n∈C-Q，|PSOQ∪{m}（D）-PSOQ（D）|≥|PSOQ∪{n}（D）-PSOQ（D）|，則：

|PSOQ∪{m}（D）-PSOQ（D）|≥|PSOQ∪{n}（D）-PSOQ（D）|

定理3是一個(gè)正域?qū)傩灾匾鹊谋３侄ɡ恚摱ɡ肀砻鳎喝粼谡撚驗(yàn)镺的計(jì)算空間下，m關(guān)于正域的外部屬性重要度大于等于n關(guān)于正域的外部屬性重要度。則在論域?yàn)镺*Q的計(jì)算空間下，m關(guān)于正域的外部屬性重要度仍大于等于n關(guān)于正域的外部屬性重要度。因此，在迭代計(jì)算中，為了提高啟發(fā)式算法效率，只需要以O(shè)*作為論域（計(jì)算空間）即可。

定理4給定的決策表DeS=（O，C∪D），對(duì)QC，則∪m∈QPS{m}（D）PSQ（D）。

證明m，n∈Q， PS{m}（D）∪PS{n}（D）PS{m}∪{n}（D）。因此，∪m∈QPS{m}（D）PSQ（D）。證畢。

定理5給定的決策表DeS=（O，C∪D）， 對(duì)于m，n∈C， PS{m}（D）-PS{n}（D）≠，若|PS{m}（D）|≥|PS{n}（D）|，則|PS{m}∪{n}（D）|>|PS{m}（D）|。

證明1）若|PS{m}（D）|>|PS{n}（D）|，由正域隨屬性變化的單調(diào)性，易得|PS{m}∪{n}（D）|>|PS{m}（D）|;2）若|PS{m}（D）|=|PS{n}（D）|，由于PS{m}（D）≠PS{n}（D），{m}∪{n}對(duì)組成的屬性集產(chǎn)生比屬性m（或?qū)傩詎）更細(xì)的粒度，因此|PS{m}∪{n}（D）|>|PS{m}（D）|。證畢。

定義6 給定的決策表DiS=（O，C∪D）， 對(duì)于QC，pi∈C-Q。如果：

|PSQ∪{p1}（D）|≥|PSQ∪{p2}（D）|≥…≥

|PSQ∪{p|C-Q|}（D）|

且：

PSQ∪{p2}（D）-PSQ∪{p1}（D）≠

PSQ∪{p3}（D）-PSQ∪{p1}（D）-PSQ∪{p2}（D）≠

…

PSQ∪{pk}（D）-PSQ∪{p1}（D）-…-PSQ∪{pk-1}（D）=

PSQ∪{pk+1}（D）-PSQ∪{p1}（D）-…-PSQ∪{pk}（D）≠

…

POSQ∪{p|C-Q|}（D）-POSQ∪{p1}（D）-…-

POSQ∪{pk-1}（D）-POSQ∪{pk+1}（D）-…-

POSQ∪{p|C-Q|-1}（D）≠

則grand（Q）={p1，p2，…，pk-1，pk+1，…，p|C-Q|}是關(guān)于集合Q的多尺度屬性粒，其中1≤k≤|C-Q|。

定義6表明，通過(guò)做差集運(yùn)算保證grand（Q）中的每個(gè)屬性和集合Q的并集相對(duì)于決策屬性D產(chǎn)生的正域之間兩兩不存在包含關(guān)系。即：grand（B）中的屬性滿足PSQ∪{p1}（D），PSQ∪{p2}（D），…，PSQ∪{pk-1}（D），PSQ∪{pk+1}（D），…，PSQ∪{p|C-Q|}（D）產(chǎn)生的集合不存在兩兩包含關(guān)系。

定理6給定的決策表DeS=（O，C∪D），集合QC，令grand（Q）={p1，p2，…，pj}，則：

|PSQ∪grand（Q）（D）|>|PSQ∪{p1}（D）|

|PSQ∪grand（Q）（D）|>|PSQ∪{p1}（D）∪PSQ∪{p2}（D）|

…

|PSQ∪grand（Q）（D）|>|PSQ∪{p1}（D）∪PSQ∪{p2}（D）∪

…∪PSQ∪{pj-1}（D）|

其中1≤j≤|grand（Q）|。

證明根據(jù)定理5易知定理6成立。證明略。

因?yàn)間rand（Q）中的屬性和集合Q產(chǎn)生的正域不存在兩兩包含關(guān)系。因此，每次迭代添加的屬性粒（集）形成的正域較經(jīng)典啟發(fā)式算法中每輪添加的單個(gè)屬性形成的正域要大，故加快了迭代的速度，提高了算法效率。

基于多尺度屬性粒策略的快速正域約簡(jiǎn)算法（MAG-QPR）算法偽代碼如下。

算法1有如下四點(diǎn)優(yōu)勢(shì)：

1）一般情況下，算法1每次迭代添加的屬性集形成的正域大于經(jīng)典啟發(fā)式正域約簡(jiǎn)算法中每次添加的單個(gè)屬性形成的正域，這樣可以更快地趨近于正域約簡(jiǎn)的停止條件，即定義5中的|PSQ（D）|=|PSC（D）|。

2）由于每次迭代添加的屬性集包含多個(gè)屬性，因此，算法1總的迭代次數(shù)較經(jīng)典啟發(fā)式正域約簡(jiǎn)算法較少。迭代次數(shù)減少，則算法效率提高。

3）現(xiàn)有的啟發(fā)式算法求核仍采用刪除法，即通過(guò)逐個(gè)刪除屬性的方法來(lái)求取核屬性。在大規(guī)模數(shù)據(jù)集下，這顯然是低效的。因此，算法1不從核屬性集出發(fā)，直接進(jìn)行迭代計(jì)算。

4）采用迭代過(guò)程中，刪除一部分對(duì)象集（待計(jì)算空間的正域或粗粒度下的正域）的方法來(lái)減少計(jì)算空間，進(jìn)而提高啟發(fā)式算法的效率。算法1的主要流程如圖2所示，其中，A部分采用多尺度屬性粒方法來(lái)計(jì)算候選屬性的正域重要度，B部分刪除候選屬性集的正域，C部分為取出啟發(fā)式算法可能產(chǎn)生的冗余屬性。

假設(shè)T表示算法1的時(shí)間復(fù)雜度，條件屬性集的基數(shù)為m，論域的基數(shù)為n，迭代第i輪次中待評(píng)估的屬性基數(shù)為mi，迭代第i輪次中的剩余對(duì)象數(shù)ni，k≤|C|表示需要迭代的輪次。除去正域與將多尺度屬性粒添加到候選子集的時(shí)間復(fù)雜度可表示為O（∑ki=1mini），去除冗余屬性的時(shí)間復(fù)雜度可表示為O（m2n）。綜上，算法1的整體時(shí)間復(fù)雜度為T(mén)=O（m2n+∑ki=1mini）。

例2如例1中的決策系統(tǒng)，O={o1， o2， o3，…， o8}為論域，C={a1，a2，a3，a4}為條件屬性集合，D=j5i0abt0b決策屬性集合。

按照算法1對(duì)例1中的表進(jìn)行屬性約簡(jiǎn)，具體計(jì)算過(guò)程如下：

1） 開(kāi)始首次迭代，初始R=，因此C=C-R中任意屬性的決策正域值為|PSO1a1（D）|=1，|PSO1a2（D）|=0，|PSO1a3（D）|=0，|PSO1a1（D）|>|PSO1a2（D）|≥|PSO1a3（D）|≥|PSO1a4（D）|。且：

PSO1R∪{a2}（D）-PSO1R∪{a1}（D）=

PSO1R∪{a3}（D）-PSO1R∪{a1}（D）=

PSO1R∪{a4}（D）-PSO1R∪{a1}（D）=

則grand（R）={a1}，R=R∪grand（R）={a1}，O2={o1， o2，…， o8}。

由于|PSO2C（D）|≠|(zhì)PSO2R（D）|，所以繼續(xù)第二次迭代。

2）計(jì)算C-R中任意屬性與R并集的決策正域的值為|PSO2R∪{a2}（D）|=4，|PSO2R∪{a3}（D）|=2，|PSO2R∪{a4}（D）|=3，|PSO2R∪{a2}（D）|>|PSO2R∪{a4}（D）|>PSO2R∪{a3}（D）|。且：

PSO2R∪{a4}（D）-PSO2R∪{a2}（D）≠

則grand（R）={a2，a4}，R=R∪grand（R）={a1，a2，a4}，O3=O2-PSO2R（D）={o7， o8}。

由于|PSO3C（D）|=|PSO3R（D）|，迭代結(jié)束。

如果R中減去任意的屬性ai均不改變R的決策正域，因此，屬性集R中不存在冗余或不相關(guān)的屬性，整個(gè)算法結(jié)束;綜上，可得決策表1的約簡(jiǎn)為R={a1，a2，a4}。

3實(shí)驗(yàn)與結(jié)果分析

本文的實(shí)驗(yàn)采用了UCI標(biāo)準(zhǔn)數(shù)據(jù)集對(duì)算法進(jìn)行測(cè)試，UCI數(shù)據(jù)集的詳細(xì)信息如表2所示，共有8組UCI數(shù)據(jù)集。實(shí)驗(yàn)所使用的PC機(jī)硬件環(huán)境為：CPU為Intel i5-2450M，內(nèi)存為4GB。軟件環(huán)境：操作系統(tǒng)為Windows 7，編程環(huán)境為Matlab 7.11.0（R2010b）。

實(shí)驗(yàn)分成四組。第一組：將本文提出的算法與FSPA-PR（a general improved Feature Selection algorithm based on the Positive Approximation-Positive Region） [12]、FSPA-SCE（a general improved Feature Selection algorithm based on the Positive Approximation-Shannon Conditional Entropy） [12]、BGRAP（a Backward Greedy Reduction Algorithm for Positive region preservation） [22]、BGRAG（A Backward Greedy Reduction for Generalized decision preservation） [25]四種算法對(duì)于算法消耗的時(shí)間與屬性約簡(jiǎn)的長(zhǎng)度進(jìn)行詳細(xì)的比較。第二組：將本文算法在不同數(shù)據(jù)集上迭代的詳細(xì)情況和最終的約簡(jiǎn)結(jié)果進(jìn)行比較。第三組：將本文算法與其他四種算法對(duì)于論域規(guī)模和消耗時(shí)間之間關(guān)系進(jìn)行比較。第四組：將本文算法與其他四種算法在分類(lèi)精度方面進(jìn)行比較。

表2給出了實(shí)驗(yàn)所需數(shù)據(jù)集的基本信息（樣本數(shù)量、條件屬性與決策類(lèi)數(shù)量）。Ticdata2000數(shù)據(jù)集為了訓(xùn)練和驗(yàn)證預(yù)測(cè)模型并建立描述（5822個(gè)客戶記錄）;Student Performance數(shù)據(jù)提供了接近兩個(gè)葡萄牙語(yǔ)學(xué)校中學(xué)教育的學(xué)生成績(jī)（數(shù)據(jù)屬性包括：學(xué)生等級(jí)、人口統(tǒng)計(jì)學(xué)、社會(huì)學(xué)和學(xué)校相關(guān)特征等）;QSAR Biodegradation為定量結(jié)構(gòu)活性關(guān)系生物降解數(shù)據(jù)集，決策類(lèi)別為是否可以生物降解;Zoo數(shù)據(jù)集為動(dòng)物園數(shù)據(jù)集，由16個(gè)屬性來(lái)描述樣本，其中15個(gè)為布爾屬性值{0，1}和1個(gè)分類(lèi)屬性（腿的數(shù)量）{0，2，4，6，8};Kr-vs-kp數(shù)據(jù)集描述了靈長(zhǎng)類(lèi)動(dòng)物的基因序列不完善理論;Flag數(shù)據(jù)集通過(guò)判斷一個(gè)國(guó)家的國(guó)旗顏色、國(guó)旗上圓圈的數(shù)量，以及國(guó)旗上星星的數(shù)量等預(yù)測(cè)這個(gè)國(guó)家的宗教信仰;German數(shù)據(jù)集為德國(guó)信譽(yù)數(shù)據(jù)，通過(guò)人的屬性描述一個(gè)人的好壞信譽(yù);Lung Cancer數(shù)據(jù)集記錄了病人的肺癌數(shù)據(jù)。由表2可以看出：數(shù)據(jù)集1的規(guī)模最大，包含的屬性數(shù)目和樣本數(shù)目均為最多;數(shù)據(jù)集2包含的決策類(lèi)數(shù)目最多;數(shù)據(jù)集4包含的屬性數(shù)目最少;數(shù)據(jù)集8包含的樣本數(shù)目最少;數(shù)據(jù)集1、3、7和8包含的決策類(lèi)數(shù)目最少。

表3給出了MAG-QPR與其他四種算法在消耗時(shí)間和屬性約簡(jiǎn)長(zhǎng)度的對(duì)比。不難看出，本文提出的MAG-QPR在8組數(shù)據(jù)集上的消耗時(shí)間均為最少，因此，MAG-QPR具有較高的運(yùn)行效率。例如，在數(shù)據(jù)集Lung Cancer中，MAG-QPR所需要的時(shí)間為0.1150s，而算法FSPA-PR、BGRAP、FSPA-SCE與BGRAG所需的時(shí)間分別為1.1086s、0.5783s、1.8054s與0.2876s。這四種算法消耗時(shí)間分別是MAG-QPR消耗時(shí)間的9.64、5.03、15.70與2.50倍。在數(shù)據(jù)規(guī)模較大的Ticdata2000中，MAG-QPR所需要的時(shí)間為126.9767s，而算法FSPA-PR、BGRAP、FSPA-SCE與BGRAG所需的時(shí)間分別為527.5613s、250.2735s、823.1517s與3392.7184s。這四種算法消耗時(shí)間分別是MAG-QPR消耗時(shí)間的4.1、1.97、6.48與26.71倍。由于多尺度屬性粒包含多個(gè)屬性，因此在啟發(fā)式約簡(jiǎn)的迭代過(guò)程中一次性添加進(jìn)選定特征屬性子集的屬性數(shù)量較多，算法效率較高，同時(shí)刪除了每次迭代中的部分正域，因此本文提出的MAG-QPR所需的時(shí)間相較于其他四種算法較短。

不同算法的時(shí)間效率對(duì)比如圖3所示，圖3給出了不同算法消耗時(shí)間隨數(shù)據(jù)規(guī)模的變化趨勢(shì)。圖3中：縱軸代表算法消耗的時(shí)間;橫軸代表論域（對(duì)象）的規(guī)模，將每個(gè)數(shù)據(jù)集的論域（對(duì)象集）分為10等份，逐一疊加作為測(cè)試數(shù)據(jù)集。例如，若給定的UCI數(shù)據(jù)集有4000個(gè)對(duì)象，將4000個(gè)對(duì)象分10等份，第一個(gè)測(cè)試數(shù)據(jù)集的論域由前400個(gè)對(duì)象構(gòu)成，第二個(gè)測(cè)試數(shù)據(jù)集的論域由前800個(gè)對(duì)象構(gòu)成，……，第十個(gè)測(cè)試數(shù)據(jù)集的論域由全部4000個(gè)對(duì)象構(gòu)成。總體上，五種算法的消耗時(shí)間均隨著論域規(guī)模的增大而增加，但在局部并不保持嚴(yán)格的單調(diào)性。例如：如圖3（c），論域規(guī)模從5增加到6，算法FSPA-PR消耗的時(shí)間反而下降;又如圖3（g）， 論域規(guī)模從8到9，MAG-QPR消耗的時(shí)間變少。這是因?yàn)閱l(fā)式算法迭代中每次選擇的屬性均為局部最優(yōu)解，因此消耗時(shí)間在局部?jī)?nèi)會(huì)出現(xiàn)隨著數(shù)據(jù)規(guī)模的增大而減少的情況。從圖3還可以發(fā)現(xiàn)，相較于其他四種算法（FSPA-PR、BGRAP、FSPA-SCE與BGRAG），MAG-QPR曲線平均斜率偏小，更貼近于水平軸。且MAG-QPR曲線隨著論域規(guī)模增大的計(jì)算時(shí)間變化較小，而其他四種算法隨著論域規(guī)模增大的計(jì)算時(shí)間變化較大。對(duì)于圖3中的每一個(gè)數(shù)據(jù)集，當(dāng)論域規(guī)模較小時(shí)，五種算法消耗時(shí)間的差別并不是很明顯;當(dāng)隨著論域規(guī)模由小變大時(shí)，五種算法消耗時(shí)間的差別越來(lái)越大，MAG-QPR消耗時(shí)間較少的優(yōu)勢(shì)越來(lái)越明顯。因此，對(duì)于大規(guī)模數(shù)據(jù)集，本文提出的MAG-QPR具有較大的優(yōu)勢(shì)。

表4給出了MAG-QPR在不同UCI數(shù)據(jù)集上迭代次數(shù)和每次迭代添加屬性的相關(guān)情況，采用ai∈|C|表示決策表中的條件屬性。整體上，采用MAG-QPR，8組數(shù)據(jù)集的屬性約簡(jiǎn)迭代次數(shù)均比較少，最大的是數(shù)據(jù)集German，迭代次數(shù)也僅為3次。迭代次數(shù)的減少會(huì)明顯提高算法的運(yùn)行效率。

表4中，用粗體表示本次迭代選擇的屬性。例如，對(duì)于數(shù)據(jù)集Student Performance， 整個(gè)算法共迭代了2次，第一次迭代的屬性集合為：{a32， a30， a31， a3}，第二次迭代添加的屬性集合為：{ a7， a26， a28， a25， a29， a9， a5}。因此，整個(gè)算法迭代過(guò)程結(jié)束以后，得到的屬性集合為：{a32， a30， a31， a3， a7， a26， a28， a25， a29， a9， a5}。刪除冗余的條件屬性后，得到的正域約簡(jiǎn)結(jié)果為：a32， a30， a31， a7， a26， a28， a25 。

表5～6給出了采用五種算法得到的約簡(jiǎn)結(jié)果在KNN和Naive Bayesian兩種分類(lèi)器的分類(lèi)精度對(duì)比，這里的分類(lèi)精度實(shí)驗(yàn)采用十折交叉驗(yàn)證（10-fold cross validation）的方法。同一數(shù)據(jù)集中，用粗體表示分類(lèi)精度最高值。在表5中，采用MAG-QPR的約簡(jiǎn)結(jié)果在4組數(shù)據(jù)集上的分類(lèi)精度優(yōu)于其他四種算法與原始系統(tǒng)的分類(lèi)精度。在表6中，采用MAG-QPR的約簡(jiǎn)結(jié)果也在5組數(shù)據(jù)集上的分類(lèi)精度優(yōu)于其他四種個(gè)算法與原始分類(lèi)精度。綜上可知，MAG-QPR在兩種分類(lèi)器上的分類(lèi)精度均值均優(yōu)于其他四種算法的分類(lèi)精度。

4結(jié)語(yǔ)

相較于差別矩陣正域約簡(jiǎn)算法，啟發(fā)式正域約簡(jiǎn)算法具有較高的運(yùn)行效率。但是面對(duì)大規(guī)模數(shù)據(jù)集，傳統(tǒng)啟發(fā)式正域約簡(jiǎn)算法需要在每次迭代的過(guò)程中添加當(dāng)前重要度（正域依賴(lài)度）最大的屬性進(jìn)候選屬性子集，效率低且算法迭代次數(shù)多，難以應(yīng)用于大規(guī)模數(shù)據(jù)集的特征選擇中?？紤]到這種情況，本文設(shè)計(jì)了一種快速的正域?qū)傩约s簡(jiǎn)算法——MAG-QPR。

該算法有如下四點(diǎn)優(yōu)勢(shì)：

1）MAG-QPR在每次迭代添加的屬性集形成的正域大于經(jīng)典正域算法中每次添加的單個(gè)屬性形成的正域;

2）MAG-QPR不需要從核屬性開(kāi)始，直接進(jìn)行迭代運(yùn)算;

3）MAG-QPR每次迭代的添加以屬性集作為基本單位，提高了迭代的效率，促使算法總的迭代次數(shù)較少;

4）在每次迭代中，刪除部分對(duì)象集（粗粒度下的正域），從而使得計(jì)算空間變小，提高算法效率。

將本文的算法MAG-QPR與四種啟發(fā)式算法（FSPA-PR、BGRAP、FSPA-SCE與BGRAG）進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明：

1）相較其他四種算法，MAG-QPR在選擇的8組UCI數(shù)據(jù)集上的算法效率具有明顯優(yōu)勢(shì);

2）采用屬性粒作為每次迭代添加的基本單位，可以有效地減少迭代次數(shù)，提高了算法效率;

3） 隨著數(shù)據(jù)規(guī)模（論域規(guī)?；?qū)ο髷?shù)目）的增多，MAG-QPR相較于其他四種算法具有明顯的效率優(yōu)勢(shì);

4） MAG-QPR在兩種分類(lèi)器上的分類(lèi)精度的表現(xiàn)總體上好于其他四種算法的分類(lèi)精度。

在今后的研究工作中，將在算法MAG-QPR中去除冗余屬性效率和其他約簡(jiǎn)目標(biāo)下的多尺度屬性粒的快速約簡(jiǎn)方面繼續(xù)進(jìn)行深入的研究。

參考文獻(xiàn) （References）

[1]PAWLAK Z. Rough sets [J]. International Journal of Computer and Information Sciences， 1982， 11（5）： 341-356.

[2]王國(guó)胤，姚一豫，于洪.粗糙集理論與應(yīng)用研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（7）：1229-1246.（WANG G Y， YAO Y Y， YU H. A survey on rough set theory and applications [J]. Chinese Journal of Computers， 2009， 32（7）： 1229- 1246.）

[3]MIAO D， ZHAO Y， YAO Y， et al. Relative reducts in consistent and inconsistent decision tables of the Pawlak rough set model [J]. Information Sciences， 2009， 179（24）： 4140-4150.

[4]LI H， LI D， ZHAI Y， et al. A novel attribute reduction approach for multi-label data based on rough set theory [J]. Information Sciences， 2016， 367/368： 827-847.

[5]YAO Y， ZHAO Y. Attribute reduction in decision-theoretic rough set models [J]. Information Sciences， 2008， 178（17）： 3356-3373.

[6]JIA X， SHANG L， ZHOU B， et al. Generalized attribute reduct in rough set theory [J]. Knowledge-Based Systems， 2016， 91（6）： 204-218.

[7]張楠，苗奪謙，岳曉冬.區(qū)間值信息系統(tǒng)的知識(shí)約簡(jiǎn)[J].計(jì)算機(jī)研究與發(fā)展，2010，47（8）：1362-1371.（ZHANG N， MIAO D Q， YUE X D. Approaches to knowledge reduction in interval-valued information systems [J]. Journal of Computer Research and Development， 2010， 47（8）： 1362-1371.）

[8]HU Q， ZHAO H， XIE Z， et al. Consistency based attribute reduction [C]// Proceedings of the 2007 Pacific-Asia Conference on Knowledge Discovery and Data Mining， LNCS 4426. Berlin： Springer， 2007： 96-107.

[9]GUAN Y Y， WANG H K. Set-valued information systems[J]. Information Sciences. 2006， 176（17）： 2507-25-25.

[10]SKOWRON A， RAUSZER C. The discernibility matrices and functions in information systems [M]// SOWINSKI R. Intelligent Decision Support： Handbook of Applications and Advances to Rough Sets Theory. Dordrecht： Kluwer Academic Publishers， 1992： 331-362.

[11]徐章艷，劉作鵬，楊炳儒，等.一個(gè)復(fù)雜度為max（O（|C||U|）， O（|C|2|U/C|））的快速屬性約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào)，2006，29（3）：391-399.（XU Z Y， LIU Z P， YANG B R， et al. A quick attribute reduction algorithm with complexity of max（O（|C||U|）， O（|C|2|U/C|）） [J]. Chinese Journal of Computers， 2006， 29（3）： 391-399.）

[12]QIAN Y， LIANG J， PEDRYCZ W， et al. Positive approximation： an accelerator for attribute reduction in rough set theory [J]. Artificial Intelligence， 2010， 174（9/10）： 597-618.

[13]LIANG J， MI J， WEI W， et al. An accelerator for attribute reduction based on perspective of objects and attributes [J]. Knowledge-Based Systems， 2013， 44： 90-100.

[14]葛浩，李龍澍，楊傳健.基于沖突域的高效屬性約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（2）：342-350.（GE H， LI L S， YANG C J. An efficient attribute reduction algorithm based on conflict region [J]. Chinese Journal of Computers， 2012， 35（2）： 342-350.）

[15]王熙照，王婷婷，翟俊海.基于樣例選取的屬性約簡(jiǎn)算法[J].計(jì)算機(jī)研究與發(fā)展，2012，49（11）：2305-2310.（WANG X Z， WANG T T， ZHAI J H. An attribute reduction algorithm based on instance selection [J]. Journal of Computer Research and Development， 2012， 49（11）： 2305-2310.）

[16]楊習(xí)貝，顏旭，徐蘇平，等.基于樣本選擇的啟發(fā)式屬性約簡(jiǎn)方法研究[J].計(jì)算機(jī)科學(xué)，2016，43（1）：40-43.（YANG X B， YAN X， XU S P， et al. New heuristic attribute reduction algorithm based on sample selection [J]. Computer Science， 2016， 43（1）： 40-43.）

[17]CHEN H， LI T， RUAN D， et al. A rough-set-based incremental approach for updating approximations under dynamic maintenance environments [J]. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（2）： 274-284.

[18]CHEN H， LI T R， LUO C， et al. A rough set-based method for updating decision rules on attribute values coarsening and refining [J]. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（12）： 2886-2899.

[19]TENG S， LU M， YANG A， et al. Efficient attribute reduction from the viewpoint of discernibility [J]. Information Sciences， 2016， 326： 297-314.

[20]SHU W， QIAN W. A fast approach to attribute reduction from perspective of attribute measures in incomplete decision systems [J]. Knowledge-Based Systems， 2014， 72： 60-71.

[21]RAZA M S， QAMAR U. Feature selection using rough set-based direct dependency calculation by avoiding the positive region [J]. International Journal of Approximate Reasoning， 2018， 92： 175-197.

[22]苗奪謙，李道國(guó).粗糙集理論、算法與應(yīng)用[M].北京：清華大學(xué)出版社，2008：87-214.（MIAO D Q， LI D G. Rough Sets Theory Algorithms and Applications [M]. Beijing： Tsinghua University Press， 2008： 87-214.）

[23]JING Y G， LI T， HUANG J， et al. A group incremental reduction algorithm with varying data values [J]. International Journal of Intelligent Systems， 2017， 32（9）： 900-925.

[24]JING Y， LI T， FUJITA H， et al. An incremental attribute reduction method for dynamic data mining [J]. Information Sciences， 2018， 465： 202-218.