康 猛，蒙祖強(qiáng)

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西南寧 530004）

0 引言

1982 年，波蘭數(shù)學(xué)家Pawlak 提出了粗糙集理論［1］，它是繼概率論、模糊集、證據(jù)理論之后的又一個(gè)處理不確定性問(wèn)題的數(shù)學(xué)工具。自粗糙集理論提出以來(lái)，屬性約簡(jiǎn)［2］一直是粗糙集領(lǐng)域的重點(diǎn)研究?jī)?nèi)容之一。屬性約簡(jiǎn)本質(zhì)上是一個(gè)搜索尋優(yōu)問(wèn)題，但最小屬性子集的搜索是一個(gè)不確定多項(xiàng)式（Non-deterministic Polynomial，NP）問(wèn)題［3］，因此學(xué)者們致力于用啟發(fā)式搜索算法尋找屬性約簡(jiǎn)的次優(yōu)解。目前，國(guó)內(nèi)外學(xué)者已經(jīng)提出了許多屬性約簡(jiǎn)算法，典型的有：基于正區(qū)域的屬性約簡(jiǎn)［4-7］、基于差別矩陣的屬性約簡(jiǎn)［8-10］、基于信息熵的屬性約簡(jiǎn)［11-14］等。然而，這些算法普遍存在約簡(jiǎn)結(jié)果分類精度低、時(shí)空復(fù)雜度高等問(wèn)題。

利用區(qū)分矩陣設(shè)計(jì)屬性約簡(jiǎn)算法具有直觀易理解的優(yōu)點(diǎn)。區(qū)分矩陣的元素是能夠區(qū)分該元素對(duì)應(yīng)的兩個(gè)實(shí)例的屬性集合。若屬性能夠區(qū)分的對(duì)象越多，即區(qū)分能力越強(qiáng)，則它對(duì)論域的劃分就越細(xì)，知識(shí)粒度就越小，該屬性就越重要，因此，利用屬性的區(qū)分能力來(lái)決定屬性的重要性是一種合理的方法；但區(qū)分矩陣存在計(jì)算復(fù)雜度高和存儲(chǔ)開(kāi)銷(xiāo)大等問(wèn)題。為提高約簡(jiǎn)算法效率，文獻(xiàn)［15］提出了一種利用二進(jìn)制區(qū)分矩陣降低時(shí)間開(kāi)銷(xiāo)的約簡(jiǎn)算法；文獻(xiàn)［16］提出了一種基于集中有序區(qū)分集的屬性約簡(jiǎn)算法，將時(shí)空復(fù)雜度分別降低為max｛O（|C||U′pos||U/C||MsCount|），O（|C|2|MsCount|）｝和O（|MsCount|）（其中C為條件屬性集，U為論域，U′pos為簡(jiǎn)化的決策表，MsCount為簡(jiǎn)化決策表差別集的基數(shù)）；文獻(xiàn)［17］為了降低區(qū)分矩陣法的計(jì)算復(fù)雜度，利用快速計(jì)數(shù)排序算法處理數(shù)據(jù)，構(gòu)建了改進(jìn)的區(qū)分矩陣，給出了一種新的屬性約簡(jiǎn)算法；文獻(xiàn)［18］對(duì)基于優(yōu)勢(shì)的粗糙集方法進(jìn)行擴(kuò)展，提出了優(yōu)勢(shì)可辨矩陣的概念，進(jìn)一步提出了一種基于優(yōu)勢(shì)區(qū)分矩陣的屬性約簡(jiǎn)算法；文獻(xiàn)［19］提出了一種新的屬性質(zhì)量度量方法和相對(duì)區(qū)分度，從區(qū)分的角度提出了一種新的屬性約簡(jiǎn)算法；文獻(xiàn)［20］針對(duì)決策系統(tǒng)中的不可區(qū)分關(guān)系及可區(qū)分關(guān)系，給出相應(yīng)的協(xié)調(diào)集判定定理，進(jìn)而借助區(qū)分矩陣及區(qū)分函數(shù)給出屬性約簡(jiǎn)方法；文獻(xiàn)［21］設(shè)計(jì)了一種更簡(jiǎn)化的區(qū)分矩陣，不需要生成所有的形式化決策上下文，進(jìn)一步提出了一種新的形式化決策上下文屬性約簡(jiǎn)方法，降低了算法的時(shí)空復(fù)雜度。

