はてなブックマーク

先週は言語処理学会の全国大会に参加してきたのですが、チュートリアル「推薦システム -機械学習の視点から-」で紹介されていた行列分解に興味が湧いたので実装しようと奮闘中です。とりあえず行列いじりの練習に、手元の本に説明があるNMF(Non-negative matrix factorization)を実装してみました。参考にした書籍は「Rで学ぶクラスタ解析」と「集合知プログラミング」です。 NMFはn×mの行列をn×k, k×mの2行列の積に分解する手法で、分解後の行列はクラスタリング結果としても利用できます。例えば文書の特徴をbag-of-wordsで表した文書-単語行列を分解すると、文書の各クラスタへの重要度を表す行列と、特徴語の各クラスタへの重要度を表す行列が出力されます。より詳しくは前述の書籍をご参照下さい。 作成したコードは以下の場所に置いてあります(汎用性のないコードだなぁ…)。

Twitterからデータを引っ張ってきたいと前から思ってたので、TwitterのStreaming APIを試し中。とりあえず1日分(2010/02/10 12:00 〜 2010/02/11 12:00)のデータを引っ張ってきてみました。ドキュメントはほとんど読んでないままやってるので、いろいろ間違ってるかも。 実際に引っ張ってくるコードはこんな感じ。ユーザ名、TweetのID、日付、Tweetの文面をタブ区切りで出力します。Config::Pitについてはここを参照。 #!/usr/bin/perl use strict; use warnings; use AnyEvent::Twitter::Stream; use Config::Pit; use Data::Dumper; use Encode qw(encode); my $config = pit_get('twitter.

クラスタリングツールbayonとOpenCVを使って、画像からbag-of-keypointsを特徴量として抽出する手順について書きたいと思います。bag-of-keypointsは自然言語処理でよく使用されるbag-of-words(文章を単語の集合で表現したもの)と同じようなもので、画像中の局所的な特徴量(keypoint)の集合で画像の特徴を表します。bag-of-wordsと同じ形式ですので言語処理と同じように、bag-of-keypointsデータを使ってクラスタリングツールに適用したり、転置インデックスに載せたりといったことが可能になります。 今回は画像からbag-of-keypointsを取り出し、そのデータを使ってbayonで画像集合をクラスタリングするところまでやってみます。ちなみに画像処理は完全に素人で、この記事もニワカ知識で書いているので、間違っている箇所やもっと効率

制約付きクラスタリング・半教師ありクラスタリングは、クラスタリングをする際に制約を与えることで精度を向上させる手法です。制約は2つのデータ間の関係を定義した、以下がよく使われるようです。 must-link 同じクラスタに所属しなければならない cannot-link 同じクラスタに所属してはならない 今回はとりあえず制約付きクラスタリングの論文で多く引用されていて、以下の論文を参考に実装してみました。手法がK-meansを少し改良しただけで一番簡単そうだったのと、最新の動向まで調べきれなかったので、まずはとっかかりとして。 "Constrained K-means Clustering with Background Knowledge", by Kiri Wagstaff, Claire Cardie, Seth Rogers, and Stefan Schroedl. ICML 20

昨年末に「平行コンピューティング技法」を読んで勉強していたのですが、せっかくなのでK-meansにOpenMPを使って高速化してみようと思います。OpenMPは簡単な構文を挿入することで、自動的にループの繰り返しを分割し、複数のスレッドにタスクを割り当ててくれます。 並行コンピューティング技法 ―実践マルチコア/マルチスレッドプログラミング 作者: Clay Breshears,千住治郎出版社/メーカー: オライリージャパン発売日: 2009/12/21メディア: 大型本購入: 12人 クリック: 598回この商品を含むブログ (38件) を見る 作成したコードは以下の通り。コンパイル・実行にはgoogle_sparsehashとOpenMPをあらかじめインストールしておく必要があります。 // K-means++ + OpenMP #include <cassert> #include

