基于对象与属性维度的属性约简算法加速器

1、an accelerator for attribute reduction based on perspectiveof objects and attributes#liang jiye1, mi junrong2, wei wei1, wang feng1*510152025303540(1. school of computer and information technology, shanxi university, taiyuan 030006;2. school of management, shanxi university, taiyuan 030006)abstract:

2、 feature selection is an active area of research in pattern recognition, machine learning andartificial intelligence, which greatly improve the performance of forecasting or classification. in roughset theory, attribute reduction, as a special form of feature selection, aims to retain the discernabi

3、lity ofthe original attribute set. to solve this problem, many heuristic attribute reduction algorithms havebeen proposed in the literature. however, these methods are computationally time-consuming for largescale datasets. recently, an accelerator was introduced by computing reducts on gradually re

4、ducingthe size of the universe. although the accelerator can considerably shorten the computational time, itremains a challenging issue. to further enhance the efficiency of these algorithms, we develop a newaccelerator for attribute reduction, which simultaneously reduces the size of the universe a

5、nd thenumber of attributes at each iteration of the process of reduction. based on the new accelerator, severalrepresentative heuristic attribute reduction algorithms are accelerated. experiments show that theseaccelerating algorithms can significantly reduce computational time while maintaining the

6、ir results thesame as before.keywords: feature selection; accelerating algorithm; attribute reduction; rough set0 introductionfeature selection is a preprocessing step in many applications including pattern recognition,machine learning, and data mining. attribute reduction is regarded as a special f

7、orm of featureselection in rough set theory and aims to retain the discriminatory power of the original attributeset 1. in databases of practical applications (image processing, bioinformatics, astronomy,finance, etc.), the number of objects is very large and the dimension (the number of attributes)

8、 isvery high as well 2, 3. it is well known that attributes irrelevant to recognition tasks maydeteriorate the performance of learning algorithms 4. to address this issue, irrelevant attributes,as pointed out in 4, can be omitted, which will not severely affect the resulting classification(recogniti

9、on) accuracy. therefore, the omission of some irrelevant attributes would be desirablerelative to the costs involved 5.according to how to combine the feature subset search with the construction of theclassification model, feature selection techniques can be organized into three categories: wrappers

10、trategy 6, filter strategy 3, and embedded strategy 7. this paper focuses on the filter strategyin order to pursue both computational efficiency and solution quality regardless of a classificationscheme. in filter methods, some common feature selection criteria are introduced as stoppingconditions,

11、which include information gain 8, consistency 9, and dependency 10. thesecriteria can be divided into two main categories: distance-based and consistency-based 4. forconsistency-based feature selection, attribute reduction in rough set theory offers a systematictheoretic framework, which does not at

12、tempt to maximize the class separability but rather to retainthe discernible ability of original attribute sets for the objects from the universe 11, 12.foundations: this work was supported by the foundation of doctoral program research of the ministry ofeducation of china (20101401110002), the nati

13、onal natural science foundation of china (nos. 71031006,70971080, 60903110), and the natural science foundation of shanxi province (nos. 2009021017-1,2010021017-3).brief author introduction:liang jiye,（1962-）, male, professor, main research interesting is data mining andknowledge discovery.correspon

14、dance author: wei wei,（1980-）, male, lecturer, main research interesting is data mining and roughset. e-mail: weiwei-1-in recent years, many methods have been proposed and examined for finding reducts.skowron 13 proposed an attribute reduction algorithm using a discernibility matrix, which can455055

15、606570758085find all reducts. kryszkiewicz and lasek 14 proposed an approach to the discovery of minimalsets of attributes functionally determining a decision attribute. hu and cercone 15 proposed aheuristic attribute reduction method, called positive-region reduction, which remains the positiveregi

