最近邻方法wangyu

关于文本分类的研究王煜文本挖掘概述文本数据的特点：•半结构化或者无结构化•高维数据•大数据量•时变数据•语义性•无标签•分布式文本挖掘的功能主要包括：•文本总结•文本分类•文本聚类•关联分析•分布分析•趋势预测文本挖掘概述•本挖掘面临的研究课题•文本的表示特征经典的文本表示模型是向量空间模型•空间降维问题•基于评估函数的方法:通常是通过在训练数据集上的统计来计算每一特征的某种指标值，根据指标值的高低决定是否保留相应的字或词，或者对相应特征加权，从而实现特征选择。主要有互信息、信息增益、词频法[、CHI概率统计、期望交叉熵、几率比和文本证据权•潜在语义索引:利用概念标引代替关键词标引，从语义相关的角度为文本选择标引词，而不考虑标引词是否在文本中出现，其通过奇异值分解将词频矩阵转化为维数极大减小的奇异矩阵，用转换后的文本向量进行文本挖掘处理。•主成分分析法:通过搜索最能代表原数据的正交向量，创立一个替换的、较小的变量集来组合属性的精华，原数据可以投影到这个较小的集合。•还有一些常见的文本降维算法，主要包括基于文档频率方法、基于分类频率和文档频率方法、IDF×TF方法，模拟退火算法等，文本挖掘概述•文本相似性度量问题•模式的理解和可视化显示•一词多义和多词一义问题•跨语言问题•算法的选择•领域知识集成•中文文本分词技术文本分类方法概述文本挖掘中最基本的两项工作就是分类和聚类，几乎在所有文本挖掘的应用领域都离不开文本的分类和聚类。文本分类是文本挖掘的一个重要内容，是指按照预先定义的主题类别，为文档集合中的每个文档确定一个类别。通过自动文本系统把文档进行归类，可以帮助人们更好地寻找需要的信息和知识。在人们看来，分类是对信息的一种最基本的认知形式。传统的文献分类研究有着丰富的研究成果和相当的实用水平。但随着文本信息的快速增长，特别是Internet上在线文本信息的激增，文本自动分类已经成为处理和组织大量文档数据的关键技术。现在，文本分类正在各个领域得到广泛的应用。但是，随着信息量日趋丰富，人们对于内容搜索的准确率、查全率等方面的要求会越来越高，因而对文本分类技术需求大为增加，如何构造一个有效的文本分类系统仍然是文本挖掘的一个主要研究方向文本分类方法概述文本分类方法主要包括基于传统技术的决策树、K最近邻（KNN）、关联规则、支持向量机（SVM）、基于数据库的算法、贝叶斯等分类算法和基于软计算的神经网络、粗糙集、模糊逻辑和遗传算法。其中，基于软计算的方法通过协同工作提供一种灵活的数据处理能力，其目标是实现对不精确、不确定、部分信息的处理能力和近似推理能力，以求能方便、稳健、低代价地逼近人类的分析判断能力。模糊逻辑提供处理由于模糊而不是随机产生的不精确、不确定性的算法，粗糙集则处理由于不可分辨关系导致的不确定性，神经网络用于模式分类与聚类，而遗传算法则用于优化和搜索。文本特征的降维方法基于模式聚合和改进统计量的文本降维方法基于CHI值原理和粗糙集理论的属性约减的文本降维方法基于神经网络的文本特征抽取方法2基于模式聚合和改进统计量的文本降维方法改进的统计量CHI的主要思想是认为词条与类别之间符合分布，词条的统计量表示词条对某个类别的贡献大小。统计量越高，词条和类别之间的独立性越小、相关性越强，即词条对此类别的贡献越大。统计量的计算公式22222)()()()()(22122111222112112211222112nnnnnnnnnnnnnχij2基于模式聚合和改进统计量的文本降维方法改进的统计量词条和类别的相关性是有正反两种情况的：当＞0，词条和类别正相关当＜0，词条和类别负相关改进的统计量2221122211nnnn21122211nnnn21122211nnnn21122211nnnn2)()()()()(n)(signχ2212211122211211221122211211222112ijnnnnnnnnnnnnnnnn基于模式聚合和改进统计量的文本降维方法改进的统计量一般特征的CHI值为该特征对所有类别的统计量的平均值或最大值。在改进的统计量上，规定词条的CHI值为：2222}χ,...,χ,χmax{CHI2is2i22i1i}χ,...,χ,χmax{CHI2is2i22i1i基于模式聚合和改进统计量的文本降维方法基于模式聚合理论的特征降维基于改进的统计量和模式聚合方法的特征降维步骤如下:•计算每个词条对每类的改进的统计量。•计算出各个词条的CHI值。然后把特征按CHI值由高到低进行排序，选取CHI值大的前M个特征词条，则由此得到的特征矩阵具有M个模式。•为比较各个模式对各类分类贡献比例是否一致，首先将每个模式的改进统计量统一处理到[-1,1]之间，处理方式如下：22}χ,...,χ,χmax{CHI2is2i22i1i22min)/(max2ijijχAmin)/(max2ijijχAmin)/(max2ijijχA基于模式聚合和改进统计量的文本降维方法•采用凝聚的层次法聚类算法，根据对模式进行聚类（的每行表示一个模式）。将欧氏距离小于一定阈值的模式进行聚类；•重新计算每个特征项的CHI值，根据CHI值大小选择前L′个特征项仿真实验1无模式聚合仿真实验1、传统统计量和模式聚合的仿真实验2、改进的统计量和模式聚合的仿真实验32}χ,...,χ,χmax{CHI2is2i22i1i22基于模式聚合和改进统计量的文本降维方法2}χ,...,χ,χmax{CHI2is2i22i1i仿真实验1仿真实验2仿真实验3测试样本数量300300300正确识别样本数量216252271错误识别样本数量844829分类正确率72%84%90.33%决策树建树时间30分43秒3分17秒3分2秒抽取规则数量1875251抽取最大规则长度1072425基于模式聚合和改进统计量的文本降维方法仿真实验12}χ,...,χ,χmax{CHI2is2i22i1i基于模式聚合和改进统计量的文本降维方法仿真实验22}χ,...,χ,χmax{CHI2is2i22i1i统计量和分枝合并的模糊决策树方法采用改进的统计量和分枝合并的模糊决策树方法测试样本数量320320正确识别样本数量229289错误识别样本数量9131分类准确率71.56%90.31%抽取规则数量12991抽取最大规则长度1103122基于CHI值原理和粗集理论的特征抽取特征抽取的具体步骤为：•⑴计算出每个特征词条和类别的统计量；•⑵指定正整数L，选择对每个类别贡献最大的L个词条，并按照统计量由大到小设置成一列。J个类别就有J列，最终得到一个L×J矩阵A，是对类别j按统计量由大到小排列在第i位的词条。•⑶将矩阵A中的特征词条按行排成一列。若有相同特征词条，则将后面的特征词条删除，得到一个特征词条有序表S，假设S含有R个特征词条。222ijAijA基于CHI值原理和粗集理论的特征抽取•⑷根据特征词条有序表S中的每个特征词条是否出现，得到决策表。•⑸对决策表的属性进行约简，进一步抽取特征。若共含有R个特征词条，约简步骤为：•①令REDUCT为空，i←1;•②REDUCT←REDUCT∪•③如果REDUCT为决策表的属性约简，约简结束；否则，如果iR，令i←i+1,转步骤②，如果i=R，属性约简失败。•⑹若不能得到属性约简，则将正整数L适当增大，转步骤⑵，否则特征抽取结束。it基于CHI值原理和粗集理论的特征抽取•仿真实验经济教育军事体育娱乐测试样本篇数8080808080正确分类篇数7471726970分类精度92.5%88.75%90%86.25%87.5%基于神经网络的特征选择灵敏度求解•将整个训练样本库中的样本作为前馈神经网络的训练样本，得到了一个神经网络分类器。此分类器对训练样本库的样本h分类的预测值为。•计算每个特征的灵敏度：对每一个特征，训练样本中所有样本的第个特征的值均改为0，其他特征值不变，形成新的样本库Bi，然后在样本库Bi的基础上，按照重新训练神经网络分类器，此时神经网络分类器对训练样本库的样本h分类的预测值为。则可根据公式计算特征的灵敏度：0hpihp基于神经网络的特征选择基于神经网络的特征选择基于神经网络的特征选择算法的具体步骤为：•⑴设定允许误差为e；•⑵将所有特征按照灵敏度由大到小进行排序，形成队列，此时特征数量为m；•⑶i←1；j←m；R←m；nhhihhipppnS1001基于神经网络的特征选择•⑷mid←[(i+j)/2]//[]表示取整数•⑸取队列前mid的特征作为训练样本的新的特征向量空间，去掉其余的特征，形成新的样本库C。•⑹按照新的样本库C建立新的神经网络分类器，分类器对样本库C中所有样本分类的误差之和为ce。•⑺如果ce≤e则i←mid-1，R←mid；否则j←mid+1。•⑻如果i＜j，转向第⑷步执行。•⑼将队列中后面的特征从样本的特征向量空间中删除，得到新的特征向量空间。•⑽整理样本库，将样本库中样本按照新的特征向量空间表示，形成新的样本库。基于神经网络的特征选择•仿真实验基于神经网络的特征选择基于模糊决策树的文本分类规则抽取方法度量连续属性离散化性能的类信息熵基于模糊决策树的文本分类规则抽取方法密度分布函数基于模糊决策树的文本分类规则抽取方法对样本集的属性求隶属度函数的个数k和中心点集C的算法步骤如下：•确定k的可能最小值kmin和最大值kmax;•fork=kmintokmaxdo：•将属性a的值域根据基于类信息熵的离散化方法划分成个不相交的区域，步骤如下：•初始化区间TE，TE为属性a的值域；j←1；•寻找将区间TE划分成两部分TE1，TE2且划分后的类信息熵E(TE1,TE2)最小的划分点；j←2；基于模糊决策树的文本分类规则抽取方法•③用②的方式分别求出每个区间TE1,TE2,…,TEj的最小化分点，并计算出其类信息熵，选择满足信息熵最小的区域进行划分；j←j+1•④重复第③步直到满足j等于k•求出k个区间中心集合，方法为：求出密度分布函数最大的点作为区间的隶属度函数的中心点。•求出F-统计量•选择令F-统计量最大的k和C为属性隶属度函数的k和C。基于模糊决策树的文本分类规则抽取方法一•所有样本的集合作为根结点，给定叶子判定标准δ；•createtree过程主要分两步：•I．计算结点所有类别的相对频率，若有超过给定标准δ或无测试属性可以选择，则该结点为叶子；•II．若不为叶子结点，计算此结点祖先中未曾使用过的属性的分割模糊熵，选择分割模糊熵最小的属性作为此结点测试属性，根据此测试属性在此结点上产生分枝；每个分枝再分别递归调用createtree过程构造各个分枝。•对模糊决策树进行分枝合并•条件一：每个分枝具有完全相同的树型结构；•条件二：相同位置的内部结点的测试属性相同；•条件三：相同位置的叶结点的代表的类别相同。基于模糊决策树的文本分类规则抽取方法二仿真实验基于特征权重修正的改进KNN方法一DKNN算法的距离公式：计算每个特征对第个类的统计量和每个特征的CHI值，求出特征j对第i类的分类作用影响因子根据灵敏度方法求得各个特征的权重法确定距离公式jijijχACHI/22mjjiiSSw1/mjjijhjjiyxAwyxD12))(1(),(基于特征权重修正的改进KNN方法一•仿真实验基于特征权重修正的改进KNN方法一