最近転置インデックスをゴニョゴニョしているのですが、インデックスの圧縮をするためにVariable Byte codeでの数字列の圧縮部分を作ってみました。アルゴリズムはIntroduction to Information Retrievalの5章Index compressionを参考にしています。 Introduction to Information Retrieval Variable Byte codeの部分 作成したコードは以下の通りです。数字列はソートして差分をとってから圧縮するようにしています。また符号化した後のchar *のサイズを別で持っておくのは面倒なので、数字列の先頭に数字列の個数を入れてから符号化しています。復号するときはまず符号化されたchar *から数字列の個数部分だけ読んでおき、後はその個数に到達するまで復号化します。 // // Variable Byt

普段使ってるdotfileをgithubに上げるために、Linuxの開発環境を少し整理してみた。 vimrcを整理 vimrcはかなり前に整理したものをずっと使ってたんだけど、周りの人の環境を聞いたり、VIMテクニックバイブルを読んだり>して以下のように設定を追加してみた。 NeoBundleでplugin管理 unite, neocomplcache などを追加 まだほとんど使いこなせてないけど、unite, neocomplcacheが便利。知らない間にvimもすごい便利になってたんだなあ…。 Vimテクニックバイブル　?作業効率をカイゼンする150の技 作者: Vimサポーターズ出版社/メーカー: 技術評論社発売日: 2011/09/23メディア: 単行本（ソフトカバー）購入: 17人 クリック: 594回この商品を含むブログ (35件) を見る tcshからbashに移行 Linu

前回のエントリでBayesian Setsを試してみたのですが、その時に書いたコードをAlgorithm::BayesianSetsというモジュールにまとめて、CPANにアップしました。生まれて初めてのCPANアップです。 http://search.cpan.org/~fujisawa/Algorithm-BayesianSets-0.01/lib/Algorithm/BayesianSets.pm すごいちっちゃいモジュールですが、これで僕もCPAN Authorの仲間入りかと思うとうれしいですね^^ 実用で使うのはちょっと厳しいかもしれませんが、なんとなくBayesian Setsを試してみるにはいいかと思います。 前回と同じように、タブ区切りのフォーマットのデータを入力として与える場合は、以下のようなコードで動きます。 #!/usr/bin/perl use strict; use

