（计算机软件与理论专业论文）基于可信最邻近分类器的文本分类的研究.pdf

j 瘟变通厶堂亟堂位i 幺奎虫塞摘要 中文摘要 摘要；直推式可信最邻近分类器( t c m n n ) 是基于算法随机性理论提出的 一种新的分类算法，它不仅能够判断样本的类别，还能够为每一个判断提供可信 度，这对于分类机器的应用是很有意义的。但因为这种分类器需要将每一个待分 类样本逐一在所有的类别中进行计算，使得计算量大大的增加。这一点对于多类 别和大数据量的文本分类尤为明显。本文在深入研究该算法的基础上，利用聚类 分析对其进行了改进，并将这一算法及其改进后的算法用在文本分类中。实验表 明改进后的算法和原算法相比准确率相近，但在计算速度上有了大幅度的提高。 关键词：可信度：k n n ；聚类；文本分类 分类号：t p 3 9 1 4 j e 塞窑通太堂硒堂僮i 金奎旦51b ! a b s t r a c t a b s t r a c t ：t r a n s d u c t i v ec o n f i d e n c em a c h i n ef o rkn e a r e s tn e i g h b o r si san e w a l g o r i t h mb a s e d o i la l g o r i t h m i cr a n d o m t h e o r y i tn o to n l yc a ng i v ep r e d i c t i o n s ，b u ta l s o c a n p r o v i d ec o n f i d e n c ef o re v e r yp r e d i c t i o n , w h i c hi ss i g n i f i c a t i v ef o rm a c h i n el e a r n i n g h o w e v e r , i ta l w a y sn c e , d $ ag r e a td e a lo fc a l c u i a d 日咀f o re v e r yt e s te x a m p l em u s t c a l c u l a t ew i t he v e r yc l a s s e s p e c i a l l yu s i n g0 1 1t e x tc l a s s i f i c a t i o nw i mm u l t i c l a s s e sa n d g r e a td a t u m i no u rt e x t ，w ei m p r o v et h ea l g o r i t h mb yu s i n gc l u s t 盯m e t h o d ，a n dt h e n u t h e mf o rt e x tc l a s s i f i c a t i o n a c c o r d i n gt ot h er e s u l t s t h ei m p r o v e da l g o r i t h mh a sa s i m i l a ra c c u r a c yt ot h eo l da l g o r i t h m ，b u tam u c hs m a l l e rt i m ea tt h es a m et i m e k e y w o r d s ：c o n f i d e n c e ；k n n ：c l u s t 盯：t e x tc l a s s i f i c a t i o n c l a s s n 0 ：t p 3 9 1 4 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：矗纵超 导师签名： 签字r 期：z 唧年1 2 月7 7 日 彩雾 签字同期：9 年， ，月7 r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：舡锁超 签字只期： 川年1 2 月碍日 北京交通大学 2 0 0 7 年1 2 月 致谢 本论文的工作是在我的导师赵宏教授的悉心指导下完成的，赵宏教授严谨的 治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来赵宏 老师对我的关心和指导。 感谢计算机学院的老师们，它们不仅教给我知识，更重要的是，他们严谨的 治学精神、勤奋踏实的工作作风时时刻刻激励着我。在这样一个治学严谨的氛围 中，我的学习和科研能力逐渐提高。 感谢实验室的所有师兄、师姐和同学，感谢他们在实验室工作及撰写论文期 问的交流指导和帮助。在此向他们表达我的感激之情。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 韭塞窆道太堂亟堂僮论塞曼i 直 1 引言 1 1 研究背景及意义 由于信息技术的飞速发展，i n t e r n e t 上的电子资源成指数方式快速增长，人 们通过因特网能很快地得到大量的资料，但同时不得不面对另一个棘手的问题一 一如何对所获得资料进行科学有效地管理，使得人们可以从浩如烟海的资料中迅 速得到有价值的信息。人工对这些电子资源进行归类、整理是人们最容易想到的 方法，但却是很不现实的。因为这不仅要耗费大量的人力、物力，而且还会花费 很长的时间，无法满足快速这一基本要求。在这种情况下，为了从含有大量数据 的集合中自动发现有效、新颖、实用的信息，将人类从繁重的重复性劳动中解放 出来，数据挖掘技术应运而生。 数据挖掘( d a t am i n i n g ) 又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，k d d ) ，是指从大型数据库或数据仓库中提取隐含的、未知的、潜在 有用的信息或模式，它融合了数据库、人工智能、机器学习、统计学等多个领域 的理论和技术“。 分类技术是数据挖掘的一种有效手段，而文本分类又是其中应用比较多的方 向之一。目前常用的文本分类技术有贝叶斯方法、支持向量机、神经网络、最邻 近分类方法等。这些方法在分类性能上有一定的差别，而且各有其特点，但是它 们却有一个共同的地方：无法提供每次判断的可信程度。即，这些方法通常只能 给出我们简单的预测分类结果，即某待分类样本的类别号，而不能提供该次判断 的可信度。虽然这些算法也提供了一些方法来评定其性能，如准确率，查准率， 查全率等等，但这些方法多是用测试集中的误差率来评估将要预测的数据集的误 差率，有很大的局限性；而且它们不能应用到每个样本的预测结果上。也有一些 学习算法用后验概率来估算判断的置信度，如b a y e s 算法能够输出后验概率进行 置信判断，但却需要建立在严格的假设条件之上。如果假设和实际情形出现偏差， 那结果就会和真实情况相差很远，甚至失去它的实际意义。而本文要研究的基于 算法随机性理论的直推式可信最邻近分类算法不仅可以为每个预测结果提供可信 度( c o n f i d e n c e ) ，为进一步的处理提供可靠的依据，而且它对学习的对象要求很 低，只要求其是独立同分布的，不必知道样本的分布类型和分布参数。 1 2 国内外研究现状 1 9 8 9 年8 月，在美国召开的第“界国际人工智能联合会议上首次出现数据库 中的知识发现( k d d ) 一词。在随后的几年里都召开过关于知识发现的专题讨论会。 后来随着参会人员的增多，逐渐发展为年会。根据最近g a r t n e r 的h p c 研究表明， “随着数据捕获、传输和存储技术的快速发展，大型系统用户将更多地需要采用 新技术来挖掘市场以外的价值，采用更为广阔的并行处理系统来创建新的商业增 长点”“”。所有这些都表明数据挖掘已经成为计算机科学界的一个研究热点。 国内外数据挖掘领域的众多专家、学者已经研究出多种有效的学习算法，并 且其中很多都已经得到了实际的应用。暂且抛开这些算法的整体性能及具体更加 适合的应用领域不提，其中大部分算法都有一个共性不能有效的计算可信度。 在9 0 年代末，a g a m m e r m a n ，v v o v k 等人就明确提出了这一观点“3 1 ，并且针对 此问题提出了置信学习机器理论。这种理论是根据算法随机性理论，利用随机性 检测函数，为学习机器建立一种置信机制。将该理论应用到具体的学习算法中， 就称之为置信学习机器。该算法在判断样本类别的同时，还能够给出该次判断的 可信程度，丰富了输出结果的有效信息，为进一步需要采取的处理措施提供了可 靠的依据。 但由于随机性检测函数通常是不可计算的，只能通过一定的方式近似得到”， 所以目前这一思想并不能应用在所有的数据挖掘算法中，主要可以应用到支持向 量机及最邻近算法中。其中支持向量机是通过拉格朗只乘子近似得到随机性检测 函数“】，而最邻近算法是通过用样本间的距离定义陌生度( s t r a n g e n e s s ) 来近似 得到。 我国早在9 0 年代就引进了数据挖掘技术，但目前无论在理论创新上，还是在 应用实践上都与国际水平有相当的距离。这是因为虽然我国起步并不晚，但由于 我国企业当时大多并没有建立完善的数据库系统，对数据挖掘领域的技术没有太 大的需求，所以该技术在出现了一段时问后就逐渐“冷”了下去，并没有受到足 够的重视。然而到了最近几年，随着我国经济的发展和国内企业的不断壮大，数 据挖掘技术越来越受到各大中型企业及科研机构的重视，已经成为计算机科学领 2 域的一大研究热点。 我国也不乏数据挖掘领域的人才和科研机构：如中国科学院的石勇教授，于 2 0 0 0 年开始将数据挖掘在银行信用征信评分概念介绍到国内；复旦大学计算机与 信息技术系国际数据库中心，本文所使用的实验平台就是来自该中心的中文文本 分类系统；又如北京大学计算语言学研究所等。 但是目前我国对置信学习机器的研究尚属少数，对这方面的应用研究也还处 于起步阶段。2 0 0 4 年，华中科技大学的邱德红，陈传波等人发表论文对最信学习 机制进行了详细的阐述，并将其用在心脏病理数据识别及签名认证试验中，取得 了良好的效果脯删。 1 3 课题研究的主要内容 因为本课题致力于用可信最邻近分类器对文本进行分类，且主要研究目的和 意义是为每个输出结果补充上相应的可信度，所以本文的主要研究内容如下： ( 1 ) 掌握文本分类的概念及其一般步骤和常用方法，重点研究文本特征表 示及特征选择的关键技术。 ( 2 ) 在理解算法随机性理论的基础上，具体研究基于直推式可信度的计算 方法和原理，重点探讨直推式可信最邻近分类算法( t c m n n ) ，理解其算法原理 和具体实现过程。 ( 4 ) 在深入研究直推式可信最邻近分类算法的基础上，采用与聚类方法相 结合的办法对其进行改进，在不影响其正确率的前提下提高它的分类速度，并输 出可信度等有效信息。 ( 5 ) 在不同的标准语料库上进行多次试验，以验证本算法的性能，并和其 他文本分类算法进行比较。 1 4 各章内容提要 第一章主要介绍了论文的选题背景、意义以及国内外相关的研究成果、进展， 并提出了本论文的研究方向和主要内容。 第二章对文本分类及聚类的相关知识进行了介绍，包括文本分类的一般步骤、 3 文本特征的表示、特征的提取，及各种聚类方法。着重论述了现今常用的向量空 间模型特征表示法及几种常用的特征提取方法。 第三章首先阐述了算法随机性理论，并在此基础上引出了基于该理论的置信 度理论，并做了具体的论述。在本章中还介绍了置信学习算法中两个重要的性能 指标c o n f i d e n c e 及c r e d i b i l i t y 的具体含义。 第四章首先详细介绍了直推式可信最邻近分类算法的基本原理和具体实现， 然后主要探讨如何对这一算法进行改进，并给出了详细的实现步骤。在此基础上 将最邻近分类算法、未改进的直推式可信最邻近分类算法及改进后的算法在标准 语料库上进行了详细的实验，并将实验结果进行了比较，然后对实验内容进行了 分析与总结。此章节也是本文的重点研究内容。 第五章给出了全文的总结，并对今后的工作提出了展望。 4 2 文本分类及聚类综述 分类和聚类是数据挖掘中最常见的两种知识模式。文本聚类和文本分类相比 最主要区别就是分类学习的样本或数据有类别标记，而要聚类的样本没有标记， 需要由聚类学习算法自动确定。分类方法是典型的有监督学习方法，它需要预先 定义一个训练集，即对文本集合进行人工分类，作为构造分类函数或分类模式的 基础；而聚类是典型的无监督学习方法，它要划分的类是未知的，不需要人工预 先确定训练文本类别。 2 1 文本分类 2 1 1 文本分类概述 文本分类( t e x tc l a s s i f i c a t i o n ，缩写为t c ) ，是指按照预先给定的主题类别， 为文档集合中的每个文档确定一个类别。这样，用户不但能够方便地浏览文档， 还可以通过限制搜索引擎范围来使文档的查找更为容易。利用文本分类技术可以 快速、有效地对大量文档进行自动分类。目前常用文本分类方法有贝叶斯方法、 支持向量机、神经网络、最邻近分类法等方法。 文本分类的一般步骤如下：文本的预处理( 包括文本的特征表示及文本特征 选择) ，实施文本分类，分类性能评估。具体的流程图见图2 1 。本节将主要介绍 文本的特征表示及特征选择的各种常见方法，其他的内容将在下面的章节中具体 阐述。 5 2 1 2 文本的特征表示 文本的 特征表示 文本特征选择 ： 图2 - 1 文本分类流样图 特征表示是指用特征项柬表示文本信息。这是一个从非结构化向结构化转化 的处理步骤，在文本分类时只需对这些特征项进行处理，从而实现对非结构化的 文本的处理，特征表示的构造过程就是挖掘模型的构造过程。特征表示模型有多 种，常用的有布尔模型、向量空间模型、概率型等。近年来应用较多且效果较好 的特征表示法是向量空问模型( v e c t o rs p a c em o d e l ，v s m ) 法。 在向量空间模型中，文本空间被看作是由一组j 下交词条向量所组成的向量空 间，每个文本表示为其中一个范化特征向量v ( d ) = ( t b w l ( d ) ；，t i ，w i ( d ) ；， t 。，w 。( d ”，其中t i 为词条项，w i ( d ) 为t i 在d 中的权重。由于t i 在文本中既可以重 复出现又应该有先后次序关系，分析起来有一定难度，为了简化分析，可以暂不 考虑t j 在文本中的先后次序并要求t i 互异( 即没有重复) 。这时可以把t i ，t 2 ， t n 看成一个n 维的坐标系，而w i ，、v 2 ，w 。为相应的坐标值，因此一个文本就 表示为n 维空间的一个向量，我们称v ( d ) = ( w l ，w 2 ，w 。) 为文本d 的向量表示 或向量空间模型。其中w i ( d ) 的计算方法有很多，如t f 方法、布尔方法、t f * i d f 方法等。 6 一一一一一一一 r，气，【厂l，、，l e 立窑垫厶仝亟! ：! j ! 位监塞塞奎筮娄缝星羞练墟 t f 方法巾w 是t 在文档i i j 现的次数。 在伽尔方法中w ，j l 取0 平l 两个值，即t 在文档中出现则w ，取l ，否则 耿0 。 t f * i d f 方法是一种常用的谢条权重确定方法。目前存在多种计算公式， 本文中采用了“种比较普遍的t f - i d f 公式： 矿( f ，孑) ：1 掣坚堕丝! 兰竺竺! 一 ( 2 1 ) 埘妙( f ，孑) l o g ( n n ，+ o ，0 1 ) r 其中，w ( t ，孑) 为词t 在文本孑中的权重，而矿o ，a ) 为词f 在文本孑 中的词频，为训练文本的总数，见为训练文本集中出现f 的文本数，分母为 归一化因子。 2 ，1 ，3 文本特征选择 常用的文本特征选择方法有：文档频率( d f ) 、信息增益( i g ) 、互信息( m i ) 、统 计量( c m ) ，期望交叉熵，文本证据权，优势率，z 统计( c h i ) 等。这些方法都 是基于阈值的统计方法，它们的基本思想都是对每一个特征计算某种统计度量值， 然后设定一个阈值，把度量值小于阈值的那些特征过滤掉，剩下的即认为是有效 特征。本文采用的是信息增益的特征选择方法。 1 文档频率 文档频率( d o c u m e n tf r e q u e n c y ) ，就是文档集合中出现某个特征项的文档数目。 在特征项选择中，计算每个特征项在训练集合中出现的频率，根据预先设定的阅 值排除那些文档频率特别低和特别高的特征项。文档频率的计算复杂度较低，随 训练集的增加而线性增加，能够适用于大规模语料，因此是特征降维的常用方法。 其基本原则是：很少出现的特征对分类价值极小，对整个分类系统的效果影 响也很小，因此，将这些特征去掉有助于降低特征空间维数，并且当这些不常出 现的特征为嗓音时，还会有助于提高分类正确率。但在信息检索领域，文档频率 较低的特征项被认为是信息含量较高，与文本分类中的原则是相反的。 2 信息增益 信息增益( i n f o r m a t i o ng a i n ) ，是种在机器学习领域应用较为广泛的特征 7 选择方法，也是本文采用的特征选择方法。它从信息论角度出发，用各个特征取 值情况来划分学习样本空间，根据所获取信息增益的多寡，来选择相应的特征。 其计算公式如下： t g ( 叨= 聊删啪暖乎+ 币晖删吼学沪2 ， 其中，p ( g i 形) 表示文本中出现单词形时，文本属于c f 的概率，同样p ( qi 矽) 表示文中不出现单词w 时文本属于g 的概率；p ( g ) 表示g 类文本在语料中出现 的概率；p ( ) 表示在整个文本训练集中出现的概率。 3 互信息方法 互信息方法( m u t u a li n f o r m a t i o n ) ，可以度量特征项和类别的共现关系，特 征项对于类别的互信息越大，说明特征中包含的与类别有关的鉴别信息就越多。 因此，互信息衡量的是词与类之间的相关程度。文本分类中，一个特征词只有一 个信息增益和文档频率，但拥有的互信息数目却是与训练语料中类别的数目相同 的，对应于每个类，该特征词都会有一个互信息值。一个词可以对应几个互信息 值，一般来说，因为我们的目的是选出对分类比较有用的词，所以通常根据每个 词最大的互信息值来排序，然后从高到低选择特征词或者设定一个阂值排除那些 互信息值比较低的词。 假设文档集合c 分为k 类，记为c ，c 一，c 。特征项对于文档类别e 的互 信息m i ( w ，g ) 的计算公式如下： m i ( w 矧岫g 需 一s ， 其中p ( 形，q ) 为特征项矽出现在类g 中的概率，p ( ，c ) 为特征项矿在所有 文档中的出现概率。 4 期望交叉熵 期望交叉熵( e x p e c t e dc r o s se n 仃o p y ) 与信息增益类似，也是一种基于概率的方 法，但是不同于信息增益对特征项属性的计算，期望交叉熵只计算出现在文本中的 特征项。其计算公式定义如下： 8 c e ( w ) = p ( w ) p ( c , iw ) l o g 等 ( 2 叫) 期望交叉熵没有考虑单词未出现的情况。如果词条和类别强相关，p ( qi ) 就 大，若p ( g ) 又很小的话，则说明该词条对分类的影响大，此时相应的函数值就大， 就有可能被选中作为特征值。交叉熵反映了文本类别的概率分布和出现了某种特 定词的条件下文本类别的概率分布之间的距离。词条的交叉熵越大，对文本类别 分布的影响也就越大。 5 z 统计 在文本分类中，特征w 的z 统计( c h i ) 权重如式( 2 - - 5 ) 所示。 z 2 ( 缈，0 = 两丽万n 万x ( a 而d - 而b c ) 2 而2 5 ) 其中，a 表示w 在c i 中出现的频度，b 表示w 在除c i 以外的其它类别中出现 的频度，c 表示除w 以外的其它词在c 。中出现的频度；d 表示除外的其它词在 除c i 以外的其它类别中出现的频度，n = a + b + c + d 。当特征项w 和类别c 之间完 全独立的时候，z 2 统计量为0 。z 2 统计和互信息的差别在于它是归一化的统计量。 2 1 4 文本分类器性能指标 对于文本分类，一般都用正确率、查准率、查全率或者是微平均、宏平均来 评价一个文本分类系统的性能。下面将给出简单的介绍，并分析它们的不足。 1 查准率及查全率 文本分类从根本上说是一个映射过程，评估文本分类系统的标志是映射的准 确程度和映射的速度。映射的速度取决于映射规则的复杂程度，而评估映射准确 程度的参照物是通过专家思考判断后对文本的分类结果( 这罩假设人工分类完全 正确并且排除个人思维差异的因素) 。与人工分类结果越相近，分类的准确程度 就越高。这里隐含了评估文本分类系统的两个指标：查准率( p r e c i s i o n ，简记为 p ) 和查全率( r e c a l l ，简记为r ) 。对于某一文档类别，它们分别定义为： p = 丽t p r = 丽t p ( 2 6 ) t p ：判断属于该类并且正确的文档数目；f n ：判断属于该类但错误的文档数 9 目；f p = 判断错误的本属于该类的文档数。 查准率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可 偏废。因此，存在一种新的评估指枥卜_ 测试值用，其数学公式如下： f l ：竺三( 2 7 ) r + p 2 微平均及宏平均 分类结果中对应于每个类都会有一个召回率和j 下确率，如何根据每个类的分 类结果评价分类器的整体性能，通常的方法有两种：微平均和宏平均。 微平均是指被正确分类的总文本数a 总，被错误分类的总文本数b 总，应当被 正确分类实际上却没有的总文本数c 总，根据j 下确率和召回率的公式直接计算出总 的正确率和召回率。宏平均是指首先计算出每个类别的正确率和召回率，然后对 i f 确率和召回率分别取平均得到总的j 下确率和召回率。微平均更多的受分类器对 一些常见类 p 一，贝uy 。l - + 1 ； 如果p + p ，但二者相差并不大，因此也就不 能做出判断说孙l 的值一定是+ l ，而- l 定不是新样本所在的类别。鉴于这一点 就有了c o n f i d e n c e 值存在的意义和必要性。 c o n f i d e n c e 的值为i - p 2 ，表示可以排除掉其他类别的可能性：若该值很大， 则其他类是新样本类别的可能性很小，那么根据c r e d i b i l i t y 的值做出的判断是可信 的；但若该值很小，则说明p 2 的值很大，那么p 2 所在的类别也在很大程度上可能 是新样本的类别，则根据c r e d i b i l i t y 的值做出的判断是不可信的。 相反，如果c o n f i d e n c e 的值很大，但c r e d i b i l i t y 的值很小，则说明最大的p 值所在的类别是，的可能性也很小，因此也不能判断此次所做的分类是正确的。 综上所述，c o n f i d e n c e 的值与c r e d i b i l i t y 的值相辅相成，二者配合使用则可以 为每次判断提供可信度；单独使用其中某一个值来判断没有实际意义。 2 t 4 直推式可信最邻近分类算法及其改进 直推式可信最邻近分类算法( t r a n s d u c t i v ec o n f i d e n c em a c h i n ef o rkn e a r e s t n e i g h b o r s ，简称为t c m - n n 算法) 是基于算法随机性理论提出的一种新的分类算 法【i 】，它不仅能够判断样本的类别，还能够为每一个判断提供可信度，丰富了输出 的有效信息，为进一步的处理提供了可靠的依据，这对于分类机器的应用是很有 意义的。下面先简单介绍一下最邻近算法的相关知识，然后再将置信度理论应用 到最邻近算法中，引出直推式可信最邻近分类算法，并进一步阐述该算法的思想 及具体实现，然后在此基础上提出对它的改进算法。 4 1 最邻近分类算法 最邻近算法( n e a r e s tn e i g h b o r ，简称n n ) 是模式识别非参数法中最重要的方法 之一，也是文本分类中一个比较典型的分类算法。最邻近分类器是基于要求的或 懒散的学习算法，即它只存放所有的训练样本，并不建立分类模型，直到新的待 分类的样本需要分类时才建立分类。这与诸如判定树归纳和后向传播这样的急切 学习算法形成鲜明的对比，后者在接受待分类的新样本之前就会构造一个一般模 型。遵循这样一个过程： 训练：训练集一 特征表示一 特征选取一 训练一 分类器 分类：新样本一 特征表示一 特征选取一 分类一 评价 i n n 是将所有训练样本都作为代表点，然后考察和待分类样本最相似的样本 所属的类别( 所谓的“相似性”通常是用样本问的距离来衡量) ，则待分类样本也 属于该类别。因此在分类时需要计算待识别样本x 到所有训练样本的距离。k n n 是i n n 的推广，即分类时选出训练文本集中与该新文本距离最近( 最相似) 的k 个样本，看这k 个近邻中的多数属于哪一类，就把x 分到哪一类。下面将用一个 例子来具体说明： 假设有两个类a 和b ，且类a 和类b 各有若干个训练样本；另有一个待分类 样本x ，如图4 1 所示。假设k 值为4 ，由图中可以看出，在这4 个与新样本x 距离最近的训练样本中，有3 个是类a 中的样本，1 个是类b 中的样本，则可以 判断样本x 属于类别a 。 0 口 口 窭 l 3 b 图4 - 1k 最邻近分类算法 当i t l 练样本增加时，k - 最邻近分类器具有较好的普遍性和较快的收敛速度，在 自动分类领域有着较多的应用。但是k n n 对训练样本库的容量要求比较大。因此 不适用于小样本情况下的自动分类，只对大的训练样本库有实际意义，但这样一 来计算量会比较大。 4 2 直推式可信最邻近算法 在上一节中我们已经简单了解了最邻近分类算法的思想，, g g z , 又该如何将置 信度理论和该算法结合起来呢? 在前面已经提到过，虽然置信度理论是以k o l m o g o r o v 算法随机性理论为基础 的，但由于其定义的随机性检测函数是不可计算的，因此本文是通过近似地实现 可计算的、又满足k o l m o g o r o v 随机性描述函数定义第一条意义的样本序列随机性 描述函数建立学习算法的置信度机制。下面就介绍一下如何以最邻近算法为基础 来实现这一理论。 4 2 1 随机性检测函数的确定 首先需要解决的问题是如何在最邻近算法中近似的得到可计算的随机性检测 函数。 一般说来，同类别的样本由于具有相似性，它们的特征向量在特征空间上的 分布具有聚集性，样本之间的距离比较j x ；不同类别的样本由于具有相异性，它 们的特征向量在特征空间上的分布具有分散性，样本之间的距离比较大。因此， 可以利用样本特征向量在特征空间上的距离来定义可计算的样本序列随机性描述 函数。 仍然只考虑分类的情况，且假设只有 + l ，- l 两种类别。 假设有一组训练集x ，共包含1 个样本： ( x l ，y 1 ) ，( x i ，y t ) ( 4 一1 ) 其中x i 是训练样本，y i 是相应样本的所属类别，y i + l ，一l 。设有一个新样 本x 。现在需要确定其所属类别。 现在定义以下几个表示符号： 表示样本i 与同类的其他样本的距离所组成的序列( 按升序排列) ； 4 t 表示样本i 与不同类的其他样本的距离所组成的序列( 按升序排列) ； 呓表示同类中，与样本i 的距离中第j 小的值； 表示其他类中，与样本i 的距离中第j 小的值； 其中，两个样本之间的距离用欧几晕得( e u c l i d ) 距离来描述： 破e t ，_ ，= l 五一l = ( 善l h 一颤f ) j 。4 2 ， 一般情况下，同类别的样本具有相似性，因此它们之问的距离比较小：而不 同类别的样本之问距离则帽对较大；对每一个样本i 定义一个陌生度( s t r a n g e n e s s ) 铫( i = 1 2 l + 1 ) ： 啦：至丝 名靠 ( 4 3 ) 从定义中可以看出，样本i 的陌生度是同类中前k 个最小的距离之和与不同类 中前k 个最小的距离之和的比值。当同类中距离和增大或不同类中距离和减小时， 陌生度增大。样本i 的陌生度越大，则表明这个样本相对于原来的样本序列来说越 “陌生”，即样本i 属于该样本序列的可能性越小。 将新样本轧。的类别。固定为某一个特定的值，如“+ l ”，代入式4 - 3 中可以 得到样本】，+ 。在类别+ l 时的陌生度。于是根据第三章中的式子( 3 - 3 ) 可以得 出p 值即随机性的计算公式，如下所示。该式已经被证明是有效的随机性检测函 韭窟窑煎太堂亟堂僮j 金奎直推式巫信基簦近筮羞簋鎏厘墓邀进 数鸭 p = 盟警擎过( 4 - 4 ) 1+ 上 在式4 4 中“# ”表示集合的势，是假设新样本砩。属于某一特定类别成立 的情况下其他训练样本的陌生度。 4 2 2t c m n n 算法 在近似的得到可计算的随机性检测函数之后，就可以将置信理论应用到最邻 近分类算法中，利用3 2 2 节中介绍的置信学习机器实现的一股方法得到直推式可 信最邻近分类算法，即t c m n n 。 利用式4 3 、式4 - 4 计算出新样本在各个类别时的p 值，根据该值确定新样本 所属的类别，并计算出相应的c o n f i d e n c e ( p 1 ) 及c r e d i b i l i t y ( 1 - 1 2 ) 的值，同样 本的类别号一起输出，作为进一步处理结果的依据。 假设有一训练样本集x ，所属于的类别y = 1 ，n ) 。现给出一个新的待分类 样本为x n e w ，则直推式可信最邻近分类算法具体的流程图为： 训练样本的预处理 j 一 好 比较各啦 得出结呆 上 ( 结束 ) 图4 - 2t c m - n n 算法流程图 该学习算法在判断样本类别的同时给出了该次判断的置信度，是种置信学 习算法。另外需要说明一点的是，t c m - n n 算法并非从训练样本得到一个通用的 判断规则后再依此对所有未知样本进行非此即彼的判断，它是一种直推式算法， 这一点从算法流程中也可以看出来。 4 3 改进的t c m n n 算法 在第二节中已经介绍了直推式可信最邻近算法，它可以为每次预算提供可信 度支持，丰富了输出结果的有效信息。但从它的算法步骤中也可以看出，该算法 的计算量非常大：不仅需要计算所有训练样本之间的距离，还必须计算所有测试 文档与所有训练样本之间的距离，并且还要将每个测试文档在所有的类别中一一 进行假设，然后分别进行相应的计算。这一点对于多类别，大数据集的文本数据 挖掘来说尤为明显。鉴于这种情况，本节提出一种改进的t c m - n n 算法，并将在 下文中用具体试验将其与其他算法进行比较。 4 3 1 基于层次聚类的k - m e a n s 算法 数据挖掘通常是在大数据集上进行，如果先对原始数据集进行处理，在不影 响其分布信息的情况下，有效的减小数据集的规模，则可以大大减少运算时间。 本文采用基于层次聚类的k - m e a n s 方法，将其引入到t c m n n 算法中。其基本思 想是：首先用聚类方法对i l 练样本的各个类别分别进行聚类得到一定数量的子类， 然后用这些子类的中心代表该类，这样不仅可以较好的表达原训练样本的信息， 而且通过减少了大量的训练样本，大大的缩短了运算时阃。 如下图所示：图4 3 a 是某个类中的样本分布图；图4 3 b 是将该类用聚类方法 进行处理后生成的各个子类的情况；图4 - 3 e 中标示出了各个子类的中心点o i 、0 2 、 0 3 、0 4 ，即将要代替该类的所有代表点。 田4 3 l 样本点原艚分布田 圈4 - 3 b 聚樊后的结果 图4 - 3 c 佯奉申的代表点子共 幽4 3 训练样本中心子类的获取过程 从图中可以看到，在该算法中采用聚类的方法将某一类c 中的样本点再次分 成几个小的子类，使得属于同一子类的对象之间具有最大的组内相似性，而不同 类别的对象问具有最小的组问相似性，然后分别计算出各个子类的中心，并记录 下所有的中心点，用这些中心点代表原来的类c 。 在本文中采用的聚类方法是改进后的k m e a n s 算法。 k - m e a n s 方法的思想是将数据集x 分割为k 个聚类并使得在每个聚类中所有值 与该聚类中心距离的总和最小。每个聚类的聚类中心是每个聚类的均值。算法选 择的相似性度量通常采用欧几里德距离的倒数，也就是说两者的距离越小表示两 者的相似性越大，反之则相似性越小。 下面给出该算法的具体步骤： 对于文档集合d 一 d l ，d 2 ，d n ) ，k - m e a n s 算法可描述如下： 步骤i ：给出要生成的类的个数k ； 步骤2 ：按照某种原则生成k 个聚类中心作为聚类的种子s f s l ，s 2 ，s k ； 步骤3 ：对d 中的每个文档依次计算它与各个种子的相似度s i m ( d i ，s j ) ； 步骤4 ：选取具有最大相似度的种子，将d i 归入以s j 为中心的类c 从而得 口 亡 一 口 口 亡口 一 凸 】 一 d 口 一 口口口d 一二 到d 的一个聚类c = c i ，c k ) ； 步骤5 ：重复步骤2 步骤4 若干次，直到得到较为稳定的聚类结果。 在上面的步骤2 中提到需要“按照某种原则生成k 个聚类中心”。为了得到更 好的聚类结果，也为了得到更高效的聚类过程，通常不会直接随机选取k 个对象 作为聚类中心，而是采用其他的方法或是与其他算法相结合的方法。本文采用 k - m e a n s 方法与层次聚类相结合的聚类算法，即利用层次聚类算法的输出结果作为 k - m e a n s 方法聚类的初始中心向量，来提高聚类性能。具体步骤如下： 步骤l ；用层次聚类算法对d 中的文本进行聚类，分别得到k 个子类及其中心 向量s i ，s 2 ，s k ； 步骤2 ：将s l ，s 2 ，s k 作为初始中心向量，再利用k - m e a n s 对d 中的文 本向量进行聚类； 步骤3 ：保存在步骤2 中得到的新的k 个子类及中心向量o l ，0 2 ，o k ， 以用于进一步的处理。 4 3 2 改进后的t c m n n 算法 在上一节中详细描述了对直推式可信最邻近算法进行改进的出发点，改进的 思想及具体改进的方法。下面给出改进后的整个算法，描述如下： 假设有一个训练集x ，类别y = 1 ，n ，每个类别c i ( i = 1 ，n ) 中有若干个训 练样本。 ( 1 ) 对训练集中的文档进行预处理； ( 2 ) 对每一个类别用改进后的k - m e a n s 方法进行聚类，得到k 个聚类中心， 以这k 个中心作为该类样本集的缩影； ( 3 ) 将步骤( 2 ) 中得到的k 41 1 个中心，作为新的训练样本输入分类器中； ( 4 ) 开始下面的训练及分类过程。 计算每个训练样本与同一类和不同类中其他样本的距离： 计算每个训练样本的a 值； 对每一个测试文档x n e w ，计算一与各训练样本的距离d ； 丫对每一个类别c x 对类别c x 中的每个样本i ：比较i 的第k 大距离与d 。，若前者 大，则重新计算峨 对不属于类别c x 中的每个样本i ：比较i 的第k 大距离与d ；， 若前者大，则重新计算o c i 计算- 一在类别c x 中时的 l n e w 值 计算相应的p 值 v 根据p 值判断) ( i i e w 的类别，并得到相应的c o n f i d e n c e 和c r e d i b i l i t y 值。 注：在上述步骤中a 值代表陌生度，它依然遵循式4 3 中的定义；p 值代表序 列的随机性，详见式4 - 4 。 具体的算法流程图如图4 4 所示： 戳i 山一个耕干千卒x 1 1 i 计算x 与所有训练样本的距离 l 假设x 在c l l 中 假设x 在c 。l 中 假设x 在c 。t 中 上 1 | l 计算a 。及p 值计算a 。及p 值计算a 及p 值 1 判断类别升计算可信度l l “ 又，中是否还、 是 、迫朱测样本 、 ( 结束 ) 图4 4 改进后的t c m - n n 算法流程图 下面给出程序中部分主要代码。 ( 1 ) 更新样本i 的陌生度俄的代码： u o i dc s u s t e a ：u p d a t e t r a i n d o c 冉1 p h a ( 1 0 n gt r a t n o o c h u n t n tc a t a n u m ) i n t1 ； f o r t = o ；t ( t r a t n u o c h u n ；l * + ) i f ( a 1 1 d l s t i c 1 5 n u i l - t c a t a n u m ) i i nt h es a _ ec l a s s ； 1 f ( a l l o t s t t d i s t u a l u e ( - 一$ a m e c l s d o c d t s t a n c e i 【k r l u e 一1 1 t e d t s t s a n e i = ( t e n p d i s t s a n e t 。 n - s a m e c l s d o c d i s t a n c e 【i 儿k a l o e 一1 + a l l o l s t 1 o t s t u a l u e ) ； ，去掉愿最小值，加上新的最小值 ms a m e c l s d o c d i s t a n c e i 【k v a l u e 一1 - e l l p l s t 1 - d i s t u a l u e ； e l s ei i nt h ed i f f e r e n tc l a s s ； i f ( n l l d t s t i d t s t u a l u e md i f f c l s d o c d t s t a n c e t 【i _ v a l u e 一1 】) t e m p d i s t d i f f i = ( t e m p d i s t d l f f t 一 m _ o i f f c l s d o c d i s t a n c e i 【k u a l u e 一1 】+ n l l d i s t t i 】- p i s t u a l u e ) ； no i f f c l s p o c o i s t a n c e i 儿k v a l u e 一1 】= a l l o i s t i 】d i s t u a l u e ： a l p h a _ u a l u e i = t e n p d i s t s a m e 1 t e m p d i s t d i f f t ； 该段代码是更新样本i 的陌生度峨的代码；陌生度c i j 的计算遵循式( 4 3 ) 。 其中，各变量及数据结构的含义如下： 变量t r a i n d o c n u m 表示训练样本的数量： 变量c a t a n u m 表示假设情况下的待测样本的类别号； 变量a l l d i s t 是结构体a a l l d i s t 的一个变量，用来存放新样本与所有训练样 本的距离。该结构体的定义为： s t r u c ta a u d i s t d o u b l ed i s t v a l u e ；新样本与菜- - p t t 练样本问的距离 i n te l s n u m ；该训练样本的类别 ) ； 变量ms a m e c l s d o e d i s t a n e e 用来存放与样本i 同类的前k 个最小的距离； 3 l 变量md i f f c i s d o c d i s t a n c e 用来存放与样本i 不同类的前k 个最小的距离。 ( 2 ) 计算新样本在某一类别中时的a c w 值代码： u o i dc s y s t e m ：c a l c u l a t e h e 蚺l p h a ( 1 0 n gt r a t n p o c h u n ，t n tc a t a n u m ) i n ti ； d o u b l es a m e c l s d i s t t t a x _ s r h e c l sd o c h u n ； d o u b l ed i f f c l s d i s t 【h n x d i f f c l s d o c h u h ； ，将新文档与训练文档的距离按类另分开 i n ts a m e n u m = b ： l o td i f f n u m = 0 ： d o u b l et e m p n e d i s t s a m e = b ： d o u b l et e m p n e d i s t d i f f = o