第1回 機械学習 ことはじめ | gihyo.jp
次のサービスや製品はどれも身近にありますが、これらに共通していることはなんでしょう。 Amazonの「この商品を買った人はこんな商品も買っています」 はてなブックマークの「関連エントリー」 Google 翻訳 Google 日本語入力 メールクライアントのスパムフィルタ デジタルカメラの自動顔認識 ニンテンドーDSの手書き文字認識 買い物履歴、ユーザが書いたコメントやタグ、Webに無数にあるページ、メール、画像や動画と対象はそれぞれ異なっていますが、どれも「データから有益な情報を取り出す」ということを行っています。 これらは「機械学習」という技術を使って実現されているのです。 機械学習の応用範囲 機械学習は冒頭で挙げた以外にも、様々な分野で使われています。 例えば、ノイズ除去や特徴の抽出を目的とした利用パターンがあります。音声認識や画像認識、文字認識（OCR）などはその代表格です。それらも
検索アルゴリズム (2)2分検索/木検索
検索アルゴリズム (2)2分検索/木検索 検索アルゴリズムの2回目は2分検索と木検索です。 1)2分検索 前回紹介した線形検索は、n個のデータ列に対して平均n/2回の比較操作が必要となるため、処理速度はnに比例していると言えます。これに対して、2分検索(Binary Search)ではn個のデータ列に対して最悪でもlog2n回の比較回数で済むので、線形検索に対してかなりの性能向上が期待できます。 ただし、2分検索を行うためにはデータ列がソートされている必要があり、その分線形検索に比べて前処理のための時間が必要となります。また、1回の比較処理にかかる時間も線形検索より長くなるため、データ数が少ない場合は2分検索の方がかえって遅くなることも考えられます。 2分検索では、まずデータ列の中央にある要素(以下mとします)と検索対象データ(以下xとします)を比較し、一致しなければxとmの大小関係より
R-tree Portal - R-trees and variants (in low-dimensional space)
When most couples contemplate retirement years, they might think of a fully-paid mortgage, endless sunny days of golf and fishing, … Continue reading “How 3 Couples Are Living Out Unique Retirement Dreams” → The challenge of living in a tiny home treehouse is achieving organizational functionality. Finding a way to make every single item in your house earn its keep while maintaining elegance and s
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秒以上かかるので注意!)。
kd-tree Visualization(2) - agwの日記
先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。 繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成したkd木を可視化したものは以下のようなものでした。 同じく、木構造として可視化したものは以下のようなものでした。 さて、では何故均衡の取れない木が構築されてしまうのでしょう? 座標群の初めの点、1番の点を挿入した直後の状態を可視してみましょう。 この可視と先ほどの木構造としての可視を比較すると不均衡な木が構築される理由がより明らかとなります。木構造の可視にて1番の左側にぶら下がっている2番以下の座標群は、この可視では1番によって空間分割された領域の下側、つまり、y座標値がより小さい側に分布しています。 同様に、木構造にて1番の右側にぶら下がってい
計算幾何学
計算幾何学とは 計算幾何学とは、「コンピュテーショナル・ジオメトリー」(Computational Geometry) の日本語訳である。 コンピュータで扱う幾何学というのが、その性格をよく表している。 最近専門家の間では、英語のまま呼ぶ人が多い。というのも、 訳の読み「けいさんきかがく」が「計算機科学」と間違われやすい、 という理由によるものだという。 私は「計算幾何学」という、 生硬でどこか不器用な面持ちが漂う邦訳の字面が好きである。 だから、「けいさん きかがく」というように読み方に注意して、 邦訳を使ってほしい。 なお、切れる場所での注意が肝心という話は、 エスペラントの読み方という記事を参照のこと。 さて、計算幾何学とは何だろうか。私の理解する範囲では、 「数学で扱う形（図形）を、 数学上の知識とコンピュータのアルゴリズム・データ構造を駆使して、 効率良く処理する学問体系」となる
kd-tree Visualization(1) - agwの日記
前回のエントリに引き続き、連続したビット群の総数を求めるアルゴリズムを考える予定でしたが、今回は空間分割データ構造に関するエントリにしました。人力検索はてなに以下のような問題が提示されていたのがきっかけでした。 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？ 条件は次の通りです １．集合Pはあらかじめ、任意の順番でソートしておける ２．点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる ターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです 集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか？ 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索する… - 人力検索
空間インデックス - ma38su.sourceforge.jp
Cell method データ領域を包含するセルのサイズを事前に決定する必要があるため、動的なデータベースには不利のようです。 各セルは、そのセル領域と重なる領域の識別子を持ちます。セルを細かく区切れば検索精度は向上しますが、使用するデータ領域が増加します。 Digital MapはCell methodにより読み込む領域を検索していますが、すべてオンメモリでデータ構造を構築しているため、セルのサイズを大きくせざるを得ず、検索精度があまりよくありません。それに加えて数値地図25000には領域の外接長方形のデータしかないのでcell methodの恩恵をあまり受けることができず、地図データの読み込みが遅く、また表示領域以外の領域が読み込まれることが多々あります。 Quad Trees 領域を4分割（2次元）することで木構造を構築します．ディスク上に構築する際には、2分割するよりも高速です．ペ
R木 - Wikipedia
2次元矩形のR木の例 R木（英: R-tree）は、B木に似た木構造のデータ構造であり、多次元情報（例えば、二次元座標データなど）のインデックス付け、すなわち空間インデックスに使われる。それは例えば、「現在位置から2km以内の全ての美術館を探す」といった用途に使われる。 R木は、階層的に入れ子になった相互に重なり合う最小外接矩形 (MBR) で空間を分割する。R木のRは矩形 (Rectangle) を意味する。 R木の各ノードのエントリ数は可変である（事前に定義された上限がある）。葉ノード以外の各エントリには2つのデータが格納される。1つは子ノードへの参照であり、もう1つはその子ノードの全エントリを囲む外接矩形のデータである。 挿入および削除のアルゴリズムはこれらの外接矩形を使い、近い要素が同じ葉ノードに属するようにする（特に、新たな要素を挿入する際に、どの最下層の外接矩形にも収まらない場
ボロノイ図の書き方
目次 ボロノイ図の書き方 ボロノイ図作成の効率的な算法 ボロノイ図作成の効率的な算法 逐次添加法と再帰二分法の概略 逐次添加法 ステップ４ 逐次添加法 添加母点Pｍ＋１に一番近い母点を求める方法 式ｄ（Pｍ＋１、P）＜ｄ（Pｍ＋１、P*） 式ｄ（Pｍ＋１、P）＜ｄ（Pｍ＋１、P*） PPT Slide 母点の添加順序の工夫 メッシュの番号付け PPT Slide T メッシュを迅速に探す方法
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
