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

決定木は，根から葉に至る経路が条件分岐からなっていて，訓練データのデータを葉に割り当てていく上で尤もらしくなる過程を表しています．
この過程を用いて，節と枝に与えられら属性と関係演算子と値を組み合わせて条件節，葉に割り当てられたクラスを結論節とする分類ルールが生成できます．
１つの決定木から得られるルールは，葉に至るパスの数だけの分類ルールとなります．
ただし，分類ルール集合となった場合は，適用順が決定木とは異なるので，決定リストとして適用順（競合解消）を考えなければなりません．
決定リストでは，各ルールの確かさをもって事前にルールの適用順を決めておくこととなります*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;

}

*1:それぞれのルールの確かさを示す指標は，数多くありますので，またの機会に書きたいと思います