26 Feature Extraction with Randomness for an Application to Machine Learning from Text Data

Size: px

Start display at page:

Download "26 Feature Extraction with Randomness for an Application to Machine Learning from Text Data"

おきみちまきい
5 years ago
Views:

1 26 Feature Extraction with Randomness for an Application to Machine Learning from Text Data

2 Random Forest Random Forest SPAM SPAM600 SPAM1000 SPAM Random Forest i

3 % Random Forest Mersenne Twister Low-Discrepancy ii

4 Abstract Feature Extraction with Randomness for an Application to Machine Learning from Text Data Natsuki Fujimori In text processing, a word vector, which is converted from text document data, is usually used as a feature vector. A word vector is a histogram of word frequency or occurrence of a document. It is a numerical data, however it is not a quantitative data such as ratio scale. It is originally a qualitative data such as ordinal or nominal scale. Some methods for data mining using machine learning employ numeric calculation which can discriminate quantitative data that able to define the distance or inner product of feature vectors, but random forests employing decision trees is machine learning technique which is suitable for qualitative text data because it constructs various shapes of decision trees by choosing predictor values randomly. When choosing predictor values, the random sampling is performed using pseudo-random sequence. However, if the number of tree depth to construct, the number of decision trees to use discriminate, or the number of features predictor values of decision trees are small values, the bias may appear because of non-uniformness of pseudo-random numbers. In order to solve this problem, in this study, we propose an application of quasi-random number generator. quasi-random sequence generates uniform sequence of points. When the number of tree of depth, the number of trees using for discrimination, or the number of features constructing tree are small, the proposed method is able to achieve higher performance than pseudo-random. By using the original Japanese SPAM dataset (600: SPAM, iii

5 1000: non-spam), we perform the experiment of conventional and proposed methods. As a result, under the condition that the maximum number of tree is 2, and that the number of feature is under 10, the proposed method improves 2 or 3 percent of the precision. key words Random Forest, Pseudo-Random Sequence, Mersenne Twister, Low- Discrepancy Sequence, Quasi-Random Sequence iv

6 Bagging Random Forest Random Forest Random Forest Random Forest Python Random Forest v

7 D max = D max = D max = 3 D max = D max = A D max 46 B 6 48 vi

8 Bagging Random Forest Mersenne Twister 1000* Mersenne Twister 10000* SOBOL 1000* SOBOL 10000* Random Forest D max = D max = D max = D max = D max = D max = D max = D max = D max = D max = D max = 2 F max = N max = vii

9 5.14 D max = 2 F max = N max = D max = 2 F max = 1 10 N max = D max = 2 F max = 1 10 N max = D max = 2 F max = N max = D max = 2 F max = N max = rand int SOBOL B B B viii

10 Random Forest A.1 D max = A.2 D max = ix

11 Web Web Weblog Twitter Random Forest Random Forest 1

12 Bagging Random Forest Random Forest Low Discrepancy Sequence Random Forest Random Forest [1],[2] SPAM SPAM Random Forest SPAM [1],[2] Random Forest SPAM Random Forest 2 2

13 3 2 Random Forest 4 Random Forest 5 6 3

14 2 Bagging Random Forest [4]

15 2.1 無料 1 0 出会い 0 1 女性 1 0 HAM SPAM 秘密 HAM 1 0 SPAM HAM 2.1 f f 2 5

16 {x i 1 i N} X Bagging Random Forest Bagging Bagging Leo Breiman 1996 [6] Bagging Bootstrap Aggregating Bagging 6

17 2.2 T 1 T m f 1 (x) f m (x) 2.2 Bagging 学習データブートストラップサンプリングブートストラップサンプル 1 ブートストラップサンプル 2 ブートストラップサンプル m 識別識別識別弱学習器 T 1 T 2 T m f 1 (x) f 2 (x) f m x 弱識別結果弱識別結果弱識別結果多数決識別結果 2.2 Bagging 7

18 2.2 Random Forest Random Forest Random Forest Leo Breiman 2001 [7] Bagging Random Forest d Breiman [5] Bagging 2.3 Random Forest Bagging Random Forest [5] 8

19 2.2 学習データブートストラップサンプリング多様な決定木が並列に並ぶ森 ( 弱学習器群 ) ブートストラップサンプル 1 ブートストラップサンプル 2 ブートストラップサンプル m 識別識別ノードに利用する特徴をランダムサンプリングで d 個選択する識別 T 1 T 2 T m f 1 (x) f 2 (x) f m x 弱識別結果弱識別結果弱識別結果多数決識別結果 2.3 Random Forest 9

20 3 k-means Random Forest 3.1 pseudorandom sequence [9] X n+1 = (A X n + B) mod M (3.1) C 10