上述算法［15-21］幾乎都是通過(guò)優(yōu)化區(qū)分矩陣或通過(guò)劃分等價(jià)類計(jì)算屬性的區(qū)分能力來(lái)降低算法的時(shí)空復(fù)雜度，但是沒(méi)有考慮到區(qū)分矩陣的構(gòu)建及區(qū)分能力的計(jì)算都具有很高的時(shí)空復(fù)雜度。針對(duì)這一不足，本文在區(qū)分關(guān)系的基礎(chǔ)上，定義了條件區(qū)分能力，給出了基于條件區(qū)分能力的屬性約簡(jiǎn)算法；又利用大數(shù)定律將條件區(qū)分能力擴(kuò)展為局部條件區(qū)分能力，加快了屬性重要度的計(jì)算，進(jìn)而提出了一種基于局部條件區(qū)分能力的高效屬性約簡(jiǎn)算法。實(shí)驗(yàn)結(jié)果表明，本文算法具有更低的時(shí)空復(fù)雜度。

1 基本概念

定義1［1］形式上，四元組IS=〈U，A，V，f〉表示一個(gè)信息系統(tǒng)，其中：U為非空有限集合，稱為論域；A為屬性集，若A=C∪D，C∩D=?，則C為條件屬性集，D為決策屬性集；V為值域；f：U×A→V為信息函數(shù)，表示每個(gè)對(duì)象的每個(gè)屬性對(duì)應(yīng)一個(gè)屬性值。具有條件屬性集和決策屬性集的信息系統(tǒng)稱為決策表，簡(jiǎn)記為IS=〈U，A〉或IS=〈U，C∪D〉。

定義2［1］在信息系統(tǒng)IS=〈U，A〉中，對(duì)于給定屬性集P?A，P在IS上的不可區(qū)分關(guān)系記為IND（P），定義如下：

IND（P）=｛（x，y）∈U×U|a∈P，f（x，a）=f（y，a）｝

對(duì)于，x∈U，令［x］=｛y∈U|（x，y）∈IND（P）｝，顯然，［x］稱為等價(jià)類；令U/P=｛［x］|x∈U｝，稱為U的一個(gè)劃分。

P在IS上的區(qū)分關(guān)系記為DIS（P），定義如下：

DIS（P）=｛（x，y）∈U×U|?a∈P，f（x，a）≠f（y，a）｝

對(duì)于，（x，y）∈DIS（P），（x，y）稱為P的區(qū)分對(duì)。本文將IND（P）和DIS（P）分別稱為不可區(qū)分集和區(qū)分集。

定義3［1］設(shè)U為一個(gè)論域，P為定義在U上的一個(gè)等價(jià)關(guān)系簇。如果每個(gè)關(guān)系R∈P在P中都是絕對(duì)必要的，則稱關(guān)系簇P是獨(dú)立的；否則，稱關(guān)系簇P是相互依賴的。

定義4［1］在信息系統(tǒng)IS=〈U，C∪D〉中，對(duì)于給定屬性集B?C，如果IND（B）=IND（C）且B是獨(dú)立的，則稱B是C的一個(gè)約簡(jiǎn)。B中所有必要關(guān)系的集合稱為B的核，記為core（B），則core（B）=∩red（B）。

定義5在決策表IS=〈U，C∪D〉中，假設(shè)U=｛x1，x2，…，xn｝是論域，C=｛a1，a2，…，am｝為條件屬性，D=｛d｝為決策屬性，令ai（xj）是樣本xj在屬性ai上的取值，定義矩陣M=（mij|i，j=1，2，…，n），其中：

mij表示區(qū)分矩陣中第i行第j列的元素，矩陣M稱為區(qū)分矩陣。

2 條件區(qū)分能力

本章主要介紹條件區(qū)分能力的相關(guān)定義、定理，并給出相關(guān)算法。

2.1 區(qū)分能力

在粗糙集理論中，知識(shí)被認(rèn)為是屬性的識(shí)別能力，同一等價(jià)類中的對(duì)象不能相互區(qū)分，而不同等價(jià)類中的對(duì)象可以相互區(qū)分。因此，給定屬性集的知識(shí)內(nèi)容可以量化為其在論域上的可區(qū)分對(duì)的總數(shù)，即屬性集在論域上的區(qū)分集大小。屬性的區(qū)分集越大，該屬性的區(qū)分能力越強(qiáng)，反之越弱。

