基于信息增益的文本特征选择方法

基于信息增益的文本特征选择 计算机科学 . 第刍.誊。.篓期 。 蕊 』年月 。???????????????????????????????????????????一 基于信息增益的文本特征选择方法 任永功杨荣杰尹明飞马名威 辽宁师范大学计算机与信息技术学院 大连 摘要在类和特征分布不均时,传统信息增益算法的分类性能急剧下降。针对此不足,提出一种基于信息增益的文 本特征选择方法。首先对数据集按类进行特征选择,以减少数据集不平衡性时特征选取的影响。其次运用 特征出现概率计算信息增益权值,以降低低频词对特征选择的干扰。最后使用离散度分析特征在每类中的信息增益 值,过滤掉高频词中的相对冗余特征,并对选取的特征应用信息增益差值做进一步细化,获取均匀精确的特征子集。 通过对比实验表明,选取的特征具有更好的分类性能。 关键词特征选择,文本分类,信息增益值,冗余特征,不平衡数据集 中图法分类号. 文献标识码 , , , , , . . , ,., . ,. , , . . , , , , 下移走高达%的“无用”单词,但是此算法考虑到全局变 引言 量,在处理不均衡数据时性能急剧下降,并缺少对选取特征的 随着的迅猛发展,网络信息迅速增加,文本分类成 进一步筛选。因此为提高 算法的性能,本文不仅考虑不平 为处理和组织大量文档数据的关键技术,但其高维特征空间 衡数据集以及低频词对特征选择的影响,还去除高频冗余特 不仅增加了分类的时间复杂度和空间复杂度,还影响分类精 征来降低特征维度,选择区分类别强的特征子集,使分类效率 度。特征选择通过降低特征空间维度以及去除噪音特征来提 和精度得到明显提高。 高分类效率及精度。常见特征选择方法有交互信息? 信息增益简介 ,、信息增益 ,、统计 量,、特征权 ,、期望交叉 .信息增益 熵,、文本证据权 定义信息增益, ,是某一特征在 ,、几率比 ,等。这些方法从不同的 文本中出现前后的信息熵之差。信息增益考虑特征出现与不 角度度量特征对分类的重要性。 出现时,特征对文本类别的信息表示量。以信息量的多少作 特征选择是一种有效的特征选择方法,如文献提 为特征的权值,进而筛选特征。 ? 出是最好的测度之一;文献比较了 一??/ ,文档频率、、、及 种特征选择方法,其 /奶?/,/聊 中以效果最好,、和之间存在很大的相关性; 定义中,表示类别总数,表示特征在文本中 文献比较了、、 种特征选择算法,表明 出现的概率,表示类文本在文本集中出现的概率, 能提取更优的特征子集。在不降低文本分类性能的前提 到稿日期;?卜 返修日期:?? 本文受国家自然科学基金项目,教育部留学回国人员科研启动基金资助项目,辽 宁省科技项目,辽宁省教育厅高等学校科研基金,大连市优秀青年科技人才基金资助。 任永功一,男,博士,教授,主要研究方向为数据挖掘、图像处理技术等,:.;杨荣杰一,女,硕士生,主要研究方向 为数据挖掘;尹明飞一,女,硕士生,主要研究方向为数据挖掘;马名威一,男,硕士生,主要研究方向为数据挖掘与并行计算。? 万方数据表示文本包含特征时属于,类的条件概率, 由定义得:的值为.,毗的值为.,珊的值 勋表示文本中不包含特征的文本的概率,/表示 为.。从结果可知数据集平衡程度严重影响了特征的提 文本不包含特征时属于,类的条件概率。 取,相对于劬具有更强的类区分性,但根据权重值筛选 根据 教授对英文文本分类中特征选择算 特征,?更容易被过滤掉。 法的深入研究,可得特征选择。 定义信息增益选择 分别计算每类中特征 的信息增益值,以避免数据集不平衡时信息增益选取特征覆 一?/?孑芦/弋一雨 盖不全的缺点。 /?石万/于 /。架丽/ 在信息增益中,分类系统负载信息量的大小是衡量特征 重要性的。负载量越大,特征越重要。因此选择值大 ?两万/奶 的特征构成分类特征子集来提高系统的分类效率。 定义中表示特征在,类中出现的概率, .信息增益的不足 奶表示特征在,类中不出现的概率。由定义得,在 虽然算法是有效的全局特征选择算法,但针对不均衡 类中砒的值为.,劬的值为.。在类中毗 数据集,算法对小样本集抽取概率降低,减少了小样本集 的值为,的值为.。因为分类选取贡献率大的特征, 的特征提取概率。它考虑特征出现与不出现两种情况,对于 所以中的劬、中的都将被提取,以减少不平衡数据 小数据集,不出现的特征权值将产生主导作用,因此很难提取 集对选择特征的影响。本文从每类中提取权重大的前个 小样本集特征。其次算法倾向于提取高频特征,忽略了提 特征组成分类特征子集,使其覆盖所有类别。 取特征间的相关性,缺少对特征子集的进一步筛选。 .减少低频特征的影响 鉴于现实生活中不均衡数据集的普遍存在,为广泛应用 虽然降低了数据集不均衡对特征选择带来的影响,但是 算法,需进一步优化算法。针对算法只适用于全局 信息增益算法本身还存在不足。 变量的缺陷,文献?分别采用不同方法对等特征选择 信息增益特征选择公式考虑了特征出现和不出现两种情 算法进行改进,提出适用于不平衡数据集的新算法。但是文 况,因而在去除“无用词”时,效果显著。但特征不出现时.对 献中当类的重叠度较小且存在类不平衡时,此算法精度会 文本分类的贡献远小于对分类的干扰,特别在类和特征分布 下降,且适用范围小,没有普遍性;文献通过、、 高度不均的情况下,低频词不出现的概率远大于出现的概率, 以及 种特征选择的组合,得到适应不平衡数据集的特 即雨》。此时信息增益值是由公式后半部分决定 征选择方法,但是它的限制条件很多,适应性差;文献用 的,其大大降低了提取特征的效果。 替换来降低不平衡数据集中低频词对选取特征性能的 假设有,,, 类,含有个样本,而后类 影响。文献虽然降低了数据集不平衡时低频词对选取特 都只含有个样本。有两个特征项:,。表示特征出 征的影响,但是没从根本上降低不平衡数据集的影响。文献 现,表示特征不出现,如表所列。 利用词频信息提高、及的性能,但对提取特征仍 需进一步处理进行降维,以提高分类的性能。 表特征文档分布情况 基于传统算法以及文献算法的不足,本文从三 特征项丁??了争蔫 方面对算法进行改进,提出一种改进的信息增益特征选择 方法。一方面对数据集进行分类特征选择,减少不平衡数据集对特征选取的 影响。另一方面使用特征出现概率计算信息 由定义可得:的值为.,毗的值为.。根据 增益权值,以降低低频词对特征选择的干扰。最后利用离散 中特征权值,比砒具有更佳的分类效果。但由表可 度分析在每类中特征的信息增益值,对提取特征做进一步细 知,对的区分性能更好。因此公式应筛选出本类中 化,过滤掉高频词中的冗余特征,获取均匀精确的特征子集。 出现次数多而在其它类中不出现的特征。 基于信息增益的改进算法 定义改进信息增益特征选择函数。考虑特 征出现时,特征对文本类别的信息表示量。以信息量的多少 . 改善不均衡数据集的影响 作为特征的权值,进丽筛选特征。 信息增益只考察特征对整个系统的贡献,而不能具体到 某个类,因此它只适用于做“全局”的特征选择,而无法做“本 ?/。%斧?/ 地”的特征选择。例如有,,, 类,前类都含有 个样本,含有个样本。有个特征项:撕,,勘。表 、, 示特征出现,表示特征不出现,如表所列。 由定义得,的值为一.,砒的值为.时,能 表特征文档分布情况 对特征进行更好的筛选。不仅选取出对本类信息量贡献大的 特征,而且在特征与类分布高度不均的情况下,减少了低频特 茕征项 征对特征权重的影响。函数比传统提取特征的性能得到一定的提高,减 少了低频词的影响,但还需要对提取的特征进行冗余处理,选 万方数据择更优的特征子集来进一步提高分类性能。 /聊、 丽? .去除高频特征的冗余 ?在每类中选取权值最大的前个特征。 在分类选取特征过程中,由于分别计算每个类中特征的 循环结束。 值,使得特征集合中出现重复特征,因此需先删除重复特 将选取的所有特征删除重复特征后,放人特征子集 征,然后对特征集合迸行冗余处理。 龇。 信息增益值的波动大小可以衡量特征对于分类存在冗余 从到循环 的程度。信息增益权值波动越大,表明特征在每个类中的文 ?根据定义,对选取特征暇,,,?,.算离敖 本表示值差异越大,剜特征值对应到每个类的中心值距离就 度: 越远,对文本分类就越精确。反之,则很难对文本进行分类。 例如训练集中的特征“促进”在教育、政治、哲学和历史个类 ??;一面 当三旦??????一 中的值分别为.、.、。、.。通过观察信 息增益值发现,以平均值.为中心,每个类的信息增益值 ?将舢特征子集中值.的特征存人&缸特 的波动很小。特征在个类中的向量值集中在以平均值为中 征子集。 心的区域内,特征“促进”很难对测试集中的样本进行类别区 循环结束。 分。因此高频特征“促进”属于冗余特征,需从特征子集中删 根据定义,计算特征子集中特征的值: 除。 ?~碱 定义基于的信息增益特征选择函数 将划特征子集中值.的特征存人特 使用离散度来计算特征在每类中值的波动大小。 征子集。 离散度是衡量一组数据波动大小的重要量,通过数据方差计 输出酬特征子集。 算。 为降低不均衡数据集对特征选择的影响,分类计算特征 权重,并通过和对特征进行筛选,设置的 ??碘,一面。 阈值为.,的阈值为.。不同的训练数据计算出 声一三』兰???一 的权重值不同,则设置的阈值也不同。阈值太小,对特征筛选 定义中珂表示选取的特征总数,毗表示第个特征在 没有意义;阈值太大将过分筛选,删除对文本分类重要的特 第类的取值,面表示第个特征在所有类中值的 征。本文经过多次对比实验,选择使实验结果最佳的阈值对 平均值,表示文本类别数。 特征进行筛选。最后使用选取的特征进行分类实验,以验证 特征选择最终筛选的是本类中出现概率大且其它类中不 本文改进的特征选择算法的有效性。 出现的特征。但特征离散度衡量的是特征在所有类中的整体 波动性,并不能精确表示具体类与类之间的信息增益值变化。 实验结果及分析 定义基于的信息增益特征选择函数 .性能评测 利用特征在类间的最大信息增益值与第二信息增益 文本表示采用变形的公式,如式所示: 值的差值对选取的特征做进一步筛选,从而选择更精 确的分类特征子集。 训,:????丝血型?~, 一声虹 。 ..糍 八,唱 定义中表示第个特征的的差值,四 表示第个特征在类中的最大信息增益值,髓 。嗜鼎 表示第个特征在类中的第二大信息增益值。 式中,,表示文档中特征训的词频,动表示文档 。值越大,表明特征越集中出现在~类中,特征对 中的词数, 表示平均每个文档中的词数,表示集 此类的区分度越强,对该类的贡献率就越大,因此增加一 合文档中总的词数,竹?,表示出现过特征,的文档数。 限制函数对特征傲进一步筛选。特征选择函数与 经变形后的文本采用分类器进行分类.分 是对特征冗余的深层分析,能达到去除高频冗余特 类器中文本间距离采用距离进行测量。文本分 征、降低特征维度、提高分类性能的效果。 类的评测指标采用文本分类评测标准中的平均准确率、平均 . 算法描述 召回率和值。各评价参数定义如下: 首先利用算法对训练数据集按类进行特征权值计 平均准确率 算,然后根据选择信息增益值波动大的特征,最后使用 分类的准确率分类正确文本/分类的实际文本数 对特征进行筛选。算法描述如下。 三?只 从到循环: ?初始化每个特征的权重即叫 式中,咒为总的分类数,为第类的准确率。 ?根据定义,对类中所有特征一,,?,训分别 平均召回率 计算权值并更新权值: 分类的召回率一分类正确文本/分类应有的文本数 缸一?芝?, 一/%浮/仍 ,一 ?】? 万方数据