クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
川柳の自動生成アルゴリズムの紹介（どうしたら 機械で川柳 詠めるかな）
こんにちは。エイプリルフールに 1 日だけローンチした Google 川柳、お楽しみいただけましたか？エイプリルフールが終わってしまったのでサービスはもうありませんが、せっかくなのでその裏側をすこしご紹介します。 今回は、Google が人工知能 CADIE を開発し、その CADIE が世界中で面白いサービスを提供するという設定で Google 川柳を提供しました。人工知能 CADIE は架空のものですが、コンピューターによる川柳の自動生成を行ったのは、ウソではありません。 ここでは、その川柳をコンピューターに生成させた手順を簡単にご紹介します。 川柳とは何かを学習する まず、本物の川柳/俳句を Web 上から集めました。集めた作品を解析し、俳句/川柳にありがちな品詞の並びパターンを学習しました。「瞬間」を切り取る 川柳/俳句には、「話題」が必要になります。これは、Web ページからラン
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
white page / junk / BWT in JavaScript (non-sentinel version)
This page is a demonstration of the Burrows-Wheeler Transform in JavaScript Language.
libdivsufsortのRubyバインディング - so what
http://storehouse.sakura.ne.jp/viewvc/viewvc.cgi/divsufsort/ruby/divsufsort.c?root=svn&view=markup http://divsufsort.rubyforge.org/ とりあえずbwt/unbwtだけ実装。 require 'divsufsort' include Divsufsort bwt = divbwt(<<-EOS) London bridge is falling down, Falling down, falling down, London bridge is falling down, My fair Lady. EOS unbwt = inverse_bw_transform(bwt) puts <<-EOS #{bwt} ----- #{unbwt} EOS 追記 divs
Sign in - Google Accounts
Not your computer? Use a private browsing window to sign in. Learn more about using Guest mode
ブロックソート - Wikipedia
ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) は、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) が開発した可逆変換の方式で、データ圧縮の前処理に応用される。 ブロックソート自体はデータの大きさを変えない。しかし、データを整列することでデータ中に出現するパターンを、いくつかのよく知られている手法で圧縮し易いものにできる。後処理としてMove To Front (MTF)・連長圧縮 (RLE)・エントロピー符号と組み合わせて、データを圧縮する。 実装はbzip2等。 Python言語による実装例が文献[1]に出ている。 長さ n のデータを巡回シフトし、得られるすべての文字列を辞書順にソートする。このようにしてできた n×n
アルゴリズムイントロダクション輪講@京都のお知らせ - motemenの日記
2008-08-18 12:19 追記 多数のご応募ありがとうございます。ここでいったん募集を打ち切らせて頂きます。なお、人数の関係で、応募された方からも今回参加できない方が出ることになりますが、あしからずご了承下さい。 社内エンジニアの間に、計算機科学をマジメにやろうという機運が高まっています。それを受けはてな社内で計算機科学に関する教科書の輪講をやろうという話になりました。という訳でまずはアルゴリズムの教科書「数学的基礎とデータ構造 (アルゴリズムイントロダクション)」を輪講してみることにします。はてなスタッフだけでなく社外からの参加も募集しているので、京都オフィスに近い方はぜひご参加下さい。 数学的基礎とデータ構造 (アルゴリズムイントロダクション) 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,
TinySegmenter: Javascriptだけで実装されたコンパクトな分かち書きソフトウェア
TinySegmenterはJavascriptだけ書かれた極めてコンパクトな日本語分かち書きソフトウェアです。 わずか25kバイトのソースコードで、日本語の新聞記事であれば文字単位で95%程度の精度で分かち書きが行えます。 Yahoo!の形態素解析のように サーバーサイドで解析するのではなく、全てクライアントサイドで解析を行うため、セキュリティの 観点から見ても安全です。分かち書きの単位はMeCab + ipadicと互換性があります。 デモ 日本語の文章を入力し、解析ボタンをクリックしてください。 ダウンロード TinySegmenterはフリーソフトウェアです. 修正BSDライセンスに従って本ソフトウェアを使用,再配布することができます. Download TinySegmenter version 0.2 使い方 <script type="text/javascript" src
ベジエ曲線とベジエ曲面
この授業では、ベジエ曲線・ベジエ曲面を学ぶことを目標としています。 これらの曲線曲面を理解するために、必要に応じてコンピュータソフト Mathematica を用いて解説する。 授業の内容を参考テキストとして配付する。 １０月５日（水） ベジエ曲線１ 今日のテキスト（pdfファイル）: ベジエ曲線とベジエ曲面１ 参考ファイル: 放物線1a 放物線1b 放物線2a 放物線2b 放物線3a 放物線3b ３次曲線1a ３次曲線1b ３次曲線2a ３次曲線2b ３次曲線3a ３次曲線3b 7次曲線a 7次曲線b レポート１ １０月１２日（水） ベジエ曲線２ 今日のテキスト（pdfファイル）: ベジエ曲線とベジエ曲面２ 参考ファイル: ３次曲線 レポート２ １０月１９日（水） ベジエ曲線３ 今日のテキスト（pdfファイル）: ベジエ曲線とベジエ曲面３ レポート３ 参考ファイル: ベジエ点 １０月２６
キャッシング 融資小ロ
午前中にカードローン審査で合格が出ると、お昼以降に融資金が受け取れる流れが普通の流れと言えます。キャッシュの持ち合わせがピンチな時も、即日融資があれば何とか凌げます。 アイフルは、テレビコマーシャルでも知名度の高いキャッシングローンを主軸にしている業者です。そして、即日キャッシングの申込ができる実績も多い全国に支店展開しているキャッシング会社だと言えます。 お金を借りるときも返す時も、コンビニや既定の銀行のＡＴＭを利用することができるカードローンは、さすが利便性が高いと思われます。当たり前ですが、手数料を払わなくても使う事ができるかを確認して下さい。 勤めている所が著名な会社とか公的な組織の人だと、高い信用度があると査定されます。こうした捉え方はキャッシングの審査に限った事ではなく、日常会話の中で言われているものと変わらないと言えます。 申し込みにつきましてはＷＥＢで行なえますから、キャッ
いろいろな曲線
グラフ描画についての指針 グラフを調べる場合、次のことを念頭において計算を進めればよい。 （１） 曲線の存在範囲（Existence)や座標軸に対する対称性(Symmetry) （２） 座標軸との交点(Intersection)や曲線上の特殊な点の座標(Special point) （３） 関数の増減と極値(One) （４） 関数の凹凸と変曲点(Two) （５） 漸近線(Straight line) 私の高校時代、上記手順を覚えるために頭文字をつなぎ合わせて、 ＳＥＳＩＯＴＳ（セシオッツ） などという語呂合わせを考案したものだ。 例 曲線 Ｙ２＝Ｘ２(１－Ｘ２) のグラフを描いてみよう。 式の特徴から、曲線は、Ｘ軸に関して対称、Ｙ軸に関して対称、原点に関して対称である ので、計算する範囲を、Ｘ≧０、Ｙ≧０ としてよい。さらに、Ｙ２≧０ であるので、 ０≦Ｘ≦１ としてよい。このとき、与えら
Quadtree demonstration
I’ve been working on different approaches to speed up the collision detection stage for some while now (mainly for the motor engine and some games). This includes a Quadtree which I started working on last year, but just recently got around to pick it up again. I’m still fine-tuning the code, so I can’t share it at the moment. But, because I added some visualization stuff to help fix some bugs, I
polygonal labs » Recursive Dimensional Clustering
Collision detection with Recursive Dimensional Clustering Brute force comparison Collision detection can be done in many ways. The most straightforward and simplest way is to just test every object against all other objects. Because every object has to test only for others after it in the list of objects, and testing an object with itself is useless, we arrive at the well known brute force compari
ricardo cabello* blog* Petrol - Fluid simulation with APE*
I have been looking to get some time to play around a bit with APE, and after doing the usual tests that everyone would do, I though that may be a good idea would be to mix the physics with the blobs effect. And here are the results: Quite slow, but it's a good start I guess. If you wonder how it works, here it's a behind the scenes version of the same piece: Main.as (you'll need Blobalise.as and
"Collective Intelligence"のサンプルをrubyに移植してみた - ma2の日記
Programming Collective Intelligence: Building Smart Web 2.0 Applications 作者: Toby Segaran出版社/メーカー: O'Reilly Media発売日: 2007/08/26メディア: ペーパーバック購入: 3人 クリック: 117回この商品を含むブログ (31件) を見る「集合知」を解説するこの本にはいろんな実例とサンプルが出てくる。サンプルは python なので ruby に書き換えてみた。書き換えたのは第二章の "Making Recommendations" の一部です。なんらかのアイテム（本とか映画とか）とその評価（Amazonレビューの★とか）を複数の人間が行った場合に，その情報を元に「似た傾向の評価者」を探し，似た傾向の評価者のリストから自分が未評価のアイテム（つまり未読の本とか未見の映画とか
リサージュ曲線で遊ぶ - 縁側でお茶
地道に攻めている音とか信号処理方面とは別に、やはりASerとしては「数学的なアルゴリズム」と「気持ちいい/面白い動きだったり見た目」、というのの絡みも関心の強い分野だったりするわけで。 というわけでまずはべったべたなところでリサージュ曲線がらみで謎なものを作ってみた。 http://labs.zkdesign.jp/ 主に使ってるのはリサージュ曲線の計算式＋BitmapData.draw()+BitmapData.scroll()。 毎度のことながらメインのコードはカオスなので、とりあえずリサージュ曲線の各点を吐かせるために書いたコードだけ貼っておいてみる。 package { import flash.geom.Point; public class Lissajous { private var _point:Point; private var _phase:Number; priv
void element blog: ハーフトーンカメラ（カラー）
前回のエントリに引き続きハーフトーンカメラ処理、今度はカラー版です。 RGBそれぞれに対してハーフトーン処理を行うと、8色に減色できるようなのでこちらも作ってみました。 大部分はモノクロ版と同じですが、最後の変換を paletteMap で一括変換しています。 こちらも全ピクセルをなめる必要なし。 画像処理様様ですね。 ソースは以下。 package { import flash.display.Bitmap; import flash.display.BitmapData; import flash.display.Shape; import flash.display.Sprite; import flash.display.StageAlign; import flash.display.StageQuality; import flash.display.StageScaleMod
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
tx-ruby - monthly gimite
