ハミング距離の計算はホントに速いのか？
これは@sakanazensen君が主催する『Computer Vision Advent Calendar 2013』の12/8の記事です。今年はあまり活発でないようなので、小ネタですが参戦しました。 はじめに 昨今のコンピュータビジョン・パターン認識分野で特徴ベクトルのバイナリベースの記述法が流行っています。その利点の一つとして、特徴ベクトル間の距離としてコンピュータにとって計算が容易な「ハミング距離」が使える、というものがあります。これはXOR演算と PopCount演算（いくつのビットが1かをカウントする演算）で構成されており、特に近年のCPUにはまず搭載されているベクトル計算命令セットの一つ「SSE4.2」の専用命令「POPCNT」が高速演算の根拠としてよく引き合いに出されます。二つともかなりプリミティブな命令ですから確かに高速に計算できそうな感じはします。しかしながら、例えばL
類似度と距離 - CatTail Wiki*
２つのデータが似ている度合いを，類似度の大きさや距離の近さといった数値にしてあらわすことで，クラスタ分析や，k-近傍法，多次元尺度構成法(MDS)をはじめとするいろいろな分析を行うことが可能となる． ここでは，よく知られている類似度や距離について述べる． 類似度という概念は，２つの集合の要素がまさにどれだけ似ているかを数量化したものであり，距離とは，要素同士の離れ具合，従って非類似度とちかい概念と考えてもよい． 参考までに数学における距離の概念の定義を示すと， 距離空間の定義 Sを１つの空でない集合とし，dをSで定義された2変数の実数値関数 d(SxS) → R が，以下の４条件（距離の公理） D1 ： （非負性） 任意のx,y∈Sに対して d(x,y)≧0． D2 ： （非退化性） x,y∈Sに対し d(x,y)=0 ⇔ x=y． D3 ： （対称性） 任意のx,y∈Sに対して d(x
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
