[1] SBS [2] SBS Random Forests[3] Random Forests ii

Size: px

Start display at page:

Download "[1] SBS [2] SBS Random Forests[3] Random Forests ii"

しなつあかさか
8 years ago
Views:

1 Random Forests A Graduation Thesis of College of Engineering, Chubu University Proposal of an efficient feature selection using the contribution rate of Random Forests Katsuya Shimazaki

2 [1] SBS [2] SBS Random Forests[3] Random Forests ii

3 Random Forests Random Forests iii

4 ii 1 Random Forests SFS SBS s r SFFS iv

5 v

6 1.1 Random Forests Random Forests Random Forests ( [5] ) Random Forests ( [9] ) Semantic Texton Forests Random Forests ( [8] ) Hough Forests ( [6] ) SFS SBS fold cross-validation Pendigits Waveform Spambase Optdigits vi

7 Random Forests vii

8 1 Random Forests Random Forests 1.1 Random Forests Random Forests Randomized Forests Randomized Trees, Randomized Deicision Forests Random Forests Random Forests Breiman [3] Bagging[4] Random Feature Selection [5] [6] [7] [8] Random Forests Random Forests 1.1 (Split Node) (Leaf Node) 1

9 t 1 t T 1.1: Random Forests Random Forests Require: : I Require: : T Require: : D Require: T : I = (I 1, I 2,..., I T ). Require: : F Require: : T H 1: For k = 1,..., T 2: I k 3: For l = 1,..., F 4: - f 5: - For m = 1,..., T H 6: 7: t f t I l I r 8: - I l = {i I n f(v i ) < t} 9: - I r = I n \ I l 10: E 11: - E = I l I n l) Ir I n r) 12: if E > E old f, t, I l, I r 13: - end for 14: end for 15: if gain = 0 D 16: - P (c l) 17: 18: else I l, I r end for 2

10 1.1. I T D I = (I 1, I 2,..., I T ) F T H F,T H f t f t Random Feature Selection F T H F T H E E n I n f t 1.1, (1.2) I l I r I l = {i I n f(v i ) < t} (1.1) I r = I n \ I l (1.2) I l I r (1.3) E E = E(I) I l I n E(I l) I r I n E(I r) (1.3) E(I) (1.4)( ) (1.5)( ) E(I) = n p(c i ) log p(c i ) (1.4) i=1 E(I) = n p(c i )(1 p(c i )) (1.5) i=1 p(c i ) c i ( ) 0 l P (c l) 3

11 v P (c l) (P 1 (c l), P 2 (c l),..., P T (c l)) P (c v) P (c v) = 1 T T P t (c l) (1.6) t=1 C i = arg max c i P (c i v) (1.7) 1.2: Random Forests 4

12 Random Forests Amit 1.3(a) Random Forests 1.3(b) [5] 1.3: Random Forests ( [5] ) Lepetit 1.4 Random Forests [9] 5

1.3. 応用例 (a) パッチを学習した RTs (b) 射影変化に頑健な結果図 1.

5 に示すように画像パッチを Semantic Texton Forests Features 特徴量を用いて Random Forests により学習する

visual word とすることにより特徴表現を行うことができこれを用いてセマンティックセグメンテーション画像識別が可能であることを実験により示している

13 1.3. 応用例 (a) パッチを学習した RTs (b) 射影変化に頑健な結果図 1.4: Random Forests を用いた特徴点マッチング (文献 [9] より引用) Shotton 等は図 1.5 に示すように画像パッチを Semantic Texton Forests Features 特徴量を用いて Random Forests により学習する Semantic Texton Forests を提案した [7] Semantic Texton Forests は Moosmann 等の手法と同様にノードを visual word とすることにより特徴表現を行うことができこれを用いてセマンティックセグメンテーション画像識別が可能であることを実験により示している正解画像 A[g] -B[b] > 28 入力画像 A[b] -B[g] > 37 A[r] + B[r] > 363 A[b] + B[b] > 284 A[g] -B[b] > 13 画像パッチ A[b] > 98 A[r] -B[b] > 21 図 1.5: Semantic Texton Forests 6

14 1.3. Shotton 1.6 Random Forests [8] CG 31 2 Random Forests 3 1.6: Random Forests ( [8] ) Gall 1.7 Hough image Hough Forests [6] Hough image Hough Forests 1.7: Hough Forests ( [6] ) 7

15 1.3. [7] [5] [9] [8] [6] 8

16 2 2.1 n d SFS SBS s r SFFS 9

17 n d n C d n d [10] d [10] 2.1 v 1, v 2, v 3 2.1: [%] v 1 7 v 2 14 v 3 21 (v 1, v 3 ) 4 (v 1, v 2 ) SFS Whiteney (Sequential Forward Selection)[11] SFS

18 d v 1,v,...,v 2 n v 1 v 2 v n max v,v,...,v 1 3 n 2.1: SFS SBS SFS Marill (Sequential Backward Selection)[2] SBS

