Some hybrid methods in fuzzy rough set based attribute reduction in decision tables

tion In this chapter, the thesis proposes two algorithms based on approaching the hybrid filter-wrapper for finding an approximate reduction set to minimize the number of attributes of reduction set and improve the accuracy of the classification model. The filter phase finds the candidates for the reduction set based on the measurement (also called the approximation set), the wrapper phase calculates the candidate's classification accuracy and selects approximate reduction set having the highest classification accuracy. (1) The filter-wrapper algorithm for finding reduction set using the fuzzy function in the fuzzy rough set. (2) The filter-wrapper algorithm for finding reduction set using fuzzy distance. The fuzzy distance constructed is the extension of the partition distance in the work [48] and different to distance measurements in the works [3, 8, 18]. The results in this chapter are published in works 1, 2, 5, 6, 7. 2.2. Attribute reduction using fuzzy function 2.2.1. Attribute reduction using fuzzy function based on filter approach 1) Fuzzy function in fuzzy rough set Given decision table  ,DS U C D  with  1,..., nU u u ,  1,..., mC c c . With P C , suppose that PR is fuzzy equivalent relation defined on attribute value region P. Fuzzy function of P based on relation PR is defined in fuzzy rough set as below [77, 78] 2) Heuristic algorithm for finding reduction set using the fuzzy dependence of attribute based on approaching filter. F_FRSAR algorithm (Filter Fuzzy Rough Set based Attribute Reduction). Input: Decision table  ,DS U C D  , fuzzy equivalent relation R defined on conditional attribute value region. Output: Reduction set B of DS 1. :B  ;   : 0D   ; 2. Calculate fuzzy equivalent relational matrix  CM R ; 3. Calculate fuzzy function   CR D ; // add gradually the greatest important attributes into B 4. While     B CR R D D  do 5. Begin 6. With each a C B  calculate         B a BB R R SIG a D D     ; 7 7. Select ma C B  so that     B m B a C B SIG a Max SIG a    ; 8.  mB B a  ; 9. Calculate   BR D ; 10. End; // Remove redundant attributes in B if any 11. For each a B 12. Begin 13. Calculate     B aR D  ; 14. If       B a CR R D D    then  :B B a  ; 15. End; 16. Return B; Complexity of F_FRSAR algorithm is  2 2O C U 2.2.2. Attribute reduction using fuzzy function based on filter-wrapper approach Consider decision table  ,DS U C D  with  1 2, ,..., mC a a a and R is fuzzy equivalent relation defined on attribute value region. Set   CR D  . According to F_FRSAR algorithm, suppose that 1 2 , ,...i ia a added into empty set based on the greatest value of attribute importance until exist  1,2,...t m so that     , ,..., 1 2 a a ai i it R D  . Finish filter F_FRSAR algorithm, we have reduction set   1 2 , ,..., ti i i B a a a and classification accuracy on data set calculated on B. On the other hand, according to the definition of fuzzy positive region in theory of fuzzy rough set and [76, 77, 78, 79] we have             , ,..., 1 1 2 1 ... a a a a ai i i i it R R R D D D       . With threshold   given, set   1 ,..., kk i i B a a to satisfy   BkR D  and     1 B ak ik R D     . Then, kB is called as approximate reduction set  . If kB and  1 ,...,k tk i iB a a used to develop classifier, publication [91] shows that, classification accuracy on   1 ,..., k tk i i B a a   is not better than on kB . Suppose that kB has better classification accuracy than  1 ,...,k tk i iB a a . Then, If select kB to be result of algorithm, kB shall have higher classification accuracy, has the number of attributes smaller, so the generalization and performance of the algorithm will be higher. This leads to the direction of approaching hybrid for finding approximate reduction set, is combination of filter and wrapper. Filter method find out approximate reduction sets, wrapper method check the classification accuracy of approximate reduction sets to select the highest accuracy reduction set. By this approach, the classification accuracy on the reduction set found is higher than conventional filter method. However, implementation time will be higher because of implementing classifiers. Filter-wrapper algorithm for finding approximate reduction set using fuzzy function as below: FW_FRSAR algorithm (Filter-Wrapper Fuzzy Rough Set based Attribute Reduction): Filter- wrapper algorithm for finding approximate reduction set using fuzzy function. Input: Decision table  ,DS U C D  , fuzzy equivalent relation R defined on conditional attribute value region. 8 Output: Approximate reduction set xB has the best classification accuracy. // Initialize 1. :B  ;   0D   ; 2. Calculate fuzzy function   CR D ; // Filter phase, finds candidates for reduction set // Add gradually the greatest important attributes into P 3. While     B CR R D D  do 4. Begin 5. With each a C B  calculate         B a BB R R SIG a D D     6. Select ma C B  so that     B m B a C B SIG a Max SIG a    ; 7.  mB B a  ; 8. End; // Wrapper phase, finds the greatest classification accuracy of reduction Set t B //t is number of elements of B, B includes attribute string selected at each iterative step of While loop, it means that        1 1 2 1 2 , , ,..., , ,..., ti i i i i i B a a a a a a ; 9. Set       1 1 2 1 21 2 , , ,..., , ,..., ti i i t i i i B a B a a B a a a   10. For j = 1 to t 11. Begin 12. Calculate the classification accuracy jB by a classifier using 10-fold method; 13. End 14. x joB B with joB has the greatest classification accuracy. Return xB ; 2.2.3. Experimental results 1) Data set Table 2.2. Data set of F_FRSAR, FW_FRSAR algorithms No. Data Set Description No. of objects No. of conditional attributes No. of class decided All Nominal attribute Real- valued attribute 1 Ecoli Protein Localization Sites 336 7 0 7 8 2 Ionosphere Johns Hopkins University Ionosphere database 351 34 0 34 2 3 WDBC Wisconsin diagnostic breast cancer 569 30 0 30 2 4 Wpbc Wisconsin Prognostic Breast Cancer 198 33 0 33 2 9 5 Wine Wine recognition data 178 13 0 13 3 6 Glass Glass Identification Database 214 9 0 9 7 7 Magic04 MAGIC gamma telescope data 2004 19020 10 0 10 2 8 Page- blocks Blocks Classification 5473 10 0 10 5 2) Evaluate the classification accuracy of F_FRSAR filter algorithm with other algorithms based on approaching fuzzy rough set Table 2.4. The classification accuracy of GAIN_RATIO_AS_FRS and F_RSAR No. Data set U C GAIN_RATIO_AS_FRS algorithm [45] F_FRSAR algorithm R SVM classifica tion accuracy C4.5 classifica tion accuracy R SVM classifica tion accuracy C4.5 classifica tion accuracy 1 Ecoli 336 7 6 0.814 0.802 7 0.865 0.855 2 Ionos phere 351 34 13 0.916 0.904 15 0.937 0.915 3 Wdbc 569 30 17 0.925 0.917 19 0.980 0.975 4 Wpbc 198 33 17 0.815 0.804 19 0.825 0.818 5 Wine 178 13 9 0.910 0.902 10 0.955 0.920 6 Glass 214 9 7 0.891 0.882 7 0.891 0.882 7 Magi c04 190 20 10 6 0.782 0.765 6 0.782 0.765 8 Page- block s 547 3 10 6 0.852 0.848 7 0.865 0.855 The classification accuracy of F_FRSAR is higher than the classification accuracy of GAIN_RATIO_AS_FRS in [45]. F_FRSAR reduction set preserves the fuzzy positive region and more attributes than GAIN_RATIO_AS_FRS algorithm in [45]. 3) Evaluate the classification accuracy of FW_FRSAR filter-wrapper algorithm with F_FRSAR filter algorithm and other filter algorithms based on approaching fuzzy rough set Table 2.5. The classification accuracy of FW_FRSAR, F_FRSAR, GAIN_RATIO_AS_FRS No. Data set Initial data set FW_FRSAR algorithm F_FRSAR algorithm GAIN_RATIO _AS_FRS algorithm [45] U C R Classification accuracy R Classification accuracy R Classification accuracy 10 1 Ecoli 336 7 5 0.901 7 0.855 6 0.802 2 Ionosphere 351 34 8 0.946 15 0.915 13 0.904 3 Wdbc 569 30 6 0.975 19 0.975 17 0.917 4 Wpbc 198 33 12 0.867 19 0.818 17 0.804 5 Wine 178 13 5 0.920 10 0.920 9 0.902 6 Glass 214 9 4 0.924 7 0.882 7 0.882 7 Magic04 19020 10 4 0.886 6 0.765 6 0.765 8 Page- blocks 5473 10 5 0.906 7 0.855 6 0.848 Table 2.5 shows that the number of attributes of reduction set of FW_FRSAR filter- wrapper algorithm is much smaller, especially for Wdbc, Ionosphere data sets. Furthermore, the accuracy of FW_FPDBAR is higher than F_DBAR and GAIN_RATIO_AS_FR. 4) Compare the implementation time of FW_FRSAR, F_FRSAR and GAIN_RATIO_AS_FRS Table 2.6. Implementation time of FW_FRSAR, F_FRSAR, GAIN_RATIO_AS_FRS No . Data set U C FW_FRSAR algorithm F_FRSA R algorithm GAIN_RATI O _AS_FRS algorithm [45] Filer procedur e Wrapper procedur e Total 1 Ecoli 336 7 2.38 1.24 3.62 2.86 2.95 2 Ionospher e 351 34 12.64 6.92 19.56 14.87 15.04 3 Wdbc 569 30 22.15 8.74 30.89 24.12 26.08 4 Wpbc 198 33 8.56 6.28 14.84 9.12 9.88 5 Wine 178 13 0.58 1.22 1.80 0.62 0.74 6 Glass 214 9 0.82 0.66 1.48 0.88 1.02 7 Magic04 1902 0 10 894.26 124.49 1018.7 5 914.86 948.16 8 Page- blocks 5473 10 98.64 22.16 120.80 112.76 126.28 Table 2.6 shows that the implementation time of the FW_FRSAR algorithm is higher than the two F_FRSAR and GAIN_RATIO_AS_FRS filter algorithms because they must implement the classifiers in the wrapper phase. 2.3. Attribute reduction using fuzzy distance In recent years, Nguyen Long Giang et al. have used distance measures to resolve the problem of attribute reduction in the decision table based on approaching conventional rough set [9, 24, 57]. , 65] and inadequate decision table based on approaching tolerance rough set [9, 10, 12, 25, 58]. Based on approaching fuzzy rough set, the team extended the proposed distance measurements into fuzzy distance measurements and had some results in using fuzzy distance measurements to resolve the problem of attribute reduction on the decision table having numeric value region [3, 8, 18]. 11 Continue this research direction, with the objective of finding effective distance measures (with simple calculation formulas) to resolve the problem of attribute reduction, in this section we develop a new fuzzy distance measurement (hereinafter referred to as fuzzy distance) based on the partition distance measurement in works [48]. Using the fuzzy distance developed, we propose a filter-wrapped attribute reduction method in the decision table to improve the classification accuracy and minimize the number of attributes of reduction set. 2.3.1. Develop fuzzy distance between two fuzzy sets Proposition 2.1. Given two fuzzy sets ,A B on object set U. then  ,d A B A B A B    is a fuzzy distance between A and B . 2.3.2. Develop fuzzy distance between two fuzzy partitions Proposition 2.2. Given decision table  ,DS U C D  with  1 2, ,..., nU x x x and  PR ,  QR are fuzzy partitions derived by two fuzzy equivalent relations PR , QR on ,P Q C . Then:              2 1 1 , n P Q i i i iP Q P Q i D R R x x x x n        Is a fuzzy distance between  PR and  QR , called as fuzzy partition distance. Proposition 2.3. Given decision table  ,DS U C D  with  1 2, ,..., nU x x x and R is fuzzy equivalent relation defined on value region of conditional attribute set, then fuzzy distance between 2 attribute sets of C andC D defined as below:            2 1 1 , n C C D i i iC C D i D R R x x x n        Proposition 2.5. Given  PR  is a fuzzy partition on , then we have:          , , 1P PD R D R       Proposition 2.6. Given decision table  ,DS U C D  with  1 2, ,..., nU x x x , B C and R is fuzzy equivalent relation defined on value region of conditional attribute set. Then          , ,B B D C C DD R R D R R     2.3.3. Attribute reduction using fuzzy distance based on approaching filter Definition 2.1. Given decision table  ,DS U C D  with B C and R is fuzzy equivalent relation defined on value region of conditional attribute set. If 1)          , ,B B D C C DD R R D R R     2)             , , ,B b B b D C C Db B D R R D R R         B is a reduction set of C , based on fuzzy distance. Definition 2.2. Given decision table  ,DS U C D  with B C and b C B  . The importance of attribute b to B defined by              , ,B B D B b B b DBSIG b D R R D R R        Importance  BSIG b denoted classification quality of attribute b to decisive attribute D and used as standard to select attribute of F_FDAR filter algorithm for finding reduction set F_FDAR algorithm (Filter - Fuzzy Distance based Attribute Reduction): filter algorithm for finding reduction set using fuzzy distance. 12 Input: given decision table  ,DS U C D  , fuzzy equivalent relation R defined on conditional attribute set. Output: A reduction set B 1. B  ;     , 1B B DD R R    ; 2. Calculate fuzzy partition distance     ,C C DD R R   ; // Add gradually the greatest important attributes into B 3. While          , ,B B D C C DD R R D R R     do 4. Begin 5. With each a C B  calculate              , ,B B D B a B a DBSIG a D R R D R R        6. Select ma C B  so that     B m B a C B SIG a Max SIG a    ; 7.  mB B a  ; 8. End; //Remove redundant attributes in B if any 9. For each a B 10. Begin 11. Calculate        ,B a B a DD R R    ; 12. If             , ,B a B a D C C DD R R D R R       then  B B a  ; 13. End; Return B ; The time complexity of F_FDAR algorithm is  2 2O C U 2.3.4. Attribute reduction using fuzzy distance based on approaching filter-wrapper Consider decision table  ,DS U C D  with  1 2, ,..., mC a a a and R is fuzzy equivalent relation defined on conditional attribute value. Set     ,C C DD R R    . According to F_FDAR algorithm, suppose that attributes 1 2 , ,...i ia a added into empty set based on the greatest important value of attribute until exist  1,2,...t m so that       1 2 1 2, ,..., , ,...,,i i i i i it ta a a a a a DD R R    . Finish the algorithm, we have reduction set   1 2 , ,..., ti i i B a a a , the classification accuracy on data set calculated by the classification accuracy on B. On the other hand, according to Clause 2.6 we have                     1 1 1 2 1 2 1 1, , ,..., ,...,, , ... ,i i i i i i i i i it ta a D a a a a D a a a a DD R R D R R D R R            with threshold   given, set   1 ,..., kk i i B a a to satisfy     ,k kB B DD R R    and       1 1,k i k ik kB a B a DD R R       . then, kB is called as approximate reduction set  . If kB and   1 ,..., k tk i i B a a   used to develop classifier, publication [91] shows that, the classification 13 accuracy on   1 ,..., k tk i i B a a   is not better than on kB . Suppose that kB has better classification accuracy   1 ,..., k tk i i B a a   . Then, if select kB is the result of an algorithm, kB has higher classification accuracy, the number of attributes is smaller, the generalization and performance of the classification algorithms are higher. This leads to a hybrid approach direction for finding approximate reduction set, is a combination of filter and wrapper. The filter method finds the approximate reduction set, wrapper method checks the classification accuracy of approximate reduction set for selecting the greatest accuracy reduction set. With this approach direction, the classification accuracy on the reduction set is higher compared to conventional filter methods. However, the implementation time will be greater because of the implementation of the classifier. The filter-wrapper algorithm finds a approximate reduct using fuzzy distance: FW_FDAR algorithm (Filter-Wrapper Fuzzy Distance based Attribute Reduction): The filter- wrapper algorithm for finding a approximate reduction set using fuzzy distance. Input: Decision table  ,DS U C D  , fuzzy equivalent relation R on conditional attribute value region. Output: Approximate reduction set xB has the best classification accuracy. // Initialize 1. B  ;     , 1B B DD R R    ; 2. Calculate the fuzzy distance     ,C C DD R R   ; // filter phase, fins candidates for reduction set // Add gradually the greatest important attributes into B 3. While          , ,B B D C C DD R R D R R     do 4. Begin 5. With each a C B  calculate              , ,B B D B a B a DBSIG a D R R D R R        ; 6. Select ma C B  so that     B m B a C B SIG a Max SIG a    ; 7.  mB B a  ; 8. End; // Wrapper phase, finds the highest classification accuracy of reduction set 9. Set t B // t is number of elements of B, B includes attribute strings selected at each iterative step of While loop, it means that        1 1 2 1 2 , , ,..., , ,..., ti i i i i i B a a a a a a ; 10. Set       1 1 2 1 21 2 , , ,..., , ,..., ti i i t i i i B a B a a B a a a   11. For j = 1 to t 12. Begin 13. Calculate the classification accuracy on jB by a classifier and using 10-fold method; 14. End 15. x joB B with joB has greatest classification accuracy. 14 Return xB ; Time complexity of FW_FDAR algorithm is    2 2* *O C U O C T with  O T is complexity of classifier. 2.3.5. Experimental algorithms 1) Experimental objectives 1) FW_FDAR filter-wrap proposed algorithm compared to FPDAR filter algorithm in [18] in terms of implementation time and classification accuracy. 2) FW_FDAR filter-wrapper proposed algorithm compared to FEBAR filter-wrapper algorithm in [91] in terms of implementation time and classification accuracy. 2) Experimental data Table 2.8. Tested data set of FW_FDAR algorithm No. Data set Description No. of objects No. of conditional attributes No. of class decided All Nominal attribute Real- valued attribute 1 Lympho Lymphography 148 18 18 0 2 2 Wine Wine 178 13 0 13 3 3 Libra Libras movement 360 90 0 90 15 4 WDBC Wisconsin diagnostic breast cancer 569 30 0 30 2 5 Horse Horse colic 368 22 15 7 2 6 Heart Statlog (heart) 270 13 7 6 2 7 Credit Credit approval 690 15 9 6 2 8 German German credit data 1000 20 13 7 2 3) Comparison result of classification accuracy Classification accuracy is shown by v  in which v mean accuracy value and  is standard error. Using CART classifier (regression tree) to calculate the classification accuracy in wrapper phase with 10-fold cross check method. Table 2.9. The classification accuracy of FW_FDAR, FEBAR, FPDAR No. Data set Initial accuracy FW_FDAR algorithm FEBAR algorithm [91] FPDAR algorithm [18] C Accuracy B Accuracy B Accuracy B Accuracy 1 Lympho 18 0.776± 0.008 4 0.768 ± 0.085 4 0.768 ± 0.085 6 0.722 ± 0.062 2 Wine 13 0.910 ± 0.066 5 0.893 ± 0.072 5 0.893 ± 0.072 7 0.886 ± 0.058 3 Libra 90 0.566 ± 0.137 7 0.658 ± 0.077 8 0.605 ± 0.103 26 0.556 ± 0.205 4 WDBC 30 0.924 ± 4 0.968 ± 3 0.952 ± 6 0.925 ± 15 0.037 0.058 0.027 0.644 5 Horse 22 0.829 ± 0.085 5 0.816 ± 0.052 4 0.802 ± 0.066 12 0.798 ± 0.058 6 Heart 13 0.744 ± 0.072 3 0.803 ± 0.074 3 0.803 ± 0.074 12 0.752 ± 0.055 7 Credit 15 0.826 ± 0.052 3 0.865 ± 0.028 2 0.846 ± 0.048 14 0.820 ± 0.078 8 German 20 0.692 ± 0.030 6 0.716 ± 0.029 5 0.702 ± 0.043 11 0.684 ± 0.024 The results in Table 2.9 show that the number of attributes of reduction set of the FW_FDAR proposed algorithm is much smaller than FPDAR filter algorithm. The accuracy of FW_FDAR is higher than FPDAR on all data sets. With FEBAR [91] filter-wrapper algorithm using fuzzy -entropy, the number of attributes of reduction set of FW_FDAR is approximate FEBAR, the classification accuracy of FW_FDAR is approximate FEBAR. 3) Comparison result of implementation time Table 2.10. Implementation time of FW_FDAR, FEBAR, FPDAR No . Data set FW_FDAR algorithm FEBAR algorithm [91] FPDAR algorith m [18] Filer procedur e Wrapper procedur e Total Filer procedur e Wrapper procedur e Total 1 Lymph o 0.32 0.50 0.82 0.38 0.52 0.90 0.34 2 Wine 0.46 1.21 1.67 0.51 1.18 1.69 0.48 3 Libra 46.28 86.18 132,4 6 55.12 88.26 143.3 8 48.48 4 WDBC 20.15 8.74 28.89 26.38 8.22 34.60 22.32 5 Horse 4.85 2.68 7.53 5.26 2.65 7.91 4.98 6 Heart 1.22 1.52 2.74 1.45 1.78 3.23 1.26 7 Credit 16.58 3.42 20.00 19.26 3.98 23.24 18.02 8 German 52.48 8.64 61.12 71.22 8.28 79.50 54.65 Table 2.10 shows that the FW_FDAR algorithm has a significantly shorter implementation time than the FEBAR algorithm [91], especially in the filter procedure for finding reduction set. The reason is that FEBAR algorithm must calculate the fuzzy positive region to determine the coefficient , furthermore, FEBAR algorithm must calculate the complex logarithm formula in the Shannon entropy formula. However, algorithm based on approaching FW_FDAR filter-wrapper and FEBAR [91] have a significantly longer implementation time than algorithm based on approaching FPDAR filter[18] because they must implement the classifier to calculate the accuracy of approximate reduction set in wrapper phase. Chapter 3. INCREMENTAL METHOD OF ATTRIBUTE REDUCTION IN DECISION TABLE CHANGED TO USE FUZZY DISTANCE 3.1. Introduction With the continuous growth in data capacity, decision tables are becoming larger and changed continuously. The application of algorithms for finding reduction set based on 16 conventional approach has many challenges. Therefore, the researchers proposed an incremental calculated approach direction for finding reduction set to minimize the implementation time and be able to implement on large decision tables. In recent years, some research teams have proposed incremental algorithms for finding reduction set on decision tables changed based on approaching fuzzy rough set [15, 16, 97, 99]. Incremental algorithms for finding reduction set on decision tables based on approaching fuzzy rough set mentioned above have significantly smaller implementation time than non- incremental algorithms and can be implemented on large data tables. However, the algorithms mentioned above follow the direction of approaching conventional filter. Thus, the reduction set of algorithms mentioned above is not optimal both in terms of number of attributes and the classification accuracy. In this chapter, the thesis presents the formula for fuzzy distance incremental calculation (proposed in Item 2.3, Chapter 2) in the case of addition and removal of object set. According to the incremental formulas developed, the thesis presents an filter-wrapper incremental algorithm for finding reduction set in the case of addition or removal of object set. The results of this chapter are published in Work no. 7. 3.2. Filter-wrapper incremental algorithm for finding approximate reduction set when adding object set 3.2.1. Incremental formula for fuzzy distance calculation when adding object set Clause 3.1. Given decision table  ,DS U C D  with  1 2, ,..., nU x x x and R is fuzzy equivalent relation defined on conditional attribute set value region. Suppose that object x added into U . Then, formula for fuzzy partition distance incremental calculation is:                      2 2 2 , , 1 1 C C D C C DUU x C C D n D R R D R R x x x n n                Clause 3.2. Given decision table  ,DS U C D  with  1 2, ,..., nU x x x and R is fuzzy equivalent relation defined on conditional attribute set value region. Suppose that object set includes s elements  1 2, ,...,n n n sU x x x    added into U , with        ij ij ( ) , ( )CU U U U Dn s n s n s n s M R p M R d       