行列分解ライブラリredsvdで潜在的意味インデキシングを試してみたの巻 - download_takeshi’s diary
久しぶりに自然言語処理的な話です。 すこし前にPFIの岡野原さんが公開されたredsvdを試してみました。 redsvd は行列分解を解くためのC++ライブラリであり、特異値分解（SVD)、主成分分析(PCA)、固有値分解などをサポートしています （中略） 例えば、行と列がそれぞれ10万、非零 の要素が100万からなる行列に対する上位20位までの特異値分解を1秒未満で行うことができます． １秒未満って、す、す、すごくねぇだべか？ というわけで早速導入してみますた。 インストール redsvdは内部の行列演算などにeigen3を使っているとのことなので、まずはこいつをセットアップ。あ、そうそうCMAKEも必要だよ。 ちなみに自分の環境でmake checkしたらエラーが少し出てたけど、気にせずそのまま突っ込んでみました。 続いてredsvdをインストール。 マニュアルサイト見ながらやれば問題
動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし（寅年）の日記
組み合わせ最適化の手法として「動的計画法」というモノがあります。 wikipediaから抜粋 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP） コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法 一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。 ナップサック問題と動的計画法 動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。 こんな感じの問題です。 今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各
クラスタリングツールbayonを便利に使うText::Bayonを書きましたよ - download_takeshi’s diary
JPerl Advent Calender 2009 のhacker trackに「Perlではじめるテキストマイニング」というタイトルで記事を書きました。テキストマイニング系のモジュールを色々紹介しているので、興味ある人はぜひご覧ください。 さてさて、記事の最後の方で軽くふれましたが、つい先日 Text::Bayon というモジュールをリリースしました。 Text::Bayon - Handling module for the clustering tool 'bayon' CPAN : http://search.cpan.org/~miki/Text-Bayon/ Github : http://github.com/miki/Text-Bayon それの具体的な使い方を紹介します。 何をするものか？ Text::Bayonはクラスタリングツールbayonをperlスクリプトからス
ギレンも登場！BM25なPerlモジュール書いたよ - download_takeshi’s diary
久しぶりに何か書きます。 情報検索のアルゴリズムで「BM25」というものがあります。 何年か前に某研究所に遊びに行ったときに「TF/IDFより精度のいいやつ」みたいな感じでかなりアバウトに教えてもらいました。 その時は「名前だけでも覚えて帰ろう」と思っていたのですが、帰りに安い居酒屋で大酒をのみ、電車のなかで騒いでしまうほど酔っ払ってすっかりその名前を忘れてしまってました。（なにやってんだか・・・） で、最近Web+DB pressをパラパラ見ていたらBM25の名前を発見！ああ、これだこれだ、思い出したよ！ というわけで、重い腰を上げてモジュール化してみました。 githubに上げてあります。 Lingua::JA::OkapiBM25 http://github.com/miki/Lingua-JA-OkapiBM25 そのうちCPANからも落とせるようになります。 正式名称は「Okap
Bayesian Setsを試してみた - のんびり読書日記
この前YAPC Asia 2009に参加してきたのですが、そこで「はてなブックマークのシステムについて」の発表の中で、「はてブの関連エントリはBayesian Setsを使って計算されている」という話を聞いてBayesian Setsに俄然興味が湧いてきました。Bayesian Setsは以前論文だけ少し読んで、あまりよく分からないまま放置していたのですが、せっかくなのでPerlで作って試してみました。 Bayesian Setsについて詳しくは、以下のリンク先の資料をご参照下さい。 Bayesian Setsの論文 Bayesian Setsの詳しい説明記事 bsets, The Bayesian Sets algorithm. (Matlabのコード) 実際に作成したコードは以下の通りです。上記のMatlabのコードを参考にさせていただいています。 #!/usr/bin/perl #
Epeg で JPEG ファイルのサムネイルを高速に生成する - bkブログ
Epeg で JPEG ファイルのサムネイルを高速に生成する Epegは JPEG ファイルのサムネイル (縮小画像) を高速に生成するライブラリです。JPEG に特化した手法でサムネイルの処理を行うため、内部的に画像をビットマップに伸張せず、高速かつ少ないメモリで処理できるのが特徴です。 インストール Epeg は Debian パッケージになっていないようなので、ソース (ダウンロード) からインストールしました Epeg は内部的に libjpeg を使っているため、Debian GNU/Linux では sudo apt-get install libjpeg62-dev で事前にインストールしておく必要があります。 Epeg そのものは ./configure && make && sudo make install でビルド・インストールできます。 サンプルコード Epeg の
String::Dictionary - naoyaのはてなダイアリー
String::Dictionary という Perl のライブラリを作ってみました。 http://github.com/naoya/perl-String-Dictionary/tree/master String::Dictionary は検索エンジンその他を作る時に必要になる「辞書」のためのデータ構造 + API です。辞書は単語の集まりですが、これを配列やハッシュなどで持つのではなく、単語をすべて繋げた一つの大きな文字列として保持することでメモリ領域を節約したものです。単語は単に文字列連結で持つだけでなく、Front Coding で圧縮しています。以下簡単な解説です。 辞書は例えば [0] ･･･ jezebel [1] ･･･ jezer [2] ･･･ jezerit [3] ･･･ jeziah [4] ･･･ jeziel ...という風に単語を配列で持つことで実現でき
全然必要ないんだけど、Moose化 - D-6 [相変わらず根無し]
全然必要ないんだけど、Moose化 Algorithm::BIT - http://d.hatena.ne.jp/naoya/20090606/1244284915 以下、全然そうする必要はなかったけど、敢えてMoose化をしてみた。なんとなく、例としてご参照ください。 ppackage Algorithm::BIT; use Moose; use MooseX::AttributeHelpers; use namespace::clean -except => qw(meta); has size => ( is => 'ro', isa => 'Int', required => 1, ); has data => ( metaclass => 'Collection::Array', is => 'ro', isa => 'ArrayRef', lazy_build => 1, p
Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
芸能人の相関関係を探ってみるスクリプト - download_takeshi’s diary
ちょっとした実験をしてみました。芸能人の相関関係を機械的に探索してみます。 具体的には「○○というタレントと関係が深い芸能人は？」といった、芸能人にフォーカスした類似検索みたいな実験です。 技術的には「潜在的意味インデキシング」（Latent Semantic Indexing）といった手法を使います。 これは普通は自然言語処理の世界で使われるテクニックですが、なにも言語だけでなく他のデータ素材でも面白い結果が得られるかもしれないので、やってみようという試みです。 以下に大まかな手順をまとめます。 wikipedia から有名人のリストを抽出 それらの有名人リストについて、一人ずつ「誰と関連が深いか」を集計。具体的には有名人個々のwikipediaのページ中に、先ほど抽出しておいた人名リストとマッチする人名がどれだけ掲載されているかをピックアップしていきます。 上記の方法で有名人の間の相関
Kansai.pmでコルーチンについて発表してきた - はこべにっき ♨
Kansai.pm#11にて「Perlで学ぶコルーチン」という発表をしてきました． だいぶ前のRuby勉強会でRuby 1.9のFiberをみてPerlでもいろいろやってみていたので，その時しらべたことを中心にぐだぐだとしゃべりました． Perlで学ぶコルーチンView more presentations from hakobe. コルーンは継続や並行処理などいろいろな概念がからんでいて調査がたいへんでした．PerlでのCoroの実装がどうなっているのかもう少し詳細に調査/発表できたらよかったです． スライドにも書いてますが，Ruby 1.9のFiberとまったく同じインターフェースをもったFiber.pmをつくってみました．githubで 公開しています． http://github.com/hakobe/perl-fiber/tree 以下のように簡単にFiber(=コルーチン)をつ
ダイクストラ法, 貪欲アルゴリズム - naoyaのはてなダイアリー
現実逃避をしながらウェブを眺めていたら ダイクストラ法（最短経路問題） にたどり着きました。単一始点最短路問題におけるダイクストラ法の解説です。 何を思ったのか、図を眺めていたところ動かしたい衝動に駆られて、気付いたらパワポでアニメーションができていました。 http://bloghackers.net/~naoya/ppt/090319dijkstra_algorithm.ppt 実装もしてみました。隣接ノードの表現は、ここではリストを使いました。 #!/usr/bin/env perl use strict; use warnings; package Node; use base qw/Class::Accessor::Lvalue::Fast/; __PACKAGE__->mk_accessors(qw/id done cost edges_to prev/); package Q
Locality Sensitive Hashing に挑んでみた - download_takeshi’s diary
久々のエントリです。 Locality Sensitive Hashing を perl で使うためのモジュールを書いてみました。Algorithm::LSHと名付けました。 先ほどDeveloper ReleaseとしてCPANにあげましたが、反映されるまで時間かかるので、興味ある方はcodereposからみてください。 Algorithm::LSH CPAN: http://search.cpan.org/~miki/Algorithm-LSH/ coderepos: http://coderepos.org/share/browser/lang/perl/Algorithm-LSH 超アルファバージョンな状態ですが、そのうちgithubにもupする予定。 そうそう、そう言えば WEB+DB PRESS Vol.49 にレコメンドエンジンの特集があって、その中に偶然にもLocality
PDL で PageRank - naoyaのはてなダイアリー
id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように
Yahoo! ウェブ検索 API で単語同士の近さを総当たりで調べる
Yahoo! ウェブ検索 API で単語同士の近さを総当たりで調べる 2009-02-26-2 [Programming][YahooHacks] あらかじめ用意された単語セットがあり、それぞれの単語同士の近さを検索ヒット数とそれによるシンプソン係数で求める手順について。 使用している Web API の提供が終了となったため、現在動作しません。ご了承ください。 Yahoo!デベロッパーネットワーク (YDN) のウェブ検索 API を用いる。 - Yahoo!デベロッパーネットワーク http://developer.yahoo.co.jp/ - Yahoo!デベロッパーネットワーク - 検索 - ウェブ検索 http://developer.yahoo.co.jp/webapi/search/websearch/v1/websearch.html ロジック やってることは、下記で書かれ
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
名義尺度間の連関係数を算出するperlモジュール - ダウンロードたけし（寅年）の日記
データマイニングを行う際に、適当な２つの変数にどれだけの相関関係があるのか確かめたくなったとします。 それらのデータはいわゆる「名義尺度」なデータ（地域別の野球チームの好き嫌いなど）だとしましょう。 名義尺度なデータ間における連関係数と言えば「クラメール係数」。 これをぱっと算出してくれるモジュールが欲しくなったので書いてみました。 Statistics::Associations - Calculates Association Coefficients of Nominal Scale. http://search.cpan.org/~miki/Statistics-Associations/ 使い方はこう。 use strict; use Statistics::Associations; my $asso = Statistics::Associations->new; my $m
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
YAPC::Asia 2009 1日目 「Perlで圧縮」の資料 - naoyaのはてなダイアリー
Algorithm-LSH-0.00001_01 - perl implementation of Locality Sensitive Hashing - metacpan.org