基于行业专有词典的TF-IDF特征选择算法改进

张齐勋 刘宏志 刘诗祥 贾 堂 曹 健

1(北京大学软件与微电子学院 北京 102600)2(北京大学信息科学技术学院 北京 100871)



基于行业专有词典的TF-IDF特征选择算法改进

张齐勋1,2刘宏志1刘诗祥1贾 堂1曹 健1,2

1(北京大学软件与微电子学院 北京 102600)2(北京大学信息科学技术学院 北京 100871)

行业专有词典是收录特定行业专有用语的词典，将行业专有词典运用到基于TF-IDF的特征选取算法中可提高文本特征空间的完备性。基于TF-IDF的改进算法的核心目标是提取出低频的关键词，现有的基于统计特征的改进方法增加了原始算法的计算复杂度，降低了算法的效率。针对这一问题，在原始的TF-IDF特征选取算法上采用词典映射的方法提取低频关键词来构建完备的特征空间。实验结果表明，基于行业专有词典的TF-IDF算法提取出的特征较未使用行业专有词典特征选取算法提取出的特征在后续的二次聚类验证实验中能有效地提高聚类的查全率和查准率。

行业专有词典 TF-IDF 特征空间 特征选择算法

0 引 言

行业专有词典是收录某种特定行业专用术语的词典。它可以使用结合统计方法的机械匹配算法对特定行业的文本库进行分词来登记生词，从而构建出该行业专有的词典。行业专用词典通常运用于文本挖掘的预处理阶段,从而获取高质量的分词结果。但实际上行业专用词典还包含了大量对应行业中的重要且在文本中出现频率较低的词，这些词都可以作为文章的关键词以及特征向量出现，然而传统的TF-IDF算法往往会忽略掉低频词汇。由此衍生了针对原始算法缺点的改进算法，例如Mingmin Xu等提出了一种基于IDF的改进算法，命名为信道分配信息，该方法通过原始数据的统计特征来识别核心词[1]。罗欣等则基于TF改进原始算法，该算法以词频差异为基础，用信息量来重新计算TF值[2]。这些改进的算法能够找到低频核心词，提高文本特征空间的准确度，但同时也提高了算法的时间开销。

本文根据数据自身的特点将行业专有词典运用到原始的TF-IDF特性选择的过程中，从而在提取出低频关键词的同时避免较大的时间复杂度，通过该算法获取的特征空间结构稳定，可满足较高的准确性要求。

1 行业专有词典的构建

1.1 基本词典

网络资源中广泛使用的大都为基本词典，基本词典是指不包含行业专业用语的词典,包含了实体词词典、停用词词典等，基本词典里面的词可以无差别地出现在任何行业的文本中，如图1所示。

正是由于针对特定行业的词典在网上难以直接获取，而该词典在后续的分词以及特征选取中又尤为重要，所以需要提前构建出行业专有词典。

图1 基本词典和行业词典的关系

1.2 行业专有词典的构建

行业专有词典的构建分为数据采集、正文提取以及利用基本词典和统计的方法构建，具体过程如下:

1) 数据采集

构建词典的第一步是获取特定的行业文本，通常的方法有：

(1) 利用网络爬虫设定关键词定向获取网页文件；

(2) 使用网络爬虫获取与行业相关的垂直新闻网站的网页文件。

2) 正文提取

获取网页文件之后需对文件进行正文提取，即过滤网页中的标签、广告、导航条等无关信息从而得到有用信息。图2为原始的网页DOM机构片段，图3从DOM结构中提取的正文。

图2 html DOM结构

图3 DOM中的正文信息

3) 利用基本词典和统计的方法构建行业词典

(1) 统计的方法

中文词是字和字之间稳定的组合，可采用基于统计的方法计算相邻字的字符串在文档集合中出现的频率，频率越大表明该字符串构成一个词的可信度越大，词的可信度主要依赖于字与字相邻出现的频率，该频率被称之为互信息。

单纯的依靠统计的方法来登记词，时间空间开销较大且效果不理想，会得到很多没有意义的词，工程中通常把这种方法和机械匹配法结合起来使用：使用机械匹配分词，使用统计方法识别新词。这样利用了机械匹配快速准确以及统计方法可识别新词的优点。

