Evolutionary Optimization of a Collection of Variable-Length Subpatterns for Pattern Classification ( ) ( ) Robert Ian McKay ( )

Size: px

Start display at page:

Download "Evolutionary Optimization of a Collection of Variable-Length Subpatterns for Pattern Classification ( ) ( ) Robert Ian McKay ( )"

지나 빙
6 years ago
Views:

1 Evolutionary Optimization of a Collection of Variable-Length Subpatterns for Pattern Classification

2 Evolutionary Optimization of a Collection of Variable-Length Subpatterns for Pattern Classification ( ) ( ) Robert Ian McKay ( )

3 (rule-based classifier)., (decision boundary) (hypercube)...,. (hypersphere). UCI,. :,,, : i -

4 (Rule) (Rule-Based Classification) (Inductive Logic Programming) (Association Rule-based Classification) (Decision Tree) SONAR SPECTF IONOSPHERE Wisconsin Diagnostic Breast Cancer (WDBC) ii -

5 ABSTRACT SONAR SONAR SONAR r SPECTF SPECTF SPECTF r IONOSPHERE IONOSPHERE IONOSPHERE r WDBC WDBC WDBC r SONAR SPECTF IONOSPHERE WDBC 27 - iii -

6 . (rule-based classifier) 표 1. 학습규칙들의예 ( 날씨 = 맑음, 온도 = 높음, 습도 = 높음, 바람 = 약함 ) à 테니스안침 ( 날씨 = 맑음, 온도 = 낮음, 습도 = 보통 ) à 테니스침 ( 날씨 = 흐림, 습도 = 높음, 바람 = 강함 ) à 테니스안침. (decision boundary) 1 (hypercube) - 1 -

7 . 그림 1. 초입방체들의집합형태의 결정경계....,.,,,

8 (hypersphere).. [1] [2] [3] [4] UCI machine learning repository [6] 30,

9 (Rule) (antecedent) à (consequent).. ( =, =, = ) à à,,,,,,. ( =, =, =, = ),,... ( <25, 65< <75, >1.0) à 1. ( =23, =180, =68, =1.2)

10 2.2. (Rule-Based Classification) 2.1. Sequential Covering.. Sequential Covering AQ [7], CN2 [8], RIPPER [9] (Inductive Logic Programming) 2.2 (propositional rule). 1 (first-order Horn rule). FOIL (First-Order Inductive Learner) [10]. FOIL Sequential Covering

11 (Relational Learning) (Association Rule-based Classification). CBA (Classification Based Associations) [11], CMAR (Classification Based on Multiple Association Rules) [12], CPAR (Classification Based on Predictive Association Rules) [13], MCAR (Multi-class Classification based on Association Rule) [14]. CBA (Breadth First Search) Apriori [15] support, confidence. CMAR (Depth First Search) FP-tree [16]. CPAR FOIL FOIL

12 CMAR. MCAR (support), (confidence), (Decision Tree).. ID3 [17], C4.5 [18], CART [19] information gain, gain ratio, gini index

13 그림 2. 결정트리의예 [20]

14 (CVLS). 입력 : n 개의원소를가지는학습패턴집합 출력 : d 개의원소를가지는서브패턴집합 1. 학습패턴들을정형화 (Standardization) 하고서브패턴길이선택의확률분포 D 와 결정경계선택의확률분포 B 를균등분포 (uniform distribution) 로초기화 2. 학습패턴의임의의속성들을포함하는부분집합인서브패턴들을 d 개생성하여서 브패턴집합 S 를구성. 이때서브패턴의길이와결정경계는각각 D 와 B 의확률 분포에따라결정됨 3. 서브패턴집합을이용하여학습패턴들을분류함. 올바르게분류된학습패턴들은 Xc, 틀린학습패턴들은 Xw 에넣음. 모든학습패턴을바르게분류시종료 4. 각서브패턴원소의적응도를계산 5. D 와 B 를적응도높은서브패턴 개의길이분포와결정경계분포로 갱신 6. 적응도낮은하위서브패턴 개를학습패턴으로부터 새로생성한서브패턴으로교체. 이때생성되는서브패턴의길이의확률 과결정경계선택확률은각각 D 와 B 를따른다 단계로돌아감. 지정된횟수이상 loop 이반복되었으면종료 그림 3. 학습알고리즘 - 9 -

