陳媛，茍光磊，盧玲

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

基于一致性準(zhǔn)則的屬性約簡(jiǎn)改進(jìn)算法

陳媛，茍光磊，盧玲

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

針對(duì)基于粗糙集的連續(xù)值屬性約簡(jiǎn)存在速度較慢的問(wèn)題，提出一種改進(jìn)的一致性準(zhǔn)則的屬性約簡(jiǎn)算法。從相對(duì)核的角度出發(fā)，將一致性準(zhǔn)則的概念和屬性的重要度的概念結(jié)合運(yùn)用，優(yōu)化了原算法的結(jié)構(gòu)，加快了屬性約簡(jiǎn)的速度。實(shí)驗(yàn)結(jié)果表明該算法有效可行。

粗糙集;一致性準(zhǔn)則;屬性約簡(jiǎn);相對(duì)核

粗糙集理論由波蘭數(shù)學(xué)家Pawlak.Z在20世紀(jì)80年代初提出，用于處理不精確、不完整與不相容數(shù)據(jù)的數(shù)學(xué)理論［1］，在數(shù)據(jù)的決策與分析、機(jī)器學(xué)習(xí)與模式識(shí)別等多個(gè)領(lǐng)域得到了廣泛的應(yīng)用［2］。針對(duì)連續(xù)值屬性的約簡(jiǎn)，已有多種擴(kuò)展粗糙集模型被用于研究。屬性約簡(jiǎn)是粗糙集理論的核心內(nèi)容之一，其主要思想是在保持某種能力不變的前提下，刪除冗余或不重要的屬性，從而減少搜索空間，提高效率。在處理連續(xù)值屬性的約簡(jiǎn)時(shí)，一是將連續(xù)值屬性離散化，用離散值屬性約簡(jiǎn)算法處理連續(xù)值屬性約簡(jiǎn)，但該方法只適合處理少量的連續(xù)值屬性的約簡(jiǎn);二是直接使用拓展粗糙集模型進(jìn)行約簡(jiǎn)。如胡清華教授等提出一種基于鄰域的屬性約簡(jiǎn)算法［3］，但該算法需求解各對(duì)象的鄰域，計(jì)算代價(jià)過(guò)高，且鄰域參數(shù)的選取缺乏理論上的合理解釋［4］。南京師范大學(xué)的楊明教授提出了一種基于一致性準(zhǔn)則的屬性約簡(jiǎn)算法ARBCC(attribute reduction based on consistency criterion)，該算法無(wú)須計(jì)算各對(duì)象的鄰域，理論分析和實(shí)驗(yàn)結(jié)果證明該算法是有效可行的。

文獻(xiàn)［4］提出一種基于一致性準(zhǔn)則的屬性約簡(jiǎn)算法，可針對(duì)離散值或連續(xù)值屬性進(jìn)行有效的約簡(jiǎn)。但當(dāng)處理的數(shù)據(jù)集中含有眾多屬性時(shí)，數(shù)據(jù)的分類速度不是很理想。本文針對(duì)文獻(xiàn)［4］的算法，提出一種改進(jìn)的一致性準(zhǔn)則的屬性約簡(jiǎn)算法。該算法以決策表的相對(duì)核為起點(diǎn)，在決策表中添加屬性時(shí)，引起決策表一致性量的變化，用變化的大小來(lái)反映該屬性的重要程度，即R=R∪{a}。該算法將一致性準(zhǔn)則的概念和屬性重要度的概念結(jié)合運(yùn)用，優(yōu)化了算法的結(jié)構(gòu)，加快了約簡(jiǎn)的速度，并通過(guò)實(shí)例分析驗(yàn)證了改進(jìn)算法的有效性。

1 粗糙集理論的基本概念

設(shè)DT=(U，AV，f)為一個(gè)信息系統(tǒng)。其中:U是非空對(duì)象集合，稱為論域;A=C∪D是屬性集合，C和D分別為條件屬性集和決策屬性集。具有條件屬性集和決策屬性集的信息系統(tǒng)稱為決策表，設(shè)P?A是U上的一個(gè)等價(jià)關(guān)系，即

其中:x，y為U中的對(duì)象;V=∪Va，Va為a屬性的

a∈A值域集;信息函數(shù)f:U×A→V指定U中每個(gè)對(duì)象的屬性值［5－6］。

定義1設(shè)P?C，P為C的D約簡(jiǎn)，當(dāng)且僅當(dāng)P是C的D獨(dú)立子集族，且posP(D)=posC(D)，則P是D的相對(duì)約簡(jiǎn)。P中所有D的等價(jià)關(guān)系構(gòu)成的集合稱為P的D核，即相對(duì)核。

