相似度算法完

2017-04-23文本相似度算法一、引語通過采集系統(tǒng)我們采集了大量文本數(shù)據(jù)，但是文本中有很多重復(fù)數(shù)據(jù)影響我們對(duì)于結(jié)果的分析。分析前我們需要對(duì)這些數(shù)據(jù)去除重復(fù)，如何選擇和設(shè)計(jì)文本的去重算法？我們知道一篇文章或網(wǎng)頁與某些內(nèi)容或關(guān)鍵字之間的相關(guān)聯(lián)程度，但是，有的時(shí)候，我們還想知道，某兩篇文章是不是講的是同一個(gè)主題，同一種內(nèi)容。比如，我們想知道兩篇文章是否都是金融類文章或者都是醫(yī)學(xué)類文章。要知道，能不能確定兩篇文章是否相似一、利用余弦定理是用向量空間中兩個(gè)向量夾角的余弦值作為衡量兩個(gè)個(gè)體間差異的大小的度量一、利用余弦定理TF-IDF（termfrequency–inversedocumentfrequency）是一種用于資訊檢索與資訊探勘的常用加權(quán)技術(shù)。TF：TermFrequency詞頻IDF：Inversedocumentfrequency倒文檔頻率/whiterbear/article/details/45583809一、利用余弦定理頻率的計(jì)算方法：用該網(wǎng)頁的關(guān)鍵字出現(xiàn)的次數(shù)除以網(wǎng)頁的總字?jǐn)?shù)。我們把這個(gè)商稱為TF（關(guān)鍵字的頻率或者單文本的頻率）。比如，某個(gè)網(wǎng)頁中共有1000個(gè)詞，其中“原子能”，“的”，“應(yīng)用”分別出現(xiàn)了2次，35次和5次，那么它們的詞頻就分別是（2/1000）=0.002，（35/1000）=0.035，（5/1000）=0.005，這三個(gè)詞頻相加之和0.042就是這個(gè)網(wǎng)頁相對(duì)于“原子能應(yīng)用”這個(gè)關(guān)鍵字的TF（單文本詞頻）一、利用余弦定理含義：如果某個(gè)關(guān)鍵詞出現(xiàn)在網(wǎng)頁中出現(xiàn)，在網(wǎng)頁總數(shù)個(gè)情況下，值越大，我們就認(rèn)為關(guān)鍵詞的權(quán)重越小，反之亦然。（如關(guān)鍵字“python”在10萬個(gè)網(wǎng)頁中出現(xiàn)，而“gensim”只在1000個(gè)網(wǎng)頁中出現(xiàn)，那么“gensim”的權(quán)重就會(huì)比“python”多，這樣搜索出來的結(jié)果就與你想要的結(jié)果越貼近）比如，假定中文網(wǎng)頁數(shù)是=10億，“的”在所有的網(wǎng)頁中都出現(xiàn)，即D=10億，那么它的IDF=log(10億/10億)=log(1)=0。假如專用詞“原子能”在兩百萬個(gè)網(wǎng)頁中出現(xiàn)，即Dw=200萬，則它的權(quán)重IDF=log(500)=2.7。又假定通用詞“應(yīng)用”，出現(xiàn)在五億個(gè)網(wǎng)頁中，它的權(quán)重IDF=log(2)則只有0.3。一、利用余弦定理首先，我們針對(duì)一篇文章中所有實(shí)詞計(jì)算出它們的TF-IDF值。然后，把這些值對(duì)應(yīng)實(shí)詞在詞匯表中的位置進(jìn)行排列，就能得到一個(gè)向量。比如，詞匯表中有64000個(gè)詞，其編號(hào)和詞如下圖從而，我們能夠得到64000個(gè)數(shù)，組成64000維向量。我們使用這個(gè)向量來代表這個(gè)文章的特征信息一、利用余弦定理將三角形的兩邊b和c看成是以A為起點(diǎn)的向量，其中，分母表示兩個(gè)向量b和c的長度，分子表示兩個(gè)向量的內(nèi)積一、利用余弦定理舉一個(gè)具體的例子，假如文章X和文章Y對(duì)應(yīng)的向量分別是那么它們的夾角的余弦等于一、利用余弦定理由于向量中的每一個(gè)變量都是正數(shù)，因此余弦的取值在0和1之間，也就是說夾角在0度到90度之間。當(dāng)兩篇文章的向量的余弦等于1時(shí)，這兩個(gè)向量的夾角為零，兩篇文章完全相同；當(dāng)夾角的余弦接近于1時(shí)，兩篇文章相似，可以認(rèn)為屬于同一類文章；當(dāng)夾角的余弦趨近于零甚至于等于零時(shí)，說明它們直接相似度很低，甚至完全無關(guān)，術(shù)語兩種完全不同的文章二、歐氏距離歐氏距離衡量的是空間各點(diǎn)的絕對(duì)距離，跟各個(gè)點(diǎn)所在的位置坐標(biāo)直接相關(guān)歐氏距離和余弦距離各自有不同的計(jì)算方式和衡量特征，因此它們適用于不同的數(shù)據(jù)分析模型：歐氏距離能夠體現(xiàn)個(gè)體數(shù)值特征的絕對(duì)差異，所以更多的用于需要從維度的數(shù)值大小中體現(xiàn)差異的分析，如使用用戶行為指標(biāo)分析用戶價(jià)值的相似度或差異。余弦距離更多的是從方向上區(qū)分差異，而對(duì)絕對(duì)的數(shù)值不敏感，更多的用于使用用戶對(duì)內(nèi)容評(píng)分來區(qū)分興趣的相似度和差異，同時(shí)修正了用戶間可能存在的度量標(biāo)準(zhǔn)不統(tǒng)一的問題（因?yàn)橛嘞揖嚯x對(duì)絕對(duì)數(shù)值不敏感）。三、Jaccard相似度兩個(gè)集合的交集除以兩個(gè)集合的并集，所得的就是兩個(gè)集合的相似度四、最長公共子串字符串的相似性：如果將一個(gè)串轉(zhuǎn)換成為另一個(gè)串所需的操作數(shù)最少，那么可以說這兩個(gè)串是相似的另外一種權(quán)衡的方法是，尋換第三個(gè)串s3，如果s3都出現(xiàn)在s1和s2中，且出現(xiàn)的順序相同，但不要求在s1和s2中連續(xù)，那么s3的長度越大，就說明相似度越高。如果用暴力搜索的方法求解LCS問題，就要窮舉X的所有子序列，對(duì)每個(gè)子序列進(jìn)行檢查，看它是否是Y的子序列，記錄找到的最長的子序列。X對(duì)應(yīng)下標(biāo)人格集合{1，2，3……m}的一個(gè)子集，那么X的子序列就有2^m個(gè)五、編輯距離編輯距離的算法是首先由俄國科學(xué)家Levenshtein提出的，故叫Levenshtein距離，指的是兩個(gè)字符串之間，由一個(gè)轉(zhuǎn)換成另一個(gè)所需的最少編輯操作次數(shù)。其它算法這些算法對(duì)于待比較的文本數(shù)據(jù)不多時(shí)還比較好用，如果我們的爬蟲每天采集的數(shù)據(jù)以千萬計(jì)算，我們?nèi)绾螌?duì)于這些海量千萬級(jí)的數(shù)據(jù)進(jìn)行高效的合并去重simhash算法simhash方法是在大文本重復(fù)識(shí)別常用的一個(gè)方法，該方法主要是通過將對(duì)象的原始特征集合映射為一個(gè)固定長度的簽名，將對(duì)象之間的相似度的度量轉(zhuǎn)化為簽名的漢明距離，通過這樣的方式，極大限度地進(jìn)行了降低了計(jì)算和存儲(chǔ)的消耗。1、分詞把需要判斷文本分詞形成這個(gè)文章的特征單詞。最后形成去掉噪音詞的單詞序列并為每個(gè)詞加上權(quán)重，我們假設(shè)權(quán)重分為5個(gè)級(jí)別（1~5）。比如：“美國“51區(qū)”雇員稱內(nèi)部有9架飛碟，曾看見灰色外星人”==>分詞后為“美國（4）51區(qū)（5）雇員（3）稱（1）內(nèi)部（2）有（1）9架（3）飛碟（5）曾（1）看見（3）灰色（4）外星人（5）”，括號(hào)里是代表單詞在整個(gè)句子里重要程度，數(shù)字越大越重要。simhash算法2、hash通過hash算法把每個(gè)詞變成hash值，比如“美國”通過hash算法計(jì)算為100101,“51區(qū)”通過hash算法計(jì)算為101011。這樣我們的字符串就變成了一串串?dāng)?shù)字，還記得文章開頭說過的嗎，要把文章變?yōu)閿?shù)字計(jì)算才能提高相似度計(jì)算性能，現(xiàn)在是降維過程進(jìn)行時(shí)。3、加權(quán)通過2步驟的hash生成結(jié)果，需要按照單詞的權(quán)重形成加權(quán)數(shù)字串，比如“美國”的hash值為“100101”，通過加權(quán)計(jì)算為“4-4-44-44”；“51區(qū)”的hash值為“101011”，通過加權(quán)計(jì)算為“5-55-555”。simhash算法4、合并把上面各個(gè)單詞算出來的序列值累加，變成只有一個(gè)序列串。比如“美國”的“4-4-44-44”，“51區(qū)”的“5-55-555”，把每一位進(jìn)行累加，“4+5-4+-5-4+54+-5-4+54+5”==》“9-91-119”。這里作為示例只算了兩個(gè)單詞的，真實(shí)計(jì)算需要把所有單詞的序列串累加。5、降維把4步算出來的“9-91-119”變成01串，形成我們最終的simhash簽名。如果每一位大于0記為1，小于0記為0。最后算出結(jié)果為：“101011”。其它算法simhash算法但是如何計(jì)算兩個(gè)simhash的相似度呢？比較兩個(gè)simhash的01有多少個(gè)不同海明距離兩個(gè)simhash對(duì)應(yīng)二進(jìn)制（01串）取值不同的數(shù)量稱為這兩個(gè)simhash的海明距離舉例如下：10101和00110從第一位開始依次有第一位、第四、第五位不同，則海明距離為3。通過大量測(cè)試，simhash用于比較大文本，比如500字以上效果都還蠻好，距離小于3的基本都是相似，誤判率也比較低。但是如果我們處理的是微博信息，最多也就140個(gè)字，使用simhash的效果并不那么理想。/question/19645541精確率和召回率又被稱為查準(zhǔn)率和查全率為什么不直接hash“你媽媽喊你回家吃飯哦，回家羅回家羅”“你媽媽叫你回家吃飯啦，回家羅回家羅”。通過simhash計(jì)算結(jié)果為：10000100101011011111111000001010110100010011111000010010110010111000010010101101011111100000101011010001001111100001101010001011通過hashcode計(jì)算為：11111111111111111111111111111111100010000011001101001110110111101010010001111111110010110011101傳統(tǒng)hash函數(shù)解決的是生成