15 3.2.. =.. 2개의 5차원학습패턴 (0,1,0,0,1,true), (1,1,1,0,0,false) 존재할경우 (f 1 =0, f 3 =0, f 5 =1, class=true) (f 2=1, f 4=0, class=true) (f 2=1, f 3=1, f 4=0, class=false) (f 1 =1, f 2 =1, f 4 =0, f 5 =0, class=false) 그림 4. 서브패턴생성예 D. D 패턴의차원. B.., missing value

16 ..,,.,, p (1). (1)

17 ., 서브패턴의속성개수., (2). 의속성개수 (2) r.,

18 입력 : 서브패턴집합, m 차원입력패턴 출력 : 입력패턴의클래스 1. 입력패턴에대해서브패턴에정해진결정경계에따라 (1) 또는 (2) 식을 만족하는모든서브패턴들을추출 2. 추출된서브패턴들의클래스중가장많은클래스를입력패턴의클래스로정함 (majority voting) 그림 5. 패턴분류알고리즘 (overfitting)

19 (3). (3) 3 s i mw, mr. s i cw, cr., (boosting)

20 [21] , (Occam's razor)., D

21 ....,.. B ,

22 .....,.. [22]

23 UCI Machine Learning Repository 30, CVLS. 2. 표 2. 실험데이터 이름 속성개수 레코드개수 SONAR SPECTF 44 학습 : 80, 테스트 : 187 Wisconsin Diagnostic Breast Cancer (WDBC) IONOSPHERE ,,.,, 50 [23]. Weka [24]

24 10. SPECTF 10 fold stratified cross validation, SONAR 6 SONAR. Iteration, Accuracy SONAR Accuracy Iteration 그림 6. SONAR 학습중의정확도변화 3 SONAR. CVLS

25 표 3. SONAR 에대한테스트정확도비교 분류기 평균정확도 (%) 표준편차 CVLS SVM (Pearson VII kernel [25]) knn (k=1) AdaBoost ( 반복횟수 =50) Random Forest ( 트리수 =50) Decision Tree (C4.5) Naive Bayes SONAR. Hypercube, Hypersphere, Sum Hypercube (Avg: ) Hypersphere (Avg: ) Sum (Avg: ) 500 Frequency Subpattern Length 그림 7. SONAR 학습완료후서브패턴길이의분포

26 8 SONAR (1) (2) r.,,, 4. r r Hypercube Hypersphere Mixed (Same Ratio) Mixed (Different Ratio) Accurcy r 그림 8. SONAR 유효성판별식의 r 과결정경계형태에따른정확도차이

27 4.4. SPECTF 9 SPECTF. SPECTF. 0.8 SPECTF Accuracy Iteration 그림 9. SPECTF 학습중의정확도변화 4 SPECTF. SPECTF. 표 4. SPECTF 에대한테스트정확도비교 분류기 평균정확도 (%) CVLS SVM (Pearson VII kernel) AdaBoost ( 반복횟수 =50) Random Forest ( 트리수 =50) Naive Bayes Decision Tree (C4.5) knn (k=1)

28 10 SPECTF 5. SPECTF Hypercube (Avg Length: ) Hypersphere (Avg Length: ) Sum (Avg Length: ) 600 Frequency Subpattern Length 그림 10. SPECTF 학습완료후서브패턴길이의분포 11 SPECTF

29 Accuracy Hypercube Hypersphere Mixed (same ratio) Mixed (different ratio) r 그림 11. SPECTF 유효성판별식의 r 과결정경계형태에따른정확도 차이 4.5. IONOSPHERE 12 IONOSPHERE. 5 93%. 5 IONOPHERE 1 IONOSPHERE Accuracy Iteration 그림 12. IONOSPHERE 학습중의정확도변화. IONOSPHERE 80%

30 CVLS. 표 5. IONOSPHERE 에대한테스트정확도비교 분류기 평균정확도 (%) 표준편차 SVM (Pearson VII kernel) AdaBoost ( 반복횟수 =50) CVLS Random Forest ( 트리수 =50) Decision Tree (C4.5) knn (k=1) Naive Bayes IONOSPHERE. IONOSPHERE Hypercube (Avg Length: ) Hypersphere (Avg Length: ) Sum (Avg Length: ) Frequency Subpatten Length 그림 13. IONOSPHERE 학습완료후서브패턴길이의분포 14 IONOSPHERE SPECTF

31 Accuracy Hypercube 0.92 Hypersphere Mixed (Same Ratio) Mixed (Different Ratio) R 그림 14. IONOSPHERE 유효성판별식의 r 과결정경계형태에따른정확도 차이 4.6. Wisconsin Diagnostic Breast Cancer (WDBC) 15 WDBC. 5 95% WDBC Accuracy Iteration 그림 15. WDBC 학습중의정확도변화

32 6 WDBC. Naive Bayes 92%. IONOSPHERE CVLS. 표 6. WDBC 에대한테스트정확도비교 분류기 평균정확도 (%) 표준편차 SVM (Pearson VII kernel) AdaBoost ( 반복횟수 =50) Random Forest ( 트리수 =50) CVLS knn (k=1) Decision Tree (C4.5) Naive Bayes WDBC. WDBC

33 Frequency Hyperrect (Avg Length: ) Hypersphere (Avg Length: ) Sum (Avg Length: ) Subpattern Length 그림 16. WDBC 학습완료후서브패턴길이의분포 17 WDBC Hypercube Hypersphere Mixed (Same Ratio) Mixed (Different Ratio) Accuracy r 그림 17. WDBC 유효성판별식의 r 과결정경계형태에따른정확도차이

34 CVLS. IONOSPHERE WDBC. CVLS. SONAR SPECTF Naive Bayes 60% CVLS. Naive Bayes Naive Bayes. CVLS..,

35 , Accuracy SPECTF SONAR IONOSPHERE WDBC Number of subpatterns per training pattern 그림 18. 학습패턴당서브패턴의수에따른테스트정확도의변화

36 . 5.1.,.... UCI Machine Learning Repository

37 5.2. CVLS

38 [1] S. Kim, S.-J. Kim, and B.-T. Zhang, Evolving hypernetwork classifiers for microrna expression profile analysis, IEEE Congress on Evolutionary Computation (CEC 07), pp , 2007 [2] J.-W. Ha, J.-H. Eom, S.-C. Kim, and B.-T. Zhang, Evolutionary hypernetwork models for aptamer-based cardiovascular disease diagnosis, The Genetic and Evolutionary Computation Conference (GECCO 07), pp , [3] S. Kim, M.-O. Heo, and B.-T. Zhang, Text classifiers evolved on a simulated DNA computer, IEEE Congress on Evolutionary Computation (CEC 06), pp , [4] J.-K. Kim and B.-T. Zhang, Evolving hypernetworks for pattern classification, IEEE Congress on Evolutionary Computation (CEC 07), pp. 1856~1862, [5] A. Wojna, Combination of Metric-Based and Rule-Based Classification, Lecture Notes in Artificial Intelligence, vol. 3641, pp , [6] A. Asuncion and D.J. Newman, UCI Machine Learning Repository [ Irvine, CA: University of California, School of Information and Computer Science, [7] J. Hong, I. Mozetic, and R. S. Michalski, AQ15: Incremental learning of attribute-based descriptions from examples, the method and user's guide, In Report ISG 85-5, UIUCDCS-F , Dept. Comp. Science, University of Illinois at Urbana-Champaign, [8] P. Clark and T. Niblett, The CN2 induction algorithm, Machine Learning, 3: , [9] W. Cohen, Fast effective rule induction, Proc International Conference on Machine Learning (ICML 95), pp , Tahoe City, CA, [10] J. R. Quinlan and R. M. Cameron-Jones, FOIL: A midterm report, Proc European Conference on Machine Learning, pp. 3-20, Vienna, Austria, [11] B. Liu, W. Hsu, and Y. Ma, Integrating Classification and Association

39 Rule Mining, Proc International Conference on Knowledge Discovery and Data Mining (KDD 98), pp , New York, NY, [12] W. Li, J. Han, and J. Pei, CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules, Proc International Conference on Data Mining (ICDM 01), pp , San Jose, CA, [13] X. Yin and J. Han, CPAR: Classification based on Predictive Association Rules, Proc SIAM International Conference on Data Mining (SDM 03), pages , San Francisco, CA, [14] F. Thabtah, P. Cowling, and Y. Peng, MCAR: Multi-class Classification based on Association Rule, Proc. 3rd ACS/IEEE International Conference on Computer Systems and Applications, Cairo, Egypt, pp , [15] R. Agrawal and R. Strikant, Fast algorithms for mining association rules in large databases, Proc. 20th Intermatonal Conference on Very Large Databases, pp , Santiago, Chile, [16] J. Han, J. Pei, and Y. Yin, Mining frequent patterns without candidate generation, Proc ACM-SIGMOD International Conference on Management of Data (SIGMOD 00), pages 1-12, Dallas, TX, [17] J. R. Quinlan, Induction of decision trees, Machine Learning, 1:81-106, [18] J. R. Quinlan, C4.5: Programs for Machine Learning, Morgan Kaufmann, 1993 [19] L. Breiman, J. Friedman, R. Olshen, and C. Stone, Classification and Regression Trees, Wadsworth International Group, [20] J. Han and M. Kamber, Data Mining: Concepts and Techniques, Morgan Kaufmann, [21] Y. Freund and R. E. Schapire, A Short Introduction to Boosting, Journal of Japanese Society for Artificial Intelligence, 14(5): , [22] J.-K. Kim, B.S. Kim, O.H. Kwon, S.K. Hwang, J.-W. Ha, C.-H. Park, D.J. Chung, C.H. Lee, J. Park, and B.-T. Zhang, A DNA computing-inspired silicon chip for pattern recognition, Preliminary Proceedings of the 13th International Meeting on DNA Computing (DNA13), pp. 373, [23] R. Caruana and A. Niculescu-Mizil, An empirical comparision of supervised learning algorithms, Proc. 23th International Conference on Machine Learning (ICML 06), pp ,

40 [24] I. H. Witten and E. Frank, Data Mining: Practical machine learning tools and techniques, 2nd Edition, Morgan Kaufmann, San Francisco, [25] B. Uestuen, W.J. Melssen, and L.M.C. Buydens, Facilitating the application of Support Vector Regression by using a universal Pearson VII function based kernel, Chemometrics and Intelligent Laboratory Systems, vol. 81, pp ,

41 ABSTRACT Joo-Kyung Kim School of Computer Science and Engineering The Graduate School Seoul National University Rules generated by the rule-based classifiers are easily interpreted and we can directly control those with lower relevancy to classification. However, most current rule-based classifiers can only show locally optimized solution and decision boundary is represented only as a set of hypercubes which are parallel to axes of input space. In this paper, we introduce a subpattern-based classification model to overcome limits mentioned above. A subpattern is a subset of randomly selected attributes from each training pattern. After generated randomly, subpatterns will either remain or be substituted according to its fitness values. Because many combinations of subpatterns are tested in this process, the accuracy of the solution can be better than locally optimized solutions. Moreover, the proposed model allows both hypercubes and hyperspheres as the shapes of decision boundaries, and therefore it can represent various forms of decision boundaries. The proposed model demonstrated competitive accuracy with the UCI data, showing high accuracy with relatively high complexity issues especially. Keywords : rule-based classification, decision boundary, subpattern, random sampling Student Number :

<313120C0AFC0FCC0DA5FBECBB0EDB8AEC1F2C0BB5FC0CCBFEBC7D15FB1E8C0BAC5C25FBCF6C1A42E687770>

<313120C0AFC0FCC0DA5FBECBB0EDB8AEC1F2C0BB5FC0CCBFEBC7D15FB1E8C0BAC5C25FBCF6C1A42E687770> 한국지능시스템학회 논문지 2010, Vol. 20, No. 3, pp. 375-379 유전자 알고리즘을 이용한 강인한 Support vector machine 설계 Design of Robust Support Vector Machine Using Genetic Algorithm 이희성 홍성준 이병윤 김은태 * Heesung Lee, Sungjun Hong,