Ant colony optimization algorithms - Wikipedia
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (August 2018) (Learn how and when to remove this mess
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+
本物と見違えるような画像補間を実現するパスフレームワーク手法 - A Successful Failure
SIGGRAPH2009で発表された"Moving Gradients: A Path-Based Method for Plausible Image Interpolation"という論文*1では、2枚の連続する入力画像を与えると、その間のフレームを極めて自然に補間生成する新たな手法を提案している。 図1 図1は両端の入力画像A, Bから間の3フレームを生成した例を示している。生成する補間フレーム数は任意で何枚でも生成可能であり、極めて自然な補間が実現できている。この例の驚くべきところは、制約条件を有する複雑で柔らかな局所変形を含む自然な補間画像が、全自動で生成されている点である。モーフィング処理では対応点を一点一点指定する必要があるが、ここで必要なのは2つの画像を選択するだけだ。 生成される補間画像の品質は素晴らしく、またアイデアもシンプルで興味深いので、原論文を参照して本手法の概要
d.y.d. - 最短性をチェックする
17:31 10/01/26 言語雑談会 言語雑談会 なるものに行ってきました。 自分は主に最近のD言語の話題 [PDF] [PPTX] についてと、 最近読んだ Pattern Calculus がイマイチ心に響かなかったという話と、 これも最近読んだ Prolog で SAT ソルバ という論文が格好良すぎて卒倒しそうです、などの話題を雑談していました。 SAT の話をしていてふと突然気づいたんですが、私が今までSATソルバに落としてみたことのある問題は、 すべて割と簡単に CNF（SATソルバがそのまま食べてくれる綺麗な形式の論理式） ができあがる問題だったようです、数独とか。 任意の命題論理式をCNFに変換できる指数爆発しない方法をそういえば知らないぞ俺！としゃべってたら soutaro さんが素晴らしい解説 をして下さいました。ありがたや。 あと shinhさんの 「コンピュータ
PythonでA*(A-Star)アルゴリズム - Pashango’s Blog
今回はA*アルゴリズムをPythonでやってみます。 ゲームプログラマの間では、もはや常識となりつつある最短経路問題解決アルゴリズムです。 A*は、古典的手法である「ダイクストラ法」を改良したものです。 スタート地点からノードnを通ってゴールに辿り付くとき、最短距離をf(n)とすると、 f(n) = g(n) + h(n) とすることができます、g(n)は「スタートからノードnまでの最短距離」、h(n)は「ノードnからゴールまでの最短距離」です。 でも、最初から適切なg(n)とh(n)が判ってるなら苦労しませんよね。 だから、テキトーな予測値を使って、最短経路をある程度予測して効率的に経路探索をしてみようという事です。 テキトーな予測値を使った最短経路距離をf*(n)とすると f*(n) = g*(n) + h*(n) となります、f*(n)を求めるためにテキトーなg*(n)とh*(n)を
BitTorrentのファイル配信メカニズム - Emerge Technology
Linuxのディストリビューションの配布などで配布サーバの回線速度などがボトルネックになり（図1)、円滑にファイルを配布することはコストがかかります。BitTorrent(図2)は配布者の負担を軽減して、素早くファイルを配信することを目的にBram Cohenによって開発されたP2Pソフトウェア(図3)です。 BitTorrentでは、トラッカーとよばれる全てのピアとピアのアップロード/ダウンロード能力、ファイルの取得状況を管理するサーバが存在します。一般的なP2PシステムではP2Pネットワーク内を検索してからファイルの取得という動作を行いますが、BitTorrentでファイルの検索という作業は行ないません。代わりにトラッカーにファイルを持っているピアを問い合わせます。ファイルを持っているピアの検索をクライアント・サーバで行うということで、従来の分類ではハイブリッド型P2Pシステムになりま
Google検索アルゴリズムで生態系崩壊を予測 | WIRED VISION
前の記事 「飛行機からレーザーで地上攻撃」実験に成功 Google検索アルゴリズムで生態系崩壊を予測 2009年9月 8日 Hadley Leggett 写真：Flickr/fusion68k、イラスト：PLOS Computational Biology。サイトトップの画像は海藻を食べるマナティ。画像はWikimedia Commons 生物学者たちは、生態系を破壊する最も効率的な方法を見い出した――Google社の検索アルゴリズムに基づいてだ。 食物網の要になる生物種が絶滅すると、生態系全体の崩壊を引き起こす危険性があるということは、以前から科学者の間では知られていた。だが、種の相互作用は無数ともいえるほど存在するため、どの動物や植物がいちばん重要なのかを推測することは難しい。 [現在の群集生態学では「食物連鎖」という言葉より、食物網という概念の方が現実的なものとして重視されてきている
ProblemSets/99 Prolog Problems Solutions - Python Wiki
Problems 1-6 André Roberge has a zip file with solutions to the first six problems, in Crunchy format: First six Problem 7: Flatten a nested list structure Based on the standard library documentation: from itertools import chain def flatten(listOfLists): return list(chain(*listOfLists))The suggested solution does not work for a list like the following: a_list = [0, 1, [2, 3], 4, 5, [6, 7]]as the a
検索と挿入がともにO(1)であるようなHashを作るにはコツがいる
このところ立て続けに表記の事実を理解していない俺実装のHash(しかもCで!)を見かけたので、おそらく知られていないんだと思う。以降、同じ轍を踏む人が少なくなればと思い、啓蒙のために公開しておく。 先に言っておくがおまえらはHashを再発明するんじゃねよボケが。おとなしくありもののライブラリ使えよ。つうかHashのある言語使えよ。Cとかマゾかよ。 言葉と前提とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、 class Hash { typedef lis
アルゴリズムと計算量
金庫破りと計算量膨張 n 桁の番号をもつ暗証ロックがあるとします。 2 桁であれば 00 〜 99 の 100 個の正解があるわけで、 0 番から順に入力していく解き方では、 最悪の場合は 100 手目に開きます。 99 が正解とは限らないので、平均的にはこれより早く解き終わります。 0 であるときの確率は 1/100 で、このときの手数は 1 手です。 1 であるときの確率は 1/100 で、このときの手数は 2 手です。 2 であるときの確率は 1/100 で、このときの手数は 3 手です。 3 であるときの確率は 1/100 で、このときの手数は 4 手です。 : 99 であるときの確率は 1/100 で、このときの手数は 100 手です。 つまり、平均手数は により、100 手目の約半分です。 ここでいう解き方をアルゴリズムといい、 問題を解くための手数 (てかず) のことを計
北海道を落とすとどう跳ねるのか？の裏側 - てっく煮ブログ
asおかげさまで大好評の 北海道を落とすとどう跳ねるのか？ ですが、どのように作ったか、製作過程を紹介することにします。1. 地図の素材を取ってくるまずは地図の素材が必要です。以下のサイトから拝借しました。白地図、世界地図、日本地図が無料pdf や eps 形式の地図データを無料で配布してくれているありがたいサイトです。2. 都道府県ごとに分割する上記の素材は県境もベクター形式で提供されていて大変ありがたかったのですが、島がどの都道府県に属しているかの情報がありませんでした。そこで、Google Maps と見比べながら、島を都道府県ごとに分類していきました。無事、全ての島を分類し終わって、こんな感じになりました。とても地味な作業でした…。3. 都道府県ごとに SVG で出力する次に、Illustrator 内で分類したデータをプログラムで扱える形式にしなければなりません。ここでは XML
話すようにプログラムするPythonチュートリアル - なんたらノート第三期ベータ
Pythonでえらくハッキッシュなコードを書き散らして遊んだ 3の倍数と3が付く数字だけアホになり、5の倍数だけガルマっぽくなるスクリプトにチャレンジ - なんたらノート 第二期 うえ、他人のエッセイをえらくこき下ろし OOコード養成ギブス - rants OOコード養成ギブスとやらが人気らしい。 - なんたらノート 第二期 て、われながら生産性のないやつだと思うので、ここは逆に、Pythonチュートリアルをひとつ書いてみようと思います。 まず最初に、こんなプログラムがあったとさ。 #素数の数列を返すアルゴリズム def prime_numbers_until(limit): prime_numbers = [] for n in range(2, limit): divider_found = False # 1より大きくその数より小さい範囲で調べる for m in range(2,
【インフォシーク】Infoseek ： 楽天が運営するポータルサイト
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
Local Lucene Geographical Search
by Patrick O'Leary (pjaol at pjaol.com) There are 3 components to how local lucene performs a geographical search. Create a bounding area. Query that areas document set for a text match. Reduce the document set to a precise distance from a center point. Geographical text searching can take multiple formats, inclusion or reductionism. Inclusion is applying text searching over a document set and ver
「確率モデルによるwebデータ解析法」8章メモ - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥
昔書いたやつを発掘してきた。また読み返す必要があるなー。 8章は商用アプリケーションの話、レコメンダシステムと顧客行動解析。 ここで扱うレコメンダシステムは、ユーザの行動履歴に基づきユーザに対してアイテムを推薦するようなもの。 興味深い問題として、欠損をすべて0と考えた場合、ユーザiがチェックしなかった項目jに関する行列V中の欠損地の扱いがある。これら欠損データは、必ずしも完全にランダムに欠損しているわけではなく、ユーザが好まない項目に対して「どちらかといえば選ばない」という負のバイアスが 影響していると思われる(Breese,J.S.,Heckerman,D. and Kadie,C. 1988 Empirical analysis of predictive algorithms for collaborative filtering.)。リコメンダシステムに関する多くの研究において、
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
Link Analysis and Related Topics - Home
2008年度 先端情報科学特論 II & IV リンク解析と周辺の話題 担当 新保 仁 shimbo@is.naist.jp 日時 2008/11/10, 11/17, 12/1, 12/8 (全 4 回) - 4限 15:10-16:40 場所 情報棟 L3 講義室 リンク解析は, グラフ (ネットワーク) データの構造から有用な情報を抽出するための, データマイニングの一研究分野です. この講義ではまず, リンク解析が取り扱う 2 種類の尺度 (重要度と関連度) について述べ, それぞれの代表的な計算手法を紹介します. 後半では, 近年機械学習分野で盛んに研究されているカーネルのうち, グラフ上の節点に対して定義されたカーネル (グラフカーネル) と, そのリンク解析への応用について紹介します. 第1回 11月10日 スライド 第2回 11月17日 スライド 第3回 12月1日
PyML - machine learning in Python — PyML v0.7.3 documentation
PyML - machine learning in Python¶ PyML is an interactive object oriented framework for machine learning written in Python. PyML focuses on SVMs and other kernel methods. It is supported on Linux and Mac OS X. News¶ Added wrapper for liblinear in version 0.7.8. This allows extremely fast training of linear SVMs. Features¶ Classifiers: support vector machines, nearest neighbor, ridge regression Mul
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
6.046/18.410 Introduction to Algorithms on MIT