定義2［7］設(shè)U為一個(gè)論域，P為定義在U上的一個(gè)等價(jià)關(guān)系族，P中所有必要關(guān)系組成的集合稱為族集P的核，記作Core(P)。

定理1core(P)=∩red(P)，其中red(P)表示屬性集P的所有約簡(jiǎn)。

證明反證法。設(shè)A，B，C為屬性集P的所有約簡(jiǎn)，若core(P)≠∩red(P)，必有A∩B∩C= φ，這與A∩B∩C≠φ矛盾，故假設(shè)不成立。

從定理可知，核概念的使用有2個(gè)方面:

1)可以作為所有約簡(jiǎn)的計(jì)算基礎(chǔ)，由核的定義可知，核包含在所有的約簡(jiǎn)之中。

2)核可以被解釋成屬性最重要部分的集合，在進(jìn)行屬性約簡(jiǎn)時(shí)是不能去掉的。

2 改進(jìn)的一致性準(zhǔn)則的屬性約簡(jiǎn)算法

本文首先對(duì)一致性和不一致性的概念及其性質(zhì)進(jìn)行介紹。

定義3［8］設(shè)DT為一決策表，P?C，對(duì)2個(gè)對(duì)象x，y∈U，f(x，D)≠f(y，D)，若有dp(x，y)＞ε (其中ε≥0)，則稱x，y在p上是ε－一致的;否則，x，y在p上是ε－不一致的。其中dp(x，y)表示2個(gè)對(duì)象x和y之間的不相似度或距離，即

根據(jù)定義4，可以將任意兩個(gè)對(duì)象的一致性概念推廣到一組對(duì)象在某個(gè)屬性集上的一致性，即定義5。

為保證快速有效地得到屬性約簡(jiǎn)，需了解在屬性集擴(kuò)大的情況下，一致性對(duì)象的變化情況。

定理2給定ε(ε≥0)，對(duì)任意的A?B，B?C，①設(shè)dA(x，y)＞ε，則有dB(x，y)＞ε成立;②若x(x∈U)是關(guān)于A的ε－一致對(duì)象，則x(x∈U)是關(guān)于B的ε－一致對(duì)象。

證明

1)反證法:假設(shè)dB(x，y)≤ε，因A?B，則存在dA(x，y)≤ε，這與dA(x，y)≤ε矛盾，故假設(shè)不成立。

2)反證法:假設(shè)x(x∈U)是關(guān)于B的ε－不一致對(duì)象，對(duì)?y∈U，dB(x，y)≤ε，則存在f(x，D)= f(y，D);由于A?B，則x，y在屬性A上必然存在f(x，D)=F(y，D);又有dA(x，y)＞ε，則x是關(guān)于A的ε－不一致對(duì)象，這與x(x∈U)是關(guān)于A的ε－一致對(duì)象矛盾，故假設(shè)不成立。

由定理2可知:改進(jìn)的一致性準(zhǔn)則的屬性約簡(jiǎn)算法具有單調(diào)性。

根據(jù)定理2，若給定的不相似度滿足單調(diào)性，則通過(guò)逐步擴(kuò)展重要屬性即可得到一個(gè)有效的屬性約簡(jiǎn)。本文提出了一種改進(jìn)的屬性約簡(jiǎn)算法，以決策表的相對(duì)核為起點(diǎn)，逐步添加增量最大的屬性，最后得出屬性約簡(jiǎn)。

定義4給定ε(ε≥0)，A?C，定義差別矩陣MA={MA(x，y)}為

從定義4可以看出:對(duì)任意的兩個(gè)元素x，y∈U，dp(x，y)≤ε，說(shuō)明對(duì)象x，y在p上不一致。在條件屬性P下，決策表對(duì)應(yīng)的差別矩陣中含有矩陣分量值為1的元素越多，說(shuō)明屬性越重要，否則說(shuō)明該屬性越不重要。

本文提出的改進(jìn)一致性準(zhǔn)則約簡(jiǎn)算法逐次選擇最重要的屬性添加到相對(duì)核中，直到滿足終止條件。IARBCC(improved attribute reduction based on consistency criterion)算法具體描述如下:

輸入1)決策表

2)一致性參數(shù)

輸出該決策表的一個(gè)屬性約簡(jiǎn)R

主要步驟

1)求核core:

①初始化核core=?;

②對(duì)?a∈C，x，y∈C－a，有f(x，D)≠f(y，D)且dC－a(x，y)≤ε，則說(shuō)明為核a;