21 3.2 M M M Mersenne Twister 1998 [8] M Mersenne Twister [10] Mersenne Twister 1000* * Marsaglia Xorshift [12] XOR scikit-learn Xorshift 3.2 Quasi random numbers Quasi-Monte Carlo method I := {0 x < 1} I n N x i (1 i N) S (f) 1 S N (f) = 1 N 1 i N f (x i ) (3.2) {x i 1 i N} n I n N P N D (P N ) = O ( N 1 (log N) n) 2 1 f 2 D 11

22 3.2 n Low Discrepancy Sequence [9] quasirandom 1 SOBOL SOBOL 1967 I.M. Sobol [11] 3.3 SOBOL 1000* SOBOL 10000*

23 x 3.1 Mersenne Twister 1000* x 3.2 Mersenne Twister 10000*

24 random[,1] 3.3 SOBOL 1000* a[,1] 3.4 SOBOL 10000*

25 4 Random Forest Random Forest Python scikit-learn Random Forest 4.1 Random Forest Random Forest Random Forest 1 Random Forest 15

26 4.2 Random Forest 4.2 Random Forest Xorshift Random Forest Random Forest Random Forest Random Forest 16

27 4.3 Python Random Forest 4.3 Python Random Forest Python scikitlearn Random Forest forest.py Random Forest fit() Random Forest... for i in range(self.n estimators): # (1) seed seed = np.random.randint(max INT) tree = self. make estimator(append=false) # (2) [j, seed] = i4 uniform(0, MAX INT, seed) # (3) tree.set params(random state=j) # tree.set params(random state=random state.randint(max INT)) trees.append(tree)... i4 uniform() sobol seq forest.py 17

28 4.3 Python Random Forest from sobol seq import * (3) rf RandomForestClassifier rf = RandomForestClassifier(n_estimator =num, max_features=feat, max_depth=2) rf.fit(traindata, trainlabel) result = rf.predict(testdata) 実行プログラム RandomForest Classifier 関数を rf に代入訓練データで決定木の森を作成変更点 forest.py 中の fit 関数 for i in range(self.n_estimators): seed = np.random.randint(max_int) tree = self._make_estimator(append=false) # 追加部分 [ j, seed ] = i4_uniform(0, MAX_INT, seed) # j に準乱数生成 # 以下 2 文のどちらかをコメントアウトして乱数を決定 tree.set_params(random_state=j) # 準乱数をセット tree.set_params(random_state= random_state.randint(max_int)) # 疑似乱数をセットテストデータで識別木の深さ : 2 木の深さ :2 識別精度 ( % ) 特徴数 MT? Quasi? 72 識 70 別精 68 度 ( % 66 ) 決定木の数 MT? Quasi? 4.1 Random Forest n estimator max features max depth fit 18

29 4.3 Python Random Forest Random Forest fit Mersenne Twister SOBOL result predict fit scikit-learn Random Forest sklearn/tree Python C Cython tree.so UNIX tree.pyd Windows tree.pyx tree.pxd Cython C tree.c setup.py install.so.pyd tree.pyx rand int rand int xorshift [12] SOBOL SOBOL 19

30 5 Random Forest SPAM 1600 SPAM 600 SPAM 1000 Random Forest ?? Python NumPy scikit-learn SOBOL sobol seq.py SPAM 600 SPAM

31 5.1 OS CPU 5.1 Windows 7 Enterprise 4.00 GB Intel(R) Core(TM) i5-2400s 2.50GHz Python scikit-learn NumPy sobol seq SPAM SPAM 600 SPAM Random Forest Random Forest D max 1, 2, 3, 4, 5 F max 1,2,3,...,10 N max 1,2,3,...,10 D max F max N max

32 5.1 深さ :1 深さ :2 深さ :3 深さ :4 深さ :

33 F max N max 10 D max =

34 5.2 精度が他方より向上した回数各乱数列を適用した際に識別 MT Quasi 決定木の最大深度 D max = D max = 2 D max = 5 24

35 木の深さ :1 識別精度 ( % ) 特徴数 MT Quasi 5.3 D max = 1 木の深さ :1 識別精度 ( % ) 決定木の数 MT Quasi 5.4 D max = 1 25

36 D max = D max = N max %, F max = 8 4.6% %, 4.6% SPAM SPAM D max = D max = N max 1 10 D max = F max = 9 1.8% F max = 3 2.0% 5.6 N max = 2 N max = 9 2.0% N max = % 26

37 5.2 木の深さ : 2 識別精度 ( % ) 特徴数 MT Quasi 5.5 D max = 2 識別精度 ( % ) 木の深さ : 決定木の数 MT Quasi 5.6 D max = 2 27

