毕业设计（论文）专用纸
第二章 系统原理介绍
2.1原理概述
本系统是基于向量空间模型（VSM）来设计的。我们将一篇文档都看成一个向量，每个词作为向量的一个维度，而词的频率看成其值（有向），即向量，这样每篇文章的词及其频率就构成了一个i维空间图，两个文档的相似度就是两个空间图的接近程度，即它们之间夹角的大小，我们通过计算余弦系数来体现。计算机不会像人一样自动识别文档里的每个词，所以要对文档进行分词处理，然后统计词频，最后根据余弦系数计算公式得出相似度比较结果。
2.2系统相关知识点简介 2.2.1向量空间模型
VSM模型（VSM：Vector Space Model）即向量空间模型，由Salton等人于20世纪70年代提出，并成功地应用于著名的SMART文本检索系统。
向量空间模型的基本思想为将文本简化为特征向量表示，将相似度计算问题简化为空间向量的运算，由此使得问题的复杂性大大降低。该方法根据文本中的词语将文本映射为n维空间向量，通过计算空间向量的余弦值来确定文本的相似度，即利用空间的相似性来解决文本上的相似性，直观易懂。通过向量空间模型，文本数据就转换成了计算机可以处理的结构化数据，两个文档之间的相似性问题转变成了两个向量之间的相似性问题。
我们可以这样来理解一下向量空间模型。对于每篇文档来说，它都是由很多词条组成的。对此，我们可以对文档（Document）和其所包含的词条（Term）之间的关系进行一个研究。我们可以将一篇文档看成一个向量D（term1,term2,??,termn）。这样，假设某两篇文档中都出现了term1和term2，就可以用一个二维的坐标来表示文档和词条之间的关系，如图2-1所示。
从图中可看出，文档1中Term1共出现3次，Term2出现1次；而文档2中Term2出现3次，Term1出现1次。所以，可以用向量D1（3,1）、D2（1,3）来表示这两篇文档。以此类推，一个搜索引擎的索引库，可以看成是一个由词条组成的N维向量空间。每一篇文档均为其中的一个向量。在这种情况下，文档之间就出现了特定的关系。例如，当两篇文档内容相近时，它们的词条也就差不多。因此，从逻辑上看，它们可能就会在这个向量空间中处于一种很“接近”的位置。此时，“接近”真实含义指的是这两个向量之间的夹
10
毕业设计（论文）专用纸
角比较小。
Term1
文档1
文档2
2.2.2中文分词技术
众所周知，中文是世界上最复杂的语言之一。那么要对文本进行相似度计算，首先就要进行分词处理。分词，即将一段文本拆分成多个词。现有的分词方式主要有单字分词、二分法、词典分词。
单字分词，顾名思义即在对中文文本进行分词时，以字为单位进行切分。按这种方式建立索引，则索引中所有的词条的集合就是中文汉字库的一个子集合。字索引比较灵活，但需要复杂的单字匹配算法，以及大量的CPU运算。
二分法，即将每两个字当作一个词语进行切分，然后建立索引。它明显的减少了每个词条后位置信息的长度。如Lucene的CJKAnalyzer就是对中文采取二分的方式进行分词。
本系统采用IK Analyzer分词器进行分词，也相当于使用词典分词，是目前来讲分词比较准确的一种方法，即通过构造一个常用词词典来对遇到的文本进行词语的切分。中国科学院计算技术所研究的ICTCLAS在中文分词领域是较为先进的分词系统，其分词词典也是世界公认的精准。
使用词典分词法在文本中匹配单词时用到一些常用的算法：
正向最大匹配算法：从左到右将待分词文本中的几个连续字符与词库匹配，如果匹配上，则切分出一个词。
逆向最大匹配算法：从被处理文档的末端开始匹配扫描，每次取最末端的2i个字符（i字字串）作为匹配字段，若匹配失败，则去掉匹配字段最前面的一个字，继续匹配。其采用的分词词典是逆序词典，对文档进行处理时先要进行倒排处理，生成逆序文档。
有的时候，需多种方式对文本进行切分，当它们切分的结果相同，表示这个词就是真正需要的词。
11
Term2
图2-1 文档和词条的向量空间
毕业设计（论文）专用纸
2.2.3TF统计方法
TF的全称Term Frequency，也就是词条频率。用数学方法来描述即某个词语出现的次数除以该文档中的词条总数。常用于情报检索与文本挖掘，用以评估一个词对于一个文档的重要程度。
如今在信息科学领域，比较经典的词频统计方法有基于匹配的词频统计算法和基于树结构的词频统计算法。
对于单关键词匹配算法国内外都有了深入的研究，比较著名的匹配算法有BF(Brute Force)算法、KMP(Knuth-Morris-Pratt)算法、BM(Boyer-Moore)算法等。
(1)BF算法
BF算法亦称蛮力算法。其基本思想是：首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则T向右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k+1?k+M]=T[1?M]，则匹配成功；否则失败。
(2)KMP算法
KMP算法是由高德纳（Donald Ervin Knuth）和 Vaughan Pratt 在1977年合作发明的。其基本思想为：假设在模式匹配的进程中，执行T[i]和W[j]的匹配检查。若T[i]=W[j]，则继续检查T[i+1]和W[j+1]是否匹配。若T[i]<>W[j]，则分成两种情况：若j=1，则模式串右移一位，检查T[i+1]和W[1]是否匹配；若1 (3)BM算法 BM算法由Bob Boyer 和J Strother Moore在1977年提出，它是一个非常有效的字符串匹配算法。它的基本思想是：假设将主串中自位置i起往左的一个子串与模式进行从右到左的匹配过程中，若发现不匹配，则下次应从主串的i + dist(si)位置开始重新进行新一轮的匹配，其效果相当于把模式和主串向右滑过一段距离distance（si），即跳过distance（si）个字符而无需进行比较。 基于匹配的词频统计方法，不可避免的是要对待处理的文档进行多次扫描。当待处理文档数据量比较大时，这无疑是要付出更高的时间和空间代价。针对这个问题，有学者又提出了基于树结构的词频统计算法。 其基本思想是：首先根据已有的关键词集合构建一棵查找树，然后利用这个查找树对文档进行扫描，从而进行关键词的统计。进行词频统计时，非常好的是每当从文档中读取一个词与查找树比较时，只需对文档扫描一遍，则可统计出所有关键词的信息。这种方法减少了一些不必要的匹配过程，大大提高了统计效率。 12 毕业设计（论文）专用纸 2.2.4TF-IDF算法 2.2.4.1TF-IDF简介 TF-IDF（term frequency–inverse document frequency）是一种用于资讯检索与资讯探勘的常用加权技术。TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。TF-IDF加权的各种形式常被搜寻引擎应用，作为文件与用户查询之间相关程度的度量或评级。除了TF-IDF以外，因特网上的搜寻引擎还会使用基于连结分析的评级方法，以确定文件在搜寻结果中出现的顺序。 在一份给定的文件里，词频 (term frequency，TF) 指的是某一个给定的词语在该文件中出现的次数。这个数字通常会被归一化（分子一般小于分母 区别于IDF），以防止它偏向长的文件。（同一个词语在长文件里可能会比短文件有更高的词频，而不管该词语重要与否。） 逆向文件频率 (inverse document frequency，IDF) 是一个词语普遍重要性的度量。某一特定词语的IDF，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到。 某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词语，保留重要的词语。 2.2.4.2TF-IDF主要思想 如果某个词或短语在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。TFIDF实际上是：TF * IDF，TF词频(Term Frequency)，IDF反文档频率(Inverse Document Frequency)。TF表示词条在文档d中出现的频率（另一说：TF词频(Term Frequency)指的是某一个给定的词语在该文件中出现的次数）。IDF的主要思想是：如果包含词条t的文档越少，也就是n越小，IDF越大，则说明词条t具有很好的类别区分能力。如果某一类文档C中包含词条t的文档数为m，而其它类包含t的文档总数为k，显然所有包含t的文档数n=m+k，当m大的时候，n也大，按照IDF公式得到的IDF的值会小，就说明该词条t类别区分能力不强。（另一说：IDF反文档频率(Inverse Document Frequency)是指果包含词条的文档越少，IDF越大，则说明词条具有很好的类别区分能力。）但是实际上，如果一个词条在一个类的文档中频繁出现，则说明该词条能够很好代表这个类的文本的特征，这样的词条应该给它们赋予较高的权重，并选来作为该类文本的特征词以区别与其它类文档。这就是IDF的不足之处. 在一份给定的文件里，词频（term frequency，TF）指的是某一个给定的词语在该文 13 毕业设计（论文）专用纸 件中出现的频率。这个数字是对词数(term count)的归一化，以防止它偏向长的文件。（同一个词语在长文件里可能会比短文件有更高的词数，而不管该词语重要与否。）对于在某一特定文件里的词语来说，它的重要性可表示为： 以上式子中 出现次数之和。 逆向文件频率（inverse document frequency，IDF）是一个词语普遍重要性的度量。某一特定词语的IDF，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到： 其中|D|：语料库中的文件总数 ：包含词语的文件数目（即 的文件数目）如果该词语不在语料 库中，就会导致被除数为零，因此一般情况下使用 然后 某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词语，保留重要的词语。 是该词在文件 中的出现次数，而分母则是在文件 中所有字词的 2.2.4.3TF-IDF算法示例 有很多不同的数学公式可以用来计算TF-IDF。这边的例子以上述的数学公式来计算。词频 (TF) 是一词语出现的次数除以该文件的总词语数。假如一篇文件的总词语数是100个，而词语“母牛”出现了3次，那么“母牛”一词在该文件中的词频就是3/100=0.03。一个计算文件频率 (DF) 的方法是测定有多少份文件出现过“母牛”一词，然后除以文件集里包含的文件总数。所以，如果“母牛”一词在1,000份文件出现过，而文件总数是10,000,000份的话，其逆向文件频率就是 log(10,000,000 / 1,000)=4。最后的TF-IDF的分数为0.03 * 4=0.12。 根据关键字k1,k2,k3进行搜索结果的相关性就变成TF1*IDF1 + TF2*IDF2 + TF3*IDF3。比如document1的term总量为1000，k1,k2,k3在document1出现的次数是100，200，50。包含了 k1，k2，k3的docuement总量分别是 1000，10000，5000。document set的总量为10000。 TF1 = 100/1000 = 0.1 TF2 = 200/1000 = 0.2 TF3 = 50/1000 = 0.05 IDF1 = log(10000/1000) = log(10) = 2.3 IDF2 = log(10000/100000) = log(1) = 0； IDF3 = log(10000/5000) = log(2) = 0.69 这样关键字k1,k2,k3与docuement1的相关性= 0.1*2.3 + 0.2*0 + 0.05*0.69 = 0.2645 其中k1比k3的比重在document1要大，k2的比重是0. 14