相似項(xiàng)發(fā)現(xiàn)(3.4-3.6)

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

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

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

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

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

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

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

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

9、 y)=0，這是因?yàn)閤x=xx=x。 然而如果xy，那么xy的大小嚴(yán)格小于xy的大小，因此d(x , y)嚴(yán)格為正； （3）由于交集和并集運(yùn)算都是對(duì)稱(chēng)的，即xy=yx，xy=yx，因此d(x , y)=d(y , x); （4）三角不等式的驗(yàn)證 SIM(x , y)是一個(gè)隨機(jī)最小哈希函數(shù)將x和y映射為相同值的概率。 Jaccard距離則為一個(gè)隨機(jī)最小哈希函數(shù)將x和y映射為不同值的概率。 如果h是一個(gè)隨機(jī)的最小哈希函數(shù)，那么h(x)h(y) 的概率不高于h(x)h(z)的概率與h(z)h(y)的概率之和。 因?yàn)橹灰衕(x)h(y)，那么至少h(x)和h(y)中的一個(gè)一定與h(z)不同，即h(x

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

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

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

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

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

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

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

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

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