1、相似項發現3.4-3.6文檔的局部敏感哈希算法文檔的局部敏感哈希算法距離測度距離測度局部敏感函數理論局部敏感函數理論3.4文檔的局部敏感哈希算法 3.4.1面向最小哈希簽名的LSH 3.4.2行條化策略的分析 3.4.3上述技術的綜合（完整的相似項發現方法）文檔的局部敏感哈希的產生原因 最小哈希簽名仍然無法高效尋找具有最大相似度的文檔。 即使文檔本身的數目不大，但需要比較的文檔對的數目可能很大。 實際中往往需要得到那些最相似或者相似度超過某個下界的文檔對，我們只需關注那些可能相似的文檔對。 通過LSH我們可以只關注可能相似的文檔對，而不需要研究所有文檔對。4.3.1面向最小哈希簽名的LSH L

2、SH(locality-sensitive hashing) 一般性做法一般性做法 對目標項進行多次哈希處理，使得相似項比不相似項更可能哈希到同一桶中。 將至少有一次哈希到同一桶中的文檔對看成是候選對（candidate pair）,只檢查這些候選對之間的相似度。 哈希到同一個桶中的非相似文檔對稱為偽正例（false positive）,希望它們在所有對中所占比例越低越好。 我們也希望大部分真正相似的文檔對會至少被一個哈希函數映射到同一桶中。 沒有映射到相同桶中的真正相似的文檔對稱為偽反例（false negative）。對最小哈希簽名矩陣的處理 假設擁有目標項的最小哈希簽名矩陣，將簽名矩陣劃

3、分成b個行條（band），每個行條由r行組成。 每個行條，存在一個哈希函數能夠將行條中的每r個整數組成的列向量（行條中的每一列）映射到某個大數目范圍的桶中。 可以對所有行條使用相同的哈希函數，但是對每個行條都使用一個獨立的桶數組，因此即使是不同行條中的相同向量列也不會被哈希到同一桶中。例3.10 12行簽名矩陣，分成4個行條，每個行條由3個行組成。3.4.2行條化策略分析 計算文檔（或其簽名）作為候選對的概率：計算文檔（或其簽名）作為候選對的概率： 假定使用b個行條，每個行條由r行組成，假定某對具體文檔間的Jaccard相似度為s. 不論常數b和r取值如何，上述形式的概率函數圖像大致如圖3-7

4、的S-曲線。曲線中上升最陡的地方對應的相似度就是所謂閾值（threshold）,是b和r的函數。閾值的一個近似估計值是 b=20,r=5,即簽名個數為100，分為20個行條，每行條有5行。 當s=0.8時，1-(0.8)5=0.328， 1-(0.8)520=0.00035 1- 1-(0.8)520=0.99965 通過對面向最小哈希簽名的LSH采用行條化策略進行處理，使得相似項會比不相似項更可能哈希到同一個桶中(0.00035 遠小于0.99965)。3.4.3上述技術的綜合 一個完整的相似項發現的方法：一個完整的相似項發現的方法：（1）找出可能的候選對相似文檔集合（2）基于該集合發現真正

5、的相似文檔 選擇某個k,并對每篇文檔構建其k-shingle集合。將這些k-shingle映射成更短的桶編號（后一步可選）； 將文檔-shingle對按照shingle排序； 選擇最小哈希簽名的長度n。對中排好序的表進行最小哈希簽名的計算； 選擇閾值t來定義應該達到的相似度使之被看做是預期的“相似對”。選擇行條數b和每個行條中的行數r，使得br=n，而閾值t近似等于(1/b)1/r 。 如果避免偽反例的產生很重要，那么選擇合適的b和r以產生小于t的閾值。 如果速度相當重要并且希望限制偽正例的數目，那么選擇合適的b和r來獲得更高的閾值。 應用面向最小哈希簽名的LSH技術來構建候選對； 檢查每個候

6、選對的簽名，確定他們一致性的比例是否大于t； （該步可選）如果簽名足夠相似，則直接檢查文檔本身看他們是否真正相似。不相似的文檔有時碰巧會具有相似的簽名。 該方法存在的缺陷：該方法存在的缺陷： （1）可能會產生偽反例，即某些相似文檔對由于沒有進入候選對所以最終沒有被識別出來。 （2）可能會產生偽正例，即在評估了某些候選對后發現其相似度不足。3.5距離測度（similarity measure） 3.5.1 距離測度的定義 3.5.2 歐氏距離 3.5.3 Jaccard距離 3.5.4 余弦距離 3.5.5 編輯距離 3.5.6海明距離3.5.1距離測度的定義 假定有一些點組成的集合，稱為空間（

