Enjoy Data Mining!

決定木から分類ルール集合への変換

マイニング手法（決定木）, マイニング手法（ルール生成）, Weka | 22:14

決定木は，根から葉に至る経路が条件分岐からなっていて，訓練データのデータを葉に割り当てていく上で尤もらしくなる過程を表しています．

この過程を用いて，節と枝に与えられら属性と関係演算子と値を組み合わせて条件節，葉に割り当てられたクラスを結論節とする分類ルールが生成できます．

１つの決定木から得られるルールは，葉に至るパスの数だけの分類ルールとなります．

ただし，分類ルール集合となった場合は，適用順が決定木とは異なるので，決定リスト?として適用順（競合解消?）を考えなければなりません．

決定リストでは，各ルールの確かさをもって事前にルールの適用順を決めておくこととなります*1．

決定木・分類ルール集合・決定リスト

決定木から分類ルールへの変換は，木構造を深さ優先でトラバースすることによって得られます．

決定木，決定木のテキスト表示，if-then-elseで書き下したテキスト表示（決定リスト）の関係を書くと下図のようになります．

単純に木構造を深さ優先で辿ると，図の左の枝からたどることになります．予測時に何らかの競合解消戦略を用いて，未知データに適用するルールを決定する場合は，単純に分類ルール集合としても問題ありません．

しかし，もし，この枝の誤分類が多いと，決定リストとした場合に最初に適用される分類ルールも誤分類が多くなります．そのため，分類ルールの確かさを返還時に確かめながら決定リストを作成する必要があります．

WekaのJ4.8の出力をルール集合形式に変換

下のスクリプトは，Wekaに実装されたJ4.8のテキスト出力をPARTと呼ばれる分類ルール集合によるテキスト表示と同等に出力するPerlスクリプトです．

(3.4系の時期に作ったスクリプトなので，バグがあるかもしれません．）

#! /usr/bin/perl

$J48 = 'weka.classifiers.trees.J48';

$Delimiter=',';
$Unknown = '?';

main();

sub main(){

  my $training="";
  my $test="";
  my $output="";
  my $java="";
  my $weka="";
  my $tmp="./";

  for(my $i=0; $i<@ARGV; $i+=2){
    if($ARGV[$i] eq "-t"){
      $training = $ARGV[$i+1];
    }
    elsif($ARGV[$i] eq "-test"){
      $test = $ARGV[$i+1];
    }
    elsif($ARGV[$i] eq "-o"){
      $output = $ARGV[$i+1];
    }
    elsif($ARGV[$i] eq "-java"){
      $java = $ARGV[$i+1];
    }
    elsif($ARGV[$i] eq "-weka"){
      $weka = $ARGV[$i+1];
    }
    elsif($ARGV[$i] eq "-tmp"){
      $tmp = $ARGV[$i+1];
    }
    else{
      print "usage: J48Rules.pl -t <training_file> -o <output_file> -java <JVM> -weka <shomewhere/weka.jar>\n";
      exit;
    }
  }

  if($test !~ /(.+)/){
    $test = $training;
  }

  my $t_output = "$tmp\/";
  if($training =~ /(.+)\/(.+)\.arff/){
    $t_output .= "$2";
  }
  elsif($training =~ /(.+)\.arff/){
    $t_output .= "$1";
  }
  else{ $t_output .= 'tmp'; }

  my $text_output = "$t_output".'_J48.txt';
  my $model = "$t_output".'.model';
  my $predictions = "$t_output".'.pre';

  # execute J4.8
  system("$java -cp $weka $J48 -t $training -T $test -d $model > $text_output");
  system("$java -cp $weka $J48 -T $test -l $model -p first-last > $predictions");

  # convert tree to ruleset
  my @ruleset = convertTree2Ruleset($text_output);

  open(OUT,">$output") || die "Can't open output=$output\n";
  print OUT "\nJ4.8 ruleset\n";
  print OUT "------------------\n\n";

  foreach my $rule (@ruleset){
    print OUT "$rule\n";
  }
  close(OUT);
}

sub convertTree2Ruleset( $ ){

  my($tree_file)=@_;

  my @result = ();

  my @stack = ();
  my $isTree = 0;

  open(TREE,"$tree_file") || die "Can't open $tree_file\n";
  while(<TREE>){
    chomp();
    if($_ =~ /J48 (.+) tree/){
      $isTree=1;
    }
    elsif($isTree == 1 && $_ =~ /Number of Leaves/){
      last;
    }
    elsif($isTree == 1){
      #print "$_\n";
      if($_ =~ /((\|   )+)(.+) (=|\>|\<=) (.+):\s+(.+)\s+\((.+)\)/){
	my $rule = "";
	for(my $i=0; $i<@stack; $i++){
	  $rule .= "$stack[$i]\n";
	}
	my $t = "$3 $4 $5: $6 ($7)";
	$rule .= "$t\n";
	#print "$rule\n";
	push(@result,$rule);
      }
      elsif($_ =~ /(.+) (=|\>|\<=) (.+): (.+) \((.+)\)/){
	my $rule = "$_\n";
	push(@result,$rule);
      }
      elsif($_ =~ /((\|   )+)(.+) (=|\>|\<=) (.+)/){
	my $numPop = 0;
	for(my $i = $#stack; $i >= 0; $i--){
	  if($stack[$i] =~ /$3/){
	    $numPop = $#stack - $i +1;
	    last;
	  }
	}
	for(my $i=0; $i<$numPop; $i++){
	  pop(@stack);
        }
	my $clause = "$3 $4 $5";
	push(@stack,$clause);
      }
      elsif($_ =~ /(.+) (=|\>|\<=) (.+)/){
	my $numPop = 0;
	for(my $i = $#stack; $i >= 0; $i--){
	  if($stack[$i] =~ /$1/){
	    $numPop = $#stack - $i +1;
	    last;
	  }
	}
	for(my $i=0; $i<$numPop; $i++){
	  pop(@stack);
        }
	my $clause = "$1 $2 $3";
	push(@stack,$clause);
      }
      else{ next; }
      #print "@stack\n";
    }
    else{ next; }
  }
  close(TREE);

  return @result;

}

分類ルール（if-thenルール）学習

マイニング手法（ルール生成） | 01:21

分類ルール?の獲得は，人工知能研究において古くから行われてきた研究の一つです．

分類ルールはif-then形式で得られ，プロダクションシステムのように，if-then-elseの予測過程を繰り返すことで未知データへの予測を行うことでシステムに知的な振る舞いを与えるために用いられてきました．このような，古くからある分類ルール（if-thenルール）獲得では，訓練データの扱いは現在の機械学習と比べて暗黙的だったり，順番を仮定するなど，多種多様でした．

その中でも，属性（説明変数）間は独立であり順序関係を規定しなくてもよく，訓練データ（インスタンス）の入力順に左右されないアルゴリズムがデータマイニングでも用いられます．さらに，90年代以降，計算機の計算やデータ蓄積量の増大に伴って，相関ルール生成を応用した分類ルール学習アルゴリズムなどが開発されてきました．以上のような分類学習アルゴリズムは，訓練データ中に含まれる正例と負例を分割する属性-値ペアを条件節とする分類ルール集合を生成し，ルール集合全体で未知データの予測を行います．それぞれのルールを学習する際，他のルールのデータ分割状況に関係しないことから，このアプローチを分離統治?（separate-and-conqure）と呼びます．

また，他の分類器?，例えば決定木?をif-then形式のルール集合に変換する手法も，基となる分類器学習アルゴリズムの開発と共に行われてきました．

他の形式の分類器を分類ルールに変換する利点は，計算コストが低い分類器学習アルゴリズムが利用可能であることに加えて，ルールの記述が「もし○○が××であれば，△である」という簡潔な記述が人間の利用者にも分かりやすい，とされるためです．ただし，他の形式からの変換過程で，元の分類器の特徴（予測過程の簡潔さや同時並行で起こる相互作用）が失われることも考慮しておく必要があります．このため，変換後のルール集合の予測精度は元の分類器に劣ることもしばしばあります．

分類ルール（集合）の学習

separate-and-conqureのアプローチによるルール学習?では，属性-関係演算子-属性値から成る条件節?を用いて，訓練データを分割していきます．このとき，なるべく負例を含まないように条件節を設定していきますが，負例の含有度合いをどのような指標で計測するかは，ルール生成アルゴリズムの差異となることもあります．元々，正例と負例の1クラス問題を扱うアルゴリズムでも，クラス値毎に正例を設定するマルチプレクサ処理によって多クラス問題に適用することができます．このアプローチでは，各ルールの初期状態と条件節によって含むデータの増減を決める方法によって，いくつかに類型化されます．

初期状態	条件節の操作
各データをルール化したもの	削除・併合
空	追加
ランダム	追加・削除

以上の類型から，１つの類型によるもの，あるいは２つ以上の類型を組み合わせたアルゴリズムがそれぞれ開発されてきました．ルールの併合は，同じ条件節（特に数値属性）のルールがある場合，関係演算子を用いて区間やグループとしていく操作です．削除は，条件節をルールから除去しても負例を含まない（含んでも許容範囲）場合に，ルールの条件部から条件節を削除していく操作です．追加は，訓練データの属性と属性値群（数値属性では区間）から，ある関係演算子を用いて条件節を作成してルールの条件部に追加していく操作です．このように，条件部に条件節を追加・削除していく操作は，属性空間中に仕切り線を引いていく探索問題とも考えることができ，様々な探索戦略が適用できます．代表的なものに，各データからルール生成を始める方法（AQファミリーなど），空状態からルール作成を始める方法（C-Aprioriなど），ランダムな初期状態のルール集合に遺伝的アルゴリズム(GA)を適用する方法があります．ただし，属性空間中の仕切り線探索は，非常に組み合わせ数が多く，計算コストがかかり，その状況下で適度な汎化性能が求められるため，探索の効率化という研究的な側面も残されています．

他の分類器に基づく方法では，決定木のルートから葉に至る分岐を条件節として，結論部を葉とする変換方法があります．また，ニューラルネットワークなど，予測過程が複雑な分類器の特徴をルールとして，ルール集合に変換する方法も研究されてきました．

分類ルール（集合）による予測

データから分類ルールを得る手法を適用すると，通常はルール集合が得られます．このため，未知（テスト）データのクラスを予測するためには，まず始めに分類予測に用いるルールをルール集合の中から決定する必要があります．このルール集合からのルールの決定を競合解消と呼び，この決め方を競合解消戦略と呼びます．競合解消戦略は，条件部の長い特殊なルール優先，負例の含有を許した場合は訓練段階においての信頼性優先などの戦略が用いられます．

また，予測を繰り返す過程で各ルールの重み付けを変更するルールベースマネジメント手法の適用も行われることもあります．このような過程で，決定木から変換されたルールなどは，元の分類器での適用順と異なる順でルールが適用されることになります．

競合解消を行って選ばれたルールによって，未知データの属性-値と条件節が照合され，ルールの示す結論が予測として出力されます．順位の高いルールが適合しなかった場合は，次のルールが適用されます．この繰り返しは，if-then-elseの連鎖となります．

しかし，未知データの値域が異なる場合，各ルールの条件節が極端に少ない場合など，全てのルールが適合しない自体が生じます．これを防ぐため，訓練データで最も割合の多いクラスを無条件に適用するデフォルトルールを用いるなどの方策が採られます．

決定木の基本的な考え方

マイニング手法（決定木） | 22:50

マイニング手法としてクラス（質的な目的変数）を分類予測するとき，よく用いられる手法として決定木があります*1．

データマイニングというと決定木という印象をもっている方も多いことと思います．

決定木は，分類予測に至る道筋を一意に表現できるため，その了解性は非常に高いと言えます．

決定木の学習

決定木学習は，訓練データを属性-値の組で分けていく過程を木構造で表される分類器とするものです．

ある分割指標を用いて，入力された訓練データを分割して，さらに分割されたデータで指標を計算して...と繰り返し，小さいデータに分割と指標の計算が適用されます．

この仕組みを分割統治（divide and conquer）と呼びます．

シンプルに決定木学習の動作を挙げると以下のようになります．

1. データ分割指標の計算
2. データ分割基準（節）の作成
3. 分割したデータの作成

決定木学習では，上記の1〜3を再帰的に繰り返して，終了条件を満たすまですべての訓練データから分割データを作成していきます．

終了条件は，分割したデータのデータ数や分割指標に閾値を用います．もちろん，クラスが一意になれば，終了です．

終了条件を満たしたデータは，”葉”にあたります．

ここで，それぞれの決定木学習アルゴリズムで異なるのは，データ分割指標と分割基準の選択および作成方法です．

決定木学習では，データを分割することによって，分割対象データが分割後にクラスの偏りが大きくなるようにします．

これが，ID3/C4.5では情報利得（比）であり，CARTではジニ係数であったりします．

データ分割基準の選択と作成では，属性値の扱いでアルゴリズム毎に相違があります．

数値属性に対しては，何回分割基準として用いるか，あるいは，どのような関係演算子を用いるか，が考えるべき点となります．

離散属性に対しては，複数の離散値ごとに分岐を作成するか，グループとするか，も異なります．

また，欠損値の扱いはどのようなデータ分割指標を用いるか，によっても異なります．

分割基準（属性と属性値とその関係）のことを”節”と呼びます．

なお，決定木学習ではデータを分割していきますので，葉に近く用いられる分割基準（属性）ほど説明力が小さくなります．

この説明力の小さい分割基準が汎化性能を低下させる過学習（over-fitting）を防ぐため，「枝刈り」という操作が必要となります．

決定木による予測

決定木が学習できると，ルートの分割基準から順にテストデータの属性と値に基づいて分岐をたどっていき，葉に割り当てられたクラスを予測クラスとします．

決定木による予測では，どの基準が当てはまるか，一意に決まりますので，if-thenルール集合による予測のような競合解消は生じません．

ただし，テストデータの分割基準にあたる属性の値が欠損していた場合には，作成時に分岐のしやすさを分割後のデータ数の割合などとして与えておき，葉に到達するまでの合計重みなどで予測クラスの確信度とすることもあります．

参考文献

Wileyのオンラインテキスト

分類モデルの選定について

データマイニング概論 | 23:35

何らかのデータがあって，データに基づいて自動的に分類を行いたい場合，分類学習アルゴリズムによる分類予測（識別・判別などと呼ぶこともあり）を行うことが可能です．

このとき，目的によって分類学習アルゴリズムの適用結果である分類モデルの性質に気をつけておくことが必要です．

分類学習アルゴリズムの類型

まず，分類予測に用いられる分類モデル（式，木構造，ルール，ネットワーク）が容易に読解できるかどうか，についての分け方があります．

入力に対して，分類予測結果が計算・出力されるまでの過程を人間が追跡可能なものをここではホワイトボックス型と呼びます．

そうでない分類モデルは，ブラックボックス型と呼ぶことにします．

次に，出力される分類モデルが属性集合で定義される空間において，線形か非線型か，によって分類することもあります．

それぞれの視点から，よく用いられる分類学習アルゴリズムを列挙すると以下のようになります．

• ホワイトボックス・線形*1
  • 決定木
  • 分類ルール学習
  • 判別分析
  • 回帰木
  • 線形回帰
• ホワイトボックス・非線形
  • 事例に基づく学習（k-NNなど）
  • ロジスティック回帰
• ブラックボックス・非線形
  • ニューラルネットワーク
  • サポートベクターマシン(SVM)

分類学習アルゴリズム利用の目的

分類学習アルゴリズムの適用目的は，第一にデータから自動的に分類予測が得られる頑健*2でより正確な分類モデルを得ることです．

また，データマイニングでは，目的変数の分類や識別に関連する属性を分類モデルから得ることも，その適用目的の一つです．

そのため，上記のホワイトボックス型分類モデルは，重要な役割を果たします．

これらのモデルでは，分類予測に関わる属性や属性間の影響の強弱（そもそも要らない属性の特定なども）を比較可能にします．

一方，決定木などは質的な目的変数に対する分類精度（正解率）の高さから，問題によっては，従来，パターン認識としてブラックボックス型の分類学習アルゴリズムが適用されていたようなものでも必要な精度を出すこともあります．

ただし，パターン認識としたほうが相応しい場合に決定木などホワイトボックス型の分類学習アルゴリズムを用いる場合には，前述の目的も含んでいると考えられます．

そのため，これまで分からなかった専門家の着眼点の計測可能化などの利点を付け加えられることが期待できます．

逆に，「便利なツールがあったから」では，提案内容全体の評価まで悪い影響を受けてしまう恐れがあります．

CSVデータの読み込みと書き出し

Weka | 20:31

WekaをMicrosoft Excelなどの表計算ソフトと連携するとき，ファイル形式の不一致が問題になることがあります．

少しずつですが，Wekaで扱えるファイル形式も増えてきていますが，現在のところExcelなどの商用ソフトの独自形式は直接読み込めません．

この場合，CSV(Comma Sepalated Values)ファイルを用いるのが一般的ですので，その方法を紹介します．

準備

以下，用いる記号の意味を列挙します．

• $…コマンドラインの始まり
• <weka.jar>…weka.jarまでのパス
• <input.csv>…CSVファイル名とファイルまでのパス
• <output.arff>…出力とするArff形式のファイル

また，コマンドライン（シェル）からJVMであるjavaが起動することを確認してください．

Weka3.6以上では，SunのJava1.5以上が必要です．以下のように確認してみてください．

$ java -version

CSVファイル→Arffファイルへの変換

CSVファイルからArffファイルへの変換はweka.core.converters.CSVLoaderクラスを用います．

同じパッケージには，WekaのGUIで読み込めるファイル形式のローダーとArffを任意の形式で保存するセーバー(*Saver)の各クラスが用意されています．

このパッケージのクラスは共通で，第一引数にファイル名を必要とし，変換後のファイルは標準出力に出力されます．

そのため，コマンドラインから用いる場合は，リダイレクションを用いて出力ファイルの保存を行います．

コマンドラインでの実行は以下のようになります．

$ java -cp <weka.jar> weka.core.converters.CSVLoader <input.csv> > <output.arff>

Arffファイルの属性情報の調整

CSVファイルを単純にArffファイルに変換しただけでは，特に半角数字だけで表された名義属性（質的な変数）がnumeric（数値属性）として扱われてしまいます．

Arffファイルは，プレーンテキストのファイルなので，テキストエディタやWordで変更が可能です．

しかし，名義属性の値の数がとても多い場合，あるいは全て全自動でスクリプトとした処理に手作業を挟むことは困難です．

そこで，数値属性をweka.filters.unsupervised.attribute.NumericToNominalフィルタを用いて，名義属性に変換します．

このとき，-Rオプションで変換を行う属性番号*1，あるいは属性番号の範囲（1を'first'，最後の属性番号を'last'とすることも可能）を指定します．

例えば，属性番号2の属性が数値属性となっている場合は，以下のように指定します．

• <input.arff>…変換前のArffファイル（上の<output.arff>）
• <output2.arff>…変換後のArffファイル

$ java -cp <weka.jar> weka.filters.unsupervised.attribute.NumericToNominal\
 -R 2 -i <input.arff> -o <output2.arff>

複数の属性を変換する必要がある場合は，-Rの値としてカンマ区切りで属性番号（あるいは'-'の前後で属性番号を指定した範囲）を指定します．

例えば，属性番号”2”と”4から7”の場合は，2,4-7が-Rの引数となります．

または，<output2.arff>を<input.arff>とすることで，逐次変換を行うことも可能です．

全ての属性を範囲として場合は，以下のコマンドです．

$ java -cp <weka.jar> weka.filters.unsupervised.attribute.NumericToNominal\
 -R first-last -i <input.arff> -o <output2.arff>

ただし，全ての変換がうまくいったかどうかは，コマンドの実行主体（ユーザやスクリプト）で判断する必要があります．

また，入力ファイルの状態によって数値属性になってしまうCSVファイルでの変数（列）も生じますので，スクリプト化の際は十分なテストを行う必要があります．