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

陳媛，茍光磊，盧玲

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

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

陳媛，茍光磊，盧玲

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

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

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

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

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

1 粗糙集理論的基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證明

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

2)反證法:假設(shè)x(x∈U)是關(guān)于B的ε－不一致對象，對?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的ε－不一致對象，這與x(x∈U)是關(guān)于A的ε－一致對象矛盾，故假設(shè)不成立。

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

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

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

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

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

輸入1)決策表

2)一致性參數(shù)

輸出該決策表的一個屬性約簡R

主要步驟

1)求核core:

①初始化核core=?;

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

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

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

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

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

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

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

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

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

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

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

3.1 適合約簡的屬性集

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

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

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

3.2 ε的取值

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

目前，粗糙集被廣泛應(yīng)用于各個領(lǐng)域，屬性約簡成為信息科學(xué)研究的熱點(diǎn)之一。面對復(fù)雜的數(shù)據(jù)，如何高效地進(jìn)行連續(xù)值屬性約簡已成為當(dāng)前粗糙集研究的熱點(diǎn)。本文提出了一種改進(jìn)的一致性準(zhǔ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ù)值屬性約簡［J］.軟件學(xué)報(bào)，2008，19(3):640－649.

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

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

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

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

［8］陳堃，李心科.基于一致性度量的屬性約簡的研究［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)則的屬性約簡改進(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.