Weka-決定木の応用

目次

データマイニングの中でよく使用されるアルゴリズムである決定木をEclipseで動かしてみよう

• 決定木とは？ • エントロピーによる分類 • サンプルコードの実行 • 新しいデータの評価

決定木のアルゴリズム

1. 全てのデータに対して、１つの属性値を選びそれによってクラスを分類する

2. １の結果によってデータを枝分かれにする 3. 分類した結果が、全てYes又は全てNoになる

まで１、２を続ける

属性と属性値の組合せの良し悪し

• 決定木は、属性による分類を繰り返す事で、そのデータがどのクラスに属するかを決定するので、属性値によってデータが良く分離される属性を選んだほうが良いといえます

どのように分類するか？

• そこで、よく分離されるかどうかを示す指標として平均情報量（エントロピー）を用いる。

• データをN個のクラスに分類する場合、エントロピーIは以下のように定義される

エントロピーによる木の生成

• diabetes.arffはデータの数が多いので、以下のボールのデータを使って計算をしてみましょう

No size color weight Rubber? Result(bounces?)

1 Small Green Light Yes Yes

2 Small Blue Medium No No

3 Medium Red Medium No No

4 Small Red Medium Yes Yes

5 Large Green Heavy Yes Yes

6 Medium Blue Heavy Yes No

7 Medium Green Heavy Yes No

8 Small Red Light No No

エントロピーの計算

• ８のデータのうち、bouncesがyesであるデータは３つ、noであるデータは５つなので最初の状態のエントロピーは以下のようになる

𝐼38

,58

=38𝑙𝑙𝑙2

83

+58𝑙𝑙𝑙2

85

≅ 0.954

評価値の計算

各属性について比率とエントロピーをかけたものの総和を評価値(disorder)として求めます

• SIZE

• 48

24𝑙𝑙𝑙2

42

+ 24𝑙𝑙𝑙2

42

+ 38

03𝑙𝑙𝑙2

30

+ 33𝑙𝑙𝑙2

33

+ 18

11𝑙𝑙𝑙2

11

+01𝑙𝑙𝑙2

10

=48

× 1 +38

× 0 +18

× 0 = 0.5

No size … Bounces?

1 Small Yes

2 Small No

3 Medium No

4 Small Yes

5 Large Yes

6 Medium No

7 Medium No

8 Small No

SIZE

Yes:2 No:2 Yes:1 No:0 Yes:0 No:3

small medium

large

評価値の計算

• COLOR

• 38

23𝑙𝑙𝑙2

32

+ 13𝑙𝑙𝑙2

31

+ 28

02𝑙𝑙𝑙2

20

+ 22𝑙𝑙𝑙2

22

+ 38

13 𝑙𝑙𝑙2

31 +

23 𝑙𝑙𝑙2

32 ≅ 0.3443 + 0 + 0.3443 ≅ 0.689

No color … Bounces?

1 Green Yes

2 Blue No

3 Red No

4 Red Yes

5 Green Yes

6 Blue No

7 Green No

8 Red No

COLOR

Yes:2 No:1 Yes:1 No:2 Yes:0 No:2

green blue

red

評価値の計算

• WEIGHT

• 28

12𝑙𝑙𝑙2

21

+ 12𝑙𝑙𝑙2

21

+ 38

13𝑙𝑙𝑙2

31

+ 23𝑙𝑙𝑙2

32

+ 38

13 𝑙𝑙𝑙2

31 +

23 𝑙𝑙𝑙2

32 ≅ 0.2500 + 03443 + 0.3443 ≅ 0.939

No weight … Bounces?

1 Light Yes

2 Medium No

3 Medium No

4 Medium Yes

5 Heavy Yes

6 Heavy No

7 Heavy No

8 Light No

WEIGHT

Yes:1 No:1 Yes:1 No:2 Yes:1 No:2

Light Medium

Heavy

評価値の計算

• Rubber

• 58

35𝑙𝑙𝑙2

53

+ 25𝑙𝑙𝑙2

52

+ 38

03𝑙𝑙𝑙2

30

+ 33𝑙𝑙𝑙2

33

≅ 0.6068 + 0 ≅ 0.607

No Rubber? … Bounces?

1 Yes Yes

2 No No

3 No No

4 Yes Yes

5 Yes Yes

6 Yes No

7 Yes No

8 No No

Rubber

Yes:3 No:2 Yes:0 No:3

Yes No

対数の計算について