(2) 生成行业词典的步骤

首先，利用已有的基本词典对提取的正文进行分词，并记录词典中未登记的单字及其在文本中出现的上下文。

其次，将单字和其位置信息作为统计方法的输入，进行新词的查找计算。

最后，人工审核和标定新词。

1.3 TD-IDF算法

TF-IDF算法是一种统计方法，用以评估一个词对一个文档集中的某一篇文本的重要程度。词的重要性随着它在文件中出现的频率成正比增加，但同时会随着它在文档集中出现的频率呈反比下降。

TF代表Term Frequency，它是特征词出现在文章中的频率[4]，其定义为：

(1)

其中f(w)是w在文本中出现的频数，n是文本中实体词总数。IDF代表Inverse Document Frequency，它是特征的逆文档频率，其定义为：

(2)

其中D是文本总数，d是包含词w的文本的数量。通过上述两个公式可知，TF反映的是w在文本中的重要程度，而IDF反映的是w在整个文档集上的常见程度[5]。若一个词的TF和IDF值都比较大则表明这个词在整个文档集合中不常见，但是在该文本中却大量出现，即该词为该文章的一个关键词，需分配较大的权重。权重为：

TF-IDF(w)=TF(w)×IDF(w)

(3)

TF-IDF算法计算简单，可以直接计算出特征的权重，面对数据量的增长，TF-IDF的算法复杂度是线性增长的。所以TF-IDF在精度要求不是非常严格的系统中是信息量算法的最好的替代者。

2 算法的改进

首先对一些现有的算法进行简介，其后提出改进算法。

2.1 K-means算法

K-means是非常典型的基于划分的聚类算法，它接收输入数值k和数据集中k个初始中心数据对象，计算剩余数据与各中心点的距离，并将其划分距离最近的中心点形成的簇中。重新计算有变化的簇的均值，并以该均值为新的中心点继续迭代上述步骤，直到中心点不再变化[6]。

2.2 DBSCAN算法

DBSACN算法从任意一个未访问的数据对象d开始，根据指定的扫描半径E来扫描所有从d出发密度可达的数据对象。当扫描半径内的对象数量达到指定的最小包含数据点数MinPts的时候，则标记这些点为一个簇，标记d为该簇的核心点，并标记其为已访问。在簇内重复上述工作，如果一个簇内出现多个核心点，那么这些核心点的簇要合并为一个簇。如果扫描半径内的对象数量达不到MinPts的时候，d则被标记为噪声和已访问。继续迭代步骤，直到没有点可以访问[7]。

2.3 基于K-means和DBSCAN算法的二次聚类

DBSCAN相比K-Means算法无需指定簇的数目作为参数，且能识别噪声[8]。本文的聚类采用DBSCAN算法作为一次聚类算法获取粗糙集[9]来确定k和k个初始的中心点，其后在粗糙集上使用K-Means算法来提高聚类效果。参数E和MinPts的确定没有规律可循[10]，本文采用一种启发式方法来确定相关参数。二次聚类算法流程如下：

(1) 设有N个数据对象，计算出这N个数据对象之间的间距，取这些间距的平均值作为DESCAN算法的扫描半径。

(2) 用(1)得到的扫描半径来计算这N个数据对象周围的数据点，并从大到小排列。

(3) 根据(2)的结果来选取K-Means算法的簇中心，若某个点在先前选定的簇中心所覆盖的区域内，则忽略该点并继续选择，直到所有点都被标记为访问。

(4) 根据(3)的结果作为K-Means算法的参数，对原数据集进行划分。

二次聚类中无需人工指定E和Minpts，而是利用了数据自身的分布情况，所以聚类结果较为稳定。

2.4 改进目标

TF-IDF是一种基于词频的算法，经常会遗漏出现频率不高但是能显著代表文本信息的词。通过TF-IDF算法选择出来的特征并不能完全代表原始文本，所以现有的基于TF-IDF的改进算法的目标都是将原始算法遗漏的低频词添加到算法选择的结果之中，提高了原始算法的计算复杂度。本文设计了基于行业专有词典的TF-IDF特征选择算法，在避免提高算法复杂度的情况下获取到文本准确的关键低频词。

