（计算机应用技术专业论文）基于混合模型的文本分类的研究.pdf

东北大学硕士学位论文 刁 商 要 基于混合模型的文本分类的研究 摘要 随着互联网技术的飞速发展，网上的资源呈指数增长，人工处理这些海量信 息代价非常高昂，因此如何高效地组织和管理这些资源成为近些年来的研究热点。 一种自 动组织和管理知识的技术文本分类，作为实现这一目标的关键技术之 一，得到了研究人员的广泛关注。 传统的基于概率的文本分类，如朴素贝叶斯方法，它们通常假设类模型服从 单一分布，在估计类模型时往往需要大量高质量的样本才能准确反映类特征。实 际上，人们在写作过程中会受到多方面因素影炯，如所要描写的主题、相关背景、 写作常识、文章风格、写作习惯、词汇上下文语境等等，即一个类的分布特征是 受到多因素影响的。如果只用单一的分布模型来拟合类的分布特征是不准确和不 完整的。 针对于此，本文提出了一种基于主题和通用知识的类模型，利用期望最大化 方法 ( e m) 估计模型参数。实验证明:基于混合模型的分类算法的整体性能明显 优于朴素贝叶斯方法，是一种比较稳定的算法，尤其是在小训练样本情况下，混 合模型分类算法表现突出。另外， 尽管估计混合模型时增加了分类模型的复杂度， 但实验表明，由于 e m算法通常在3次迭代后基本收敛，对算法的整体效率影响 不大。 本文还论述了我们提出的基于混合模型的文本分类器的两种用途。 ( 1 ) 建立用 户模型: 在我们的一个个性化推荐原型系统s m a rt w e b中， 用户模型是其中的一个 重要模块， 好的用户模型可以大大改善其推荐结果:( 2 ) 聚焦爬虫:文本分类器是 聚焦爬虫的一个重要构件。本文提出应用基于混合模型的文本分类器以满足上述 两种需求。 关键字数据挖掘 文本分类 混合模型 期望最大化 朴素贝叶斯 东北大学硕士学位论文 人b s t r a c t s t u d y o n t e x t c ca s s ii ic a t i o n b a s e d o n f i n i t e 9 y 姆u r e , r o d e ( ab s t r a c t wi t h t h e r a p i d d e v e l o p m e n t o f i n t e rn e t , t h e i n f o r m a t i o n r e s o u r c e s o n i n t e r n e t i n c r e as e e x p o n e n t i a l ly . a s a r e s u l t , i t i s a lm o s t i m p o s s i b l e t o d e a l w i t h t h e m as s i n f o r m a t i o n m a n u a l l y . i n t h e r e c e n t y e a r s , m o r e a n d m o r e r e s e a r c h e r s a r e c o n c e rn i n g h o w t o o r g a n i z e a n d m a n a g e t h e in f o r m a t i o n e f f i c i e n t l y a n d e ff e c t i v e l y . a s o n e o f t h e k e y t e c h n o l o g i e s t o w a r d th i s g o a l , t e x t c l as s i f i c a t i o n i s f o c u s e d w i d e l y b y r e s e a r c h e r s . t r a d i t i o n a l t e x t c l as s i f i c a t i o n a l g o r i t h m s b as e d o n p r o b a b i l i t y m o d e l s u c h as n a i v e b a y e s a l g o r i t h m m a k e a s s u m p t i o n t h a t d o c u m e n t i s g e n e r a t e d fr o m o n l y o n e c o m p o n e n t . i n t h e c as e o f s u c h ass u m p t i o n , t o e s t i m a t e t h e m o d e l p a r a m e t e r s a n d m o d e l t h e c l a s s c h a r a c t e r i s t i c s a c c u r a t e l y , p l e n ty o f t r a in in g s a m p l e s a r e r e q u i r e d i n d i s p e n s a b l y . i n f a c t , t h e r e a r e m a n y f a c t o r s , s u c h a s t o p i c , w r i t i n g b a c k gr o u n d , w r i t i n g c o m m o n p l a c e , d o c u m e n t s t y l e a n d w r i t i n g h a b i t s o f w r i t e r s e t c . , t o i n fl u e n c e c l ass c h a r a c t e r i s t i c s . t o c h a r a c t e r i z e t h e c l as s m o d e l c o m p r e h e n s i v e l y a n d a c c u r a t e l y , w e p r o p o s e a f i n i t e m i x t u r e m o d e l b a s e d o n t o p i c m o d e l a n d g e n e r a l m o d e l t o r e v e a l t h e c l as s c h a r a c t e r i s t i c s m o r e a c c u r a t e l y . e m ( e x p e c t a t i o n ma x im i z a t i o n ) m e t h o d i s a p p l i e d t o e s t i m a t e p a r a m e t e r s o f m i x t u r e m o d e l . b a s e d o n t h e m i x t u r e m o d e l p r o p o s e d i n t h i s t h e s i s , a t e x t c l a s s i f i c a t i o n i s i m p l e m e n t e d . t h e r e s u lt s o f e x p e r i m e n t s s h o w t h a t t e x t c l as s i fi c a t i o n a l g o r i t h m b a s e d o n f in i t e mi x t u r e mo d e l i s a s t a b l e a l g o r i t h m a n d o u t p e r f o r m s n b . b e s i d e s , t e x t c l as s i f i e r b a s e d o n mi x t u r e mo d e l p e r f o r m s w e l l e v e n t h o u g h t h e t r a i n i n g s a m p l e i s s m a l l m o r e o v e r , t h e t h e s i s p r e s e n t s t w o a p p l i c a t i o n s o f m i x t u r e m o d e l p r o p o s e d h e r e . ( 1 ) u s e r p r o f i l e . u s e r p r o fi l e i s o n e o f t h e m o s t im p o r t a n t m o d u l e s i n s m a r t w e b - o u r p e r s o n a l i z e d r e c o m m e n d a t i o n p r o t o t y p e s y s t e m . a g o o d u s e r p r o f il e c a n i m p r o v e t h e r e c o m m e n d a t i o n r e s u l t o f s m a rt we b . ( 2 ) f o c u s c r a w l e r . t e x t c l a s s i f i c a t i o n i s t h e k e y c o m p o n e n t i n f o c u s c r a w l e r . i n t h i s t h e s i s , w e s u g g e s t t o a p p l y t h e t e x t c la s s i f ie r b as e d m i x t u r e m o d e l t o t h e s e t w o a p p l i c a t i o n s k e y w o r d l d a t a m i n in g , t e x t c l as s i f i c a t i o n , m i x t u r e m o d e l , e x p e c t a t i o n ma x i m i z a t i o n , n a i v e b a y e s i i i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学 位 论 文 作 者 签 名 : i ， 传建 日期: 2 心 口 5 1 / . / 学位论文版权使用授权书 本学位论文作者和指导教师完全了 解东北大学有关保留、使用学 位论文的规定:即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流， 请在下方签名;否则视为不同意。 ) 学 位 论 文 作 者 签 名 :5 1 体 立 签 字 日 期 :2 0 6 , 1 1 5 - 导师签名: 签字日期: 砂在 ， s. r , r 歹 东北大学 硕士学位论文 第一章 前言 第一章 前言 1 . 1课题来源 本文的研究来源于课题 i n t e rne t 上支持高质量 e - s e r v i c e s 的零输入个性化技 术的 研究” ， 这是国 家自 然科学基金资 助的 项目 ( 项目 批准号: 6 0 1 7 3 0 5 1 ) 。 该课 题 在对个性数据采集技术、we b 数据仓库技术、面向个性化的we b 数据挖掘技术、 个性化规则解析技术以 及个 性化服务 推荐技术等关 键技术进行研究的基础之上， 提出了一种结合数据挖掘、规则解析和信息集成技术的 c ( c o l l e c t i n g ) m ( m i n i n g ) r ( r e c o m m e n d i n g ) 个性化方法，并设计和实现了一个个性化推荐系统 s ma rt we b a 1 . 2背景介绍 十八世纪的法国，在启蒙运动精神的鼓舞下，一些学者提出一项雄心勃勃、 近乎天方夜谭的计划:编制一本能够反应人类全部文明、汇聚所有知识的大百科 全书。在第三次科技革命浪潮的推动下，计算机和互联网技术飞速发展，先贤的 梦想逐渐变成现实。 但是一个随之而来的挑战出现了:如何有效的使用、组织和 管理这些海量信息呢?如何让 “ 大百科全书”真正为人们服务呢? i n t e rn e t 上的信息浩如烟海，信息爆炸时代已经到来。第三次中国互联网络信 启 、 资源数量调查报告内 容显示:全国 域名1 1 8 7 3 8 0 个， 全国网站数约5 9 5 5 5 0 个， 其中c o m和 c o m.c n比例最高，网站信息最主要来源是采集，比例高达 8 8 . 8 %, 9 5 .4 %网站提供简体中文阅读，3 1 .3 %提供全站搜索;全国网页总数己经达到 3 1 1 , 8 6 4 , 5 9 0 个，相较2 0 0 2 年，2 0 0 3 年网页数量增长了近9 8 . 5 %;截至2 0 0 4 年2 月， 全国 在线数 据库总 量为1 6 9 8 6 7 个 o 1 人类要成为海量信息的主人，而不是信息的奴隶。如何组织和管理这些海量 信息?如何准确、方便和快捷的帮助人类找到感兴趣的信息?如何根据定制用户 的兴趣为用户提供个性化的服务?如何跟踪和发现用户的兴趣，从而为用户推荐 他们所感兴趣的信息?在这种巨大的应用背景下，文本挖掘技术应运而生，近年 来得到研究人员的广泛关注。 文本挖掘是以计算语言学、统计数理分析为理论基础，结合机器学习和信息 检索技术，从大量的文本数据中发现和提取隐含的、事先未知的知识，最终形成 用户可理解的、有价值的信息和知识的过程。作为一个新的数据挖掘研究领域， 目前尚无统一的、确切的定义。内容挖掘多为基于文本信息的挖掘。按照文本挖 东北大学 硕士学位论文 第一章 前言 第一章 前言 1 . 1课题来源 本文的研究来源于课题 i n t e rne t 上支持高质量 e - s e r v i c e s 的零输入个性化技 术的 研究” ， 这是国 家自 然科学基金资 助的 项目 ( 项目 批准号: 6 0 1 7 3 0 5 1 ) 。 该课 题 在对个性数据采集技术、we b 数据仓库技术、面向个性化的we b 数据挖掘技术、 个性化规则解析技术以 及个 性化服务 推荐技术等关 键技术进行研究的基础之上， 提出了一种结合数据挖掘、规则解析和信息集成技术的 c ( c o l l e c t i n g ) m ( m i n i n g ) r ( r e c o m m e n d i n g ) 个性化方法，并设计和实现了一个个性化推荐系统 s ma rt we b a 1 . 2背景介绍 十八世纪的法国，在启蒙运动精神的鼓舞下，一些学者提出一项雄心勃勃、 近乎天方夜谭的计划:编制一本能够反应人类全部文明、汇聚所有知识的大百科 全书。在第三次科技革命浪潮的推动下，计算机和互联网技术飞速发展，先贤的 梦想逐渐变成现实。 但是一个随之而来的挑战出现了:如何有效的使用、组织和 管理这些海量信息呢?如何让 “ 大百科全书”真正为人们服务呢? i n t e rn e t 上的信息浩如烟海，信息爆炸时代已经到来。第三次中国互联网络信 启 、 资源数量调查报告内 容显示:全国 域名1 1 8 7 3 8 0 个， 全国网站数约5 9 5 5 5 0 个， 其中c o m和 c o m.c n比例最高，网站信息最主要来源是采集，比例高达 8 8 . 8 %, 9 5 .4 %网站提供简体中文阅读，3 1 .3 %提供全站搜索;全国网页总数己经达到 3 1 1 , 8 6 4 , 5 9 0 个，相较2 0 0 2 年，2 0 0 3 年网页数量增长了近9 8 . 5 %;截至2 0 0 4 年2 月， 全国 在线数 据库总 量为1 6 9 8 6 7 个 o 1 人类要成为海量信息的主人，而不是信息的奴隶。如何组织和管理这些海量 信息?如何准确、方便和快捷的帮助人类找到感兴趣的信息?如何根据定制用户 的兴趣为用户提供个性化的服务?如何跟踪和发现用户的兴趣，从而为用户推荐 他们所感兴趣的信息?在这种巨大的应用背景下，文本挖掘技术应运而生，近年 来得到研究人员的广泛关注。 文本挖掘是以计算语言学、统计数理分析为理论基础，结合机器学习和信息 检索技术，从大量的文本数据中发现和提取隐含的、事先未知的知识，最终形成 用户可理解的、有价值的信息和知识的过程。作为一个新的数据挖掘研究领域， 目前尚无统一的、确切的定义。内容挖掘多为基于文本信息的挖掘。按照文本挖 东 北大学 硕士学 位论天第一章 前言 掘的对象可把文本挖掘分为基于单文档的数据挖掘和基于文档集的数据挖掘。基 干单文档的数据挖掘对文档的分析并不涉及其它文档，其主要的挖掘技术有:文 本摘要、信息提取 ( 包括名字提取、短语提取、关系提取等) 。基于文档集的数据 挖掘是对大规模的文档数据进行模式抽取，其主要的技术有:文本分类、文本聚 类、个性化文本过滤、文档作者归属、因素分析等。从功能上，文本挖掘主要是 对大量文档集合的内容进行总结、分类、聚类、关联分析等。下面分别予以介绍。 1 .2 . 1文本总结 文档总结又称之为文本摘要，是文本挖掘的一个重要内容。它是指从文档中 抽取关键信息，用简洁的形式对文档内容进行摘要和解释，使用户无须浏览全文 即可了解文档或文档集合的总体内容。其目的是对文本信息进行浓缩，给出其紧 凑的描述，文本总结在有些场合十分有用，如搜索引擎在向用户返回查询结果时， 通常需要给出文档的摘要。目 前，绝大部分搜索引擎采用的方法是简单地截取文 档的 前几 行。 文 献2 提出了 使用中 心文 档代表 文档 集合， 使 用中 心词汇表示文档的 方法， 并给出了 求取中心文档和中心词汇的算法。 摘要算法常用的技术有: 采用 词性标注，进行切词分析; 用统计方法提取高频词，以确定摘要。有些算法对 开始句和结束句中出现的短语给予较高的权重;有些方法通过寻找提示短语卜确 定重要句子，如结论语句等。主要应用于多文本摘要、多语言摘要、多媒体摘要 等方面。目 前， 网页摘要主要基于自 动文摘技术( 机械文摘和理解文摘) ， 文本自 动 摘要方法分为表面级、实体级、论述级和知识库四种 ( 限于篇幅，不作详述) 。 1 .2 .2文本聚类 文 本 聚 类也是 一 种文 本 挖掘， 是 一 类 典 型的 无 监 督( u n s u p e r v i s e d i n d u c t io n ) 的机器学习问题。文本聚类是指把一组对象集合按照相似性归成若千类别。与分 类有所不同， 聚类没有预先定义好主题类别标记，需要由聚类学习算法来自 动确 定。其目 标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能 的大，内聚性尽可能的强，而不同簇间的相似度尽可能的小，即 “ 物以类聚” 。聚 类可以按照文档内容聚类， 也可按文档属性聚类o h e a r s t 等人的研究己经证明了 “ 类 聚假设” ，即与用户查询相关的文档通常会类聚得比较近， 而远离与用户不相关的 文档13 1 。 因此， 我们可以利用文本聚类技术， 提供大规模文档集内容的总括: 识别 隐藏的文档间的相似度:减轻浏览相关、相似信息的过程。如将搜索引擎的检索 结果划分为若千个簇， 用户只需考虑那些相关的簇，大大缩小了所需要浏览的结 果数量。 东 北大学 硕士学 位论天第一章 前言 掘的对象可把文本挖掘分为基于单文档的数据挖掘和基于文档集的数据挖掘。基 干单文档的数据挖掘对文档的分析并不涉及其它文档，其主要的挖掘技术有:文 本摘要、信息提取 ( 包括名字提取、短语提取、关系提取等) 。基于文档集的数据 挖掘是对大规模的文档数据进行模式抽取，其主要的技术有:文本分类、文本聚 类、个性化文本过滤、文档作者归属、因素分析等。从功能上，文本挖掘主要是 对大量文档集合的内容进行总结、分类、聚类、关联分析等。下面分别予以介绍。 1 .2 . 1文本总结 文档总结又称之为文本摘要，是文本挖掘的一个重要内容。它是指从文档中 抽取关键信息，用简洁的形式对文档内容进行摘要和解释，使用户无须浏览全文 即可了解文档或文档集合的总体内容。其目的是对文本信息进行浓缩，给出其紧 凑的描述，文本总结在有些场合十分有用，如搜索引擎在向用户返回查询结果时， 通常需要给出文档的摘要。目 前，绝大部分搜索引擎采用的方法是简单地截取文 档的 前几 行。 文 献2 提出了 使用中 心文 档代表 文档 集合， 使 用中 心词汇表示文档的 方法， 并给出了 求取中心文档和中心词汇的算法。 摘要算法常用的技术有: 采用 词性标注，进行切词分析; 用统计方法提取高频词，以确定摘要。有些算法对 开始句和结束句中出现的短语给予较高的权重;有些方法通过寻找提示短语卜确 定重要句子，如结论语句等。主要应用于多文本摘要、多语言摘要、多媒体摘要 等方面。目 前， 网页摘要主要基于自 动文摘技术( 机械文摘和理解文摘) ， 文本自 动 摘要方法分为表面级、实体级、论述级和知识库四种 ( 限于篇幅，不作详述) 。 1 .2 .2文本聚类 文 本 聚 类也是 一 种文 本 挖掘， 是 一 类 典 型的 无 监 督( u n s u p e r v i s e d i n d u c t io n ) 的机器学习问题。文本聚类是指把一组对象集合按照相似性归成若千类别。与分 类有所不同， 聚类没有预先定义好主题类别标记，需要由聚类学习算法来自 动确 定。其目 标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能 的大，内聚性尽可能的强，而不同簇间的相似度尽可能的小，即 “ 物以类聚” 。聚 类可以按照文档内容聚类， 也可按文档属性聚类o h e a r s t 等人的研究己经证明了 “ 类 聚假设” ，即与用户查询相关的文档通常会类聚得比较近， 而远离与用户不相关的 文档13 1 。 因此， 我们可以利用文本聚类技术， 提供大规模文档集内容的总括: 识别 隐藏的文档间的相似度:减轻浏览相关、相似信息的过程。如将搜索引擎的检索 结果划分为若千个簇， 用户只需考虑那些相关的簇，大大缩小了所需要浏览的结 果数量。 东 北大学 硕士学 位论天第一章 前言 掘的对象可把文本挖掘分为基于单文档的数据挖掘和基于文档集的数据挖掘。基 干单文档的数据挖掘对文档的分析并不涉及其它文档，其主要的挖掘技术有:文 本摘要、信息提取 ( 包括名字提取、短语提取、关系提取等) 。基于文档集的数据 挖掘是对大规模的文档数据进行模式抽取，其主要的技术有:文本分类、文本聚 类、个性化文本过滤、文档作者归属、因素分析等。从功能上，文本挖掘主要是 对大量文档集合的内容进行总结、分类、聚类、关联分析等。下面分别予以介绍。 1 .2 . 1文本总结 文档总结又称之为文本摘要，是文本挖掘的一个重要内容。它是指从文档中 抽取关键信息，用简洁的形式对文档内容进行摘要和解释，使用户无须浏览全文 即可了解文档或文档集合的总体内容。其目的是对文本信息进行浓缩，给出其紧 凑的描述，文本总结在有些场合十分有用，如搜索引擎在向用户返回查询结果时， 通常需要给出文档的摘要。目 前，绝大部分搜索引擎采用的方法是简单地截取文 档的 前几 行。 文 献2 提出了 使用中 心文 档代表 文档 集合， 使 用中 心词汇表示文档的 方法， 并给出了 求取中心文档和中心词汇的算法。 摘要算法常用的技术有: 采用 词性标注，进行切词分析; 用统计方法提取高频词，以确定摘要。有些算法对 开始句和结束句中出现的短语给予较高的权重;有些方法通过寻找提示短语卜确 定重要句子，如结论语句等。主要应用于多文本摘要、多语言摘要、多媒体摘要 等方面。目 前， 网页摘要主要基于自 动文摘技术( 机械文摘和理解文摘) ， 文本自 动 摘要方法分为表面级、实体级、论述级和知识库四种 ( 限于篇幅，不作详述) 。 1 .2 .2文本聚类 文 本 聚 类也是 一 种文 本 挖掘， 是 一 类 典 型的 无 监 督( u n s u p e r v i s e d i n d u c t io n ) 的机器学习问题。文本聚类是指把一组对象集合按照相似性归成若千类别。与分 类有所不同， 聚类没有预先定义好主题类别标记，需要由聚类学习算法来自 动确 定。其目 标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能 的大，内聚性尽可能的强，而不同簇间的相似度尽可能的小，即 “ 物以类聚” 。聚 类可以按照文档内容聚类， 也可按文档属性聚类o h e a r s t 等人的研究己经证明了 “ 类 聚假设” ，即与用户查询相关的文档通常会类聚得比较近， 而远离与用户不相关的 文档13 1 。 因此， 我们可以利用文本聚类技术， 提供大规模文档集内容的总括: 识别 隐藏的文档间的相似度:减轻浏览相关、相似信息的过程。如将搜索引擎的检索 结果划分为若千个簇， 用户只需考虑那些相关的簇，大大缩小了所需要浏览的结 果数量。 东北大学硕士学位论文第一幸 前言 目 前， 有多种文本聚类算法， 大致可以分为两种类型: 以g - h a c等算法为代 表的 层 次凝 聚 ( h ie r a r c h ic a l c lu s t e r in g ) 法 ja i ， 又分为 聚合聚类 ( a g g lo m e r a ti v e c lu s t e ri n g ) 和分裂聚类 ( s p l itt i n g c lu s t e r in g ) ;以k - m e a n s 等算法为代表的 平面 划分法5 1 。文献fi 介绍了 将 g - h a c和 k - m e a n s 集合起来的 b u c k s h o t 方法和 f r a c t i o n a t i o n 方法。 层次聚类方法是最为常用的聚类方法， 它能够生成层次化的嵌 套簇，且准确度较高。但是在每次合并时，需要全局地比较所有簇之间的相似度， 并选择出最佳的两个簇，因此运行速度较慢，不适合于大量文档的集合。 平面划 分法与层次凝聚法的区别在于它将文档集合水平地分割为若干个簇，而不是生成 层次化的嵌套簇。 1 .2 .3信息提取 信息提取是通过挖掘从文本中获得更多隐藏的信息，如短语间的关系、 规则、 典型框架等，这些信息将体现主题、意图、期望及要求等。信息提取有很好的商 业价值，对用户需求、市场预测、趋向 分析等都很有帮助。目 前，信息提取主要 针 对于 名字 提取、 缩写 识 别、 关 系 提取。 主 要的 技 术是 基 于 语言 学的 启 发 式 规 则， 利用自 然语言处理技术提取文本中的信息 、 。通过建立各种词表，如同义词表、蕴 含词表等解决一词多义及一义多词的语言复杂性。把文档中出现的单词分成不同 的类，并且度量它们对文档内容的重要性，充分利用文本中有限的结构信息。 1 .2 .4关联分析 关联规则是 k d d( 知识发现) 研究中的一个重要课题。 该问题是 r .a g r a w a l 等人提出的， 挖掘的 对象主要是事务型数据库 ( t r a n s a c t i o n a l d a t a b a s e s ) ， 其中 针对 的应用主要是售货数据，也称货篮数据。随着关联规则研究的深入，己不仅仅限 于在事务数据库中挖掘相关规则，同样可以基于不同数据源挖掘，如关系型数据 库、面问对象数据库、多维数据库、数据仓库等。 文本挖掘中的关联分析是指从文本集合中找出不同特征词语之间的关联关 系。 其基本思想是将类a p r i o r i 的关联规则算法应用于中文文本挖掘。 将文本集d 看 成交易数 据库， i = i l , i 2 , . , i m 是 个。 特征词的 集合， 文本集中的 文 本看成 交 易数据库中的每个交易， 睡个文本都包含若干个特征项i l , i 2 , , ik ， 它们都属于i , 用类a p r i o ri 算法求出 文本集中 关于 特 征词的 频繁项集， 然后利用频繁项 集生成 满 足最小置信度的所有关联规则。这样就能求出特征项的关联关系，进而了解各文 本间的关联关系。 b r in 提出了一种从大量文档中发现一对词语出现模式的算法，并用在w e b 上 东北大学硕士学位论文第一幸 前言 目 前， 有多种文本聚类算法， 大致可以分为两种类型: 以g - h a c等算法为代 表的 层 次凝 聚 ( h ie r a r c h ic a l c lu s t e r in g ) 法 ja i ， 又分为 聚合聚类 ( a g g lo m e r a ti v e c lu s t e ri n g ) 和分裂聚类 ( s p l itt i n g c lu s t e r in g ) ;以k - m e a n s 等算法为代表的 平面 划分法5 1 。文献fi 介绍了 将 g - h a c和 k - m e a n s 集合起来的 b u c k s h o t 方法和 f r a c t i o n a t i o n 方法。 层次聚类方法是最为常用的聚类方法， 它能够生成层次化的嵌 套簇，且准确度较高。但是在每次合并时，需要全局地比较所有簇之间的相似度， 并选择出最佳的两个簇，因此运行速度较慢，不适合于大量文档的集合。 平面划 分法与层次凝聚法的区别在于它将文档集合水平地分割为若干个簇，而不是生成 层次化的嵌套簇。 1 .2 .3信息提取 信息提取是通过挖掘从文本中获得更多隐藏的信息，如短语间的关系、 规则、 典型框架等，这些信息将体现主题、意图、期望及要求等。信息提取有很好的商 业价值，对用户需求、市场预测、趋向 分析等都很有帮助。目 前，信息提取主要 针 对于 名字 提取、 缩写 识 别、 关 系 提取。 主 要的 技 术是 基 于 语言 学的 启 发 式 规 则， 利用自 然语言处理技术提取文本中的信息 、 。通过建立各种词表，如同义词表、蕴 含词表等解决一词多义及一义多词的语言复杂性。把文档中出现的单词分成不同 的类，并且度量它们对文档内容的重要性，充分利用文本中有限的结构信息。 1 .2 .4关联分析 关联规则是 k d d( 知识发现) 研究中的一个重要课题。 该问题是 r .a g r a w a l 等人提出的， 挖掘的 对象主要是事务型数据库 ( t r a n s a c t i o n a l d a t a b a s e s ) ， 其中 针对 的应用主要是售货数据，也称货篮数据。随着关联规则研究的深入，己不仅仅限 于在事务数据库中挖掘相关规则，同样可以基于不同数据源挖掘，如关系型数据 库、面问对象数据库、多维数据库、数据仓库等。 文本挖掘中的关联分析是指从文本集合中找出不同特征词语之间的关联关 系。 其基本思想是将类a p r i o r i 的关联规则算法应用于中文文本挖掘。 将文本集d 看 成交易数 据库， i = i l , i 2 , . , i m 是 个。 特征词的 集合， 文本集中的 文 本看成 交 易数据库中的每个交易， 睡个文本都包含若干个特征项i l , i 2 , , ik ， 它们都属于i , 用类a p r i o ri 算法求出 文本集中 关于 特 征词的 频繁项集， 然后利用频繁项 集生成 满 足最小置信度的所有关联规则。这样就能求出特征项的关联关系，进而了解各文 本间的关联关系。 b r in 提出了一种从大量文档中发现一对词语出现模式的算法，并用在w e b 上 东北大学硕士学位论文第一幸 前言 目 前， 有多种文本聚类算法， 大致可以分为两种类型: 以g - h a c等算法为代 表的 层 次凝 聚 ( h ie r a r c h ic a l c lu s t e r in g ) 法 ja i ， 又分为 聚合聚类 ( a g g lo m e r a ti v e c lu s t e ri n g ) 和分裂聚类 ( s p l itt i n g c lu s t e r in g ) ;以k - m e a n s 等算法为代表的 平面 划分法5 1 。文献fi 介绍了 将 g - h a c和 k - m e a n s 集合起来的 b u c k s h o t 方法和 f r a c t i o n a t i o n 方法。 层次聚类方法是最为常用的聚类方法， 它能够生成层次化的嵌 套簇，且准确度较高。但是在每次合并时，需要全局地比较所有簇之间的相似度， 并选择出最佳的两个簇，因此运行速度较慢，不适合于大量文档的集合。 平面划 分法与层次凝聚法的区别在于它将文档集合水平地分割为若干个簇，而不是生成 层次化的嵌套簇。 1 .2 .3信息提取 信息提取是通过挖掘从文本中获得更多隐藏的信息，如短语间的关系、 规则、 典型框架等，这些信息将体现主题、意图、期望及要求等。信息提取有很好的商 业价值，对用户需求、市场预测、趋向 分析等都很有帮助。目 前，信息提取主要 针 对于 名字 提取、 缩写 识 别、 关 系 提取。 主 要的 技 术是 基 于 语言 学的 启 发 式 规 则， 利用自 然语言处理技术提取文本中的信息 、 。通过建立各种词表，如同义词表、蕴 含词表等解决一词多义及一义多词的语言复杂性。把文档中出现的单词分成不同 的类，并且度量它们对文档内容的重要性，充分利用文本中有限的结构信息。 1 .2 .4关联分析 关联规则是 k d d( 知识发现) 研究中的一个重要课题。 该问题是 r .a g r a w a l 等人提出的， 挖掘的 对象主要是事务型数据库 ( t r a n s a c t i o n a l d a t a b a s e s ) ， 其中 针对 的应用主要是售货数据，也称货篮数据。随着关联规则研究的深入，己不仅仅限 于在事务数据库中挖掘相关规则，同样可以基于不同数据源挖掘，如关系型数据 库、面问对象数据库、多维数据库、数据仓库等。 文本挖掘中的关联分析是指从文本集合中找出不同特征词语之间的关联关 系。 其基本思想是将类a p r i o r i 的关联规则算法应用于中文文本挖掘。 将文本集d 看 成交易数 据库， i = i l , i 2 , . , i m 是 个。 特征词的 集合， 文本集中的 文 本看成 交 易数据库中的每个交易， 睡个文本都包含若干个特征项i l , i 2 , , ik ， 它们都属于i , 用类a p r i o ri 算法求出 文本集中 关于 特 征词的 频繁项集， 然后利用频繁项 集生成 满 足最小置信度的所有关联规则。这样就能求出特征项的关联关系，进而了解各文 本间的关联关系。 b r in 提出了一种从大量文档中发现一对词语出现模式的算法，并用在w e b 上 东 北大 学硕士学位论文第一章 前言 寻找作者和书名的出现模式， 从而发现了数千本在a m a z o n网站上找不到的新书籍 t 1 。 w a n g 等 人以w e b 上的电 影 介绍 作 为 测 试文 档， 通过 使 用o e m模型 从 这些 半 结构化的页面中抽取词语项，进而得到一些关于电影名称、导演、演员、编剧的 出 现模式 1 8 1 1 .2 .5文本分类 由于 i n t e rne t 的飞速发展，i n t e rn e t 上的电子资源成指数方式快速增长，因此 在这种情况下，人工的这些电子资源进行归类耗费大量的人力，并且归类效果非 常不理想，不能快速地将所搜索的信息及时地进行处理，因此研究具有机器学习 的智能的自 动文本分类系统，能够根据给定的样本数据进行训练得到分类模型， 利用这种分类模型对未知样本或待分类的网页信息进行自 动归类可以极大地降低 人工繁重的重复性劳动，并且可以实现快速归类，提高归类质量。正因为这些优 点，文本分类技术在很多领域得到了广泛的应用。在信息检索领域，文本分类用 于对用户模型的描述:在数字图书馆领域，文本分类是组织和管理知识的重要手 段之一，比如对知识和电子资源进行分门别类; 对于特定领域搜索引擎，其爬虫 的核心部件是一个文本分类器，用于筛选与特定领域内容相关的we b页。在个性 化推荐领域，文本分类用于描述用户的兴趣，生成用户兴趣模板，从而对推荐系 统的推荐信息进行过滤。 近年来，文本分类领域在技术和应用上都取得了很大发展，但是仍存在诸多 挑战。 文本数据的高维性与稀疏性:在文本处理过程中，通常情况是:将文档集合 中的每个文档实行分词处理，统计每个文档出现的词以及相应的词频，然后将每 个文档出现的词合并成一个词空间，必要的情况下统计出现在词空间中每个词的 词频，所以词空间中出现的不同的词的个数达到几万、几十万之多。表示一篇文 档的时候，无论文档用向量空间模型还是概率统计模型来表示，文档的特征的维 度都和词空间的维度一样，只不过在文档中出现的词的词频按照实际词频统计， 而文档中没有出现的但在词空间中出现的词的词频设为零或者选择一定的平滑处 理。这样出现了一个问题，某个文档中出现的词只占词空间中很少一部分，文档 特征表示非常稀疏。文本数据的高维性和稀疏性，不但使分类算法的时间复杂度 和空间复杂度增加，而且会到文本特征表示的不准确，严重影响文本分类性能和 分类质量。 分类器更新自动化:在某些情况下，文本分类器一经设计完成就一成不变或 者很少改动。但是越来越多的情况是:世界在不断的向前发展，新事物不断涌现， 东 北大 学硕士学位论文第一章 前言 寻找作者和书名的出现模式， 从而发现了数千本在a m a z o n网站上找不到的新书籍 t 1 。 w a n g 等 人以w e b 上的电 影 介绍 作 为 测 试文 档， 通过 使 用o e m模型 从 这些 半 结构化的页面中抽取词语项，进而得到一些关于电影名称、导演、演员、编剧的 出 现模式 1 8 1 1 .2 .5文本分类 由于 i n t e rne t 的飞速发展，i n t e rn e t 上的电子资源成指数方式快速增长，因此 在这种情况下，人工的这些电子资源进行归类耗费大量的人力，并且归类效果非 常不理想，不能快速地将所搜索的信息及时地进行处理，因此研究具有机器学习 的智能的自 动文本分类系统，能够根据给定的样本数据进行训练得到分类模型， 利用这种分类模型对未知样本或待分类的网页信息进行自 动归类可以极大地降低 人工繁重的重复性劳动，并且可以实现快速归类，提高归类质量。正因为这些优 点，文本分类技术在很多领域得到了广泛的应用。在信息检索领域，文本分类用 于对用户模型的描述:在数字图书馆领域，文本分类是组织和管理知识的重要手 段之一，比如对知识和电子资源进行分门别类; 对于特定领域搜索引擎，其爬虫 的核心部件是一个文本分类器，用于筛选与特定领域内容相关的we b页。在个性 化推荐领域，文本分类用于描述用户的兴趣，生成用户兴趣模板，从而对推荐系 统的推荐信息进行过滤。 近年来，文本分类领域在技术和应用上都取得了很大发展，但是仍存在诸多 挑战。 文本数据的高维性与稀疏性:在文本处理过程中，通常情况是:将文档集合 中的每个文档实行分词处理，统计每个文档出现的词以及相应的词频，然后将每 个文档出现的词合并成一个词空间，必要的情况下统计出现在词空间中每个词的 词频，所以词空间中出现的不同的词的个数达到几万、几十万之多。表示一篇文 档的时候，无论文档用向量空间模型还是概率统计模型来表示，文档的特征的维 度都和词空间的维度一样，只不过在文档中出现的词的词频按照实际词频统计， 而文档中没有出现的但在词空间中出现的词的词频设为零或者选择一定的平滑处 理。这样出现了一个问题，某个文档中出现的词只占词空间中很少一部分，文档 特征表示非常稀疏。文本数据的高维性和稀疏性，不但使分类算法的时间复杂度 和空间复杂度增加，而且会到文本特征表示的不准确，严重影响文本分类性能和 分类质量。 分类器更新自动化:在某些情况下，文本分类器一经设计完成就一成不变或 者很少改动。但是越来越多的情况是:世界在不断的向前发展，新事物不断涌现， 东北大学硕士学位论文第一章 前言 用户的兴趣和关注的焦点会随着时间的变化而不断地变化。这种情况下，分类器 也应该随着时间的变化而不断地更新，但是这种更新不是突发式的，而是渐进式 的、增量的更新。如果每次更新都由人工来完成将会耗费大量的人、财、物，所 以对分类器的更新必须形成一种自动化的更新机制。基于以上考虑，选择好的分 类器更新策略，实现分类器更新自 动化也是当前研究的一个难点。 文本模型选择:正确的选择文本模型对于文本分类的结果至关重要。当前的 文本模型分为两大类，一种是向量空间模型，一种是概率统计模型，不同的模型 各有优缺点。不同的模型都在某些领域有较好的应用效果。比如概率模型中的高 斯模型适合于低维数据， 多变量贝努利模型、 多项式模型和、 mf模型比较适合于 文本文档，马尔可夫链和隐马尔可夫模型在时间序列应用中表现较好。另外混合 模型方法在文本领域也有上佳的表现。因此，在实际情况下，根据不同的应用选 择正确合理的文本模型也是分类领域的一个重要挑战。 小训练样本:收集有标签数据代价昂贵，需要大量的人工给无标签数据加上 标签，所以在应用中通常的情况是可得到的有标签数据比较稀少，这对于很多文 本分类算法是一个致命的缺陷，因为传统的文本分类算法需要大量的样本数据才 能训练出准确的、高质量a -ij 文本分类器。所以，基于小训练样本的高质量的文本 分类算法是研究的难点。 对于克服数据的高维性和稀疏性，主要在文本分类预处理阶段展开研究， 本 文主要针对后两个挑战模型选择和小训练样本。本文分析了单一概率模型难 以准确刻画类特征的原因，提出了一种新的基于主题和通用的混合模型作为类模 型，以期更准确地拟合