Locality Sensitive Hashing
Locality Sensitive Hashing (LSH) merupakan suatu metode untuk melakukan pengurangan jumlah dimensi dari data dengan dimensi tinggi, dimana pengurangan dilakukan dengan berbasis pada probabilitas. Ide dasarnya adalah melakukan hashing terhadap input data, sehingga data yang probabilitasnya tinggi untuk dikatakan sejenis akan di-map ke dalam bucket yang sama. Rendah tingginya probabilitas suatu data terhadap data yang lain, dihitung dengan jarak dari kedua data tersebut. Data yang dekat secara jarak akan mempunyai probabilitas tinggi, sedangkan data yang jauh secara jarak akan mempunyai probabilitas yang rendah. Data yang mempunyai probabilitas tinggi di-hash ke dalam satu bucket yang sama.
Locality Sensitive Hashing dapat juga digunakan untuk Clustering. Vector dari feature space dianggap himpunan dan ukuran similarity yang sering digunakan adalah Jaccard distance. Feature space dapat dianggap high-dimensional. Skema min-wise independent permutation (MinHash) kemudian digunakan untuk menyimpan item yang sejenis ke dalam satu bucket.
Persamaan yang sering digunakan adalah sebagai berikut:
* if d(p,q) \le R, then h(p) = h(q) (i.e.,p and q collide) atau probabilitas data untuk dibilang sama adalah tinggi,
* if d(p,q) \ge cR, then h(p) = h(q) dengan probabilitas yang rendah
* if d(p,q) \le R, then h(p) = h(q) (i.e.,p and q collide) atau probabilitas data untuk dibilang sama adalah tinggi,
* if d(p,q) \ge cR, then h(p) = h(q) dengan probabilitas yang rendah
Sumber:yudiagusta.wordpress.com
