2008年11月25日にソーシャルブックマークサービス「はてなブックマーク」がリニューアルされました（注⁠）⁠。新しいはてなブックマークのページ上部には，「⁠社会」「⁠生活・人生」「⁠コンピュータ・IT」などいくつかのカテゴリが並んでいます。このカテゴリ分類は，人手を介して行うのではなく，ブックマークされたページの本文を抽出して内容を解析し自動的に行っています。自動分類を行うアルゴリズムには，Complement Naive Bayesを利用しています。取り上げた記事では，このアルゴリズムの解説を行っています。

Complement Naive Bayesは2003年に発表された比較的新しいアルゴリズムで，「⁠実装が簡単」「⁠学習時間が短い」「⁠性能がそこそこよい」などの特徴があります。

記事ではまず土台となるNaive Bayesの解説を行っています。Naive Bayesの処理は，あらかじめカテゴライズされたデータをもとに学習する「学習フェーズ」と，カテゴリが未知の文書に対してカテゴリを推定する「テストフェーズ」に分かれます。学習フェーズではカテゴリごとに文書中単語の出現確率を学習します。そしてテストフェーズでは対象文書の各カテゴリでの単語出現確率を求めて，最も高確率なものを返します。

Naive Bayesは「そのカテゴリに属する文書」を使って学習していたのに対し，Complement Naive Bayesは「そのカテゴリに属さない文書」を使って学習を行います。これによりデータ量のバラつきによる影響をあまり受けないという効果が得られます。

ちなみにComplement Naive Bayesの実装として，Apache Mahoutという機械学習ライブラリが，Apache Luceneのサブプロジェクトに含まれています。

注）

『WEB+DB PRESS Vol.49』特集2「⁠［⁠新］はてなブックマーク 構築ノウハウ大公開」（⁠49ページ）で詳しく解説しています。

URL：http://d.hatena.ne.jp/tkng/20081217/1229475900