機械学習

decision tree (決定木) でユーザエージェント判定器を作ってみる

カテゴリ
ブックマーク数
このエントリーを含むはてなブックマーク はてなブックマーク - decision tree (決定木) でユーザエージェント判定器を作ってみる
このエントリーをはてなブックマークに追加

アクセスログのユーザエージェント(UA)からブラウザを判別するのって,みんな何使ってますか?

自分が作ったアクセス解析システムでは HTTP::BrowserDetectHTTP::MobileAgent にそれぞれ独自パッチをあてたものを使っています。これらはルールベースの判定器なので,新しいブラウザや新種の bot が登場するたびに手作業でルールを追加し,パッチを作って配布するという作業が必要になります。

この更新作業が大変面倒くさくて対応が遅れがちになるので,「このUA文字列はこのブラウザですよ、という例を大量に与えたら、自分で勝手に判定ルールを学習してくれるようになったら便利なのになぁ」と思い,decision tree (決定木)を使ってみることを思い立ちました。

目標は,

  • "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15" は Firefox
  • "Mozilla/5.0 (iPod; U; CPU iPhone OS 4_1 like Mac OS X; ja-jp) AppleWebKit/532.9 (KHTML, like Gecko) Version/4.0.5 Mobile/8B117 Safari/6531.22.7" は Safari
  • ...

というふうに例を与えていくと,UA文字列からブラウザを判定するルールを自動的に獲得するプログラムを作成することです。Perlの場合 AI::DecisionTreeというライブラリがあって,手軽に decision tree で遊ぶことができます。

BlogPaint

decision tree の動きを見てみる

以下の簡単なスクリプト dt_test.pl を使って,AI::DecisionTree がルールを学習する過程をみていきましょう。(あらかじめCPAN経由でAI::DecisionTreeがインストールされていることが前提です。)

・dt_tree.pl

#!/usr/bin/perl

use strict;
use AI::DecisionTree;

my $dtree = new AI::DecisionTree( prune => 0 );

# stdinから教師データ(UA文字列+タブ+正解文字列)読み込み
while(<>) {
    chomp;
    my ($attributes, $result) = split(/\t+/);

    $dtree->add_instance(
        attributes => { map { $_ => 1 } split(/\s+/, $attributes) }, # UA文字列をスペースで分割したものをすべてattributeとする。
        result => $result,
    );
}

$dtree->train; # 学習

# 学習したルールを表示
print "\n--- rules\n";
print join "\n", $dtree->rule_statements;
print "\n---\n";

動作例

> ./dt_test.pl
Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15	Firefox/3.6
Mozilla/5.0 (iPod; U; CPU iPhone OS 4_1 like Mac OS X; ja-jp) AppleWebKit/532.9 (KHTML, like Gecko) Version/4.0.5 Mobile/8B117 Safari/6531.22.7	Safari/4.0
^D
--- rules
if Mac='' -> 'Firefox/3.6'
if Mac='1' -> 'Safari/4.0'
---
>

イタリックの部分がユーザ入力です。dt_test.pl を起動したあと,Firefox と Safari を表す2行の教師データ (UA文字列と正解のブラウザ名をタブでつなげたもの) を入力しています。プログラムはこの教師データを

  • 「"Mozilla/5.0", "(Windows;", "U;", "NT", "6.1;" ... などの文字列があれば "Firefox/3.6"」
  • 「"Mozilla/5.0", "(iPod;", "U;", "CPU" ... などの文字列があれば "Safari/4.0"」

というふうに記録していきます。この "Mozilla/5.0" などの文字列ひとつひとつを attribute と呼びます。ここでは与えられたUA文字列を空白で分割したものを attribute として利用しています。

プログラムは与えられた例の中から "Firefox/3.6" と "Safari/4.0" を見分ける一番簡潔なルールを探します。その結果,"Mac" という attribute に注目し,

  • 「"Mac" という attribute がなかったら Firefox,あったら Safari」

というルールを導きだしました。

実際には "Mac" があっても Firefox の可能性はあります。その例を教師データとして追加し,プログラムがルールをどう修正するかみてみましょう。

