kd木 - Wikipedia
3次元のkd木。根セル（白）をまず2つの部分セルに分割（赤）し、それぞれをさらに2つに分割（緑）している。最後に4つのセルそれぞれを2つに分割（青）している。それ以上の分割はされていないので、最終的にできた8つのセルを葉セルと呼ぶ。黄色の球は木の頂点を表している。 kd木（英: kd-tree, k-dimensional tree）は、k次元のユークリッド空間にある点を分類する空間分割データ構造である。kd木は、多次元探索鍵を使った探索（例えば、範囲探索や最近傍探索）などの用途に使われるデータ構造である。kd木はBSP木の特殊ケースである。 kd木は、座標軸の1つに垂直な平面だけを使って分割を行う。BSP木では分割平面の角度は任意である。さらに一般的には、kd木の根ノードから葉ノードまでの各ノードには1つの点が格納される[1]。この点もBSP木とは異なり、BSP木では葉ノードのみが点（ま
Visualizing the London Underground in 3D with Ubigraph - smly’s notepad
モントリオール, 東京, ロンドンの地下鉄の駅と路線の関係をグラフとして可視化してみました. この結果には別に意味はないのですが, アルゴリズムのデバッグなんかには結構役に立ってくれそうだなと思いました. デモムービーでは次のようなことを行っています. typo がかなり多い. (00:05) モントリオールの地下鉄をグラフ表示 (01:15) GREEN の路線を緑色に色付けし, 強調表示 (01:48) 東京の地下鉄をグラフ表示 (02:59) 日比谷線を赤色に色付けし, 強調表示 (04:35) ロンドンの地下鉄をグラフ表示 (05:55) Square が名前に付く駅を探す (06:10) Square が名前に付く駅を緑で色付け (07:42) Euston Square から Sloane Square までの最短経路を緑色に色付けし, 強調表示右側のウィンドウで動いていたプロ
線形回帰モデル - yasuhisa's blog
明日発表の分のゼミの資料。PRMLの3.1.2から3.1.5までです。先週のはこの辺に書いている。 今日の日記 - yasuhisa's blog 最小二乗法の幾何学 ここではN=3と固定して考えてみる ということなので、3次元空間で考える 各軸が、、で与えられる3次元空間 図についてはここを見る M < NのケースとしてM=2の場合を考える すると次元が一つ落ちるので、ベクトル、は(図でいうところの)M=2次元の線形部分空間Sを貼る この平面を動き回る yはベクトル、のパラメータによる線形結合で表わされるので、線形部分空間Sの中のどこにいてもよい どこにいてもいいんだけど、どこにいると一番いいんでしょう tとyとの距離が一番近いところがいいよね→tとyとのユークリッド距離 図からも適切なtというのはtの部分空間Sの上への正射影に対応していることが分かる 逆行列を取る関係で、が非正則、非正
DO++ : 部分文字列の話
ここしばらく、部分文字列の統計量を利用した機械学習やデータマイニングをやっている。そこの話からちょっと抜粋。 長さnの文字列T[1,...,n]が与えられた時、T中に出現する部分文字列T[i...j] (1≦i≦j≦n）の数はn個の中からiとjの2箇所を選ぶのでO(n^2)個ある。例えば、n=10^6(1MB)だったら、部分文字列の数は約10^12個(1T)と非常に大きい。 しかし、これらの部分文字列の出現位置は同じである場合が多い。例えばT="abracadabra"であれば、"abra"と"abr"の出現場所は1番目と8番目であり、全く同じである。 では出現位置（部分文字列の左端を出現位置とする）が全く同じであるような部分文字列をまとめてグループにした場合、グループの数はいくつになるのだろうか。 これは接尾辞木（wikipedia 授業の資料）を知っているなら簡単に説明できる。 Tに対
分布推定アルゴリズム - yukobaのブログ
分布推定アルゴリズム。遺伝的アルゴリズムを改良した物です。個体の集合を交叉・突然変異させるのではなく、個体の生成確率を進化させます。最適化問題のアルゴリズムです。以下、自分へのメモです。わかったことが増えたら追記するかも。 ビットストリング 計算量に関しては、ビット数をn、反復数をTとしています。 Population-Based Incremental Learning (PBIL) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.8554 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5424 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.1108 Population-ba
Double-Array Articles
ダブル配列のライブラリを公開しているページです． An Implementation of Double-Array Trie URL: http://linux.thai.net/~thep/datrie/datrie.html Darts: Double-ARray Trie System URL: http://chasen.org/~taku/software/darts/ Dame URL: http://www.void.in/wiki/Dame Tiny Double-Array Library URL: http://nanika.osonae.com/TinyDA/index.html Dynamic Double-Array Library URL: http://nanika.osonae.com/DynDA/index.html
グラフ理論ライブラリのJGraphTを使ってみた - kaisehのブログ
JGraphT JGraphTは、Javaのグラフライブラリです。グラフの描画ではなく、グラフ理論のモデルとアルゴリズムの方にフォーカスしています。とても使いやすかったので、紹介してみます。 無向グラフ UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>( DefaultEdge.class); g.addVertex("a"); g.addVertex("b"); g.addVertex("c"); g.addEdge("a", "b"); g.addEdge("b", "c"); System.out.println(g.vertexSet()); System.out.println(g.edgeSet()); System.out.println(g.edgesOf("c"));
株式会社エス・スリー・フォー » STLport のハッシュ・コンテナ
STLport のハッシュ・コンテナ 標準C++ライブラリが提供するコンテナは、vector, list, deque, set, multiset, map, multimap の7種です。 これらコンテナから特定の要素を検索するとき、その時間計算量は vector, list, deque では O(N), set, multiset, map, multimap では O(logN) となります。 これ以上に高速な検索が可能なコンテナとしてハッシュ表(hashtable)を利用すれば、適切なハッシュ関数を与えることによって検索に要する時間計算量をコンテナ内の要素数に関わらず O(1) に近づけることができますが、残念ながら標準C++ライブラリにはハッシュ表で実装されたコンテナ(ハッシュ・コンテナ)を提供していません。 SGI(Silicon Graphics社)のSTL実装をベースに
latent Dirichlet allocation - 機械学習の「朱鷺の杜Wiki」
latent Dirichlet allocation (LDA)† probabilistic latent semantic analysis (pLSA) を改良した，文書集合の生成モデル．各文書は，\(k\)個の話題に応じて発生した語で構成されている． 以下の過程で，文書に含まれる\(N\)個の語を生成する． \(N\sim\mathrm{Poisson}(\xi)\) … Poisson分布で語数を生成 \(\theta\sim\mathrm{Dir}(\alpha)\) … Dirichlet分布で，\(k\)個の話題を生成するモデルのパラメータを生成． \(N\)個のそれぞれの語\(w_n\)について (a) \(z_n\sim\mathrm{Multinomial}(\theta)\) … 多項分布で話題を生成 (b) 語\(w_n\)を，話題\(z_n\)で条件付けした分
B-Tree - アルゴリズム・イントロダクション 18章 - ninjinkun's diary
アルゴリズム・イントロダクション勉強会，B-Treeの章を担当しましたので，資料を公開いたします． Algorithm Introduction #18 B-Tree View more presentations from ninjinkun. B-Treeはデータ容量が主記憶に収まらないような場合に有効なデータ構造で，MySQLなどのDBや，最新のファイルシステムのインデックスとして用いられています．（MySQLはインデックス管理の方式を選択可能） 主に以下の利点があります． ノードの大きさをページサイズに最適化できる ページの読み込みがディスクアクセスに最適化される ページの読み込み数を木の高さhに抑えられる ディスクへのアクセス回数を抑えることができる id:naoyaのブログも参考になります． B木 - naoyaのはてなダイアリー 当日の発表はテンパってしまい，アレな感じになっ
UB-tree - Wikipedia
The UB-tree, also known as the Universal B-Tree,[1] as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. Like a B+ tree, information is stored only in the leaves. Records are stored according to Z-order, also called Morton order. Z-order is calculated by bitwise interlacing of the keys. Insertion, deletion, and point query ar
オンラインEMアルゴリズム - DO++
EMアルゴリズム（Expectation Maximizationアルゴリズム、期待値最大化法、以下EMと呼ぶ）は、データに観測できない隠れ変数（潜在変数）がある場合のパラメータ推定を行う時に有用な手法である。 EMは何それという人のために簡単な説明を下の方に書いたので読んでみてください。 EMのきちんとした説明なら持橋さんによる解説「自然言語処理のための変分ベイズ法」や「計算統計 I―確率計算の新しい手法 統計科学のフロンティア 11」が丁寧でわかりやすい。 EMは教師無学習では中心的な手法であり、何か観測できない変数を含めた確率モデルを作ってその確率モデルの尤度を最大化するという枠組みで、観測できなかった変数はなんだったのかを推定する場合に用いられる。 例えば自然言語処理に限っていえば文書や単語クラスタリングから、文法推定、形態素解析、機械翻訳における単語アライメントなどで使われる。
コサイン距離ベースのLSHをRubyで - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥
参考文献:Web+DB press vol.49 レコメンド特集のPart3など。 アルゴリズムの概要 詳細(特に数学的な)はぐぐれ。 モチベーションとしては、高次元における近傍点探索を高速で行いたい。まじめにやるとどう工夫しても計算量がすごいことになるので、近似で。 どうするかというと、「距離が近いと同じような値になるハッシュ関数」を使う。あるベクトルの近傍を求めたい場合、そのベクトルのハッシュと同じ(もしくは近い)値のハッシュを持つベクトルをテーブルから引いてきて返す。計算量がどうなるかはややこしいけど、とりあえず全部探すよりは速い。 で、どういう関数をハッシュとするのか。これは距離の定義によって異なる。ハミング距離、コサイン距離、ユークリッド距離などにはそういった関数の存在が知られている。 コサイン距離の場合、ランダムなベクトルをいくつか用意して、入力されたベクトルがそれらと似ている
SumoBet88: Situs Judi Online Slot88 Terbaru Slot Gacor Hari Ini
Pemeliharaan Terjadwal: Crowd Play pada 2023-11-30 dari 7:00 AM sampai 2025-06-02 6:30 PM (GMT + 7). Selama waktu ini, Crowd Play permainan tidak akan tersedia. Kami memohon maaf atas ketidaknyamanan yang mungkin ditimbulkan. Pemeliharaan Terjadwal: ESports Bull pada 2024-05-20 dari 10:00 AM sampai 2025-06-03 11:00 AM (GMT + 7). Selama waktu ini, ESports Bull permainan tidak akan tersedia. Kami me
「確率モデルによる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.)。リコメンダシステムに関する多くの研究において、
自然言語処理における半教師あり学習のテキスト - 武蔵野日記
最近移動続きであまり研究に時間は割けないのだが、本は読めるということで本を2冊、サーベイ的な記事を3本(うち2本はチュートリアルスライドつき)を紹介する。まず Semisupervised Learning for Computational Linguistics (Chapman & Hall/CRC Computer Science & Data Analysis) 作者: Steven Abney出版社/メーカー: Chapman and Hall/CRC発売日: 2007/09/17メディア: ハードカバーこの商品を含むブログ (4件) を見る を読む。この本の著者の Steven Abney はブートストラッピングの理論的解析をした人で、 Steven Abney. Bootstrapping. 40th Annual Meeting of the Association fo
Perlでアニメ顔を検出＆解析するImager::AnimeFace - デー
というのを作ったので自己紹介します。 2月頃から、コンピュータでアニメ顔を検出&解析する方法をいろいろ試しつつ作っていて、その成果のひとつとして、無理やり出力したライブラリです。 はじめに はじめにざっとライブラリの紹介を書いて、あとのほうでは詳細な処理の話を僕の考えを超交えつつグダグだと書きたいと思います。 Imager::AnimeFaceでできること Imager::AnimeFaceは、画像に含まれるアニメキャラクター的な人物の顔の位置を検出し、さらに目や口など顔を構成する部品位置や大きさの推定、肌や髪の色の抽出を簡単に行うことができるライブラリです。 これらが可能になると、 画像から自動でいい感じのサムネイルを作成できる 動画から自動でいい感じのサムネイルを作成できる 自動的にぐぬぬ画像が作れる 自動的に全員の顔を○○にできる 顔ベースのローカル画像検索 など、最新鋭のソリューシ
Google PageRank (ruby script/class)
Kodama's home / tips. Japanese description. Google PageRank (ruby script/class) This ruby script get a Google PageRank for a URL. Download: gprank.rb. Containing module is very simple, so it will be easily used in your script. Note update 2007-07-10. Because the format of query/reply for the PageRank server is changed. Note The script gprank.rb does not complete inperfect URL. Therefore, where a b
LZ77圧縮
じゅげむじゅげむごこうのすりきれかいじゃりすいぎょのすいぎょうまつうんらいまつふうらいまつくうねるところにすむところやぶらこうじのぶらこうじぱいぽぱいぽぱいぽのしゅーりんがんしゅーりんがんのぐーりんだいぐーりんだいのぽんぽこぴーのぽんぽこなーのちょうきゅうめいのちょうすけ 符号 辞書幅(Byte) ■英数字 ■英数字+記号 ■ASCII ■ASCII+半角カナ1 ■ASCII+半角カナ2 ■原型 ■16進数用1 ■16進数用2 ■16進数用3その他の設定 \uF8F0-\uF8F3を使わない 連長圧縮しない 仕様任意の文字列を190種類程度の半角文字で表現します.使用する文字は以下から選択.1～5番目までは圧縮率が高まっていく傾向にあります.Byte数は文字CodeをShift-JISと見なして算出 [英数字]任意の文字列を英数字のみからなる文字列[0-9A-Za-z_]に変換します
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://sugiyama-www.cs.titech.ac.jp/~sugi/2008/NECsoft-MachineLearning-jp.html