Ⅰ 如何用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。
然後按照停用詞表中的詞語將語料中對文本內容識別意義不大但出現頻率很高的詞、符號、標點及亂碼等去掉。如「這，的，和，會，為」等詞幾乎出現在任何一篇中文文本中，但是它們對這個文本所表達的意思幾乎沒有任何貢獻。使用停用詞列表來剔除停用詞的過程很簡單，就是一個查詢過程：對每一個詞條，看其是否位於停用詞列表中，如果是則將其從詞條串中刪除。
Ⅱ 文本相似度演算法
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的作用主要是調節文本長度對相關性的影響。
Ⅲ 文本相似度之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文章數據
測試結果： 下圖為隨機抽樣的測試結果（第一條為查詢數據），基本 符合預期效果 。前期還可以使用 類目和發布時間 進行前置過濾，減少數據量。
Ⅳ 文本比較有哪些演算法
用java比較兩個文本文件的不同
RangeDifferencer
public class RangeDifferencer {
private static final RangeDifference[] EMPTY_RESULT= new RangeDifference[0];
/* (non Javadoc)
* Cannot be instantiated!
*/
private RangeDifferencer() {
// nothing to do
}
/**
* Finds the differences between two <code>IRangeComparator</code>s.
* The differences are returned as an array of <code>RangeDifference</code>s.
* If no differences are detected an empty array is returned.
*
* @param left the left range comparator
* @param right the right range comparator
* @return an array of range differences, or an empty array if no differences were found
*/
public static RangeDifference[] findDifferences(IRangeComparator left, IRangeComparator right) {
int rightSize= right.getRangeCount();
int leftSize= left.getRangeCount();
//
// Differences matrix:
// only the last d of each diagonal is stored, i.e., lastDiagonal[k] = row of d
//
int diagLen= 2 * Math.max(rightSize, leftSize); // bound on the size of edit script
int maxDiagonal= diagLen;
int lastDiagonal[]= new int[diagLen + 1]; // the row containing the last d
// on diagonal k (lastDiagonal[k] = row)
int origin= diagLen / 2; // origin of diagonal 0
// script corresponding to d[k]
LinkedRangeDifference script[]= new LinkedRangeDifference[diagLen + 1];
int row, col;
// find common prefix
for (row= 0; row < rightSize && row < leftSize && rangesEqual(right, row, left, row) == true;)
row++;
lastDiagonal[origin]= row;
script[origin]= null;
int lower= (row == rightSize) ? origin + 1 : origin - 1;
int upper= (row == leftSize) ? origin - 1 : origin + 1;
if (lower > upper)
return EMPTY_RESULT;
//System.out.println("findDifferences: " + maxDiagonal + " " + lower + " " + upper);
// for each value of the edit distance
for (int d= 1; d <= maxDiagonal; ++d) { // d is the current edit distance
if (right.skipRangeComparison(d, maxDiagonal, left))
return EMPTY_RESULT; // should be something we already found
// for each relevant diagonal (-d, -d+2 ..., d-2, d)
for (int k= lower; k <= upper; k += 2) { // k is the current diagonal
LinkedRangeDifference edit;
if (k == origin - d || k != origin + d && lastDiagonal[k + 1] >= lastDiagonal[k - 1]) {
//
// move down
//
row= lastDiagonal[k + 1] + 1;
edit= new LinkedRangeDifference(script[k + 1], LinkedRangeDifference.DELETE);
} else {
//
// move right
//
row= lastDiagonal[k - 1];
edit= new LinkedRangeDifference(script[k - 1], LinkedRangeDifference.INSERT);
}
col= row + k - origin;
edit.fRightStart= row;
edit.fLeftStart= col;
//Assert.isTrue(k >= 0 && k <= maxDiagonal);
script[k]= edit;
// slide down the diagonal as far as possible
while (row < rightSize && col < leftSize && rangesEqual(right, row, left, col) == true) {
++row;
++col;
}
//Assert.isTrue(k >= 0 && k <= maxDiagonal); // Unreasonable value for diagonal index
lastDiagonal[k]= row;
if (row == rightSize && col == leftSize) {
//showScript(script[k], right, left);
return createDifferencesRanges(script[k]);
}
if (row == rightSize)
lower= k + 2;
if (col == leftSize)
upper= k - 2;
}
--lower;
++upper;
}
// too many differences
//Assert.isTrue(false);
return null;
}
/**
* Finds the differences among two <code>IRangeComparator</code>s.
* In contrast to <code>findDifferences</code>, the result
* contains <code>RangeDifference</code> elements for non-differing ranges too.
*
* @param left the left range comparator
* @param right the right range comparator
* @return an array of range differences
*/
public static RangeDifference[] findRanges(IRangeComparator left, IRangeComparator right) {
RangeDifference[] in= findDifferences(left, right);
List out= new ArrayList();
RangeDifference rd;
int mstart= 0;
int ystart= 0;
for (int i= 0; i < in.length; i++) {
RangeDifference es= in[i];
rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, es.rightStart() - mstart, ystart, es.leftStart() - ystart);
if (rd.maxLength() != 0)
out.add(rd);
out.add(es);
mstart= es.rightEnd();
ystart= es.leftEnd();
}
rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, right.getRangeCount() - mstart, ystart, left.getRangeCount() - ystart);
if (rd.maxLength() > 0)
out.add(rd);
return (RangeDifference[]) out.toArray(EMPTY_RESULT);
}
//---- private methods
/*
* Creates a Vector of DifferencesRanges out of the LinkedRangeDifference.
* It coalesces adjacent changes.
* In addition, indices are changed such that the ranges are 1) open, i.e,
* the end of the range is not included, and 2) are zero based.
*/
private static RangeDifference[] createDifferencesRanges(LinkedRangeDifference start) {
LinkedRangeDifference ep= reverseDifferences(start);
ArrayList result= new ArrayList();
RangeDifference es= null;
while (ep != null) {
es= new RangeDifference(RangeDifference.CHANGE);
if (ep.isInsert()) {
es.fRightStart= ep.fRightStart + 1;
es.fLeftStart= ep.fLeftStart;
RangeDifference b= ep;
do {
ep= ep.getNext();
es.fLeftLength++;
} while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart);
} else {
es.fRightStart= ep.fRightStart;
es.fLeftStart= ep.fLeftStart;
RangeDifference a= ep;
//
// deleted lines
//
do {
a= ep;
ep= ep.getNext();
es.fRightLength++;
} while (ep != null && ep.isDelete() && ep.fRightStart == a.fRightStart + 1);
boolean change= (ep != null && ep.isInsert() && ep.fRightStart == a.fRightStart);
if (change) {
RangeDifference b= ep;
//
// replacement lines
//
do {
ep= ep.getNext();
es.fLeftLength++;
} while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart);
} else {
es.fLeftLength= 0;
}
es.fLeftStart++; // meaning of range changes from "insert after", to "replace with"
}
//
// the script commands are 1 based, subtract one to make them zero based
//
es.fRightStart--;
es.fLeftStart--;
result.add(es);
}
return (RangeDifference[]) result.toArray(EMPTY_RESULT);
}
/*
* Tests if two ranges are equal
*/
private static boolean rangesEqual(IRangeComparator a, int ai, IRangeComparator b, int bi) {
return a.rangesEqual(ai, b, bi);
}
/*
* Tests whether <code>right</code> and <code>left</code> changed in the same way
*/
private static boolean rangeSpansEqual(IRangeComparator right, int rightStart, int rightLen, IRangeComparator left, int leftStart, int leftLen) {
if (rightLen == leftLen) {
int i= 0;
for (i= 0; i < rightLen; i++) {
if (!rangesEqual(right, rightStart + i, left, leftStart + i))
break;
}
if (i == rightLen)
return true;
}
return false;
}
/*
* Reverses the range differences
*/
private static LinkedRangeDifference reverseDifferences(LinkedRangeDifference start) {
LinkedRangeDifference ep, behind, ahead;
ahead= start;
ep= null;
while (ahead != null) {
behind= ep;
ep= ahead;
ahead= ahead.getNext();
ep.setNext(behind);
}
return ep;
}
}
下面是一段關於如何使用這些類的簡單的測試代碼
public class RangeDifferencerTest extends TestCase {
InputStream left = null;
InputStream right = null;
/**
* @see junit.framework.TestCase#setUp()
*/
protected void setUp() throws Exception {
String file1 = "d:/temp/1.txt";
String file2 = "d:/temp/2.txt";
left = new FileInputStream(new File(file1));
right = new FileInputStream(new File(file2));
super.setUp();
}
/**
* @see junit.framework.TestCase#tearDown()
*/
protected void tearDown() throws Exception {
left.close();
right.close();
super.tearDown();
}
public static void main(String[] args) {
}
/*
* Test method for 'com.greatroad.smbnm.compare.RangeDifferencer.findDifferences(IRangeComparator, IRangeComparator)'
*/
public void testFindDifferences() {
try {
RangeDifference[] rds = RangeDifferencer.findRanges(new LineComparator(left,"GBK"),new LineComparator(right,"GBK"));
if(rds != null ){
for(int i=0; i<rds.length; i++){
RangeDifference rd = rds[i];
int length = rd.leftLength();
System.out.println(
"kind = "+rd.kind()
+",left["+rd.leftStart()+"-"+rd.leftEnd()
+"],right["+rd.rightStart()+"-"+rd.rightEnd()+"]");
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
Ⅳ 經典大規模文本相似識別架構和演算法總結
在數據分析和挖掘領域，我們經常需要知道個體間差異大小，從而計算個體相似性。如今互聯網內容爆發時代，針對海量文本的相似識別擁有極大需求。本文將通過識別兩段文本是否相似，來看看常見的相似演算法，及線上落地方案。
一般情況下，我們會將數據進行向量化，將問題抽象為數學問題。比如兩個樣本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存儲索引方案
Ⅵ 文本演算法是什麼意思
在文本信息空間內尋找任何兩個最相關的文本信息，並將之簡並成一個文本信息，從而實現信息數量的收縮。
簡並演算法的實現通過比較整個信息空間內的所有文本的相關性（相識性），得到相互之間的相關性後兩兩(注)進行配對。配對的要求是這兩個文本信息的相關性最大，例如A 找到了文檔B，那麼B 也一定找到最相關的文檔就是A 。
注，某些情況A 最相近的文檔是C ，那麼B 而B 最相關的文檔也是C ，存在一種情況，A,B,C 三者之間自恰，就是構成空間信息最近的一個三角形。
得到了最相似文檔後，將只進行平均化，或者簡單的迭加。
信息空間中獨立信息的數量會減少到原來的一半以下，然後重復實現1 的過程，在進行兼並。
信息最後簡並到唯一的一個信息，就是整個信息文本的平均值。
畫出信息樹的結構，就能夠根據要進行規模不同大小的聚類進行自動聚類了。
Ⅶ 文本、語音相似度演算法
前段時間公司項目用到了語音識別,圖像識別,視頻識別等,其實不能說是識別,應該說是相似度對比吧,畢竟相似度對比還上升不了到識別哈,等以後有了更深的理解再來討論修改下!這次就當做一個總結吧!
其實它的原理和視頻圖像相似度演算法類似，將一系列的向量,特徵,權重,進行合並,然後降維降到一維,其實這個演算法也就是採用降維技術,將所有的特徵都用一個唯一標識來表示.然後這個標識是經過這個演算法內部的計算,再利用海明距離計算相似度，視頻和圖片是經過漢明距離計算的
文本我們是採用simhash演算法：
1.我們給文本裡面的詞進行分詞,我們是用ik演算法,這個演算法就是while循環,讀取一行,然後調用ik智能分詞的類,智能去切割裡面的分詞;
2.根據裡面的詞頻,simhash演算法會加一個權重,當然,得詞頻達到多少個的時候才會有有權重,這也是它的缺點,一般文本數據較少的時候,他是不準確的,一般數據量在500+;演算法內部的話會將一系列的向量,特徵,權重,進行合並,然後降維降到一維,其實這個演算法也就是採用降維技術,將所有的特徵都用一個唯一標識來表示.然後這個標識是經過這個演算法內部的計算,然後得到的一個指紋簽名；
3.然後對比兩個文本的相似度就是將兩個指紋簽名進行海明距離計算,如果海明距離<8(根據業務和場景去判斷這個值，8是建議，參考)的話,表示兩個相似,小於3的話.表示兩個文本重復.
simhash演算法我們還可以做語音相似度,它的基本原理就是根據傅里葉變換處理得到聲波的形狀。
語音的坡度如果向上我們就用1表示,向下我們就用0表示,這樣的話,我們也可以用二進制碼去描述一首歌曲.得到一個唯一的指紋簽名,對比兩個音頻的相似度就是將兩個指紋簽名進行海明距離計算<8的話,我們就默認兩個音頻相似.
總結：都是把特徵降到一維，然後採用海明距離計算。計算的值小於多少時，就當做是相似。我這邊講的太淺了，實在領悟有限，時間有限，觸摸不深，等下次有新的領悟再來補充！