> ./dt_test.pl
Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15	Firefox/3.6
Mozilla/5.0 (iPod; U; CPU iPhone OS 4_1 like Mac OS X; ja-jp) AppleWebKit/532.9 (KHTML, like Gecko) Version/4.0.5 Mobile/8B117 Safari/6531.22.7	Safari/4.0
Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; ja-JP-mac; rv:1.9.2.11) Gecko/20101012 Firefox/3.6.11 GTB7.1	Firefox/3.6
^D
--- rules
if like='' -> 'Firefox/3.6'
if like='1' -> 'Safari/4.0'
---
>

今度は "Mac" という attribute の有無では Firefox と Safari とを見分けられなかったため,

  • 「"like" がなければ Firefox,あれば Safari」

というルールに変わりました。まあ確かに言われてみれば...という気がしないでもないですが,ここでさらに Internet Explorer と Chrome の例を二つ加えて混乱させてみましょう。

>./dt_test.pl 
Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15	Firefox/3.6
Mozilla/5.0 (iPod; U; CPU iPhone OS 4_1 like Mac OS X; ja-jp) AppleWebKit/532.9 (KHTML, like Gecko) Version/4.0.5 Mobile/8B117 Safari/6531.22.7	Safari/4.0
Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; ja-JP-mac; rv:1.9.2.11) Gecko/20101012 Firefox/3.6.11 GTB7.1	Firefox/3.6
Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 5.1; Trident/4.0; GTB6.6; .NET CLR 1.1.4322)	Internet Explorer/8.0
Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_5_8; en-US) AppleWebKit/534.13 (KHTML, like Gecko) Chrome/9.0.597.102 Safari/534.13	Chrome/9.0
^D
--- rules
if like='' and MSIE='' -> 'Firefox/3.6'
if like='' and MSIE='1' -> 'Internet Explorer/8.0'
if like='1' and AppleWebKit/534.13='' -> 'Safari/4.0'
if like='1' and AppleWebKit/534.13='1' -> 'Chrome/9.0'
---
>

今度は判定が以下のように二段階になりました。

  • "like" がなかったら
    • → "MSIE" がなかったら Firefox,あったら InternetExplorer
  • "like" があったら
    • → "AppleWebKit/534.13" がなかったら Safari,あったら Chrome

まだまだUAの判定ルールとして使い物になるレベルではないですが,たった5例しか教師データを与えていないのにここまで簡潔なルールを導きだしたことに注目してください。

このように decision tree は,与えられた例を一般化してツリー状の分類ルールを推定してくれるわけです。

もう少し実用的なUA判定器と,教師データセットを作成する

ここまでで decision tree の動きを確認してきましたが,これを実用的なものにするには

  1. UA文字列をスペースだけで分割するのは大雑把すぎるので,もう少し工夫して精度を上げる。
  2. 種別 (PCブラウザ/モバイルブラウザ/クローラ etc.),OS名,ブラウザ名の三段階の判別ができるようにする。
  3. 大量の教師データを与えて,あらゆるパターンを網羅できるようにする。
  4. (しかし,大量の教師データ読み込みには時間がかかるので) いったん学習したルールを保存しておけるようにする。

などの努力が必要です。

UA文字列から attribute を抽出する方法を工夫する

例えば

Mozilla/5.0 (Windows; U; Windows NT 6.1; en-US) AppleWebKit/534.13 (KHTML, like Gecko)

というUA文字を見てみると,

  • 空白よりも先に,"(", ")", ",", ";" などの記号で分割する。
    • → "Windows NT 6.1", "Mozilla/5.0" といった文字列が,ひとまとまりのまま attribute になる。
  • それらをさらに空白や"/" などで分割してみて,分割できたらそれらも attribute に加える。
    • → "Windows NT 6.1", "Windows", "NT", "6.1", "Mozilla/5.0", "Mozilla", "5.0" などがすべて attribute になる。

という二段階の文字列分解をするとうまくいきそうな気がします。

最初から空白や"/"で分割してしまわないのは,例えば "Windows NT 5.0" と "Mozilla/5.0" の "5.0" は前の文字列とくっついた状態でないと意味をなさないからです。かといって "Mozilla/5.0" のようにバージョン番号がくっついたものだけを attribute にしてしまうと,分類器が "Mozilla/4.0" と "Mozilla/5.0" の類似性に気づかず,一般化に苦労するはめになります。そこで,細分割前の文字列と後の文字列を両方 attribute として記録しておき,どの attribute を採用するかは AI::decisionTree に任せることにします。

  • UA文字列から,attribute の候補をすべて array ref で返すメソッドの例
