（计算机软件与理论专业论文）基于聚类的网页相关性挖掘技术研究.pdf

摘要 随着互联网的 普及和计算机技术的发展，从互联网 上获取满足用户 需求的信息越 来越困 难。为了 帮助用户有效地发现、选择、 搜寻感兴趣的 信息， 提高用户检索信息 的响应速度，从海f的网页信息中发现它们之间的关联， 从而得到有用的知识，人们 将传统的 数据挖掘技术和网 页结合 起来， 提出了网页挖掘技术。 网页挖掘中的一个主要问 题是对网页进行相关性挖掘。 网页的相关性挖掘首先从 各种网 页文本对象中抽取出能反映 其本质的重要特征， 将这些网页文本对象映 射成高 维特征空间中的点，然后通过高维空间中的距离计算来完成。 通过网页文本的相关性 挖掘，可以 将网页文本集合中 相似的 文本联系起来，便于从中 发现有用的知识。 本文首先从墓本概念入手，阐明了 数据挖掘和网页挖掘的 主要内 容. 然后， 对数 据挖掘的重要工具聚类分析算法的相关部分 ( 如聚类分析中的数据表示、距离度a和 常用算法) 进行了 深入的分析和讨论。 接下来逐一解决了网 页文本内 容特征抽取过程 中的三 个关 键性问题: 如何为网 页文本内 容的 特征选择合 适的 模型、 如何抽取出的 合 适的 特征、 如何为网 页的特征斌予一个合适的 权重。 在此荃础之上，设计实现了一个 网页相关性挖招的原型系统。 聚类;网 页挖掘; 相关性挖掘; 特征抽取;向 盘空间模型、 ab s t r a c t n o w a d a y s , w i t h t h e p o p u l a r i z a t i o n o f i n t e r n e t a n d d e v e l o p m e n t o f c o m p u t e r t e c h n o l o g y , o b t a i n i n g s a t i s f a c t o ry i n f o r m a t i o n f r o m i n t e r n e t b e c o m e s m o r e d i f f ic u l t . t o fi n d i n f o r m a t i o n , s e l e c t i n f o r m a t i o n a n d r e t r i e v e i n f o r m a t i o n e ff e c x u a l l y , a n d r a i s e t h e r e s p o n d s p e e d o f i n f o r m a t i o n r e t r i e v a l , a n d t h e n酬 u s e f u l k n o w l e d g e f r o m r e l a t i v i t y o f w e b i n f o r m a t i o n , t r a d i t i o n a l d a t a m in i n g t e c h n o l o g y i s u s e d 运w e b d o m a i n , w h i c h c o m e s i n t o b e i n g t h e w e b m i n i n 启 t e c h n o l o g y . o n e o f t h e k e y p r o b l e m s o f w e b m i n i n g i s w e b r e l e v a n t m i n i n g . i n w e b r e l e v a n t m i n i n g p r o c e s s , e x t r a c t i n g s o m e i m p o r t a n t w e b f e a t u r e s t o f i g u r e h y p o s t at i c f e a t u r e s o f w e b t e x t i s p r i n c i p a l . t h e n , a c c o r d i n g t o t h e s e f e a t u r e s , m a p w e b t e x t o b j e c ts to p o i n t s in h i g h d i m e n s i o n a l s p a c e . f i n a l l y , c a l c u l a t e t h e r e l a t i v i t y o f w e b t e x t 勿 t h e d is t a n c e s o f t h e s e p o i n t s . b y w e b r e l e v a n t m i n i n g , w e c a n c o n t a c t t h e s o u r c e w e b t o i t s s i m i l a r w e b s a n d fi n d u s e f u l k n o w l e d g e u l t i m a t e l y . i n t h i s d is s e r ta t i o n , w e c o m m e n c e f ro m t h e b a s i c c o n c e p t o f d a t a m i n i n g a n d w e b m i n i n g t e c h n o l o g y , c l a r 晚i n g t h e i r m a i n con t e n t s . t h e n , w e d i s c u s s t h e c o r r e l a t i v e d a t a d e n o t a t i o n , d i s t a n c e m e a s u r e m e n t , a n d s o m e c o m m o n a r i t h m e t i c i n c l u s t e r a n a l y s i s a l g o r i t h m w h i c h i s o n e o f t h e i m p o r ta n t m e a n s o f d a t a m i n i n g . a f t e r w a r d , w e r e s o lv e t h r e e k e y p ro b l e m s o f w e b t e x t f e a t u r e s e x t r a c t in g , t h a t 斌h o w t o s e l e c t s u i t a b l e m o d e l f o r w e b t e x t f e a t u r e s , h o w t o e x t r a c t s u it a b l e f e a t u r e s f ro m w e b a n d h o w t o c a l c u l a t e t h e w e i g h t v a l u e o f w e b f e a t u r e s . f i n a l ly , w e d e s i g n a n d c a r ry o u t a p ro t o t y p e s y s t e m f o r w e b r e l e v a n t mi n ing . : c l u s t e r ; w e b m i n in g ;m in in g ; f e a t u r e e x t r a c t ; v e c t o r s p a c e m o d e l 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的 研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致 谢的地方外， 论文中不包含其他人已 经发表或撰写过的研究成果， 也不包含为获得东北师范大学或其他教育机构的学位或证书而使 用过的材料.与我一同工作的同志对本研究所做的狂何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名:越兔日 m : 24 ,t o 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位 论文的规定，即:东北师范大学有权保留并向国家有关部门或机 构送交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权东北师范大学可以将学位论文的全部或部分内 容编入有关数 据库进行枪索，可以采用影印、缩印或其它复制手段保存、汇编 学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名: 日期: 指导教师签名: 日期 : 2 a 5 , 6 . 1 学位论文作者毕业后去向: 工作单位: 通讯地址: 电话: 邮编: 第一章引言 1 . 1 研究的背景和意义 随着互联网的普及和计算机技术的发展，互联网上的信息 资源呈现出指数级增长 的态势， 海皿的网页信息连同现代的网 络体系结构已 经发展成为一个巨大的、 动态的、 分布式的信息系统，这使得从互联网 上获取满足用户需求的信息越来越困难。面对今 天浩如烟海的网页信息， 如何帮助用户有效地发现、选择、搜寻所感兴趣的信息，提 高用户检索信息的响应速度，如何从这些海里的网页信息中发现它们之间的关联， 从 而得到有用的知识，解决 “ 数据丰富而信息缺乏”的状况，一直以来是人们研究的热 门问题。目前，人们开发了许多基于关键字匹配的搜索引擎，这些搜索引擎部分地解 决了上述问 题。 但这些传统的搜索引擎往往查全率和查准率不是很高， 对于用户的某 个搜索请求， 搜索引擎常常会返回很多的结果， 其中很大一部分是无用或无关的结果， 人们为了找到想要的结果，常常孺要浏览几十条记录或上百条记录，因 此这些传统的 搜索引擎难以 很好地满足用户的需求。此外，传统的搜索引攀的目的在于发现网页上 的 资 源， 即 使其检索精度再高， 也 难以 胜 任网 页上的 知 识 发现和数据挖掘的 任务。 1 1 2 1 近年来，为了从大f数据的集合中发现有效、新颖、有用、可理解的模式，数据 库 领 域引 用了 数 据挖 掘技 术 3 1 ， 这些 数 据 挖 掘的 绝 大 部 分 工 作 所 涉 及的 是结 构 化 数 据， 很少能够处理互联网上的异质、非结构化的网页信息。解决这些问题的一个途径就是 将传统的数据挖掘技术和网页结合起来，进行网页挖掘。网页挖掘是指从大t非结构 化、 异质的网页信息资源中发现有效的、 新颖的、 潜在可用的 及最终可理解的知识饱 括概念、 模式、 规则、 规 律、 约束及可视 化等形式 ) 的 非 平凡过 程。 网 页 挖掘 作为数 据 挖掘的一个新主题，近年来引起了人们的极大兴趣，通过网页挖掘，可以帮助用户在 日 益增多的 信息中自 动发现新的概念，并自 动分析它们之间的关系，从而实现信息的 自 动化分析和处理。 网页文本挖掘是网页挖掘中的一个非常重要的研究领域， 在过去几年里，对于网 页文本的相关性挖掘的研究已 经成为这一领域的一个非常活跃的 研究分支。 对于网页 文本的 相关性挖掘首先从各种网页文本对象中 抽取出能反映其本质的重要特征， 将这 些网页文本对象映射成高维特征空间中的点，这样就可以 通过高维空间中的距离计算 的来解决网页文本的相关性挖掘的问题。通过网页文本的相关性挖掘，可以将网页文 本集合中 相似的文本联系起来，便于从中发现有用的知识。 网页文本的相关性挖掘技术可以 用于不同的应用环境之中。 在网页浏览服务器端 集成网页相关性挖掘技术，可以自 动产生所浏览网页的相关文章，从而吸引用户浏览 更多的内容，便于用户找到更多的感兴趣的内容，同时，也可以 提高系统自 身的点击 率和用户浏览时间;在信息检索系统的前端集成网页相关性挖掘技术，可以将相似的 网 页集成在一起，便干网页信息的组织和索引，同时，也可以 大幅度地降低检索候选 集合的数量，从而减少检索时系统的计算量， 提高检索的响应速度; 在信息 检索的 后 端集成网页相关性挖掘技术，可以 将检索结果用一个用户容易理解的方式 ( 如树或图 的形式) 表现出 来， 增加访问的方便性， 给用户留下较好的印象; 在网页自 动分类中， 也可以 通过应用网页相关性挖掘技术， 将网 页页面归 类到最相似的 类别中。此外，网 页相关性挖掘技术还可以 应用在多文档文摘、新闻话题识别和追踪等领域中。因此， 对网 页相关性挖掘技术进行深入的 研究是十分必要的。 聚 类分 析( c l u s t e r i n g a n a l y s i s ) ， 又 称聚 类， 是一 种 广 泛 应 用于 知识 发 现与 数 据 挖掘的分析手段，它按照事物的某些属性，将事物分成多个类或簇，使得在同一类别 中 的 事 物 相 似 度 尽 a 大 ， 不 同 类 别 间 的 事 物 相 似 度 尽 量 小 。 聚 类 作为 一 种 非 监 督 型 的 知识发现方法，不需要任何事先的训练数据， 而仅仅按照相似度原则， 将一组数据划 分 为 事 先 未 知 的 分 类 状 态 ， 因 而 是 一 种 有 效 的 、 得 到 广 泛 应 用 的 模 式 识 别 与 知 识 发 现 的方法。 本文将以 聚类分析作为处理和组织数据的 手段， 对网页 相关性挖掘技术进行深入 的探讨和研究，具体而言， 将包括以 下几方面的内容: 1 .对当前主要聚类算法进行分析和比 较，从而确定在网页相关性挖掘中适宜采 用的聚类算法。 2 .研究对网页文本进行特征提取的算法，选择适当的数学模型，对特征提取的 结果进行建模，以 便于对网页相关性进行挖拥。 3 .在此荃础上，实现墓于聚类的网页相关性挖掘原型系统，并对它的实际应用 进行分析和总结，提出 进一步改进的设想。 1 .2 论文的组织 本文共分为六个章节: 第一章为引言部分，介绍本文研究的 背景和意义。 第二章为数据挖捆技术和网页挖掘技术概述部分。 第三章为聚类分析算法部分。 第四章为网页文本内容的 特征提取与表示。 第五章为网页相关性挖掘原型系统实现。 第六章为结论部分。 第二章数据挖掘技术和网页挖掘技术概述 2 . 1 2 . 1 . 1 数据挖掘技术 数据挖捆技术的产生 数据挖掘是近年来随着数据库和人工智能技术的发展而出现的一种信息处理技 术。它是以 数据库技术为基础， 集统计学、人工智能、模式识别、并行计算、机器学 习等技术于一身的 交叉性的 研究领域。 它的目 标是高 度自 动化地分析企业原有数据， 做出归纳性推理，从中挖掘出潜在的模式，预测客户的行为，帮助企业决策者调整市 场策略，减少风险，做出正确决策。从2 0 世纪6 0 年代至今，数据挖掘技术经历了数据 搜集、数据访问、 数据仓库和数据挖掘四 个过程， 如表2 . 1 所示: 表2 . 1 数据挖掘技术进化的四个过程 进化阶段时间段技术支持生产厂家产品特点 数据收集6 0 年代计算机、 磁带 等 i b m , c d c 提供静态历史数据。 数据访问8 0 年代关系数据库、 结构化查询 语言 s q l o r a c l e、 s y b a s e、 i n f o r m i x 、i b m 、 m i c r o s o f t 在记录中提供动态 历史数据信息。 数据仓库9 0 年代联机分析处 理、 多维数据 库 p i l o t、 c o m s h a r e、 s a s , a r b o r , c o g n o s , m i c r o s t r a t e g y 在各个层次提供回 溯的动态历史数据。 数据挖掘正在流行高级算法、 多 处理器系统、 海t算法 p i l o t , s a s , i b m , s g i 等公司 可提供预测性信息 2 . 1 .2 数据挖掘的定义 由 于数据挖掘技术是属于多学科交叉领域的 研究课题，长期以 来，人们从不同的 角度和侧重点对数据挖掘技术进行了不同的定义。 j . h 。和m . k a m b e r s 从数据库的角度出 发， 认为 数据挖掘就是从数据库、 数据仓 库或其它 信息 仓库中 存 储的 大a 数据中 发现有用的 知识的 过 程13 1 , 1 . h . w i t t e n和 e . f r a n k s 将数据挖掘定义为从数据中提取固有的，以 前不知道的并且潜在的有用信息的 过 程， 这 样的 观 点 是以 机 器 学习 为 基 础的 15 1 。 另 外， d . h a n 氏h . m a n n i la 和p s m y th 的 数 据 挖 掘的 定 义 是 为了 找 到 毋 庸置 疑 的 关 系 而 进 行 的 对 休量 ) 观 测 数 据 的 分 析， 并 按易于为 用户所理 解和使用的新 颖的方式 进行总结 数据16 1 。 显然， 这是从统计学出 发 的。 在此基础上， 通过综合各种不同的 观点， 对数据挖掘技术渐渐形成了一个比 较完 整和准确的定义: 定义 2 . 1数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际 应用数据中，抽取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程。从更广义的角度来讲，数据挖掘就是在一些事实或观察数据的集合中寻找模 式的决策支持过程。 2 . 1 3 数据挖掘的研究内容 随着数据挖掘研究的逐步深入， 数据挖掘的研究主要由 三个方面来支持; 数据库、 人工智能和数理统计。目 前的主要研究内 容包括荃础理论、 算法研究、数据仓库、可 视化技术、定型定t互换模型、知识表示方法、发现知识的维护和再利用、半结构化 和非结构化数据中的知识发现以 及网 页数据挖掘等。 3 2 . 1 .4 数据挖拥的功能分类 数据挖掘不仅能对过去的数据进行查询和遍历，并且能够对将来的趋势和行为进 行预测，并自 动探测以 前未发现的模式，从而很好地支持人们的决策。 被挖掘出来的 信息，能够用于信息管理、查询处理、决策支持、过程控制以及许多其它应用。数据 挖掘按其功能划分主要包括以 下几类3 1 . ( 1 ) 关联分析 若两个或多个数据项的取值重复出 现且概率很高时，它就存在着某种关联，可以 建立起这些数据项的关联规则。关联分析的目 的是找出 数据库中隐藏的关联网。在大 型数据库中，这种关联规则是很多的，一般用 “ 支持度” 和 “ 里信度” 两个闽值来淘 汰那些没有用的关联规则。 ( 2 ) 分类 分类是找出一个类别的 概念描述， 它代表了 这类数据的整体信息，即该类的内 涵 描述， 一般用规则或决策树模式表示。 一个类的内 涵描述分为 特征性描述和区别性描 述。 特征性描述是对类中 对象的 共同特征的 描述，区别性描述是对两个或多个类之间 的区别的描述。 ( 3 ) 聚类 数 据库中 的 数 据 可分 为 一 系 列 有 意 义的 子 集， 或 称为 类 ( 簇 ) 。 在同 一 类 别中 ， 个 体 之间的距离较小而不同类别的个体之间的距离较大。聚类增强了人们对客观现实的认 识，即通过聚类建立宏观概念。 ( 4 ) 时 序模式 通过时间序列搜索出重复发生概率较高的模式。 这里强调时间序列的 影响。 例如， 在所有购买激光打印 机的人中， 半年后有8 0 %的人再购买新硒鼓， 2 0 % 的 人用旧 硒鼓 装碳粉。 ( 5 ) 偏差检测 数据库中的 数据常有一些异常记录，从数据库中检测出 这些偏差很有意义。 偏差 包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预 测值的偏差、量值随时间的变化等。 偏差检测的基本方法是寻找观测结果与参照之间 的差别。 ( 6 ) 预测 预测是利用历史数据找出变化规律，即建立模型，并用此模型来预侧未来数据的 种类、特征等。 2 . 1 . 5 数据挖掘的发展方向 被挖掘的数据、数据挖掘任务和数据挖掘方法的多样性给数据挖掘提出了 许多挑 战性的课题。 数据挖掘语言的设计， 高效而有用的 数据挖掘算法和系统的开发，交互 和继承的数据挖掘环境的建立，以及应用数据挖掘技术解决大型应用问 题， 都是目 前 数据挖掘研究人员、系统和应用开发人员所面临的主要问题。目 前，数据挖掘的研究 方向 和趋势主要有13 1 . ( 1 ) 应用的 探索 通用数据挖掘系统在处理特定应用问 题时有其局限性，因 此开发针对特定 应用的 数据挖掘系统是很有必要的。 ( 2 ) 可伸缩的 数据挖掘方法 由于数据t的迅速增长，针对单独的和集成的数据挖掘功能的可伸缩算法显得非 常重要。 ( 3 ) 数 据 挖掘 与 数 据库 系 统、 数 据 仓 库系 统 和网 页 数 据 库系 统的 集 成 数据挖掘系统的理想体系结构是与数据库和数据仓库系统的紧祸合方式。因此， 保证数据挖掘作为基本的数据分析模块能够顺利地集成到这些信息处理环境中，将有 重要意义。 ()数据 挖 掘语 言的 标准 化 标准的数据挖掘语言或其他方面的标准化工作将有助于数据挖掘的系统化开发， 改进多个数据挖掘系统和功能间的互操作，促进数据挖掘系统在企业和社会中的普及 和使用。 ( 5 ) 可视化数据挖掘 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解，便于在 知识发现的过程中 进行人机交互，有助于推进数据挖掘成为数据分析的基本工具。 ( 6 ) 对于复杂数据类型进行挖掘的新方法研究 复杂数据类型挖掘是数据挖掘中一项重要的前沿研究课题，为了处理这些复杂的 s 数据， 就需要一些新的和更好的分析和建立 模型的方法，尤其是把现存的 数据分析技 术与复杂数据的 特点结合起来的研究，同时 还会涉及到为处理这些复杂或独特数据所 准备的一些工具和软件。 ( 7 ) 网页挖拥 对互联网上大t非结构化、异质的网页信息资源进行有效的挖掘，从中抽取出 用 户感兴趣的知识和信息，是当前数据挖掘技术的一个重要发展方向。 ( 8 ) 数据挖 掘中 的隐 私保护与 信息 安 全 随着数据挖掘工具和网络技术的日 益发展，数据挖掘要面对的一个重要问题是隐 私保护和信息安全，尤其对于网络数据的挖掘。需要进一步开发有关方法，以便在适 当的信息访问和挖掘过程中确保隐私保护与信息安全。 网页挖掘技术 网页挖拥的定义 网页挖掘是指从大t非结构化、异质的网页信息资源中发现有效的、新颖的、潜 在 可 用的 及最 终 可 理 解的 知 识 ( 包 括 概 念、 模式、 规则、 规 律、 约 束 及可 视 化等 形 式) 的非平凡过程。 这 个定 义是从 数 据挖掘角 度给出的， 可以 从更 一 般角 度将网 页挖掘定 义为 门 : 定 义2 .2网 页 挖 掘 是 指 从 大量网 页 文 档 集 合c 中 发 现隐 含 模 式p ， 如 果 将c 看作 输 入， p 看 作 输出 ， 那么， 网 页 挖 掘 过 程 就 是 从 输 入 到 输出 的 一 个映 射6 :c - p . 2 .2 . 2 网页挖掘的分类 网页上信息的多 样性决定了网页挖掘任务的多样性， 按照处理对象不同 我们将网 页 挖掘分为三大 类:网 页内 容挖掘、网 页结 构 挖掘和网 页 访问 信息挖掘。 门 ( 1 ) 网 页内 容 挖掘 网 页内 容 挖 掘 ( w e b c o n t e n t m i n i n g ) 就 是 对网 页 页 面 的内 容 进 行 挖 掘， 从 大 童网 页 数据中发现信息、 抽取知识的过程。 这些数据既有文本数据，也有图 像、声频、视频 等多媒体数据;既有来自 数据库的结构化数据，也有用h t m标记的半结构化数据和 无结构的自由 文本。从挖掘对象上来分，内 容挖掘又可以 分为两类: 其一，网 页文本 挖 掘 咆括 t e x t 和 h t m i 籍式 ) ;其 二， 网 页 多 媒 体 数 据 挖掘( 包 括 i m a g e , a u d io , v i d e o 等 媒 体 类型 ) 。 网 页 文 本 挖掘 可以 对网 页 上 的 文 本 集 合中 的内 容 进 行 关 联 分 析、 总 结、 分类、聚类以 及利用网页文本进行趋势预测等.网页多媒体挖掘主要是利用多媒体提 取工具进行特征提取，然后对这些特征进行关联规则或者分类等挖掘操作。 ( 2 )网页结构挖掘 网 页 结 构挖 掘 ( w e b s tr u c tu r e m in i n g ) 是 从 w w w 的 组 织 结 构、 文 本 结 构 及 其 链接 关 系中推导知识。 由于文本之间的关联关系使得www不仅可以揭示文本所包含的信息， 也可以 揭示文本间的关联关系所代表的信息， 反映文本之间的某种联系，同时体现某 个页面的重要程度。挖掘网页结构的目的是:发现网页的结构和页面结构以及蕴含在 这些结构中的有用模式; 对页面及其链接进行分类和聚类，找出权威页面。 这方面研 究 工 作 的 代 表 有 p a g e r a n k 和 c l e v e r 等。 ( 3 ) 网 页 访问 信 息 挖掘 网 页访问 信息 挖 掘 ( w e b u s a g e m in in 幻 就 是 对 用 户 访问 网 页时 在服 务 器留 下 的 访 问记录进行挖掘，即 对用户访问网页站点的存取方式进行挖掘，以发现用户访问 站点 的浏览模式，页面访问 频率等信息。根据应用的不同，可以将网页访问信息挖掘分为 两种主要倾向，即: 一般访问 模式追踪和个性化使用记录追踪。一般访问 模式追踪通 过分析网页日 志来了 解用户群体的共同行为和共同兴趣， 理解用户的访问 模式和倾向， 以 改进站点的组织结构和网 络服务质量。 个性化使用记录追踪其目 的是为每个用户定 制符合个人特色的网页站点。挖掘出来的模式可用于指导站点管理员改进网页站点的 设计和组织结构或提供可以带来经济效益的信息。 2 .2 .3 网页挖掘的挑战 网页挖掘所面临的主要挑战在于: . 对感兴趣的 信息仅限于利用各种搜索引擎进行查找， 但其检索性能 和服务质t 并不令人满意;网页上的信息只有很小的一部分是相关的或有用的。据统计 9 9 %的网页信息相对9 9 % 的用户是无用的。 虽然这看起来不是很明显， 但用户 只是关心网 页上的很少一部分信息确是事实， 网页所包含的其余信息对用户来 说是不感兴趣的，而且会淹没其所希望得到的搜索结果。 . 网页页面以 某种格式呈现半结构化， 数据结构不规则或不完整， 复 杂程度远高 于普通文本文档， 其数据结构隐含、 模式信息2大、 模式变化快。 大i文档无 任何排列次序，无分类索引. . 网页是一个异 质、 动态、 分布的 数据源， 网页及其数据的更新、 增长 速度极快， 无固定模式，仅用传统的基于关键字的检索方式很难实现。 . 不同用户访问网页的兴趣、 爱好和使用目的千差万别， 能否根据用户的爱好兴 趣定制网页，从而提供个性化信息检索和查询服务。 . 构建一个庞大的 数据仓库把网 页上所有分布和异质的 数据集成在一 起几乎是 不可能的。 这些问 题推动了 如何有效且高效地发现和充分利用网上资源的研究工作。万维网 的分布、海量、 动态、异 质、 变化、开放性特点，网 页内 容的半结构化特征决定了网 页挖掘比 传统的以 关键字搜索为主的信息检索问 题更为复杂和困 难。 解决网 页挖掘问 题需要有新的数据模型、体系结构和算法等，在理论上、方法上要有新突破，要有更 高级的网页信息处理技术。 2 .3 网页挖掘与数据挖掘的区别 网页挖掘从数据挖掘发展而来， 但是，网页挖掘与传统的数据挖掘相比有许多独 特之处。 首先，网页挖掘的对象是大量、异质、分布的网页文档。以网页作为中间件对数 据库进行挖掘，以 及对网页服务器上的日 志、用户信息等数据所开展的 挖掘工作， 本 质上仍属于传统的数据挖掘的范畴。 其次， .网页在逻辑上是一个由文档节点和超链构成的图。因此网页挖掘所得到的 模式可能是关于网页内容的，也可能是关于网页结构的。 此外，由于网页文档本身是半结构化或无结构的，且缺乏机器可理解的语义，而 数据挖掘的对象局限于数据库中的结构化数据，并利用关系表格等存储结构来发现知 识，因此有些数据挖掘技术并不适用于网页挖掘，即使可用也需要建立在对网页文档 进行预处理的基础之上。 第三章聚类分析算法 3 . 1 聚类分析概述 聚类 ( c l u s t e r i n g ) 是一个将数据集划分为若干组 ( c l a s s ) 或类 ( c l u s t e r ) 的 过程，并使得同一个组内的 数据对象具有较高的相似度，而不同 组中的数据对象则是 不相似的。 相似或不相似的度最是基于数据对象描述的取值来确定的， 通常是利用( 各 对象间)距离来进行描述。 对于聚类没有一个统一和精确的定义，人们根据观察的角度和方法的不同，应用 的领域和范围的不同，给出了不同的定义: 定义3 . 1 良 好分隔的 聚 类定 义 ( w e l l - s e p a r a t e d c l u s t e r d e f i n i t i o n ) : 聚类是 一些点的集合，与不在聚类中的点相比，聚类中的每一个点彼此间更接近 ( 更相似) 。 图3 . 1 显示了适合于良好分隔的聚类定义的数据集合的外部特征。 巷 图3 . 1 适合于良 好分隔聚类定义的数据集合。 定义3 . 2 荃于中心的 聚类定义 ( c e n t e r - b a s e d c l u s t e r d e f i n i t i o n ) : 聚类是一 些对象的集合，与其它聚类的“ 中心” 相比，在聚类中的对象更接近 ( 更相似)于本 聚类的 “ 中心” 。 聚类的“ 中心” 常常是一个质心 ( 聚类中所有的点的平均值) ，或者 是聚类的中心点 ( 聚类中最具代表性的点) 。 图3 . 2 显示了 适合于基于中心的聚类定义的数据集合的外部特征. :主 : .:.:.:.: ，.:.:.卜.:+卜， 图3 . 2 适合于墓于中心的聚类定义的数据集合. 定 义 3 . 3 最近 邻居的 聚 类定 义 ( c o n t i g u o u s c l u s t e r d e f i n i t i o n o r n e a r e s t n e i g h b o r c l u s t e r d e f i n i t i o n ) : 聚 类 是一 些点 的 集 合， 与 不 在聚 类中 的 点 相比 ， 聚 类中的点更接近 ( 更相似) 于 本聚类中的 某个点 或某些点。 图3 , 3 显示了适合于最近邻居的聚类定义的数据集合的外部特征， 1一井 缴份 、卜于 图3 . 3 适合于最近邻居的聚类定义的数据集合 定义3 . 4 荃于密度的聚类定义 ( d e n s i t y - b a s e d c l u s t e r d e f i n i t i o n ) : 聚类是 点的密集区域， 这些区域和其他的区域彼此间由 低密度的区域分隔开来。 图3 . 4 显示了适合于基于密度的聚类定义的数据集合的外部特征。 图3 . 4 适合于基于密度的聚类定义的数据集合 定义3 , 5 墓于相似度的聚 类定义 ( s i m i l a r i t y - b a s e d c l u s t e r d e f i n i t i o n ) : 聚 类是相似的对象的集合，在其他聚类中的对象是不相似的。 聚类分析是人类的一个重要内容。 早在儿童时期，一个人就是通过不断完善潜意 识中的分类模式，来学会识别不同 物体， 如: 猫和狗; 动物和植物等。聚类分析已 被 应用到许多领域，其中包括:模式识别、数据分析、图 象处理和市场分析等。通过聚 类， 人可以 辨识出空旷和拥挤的区域， 进而发现整个的分布模式，以 及数据属性之间 存在的有价值的相关联系。 聚类分析的典型应用主要有:在商业方面，聚类分析可以帮助市场人员发现顾客 群中所存在的不同特征的组群，并可以利用购买模式来描述这些具有不同 特征的顾客 组群。在生物学方面，聚类分析可以用来获取动物或植物所存在的层次结构 ( t a x o n o m i e s ) ， 可根据基因功能对其进行分 类以获得对人群中所固有的结构更深入的 了解。聚类还可以从地球观测数据库中帮助识别具有相似的土地使用情况的区域。 此 外，还可以帮助分类识别互联网上的文档以便进行信息发现。作为数据挖掘的一项功 能，聚类分析还可以 作为一个单独使用的工具， 来帮助分析数据的 分布、了 解各数据 类的 特征、 确定所感兴趣的数据类以 便作进一步分析。当 然聚类分析也可以 作为 其他 算法 ( 诸如:分类和定性归纳算法)的预处理步骤。 数据聚类分析是一个正在蓬勃发展的 领域。 聚类分析所涉及的领域包括; 数据挖 掘、统计学， 机器学习、 空间数据库技术、 生物学和市场学等。由 于各应用数据库所 包含的数据t越来越大， 聚类分析己 成为数据挖掘研究中一个非常活跃的研究课题。 作为统计学的一个分支， 聚类分析己 有多年的历史，其研究主要集中 在基于距离 的聚类分析方面。 许多统计软件包， 诸如:s - p l u s s p s s和 s a s ， 都包含基于 k - 均值、 k - 中心等诸多聚类分析方法。 在机器学习中， 聚类分析属于一种无 ( 教师) 监督的学习方法。与分类学习不同， 无 ( 教师) 监督学习不依靠事先确定的数据类别，以及标有数据类别的学习训练样本 集 合. 正 因 为 如 此， 聚 类分 析 又 是 一 种 观察 学 习( l e a r n in g b y o b s e r v a ti o n ) 方 法， 而不 是 示 例学习 l e a r n in g 勿e x a m p l e ) 方 法。 在 对概 念 进 行 聚 类的 方 法中， 仅当 一 组 对 象 可以由一个概念所描述时， 这些对象才能构成一个类。 这与基于几何距离表示相似程 度并进行聚类的传统聚类方法有所不同。 概念聚类方法主要包含两部分内 容: ( 1 ) 发 现适当的 类:( 2 ) 根据每个类形成相应的特征描述。 无论如何最大程度地实现类中 对 象相似度最大， 类间对象相似度最小是聚类分析的墓本指导思想。 在数据挖掘中， 大多数工作都集中 在发现能 够有效、高效地对大数据库进行聚类 分析的方法上。 相关的研究课题包括: 聚类方法的可扩展性、复杂形状和复 杂数据类 型的聚类分析的有效离效性、高维聚类技术，以 及混合数值属性与符号属性数据库中 的聚类分析方法等。 聚类分析是一个富 有挑战的 研究领域， 有关每一个应用都提出了 一个自 己 独特的 要求。以下就是对数据挖掘中的聚类分析的一些典型要求。 . 可扩展性。 许多聚类算法在小数据集( 少于2 0 0 个数据对象) 时可以工作很好; 但一个大数据库可能 会包含数以百万计的 对象。 利用采样方法进行聚类分析可 能得到一个有偏差的结果，这时就需要可扩展的聚类分析算法。 . 处理不同类型属性的能力。 许多算法是针对基于区间的数值属性而设计的。 但 是有些应用需要对其它类型数据， 如: 二值类型、 符号类型、 顺序类型， 或这 些数据类型的组合。 . 发现任意形状的聚类。 许多聚类算法是根据欧氏距离和ma n h a t t a n 距离来进行 聚类的。 墓于这类距离的聚类方法一般只能发现具有类似大小和密度的圆形或 球状聚类。 而实际上一个聚类是可以具有任意形状的， 因此设计出能够发现任 惫形状的聚类算法是非常重要的。 . 需要 ( 由用户) 决定的输入参数最少。 许多聚类算法需要用户输入聚类分析中 所需要的一些参数 ( 如:期望所获聚类的个数) ，聚类结果通常都与输入参数 密切相关， 而这些参数常常也很难决定， 特别是包含高维对象的 数据集。 这不 仅构成了用户的负担，也使得聚类质量难以控制。 处理嗓声数据的能力。 大多数现实世界的 数据库均包含异常数据、不明 数据、 数据丢失和噪声数据， 有些聚类算法 对这样的数据非常敏感并会导致获得质a 较差的数据。 对输入记录顺序不敏感。 一些聚类算法对输入数据的顺序敏感， 也就是不同的 数据输入顺序会导致获得非常不同 的 结果。 因 此设计对输入数据顺序不敏感的 聚类算法也是非常重要的。 高维问 题。 一个数据库或一个数据仓库或许包含若干维或属性。 许多聚类算法 在处理低维数据时( 仅包含二到三个维) 时 表现很好。 人的视觉也可以 帮助判 断多至三维的数据聚类分析质a. 然而设计对高维空间中的数据对象， 特别是 对高维空间稀疏和怪异分布的 数据对象， 能进行较好聚类分析的聚类算法已成 为聚类研究中的一项挑战。 基于约束的聚类。现实世界中的应用可能需要在各种约束之下进行聚类分析。 假设需要在一个城市中确定一些新加油站的 位置， 就需要考虑诸如: 城市中的 河流、高 速路，以 及每个区域的 客户需求等约束情况下居民 住地的聚类分析。 设计能够发现满足特定约束条件且具有较好聚类质t的聚类算法也是一个重 要聚类研究任务。 可解释性和可用。 用户往往希望聚类结果是可理解的、 可解释的， 以 及可用的。 这就需要聚类分析要与特定的解释和应用联系在一起。 3 .2 聚类分析中的数据表示 基于内 存的聚类算法通常都采用以 下两 种数据结构来表示数据3 j . 3 . 2 . 1 数据矩阵 数据矩阵是一个对象一 属性结构 来进行描述的，如:年龄、高度、 示，如图3 .5 所示。 . 它是由n 个 对象组成。这些对象是利用 重it等。 数据矩阵采用关系表形式或n p p 个属性 矩阵来表 ，.且.且.吸哥. :夕。尹 r.侧盛.r. x t i a h t 图3 .5 数据矩阵 3 . 2 . 2 差异矩阵 差异矩阵是一个对象一 对象结构。它存放所有n 个对象彼此之间所形成的差异。它 一般采用n x n 矩阵来表示，如图3 . 6 所示。 ，.，刁.，月，卫j，.，刃 . 。0 . d ( 3 , 2 )0 d ( t ? , 2 ) 0(2.(3.;(n. f卜ia阳|卜a 图3 . 6 差异矩阵 其中d ( i j ) 表示对象i 和对象j 之间的差异程度 ( 或不相似程度) ， 在下一节中 将详 细介绍各种不同的距离 度全方法。 数据矩阵通常又称为双模式矩阵，差异矩阵称为单模式矩阵。前者行和列分别表 示不同的实体， 后者行和列表示的是同一实 体。 许多聚类算法都是基于 差异矩阵 进行 聚类分析的。如果数据是以数据矩阵形式给出的，那么首先需要转换为差异矩阵，方 可利用这些聚类算法进行处理。 3 .3 聚类分析中距离度盆 在聚类分析中，首先要确定的是如何计算对象之间差异程度 ( 不相似程度) ，即对 象之间的距离。 在过去的 研究过程中， 人们提出了 各种不同的距离度量公式， 总体而 言， 这些不同的距离公式需要具有和满足以 下的数学性质 ( 要求) 3 . 1 ) d ( i , j ) 0 。 这 表 示对 象 之间 距离为 非 负 的 一 个 数 值。 匀 d ( i , i ) = 0 。 这 表 示 对象自 身 之间 距 离 为 零 3 ) d ( i , j ) = d ( j , i ) 。 这表 示 对 象 之间 距 离是 对 称函 数。 4 ) d ( i , j ) d 0 d , d 角分离度d、 一 i xcy, 客 x ; 2客 ， z) ay , ) 3 .3 .2 二值变f的距离 度f 对于二值变盆，人们提出了各种不同的距离度a方法。 对于由二值变19组成的向 量x 与y ，可有通过a , b , c 和d 的值将相异程度表达出来， 其中: a 等于x ; = 1 和” 二 1 所出 现的次 数。 b 等于x ; = 。 和y ; = 1 所出 现的 次 数。 c 等于x ; = 1 和y ; = 0 所出 现的次 数。 d 等 于x ; = 0 和y , = o 所出 现的次 数。 表3 .2 对此作出了 总结: 表3 . 2 二值变it的 取值 一 .14 n一b 习 惯 上， 为 二 值变 童定 义 相似度而不是 相异 度 二 d! 表3 .3 总结了一些对于二值数据较 ，1一a一c 常 用的相似度度量方法。 s ) 表3 . 3 常用的二值变里相似度度it 方法 相似度度量数学形式 简单匹配系数 d _ 二 ，a + d a 十 o 十 c 十 a r u s s e l l 和 r a o 心 一 一 卫a - 一 a 十 b + c + d j a c c a r d d ， 一止 z “ 十 a + c c z e k a n o ws k i 2 a a_ . 2 a+b+c 3 .4 聚类分析算法分类 聚类分析的算法很多，在实践上，需要根据应用所涉及的数据类型、聚类的目的 以 及 具 体应 用要 求 来 选择 合 适的 聚 类 算 法。 聚 类 分 析 算 法 可以 划分 为以 下 几 大 类 3 1 9 1 .划分方法 给定一个包含n 个对象或数据行， 划分方法将数据集划分为k 个子集 ( 划分) . 其 中每个子集均代表一个聚类( k n ) 。 也就是说将数据分为k 组， 这些组满足以 下要求: ( a ) 每组至少应包含一个对象; ( b ) 每个对象必须只能属于某一组。 需要注惫的是后 一个要求在一些模糊划分方法中可以