解析

wikipediaのデータや顔文字辞書からmecabのユーザ辞書を作成するフレームワーク

カテゴリ
ブックマーク数
このエントリーを含むはてなブックマーク はてなブックマーク - wikipediaのデータや顔文字辞書からmecabのユーザ辞書を作成するフレームワーク
このエントリーをはてなブックマークに追加

突然ですが,mecabの辞書 (mecab-ipadic) をデフォルトのまま使って,mecab意外と使えねぇとか文句言ってる悪い子はおらんかね?

mecab-ipadic は比較的お行儀のよい日本語をベースに作られているので,そのままでは web上の口語文体のテキストはうまく扱えないことがあります。本来は教師データを用意し,学習させるといった手法を使うのが正攻法だと思いますが,とりあえず名詞を充実させるだけでも実用度はだいぶ上がるでしょう。

人間の話す言語には,動詞の語幹や名詞には日々新しく語彙が増えるけど,助詞や活用のルールは簡単には変化しない,という特性があります。特に「いま最もつぶやかれている単語ランキング」といった集計をするような場合は,名詞の範囲の切り出しさえ間違えなければそれなりの結果を出せることも多いのです。

ただ,辞書への単語追加はここにある通り簡単にできるのですが,単語の生起コストを決める部分で躓いてしまうことも多いと思います。

そこで,うちで以前から使っていた mecab の辞書増強用のフレームワークを公開することにしました。wikipedia のデータや顔文字辞書などからユーザ辞書を作成することができます。

mecab-dic-overdrive

https://github.com/nabokov/mecab-dic-overdrive

GenDic.pm のサブクラスを作成することで,さまざまな形式の入力データから単語を読み取り,(それなりに)適切な生起コストを自動的に推測してユーザ辞書ファイルを生成してくれる仕組みになっています。デフォルトでは wikipedia 日本語版の jawiki-latest-page.sql.gz と顔文字辞書用のtsvとから,それぞれユーザ辞書を作成することができます。

似たようなスクリプトや記事がすでにいくつか公開されているのであえて公開することもないかなと思っていたのですが,後で述べるように,生起コストの計算方法や,ノーマライゼーションまで含めた辞書管理に多少の独自性というか公開する意義がある気がしましたので。何かの参考になれば幸いです。

mecab-dic-overdriveの機能

辞書のutf-8化

mecabを使うのにipadic自体をutf-8化する必要は必ずしもないのですが,次に述べる辞書パッチを作る場合や,各種プログラムから参照する場合などには utf-8 の方が便利なので,最初に文字コードの変換をします。

辞書へのパッチ適用