19 2.1. v,v,...,v 1 2 n v,v,...,v v,v,...,v v,v,...,v 2 3 n 1 3 n 1 2 n-1 max v 1,v 3,...,vn v2 2.2: SBS s r Stearns s r [12] SFS SBS k X k 1. X k+s X k SFS s 2. X k+s r X k+s SBS r 3. d = k + s r 1 2 s > r s = 2, r = 1 s r s r s = 1, r = 0 SFS s = 0, r = 1 SBS 12

20 SFFS Pudil SFFS (Sequential Floating Forward Selection)[13] s r s, r SFFS k = 0 1. SFS k k k SBS k = d 1 SFFS SFS SBS 13

21 3 Random Forests 3.1 Random Forests Random Forests C(v d ) (3.1) C(v d ) j d v d S d S (3.1) d 14

22 3.1. v d j T S d S C(v d ) = T t=1 j f(v d ) S t,j j J S t,j 100 (3.1) f(v d ) f (v ) d I n y f (v d ) x I l I r 3.1: 3.2 t 1 t 1 t 1 t 1 v 1 v 2 v 3 v 4 v 5 v 6 C(v 2 ) t 1 v 1 v 2 v 3 v 4 v 5 v 6 C(v 4 ) t 1 v 1 v 2 v 3 v 4 v 5 v 6 3.2: 15

23 Random Forests : Random Forests

24 : 17

25 SBS(Sequential Backward Selection) 10% UCI Machine Learning Repository[14] UCI Machine Learning Repository UCI Machine Learning Repository Pendigits, Waveform, Spambase, Optdigits

26 : Pendigits Waveform Spambase Optdigits Random Forests : Random Forests Pendigits Waveform Spambase Optdigits cross-validation [15] Seymour Geisser K-fold cross-validation K-fold cross-validation N K K K 1 K-fold cross-validation K 19

27 4.2. K K N K 3 3-fold cross-validation 3-fold cross-validation : 3-fold cross-validation SBS 10% 4.2, 4.3, 4.4, 4.5 SBS SBS 20

28 : Pendigits 4.3: Waveform 21

29 : Spambase 4.5: Optdigits 22

30 % : SBS [ ] [ ] [ ] Pendigits (16) Waveform (21) Spambase (57) Optdigits (64) SBS 3 10% : 23

31 4.2. Pendigits SBS 9 Pendigits 38 SBS SBS 24

32 Random Forests 1 Random Forests Random Forests 2 3 Random Forests 2 4 SBS Spambase Optdigits 25

33 SBS SFS 26

34 27

35 [1] vol. 48, no. 16, pp. 1-24, [2] Marill, T, D. M. Green, On the effectiveness of receptors in recognition system, IEEE Trans. Inform. Theory 9, pp , [3] L. Breiman, Random Forests, Machine Learning, vol. 45, no. 1, pp. 5-32, [4] L. Breiman, Bagging Predictors, Machine Learning, vol. 24, no. 2, pp , [5] Y. Amit, G. August and D. Geman: Shape quantization and recognition with randomized trees, Neural Computation, no. 9, pp , [6] Gall, J. and Yao, A. and Razavi, N. and Van Gool, L. and Lempitsky, V., Hough forests for object detection, tracking, and action recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 11, pp , [7] J. Shotton, M. Johnson and R. Cipolla, Semantic texton forests for image categorization and segmentation, Computer Vision and Pattern Recognition, [8] J. Shotton,and A. Fitzgibbon, and Cook, M. and Sharp, T. and Finocchio, M. and Moore, R. and Kipman, A. and Blake, A., Real-time human pose recognition in parts from single depth images, Computer Vision and Pattern Recognition, [9] V. Lepetit and p. Fua, Keypoint recognition using randomized trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 9, pp ,

36 [10],, pp [11] Whitney, A. W, A direct method of nonparametric measurement selection, IEEE Trans. Comput.20,pp , [12] S. D. Stearns: On selecting features for pattern classifies, Proc. Third Internat. Conf. Pattern Recognition, pp , [13] P. Pudil, J. Novovicora and J. Kittler: Floating search methods in feature selection, Pattern Recognition Letters, Vol. 15, No. 11, pp , [14] UCI Machine Learning Repository, [15] Kohavi, Ron: A study of cross-validation and bootstrap for accuracy estimation and model selection,

37 Random Forests ( )

% 2 3 [1] Semantic Texton Forests STFs [1] ( ) STFs STFs ColorSelf-Simlarity CSS [2] ii

% 2 3 [1] Semantic Texton Forests STFs [1] ( ) STFs STFs ColorSelf-Simlarity CSS [2] ii 2012 3 A Graduation Thesis of College of Engineering, Chubu University High Accurate Semantic Segmentation Using Re-labeling Besed on Color Self Similarity Yuko KAKIMI 2400 90% 2 3 [1] Semantic Texton