Paradigm Shift Design

ISHITOYA Kentaro's blog.

趣味プログラミング

徒然

最近、忙しかったけど少しだけ余裕がでてきました。
ので久しぶりに記事を書こうかなと思ったけど、気合を入れちゃいそうなのでガス抜きに適当なエントリを書こうと思う。


やっぱりなにごとも継続することが重要だとおもうのです。飽きっぽいから。
ギターは2年くらい練習しているけれど一向にうまくならず。CとGとDとAmとEとBとFだけ覚えて、じゃかじゃかやってれば弾ける曲で、音痴に歌って楽しんでるだけだけど。なんとなく弾けるようになったのは、2年間やってるからで。


まぁ継続は力なりというので、趣味プログラミングも続けていきたいと思っているんだけれども、もうそろそろ経緯を忘れてしまいそうになってきたので、メモっておく。


2月の頭くらいに先生にTimeMachineBoardで利用する辞書を作ってくれと言われて、Blogを形態素解析するプログラムを作ったのがきっかけで、思いついたことがあった。
思いついたことがなんなのかは、いつもできたらいいなで終わっているので、できるまでは書かない。


まずHatenaの記事をRecursiveに取ってきて形態素解析するクローラーを作った。確か3月の始めに思い立って、3月末にはできていたと思う。その過程で自分の作業用PCで動かすのに限界を感じたので、安いケースを買ってきてサーバーを一台でっち上げた。
それが、

あたり。


次に、そのエントリ群を分類したいと思ってNMFを使おうと思った。NMFを知ったのはどこでかというと、情報処理学会の全国大会で「動画共有サイトにおけるコメントを用いた動画分類の細分化手法」というニコニコ動画のコメントをクラスタリングしますみたいな話があって、そこでアルゴリズム名を知り、

集合知プログラミング

集合知プログラミング


を買った。
で実装してみたけれど、2日経っても1回目のイテレーションが終わらず、苦し紛れに人力検索してみた。
趣味で、ブログエントリを形態素解析し語のTFIDFを取得して、NMF.. - 人力検索はてな


計算量が多いのが問題なのだということに気がついて、疎行列なるものの存在を知り、実装してみるが、2日経っても1回目のイテレーションが終わらず。
そもそも対象としているエントリの集合が大き過ぎるのだと思い、調べてみるとCiNii 論文 - 

Non-negative Matrix Factorizationを用いた情報検索モデルの次元圧縮および検索質問拡張


という論文を発見したので、クラスタリングをしてからNMFをかけることにする。


クラスタリングアルゴリズムを調べると、k-means、K平均法というのが普通のやり方で、ぐぐるとk-means++というのがあることを知ったのがクラスタリングアルゴリズムk-means++のコードをPHPにポートした - Paradigm Shift Designのあたり。


･･･k-means++を実装して、最初に実行した時は1回のイテレーションが5時間ほどかかって絶望した。で、また人力検索してみた。
下記スクリプトの関数distanceSquaredPointsの実行速度を上げる.. - 人力検索はてな
id:kn1967さん、id:Mookさんに御教示賜り、24時間ほどで処理が終わるようになった。


期待に胸を膨らませて結果を見るに、クラスタが異常に偏っていてさらに絶望した。ので、やはり苦し紛れに人力検索してみた。
三次元空間にある複数の点を、大きな偏りのないようにいくつか選.. - 人力検索はてな
しかし、やはり苦し紛れすぎてどうにもならないので、アルゴリズムに問題があるのではないかと思って色々調べると神嶌敏弘さんのページで"データマイニング分野のクラスタリング手法(2) − 大規模データへの挑戦と次元の呪いの克服 −", 人工知能学会誌という記事を見つけ、「次元の呪い」とか言う格好いい現象に直面しているのだということを知る。


で、次元数を減らす必要があるということを知り、上の文献にあったFastMapというアルゴリズムを実装してみた。･･･が、どうもデータがきちんと埋まっていると次元縮約がうまくいくのだけれども、疎行列ではうまく縮約されないというか、全ての点が同じ所に射影されてしまってきちんと動かず。
それが4月中の成果かな。


そして、今、FastMapを改良した

というアルゴリズムがあることを知り実装中と。


しかし、この泥沼から抜け出ることはできるのだろうか。
6月末には、アプリケーションとしてリリースしたいんだけどなぁ。
まぁ、趣味趣味。
趣味で論文読んでプログラム書いているっていうのは、なんか勉強してるんだか趣味なんだか、よく分からないけれど妙に充実してます。


というわけで次はもう少しましなことを書きます。