文本特征提取遇到的困难
- 特征维数太大
- 很多词是冗余的 -> 停词表
- 对于高维的向量空间，覆盖所有的特征词是很困难的
- 训练样本容量一定时，过大的特征空间会导致样本系统统计特性的评估变得更加困难。
文本分类系统
一般来说，一个完整的文本分类系统通常包括如下几个主要阶段:
文本预处理 -> 文本表示 -> 维数约减(包括特征抽取和特征选择) -> 分类器的学习 -> 分类器的测试以及性能评价
预处理：包括对文档集合进行格式分析并提取出重要内容，中文分词、英文词干化、剔除停用词等操作。对于英文的预处理技术相对比较成熟，对于中文来说，分词是最具有挑战性的难题。目前处理方法有基于词典的方法、基于自然语言处理的方法和基于统计的方法。
文本集合的表示：将文本看成是出现在文本中的关键词的集合，这些关键词就是原始特征项。为了能让计算机处理文本信息，通常将这些文档集用向量空间模型(Vector Space Model: VSM)来表示。
维数约减：这个包含两方面的内容：
(1)特征抽取,也就是原始特征空间的转换。从广义上讲是这指一种变换，原始特征的数量一般都很大，也就是说它们处于高维空间，通过映射或者变换将它们用低维空间来表示。
(2)特征选择。维数约减不单单是使向量的维数缩小，也可以通过剔除那些对类别区分作用不大的特征词，保留区分作用较大的特征词来更好的表示一个文本。
有效的降维约减，不仅仅可以提高分类算法的运行效率，而且可以大大提高分类的精度。
训练分类器：文本分类的核心。根据训练集中的文档至类别的关系映射规律，利用一定的算法对该训练集合进行统计或者有指导的学习，确定分类器的各个参数或者是阈值，最终构造一个分类器 $\phi ^ {‘} : Doc *Cat \rightarrow \{True,False\}$。Doc表示文档，Cat表示类别
分类器的测试：用分类器对测试集文档集合进行分类，确定测试集合中每一篇文档所属的类别，得到分类结果。
分类器性能的评价：采用一定的指标，对分类结果进行评价。不符合要求时，需要返回到前面的某一步骤，重新再做。
本文主要针对的是维数约减的特征选择部分
特征选择
特征选择问题陈述
向量空间模型一般选择原始文本中的词汇作为特征项，这样形成的文本向量维数非常大，文本自动分类的速度难以提高。不仅如此，原始特征空间中还含有许多干扰噪音，它们会影响最后的分类准确性。另外，高维的特征空间将直接带来数据稀疏的问题，同时大大增加机器学习的时间和空间复杂度，导致所谓的”维数灾难”。
现有的特征选择方法主要是借助统计学、信息论等方法对特征与类别之间的关系进行分析，选择包含类别信息较多，对分类贡献较大的若干特征项。
目前比较成熟的特征选择方法:
- TF-IDF
- 信息增益 （Information Gain）
- 期望交叉熵 (Cross Entropy)
- 互信息 (Mutual Information)
- 文本证据权 (Weight of Evidence)
- 几率比 (Odds)
- 卡方统计量
特征选择评价指标
采用不同的特征选择算法，如果最终的分类效果较好，则认为该特征项选择算法较优。因此，评价一个特征选择算法，通常是这么做的。将特征选择算法的输出用于分类器的训练，然后用分类效果来评价该特征选择算法的优劣。
文本分类从根本上说是一个映射过程，所以评估文本分类系统的标志是映射的准确程度。评估映射准确程度的参照物是通过专家思考判断后对文本的分类结果。与人工分类结果越相近，分类的准确程度就越高，这里隐含了评估分类系统的一个指标：准确率。它表示所有判断的文本中与人工分类结果吻合的文本所占的比率。
(1)准确率(precision) = 分类的正确文本数 / 实际分类的文本数
分类系统的另外一个基本评测指标是查全率，表示人工分类结果应有的文本中分类系统吻合的文本所占的比率。计算公式如下：
(2) 查全率(recall) = 分类的正确文本数 / 应有文本数
| 真正属于该类j的文档数 | 真正不属于该类j的文档数 | |
|---|---|---|
| 判断为属于该类j的文档数 | a | b |
| 判断为不属于该类j的文档数 | c | d |
准确率: $p_j = a/(a+b)$
查全率:$r_j = a/(a+c)$
准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可以偏废，因此，存在$F_j$测试值，表示为
$$
F_j = 2p_jr_j / (p_j + r_j)
$$
$F_j$只是考察了某一个类别的性能，考虑综合性能，对所有的F求一个宏平均即可
$$
Macro-F = \frac{1}{m} \sum_{j=1}^m F_j
$$
Macro-F值越大，说明分类效率越好，也证明特征选取的效果很好。
遗传算法在文本特征中的应用
遗传算法简单介绍
遗传算法的基本思想是仿效生物进化与遗传，根据“生存竞争”和“优胜劣汰”原则，借助选择，交叉，变异等遗传操作，使所要解决的问题从初始解一步步地逼近全局最优解。
这种算法的主要特点不仅是采用群体搜索策略和可实现群体中个体之间的信息交换，且搜索过程不依赖于梯度信息。它尤其适用于处理传统搜索方法难以解决的复杂和非线性问题。
同时，遗传算法具有内在学习性。学习是一种有选择保留的行为。知识通过反复实践获得。学习是演化过程自身所具有的不可与其分割的行为方式。与自然演化过程类似，而这些学习方式又内在地体现在演化的整个过程中。
(1) 宗亲学习(phylogenetic learning): 这种学习发生在整个演化过程中，祖先的良好特性通过遗传传递给后代，后代通过家族成员“血缘”继承方式学习其先辈的自适应行为。
个人认为这一步对应的是遗传算法中的 选择 ，大自然总是选择适应度高的个体生存下来
(2)社团学习(sociogenetic learning): 这种学习是一些经验和知识在某个社团(group)内的共享，体现在演化计算中即是独立群体内部知识或结构的共享。
个人认为这一步对应的是遗传算法中的 交叉，个体之间通过交换了某段基因，相当是某个社团内的共享信息
(3)个体学习(ontogenetic learning): 这种学习是自然界发生的最为频繁的一种行为。生物体为了生存，就必须进行学习。通过不断实践来积累知识和经验，以增强自己的适应性，演化计算的个体学习方式是通过改变个体的基因结构来提高自己的适应度。
个人认为这一步对应的是遗传算法中的 变异 ，个体为了适应大自然在不断地变异，变异差的被淘汰，变异效果好的就存活了下来
遗传算法具有可以获得全局最优解、隐含并行性和群体搜索等特点，近年来在机器学习、模式识别、图像处理、神经网络、工业优化控制和社会科学等方面得到广泛的应用，是一种全局启发式寻优算法，在解决优化组合问题方面有独特的优势。
遗传算法文本特征选择的关键技术
编码方案
采用传统的二进制编码，文本特征选择问题中，就是在特征空间对于每个特征判断其是否被选择，也就是0，1。假设特征空间大小为m，编码就相当于$B^{m} = {0,1}^m$。然后在位串空间上进行遗传操作。结果再通过解码过程还原进行适应值的评估。
这种编码方案编码简单，交叉变异操作便于实现，搜索能力强且产生的新个体不受父个体所构成的超体的限制。而且，从直观上来说，一篇文档由若干特征词汇构成，一个特征词汇出现或者不出现在最优特征项集合中，这与一个染色体由若干基因构成，每个基因只有0，1两种选择。
群体规模和初始种群的生成
群体规模是演化算法的很重要的一个控制参数，有时它对算法的性能可能会起到关键性的影响作用。如果群体规模太小，则群体内缺乏足够的多样性，算法可能收敛过快，易于陷入局部最优解；而如果群体规模过大，则算法的计算量增大，会浪费很多计算资源，等待结果的更新要花费太长的时间。
有研究指出，群体规模一般取个体编码长度的一个线性函数，通常群体规模大致取 $n = \mu m $ , m表示特征空间大小，$\mu$为介于1和2之间的常数。
适应度函数(评估函数)的构造
自然界中，个体的适应值即是它的繁殖能力，它将直接关系到其后代的数量。在遗传算法中，适应函数是用来区分群体中个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的唯一依据。改变种群内部结构的操作皆通过适应值加以控制，因此适应度函数是遗传算法实现的关键，直接影响到遗传算法的收敛速度及能否找到最优解，不同的适应度函数往往得到不同的优化特征子集，适应度函数与要解决的问题空间密切相关。
Reference
[1] (遗传算法在文本特征选择中的应用研究)[http://www.doc88.com/p-4184726156442.html]
