差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
Big Sky :: レーベンシュタイン距離を使ったあいまい grep コマンド「lsdgrep」作ってみた
元ネタはずいぶんと昔の記事なのだけど。 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー ■ 編集距離 (Levenshtein Distance) 昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベン... http://d.hatena.ne.jp/naoya/20090329/1238307757 思い付きはまったく関係ない所から。 mp3 が数千ファイル入ってるフォルダで何かの手違いで同じ曲が入ってしまう事が結構あって重複取り去る作業してた。ID3が違ってるとMD5も違うのでレーベンシュタインの文字列距離を使ってファイル名が似てるの調べたら422ファイル消せる事が分かった。 — Vim芸人 (@mattn_jp) February 25, 2017 これを
iBeaconのRSSIでiPhoneの二次元座標をとれたらいいな - tsujimotterのノートブック
この記事は iBeacon Advent Calendar 2013 の 22日目の記事です。 本当はestimoteを使って遊んでみた系の記事を書こうと思っていたのですが、とある事情で日本では使えないとのことで、仕方なく方針を変えて私の知っている知識を紹介したいと思います。（あまりiBeaconっぽい話じゃなくてすみません） 背景 タイトルの通り「iBeaconの電波強度 (RSSI) の測定値を使って正確な二次元座標を取ろう」という目論見です。 iBeaconではRSSIの値を使ってビーコンまでの距離が計算できますが、ざっくりとした近い・遠いの情報しかわかりません。 これをもっと精度よく、二次元座標がとれたらいいなと思った訳です*1。 RSSIを使った測位手法の中で、比較的精度の高い位置が得られる方法として、フィンガープリンティングという手法があります。iBeacon で実例がありませ
Twitterの投稿時間で類似度を計算してみた - 確率分布の類似度 - 唯物是真 @Scaled_Wurm
以前集合やベクトルの類似度の記事を書いたんですが、確率分布の類似度には触れていなかったのでついでに書きました ツイート時間分布の類似度を求める 今回はツイート時間ごとの頻度を正規化して、確率分布とみなして類似度を計算してみます 私のアカウント(以下mainと表記)に対して、私のもう一つのアカウント(以下subと表記)+私がリプライを送ってる数が多い(以下friendと表記)上位5人と比較します subがfriendよりも似た結果になることを期待しています 以下にツイート時間の分布(main + sub + friend 5人)を載せました ある程度似ていますが、人によってそこそこ形が違っていて、特に午前中の投稿時間の差は特徴的に見えます またfriend1の一人だけは大きく違った傾向を示しています 以下ではこれらが定量的にどれぐらい異なるのか類似度を計算して比較していきます グラフを描くの
マハラノビス距離とユークリッド距離の違い
相関のある多変量データで距離を測る場合、我々が通常「距離」と呼ぶユークリッド距離よりも、マハラノビス距離の方が都合がよい。多変量データを変数ごとに標準化してユークリッド距離をとる場合は標準化により変数間の関係性が変わる上に相関関係は考慮されないが、マハラノビス距離を使えば変数間の相関関係も考慮した多変量標準化尺度として使用できる。Rでのデモつき。 このメモでは、説明のために、比較的きれいなデータを用いて、距離の大きさで便宜上外れ値を判定してはいるが、ロバスト性のない平均値ベクトルや共分散行列から計算されるマハラノビス距離はやはり全くロバスト性をもたないため、外れ値検出の目的で使用してはいけない。逆に言えば、マハラノビス距離を用いて外れ値検出を行うためには、平均値ベクトルと共分散行列の代わりに、ロバスト推計した位置と尺度指標を用いれば良い。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.kecl.ntt.co.jp/icl/signal/sawada/mypaper/sigmod_j2013.pdf
¥¤¥ó¥¿¡¼¥Í¥Ã¥È·×¬¤È¥Ç¡¼¥¿²òÀÏ Âè12²ó
https://www.kamishima.net/archive/clustering.pdf