misc/dic/*.patch に,ipadic に対するパッチがいくつか用意してあります。"A" "B" などの英数字が単独で切り出されにくくなるための変更や,"ゎ" "ょ" などが助詞として認識されるようになるためのパッチが含まれます。この他にも自前で何か変更を加えたい場合は *.patch ファイルを (utf-8で) 書いてここに置いておくと自動的に適用されます。

辞書のノーマライズ

辞書を有効活用するためには,

など,さまざまな手法を駆使して表現揺れを吸収しておく必要があります。辞書作成時と文章解析時の両方で同じノーマライゼーションを適用するのも重要な注意点です。

デフォルトでは以下のノーマライズ処理がこの通りの順で適用されます。NFKCとlc以外はバッドノウハウの塊です。改行の扱いなどは辞書作成時には無害ですが,特に顔文字や記号を含むテキストに大きく影響する設定も含まれるので,必ず,解析時に使う正規化と同じものを設定するようにしてください。

  1. decode_entities : HTMLエンティティをユニコード文字にデコード [ ♥ → ♥ ]
  2. strip_single_nl : 単独の改行を除去 (二つ以上連続する改行は区切りと見なす)
  3. wavetilde2long : 波ダッシュを長音記号に置き換える [ プ〜 → プー ]
  4. fullminus2long : 全角マイナス記号を長音記号に置き換える [ プ− → プー ]
  5. dashes2long : ダッシュ全般を長音記号に置き換える [ プ— → プー ]
  6. drawing_lines2long : 罫線に使われる横線などを長音記号に置き換える (参考:[1] [2]) [ プ─ → プー ]
  7. unify_long_repeats : 連続する長音記号を長音記号一個に置き換える [ プーーー → プー ]
  8. nfkc : NFKC正規化 [ フ゜ブ→ ププ ]
  9. lc : アルファベットを小文字に統一 [ ABC → abc ]

変更したい場合は lib/MecabTrainer/NormalizeText.pm を参照の上,etc/config.pl の内容を編集します。bin/normalize_text.pl を使ってノーマライゼーションの結果を確認することもできます。

>bin/normalize_text.pl
キタ━━━━━━(゚∀゚)━━━━━━ !!!!!
キター(゚∀゚)ー !!!!!

>bin/normalize_text.pl --normalize_opts=decode_entities,nfkc
㍖ ½
レントゲン 1⁄2

単語生起コストの自動割り当て

新しく単語を登録する場合に問題になるのが,上で述べた単語生起コストの算出です。ここで"鼻セレブ" という商品名を例に,単語生起コストの調整のしかたを考えてみましょう。

鼻セレブタワー
鼻セレブ(ウサギ限定)ばかり買ってる人の例

単語が単体で現れた場合に,分割されないぎりぎりのラインを求める方法

素の辞書で"鼻セレブ"だけからなる文を mecab で解析すると以下のように「鼻」と「セレブ」が別々の単語として認識されてしまいます。

形態素 連接コスト 単語生起コスト 累積コスト
BOS - 0 0
-283 - -283
鼻(名詞/一般) - 6033 5750
62 - 5812
セレブ(名詞/一般) - 9461 15273
-573 - 14700
EOS - 0 14700

(BOSは文頭,EOSは文の終わりを表します。)

そこで,単語「鼻セレブ」が単体の文章として現れた場合に,それ以上分割されないようにすることを目標としてみます。

まず辞書に形態素「鼻セレブ(固有名詞/一般)」を追加します。そして,mecab が「『鼻+セレブ』に分解するより『鼻セレブ』単体とした方がトータルコストが低い」と判断するように単語生起コストを調節することを考えます。

つまり,

形態素 連接コスト 単語生起コスト 累積コスト
BOS - 0 0
-310 - -310
鼻セレブ(固有名詞/一般) - *1 *
-919 - *
EOS - 0 *2

上表の *1 を何にすれば *2 が 14700 以下になるか? という穴埋め問題を解くことになるわけです。この場合は *1 を 15928 以下にすれば,全体のコストが「鼻+セレブ」の14700よりも低くなります。

BlogPaint

※1「明日の鼻セレブ祭りは中止です」のように前後に他の形態素がつながる場合は,前後の連接コストが変わってきます。「単体の文章として(BOSとEOSの間に)現れた場合に分割されないようにする」というルールはあくまでも恣意的な基準にすぎません。

※2 ときどきここにあるAuto Linkの例に従って,cost = (int)max(-36000, -400 * (length^1.5)) という式をそのまま使っている記事を見かけますが,この式はあくまでこの辞書だけを使って mecab を AutoLink 専用に用いる場合 を想定して書かれたもので,これを ipadic と混ぜると基準値が合わなくなると思います。ipadicにある生起コストは四桁ぐらいまでの正の数ですが,この式だとコストがマイナスになるので,文脈に関わらずほぼ常にユーザ辞書のエントリが優先されるでしょう。(勿論そういう意図ならそれで構わないのですが。)

既存辞書から,同じ品詞&同じ長さの形態素の平均コストを計算しておく方法

上とは別に,もう少し単純に生起コストの目安を得る方法もあります。

例えば既存のipadicの中から「固有名詞/一般」の単語だけを取り出し,単語の長さごとに生起コストの平均をとっておきます。

文字数 平均コスト
1 8998
2 8242
3 8339
4 7989
5 6947
... ...
10 5038
... ...

このテーブルをあらかじめつくっておき,新たな単語を登録する際は,同じ品詞&同じ長さの既存の形態素の平均値をあてはめるようにするわけです。"鼻セレブ"の場合は4文字なので生起コストとして7989を採用することになります。まあ,大雑把ではありますが何もしないよりはだいぶマシな感じになると思います。

mecab-dic-overdrive のコスト生成方式

mecab-dic-overdrive では,この二つの方式を組み合わせてコスト決定を行います。デフォルトの動作は

  1. 同じ品詞&同じ長さの既存単語の平均コスト (※条件を満たす既存単語が見つからない場合はあらかじめ決めた固定値を利用)
  2. 上で示した「単独で現れた場合にそれ以上細分割されないぎりぎりのコスト」x 0.7

の,どちらか小さい方をとるようになっています。(この動作は GenDic.pm の200行目からのあたりを編集すればカスタマイズ可能です。)

前者の計算には辞書の元のcsvファイル,後者の計算には left-id.def, right-id.def, matrix.def を参照するため,mecab-ipadic のソースの場所を config に設定してやる必要があります。

mecab-dic-overdrive 使用方法

辞書のインストール & ユーザ辞書作成

(1) 事前に必要なライブラリ等の準備
  • あらかじめ mecab本体, および,以下のperlライブラリをインストールしておく
    • Text::MeCab
    • Unicode::Normalize
    • Unicode::RecursiveDowngrade
    • HTML::Entities
    • File::Spec
    • Path::Class
    • Log::Log4perl
  • mecab-dic-overdrive本体をgithubから入手する
  • mecab-ipadic-2.7.0-20070801 をダウンロードし,解凍しておく。(他のバージョンの場合,前述のパッチの段階などでこける可能性があります)
> git clone https://github.com/nabokov/mecab-dic-overdrive.git
> tar -xvzf mecab-ipadic-2.7.0-20070801.tar.gz
(2) config.pl / log.conf の設定

mecab-dic-overdrive/etc/config.pl の内容を環境にあわせてカスタマイズする。最低でも

  • $HOME (mecab-dic-overdrive を解凍したディレクトリ)
  • $DIC_SRC_DIR (mecab-ipadic-2.7.0-20070801 を解凍したディレクトリ)

は編集してください。

また,ノーマライゼーションを変更したい場合は上の「辞書のノーマライズ」の項を参考に default_normalize_opts を編集してください。

(例)
default_normalize_opts => [qw(decode_entities strip_html nfkc lc)],

動作ログの書き出し先を変えたり,ログレベルを変えたい場合は etc/log.conf を編集してください。

(例)
log4perl.rootLogger=DEBUG, LOGFILE
log4perl.appender.LOGFILE.filename=/path/to/log.txt
(3) utf8化+ノーマライズ+パッチ適用された mecab-ipadic の作成
>bin/initialize_dic.pl

これで (1)辞書のutf-8化 (2)辞書へのパッチ適用 (3)辞書のノーマライズ (4)辞書のコンパイル&インストール,までが完了します。

"make install failed" と言われてしまう場合,あるいは既存の辞書 (/usr/local/lib/mecab/dic/ipadic) を残して別の場所へインストールしたい場合は,以下のように別の場所へ手作業で辞書をコピーし, mecab 呼び出しの際に -d オプションを使って辞書ディレクトリを指定するようにしてください。

(手動で /usr/local/lib/mecab/dic/ipadic-utf8 へインストールする場合の例)

>bin/initialize_dic.pl --noinstall
>mkdir /usr/local/lib/mecab/dic/ipadic-utf8
>cp [ipadicのソースディレクトリ]/*.bin /usr/local/lib/mecab/dic/ipadic-utf8/
>cp [ipadicのソースディレクトリ]/*.def /usr/local/lib/mecab/dic/ipadic-utf8/
>cp [ipadicのソースディレクトリ]/*.dic /usr/local/lib/mecab/dic/ipadic-utf8/
>cp [ipadicのソースディレクトリ]/dicrc /usr/local/lib/mecab/dic/ipadic-utf8/

(このあと etc/config.pl の dicdir = "/usr/local/lib/mecab/dic/ipadic" を
 "/usr/local/lib/mecab/dic/ipadic-utf8" へ変更する)

(mecab をコマンドラインから使う場合は -d オプションを指定)
>mecab -d /usr/local/lib/mecab/dic/ipadic-utf8/

(4) wikipediaのデータからユーザ辞書を作成する

日本語版wikipediaのダンプサイトから jawiki-latest-page.sql.gz を入手して misc/dic 以下に .gz のまま保存します。( zcat/gzcat が利用できない環境では解凍しておきます。ファイル名や置き場所を変えたい場合は GenDic/WikipediaFile.pm を適宜変更してください。)

>bin/generate_dic.pl --target=wikipedia_file

とすると,SQLファイルを直接読み込んで記事タイトルを抽出し,「固有名詞/一般」としてユーザ辞書ファイル misc/dic/wikipedia.dic に書き出します。

※SQL文を直接強引にパースする仕組みのため,今後wikipediaのダンプ仕様に変更があると動かなくなる可能性もあります。その場合はいったんデータをDBに読み込み,DBから書き出しを行うより確実な方法( --target=wikipedia_file のかわりに --target=wikipedia を指定) も利用できます。詳しい設定方法は GenDic/Wikipedia.pm を参照してください。

(5) 顔文字辞書からユーザ辞書を作成する (optional)

顔文字辞書用として様々な場所で配布されているtsvを読み込んでユーザ辞書を作ることができます。

読み込み元は misc/dic/kaomoji.tsv にあるので,追加したい顔文字がある場合はここに追記したあと,

>bin/generate_dic.pl --target=kaomoji

とすると,各顔文字を「記号/一般」として misc/dic/kaomoji.dic に書き出します。

wikipedia.dic にある記号系エントリより優先度を高くするために,先に作成した wikipedia.dic を読み込んだ mecab をつかって生起コスト計算をするようになっています。そのため,misc/dic/wikipedia.dic がないと動きません。この仕様を変更したい場合は GenDic/Kaomoji.pm の defaults メソッドを編集してください。

(6) その他,wikipediaにない固有名詞などを追加する (optional)

上記以外に追加したい名詞がある場合は misc/dic/simple_list.txt に改行区切りで列挙し,

>bin/generate_dic.pl --target=simple_list

とすると,それらをすべて「名詞/固有名詞/一般」として読み込み,misc/dic/simple_list.dic に書き出します。

作成した辞書の利用

上記ステップ(4)-(6)で作成したユーザ辞書は,mecab の -u オプションで指定して利用できます。

>mecab -u misc/dic/wikipedia.dic,misc/dic/kaomoji.dic,misc/dic/simple_list.dic
(使用前)
> mecab
崖の上のポニョニコ動で見た
崖	名詞,一般,*,*,*,*,崖,ガケ,ガケ
の	助詞,連体化,*,*,*,*,の,ノ,ノ
上	名詞,非自立,副詞可能,*,*,*,上,ウエ,ウエ
の	助詞,連体化,*,*,*,*,の,ノ,ノ
ポニョニコ	名詞,一般,*,*,*,*,*
動	名詞,一般,*,*,*,*,動,ドウ,ドー
で	助詞,格助詞,一般,*,*,*,で,デ,デ
見	動詞,自立,*,*,一段,連用形,見る,ミ,ミ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
EOS

(使用後)
>mecab -u misc/dic/wikipedia.dic
崖の上のポニョニコ動で見た
崖の上のポニョ	名詞,固有名詞,一般,*,*,*,崖の上のポニョ,Wikipedia:1070057
ニコ動	名詞,固有名詞,一般,*,*,*,ニコ動,Wikipedia:1347271
で	助詞,格助詞,一般,*,*,*,で,デ,デ
見	動詞,自立,*,*,一段,連用形,見る,ミ,ミ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
EOS

utf-8版 ipadic をデフォルトの場所とは違う場所に書き出した場合は,-d オプションも指定します。

>mecab -d /usr/local/lib/mecab/dic/ipadic-utf8

ノーマライザの利用

前述のように,解析時には辞書作成時と同じノーマライザを通さないと意味がないので,作成した辞書を使う場合には以下のように MecabTrainer::NormalizeText のインスタンスを通すようにしてください。

use Encode;
use MecabTrainer::NormalizeText;
new $normalizer = MecabTrainer::NormalizeText->new(
    [decode_entities strip_single_nl nfkc lc]
);

$normalized_decoded_text = $normalizer->normalize(
    Encode::decode('utf8', $raw_input_text)
)

使用方法については bin/normalize_text.pl のソースなども参照。

コマンドラインで使う場合には bin/normalize_text.pl をパイプでかませて利用することができます。

使用例と解析結果の例を以下にいくつか載せておきます。

> bin/normalize_text.pl | mecab -d /usr/local/lib/mecab/dic/ipadic-utf8/ -u misc/dic/wikipedia.dic,misc/dic/kaomoji.dic
ひまなう(´・ω・`)
^D
ひま	名詞,一般,*,*,*,*,ひま,ヒマ,ヒマ
なう	助詞,終助詞,*,*,*,*,なう,ナウ,ナウ
( ́・ω・`)	名詞,固有名詞,一般,*,*,*,( ́・ω・`),Wikipedia:700982
EOS

久々更新〜 お腹へったょ
^D
久々	名詞,一般,*,*,*,*,久々,ヒサビサ,ヒサビサ
更新	名詞,サ変接続,*,*,*,*,更新,コウシン,コーシン
ー	記号,一般,*,*,*,*,─,─,─
お腹	名詞,一般,*,*,*,*,お腹,オナカ,オナカ
へっ	動詞,自立,*,*,五段・ラ行,連用タ接続,へる,ヘッ,ヘッ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
ょ	助詞,終助詞,*,*,*,*,よ,よ,よ

朝からテゴマスのあいCMやってた
^D
朝	名詞,副詞可能,*,*,*,*,朝,アサ,アサ
から	助詞,格助詞,一般,*,*,*,から,カラ,カラ
テゴマスのあい	名詞,固有名詞,一般,*,*,*,テゴマスのあい,Wikipedia:2035668
cm	名詞,一般,*,*,*,*,CM,シーエム,シーエム
やっ	動詞,自立,*,*,五段・ラ行,連用タ接続,やる,ヤッ,ヤッ
て	動詞,非自立,*,*,一段,連用形,てる,テ,テ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
EOS

( ゚∀゚)アハハ八八ノヽノヽノヽノ \ / \/ \
^D
( ゚∀゚)アハハ八八ノヽノヽノヽノ  / / 	記号,一般,*,*,*,*,( ゚∀゚)アハハ八八ノヽノヽノヽノ  / / \n

カスタムの読み込みクラスの作成

GenDic/ 以下にサブクラスを作成することで,任意の入力からユーザ辞書をつくることができます。MecabTrainer::GenDic クラスを継承して

  • 入力ストリームの開き方
  • 入力を一行ずつ読み,パースする方法
  • 読みとった単語にどんな品詞,featuresを割り当てるか

を記述しておけば,生起コストの計算や辞書のコンパイルは親クラスがすべて肩代わりしてくれる仕組みです。詳しくは GenDic ディレクトリ以下の各ソースを参照して下さい。

generate_dic.pl の --target オプションでサブクラス名を指定 (CamelCaseを小文字+"_"に置き換え) することで,作成したサブクラスを呼び出すことができます。

(サブクラス TestClass.pm を指定する場合の例)
>bin/generate_dic.pl --target=test_class

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回)