《Machine Learning：Clustering & Retrieval》課程第2章之LSH

1.KD-tree的局限？

當維度較高時，kd-tree有一系列問題，主要是node之間的交叉導致不能很好的prune，導致搜索效率很低。

一種方式就是找近似解就可以了，比如提到的approximate KNN，另外一種近似解法就是LSH。

2.什麼是LSH？

用隨機的超平面進行編碼。

3.為什麼說LSH是近似解？

因為最近鄰不一定在query point這一邊。

4.用超平面去劃分，會涉及哪些問題？

2指的是false negative，3指的是false positive。

5.如何選擇超平面呢？

random！

為什麼選擇隨機產生呢？

因為從概率角度，隨機產生把兩個點分到一邊的概率還是很大的，尤其當兩個點很相近的時候。

6.一個超平面夠嗎？

當然不夠啦，因為false positive太多了，計算複雜度也太高了。

7.那怎麼能減少false positive呢？

加更多的超平面唄。

8.那怎麼較少false negative呢？

因為加了更多的超平面後，那兩個相鄰的點的bin index不一樣的概率就加大了，所以

要加更多的hash table。

9.所以加超平面有利有弊了？

是的，減少false positive的同時增加了false negative，是一個trade－off。

為了減少false negative，要加hash table。

10.除了加hash table的數量外，還有別的方法嗎？

有，搜索neighbor bins，怎麼定義neighbor bins呢？就是flipping bits的個數，（有點像漢明距離），如果是flipping bits是1的話，那麼010的鄰居是000， 110， 011.

11.LSH的過程總結一下？

12.為什麼叫做Locality Sensitive hash？

If a hash has the tendency to put nearby data into the same bin, then it is a LS-Hash.

13.那LS hash和普通的hash有什麼區別呢？

普通的hash，比如md5，如果一個位元組變了，那麼整個hash值就完全變了。

而LS hash的目的是讓值相近的hash後的值也相近。

前者是用來validate file用的，後者是detection duplicate file用的。

推薦閱讀：