16、on of target decision unchanged. furthermore, many researchers introduced variousinformation entropies (shannon's entropy, complement entropy, combination entropy, etc.) tomeasure the uncertainty of an information table, and constructed the corresponding attributereduction algorithms 16,17,18,19

17、.these attribute reduction algorithms mentioned above can be divided into two types: findingall reducts (or an optimal reduct) and finding one reduct 20. however, it has been proved to bean np-hard problem to find all reducts 21. by contrast, heuristic algorithms (finding one reduct)can efficiently

18、lessen the computational burden of attribute reduction. in this paper, we efforts tofurther improve the efficiency of heuristic algorithms. for convenience of our further development,we classify these attribute reduction methods in terms of heuristics into four categories: positiveregion reduction 2

19、, 15, shannon's entropy reduction 21, complement entropy reduction 17, 18and combination entropy reduction 19. each of these heuristic methods can extract a singlereduct from a given decision table and preserves the particular property of the decision table.although these heuristic methods are m

20、uch faster, attribute reduction still remains acomputationally difficult problem when data sets are large. to overcome this difficulty, qian andliang 22 proposed an accelerator for attribute reduction based on positive approximation. theheuristic methods based on the accelerator can significantly de

21、crease the time consuming andobtain the same attribute reduct as their original versions. in 23, this idea of accelerator wasextended to incomplete data and hybrid data, and these corresponding accelerators cansignificantly improved the performance of attribute reduction algorithms. however, by mean

22、s ofthe accelerator, only the insignificant objects are removed from datasets when each iteration ofcomputing reducts. it has been observed that the number of attributes in datasets can also largelyaffect the efficiency of attribute reduction. this motivates the idea of this paper. therefore, inorde

23、r to further improve the performance of the heuristic attribute reduction methods, we developa new accelerator by gradually reducing not only the size of universe but also the number ofattributes when each iteration of attribute reduction. by incorporating the new accelerator intoeach of the above f

24、our representative heuristic attribute reduction methods, we obtain theiraccelerating versions. numerical experiments show that each of the improved methods can obtainthe same attribute subset as its corresponding original method while greatly saving computationalcost, especially for the large scale

25、 datasets.the rest of study is organized as follows. a relative basic concept is in section 2. in section3, through analyzing the rank preservation of four representative significant measures of attributes,we develop a new accelerator based on the perspective of objects and attributes. experiments o

26、nsix datasets in uci machine learning repository show that the four representative heuristicalgorithms based on the proposed accelerator outperform their original counterparts in terms oftime consuming in section 4. then, conclusion and future work come in section 5.1 preliminariesin this section, w

27、e review some basic concepts such as indiscernibility relation, partition,significance measures and forward attribute reduction algorithms.-2-1.1 rough approximationsan information table is a 4 -tuple s = (u , a,v , f ) (for short s = (u , a) ), where uis a non-empty and finite set of objects, calle

28、d a universe, and a is a non-empty and finite set of90attributes, va is the domain of the attribute a , v =function f ( x, a) va for each a a 2.uaava and f : u × a = v is aan indiscernibility relation rb = ( x, y) u ×u | a( x) = a( y), a b was determinedby a non-empty subset b a . u / rb =

29、 xb | x u (just as u / b ) indicates thepartition of u resulted from rb , where xb denotes the equivalence class determined by x95100105110115120with respect to b , i.e., xb = y u | ( x, y) rb .furthermore, given an information table s = (u , a) and an object subset x u ,b a , one can construct a ro

30、ugh set of x on the universe by elemental information granulesin the following definition:bx = xb | xb x ,bx = xb | xb x ,where bx and bx are called b -lower approximation and b -upper approximationwith respect to b , respectively. the order pair (bx , bx ) is called a rough set of x .there are two

31、kinds of attributes for a classification problem, which can be characterized by adecision table dt = (u , c d) with c d = , where an element of c c is called acondition attribute, c is called a condition attribute set, an element of d is called a decisionattribute, and d is called a decision attribu

32、te set.given a decision table dt = (u , c d) , b c , u / d = y1,y2 ,l, yn , the lowerand upper approximations of the decision attribute set d are defined asbd = by1, by2 ,l, byn ,bd = by1, by2 ,l, byn .nlet posbb in the decision table dt = (u , c d) .1.2 four representative significance measures of

33、attributesin heuristic attribute reduction methods, attribute significance measure is a crucial factor.therefore, we will introduce the four representative significance measures here, which are basedon positive region, shannons conditional entropy, complement conditional entropy andcombination condi

34、tional entropy.· positive region (pr) was first employed in a heuristic attribute reduction algorithm, calledpositive region reduction, which keeps the positive region of target decision unchanged 15.· shannons conditional entropy (sce) was introduced to search reducts of a decision table2

35、1. this reduction algorithm calls shannons entropy reduction, which remains the conditionalentropy of target decision. shannons conditional entropy of b with respect to d indt = (u , c d) is denoted as-3-(u ,c )(d) = ui =1 byi , which is called the positive region of d with respect tom n| x ) log( p

36、(y | xi=1 j=1where p( x i ) =| x i |u |and p(y j | x i ) =| x i y j | x i |, when x is an empty set, the conditionalprobability is defined as 1.125· complement conditional entropy (pce) was defined to measure the uncertainty andapplied to reduce redundant attribute of a decision table 17,18. th

37、e reduction method based onthe entropy is called complement entropy reduction, which can preserve the conditional entropy ofa given decision table. the conditional entropy of b with respect to d in dt = (u , c d)is denoted as130m ni=1 j =1| y j x i | | y jc x ic | u | | u |,c c· combination con

38、ditional entropy (cce) is based on the intuitionistic knowledge contentnature of information gain, which can be used to obtain attribute reducts 19. the reductionmethod can remain combination conditional entropy of a given decision table. the conditional135entropy of b with respect to d in dt = (u ,

39、 c d) is defined asce(u ,c )mi=12| u | c|u2 |nj=1| u | c|u |2),2| x i |×(| x i |1)2denotes the number of pairs of the objects which are notdistinguishable from each other in the equivalence class x i .the corresponding significance measures based on the measures mentioned above are given140145a

40、s follows.let dt = (u , c d) be a decision table and b c . for a b , the innersignificance measures of a based on positive region, shannons conditional entropy,complement conditional entropy and combination conditional entropy are respectively defined as(u ,c )sig 2inner (a, b, c, d,u ) = h (u ,c )

41、( d | b a) h (u ,c ) (d | b),sig 3inner (a, b, c, d,u ) = e (u ,c ) (d | b a) e (u ,c ) (d | b),sig 4inner (a, b, c, d,u ) = ce (u ,c ) (d | b a) ce (u ,c ) ( d | b).where(u ,c )b( d )|.by means of the inner significant measures, the definition of core can be denoted as follows.150155let s = (u , c

42、d) be a decision table and a c . if sig Äinner (a, c, c, d,u ) > 0( Ä = 1, 2, 3, 4 ), then a is a core attribute of s in the context of type Ä .furthermore, we suppose s = (u , c d) be a decision table and b c . fora c b , the outer significance measures of a based on positive regi

43、on, shannonsconditional entropy, complement conditional entropy and combination conditional entropy arerespectively defined as-4-h (u ,c ) (d | b) = p( x i ) p(y j i j i ),e (u ,c ) ( d | c ) = where y j and x i are the complements of y j and x i , respectively.(d | c) = (| x i | c| x i | | x i y j

44、| c| x i y j |2where c| x i | =sig inner (a, b, c, d,u ) = ã b (d) ã bu c (d),sig1outer (a, b, c, d,u ) = ã b(u,ca) ( d) ã b(u ,c ) ( d),sig 2outer (a, b, c, d,u ) = h (u ,c ) ( d | b) h (u ,c ) (d | b a),sig 3outer (a, b, c, d,u ) = e (u ,c ) (d | b) e (u ,c ) (d | b a),sig 4out

45、er (a, b, c, d,u ) = ce (u ,c ) (d | b) ce (u ,c ) ( d | b a),160where(u ,c )b( d )|.1.3 forward attribute reduction algorithmsin rough set theory, many heuristic attribute reduction algorithms have been designed toachieve efficiently attribute reducts, in which forward greedy search strategy is com

46、mon. ingeneral, starting with an attribute with the maximal inner significance measure, a forward greedy165170175180185attribute reduction approach takes an attribute with the maximal outer importance into the attributereduct in each loop until this subset satisfies the stopping criterion, which yie

47、lds an attribute reduct.formally, a forward greedy attribute reduction algorithm can be written as follows.algorithm 1. 15 general forward greedy attribute reduction algorithminput: decision table s = (u , c d) ;output: one reduct red .step 1: red ; / red is the pool to conserve the selected attribu

48、tesstep 2: compute sig inner (ak , c, c, d,u ) , k | c | ;step 3: put ak into red , where sig inner (ak , c, c, d,u ) > 0 ;step 4: while ef (u ,c ) (red , d) ef (u ,c ) (c, d) do /this provides a stoppingcriterion. red red a0 , where sig outer (a0 , red , c, d,u ) = maxsig outer (ak , red , c, d,

49、u ) ,ak c red ;step 5: return red and end.2 rank preservation of significance measures of attributesit is well known that each of significance measures of attributes provides some heuristicinformation for forward attribute reduction algorithms. in this section, to further improve theperformance of t

50、hese attribute reduction algorithms, we will focus on the rank preservation of thefour significance measures of attributes from the perspective of decreasing the number of objectsand attributes simultaneously.in order to prove the rank preservation of a significance measure of attributes, we need th

51、efollowing lemma.lemma 2.1.let 0 ai , bi 1, i = 1, 2,l, n ,ni=1ai = 1 , andni=1 ini=1ai × bi = 1, then 1 u n such that au = bu = 1 and ak = bk = 0 for k u .proof. by means of the existing conditions, we have that190n thus, one has-5-b = 1 . if=i 1n ai ib = ai × (1 b j ) = ai ai × b j

52、= 1 ai × b j .n n n n n n ×i =1 i=1 j =1, j ii=1j =1, j ii=1 j =1, j in n i=1 i=1 nj =1, j i n nj=1, j i ai ×nj =1, jib j = 0, for i n ai = 0 ornj =1, j ib j = 0, for i nfurthermore, because ofni=1ai = 1 , there exists u n such that au 0 . thereforenj =1, j ub j = 0 , i.e., bk = 0, fork u . and because ofnj =1b j = 1 , we can obtain b