935
文本相似度計算基本方法小結
在計算文本相似項發現方麵，有以下一些可參考的方法。這些概念和方法會幫助我們開拓思路。
相似度計算方麵
Jaccard相似度：集合之間的Jaccard相似度等於交集大小與並集大小的比例。適合的應用包括文檔文本相似度以及顧客購物習慣的相似度計算等。
Shingling：k-shingle是指文檔中連續出現的任意k個字符。如果將文檔表示成其k-shingle集合，那麼就可以基於集合之間的Jaccard相似度來計算文檔之間的文本相似度。有時，將shingle哈希成更短的位串非常有用，可以基於這些哈希值的集合來表示文檔。
最小哈希：集合上的最小哈希函數基於全集上的排序轉換來定義。給定任意一個排列轉換，集合的最小哈希值為在排列轉換次序下出現的第一個集合元素。
最小哈希簽名：可以選出多個排列轉換，然後在每個排列轉換下計算集合的最小哈希值，這些最小哈希值序列構成集合的最小哈希簽名。給定兩個集合，產生相同哈希值的排列轉換所占的期望比率正好等於集合之間的Jaccard相似度。
高效最小哈希：由於實際不可能產生隨機的排列轉換，因此通常會通過下列方法模擬一個排列轉換：選擇一個隨機哈希函數，利用該函數對集合中所有的元素進行哈希操作，其中得到的最小值看成是集合的最小哈希值。
簽名的局部敏感哈希：該技術可以允許我們避免計算所有集合對或其最小哈希簽名對之間的相似度。給定集合的簽名，我們可以將它們劃分成行條，然後僅僅計算至少有一個行條相等的集合對之間的相似度。通過合理選擇行條大小，可以消除不滿足相似度閾值的大部分集合對之間的比較。
向量空間距離方麵
歐式距離：n維空間下的歐式距離，是兩個點在各維上差值的平方和的算數平方根。適合歐式空間的另一個距離是曼哈頓距離，指兩個點各維度的差的絕對值之和。
Jaccard距離：1減去Jaccard相似度也是一個距離測度。
餘弦距離：向量空間下兩個向量的夾角大小。
編輯距離：該距離測度應用於字符串，指的是通過需要的插入、刪除操作將一個字符串處理成另一個字符串的操作次數。編輯距離還可以通過兩個字符串長度之和減去兩者最長公共子序列長度的兩倍來計算。
海明距離：應用於向量空間。兩個向量之間的海明距離計算的是它們之間不相同的位置個數。
索引輔助方麵
字符索引：如果將集合表示成字符串，且需要達到的相似度閾值接近1。那麼就可以將每個字符串按照其頭部的一小部分字母建立索引。需要索引的前綴的長度大概等於整個字符串的長度乘以給定的最大的Jaccard距離。
位置索引：我們不僅可以給出索引字符串前綴中的字符，也可以索引其在前綴中的位置。如果兩個字符串共有的一個字符並不出現在雙方的第一個位置，那麼我們就知道要麼存在某些前麵的字符出現在並集但不出現在交集中，那麼在兩個字符串中存在一個更前麵的公共字符。這樣的話，我們就可以減少需要比較的字符串對數目。
後綴索引：我們不僅可以索引字符串前綴中的字符及其位置，還可以索引當前字符後綴的長度，即字符串中該字符之後的位置數量。由於相同字符但是後綴長度不同意味著有額外的字符必須出現在並集但不出現在交集中，因此上述結構能夠進一步減少需要比較的字符串數目。
總結
以上的一些概念和方法可以配合使用，可以基本滿足許多場景下的相似度計算。相似度計算又可以為相關推薦做基礎。怎麼做好詞的粒度切分，怎麼劃定閾值，選擇何種距離測算，如何優化實現方法還是要下很多功夫的。
兩個例子
Levenshtein其實是編輯距離，下麵計算編輯距離的方法是把兩個String串裏的字/詞當成一個矩陣來比較和計算。
package zbf.search.recommend;
public class LevenshteinDis {
public static void main(String[] args) {
// 要比較的兩個字符串
String str1 = "相似度計算方法";
String str2 = "文本相似項發現";
levenshtein(str1, str2);
}
public static void levenshtein(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
int[][] dif = new int[len1 + 1][len2 + 1];
for (int a = 0; a <= len1; a++) {
dif[a][0] = a;
}
for (int a = 0; a <= len2; a++) {
dif[0][a] = a;
}
int temp;
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
temp = 0;
} else {
temp = 1;
}
// 取三個值中最小的
dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
dif[i - 1][j] + 1);
}
}
System.out.println("字符串\"" + str1 + "\"與\"" + str2 + "\"的比較");
System.out.println("差異步驟：" + dif[len1][len2]);
// 計算相似度
float similarity = 1 - (float) dif[len1][len2]
/ Math.max(str1.length(), str2.length());
System.out.println("相似度：" + similarity);
}
private static int min(int... is) {
int min = Integer.MAX_VALUE;
for (int i : is) {
if (min > i) {
min = i;
}
}
return min;
}
}
下麵是餘弦距離計算的例子：
public class CosineSimilarAlgorithm {
public static double getSimilarity(String doc1, String doc2) {
if (doc1 != null && doc1.trim().length() > 0 && doc2 != null
&& doc2.trim().length() > 0) {
Map<Integer, int[]> AlgorithmMap = new HashMap<Integer, int[]>();
//將兩個字符串中的中文字符以及出現的總數封裝到，AlgorithmMap中
for (int i = 0; i < doc1.length(); i++) {
char d1 = doc1.charAt(i);
if(isHanZi(d1)){
int charIndex = getGB2312Id(d1);
if(charIndex != -1){
int[] fq = AlgorithmMap.get(charIndex);
if(fq != null && fq.length == 2){
fq[0]++;
}else {
fq = new int[2];
fq[0] = 1;
fq[1] = 0;
AlgorithmMap.put(charIndex, fq);
}
}
}
}
for (int i = 0; i < doc2.length(); i++) {
char d2 = doc2.charAt(i);
if(isHanZi(d2)){
int charIndex = getGB2312Id(d2);
if(charIndex != -1){
int[] fq = AlgorithmMap.get(charIndex);
if(fq != null && fq.length == 2){
fq[1]++;
}else {
fq = new int[2];
fq[0] = 0;
fq[1] = 1;
AlgorithmMap.put(charIndex, fq);
}
}
}
}
Iterator<Integer> iterator = AlgorithmMap.keySet().iterator();
double sqdoc1 = 0;
double sqdoc2 = 0;
double denominator = 0;
while(iterator.hasNext()){
int[] c = AlgorithmMap.get(iterator.next());
denominator += c[0]*c[1];
sqdoc1 += c[0]*c[0];
sqdoc2 += c[1]*c[1];
}
return denominator / Math.sqrt(sqdoc1*sqdoc2);
} else {
throw new NullPointerException(
" the Document is null or have not cahrs!!");
}
}
public static boolean isHanZi(char ch) {
// 判斷是否漢字
return (ch >= 0x4E00 && ch <= 0x9FA5);
}
/**
* 根據輸入的Unicode字符，獲取它的GB2312編碼或者ascii編碼，
*
* @param ch
* 輸入的GB2312中文字符或者ASCII字符(128個)
* @return ch在GB2312中的位置，-1表示該字符不認識
*/
public static short getGB2312Id(char ch) {
try {
byte[] buffer = Character.toString(ch).getBytes("GB2312");
if (buffer.length != 2) {
// 正常情況下buffer應該是兩個字節，否則說明ch不屬於GB2312編碼，故返回'?'，此時說明不認識該字符
return -1;
}
int b0 = (int) (buffer[0] & 0x0FF) - 161; // 編碼從A1開始，因此減去0xA1=161
int b1 = (int) (buffer[1] & 0x0FF) - 161; // 第一個字符和最後一個字符沒有漢字，因此每個區隻收16*6-2=94個漢字
return (short) (b0 * 94 + b1);
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
}
return -1;
}
}
最後更新：2017-04-03 21:30:16