定義6在信息系統(tǒng)IS=〈U，A〉中，對(duì)給定屬性集B?A，B的區(qū)分能力記為E（B），定義如下：

E(B)=|DIS(B)|

屬性約簡(jiǎn)要求保持原知識(shí)庫(kù)分類能力不變，這種分類能力在決策表中是指條件屬性集相較于決策屬性集的分類能力。因此，當(dāng)某個(gè)可區(qū)分對(duì)不屬于決策屬性集的區(qū)分集DIS（D）時(shí)，即使它屬于某個(gè)條件屬性a的區(qū)分集DIS（｛a｝）也是沒(méi)有意義的，即條件屬性的區(qū)分能力受制于決策屬性。因此，在約簡(jiǎn)過(guò)程中，需要利用在決策屬性區(qū)分集的基礎(chǔ)上條件屬性的區(qū)分集大小來(lái)衡量屬性的重要性。

定義7在信息系統(tǒng)IS=〈U，C∪D〉中，對(duì)于給定屬性集B?C，B在D上的條件區(qū)分集記為DIS（B|D），定義如下：

DIS（B|D）=DIS（B）∩DIS（D）

B在D上的條件區(qū)分能力記為E（B|D），定義如下：

E（B|D）=|DIS（B|D）|

定義8在信息系統(tǒng)IS=〈U，C∪D〉中，對(duì)給定屬性集B?C，B是C相較于D的一個(gè)約簡(jiǎn)的充要條件為：

1）E（B|D）=E（C|D）；

2）B′?B，E（B′|D）

定理1若Q?P，則DIS（Q）?DIS（P），DIS（Q|D）?DIS（P|D），E（Q）≤E（C），E（Q|D）≤E（C|D）。

證明 由定義2 易得。

定理2令red為C的一個(gè)約簡(jiǎn)，對(duì)于給定的屬性集red1，red2?red，如果red1?red2，則E（red1|D）

證明 因red1?red2，不妨設(shè)as?red1∧as∈red2，由定理1 可知，E（red1|D）≤E（red1∪｛as｝|D）≤E（red2|D）。假設(shè)E（red1|D）=E（red2|D），則E（red1|D）=E（red1∪｛as｝|D），結(jié)合定義8 可得，as?red，與條件as∈red2?red矛盾，故假設(shè)不成立，因此E（red1|D）

定理3在信息系統(tǒng)IS=〈U，A〉中，對(duì)于給定屬性集P，Q?A，令U/P=｛Xi|i=1，2，…，p｝，Xi/Q=｛Xij|j=1，2，…，qi｝，則有：

證明 由定義2 和定義7 可知，E（Q）-E（P|Q）=|DIS(Q)-DIS(P)∩DIS(Q)|=|{(x，y)∈U×U|?aq∈Q，ap∈P，f(x，aq)≠f(y，aq)∧f(x，ap)=f(y，ap)}|。因同一等價(jià)類間不可相互區(qū)分，不同等價(jià)類間可以互相區(qū)分，故對(duì)于Xi∈U/P，｛（x，y）∈Xi×Xi｝等價(jià)于｛（x，y）∈U×U|ap∈P，f（x，ap）=f（y，ap）｝，因此E（Q）-E（P|Q）=|{(x，y)∈Xi×Xi|?aq∈Q，f(x，aq)≠f(y，aq)}|。對(duì)于Xi∈U/P，Q在Xi上的區(qū)分集為Xi/Q中不同等價(jià)類間的對(duì)象組成的可區(qū)分對(duì)的集合，因此Q在Xi上的區(qū)分集大小為不同等價(jià)類大小乘積之和，即，因此

2.2 基于條件區(qū)分能力的屬性約簡(jiǎn)算法

