平面幾何におけるベクトル演算 » 内積と外積
内積・外積 ベクトルの内積 (inner product, dot product, scalar product) と外積 (outer product, cross product, vector product) という演算を用いると幾何の問題を解く考え方が簡単になります。 幾何学における内積や外積はもともと3次元空間上で定義されるものなので，まずは3次元空間上で幾何学的な内積・外積を導入し， それらが線形代数的なベクトル演算と等価であることを利用し，内積・外積を2次元平面上に拡張（縮小？）します。 3次元空間上において，ベクトルの内積（ドット積）は a⋅b で表され， 以下の式で定義されます： 内積はcosを使って定義されている点と，内積の結果は単一の値＝スカラーになる点に注意してください。 また，ベクトルの外積（クロス積）は a×b で表され， その大きさ |a×b| は で与え
はてなのような自動キーワードリンクをtx-rubyで実装
はてなダイアリーやニコニコ大百科では、本文のキーワードに自動的にリンクが付くようになっていますが、ニコニコ大百科では、sennaとrubyを使って実装しているそうです。 はてなのようなキーワードリンクをRubyで付与する実例 僕もキーワードリンクを実装する機会があったのですが、そのときはtx-rubyを使いました。 tx-ruby これはtrieというデータ構造を扱うtxというライブラリを、rubyから使うものです。 rubyを介しても十分高速で、以前Wikipediaの見出し語約90万語をキーワードに使って試した際も、非常に高速に動作しました。 大変便利だったので、書いておきます。 tx-rubyのダウンロードはこちらから。 ダウンロードしたファイルを解凍したあと、そのディレクトリに移動して、 ruby setup.rb とすると、簡単にインストールできます。（Windowsでも使えます
ベイズ推定を知っているフリをするための知識
最近はベイジアンが増えてきて、実用分野での利用も進んでいるようだ。話題としては知っておきたいが、世間一般には理解に混乱を生んでいるようだ。 ベイズ推定は入門レベルの統計学の教科書ではオマケ的な扱いがされており、実際に伝統的な統計手法を拡張している面が強い。そういう意味では、誤解や混乱があっても仕方が無い。 利用する必要があるのか無いのか良く分からない点も多いのだが、知らないと告白するのも気恥ずかしいかも知れない。自分ではベイズ推定で分析を行わない人が、ベイズ信者と話をあわせるために最低限知っておくべき事をまとめてみた。 1. ベイズ推定とは何か？ ベイズ推定とは、ベイズの定理を応用した推定手法だ。端的に理解するためには、最尤法に事前確率を導入している事だけ覚えれば良い。これで哲学的議論を全て回避してベイズ推定を把握することができる。 下の(1)式ではπ（θ）が事前確率、π(θ|x)が事後確
点の多角形に対する内外判定
点が多角形ループの内側にあるか外側にあるかを判定するには？ 要素は２次元空間内に存在するものとします。 解説 内外判定の基本的な考え方として、「内外を判定したい点から発するレイ（ray：一条の光）を仮定し、レイが多角形の辺を何回横切るかを数え、偶数回横切るとき、点は多角形の外側、奇数回横切るとき、点は多角形の内側と判定することができる」という考え方があります。 ただ、この考え方に従って実装を行うと、レイに対して点接触になる点のある多角形や、レイに対して線接触になる辺のある多角形の場合に判定を誤ってしまう実装になることがあります。 下に示す実装では、レイをＸプラス方向に発して、多角形の辺がレイを、「上から下に横切るときには横切り回数を１引き、下から上に横切るときには横切り回数を１足すこととする」ことや、「レイの線上にある点はレイより上にあることとする」ことにより、レイに対して点接触になる点の
http://homepage3.nifty.com/katamari/knowledge/knowledge1/knowledge1.html
多角形の内部か外部かを判定 落雷データの解析で、何県に落ちているかを判定するときに使ったものです。 ある点が多角形の内部にあるか外部にあるか判定するには、その点から下に垂線を引き、垂線が多角形と何回交わるかによって判定します。奇数回交わればその点は内部、偶数回交われば外部にあることになります。 線分の交差判定 線分 a = a2 - a1 と線分 b = b2 - b1 が交差している場合，線分 b の端点 b1 と b2 は必ず線分 a の両側にあります。また，線分 a の端点 a1 と a2 も必ず線分 b の両側にあります。逆に交差していない場合，線分 a か線分 b のどちらかから見て，両点ともに片側にある場合が必ずあるといえます。 ある点が線分（ベクトル）の左側にあるか右側にあるかというのは，外積を使えば判定できます。sinは0度～180度で正の値，180度～360度で負の値
射影幾何
射影幾何が結構面白かったので書いておく。 ユークリッド幾何では以下の性質がある。 二つの点は一つの直線で結ばれる。 二つの直線は平行でなければ一つの点で交わる。 「平行でなければ」というのを除けば二つの命題は双対的である。ゆえに「平行でなければ」を取り除きたくなってしまう。 取り除いたのが射影幾何である。 射影幾何では以下の命題が成り立つ。 二つの点は一つの直線で結ばれる。 二つの直線は一つの点で交わる。 つまり平行線も交わらなくてはならない。どこで交わるか。無限遠点である。 射影平面はユークリッド平面に無限遠点の集合を付け加えたものになる。 無限遠点はどこにあるか。無限遠の彼方である。 無限遠点をどう表したらいいか。 ユークリッド平面上の任意の点は(x,y)という直交座標によって表せる。 たとえばy軸の正方向にある無限遠点を(0,∞)で表すというのもひとつの方法かも知れない。しか
サルでもわかる顔検出の原理 - 科学信仰
顔検出機能はここ数年で急激に普及してデジカメとかケータイとかにフツーに入るようになったり、Google画像検索のオプションに入ってたりして、すっかりコモディティ化しちゃってるけど、ちょっと前まではすごい困難で実用化に手を出すなんてとてもとてもな技術だったんだよね。 2001年のViola & Johnsの論文*1で超高速＆超正確な検出アルゴリズムが発表されるまでは。 これの画期的だった点は非力なパソコン（とか現在のケータイ内蔵CPUとか）で画像中からリアルタイムに顔を検出できたことなんだ。 キモは３点。 Integral-ImageによるHaar-like検出器の高速演算 AdaBoostによる検出能力の強化 多段フィルタ（cascade）による非顔領域の高速排除 具体的にどれがViolaらのオリジナルの仕事なのかはよく知らないけれど。 少なくとも一個目と三個目はそうな気がする。 Inte
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
kd tree（kd木）を使った近傍点検索 - higepon blog
kd tree を使った近傍点検索のメモ。 kd tree の日本語の説明はkd木 - 日本語版 Wikipedia。 近傍点検索の擬似コードがあり、日本語版の元となっているのはkd-tree - 英語版 Wikipedia。 実際に動くコードで分かりやすいものは弾さんのところ。404 Blog Not Found:algorithm - 最近点検索をkd-treeで。 他には An intoductory tutorial on kd-trees という PDF があるが難しい。 kd tree の構築は、平衡木にするためのロジックがいくつかある事をのぞけばとても簡単。弾さんのコードを読めば分かると思う。 近傍点の検索は k 次元で説明されているものが多く分かりづらいと思った。自分で単純な2次元の場合にして考えれば良い。 流れは以下の通り。 検索対象点 p を kd tree 上で bi
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
SPYSEEのつながりマイニングのはなし。 - TMBのおぼえがき
オーマ×クックパッド勉強会に参加しました ごはんが美味しかった。 まえおき http://spysee.jp/のなかのひとです。 フロントエンドやインフラ系はシャッチョーやid:amachangがやっているので、それ以外のところやってます。主にアルゴリズム。つながりの抽出手法や同姓同名処理手法を開発しました。 時々、なかのひととしていろんな会合に出没してます。そのたびに、 「つながりどうやってできてんのー？」 「同姓同名どうなってんのー？」 など聞かれますが、詳細に答えたことはありませんでした。about SPYSEE的な話はIVSのLaunch Pad(動画)などで話したことはありますが、アルゴリズムの詳しいところまでは時間なくて話しておりません。 さて先日、オーマ×クックパッド合同勉強会 を開催しました。そこでお時間いただき、「SPYSEEのつながりマイニング手法」という題目で講演させ
EM algorithm（EMアルゴリズム、Expectation Maximization algorithm）について - データサイエンティスト上がりのDX参謀・起業家
EMアルゴリズムはいろんなところで使われます。 基本的には未知パラメータの推定方法の一種です。 とりあえず箇条書でまとめます。 提案論文：Maximun likelihood from incomplete data via the EM algorithm. Dempster AP, Laird NM and Rubin DB. JRSS B. 39,1-38. 1977. 提案者のRubinは欠測分野、因果推論の権威で次の教科書も書いています。 Statistical Analysis with Missing Data (Wiley Series in Probability and Statistics) 作者: Roderick J. A. Little,Donald B. Rubin出版社/メーカー: Wiley-Interscience発売日: 2002/09/09メディア:
MinHashによる高速な類似検索 - Preferred Networks Research & Development
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
パターン認識の前処理に必要な二値画像の細線化
はじめに 細線化はThinningやSkeletonizationと呼ばれ、二値画像（白と黒の色だけで表現された2階調の画像）を幅1ピクセルの線画像に変換する処理です。線が途中で切れたり、孔が開いたりしてはいけません。得られた線は、元の図形の幅の中心にくることが望まれます。 エッジ検出によって得られた画像は、元の画像の変化が比較的緩やかで広範囲な場合には、幅が広くなってしまいます。エッジ検出の閾値を高くすると幅は狭くなりますが、緩やかな変化を見逃してしまいます。したがって、閾値を低く選んで、幅広くエッジ部分を出させ、その後に細線化処理を行って、文字認識やパターン認識に使うことが多いのです。 アプレットを見る 対象読者 画像処理に関心があり、パターン認識の前処理を学習したい人。 必要な環境 J2SE 5.0を使っていますが、それより若干古いバージョンでも大丈夫です。CPUパワーは、大きい方が
2010年まとめ:データと向き合った一年 - 科学と非科学の迷宮
はじめに:2010年弾丸ツアー 今年一年を一言でまとめると、「データと向き合った」一年でした。 2009年の終わり、私は The Datacenter as a Computer の読書会を通して、分散システムによる大量なデータの処理がこれからの時代にもっと重要になるということを学びました。 The Datacenter as a Computer 読書会 その流れを受け、1月には id:marqs や id:daisukebe とともに「集合知プログラミング」の読書会を開き、データマイニングの基礎を勉強しました。 大量のデータを扱う前に、小さなデータを扱う術を身につける必要があると思ったからです。 Programming Collective Intelligence 100111View more presentations from Sho Shimauchi. 第1回集合知プログラ
ハフ変換 - Wikipedia
ハフ変換（ハフへんかん、Hough変換）は、デジタル画像処理で用いられる特徴抽出法の一つである。古典的には直線の検出を行うものだったが、更に一般化されて様々な形態に対して用いられている。現在広く用いられている変換法はen:Richard Duda及びen:Peter Hartが1972年に発明した「一般化ハフ変換」である。この名は1962年にen:Paul Houghが得た関連する特許に由来する。この変換法は1981年のen:Dana H. Ballardの論文 "Generalizing the Hough transform to detect arbitrary shapes"（「 ハフ変換の一般化による任意の形態の検出」）によってコンピュータビジョンの領域で広く用いられるようになった。 理論[編集] いかなる点をとっても、その点を通る直線は無限個存在し、それぞれが様々な方向を向くが
Kazuho@Cybozu Labs: アクセスログからアテンション（注目情報）をデータマイニングする手法について
多数のユーザーの行動記録からアテンション情報（注目されているデータが何か）をデータマイニングしたいというのは、大量のデータを扱っているウェブサイトにおいては自然と出てくる要求です。そこで、先月末にサービスを終了したサービス「パストラック」において使用していた、アクセスログから注目度（人気度）の高いウェブページや人名等のキーワードを抽出するためのアルゴリズムを紹介しておきたいと思います。 たとえばはてなブックマークのような、ユーザーの能動的な行為（「ブックマークする」という作業）から注目情報を抽出するのは決して難しいことではありません。それは、直近の一定期間内のブックマーク数＝注目度、という前提が上手に機能するからです。現に、はてなブックマークの人気エントリーは、最近24時間程度の期間内にブックマークしたユーザー数の多い URL を降順で並べているように見受けられます。 しかし、アクセスログ
ベクトル量子化 - デー
はてブのコメントを見たのと、僕もbag of keypoints関係の論文を見たときに一瞬で分かったつもりになってそれを信じ続けていたけど不安になったのでググったところ別に間違ってもいなさそうだったので、ここでたまに書いてるベクトル量子化とは何かという話とそれをなぜ使っているのかという話を。（僕なりに） 僕がベクトル量子化と言ったときには、単純には 入力ベクトル→クラスラベル(スカラ) への変換を指している。あらかじめ、K個のクラス(グループ)を定義しておいて、入力ベクトルがどのクラスに属するか推定を行って、属するクラスの番号に変換してしまう。これによって、どんな入力ベクトルも(int)1〜Kのスカラ値に変換できる、というかかなり大雑把だけどそういうことにしてしまう。 具体的な例としては、 まず入力ベクトルとして想定されるデータを適当に集めてそれをk-meansでクラスタリングする。データ
３点の座標から簡単に角度と回転方向を求める．(2・3・N次元，外積を用いる方法)
S ≡ (Px - Cx) * (Qy - Cy) - (Py - Cy) * (Qx - Cx) とする．S＞0 なら左回り，S＜0 なら右回り，S＝0 ならば C，P，Q は一直線上にある．(注) なお，この判別方法は，CP と CQ が同じ長さである必要はない． θを求めたい場合はこちらへ． この問題を見て，逆三角関数 tan-1 (Ｃ言語では atan() や atan2()) を使って CP と CQ の角度をそれぞれ求め， 両者を比較しようと考えた方が多いのではないでしょうか． しかしこの問題では，角度そのものではなく角度差の符号を求めればよいので， 逆三角関数を使う方法よりも簡単で優れた，外積を使う方法を紹介します． ２つの２次元ベクトル A＝(Ax, Ay), B＝(Bx, By) の外積を次のように定義する． A × B ≡ Ax * By － Ay * Bx ここで O
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
HMM, MEMM, CRF まとめ - あらびき日記
