エンジニア長期インターン GREE Studio 2010 5日目

前回に引き続き、井上が書かせていただきます。
GREE Studio 2010 5日目の講義内容はデータマイニングエンジニア、moritaさんによる「データマイニング」。業務のログ解析において用いられるデータマイニングの内容です。前回はレポート形式でしたが、今回はもう少しエンジニアリングブログに近い形で書こうと思って頑張りました。宜しくお願いします。今回のブログの内容は、

  1. データマイニングの基礎知識
  2. 大規模データへの挑戦

になります。後で定義しますが、ここでの「データマイニング」とはデータを取得し、集計する作業も含めてこの言葉を指すことにしています。また、解析者とはデータマイニングを行う人のことを指します。(GREEではデータマイニングエンジニアと呼ばれています。)moritaさんの講義で学んだことを自分なりに膨らましてみました。色々誤りがあると思いますが、そういった部分は(優しく)指摘していただけると幸いです。

1.データマイニングの基礎知識

ここではデータマイニングの定義や手法、活用事例について述べさせていただきます。

定義

データマイニングの定義は色々ありますが、ここでは

企業に大量に蓄積されるデータを収集・集計する技術
データを解析し、その中に潜む項目間の相関関係やパターンなどを探し出す技術

を指すことにします。前述しましたが、前者のデータの収集・集計作業を含めてこの言葉を指すようにしました。その理由は、

  • サービス規模の増加による分散技術の導入によってデータ(ログ)がネットワークを通じて散在している
  • データのサイズが非常に大きくなっているために、前処理や平均などの簡単な統計計算さえも簡単にはできない

といったように、特に大量のユーザーを抱えるWeb企業においてはデータを収集、集計することさえも困難になり、それらを行う事自身に技術が求められるようになってきたからです。それを支援するためのHadoopなどの大規模分散データ処理技術が近年注目されています。

後者は従来から使われていた意味で、データに潜む顧客のニーズや行動パターンを「鉱山」に見立て、それらを「採掘(mining)」するところから来ています。

データマイニング分野のクラシカルな技術

伝統的なデータマイニング技術(手法)は大きく5つに分類されます:

  • クラスタリング
  • 分類
  • 相関
  • 回帰
  • 確率モデル
  • クラスタリング

データの集合を(何らかの特徴によって)グループ分けしたい場合に用いられます。事前にグループの分け方を人間が定義するのではなく、入力されたデータに対して、機械が自動的に「似ているもの」でグループ化する手法です。クラスタリングによってできたグループをクラスタと呼びます。
ここで、似ているかどうかの指標には類似度や距離を利用することになり、様々な手法が考案されています。類似度も距離も数値で表現されますが、ある2つのデータに対して、類似度は大きい方が、距離は小さい方が似ているとされます。
ここで重要なのは、グループの分け方には正しい答えが無いことです。使用する類似度や距離によって結果は大きく変わってきます。様々なパターンを検証し、目的にあった答えを導くといったプロセスは非常に重要です。
代表的な手法:最短距離法、最長距離法、ウォード法、k-means法

  • 分類

分類とは、与えられた個々のデータが(あらかじめ定められた)カテゴリのどれに所属しているのかを予測する手法です。カテゴリとは例えば男女や年齢層といった、そのデータが本来持っている属性であることが多いです。カテゴリが不明のデータに対して、ヒント(他の指標)と過去の経験(学習)を基にして機械にどのカテゴリに属しているかを予測させる手法です。
代表的な手法:ナイーブベイズ、決定木(C4.5, CART)、サポートベクターマシン

  • 相関

大量のデータから頻繁に同時に発生する事象同士を「相関が強い事象」の関係として抽出する技術を指します。POSやEコマースの取引ログに含まれる購買履歴を利用したバスケット解析というのが有名です。
例:商品Aを買った人は商品Bも併せて買う人が多い → 両者を近い場所に置く。
代表的な手法:apriori

  • 回帰

回帰とは既存のデータ(説明変数)を基に、対象の数値(目的変数)を予測する手法です。あるいは既存のデータに基づいて、将来の結果を予測する手法を指します。
代表的な手法:線形回帰、ロジスティック回帰

  • 確率モデル

確率を用いたモデルでデータ集合を表現する手法です。
代表的な手法:隠れマルコフモデル、ベイジアンネットワーク

データマイニングの活用事例

先ほどはデータマイニングに用いられる手法を紹介して、少し難しいと思われたかもしれませんが、実際にデータマイニングが企業で活用されている例は非常に多く存在します。

  • Amazonの類似商品リコメンド
  • 不適切コメントの自動チェックシステム
  • パーソナライズドWeb検索エンジン

といったデータマイニングがシステムに組み込まれている例や、

  • ブログやTwitterの評判分析
  • POSデータを使った会員分類
  • 企業評価(格付け)モデル
  • 名寄せ

のようにマーケティングツールとして用いられている例もあります。

2.大規模データへの挑戦

