かれ4

かれこれ4個目のブログ

人間にはわかるのに、なぜ機械にはそれがわからないのか。A.I.とスクレイピング

この投稿は クローラー/スクレイピング Advent Calendar 2014の12月23日用です。


はじめに

人間って凄い。

まずはこの画像を御覧ください。

f:id:tottokug:20141223133132j:plain

図1 各国のECサイトの画像

Eコマースのサイトで、商品の詳細のページを見るだけですぐに商品名、価格を判断出来ましたよね?
それが英語のサイトでも中国語のサイトでも、韓国語のページでも分かりましたよね?
凄いですね。

人間のスクレイピング能力

人間は恐ろしいほどのスクレイピング能力を持っている事が分かりました。
ソースも見ない、タグも見ないで、なんとなく雰囲気だけでスクレイピングしています。

もしこの能力をコンピュータに移植できたら凄いことですね。


もし、先ほどの画像を身の回りのインターネットに一番疎い人に見せてみて下さい。
きちんととスクレイピング出来たでしょうか?
おそらく出来なかった事が多いのではないかと思います。

こんな事させて何させたいかと、人間のスクレイピング能力は生まれつき持っているものではなく、なんらかの学習のプロセスを経て手に入れたものだということです。

それも、人生における経験ではなく、インターネットに関する経験です。

この経験をもしコンピュータで実現出来たら、スクレイピングの自動化に近づくはずです。

なぜやろうとしたのか

もともと家電やPCの価格調査を行っていました。
そこから本業としてクローラのプラットフォームを作りました。
抽象化するべきところは抽象化し、プラットフォームとすることが出来たのですが、それはスクレイピングの運用の手間を極力減らすためのものであって、スクレイピングまで自動化するものではありませんでした。

例えば、Eコマース 100サイトから価格情報を収集したいとします。
その場合、100サイト分のスクレイピング用のコードを用意しなくてはいけません。
抽象化したところで、100サイト分の何かしらが必要になります。
これが決まった100サイトとわかっていれば、頑張れるかもしれません。
しかし、100サイトから増減していった時、ずっと対処し続けないといけません。
運用のコストばかり上がってしまい、疲弊していく事は目に見えてます。

この状況を打破するために、人間と同じような成長をし見分ける能力をコンピュータ上に作りたいと思いました。

どのようにやるか

人間がなぜスクレイピング出来るのかを真剣に考えました。

人間がスクレイピングしている時はどのように判断していくのか仮説を立てました。

  • 周辺にある単語から判断
  • 位置関係からの判断
  • 文字の大きさからの判断
  • 文字の色からの判断

この4つから判断しているだろうと考え、この4つを学習させるすべを考えます。
しかし、これには問題があります。

f:id:tottokug:20141223135450p:plain
画像2 レコメンドなどで複数の商品が同じページ内に載っている場合

このような場合、複数の抽出すべき項目があり、悩ましいです。

そこで、HTMLを分割することにします。

HTMLからブロックを抽出する

HTMLからブロックを抽出する方法ですが、これはDOMツリーを必要最小の範囲で抜き出すと言い換えられます。

f:id:tottokug:20141223170423p:plain
図3 全体のDOMツリーから、必要部分の抽出

では、これをどのように実装していくかという話になります。
大きくは、

  • タグに対してのスコアリング
  • スコアによるフラグ付
  • フラグの付いているタグをマージ

の3つの工程になります。

サイトの性質毎に特定の言葉(ECであれば税込や送料など)の存在に応じて、
全てのタグに点数をつけていきます。点数の付け方は、そこに含まれる単語とタグの深さを計算してつけていきます。
点数をタグの開いた順番に並べ、微分していきます。
微分した値にしきい値を設け、ブロックを構成する部品としてフラグを立てて置きます。
可視化すると先ほどの図2のようなページの場合は以下のようになります。
青がタグの深さ、緑がタグに付けられたスコア、ピンク色がフラグです。
可視化するとこんな感じになります。
f:id:tottokug:20141223155743p:plain
図4 タグのスコアリング