傳統(tǒng)基于區(qū)分矩陣的方法利用吸收率逐一對(duì)比區(qū)分矩陣中的元素，直到區(qū)分矩陣元素全為空集時(shí)終止，算法比較耗時(shí)。本文依據(jù)定理3，通過(guò)劃分等價(jià)類計(jì)算屬性的條件區(qū)分能力，以條件區(qū)分能力衡量屬性重要性，從而實(shí)現(xiàn)約簡(jiǎn)，這樣大大減少了實(shí)例間相互比較的次數(shù)，提高了約簡(jiǎn)效率。依據(jù)定理2，在約簡(jiǎn)中并不需要計(jì)算E（C|D），由于E（red|D）是隨屬性子集red嚴(yán)格遞增，因此，當(dāng)E（red|D）不再增加時(shí)，算法終止即可。

據(jù)此，本文構(gòu)造了基于條件區(qū)分能力的約簡(jiǎn)算法。該算法描述如下。

在算法1 中，初始約簡(jiǎn)集red為空，每次選取條件區(qū)分能力最強(qiáng)的屬性加入到red中，并逐步減小論域，直到red的條件區(qū)分能力不再增加時(shí)算法結(jié)束，從而得到約簡(jiǎn)。由于屬性集的條件區(qū)分能力是依據(jù)定理3 通過(guò)劃分等價(jià)類計(jì)算的，因此，算法1 的總計(jì)算復(fù)雜度為。

3 局部條件區(qū)分能力

目前，國(guó)內(nèi)外學(xué)者們?cè)O(shè)計(jì)的屬性約簡(jiǎn)算法，一般都是基于貪心策略進(jìn)行屬性選取的，每次選取最重要的屬性加入到約簡(jiǎn)集red中，這就要計(jì)算每個(gè)屬性在整個(gè)論域中的重要性，這種屬性選取的要求太過(guò)嚴(yán)苛。實(shí)際上，就最終約簡(jiǎn)結(jié)果redend而言，并不是一定要嚴(yán)格按照屬性重要性順序加入到red中，而是滿足在選取屬性時(shí)，存在ai∈redend-red對(duì)任意aj∈C-redend，使得E（｛ai｝|D）≥E（｛aj｝|D）即可。退一步而言，即使上述條件不存在，也會(huì)得到C的另外一個(gè)約簡(jiǎn)。因此，本文在區(qū)分集DIS（D）上隨機(jī)抽取k個(gè)可區(qū)分對(duì)組成局部區(qū)分集DISk（D），利用屬性在DISk（D）上的條件區(qū)分能力進(jìn)行屬性選取。

定義9在信息系統(tǒng)IS=〈U，A〉中，A=C∪D，對(duì)于給定屬性集P?A，P在IS上的局部區(qū)分集記為DISk（P），定義如下：

DISk（P）=rand（DIS（P），k）

其中：rand（*，k）表示從*中隨機(jī)抽取k個(gè)元素；k為局部區(qū)分集大小。P的局部區(qū)分能力記為DISk（P），定義如下：

Ek(P)=|DISk(P)|

對(duì)于給定屬性集B?C，B的局部條件區(qū)分能力記為Ek（B|D），定義如下：

Ek(B|D)=|DIS(B)∩DISk(D)|

定理4伯努利大數(shù)定理［22］。設(shè)μ是n次獨(dú)立實(shí)驗(yàn)中事件A 發(fā)生的次數(shù)，且事件A 在每次實(shí)驗(yàn)中發(fā)生的概率為p，則對(duì)任意正數(shù)ε，有

定理4 表明，當(dāng)n足夠大時(shí)，事件A 出現(xiàn)的頻率幾乎接近于其發(fā)生的概率，即頻率的穩(wěn)定性。該定理為抽樣調(diào)查中，用樣本成數(shù)估計(jì)總體成數(shù)的理論依據(jù)。

定理5令p1=E（B|D）/E（D），p2=Ek（B|D）/Ek（D），則當(dāng)k→∞時(shí)，p1=p2。

證明 由定理4 易得。

算法1 以條件區(qū)分能力衡量屬性重要度，從而實(shí)現(xiàn)約簡(jiǎn)。然而當(dāng)數(shù)據(jù)規(guī)模較大或條件屬性較多時(shí)，對(duì)屬性重要度的計(jì)算耗時(shí)太長(zhǎng)。文獻(xiàn)［19］中定義了相對(duì)區(qū)分度，利用相對(duì)區(qū)分度重新設(shè)計(jì)了屬性重要性的衡量標(biāo)準(zhǔn)，也同樣存在屬性重要度計(jì)算耗時(shí)太長(zhǎng)的問(wèn)題。

