エスキュービズム ラボ Blog

階層クラスタリングは、データマイニング手法の一つです。
今回はこの手法を、はてなブックマークのタグ付けデータに対して適用しました。
まずは、結果から紹介します：

より大規模なデータセットを用いて解析した結果はこちら：
ツリー表現　タグクラウド表現　

=== 解説 ===

階層クラスタリングは、
「類似する要素をグループ化し、
徐々にそのグループもグループ化していき、
最終的に一つのグループにして、
階層的に要素およびグループを表現する」手法です。

上の例では、
“レシピ”と”料理”がまずグループ化されて、次に、そのグループと”食”がグループ化されています。
そのグループはさらに、音楽やアニメ、ゲーム関連の要素
（”音楽”、”music”、”アニメ”、”ニコニコ動画”、”著作権、”game”、”ゲーム”）
からなる階層的なグループと統合されています。
このようなグループ化が繰り返されて、最終的に一つのツリーになっているのが見て取れます。

今回は、入力データとして、はてなブックマークのタグ付けデータを用いました。APIから取得した、2008年6月から2009年3月までの、約8万件の記事に対して、どのタグが何回つけられたかというデータを用いました。各タグは約8万の要素数からなるベクトルで表現されますが、よりソリッドな結果を出すために、今回は、タグ同士の共起度をそのデータから算出したものを、タグ同士の類似関係を求める入力データとして用いました（上の記事×タグの行列データをVとすると、V^TVが今回の共起度行列となります）。上図の結果は、頻出する約100個のタグ同士の共起関係を基にしています。大規模版は、頻出する約1500個のタグ同士の共起関係を基にしたもので、次のような行列になっています：

クラスタリングする際に指標となるタグ同士の類似度は、上の様な共起行列の各行(or列)ベクトル同士の”距離”になります。このとき、この距離には、幾つかの定義があり、適当に最適なものを選びます。一般的には、ユークリッド距離やマンハッタン距離といった指標が用いられます。ただし今回は、試行錯誤から、ブレイ・カーティス距離というのを選びました。

次に、グループ同士の類似度を定義します。この類似度を基に、どのグループ(or要素)同士を統合するかが決まります。類似度の高いものから逐次的にグループを統合していきます。
グループ同士の類似度には、以下のような指標があります：
最短距離法、最長距離法、群平均法、ウォード法
（参考pdf）
この中で、個人的には、ウォード法がよく用いられているのではないかと思います。
ウォード法は、グループ内の分散を小さくし、グループ間の分散を大きくするように、グループを統合します。

最終結果は、一般に、上図あるようなデンドログラムと呼ばれるグラフによって可視化します。
グラフの木構造は、個々の要素がどのように統合されていったかを示します。
さらに、各ノードの高さは（上図では横軸）、そのノードの子グループ間の非類似度を表します。
大規模版では、デンドログラムが1画面に収まりきらないため、独自の表記方法を用いて可視化しています。

他手法と比べたとき、階層クラスタリングのメリットとしては、
デンドログラム等を用いて、直感的にデータ構造を把握することができることです。
特に、全体的な類似関係から、詳細な類似関係まで捉えられるのがいい点です。

デメリットとしては、
大規模なデータに対応できないということです。
計算量は、全ての要素間の類似度を計算する必要があり、
O(n²)となってしまいます。
今回、大規模版として約1500件のタグを解析しましたが、
現状、シングルマシンで解析するには、これくらいが限度です。
本当は全部で、約7万件のタグがあったのですが、これら全てを解析に含めるのは不可能です。
まあ、100件程度で十分だという見方もありますが。