机器学习那些事——文本挖掘中的特征提取

机器学习当然包含很多的方面，但我只关心文本挖掘，那么机器学习和文本挖掘的关系是什么？

文本挖掘的一般流程如下所示：

第一步当然是，特征提取，这是一个文档降维的过程。首先明晰几个概念，特征提取、特征选择（特征选取）Feature Selection、特征抽取Feature Extraction。一般来说，特征提取实际上有两大类方法。一类称为特征选择，指的是从原有的特征（那许多有用无用混在一起的词汇）中提取出少量的，具有代表性的特征，但特征的类型没有变化（原来是一堆词，特征提取后仍是一堆词，数量大大减少了而已）。另一类称为特征抽取的方法则有所不同，它从原有的特征中重构出新的特征（原来是一堆词，重构后变成了别的，例如LSI将其转为矩阵，文档生成模型将其转化为某个概率分布的一些参数），新的特征具有更强的代表性，并耗费更少的计算资源。

特征选择的方式又分为4种：(1)用映射或变换的方法把原始特征变换为较少的新特征；(2)从原始特征中挑选出一些最具代表性的特征；(3)根据专家的知识挑选最有影响的特征；(4)用数学的方法进行选取，找出最具分类信息的特征，这种方法是一种比较精确的方法，人为因素的干扰较少，尤其适合于文本自动分类挖掘系统的应用。

网络各个大神对特征提取的博文已有很多，我们这里主要做一个整合，留以后用。

特征提取

Reference:http://blog.chinaunix.net/uid-20767210-id-1849628.html首先来说说什么是向量空间模型VSM

向量空间模型是由Salton等人于20世纪60年代末提出，是一种简便、高效的文本表示模型，其理论基础是代数学。向量空间模型把用户的查询要求和数据库文档信息表示成由检索项构成的向量空间中的点，通过计算向量之间的距离来判定文档和查询之间的相似程度。然后，根据相似程度排列查询结果。向量空间模型的关键在于特征向量的选取和特征向量的权值计算两个部分。

下面内容来自：http://blog.chinaunix.net/uid-446337-id-94440.html

举个例子，假设说把我正在写的“文本分类入门”系列文章的第二篇抽出来当作一个需要分类的文本，则可以用如下的向量来表示这个文本，以便于计算机理解和处理。

　　w2=（文本，5，统计学习，4，模型，0，……）

　　这个向量表示在w2所代表的文本中，“文本”这个词出现了5次（这个信息就叫做词频），“统计学习”这个词出现了4次，而“模型”这个词出现了0次，依此类推，后面的词没有列出。

　　而系列的第三篇文章可以表示为

　　w3=（文本，9，统计学习，4，模型，10，……）

　　其含义同上。如果还有更多的文档需要表示，我们都可以使用这种方式。

　　只通过观察w2和w3我们就可以看出实际上有更方便的表示文本向量的方法，那就是把所有文档都要用到的词从向量中抽离出来，形成共用的数据结构（也可以仍是向量的形式），这个数据结构就叫做词典，或者特征项集合。

　　例如我们的问题就可以抽离出一个词典向量

　　D=（文本，统计学习，模型，……）

　　所有的文档向量均可在参考这个词典向量的基础上简化成诸如

　　w2=（5，4，0，……）

　　w3=（9，4，10，……）

　　的形式，其含义没有改变。

　　5，4，10这些数字分别叫做各个词在某个文档中的权重，实际上单单使用词频作为权重并不多见，也不十分有用，更常见的做法是使用地球人都知道的TF/IDF值作为权重。

那么我们把文本转化为VSM的前提，就是要进行特征选择和权重计算。所以选择不同的特征选择和权重计算方法，可以将文档转换为不同样式的VSM。

常用方法的总结：这里只说常见的，可以用的，其他的嘛，用到再说~有些简单的一两句话就能解释清楚，有些嘛……

（1）最简单的当然是词频方法（Word Frequency）：

词频是一个词在文档中出现的次数。通过词频进行特征选择就是将词频小于某一闭值的词删除，从而降低特征空间的维数。这个方法是基于这样一个假设，即出现频率小的词对过滤的影响也较小。但是在信息检索的研究中认为，有时频率小的词含有更多的信息。因此，在特征选择的过程中不宜简单地根据词频大幅度删词。

（2）对于多文档最简单的方法：文档频数DF

文档频数(Document Frequency,DF)是最为简单的一种特征选择算法,它指的是在整个数据集中有多少个文本包含这个单词。在训练文本集中对每个特征计计算它的文档频次，并且根据预先设定的阑值去除那些文档频次特别低和特别高的特征。文档频次通过在训练文档数量中计算线性近似复杂度来衡量巨大的文档集，计算复杂度较低，能够适用于任何语料，因此是特征降维的常用方法。

