i
W% ∈ H d × p ，是一个二元矩阵，每列有且仅有一 由于 个非零元素，那么： c nj % TS W% ) = p W% TS W% = p trace(W w (Alki − M jki )2 ∑i=1 i w i ∑i=1 ∑ j=1 ∑l =1
只要根据 ∑ cj =1 ∑ ln=1 (Alk 即可
进一ห้องสมุดไป่ตู้工作
当选取的特征数比较少的时候，微平均值相对比 较低，特征的类内分布分数受那些稀有词的影响 比较大，如何消除稀有词带来的噪音。
– 通过与投影寻踪或者是卡方统计量特征选择方法进行 组合。 – 进一步合理化和优化类别信息的目标函数
请各位老师、同学指正 请各位老师、 谢谢! 谢谢!
p p c
nj
n 现在问题变成：找到p个特征，由这些特征生成的 变换矩阵能够最大化（a）式，这等价于根据
(M jki − M ki ) 2
（a）
∑
c j =1
nj n
找前p个最大值
(M
k j
− M k ) 2 , k = 1, 2, ...d
类别信息特征选择
OCFS算法仅仅考虑了特征对类间离散程度的贡 献，而特征对类内离散程度的影响却被忽略。 这里，我们目的也是要找到一个变换矩阵 W% ，使 % TS W% ) 最小，其中 S w = ∑ ic=1 ∑ nj =1 (A j − M i )(A j − M i )T 得 trace(W w
n i i 2 第四步：计算各个特征对类内分布的贡献 sw (i) = ∑ j =1 ∑ l =1 (Al − M j )
第五步：计算各个特征的最终分数 s (i ) = sb (i ) sw (i ) 第六步：在分数集合 S = {s (i ) 1 ≤ i ≤ d } 中选取前 p 个数最大的特征
常用的特征选择方法存在的问题
– 卡方统计量和信息增益都是贪心算法，寻求满意解
基本思路
正交质心算法
从特征选择的角度来优化特征提取算法
OCFS算法 算法
考虑特征对类内分布的影响
类别信息特征选择
目标是：用一组特征来表示文档集合，在这组特 征的表示下，类别与类别之间的分散程度达到最 大，类别内文档的离散程度达到最小。 OCFS算法使得类别之间的离散程度最大，但是 没有考虑类内文档的聚集程度。 利用LDA的两个目标函数来刻画类间分布与类内 分布。优化这两个目标函数，并且进行综合，得 到最后对特征评分函数（即特征对分类信息的贡 献）
j
i
− m ki ) 2 , ki = 1, 2,...d j
找前p个最小的
第一步：计算训练集中各个类别的质心 M i i = 1, 2,...c 第二步：计算整个训练集文档的质心 M 第三步：计算各个特征对类间分布的贡献 sb (i) = ∑ j =1
c
c
nj n
(M ij − M i ) 2
j
LDA的目标函数 LDA的目标函数
类间分布矩阵：
Sb = ∑
j =1
c
nj n
(M j − M )(M j − M ) T
类内分布矩阵：
S w = ∑i=1 ∑ j =1 (Aj − M i )(Aj − M i )
c
ni
T
OCFS算法 OCFS算法
思想：在OR算法的基础上，从特征选择的角度来 优化特征抽取方法。 OC算法目的是，通过对类别中心矩阵进行QR分 解，从连续的空间中找到一个变换矩阵 W ∈ R d × p ， 使得文档向量 X i ∈ R d 变换成 Y i ∈ R p (p<<d) 定理：求OC算法的解等价于下面的优化问题， arg max J (W ) = arg max trace(W TS bW ),
试验结果
文档集：Reuters-21578，共135类，保留训练集 和测试集都有正例的90个类。 特征选择方法：卡方统计量、OCFS以及本文提 出的类别信息特征选择方法。 特征权重：LTC权重 分类器：SVMLight以及KNN分类器 性能指标：宏平均F1和微平均F1
表2 SVM分类结果 分类结果
2006年度全国搜索引擎和网上信息挖掘会议
文本分类中的类别信息特征选择方法
余俊英 王明文 盛俊 江西师范大学
2006年7月21日
提纲
研究背景 基本思路 OCFS算法 类别信息特征选择算法 实验结果 进一步工作
研究背景
文本分类的特点
– 数量巨大的训练样本 – 高特征维数
特征降维技术
– 特征提取：主成分分析、线性判别分析、潜在语义索 引 – 特征选择：文档频数、信息增益、期望交叉熵、互信 息、文本证据权、几率比、卡方统计量等
subject to W TW = I
从特征选择的角度考虑，在离散的空间求变换矩 阵，便转换成这样一个优化问题： J (W% ) = arg max trace(W% TS W% ), W% ∈ H d × p
b
设为 W% 二元矩阵，每列有且仅有一个非零元，则：
trace(W% TS bW% ) = ∑ i =1W%i TS bW%i = ∑ i =1 ∑ j