文本相似度——基于TF-IDF与余弦相似性

2018-01-13 11:14:07来源:oschina作者:刘太刚人点击

分享

本篇博客,主要是描述一种计算文本相似度的算法,基于TF-IDF算法和余弦相似性。算法的描述请务必看阮一峰的博客,不然看不懂本篇博客,地址:


http://www.ruanyifeng.com/blog/2013/03/tf-idf.html


http://www.ruanyifeng.com/blog/2013/03/cosine_similarity.html


在这里,主要讨论具体的代码的实现。过程如下:

使用TF-IDF算法,找出两篇文章的关键词;
每篇文章各取出若干个关键词(比如20个),合并成一个集合,计算每篇文章对于这个集合中的词的词频(为了避免文章长度的差异,可以使用相对词频);
生成两篇文章各自的词频向量;
计算两个向量的余弦相似度,值越大就表示越相似。

首先,请看此算法代码的文件结构:


文件结构图


接下来,是算法的实现步骤:


第一步:使用TF-IDF算法,找出两篇文章的关键词
/**
* (1)使用TF-IDF算法,找出两篇文章的关键词;
*
* @param uri
* 待比较的文本的路径
* @return 文本被分词后,词的ELementSet集合
* @throws IOException
*/
private static ElementSet getKeyTerms(String uri) throws IOException {
// 分词后,获得ElementMap集合
ElementMap em = null;
String text = Utils.readText(uri);
em = Utils.tokenizer(text);
ElementSet es = em.getElementSetOrderbyTf();
// 计算tf、idf和tf_idf的值
Double de = (double) ConnectKit.countTatolFromTerm("的")+1;
for (Element e : es.getElementSet()) {
// 计算tf
Double tf = e.getTf() / es.getElementSet().size();
e.setTf(tf);
// 计算idf
Double num = (double) ConnectKit.countTatolFromTerm(e.getTerm());
Double idf = Math.log10(de / (num+1));
e.setIdf(idf);
// 计算tf_idf
Double tf_idf = tf * idf;
e.setTf_idf(tf_idf);
}
// 将排序的依据更改为tf_idf
es.orderbyTf_idf();
System.out.println("第一步:计算词的tf、idf和tf_idf");
for (Element e : es.getElementSet()) {
System.out.println(e.getTerm() + "---tf:" + e.getTf() + "---idf:" + e.getIdf() + "---tf_idf:" + e.getTf_idf());
}
return es;
}

其中的ElementSet和ElementMap是自己封装的集合类(没有继承任何一个集合),分别使用Set和Map作为其属性,并提供两者相互转换的方法。


第二步:每篇文章各取出若干个关键词(比如20个),合并成一个集合,计算每篇文章对于这个集合中的词的词频(为了避免文章长度的差异,可以使用相对词频)
&
第三步:生成两篇文章各自的词频向量
/**
* (2)每篇文章各取出若干个关键词(比如20个),合并成一个集合,
* 计算每篇文章对于这个集合中的词的词频(为了避免文章长度的差异,可以使用相对词频); (3)生成两篇文章各自的词频向量;
*
* @param es01
* 词的ElementSet的集合
* @param es02
* 词的ElementSet的集合
* @param percent
* 需要用于的计算的词百分比(相对于所有的词)
* @return Vectors
*/
private static Vectors getVectors(ElementSet es01, ElementSet es02, int percent) {
// (2)每篇文章各取出若干个关键词(比如20个),合并成一个集合,
// 计算每篇文章对于这个集合中的词的词频(为了避免文章长度的差异,可以使用相对词频);
percent = Math.abs(percent);
if (percent > 100)
percent %= 100;
int num01 = Math.round(es01.getSize() * ((float) percent / 100));
int num02 = Math.round(es02.getSize() * ((float) percent / 100));
if (num01 == 0)
num01 = 1;
if (num02 == 0)
num02 = 1;
HashSet hs = new HashSet();
Iterator it01 = es01.getElementSet().iterator();
for (int i = 0; i < num01; i++) {
if (it01.hasNext()) {
hs.add(it01.next().getTerm());
}
}
Iterator it02 = es02.getElementSet().iterator();
for (int i = 0; i < num02; i++) {
if (it02.hasNext()) {
hs.add(it02.next().getTerm());
}
}
// (3)生成两篇文章各自的词频向量;
ElementMap em01 = es01.getElementMap();
ElementMap em02 = es02.getElementMap();
List vector01 = new ArrayList();
List vector02 = new ArrayList();
for (String term : hs) {
if (em01.getElementMap().containsKey(term)) {
vector01.add(em01.getDataByTerm(term).getTf());
} else {
vector01.add(0D);
}
if (em02.getElementMap().containsKey(term)) {
vector02.add(em02.getDataByTerm(term).getTf());
} else {
vector02.add(0D);
}
}
System.out.println();
System.out.println("第二步:分别提取若干个关键字,并分别计算两篇文章的词频向量");
for (Double d : vector01) {
System.out.print(d + ",");
}
System.out.println();
for (Double d : vector02) {
System.out.print(d + ",");
}
System.out.println();
System.out.println();
return new Vectors(vector01, vector02);
}