本文依據(jù)定理5，通過(guò)構(gòu)建局部區(qū)分集計(jì)算屬性的局部條件區(qū)分能力，選擇局部條件區(qū)分能力最強(qiáng)的屬性加入到約簡(jiǎn)集中，將每個(gè)屬性重要度的計(jì)算復(fù)雜度降低為O（k），有效地提高了約簡(jiǎn)效率。同時(shí)，當(dāng)區(qū)分集（DIS（D）-DIS（red|D））的大小低于預(yù)設(shè)局部區(qū)分集大小k時(shí)，將區(qū)分集（DIS（D）-DIS（red|D））作為局部區(qū)分集計(jì)算屬性的局部條件區(qū)分能力，從而保證了約簡(jiǎn)的正確性。依據(jù)定理2，當(dāng)E（red|D）不再增加時(shí)，算法終止即可。

據(jù)此，本文構(gòu)造了基于局部條件區(qū)分能力的約簡(jiǎn)算法。該算法描述如下。

由定義2 和定理3 可知，DIS（D）-DIS（red|D）可以通過(guò)劃分等價(jià)類（U′/red）/D計(jì)算，計(jì)算復(fù)雜度為。在選取局部區(qū)分集時(shí)，每一次對(duì)可區(qū)分對(duì)的抽取需要先從U′/red中加權(quán)抽取一個(gè)等價(jià)類Xred，再?gòu)腦red/D中加權(quán)抽取兩個(gè)等價(jià)類X1、X2，最后分別從X1、X2中隨機(jī)抽取一個(gè)實(shí)例，組成一個(gè)可區(qū)分對(duì)加入到局部區(qū)分集中，所以步驟2）的總計(jì)算復(fù)雜度為。在選擇屬性過(guò)程中，由于屬性重要度的計(jì)算依據(jù)是基于局部區(qū)分集計(jì)算的局部條件區(qū)分能力，所以步驟3）～4）的總計(jì)算復(fù)雜度為。步驟 5）計(jì)算復(fù)雜度為，低于步驟2）。綜上，算法2的總計(jì)算復(fù)雜度為。若將局部區(qū)分集大小k視為常數(shù)，則算法2 的總計(jì)算復(fù)雜度為。不難發(fā)現(xiàn)，利用局部條件區(qū)分能力可以有效地降低屬性選取的計(jì)算時(shí)間，提高約簡(jiǎn)效率。

事實(shí)上，對(duì)于一個(gè)確定的信息系統(tǒng)，每個(gè)屬性的區(qū)分能力和條件區(qū)分能力都是固定不變的，而其局部條件區(qū)分能力可能會(huì)因選取屬性的不穩(wěn)定在約簡(jiǎn)過(guò)程中發(fā)生相對(duì)變化。上文中提到只要滿足在選取屬性時(shí)，存在ai∈redend-red對(duì)任意aj∈C-redend，使得E（｛ai｝|D）≥E（｛aj｝|D）即可，那么局部條件區(qū)分能力就不會(huì)發(fā)生相對(duì)變化；否則會(huì)得到C的另外一個(gè)約簡(jiǎn)。這種不穩(wěn)定的關(guān)鍵在于局部區(qū)分集大小k的選取，因?yàn)閗值決定了局部樣本能否體現(xiàn)出屬性間條件區(qū)分能力的真實(shí)大小關(guān)系。在固定k值條件下，屬性間的條件區(qū)分能力相差越大，局部樣本體現(xiàn)屬性間條件區(qū)分能力的真實(shí)大小關(guān)系的效果越好，反之越差；對(duì)于同一個(gè)信息系統(tǒng)，k值越大，局部樣本體現(xiàn)屬性間條件區(qū)分能力的真實(shí)大小關(guān)系的效果越好，反之越差。不難發(fā)現(xiàn)，屬性間條件區(qū)分能力的相對(duì)關(guān)系與信息系統(tǒng)的大小無(wú)關(guān)，即k與U無(wú)關(guān)。此外算法2 的約簡(jiǎn)過(guò)程中，只需要額外存儲(chǔ)局部區(qū)分集即可，空間復(fù)雜度為O（|U|）。因此，算法2 更適用于海量數(shù)據(jù)屬性約簡(jiǎn)。

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

