文本特征选择的关键算法总结

 

 

一、特征词选择与特征词权重关系

 

开始学文本分类的时候经常要搞晕特征词选择和特征词权重 这两个东西，因为两者都要进行量化，很容易认为特征词选择就是计算权重，因此我认为有必要先搞清楚这两个概念。

两者的区别 ：特征词选择是为了降低文本表示的维度，而特征词权重是为了表示文本表示中每一个特征项的重要程度。

特征词的选择算法 有：文本特征选择的算法有基于文档频率 (Document Frequency) 、信息增益 (Information Gain, IG) 、开方拟和检验方法 (CHI 统计 ) 、互信息 (mutual Information) 、潜在语义分析LSA、期望值交叉算熵、文本证据权、 term strength(TS) 、 GSS Coefficient 、 odds ratio等；

特征词的权值 （即所谓的文本表示）计算有：TF-IDF，TF的改进，信息熵的引用等^[1] 。这个将在下篇进行分析一下。

 

二、特征词权重选择方法分析

 

以下分别分析一下特征词的选择算法，由于信息增益是很有效的特征选择方法，因此，将给出信息增益的java代码。

1. 基于文档频率（DF）

 

 

 

在文档频率方法中，使用特征词在一个类别中出现的文档数来表示这个特征词与该类别的相关度。出现的文档数多的特征词被保留的可能性大。显然，文档频率方法实现最简单、算法复杂度最低，而且 DF 方法与其他几种方法的分类性能也差不多。

计算公式：DF_term ：特征词term在某一类中的所有文档出现的次数。

改进公式：^[2]

 

缺点：待补充

 

2. 互信息 (mutual Information)

 

在互信息算法中，采用计算特征词 t 和类别 c 之间的相关度：

其中， A 为在类别 c 中特征词 t 出现的文档数； B 为在除了类别 c 的其他类别中特征词 t 出现的文档数； C 为在类别 c 中特征词 t 未出现的文档数； N 为所有类别中的文档数的总和。如果共有 m 个类别，那么每个特征词将得到 m 个相关度值，取这 m 个值的平均值作为每个特征词的权值，权值大的特征词被保留的可能性大。

 

缺点：待补充

 

3. 信息增益 (Information Gain)

 

 

信息增益 (IG) 是公认较好的特征选择方法，它刻画了一个词语在文本中出现与否对文本情感分类的影响，即一个词语在文本中出现前后的信息嫡之差。某个词语的信息增益值越大，说明它对分类的贡献就越大。信息增益的计算见公式：

 

 

P(Ci) ，表示类别 Ci 出现的概率，其实只要用 1 除以类别总数就得到了（这是说你平等的看待每个类别而忽略它们的大小时这样算，如果考虑了大小就要把大小的影响加进去）。

P(t) ，就是特征 t 出现的概率，只要用出现过 t 的文档数除以总文档数就可以了

P(Ci|t) 表示出现 t 的时候，类别 Ci 出现的概率，只要用出现了 T 并且属于类别 Ci 的文档数除以出现了 T 的文档数就可以了^[3]

 

 

 

	/**
	 * @param j
	 * @return double
	 * 
	 */
	private double getFirstPart(int j) {
		double sum = 0;
		for (int i = 0; i < C; i++) {
			//log2(P(cj)) = ln(P(cj))/ln(2);
			sum += P_C(i) * (Math.log(P_C(j)) / Math.log(2));
			
		}
		return -sum;
	}

 

 

	/**
	 * @param j
	 * @return double
	 * TC[][] represents the number of documents including the term j and belonging to Classification j
	 */
	private double getSecondPart(int j) {
		double sum = 0;
		//P_Tj represents P(tj) which is the probability of the documents including term j  
		//That is , P(tj) = documents including term j / the total number of documents
		double P_Tj = this.P_t(j);
		for (int i = 0; i < C; i++) {
			if (TC[j][i] == 0)
				TC[j][i] = 1;
			//log2(TC) = ln(TC)/ln(2);
			sum += (double) TC[j][i]
					* ((double) Math.log(TC[j][i]) / (double) Math.log(2));
			
		}
		return P_Tj * sum;
	}

 

 

 

 

 

	/**
	 * @param j
	 * @return 　 double
	 * 
	 */
	private double getThirdPart(int j) {
		//p(tj) = 1 - p(t_barj)
		double P_t_bar_j = this.P_t_bar(j);
		double sum = 0.0;

		//T_barC = number of classifications -  number of docs including Term i and belonging to Classification j
		for (int i = 0; i < C; i++) {
			if (T_barC[j][i] == 0)
				T_barC[j][i] = 1;
			sum += (double) T_barC[j][i]
					* ((double) Math.log(T_barC[j][i]) / (double) Math.log(2));
		}

		return P_t_bar_j * sum;
	}

 

缺点 ：信息增益最大的问题还在于它只能考察特征对整个系统的贡献，而不能具体到某个类别上，这就使得它只适合用来做所谓 “ 全局 ” 的特征选择（指所有的类都使用相同的特征集合），而无法做 “ 本地 ” 的特征选择（每个类别有自己的特征集合，因为有的词，对这个类别很有区分度，对另一个类别则无足轻重）。

4. 开方拟和检验方法 (CHI 统计 )

 

开方检验最基本的思想就是通过观察实际值与理论值的偏差来确定理论的正确与否。

 

 

缺点：待补充

 

5. 潜在语义分析LSA

LSA思想方法最初应用于文本信息检索领域有效地解决了同义词和多义词的问题,通过识别文本中的同义词, LSA将信息检索精度提高了10%--30%

随着应用领域的不断拓展, LSI在信息过滤、信息分类/聚类、交叉语言检索、信息理解、判断和预测等众多领域中得到了广泛的应用。（语义，降维）^[4]

 

计算奇异值矩阵，可以通过maltab svd 命令来解。

 

缺点：待补充

 

 

 

 

 

 

 

 

 

 

 

 

参考资料：

 

[1]. 冯长远, 普杰信 Web 文本特征选择算法的研究

[2]. 杨凯峰，张毅坤，李燕  基于文档频率的特征选择方法

[3]. http://tech.ddvip.com/2009-03/1237883850112130_4.html

[4]. 杨建武 文本特征提取技术

 

 

 

CSDN:http://blog.csdn.net/techq

百度：http://hi.baidu.com/futrueboy/home

javaeye：http://futrueboy.iteye.com/

 

联系方式：[e-mail]