7、space）。該空間下的距離測度是一個函數d(x , y)，以空間中的兩個點作為參數，輸出是一個實數值。該函數必須滿足下列準則：該函數必須滿足下列準則： d(x , y)0（距離非負） d(x , y)=0當且僅當x=y（只有點到自身的距離為0，其他距離都大于0） d(x , y)=d(y , x)（距離具有對稱性） d(x , y)d(x , z)+d(z , y)（三角不等式） 如果從x點行進到y點，那么一定要求經過某個特定的第三點z則不會有任何好處。 使得所有的距離測度表現的如同是從一個點到另一個點的最短路徑的長度。3.5.2歐氏距離 L2范式： Lr范式： L1范式距離（曼哈頓距離）：

8、 兩個點的距離是每維距離的絕對值之和。 L范式： 當r趨向于無窮大時Lr范式的極限值。 當r增大時只有那個具有最大距離的維度才真正起作用。 正式定義：在所有維度i下|xi-yi|中的最大值。例3.12 二維歐氏空間（平面）上有兩個點(2,7),(6,4)。 L2范式距離： L1范式距離： L范式距離：3.5.3 Jaccard距離 Jaccard距離： d(x , y)=1-SIM(x , y) 即1減去x、y的交集與并集的比率。 驗證驗證Jaccard距離是否為距離測度：距離是否為距離測度： （1）交集的大小不可能大于并集的大小，因此d(x , y)不可能為負值； （2）若x=y則d(x ,

9、 y)=0，這是因為xx=xx=x。 然而如果xy，那么xy的大小嚴格小于xy的大小，因此d(x , y)嚴格為正； （3）由于交集和并集運算都是對稱的，即xy=yx，xy=yx，因此d(x , y)=d(y , x); （4）三角不等式的驗證 SIM(x , y)是一個隨機最小哈希函數將x和y映射為相同值的概率。 Jaccard距離則為一個隨機最小哈希函數將x和y映射為不同值的概率。 如果h是一個隨機的最小哈希函數，那么h(x)h(y) 的概率不高于h(x)h(z)的概率與h(z)h(y)的概率之和。 因為只要有h(x)h(y)，那么至少h(x)和h(y)中的一個一定與h(z)不同，即h(x

10、)和h(y)不可能都是h(z),否則二者肯定相等。3.5.4 余弦距離（cosine distance） 在有維度的空間下余弦距離才有意義，這些空間包括歐氏空間和離散歐式空間（包括坐標只采用整數值或布爾值來表示的空間）。 在上述空間下，點可以代表方向。在這里不區分一個向量及其多倍向量（向量的每一維都放大相同的倍數得到的向量）。 兩個點的余弦距離實際上是點所代表的向量之間的夾角，不管空間有多少維，該夾角的范圍是0到180度。 首先計算夾角的余弦，然后應用反余弦函數將結果轉化為0到180度之間的角度，從而最終得到余弦距離。 給定向量x和y，其余弦距離如下： 驗證余弦距離是否為距離測度：驗證余弦距離

11、是否為距離測度： （1）余弦定義為0到180度之間，因此余弦距離非負； （2）當且僅當兩個向量表示同一方向時向量的夾角為0； （3）余弦距離 的對稱性：x和y的夾角顯然與y和x的夾角相等； （4）通過物理含義詮釋三角不等式。如要將向量x旋轉到y，可以先從x旋轉到z，再從z旋轉到y。兩次旋轉經過的夾角之和不會小于直接旋轉所得到的夾角。3.5.5 編輯距離 只適用于字符比較串。 兩個字符串x=x1x2xn 及y=y1 y2 ym 的編輯距離等于將x轉換為y所需要的單字符插入及刪除操作的最小數目。例3.14 兩個字符串x=abcde, y=acfdeg的編輯距離為3. 刪除字符b; 在字符c之后插入

12、字符f; 在字符e之后插入字符g。 可以驗證不存在少于3步的插入或刪除操作序列能把x轉換為y。最長公共子序列(LCS)（longest common subsequence） 通過在x和y的某些位置上進行刪除操作能夠得到某個字符串，基于上述方法構造出的x和y的最長公共字符串就是x和y的LCS。 其編輯距離等于x和y的長度之和減去它們的LCS長度的兩倍。例3.15 字符串x=abcde和y=acfdeg存在一個唯一的LCS即acde，包含了所有同時在x和y中出現的字符，且次序相同。 x的長度為5，y的長度為6，LCS的長度為4。 編輯距離=5+62*4=3 驗證編輯距離是否為距離測度：驗證編輯距

