毕业论文-基于关键词提取的TFIDF和TextRank方法的对比研究.docx

基于关键词提取的TFIDF和TextRank方法的对比研究【摘要】随着大数据云计算的时代到来，关键词提取技术越发重要。选用合适的关键词提取算法能大大加快工作效率。本文选取了两个常见的关键词提取算法TFIDF和TextRank算法，对它们进行比较分析。【Abstract】As the era of big data and cloud computing comes, the technique of extraction of keywords becomes more and more important. With appropriate extraction algorithms, the efficiency can be improved significantly. In this paper, I choose two popular keyword extraction algorithm, TF-IDF and TextRank, to analyze and compare their pros and cons.【关键词】关键词抽取；TFIDF；TextRank1. 引言 关键词提取技术是自然语言处理和信息检索研究的重要基础之一。随着互联网技术的快速发展，网络文本志愿信息呈几何级数不断增长，大数据、云计算等技术对文本分类的要求也越来越高。关键词抽取技术被广泛应用在文章语义分析、文本的分类与聚类、情感分析等多种场合中。面对日益更新和规模庞大的文本数据，能够高效准确得实现关键词提取成为加快计算速度性能的关键。 关键词抽取的主要任务是：对未知类别的文档进行自动处理，通过一定算法提取出其中的关键词，从而方便后续操作。因此，为了使之后的信息检索和过滤等操作的准确性加强，对文本关键词抽取算法的精确度要求也越来越高。近年来，多种机器学习、统计理论等方法被用来进行文本的自动分类。【1】本文根据文本关键词词语之间的关联性与词频特性，选取了TFIDF和TextRank关键词提取算法，进行两者的效率和准确性的对比研究。2. TFIDF算法2.1 TF-IDF算法简介 TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一个词组或短语的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。在一组文档中，刻画某一文档特征的特征项可以根据其在这组文档中出现的频率赋予相应的权重，只有在少数文档中出现的较特殊的词，权重要比在多篇文档中出现的词的权重要高。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。2.2 TF-IDF算法原理TF-IDF实际上是TF和IDF的组合。TF即词频（Term Frequency），IDF即逆向文档频率（Inverse Document Frequency）。TF（词频）就是某个词在文章中出现的次数，此文章为需要分析的文本。为了统一标准，有如下两种计算方法【2】：TF（词频） = 某个词在文章中出现的次数该篇文章的总次数和TF词频= 某个词在文章中出现的次数该篇文章出现最多的单词的次数IDF（逆向文档频率）为该词的常见程度，需要构建一个语料库来模拟语言的使用环境。IDF逆向文档频率= log语料库的文档总数包含该词的文档总数+1如果一个词越常见，那么其分母就越大，IDF值就越小。TF-IDF=TF词频IDF（逆文档频率）之后，将每个单词的TF-IDF值按从大到小降序排列，排在最前面的几个词即为关键词。2.3 TF-IDF算法实现2.3.1 构建一一映射Map类C+STL函数库中已经包含了map的库函数，但为了使用起来更加方便、更便于个性化定制操作，于是使用自己定制的Map类模板。这个类函数主要是构建单词的string值与其TF、IDF值的一一对应关系，方便直接用string值下标访问其int值或double值，简化写代码的工作量。同时模板类中主要采取树形结构，建立一棵查找树，利用vector的空间动态分配的灵活性，从string的第一个字母开始一个一个往下找。每个Map类代表一个字母，从根部开始向下遍历，利用bool值判断该处是否为一个单词结尾。代码如下：/*一一映射函数Map类*Type为存储的TF、IDF、TF-IDF值，如int、double等*旨在通过string类型下标访问其Type值*/templateclass Mappublic:Type val = NULL;/Type值，类型为int、double/*下标运算符重载*中值为string类型*如果该string值已存在，则返回对应val*如果不存在则新建一个，返回初始值*/Type& operator (string item)Map &temp = find(item);/引用类函数find()查找到的值if (temp != NULL)/找到，则返回对应valreturn temp.val;else/未找到，则用create()函数创建一个并返回新的值create(item);return find(item).val;/*算术运算符=重载*左值为找到的Map.val引用*右值为对应的val值*返回当前Map的引用*/Map& operator =(Type item)val = item;return this;/*类函数列表*find为查找函数，找到则返回其值，没找到则新建一个返回初值*create为创建新值得函数*/Map find(string word);void create(string word);private:bool is_end = false;/是否为单词结尾char ID;/代表当前类的字母vector childs;/子节点集合;/*find查找函数*如果该string值已存在，则返回对应值*如果不存在则新建一个，返回初始值*/templateMap Map:find(string word)for (auto &r : childs)/遍历类函数的所有子节点直到找到对应项if (r-ID = word0 & r-is_end)/如果相等且为单词末尾if (word.size() = 1)/大小为一说明已找到return this;/返回当前类return r-find(word.substr(1, word.size() - 1);/递归调用find函数，一次减少一个字符return NULL;/返回空类/*create创建函数*递归创建字母树*/templatevoid Map:create(string word)if (word.size() = 0)/如果大小为0，说明所有字母都已创建完毕is_end = true;/标记单词结尾为truereturn;for (auto &r : childs)/遍历所有子节点if (r-ID = word0)/如果找到，则减少第一个字符，继续递归向下遍历r-creat(word.substr(1, word.size() - 1);return;Map *temp = new Map;/没找到，则新建一个Maptemp-ID = word0;/将其所代表的字符ID设为当前word的第一个字符childs.push_back(temp);/子节点中增加这一Maptemp-creat(word.substr(1, word.size() - 1);/继续递归创建后续字符return;2.3.2 构建语料库为了使语料库更符合本程序的应用场景，语料库采用自己构建的语料库。语料库素材来源于小说新闻等，总词数超过8亿词。因为每篇文档有几十万字，为了使词语的ITF更具普遍性，假设每1000词为一篇文章。然后每次将文章先存入一个临时语料库中，进行分析处理后，将处理后的词加入临时语料库。之后再将临时语料库合并入总的语料库。大致流程图如下：正序遍历去除前缀逆序遍历去除后缀保留中间必要的符号全部读完后输出到文件保存每读入1000个字符将临时语料库与总语料库合并并清空临时语料库对读入的每一个单词进行处理使其前后都没有不必要的字符并将其转化为小写定义语料库定义临时语料库循环读入文件 /建立语料库map corpus;/语料库，由字母string到出现频率double的映射long long int times = 0;/文章总数，作为计算频率的基数ofstream output(corpus.csv);/输出到excel表格中存储/*导入制作好的语料库*存在一一映射corpus中*/void buildCorpus()ifstream input(corpus.csv);/打开文件string item;/定义临时存储变量string和doubledouble val;while (!input.eof()/读入文件，存储到语料库映射中input item val;corpusitem = val;/*分析处理读入的string短语*先删去字符前的不必要符号 如数字、标点(等等*将剩下的大写字符转化为小写*保留字符中的标点，如Mr.Bill等*再删除字符后的不必要标点，如.,:等等*返回修改后的字符*/string analysis(string item)string temp = ;/定义空字符bool flag = false;/flag标记，当碰到第一个字母时，flag变为true，否则为false，滤过不必要的前缀for (auto &r : item)/遍历string中每一个字符if (r = , | r = ;)/滤过,;等符号continue;if (r = a)/碰到字母标记trueflag = true;if (r = A)/转化大小写flag = true;r += 32;if (flag)/如果已碰到字母，则在缓存string中加入该字符temp += r;if (temp.size() = 0)/如果是空字符，直接returnreturn temp;for (auto i = temp.rbegin(); i = temp.rend(); i+)/从尾开始遍历string，删去string中不必要的后缀if (*i = a)/若碰到字母，则跳出循环break;temp.pop_back();/删去后缀return temp;/返回处理过的字符string/*遍历临时语料库的数值*将其合并到总的语料库*/void print(map &frequency)for (auto &r : frequency)/遍历临时语料库if (corpus.find(r.first) = corpus.end()/第一次出现则将在总语料库中新建一个，并将其初始化corpusr.first = 0.0;corpusr.first+;/合并语料库中对应数值/*创建语料库*通过文件读入文章*由于部分文章为小说，有几十万字，于是统一按每1000字为一篇文章*语料库素材中所有文章的总次数大概有8亿词*将该文章中出现的单词存入临时语料库中*每一千字更新总语料库corpus，清空临时语料库frequency*最后计算每个单词的IDF值*/void readDictEn()int words = 0;/记录当前已读入的word词数，每一千字更新一次map frequency;/临时语料库，存放string单词到double频率的一一映射long long int cnt = 0;/临时变量，记录临时语料库被清零多少次for (int i = 1; i = 633; i+)/遍历语料库素材TXT文档，共有633个TXT文档，每篇文档平均12万词/*每篇文档的命名方式为EN(i),i为文档编号*先利用stringstream流创建文件名的字符串*再用ifstream流打开对应文件*/cout i :;/输出当前读入文件状态ostringstream out;/stringstream流，存储文件名字符串out EN ( i item;item = analysis(item);/将读入字符串处理成所需要求if (item.empty()/空字符串则略过continue;if (frequency.find(item) = frequency.end()/如果是新的字符串，则在语料库里新建一个并初始化frequencyitem = 0.0;frequencyitem+;/增加出现次数words+;if (words = 1000)/读入一千词时，即读入一篇文章时，合并语料库并清空临时语料库print(frequency);frequency.clear();cnt+;words = 0;for (auto &r : corpus)/打印每个单词的IDF值r.second /= (cnt + 1);r.second = abs(log(r.second);output r.first r.second endl;2.3.3 计算TF-IDF值 计算TF值时，只需要将所抽取的文章对象全部遍历一遍，对每个词计算其词频，再将词频乘以对应的IDF值，按照从大到小排序即可输出结果。/*提取关键词*对读入文章的每一个单词计算TF值*再分别计算TF-IDF值*将每个单词的结果输出到excel表格中*/void extract(string name)ifstream file(name);/打开文件string item;long long int words = 0;/单词总数，包括相同的单词map frequency;/这篇文章的语料库while (!file.eof()/循环读入文章中所有单词/以下过程与构建语料库过程类似file item;item = analysis(item);if (item.empty()continue;if (idle.find(item) != idle.end()continue;if (frequency.find(item) = frequency.end()frequencyitem = 0.0;frequencyitem+;words+;output.open(data.csv);for (auto &r : frequency)/输出数据到Excelr.second /= words;r.second *= corpusr.first;output r.first , r.second endl;3TextRank算法3.1算法简介TextRank也是一种用于文本排序的算法，它主要运用了矩阵迭代的代数知识来对每个文本词语进行分析，最后得出数值越高则越重要。其思想来源于网页排序算法PageRank。PageRank的基本思想主要是：一个网页的重要程度取决于链接到它的网页的数量以及这些网页的重要程度。比如有n个网页，对于其中一个网页Webi，所有链接到Webi的页面集合记为InWebi，所有Webi链接到的页面集合记为OutWebi，则其重要程度为：ImportanceWebi=WebjInWebj1OutWebjImportanceWebi此处的求和号可以通过矩阵计算来模拟实现，并通过不断地迭代，重要性的值会不断收敛为一常值，最后可以求出最后的网页重要性。TextRank就是仿造这算法设计。【3】3.2算法思路TextRank总体思路与PageRank类似。因为文本中不存在窗口与链接，所以要模拟造出窗口。在这里不妨设k个词为一个窗口，其中每个单词为一个链接，当一个窗口中的单词与另一个窗口中的单词一样时，即视为两个窗口有链接。当然也可以脱离PageRank的思想来解释这一算法。对于一个句子，其中的一个单词与这个句子的剩余单词都有关联性。同时，这个句子中的每一个单词又与另外其他句子中相同的单词也有关联性。也就是说，一个单词的重要性不仅仅取决于单词的重要性，还与该句子中其他单词的重要性相关。但为了使构造出来的矩阵运算更为简便，在此将单词句子假定为长度为k，每个单词为k的第一个单词。这样，每k个单词就构成一个句子，句子与句子中任意两个单词之间就构成一条边，最后形成的图是一个无向图。为了加快运算速度，图采用邻接矩阵的方式存储。而且，经过实际检验可以发现，该矩阵并不稀疏，所以直接转化为二维数组。每次计算时就不断按照公式迭代。如此循环遍历下去，这样不仅得到的矩阵运算方便计算，而且对结果的准确性也没有影响。迭代公式如下：ImportanceWordi=1-d + d *WordjInWord1OutWordjImportanceWordi其中d是阻尼系数，一般设置为0.85。初始时，可以先设重要性为1。容易看出，经过多次迭代后，该重要性的值会逐渐收敛为一常数。3.3 TextRank算法实现对读入的每一个单词进行处理使其前后都没有不必要的字符并将其转化为小写去除停用词TextRank所主要用到的主要是图的邻接矩阵存储，矩阵相乘合并等数据结构算法。流程图如下：对读入的每一个单词进行处理使其前后都没有不必要的字符并将其转化为小写正序遍历去除前缀逆序遍历去除后缀保留中间必要的符号设置迭代次数进行矩阵迭代运算将处理好的词存入string流中将单词存入语料库中构造单词图的邻接矩阵定义邻接矩阵阻尼向量读入文件 打印前十个结果作为关键词抽取结果构造结构体将矩阵结果信息转存到结构体中对其进行排序算法代码如下：ifstream EnFile;ofstream output;stringstream tempFile;set idle;map EnMatr;int EnRank = 0;const int k = 8;int key1000010000;double d1510000;double ans10000;/*读入文件并去除停用词*仿造TF-IDF的方法，对读入的词进行分析处理*将文章中处理过的词按照原来的顺序存入stringstream流tempFile中*将每个词按照构造语料库的方法，存入语料库中*构建单词图的邻接矩阵*/void scan(string name)ifstream stop(Stop.txt);while (!stop.eof()string temp;stop temp;idle.insert(temp);EnFile.open(name);string temp;while (!EnFile.eof()EnFile temp;temp = analysis(temp);if (idle.find(temp) != idle.end()continue;if (temp = )continue;if (EnMatr.find(temp) = EnMatr.end()EnMatrtemp = EnRank+;tempFile temp ;/*读入文件并去除停用词*仿造TF-IDF的方法，对读入的词进行分析处理*将文章中处理过的词按照原来的顺序存入stringstream流tempFile中*将每个词按照构造语料库的方法，存入语料库中*构建单词图的邻接矩阵*/void build()string bufferk;for (int i = 0; i bufferi;for (int i = 0; !tempFile.eof(); i = (i + 1) % k)/将string流中的数据读入循环数组中/为节省空间，数组只开k项，利用循环数组存储更新string temp = bufferi;for (auto &r : buffer)/构造邻接矩阵if (r = temp)continue;keyEnMatrtempEnMatrr+;tempFile bufferi;/*矩阵相乘运算*套用求TextRank公式*/void multiple()double temp10000;const size_t size = EnMatr.size();for (int i = 0; i size; i+)/矩阵相乘double sum = 0;for (int j = 0; j size; j+)sum += keyij * ansj;tempi = sum * 0.85;for (int i = 0; i size; i+)/向量相加ansi = tempi + 0.15;/*设置迭代次数*对每个单词进行迭代操作*/void solve(int times)/迭代times次const int size = EnMatr.size();for (int i = 0; i = size; i+)ansi = 1.0;for (int i = 0; i b.ans;/*将map中的值转移到结构体进行排序*输出排在前十位的词作为关键词*/void printAns()const int size = EnMatr.size();int i = 0;for (auto &r : EnMatr)outi.item = r.first;outi+.ans = ansr.second;sort(out, out + size, compare);for (int i = 0; i 10; i+)cout outi.item endl;4. 测试数据第一组测试数据：When I was a kid, I thought I would grow up to be an actress. I thought I would live in New York City, in a high-rise apartment building, with my husband and family of, oh, five or six kids. I thought Id live an urban, impossibly sophisticated1 life. Money would be no object. Perhaps there would be a private plane. (I should mention here that these fantasies were firmly rooted in the 1980s.) Well, I grew up and left the city for the country. I married and had one child - an only child, just like I had been. My husband and I work hard to make ends meet. But my life - my rich, imperfect, complicated, contented2 life - is the one Ive built for myself. Its an honest life. Its a life of integrity3. Its a life I love. But to have it, I had to lose my fantasy straight out of the pages of a magazine of what it was that I thought I wanted - of who I thought I was. I was underselling myself, it turned out.To love, to really live is to become willing to lose people, places, things, dreams, even to lose versions of ourselves that no longer serve us. And in place of what is lost, something new emerges4. It may not be what we imagined. But it is beautiful and it is ours. 直观上来看，这篇短文的关键词应该是live、grow。 TF-IDF运行结果：可以看出，life、live排在比较靠前的位置但不是在最前面，排名第一的居然是undershelling，可能与这个词在普通的文本中出现得比较少有关，但它并不是关键词。lose还能勉强说得过去，但emerge、high-rise、imperfect这些就有点牵强。结果有一定的可靠性但不能算准确。TextRank运行结果：这个结果的前几名就靠谱一些，关键的life、child、city、country、grew、married、huaband都有指出来，imperfect、contented虽然有点牵强，但还是少数，并且也是在排名靠后的位置。第二组测试数据： VOA Associates Incorporated is delighted to announce that we have joined Stantec. We are now part of a team that unites approximately 22,000 employees working in over 400 locations across six continents. This is an exceptional growth opportunity for us. More importantly, it offers our clients with the benefits and opportunities of working with a top ten global design firm.VOA was built with an emphasis on great design, great people, and great client experiences. Our business strategy has been centered on building a diverse practice and offering deep expertise in multiple market sectors to best serve our clients. We have grown the practice under this model for more than 46 years, and we are proud of our achievements.Stantec shares our commitment to design, a global growth strategy, and market diversity. Their culture and values align with ours. Our practices and geographic locations complement each other exceedingly well. Merging our talented teams allows us to offer a highly dynamic resource for our clients. And the combined creativity we apply to projects will allow us to go anywhere and meet our clients needs in a personalized way.Visit and youll see first-hand how Stantecs commitment to clients, creativity, and community inspires us to enhance and c