【朴素贝叶斯】实战朴素贝叶斯_代码实现_特征选择1

特征选择对于文本分类任务很重要，选的好了能够大大提高文本分类准确率。其实特征选择也没有多神秘。首先，不选择也是一种选择，把所有可能的特征类型都用来作文本分类也没有问题。其次，随机选择也是一种选择，效果还真不见得差到哪里去。第三，特征选择方法有很多：卡方选择、信息增益、tf/idf也行。这一篇，还是介绍最基本的卡方选择方法。

【基本原理】

卡方选择就是通过卡方公式计算某个特征与某个类别之间的关联程度；计算出的数值越大，关联程度越高。卡方计算本身有他的信息论含义，这篇文章就不累述了。

首先定义一些变量：

A：包含某个特征，并且属于某个类别的文档个数，例如：包含“足球”且属于“体育”类别的文档数。

B：包含某个特征，并且不属于某个类别的文档个数，例如：包含“足球”且不属于“体育”类别的文档数。

C：不包含某个特征，并且属于某个类别的文档个数，例如：不包含“足球”且属于“体育”类别的文档数。

D：既不包含某个特征，并且也不属于某个类别的文档个数，例如：不包含“足球”且不属于“体育”类别的文档数。

卡方统计量由以下公式计算：

chi-square-value = (A*D - B*C) ^ 2 / (A + B) * (C + D)

这四个变量的定义都非常显然，不用做特别的解释。需要注意的是，在实际的统计中，并不需要“明显”地将这四个变量都统计出来，除了A之外，其它变量是可以通过计算得到的——当然前提是，要统计边缘分布。这个，该怎么解释呢？我们想象一下，在一个平面上，有两个维度，横坐标表示不同的特征类型，纵坐标表示不同的类别。特征类型的数量和类别的数量都是一定的，所以在平面上，这两个维度构成了一个面积有限的长方形。在长方形区域的每个格子上面，都是当前特征与这个类别共现的文档的个数。假设我们关注的是第一个特征和第一个类别，A的值就是左上角的值。极端条件下，只有两个类别和两个特征类型，则A, B, C, D的分布如下图所示：

A	C
B	D

当知道边缘概率的时候，B, C, D的值都可以通过边缘概率与A的关系计算出来，计算公式如下：

B = 该特征类型在所有类别中出现的文档数 - A

C = 在某个类别中出现的所有的特征的文档数目 - A

D = 文档总数 - A - B - C

在上文中，计算卡方值的代码如下：

// 3. calculate the model parameters
// 3.1 the chi-square value as well as the post-probabilty
for (int i=0; i<iClassNum; i++)
{
	for (int j=0; j<iFeaTypeNum; j++)
	{
		double dA = ppChiMatrix[i][j];
		double dB = pFeaItemPriorProb[j] - dA; // currently pFeaItemPriorProb[i] == sum_i (ppChiMatrix[i][j])
		double dC = pClassPriorProb [i] - dA;  // currently pClassPriorProb[i] == sum_j (ppChiMatrix[i][j])
		double dD = (double)iTotalDocNum - dA - dB - dC;

		// the chi value 
		double dNumerator = dA * dD;
		dNumerator -= dB * dC;
		dNumerator = pow (dNumerator, 2.0);
		double dDenominator = dA + dB;
		dDenominator *= (dC + dD);
		dDenominator += DBL_MIN; // for smoothing
		ppChiMatrix[i][j] = dNumerator / dDenominator;

		// the post-probability: p(feature|class)
		ppPProbMatrix[i][j] = dA / pClassPriorProb [i];
	}
}

其中，ppChiMatrix记录的是文档个数，pFeaItemPriorProb和 pClassPriorProb记录的也是文档个数，对应的是边缘概率，他们的真实值在下段代码中才被计算出来。

写累了，卡方选择还有一点细节问题，下一篇再说。