13、離是否為距離測度： （1）編輯距離非負。只有兩個相等的字符串的編輯距離才會為0； （2）編輯距離是對稱的。x到y的插入、刪除的操作序列完全可以顛倒次序應用與y轉換為x的過程中去。 （3）編輯距離滿足三角不等式。將x轉換為y的一種方法是先將x轉換為z，再將z轉換為y。x到z再到y的最少編輯操作數一定不小于從x到y的最小編輯操作數。3.5.6 海明距離（Hamming distance） 海明距離：兩個向量中不同分量的個數。 海明距離往往應用與布爾向量。 例3.16 向量10101和11110的海明距離為3。 兩個向量第2、4、5位元素不同，而其他元素均相同。 驗證海明距離是否為距離測度：驗證海明

14、距離是否為距離測度： （1）海明距離非負，當且僅當兩個向量相等時，海明距離為0； （2）海明距離在計算時與向量的先后順序無關； （3）滿足三角不等式：如果x和z有m個分量不同，z和y有n個分量不同，那么x和y中不同的分量個數不可能超過m+n個。3.6 局部敏感函數理論 3.6.1 局部敏感函數 3.6.2 面向Jaccard距離的局部敏感函數族 3.6.3 局部敏感函數族的放大處理 可高效產生候選對的函數族要滿足的三個條件：可高效產生候選對的函數族要滿足的三個條件： （1）它們必須更可能選擇近距離而不是遠距離作為候選對。 （2）函數之間必須在統計上相互獨立，在這個意義上，兩個或者多個函數的聯合

15、概率等于每個函數上獨立事件的概率乘積。 （3）必須在以下兩個方面具有很高的效率： 必須能夠在很短的時間內識別候選對，該時間遠低于掃描所有對所花費的時間。 它們必須可以組合在一起以更好地避免偽正例和偽反例，組合后函數所花費的時間也必須遠低于對的數目3.6.1 局部敏感函數 函數族（family of functions） f(x , y) f(x)=f(y)：x和y是一個候選對 f(x)f(y)：x和y不是一個候選對 （d1 , d2 , p 1 , p 2）-敏感的函數族： 令d1 d2 是定義在某個距離測度d下的兩個距離值。 函數族F中的每個函數f都滿足以下條件： 如果d(x , y) d1

16、， 那么f(x)=f(y)的概率至少是p 1 如果d(x , y) d2, 那么 f(x)=f(y)的概率最大是p23.6.2面向Jaccard距離的局部敏感函數族 目前只有一種找到局部敏感函數族的方法：采用最小哈希函數族并假設距離測度采用Jaccard距離。 一個最小哈希函數h:當且僅當h(x)=h(y)時，x和y是一對候選對。 對任意d1 ，d2， 0 d1 d2 1，最小哈希函數族是（ d1 ， d2 ， 1-d1 ，1- d2 ）-敏感的。3.6.3局部敏感函數族的放大處理 與構造（與構造（AND-construction） 假設給定一個（d1 , d2 , p 1 , p 2）-敏感

17、的函數族F 構造的新的函數族F： F的每個成員函數由r個F成員函數組成，r是一個固定常數。 若f在F中，f從F的成員函數集合f1 ,f2 ,，fn中構造，i=1,2r，當且僅當對所有i都有fi (x)=fi (y)時，才有f(x)=f(y) 由于F的成員函數都是從F的成員函數中獨立選出來的，因此可以斷言F是一個（d1 , d2 , (p1 ) r, (p2 )r )-敏感函數族。 即對任意p,如果F的一個成員函數判定(x , y)是候選對的概率為p，那么F的一個成員函數做相同判定的概率是pr . 與構造實際上反映了單個行條中所有r行的每一行的效果： 如果一個行條中r行的每一行的x , y值都相

18、等，那么基于整個行條就可以認為x和y是候選對。 或構造（或構造（OR-construction） 可以將一個（d1 , d2 , p 1 , p 2）-敏感的函數族F轉換為（d1 , d2 , 1-(1-p1 ) b, 1-(1-p2 )b )-敏感函數族F。 F的每一個成員函數f由b個F中的成員函數f1 ,f2 ,，fb構成。當且僅當存在一個或者多個i使得fi (x)=fi (y)時，才有f(x)=f(y) 或構造實際上反映了將多個行條組合的效果： 如果某個行條使得x和y可以成為候選對，那么x和y就成為候選對。 與構造過程降低了所有的概率(pr )。若謹慎選擇F和r，可使小概率p 2 非常接近0，