文本关键词提取(TFIDF和TextRank)
- 格式：docx
- 大小：162.71 KB
- 文档页数：27
基于关键词提取的TFIDF和TextRank方法的对比研究
题目：开发一个程序，在该程序中，允许输入一段文本（以界面或者文件输入方式均可），该程序自动抽取出包含的关键词，并按照关键词的权重由高到低排序后输出。
完成日期：2016.06.05
一、 需求分析
1. 以文本的形式读入数据，将每个单词抽象成一棵树，将单词与单词之间的关系抽象为图。
2. TFIDF算法部分以EXCEL形式将所有数据输出，TextRank算法部分直接以窗口形式输出排名前十位的数据。
3. 本程序的目的是在提取文本关键词的同时，比较TFDIF和TextRank算法的准确性和性能方面的差异。
4. 测试数据（附后）。
二、 概要设计
1. 抽象数据类型映射树定义如下：
ADT Map {
数据对象ID：ID是类型为char的元素集合，即为一个单词中的单个字
符，称为字符集。
数据对象val：val是类型为double或int的元素集合，为每个单词对应
的 TF值或IDF值，称为频率集。
数据对象is_end：is_end是类型为bool的元素集合，判断当前子结点是
否为单词末尾
数据关系 R :
R = { IDVal }
IDVal = { word–> num| word ∈ ID，num ∈ val，表示从word到num之间的一一映射}
运算符重载：
下标运算符 [] : 运算对象为string值，返回对应string值的子
树所代表的val值。
算术运算符 =：运算对象为double或int值，等式左值的val值替换为等式右值，并返回当前子树。
算术运算符 +-*/ : 运算对象为double或int值，对其val值进行运算，并返回当前子树。
相等运算符 ==和!= : 运算对象为val值，判断其val值是否相等，返回对应的bool值。 基本操作：
InitMap (&T);
操作结果：构造空树。
DestroyMap (&T);
初始条件：树T存在。
操作结果：构造空树。
CreateMap (&T, word);
初始条件：树T存在且word为string值。
操作结果：按照word的字符顺序自上而下遍历，如果有字符结点未创造，则构造新子结点，直到字符结束。
MapEmpty (T);
初始条件：树T存在。
操作结果：若T为空树，则返回True，否则False。
MapDepth (&T);
初始条件：树T存在。
操作结果：返回树的深度。
Root (&T);
初始条件：树T存在。
操作结果：返回T的根。
Value (&T, value);
初始条件：树T存在，value为T中某个结点的值。
操作结果：返回value的值。
Assign (&T, word, value);
初始条件：树T存在，且word结点也存在。
操作结果：结点word的value值替换为当前value。
Parent (&T, word);
初始条件：树T存在，且word结点也存在。
操作结果：返回word结点的双亲。 InsertWord (&T, word);
初始条件：树T存在。
操作结果：往树加入word值，并将其value值默认初始化。
DeleteChild (&T, word);
初始条件：树T存在，且word结点也存在。
操作结果：将word对应子节点的is_end值改为false。
TraverseMap (&T, visit() );
初始条件：树T存在，visit是对结点操作的应用函数。
操作结果：按某种次序对T的每个结点调用visit一次且至多一次。一旦visit失败，则操作失败。
}ADT Map
2. 抽象数据类型图定义如下
ADT Graph {
数据对象n：n是具有相同特征的数据元素集合，称为顶点集。
数据关系：DR = { | v, w ∈ n且 表示从v指向w的
弧 }
基本操作：
CreateGraph (&G, V, VR) ;
初始条件：V是图的顶点集，VR是图中弧的集合
操作结果：按V和VR的定义构造图G
DestroyGraph (&G);
初始条件：图G存在
操作结果：销毁图G
LocateVex (G, u);
初始条件：图G已存在，u和G中顶点有相同特征
操作结果：若G中存在顶点u，则返回该顶点在图中位置，
否则返回其它信息
GetVex (G, v);
初始条件：图G存在，v是G中某个顶点
操作结果：返回v的值
PutVex (&G, v, value); 初始条件：图G存在，v是G中某个顶点
操作结果：对v赋值value
FirstAdjVex (G, v);
初始条件：图G存在，v是G中某个顶点
操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻
接顶点，则返回“空”
NextAdjVex (G, v, w);
初始条件：图G存在，v是G中某个顶点，w是v的邻接顶
点
操作结果：返回v的(相对于w的)下一个邻接顶点。若w是
v的最后一个邻接点，则返回"空”
InsertVex (&G, v);
初始条件：图G存在，v和G中顶点有相同特征
操作结果：在图中增添新顶点v
DeleteVex (&G, v);
初始条件：图G存在，v是G中某个顶点
操作结果：删除G中顶点v及其相关的弧
InsertArc (&G, v, w)
初始条件：图G存在，v和w是G中两个顶点
操作结果：在图G中增添弧，若G是无向的，则还应
增添对称弧
DeleteArc (&G, v, w)
初始条件：图G存在，v和w是G中两个顶点
操作结果：删除G中的弧，若G是无向的，则还应删
除对称弧
DFSTraverse (G, v, visit())
初始条件：图G存在，v是G中某个顶点，visit是对顶点
的应用函数
操作结果：从顶点v起深度优先遍历图G，并对每个顶点调
用函数visit()一次且至多一次。一旦visit()失败，则操作失败
BFSTraverse (G, v, visit())
初始条件：图G存在，v是G中某个顶点，visit是对顶点
的应用函数
操作结果：从顶点v起广度优先遍历图G，并对每个顶点调
用函数visit()一次且至多一次。一旦
visit()失败，则操作失败
} ADT Graph 3. 本程序包含两大模块，TF-IDF算法部分和TextRank算法部分
1）主函数部分
void main () {
TF-IDF算法;
TextRank算法;
}
2）TF-IDF算法
i. 构建语料库（语料库的原料来源于超过八亿词的文本）
ii. 导入语料库
iii. 读入文本
iv. 分析所读入的单词
v. 合并语料库
vi. 输出到EXCEL
3）TextRank算法
i. 读入数据
ii. 分析所读入的单词
iii. 构造矩阵
iv. 套用公式
v. 结果排序
vi. 输出前十名
各模块之间的调用关系如下：
主程序模块
构建语料库
导入语料库 分析所读入的单词 读入数据
三、 详细设计
1. 设计思路 本程序以实现关键词抽取为目的，选取了TF-IDF和TextRank关键词提取算法，进行两者的效率和准确性的比较研究。
2. TFIDF算法
2.1． TF-IDF算法简介 读入文本
合并语料库
输出到EXCEL 构造矩阵
套用公式
结果排序
输出前十名 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值按从大到小降序排列，排在最前面的几个词即为关键词。
2.3． TF-IDF算法实现
