文档章节

搜索:文本的匹配算法

alexqdjay
 alexqdjay
发布于 2017/04/08 00:53
字数 1277
阅读 198
收藏 1

搜索即找到跟搜索词句很相似的文本,例如在百度中搜索"人的名",结果如下

那么怎么评价两个文本之间的相似度呢?

余弦相似度  (cosine similiarity)

本文介绍基于VSM (Vector Space Model) 的 余弦相似度 算法来评价两个文本间的相识度。

余弦相似度,又称为余弦相似性。通过计算两个向量的夹角余弦值来评估他们的相似度。 -- 百度百科

两个空间向量之间的夹角越小,我们就认为这两个向量越吻合,cosθ 越大,当完全重合时 cosθ = 1

由余弦定律可知:(原谅我百度盗的公式图)

展开, 假设是n个维度一般化公式如下:

公式已经有了,我们需要将文本转化成可以计算的数据。

那么怎么把文本转化成向量呢?

文本向量化

使用词袋one-hot的方式,就是形成一个词的字典集,然后将文本中的词投射到词袋中,对应的位置用出现的频次填充,没有的填充零,例如有这么个词袋:

0 苹果
1 手机
2 魅族
3 非常
4 好用
5 美观
6 完美
7 小米
8 平板
9 薄

每个词前面的数字表示序号(索引)

有四句话

A:苹果/手机/非常/美观
B:苹果/手机/非常/好用
C:小米/手机/非常/好用
D: 魅族/平板/非常/好用

转化为向量

A: [1, 1, 0, 1, 0, 1, 0, 0, 0, 0]
B: [1, 1, 0, 1, 1, 0, 0, 0, 0, 0]
C: [0, 1, 0, 1, 1, 0, 0, 1, 0, 0]
D: [0, 0, 1, 1, 1, 0, 0, 0, 1, 0]

 转化完成,代入上面的公式计算:

B & A = 3/4 = 0.75
B & C = 3/4 = 0.75
B & D = 2/4 = 0.5

从结果上看B跟AC都比较接近,但是跟D就相差很大。

但是,当你搜索B “苹果手机非常好用” 时,你可能更希望看到其他有关 “苹果手机” 的信息,因为这里的关键字是 “苹果”,那么怎么样才能把一些关键字的比重提高呢?换句话说怎么样把一些关键字识别出来进行重点关注。

TF-IDF算法

TF-IDF(term frequency–inverse document frequency)是一种用于信息检索与数据挖掘的常用加权技术。 -- 还是百度百科

TF: 一个词在文档中出现的频率 = 该词出现次数/文档中总词数
IDF:log((文档库中总文档数+1)/(出现该词的文档数 + 1))

TF描述的是一个词跟文档的相关度,一个文档中出现某个词越多说明该文档的主题跟该词有很大的关系;

IDF描述一个词的个性度(重要性),如果一个词在很多文档中出现说明该词是个“大众面”,如一大堆词都是一些公司名称,这时你说出两个字能非常好地定位到你需要的公司名字,那么你就要挑那个公司名字中核心的、独一无二的字,假如你挑 “公司” 这两个字那么等于没说,因为99%的名字中都含有 “公司” 两个字。

IDF原理来自【信息论】中 信息熵  (可以点击查看我另一篇关于 信息熵 的博客)

TF与IDF相乘以后得到的值为 TF-IDF,是衡量一个词对该文档的重要程度,该值越大表示重要性越大。

将上面的例子使用TF-IDF值作为向量的权重,取代之前的频次。

词袋IDF

0 苹果 2 IDF=0.737
1 手机 3 IDF=0.3219
2 魅族 1 IDF=1.3219
3 非常 4 IDF=0
4 好用 3 IDF=0.3219
5 美观 1 IDF=1.3219
6 完美 0 IDF=2.3219
7 小米 1 IDF=1.3219
8 平板 1 IDF=1.3219
9 薄   1 IDF=1.3219

向量

A: [0.737, 0.3219, 0,      0, 0,      1.3219, 0, 0,      0,      0     ]
B: [0.737, 0.3219, 0,      0, 0.3219, 0,      0, 0,      0,      0     ]
C: [0,     0.3219, 0,      0, 0.3219, 0,      0, 1.3219, 0,      0     ]
D: [0,     0,      1.3219, 0, 0.3219, 0,      0, 0,      1.3219, 0     ]