為了驗(yàn)證本文算法的有效性和實(shí)用性，本文選取UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)（http：//www.ics.uci.edu）中的5 個(gè)數(shù)據(jù)集：Tictac-toe、Kr-vs-kp、Mushroom、Letter 和Connect 進(jìn)行實(shí)驗(yàn)。采用基于區(qū)分度的高效前向?qū)傩约s簡(jiǎn)算法（efficient Forward Attribute Reduction algorithm from Discernibility View，F(xiàn)ARDV）［19］、基于k近鄰屬性重要度和相關(guān)系數(shù)的屬性約簡(jiǎn)算法（attribute reduction algorithm based onk-Nearest Neighbor attribute importance and Correlation Coefficient，K2NCRS）［23］、基于正區(qū)域排序升序決策表的快速正區(qū)域約簡(jiǎn)算法（Fast Positive Region reduction Algorithm based on positive region sort ascending decision table，F(xiàn)PRA）［7］與本文算法1、2 進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)運(yùn)行的硬件環(huán)境為Intel i7-8750H 2.20 GHz CPU和8 GB 內(nèi)存。本實(shí)驗(yàn)使用Python3.6.6 實(shí)現(xiàn)，采用PyCharm 2020 作為實(shí)驗(yàn)平臺(tái)進(jìn)行實(shí)驗(yàn)。

表1 數(shù)據(jù)集描述Tab.1 Description of datasets

本文共設(shè)計(jì)4 個(gè)實(shí)驗(yàn)如下：

實(shí)驗(yàn)1 利用FAR-DV、算法1、算法2（k=1 000）分別對(duì)每個(gè)數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)，比較三種算法的約簡(jiǎn)結(jié)果和分類精度（使用支持向量機(jī)（Support Vector Machines，SVM）和分類回歸樹(shù)（Classification And Regression Tree，CART）兩種分類器）。

實(shí)驗(yàn)2 采用遞增序列k值，記錄不同k值下算法2 約簡(jiǎn)結(jié)果的分類精度，與FAR-DV、算法1 約簡(jiǎn)結(jié)果的分類精度進(jìn)行對(duì)比。

實(shí)驗(yàn)3 采用遞增序列k值，對(duì)比FAR-DV、算法1 和不同k值下算法2 的屬性選取順序。

實(shí)驗(yàn)4 利用FAR-DV、K2NCRS、FPRA、算法1、算法2（k=1 000）分別對(duì)每個(gè)數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)，比較五種算法的約簡(jiǎn)時(shí)間。

實(shí)驗(yàn)1 的實(shí)驗(yàn)結(jié)果如表2～3 所示。從表2～3 可看出：在約簡(jiǎn)率上，三種算法完全一致；在約簡(jiǎn)結(jié)果的分類精度上，算法2 略優(yōu)于算法1 和FAR-DV。這表明條件區(qū)分能力進(jìn)行屬性約簡(jiǎn)的正確性，同時(shí)也驗(yàn)證了利用局部條件區(qū)分能力進(jìn)行屬性約簡(jiǎn)的有效性。

表2 三種算法的約簡(jiǎn)結(jié)果Tab.2 Reduction results of three algorithms

表3 三種算法約簡(jiǎn)結(jié)果的分類精度Tab.3 Classification accuracies of reduction results of three algorithms

實(shí)驗(yàn)2 的實(shí)驗(yàn)結(jié)果如圖1～2 所示。實(shí)驗(yàn)2 在SVM、CART兩種分類器上比較了三種算法約簡(jiǎn)結(jié)果的分類精度。在圖1～2 中，F(xiàn)AR-DV 與算法1 約簡(jiǎn)結(jié)果一致，故使用同一條折線表示。圖1～2 的結(jié)果表明：當(dāng)局部區(qū)分集大小k超過(guò)某個(gè)特定值時(shí)，算法2 約簡(jiǎn)結(jié)果的分類精度逐漸趨向于FAR-DV和算法1 約簡(jiǎn)結(jié)果的分類精度，即隨著局部區(qū)分集大小k的增大，局部條件區(qū)分能力逐漸趨向于條件區(qū)分能力，與本文定理5 相符。