真ん中よりも少し左側にフラグが幾つか立っている所があります。
ここがメインの商品の情報になっています。
そして、真ん中から右側に周期的にフラグが現れている所がありますが、これがレコメンドによって表示されている商品です。

次はこれをブロックとしてまとめ上げる工程に入ります。
ここから先はHTMLをツリー構造と見た解析になっていくので、タグの事をノードと呼んで行きます。

バラバラと存在しているフラグ付されたノードをまとめる作業になるのですが、
親のノードからみて、子孫たちがどの程度フラグが立っているかというのを見ていきます。
もし、自ノードの配下のノードでフラグ付されているノードの数が多い場合は自分自身がフラグ付されて行きます。
この工程を何度か繰り返す事によって、ブロックを抜出します。

以下の図で説明すると、まずはピンク色がフラグ付されたノードになります。
フラグ付されたノードが子供の中に割合多くいた場合自分自身がフラグ付されるというルールに基づき、再度フラグ付されます(赤いノード)
全く同じルールにもとづいてルートノードから辿って行くことで、今度は青いノードが生まれます。

f:id:tottokug:20141223161415p:plain

f:id:tottokug:20141223161418p:plain

図5 フラグから必要最小の範囲の決定

このような工程を何度か繰り替えす事によって、抽出すべきブロックが導きだされます。
この工程は複数回やっても、あるところに集約されますが、だいたい一般的なHTMLの深さであれば、5回もやれば十分集約されます。

これでブロックが抽出出来ました。

ブロックから項目を抽出する

つぎにこのブロックから項目を抽出していきます。
抽出するためにはどのようにするのが良いのでしょう。

ここに機械学習的なアプローチを使っていきます。

この処理に入る段階で既に、ブロックとなっているため、ページ全体のノードの数に比べだいぶ少なくなっています。
だいたい20〜50位のノード位になっています。

これらのノードそれぞれで取得したい項目、例えば"商品名"や"価格"などに対してのそれぞれの尤度を求めて行きます。

下の図の青いノードが商品名かどうかを調べる場合を考えてみます。
青いノードの自己主張だけでは、怪しいので、ピンクのノードの意見も取り入れます。
ピンクのノードは青のノードの位置関係と、含まれる単語、タグ名、アトリビュートから青いノードが商品名のノードであるかどうかを主張します。
f:id:tottokug:20141223162939p:plain
図6 ノードが商品名らしいかの投票

ピンクのノードが満場一致で、この青いノードが商品名ですというのであれば良いのですが、そんな事はありません。
なので、ピンクのノードのみんなの意見を集約して、青いノードが商品名だと判断をしていきます。
こんな判断を全てのノードに対して行い、得票数が一番多いノード、かつ閾値を超えているものを商品名として判断します。

しかしこれだけだとピンクのノード全てが同じ重みで判断されてしまいますが、そんなことはないはずです。
なので、各タグに対しての重みの係数を与える事にします。
そして、この係数の調整は、遺伝的アルゴリズムを使って自動的に調整されるようにします。


この仕組によって、ノードが商品名であるのかどうかを判断し、抽出します。
スクレイピングの自動化が出来ました。


この仕組の現在とこれから

この仕組みは 特許を取得しています。
特許 第4959032号(2012年3月30日)

そして、サービスとしても提供しています。 hanamgri

しかし、β版リリースから数年たっても未だにβになっています。というのも、今は教師付きの学習が必要ですぐに使えるようなものではないからです。
今後Deep Learningでの特徴の発見が自動的に出来るようになれば、ユーザによる事前の学習を必要とせずに利用できると考えています。

ちょっと小難しい話になってしまいましたが、スクレイピングを機械にやらせようと思い、考えた仕組みの紹介でした。