『壹』 文本、語音相似度演算法
前段時間公司項目用到了語音識別,圖像識別,視頻識別等,其實不能說是識別,應該說是相似度對比吧,畢竟相似度對比還上升不了到識別哈,等以後有了更深的理解再來討論修改下!這次就當做一個總結吧!
其實它的原理和視頻圖像相似度演算法類似，將一系列的向量,特徵,權重,進行合並,然後降維降到一維,其實這個演算法也就是採用降維技術,將所有的特徵都用一個唯一標識來表示.然後這個標識是經過這個演算法內部的計算,再利用海明距離計算相似度，視頻和圖片是經過漢明距離計算的
文本我們是採用simhash演算法：
1.我們給文本裡面的詞進行分詞,我們是用ik演算法,這個演算法就是while循環,讀取一行,然後調用ik智能分詞的類,智能去切割裡面的分詞;
2.根據裡面的詞頻,simhash演算法會加一個權重,當然,得詞頻達到多少個的時候才會有有權重,這也是它的缺點,一般文本數據較少的時候,他是不準確的,一般數據量在500+;演算法內部的話會將一系列的向量,特徵,權重,進行合並,然後降維降到一維,其實這個演算法也就是採用降維技術,將所有的特徵都用一個唯一標識來表示.然後這個標識是經過這個演算法內部的計算,然後得到的一個指紋簽名；
3.然後對比兩個文本的相似度就是將兩個指紋簽名進行海明距離計算,如果海明距離<8(根據業務和場景去判斷這個值，8是建議，參考)的話,表示兩個相似,小於3的話.表示兩個文本重復.
simhash演算法我們還可以做語音相似度,它的基本原理就是根據傅里葉變換處理得到聲波的形狀。
語音的坡度如果向上我們就用1表示,向下我們就用0表示,這樣的話,我們也可以用二進制碼去描述一首歌曲.得到一個唯一的指紋簽名,對比兩個音頻的相似度就是將兩個指紋簽名進行海明距離計算<8的話,我們就默認兩個音頻相似.
總結：都是把特徵降到一維，然後採用海明距離計算。計算的值小於多少時，就當做是相似。我這邊講的太淺了，實在領悟有限，時間有限，觸摸不深，等下次有新的領悟再來補充！
『貳』 怎麼用lucene判斷兩篇文章的相似度 java
用演算法中的求最大相似子字元串的方法LCS或許可以，它可以找到兩個字元串中最大相似的子字元串。
Java code
/*
* @author talent_marquis<甜菜侯爵>
* Email: [email protected]
* Copyright (C) 2007 talent_marquis<甜菜侯爵>
* All rights reserved.
*/
package ustc.mse.algorithms.dynamicProgramming;
/*
* LCS, Longest-Common-Subsequence
*/
public class LCS
{
public enum DIRECTION{ TOP, TOP_LEFT, LEFT };
private char[] first;
private char[] second;
private int[][] lcsTable;
private DIRECTION[][] lcsAssistTable;
private int lcsLength;
private String lcs_str, lcsMatrix_str, lcsAssistMatrix_str;
private StringBuffer str_buffer;
public LCS( String str1, String str2 )
{
first = str1.toCharArray();
second = str2.toCharArray();
lcsTable = new int[ first.length + 1 ][ second.length + 1 ];
lcsAssistTable = new DIRECTION[ first.length + 1 ][ second.length + 1];
lcs_str = null;
『叄』 文本相似度演算法
TF是指歸一化後的詞頻，IDF是指逆文檔頻率。給定一個文檔集合D，有d1,d2,d3,......,dn∈D。文檔集合總共包含m個詞（註：一般在計算TF−IDF時會去除如「的」這一類的停用詞），有w1,w2,w3,......,wm∈W。我們現在以計算詞wi在文檔dj中的TF−IDF指為例。
TF的計算公式為：
TF=freq(i,j) / maxlen(j)
在這里freq(i,j) 為wi在dj中出現的頻率，maxlen(j)為dj長度。
TF只能時描述詞在文檔中的頻率，但假設現在有個詞為」我們「，這個詞可能在文檔集D中每篇文檔中都會出現，並且有較高的頻率。那麼這一類詞就不具有很好的區分文檔的能力，為了降低這種通用詞的作用，引入了IDF。
IDF的表達式如下：
IDF=log(len(D) / n(i))
在這里len(D)表示文檔集合D中文檔的總數，n(i)表示含有wi這個詞的文檔的數量。
得到TF和IDF之後，我們將這兩個值相乘得到TF−IDF的值：
TF−IDF=TF∗IDF
TF可以計算在一篇文檔中詞出現的頻率，而IDF可以降低一些通用詞的作用。因此對於一篇文檔我們可以用文檔中每個詞的TF−IDF組成的向量來表示該文檔，再根據餘弦相似度這類的方法來計算文檔之間的相關性。
BM25演算法通常用來做搜索相關性評分的，也是ES中的搜索演算法，通常用來計算query和文本集合D中每篇文本之間的相關性。我們用Q表示query，在這里Q一般是一個句子。在這里我們要對Q進行語素解析（一般是分詞），在這里以分詞為例，我們對Q進行分詞，得到q1,q2,......,qt這樣一個詞序列。給定文本d∈D，現在以計算Q和d之間的分數（相關性），其表達式如下：
Score(Q,d)=∑ti=1wi∗R(qi,d)
上面式子中wi表示qi的權重，R(qi,d)為qi和d的相關性，Score(Q,d)就是每個語素qi和d的相關性的加權和。
wi的計算方法有很多，一般是用IDF來表示的，但這里的IDF計算和上面的有所不同，具體的表達式如下：
wi=IDF(qi)=logN−n(qi)+0.5n(qi)+0.5
上面式子中N表示文本集合中文本的總數量，n(qi)表示包含qi這個詞的文本的數量，0.5主要是做平滑處理。
R(qi,d)的計算公式如下：
R(qi,d)=fi∗(k1+1)fi+K∗qfi∗(k2+1)qfi+k2
其中
K=k1∗(1−b+b∗dlavgdl)
上面式子中fi為qi在文本d中出現的頻率，qfi為qi在Q中出現的頻率，k1,k2,b都是可調節的參數，dl,avgdl分別為文本d的長度和文本集D中所有文本的平均長度。
一般qfi=1，取k2=0，則可以去除後一項，將上面式子改寫成：
R(qi,d)=fi∗(k1+1)fi+K
通常設置k1=2,b=0.75。參數b的作用主要是調節文本長度對相關性的影響。
『肆』 如何用wordnet計算 文本相似度 演算法實現
1.信息檢索中的重要發明TF-IDF
1.1TF
Term frequency即關鍵詞詞頻，是指一篇文章中關鍵詞出現的頻率，比如在一篇M個詞的文章中有N個該關鍵詞，則
（公式1.1-1）
為該關鍵詞在這篇文章中的詞頻。
1.2IDF
Inverse document frequency指逆向文本頻率，是用於衡量關鍵詞權重的指數，由公式
（公式1.2-1）
計算而得，其中D為文章總數，Dw為關鍵詞出現過的文章數。
2.基於空間向量的餘弦演算法
2.1演算法步驟
預處理→文本特徵項選擇→加權→生成向量空間模型後計算餘弦。
2.2步驟簡介
2.2.1預處理
預處理主要是進行中文分詞和去停用詞，分詞的開源代碼有：ICTCLAS。
然後按照停用詞表中的詞語將語料中對文本內容識別意義不大但出現頻率很高的詞、符號、標點及亂碼等去掉。如「這，的，和，會，為」等詞幾乎出現在任何一篇中文文本中，但是它們對這個文本所表達的意思幾乎沒有任何貢獻。使用停用詞列表來剔除停用詞的過程很簡單，就是一個查詢過程：對每一個詞條，看其是否位於停用詞列表中，如果是則將其從詞條串中刪除。
『伍』 相似度計算
你是求一個相似度演算法：
如果一個公司真實排名為x1,
而你的打分排名是
x2，
怎麼搞一個合理的評分數呢？
對差值的絕對值進行打分
|x1-x2|=0
得14分（28的一半)
|x1-x2|>=14
得
0分
就是：|差值|>14
得0分，|差值|<=14,得
14-|差值|
滿分
14x28
分，
這樣對28個排名，就可以算出得分了
相似度=得分/(14x28)
x
100
(%)
用c語言編個計算小程序很簡單。
『陸』 文本相似度-bm25演算法原理及實現
BM25演算法，通常用來作搜索相關性平分。一句話概況其主要思想：對Query進行語素解析，生成語素qi；然後，對於每個搜索結果D，計算每個語素qi與D的相關性得分，最後，將qi相對於D的相關性得分進行加權求和，從而得到Query與D的相關性得分。
BM25演算法的一般性公式如下：
其中，Q表示Query，qi表示Q解析之後的一個語素（對中文而言，我們可以把對Query的分詞作為語素分析，每個詞看成語素qi。）；d表示一個搜索結果文檔；Wi表示 語素qi的權重 ；R(qi，d)表示 語素qi與文檔d的相關性得分 。
下面我們來看如何定義 。判斷 一個詞的權重 ，方法有多種，較常用的是IDF。這里以IDF為例，公式如下：
其中，N為索引中的 全部文檔數 ，n(qi)為 包含了qi的文檔數。
根據IDF的定義可以看出，對於給定的文檔集合， 包含了qi的文檔數越多，qi的權重則越低 。也就是說，當很多文檔都包含了qi時，qi的區分度就不高，因此使用qi來判斷相關性時的重要度就較低。
我們再來看語素qi與文檔d的相關性得分 。首先來看BM25中相關性得分的一般形式：
其中，k1，k2，b為 調節因子 ，通常根據經驗設置，一般k1=2，k2=1，b=0.75；fi為 qi在d中的出現頻率 ，qfi為 qi在Query中的出現頻率 。dl為 文檔d的長度 ，avgdl為 所有文檔的平均長度 。由於絕大部分情況下，qi在Query中只會出現一次， 即qfi=1 ，因此公式可以簡化為：
從K的定義中可以看到，參數b的作用是 調整文檔長度對相關性影響的大小 。 b越大，文檔長度的對相關性得分的影響越大 ，反之越小。而 文檔的相對長度越長，K值將越大，則相關性得分會越小 。這可以理解為，當文檔較長時，包含qi的機會越大，因此，同等fi的情況下，長文檔與qi的相關性應該比短文檔與qi的相關性弱。
綜上，BM25演算法的相關性得分公式可總結為：
分段再分詞結果
列表的每一個元素是一個dict，dict存儲著 一個文檔中每個詞的出現次數
存儲每個詞的idf值
['自然語言', '計算機科學', '領域', '人工智慧', '領域']與每一句的相似度
https://github.com/jllan/jannlp/blob/master/similarity/bm25.py
『柒』 經典大規模文本相似識別架構和演算法總結
在數據分析和挖掘領域，我們經常需要知道個體間差異大小，從而計算個體相似性。如今互聯網內容爆發時代，針對海量文本的相似識別擁有極大需求。本文將通過識別兩段文本是否相似，來看看常見的相似演算法，及線上落地方案。
一般情況下，我們會將數據進行向量化，將問題抽象為數學問題。比如兩個樣本X、Y，X=（x1, x2, x3, … xn），Y=（y1, y2, y3, … yn）表示N維向量空間的兩個樣本，分析差異主要有距離度量和相似度度量。
文本向量化有很多方法，切詞、ngram是最常用方法。一般的，分詞加預處理能更好的表達語義，我們通過預處理，過濾掉無效字元及停用詞。
對"組裝衣櫃，剛買不久" 和 "組裝鞋櫃，全新"向量化
距離（Distance）用於衡量樣本在空間上的距離，距離越大，差異越大。
歐氏距離是最容易直觀理解的距離度量方法，我們認知中兩個點在空間中的距離就是歐氏距離。擴展到高維空間中，歐式距離的計算公式如圖1：
圖1 歐氏距離歐式距離因為計算是基於各維度特徵的絕對數值，所以歐氏度量需要保證各維度指標在相同的刻度級別，當不同維度單位不同將使距離失去意義。
餘弦相似度用向量空間中兩個向量夾角餘弦值作為衡量兩個個體間差異的大小。餘弦相似度更加註重兩個向量在方向上的差異，而非距離或長度。公式如圖2：
圖2 餘弦相似度
通過三維坐標系可以很直觀的看到兩者的區別，如圖3所示：
圖3 歐式距離和餘弦相似度區別
歐氏距離和餘弦相似度各自的計算方式和衡量特徵，分別適用於不同的數據分析模型：歐式距離適應於需要從維度大小中體現差異的場景，餘弦相似度更多的是方向上的差異。如果我們分詞後，將每個詞賦予一定的權重，那麼可以使用歐氏距離。更多情況下，我們採用餘弦相似度來計算兩文本之間相似度。
上面的相似演算法，適用於小量樣本，兩兩計算。那麼在大規模樣本下，給定新的樣本怎麼找到相似的樣本呢？
下面我們將引入 SimHash 演算法。
SimHash是Google在2007年發表的一種指紋生成演算法或者叫指紋提取演算法（如圖4），其主要思想是降維。
圖4 SimHash演算法
演算法主要原理分為這幾步：
大家可能存在疑問：生成一串二進制需要這么麻煩嗎？直接用hash函數生成0和1的不是更簡單。比如：md5和hashcode等。
可以看得出來，相似兩個文本，simhash局部變化而普通的hashcode卻天壤之別。文本轉換為SimHash後，我們通過海明距離（Hamming distance）計算兩個SimHash是否相似。
Google的論文給出的數據中，64位的簽名，在漢明距離為3的情況下， 可認為兩篇文檔是相似。
為了查詢相似，我們依然需要兩兩比較。但漢明距離演算法給了我們降維的捷徑。
可以證明，漢明距離小於3情況下，將hash code等分為4份，則必有一份完全相同。
基於上述特點，我們設計一個MySQL存儲索引方案來實現，如圖5所示。
圖5 MySQL存儲索引方案
『捌』 文本相似度之Sim_hash演算法
本文記錄的目的是方便自己學習和復習，有誤之處請諒解，歡迎指出。
最近項目有用到Sim_hash，做個簡單記錄。
Sim_hash是Google用來處理大量文本去重的演算法，屬於 局部敏感哈希（Locality Sensitive Hashing，LSH） ，LSH哈希能夠使兩篇只有小部分改動的文章編碼後哈希值具有相似性，既可用於去重，也可用於計算相似度。對於只有小部分改動的兩篇文章，在計算他們之間的相似度時，如果採用md5，兩篇文章的md5編碼值差異會非常大。但使用局部敏感哈希可以使相似的文章哈希編碼後聚集在一起，刪除符合閾值條件的文章，達到去重的效果。
一、演算法流程
1）分詞：對文本進行去停用詞、分詞，提取n個關鍵詞和關鍵詞的tf-idf權重來表徵文章。如下圖分詞及權重。
2）關鍵詞哈希編碼：每個關鍵詞通過hash函數生成固定位數二進制哈希。
3）權重編碼：二進制編碼中0調整為-1變為權重向量，與權重相乘。
4）權重編碼疊加：將所有權重編碼縱向求和，得到最終的文章權重。
5）二值化：按正數為1負數為0的規則將文章權重二值化。
6）漢明距離相似度：排除漢明距離小於閾值的文章，一般設置為3。漢明距離計算速度快，思路簡單，原理是計算兩個二值化編碼相同位置處的不同值的個數。
二、Sim_hash整體流程
需求： 來了一個相似文章推薦需求，需要推薦出與文章內容相似的數據，但又不能完全相似。利用目前庫中已有的POI標簽和POI權重數據，結合simhash演算法，計算出每個文章poi_sim_hash，計算距離
數據： 線上拉取10W文章數據
測試結果： 下圖為隨機抽樣的測試結果（第一條為查詢數據），基本 符合預期效果 。前期還可以使用 類目和發布時間 進行前置過濾，減少數據量。