• 対数の計算はgoogle電卓を使うと便利かもし

れません。検索キーワードの欄に数式を入れてみましょう

識別力の評価

• 最初の状態のエントロピーから、それぞれの評価値を引いたものを識別力（情報ゲイン、Information gain）といい、この値が最も高い属性で分類する

属性 元のエントロピー 評価値 識別力

Size

0.954

0.5 0.454

Color 0.689 0.265

Weight 0.939 0.015

Rubber 0.607 0.347

識別力の評価

• 木の第一段階が決定しました

SIZE

? Yes No

small medium

large

No color weight Rubber? Result(bounces?)

1 Green Light Yes Yes

2 Blue Medium No No

4 Red Medium Yes Yes

8 Red Light No No

評価値の計算 • Sizeがsmallであったデータについて再び計算します

• Color

• 14

11𝑙𝑙𝑙2

11

+ 01𝑙𝑙𝑙2

10

+ 14

01𝑙𝑙𝑙2

10

+ 11𝑙𝑙𝑙2

11

+ 24

12 𝑙𝑙𝑙2

21 +

12 𝑙𝑙𝑙2

21 = 0.5

color … bounces?

Green Yes

Blue No

Red Yes

Red No

COLOR

Yes:1 No:0 Yes:1 No:1 Yes:0 No:1

green blue

red

評価値の計算 • Weight

• 24

12𝑙𝑙𝑙2

21

+ 12𝑙𝑙𝑙2

21

+24

12𝑙𝑙𝑙2

21

+ 12𝑙𝑙𝑙2

21

+ 0 = 1.0

weight … bounces?

Light Yes

Medium No

Medium Yes

Light No

WEIGHT

Yes:1 No:1 Yes:0 No:0 Yes:1 No:1

Light Medium

Heavy

評価値の計算 • Rubber

• 24

22𝑙𝑙𝑙2

22

+ 02𝑙𝑙𝑙2

20

+24

02𝑙𝑙𝑙2

20

+ 22𝑙𝑙𝑙2

22

= 0

Rubber? … bounces?

Yes Yes

No No

Yes Yes

No No

Rubber

Yes:2 No:0 Yes:0 No:2

yes no

識別力の評価

• 同様に識別力の評価を行うが、ここで使用するエントロピーは、Sizeがsmallであるときの値を使用する

属性 Size=smallのエントロピー

評価値 識別力

Color 1.000

0.500 0.500

Weight 1.000 0.000

Rubber 0.000 1.000

識別力の評価

• 木の第二段階が決定しました

• 全てのデータに対し、うまくyes/noに分類できたので、ここで終了

SIZE

Yes No

small medium

large

Rubber?

Yes No

no yes

決定木ー例２

• Wekaを起動してdiabetes.arff(インディアンの糖尿病に関するデータ)の決定木を作ってみましょう

• Where it is? • In my PC, C:¥Program Files (x86)¥Weka-3-7¥data

データの読み込み

Open fileをクリックして、wekaをイ

ンストールしたところにあるdataフォルダからdiabetes.arffを選択

アルゴリズムの選択

アルゴリズムはtreeの中にあるRandomTreeを選択します

データマイニングの実行

Startをクリックし、

結果が表示されたら右クリックしてVisualize treeをクリックします

決定木の表示

• なにこれっ！？

なぜごちゃごちゃした木になるのか？

• 今の木は、ランダムで分類する属性を選んだため非効率な木ができてしまいました。

• わかりやすい木にするにはどうしたらいいでしょうか？

J48との比較

• このようにエントロピーを利用するとノードが少なくなり、見やすい木を生成できます

• この手法を応用したアルゴリズム、J48を使ってdiabetes.arffを分類し、RandomTreeでできた木と比較してみましょう

実行例

EclipseでWekaのAPIを呼び出す

EclipseでWekaを呼び出せるようにするには？

• WekaはJavaで開発されているので、自分で作ったプログラムからWekaのAPI（Wekaの製

作者が用意したクラスやメソッド等）を呼び出すことができます

• さっそくEclipseを起動しましょう

EclipseでWekaを呼び出せるようにするには？

• 適当な名前でJavaプロジェクトを作ります 画像はWekaProjectにしています

EclipseでWekaを呼び出せるようにするには？

プロジェクトフォルダを右クリックし、 ビルド・パス→ ビルドパスの構成と開いていきます

EclipseでWekaを呼び出せるようにするには？

• 図のような画面が出るので、外部jarの追加をクリックします

