O'Reillyの「集合知プログラミング」という本を買ってみました。この本はWeb APIや簡単なPythonのスクリプトを使って最近流行っているデータマイニングを広く浅く紹介している本です。
本当はもう少し統計的な面から捉えた、Rなどで説明している本を読もうかとも思ったのですが、僕から失われたWebサービス対する「勘」のようなものを取り戻すきっかけにならないかと思い、実際に公開されているAPIなどを多く利用しているこの本を選びました。
今回は、協調フィルタリングとクラスタリングを説明した２章と３章だけ読んで見ました。
第二章「推薦を行う」
協調フィルタリング(Collaborative Filtering)の説明です。これはAmazonの行なっているユーザの購入履歴から商品を推薦する機能や、似たようなアイテムを推薦する機能などに応用されている技術です。基本的なコンセプトは単純で、ユークリッド距離や相関係数でユーザやアイテムの類似度を測った後に、その類似度を重みとした加重平均を行ない、その結果を推薦度とします。主に、アイテムベースとユーザベースの2種類の方法があるそうです。
アイテムベース: まず、アイテム間の類似性を測り、ユーザが評価（購入）したアイテムに対し、その類似度に応じた加重平均をして、推薦度を算出。
ユーザベース: まず、ユーザ間の類似性を測り、その類似度に応じた加重平均をして（勿論、似たユーザの重みが大きい）推薦度を算出。
一般に、アイテムベースだと、アイテム間の関係はユーザ間の関係ほど頻繁に変わらないので、バッチなどで前もってデータを用意しておくことができるため、データのメンテナンスは必要になるがパフォーマンスは良く、疎なデータセットに対しても強いそうです。一方、小規模で変更が頻繁に起こるようなデータに対してはユーザベースが強いそうです。
第三章「グループを見つけ出す」
この章では教師なし学習の一種であるクラスタリングについて説明しています。第二章で測定したようなアイテムやユーザ間の類似度（もしくは距離）を元にして、似たアイテムをクラスタとして集めていくという方法です。本書ではブログをクラスタリング対象とし、ブログ内の単語の出現頻度をベクトル（列）とすることによってブログ間の距離を表現するという例を用いています。階層型クラスタリングとK-mean法によるクラスタリング手法を説明しています。
階層型クラスタリング:
まず個々のブログをクラスタとし、すべての個々のクラスタ間の距離を測り、一番近い２つのクラスタを結合し新たなクラスタとする、という処理を繰り返す。これにより、すべてのブログを階層的に並べることができます。すべてのクラスタ間の距離を測る必要があるため計算量が膨大（クラスタリング対象の数の二乗 x ベクトル数）になる。（学生の時に悩まされました。疎なベクトルに対して使えるトリッキーなベクトル圧縮や計算方法を利用した記憶があります。）ブログと単語の列、行を入れ替えても動作するが、行（単語）の数が多くなるため計算量が増し、列（ブログ）の数が減るため精度が下がる可能性が高い。
K-mean法:
まず、任意の数の重心ををランダムに配置し、それに近い単語群でクラスタを形成する。さらに、形成されたクラスタの重心から近い単語群で新たなクラスタを作るという処理を、クラスタ内の単語が変化しなくなるまで繰り返す。はじめに選択されてた重心に結果が左右されるが、個々の単語の距離を測る必要がないため高速に動作するという利点がある。
その他、形成されたクラスタの二次元座標へのプロットの方法なども解説してありましたが、今回は読み飛ばしました。
実際のWeb APIなどを利用しており、簡単なスクリプトの例によって説明しているためとても実用性の高い本だと思います。簡単なレコメンデーションシステムなら２章のコードをコピペしてしまうだけで作れてしまうでしょう。
今回は２章と３章を少し時間をかけて読み込みましたが、本書のイメージは掴めましたし、さすがに全部このペースで読んでレビューまでこなすのはヘビーなので、一度簡単に全体をポイントだけ理解しながら読みつつ、興味のある部分は改めて細かく見てみたいと思います。
で、僕から失われたWebサービス対する「勘」が多少なりとも戻ったかというと。「Amazonのこの部分の推薦はアイテムベースでを使っているだろう」とか、「この間話した携帯ゲーム会社の人が話していたHadoopのバッチ処理もこのアイテムベースの類似度データを作ってるんだな」、くらいのイメージは湧きます。でも何か応用できる分野が見つかるかと言われると、、、うーん、例えば広告のWebクリック率履歴を利用してユーザ毎にカスタマイズした広告を出すとか？いやー、そんなものGoogleとかで確実にもう実装されてるよな。もう少し訓練が必要ですね。
