K-means法によるクラスタリングのスマートな初期値選択を行うK-means++ - kaisehのブログ
K-means法は、入力データからK個のランダムな個体を初期クラスタの中心として選択し、以降、クラスタの重心を移動させるステップを繰り返すことでクラスタリングを行う非階層的手法です。K-means法はシンプルで高速ですが、初期値依存が大きいのが弱点で、不適切な初期値選択をすると間違った解に収束してしまいます。 以下は、Introduction to Information Retrievalの16章に出てくる例です。 {d1, d2, ..., d6}をK=2でクラスタリングする場合、{{d1, d2, d4, d5}, {d3, d6}}が大域最適解ですが、初期クラスタの中心をd2, d5で与えると、{{d1, d2, d3}, {d4, d5, d6}}という誤った解に収束してしまいます。 この問題を改善するK-means++という手法を見つけたので、試してみました。 K-means+
ソートアルゴリズムの可聴化 - ならば
Sorting Algorithm Animationsなどのサイトでは、ソートアルゴリズムの可視化の例を見ることができる。今回は可視化に倣ってソートアルゴリズムを可聴化した。聴覚化すると、情報を分かりやすく提示するという方向から外れるけど。 ソートする対象は50から90までの整数をランダムに並べた列。可聴化の方法は、整数をMIDIノート番号とみなして、ソートアルゴリズムが各時点でポイントしている位置にある、MIDIノート番号の音高の音を鳴らすようにした。ChucKのプログラムはいつもより長くなったから最後に載せる。 録音したもの。元の整数列は全部同じで、サイズ（整数の数）は30。 バブルソート 選択ソート 挿入ソート シェルソート クイックソート マージソート ヒープソート 拡張としては、 より詳細に情報を提示する方向（例：整数同士の位置の交換時に音色を変える） サウンドアートな方向（例
ビット数を数えるルーチン - Weblog on mebius.tokaichiba.jp
かつてＪＲ横浜線 十日市場駅近くのMebius (CPU:Pentium 150MHz)より発信していたウェブログです。 32bitの立っているビット数を高速に数えるアルゴリズムとして、 int bitcount(unsigned long n) { n = ((n&0xaaaaaaaa) >> 1) + (n&0x55555555); n = ((n&0xcccccccc) >> 2) + (n&0x33333333); n = ((n&0xf0f0f0f0) >> 4) + (n&0x0f0f0f0f); n = ((n&0xff00ff00) >> 8) + (n&0x00ff00ff); n = ((n&0xffff0000) >> 16) + (n&0x0000ffff); return n; } こういうのが良く知られている。1行目で2ビットずつ足し合わせることで2ビットの中の
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
新はてなブックマークでも使われてる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に負けていた。しかし、学習が早いというのは実アプリケーシ
[P2P]位置情報を数値1つで表す手法「Z-ordering」 - Tomo’s HotLine
IT技術を中心に、暮らしに役立つ情報からクラシック音楽の解説まで気軽に情報発信しています。 WEBサイトはhttp://toremoro21.world.coocan.jp/ Twitterは@toremoro21です。 □はじめに ＤＨＴやＳｋｉｐｇｒａｐｈなどの技術が注目されるとともに、位置情報をP2Pで扱いたいという要望がでてきている。だがＤＨＴやＳｋｉｐｇｒａｐｈは1次元の数値で各ノードが扱う情報範囲を扱うため、位置情報など多次元の情報を扱うのには、当初は向いてないと見られていた。しかしあるテクニックを使うとそれは一発で解消する。それがZ-orderingである。なお、このZ-orderingは位置情報を扱えるP2PミドルウェアPIAXでも採用されている。 □簡単な例 多次元を1次元で表すにはどうすればよいのだろうか？まずここで一例を挙げてみる。 例えば、2次元空間においてｘ＝｛１
![[P2P]位置情報を数値1つで表す手法「Z-ordering」 - Tomo’s HotLine](https://cdn-ak-scissors.b.st-hatena.com/image/square/b4e38426fa9529bdb687a0c8ea1406a0f5bee683/height=288;version=1;width=512/http%3A%2F%2Ftoremoro.tea-nifty.com%2F.shared-cocolog%2Fnifty_managed%2Fimages%2Fweb%2Fogp%2Fdefault.png)
『コンピュータを使わない情報教育 アンプラグドコンピュータサイエンス』
『コンピュータを使わない情報教育 アンプラグドコンピュータサイエンス』 監訳者：兼宗進 翻訳者：正田良、鎌田敏之、紅林秀治 翻訳協力者：西田知博、井戸坂幸男、保福やよい 追補執筆者：久野靖 ISBN978-4-904013-00-7 C3037 \1,500E 2007年9月1日第２刷 ★ご購入方法 ジュンク堂池袋本店に常備しております。 JUNKUDO BOOK WEBからご購入できるようになりました。 ※お問い合わせ ご購入、仕入れに関してはkyutaro@urap.orgにメールでお問い合わせください。 原著者たちは普段、コンピュータアルゴリズムの専門家として数式に囲まれながら研究を進めているはずですが、この本では10年以上前に、ティム・ベル博士が当時小学生だったお嬢さんに教えたときの体験を元に書かれているため、とても楽しく、わかりやすい内容
Judy Arrays Web Page
What is Judy? Judy is a C library that provides a state-of-the-art core technology that implements a sparse dynamic array. Judy arrays are declared simply with a null pointer. A Judy array consumes memory only when it is populated, yet can grow to take advantage of all available memory if desired. Judy's key benefits are scalability, high performance, and memory efficiency. A Judy array is extensi
GC FAQ -- draft
GC FAQ -- draft This is a draft FAQ for the GC-LIST. Comments, editorial remarks, and especially additions are welcome. The file is currently broken up into three parts, corresponding roughly to general stuff, techniques and algorithms, language interfaces to GC, and more difficult topics. As sections grow, these files may be reorganized in an attempt to keep the individual files small enough to b
「アルゴリズム」って？ 「プログラマ」って？ - 檜山正幸のキマイラ飼育記 (はてなBlog)
メモ編に対してですが、id:sumiiさんから、「アルゴリズム」という言葉の意味と使い方に関して、以下のコメントをいただきました： 通常の定義では、「アルゴリズム」といったら（特に断らなければ）任意の有効な入力について停止せねばならず、停止しない（かもしれない）場合は「セミアルゴリズム」といいます。もしそれ以外の理解をしている「プログラマ」がいるとしたら、単なる誤りか、少なくとも通常の定義とは異なるかと。 とまー、「プログラマ／技術者」ならば、「アルゴリズム」という言葉を、上記のごとく理解している（べき）だろう、ということです。 僕は週に何回か、プログラマ／技術者の方々と打ち合わせをします。そのときよく、「そこのロジックはどうなっているの？」とか「アルゴリズムはもう決まっています。」なんて会話になります。そんな打ち合わせの出席メンバーのような人々が「プログラマ／技術者」であり、今のような会
No Free Lunch Theorem—理想の＊＊の探し方—
すべての評価関数に適用できる効率のよいアルゴリズムは存在しない。 “すべての評価関数”というのは上の例で言えば“すべての”ということである。 この定理を証明する前に、まずよく知られた探索アルゴリズム[5]を挙げて、探索とはそもそもどのようなものなのかを説明しよう。 探索アルゴリズム “探索”というのは問題の解の候補の中からよいものを探し出すことである（同語反復という感じだが）。ここでは次のように、評価関数が定義された問題を解く過程のことを探索と呼ぶことにする。 解の候補の有限集合を、その要素のひとつをとする。 評価関数はから有限集合への写像である（の要素のひとつをで表す）。 の最大値を与えるようなが問題の解で、それを見つけたいのである。 このような探索問題を解くためのアルゴリズムには大きく分けて次の2つがある。 アルゴリズムのように知識を用いて解を構成するもの（適切なヒュ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - livedoor/cicindela2: a highly customizable recommendation engine written in perl + MySQL