圖1 SVM上三種算法的約簡(jiǎn)結(jié)果分類精度的比較Fig.1 Comparison of classification accuracy of reduction results of three algorithms on SVM

實(shí)驗(yàn)3 中，由于不同的數(shù)據(jù)集的數(shù)據(jù)規(guī)模、屬性間區(qū)分能力不同，因此不同的數(shù)據(jù)集的約簡(jiǎn)結(jié)果趨于穩(wěn)定所對(duì)應(yīng)的臨界k值不同。為了體現(xiàn)算法2 的約簡(jiǎn)結(jié)果及屬性選擇順序隨k值增加而變化的過(guò)程，對(duì)不同數(shù)據(jù)集采用了不同的k值區(qū)間和步長(zhǎng)。其中數(shù)據(jù)集Mushroom 采用了k值區(qū)間［10，170］，步長(zhǎng)為20；其他數(shù)據(jù)集采用了k=100，以及k值區(qū)間［500，4 000］，步長(zhǎng)為500。實(shí)驗(yàn)3 的實(shí)驗(yàn)結(jié)果如表4～5 所示。對(duì)比表2 與表4～5 可得：隨著局部區(qū)分集大小k的增大，算法2 的約簡(jiǎn)結(jié)果、約簡(jiǎn)率、屬性選擇的順序都逐漸趨向于算法1。這進(jìn)一步驗(yàn)證了利用局部條件區(qū)分能力進(jìn)行屬性約簡(jiǎn)的有效性。

表4 算法2在Tic-tac-toe、Letter和Mushroom數(shù)據(jù)集上的約簡(jiǎn)結(jié)果Tab.4 Reduction results of algorithm 2 on Tic-tac-toe，Letter and Mushroom datasets

表5 算法2在Kr-vs-kp和Connect數(shù)據(jù)集上的約簡(jiǎn)結(jié)果Tab.5 Reduction results of algorithm 2 on Kr-vs-kp and Connect datasets

實(shí)驗(yàn)4 的實(shí)驗(yàn)結(jié)果如表6 所示。從表6 可看出，在約簡(jiǎn)效率上，算法2 明顯優(yōu)于其他四種算法：當(dāng)數(shù)據(jù)規(guī)模較大或條件屬性較多時(shí)，F(xiàn)AR-DV、K2NCRS、FPRA 和算法1 在約簡(jiǎn)效率上有了明顯的局限性，而算法2 依然能夠快速地得到有效的約簡(jiǎn)；相較于其他四種算法，算法2 在Kr-vs-kp、Mushroom、Letter 上的約簡(jiǎn)效率平均提高了10 倍以上，在Connect 上的約簡(jiǎn)效率最低提高了約20 倍。本次實(shí)驗(yàn)驗(yàn)證了算法2 適用于海量數(shù)據(jù)屬性約簡(jiǎn)。

表6 五種算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比 單位：sTab.6 Comparison of running time of five algorithms on different datasets unit：s

圖2 CART上三種算法的約簡(jiǎn)結(jié)果分類精度的比較Fig.2 Comparison of classification accuracy of reduction results of three algorithms on CART

5 結(jié)語(yǔ)

本文針對(duì)目前約簡(jiǎn)算法時(shí)空復(fù)雜度高、無(wú)法高效處理海量數(shù)據(jù)的問(wèn)題，構(gòu)造了條件區(qū)分能力進(jìn)行屬性約簡(jiǎn)，提出了基于條件區(qū)分能力的屬性約簡(jiǎn)算法，并利用大數(shù)定律將條件區(qū)分能力擴(kuò)展為局部條件區(qū)分能力，有效地減少了屬性重要性的計(jì)算時(shí)間，提出了基于局部條件區(qū)分能力的屬性約簡(jiǎn)算法，將計(jì)算復(fù)雜度降為。利用局部條件區(qū)分能力進(jìn)行屬性選擇，可以極大限度地降低約簡(jiǎn)過(guò)程中計(jì)算時(shí)間和空間上的耗費(fèi)，非常適用于海量數(shù)據(jù)的屬性約簡(jiǎn)。但在屬性約簡(jiǎn)過(guò)程中，局部條件區(qū)分能力的不穩(wěn)定問(wèn)題還需要進(jìn)一步研究。