（控制理论与控制工程专业论文）文本挖掘技术研究及应用.pdf

abs tract wit h t h e d e v e l o p m e n t o f i n t e rn e t a n d i n f o r m a t i o n t e c h n o l o g y , t h e p r o b l e m r i c h da t a a n d p o o r i n f o r ma t i o n i n f o r m a t i o n e x p l o s i o n h a s a r i s e n , t h a t i s , w i t h we b s r a p i d g r o w t h , q u i c k l y o b t a i n i n g _ o f bu t mo r e d i f f i c u l t b e c a u s e o f i n t e rne t s r e q u i r e m e n t q u i c k l y a n d e ff i c i e n t l y i n f o r m a t i o n m i n i n g o n we b i s a n e w t o r e t r i e v e i n f o r ma t i o n o n i n t e rne t . i t o p e n ing w h a t u s e r s n e e d o n www i s g e tt i n g a n d h e t e r o g e n e it y . h o w t o o b t a i n t h e g e tt i n g m o r ea n d t e c h n o l o g y t h a t a d o p t s i s a n e w r e s e a r c h i s s u e w e f o c u s o n s o m e k e y t e c h n o l o g i e s o f w e b t e x t i n f o r m a t i o n t h e ma i n c o n t e n t s o f t h i s t h e s i s : m o r e i m p o rt a n t . t e x t d a t a m i n i n g t e c h n o l o g y t h a t d r a w s g r e a t i n t e r e s t m i n i n g . t h e f o l l o w i n g i s i n t h i s p a p e r , a s y s t e m ic d i s c u s s i o n a b o u t t h e p r i n c i p le o f w e b a n d t e x t m i n i n g i s p r e s e n t e d , i n c l u d i n g t h e c o n c e p t s , m e t h o d s a n d t a x o n o m y . t h e n t h e g e n e r a l m i n i n g p r o c e s s in g i s in t r o d u c e d . b e f o r e p r o c e s s i n g t h e t e x t , w e m u s t s e g m e n t c h in e s e w o r d b e c a u s e o f h a v i n g n o s e g m e n t a t i o n b e t w e e n c h in e s e c h a r a c t e r s . we u s e t h e a d j a c e n t m a t c h i n g a l g o r i t h m o n c h i n e s e w o r d s e g m e n t a t i o n , w h i c h c a n r e c o g n i z e a n d c o r r e c t t h e s e m a n t i c a m b i g u o u s w o r d g r o u p . i t a l s o c a n d i m i n i s h t h e r a t e o f i n a c c u r a t e s e g m e n t a t i o n w e a d o p t v e c t o r s p a c e m o d e l ( v s m ) t o r e p r e s e n t d o c u m e n t s . d u e t o m a n y o t h e r r e d u n d a n t a n d u s e l e s s w o r d s i n t h e t e x t v e c t o r , t h e v e c t o r d i m e n s i o n i s v e ry l a r g e . t o s e tt l e t h i s p r o b l e m , w e a d o p t a s t a t i s t i c a l m e t h o d - p r i n c ip a l c o m p o n e n t s a n a l y s i s t o e x t r a c t t e x t f e a t u r e . t h i s m e t h o d c a n b e u s e d t o i m p r o v e t h e s k e w i n t e r s e c t i o n o n t h e v e c t o r s p a c e m o d e l s . u s i n g t h i s m e t h o d , w e c a n e x t r a c t s e v e r a l s y n t h e t i c f e a t u r e s t o s t a n d f o r a l l t h e f o r m e r i n f o r m a t i o n w e l l , a n d c a n r e d u c e t h e d i m e n s i o n g r e a t l y . t h e m e t h o d h as m a n y g o o d c h a r a c t e r s : p r e d o m i n a n t v a r i a n c e , l e s t i n f o r m a t i o n l o s t , t h e b e s t c o r r e l a t i o n a n d s o o n . w e a l s o a d o p t a n o t h e r s t a t i s t i c s m e t h o d - s e q u e n t i a l c l u s t e r i n g o n t e x t s t r u c t u r e a n a l y s i s . w e u s e i t t o a n a l y z e t h e s t r u c t u r e o f t h e t e x t s , a p p l i e s t h e t e x t h i e r a r c h i c a l a n a l y s i s a p p r o a c h t o e x t r a c t t h e k e y w o r d s fr o m t h e t e x t s t e x t c l as s i f i c a t i o n i s a n o t h e r i m p o rt a n t i s s u e i n t h e f i e l d o f t e x t i n f o r m a t i o n p r o c e s s in g . i n t h i s p a p e r , a d o c u m e n t c l as s i f i c a t io n i s d e s i g n e d a n d i m p l e m e n t e d . e s p e c i a l l y , it d i s c u s s e s s o m e k e y t e c h n i q u e s i n t h e im p l e m e n t a t i o n o f t h i s m o d e l . t h e r e s u l t s o f t h e e x p e r i m e n t s h o w t h a t t h e t w o i m p o r t a n t n o r m s w h i c h a r e u s e d f o r e v a l u a t i n g t h e c l a s s i f i c a t i o n a l g o r i t h m: p r e c i s i o n a n d r e c a l l , a r e q u i t e s a t i s f y i n g . k e y w o r d s : t e x t m i n i n g w o r d s e g m e n t a t i o n f e a t u r e e x t r a c t t e x t cl a s s i f i c a t i o n vs m 曰. 一主赳丝遨塑壁r 翌 一一一一一一 序言 随着信息技术的高速发展，尤其是 i n t e r n e t 应用的普及，人们每天都要获取 和处理大量的信息， i n t e rn e t 己经发展为当今世界上最大的信息库和全球范围内传 播信息的最主要渠道。 其中www ( w o r l d w i d e w e b ) 的发展最为迅速。 自 从1 9 9 1 年诞生以来，它已经发展为拥有几千万用户和约 4 0 0万站点、3亿页面的巨大分 布式信息空间， 而且这个数字仍以 每4 至6 个月翻一倍的速度增加。 i n t e rn e t 是以 超文本的形式呈现给用户的，包含了从技术资料、商业信息到新闻报道、娱乐信 息等多种类别和形式的信息，构成了一个异常庞大的具有异构性、开放性的分布 式数据库。随着i n t e rn e t 的爆炸性增长， i n t e r n e t 己经发展成为包含多种信息资源、 站点遍布全球的巨 大信息服务网络，为用户提供了一个极具价值的 信息源。 在we b 迅猛发展的同时，我们不能忽视 “ 信息爆炸”的问题，即信息极大丰 富而知识相对匾乏。 面对爆炸性增长的i n t e rn e t 信息资源， 使用户感到十分的茫然。 由于i n t e r n e t 上数据信息形式和内 容没有一个统一的格式和结构， 信息资源分布非 常散乱， 重复信息、 相互矛盾的 数据比比皆 是。 而且i n t e rn e t 上的信息基本上呈几 何级数增长，面对汹涌而来的信息，有限的数据信息处理能力和技术已经无法应 对信息爆炸而知识贫乏的现象。从某种意义上说，用户很难准确快捷地获取所需 信息，出现了所谓的 “ 信息过载”和 “ 信息迷向”问题。因此，如何快速、准确 地从浩瀚地信息资源中提取用户所需要的信息已经成为一个新的研究课题。 www上的海量信息大多为自 然语言形式， 即使是h t ml也是以自 然语言为主体 加上部分的形式化描述语言。因此对自 然语言文本信息的加工处理需求目 前变得 十分紧迫，而对于文本信息的处理也日 益成为人们关注的研究热点。 数 据挖掘 ( d a t a m i n i n g ) 也可以 称为数 据库中的 知识 发现 ( k d d k n o w l e d g e d i s c o v e r y ) ， 可以 帮 助人 们从大量原始数据中 挖掘出 隐 含的、 有用的尚 未发现的 信 息和知识， 有效地解决信息丰富知识贫乏问 题 ( r i c h d a t a p o o r i n f o r m a t i o n ) 。 由于 i n t e rn e t 上大量的信息表现形式为文本形式， 因此， 基于w e b 文本信息的挖掘( t e x t m i n i n g ) 作为 知识发 现的 一 个新主题， 引 起了 人们的 极大兴 趣。 w e b文本信息挖 掘技术是数据挖掘技术在网络信息处理中的 应用。文本挖掘不同于数据挖掘，数 据挖掘处理的是结构化数据， 采用的方法大多是非常明确的定量方法。而文本挖 掘处理的是非结构化的文本，因此，它采用的方法与数据挖掘不同。它经常使用 的方法来自自 然语言理解和文本处理领域，如文本摘要、文本分类、文本检索等 技术。 w e b 文本信息的挖掘就是在对大量训练样本处理的基础上，得到文本数据间 的内在特征，并以此为依据对网络信息资源中进行有目的的信息提取。主要包括 文本的分词处理、文本特征表示及抽取、文本分类与文本聚类等内容。本文对此 给出了一些具体的方法及应用。 -一主些m 鱼巡鱼c r 旦一一 一 第一章we b 文本挖掘概述 当 前 w w w ( w o r l d w i d e w e b ) 正 在 深度和 广度方 面飞 速地发展 着， 而且其 信息 容量仍以 指数形势飞速增长， i n t e rn e t 也正在前所未有地改变我们的生活。www 上的一些主要工作，例如 we b 站点设计、w e b 服务设计、we b 站点的导航设计、 电子商务等工作正变得越来越复杂和越来越繁重。 在 w e b 迅猛发展的同时， 我们不能忽视“ 信息爆炸” 的问题，即信息极大丰 富而知识相对匾乏。 在这些大量、 异质的 w e b 信息资源中， 蕴含着具有巨大潜在 价值的知识。人们迫切需要能够从 we b上快速、有效地发现资源和知识的工具。 w e b上的搜索引擎部分地解决了资源发现问题，但由于精确度不高等原因，其效 果远不能使人满意。 此外， 搜索引擎的目的在于发现 w e b 上的资源，就 w e b 上 的知识发现而言，即使检索精度再高，搜索引擎也不能够胜任。为此，我们需要 开发比 信息检索层次更高的新技术。为了从大量数据的集合中发现有效、新颖、 有用、可理解的模式， 数据库领域采用了数据挖掘技术。但是，数据挖掘的绝大 部分工作所涉及的是结构化数据库， 很少有处理 w e b 上的异质、 非结构化信息的 工作。w e b挖掘作为数据挖掘的一个新主题，引起了人们的极大兴趣。同时，它 也是一个富于争议的研究方向。目 前， 对于 w e b 挖掘的含义、 功能等尚 无统一的 结论，需要国内外学者在理论上开展更多的讨论以进行精确地定义。此外，w e b 挖掘系统的开发对其研究也将起到很大推进作用。 下面我们主要介绍 we b 挖掘的定义，讨论 w e b 挖掘与传统的数据挖掘之间 的关系;对 we b 挖掘的任务进行了分类，讨论了 we b 文本挖掘和结构挖掘的功 能:介绍了 w e b 文本挖掘的方法，包括文本的特征表示、文本分类和文本聚类。 1 . 1 . we b 挖掘 w e b 挖掘是一项综合技术， 涉及 w e b 、 数据挖掘、 计算机语言学、 信息学等 多个领域。不同研究者从自 身的领域出发，对 w e b 挖掘的含义有着不同的理解， 项目 开发也各有其侧重点。 例如，有些计算机语言学家认为，w e b文档为自 然语 言理解提供了丰富的语料，可以从中自 动地学习词语的意义，以进行词义辨析或 确定词语所属的概念。我们从更为一般的角度出发， 对 w e b 挖掘作如下定义。 定义 1 . w e b 挖掘是指从大量 w e b 文档的集合 c中发现隐含的模式p 。 如果 将 c看作输入， 将p 看作输出，那么 w e b 挖掘的过程就是从输入到输出的一个 映射毛 :c - - p o w e b 挖掘从数据挖掘发展而来，因此其定义与我们熟知的数据挖掘定义相类 似。但是，w e b 挖掘与传统的数据挖掘相比有许多独特之处。首先，w e b 挖掘的 对象是大量、异质、分布的 w e b文档。我们认为，以w e b作为中间件对数据库 进行挖掘，以及对 we b 服务器上的日志、 用户信息等数据所开展的挖掘工作， 仍 属于传统的数据挖掘的范畴。其次，w e b在逻辑上是一个由文档节点和超链构成 一一2违鱼坠述竺丝迪旦一一一 的图，因此 w e b 挖掘所得到的模式可能是关于 w e b内容的，也可能是关于 w e b 结构的。 此外，由于 w e b 文档本身是半结构化或无结构的， 且缺乏机器可理解的 语义，而数据挖掘的对象局限于数据库中的结构化数据，并利用关系表格等存储 结构来发现知识， 因此有些数据挖掘技术并不适用于 we b 挖掘， 即使可用也需要 建立在对w e b文档进行预处理的基础之上。这样，开发新的 w e b 挖掘技术，以 及对 w e b 文档进行预处理以得到关于文档的特征表示，便成为 we b 挖掘研究的 重点。 1 . 2 we b 挖掘任务 1 . 2 . 1 we b 挖掘的分类 w e b 上信息的多样性决定了 w e b 挖掘任务的多样性。 按照处理对象的不同， 我们将 w e b 挖掘分为两大类:内容挖掘和结构挖掘。内 容挖掘指的是从 w e b 文 档的内容信息中抽取知识;而后者指的是从 w e b文档的结构信息中推导知识。 w e b内 容挖掘又分为 对文本文档( 包括 t e x t , h t m l等格式) 和多媒体文档( 包括 i m a g e , a u d i o , v i d e 。 等媒体类型 ) 的 挖掘。 w e b 结构 挖掘不仅 仅局限 于文档之间的 超链结构， 还包括文档内 部的结构、 文档 u r l 中的目 录路径结构等。 如图1 . 1 所 示. 在本文中， 我们仅对 w e b 上的文本挖掘和结构挖掘加以 讨论， 下文中提及的 “ 文档”指的是文本文档，不包括多媒体文档。 内容挖掘 文本挖掘 i i多媒体挖掘 超 链 挖 掘 一 内 部 结 构 挖 掘 i u r l 挖 掘 一 图1 . 1 w e b 挖掘的 分类 1 . 2 .2 we b 文本挖掘 w e b文本挖掘可以 对 w e b上大量文档集合的内 容进行总结、分类、聚类、 关联分析，以及利用 w e b 文档进行趋势预测等。 文本总结是指从文档中抽取关键信息，用简洁的形式对文档内容进行摘要或 解释。这样，用户不需要浏览全文就可以了解文档或文档集合的总体内容。文本 总结在有些场合十分有用，例如，搜索引擎在向用户返回查询结果时，通常需要 给出文档的摘要。目 前，绝大部分搜索引擎采用的方法是简单地截取文档的前几 行。 文献川提出了 使用中心文档来代表文档集合， 使用中 心词汇来表示文档的方 法，并给出了求取中心文档和中心词汇的算法。 _ 达 塑迪生鲤匹些巡一一 - 文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一个 类别。这样，用户不但能够方便地浏览文档，而且可以通过限制搜索范围来使文 档的查找更为容易。目 前， y a h o o ! 通过人工来对 w e b 上的文档进行分类，这大大 影响了索引的页面数目( y a h o o ! 索引的覆盖范围远远小于 a i t a -v i s t a等搜索引 擎) 。 利用文本分类技术可以 对大量文档进行快速、 有效地自 动分类。目 前， 文本 分类的算法有很多种，比 较常用的有 t f i d f 和 n a i v e b a y e s 2 等方法。 文本聚类与分类的不同之处在于，聚类没有预先定义好的主题类别，它的目 标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能地大，而 不同簇间的相似度尽可能地小。 h e a r s t 等人的研究己 经证明了“ 聚类假设” ，即与 用户查询相关的文档通常会聚类得比 较靠近，而远离与用户查询不相关的文档。 因此，我们可以利用文本聚类技术将搜索引擎的检索结果划分为若干个簇，用户 只需要考虑那些相关的簇，大大缩小了所需要浏览的结果数量。目前，有多种文 本聚类算法，大致可以分为两种类型:以 g - h a c等算法为代表的层次凝聚法， 以k - m e a n s 等算法为 代表的 平面 划分法。 文献 3 介绍了 将 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 方法。 关联分析是指从文档集合中找出不同词语之间的关系。b r i n 提出了一种从大 量文档中发现一对词语出现模式的算法， 并用来在 w e b 上寻找作者和书名的出现 模式， 从而发现了 数千本在 a m a z o n 网站上找不到的新书籍。 w a n g 等人以 w ww 的上的电影介绍作为测试文档，通过使用 o e m 模型从这些半结构化的页面中抽 取词语项，进而得到一些关于电影名称、导演、演员、编剧的出现模式。 分布分析与趋势预测是指通过对 w e b 文档的分析， 得到特定数据在某个历史 时刻的情况或将来的取值趋势。f e l d m a n等人使用多种分布模型对路透社的两万 多篇新闻进行了挖掘，得到主题、国家、组织、人、股票交易之间的相对分布， 揭示了一些有趣的趋势。w u t h r i c h 等人通过分析 w e b 上出版的权威性经济文章， 对每天的股票市场指数进行预测，取得了良好的效果。 需要说明的是，w e b 上的文本挖掘和通常的平面文本挖掘的功能和方法比较 类似， 但是， w e b 文 档中的 标记， 例如, 等蕴含了 额外的 信 息，我们可以利用这些信息来提高 w e b 文本挖掘的性能。 1 . 2 .3 we b 结构挖掘 由于 w e b 中包含的结构信息处理起来比较困 难，因此通常的 w e b 搜索引擎 等工具仅将 we b看作是一个平面文档的集合，而忽略了其中的结构信息。w e b 结构挖掘的目 的在于揭示蕴含在这些文档结构信息中的有用模式。 文档之间的超链反映了文档间的某种联系，例如包含、从属等。超链中的标 记文本( a n c h o r ) 对链宿页面也起到了 概括作用， 这种概括在一定程度上比 链宿页面 作者所作的概括( 页面的标题) 要更为客观、 准确。 c r a v e n等人使用一阶学习方法 对 w e b页面间的超链类型进行分类，以判断页面间的 m e m b e r s - o f - p r o j e c t , _ 这兰丝丝壑丝进燮色一 d e p a r t m e n t - o f - p e r s o n s 等关系; 同 时， 他们还 利用超链中 的 标记 文本对链宿页面 进 行分类，取得了较好的效果。超链还反映了文档间的引用关系，一个页面被引用 的次数体现了该页面的重要性。b r i n等人通过综合考虑页面的引用次数和链源页 面的重要性来判断链宿页面的重要性， 从而设计出能够查询与用户请求相关的“ 权 威”页面的搜索引擎。 we b页面的 u r l可能会反映页面的类型，也可能会反映页面之间的目 录结 构关系。 s p e r t u s 提出了 与w e b 页面 u r l 有关的启发式规则， 并用于寻找个人主 页，或者寻找改变了 位置的 w e b 页面的新位置。 目 前， 与 w e b 挖掘有关的各种项目 涉及了上述任务的某个方面， 也有一些项 目 综合考虑了w e b 的内容和结构因素， 将文本挖掘与结构挖掘结合起来，以取得 更好的效果。尽管与多媒体信息相比，文本信息显得比较普通，但文本仍然是记 载和传播信息的最主要媒体。此外，文本挖掘又相对容易取得技术突破，其中的 许多研究成果也可以为多媒体挖掘和结构挖掘所借鉴。因此对文本挖掘技术的研 究具有十分重要的意义和广泛的应用前景。 下面， 我们重点对 w e b 文本挖掘的方 法和应用进行讨论。 ， . 3 we b 文本挖掘方法及应用 1 . 3 . 1 we b 文本挖掘方法 在we b 文本挖掘中， 文本的 特征表示是挖掘工作的基础， 而文本分类和聚类 是两种最重要、最基本的挖掘功能。 1 . 文本的特征表示 与数据库中的结构化数据相比，w e b文档具有有限的结构，或者根本就没有 结构。即使具有一些结构，也是着重于格式，而非文档内容。 不同类型文档的结 构也不一致。 此外，文档的内容是人类所使用的自 然语言，计算机很难处理其语 义。文本信息源的这些特殊性使得现有的数据挖掘技术无法直接应用于其上。我 们需要对文本进行预处理，抽取代表其特征的元数据。这些特征可以用结构化的 形式保存，作为文档的中间表示形式。 文本特征指的是关于文本的元数据，分为描述性特征， 例如文本的名称、日 期、大小、类型等;以及语义性特征，例如文本的作者、机构、标题、内容等。 描述性特征易于获得， 而语义性特征则较难得到。w 3 c近来制定的x m l , r d f 等规范提供了 对 w e b 文档资源进行描述的语言和框架。 在此基础上， 我们可以从 半结构化的 w e b 文档中抽取作者、机构等特征。 对于内容这个难以表示的特征，我们首先要找到一种能够被计算机所处理的 表示方法。矢量空间模型( v s m ) 是近年来应用较多且效果较好的方法之一。在该 模型中，文档空间被看作是由一组正交词条矢量所张成的矢量空间，每个文档过 表示为其中的一个范化特征矢量 一 t c 丝 # #c l t叁型 a v ( d ) = ( t , , w , ( d ) ; 二 以 , w , ( d ) ; . . . ; t , w . ( d ) ) ， 其中t 为 词条项，w , ( d ) 为t ， 在d 中 的 权值。 可以 将d 中出 现的 所有单词作为t ,， 也 可以 要 求t 是d 中出 现的 所 有 短 语， 从 而 提高内 容 特征 表示的 准 确 性。 w ; ( d ) 一 般被定义为t ， 在d 中出 现频率tf , ( d ) 的函 数，即w , ( d ) = t ( tf , ( d ) ) 。 常用的qj 有: 布尔函 数梦 对数函数t = 2 . 文本分类 一 l ,tf ( d ) 2 1 , o ,tf , ( d ) = 0平 方 根 函 数 、 二 召 1 万 又 雨 l o g ( 抓( d ) + 1 ) 文本分类是一种典型的有教师的机器学习问题，一般分为训练和分类两个阶 段，具体过程如下: 训练阶段: ( 1 )定 义 类别 集合 c = 执，. , c . , c , ， 这些 类别可以 是 层次 式的， 也可以 是并列式的; ( 2 )给出 训 练 文 档 集 合s = ( s. . . ， s .， . . s n ，每 个 训 练 文 档s ， 被 标 上 所 属的 类 别 标识c , ， ( 3 )统 计s 中 所 有 文 档 的 特 征 矢 量v ( s j ) , 确 定 代 表c 中 每 个 类 别 的 特 征 矢 量 v ( c ,): 分类阶段: ( 4 )对于 测试文 档 集 合t = d l ， . . . ， d k ， . . . ， d , 中 的 每个 待分 类文 档d k ， 计算 其 特 征 矢 量v ( d k ) 与 每 个v ( c ) 之间的 相 似 度s im ( d k , c , ) ; ( 5 )选取相似度最大的 类别a r g m a x s i m ( c d k ) 作为d * 的 类别。 ,ec 有时也 可以 为d k 指定多 个 类别， 只要d k 与 这些类别 之间的 相似度超过某 个预 定的 阂 值。 如 果d k 与 所 有 类别 的 相 似度 均 低于 阂 值， 那 么 通常 将该 文 档放 在 一 边， 由 用户来做最终决定。对于类别与预定义类别不匹配的文档而言，这是合理的， 也是必须的。如果这种情况经常发生，则说明需要修改预定义类别，然后重新进 行上述训练与分类过程。 在 计 算s im ( 人 ， c i ) 时， 有 多 种方 法 可以 选 择。 最 简单 的 方法 是 仅 考 虑两 个 特征 矢 量 中 包 “ 的 词 条 的 重 叠 程 “ ， 即 sim (d k, c, ) 簇 炭 爱 台 ， “ 中 n n (d k ,c,， 是 v (d k) 和v ( c ; ) 具 有的 相同 词 条 数目 ， n u ( d k , c ) 是v ( d k ) 和v ( c ) 具 有的 所有 词 条 数目 ; 最常用的方法是考虑两个特征矢量之间的夹角余弦，即 s i m ( 峨, c ) _ v ( d k ) v ( c , ) v ( d k ) 卜 v ( c ) 7 c 奎 塑 r 竺叁 塑匕一一一一一 一 3 . 文本聚类 文本聚类是一种典型的无教师的机器学习问题。目 前的文本聚类方法大致可 以分为层次凝聚法和平面划分法两种类型。 对于给定的文档集合d= d l , . . . 试 ，. , d ， 层次凝聚法的具体过程如下: ( 1 )将d 中的 每个文 档d ， 看作是一 个具 有单个成员 的 簇c , = ( d ; ， 这些簇构成了 d 的一个聚类c = c l , . . . , c . . . . . . c ; ( 2 )计 算c 中 每 对 簇 ( e n c j ) 之 间 的 相 似 度 s im 仁 , c j ) ; ( 3 )选 取 具 有 最 大 相 似 度 的 簇 对a r g m a x s im ( c c , ) , 并 将 c ， 和 c i 合 并 为 一 个 新 马，c , e c 的 簇 c k = c , u c , ， 从 而 构 成 了 d 的 一 个 新 的 聚 类 c = c i , , c n - 1 ) ; ( 4 ) 重复上述步骤，直至c 中剩下一个簇为止。 该过程构造出一棵生成树，其中包含了簇的层次信息，以 及所有簇内 和簇间 的相似度。层次聚类方法是最为常用的聚类方法。它能够生成层次化的嵌套簇， 且准确度较高。但是，在每次合并时，需要全局地比较所有簇之间的相似度，并 选择出最佳的两个簇，因此运行速度较慢，不适合大量文档的集合。 平面划分法与层次凝聚法的区别在于， 它将文档集合水平地分割为若干个簇， 而 不 是 生 成 层次 化的 嵌 套 簇。 对 于 给 定 的 文 档 集 合d = d l , . . . , d . . . . . . d j， 平 面 划 分法的具体过程如下: ( 1 ) 确定要生成的簇的数目k ; ( 2 )按 照 某 种 原 则 生 成k 个 聚 类中 心作 为 聚 类的 种子,s = s 1 , . . . i s , . . . i s o . ( 3 )对d 中 的 每 个 文 档d ， ， 依 次 计 算 它 与 各 个 种 子 的 相 似 度s im ( d s , ) ; ( 4 )选 择 具 有 最 大 相 似 度 的 种 子a r g m a x s i m ( d ;, s , ) ， 将d , 归 入以 s i 为 聚 类 中 心 , e s 的 簇， 从而 得 到d 的 一 个聚 类c = f e l l . c i , . . . , c k ) e ( 5 ) 重复步骤 ( 2 ) , ( 3 ) , ( 4 ) 若干次，以 得到较为稳定的聚类结果。 该方法的运行速度快，但是必须预先确定k 的取值，且种子选取的好坏对聚 类结果有较大的影响。 1 .3 . 2 we b 文本挖掘的主要应用 由于目前绝大多数信息均表现为文本方式，文本挖掘技术，随着信息时代的 发展而得到重视和研究， 具有广泛的应用价值和商业前景。 文本过滤、 文本检索、 文本摘要、文本分类等相关技术有着密切的联系。主要应用于:自动索引、信息 检索、文档分类、文章摘要等方面。 1 . 所谓自 动索引， 就是自 动地从文档中抽取主题词。 索引的具体形式和所要 存取的信息内容是紧密相关的。其中，主题索引是最有意义的，它用少量的主题 主到 丝翌 述竺型 丝塑 匕一一 一一 一一 词来表征书刊的内容。特别地，对于期刊上的文章和技术报告来说，由于它们有 着相对集中的主题，更便于用少数的主题词来反映中心论题。 通过抽取主题词， 要能达到三个密切相关的目的。 能表示文档的内容，便于用户通过主题词来查找 文档中感兴趣的部分;通过主题词之间的联系来反映文档各主题之间的联系;根 据主题词与用户信息之间的相似程度，判断文档是否满足用户的检索需要。这些 目 的决定了衡量索引系统的两个主要指标，即彻底性 ( e x h a u s t i v i t y )和专门性 ( s p e c i f i t y ) 。 彻底性是指文本所讨论的主要内 容被主题词所覆盖的程度，专门 性是指抽取出来的主题词必须能反映文本的具体内容，而不能是泛泛而谈。 自 动索引分成两种情况，一是给定索引词典，以列出所有可能作为主题词的 词汇。 索引词典可能是与领域无关的， 如国内出版的 汉语主题词表 ， 共收录了 不同领域的十万多个主题词。图书分类目 录是另一种领域无关的索引词典。它一 般采用分类树的形式列出书籍的分类码， 如美国的 国会图书馆分类体系 。 另一 种索引词典是和特定的领域有关的。在美国，著名的领域索引词典有计算机领域 的a c m c r 分 类树， 医学界的m e d i c a l s u b j e c t h e a d in g和i程界的e n g i n e e ri n g i n d e x t h e s a u r u s 。 我国也出 版了 许多可作为特定领域索引词典之用的领域词典， 如 英汉计算机词汇等。 无论是否提供了索引词典，自 动索引过程都可以分成一下三各部分:候选主 题词的建立，权重的计算，主题词的生成。 2 信息检索 ( i n f o r m a t i o n r e t ri e v a l , i r )泛指用户从包含各种信息的文档集 中查找所需要的信息或知识的过程。从6 0年代以来，信息检索领域在索引模型、 文档内容表示、匹配策略等方面取得了许多研究成果。这些成果被成功地应用在 w e b 上，产生了搜索引擎，例如 y a h o o ! , a l t a -v i s t a 等。搜索引擎工作的一般流 程包括:使用 r o b o t 搜集 we b文档、对文档集合建立倒排索引、分析用户的查 询请求、匹配文档与查询请求以计算二者之间的相似度、对查询结果进行排序以 及用户相关度回馈。 3 . 文档分类就是将大量的文档归到一个或几个文档类别中去， 而这些文档的 类别是多种多样的，有报告、单据、新闻、邮件等等。文档的类别是预先确定好 的，也可以是不确定的，要经过文档的组织、聚类后才能得出。 文档分类系统最初是应信息检索的要求而出现的。信息检索系统必须操纵大 量的数据，其文档信息库可能是相当庞大的。同时用来表示文档内容的词汇数量 又是成千上万的。在这种情况下，如能提供文档集的良 好的组织和结构，就能大 大的简化文档的存取和操纵。文档分类系统的目 的就是对文档进行有序的组织， 把相似的、相关的文档组织在一起。它作为知识的组织工具，为信息检索提供了 更高效的搜索策略和更准确的查询结果。其中，高效性来自与用户可以首先确定 查询的可能类别，以减小需进一步匹配的文档数量。而有效性是因为相似的文档 一一三主幽些鲤塑巡翌1一一一一一 很可能与相同的查询相关。 4 .自 动文摘: 是网上智能业务中重要的一个。 文摘就是按用户的要求以简洁 的形式表达原文的主要内容。中文自 动文摘系统普遍采用两种方法:机械式文摘 和理解式文摘。前者的发展已进技术极限，文摘技术很难再有质的飞跃，一个出 路是对机械式文摘结果进行加工以改进其质量，这个过程也必须用到理解技术， 因此研究理解式文摘是必然趋势。理解文摘即报道性文摘，一般要求对原文作深 入的语义理解，并在此基础上对原文作完整的浓缩。因此不仅要求系统有篇章理 解的能力，而且还要求有自 然语言生成的能力。由于篇章理解及自 然语言生成的 难度都非常大，建立实用的基于理解的自 动文摘系统还有相当长的路程要走。 1 .4 文本挖掘过程及系统 1 . 4 . 1文本挖掘过程 文本 特征 建立 必 模型 质 t 评价 动 征的 特集 必 约简 、 一夕、 一 . - - - - 211、 es 目 一 一 产户 ;本木、 -尹承; t _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 三 _ _ _ _ _ _ _ _ _ _ _ _ a _ _ _ _ _ _ _ _ _ _ _ i - - - - - - - - - - - - - - 图1 . 2文本挖掘的一般过程 i n t e rn e t 上文本数据挖掘的一般处理过程可以用图1 .2 来概括描述。首先对挖 掘的文本进行分词处理， 把文本切分成特征词条。 接着建立挖掘对象的特征表示， 在i n t e r n e t 上的文本数据挖掘对象通常是一组h t tn l 格式的文档集，这样的挖掘对 象缺乏象关系数据库中数据的组织规整性，因此要将这些文档转化成一种类似关 系数据库中记录的较规整且能反映文档内容特征的表示， 一般采用文档特征向量。 但在目前的所采用的文档表示方法中，存在一个共同的不合人意的地方是文档特 征向量具有惊人的维数，因而特征向量的约简处理成为文本挖掘处理过程中一个 必不可少的环节。在完成特征向量维数的缩减后，便可以利用机器学习的方法来 提取面向特定应用目的的知识模式。最后对获取的知识模型进行质量评价，若评 价的结果满足一定的要求，则存储该知识模式，否则返回到以前的某个环节分析 改进后进行新一轮的挖掘工作。 1 . 4 . 2 i n t e r n e t 上文本挖掘的一些系统 目前世界上的一些大学、机构和公司都致力于 i n t e rn e t上文本挖掘系统的开 发，下面对它们中的一些工作作一下介绍: 1 ) w e b w a t c h e : 与p e r s o n a l w e b w a t c h e r 一一二些丝鱼塑塑墨些夔一一一一 w e b w a t c h e r 是由c m u开发的一个可安装在一个www站点上的导游器( t o u r g u i d e ) , w e b w a t c h e r 对来访的用户的访问 行为进行在线的学习， 通过对站点上主 页的超文本结构和以前用户浏览路径的学习，建立起一个经验模型。当一个用户 进入该站点时， 系统提供一个接口来启动we b wa t c h e r 的导游功能， 它将陪伴用户 进入每一个网页， 同时通过对用户兴趣的分析向用户建议下一步他要访问的连接。 p e r s o n a l w e b w a t c h e r 是一个个人化导游器， 它与w e b w a t c h e r 的功用很相似， 也由 c m u开发。 p e r s o n a l w e b w a t c h e r 与w e b w a t c h e r 的区别在于后者是面向 特定的个 人而前者是面向 特定的www站点。 2 ) a 1 t a v i s t a d i s c o v e r y a l t a v i s t a d i s c o v e r y 是由d e c 公司开 发的一 个新型的桌 面信息检索工 具， 它 提供了对桌面、 i n t e rn e t 数据的无缝集成。 它可以基于内容在不同搜索空间进行检 索，如本地盘、网络盘、i n t e rn e t 。可以自 动对所搜索到的文档进行总结、寻找与 当前网页相关联的网页，如内容相似、曾对该网也进行过引用的网页等。 1 . 5 we b 挖掘的意义和方向 w e b 挖掘在当前是前沿的研究领域， 是把i n t e rn e t , w w w和数据挖掘结合起 来的一种新兴的技术， 国外对此也处于刚起步阶段。 几个非常有用的研究方向是: 1 ) 聚类分析在 i n t e r n e t d v b 接入过程中，动态地构造和组织 d v b页面广播 内容的研究。 2 ) 路径分析在建立 i n t e r n e t 虚拟社区的研究。 3 ) 关联规则和序列模式的发现在构造自 组织站点的研究。 4 )分类在电子商务市场智能提取中的研究。 w e b挖掘的应用领域非常广阔，不但涉及页面信息提取、站点分析、设计， 而且在即将广阔蓬勃发展的基于 i n t e r n e t的电子商务方面也会有良 好的应用前 景。 例如现在正在把聚类方法应用到 d v b 页面中的广播中，己取得了一定的研究 成果。 在 w e b 信息充斥的情况下，w e b 挖掘是一个具有极大潜力的研究方向。一些 国际会议，例如 k d d 9 7 . i j