EclipseでWekaを呼び出せるようにするには？

• Wekaをインストールしたところにあるweka.jarを選択して開きます

EclipseでWekaを呼び出せるようにするには？

• ライブラリーの欄にweka.jarが表示されていれば成功です。OKを押して閉じます

EclipseでWekaを呼び出せるようにするには？

• プロジェクトの欄からもweka.jarが追加されていることがわかります

※weka.jarの場所を変更した場合は追加し直す必要があります

サンプルコードの実行

• 参考資料からJ48Test.javaをダウンロードして実行してみましょう

※作成したball.arffをコピーしてプロジェクト直下に置くこと

実行結果

ball.arffの解析結果が出力されました

プログラムの流れ

データの読み込み・クラスの設定 ↓

（フィルターの設定） ↓

アルゴルズムの設定 ↓

結果の評価

データの読み込み

データを読み込みます。 Instancesは扱うデータの集合の情報をもつクラスです 読み込んだ後にインデックス（何を出力するか）を設定します

DataSource source = new DataSource(“ball.arff"); Instances data = source.getDataSet(); data.setClassIndex(data.numAttributes() - 1);

フィルターの設定

データの属性を減らしたり、値を補正する場合はフィルターの設定をします。 今回の例では設定をしていません

アルゴリズムの設定

• フィルターの設定ができたら、アルゴリズムの指定をしてデータマイニングを行います

• アルゴリズム毎にクラスが用意されています J48 j48 = new J48(); j48.buildClassifier(data);

結果の評価

• マイニングの具体的な評価を見たい時はEvaluationクラスを呼び出して出力します

Evaluation eval = new Evaluation(data); eval.evaluateModel(j48, data); System.out.println(eval.toSummaryString()); System.out.println(eval.toClassDetailsString()); System.out.println(eval.toMatrixString());

木の図示

• 木のビジュアライズをするTreeVisualizerクラスを使うことで木の図示も可能です

木の図示

図示する木の情報やノードの設定をしてフレームに載せます TreeVisualizer tv = new TreeVisualizer(null, j48.graph(), new PlaceNode2()); jf.getContentPane().add(tv, BorderLayout.CENTER); jf.setVisible(true); tv.fitToScreen();

決定木からルールを取り出す

• 生成した木からルールを抽出し、新しく得られたボールのデータを評価してみましょう

J48クラスのtoSourceメソッドを使う

• J48クラスには、Javaコード形式のIF-THEN形式のルールを出力するtoSourceメソッドがあります

String source =j48.toSource(クラス名);

ルールを出力するコード // 生成するjavaファイル名 String className = "BallBounceRule"; // javaコードの生成 String cl = j48.toSource(className); // ファイルの生成(同じフォルダに出力) PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter( new File("src/" + className + ".java")))); // ファイルにルールを書き込む pw.println(cl); // ファイルを閉じる pw.close();

実行結果

• プログラムを実行するとソースフォルダにBallBounceRule.javaというのが作成されています

実行結果

• Eclipse上でも確認できます。

表示されていない場合は、 パッケージを右クリックして リフレッシュを押す

C:¥Huang-Start2011¥java2012¥WekaTester¥src

生成されたクラス class BounceBallRule { public static double classify(Object[] i) throws Exception { double p = Double.NaN; p = BounceBallRule.N1100d7a0(i); return p; } static double N1100d7a0(Object []i) { double p = Double.NaN; if (i[3] == null) { p = 0; } else if (i[3].equals("Yes")) { p = 0; } else if (i[3].equals("No")) { p = 1; } return p; } }

革製かどうかによる分類

ルールクラスの使い方

• 新しいデータの値を引数にして、classifyメソッドを呼び出します

図は、Size:Small, Color:Blue, Weight:Light, Rubber:Yes というボールの情報を設定

Object[] data = new Object[] { "small", "Blue", "Light", "Yes" };

新しいデータの評価 • さっそく新しいデータを評価してみましょう

演習 C:¥Program Files (x86)¥Weka-3-7¥data You can try all different dataset in this folder Please try weather.arff

1. Please submit your Midterm-project to Runhe Huang (rhuang@hosei.ac.jp) by 9th Jan. 21:00pm 2014 2. Check your program on 10th Jan. in class 2014

3. 17th Jan. 2014(1時限目、W213) 期末試験 を頑張ってくださ

い！ Do not miss the final exam.

Midterm-project と期末試験について