多くのサービスに日常的に用いられているデータマイニングではありますが、近年のインターネットの爆発的な普及に伴って、解析対象とするデータ(主にログ)のサイズが非常に大きくなってきました。そのために、今までのように解析の手法の研究だけにとどまらず、解析のためにどのようなアーキテクチャを構成するかも重要な問題になってきました。

大規模分散処理技術の発展

現在はこの問題への解決策として「1台のマシンではなく、複数のマシンで並列処理させる」ことが主流のようです。他にも「サンプリングによって全データ(母集団)を代表する少数のデータのみを解析して近似的な結果を得る」といったものがあるかもしれません。僕はつい最近まで「サンプリングを用いて近似的に解析する手法が重要」と主張していました(現在それに関連した研究をしています)が、HadoopのMapReduceなどの大規模分散処理技術の存在とその威力を知って、その主張を改めることになりました。
複数のマシンによる並列処理というのは以前から考案されていたものですが、Hadoopなどの出現によって、従来実装のハードルとされていた、

  • マシン間の通信
  • スケジューリング
  • データのキャッシュ
  • 障害発生時の対処

などがライブラリとして初めから提供されたことによって一般の人でも従来より手軽に分散並列処理を行う事が可能になりました。

機械学習へ適用の難しさ

しかしこういったMapReduceをはじめとする大規模分散処理がデータマイニング、特に機械学習に簡単に適用できるかは難しい問題とされてきました。その理由は相互に関連しあうデータや数値演算処理を複数のマシンに「独立に切り分ける」ことが難しいからです。基本的にMapReduceは、複数のマシンで独立に計算したデータを統合するというプロセスをとりますが、多くの機械学習のアルゴリズムでは処理を独立に切り分けるのが難しいので適用は難しいのではないか、という懸念がありました。

多くの機械学習でMapReduceが適用できる

しかしこの懸念を吹き飛ばし、「機械学習にもMapReduceが適用できる」と主張する人々が現れ、機械学習コミュニティは大きく盛り上がることになりました。それが
Map-Reduce for Machine Learning on Multicore(NIPS’06)です。これを契機に機械学習のMapReduceの実装や研究が盛んに進められることになりました。その有名なプロジェクトとして、Apache Mahout が挙げられます。

「和」の形で記述できるかがポイント

この論文の主張は、「Statistical Query Model という種類のモデルで記述可能な機械学習のアルゴリズムは MapReduceによる並列演算が可能である。しかも多くの機械学習のクラスはこのStatistical Query Modelに属する。」です。Statistical Query Modelに関しては僕も不勉強でうまく説明できないのですが、要はこの時にはアルゴリズムにおける計算式が和の形(Summation Form)で記述でき、各々の項を複数のマシンに振り分けて処理をさせ(Map)、最後に集約して和をとる(Reduce)ことができるというものです。

MapReduceが適用可能な機械学習

それでは(理論的に)Summation Formで表すことができ、MapReduceが適用できる機械学習アルゴリズムをリストアップしてみます。

  • Naive Bayes (NB)
  • Gaussian Discriminative Analysis (GDA)
  • k-means
  • Logistic Regression (LR)
  • Neural Network (NN)
  • Principal Components Analysis (PCA)
  • Independent Component Analysis (ICA)
  • Expectation Maximization (EM)
  • Support Vector Machine (SVM)

Mahout による実装

これらの機械学習に対して、現在Mahoutによって実装が完了しているものをリストアップしておきます。

  • Apache Mahout 0.1

    • Taste Collaborative Filtering
    • k-Means, Fuzzy k-Means, Dirchlet, Mean-Shift and Canopy
    • Distributed Naive Bayes and Complementary Naive Bayes classification implementations
    • Distributed fitness function implementation for the Watchmaker evolutionary programming library
  • Apache Mahout 0.2

    • K-nearest-neighbor and SVD recommenders
    • Random forests, frequent pattern mining using parallel FP growth
  • Apache Mahout 0.3

    • Parallel Dirichlet process clustering (model-based clustering algorithm)
    • Parallel co-occurrence based recommender
    • Parallel text document to vector conversion using LLR based ngram generation
    • Parallel Lanczos SVD(Singular Value Decomposition) solver

本日の講義を終えて

今回も普段では聞けないお話を聞けて大変勉強になりました。講義後は「企業とデータマインニング」のあり方について、現場のmoritaさんと色々議論できたのもとても貴重な機会でした。この中で一番印象に残った内容は、

「解析者こそ自社のサービスの一番のファンであれ」

企業におけるデータマインイングにおいては、選択(どういうデータや手法を用いるのか)と意志決定(結果から的適切なアクションを起こす)が非常に重要です。そしてそれを適切に見分けるためには、何より解析者自身がサービスに精通していないといけないということです。誰よりもサービスについて知っていなければ良い解析はできない、これは非常に印象に残るお言葉でした。

インターン中に、オフィスのエントランスが新しくなっていました。

Author: greestudio2010