北邮郭军2016web搜索第二章.ppt

* WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC * WIR WIF WIC 常用核函数 多项式核函数 径向基函数 Sigmoid函数 特征选择 文本聚类和文本分类都以词作为基本特征来描述文档 高维文档特征不仅带来高额的运算开销，而且会产生由训练样本不足所导致的模型不可靠或失效的问题 特征降维非常重要，特征选择是方法之一 两类特征选择算法 包含算法: 从空集开始选择越来越多好的特征，直到适当为止 排除算法: 从初始特征集开始逐步排除差的特征，直到适当为止 包含算法 算法 1) 对每个词，计算其类区分性测度 2) 按区分性测度对词进行降序排序 3) 保留最好的n个词作为特征用于表达文档 各个词的类区分性一般是独立计算的，因此这类算法具有贪心(greedy)的特点 区分性测度是关键 常用测度包括χ2、互信息、Fisher鉴别指数等 χ2 测度 以二类问题为例，设 k00, k01分别为不包含/包含词t的类0中文档数 k10 , k11分别为不包含/包含词t的类1中文档数 n = k00 + k01+ k10+ k11 P(C=0) = (k00+k01) / n … 定义 χ2越大，类与词之间的相关性也越大 互信息 通过互信息计算文档类与词之间的相关性 互信息通过P(x,y)对P(x)P(y)的偏离程度对随机变量之间的依赖程度进行测量 如果随机变量X和Y相互独立，则对于所有的取值x和y P(x,y)/P(x)P(y)=1 因此，定义互信息为 Fisher鉴别 以二类学习问题为例，令X和Y分别表示一类向量的集合。向量的元素可以是令向量长度归一的实数 Fisher鉴别在寻找一种映射α*，它使得X和Y两个数据集被映射到二者质心间的距离相对集合内数据的展开幅度达到最大的方向上，即 令S = (SX+SY)/2，当S-1存在时，α = S-1 (μX-μY) 是一个解 Fisher鉴别指数 Fisher鉴别是一种变换，具有破坏特征稀疏性的特点 将每个词t都看作为一个候选的方向，即令 　αt = (0,…,1,…,0)T，即1只在词t的位置出现，定义t的Fisher鉴别指数为 由于αt的特殊形式，上式可简化为 　 对于多类问题 　 排除算法 排除算法从全部词特征集T开始逐步对“无用”特征进行排除，直至获得一个满意的特征子集F 排除算法的核心思想是尽量保持P(C?|T)与P(C|F)的相似性，因为分类与聚类可以基于类(C)的后验概率分布来设计算法 P(C?|T)与P(C|F)的相似性可用KL距离来度量 排除算法 如果P(P=p|Q=q，R=r) = P(P=p|R=r)，则称P