基于多尺度屬性粒策略的快速正域約簡算法

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

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

關鍵詞：屬性約簡;粗糙集;多尺度屬性粒;正域約簡;快速約簡算法

中圖分類號： TP181;TP301.4文獻標志碼：A英文標題

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.英文關鍵詞

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

0引言

粗糙集理論（rough set theory）[1-2]是一種描述不精確、不確定性信息的形式化工具。目前已經廣泛地應用于機器學習、模式識別和數據挖掘等研究領域。屬性約簡（attribute reduction）[3-9]是粗糙集與粒計算研究的重要問題之一，受到眾多學者的廣泛關注與深入研究。隨著大規模高維數據集中數據量的迅速膨脹，數據的冗余特征（屬性）也伴隨增多，這會嚴重降低計算機的計算效率，增加計算機存儲的負擔，降低數據分類模型的泛化、預測能力。因此，找到與原始數據集具有相同分辨能力（或分類能力）的特征子集顯得尤為重要。在粗糙集與粒計算研究中，這樣的特征（屬性）子集的選擇過程被稱為屬性約簡，或屬性（子集）選擇。

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

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

1基礎知識

本章將介紹與本文研究相關的粗糙集基本概念和定理，更加詳細的內容請參見文獻[1]。

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

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

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

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

易得IR（Q）滿足IR（Q）=∩m∈QIR（{m}），且IR（Q）是一個等價關系。

[oi]IND（Q）={oj|oj∈U且m∈Q， f（oi，m）=f（oj， m）}是關于屬性集Q包含對象oi的等價類，商集O/IR（Q）={[oi]IND（Q）|oi∈O}。

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

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

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

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

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

根據上述定義給出以下定義：

PSQ（S）=Q（S）

NGQ（S）=O-Q（S）

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

其中：PSQ（S）是S關于Q屬性集的正域，由屬性集Q下確定屬于集合S里的對象構成;NGQ（S）為S關于屬性集Q的負域，由屬性集Q下確定不屬于集合S的對象構成;BNQ（S）是S關于Q屬性集的邊界域，由屬性集Q下不確定屬于集合S的對象構成。

PSQ（S）、BNQ（S）和NGQ（S）的關系如圖1所示。

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

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

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

PSQ（D）=Q（D）是關于屬性集Q的決策屬性D的正域。

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

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

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

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

2本文算法MAG-QPR

基于迭代中一次添加多個屬性的策略，本節提出了一種新的快速正域約簡算法，并對算法復雜度進行了分析。

定理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）， 對于任意的QC，O=O-PSOQ（D）。對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是一個正域屬性重要度的保持定理，該定理表明：若在論域為O的計算空間下，m關于正域的外部屬性重要度大于等于n關于正域的外部屬性重要度。則在論域為O*Q的計算空間下，m關于正域的外部屬性重要度仍大于等于n關于正域的外部屬性重要度。因此，在迭代計算中，為了提高啟發式算法效率，只需要以O*作為論域（計算空間）即可。

定理4給定的決策表DeS=（O，C∪D），對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）， 對于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）|，由正域隨屬性變化的單調性，易得|PS{m}∪{n}（D）|>|PS{m}（D）|;2）若|PS{m}（D）|=|PS{n}（D）|，由于PS{m}（D）≠PS{n}（D），{m}∪{n}對組成的屬性集產生比屬性m（或屬性n）更細的粒度，因此|PS{m}∪{n}（D）|>|PS{m}（D）|。證畢。

定義6 給定的決策表DiS=（O，C∪D）， 對于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|}是關于集合Q的多尺度屬性粒，其中1≤k≤|C-Q|。

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

定理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）|。

證明根據定理5易知定理6成立。證明略。

因為grand（Q）中的屬性和集合Q產生的正域不存在兩兩包含關系。因此，每次迭代添加的屬性粒（集）形成的正域較經典啟發式算法中每輪添加的單個屬性形成的正域要大，故加快了迭代的速度，提高了算法效率。

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

算法1有如下四點優勢：

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

2）由于每次迭代添加的屬性集包含多個屬性，因此，算法1總的迭代次數較經典啟發式正域約簡算法較少。迭代次數減少，則算法效率提高。

