通过确定邻近区域改进KNN文本分类.pdfVIP

计算机系统应用 2009年第11期 通过确定邻近区域改进KNN文本分类① KNNforTextClassificationDomain Improving byAdjacent 汪成亮1。2张硕果1 (1．重庆大学计算机学院重庆400030；2．重庆大学电气工程学院重庆400030) 摘要：文本分类技术已经成为处理和组织文本信息的关键技术之一。KNN算法是文本分类中一种实用的方法。 它在每次分类的过程中都要计算测试集中未标记文本与训练集合中所有样本的相似度(距离)，然后通过 排序来找到K个最近邻样本，耗时较长，不利于Web上实时在线分类等应用。提出了一种确定邻近区 域来加快搜寻K个最近邻的方法。试验证明，改进后的KNN算法较经典KNN算法在分类过程中速度 有所提升，并且当训练文本数量增加时，在分类时间上表现相对更稳定。 关键词：文本分类k一最近邻邻近区域相似度kNN算法 1 引言 2．2文本的表示 文本分类是指根据文本内容将文本归入预先定义 常用的文本表示方法是向量空间模型法(VSM)， 的类别。随着可用电子文档的增长和在线信息的快速 即将文本表示为特征词组成的特征向量，这里称为文 膨胀，文本分类技术已经成为处理和组织文本信息的 本的特征词向量。本文中，特征权重的计算采用 关键技术之一11】。 TF—IDF方、法【4l： KNN文本分类算法首先确定k值，然后依据文本 矿(‘，p)×log(Nine,+o．01) 相似度找出k个最相似的训练文本，把测试文本指派 (1) ‘√∑阿(‘，D『)×log(帆+0．01)]2 给其中相似样本最多的一类【2】。 经典KNN算法在每次分类的过程中都要计算待 分类文本与样本集中所有样本的相似度(距离)，然后排 文本的总数，n。为训练文本集中出现tk的文本数。 序找出K个最近邻，速度较慢，并且当训练集中文档 2。3特征选择 样本的数量增加时，计算量也随之上升，这不太适合 由于向量空间的高维性会导致分类时运算量过 于在线Web文档分类等技术的应用【3】。 大，因此需要有效的特征选择方法来进行特征选择以 本文针对此提出通过确定测试文档的邻近区域来 降低向量空间的维度。常用的方法有信息增益、CHI 加速K个最近邻查找过程的方法。试验证明改进后的 统计、互信息和期望交叉熵等。 KNN算法在速率上有所提升，并且当测试文档数量增 本文采用信息增益方法进行特征项提取，公式【5】 加时分类时间能够保持相对的稳定。 如下： IG(t)=-T．．P(CJ)log尸(cf) f-j 2中文文本分类方法 2．I文本预处理 +P(f)∑P(cft)logP(C,lt) (2) I=1 文本预处理包括去除停用词等。由于中文文本词 T)IogP(C,I7-) +户(F)∑P(G 与词间没有天然间隔，还需要进行分词处理。 I ①基金项目：重庆市自然科学基金(CSl℃)(2007B