其中,Vectors的属性是两个向量。


第四步:计算两个向量的余弦相似度,值越大就表示越相似。
/**
* 计算余弦相似度
*
* @param vs
* Vectors的实现
* @return 余弦相似度的值
*/
private static Double getCosSimilarty(Vectors vs) {
List list1 = vs.getVector01();
List list2 = vs.getVector02();
Double countScores = 0D;
Double element = 0D;
Double denominator1 = 0D;
Double denominator2 = 0D;
int index = -1;
for (Double it : list1) {
index++;
Double left = it.doubleValue();
Double right = list2.get(index).doubleValue();
element += left * right;
denominator1 += left * left;
denominator2 += right * right;
}
try {
countScores = element / Math.sqrt(denominator1 * denominator2);
} catch (ArithmeticException e) {
e.printStackTrace();
}
return countScores;
}

到此,算法就结束了,但是还有两个重要的点需要提一下,就是如何计算idf值和分词:


如何获取idf值:
/**
*
* @param url 访问的地址
* @return 访问的返回值
* @throws MalformedURLException
* @throws IOException
*/
private static Long getTatolFromUrl(String url) throws MalformedURLException, IOException {
InputStream instream = null;
BufferedReader rd = null;
Long tatol = -1L;
try {
instream = new URL(url).openStream();
rd = new BufferedReader(new InputStreamReader(instream, Charset.forName("UTF-8")));
//使用正则匹配,从网页中获取搜索数信息
Pattern pattern = Pattern.compile("百度为您找到相关结果约[0-9-,]+个");
String s;
while ((s = rd.readLine()) != null) {
Matcher matcher = pattern.matcher(s);
if (matcher.find()) {
Pattern p = Pattern.compile("[0-9-,]+");
Matcher m = p.matcher(matcher.group());
if (m.find()) {
String str = m.group().replace(",", "");
tatol = Long.valueOf(str);
break;
}
}
}
} finally {
instream.close();
rd.close();
}
return tatol;
}
public static Long countTatolFromTerm(String term) throws IOException {
int i = 0;
while(true){
//因为有时访问的内容是错误的,所以要多次访问,以得到正确的结果,但是如果重复的次数过多的话,退出进程
if((i++)==100){
System.out.println("访问百度失败!!");
System.exit(0);
};
//拼接访问百度的URL
Long answer = getTatolFromUrl("http://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=0&rsv_idx=1&tn=baidu&wd=" + term);
if(answer != -1){
return answer;
}
}
}

类似与爬虫程序,但是只是获取搜索数。你也许会问,为什么idf要这么计算,请看下图,注意观察,词的搜索数和idf值之间的关系:



可见,但搜索量变少后,idf值会急剧增大,这样可以筛选出关键词。当然,这样的访问网络的操作,是很耗时的。


如何分词:
/**
* 将传入的文本进行分词,然后词(单个字要被过滤掉)放入ElementMap中
* @param text 需要分词的文本
* @return 分好词的ElementMap集合
* @throws IOException
*/
public static ElementMap tokenizer(String text) throws IOException {
Map map = new TreeMap();
IKAnalyzer analyzer = new IKAnalyzer();
analyzer.setUseSmart(true);
TokenStream stream = null;
try {
stream = analyzer.tokenStream("", new StringReader(text));
stream.reset();
while (stream.incrementToken()) {
CharTermAttribute charTermAttribute = stream.getAttribute(CharTermAttribute.class);
String term = charTermAttribute.toString();
if (term.length() > 1) {
Data data = new Data();
data.setTf(1D);
boolean isContainsKey = map.containsKey(term);
if (isContainsKey) {
Data temp = map.get(term);
data.setTf(temp.getTf() + 1D);
map.replace(term, temp, data);
}
map.put(term, data);
}
}
} finally {
stream.close();
analyzer.close();
}
ElementMap em = new ElementMap(map);

if(em.getElementMap().isEmpty()){
throw new NullPointerException();
}
return em;
}

分词这部分可能很少接触,这部分需要两个jar包,在lib文件中,还可参考博客:


https://www.cnblogs.com/lyssym/p/4880896.html


本程序的部分代码也是出自这篇博客。


到这里,本篇博客结束,但是要强调一点,这个算法并不能用在实际的生产中,因为搜索数是从网络获取的,是一个很耗时的过程。本算法会进一步修改的,源码地址(码云):


https://gitee.com/liutaigang/cosineSimilarty.git


通过git获取。


end

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台