のんびり読書日記

日々の記録をつらつらと

Programming

確率的勾配降下法による行列分解を試してみた

前々回のNMF(Non-negative Matrix Factorization)に続いて行列分解ネタです。言語処理学会全国大会のチュートリアル「推薦システム -機械学習の視点から-」で紹介されていた、確率的勾配降下法による行列分解を試してみました。チュートリアルの資料は公開さ…

Bayesian Setsの特許について

別にブログに書いてもしょうがないかなーと思っていたのですが、同じような目に遭う方がいるかもしれないのでちょろっとだけ書いておきます。先日Stupaという関連文書検索システムを公開したのですが、その中で使用していたBayesian Setsというアルゴリズム…

NMF(Non-negative Matrix Factorization)を試してみた

先週は言語処理学会の全国大会に参加してきたのですが、チュートリアル「推薦システム -機械学習の視点から-」で紹介されていた行列分解に興味が湧いたので実装しようと奮闘中です。とりあえず行列いじりの練習に、手元の本に説明があるNMF(Non-negative mat…

Twitter Streaming APIでデータ収集

Twitterからデータを引っ張ってきたいと前から思ってたので、TwitterのStreaming APIを試し中。とりあえず1日分(2010/02/10 12:00 〜 2010/02/11 12:00)のデータを引っ張ってきてみました。ドキュメントはほとんど読んでないままやってるので、いろいろ間違…

bayonを使って画像からbag-of-keypointsを求める

クラスタリングツールbayonとOpenCVを使って、画像からbag-of-keypointsを特徴量として抽出する手順について書きたいと思います。bag-of-keypointsは自然言語処理でよく使用されるbag-of-words(文章を単語の集合で表現したもの)と同じようなもので、画像中の…

COP-KMEANS(Constrained K-means)を試してみた

制約付きクラスタリング・半教師ありクラスタリングは、クラスタリングをする際に制約を与えることで精度を向上させる手法です。制約は2つのデータ間の関係を定義した、以下がよく使われるようです。 must-link 同じクラスタに所属しなければならない cannot…

K-meansをOpenMPで並列化

昨年末に「平行コンピューティング技法」を読んで勉強していたのですが、せっかくなのでK-meansにOpenMPを使って高速化してみようと思います。OpenMPは簡単な構文を挿入することで、自動的にループの繰り返しを分割し、複数のスレッドにタスクを割り当ててく…

Variable Byte codeを試してみた

最近転置インデックスをゴニョゴニョしているのですが、インデックスの圧縮をするためにVariable Byte codeでの数字列の圧縮部分を作ってみました。アルゴリズムはIntroduction to Information Retrievalの5章Index compressionを参考にしています。 Introdu…

Perlでconstantを使うときの注意

この前CPANにアップしたモジュールでCPAN Testersの結果を見てたら、Perlのversion5.6.2で毎回テストに失敗してて、何でだろう?と思っていたらbug reportがきていた。 The syntax you are using to declare constants was not always supported. perl 5.6.2…

Algorithm::FuzzyCmeans と Algorithm::Kmeanspp を作った

なんとなくCPANにもっと上げてみたくなったので、昔書いたネタをパッケージングして上げてみました。とりあえず今回はFuzzy c-means clusteringと、K-means++。 Algorithm::FuzzyCmeans Fuzzy c-meansを試してみた - のんびり読書日記 Algorithm::Kmeanspp k…

freshmeatに登録してみた

せっかくオープンソースのプロダクトを作ったので、freshmeatにbayonを登録してみました。説明文をもっと分かりやすく、キャッチーにしないとダメですねぇ。 Bayon – Freecode 大したプロダクトでもないのでちょっと恥ずかしいですが、これ見て海外の人も使…

Algorithm::BayesianSetsモジュールをアップした

前回のエントリでBayesian Setsを試してみたのですが、その時に書いたコードをAlgorithm::BayesianSetsというモジュールにまとめて、CPANにアップしました。生まれて初めてのCPANアップです。 http://search.cpan.org/~fujisawa/Algorithm-BayesianSets-0.01…

Bayesian Setsを試してみた

この前YAPC Asia 2009に参加してきたのですが、そこで「はてなブックマークのシステムについて」の発表の中で、「はてブの関連エントリはBayesian Setsを使って計算されている」という話を聞いてBayesian Setsに俄然興味が湧いてきました。Bayesian Setsは以…

pLSIを試してみた

これまでにK-means++とfuzzy c-meansを使用したクラスタリングを試してきましたが、今回はpLSI(probabilistic latent semantic indexing, 潜在的意味インデキシング)によるクラスタリングを試してみようと思います。pLSIは確率・統計的な枠組みで次元縮約を…

STLのvectorとpriority_queueのソート用比較関数は不等号が逆

この前自分のソースを読んでいたら、両方とも降順にソートするために作った比較関数なのに何故か不等号が逆になっていて、「うわ、ひどいバグ作っちゃった?!」って慌ててテストしたら問題なし。調べてみると、STLのvectorとpriority_queueのソート用比較関…

Fuzzy c-meansを試してみた

K-meansは各入力ドキュメントがただ1つのクラスタにのみ属するハードクラスタリング手法ですが、fuzzy c-meansは所属度を持って複数のクラスタへの所属を許すソフトクラスタリング手法です。K-meansは以前に作りましたので、今回はfuzzy c-meansを試したいと…

google::dense_hash_mapのset_deleted_keyメソッド

google::dense_hash_mapを使うときは、データのinsertを行う前にset_empty_keyメソッドで空のとき用のキーを指定しておく必要がある。同様にキーの削除を行う前には、set_deleted_keyメソッドで削除されたとき用のキーを指定しておかなければならない。で、…

Wikipediaのリダイレクトを使って同義語とれるかな

wikipediaは同義語の単語(「ASIA」と「アジア」とか)は、代表的な単語にリダイレクトするようになっています。つまりリダイレクト関係にある単語は、大抵は同じ意味であることが期待されます。そこでこのリダイレクト関係を使って、同義語を抽出してみようと…

Yahooのキーフレーズ抽出APIを試す

Yahoo!デベロッパーネットワークでキーフレーズ抽出APIが公開されていたので、ちょろっと試してみました。 テキスト解析:キーフレーズ抽出 - Yahoo!デベロッパーネットワーク ただコマンドラインから文章受け取って、APIにリクエスト送るだけのスクリプト。 …

フラクタルを書いてみる

アルゴリズムC++を読んでいて、再帰の章でフラクタルが載ってたので、Python + PILで実際に図形を書いてみた。 全部同じ色 階層毎に色分け #!/usr/bin/env python # -*- coding:utf-8 -*- import Image import ImageDraw def fractal(draw, x, y, r): if (x …

Locality Sensitive Hashを試してみた

WEB+DB PRESS Vol.49作者: arton,桑田誠,角田直行,和田卓人,伊藤直也,西田圭介,岡野原大輔,縣俊貴,大塚知洋,nanto_vi,徳永拓之,山本陽平,田中洋一郎,下岡秀幸,ミック,武者晶紀,高林哲,小飼弾,はまちや2,WEB+DB PRESS編集部出版社/メーカー: 技術評論社発売日…

パーセプトロン作ってみた

会社でパーセプトロンの話が出てきて、ちょっと調べてみたら一番単純なパーセプトロンは非常に簡単そうだったので、試しに作ってみました。 http://ja.wikipedia.org/wiki/パーセプトロン 作ったコードは以下の場所に置いてあります。お勉強コードもすぐ見れ…

Wikipediaのデータでk-means++を試す

前にPerlでk-means++を書いたのですが、今回はk-means++をC++で書き直してみました。でも愚直に作ったので、非常に遅い…。大きめのデータだとちょっと使い物にならないのですが、せっかくなので作成したコードはgithubに置いてみました。 kmeanspp.cc ハッシ…

マルコフ連鎖で文生成

今回はデータマイニングっぽい話ではなくて、ちょいネタで。昨日の記事でWP2TXTを使ってwikipediaのテキスト情報を取り出したので、これを使ってちょっと遊んでみます。以前プログラミング作法を読んだときに載っていた、マルコフ連鎖を試してみたいと思いま…

TFIDFを使ってwikipediaの各キーワードの特徴量を抽出

以前にk-means++をPerlで書いたのですが、実際に試すデータがなかったのでそのまま放置してました。せっかくなので大きなデータで試してみたいので、今回は下準備としてwikipediaの各キーワードに対し、その特徴を表すデータを抽出したいと思います。そして…

ナンクロを解く(2) 解答

ナンクロを解く(1) 辞書作り - のんびり読書日記前回からちょっと時間が経ってしまいましたが、ナンクロ解きの続きです。前回はナンクロ用の辞書をDBMに保存するところまで作りましたので、今回は実際に問題を解かせたいと思います。まず入力する問題の形式…

ナンクロを解く(1) 辞書作り

前回はナンバープレイスを解いたので、今度はナンクロを解いてみます。ナンクロなんて知らない!という人は、wikipediaのナンクロのページを読んでください。http://ja.wikipedia.org/wiki/ナンバークロスワードナンクロを解くには、カナをつなげた単語がち…

ナンバープレイスを解く

Wikipediaネタが何回か続いたので、ガラッと話を変えてパズルを解いてみようと思います。wikipediaに飽きたわけじゃないですからね^^; まだあのデータを使って色々と遊べるので、その話はまた今度で。パズルのプログラムは結構好きで、ちょこちょこいろんな…

WikipediaのキーワードリンクでPageRankを試す

この前のエントリ(WikipediaのキーワードリンクでHITSアルゴリズムを試す - のんびり読書日記)ではWikipediaのキーワードリンクを使ってHITSを実行してみましたが、今回はPageRankを試してみたいと思います。PageRankの概要はもう説明するまでもないですね。…

WikipediaのキーワードリンクでHITSアルゴリズムを試す

昨日の記事で作成した、Wikipediaのキーワードリンクのデータを使って、HITSアルゴリズムを試してみます。HITSはグラフ理論では有名なアルゴリズムで、リンク関係を使用してネットワーク中の重要なノードを特定する手法です。HITSで求められるノードには、Au…