sub breakdown_ua {
    my ($ua) = @_;

    $ua = lc($ua);
    my @ua_str = map { s/^\s+//;s/\s+$//;$_ } grep $_, split (/[,;\"\(\)]/, $ua);
    my @sub_ua_str;
    for (@ua_str) {
        push @sub_ua_str, grep { $_ !~ /^[0-9\._\-\+]*$/ } split(/[\s\/\-]/);
    }

    return [@ua_str, @sub_ua_str];
}

※UA文字列の付け方に関しては,[ここ][ここ]が参考になりました。

UA種別,OS名,ブラウザ名の三段階の判別ができるようにする

UA判定器の典型的な使い方としては,

  • "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15"
    • → PCブラウザ / Windows 7 / Firefox/3.6
  • "DoCoMo/2.0 N01B(c500;TB;W24H16) Mobile Browser DoCoMo N01B"
    • → モバイルブラウザ / DoCoMo / N01B
  • "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html) "
    • → クローラ / - / Googlebot

というふうに一つのUA文字列から三段階のタイプ判定をすることが挙げられます。

しかし,decision tree は基本的には「与えられた attribute のセットから,ひとつの判定結果を導きだす」ために使われます。上の例のように三段階の判定を同時にしたい場合は

  1. "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15" は "PC - Windows 7 - Firefox/3.6" という名前のブラウザです」というように,種別/OS名/ブラウザ名をひとまとまりの result として扱う
  2. 分類器を三つ用意し,それぞれを独立に「"Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15" は "PCブラウザ" です」「"Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15" は "Windows 7" です」「"Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1.9.2.15) Gecko/20110303 Firefox/3.6.15" は "Firefox/3.6" です」と訓練していく。

の二種類の方法があります。組み合わせが増える分,前者のほうがルールが無駄に複雑になる気がしたので,今回は後者の方法を採用しました。

十分な量の教師データを用意する

最初の例でみたように,データ量が十分でなかったり偏っていたりすると実用的なルールが学習できません。

今回は

  1. DoCoMo, SoftBank, AU の各キャリアの公式サイトの情報を元に独自に生成したもの
  2. useragentstring.com のデータを色々アレして独自に加工したもの
  3. livedoor のサーバの実際のアクセスログのUAをサンプリングし,(一部UAの端末IDフィールドを取り除いたり,重複処理をした後) すでに利用しているルールベースのUA判定器にかけたもの

の三種類のデータを用意しました。

試してみたい方は [こちら] から自由にダウンロードして頂けます

  • データの正確性は保証しません
  • いずれもUA文字列の後ろにタブ区切りでフィールドが3つ入っています。フィールドは以下の通りです。
    • PC&スマートフォンブラウザは "Browser / (OS名) / (ブラウザ名)"
    • モバイルブラウザは "Mobile Browser / (キャリア名) / (機種名)"
    • クローラは "Crawler / (空フィールド) / (クローラ名)"

学習済みの判定器を保存しておけるようにする

上のような大量のデータを読み込んでルールを生成するにはそれなりの時間が必要になります。。プログラムを起動するたびにデータ読み込みとルール生成をしていては,実際の判別処理ができるようになるまでに時間がかかってしまいます。

そこで,学習プログラムが AI::DecisionTree のインスタンスをStorable にてファイルに保存し,判別プログラムはそこからインスタンスを解凍して使うようにプログラムを二つに分割します。

出来上がったものがこちらです

  • build_tree.pl (与えられた例から decision tree を構築する)
#!/usr/bin/perl

use strict;
use AI::DecisionTree;
use Storable qw(store_fd);

$| = 1;

my $N_TREES = 3;
my $FREEZER = 'frozen_dt.dat';

my @trees;
for my $i (1..$N_TREES) {
    push @trees, new AI::DecisionTree(
        prune => 1,
        noise_mode => 'pick_best',
    );
};

while (<>) {
    chomp;
    my ($ua, @results) = split(/\t/);
    return unless $ua;

    my $ua_fragments = breakdown_ua($ua);

    for my $i (0..$N_TREES-1) {
        next unless $results[$i];
        $trees[$i]->add_instance(
            attributes => {
                map {$_ => 1} @$ua_fragments,
            },
            result => $results[$i],
        );
    }
    print ".";
}

print "\ndone.\n";

open FH, ">$FREEZER";
for my $i (0..$N_TREES-1) {
    print "\ntraining tree $i\n";
    $trees[$i]->train;

    my @s = $trees[$i]->rule_statements;
    print "\n==============\n";print join "\n",@s;print "\n";

    store_fd $trees[$i], \*FH;
}
close FH;

sub breakdown_ua {
    my ($ua) = @_;

    $ua = lc($ua);
    my @ua_str = map { s/^\s+//;s/\s+$//;$_ } grep $_, split (/[,;\"\(\)]/, $ua);
    my @sub_ua_str;
    for (@ua_str) {
        push @sub_ua_str, grep { $_ !~ /^[0-9\._\-\+]*$/ } split(/[\s\/\-]/);
    }

    return [@ua_str, @sub_ua_str];
}
  • 使用例
> cat *.tsv | build_tree.pl
  • decide_ua.pl (あらかじめ保存した decision tree を使ってUAの判定をする)
#!/usr/bin/perl

use strict;
use AI::DecisionTree;
use Storable qw(fd_retrieve);

my $N_TREES = 3;
my $FREEZER = 'frozen_dt.dat';

my @trees;
open FH, $FREEZER;
for my $i (1..$N_TREES) {
    push @trees, fd_retrieve(\*FH);
}
close FH;

my $ua = $ARGV[0];
if ($ua) {
    my $ua_fragments = breakdown_ua($ua);
    for my $i (0..$#trees) {
        my $result = $trees[$i]->get_result(
            attributes => {
                map {$_ => 1} @$ua_fragments,
            }
        );
        print "$result\n";
    }
} else {
    for (@trees) {
        my @s = $_->rule_statements;
        print "\n==============\n";print join "\n",@s;print "\n";
    }
}

sub breakdown_ua {
    my ($ua) = @_;

    $ua = lc($ua);
    my @ua_str = map { s/^\s+//;s/\s+$//;$_ } grep $_, split (/[,;\"\(\)]/, $ua);
    my @sub_ua_str;
    for (@ua_str) {
        push @sub_ua_str, grep { $_ !~ /^[0-9\._\-\+]*$/ } split(/[\s\/\-]/);
    }

    return [@ua_str, @sub_ua_str];
}

※ breakdown_ua メソッドなど,生成と判定の両方で必要な処理・変数がいくつかありますので,実用に使う場合は適宜共通化してください。

  • 使用例
> decide_ua.pl "Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; .NET4.0C)"
Browser
Windows 7
Internet Explorer/8.0
>

decide_ua.pl は,引数を与えた場合はそのUA文字列に対する判定結果を,引数がない場合は保存された判定ルールを,それぞれ表示します。

オチ

で、こうして出来たUA判定器を実際の業務で使っているかということですが、結局使っていません。

確かに,ルールを手で作成するのではなく例を列挙していくだけでよい,というのはメンテナンスが楽そうなのですが,そのためには「webから簡単に例が追加できて,再学習→テスト→本番反映がボタンひとつでできる」という管理システムまで作らないと意味ないし,そこが非常に面倒くさかったので…

また,例えばルールベースの場合,このようにバージョン番号や機種名の取り出し方を記述しておくことで、新しく"MSIE 99.9" など,教師データにない新顔が出現した場合にも対応し続けることができます。

if ($ua =~ /MSIE\s+([0-9\.]+)/i) {
  $browser = 'Internet Explorer';
  $version = $1;
}

しかし,ここで示したような decision tree 方式だと,バージョンや機種毎に別々の教師データが必要になります。(可変部分を全部 "#" に置き換えるなどの工夫が出来そうな気はするけど…。)

というわけで,現状ルールベースでなんとかなっている+いろいろ面倒くさい,のコンボでいまのところ試しただけで終わりになっているのですが,この decision tree はUA判定器以外にも様々な用途に使えますので,心の片隅においておくときっといつか役に立つときが来ると思います。

(この記事中の「面倒くさい」の出現頻度: 4回)