クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。 K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。 クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、Restart を押すと好きなパラメータで試すことができます。 こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。 (追記) HTML5 版の K-means 法を D3.js でビジュアライズしてみた も作成しました。Flash を表示できない環境ではそちらをご覧ください。 K-means 法とは K平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージに
クレジットカード番号のチェックに有効なアルゴリズム - crays diary
お仕事で使っているCakePHPに面白いチェックがあった。 クレジットカード番号は、乱数の羅列なのではなく、ルーン・アルゴリズム（Luhn algorithm - Wikipedia）という方法によって算出された数値らしい。 これをチェックに使う事ができるので組み込んでみた。 このルーン・アルゴリズムは末尾から数値を一桁飛ばしで２倍にし、全ての桁を足していくと10で割り切れるかというもの。 ちょっと難しいので、図で説明。 例えば、「49927398716」というカード番号だった場合、末尾から一桁飛ばしで二倍にする。 4 9 9 2 7 3 9 8 7 1 6 ↓*2 ↓ *2 ↓ *2 ↓ *2 ↓ *2 ↓ 4 18 9 4 7 6 9 16 7 2 6算出した値を桁毎に足していき、10で割る。 4 18 9 4 7 6 9 16 7 2 6 ↓ 4189476916726 ↓ 4+1+
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた
A* ではゴールへの経路が判明した段階で処理は終了です。 A* はダイクストラ法に比べてゴールに到達するまでに調べるマス目が少ないのが印象的です。 ダイクストラ法と同じように水で例えると、A* では水が少し意思を持っていて、なるべくゴールに近いほうに流れようとするようなイメージです。ここがまさに A* のキモです。ゴールへの近さを加味して、探索するノードの数をなるべく減らそうとします。 A* では、スコアとして f* = g* + h* を用います。各ノードの f* を調べて、f* の値が小さいノードから先に探索していきます。g* はスタート地点からの距離であり、ダイクストラ法で用いるスコアと同じです。h* がゴールへの距離なのですが、実際の最短距離は途中の段階では分からないので、ゴールへの直線距離やマンハッタン距離を利用して計算します。 この、h* の部分がゴールへの近さを加味する部分で
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