在训练文本集中对每个特征计算它的文档频数,若该项的DF 值小于某个阈值则将其删除,若其DF 值大于某个阈值也将其去掉。因为他们分别代表了“没有代表性”和“没有区分度”2 种极端的情况。DF 特征选取使稀有词要么不含有用信息,要么太少而不足以对分类产生影响,要么是噪音,所以可以删去。DF 的优点在于计算量很小,而在实际运用中却有很好的效果。缺点是稀有词可能在某一类文本中并不稀有,也可能包含着重要的判断信息,简单舍弃,可能影响分类器的精度。

文档频数最大的优势就是速度快,它的时间复杂度和文本数量成线性关系,所以非常适合于超大规模文本数据集的特征选择。不仅如此,文档频数还非常地高效,在有监督的特征选择应用中当删除90%单词的时候其性能与信息增益和x2 统计的性能还不相上下。DF 是最简单的特征项选取方法,而且该方法的计算复杂度低,能够胜任大规模的分类任务。

但如果某一稀有词条主要出现在某类训练集中,却能很好地反映类别的特征,而因低于某个设定的阈值而滤除掉,这样就会对分类精度有一定的影响。

（3）第二简单的方法TF-IDF

TF-IDF（term frequency–inverse document frequency）是一种用于信息搜索和信息挖掘的常用加权技术。在搜索、文献分类和其他相关领域有广泛的应用。

TF-IDF的主要思想是，如果某个词或短语在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。TF词频(Term Frequency)指的是某一个给定的词语在该文件中出现的次数。IDF反文档频率(Inverse Document Frequency)的主要思想是：如果包含词条的文档越少，IDF越大，则说明词条具有很好的类别区分能力。

使用TF*IDF可以计算某个关键字在某篇文章里面的重要性，因而识别这篇文章的主要含义，实现计算机读懂文章的功能。

这篇文章讲的挺详细http://www.ruanyifeng.com/blog/2013/03/tf-idf.html

（4）互信息(MutualInformation)

http://www.voidcn.com/article/p-rmksqitq-sg.html

http://www.cnblogs.com/polugen/archive/2006/11/29/576213.html

http://blog.sina.com.cn/s/blog_6255d20d0100ex51.html

http://hi.baidu.com/kuizeng/item/2f66cb0556f64c3ef2eafc26

互信息计算公式：

平均互信息：

一张图足以说明问题了。

（5）期望交叉熵(Expected Cross Entropy)

交叉熵反应了文本类别的概率分布与在出现了某个词条的情况下文本类别的概率分布之间的距离。词条的交叉熵越大，对文本类别分布影响也就越大。所以选CE最大的K个词条作为最终的特征项。

http://www.cnblogs.com/zhangchaoyang/articles/2655785.html

（6）信息增益方法(Information Gain)

（7）遗传算法(Genetic Algorithm,GA)

遗传算法的概念、算法描述及理论基础 http://blog.itpub.net/15203236/viewspace-615603/

遗传算法入门到掌握（一）http://www.voidcn.com/article/p-wuwawnzi-um.html

用遗传算法让电脑写宋词http://www.cnbeta.com/articles/110762.htm

非常好的理解遗传算法的例子http://www.voidcn.com/article/p-xuwtgjqc-uq.html

遗传算法入门http://www.cnblogs.com/heaad/archive/2010/12/23/1914725.html

特征选择常用算法综述http://www.cnblogs.com/heaad/archive/2011/01/02/1924088.html

遗传算法在文本特征选择中的应用研究 http://www.doc88.com/p-4184726156442.html

（8）模拟退火算法(Simulating Anneal，SA)：

大白话解析模拟退火算法http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html

模拟退火法求解TSP问题(MATLAB)http://blog.chinaunix.net/uid-9177504-id-2435124.html

http://blog.sina.com.cn/s/blog_4bc179a80100dl9i.html

POJ 2420 模拟退火http://blog.sina.com.cn/s/blog_64675f540100sehz.html

poj1379 模拟退火http://www.voidcn.com/article/p-otnjpsgo-yg.html

模拟退火（SA） http://blog.163.com/qianshch@126/blog/static/4897252220101048524568/

（9）N—Gram算法

这个跟本文的主题倒是不相关，但是很有趣~！~！用Ngram Viewer通过词汇探索历史，你也可以~ http://www.guokr.com/post/344966/

1980年-2008年，英语书中love出现的词频概率趋势图

Love在减少又反弹了~

中文书中“爱”的趋势图

爱在增加又减少了……

ngram模型中文语料实验step bystep(1)-分词与统计http://www.cnblogs.com/rocketfan/archive/2011/01/02/1924065.html

N-gram模型介绍http://hi.baidu.com/jasonlyy/item/49c1c0855f319722110ef32b

N-Gram学习笔记 http://blog.sina.com.cn/s/blog_623e3c050100m31g.html

转自：http://blog.sciencenet.cn/blog-995625-803323.html