MapReduceのパターン、アルゴリズム、そしてユースケース - きしだのHatena
Ilya Katsov氏による「MapReduce Patterns, Algorithms, and Use Cases」の翻訳 http://highlyscalable.wordpress.com/2012/02/01/mapreduce-patterns/ (下書きに入れて推敲するつもりが、なんか公開されてしまっていたので、あとでいろいろ修正すると思います) February 1, 2012 この記事では、Webや科学論文で見られる異なるテクニックの体系的な視点を与えるために、数々のMapReduceパターンとアルゴリズムをまとめた。 いくつかの実用的なケーススタディも提供している。 すべての説明とコードスニペットでは、Mapper、Reducer、Combiner、Partitionaer、ソーティングにおいてHadoopの標準的なMapReduceモデルを利用します。このフレー
Rubyで作る実験的Quicksilverのようなもの - ザリガニが見ていた...。
前回探った、略語（Abbreviation）と関連するテキストを点数付けするアルゴリズムは、Quicksilverの使い勝手を左右する重要な要素の一つだ。とすると、このアルゴリズムを取り込めば、なんちゃってQuicksilverもどきが出来るかもしれない...。と思って、まったく実用的ではないのだけど、実験的なソフトウェアとして試してみた。 作業環境 MacBook OSX 10.6.2 ruby 1.8.7 (2009-04-08 patchlevel 160) [i686-darwin9] 以下、コード中に半角￥が見える場合は、すべて半角＼に置き換える必要があり。 Ruby版 scoreForAbbreviation Stringクラスを拡張して、to_scoreメソッドを追加した。 正規表現を利用して実装した。 マッチした部分とその前後の文字列が簡単に取得できるので、Objectiv
GeoHashのdecodeのアルゴリズムの解説します & ScalaのGeoHashライブラリを作ってみました(仮) - ( ꒪⌓꒪) ゆるよろ日記
GeoHash(http://en.wikipedia.org/wiki/Geohash)は、緯度経度を文字列のハッシュで表現する仕様です。 GeoHashにより表現された緯度経度の情報は、一つの文字列で緯度と経度という2次元の情報に加えて精度も表すことができるという特徴を持っています。 例えば、どうでしょうバカの聖地である北海道札幌市の平岸高台公園は、北緯43.025東経141.377ですが、これをGeoHashで表現すると、"xpssc0"となります。 この"xpssc0"というGeoHash表現は、「北緯43.0224609375から43.0279541015625の間で、東経141.3720703125から141.383056640625の矩形範囲」であり、座標はこの矩形範囲の中心点になります。 @masuidrive blogさんの緯度経度を文字列で表すGeoHash - @ma
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
NLTK Bookで教師なし形態素解析 - nokunoの日記
意外と知られていないようなので、NLTK BookのSegmentationの節にある教師なし形態素解析（単語分割）について紹介してみます。 この手法では、テキストを「単語の辞書」と「単語IDの列」で表したときにその合計サイズが最小になるように単語分割の位置を最適化します。言い換えれば、単語の出現確率に一様分布を仮定して圧縮したときに、その圧縮効率を最大とするように単語を分割します。持橋さんの研究よりはるかに単純なモデルですが、原理としては近いものになります。最適化にはシミュレーテッドアニーリング（焼きなまし法）を使っていて、適当に初期化してからランダムに単語分割位置を変えて、評価関数にかけて良い結果になったら採用する、という操作を繰り返し行うものです。 NLTK Bookでは、英語のテキストからスペースを取り除いたものを用いて単語を抽出しています。これはかなり恣意的に選ばれたテキストで、
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
転置インデックスを実装しよう - mixi engineer blog
相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。 デモ モチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java 6の日本語文書を対象としているので、「stringbuffer」とか「コンパイル」とか「倍精度浮動小数」とかそれっぽい用語で検索してみてください。 インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら（テンプレートはこちら）です。 でも、今回はUIの話ではないのです。ものすごく地味に、全文検索
Web上の膨大な画像に基づく自動画像補完技術の威力 - A Successful Failure
画像内に映り込んだ所望のオブジェクトを排除し、違和感の無い画像を生成するシーン補完技術に関しては近年複数の研究成果が発表されている。しかし中でも2007年のSIGGRAPHにて米カーネギメロン大のJames HaysとAlexei A. Efrosが発表した手法*1はブレークスルーとなりうる画期的なものだ。 論より証拠、早速適用例を見てみよう。本エントリで利用する画像はPresentationからの引用である。元画像の中から邪魔なオブジェクト等の隠蔽すべき領域を指定すると、その領域が補完された画像が自動的に生成される。 アルゴリズム 効果は抜群だがアイデア自体は単純なものだ。Web上には莫大な数量の画像がアップされており、今や対象となる画像の類似画像を一瞬にして大量に検索することができる。そこで、検索された類似画像で隠蔽領域を完全に置き換えてしまうことで違和感の無い補完画像を生成するのだ。
クラスタリングツール「bayon」を試してみた - download_takeshi’s diary
夜中の3時半過ぎですが、久しぶりになんか書こうと思います。 ちょっと前にmixiのfujisawaさんという方がすごくナイスなソフトウェアをリリースしてくれました。 「軽量データクラスタリングツールbayon」 http://alpha.mixi.co.jp/blog/?p=1049 今までにもCLUTOというすごく高精度なクラスタリングツールがありましたが、こいつはライセンス的にちょっとイケズな感じでした。そこにbayonがスーパーマンのように登場してくれました！「商用利用OKだよ」ということで、仕事の上での悩みが解決しました。本当にありがたいことです。 さてさて、早速使ってみたいんですが、ブログに書くのにちょうどいい題材がなかったので、以前に自分が書いたエントリからデータを持ってくることにしました。 「芸能人の相関関係を探ってみるスクリプト」 http://d.hatena.ne.jp
３Ｄ版！「K-Means法」ビジュアライズしてみた - てっく煮ブログ
前回の クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた が好評だったので、３Ｄ空間でも K平均法をビジュアライズしてみました。ちょっと重めなのでクリックすると始まります。さらにクリックして、１ステップずつ動かしてみてください。3次元にしてみると、宇宙空間のように見えてきて美しいです。前回からは数式の上ではほとんど変わってなくて、２次元空間上での距離だったのが３次元での距離になったぐらいです。K平均法については、前回のエントリ クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた をご覧ください。ちなみに、3次元座標の計算は、Flash 10 から導入された Matrix3D を使っています。ソースは [as]FP10をそろそろ。Matrix3Dとか [NUTSU] を参考にさせてもらいました。Zソートしてないので、たまに奥のものが手前に
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GC¥¢¥ë¥´¥ê¥º¥à¾ÜºÙ²òÀâ ÆüËܸì¤Î»ñÎÁ¤¬¤¹¤¯¤Ê¤¤GC¥¢¥ë¥´¥ê¥º¥à¤Ë¤Ä¤¤¤Æ¾ÜºÙ¤Ë²òÀ⤷¤Þ¤¹ ¥È¥Ã¥×¥Ú¡¼¥¸¥Ú¡¼¥¸°ìÍ÷¥á¥ó¥Ð¡¼ÊÔ½¸ GC ºÇ½ª¹¹¿·¡§ author_nari 2010ǯ03·î14Æü(Æü) 20:47:11ÍúÎò Tweet ¤³¤ÎWiki¤¬Ìܻؤ¹½ê GC¤È¤Ï¡© GC¤ò³Ø¤ÖÁ°¤ËÃΤäƤª¤¯»ö ¼Â¹Ô»þ¥á¥â¥ê¹½Â¤ ´ðËÜ¥¢¥ë¥´¥ê¥º¥àÊÔ Reference Counter Mark&Sweep Copying ±þÍÑ¥¢¥ë¥´¥ê¥º¥àÊÔ IncrementalGC À¤ÂåÊÌGC ¥¹¥Ê¥Ã¥×¥·¥ç¥Ã¥È·¿GC LazySweep TwoFinger Lisp2 Pa
GoogleのMapReduceアルゴリズムをJavaで理解する
GoogleのMapReduceアルゴリズムをJavaで理解する：いま再注目の分散処理技術（前編）（1/2 ページ） 最近注目を浴びている分散処理技術「MapReduce」の利点をサンプルからアルゴリズムレベルで理解し、昔からあるJava関連の分散処理技術を見直す特集企画（編集部） いま注目の大規模分散処理アルゴリズム 最近、大規模分散処理が注目を浴びています。特に、「MapReduce」というアルゴリズムについて目にすることが多くなりました。Googleの膨大なサーバ処理で使われているということで、ここ数年の分散処理技術の中では特に注目を浴びているようです（参考「見えるグーグル、見えないグーグル」）。MapReduceアルゴリズムを使う利点とは、いったい何なのでしょうか。なぜ、いま注目を浴びているのでしょうか。 その詳細は「MapReduce : Simplified Data Proc
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
mapee.jp
PHPでPageRankを計算するサンプルコード:phpspot開発日誌