基于特征选择优化的主题描述算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于特征选择优化的主题描述算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：针对当前主题描述不精确以及适应性低的问题，提出了一种基于特征选择优化的主题描述算法――TDFSO（Topic Description based on Feature Selection Optimization）。此算法改进了主题关键词在文本中权重的计算方法，能提取出具有较强文本描述和类别区分能力的关键词。
关键词：主题描述；主题爬虫；文本分类；关键词提取
中图分类号：TP301.6文献标识码：A文章编号：1007-9599 (2012) 01-0000-02
Theme Description Algorithm Based on Feature Selection Optimization
Wang Chunhui,Wu Qi,Zhu Kai
(Computer College,Sichuan University,Chengdu610064,China)
Abstract:The current topic describes the problem of inaccurate and low adaptability topic describes algorithms-TDFSO (Topic Description based on Feature the Selection Optimization) based feature selection optimization.This algorithm improves the topic keywords in the text weight calculation method can extract the key words with strong text description and category distinguishing ability.
Keywords:Theme description;Theme reptiles;Text classification;Keyword extraction
一、引言
随着因特网信息量的快速增长，在网络信息采集、用户个性化需求、信息更新速度方面都面临着前所未有的挑战。传统的基于层次遍历的网络爬虫已经不能满足现有要求。因此，基于主题的网络爬虫已经成为网络信息采集的重要手段之一。主题爬虫的目的是在有限的时间发现更多与主题相关的网页。所以，如何准确的描述主题以便更好地判断网页与主题的相关性成为实现主题爬虫的关键点之一。目前主题描述的方法主要有三种：基于关键词的主题描述[1，2]，基于自然文本语言的主题描述[3]和基于分类法的主题描述[4，5]。前两种最终都是形成关键词及其对应的权重去描述一个主题，而基于分类法的主题描述是利用人工维护的一个大型的分类目录去描述主题。文章[6]说明了基于分类法的主题描述能避免基于关键词的主题描述的弊端，即没有考虑到主题之间的联系而认为所有主题都是具有独立的语义的个体。但是基于分类法的主题描述并不能满足用户对不同主题的信息采集需求。因为网络上关注的热点主题随时间变化较大，不可能要求分类目录更新的提取出分值较大的关键字形成主题向量。算法中所使用的训练集可以从网络速度与网络更新的速度相同，所以分类目录并不能描述随时间变化而变化的主题。文章[7]使用TF-IDF算法[8]提取主题关键词作为主题描述。虽然TF-IDF算法是关键词提取的经典算法之一，它能很好地提取出在文本中频繁出现的单词来描述文本主题，但是由于IDF的定义过于简单，它并不能十分准确的提取出最适合的关键词[9]。
为了适应网络主题的多样性以及提取出更具类别区分力的主题关键词，本文提出一种基于关键词特征提取和优化的主题描述算法――TDFSO（Topic Description based on Feature Selection Optimization）。该算法首先对训练集进行学习，提炼出用户感兴趣主题的主题库。然后计算出主题库中的每个关键词与主题的相关度，并用一个分值表示。最后根据分值排序中收集也可以由用户提供，因此提炼出的关键词更能表达用户实际关心的主题信息。另外，TDFSO算法重点突出了关键词在不同类别的训练集中权重的比较。因此相比于TF-IDF算法，TDFSO算法提取出的关键词具有更好的类别描述和区分能力。
二、主题描述算法
（一）主题训练集
在进行主题描述之前需要收集训练集，训练集分为动态训练集和静态训练集。动态训练集可通过两种方式获取，第一种是直接由用户提供一些包含了他们所关心主题的文本；另一种是在用户指定主题后从网络中收集。动态训练集为主题的初始描述，但是其中包括了许多主题不相关信息，对主题的描述并不准确，因此需要静态训练集辅助以提高主题描述的准确度。
静态训练集是各种类别文本的集合，其中主要包括如“世界”、“国家”等主题分类不明确的单词或短语以及一些人称代词、副词。静态训练集不同于动态训练集，它可在主题确定前进行收集和训练。静态训练集中的文档所包含的单词越通用，静态训练集质量就越高，也就可供越多不同的主题使用。
（二）关键词提取
TF-IDF是提取特征关键词的经典算法之一，TF-IDF算法中的TF代表单词在文本中的频数，IDF为单词逆文本频率。其主要思想是提取出那些在一个文本中频繁出现而在其它文本中很少出现的单词来描述此文本。本文借用此思想，提出了一种主题关键词提取的算法。此算法通过加权计算出单词在文本中的权重，利用此权重进一步计算单词在一类文本集中的得分，以此来评价单词描述此类文本集的能力。
下面介绍主题关键词提取的算法流程：
1.对动态文本集和静态文本集中的所有文本进行分词处理（这里使用中科院的ICTCLAS分词器[10]）；
2.根据公式（1）计算动态文本集中出现的每一个单词在对应文本中的权重；公式（1）中 表示单词 在文本中的频率，0.5是一个平滑值，可以让单词权重值的分布不至于太陡峭。
3.根据公式（2）计算单词的得分；公式（2）中的 和 分别表示动态训练集和静态训练集的文本数， 表示单词 在对应训练集中第 个文本的权重值。 和 分别表示在动态训练集和静态训练集中出现了单词 的文本数量。
4.根据单词的得分进行排序，提取前若干个单词作为主题描述的主题关键词并根据得分形成主题向量。
本算法计算单词在静态训练集中的权重之和，而不是简单计算静态训练集总文本数量与出现了单词的文本数量的比值，既可以降低类别区分度不明显的单词的分值，又能避免TF-IDF算法的弊端，最终达到准确提取出适合描述文本主题的关键词的目的。
（三）相似度计算
文本分类或主题爬虫都需要计算文本与主题的相关度。本文使用向量空间模型（VSM）将文本表示成为向量，从而使用余弦相似度算法计算文本向量与主题向量的相似度。VSM将文本表示成为 的形式，其中 是第 个单词在文本中的权重值。文本中单词的权重值一般是由TF-IDF算法计算。TF-IDF算法公式如下：
公式（3）中的 为单词在文本中出现的频数， 为单词的逆文本频率。公式（4）中的 为全部训练文档的总数， 为训练文档中包含此单词的文本总数。为了避免篇幅的长短带来的影响，需要将使用公式（5）将TF-IDF归一化。最后通过余弦相似度计算公式（6）计算出文本与主题的相似度。
计算网页与主题相似度时，需要将网页向量与主题向量里的关键词一一对应，如果网页中包含主题向量里出现的关键词，则网页向量对应维度上置为此关键词在网页中的权重，如果没有则置为0，从而提高的爬行过程中网页相似度计算的效率。
三、实验与分析
（一）实验框架
本文将TDFSO的实现分为五个模块：文本收集模块、分词模块、词频统计模块、文本单词权重计算模块、得分计算模块。下面分别介绍五个模块的功能。
1.文本收集模块：主题描述的初始化步骤，主要是收集与主题相关的文本集，可以通过网络收集和用户提交两种形式实现。
2.分词模块：对收集到的文本集进行分词处理。由于中文单词中包含了许多不同的词性，而一般能描述主题的单词多为名词、动词或形容词，因此在分词的过程中需要对单词的词性进行分析。
3.词频统计模块：主要是对单词在文本中出现的次数进行统计。
4.文本单词权重计算模块：根据单词在文本中的词频计算其对此文本的描述能力。
5.得分计算模块：综合了单词在某类文本中的权重以及单词在其余类文本中的权重，最终计算出单词描述某类主题的能力并形成主题向量。
主题描述的过程即上述五个模块的组合，图1所示为整个主题描述的大致流程：（1）文本收集模块通过因特网收集用户感兴趣的文本或直接获取用户提交的文本。（2）分词模块将文本收集模块获取到的文本进行分词和词性分析处理，将文本表示为关键词的集合。（3）词频统计模块计算每个单词在其所在的文本中出现的次数。（4）文本单词权重计算模块根据单词的词频计算其在文本中的权重。（5）得分计算模块将单词在训练集中的权重进行整合，分析出单词描述某类主题文本集的能力和区分不同主题文本集的能力，并形成主题向量存入数据库。
图1 主题描述算法实验框架
（二）主题关键词对比
为了证明TDFSO算法提取出的关键词优于TF-IDF算法，下面通过对比实验从直观上进行比较。此次实验中使用的训练集来自搜狗实验室[11]提供的文本分类测试集，主题包括IT、财经、健康、教育、旅游、军事、体育、文化8个大类。动态训练集为财经类文本，静态训练集由其余7类文本构成。TDFSO算法提取到的主题关键词与TF-IDF算法的提取结果对比如下所示。
表1 主题关键词对比
表1是TDFSO和TF-IDF两种算法提取出的关键词的对比，其中斜体带下划线的关键词不能明显的区别财经类主题与其它主题。从表中可以发现，TDFSO提取出的关键词更能描述财经类的主题，而TF-IDF提取出的关键词中包含了一些类别区分不明显的单词，例如“公司”、“论坛”等。这就是因为对IDF的定义过于简单，并没有能有效降低这些词语的权重所导致的。
四、结束语
本文在研究了常用的主题关键词提取算法的基础上，借助其中的思想，提出了一种新的基于特征选择优化的主题描述算法。该算法细化了一个关键词在训练集中权重的计算，并且合理的权衡了其在不同训练集中的权重。该算法可以应用于需要进行主题描述的大多数场合。由于采用用户提供的文本作为训练集，因此能提取出更多符合用户需求的主题关键词。实验结果表明该算法形成的主题描述在文本分类和主题爬虫中都有较好的效果。但是由于该算法对动态训练集和静态训练集的依赖较大，所以训练集的好坏一定程度的决定了主题关键词提取的质量。
参考文献：
[1]N Angkawattanawit,A Rungsawang.Learnable Crawling：an Efficient Approach to Topic-specific web Resource Discovery[C].In Proceeding of 2002 International Symposium on Communication and Infromation Technology,2002:573-582
[2]Hersovici M,Jacov M I,Marek Y.et al.The shark-search algorithm-An application：Tailored web site mapping[J].In Proceeding of the 7th International World Wide Web Conference,1998:317-326
[3]中文Web信息检索[EB/OL].
[作者简介]王春晖（1987-），男，广州柳州人，硕士研究生，主要研究方向为信息安全、WEB挖掘；吴麒（1985-），男，四川青神人，博士研究生，主要研究方向为信息安全、WEB挖掘；朱锴（1987-），男，天津人，硕士研究生，主要研究方向为WEB挖掘。