Locality Sensitive Hashing

7 09 2009

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


Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: