数据挖掘与数据分析应用案例 数据挖掘算法实践基于Java的文本相似度(Levenshtein distance算法)计算.doc
版权申诉
9 浏览量
2024-06-30
21:22:19
上传
评论
收藏 97KB DOC 举报
1
xxx 大学信息与电气工程学院 2017－2018 学年第 2 学期
《数据挖掘(研)》课程论文
课程号：220121160-01
任课教师 xxx 成绩
论文题目：（可指定题目，也可说明题目范围。）
文本相似度(Levenshtein Distance 算法)
论文要求：（对论文题目、内容、行文、字数等作出判分规定。）
1、结合自己感兴趣的实际应用领域，自拟题目，并使用本学期
数据挖掘课程中所学习的基本数据分析和处理方法，包括数据预处
理、探索性分析、数据仓库、相似度计算、决策树分类、最近邻分
类、朴素贝叶斯分类、逻辑回归、支持向量机、神经网络、关联规
则、K-means 聚类、层次聚类和密度聚类等知识，对所解决的实际问
题从基本理论、数学原理、算法设计、数据描述和实验结果与分析
等角度展开描述。
2、要求论文结构清晰、语言通顺、图文并茂，字数不少于 5000
字。正文首行缩进 2 个汉字，多倍行距设置为 1.25，字体要求汉字
为宋体，英文为 Times New Roman，大小为小四。论文一定要亲自
撰写，自己动手设计算法和编写程序，如发现论文来自网上，或是
抄袭他人，按作弊处理，本门课程考核总成绩计 0 分。
3、上交论文电子版时每人提交一个文件夹，里面包含论文电子
版和程序文件夹；文件夹和论文电子版的命名格式统一为“学号-姓
名-班级-论文题目”。此外，必须上交论文的打印稿，并要与电子稿
的内容一致，不规范者将酌情扣分。
教师评语：
教师签字：
年 月 日
正文
文本相似度(Levenshtein Distance 算法)
1. 前言
在自然语言处理过程中，经常会涉及到如何度量两个文本之间的相似性，我们都
知道文本是一种高维的语义空间，如何对其进行抽象分解，从而能够站在数学角度去
量化其相似性。而有了文本之间相似性的度量方式，我们便可以利用划分法的
K-means、基于密度的 DBSCAN 或者是基于模型的概率方法进行文本之间的聚类分
析；另一方面，我们也可以利用文本之间的相似性对大规模语料进行去重预处理，或
者找寻某一实体名称的相关名称（模糊匹配）。而衡量两个字符串的相似性有很多种
方法，如最直接的利用 hashcode，以及经典的主题模型或者利用词向量将文本抽象为
向量表示，再通过特征向量之间的欧式距离或者皮尔森距离进行度量。
提到如何比较两个字符串，我们从最初编程开始就知道：字符串有字符构成，只
要比较比较两个字符串中每一个字符是否相等便知道两个字符串是否相等，或者更简
单一点将每一个字符串通过哈希函数映射为一个哈希值，然后进行比较。但是这种方
法有一个很明显的缺点，就是过于“硬”，对于相似性的度量其只有两种，0 不相似，
1 相似，哪怕两个字符串只有一个字符不相等也是不相似，这在 NLP 的很多情况是
无法使用的，所以下文我们就“软”的相似性的度量进行整理，而这些方法仅仅考虑了
两个文本的字面距离，无法考虑到文本内在的语义内容。
基于关键词的空间向量模型的算法，将用户的喜好以文档描述并转换成向量模型，
对商品也是这么处理，然后再通过计算商品文档和用户偏好文档的余弦相似度。文本
相似度计算在信息检索、数据挖掘、机器翻译、文档复制检测等领域有着广泛的应用。
比如舆论控制，我们假设你开发了一个微博网站，并且已经把世界上骂人的句子都已
经收录进了数据库，那么当一个用户发微博时会先跟骂人句子的数据库进行比较，如
果符合里面的句子就不让用户发出。通常情况下，很多工程师就会想到用 like 或者
where 的 sql 语法去查找。可是当情况更为复杂呢？数据库存放了“你是个坏人”，用
户要发“小明是个坏人”，这时应该怎么办呢？最简单的办法就是通过判断文本的相似
程度来决定用户发的内容是否是骂人的。本章节就几种简单的判断文本相似性的算法
来讲解，帮助大家更好的理解。
2. Levenshtein Distance 算法的介绍
Levenshtein Distance 算法原名叫编辑距离(Edit Distance)算法，最先是由俄罗斯科
学家 Vladimir Levenshtein 在 1965 年发明，用他的名字命名，又称 Levenshtein 距离。
是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包
括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
学 院 ____xxx 大 学 ____ 专 业 __ 计 算 机 科 学 与 技 术 __ 班 级 ___1501___ 本 专 学 号 __xxxxxxxxx___ 姓 名
___xxx____xxx_______
密封线 学生须将文字写在此线以下
资源评论
