データマイニングで使われるトップ10アルゴリズム

2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します（この論文は@doryokujin君のポストで知りました、ありがとうございます！）。

　必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。

データマイニングの基礎

View more presentations from Issei Kurahashi

1. C4.5

C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。

• CARTは2分岐しかできないがC4.5は3分岐以上もできる
• CARTはジニ係数を分割の指標にするがC4.5は情報ベースの基準を使っている
• CARTは木の剪定をクロスバリデーションによって行うため時間がかかるがC4.5は二項信頼限界を使うため一方行でできる

C4.5は1997年に商用のSee5/C5.0に改善され、以下のような変更点がありました（詳細はこちら）。

• ブースティングを組み込むことで精度が格段に上がった
• スケーラビリティが向上しているのでマルチコアCPUで有用

2. k-meansアルゴリズム

k-meansアルゴリズムは言わずと知れたクラスタリングの方法ですね。こちらのブログがとても視覚的に分かりやすかったので紹介させて頂きます（画像を使わせて頂いております）。

この画像の例では、2次元に分布しているデータを5つのクラスターに分けています。手法としては、次の2ステップを反復して計算します。

　Step 1. データの割り振り（一番近い中心に割りつける）
　Step 2. 平均値の計算（クラスター毎の平均値を計算する）

実用的には、「いくつのクラスターに分類するか」というkを事前に決定する必要があります。データから最適なkを推定する方法もいくつか提案されています（GAP推定量など）。

3. サポートベクターマシン

サポートベクターマシン（SVM）は機械学習の分野で最も代表的な手法です。SVMを学んだ際のに感じる主な疑問は「SVMの結果を解釈できるか？」と「SVMを連続値の予測に応用できるか？」の2ではないでしょうか。個人的にはSVMの結果の解釈は難しいと感じています。ただ、数%の予測精度の改善で売上が数千万も変わるようなビジネスの現場では、「結果の可読性」よりも「予測精度」を求められることも多いと思います。この2つはトレードオフの関係にありますので。また、SVMは連続値に容易に応用できます。パッケージによっては、特に指定しなくても連続変数を認識してそのようにモデルを作るものもあるでしょう。

　SVMに関してもう1つ気になるのは、学習（パラメータの予測）にかかる時間です。特にデータが数万を超えると、顕著に計算時間が増大します。これに関しては、core-vector machineという手法が提案されており、とても早く計算できるようです。

4. アプリオリアルゴリズム

アソシエイションルールの分析によって、高頻度のトランザクションを見つける際に最も良く使われる手法です。「土曜はビールとおむつがペアで買われる」というアレですね。以前みかけた記事によると、これはどうやら都市伝説みたいです。どこかの店舗でたまたま発見されたルールがインパクトがあったので広まってしまったが、全体のデータで試したらそんなルールは出なかったとか（web上の記事で読みました）。「部分集団で発見されたルールが全体には適応できない」という現象は分析をしていると良くある話です。

　アプリオリアルゴリズムは強力な結果を得ることができる割に、実装は他の手法に比べて難しくありません。ですのでデータマイナーにとっては最初に実装することのできる手法でしょう。近年のアプリオリアルゴリズムの顕著な発展は、FP-growth（frequent pattern growth、頻出パターン成長）という手法です。以下のようにデータベースをスキャンすることでルールを作成できます。データベースを2回しかスキャンしないので、アプリオリアルゴリズムよりも格段に早い手法です。

　Step 1. データベースを、全ての重要な情報を持つFP-treeという構造に圧縮する
　Step 2. 圧縮されたデータベースを、高頻度セットに関連する条件付きデータベースに分割し、それぞれをマイニングする

　他にも様々なトピックがあり、(1)分類学の組み込み、(2)インクレメンタルマイニング、(3)アイテムの連続変数の利用、(4)頻度ではない指標の利用、(5)アイテムセットよりリッチな表現（ツリーやグラフによる表現）、(5)閉じたアイテムセットなどがあります。

5. EMアルゴリズム

様々なモデルでパラメータ推定する際に使われるアルゴリズムです。モデル式が複雑になると数式展開では解を求めることができないので、EMアルゴリズムのような数値計算による最適化によってパラメータを求めます。論文では混合分布のモデルが紹介されています（なのでEMアルゴリズムというより混合モデルが良く使われるということでしょう）。

　混合分布がいくつのクラスター（正規分布）から出来ているかを決める必要がありますが、この最適な数を推定する方法がいくつかあります。BICを利用したり、尤度比検定を行ったりします。BICを使った最適化を組み込んだものに、MFclust関数という手法があります（以前、この記事で紹介しました）。EMアルゴリズムの説明のときは、k-means法と混合分布の話が良く出てきます。未確認ですが、正規分布を仮定すると、k-means法は混合モデルに帰着するのかもしれません。

6. ページランク

ページランクは1998年にSergeyによって提案されたサーチランキングを付ける方法です。そのアルゴリズムを元にサーチエンジンを開発したGoogleは大成功を収めました。本質的には、ハイパーリンクを投票のように解釈しています。しかし単純に投票数だけを見ているのではなくて、投票元のページも分析し、重みを付けています。

