MLlearning(2)——simHashアルゴリズム

この文章は主にsimHashのアルゴリズムについて述べている.これはLSHの簡単な実現である.データの再利用に広く使われているアルゴリズムです.似たようなウェブサイトや画像の検索に利用できます.そして、二つのサンプルがあまり違っていないとき、アルゴリズムはまだ効果があります.言及に値するのは,このアルゴリズムの時空複雑さは次元に関する項が存在しないので,次元災害に遭遇しないし,次元が高い時にkNNアルゴリズムを最適化することもできる.
特徴
このアルゴリズム(LSH)は二重性を持っています.

は、いくつかのグループの異なる特徴について、hashと同じ(すなわち衝突)の可能性ができるだけ小さい.これもhashの基本的な特徴です.

は、類似した特徴のいくつかのセット(すなわち、特徴空間における距離が小さい)の特徴について、hashの同じまたは類似の可能性ができる限り大きくなる.これはLSHの特徴である.

simHash実現
SImHashはLSHのうちの一つで、文字列についての簡単な実現である.操作手順は以下の通りです.

は、1つの数がhashを表し、数の2進数が選択可能であることを定義し、一般的に32 bitまたは64 bitを選択します.この数桁と同じ整形ベクトルvを同時に定義する.

は入力文字列を分割し、文字数で分割してもいいし、スペースで分割してもいいです.

は、分割された文字列ごとに通常hashを行い、hashの値がkであることを記憶する.約束num[i]はnumのi番目のバイナリ値を表します.kの各iに対して、k[i]>0なら、v[i]+=weight、さもなければv[i]-=weight、weightはこのサブストリングの権利値を表します.

は、ベクトルvの各項目について、このエントリが0より大きいなら、simHashの対応する位置1を、そうでなければ、0

にセットする.
これにより、文字列のsimHash値が得られ、時間の複雑さはOである.
サブストリング類似判定
2つの文字列が似ていることを定義します.すなわち、ハミングディスクは、2つの整数の海明距離を計算する関数です.海明距離は2つの整数バイナリで異なる桁数を符号化します.
経験によって、kは普通3を取ります.一方海明距離の計算にはCの実現を与える高速な方法がある.この統計的なバイナリの1つの数のアルゴリズムは平行アルゴリズムと呼ばれていますが、ここでは詳しく述べません.

static int bitCount(unsigned int n){
    n=(n &0x55555555)+((n>>1)&0x55555555);
    n=(n &0x33333333)+((n>>2)&0x33333333);
    n=(n &0x0f0f0f0f)+((n>>4)&0x0f0f0f0f);
    n=(n &0x00ff00ff)+((n>>8)&0x00ff00ff);
    n=(n &0x0000ffff)+((n>>16)&0x0000ffff);
    return n;
}

int hammingDist(unsigned int a,unsigned int b){
    return bitCount(a^b);
}

検索
新しい要素と既知のセット要素が似ているかどうかを検索する方法は2つあります.

時間の複雑さはO(N)である.線形検索アルゴリズム

時間の複雑さは、O([C(3,32)+C(2,32)+C(1,32)]k)=O(5488 k)——合成アルゴリズムである.

光算出simHash値は、新要素が既知のセットの中の要素と似ているかどうかを判断するのに時間がかかります.特にデータ量が多い時.このとき、第一のアルゴリズムは、一定の前処理アルゴリズムで最適化され得る.
k=3と仮定する.最適化の方法は、32 bitまたは64 bit(以下、32 bitを例とする)のsh値を平均的に4つのセグメントに分けます.引出しの原理によって、二つの文字列のhashの中には必ず1段の中に違いがない位があります.したがって、各要素hashの4つの8 bitをキーとして表に格納し、値はhashの完全な値とすることができる.検索する場合は、新しい文字列hashの4つの8 bit表のすべてのhashを比較し、海明距離が3以下であるかどうかを判断します.このように最適化すると、時間複雑度はO(4 k)=O(4＊n/(2^9-1)≒O(n/128)に低下します.線形複雑度ですが、かなり速くなりました.
全体的に実現する
SimHashシステム全体の実装(C＋＋バージョン)は、githubにソースを開始しました.https://github.com/Darksun2010/MLlearning/tree/master/LSH