2)對(duì)全部數(shù)據(jù)的全部屬性求其一致性量;

3)令R=core，計(jì)算R的一致性量;

4)對(duì)?a∈C－R，計(jì)算R+a的一致性量:

①初始化區(qū)別矩陣中數(shù)值為 1;

②計(jì)算MR+a，即計(jì)算所有對(duì)象關(guān)于當(dāng)前屬性集的不一致性(0的個(gè)數(shù));

③計(jì)算矩陣中1的個(gè)數(shù);

④判斷該屬性是否為C－R中最后一個(gè)屬性，如果是，轉(zhuǎn)5，否則，轉(zhuǎn) 4;

5)找出一個(gè)數(shù)最多的屬性，即該屬性為最重要的屬性，有R=R+a;

6)計(jì)算R的一致性量，當(dāng)R的一致性量等于全部數(shù)據(jù)全部屬性的一致性量時(shí)，算法終止，否則，轉(zhuǎn)4)。

3 實(shí)驗(yàn)分析

3.1 適合約簡(jiǎn)的屬性集

本文的實(shí)驗(yàn)采用文獻(xiàn)［4］中的部分?jǐn)?shù)據(jù)集，其描述如表1所示。

表1 數(shù)據(jù)集的描述

其中:Iris的屬性為離散值屬性，即ε=0。對(duì)Iris數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)，得到屬性約簡(jiǎn)R={1，3，4}。由此可知:必須有3個(gè)條件屬性才能將Iris數(shù)據(jù)集區(qū)分開(kāi)。因此，Iris數(shù)據(jù)集不具有屬性約簡(jiǎn)的價(jià)值。所以，本章采用剩余4個(gè)數(shù)據(jù)集來(lái)進(jìn)行實(shí)驗(yàn)。

3.2 ε的取值

為了解一致性參數(shù)ε與屬性約簡(jiǎn)結(jié)果之間的關(guān)系，本文對(duì)Wine和Wave數(shù)據(jù)集進(jìn)行了處理和分析，所得結(jié)果如表2、3所示。

從表2可見(jiàn):當(dāng)ε取0.15或更小的值時(shí)，屬性可以約簡(jiǎn)，但由于沒(méi)有產(chǎn)生相對(duì)核，所以ε在該范圍內(nèi)取值對(duì)本算法而言是無(wú)效的;當(dāng)ε在［0.175，0.181 8］內(nèi)取值，屬性可以約簡(jiǎn)，同時(shí)產(chǎn)生了相對(duì)核，ε在該范圍內(nèi)取值對(duì)本算法是有效的;隨著ε取值的不斷增大，屬性無(wú)法約簡(jiǎn)。同樣，從表3可以得出:當(dāng)ε在(0.095，0.097］內(nèi)取值時(shí)，對(duì)本算法是有效的。由此說(shuō)明本文提出的算法在某些情況下是有效的。

表2 Wine數(shù)據(jù)集中ε的取值與屬性約簡(jiǎn)和相對(duì)核之間的關(guān)系

表3 Wave數(shù)據(jù)集中ε的取值與屬性約簡(jiǎn)和相對(duì)核之間的關(guān)系

3.3 實(shí)驗(yàn)結(jié)果

選取適合的數(shù)據(jù)集以及相對(duì)應(yīng)的一致性參數(shù)ε，對(duì)ARBCC算法和IARBCC算法進(jìn)行決策表的運(yùn)行效率和分類精度在內(nèi)的算法的有效性分析。

首先，比較ARBCC算法和IARBCC算法在一致性參數(shù)ε不變、數(shù)據(jù)集變化情況下的執(zhí)行效率。本文從Wave中隨機(jī)抽取了500到3 000的一系列數(shù)據(jù)，對(duì)一致性參數(shù)ε=0.095和ε=0.097，分別比較ARBCC算法和IARBCC算法的執(zhí)行效率。所得結(jié)果如圖1所示。

圖1 算法ARBCC和IARBCC的運(yùn)行時(shí)間

圖1的實(shí)驗(yàn)結(jié)果表明:IARBCC算法比ARBCC算法擁有更快的運(yùn)行速度。

針對(duì)Wine數(shù)據(jù)集，在一致性參數(shù)ε變化的情況下，ARBCC算法和IARBCC算法的分類精度和執(zhí)行時(shí)間情況如圖2、3所示。

觀察圖2、3的實(shí)驗(yàn)結(jié)果可知:無(wú)論是對(duì)小樣本數(shù)據(jù)集還是大樣本數(shù)據(jù)集，IARBCC算法都比ARBCC算法擁有更高的屬性約簡(jiǎn)的效率。

圖2 算法ARBCC和IARBCC的分類精度隨一致性參數(shù)ε的變化

圖3 算法ARBCC和IARBCC的執(zhí)行時(shí)間隨一致性參數(shù)ε的變化

最后，針對(duì)Ionosphere和Pima數(shù)據(jù)集，分析ARBCC算法和IARBCC算法的執(zhí)行時(shí)間。實(shí)驗(yàn)結(jié)果如表4所示。

表4 運(yùn)行速度的對(duì)比

從表4的實(shí)驗(yàn)結(jié)果可見(jiàn):與ARBCC算法相比，IARBCC算法加快了運(yùn)行的速度。

綜合分析上述的實(shí)驗(yàn)結(jié)果，在分類精度保持不變或較高的情況下，與ARBCC算法相比，IARBCC算法是有效可行的。它有效地改進(jìn)了屬性約簡(jiǎn)的效率，提高了運(yùn)行的速度。在對(duì)屬性眾多的數(shù)據(jù)集進(jìn)行約簡(jiǎn)時(shí)，這種改進(jìn)是十分必要的。

4 結(jié)束語(yǔ)

目前，粗糙集被廣泛應(yīng)用于各個(gè)領(lǐng)域，屬性約簡(jiǎn)成為信息科學(xué)研究的熱點(diǎn)之一。面對(duì)復(fù)雜的數(shù)據(jù)，如何高效地進(jìn)行連續(xù)值屬性約簡(jiǎn)已成為當(dāng)前粗糙集研究的熱點(diǎn)。本文提出了一種改進(jìn)的一致性準(zhǔn)則的屬性約簡(jiǎn)算法，該算法以ARBCC算法為BaseLise。實(shí)驗(yàn)分析結(jié)果表明:本文方法取得了比BaseLise算法更快的運(yùn)行速度，證明了該方法的有效性。

［1］Pawlak Z.Rough Sets［J］.International Journal of Information and Computer Science，1982，11(5):341－365.

［2］Pawlak Z.Rough Sets and Intelligent Data Analysis［J］.Information Science，2002，147(1－4):1－12.

［3］胡清華，于達(dá)仁，謝宗霞.基于鄰域?；痛植诒平臄?shù)值屬性約簡(jiǎn)［J］.軟件學(xué)報(bào)，2008，19(3):640－649.