これまでにK-means++とfuzzy c-meansを使用したクラスタリングを試してきましたが、今回はpLSI(probabilistic latent semantic indexing, 潜在的意味インデキシング)によるクラスタリングを試してみようと思います。 pLSIは確率・統計的な枠組みで次元縮約を行う枠組みで、なかなか精度がよいらしく色々な論文で見かけます。Google NewsのレコメンドでもpLSIを使用しており、MapReduceで処理を並列化させて高速に実行しているそうです(論文読んでないので間違っているかも)。また入力ベクトルをあらかじめ重み付けしておく必要がなく、文書であれば単語の頻度をそのまま入力として使用できるのもうれしいところです。 より詳しくは以下のWikipediaのエントリか、書籍をご参照下さい。(書籍は処理結果の表8.4が並びがグチャグチャになってる

WEB+DB PRESS Vol.49 作者: arton,桑田誠,角田直行,和田卓人,伊藤直也,西田圭介,岡野原大輔,縣俊貴,大塚知洋,nanto_vi,徳永拓之,山本陽平,田中洋一郎,下岡秀幸,ミック,武者晶紀,高林哲,小飼弾,はまちや2,WEB+DB PRESS編集部出版社/メーカー: 技術評論社発売日: 2009/02/23メディア: 大型本購入: 10人 クリック: 373回この商品を含むブログ (45件) を見る Web+DB Pressのレコメンド特集に載っていたLocality Sensitive Hashを試してみました。あまりよく理解できてないので間違っているかもしれませんが、せっかくなのでブログに書いておきます。 作成したコードは以下に置いてあります。 http://github.com/mjmania/mining/blob/991a855fc378d831a057

昨日の記事で作成した、Wikipediaのキーワードリンクのデータを使って、HITSアルゴリズムを試してみます。 HITSはグラフ理論では有名なアルゴリズムで、リンク関係を使用してネットワーク中の重要なノードを特定する手法です。HITSで求められるノードには、AuthorityとHubの2種類があります。Authorityはその名の通りネットワーク中で権威のあるノードで、情報量が豊富であるなどといった特徴を持ちます。Hubは権威のあるノードに多くつながっているノードで、Webではリンク集ページなどに相当します。 考え方はPageRankと似ており、Yahooの検索でもHITSが使用されているらしいです。HITS具体的なアルゴリズムについては、解説しているページが多く存在するので、そちらを参照してください。 では実際にWikipediaのデータを使って、AuthorityとHubを求めてみま

今回はデータマイニングっぽい話ではなくて、ちょいネタで。昨日の記事でWP2TXTを使ってwikipediaのテキスト情報を取り出したので、これを使ってちょっと遊んでみます。以前プログラミング作法を読んだときに載っていた、マルコフ連鎖を試してみたいと思います。 プログラミング作法 作者: ブライアンカーニハン,ロブパイク,Brian Kernighan,Rob Pike,福崎俊博出版社/メーカー: アスキー発売日: 2000/11メディア: 単行本購入: 58人 クリック: 1,152回この商品を含むブログ (203件) を見る 作ったのはこんな感じ。そろそろコードのベタ張りはやめます。次あたりからはgithubにでも置きますかね。あれってちゃんとしたプロジェクトものしか置かない方がいいのかなと思ってたのですが、別に勉強用コードを置いてる人も結構いるんですね。僕も適当に置きまくろう。 #!/

以前にk-means++をPerlで書いたのですが、実際に試すデータがなかったのでそのまま放置してました。せっかくなので大きなデータで試してみたいので、今回は下準備としてwikipediaの各キーワードに対し、その特徴を表すデータを抽出したいと思います。そして今回作ったデータを使って、k-meansや階層的クラスタリングなど他の手法をいずれ試してみる予定です。 今回は特徴量としてベタにTFIDFを使うこととします。TFIDFについては、下記のページが詳しいためそちらをご参照ください。 形態素解析と検索APIとTF-IDFでキーワード抽出 tf-idf - Wikipedia まずWikipediaのデータをダウンロードしてきます。以下のページから、「jawiki-latest-pages-articles.xml.bz2」をダウンロードしてください。 http://download.wik

UbuntuでPDFを見るときに、デフォルトで起動する「文書ビューア」は日本語がたびたび文字化けしてちょっと使いものにならない。xpdf, xpdf-japaneseを入れればとりあえず日本語は読めるようになるけど、表示が汚すぎてちょっと使う気にならない…。 やっぱりPDFよむならAcrobatReaderが一番きれいだねってことで、UbuntuにAcrobatReaderを入れてみます。 Install Adobe Acrobat Reader 8.1.2 on Ubuntu 8.04 shibata(hi) shokudou: Acroread asian font packをubuntuへインストール 入れ方は上のページの通りです。メモ代わりにここにも書いておきます。 まずAcrobatReader本体をインストール。 % sudo wget http://www.medibuntu

http://d.hatena.ne.jp/kaiseh/20090113/1231864089 上の記事を見て、k-means++が面白そうだったので、ちょっとだけ試してみた。 k-meansは初期値に大きく依存するところが嫌い。初期値への依存度を軽減するために、初期値を変えて何回か試行してその中で一番良い結果のものを使用する、なんてことをしないといけない。そのため処理時間も馬鹿にならなくなってしまうので、ちょっとこれじゃあなあ…ということで使ってなかった。 でも今回のk-means++は初期値をうまく求めることで、精度と速度の向上が得られるらしい。これはうれしい！ 論文著者のページにサンプルコードがあったので試してみようと思ったんだけど、MFCを使っているみたいで僕の環境ではコンパイルできず…。 http://www.stanford.edu/~darthur/kMeansppTest