3）現有的啟發式算法求核仍采用刪除法，即通過逐個刪除屬性的方法來求取核屬性。在大規模數據集下，這顯然是低效的。因此，算法1不從核屬性集出發，直接進行迭代計算。

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

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

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

按照算法1對例1中的表進行屬性約簡，具體計算過程如下：

1） 開始首次迭代，初始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）|≠|PSO2R（D）|，所以繼續第二次迭代。

2）計算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）|，迭代結束。

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

3實驗與結果分析

本文的實驗采用了UCI標準數據集對算法進行測試，UCI數據集的詳細信息如表2所示，共有8組UCI數據集。實驗所使用的PC機硬件環境為：CPU為Intel i5-2450M，內存為4GB。軟件環境：操作系統為Windows 7，編程環境為Matlab 7.11.0（R2010b）。

實驗分成四組。第一組：將本文提出的算法與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]四種算法對于算法消耗的時間與屬性約簡的長度進行詳細的比較。第二組：將本文算法在不同數據集上迭代的詳細情況和最終的約簡結果進行比較。第三組：將本文算法與其他四種算法對于論域規模和消耗時間之間關系進行比較。第四組：將本文算法與其他四種算法在分類精度方面進行比較。

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

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

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

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

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

表5～6給出了采用五種算法得到的約簡結果在KNN和Naive Bayesian兩種分類器的分類精度對比，這里的分類精度實驗采用十折交叉驗證（10-fold cross validation）的方法。同一數據集中，用粗體表示分類精度最高值。在表5中，采用MAG-QPR的約簡結果在4組數據集上的分類精度優于其他四種算法與原始系統的分類精度。在表6中，采用MAG-QPR的約簡結果也在5組數據集上的分類精度優于其他四種個算法與原始分類精度。綜上可知，MAG-QPR在兩種分類器上的分類精度均值均優于其他四種算法的分類精度。

4結語

相較于差別矩陣正域約簡算法，啟發式正域約簡算法具有較高的運行效率。但是面對大規模數據集，傳統啟發式正域約簡算法需要在每次迭代的過程中添加當前重要度（正域依賴度）最大的屬性進候選屬性子集，效率低且算法迭代次數多，難以應用于大規模數據集的特征選擇中。考慮到這種情況，本文設計了一種快速的正域屬性約簡算法——MAG-QPR。

該算法有如下四點優勢：

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

2）MAG-QPR不需要從核屬性開始，直接進行迭代運算;

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

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

將本文的算法MAG-QPR與四種啟發式算法（FSPA-PR、BGRAP、FSPA-SCE與BGRAG）進行比較，實驗結果表明：

1）相較其他四種算法，MAG-QPR在選擇的8組UCI數據集上的算法效率具有明顯優勢;

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

3） 隨著數據規模（論域規模或對象數目）的增多，MAG-QPR相較于其他四種算法具有明顯的效率優勢;

4） MAG-QPR在兩種分類器上的分類精度的表現總體上好于其他四種算法的分類精度。

在今后的研究工作中，將在算法MAG-QPR中去除冗余屬性效率和其他約簡目標下的多尺度屬性粒的快速約簡方面繼續進行深入的研究。

參考文獻 （References）

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

[2]王國胤，姚一豫，于洪.粗糙集理論與應用研究綜述[J].計算機學報，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]張楠，苗奪謙，岳曉冬.區間值信息系統的知識約簡[J].計算機研究與發展，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]徐章艷，劉作鵬，楊炳儒，等.一個復雜度為max（O（|C||U|）， O（|C|2|U/C|））的快速屬性約簡算法[J].計算機學報，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]葛浩，李龍澍，楊傳健.基于沖突域的高效屬性約簡算法[J].計算機學報，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]王熙照，王婷婷，翟俊海.基于樣例選取的屬性約簡算法[J].計算機研究與發展，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]楊習貝，顏旭，徐蘇平，等.基于樣本選擇的啟發式屬性約簡方法研究[J].計算機科學，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]苗奪謙，李道國.粗糙集理論、算法與應用[M].北京：清華大學出版社，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.