目录：

一 计算两个字符串之间的相似度

二、TF-IDF与余弦相似性的应用（二）：找出相似文章

一 计算两个字符串之间的相似度

本文转载自cscmaker

（1）余弦相似性 

          通过测量两个向量之间的角的余弦值来度量它们之间的相似性。0度角的余弦值是1，而其他任何角度的余弦值都不大于1;并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。所以，它通常用于文件比较。

          详见百科介绍（点击打开链接）

（2）算法实现的中未使用权重（IDF ---逆文档频率），使用词项的出现次数作为向量空间的值。

import java.util.HashMap; 
import java.util.Iterator; 
import java.util.Map; 

public class SimilarDegreeByCos 
{ 
/* 
* 计算两个字符串(英文字符)的相似度，简单的余弦计算，未添权重 
*/ 
public static double getSimilarDegree(String str1, String str2) 
{ 
//创建向量空间模型，使用map实现，主键为词项，值为长度为2的数组，存放着对应词项在字符串中的出现次数 
Map<String, int[]> vectorSpace = new HashMap<String, int[]>(); 
int[] itemCountArray = null;//为了避免频繁产生局部变量，所以将itemCountArray声明在此 

//以空格为分隔符，分解字符串 
String strArray[] = str1.split(" "); 
for(int i=0; i<strArray.length; ++i) 
{ 
if(vectorSpace.containsKey(strArray[i])) 
++(vectorSpace.get(strArray[i])[0]); 
else 
{ 
itemCountArray = new int[2]; 
itemCountArray[0] = 1; 
itemCountArray[1] = 0; 
vectorSpace.put(strArray[i], itemCountArray); 
} 
} 

strArray = str2.split(" "); 
for(int i=0; i<strArray.length; ++i) 
{ 
if(vectorSpace.containsKey(strArray[i])) 
++(vectorSpace.get(strArray[i])[1]); 
else 
{ 
itemCountArray = new int[2]; 
itemCountArray[0] = 0; 
itemCountArray[1] = 1; 
vectorSpace.put(strArray[i], itemCountArray); 
} 
} 

//计算相似度 
double vector1Modulo = 0.00;//向量1的模 
double vector2Modulo = 0.00;//向量2的模 
double vectorProduct = 0.00; //向量积 
Iterator iter = vectorSpace.entrySet().iterator(); 

while(iter.hasNext()) 
{ 
Map.Entry entry = (Map.Entry)iter.next(); 
itemCountArray = (int[])entry.getValue(); 

vector1Modulo += itemCountArray[0]*itemCountArray[0]; 
vector2Modulo += itemCountArray[1]*itemCountArray[1]; 

vectorProduct += itemCountArray[0]*itemCountArray[1]; 
} 

vector1Modulo = Math.sqrt(vector1Modulo); 
vector2Modulo = Math.sqrt(vector2Modulo); 

//返回相似度 
return (vectorProduct/(vector1Modulo*vector2Modulo)); 
} 

/* 
* 
*/ 
public static void main(String args[]) 
{ 
String str1 = "gold silver truck"; 
String str2 = "Shipment of gold damaged in a fire"; 
String str3 = "Delivery of silver arrived in a silver truck"; 
String str4 = "Shipment of gold arrived in a truck"; 
String str5 = "gold gold gold gold gold gold"; 

System.out.println(SimilarDegreeByCos.getSimilarDegree(str1, str2)); 
System.out.println(SimilarDegreeByCos.getSimilarDegree(str1, str3)); 
System.out.println(SimilarDegreeByCos.getSimilarDegree(str1, str4)); 
System.out.println(SimilarDegreeByCos.getSimilarDegree(str1, str5)); 
} 
}

二、TF-IDF与余弦相似性的应用（二）：找出相似文章

本段转载自阮一峰

上一次，我用TF-IDF算法自动提取关键词。

【

TFIDF的主要思想是：如果某个词或短语在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。TFIDF实际上是：TF * IDF，TF词频(Term Frequency)，IDF逆向文件频率(Inverse Document Frequency)。TF表示词条在文档d中出现的频率。IDF的主要思想是：如果包含词条t的文档越少，也就是n越小，IDF越大，则说明词条t具有很好的类别区分能力。

】

今天，我们再来研究另一个相关的问题。有些时候，除了找到关键词，我们还希望找到与原文章相似的其他文章。比如，"Google新闻"在主新闻下方，还提供多条相似的新闻。

为了找出相似的文章，需要用到"余弦相似性"（cosine similiarity）。下面，我举一个例子来说明，什么是"余弦相似性"。

为了简单起见，我们先从句子着手。

　　句子A：我喜欢看电视，不喜欢看电影。

　　句子B：我不喜欢看电视，也不喜欢看电影。

请问怎样才能计算上面两句话的相似程度？

基本思路是：如果这两句话的用词越相似，它们的内容就应该越相似。因此，可以从词频入手，计算它们的相似程度。

第一步，分词。

　　句子A：我/喜欢/看/电视，不/喜欢/看/电影。

　　句子B：我/不/喜欢/看/电视，也/不/喜欢/看/电影。

第二步，列出所有的词。

　　我，喜欢，看，电视，电影，不，也。

第三步，计算词频。

　　句子A：我 1，喜欢 2，看 2，电视 1，电影 1，不 1，也 0。

　　句子B：我 1，喜欢 2，看 2，电视 1，电影 1，不 2，也 1。

第四步，写出词频向量。

　　句子A：[1, 2, 2, 1, 1, 1, 0]

　　句子B：[1, 2, 2, 1, 1, 2, 1]

到这里，问题就变成了如何计算这两个向量的相似程度。

我们可以把它们想象成空间中的两条线段，都是从原点（[0, 0, ...]）出发，指向不同的方向。两条线段之间形成一个夹角，如果夹角为0度，意味着方向相同、线段重合；如果夹角为90度，意味着形成直角，方向完全不相似；如果夹角为180度，意味着方向正好相反。因此，我们可以通过夹角的大小，来判断向量的相似程度。夹角越小，就代表越相似。

以二维空间为例，上图的a和b是两个向量，我们要计算它们的夹角θ。余弦定理告诉我们，可以用下面的公式求得：

假定a向量是[x1, y1]，b向量是[x2, y2]，那么可以将余弦定理改写成下面的形式：

数学家已经证明，余弦的这种计算方法对n维向量也成立。假定A和B是两个n维向量，A是 [A1, A2, ..., An] ，B是 [B1, B2, ..., Bn] ，则A与B的夹角θ的余弦等于：

使用这个公式，我们就可以得到，句子A与句子B的夹角的余弦。

余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相似，这就叫"余弦相似性"。所以，上面的句子A和句子B是很相似的，事实上它们的夹角大约为20.3度。

由此，我们就得到了"找出相似文章"的一种算法：

　　（1）使用TF-IDF算法，找出两篇文章的关键词；

　　（2）每篇文章各取出若干个关键词（比如20个），合并成一个集合，计算每篇文章对于这个集合中的词的词频（为了避免文章长度的差异，可以使用相对词频）；

　　（3）生成两篇文章各自的词频向量；

　　（4）计算两个向量的余弦相似度，值越大就表示越相似。

"余弦相似度"是一种非常有用的算法，只要是计算两个向量的相似程度，都可以采用它。

下一次，我想谈谈如何在词频统计的基础上，自动生成一篇文章的摘要。

（完）

基础知识《二》