2.5 算法改进流程

(1) 将行业专有词典中的词以哈希表的形式存入内存，例如：“聚亚安酯轮辐”是轮胎行业专有词典中的词，则在内存中以“聚亚安酯轮辐”为键，“1”为对应的值，键值就是这个词的权重。

(2) 对文本的分词数据进行TF-IDF值的计算，结果从小到大进行排列，TF-IDF大于阈值的词被视为特征元素。

(3) 遍历文本的分词数据，如果分词数据中的项存在于(1)生成的哈希表中，则标记该中间数据为特征元素。

(4) 将(2)和(3)中的特征合并，得到该文本的特征向量。

3 验证实验设计

实验的目的在于对比由本文提出的基于行业专有词典的TF-IDF特征选择算法选择出的文本特征和用普通TF-IDF算法选择出的文本特征的差异，主要通过聚类的方法来进行验证。通过对聚类的查全率以及查准率的比较得出实验结论。

3.1 实验环境

数据采集以及后续的预处理和聚类都属于计算密集形的工作，本文的实验环境如下：

(1) 实验环境由台式电脑集群构成，其系统为Window2003，CPU：i7-4800、内存：16 GB、硬盘：4 TB。分别负责新闻数据采集、预处理、聚类。这些模块都使用Java语言进行编写。

(2) 数据库采用MySQL。

3.2 实验流程

选取不同行业的文本进行二次聚类来横向对比子向量空间的优劣，其流程具体如下：

(1) 选取具有行业专有词典的轮胎行业新闻文本20 000篇，选取金融行业新闻文本20 000篇，根据百度热点新闻获取的其他社会热点新闻文本40 000篇(4类新闻，每个类10 000篇)作为原始数据；

(2) 预处理(1)中的文本；

(3) 先使用二次聚类，并从中获得DBSCAN需要的扫描半径；

(4) 采用(3)获取的扫描半径开始用DESCAN算法聚类，Minpts指定为10 000；

(5) 用K-Means算法聚类，根据粗糙集的中间结果来设定k值；

(6) 分别用K-means和DBSCAN进行聚类生成结果对照组。

3.3 实验结果分析

实验结果从三方面进行考察：

• 时间开销：时间从特征选择开始计时直到聚类结束；

• 查全率：查全率是指某个簇中数据量和数据集中与该簇同类的数据量的比值；

• 查准率：查准率是指簇中某个类别的数据总数和全簇数据总数的比值。

1) 时间开销

各算法时间开销如图4所示。

图4 时间开销对比

图4展示了三种算法随文本数量变化的变化情况，可见以上三种算法的时间开销都随着文本增加而增加，但是二次聚类算法的增长速度较慢，而DBSCAN算法和K-Means算法增长率随文本增加大幅上升。时间开销上升有两方面的原因:随着文本数量加剧预处理的时间上升，算法自身的时间开销。K-Means和DBSCAN算法对于不同的参数设定会有不同的时间开销，当参数选取不当时，时间开销较大。

2) 查全率

查全率如图5、图6所示。

图5 轮胎行业的查全率

图6 金融行业的查全率

从图5、图6中可以看出，查全率随着特征向量的维数升高而升高。二次聚类的查全率高于其他两种算法，说明二次聚类更加稳定。轮胎行业的查全率普遍高于金融行业的查全率，这是因为在轮胎行业文本的特征选择阶段加入了轮胎行业专有词典，从而使得轮胎行业的特征更为明显。

3) 查准率

查准率如图7、图8所示。

图7 轮胎行业的查准率

图8 金融行业的查准率

从图7、图8中可以看出，查准率随着特征向量维数的增加而降低，这是因为特征的维数越大，特征间的区别度就越低，就容易把不相关的文本聚类到簇中。总体来说，轮胎行业的查准率也高于金融行业的查准率。

