区間木 - Wikipedia
区間木またはインターバル木（英: Interval tree）は、区間を保持するための木構造のデータ構造の一種。計算幾何学のアルゴリズム。特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。似たものに区分木（英: Segment tree, segtree）があるが別物である。 単純なケースとして、区間が互いにオーバーラップしないなら、単純な2分木で表すことができ、クエリにかかる時間は O(log n) となる。しかし、区間同士がオーバーラップするなら、始点でソートする場合と終点でソートする場合で順序が異なることになるので、挿入時に2つの区間をどう比較すべきかが問題となる。素朴な方法としては、同時に2つの木
オンライン凸最適化と線形識別モデル学習の最前線 - Preferred Networks Research & Development
内容は線形識別モデルの学習について（Perceptron, PA, CW, AROW, NHELDとNLP2010のtutorial + 最新のアップデート. 更新式が整理されています）、オンライン凸最適化のregret解析、sublinearなSVMの学習の話です。最近公開したjubatusの中の学習アルゴリズムの解説でもあります。 コスト関数が凸である場合のOnline Gradient Descentのregret解析の証明は美しかったので、普通はこういうのはプレゼンではやらないとおもうのですが紹介しました。 Sublinearの学習の話は今後いろいろ発展しそうです。各学習例に動的に重みをつけて優先的に学習する方法は直感的にはできそうだと昔考えてたのですが、こういう形できれいに定式化できるのだと感心しました。 IBISはそこそこ参加していますが、毎年新しい分野の問題が登場してきて面白
ANN - Approximate Nearest Neighbor Library
ANN is a library written in C++, which supports data structures and algorithms for both exact and approximate nearest neighbor searching in arbitrarily high dimensions. In the nearest neighbor problem a set of data points in d-dimensional space is given. These points are preprocessed into a data structure, so that given any query point q, the nearest or generally k nearest points of P to q can be
algorithm - 最近点検索をkd-treeで : 404 Blog Not Found
2009年04月30日01:00 カテゴリMathLightweight Languages algorithm - 最近点検索をkd-treeで というわけで、kd-treeによる検索も実装してみました。 はてなブックマーク - ototoiのブックマーク データ数が少ない場合、この全検索が高速。ただデータが多くなってくるとkd-treeがいいと思う。点ならば配列をソートするだけで実現できる。 以下のデモでは、単にkd-treeによる検索だけではなく、kd-tree構築の速度と、総当たりの場合の速度の比較もできるようにしてあります。10,000点ぐらいだと、その差を顕著に感じることが出来るでしょう。100,000点ぐらいあると、感動的なほど差が出ます。それだけあってもkd-treeの方はほぼ1ms以内に検索が終わるのですから(ただしこの場合、デモの実行に合計10秒以上かかるので注意!)。
新はてなブックマークでも使われてる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に負けていた。しかし、学習が早いというのは実アプリケーシ
JOI 春合宿での講義資料 - iwiwiの日記
情報オリンピックの春合宿で担当した講義のスライドをアップロードしました． プログラミングコンテストでの動的計画法 プログラミングコンテストでのデータ構造 講義は動的計画法についてとデータ構造についてで，それぞれ独立しています． 動的計画法については，動的計画法のアルゴリズムを導くにあたっての非常に基本的な部分について話しています．動的計画法がよく分かっていない人や，苦手な人にオススメ． データ構造については，Union-Find 木，バケット法，セグメント木について話しています．特に，バケット法やセグメント木の話は，中上級者向けですが，世の中の資料がかなり少ないので，活用されることを期待します． 講義を受け持つのははじめてで不安でしたが，生徒さん達に褒めてもらえたりもしていて嬉しいです． http://twitter.com/tozangezan/status/10718667041 ht
Weka - 機械学習の「朱鷺の杜Wiki」
ライブラリ† AlgorithmsForWekaWakka：ファジィc-means法などのファジィ系の手法 BioWeka：バイオインフォマティクス fast-random-forest Fuzzyweka：if-thenルールによるファジィ分類器 jBNC：ベイジアンネットライブラリ HMMWeka：隠れMarkovモデル Olex-GA：文書分類ルールを遺伝的アルゴリズムで獲得 pHMM4weka：隠れMarkovモデルによるタンパク質の分類 Spectral Clusterer for WEKA @ Luigi Dragone：スペクトラルクラスタリング Weka4WS：Grid環境でWekaを実行 WEKA Classification Algorithms：Wekaのプラグイン集．ニューラルネット，学習ベクトル量子化，自己組織化マップなど． Weka LibSVM (WLSVM)
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
ACM/ICPC国内予選突破の手引き
ACM/ICPCの2008年度の大会日程が公開されています。 国内予選は2008年7月4日，アジア地区予選会津大会は2008年10月25日～27日でホスト校は会津大学です。 参加登録締め切りは2008年6月20日です。 ここではACM/ICPC（ACM国際大学対抗プログラミングコンテスト: ACM International Collegiate Programming Contest）で 国内予選を突破するために必要な情報を載せています。 ACM/ICPC自体については2006年度の横浜大会のWebサイトなどを読んでください。 結局のところ，ACM/ICPCで良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが，出題される問題の多くはいくつかのカテゴリ，例えば探索問題やグラフ問題，あるいは幾何問題などに分類することができます。 つまり，「傾向と対策」が存在します。 本サ
OpenCV - Shunsuke Yamamoto Wiki
ラベリング手法 † 画像処理において，ラベリングを使うことはよくある． ただ，OpenCVではラベリングに関する関数は定義されていません． そこで，奈良先端科学技術大学院大学の井村さんという方が作成されたLabeling.hを使います．(入手先) あと，これを参考にサンプルプログラムを作成されたmasayoshiさんのサイトを参考にします． プログラムでは，Labeling.hを呼出し， ラベリングを使う関数の中で以下のようにラベリングクラスを呼び出します． LabelingBS labeling; ここでは簡単のため，ラベリング変数はlabelingとしました． あとは，ラベリングを行う関数で，実行するだけです． IplImage *src; .... IplImage *dst = cvCreateIMage( cvGetSize( src ), IPL_DEPTH_16
Graphics2Dの実装(6) - Mysaifu JVM - Windows Mobile用Java仮想マシン - 作成記
Graphics2D.draw(Shape s)メソッドGraphics2Dには、「任意の図形を描画する」以下のメソッドがある。http://sdc.sun.co.jp/java/docs/j2se/1.5.0/ja/docs/ja/api/java/awt/Graphics2D.html#draw(java.awt.Shape) public abstract void draw(Shape s) 現在の Graphics2D コンテキストの設定を使うことにより、Shape の輪郭をストロークで描画します。 現在のMysaifu JVMはこのメソッドを実装していないので、作ってみることにした。Shapeを描画する方法クラスShapeを描画する手順は以下のようになる。1. Shapeの以下のメソッドを用いて、PathIteratorを取り出す。http://sdc.sun.co.jp/ja
Hough変換による画像からの直線や円の検出：CodeZine
はじめに Hough変換は、画像から直線や円を検出する技法として知られています。通常の直交座標上の画像を、極座標の二次元空間（直線検出の場合）に変換したり、三次元の空間（円検出の場合）に変換したりして、そこで最も頻度の高い位置を求め、それを逆変換して、直線や円を検出します。 Hough変換は数学的に興味深く、プログラムの対象として面白いため、多くの論文が見られますが、実用化には多くの問題点もあります。 ここでは最初に、一般的なHough変換の基本プログラムを紹介し、次に交通標識認識への応用に特化したプログラムについて述べます。 基本図形認識版アプレットを見る 交通標識認識版アプレットを見る 対象読者 画像から直線や円を検出する方法に興味を持ち、その一つであるHough変換の仕組みを学びたい人。 必要な環境 J2SE 5.0を使っていますが、J2SE 1.4.2でも大丈夫で
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Splay Trees
微分積分
Solaris Essentials - General Technical Questions - Solaris on x86