（计算机软件与理论专业论文）基于文本聚类技术的邮件分类系统的研究与实现.pdf

摘要 随着i n t e r n e t 技术的发展 各种网络应用服务越来越多 其中 网络中广 泛使用的电子邮件正成为一种快捷而经济的通信手段 如何面对每天各种各样 种类繁多的邮件 就成为一个迫切要解决的问题 以前的邮件分类系统 由于邮件的主要部分是文本 因此研究方向主要是基 于数据挖掘中的文本分类技术的 但是 这类方法主要有两点不足 第一就是分 类技术首先要指定各个分类的类别 同时 要形成准确的结果 都需要事先进行 大量的学习样本用例的过程 第二就是现有的邮件分类系统只是考虑到邮件的正 文 而没有考虑到邮件的其他特征 因此本文提出了基于文本聚类技术的邮件分类系统 它通过采用基于文本聚 类的算法来对邮件进行分类 同时 本系统还结合了邮件的一些特性来提高聚类 效果 这样就可以有效的改进上面的两种缺陷 在本文中 本文围绕这种邮件聚 类模型来介绍其中的相关的关键技术与方法 其中主要的内容有 通过使用改进 的向量空间模型 v s m 方法在计算机中表示文本 在特征项的选择上使用单词 权技术 在邮件相似度计算中加入了非邮件正文文本信息的相似度 在聚类算法 选择上 将两种算法相结合以适应邮件聚类等等 此外 本文还在此理沦基础上 进行了实际的实验分析 证明了这个理论的正确性 关键词 邮件分类 文本聚类 向量空间模型 v s m 层次聚类法 k m e a n s a b s t r a c t w t ht h ed e v e l o p m e n to fi n t e r n e tt e c h n o l o g y v a r i o u sk i n d so fn e t w o r k a p p l i c a t i o ns e r v i c e sw e l l e du p a m o n g t h e m t h ee m a i lu s e de x t e n s i v e l yi nt h e n e t w o r ka n di ti s b e c o m i n g ak i n do fs w i f ta n de c o n o m i cc o m m u n i c a t i o n m e a n st h e p r o b l e ma b o u th o w t 0m a n a g ev a r i o u se m a i l si no u rd a i l yl i f eh a s t ob es o l v e du r g e n t l y b e c a u s et h em a i np a r to ft h ee m a i lw a sat e x t s ot h ec l a s s i f i c a t i o n s y s t e m o fe m a i li nt h ep a s ti s m a i n l yb a s e d o nt h et e c h n o l o g yo ft e x t c l a s s i f i c a t i o n h o w e v e r t h i sk i n do fm e t h o dl a s t st w oi n s u f f i c i e n t t h ef i r s ti st h e c l a s s i f i c a t i o nt e c h n o l o g ys h o u l da p p o i n te a c hc l a s s i f i c a t i o nf i r s t m e a n w h i l e i n o r d e rt of o r mt h ea c c u r a t er e s u l t s i ta l ln e e dt oc a r r yo nal a r g en u m b e r s a m p l e st os t u d y t h e s e c o n di st h a tt h ee x i s t i n gc l a s s i f i c a t i o n s y s t e mo f e m a i lo n l yc o n s i d e r st h et e x ta n dd i d n l tc o n s i d e ro t h e rc h a r a c t e r i s t i c so ft h e e m a i l s ow e p u tf o r w a r dt h ec l a s s i f i c a t i o ns y s t e mo fe m a i lb a s e do nc l u s t e r s t e c h n o l o g y o ft h et e x t t h i ss y s t e mu s et h ea l g o r i t h mb a s e do nt e x tc l u s t e r i n g t oc l a s s i f yt h ee m a i l m e a n w h i l e i ta l s oc o m b i n e ds o m ea d d i t i o n a lp r o p e r t i e s o ft h ee m a i lt o i m p r o v ec l u s t e r sr e s u l t 8 0t w ok i n d so fd e f e c t sm e n t i o n e d a b o v ec a nb ei m p r o v e d t h ep a p e ri n t r o d u c e dr e l e v a n tk e yt e c h n o l o g ya n d m e t h o da r o u n dl h i sk i n do fc l u s t e r sm o d e l a n dt h em a i nc o n t e n ta r e u s e i m p r o v e d v e c t o r s p a c em o d e l v s m m e t h o dt oe x p r e s st h e 培埘i nt h e c o m p u t e r u s et h ew o r ds t r e n g t h0 n s t e c h n o l o g yi nt h e f e a t u r es e l e c t i o n a d d t h ea d d i t i o n a li n f o r m a t i o no fo n ee m a i lw h i l e c a l c u l a t i n gt h es i m i l a r i t yb e t w e e n t h e s ee m a i l s c o m b i n et w ok i n d so fa l g o r i t h m si no r d e rt o a d a p tt oe m a i l c l u s t e r e t c i na d d i t i o n w eh a v ea l s oc a r r i e do nr e a j e x p e r i m e n t a la n a l y s i s o nt h eb a s i so ft h i st h e o r y t h er e s u l th a v ep r o v e dt h ee x a c t n e s so ft h i st h e o r y k e y w o r d s e m a i lc l a s s i f i c a t i o n t e x tc l u s t e r i n g v e c t o rs p a c em o d u l e v s m h i e r a r c h i c a lm e t h o d k m e a n s 河海大学硕士学位论文 基于文本聚类技术的邮件分类系统的研究与实现 第一章绪论 1 1 研究邮件分类的背景和意义 随着i n t e m e t 技术的发展 各种网络应用服务越来越多 其中 网络中广泛 使用的电子邮件 e m a i l 正成为一种快捷而经济的通信手段 然而 面对每天各 种各样 种类繁多的邮件 其中包括各种垃圾邮件 j u n ke m a i l 所谓垃圾邮件 就是那些接收者并不愿意收到的大量的无聊的邮件 垃圾邮件的来源主要有以下 几个方面 商业广告 站点宣传 某些网络杂志 连环信的e m a i l 版 还有一 些政治宣传或者淫秽的内容 如何有效的对这些邮件分类处理 是摆在人们眼前 的问题 如果处理不当 会严重的浪费了人力 物力 和财力 在以往 对电子邮件进行过滤是以往常用的对付垃圾邮件的手段 市场上也 有一些商业化的软件再进行销售 但是由于现在垃圾邮件的制造手段越来越狡 猾 隐蔽 一些传统的邮件过滤手段已经不能应对这种新的垃圾邮件了 漏判 误判的事情时有发生 同时 在日常的生活中 尤其是商业应用中 人们对待邮 件的态度是宁可多阅读垃圾邮件 也不能错过一封重要的邮件 如何与时俱进 应对这种新的形势 本文提出了邮件分类的概念 1 2 问题描述 邮件分类的方法 可以将其分为人工分类和自动分类两大类 人工分类 组 织结构清晰 分类精度高 服务质量好 但是人工分类耗时 耗力 耗钱 难以 及时更新 尤其是随着现代信息社会的发展 知识经济时代的到来 人工分类远 远不能满足现代社会信息的需求 因此必须要发展自动分类技术 邮件自动分类是指计算机根据邮件的内容 将其自动归到一个或者几个类别 中去 这些邮件的来源是多种多样的 有私人信件 新闻信件 娱乐信件 垃圾 信件等等 邮件的类别和数量可以是预先预定好的 也可以是不确定的 要经过 邮件的自组织 聚类后才能得到 需要预先定义类别体系的邮件分类称为有指导 s u p e r v i s e d 的分类 也称自动归类 类别体系不确定的邮件分类称为无指导 u n s u p e r v i s e d 的分类 也称自动聚类 自动归类的一般做法是 预先确定好邮 件类别 并且对每个邮件类别提供一批预先分好类的邮件 称为训练文本集 类 系统先通过训练文本集学 j l e a r n i n g 分类知识 在实际分类时 再根据学习到 的分类知识为需要分类的文本确定 个或者多个文档类别 自动聚类是指文本聚 类 c l u s t e r i n g 即对给定的待分类邮件集利用聚类方法将其划分为多个类别 自 口j 薄大学坝士学位论文 基于文本聚类技术的邮件分类系统的研究与实现 动聚类系统不需要训练邮件 划分出的文档类也是不确定的 本文研究的邮件自 动分类是无指导的归类 也就是对邮件进行聚类 根据需要不同 标准不同 目 的不同 可以设计不同的类别体系 对于计算机进行的邮件自动分类 要求各类 邮件之间具有一定的区分度 类别体系确定以后 如何将邮件划分到各个类别中呢 分类系统可以有两 种 基于知识工程的分类系统 基于统计的分类系统 人在进行分类时 可 以通过人脑所具有的抽象思维能力来理解文本内容 达到邮件分类的目的 人类 所做的邮件分类是一种基于篇章理解的分类 知识工程的方法主要依赖语言学知 识 需要编制大量的推理规则作为分类知识 由于自然语言的复杂性以及知识库 的严重不足 目前采用计算机来做篇章理解 还远远未能达到理解各种各样真实 文本的水平 相比之下 统计方法由于其相对简单的机制 以及在实际环境中所 表现出来的良好性能 而为大多数文档分类系统所采用 利用统计学方法实现文 档分类具有速度快 实现简单等特点 且分类准确度也较高 能够满足一般应用 的要求 基于统计的分类方法具有如下特点 忽略邮件的语言学结构 把邮 件文本作为特征项集合对待 利用加权特征项构成向量作为邮件文本表示 根据词频信息对邮件文本特征进行加权 因此 需要通过各种方法找出真实出口件 文本的一些可量化特性来描述各个邮件文本类别的特征 并以此作为分类的依 据 至此 邮件自动分类问题可以被看作一种特定的模式识别问题 真实邮件文 本所反映出的文本类别特征可以看作一种待识别的模式 以邮件文本为研究对象 的模式识别所要研究的内容主要有以下几点 邮件可量化特征的选取 邮件特征 的量化以及对邮件特征的分类 聚类决策方法 或分类 聚类算法 1 3 邮件分类技术在国内外的发展 1 3 1 特征表示与特征提取 特征表示是指以一定特征项 如词条或描述 来代表文档 在邮件文本挖掘时 只需对这些特征项进行处理 从而实现对非结构化的邮件文本的处理 这是 个非 结构化向结构化转化的处理步骤 特征表示的构造过程就是挖掘模型的构造过 程 特征表示模型有多种 常用的有布尔逻辑型 b o o l e a nm o d e l 概率型 p r o b a b i l i s t i cm o d e l 向量空间型 v e c t o rs p a c em o d e l 简称v s m 等 这些模型 从不同的角度出发 使用不同的方法处理特征加权 类别学习和相似计算等问题 其中应用较多的则是向量空间模型 v e c t o rs p a c e m o d e l 在文本处理中 常用的文本特征提取方法有 文档频率 d o c u r n e n tf r e q u e n c y l 信思增益 i n f o r m a t i o ng a i n 互信息 m u t u a l i n f o r m a t i o n 单词权 文本证据权 河海大学硕士学位论文基于文本聚类技术的邮件分类系统的研究与实现 优势率等 1 3 2 分类决策方法 目前的分类决策方法 或分类算法 主要采用的是分类技术 而没有使用聚类 技术 由于邮件的正文是非结构化的文本文件 因此 目前邮件分类方法大部分 采用的就是文本分类方法 主要是现在常见的有贝叶斯分类法 1 和r o c c h i o a p p r o a c h b o o s t i n g z 等基于指导分类的方法 目前绝大部分的邮件分类器主要使 用的是基于文本数据挖掘的方法 而在其中大部分又是使用的贝叶斯分类法及其 改进的算法 朴素贝叶斯分类器是一个简单 有效而且在实际使用中很成功的分 类器 其性能可以与判定树与神经网络分类算法相媲美 3 在某些场合还优于其 他分类器 然而 和其他的基于指导分类的邮件分类系统一样 要形成准确的结 果 都需要事先进行大量的学习样本用例的过程 由于邮件发送者以及邮件种类 的不停变化 为了保持分类的精度 系统还必须经常学习 因此 就必须要寻找 一种灵活性的分类方法 采用文本聚类的方法来处理邮件 就可以达到这种目的 聚类不需要人们指定数据样本和指定分类 它根据文档内容的相似度来自动分 类 因此 使用了基于聚类方法的邮件处理系统后 能提高处理速度 缩短处理 时间 1 4 本文主要的工作内容 本文对基于聚类技术的邮件分类系统中所涉及的各项技术进行了全面的论 述 并根据电子邮件自身的特点提出了结合除了邮件正文外的相关信息与邮件正 文相结合的邮件聚类系统 以提高邮件聚类的效果 最后 本文通过对上述实现技术的阐述及其对试验结果的分析 提出了一些 关于邮件分类研究的见解 并对今后的研究工作进行了展望 1 5 本文组织 第一章绪论 介绍了本文的研究背景以及主要工作和论文组织 第二章向量空间模型及相关技术 介绍本文采用的特征表示的方法一向量 空间模型以及特征项的抽取等相关技术 第三章聚类学习算法 对现有的聚类技术相关方面进行了详细的描述与研 究 第四章基于文本聚类技术的邮件分类技术 介绍了自己如何结合邮件的特 点来构建基于文本聚类技术的邮件分类系统 河海人学硕士学位论文基于文本聚类技术的邮件分类系统的研究与实现 第五章系统评测 介绍如何对自己的系统的实验结果的评测以及最后的实 验结果 最后 第六章对本文的工作做了总结与展望 河海大学硕士学位论文基于文本聚类技术的邮件分类系统的研究与实现 第二章向量空间模型及相关技术 2 1 文本的表示 计算机并不具有人类的智能 人在阅读文章后 根据自身的理解能力可以产 生对文章内容的模糊认识 而计算机并不能轻易地 读懂 文章 从根本上说 它只认识0 和1 所以必须将文本转换为计算机可以识别的格式 根据 贝叶 斯假设 假定组成文本的字或词在确定文本类别的作用上相互独立 这样可以 就使用文本中出现的字或词的集合来代替文本 不言而喻 这将丢失大量关于文 章内容的信息 但是这种假设可以使文本的表示和处理形式化 并且可以在文本 分类中取得较好的效果 目前 信息检索的概念被提出后 出现了许多基于文档 o c u r n e n t 平u 查询 f q u e r y 之间的文本计算模型 具有代表性的有布尔模型 b o o l e a nm o d e l 向量 空间模型 v e c t o rs p a c em o d e l 简称v s m 概率模型 p r o b a b i l i s t i cm o d e l 等 这些模型从不同的角度出发 使用不同的方法处理特征加权 类别学习和相似计 算等问题 这几种模型中 向量空间模型是最简便有效的文本表示模型之一 向量空间 模型是s a l t o n 6 等人于6 0 年代末首先提出的 并在著名的s m a r t s y s t e m f o rt h e m a n i p u l a t i o na n dr e t r i e v a lo ft e x t 系统得到成功的应用从此以后 该模型及其相 关技术 包括项的选择 加权策略 以及采用相关反馈进行优化查询等在文本分 类 自动索引 信息检索等许多领域得到广泛的应用 特别是随着网上信息的迅 速膨胀 还被广泛地应用到搜索引擎 个人信息代理 网上新闻发布等信息检索 领域新的应用中 并且取得了较好的效果 2 2 向量空间模型 1 文档 d o c u m e n t 泛指一般的文本或者文本中的片段 段落 句群或句子 一般指一篇文章 尽管文档可以是多媒体对象 但是以下讨论中本文只认为是文 本对象 文本与文档不加以区别 2 项 t e r r a 文本的内容特征常常用它所含有的基本语一言单位 字 词 词组或短语等 来表示 这些基本的语言单位被统称为文本的项 即文本可以用 项集 t e r m l i s t 表示为d t l f 2 r 3 其中 是项 1 k 审n 3 项的权重 t e 皿w e i g h t 对于含有n 个项的文本d t 1 毛 屯 吒 基于文本聚类技术的邮件分类系统的研究与实现 项 常被赋予一定的权重 表示它们在文本d 中的重要程度 即d d r 简记为d d w 2 w 3 这时说项 的 权重为 l k n 4 向量空间模型 v s m 给定一文本d d w l 2 f 3 w 3 t 嵋 由于f 在文本中既可以重复出现又应该又先后次序的关系分析起来仍有 定的 难度 为了简化分析 可以暂时不考虑k 在文档中的先后顺序并要求 互异 这 时可以把 乞 乞 看成一个n 维的坐标系 而w 1 心 w 为相 应的坐标值 因而d d 心 m 被看成是n 维空间中的一个向量 称d d m 为文本d 的向量表示 5 相似度 s i m i l a r i t y 两个文本d 1 和d 2 之间的 内容 相关程度 d e g r e eo f r e l e v a n c e 常常用它们之间的相似度s i r e d 1 d 2 来度量 当文本被表示为向量 空间模型时 可以借助于向量之间的某种距离来表示文本间的相似度 常用向量 之间的内积进行计算 s i m d 1 d 2 w l t 4 w 2 t 2 1 t l 或者用夹角余弦值来表示 8 i 如图 2 1 所示 s i m d 1 d 2 c o s 0 2 2 图 2 1 文本的向量空间模型 v s m 以及文本间的相似度s i m d 1 d 2 6 一 河海人学硕士学位论文基于文本聚类技术的邮件分类系统的研究与实现 2 3 项的选择 如前所述 项可以是文本中的各种语言单位 特别是对中文来说有字 词 短语 甚至是句子或旬群等更高单位 4 j 为了简便起见 本系统暂时不考虑中 文的项的情况 项也可以是相应词语或者短语的语义概念类 因此 项的选择 只能由处理速度 精度 存储空间等方面的具体要求来决定 选出的项越具有代 表性 语言层次越高 所包含的信息就越丰富 但是分析的代价就越大 而且受 分析精度 如句法分析的正确率 的影响就越大 由于词汇是文本最基本的表示 项 在文本中的出现频度较高 呈现一定的统计规律 再考虑到处理大规模真实 文本所面临的困难 选择词或者短语作为特征项是比较合理的 常常被应用于文 本检索与分类领域 但是直接选用文本中的词或者词组作为文本特征项时也会出 现以下问颗 1 文本中存在一些没有实在意义但使用频率很高的虚词和功能词 如英语 中的 t h e a o f 等 常常把一些真正由分类作用的实词淹没掉 解决这 个问题的方法是把这些词组织成一个禁用词表 去除停用词 合并数字和人名等 词汇 把禁用词表中的词从特征集中滤掉 去除停用词 合并数字和人名等词汇 此外 还可以在文本预处理时进行词性标注 从词汇特征集中滤去那些对特 征区别贡献极小的大部分虚词和功能词 2 一词多义或词汇变形问题 事实上 自然语言有着极为丰富的语言现象 例如词汇之间的关系 就有同义关系 近义关系 从属关系 关联关系等等 在 使用短语等复合词时关系就更加复杂了 另外词汇的歧义和多义也很普遍 例如 c o n s o l eaf r i e n di ng r i e f c o n s o l e 意义为安慰 l o g i ni n t oo n ec o n s o l e 这里 的c o n s o l e 指的是计算机中的终端 因此 不同的词义当作不同的项来看待会更 合理 词汇变形问题主要是指西文单词有复杂地词尾变化和派生现象 解决这些 问题常有两种办法 第一种是进行概念语义标注 以便把同义的或相似的特征项 合并为相应的概念类 对于西文 可以通过特别的抽取词千处理 把同源的词用 同一个词干来标记 显然 通过概念标注并利用概念信息作为文本的特征项比单 纯的词汇信息更能反映文本的内容 因此 词义相同或者详尽的词汇往往被映射 为同一个概念 而同一词汇所表示的词义也是和上下文相关的 把词汇在具体的 上下文中所对应的概念作为文本的描述项 那么内容相似而仅在用词上有较大差 异的文章 彼此之间的相似度就会大大增加 所以采用概念作为特征项是比较合 理的 但是这样做的同时势必加大了文本处理的复杂程度 7 u 脚凡学砸卜学位论文 基于文本聚粪技术的邮件分类系宝觅的研究 j 实现 2 4 项的权重计算 在v s m 中 给每个项赋上权重时 应使文本中越重要的项权重越大 种方 法是由专家或者用户根据自己的经验与所掌握的领域知识人为的赋上权值 这种 办法随意性很大 而且效率也很低 很难适用于大规模真实文本的处理 另一种 办法是运用统计的方法 也就是用文本的统计信息 如词频 词之间的同现频率 等 来计算项的权重 目前被广泛采用的权重计算公式是t f i d f 公式 7 阳 丝丝堕垒丝竺 望i 2 3 耐矿 孑 l o g n n 0 0 1 r 其中 f 厅 为词 在文本孑中的权重 而t f t 孑 为词f 在文本西 中的词频 为文本的总数 门 为文本集中出现f 的文本数 分母为归一化因 子 这种公式是根据香农信息学理论 如果项在所有文本中出现的频率越高 那 么它所包含的信息嫡就越少 如果项的出现较为集中 只在少量文本中有较高的 出现频率 那么它就会拥有较高的信息嫡 上述公式就是基于这个思想的一种实 现 同时 由于考虑到文本长度的对权值的影响 这个公式还对项权值公式做归 一化处理 这样就可以将各项权值规范到 o 1 之问 另外 对于特征较为明显的文本类别 往往有少数项的出现频率数远远大于 其他项 根据上述计算公式计算出的权值会很高 如果个别项的权值很高 在分 类过程中往往会抑制其他项的作用 因此在计算各项权重时 应对统计出的词频 做适当的均衡处理 较为简单的均衡处理方法是对统计出的权值进行开平方 经 过词频均衡处理的权值计算公式为 w t d 丝丝 塑丝 竺兰 塑 24 2 2 l q j 撇孑 1 0 9 n 氇 0 0 1 丁 该公式中参数的含义与上式相同 权重的计算只能视具体情况而定 至今仍没有普遍使用的 最优公式 另 外 前面的讨论中项的权值一般为正 其实权值也可以取负值 用来描述某用户 厌弃某特征 t f i d f 公式是一种经验公式 并没有坚实的理论基础 但是 多 年的实验表明 上述公式是文本处理中的一个有效工具 事实上 这一公式不仅 在信息检索中得到了成功应用 它对子其他文本处理领域 如信息分发 信息过 滤和文本分类也有很好的借鉴意义 本文研究的邮件自动聚类系统也是以它作为 文本表示模型而实现的 河海大学硕士学位论文 基于文本聚类技术的邮件分类系统的研究与实现 2 5 特征项的抽取 特征抽取是从一组特征中选出一部分最有代表性的特征 5 特征抽取在文本 分类中起着重要的作用 能够起到降低向量空间维数 简化计算 防止过分拟合 等作用 1 0 由于特征子集的数量和特征数量之间是指数的关系 枚举几乎是不可 能的 因此本文中假设特征之间是独立的 这样特征子集的抽取就转化特征项的 抽取 及根据某个特征评估函数计算各个特征的评分值 然后按评分值排序 选 取若干个评分最高的作为特征词 这就是特征提取 国际上在特征选择方面进行了大量的工作 其中c 州的y a n gy i m i n g 教授和 s t a n f o r d 的m e h r as a h a m i 的论点较具代表性和总结性 特别在y a n g 的论文中 她对现有的许多特征选择方法做了总结和归纳 她的实验表明 特征选择的主要 功能是在不损伤分类精度的情况下尽量减少要处理的单词数 以此来降低向量空 间维数 从而提高分类工作的速度和效率 因此 特征选择对提高分类精度来说 即使是有帮助 但是对不同的分类器所起的效果不同 在文本处理中 常用的文本特征选择方法有 文档频率 d o c u m e n t f r e q u e n c y 信息增益 i n f o r m a t i o ng a i n 互信息 m u t u a li n f o r m a t i o n z 2 统计量 c h i 期望交叉熵 文本证据权 单词权等1 1 1 1 2 1 3 2 9 这些方法的基 i 本思想都是对每一个特征 在这里是词 计算某种统计度量值 然后设定一个阈 值t 把度量值小于t 的那些特征过滤掉 剩下的即认为是有效特征 下面简单 的介绍一下文档频率 信息增益 互信息 单词权的计算方法 对于特征词t 各种选择标准的含义如下 1 文档频数 d o c u m e n tf r e q u e n c y 即是特征t 在文本集中出现的文档数 它是最简单的评估函数 其值为 训练集合中该单词发生的文本数 d f 的缺点是稀有单词可能在某一类文本中 并不稀有 也可能包含着重要的判断信息 简单地舍弃 可能影响分类器的 精度 因此 在实际运用中一般并不直接使用d f 2 信息增益 i n f o r m a ti o ng a i n 信息增益 i n f o r m a t i o ng a i n 在机器学习领域被广泛使用 f 4 i g 考察c 中出现和不出现t 的文档频数来衡量t 对于c 的信息增益 可以采用如下 的定义式 三一旦 一一 i g t 2 尸0 乞p c jj t l o g p c rir p f p qi t l o g p c l f 2 5 其中户 c f 表示c 类文档在语料中出现的概率 p 表示语料中包含词条 t 的文档的概率 p qi t 表示文档包含诃条t 时属于c 类的条件概率 河海大学顾 卜学位论文 基于文本聚类技术的邮件分类系统的研究与实现 p n 表示语料中不包含词条t 的文档的概率 j d c jf 表示文档不包含词条t 时属于c 的条件概率 m 表示类别数 3 互信息 m u t u a l i n f o r m a ti o n 在统计学中 互信息用于表征两个变量的相关性 常被用来作为文本特 征相关的统计模型及其相关的应用标准 文本特征t 与类别c 的互信息 m i t c 定义如下 m i t c 1 g 等 26 如果用a 表示包含词条t 且属于类别c 的文档频数 b 为包含t 但是 不属于c 的文档频数 c 表示属于c 但是不包含t 的文档频数 n 表示语 料中文档总数 t 和c 的互信息可由下式计算 m i t c l 8 酉而a x n 2 7 4 单词权 t s 它和其它的评估函数完全不同 与类别信息无关 首先利用文本向量 间的余弦夹角找出相似度大于 f 限值的文本对 令 x v 是任意一个这样 的文本对 定义 t s w p y i w x 2 6v s m 的总结 2 8 向量空间模型的最大优点在于它在知识表示方法上的巨大优势 在该模型 中 文本内容被形式化为多维空间中的一个点 通过向量的形式给出 把对文本 内容的处理简化为向量空间中向量运算 使问题的复杂性大为降低 而权重的计 算既可以用规则的方法手工完成 又可以通过统计的办法自动完成 便于融合统 计和规则两种方法的优点 也正是因为把文本以向量的形式定义到实数域中 才 使得模式识别和其他领域中的各种成熟的计算方法得以应用 极大提高了自然语 言文本的可计算性和可操作性 所以说 文本的形式化表示方法一向量空间模型 是基于文本处理的各种应用得以实现的基础和前提 向量空间模型是一种不考虑特征项出现顺序的词袋 b a go fw o r d s 文本表示 模型 3 2 l 这种模型虽然带来了计算和操作上的方便 但是却损失了大量的文本结 构信息 而这些信息在自然语言中是至关重要的 如句子中词序信息等 另外 在权重和相似度的计算中也做了许多简化工作 一是对不同的语言单位构成的特 河海火学硕 e 学位论文基于文本聚类技术的邮件分类系统的研究与宴现 征项大都只考虑其统计信息并采用统一的权重计算方法 而这种计算只是经验公 式并没有很好的理论基础 所以计算出的权重未必能真实反映各项的重要性 二 是向量空间模型是建立在所有项两两正交这一假设基础之上的 没有考虑特征项 之间的相关性 对于自然语言这种有着非常丰富语言现象的研究对象来说 这种 假设显然是过于严格的 不能很好地反映自然语言的特征 目前已经有许多改进 项权重计算的方法 但是效果并不明显 原因在于语义关系实际上是一个很复杂 的运算 采用简单的初等运算代替它 误差势必存在 目前 自然语言理解领域的多项试验表明 在以自然语言为研究对象的知识 处理和知识获取问题中 知识表示始终是其处理的主要瓶颈 如何确定和弥补现 有文本内容映射到特征项时出现的大量有效信息的损失是自然语言处理领域今 后需要关注和解决的问题之一 河海大学顾七学位论文 基于文本聚类技术的邮件分类系统的研究与实现 第三章聚类学习算法 聚类 分类是人类认识未知世界的一种重要的认知手段 在生产和生活中 人们往往面对非常复杂的事和物 如果能够把相似的东西归为一类 有明显区别 的事物分属在不同的类别中 处理起来就大为简便 所谓 物以类聚 人以群分 说的就是这个道理 譬如人们将生物分为动物和植物 又根据不同的生理特点将 生物分为不同的门 纲 目 科 属 种 在化学理论中 人们根据不同的化学 性质将各种元素划分为不同的类别 比如卤族元素 惰性气体等等 进而总结出 元素周期率 在社会学中 人们还根据不同的信仰划分出不同的党派 宗教等 在原始的分类学中 人们的分类依据是经验和专业知识来进行定性分析 很 少使用数学工具 随着人类对自然和社会的认识不断深入 要处理的数据量规模 越来越大 相互关系也越来越复杂 分类越来越细 对分类的要求也越来越高 这时仅仅依靠定性分析就不能满足要求 于是数学这个得力工具被引入 形成了 数值分类学 对分析对象进行定量的研究 由于数值分类学中的方法不仅能够用 于分类 还能用于其他领域 于是人们觉得使用 聚类分析 这个名称更为恰当 聚类分析的目的是揭示样本点之间最本质的 抱团一隆质 要想定量地处理 一批样本点 首先必须对这些样本点的性质进行定量的表示 领域专家确定采用 哪些指标特征变量来精确刻画样本的性质 以及如何定义样本之间的相似性测 度 3 1 什么是聚类分析 聚类分析是数据挖掘的一项重要功能 而聚类算法是目前研究的核心 聚类 是把一组个体按照相似性划分成若干类别 即 物以类聚 它的目的是使得属 于同一类别的个体之间的距离尽可能的小 而不同类别的个体间的距离尽可能的 大 聚类分析就是使用聚类算法来发现有意义的聚类 它的主要依据是把相似的 样本归为一类 而把差异大的样本区分开来 这样所生成的簇是一组数据对象的 集合 这些对象与同一个簇中的对象彼此相似 而与其他簇中的对象彼此相异 在许多应用中可以把一个簇中的数据对象当作一个整体来对待 聚类分析是一种重要的人类行为 很小的时候人就可以通过不断的改进下意 识中的聚类模式来学会如何区分不同的动物或动物和植物 聚类分析已经广泛的 应用在许多应用中 包括模式识别 数据分析 图象处理以及市场研究 通过聚 类人们能够识别密集和稀疏的区域 因而发现全局的分布模式以及数据属性之间 河海大学硕士学位论文基于文本聚类技术的邮件分类系统的研究与实现 的有趣的相互联系 作为一个数据挖掘的功能聚类分析能作为一个独立的工具来 获得数据分布的情况 观察每个簇的特点 集中对特定的簇做进一步的分析 而 且聚类分析可以作为其他算法 如特征和分类等 的预处理步骤 虽然聚类也可以起到分类的作用 但是它和大多数分类方法不同 大多数分 类方法都是演绎的 即人们事先确定某种事物分类的准则或各类别的标准 分类 的过程就是比较分类的要素与各类别标准 然后将各要素划归于各类别中 确定 事物的分类准则或各类别的标准或多或少带有主观的色彩 而聚类分析是归纳 的 不需要事先确定分类的准则 不知道它们的分类 甚至连分成几类也不知道 它通过一些计算来把观测进行合理的分类 使得同 类的观测比较接近 不同类 的观测相差较多 这是无指导的学习 本文中讨论的聚类分析依赖于对观测间的接近程度 距离 或相似程度的理 解 定义不同的距离量度和相似性量度可能产生不同的聚类结果 3 2 聚类算法涉及的各类型数据及预处理 数据挖掘的一个重要步骤是数据准备 这包括对选定的数据进行规范化 整 合和预处理等等 这是进行数据挖掘的前提也同样是聚类算法能正常实施的必要 前挺 要对数据对象进行聚类 基于统计方法 其最重要的前提是要计算各个数 据对象之间的距离一即文中相异度 聚类算法最常使用的两种有代表性的数据结构为数据矩阵和相异度矩阵 数 据矩阵一般用p 个变量 也称为度量和属性 来表现n 个对象 这种数据结构是关 系表的形式 或看成 p n 个对象 p 个变量 的矩阵 阵 图 3 1 数据矩阵 相异度矩阵存储n 个对象两两之间的近似性 表现形式为一个n n 的矩 一l p p p 加 易 岛 一 一 旷 旷 乃 一 一 五 五 瓦 一 一 河海人学顾 l 学位论义基于文本聚类技术的邮件分类系统的酬究与实现 垫1 od 3100d n2 1 d 2 f d o 2 i d m 1 d j 矩阵中的d i j 表示对象i 和对象j 之间的相异性 通常它是一个非负的数 值 当对象i 和对象j 越相似或接近时其值越接近0 两个对象越不同其值就越 大 因此有d i j d j f d i f 0 数据矩阵通常被称为二模矩阵 而相异度矩阵称为单模矩阵 这是因为前者 的行和列代表不同的实体而后者的行和列代表相同的实体 实际中很多聚类算法 是以相异度矩阵为基础的 相异度是聚类算法的基础 对于相异度的估算不同的变量类型有不同的计算 方式 详细的计算方式在第四章中会阐述 3 3 现存重要的代表性聚类算法的分析与研究 目前 已经提出的聚类算法有很多口 可以在此仔细分析研究它们的具体性 能 优势与缺点 明确它们所适合的具体情形 当然 这些算法一般都存在这样 或那样的不足 对于一些情况无能为力 因此 在使用这些聚类算法的时候 必 然要与具体情况相结合 做出一些相应的调整 一般来说这些算法可以分为如下 的几类 3 3 1 划分方法 p a r t i t i o n i n gu e t h o d 给定一个n 个对象或元组的数据库 一个划分方法构建数据的k 个划分 每 个划分表示一个聚簇 并且k 墨n 也就是说它将数据划分为k 个组 同时满足 如下的要求 i 每个组至少包含一个对象 i i 每个对象必须属于且只属于一个 组 给定要构建的划分的数目k 划分方法首先创建一个初始划分 然后采用一 种迭代的重定位技术 尝试通过对象在划分间的不断移动来改进划分 一个好的 划分的一般准则是 在同一个类中的对象之间尽可能的接近或相关 而不同类中 的对象之间尽可能的远离或不同 实际上绝大多数应用采用了以下比较流行的启发式算法 i k 平均算法 1 在该算法中每个簇用该簇中对象的平均值来表示 i i k 中心点算法 在 河海人学硕上学位论文 基于文本聚娄技术的邮件分类系统的研究与实现 该算法中 每个簇用接近聚类中心的一个对象来表示 这些启发式聚类方法对在 中小规模的数据库中发现球状簇很适用 而且其实现相对的简单 但是它不能发 现任意形状的簇 其参数k 对聚类结果有很大的影响 很影响聚类的质量而且这 类算法不具有很好的伸缩性 要对大规模的数据集进行聚类以及处理复杂形状的 聚类就要对基于划分的方法做进一步的扩展 如下为当前最常用最流行的两个经典算法的详细阐述 1 k 一平均算法 k m e a n s 的具体步骤如下 输入 簇的数目k 和包含n 个对象的数据库 输出 k 个簇并且使平方误差准则最小 i 假设要聚成k 个类 由人为决定k 个类中心z l 1 z 2 1 互 1 2 在第k 次叠代中 样本集 z 用如下方法分类 对所有i l 2 k i 若忙一弓 七 i l l z z 硎i 则z 邑 忌 3 令由 2 得到的s 的新的类的平准值为z 克 1 令 l i z z j k 1 1 2 最小 j 1 2 k c 6 t 则z j k 1 争 z 量 七 中的样本数 z s 对于所有的j 1 2 k 若z j 七 1 z 尼 则终止 否则继续再从 第二步开始 图 3 3 k 平均值法迭代图例 o 这个算法尝试找出使平方误差函数值最小的k 个划分 当结果簇是密集的 而簇与簇之间区别明显时它的效果很好 但是k 一平均方法只有在簇的平均值被 河海人学硕士学位论文基于文本聚类技术的邮件分类系统的研究与实现 定义的情况下才能使用 这可能不适用于某些应用 例如涉及分类属性的数据 要求用户必须事先给出k 要生成的簇的数目 可以说是该方法最大的缺点 而且 k 一平均方法不适合于发现非凸面形状的簇 或者大小差别很大的簇 与此同时它 对于 噪声 和孤立点数据很敏感 少量的该类数据能够对平均值产生大的影响 此算法不仅对参数k 的选择很敏感而且对最初始簇中心的选择也具有很大的依 赖性 不同的初始类中心选择可能会产生不同的聚类结果 它的流行主要在于它 的实现很简单 针对k 一平均算法对 噪声 和孤立点数据的敏感性 对其进行改进出现 k 一中心点方法 2 k 一中心点算法具体步骤如下 输入 结果簇的数目k 包含n 个对象的数据库 输出 k 个簇 使得所有对象与其最近中心点的相异度总和最小 1 假设要聚成k 个类 由人为决定k 个类中心z i 1 z 2 1 五 1 2 若l i z z i i l l z z 川 n z 墨 s 为以z f 为中心点的簇 对所有的 i 1 2 k i 3 在每次叠代中 样本集 z 用如下方法分类 对所有i i 2 k 随机从咀z 为中心点的簇中取z 若 忙一乙j l e i i z z i i 其中z 为簇中的每一个对象 则用匆代替互 z z e 为中心点 4 由 3 得到的新的类的中心点 k 令 l i z 一圳最小 i l 2 k i 1z e 0 z 为以互为中心点的簇中的对象 5 若j 已经达到最小或不在变化 则终止 否则再转到第三步 河海大学烦士学位论文 基于文本聚类技术的邮件分类系统的研究与实现 4 g 蜘m 岬 l j h 上 工 籼 叶 a g n e s d i v i s i 仰 m a h a 图 3 5 数据对象 a b c d e 的凝聚与分裂 现在算法研究主要集中在凝聚层次聚类方面 分裂方面的很少 其中凝聚方面 可以按照的思路就是 寻找 距离 最近的两个样本结合 这个算法步骤如下 有n 个样本的集合邑 fz l z 2 乙 若想要聚成k 个类 其中k 要预先指定 1 k n e 互 i l 2 n 2 i fk k t h e ne n d 3 找到c 与c 之间的距离d e c 最小的一对 4 c 与c j 合并成一个类g 并计算新的c 的中心 5 去除c k k 一1 然后转到第二步 类间距离d g c 的度量可以有以下四种 1 中心间距 a i i i m 一蚂 其中m z 一是属于c 的样本数 t l z e c 2 距离最近的样本 吐 乏i 虿藕f z f 一弓 f 3 距离最近的样本 吐 z j c i z c 硼互一乙 l 4 类间平均距离 吐 1 4 x x q l z 一乙4 河海大学硕士学位论文 基于文本聚类技术的邮件分类系统的研究与实现 c ic 2c 3c 4c 5c 6 相似性尺度 6 0 7 0 8 0 9 0 1 0 0 图 3 6 层次方法图例 层次聚类方法虽然很简单 但是它经常的遇到合并或分裂点选择的困难 合 并和分裂点的选择是非常关键的 因为一旦 组对象被合并或者分裂 下一步的 处理将在新生成的簇上进行 已做的处理不能被撤消 聚类之间也不能交换对象 这样做不用担心组合数目的不同选择 相对来说计算代价会较小 但另一方面造 成的后果是如果在某一步没有很好的选择合并和分裂点 刚可能会导致低质量的 聚类结果 而且由于合并和分裂的决定需要检查和估算大量的对象或簇 这种聚 类方法不具有很好的可伸缩性 改进层次方法聚类质量的一个很有前途的方向是把层次聚类和其他聚类方 法相结合起来 形成多阶段的聚类 下面将讨论的b i r c h 算法就是其中有代表性 的一种 它首先用数结构对对象进行层次划分 然后采用其他的聚类算法对聚类 结果进行求精 它采用最多的聚类算法是划分方法方面的 b i r c h 算法口l 的核心是用一个聚类特征三元组c f 总结了一个簇个体的有关