我們希望尋找在眾多商品之間的關係,這種尋找多對多且同時發生的關係,我們稱之為 Market Basket Analysis。如同IF {A} then {B} ,當A發生時B會同時發生(co-occurrence)的機率很高時,我們會說A與B之間存在著關聯。本系列文會介紹找出這種關聯的技巧associationrule,以及兩種演算法來解決因資料量太大而需要大量disk IO的問題。



我們希望尋找在眾多商品之間的關係,這種尋找多對多且同時發生的關係,我們稱之為 Market Basket Analysis。如同IF {A} then {B} ,當A發生時B會同時發生(co-occurrence)的機率很高時,我們會說A與B之間存在著關聯。本系列文會介紹找出這種關聯的技巧association rule learning,以及兩種演算法來解決因資料量太大而需要大量disk IO的問題。



在本文中會介紹LSH(Locality-Sensitive Hashing),它的核心概念是:若能透過 hashing 的機制,讓相似度高的資料有高機率被 hash 到同一個 bucket 中,相似度低的資料被分到同一個 bucket 的機率很小,那就只需要在同一個 bucket 中做線性搜尋,就可以找到大多數相似的資料。如此即可將原本大量的資料,分為很多個小的子集合,只需要對子集合中的元素進行運算,進而達到接近 O(N) 的時間。



這篇文主要會簡介 Jaccard similarity 及 Minhash 的原理、證明及實作的技巧。 為了降低資料的維度,且仍能保留相似度(similarity),我們希望能找到一個hash函數h符合以下兩種特徵:1. 能將高維度的資料C,映射為較低維度的特徵h(C) (signature) 2. 維持 Sim(C1,C2) ≒ Sim(h(C1),h(C2))



在一般低維度的資料中,找尋相似的資料只需要透過線性搜尋(linear search)以O(N^2)的時間複雜度去搜尋即可,但若對高維度、資料量大的資料進行線性搜尋就會花上過多的時間,本文會介紹解決問題的想法。現今有非常多這類型的應用。如:圖片檢索(以圖搜圖)、對相似主題的網頁分類、尋找抄襲、重複的文章內容