Go to Qiita Advent Calendar 2024 Top
LoginSignup
30
29

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

LivesenseAdvent Calendar 2014Day 22
@taiseinTimeTree, Inc.

ルールベースの判別ロジックに決定木を使ってみる

Last updated at Posted at 2014-12-22

Livesense Advent Calendar 22日目を担当しますtaiseです。

21日目はeriさんの「ChucKで発見！自分の好きな音。」でした。

そろそろAdvent Calendarも終盤戦です。

絶え間なきUser Agentとの戦い

HTTPリクエストを送る際に、利用しているエージェント(ブラウザ等)の情報が書かれている、あのUser Agentについてです。

例えば、提供しているWebサービスの画面描画が崩れたという問い合わせとか、サービスの利用者の使っている端末やブラウザの割合を調べる場合にUser Agentが利用されると思います。

しかし、User Agentをよくよく調べてみると、PCやスマフォにかぎらずゲーム機やら、電子ブックリーダを始め、様々なデバイスやらブラウザからアクセスされていることがわかります。また、デバイスだけでなく、Webブラウザも日々増え続けています。

User Agentの判別の仕方を考えた時に、パッと2通りの方法がありそうです。

  1. 辞書ベース
  2. ルールベース

辞書ベース

辞書ベースは、対象のUser Agentとそれに紐づくブラウザ、OS等の情報をすべて辞書として保存しておき、利用するときは辞書から探す方法です。登録されているものについては正確に返せますが、ちょっとしたバージョンの違い等に弱く、辞書の更新の労力を考えるとすぐに破綻してしまいそうです。

ルールベース

次のルールベースは、特定の文字列や文字列のパターンからブラウザ・OS等の判別を行います。辞書ベースのものと比べて正確性はやや損なわれるものの、逆におおらかな判定によって救えるものが多そうです。

では本当にルールベースで判定できそうか、試してみることにします。

とはいえ、User Agentはとても複雑です。

例えば、OSXのChromeのUser Agentの場合
"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/38.0.2125.111 Safari/537.36"
こんな感じなのですが、AppleWebKitとSafariと書かれていて、一見するとSafariと間違えてしまいそうです。
Chromeは、レンダリングエンジンをWebkitからBlinkに分岐させていますが、AppleWebKitのままというのも、ややこしいポイントです。

判定ルールを自分ですべて考えようとすると確実にミスや正確性が落ちそうなので、決定木に頼ってみます。

決定木

決定木についてざっくり書くと、クラス(種類）の分類や値の近似値を推測する際に使われる機械学習の手法で、分割の結果が最も不純度が低くなるように木構造で分岐していく手法です。
詳細が知りたい方は「decision tree」とかでググってください。

この木構造の分岐で使われる説明変数を使って、今回はAgent(ブラウザ)とOSの判定ルールを構築してみようと思います。

ルールベースの判定ロジック

ざっくり以下のことをやってみます

  • User Agentの実データの取得
  • 学習用データの作成
  • モデル(判定ロジック)の構築

User Agent のデータの取得

httpdのアクセスログから持ってくることにします。
厳密ではないかもしれませんが、こんなかんじで。

cut -d' ' -f13- access_log > user_agent.txt
sort < user_agent.txt | uniq | sed 's/^"//g' | sed 's/"$//g' > uniq_user_agent.txt

ざっくりとれました。
ほとんど使っていない個人のレンタルサーバなので、ログの量が少し足りないかもとおもいつつですが、お試しなのでこのまま行くことにします。
不要なコーテーションなども削除しておきます。

取得したuser_agent.txtのサイズが大きいときは、sortがつらいので分割してからユニークにするか、
適当にサンプリングして取得してみてもいいかもしれません。

学習用データの作成

続いて学習用データを作成します。

今回はAPI経由でUser AgentのOS情報まで取得できるwww.useragentstring.com から情報を取得することにします。
APIに負荷をかけてしまわないよう、5~10秒のsleepを使ってリクエストを投げます。

# -*- coding: utf-8 -*-

require 'httparty'
require 'active_support'
require 'active_support/core_ext'
require 'csv'


BASE_HOST = 'www.useragentstring.com'.freeze
csv = CSV.open('user_agent.csv', 'w+')

def build_uri(user_agent)
  query = { getJSON: 'all', uas: user_agent }.to_param
  URI::HTTP.build({ host: BASE_HOST, query: query }).to_s
end

open('uniq_user_agent.txt', 'r').each do |line|
  puts user_agent = line.chomp
  uri = build_uri(user_agent)
  res = HTTParty.get(uri)
  res['user_agent'] = user_agent
  csv << res.values
  sleep(rand(5) + 5)
end

csv.close

さて、これで取得完了です。

では続いて、データを決定木にかけるまえに前処理を行ないます。
APIからの取得結果をみてみたら、クローラーや各言語のライブラリの種類が多かったですが、今回は重要ではないのでまとめておくことにします。

また、この後MeCabを使った形態素解析をかけるので、不要な記号や数字は削除しておきます。

# coding: utf-8

require 'csv'

# replace Non-Alphabet
def replace_stopword(str)
  str.gsub(%r!\W|_|\d!, ' ')
     .gsub(/(  +)/, ' ')
     .strip
end

def reset_by_agent_type(row)
  case row[:agent_type]
  when 'Crawler'        then 'Crawler'
  when 'Librarie'       then 'Librarie'
  when 'Cloud Platform' then 'Cloud Platform'
  else row[:agent_name]
  end
end

csv     = CSV.table('./user_agent.csv', headers: true)
headers = csv.headers.push(:processed_user_agent)

CSV.open('./processed_user_agent.csv', 'w') do |processed_csv|
  processed_csv << headers
  csv.map do |row|
    row[:agent_name] = reset_by_agent_type(row)
    row[:processed_user_agent] = replace_stopword(row[:user_agent])
    processed_csv << row
  end
end

こんな感じかな。

モデル(判定ロジック)の構築

User Agentの文字列は、それぞれ一意なデータなので形態素解析をして文字列の出現有無の行列を作ってあげます。

さて、ここからはRを使って形態素解析と決定木を実行してみます。
なお、形態素解析はRMeCabを使いますが、CRANにRMeCabが登録されていないようなので、インストールするにはreposを指定してあげる必要があります。

# install.packages("RMeCab", repos = "http://rmecab.jp/R")
library(RMeCab)
library(rpart)

setwd('/path/to/dir')
df <- read.csv('processed_user_agent.csv', head = T)

d <- t(docMatrixDF(df[,'processed_user_agent']))

データの読み込みと、User Agentの形態素解析 + 行列化ができました。
docMatrixDF()を実行すると、行列が入れ替わってしまうので、t()で転置しておきます。

agent_type(browserの種類)の判定

まずはagent_typeから。
rpartで学習して、できた木構造をプロットします。

train.agent_name.data <- cbind(df['agent_name'], d)

train.agent_name.tree <- rpart(agent_name ~., data = train.agent_name.data, cp = -1)

plot(train.agent_name.tree, uniform=T, branch=1, margin=0.01)
text(train.agent_name.tree)

グシャァ...

スクリーンショット 2014-12-22 12.30.15.png

終端ノードで同一ブラウザがでているので、判定ロジックとしては不要な分岐がたくさん出てきてしまっています。

summary(train.agent_name.tree)

# 抜粋
#            CP nsplit rel error    xerror       xstd
#1  0.273170732      0 1.0000000 1.0000000 0.03887217
#2  0.253658537      1 0.7268293 0.8292683 0.04159051
#3  0.219512195      2 0.4731707 0.5170732 0.04027518
#4  0.043902439      3 0.2536585 0.2536585 0.03194866
#5  0.003252033      4 0.2097561 0.2243902 0.03041471
#6  0.000000000      7 0.2000000 0.2585366 0.03218850
#7 -1.000000000     15 0.2000000 0.2585366 0.03218850

cp(complexity parameter)が0の時にすでに相対誤差(rel error)が最低値になっています。そのわりに分割数(nsplit)が多いので、cp値で調整してあげればよさそうです。

cp値を0にして再実行

train.agent_name.tree <- rpart(agent_name ~., data = train.agent_name.data, cp = 0, maxdepth=6)
plot(train.agent_name.tree, uniform=T, branch=1, margin=0.01)
text(train.agent_name.tree)

プロットした結果は...

ss2014-12-22_2.12.05.png

うん、これなら良さそうですね。

plotの図で0.5以上/未満とでているのは、User Agentの中にその単語が含まれるか含まれないかということを表しています。
たとえば、一番右端の"Chrome >= 0.5"となっているものは、User Agentに"Chrome"という単語が1つ以上含まれていた場合は、agent_typeがChromeと推測されるわけです。推測された結果がどの程度正しく判定できているかは、summaryで出力した結果の"expected loss"にでてきます。

実際に判別ルールを書く場合は、この決定木の通りの条件分岐を書いてあげれば再現できます。

os_nameの判定

では、先ほどと同じようにOSも判定してみます。

train.os_name.data <- cbind(df['os_name'], d)
table(train.os_name.data[,1])

train.os_name.tree <- rpart(os_name ~., data = train.os_name.data, cp = -1)
plot(train.os_name.tree, uniform=T, branch=1, margin=0.01)
text(train.os_name.tree)
summary(train.os_name.tree)

#             CP nsplit rel error    xerror       xstd
#1  0.353488372      0 1.0000000 1.0372093 0.03466982
#2  0.158139535      1 0.6465116 0.6465116 0.03999625
#3  0.083720930      2 0.4883721 0.4883721 0.03832027
#4  0.046511628      3 0.4046512 0.4046512 0.03647981
#5  0.032558140      4 0.3581395 0.3813953 0.03583517
#6  0.004651163      5 0.3255814 0.3581395 0.03512692
#7  0.000000000     10 0.3023256 0.3395349 0.03451189
#8 -1.000000000     16 0.3023256 0.3395349 0.03451189

こちらもグシャァ...

スクリーンショット 2014-12-22 12.41.45.png

先ほどと同じようにcp値0で相対誤差が最低になっているので、再度同様に実行してみます。

train.os_name.tree <- rpart(os_name ~., data = train.os_name.data, cp = 0, maxdepth = 5)
plot(train.os_name.tree, uniform=T, branch=1, margin=0.01)
text(train.os_name.tree)

ss2014-12-22_2.29.01.png

Windows7とWindowsXPの判定が少し厄介なものの、先ほどよりはまともになりました。(expected lossが高めですが…)

まとめ

ということで、決定木を使ってルールベースのUser Agent判別ロジックを探してみました。
今回は深く踏み込んでいませんが、意図しない文字で形態素が分割されていたり、分割結果によっては誤判定率の高いものがあったりします。そういったものは、MeCabのUser Agent用辞書を準備したり、ブラウザの判定結果をOSの予測で利用するなどで、精度向上の余地はまだまだありそうです。

データの準備や前処理などの手間はあるものの、複雑なルールベースのロジックを作る際には、決定木を使うのもありかなと思いました。

さて、明日(12/23)はhiro_kobaさんです。
会社でAdvent Calendarをやるのは、プレッシャーもありつつなかなか楽しいですね。masahixixiさん、企画ありがとうございました。

こちらからは以上です。

30
29
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
30
29

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?