计算结果

B & A = 0.64678861/(1.547*0.866) = 0.48
B & C = 0.20723922/(0.866*1.398) = 0.17
B & D = 0.10361961/(0.866*1.90) = 0.06

这样,B和A的相似得分最高,非常好地满足了我们的需求。

当然在实际使用时需要调整下计算公式,如加入词权重,文档权重等,还可以根据词出现的位置给予不一样的权重分值。

TF-IDF优点是计算比较快,有比较好的理论推导基础可信度非常高。

余弦相似度在实际使用时可以加入些优化使得计算更快,譬如预先计算好各个文档的 |d|,因为该值在文档形成时就已经确定,向量点乘计算时直接将两个向量的非零项相乘然后求和,不用挨个计算,因为实际中绝大多数项是零而且项数非常大,所以既耗时又白费。

下一篇准备写Lucene是怎么应用这个算法做搜索匹配的

© 著作权归作者所有

alexqdjay
粉丝 35
博文 26
码字总数 31560
作品 0
浦东
高级程序员
私信 提问
MatcherDroid-类正则表达式匹配自动机,更高效率,更好中文支持

What’s MatcherDroid 因为不爽正则表达式复杂的语法,较低的中文支持度,不是很好的效率,所以自己写了一个类正则表达式的自动匹配/提取机。目前测试来看,MatcherDroid相较于正则表达式,有...

王下邀月熊
2013/11/30
288
1
双数组字典树关键词查询匹配和替换

大家在进行关键词匹配和替换的时候都是用的什么算法?很多人都可能有这样的需求,比如聊天文本中的敏感词替换、html文本中的关键词加超链接等。不深入技术算法和时刻关注程序性能的人来说,就...

银杏果果
2016/12/24
317
1
正则表达式太慢?这里有一个提速100倍的方案(附代码)

     作者:Vikash Singh   编译:肖依月、吴双、钱天培   “当遇到一个文本处理问题时,如果你在第一时间想到了正则表达式,那么恭喜你,你的问题从一个变成了俩!“   如果你曾参...

大数据文摘
2017/12/14
0
0
数据结构与算法JavaScript (五) 串(经典KMP算法)

KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右...

文艺小青年
2017/06/01
0
0
Flashtext:大规模数据清洗的利器

在这篇文章中,我们将介绍一种新的关键字搜索和替换的算法:Flashtext 算法。Flashtext 算法是一个高效的字符搜索和替换算法。该算法的时间复杂度不依赖于搜索或替换的字符的数量。比如,对于...

chen_h
2017/11/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

代理模式之JDK动态代理 — “JDK Dynamic Proxy“

动态代理的原理是什么? 所谓的动态代理,他是一个代理机制,代理机制可以看作是对调用目标的一个包装,这样我们对目标代码的调用不是直接发生的,而是通过代理完成,通过代理可以有效的让调...

code-ortaerc
59分钟前
4
0
学习记录(day05-标签操作、属性绑定、语句控制、数据绑定、事件绑定、案例用户登录)

[TOC] 1.1.1标签操作v-text&v-html v-text:会把data中绑定的数据值原样输出。 v-html:会把data中值输出,且会自动解析html代码 <!--可以将指定的内容显示到标签体中--><标签 v-text=""></......

庭前云落
今天
7
0
VMware vSphere的两种RDM磁盘

在VMware vSphere vCenter中创建虚拟机时,可以添加一种叫RDM的磁盘。 RDM - Raw Device Mapping,原始设备映射,那么,RDM磁盘是不是就可以称作为“原始设备映射磁盘”呢?这也是一种可以热...

大别阿郎
今天
10
0
【AngularJS学习笔记】02 小杂烩及学习总结

本文转载于:专业的前端网站☞【AngularJS学习笔记】02 小杂烩及学习总结 表格示例 <div ng-app="myApp" ng-controller="customersCtrl"> <table> <tr ng-repeat="x in names | orderBy ......

前端老手
昨天
14
0
Linux 内核的五大创新

在科技行业,创新这个词几乎和革命一样到处泛滥,所以很难将那些夸张的东西与真正令人振奋的东西区分开来。Linux内核被称为创新,但它又被称为现代计算中最大的奇迹,一个微观世界中的庞然大...

阮鹏
昨天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部