采用TFIDF自动对文本进行形式化.doc

试验报告实验名称：采用TFIDF自动对文本进行形式化第1章 试验目的1加深对文本形式化的理解，掌握文本形式化的方法。2熟练掌握TFIDF算法，掌握如何计算权值（wij）。3在理解TFIDF算法基础下，编写程序实现该算法。4对某方面的文本运用该算法计算，并分析结果。第2章 试验的软硬件平台硬件配置：pc机系统软件：Windows 2000 sp4工具软件：Microsoft Visual Studio 6.0第3章 试验数据说明根据试验要求，本试验有两种输入数据。输入数据之一：面向某个领域的文本集。取自MIT-Principles of Data Mining.pdf的第5页至第24页，共计20页内容。每页内容作为一个文本，这样文本集中的文本数量为20。这20个文档存储在text目录下。文本命名： p00.txt，p01.txt,p19.txt。输入数据之二：文本形式的术语集。该术语集存储在text目录下vo.txt中，每行一个术语（词汇）。可自行编辑。输出数据：文本集的矩阵表示。程序运行当前目录下输出文本mm.txt。矩阵格式说明：文档编号 总词数词汇权值词出现次数文档频率文档编号0 661词汇A0.01601842词汇B0.0042142318文档编号1 713词汇A词汇B文档编号n 599词汇A词汇B（注：词出现次数词在该文档中出现次数，文档频率词在几篇文档中出现， 权值精确到小数点后六位。）第4章 试验内容一 、实验设计方案1、 算法及相关公式说明TFIDF（term frequency/inverse document frequency） 的概念被公认为信息检索中最重要的发明。在搜索、文献分类和其他相关领域有广泛的应用。IDF 的概念就是一个特定条件下、关键词的概率分布的交叉熵（Kullback-Leibler Divergence）TFIDF算法建立在这样假设之上的: 对区别文档最有意义的词语应该是那些在文档中出现频率高,而在整个文档集合的其他文档中出现频率少的词语, 所以如果特征空间坐标系取 TF词频作为测度, 就可以体现同类文本的特点。另外考虑到单词区别不同类别的能力, TFIDF法认为一个单词出现的文本频数越小,它区别不同类别文本的能力就越大。因此引入了逆文本频度 IDF的概念,以 TF和 IDF的乘积作为特征空间坐标系的取值测度, 并用它完成对权值 TF的调整, 调整权值的目的在于突出重要单词, 抑制次要单词。词频Term Frequency（tfij）：文档i中词汇j出现的频率。本试验中，某个文档中某词频的计算采用如下公式：tfij =词汇j在文档i中出现的次数/文档的总词数。需要说明的是，文档的总词数统计含重复出现的词汇，例如，本试验中“in Schools in America”总词数计为4。文档频率Document Frequency(dfj)：多少个文档包含词汇j。tfidf权值（wij）：wij = tfij * log(d/dfj) 其中d是文档的数目。本试验中文档数目为20，即d=20。本试验的算法实现并没有考虑词频的归一化处理。2、程序流程设计：二 、详细试验过程 1、程序设计实现 学习tfidf的相关知识，在此基础上理解公式，编写算法实现程序。程序计算文本集中所有出现的单词的tfidf权值Wij。在不输入术语集的情况下，输出所有单词的权值。在输入术语集的情况下，仅输出给定术语的权值。struct Ttreechar data20;double weight;double num; /一篇文献中的某一索引词出现的次数double max; /一篇文献的总词数double n; /索引词出现在几个文档中struct Ttree *lchild; /左儿子struct Ttree *rchild; /右儿子;数据结构：试验程序设计采用二叉树的链式存储作为文本集存储的数据结构。权值排序示例画树形图 权值从大到小依次为：左儿子节点节点右儿子节点主要函数：Ttree *createTtree(Ttree *root,FILE *fp) 创建二叉树用来存放单词，以及该词在文档中出现的次数/计算词频Ttree *SearchBinTtree(Ttree *rootx,Ttree *rooty) void InMidThread(Ttree *rooty,Ttree *rootx) 计算文档频率词在几篇文档中出现void InThread(Ttree *root,Ttree *Mroot) 计算权值void weight(Ttree *root) 对权值进行排序，二叉树节点插入过程bool in(char data20) 判断某词是否在词汇集中void ThreadWeight(Ttree *root) 权值输出，从大到小顺序2、输入术语集的选取针对本试验的输入数据，20个文本均来自于MIT-Principles of Data Mining.pdf，我们可以知道这20个文本应该属于数据挖掘类，可初步判断文档必然具有一定的相似性，即都与数据挖掘有关。因此，我们对术语集的选取也从能否表现文档的类特征角度出发。第一步，我们不设定术语集（删除textvo.txt），即按照程序设计想法对每个文本的所有词汇依次输出权值。观察并记录试验输出结果。第二步，我们选取WEIGHT、 degree和behavior这三个术语作为术语集，这三个术语在20个文本中的出现频度并没有普遍规律。如，weight这个词只出现在文本16和文本17中，它的在数据挖掘类的某些文本内容中出现较为频繁，但并不是在所有文本中普遍出现。除weight外，其它两个术语与数据挖掘关系不大。观察并记录试验输出结果。 第三步，我们选取WEIGHT 、data 和Mining 作为术语集。我们估计data 和Mining在这20个文本中出现的频率应当较高。观察并记录试验输出结果。三 、数据记录记录1 不输入术语集(删除textvo.txt)，输出所有词汇的值。（下面是文档0(p00.txt)部分结果数据，其它文档略。） 总词数 词汇 权值 词出现次数 文档频率第0篇文档 661 book 0.013934 4 2 computational 0.013596 3 1 material 0.013596 3 1 own 0.013596 3 1 reader 0.013596 3 1 tools 0.011480 4 3 authors 0.009064 2 1 exciting 0.009064 2 1 thank 0.009064 2 1 introduction 0.006967 2 2 viewpoint 0.006967 2 2 statisticians 0.006292 3 5 statistical 0.006040 5 9 text 0.006040 5 9 algorithmic 0.005740 2 3 familiar 0.005740 2 3 go 0.005740 2 3 texts 0.005740 2 3 work 0.005740 2 3 like 0.005464 3 6 acknowledge 0.004532 1 1 acquisition 0.004532 1 1 adams 0.004532 1 1 assisting 0.004532 1 1 benton 0.004532 1 1blame 0.004532 1 1 example 0.000288 4 19 such 0.000288 4 19 have 0.000216 3 19 which 0.000216 3 19 with 0.000216 3 19 a 0.000000 16 20 and 0.000000 11 20 by 0.000000 2 20 for 0.000000 9 20 in 0.000000 20 20 is 0.000000 11 20 of 0.000000 24 20 that 0.000000 10 20 this 0.000000 9 20 to 0.000000 27 20 will 0.000000 1 20记录2 vo.txt中术语集（词汇集）为： 总词数 词汇 权值 词出现次数 文档频率第0篇文档 661第1篇文档 713第2篇文档 573第3篇文档 414第4篇文档 547第5篇文档 655第6篇文档 293第7篇文档 720 behavior 0.005270 2 3第8篇文档 497第9篇文档 599 behavior 0.009501 3 3 degree 0.003844 1 2第10篇文档 553第11篇文档 659第12篇文档 736第13篇文档 770第14篇文档 790 degree 0.002915 1 2第15篇文档 611第16篇文档 575 weight 0.016018 4 2第17篇文档 746 weight 0.043212 14 2第18篇文档 745第19篇文档 576 behavior 0.003294 1 3WEIGHTdegreebehavior右侧为输出结果：记录3 vo.txt中术语集（词汇集）为： 总词数 词汇 权值 词出现次数 文档频率第0篇文档 661 mining 0.003038 9 16 data 0.002550 16 18第1篇文档 713 data 0.005172 35 18 mining 0.003756 12 16第2篇文档 573 data 0.004781 26 18 mining 0.003115 8 16第3篇文档 414 data 0.002799 11 18第4篇文档 547 data 0.003274 17 18 mining 0.000816 2 16第5篇文档 655 data 0.002735 17 18 mining 0.001022 3 16第6篇文档 293 data 0.001438 4 18第7篇文档 720 data 0.001902 13 18 mining 0.001240 4 16第8篇文档 497 data 0.001696 8 18第9篇文档 599 mining 0.001118 3 16 data 0.000704 4 18第10篇文档 553 data 0.002477 13 18 mining 0.001614 4 16第11篇文档 659 data 0.002878 18 18 mining 0.000339 1 16第12篇文档 736 data 0.005869 41 18 mining 0.004245 14 16第13篇文档 770 data 0.003421 25 18 mining 0.000580 2 16第14篇文档 790 data 0.003734 28 18 mining 0.001130 4 16第15篇文档 611 mining 0.005478 15 16 data 0.005173 30 18第16篇文档 575 weight 0.016018 4 2 data 0.004214 23 18 mining 0.001940 5 16第17篇文档 746 weight 0.043212 14 2第18篇文档 745 mining 0.000300 1 16第19篇文档 576 data 0.000915 5 18 mining 0.000387 1 16WEIGHTdataMining右侧为输出结果：第5章 试验数据分析我们得到得权值总的来说较小（如，最大也只有0.04*），是因为我们在计算tfij时没有进行归一化处理。而直接用公式tfij =词汇j在文档i中出现的次数/文档的总词数。下面的分析中“大”和“小”均是在我们得到得权值范围内的相对说法。对数据记录一，因为没有输入特定的术语集，程序输出文本中出现的所有词汇的权值。我们只分析文本0（p00.txt）数据，其它类似。该文本中总词数为661。我们采用的tfidf公式在计算tf值时要用到总词数这个值。首先，我们观察权值最高的10个词汇，它们词出现次数分别是4、3、3、3、3、4、2，它们的文档频率分别是2、1、1、1、1、3。从这10个词汇的相关数据，我们可以粗略看出，它们的词频较高，且文档频率较低。按照tfidf公式 wij = tfij * log(d/dfj) 在文档（文本）数目一定的情况下，dfj值较小，则idfj=(d/dfj)必然较大，加之词频tfij值也较高，故二者乘积必然较大，即tfidf权值较大。上面的分析说明了我们得到的程序输出结果符合tfidf公式。 权值 词出现次数 文档频率 are 0.000388 5 19 with 0.000388 5 19 one 0.000338 1 16 so 0.000338 1 16 may 0.000246 1 17 example 0.000233 3 19 which 0.000233 3 19 some 0.000159 1 18 from 0.000155 2 19 or 0.000155 2 19 such 0.000155 2 19 have 0.000078 1 19 a 0.000000 11 20 and 0.000000 26 20 by 0.000000 3 20 for 0.000000 13 20 in 0.000000 19 20 is 0.000000 9 20 of 0.000000 23 20 that 0.000000 6 20 this 0.000000 10 20 to 0.000000 16 20 will 0.000000 5 20其次，我们观察权值最低的一些词汇，如下面的文本框中所示数据。按照tfidf公式，我们可以估计，若文档频率dfj值较大，接近文档数目d的值，log(d/dfj)必然接近于0,虽然词频较大，tfi-df权值仍然会比较小。数据中词汇are、with、都说明了这一情形。我也可以根据tfidf公式若词频tfij接近于0，即使文档频率不十分高，tfidf权值仍然会比较小。数据中词汇one、so、may都说明了这一情形。另外我们也可以看出，权值最低的这些词汇都是英文中十分常见，出现频率也较高的词。因此它们不能用来说明文档的特征。Tfidf算法用权值来刻画词语在描述文本内容时所起作用的重要程度。这些词汇的权值也验证了Tfidf算法的这一特性，至少说明了权值低的词汇在描述文本内容时几乎不起作用。对数据记录二，术语分别为WEIGHT degree和behavior。weight这个词只出现在文本16（p16.txt）和文本17(p17.txt)中，在这两个文档中其tfidf权值0.043212和0.016018很高，说明它在描述文本内容时起到重要作用。这与我们选取WEIGHT作为术语的初衷相吻合。degree和behavior在描述数据挖掘