［4］楊明.一種基于一致性準(zhǔn)則的屬性約簡(jiǎn)算法［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33(2):231－238.

［5］張文修，仇國(guó)芳.吳偉志.粗糙集屬性約簡(jiǎn)的一般理論［J］.信息科學(xué)，2005，35(12):1304－1313.

［6］宋佳娟，曲朝陽(yáng)，李翔坤.基于信息熵的粗糙集屬性約簡(jiǎn)算法研究［J］.軟件時(shí)空，2010，26(6－3):212－214.

［7］吳尚智，茍平章.粗糙集和信息熵的屬性約簡(jiǎn)算法及其應(yīng)用［J］.計(jì)算機(jī)工程，2011，37(7):56－59.

［8］陳堃，李心科.基于一致性度量的屬性約簡(jiǎn)的研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2008，18(10):64－67.

(責(zé)任編輯 楊黎麗)

Improved Algorithm for Attribute Reduction based on Consistency Criterion

CHEN Yuan，GOU Guang－lei，LU Ling
(School of Computer Science and Engineering，
Chongqing University of Technology，Chongqing 400054，China)

To solve the low efficiency of reduction of continuous－valued attributes based on rough sets，an improved attribute reduction algorithm based on consistency criterion is proposed.From the view of relative core，the concept of consistency criterion and important degree of attributes is used to optimize the structure of the original algorithm and improve the efficiency.The experiment results show that this algorithm is feasible and effective.

rough set;consistency criterion;attribute reduction;relative core

TP18

A

1674－8425(2014)05－0079－05

10.3969/j.issn.1674－8425(z).2014.05.016

2014－01－20

陳媛(1966—)，女，重慶人，教授，主要從事智能信息處理研究。

陳媛，茍光磊，盧玲.基于一致性準(zhǔn)則的屬性約簡(jiǎn)改進(jìn)算法［J］.重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版，2014(5): 79－83.

format:CHEN Yuan，GOU Guang－lei，LU Ling.Improved Algorithm for Attribute Reduction based on Consistency Criterion［J］.Journal of Chongqing University of Technology:Natural Science，2014(5):79－83.