基于互信息的用于文档分类的并行特征选择方法

摘要

本发明的基于互信息的用于文档分类的并行特征选择方法，包括a).选取样本并分类；b).求解词的TF‑IDF值；c).生成初始化数据集合D＝{x₁,x₂,...,x_N}；d).分布式计算，将所有子数据集平均分布到m个计算节点上；e).建立集合，S＝Φ，V＝{X₁,X₂,...,X_M}；f).计算联合、条件概率分布；g).计算互信息；h).选取特征变量；i).判断数量是否已够；j).文本分类。本发明的文档分类的并行特征选择方法，基于瑞利熵的互信息被用来度量特征变量与类变量之间的相关性，使得最终选取的特征变量的更能代表文档分类的特征，分类效果更准确，分类结果要好于目前常用特征选择方法得到的结果，有益效果显著，适于推广应用。

主权项

一种基于互信息的用于文档分类的并行特征选择方法，其特征在于，通过以下步骤来实现：a).选取样本并分类，选取N篇文档，形成训练样本集合D＝{d₁,d₂,...,d_N}，d_i为选取的单篇文档；采用人工划分的方式每个文档进行分类，形成类变量集合C＝Y＝{c₁,c₂,...,c_p}，文档d_i的种类必属于类变量集合C；b).求解词的TF‑IDF值，TF‑IDF是词频tf(t,d)和逆文档频率idf(t,D)的乘积，对于每个文档中的每个词计算求解其TF‑IDF值；在所有文档中如果某个词的TF‑IDF值都小于临界值m，则该词属于低频词，将其忽略掉；c).生成初始化数据集合，以每个文档中词的TF‑IDF值为向量，组成初始化数据集合D＝{x₁,x₂,...,x_N}，x_i为文档i中所有被选中词的TF‑IDF值所组成的向量；d).分布式计算，将数据集合D＝{x₁,x₂,...,x_N}平均分成n个子数据集D₁,D₂,…,D_n，然后将所有子数据集平均分布到m个计算节点上，以确保较高的计算速度；设要选择出数目为k的词变量集合；e).建立集合，假设S和V为两个集合，设S＝Φ，V＝{X₁,X₂,...,X_M}，S表示已被选择的特征，V表示没被选择的特征，M表示特征变量个数；f).计算联合、条件概率分布，对于每个没有被选中的词变量X_i，计算联合概率分布p({S,X_i})和条件概率分布函数p({S,X_i}|C_j)，i∈{1,2,...,M}，M表示特征变量个数；j∈{1,2,...,p}；p({S,X_i})表示某一文档中待判断的特征变量X_i与已选中的特征词集合S之间的联合概率分布；g).计算互信息，通过公式(1)计算{S,X_i}与类变量Y之间的互信息I({S,X_i}；Y)：I({S,X_i}；Y)＝H({S,X_i})+H(Y)‑H({S,X_i},Y)    (1)其中，i∈{1,2,...,M}，M表示特征变量个数；每个计算节点计算完毕后，本次计算中使互信息I({S,X_i}；Y)具有最大值的特征变量X_i作为选中词；h).选取特征变量，统计每个计算节点所返回的特征变量X_i和相应的互信息，被选中次数最多的词X_i作为本次计算所要选择的特征变量；如果两个变量被选中的次数一样多，则选择互信息值的和最大的特征变量作为计算所要选择的特征变量；把本次计算中选取的词变量X_i从集合V中去除，将其增添至集合S中，执行步骤i)；i).判断数量是否已够，判断集合S中所选取的特征变量的数目是否达到了设定的k个，如果达到，则停止运算；如果没有达到，则跳转至步骤f)，继续进行特征变量的选取；j).文本分类，利用所选取的k个特征变量作为支持向量机的输入对文本进行分类，具有很高的准确率；其中，步骤f)中所述的联合概率分布和条件概率分布通过以下步骤来实现：f‑1).假设一组训练文档样本用(x_i,c_i)表示，i＝1,2,…,N,x_i是文档中所有TF‑IDF值组成的向量，其中每个文档的向量值和对应的类变量值都已知，通过公式(5)计算概率分布函数：$p\left(x\right)=\frac{1}{{\left(2\pi \right)}^{M/2}|\hat{\Sigma }{|}^{1/2}}\exp (-\frac{{(x-\hat{\mu })}^T\hat{\Sigma }(x-\hat{\mu })}{2})---\left(5\right)$其中，参数μ和∑的极大似然估计分别通过公式(6)和公式(7)进行求取：$\hat{\mu }=\frac{1}{N}\underset{k=1}{\overset{N}{\Sigma }}{x}_k---\left(6\right)$$\hat{\Sigma }=\frac{1}{N}\underset{k=1}{\overset{N}{\Sigma }}(x_k-\hat{\mu }){(x_k-\hat{\mu })}^T---\left(7\right)$f‑2).最初的数据集合被分成q部分，每部分的大小为N_j，它满足类C＝c_j的概率分布函数为：$p\left(x\right|c_j)=\frac{1}{{\left(2\pi \right)}^{M/2}|{\hat{\Sigma }}_j{|}^{1/2}}\exp (-\frac{{(x-{\hat{\mu }}_j)}^T{\hat{\Sigma }}_j(x-{\hat{\mu }}_j)}{2})---\left(8\right)$f‑3).离散类变量的概率分布函数通过统计方法计算，即：$P\left(c_j\right)=\frac{N_j}{N},j=1,2,...,q---\left(9\right)$f‑4).X和C＝c_j的联合概率分布函数为：$\begin{array}{c}p(x,c_j)=p\left(c_j\right)p\left(x\right|c_j)\\ =\frac{N_j}{{\left(2\pi \right)}^{M/2}N|{\hat{\Sigma }}_j{|}^{1/2}}\exp (-\frac{{(x-{\hat{\mu }}_j)}^T{\hat{\Sigma }}_j(x-{\hat{\mu }}_j)}{2})\end{array}---\left(10\right)$将变量{S,X_i}代入公式(10)和(8)即可求取联合概率分布函数和条件概率分布函数。