プチ間空きましたが、「IIR の「効果的な」階層的クラスタリング」の続き。
「次回は feature selection で次元を落とすのを試してみるべき」と書いたとおり、feature selection(特徴選択)を行ってみます。
要は「２５文書しかないのに 8000 語とか多すぎる。文書増えてったらガクブル。よし減らそう。全部必要な訳ないしね。でも、どうやって？」という話です。
IIR では、Chapter 13 にて feature selection を扱っており、 また Chapter 18 では LSI(latent semantic indexing)、乱暴に言えば固有ベクトルを求めることでその空間が本来持っている次元数(階数)を導いている。
しかし、Ch.13 の内容は Bayesian のような「教師有り分類」の場合の feature selection しかカバーしておらず。
固有ベクトルを求めるのは bag of words の世界で本質的に最も正しい気はしますが、追加学習のコストが高そう。
Web などの文書も単語もあとからあとから追加されるシチュエーションでは、なかなかしんどそうです(現在の個人的な印象。いい方法があるのかもしれません)。
というわけで がちゃがちゃ検索して適当な論文を探してみました。
2002 CADIP Research Symposium で発表されたとおぼしき "Feature Selection and Document Clustering" が、k-Means など「教師無し分類」における feature selection の効果的な手法を取り扱っていたので、これを実装してみることにしました。
その論文で紹介されていた手法は大きく分けて３つ。
- Term variance quality
- Same context terms
- Spherical Principal Directions Divisive Partitioning
１つ目と２つ目はどちらも単語ごとにある種の評価値を計算して、上位××語を選ぶというもの。
３つ目は分類の手法に依存していて、HAC では使えません。
Term variance quality
Term variance quality (分散特性、かな？) では２種類の評価式があります。
q_0(t) = Σf^2 - (Σf)^2 / n_0
q_1(t) = Σf^2 - (Σf)^2 / n_1
ここで f は各ドキュメントにおける単語 t の出現回数( term frequency )であり、Σ はドキュメント全体にわたってその和を取ることを表しています。また、n_0 は「全ドキュメント数」、n_1 は「 t が出現するドキュメント数」です。
２つの式の違いは第２項の分母のみ。q_0(t) はもう一回 n_0 で割ればいわゆる分散そのものですね。
これらを実装したものは例によって github に。
git://github.com/shuyo/iir.git
$ ./fselect.rb -n 1000 -s -tq0 4million.corpus
とすれば、前回使用したコーパスファイルを読み込んで「 q_0 の式で評価し、上位 1000 語を抽出(stop words 除く)」して、同じフォーマットで 4million.corpus.q0 を生成します。
あとはこの新たに作成されたコーパスを使って、前回の hac を呼び出せばＯＫ。
ruby hac.rb 4million.corpus.q0
結果。
# without feature selection
$ ./hac.rb 4million.corpus
------------------------- TOBIN'S PALM
|| | || +---- BETWEEN ROUNDS
|| | |+------------------ THE SKYLIGHT ROOM
|| | | || | +------- THE FURNISHED ROOM
|| | | || +----------- AN UNFINISHED STORY
|| | | |+------------- THE GREEN DOOR
|| | | | +--------- THE CALIPH, CUPID AND THE CLOCK
|| | | | +------ BY COURIER
|| | | +-------------- SPRINGTIME A LA CARTE
|| | +------------------- AN ADJUSTMENT OF NATURE
|| +--------------------- THE BRIEF DEBUT OF TILDY
|+----------------------- THE GIFT OF THE MAGI
| | | | +-- SISTERS OF THE GOLDEN CIRCLE
| | | +---------- MEMOIRS OF A YELLOW DOG
| | +----------------- THE ROMANCE OF A BUSY BROKER
| +-------------------- A COSMOPOLITE IN A CAFE
| +---------------- MAN ABOUT TOWN
| | | +--- FROM THE CABBY'S SEAT
| | +-------- LOST ON DRESS PARADE
| +------------ MAMMON AND THE ARCHER
+------------------------ A SERVICE OF LOVE
| | +----- THE COMING-OUT OF MAGGIE
| | +- AFTER TWENTY YEARS
| +--------------- THE COP AND THE ANTHEM
+---------------------- THE LOVE-PHILTRE OF IKEY SCHOENSTEIN
# q_0/1000 words
$ ./hac.rb 4million.corpus.q0
------------------------- TOBIN'S PALM
|| | | | | +-------- THE CALIPH, CUPID AND THE CLOCK
|| | | | | +--- BY COURIER
|| | | | +----------- BETWEEN ROUNDS
|| | | | | +----- THE FURNISHED ROOM
|| | | | +--------- THE SKYLIGHT ROOM
|| | | +--------------- THE ROMANCE OF A BUSY BROKER
|| | +------------------ A COSMOPOLITE IN A CAFE
|| +-------------------- AN ADJUSTMENT OF NATURE
|+----------------------- THE GIFT OF THE MAGI
| | | | +---- SISTERS OF THE GOLDEN CIRCLE
| | | +------------- AN UNFINISHED STORY
| | +------------------- MAN ABOUT TOWN
| | | | | | | +-- FROM THE CABBY'S SEAT
| | | | | | +------ LOST ON DRESS PARADE
| | | | | +---------- MEMOIRS OF A YELLOW DOG
| | | | +------------ THE GREEN DOOR
| | | +-------------- MAMMON AND THE ARCHER
| | +----------------- SPRINGTIME A LA CARTE
| +--------------------- THE BRIEF DEBUT OF TILDY
+------------------------ A SERVICE OF LOVE
| | +------- THE COMING-OUT OF MAGGIE
| | +- AFTER TWENTY YEARS
| +---------------- THE COP AND THE ANTHEM
+---------------------- THE LOVE-PHILTRE OF IKEY SCHOENSTEIN
# q_1/1000 words
$ ./hac.rb 4million.corpus.q1
------------------------- TOBIN'S PALM
|| | | | | | ||+- BETWEEN ROUNDS
|| | | | | | |+-- THE FURNISHED ROOM
|| | | | | | +--- THE SKYLIGHT ROOM
|| | | | | +-------- BY COURIER
|| | | | +----------- THE CALIPH, CUPID AND THE CLOCK
|| | | +---------------- MEMOIRS OF A YELLOW DOG
|| | +------------------ THE COMING-OUT OF MAGGIE
|| +--------------------- THE ROMANCE OF A BUSY BROKER
|+----------------------- A COSMOPOLITE IN A CAFE
| | || | || +--------- MAN ABOUT TOWN
| | || | |+------------- AN UNFINISHED STORY
| | || | | +------- LOST ON DRESS PARADE
| | || | +-------------- MAMMON AND THE ARCHER
| | || +----------------- AN ADJUSTMENT OF NATURE
| | || | +------ THE BRIEF DEBUT OF TILDY
| | || +------------ SPRINGTIME A LA CARTE
| | || +---- THE GREEN DOOR
| | |+------------------- FROM THE CABBY'S SEAT
| | +-------------------- THE LOVE-PHILTRE OF IKEY SCHOENSTEIN
| +---------------------- A SERVICE OF LOVE
| +--------------- THE COP AND THE ANTHEM
| +----- AFTER TWENTY YEARS
+------------------------ THE GIFT OF THE MAGI
+---------- SISTERS OF THE GOLDEN CIRCLE
何をもって良いと評価するかが例によって悩ましいわけですが、特にどちらかの結果の方が分類にまとまりがあって(主観的に)望ましいということもなさそうです。
が、少なくとも「q_0 の結果の方が feature selection を行わなかった場合の結果に近い」ことは読み取れます。
実は元論文では、全く種類の異なる３つのコーパス群を用意し、それらを機械分類させたときに３種類のコーパスをそれぞれに分類できたか、という方法で feature selection 手法の評価を行っているんですが、 そこでも q_0 の方が q_1 より再現率が高いという結果が出ています。
論文は k-Means/Principal Direction Divisive Partitioning、ここでの実装は HAC と、全く異なる分類手法で同じ傾向を示したり(ここでの試行は件数少なすぎですが)、 式を見た瞬間は q_1 の方が筋がよいのではという印象がさっくり裏切られるのが、おもしろい。
Same context terms
q_0/q_1 は term frequency から簡単に計算できましたが、 Same context terms では、単語ごとの近さ(same context = 同じ sentence 中で使われているかどうか)を表現した "term profile vector" なるものを定義して計算に使用します。
全体は複雑なので、"term profile vector" のところだけ抜き出すとこんな感じ。
- term 全体 T = { t_1, ... , t_m }
- sentence 全体 { s_1, ... , s_n }
- term t の profile P(t) とは、t が含まれる sentence に含まれる term 全体とする。
- "term by sentence" matrix S とは、その要素 S_ij が sentence s_j に term t_i が出現する回数である (m x n) 行列。
- t_i の profile vector PV(t_i) は対称行列 (SS^T) の第 i 行列。すなわち その第 j 成分は、t_i と t_j の出現回数の積を sentence 全体にわたって和をとったもの。
この "term profile vector" を用いて、最終的に各単語の評価を算出するわけですが、その式も補正＆ペナルティでガッチガチに構成してあって、俺がヒューリスティックの見本を見せてやる！ な感じです。
頑張ってます。
そして、論文では同様に分類の再現性でこの手法の評価をしていますが、残念ながら q_0 や q_1 よりずっと再現性が低いという結果が記されていました。
empty document(残した単語が一つも含まれていない文書) も生じてしまっており、全くのダメダメとしか言いようがない状態です(なぜ補正＆ペナルティがいっぱいついているのか……わかりますねｗ)。
というわけで。
かなり計算量の多い面倒な手法＆結果はダメダメ、ということで実装のモチベーションが起きなくてスルーしました。すいません(苦笑)。
ここで試した feature selection は「都合のいい単語を選ぶ」という一番シンプルな方針。
「都合のいい」というのはイメージでは「できるだけバラバラ（イメージ）に選ぶ」ということで、「バラバラ（イメージ）」ということは偏りのある単語を選ぶのが有利な感じ。
評価の高い単語と同じ sentence に含まれると評価の上がりやすい Same context terms や、全体にまんべんなく出現している(= n_1 が大きい)と有利になる q_1 が、どちらも悪い結果が出てしまったのは自然なことでもあるのかな。
って、全て後知恵＆あくまで印象ですが。
コーパスをオープンソースのクラスタリングツール CLUTO 用のフォーマットで吐いて遊ぶ、というのもやってみたんだけど、長くなったのでまた今度。