nakatani @ cybozu labs

IR の階層的クラスタリングを試すの続きです。
"efficient" な HAC(hiererachical agglomerative clustering) を実装してみます。
今回は、コード全体をぺたぺた貼り付けるのも見にくいし面倒だしということで、github に置いてみました。

git://github.com/shuyo/iir.git

前回作った corpus パックも commit してありますので、 clone すればいきなり動く、はず。

git clone git://github.com/shuyo/iir.git
cd iir/hac
ruby hac.rb 4million.corpus

おのおの手元でちょこちょこ改変して試してみるには CodeRepos より git の方が向いてるんじゃあないかなあと思ったんですが、git まだ使いこなせてないのでなんか色々間違ってるかも。

実装の説明に行く前に、まず前回の naive HAC (=single-link clustering) はなぜ inefficient だったか、という話を簡単に。

クラスタを近い(=類似度が高い)順に結合していくのが HAC の基本ですが、そうなると当然「クラスタ同士の類似度」を計算しなくてはならなくなります。
一番素直で簡単のだと、「クラスタ間で最も近い(類似度が高い)ベクトル同士の類似度を、クラスタ間の類似度とする」という方法があるのですが(これが single-link clustering)、これが「大きいクラスタほど有利」な計算方法であることは明らかでしょう。
このため、「大きいクラスタが、対象を一つずつ拾っていってしまう」という現象(chaining)が発生してしまい、クラスタリングとして役に立たなくなってしまうことがあるわけです。
それを解消するための方法として、IIR の 17.2～17.4 では single-link clustering 以外に complete-link clustering, centroid, group-average など、チェインニングが起きにくい「クラスタ同士の類似度」を紹介しています。これらの詳細については、ここでは省きますね。
前回も紹介した「クラスタリングとは (クラスター分析とは)」にもこれらの方法が載っています。ただし、こちらは類似度として(ユークリッド)距離を使用しているので、IIR の cosine similarity とは大小が逆だったり、距離の場合に有効な「ウォード法」が紹介されていたりします。

また、IIR 17.2.1 では、前回の naive HAC の計算量は Θ(N^3) だったのですが、priority queue を導入すると Θ(N^2 log N) にできるよ、という話をしています。

それらを合わせたアルゴリズムの pseudo code が掲載されているので、今回はそれに沿って実装してみるわけです。

英単語タイピングゲーム iVoca につきまして、以下の日程でメンテナンスを実施させていただきます。

・2009年2月16日(月) 18:00 ～ 20:00

メンテナンス中は iVoca をご利用していただくことが出来ませんので、ご了承ください。
メンテナンスが終了次第、サービスを再開いたします。

今回のメンテナンスにおきまして、以下の更新を予定しております。

• サイボウズ(R) ネットID のアカウントから、iVoca 独自のアカウントシステムに移行します。アカウントデータは移行されますので、ご利用のユーザーにおかれましては、別途アカウントを作成する必要はございません。
  また、mixi OpenID でご利用いただいていたユーザーにおきましては、従来通り mixi OpenID にて引き続きご利用いただけます。
• 学習データを公開および API で取得できるようになります。
• iKnow 連係機能を追加します。第１弾として、iKnow の単語リストを iVoca で学習することができるようになります。

本日、英単語タイピングゲーム iVoca をアップデートしました。
更新内容は次の通りです。

1. サイボウズ(R) ネットID のアカウントから、iVoca 独自のアカウントシステムに移行します。アカウントデータは移行されますので、ご利用のユーザーにおかれましては、別途アカウントを作成する必要はございません。
   また、mixi OpenID でご利用いただいていたユーザーにおきましては、従来通り mixi OpenID にて引き続きご利用いただけます。
2. 学習データを公開および API で取得できるようになります。
3. iKnow! 連係機能を追加します。第１弾として、iKnow の単語リストを iVoca で学習することができるようになります。

iVoca の認証はこれまで「外部認証のみ」だったわけですが、API をどうするか、などなどなどの頭の痛い問題がありました。
今回、iVoca が利用していた外部認証の一つ「サイボウズ(R) ネットID」がサービスを停止することになったので、これを機に独自認証の機能を提供することにいたしました。
これで API を提供できる道筋がついたので、まずは第一弾として、個人の学習履歴データを取得できるようにしました。

iVoca アカウントを設定し、公開設定を「公開」に指定した後、

http://ivoca.nsdev1/api/progresses/[iVoca アカウント名]

この URL にアクセスすることで、熱心に学習している５件のブックについて、日々の学習履歴が json 形式で得られます(フォーマットについては後日解説します……すいません)。

なお、従来「サイボウズ(R) ネットID」をご利用いただいていた方のログインID(メールアドレス)とパスワードは、上の注意書きの通りそのまま iVoca アカウントのほうに移行させていただいていますので、「ログイン」をクリックした後、iVoca アカウントのログインフォームにてメールアドレスとパスワードを入れてログインしてください。

mixi OpenID でご利用いただいていた方はそのまま引き続きご利用いただけますし、setting メニューにて iVoca アカウントも設定して、併用することも出来るようになっています。

そして、今回の目玉機能は iKnow! 対応です。

iKnow の API を利用して、iKnow の「学習アイテムリスト」を iVoca で学ぶ(遊ぶ)ことができるようになりました。
これにより iKnow の素晴らしい問題リストを iVoca で覚えられるようになっただけでなく、iKnow にて音声データのある単語はちゃんとゲーム中に発音してくれるようになっています。

• 基礎英語 ステップ１
• 【2008オバマ氏勝利演説：全音声付き】
• タグ「TOEIC」の一覧

ここに挙げたリスト以外にも、iVoca のユーザであればどなたでも、iKnow のどのリストでも iVoca で学べる(遊べる)ように登録することができます。
iVoca の iKnow メニュー から、iKnow のリスト画面の URL ( http://www.iknow.co.jp/lists/.... という形式のもの) を指定するか、同じ画面の iKnow リスト検索を使って利用したいリストを探してください。
なお、初めて iVoca にて利用するリストの場合には、学習データ初期化のための処理が10秒～１分程度かかります。

これほど素晴らしいデータを API で提供してくれているセレゴさんには、本当に感謝します。ありがとうございます。
これを第１弾として、逆に iVoca のブック(単語帳)を iKnow に登録する機能や、iVoca と iKnow の学習データを一元化して見せる機能とか、まずは iVoca でざっと覚えて、特に苦手な単語だけを選んで iKnow のリストを自動的に作るとかとか、いろいろ夢はふくらむんですが、順番にちょっとずつ、ですね。
まずは「問題の長さをもうちょっと長くできると嬉しい」という要望をいただいているのに、まだほうったらかしなので、こちらをやっつけるところからでしょうかね。

なお発音機能は Flash Player にて、バックエンドで iKnow アイテム情報を順次取得して実現しています。そのため、音声を発音するようになるまで少し遅れたり、ごく一部の単語のみしか発音してくれない、という状態になる場合があります。iKnow が混雑する時間帯は特に起きやすいようです。
改善を図りたいと考えてはいますが、あらかじめご了承ください。