最近鄰問題(NN)

將次數看成向量，然后我們就可以比對向量的距離(歐式距離，余弦距離)。數據中會有一些異常點，這些異常點會導致結果的不穩定。

這種思想非常的不穩定，因為他只基于一個樣本來做最后類別的判定。

K最近鄰算法(NN => KNN)

少數服從多數。

距離準則

Jaccard：并不是每個人都會點擊或者購買這么高強度的行為，因為購買是需要花錢的。我們能采集到的數據量比較的數據，實際上是用戶的一些隱性的行為，比如他在這個頁面停留了多久(時間閾值，比如30秒)，超過閾值我就認為他有興趣。它不像打分數據一樣有嚴格的連續值，比如0-10這樣一個嚴格的連續取值，它只有0，1（有或沒有）的這種行為，看過或沒看過，感興趣或不感興趣。Jaccard是算兩個向量共同是1的部分或者共同是0的部分。

近似最近鄰算法(KNN => ANN)

預先對數據做劃分會面臨一個問題，可能會劃分錯誤，無論怎么劃分都有可能將本身比較接近的一些點給劃分開。所以他會損失掉一部分準確度，當然這部分損失在你的承受范圍內的。在損失一些準確度的情況下，用一部分的空間去提升速度，實際上就是預先對數據做了劃分和索引。這種操作在工業界并不是致命的，比如淘寶上的找相似或者找同款功能。

局部銘感度哈希

生成2進制串，保證距離特性

在高維空間比較接近的會落到同一個桶里面。

LSH第一步做哈希，即把這些圖片都分完桶了，LSH映射完之后，他會拿到你指定的個數的，例如指定的是k，那它就會拿到kbit的串，意味著你掉到了kbit這樣一個串的桶里面。第一步是映射，映射做的事情就是對原始給定的高維向量，做一個映射，得到映射拿到的桶ID號。

第二步檢索，檢索做的是，首先他會去找桶里面其他的數據，LSHash這個庫檢索回來的張數是不確定的。當新的數據過來時，通過第一步的映射，一樣會拿到一個桶的編號，到這個桶里面看看有多少張圖片，將這個桶的圖片取出來，計算看滿不滿足要求，如果桶里的圖片不夠，LSHash保證不了個數，所以這個庫解決不了這個問題。在不夠的情況下，通過計算二進制串的漢明距離，將與他漢明距離為1的這些桶編號全都拿回來。如果漢明距離為1的不夠怎么辦，它再取漢明距離為2的桶。、

注意：你要小心的設置LSH 他映射到的空間維度，你要根據你的樣本量大致的估一下或者做測試。

lSH的直觀理解

像左圖中的c點劃分錯誤的情況下，你想讓你的檢索盡量的準確怎么辦，這個事情是可以做的，需要付出的代價是你計算資源或時間的成本，可以采用多次劃分的方式，然后根據這幾個超平面的檢索結果，取他們的并集。

LSH之相似網頁查找

詞(特征)的權重是指這個詞對這句話的重要度(tf-idf)。乘以權重時，原來是1的位置直接乘以權重，原來是0的位置用-1乘以權重。

有用的理由：如果現在去掉灰色這個詞，對最后的結果的正負性沒有影響，只有你去掉那些詞的時候對結果的正負性可能會有影響呢？是不是w權重比較大的詞！！就是說，如果在原來的文本中剔除一些或者加入一些不是那么重要的字的話，那我認為沒有影響，除非你剔除或加入額外分詞重要的詞，那這個時候可能就會認為這是不同的句子。

SimHash可用庫

LSH常用庫

ANN之K-means Tree

每個非葉子節點都是一個簇的聚類中心點。

如果你現在要找回Top 2T，如果不滿足他會怎么做呢？他會回溯回去，回溯到上一級大團，然后去找聚類中心第二接近的，因為聚類中心他們總會有一個遠近，所以他會對他們做一個排序(rank)，拿出來那些比較接近的小的簇，然后再去求并。

ANN之K-D Tree

DT決策樹，它在做的事情是去找一個波動最大的維度，為什么要找方差最大的維度？方差最大的維度，意味著這個維度上的熵比較大或者是他的不確定性比較高，他的信息增益比較大，也就是他能夠給我帶來減小不確定的可能性最大。

二維用線做切分

三維用面做切分，從三個維度中找哪個是波動/方差最大的。

假設現在要與(6,1)最接近的3個點，首先是第一個維度6，在7的左側，然后順著左側往下走，緊接著第二個維度1，判斷在4的左側還是右側？在左側，找到了(2,3)是離她最接近的點。然后沿著(2,3)這個葉子節點回溯到父節點(5,4)，計算加上父節點滿不滿足3個，不滿足，父節點還有一側(4,7)，再計算加上這個節點滿不滿足3個，發現滿足，就不再回溯到上一個父節點。

K-means Tree VS K-D Tree

工程經驗之ANN庫