　様々な改善方法が論文で提案されており、より進んだトピックはこの2冊の本に紹介されています。

Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data (Data-Centric Systems and Applications)

Google’s PageRank and beyond: the science of search engine rankings.

7. アダブースト

1997年に提案された、アンサンブル学習と呼ばれる手法の1つです。いくつかの学習器を組み合わせることで、強力な予測性能を得ることができます。また実装も難しくありません（たった10行程度のコード）。

　多くの研究によればアダブーストは過学習しにくいことがわかっています。つまり、訓練データでエラーが0であっても、テストデータのエラーも減少できるという結果が出ています。どうしてこのような現象が起こるのか、ということについての研究もされています。Schapireらはこの論文でマージンを基にした説明を試みており、この説明が成功するとアダブーストとSVMの関連性が見つかることになります。

　現実に得られるデータは変数の次元がとても大きいことが多いです。このようなときは、次元縮約と変数選択（特徴選択）2つのアプローチがあります。次元縮約は数理的な意味づけはできますが、縮約後の変数は解釈をしにくいものになります（主成分分析など）。それに対して変数選択は解釈はしやすいものの、経験的に行われることが多いため数理的な基盤はありません。しかし、アダブーストは数理的な意味合いを持たせたまま、変数選択に利用できるのではないかという研究があります（論文）。画像の分野で主に研究されていますが、アダブーストを変数選択に応用することはとても重要なトピックでしょう（xboxのkinectによる認識技術も、アダブーストと類似のランダムフォレストで行われていると記憶しています）。

8. k-近傍分類

全ての訓練データを記憶してクラスタリングを行う、「まる暗記」型の分類器です。あるデータを、最も近いk個のデータの最多数のクラスに分類します。実装も理解するのも簡単ですが、訓練データを全て記録しておかなくてはならないのでコストが大きく、計算にも時間がかかります。

　分野によってはSVMのような高度な手法よりも性能が良いことがあります（遺伝子分野の論文）。進んだトピックとしては、精度を落とさないまま訓練データを減らす方法（condensing）、訓練データは減らすが精度が高くなる方法（editing）、近接グラフへの応用、ファジーアプローチなどがあります。

9. ナイーブベイズ

ナイーブベイズもクラスを予測するための手法です。構築するのが簡単で、パラメータ推定するために複雑な繰り返し計算が必要ありません。そのため大きなデータに対しても適用することができます。解釈もしやすく、性能もとても高いです。

　ナイーブベイズは簡潔であり、エレガントであり、ロバストであることから様々な分野で応用されています。最も古い手法であり、形も単純であるに関わらず、性能はとても高いです。テキスト分類やスパムフィルタリングで広く利用されています。また統計、データマイニング、機械学習、パターン認識の分野で様々な応用や改良がされています。ベイジアンネットワーク、boostedナイーブベイズのように進んだトピックもあります。

10. CART

1984年に出たこの本で提案されたCARTが、人工知能、機械学習、ノンパラメトリック統計学、データマイニングの分野でのマイルストーンになった。

Classification and Regression Trees (Wadsworth Statistics/Probability)

　CART（Classification and Regression Trees、分類と回帰木）は2分岐の決定木によってクラス、連続値、生存時間を予測する手法です。決定木に関しては以前この記事で概要を書きました。欠測値もカテゴリとして扱うことで、欠測のあるデータをそのままアルゴリズムに突っ込むことができることも利点の一つです。

読み終わっての感想など

以上です。正直言ってC4.5が1番に紹介されているのが意外でした。ブースティングを組み込んだC5.0がそれだけ強力なのでしょうか。しかしそれだとランダムフォレストも同じくらい強力な気もしますが、どうなのでしょうか。何年か前のKDDのコンテストで優勝した人もアンサンブル学習を使っていたみたいですし、過去10年から今後10年くらいはアンサンブル学習が最も強力なのかもしれません。

　こうして改めて勉強してみると、自分がどこまで理解しているのか分かって良いですね。「k-means法と混合分布モデルの違いは？」「アダブーストとランダムフォレストの違いは？」「ナイーブベイズとベイジアンネットワークの違いは？」など、もうちょっと勉強しなきゃいけないかなと。

　今やRでどの手法も手軽に利用できますが、歴史を考えると感慨深いものがあります。むしろこんなに簡単にできちゃって良いのかと思うくらいです。これからは先人達の偉業を噛み締めながら利用することにしましょう。そして次の革新的な手法も提案していきたいところですね。

　あとは、回帰モデルや判別分析などのような、古典的な統計手法は入っていませんでしたね。これらの手法はモデルの可読性に重点を置いているので、機械学習のように性能を追求する分野ではあまり使わないのかもしれません。データを解釈するときには良いのですが、実際にシステムに組み込むときには性能不足なのでしょう。また決定木は、回帰モデルよりもさらに可読性が高いので、人気があるのかなと思います。

おまけ

gihyo.jpというサイトの機械学習に関する連載がとても良いです。私もこれから時間を見つけて読んでみようと思います。