基于决策树和K最近邻算法的文本分类研究

文本分类是文本挖掘的重要内容,是对信息的一种最基本的认知形式。目前的文本特征降维算法、改进或创造适应文本数据的分类算法、抽取文本分类规则等方面的研究仍远远不能满足实际的需要。本文主要研究了文本特征空间的降维问题、利用决策树抽取文本分类规则问题和改进KNN算法以适应文本分类问题。 本文提出了三种特征降维方法:一种是基于模式聚合和改进χ2统计量的文本降维方法,有效地降低文本维数并可提高分类精度;一种是基于CHI值原理和粗糙集理论的属性约减的文本降维方法,据此提出的基于决策树的文本分类规则获取方法,可获得分类精度较高且易于理解的文本分类规则;第三种是基于神经网络的特征抽取方法,此方法根据灵敏度将特征进行排序,采用二分法的方式去掉部分特征,降低了神经网络特征提取的计算量。 本文提出了两种基于模糊决策树的模糊文本分类规则抽取方法。第一种方法采用分枝合并减少了分类规则,第二种方法提出了一种基于类信息熵和密度分布函数的数据模糊化方法,降低了数据模糊化的工作量和模糊决策树的规模,减少了分类规则数量。 本文关于KNN算法的改进主要做了三个方面的工作: 欧氏距离中的权重求解问题:提出了两种权重求解方法。一种采用灵敏度方法获得每个文本特征对分类作用的权重,并且在距离公式中又加入了同一特征对不同文本类的分类作用的权重;第二种是基于chi-square距离理论的权重求解方法,首先根据SS-Tree划分的区域查找近似k0个最近邻,根据k0个最近邻和chi-square距离理论计算权重。这两种方法都可以提高KNN算法的分类精度。 提高K个最近邻查找速度:提出了一种快速查找精确K个最近邻的算法TFKNN,预先建立SSR-Tree,SSR-Tree的每个非叶子结点的孩子按照其距父结点中心点的距离排序。根据这棵树进行K个最近邻的查找,只需在满足一定条件内的部分样本中查找K个最近邻,从而减小了查找范围,大大降低了相似度计算量。 裁减样本库:提出了一种KNN算法中的训练样本库的裁减维护方法,首先采用CURE算法对训练样本库进行聚类,获得每个聚类的代表样本组成新的训练样本集合,然后用tabu算法对此样本集合进行进一步维护。此算法不仅极大缩减样本库裁减的工作量,且使KNN算法的分类速度和分类精度都得到了提高。