从上述轮胎行业和金融行业的查全率、查准率测试结果对比中可以看出使用了行业专有词典选择的特征在聚类分析中对聚类效果的提升影响非常明显，二次聚类比起人工确定参数的单次聚类表现得更加稳定。

4 结 语

本文研究了垂直行业中专有词典的生成，主要包括用统计的方法进行新词的识别。本文创新性地将行业专有词典用于特征的选择中，提高了特征向量的区分度。通过对比实验，证明了本文设计的基于行业专有词典的TF-IDF特征选择算法在查全率和查准率上较原始算法均有所提高。

[1] Lu Z, Zhao Q, Yang L. A segmentation method for crossing ambiguity string based on mutual information and t-test difference[C]// Information, Computing and Telecommunication, 2009. YC-ICT '09. IEEE Youth Conference on. IEEE, 2009:371-374.

[2] 罗欣, 夏德麟, 晏蒲柳. 基于词频差异的特征选取及改进的TF-IDF公式[J]. 计算机应用, 2005, 25(9):2031-2033.

[3] Huang X, Wu Q. Micro-blog commercial word extraction based on improved TF-IDF algorithm[C]// TENCON 2013-2013 IEEE Region 10 Conference (31194). IEEE, 2013:1-5.

[4] Xu M, He L, Xin L. A Refined TF-IDF Algorithm Based on Channel Distribution Information for Web News Feature Extraction[C]// Proceedings of the 2010 Second International Workshop on Education Technology and Computer Science-Volume 02. IEEE Computer Society, 2010:15-19.

[5] 赵卫中, 马慧芳, 傅燕翔,等. 基于云计算平台Hadoop的并行k-means聚类算法设计研究[J]. 计算机科学, 2011, 38(10):166-168.

[6] Ay M, Kisi O. Modelling of chemical oxygen demand by using ANNs, ANFIS and k-means clustering techniques[J]. Journal of Hydrology, 2014, 511(7):279-289.

[7] Abbasi A A, Younis M. A Survey on Clustering Algorithms for Wireless Sensor Networks[J]. Network Based Information Systems International Conference on, 2010, 30(2-3):358-364.

[8] Wang Q, Dai H, Sun Y. A rough set based clustering algorithm and the information theoretical approach to refine clusters[C]// Intelligent Control and Automation, 2004. WCICA 2004. Fifth World Congress on. IEEE, 2004:4287-4291.

[9] Kerdprasop K, Kerdprasop N, Sattayatham P. Weighted K-Means for Density-Biased Clustering[J]. Lecture Notes in Computer Science, 2005, 3589:488-497.

[10] 付立东. 核k-means聚类检测复杂网络社团算法[J]. 计算机科学, 2010, 37(9):212-213.

IMPROVEMENT OF TF-IDF FEATURE SELECTION ALGORITHM BASED ON INDUSTRY PROPRIETARY DICTIONARY

Zhang Qixun1,2Liu Hongzhi1Liu Shixiang1Jia Tang1Cao Jian1,2

1(SchoolofSoftwareandMicroelectronics,PekingUniversity,Beijing102600,China)2(SchoolofElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871,China)

An industry proprietary dictionary is a dictionary of industry-specific terms, it can improve the completeness of the text feature space by applying the industry proprietary dictionary to the feature selection algorithm based on TF-IDF. The key goal of TF-IDF-based improved algorithm is to extract low-frequency keywords. The existing improved method based on statistical features increases the computational complexity of the original algorithm and reduces the efficiency of the algorithm. To solve this problem, the original TF-IDF feature selection algorithm adopts lexical mapping to extract low-frequency keywords to construct a complete feature space. Experimental results show that the feature extracted by TF-IDF algorithm based on industry proprietary dictionary can improve the recall and precision of clustering effectively in the following secondary clustering verification experiments compared with the feature extracted without using the industry proprietary dictionary feature selection algorithm.

Industry proprietary dictionary TF-IDF Feature space Feature selection algorithm

2016-05-06。张齐勋，讲师，主研领域：计算机软件与理论。刘宏志，副教授。刘诗祥，硕士生。贾堂，硕士生。曹健，讲师。

TP391.1

A

10.3969/j.issn.1000-386x.2017.07.051