及与动态规划的文本特征选择.pptx

基于动态规划的文本特征选择算法 年级：2012级 专业：计算机应用技术 研究方向：网络与信息安全 DPFS算法 Contents 文本特征选择 动态规划 1 2 3 漫画图像与自然图像的区别 漫画图像 自然图像 线条 边缘清晰 受光线、角度、纹理影响，边缘难以准确检测 纹理 纹理稀少 纹理丰富 结构 结构清晰 与拍摄内容有关 颜色 种类较少，区域内部颜色过渡平缓、线性 颜色变化规律性差、复杂 文本特征选择 文本特征选择是文本分类过程中的一个关键技术和核心步骤，是根据某个准则从众多原始文本特征中选择部分最能反映模式类别统计特征的相关文本特征。 文本特征选择算法是利用某种评价函数独立地对每个原始文本特征项进行评估，然后将它们按评估值的大小按降序排序，从中选取若干个评估值最高的文本特征项。 文本特征选择 互信息（MI），反映了文本特征与类别之间的相关程度，互信息越大，文本特征的出现就只依赖于某一种类别，当MI=0时，文本特征与类别相互独立；当互信息是负数时，文本特征就很少在该类别中出现。 特征t与c类文档之间的互信息MI（t , c)的定义如下： 其近似计算公式为： 其中A为特征t与文档c类同时出现的次数；B为特征t出现而c类文档不出现的次数；C为c类文档出现而特征t不出现的次数；N为文档总数。 如果t与c相互之间独立，那么MI(t , c)为0。 文本特征选择 期望交叉熵，是一种基于概率的方法，反映了文本类别的概率分布和在出现了某个特定词汇的条件下文本类别的概率分布之间的距离，特征词w的交叉熵越大，对文本主类别分布的影响也越大。 其中, P(Ci|w)表示文本中出现特征词w时，文本属于Ci的概率；P( Ci)是类别出现的概率。 如果特征词和类别相关，也就是P(Ci|w)大，且相应的类别出现概率又小，则说明特征词对分类的影响大，相应的函数值就大，就很有可能被选中作为特征项。 文本特征选择 度量两个对象之间的相互性 体现了特征项与类别的相关程度 只计算出现在文档中的词汇 反映了文本类别的概率分布和在出现了某个特定词汇的条件下文本类别的概率分布之间的距离 互信息没有考虑特征出现的频率，会导致互信息评估函数不选择高频的有用词而有可能选择稀有词作为文本的最佳特征 文本特征选择 动态规划 找出最优解的性质，并刻画其结构特征 以自底向上的方式计算出最优解 递归定义最优解的值 根据计算最优解过程中得到的信息，构造最优解 动态规划四步骤 动态规划 DPFS算法 特征冗余，一般是以文本特征的关联来确定，如果两个文本特征的数值完全的相互关联，那么它们彼此是冗余的，实际上，当一个文本特征与一组文本特征部分地相互关联的时候，不可能直接决定该文本特征是冗余的。 C - 相关，任何的文本特征Fi和类别 C 之间的相关度叫做C - 相关，用RMI（i,C）表示。 F - 相关，文本特征Fi和Fj（i ≠ j）之间的相关度叫做F - 相关，用RMI（i,j）表示。 DPFS算法 DPFS算法 DPFS算法 DPFS算法主要是针对高维文本数据的特征选择，在算法开始前先对所有文档进行预处理，如去除一些在文本出现频率对文本没有区分作用并且干扰关键词所起作用的词汇。 因为DPFS算法利用了动态规划的思想，保存了已经解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量重复计算。 DPFS算法不仅能选择出近似最优的文本特征，而且通过减少计算量来提高运行时间。