38 5.2 N max = D max = 3 D max = 4 76 木の深さ :3 識別精度 ( % ) MT Quasi 特徴数 5.7 D max = D max = D max = N max % 1.5% % 3.6% D max = % 1.2% % 1.0% D max =

39 5.2 木の深さ :3 識別精度 ( % ) 決定木の数 MT Quasi 5.8 D max = 3 D max = 4 D max = 4 29

40 木の深さ :4 識別精度 ( % ) 特徴数 MT Quasi 5.9 D max = 4 識別精度 ( % ) 木の深さ : 決定木の数 MT Quasi 5.10 D max = 4 30

41 D max = 1 木の深さ :5 識別精度 ( % ) 特徴数 MT Quasi 5.11 D max = 5 識別精度 ( % ) 木の深さ : 決定木の数 MT Quasi 5.12 D max = 5 31

42 D max = N max % 5.7% % 8.2% D max = 5 D max = F max = Random Forest 10 SPAM A D max =

43 5.2 木の深さ :2, 決定木の数 11~20 識別精度 ( % ) 特徴数 MT Quasi 5.13 D max = 2 F max = N max = 木の深さ :2, 特徴数 :11~20 識別精度 ( % ) 決定木の数 MT Quasi 5.14 D max = 2 F max = N max =

44 木の深さ :2, 決定木の数 :11~20 86 識別精度 ( % ) MT Quasi 特徴数 5.15 D max = 2 F max = 1 10 N max = 木の深さ :2, 特徴数 1~10 識別精度 ( % ) 決定木の数 MT Quasi 5.16 D max = 2 F max = 1 10 N max =

45 5.2 F max N max

46 木の深さ :2, 特徴数 :11~20 識別精度 ( % ) MT Quasi 決定木の数 5.17 D max = 2 F max = N max = 木の深さ :2, 決定木の数 :1~10 識別精度 ( % ) 特徴数 MT Quasi 5.18 D max = 2 F max = N max =

47 rand_int 関数による特徴選択 rand int SOBOL 列による特徴選択 SOBOL 5.19 rand int

48 5.3 SOBOL 0 51 F max = 5, N max = 5, D max = 2 SOBOL SOBOL rand int rand int SOBOL Random Forest 38

49 6 Random Forest Random Forest D max 1 5 F max 1 10 N max 1 10 SPAM 600 SPAM 1000 SPAM D max = 2 F max = 1 9 N max = % 39

50 D max D max = 2 F max = 1 9 N max = 2 10 D max = 2 2 F max N max 1 20 D max = 2 UCI Spambase dataset UCI Machine Learning Repository Spambase dataset % 3% D max = % 3.2% D max = 2, F max = 1 10, N max = 1 10 SOBOL SOBOL Random Forest Random Forest 40

51 Random Forest 41

54 [1] Natsuki Fujimori and Shinichi Yoshida, Comparison of Machine Learning Algorithms for English and Japanese SPAM mail discrimination, The 3rd International Workshop on Advanced Computational Intelligence and Intelligent Informatics, IWACIII 2013, Shanghai, China, October 18-21, ss1-10, [2] Natsuki Fujimori and Shinichi Yoshida, Machine Learning Algorithms applied to SPAM Filtering for English and Japanese , The 14th International Symposium on Advanced Intelligent Systems, ISIS2013, Daejeon, Korea, November 13-16, F3a-1, [3] 2013 [4] 2010 [5] R p [6] Leo Breiman, Bagging Predictors, Machine Learning, 24, pp , [7] Leo Breiman, Random Forests, Machine Learning, 45, pp.5-23, [8] Makoto Matsumoto and Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation (TOMACS) 8.1 (1998), pp [9] 4 p [10] number generation/node6.html. [11] IM Sobol, On the distribution of points in a cube and the approximate evaluation of integrals, USSR Computational mathematics and mathematical physics 7, pp ,

55 [12] George Marsaglia, Xorshift RNGs, Journal of Statistical Software 8(14), pp.1-6,

56 A D max A.1 D max = 1 F max N max

57 A.2 D max = 2 F max N max

58 B 6 精度が他方より向上した回数各乱数列を適用した際に識別 MT Quasi 決定木の最大深度 B.1 48

59 識別精度 ( % ) 木の深さ : 特徴数 MT Quasi B

60 木の深さ :6 識別精度 ( % ) 決定木の数 MT Quasi B

24 SPAM Performance Comparison of Machine Learning Algorithms for SPAM Discrimination

24 SPAM Performance Comparison of Machine Learning Algorithms for SPAM Discrimination 1130378 2013 3 9 SPAM SPAM SPAM SPAM SVM AdaBoost RandomForest SPAM SPAM UCI Machine Learning Repository Spambase 4601