（计算机软件与理论专业论文）web挖掘中聚类算法的研究.pdf

南京邮电大学 硕士学位论文摘要 学科、专业：工学计算机软件与理论 研究方向：基于网络的计算机软件应用技术 作者：2 0 0 7 级研究生李冰 指导教师：李玲娟教授 y 1 洲7 m 5 5 帅3 川5 8 l 题目：w e b 挖掘中聚类算法的研究 英文题目：r e s e a r c ho nc l u s t e r i n ga l g o r i t h mo fw e bm i n i n g 主题词：w e b 挖掘；聚类；k m e a n s ；蚁群 k e y w o r d s ：w e bm i n i n g ；c l u s t e r i n g ；k m e a n s ；a n tc o l o n y 南京邮电大学硕士研究生学位论文摘要 摘要 随着互联网的飞速发展，w e b 数据以指数级的速度快速增长，对w e b 资源所蕴涵的潜 在价值的需求促进了数据挖掘技术在其中的应用。由于w e b 数据的海量、高维、动态以及 不可预测性，基于w e b 的聚类研究已逐渐成为了新的热点。 本文对聚类算法在w e b 挖掘中的应用展开研究，针对w e b 文本数据的特点，对已有 的聚类算法做了一定的改进，使其能适应于w e b 文本挖掘，并且提高聚类的准确度。 论文首先针对k m e a n s 聚类算法在w e b 文本挖掘中的应用，引入了一种新的数据预处 理方法，并优化了初始质心的选择，设计了改进的k - m e a n s 聚类算法。接着，研究了蚁群 聚类算法及其在w e b 挖掘中的应用。针对传统的蚁群聚类算法( a c c a ) 未考虑各维特征 贡献率的缺陷，引入了特征加权算法，并且使用了新的概率转换函数；针对a c c a 中离群 点问题，提出了一种基于层次聚类和蚁群聚类的组合聚类算法一层次化蚁群聚类算法 ( h a c c a ) 。论文还进行了算法实现，并基于人民日报标注语料库的文档特征矩阵做 了仿真实验，验证了所设计的各个算法对w e b 文本挖掘的有效性。 论文对聚类算法在w e b 挖掘中的应用做了有益的研究。 关键词：w e b 挖掘；聚类；k m e a n s 蚁群 南京邮电大学硕士研究生学位论文 a b s t ra c t a b s t r a c t w i t ht h er a p i d d e v e l o p m e n to ft h ei n t e r n e t ，w e bd a t a i s c r e a s i n ge x p o n e n t i a l l y t h e d e m a n d so fp o t e n t i a lv a l u ei nt h ew e br e s o u r c e si m p r o v et h ea p p l i c a t i o no fd a t am i n i n g t e c h n o l o g yo ni t a st h em a s s ，h i g h - d i m e n s i o n a l ，d y n a m i ca n du n p r e d i c t a b l eo ft h ew e bd a t a , r e s e a r c ho nt h ec l u s t e r i n gb a s e do nw e bh a sg r a d u a l l yb e c o m et ob ean e wh o t s p o t i nt h i st h e s i s ，t h ea p p l i c a t i o no fc l u s t e r i n ga l g o r i t h mi nw e bm i m n gi ss t u d i e d f o rt h e c h a r a c t e r i s t i c so fw e bt e x td a t a ，s o m eo ft h eo r i g i n a lc l u s t e r i n ga l g o r i t h m sa l em a d ec e r t a i n i m p r o v e m e n t st oa d a p tt ow e b t e x tm i n i n g ，a n dt oi n c r e a s et h ec l u s t e r i n ga c c u r a c y i no r d e rt ou s et h ek - m e a n sc l u s t e r i n g a l g o r i t h m t om i n ew e bt e x t ，an e wd a t a p r e - p r o c e s s i n gm e t h o di si n t r o d u c e da n dt h ec h o i c eo ft h ei n i t i a lp a r t i c l ei so p t i m i z e d t h e n ，a n i m p r o v e dk m e a n sc l u s t e r i n ga l g o r i t h mi sd e s i g n e d t h e nt h et h e s i ss t u d i e st h ec o l o n yc l u s t e r i n g a l g o r i t h ma sw e l la si t sa p p l i c a t i o ni nt h ew e bm i n i n g c o n s i d e r i n gt h eo r i g i n a la n tc o l o n y c l u s t e r i n ga l g o r i t h m ( a c c a ) d o e s n tt a k et h ec o n t r i b u t i o nr a t eo fe v e r yf e a t u r ei n t oa c c o u n t ， t h i st h e s i si n t r o d u c e san e wf e a t u r ew e i g h t e da l g o r i t h ma n du s e san e wp r o b a b i l i t yc o n v e r s i o n f u n c t i o n f o rt h eo u t l i e rp r o b l e mo fa c c a ，i tp r o p o s e sac o m b i n a t i o no fc l u s t e r i n ga l g o r i t h m b a s e do nh i e r a r c h i c a lc l u s t e r i n ga l g o r i t h ma n da n tc o l o n yc l u s t e r i n ga l g o r i t h m 一一h a c c a t h e t h e s i sa l s oi m p l e m e n t st h e s ea l g o r i t h m s ，a n dh a sd o n es i m u l a t i o ne x p e r i m e n t su s i n gs o m eo ft h e d o c u m e n t - f e a t u r em a t r i xd a t ao f p e o p l e sd a i l ya n n o t a t e dc o r p u s ”，t ov e r i f yt h ee f f e c t i v e n e s so f e a c hd e s i g n e da l g o r i t h m si nt h ew e bt e x tm i m n g t h i sp a p e rh a sd o n es o m eb e n e f i c i a lr e s e a r c ht ot h ea p p l i c a t i o no fc l u s t e r i n ga l g o r i t h m si n w e b m i m n g k e y w o r d s ：w e bm i n i n g ；c l u s t e r i n g ；k - m e a n s ；a n tc o l o n y i i 南京邮电大学硕士研究生学位论文目录 目录 摘要：i a b s t r a c t 。：i i 第一章引言1 1 1 研究背景及选题意义1 1 2 论文所做的工作2 1 3 论文内容安排2 第二章w e b 挖掘技术概述4 2 1 数据挖掘简介4 2 2w e b 挖掘概念及特点6 2 3w e b 挖掘分类6 2 3 1w 曲内容挖掘7 2 3 2w e b 结构挖掘9 2 3 3w e b 用户访问信息挖掘1 0 2 4 本章小结1 2 第三章聚类算法及研究现状概述1 3 3 1 聚类概述1 3 3 2 聚类所需数据类型。1 5 3 2 1 数据矩阵1 5 3 2 2 相异度矩阵1 5 3 3 聚类算法分类16 3 3 1 划分方法l7 3 3 2 层次方法1 8 3 3 - 3 基于密度的方法1 9 3 3 4 基于网格的方法1 9 3 3 5 基于模型的方法2 0 3 3 6 基于计算智能的方法2 0 3 4 现阶段聚类研究热点2 1 3 5 本章小结2 2 第四章k - m e a n s 聚类算法在w e b 文本挖掘中的应用研究2 3 4 1k 均值聚类概述2 3 4 1 1k 均值聚类概念及基本原理2 3 4 1 2k 均值聚类面临的问题及解决思路2 4 4 2 适用于k m e a n s 算法的数据预处理方法2 5 4 3 改进的k m e a n s 算法2 5 4 3 1 初始质心选择算法的优化2 6 4 3 2 改进后的k m e a n s 算法流程2 6 4 4 算法仿真及结果分析2 7 4 4 1 实验数据集2 7 i i i 南京邮电大学硕士研究生学位论文 目录 4 4 2 算法实现2 8 4 4 3 实验结果及分析。3l 4 5 本章小结3 4 第五章蚁群聚类算法及其在w e b 文本挖掘中的应用研究3 5 5 1 蚁群聚类算法概述3 5 5 1 1 基于蚂蚁觅食原理的聚类算法3 7 5 1 2 基于蚂蚁自我聚集行为的聚类算法3 7 5 1 3 基于蚂蚁化学识别系统的聚类算法。3 9 5 1 4 基于蚁群形成原理的聚类算法4 0 5 2 改进的蚁群聚类算法( h a c c a ) 4 3 5 2 1 特征加权算法4 3 5 2 2 概率转换函数一4 4 5 2 3 离群点处理策略4 5 5 2 4h a c c a 算法流程。4 6 5 3 算法仿真及结果分析。4 6 5 3 1 实验数据集4 6 5 3 2 算法实现4 7 5 3 3 实验结果及分析5 2 5 4 本章小结5 4 第六章总结与展望5 5 缩略词5 6 图表清单5 7 j l 炙 谢5 8 参考文献o 5 9 攻读硕士学位期间的学术论文“ i v 南京邮电大学硕士研究生学位论文第一章引言 1 1 研究背景及选题意义 第一章引言 随着数据库技术的成熟和应用的普及，人们积累的数据量以指数级的速度迅速增长， 与此同时也陷入了“数据丰富，知识贫乏”的尴尬境地。一个新的研究领域数据挖掘( d a t a m i n i n g ，d m ) 应运而生。数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的 实际应用数据中发现隐含的、规律性的、人们事先未知的，但又是潜在有用的并且最终可 被理解的信息和知识的非平凡过程。 i n t e r n c t 目前是一个巨大、分布广泛、全球性的信息服务中心，它涉及新闻、广告、消 费信息、金融管理、教育、政府、电子商务和许多其他信息服务。w e b 包含了丰富和动态 的超链接信息，以及w e b 页面访问和使用信息，这为数据挖掘提供了丰富的资源。w e b 数据挖掘是数据挖掘技术与w e b 相结合的产物，是一项综合技术，是从w w w 资源上抽 取信息( 或知识) 的过程，是对w e b 资源蕴涵的、感兴趣的、未知的、有潜在应有价值的 模式的提取。它反复使用多种挖掘数据算法，从观测数据中确定模式或合理模型，也是将 数据挖掘技术和理论应用于对w w w 资源进行挖掘的一个新兴的研究领域。 为此，本文对w e b 数据挖掘技术进行研究，并重点研究w e b 数据挖掘中的聚类算法及 应用。 聚类是将物理或抽象对象的集合分成相似的对象类的过程。由于数据库中收集了大量 的数据，聚类分析已经成为数据挖掘研究领域中的一个非常活跃的研究课题，研究工作集 中在为大型数据库的有效聚类分析寻找适当的方法。活跃的研究主题集中在聚类方法的可 伸缩性、对复杂形状和类型的数据聚类的有效性，高维聚类技术，以及针对大型数据库中 混合数值和分类数据的聚类方法。 传统的聚类算法包括划分方法、层次方法、基于密度的方法、基于网格的方法和基于 模型的方法。这些聚类方法在处理一般的数据方面效果还不错，但在处理高维的、动态的 w e b 数据时聚类效果并不理想。近年来不断有人提出将新的数据计算方法应用到传统的聚 类算法中去，取得了较好的效果。与此同时也涌现了不少新的算法，比如蚁群算法、神经 网络算法等，这些算法经过改进后应用到w e b 聚类研究领域之后，效果比一般聚类方法要 好，成为了目前的研究热点之一。 本文的研究工作将具有较高的理论价值和现实意义。 l 南京邮电大学硕士研究生学位论文第一章引言 1 2 论文所做的工作 本文重点分析了数据挖掘中各种聚类算法的原理及应用情况，对已有的一些经典聚类 算法做了分析研究，针对w e b 数据的海量性、高维性以及动态性等特征，提出了新的聚类 思路和改进方法。 具体工作如下： 1 ) 详细介绍了w e b 挖掘技术，着重分析了三种w e b 挖掘技术的挖掘原理及过程，对 于w e b 挖掘技术在网络中的应用也做了一定的阐述和展望。 2 ) 重点介绍了w e b 挖掘中应用比较广泛的聚类算法，分析了各算法的优缺点，给出 了现阶段聚类的研究热点及方向。 3 ) 详细分析了k 均值聚类算法，引入一种数据预处理算法，并且优化了初始质心的 选择，之后使用处理后的人民日报标注语料库向量数据集，进行了实验验证，实验结 果表明使用改进的k m e a n s 算法在聚类的精确度上有了很大的提高。 4 ) 重点分析了蚁群聚类算法，将特征加权算法引入到聚类的运算中，使用了新的概 率转换函数，并进行了实验验证；针对离群点问题，本文也提出了一种新的处理策略。之 后使用3 ) 中的部分向量数据集做了仿真验证，试验结果证明此算法可以有效提高w r e b 聚 类的精确度。 1 3 论文内容安排 本文共有七章，后续各章的内容如下： 第二章w e b 挖掘技术概述：简单介绍了数据挖掘技术和w e b 挖掘技术，重点叙述了 w e b 挖掘的三种类型，即w e b 内容挖掘、w e b 结构挖掘和w e b 用户访问信息挖掘，之后 分析了w e b 挖掘的特点。 第三章聚类算法及研究现状概述：简单介绍了聚类的一般概念和数据挖掘应用对于 聚类的要求，详细介绍了现阶段聚类算法的分类，在分析了各自算法的原理及研究现状后， 总结出了现阶段聚类的研究热点。 第四章k 均值聚类算法在w e b 文本挖掘中的应用研究：详细介绍了经典的k m e a n s 算法，分析了其优劣；引入一种数据预处理算法；并且优化了初始质心的选择，通过仿真 实验验证了所做工作对w e b 文本聚类的有效性。 第五章蚁群聚类算法及其在w e b 文本挖掘中的应用研究：详细介绍了传统的蚁群聚 2 堕室坚皇奎兰堡主堕垄竺堂垡堡奎 兰二兰! ! 宣 类算法，针对其不足，对原有的算法进行了改进，通过仿真实验验证了该算法在w e b 文本 挖掘中的有效性。 第六章结束语：总结了本文所做工作，分析了不足之处，提出了下一步的研究目标。 南京邮电大学硕士研究生学位论文第二章w e b 挖掘技术综述 第二章w e b 挖掘技术概述 随着i n t e m e t i n t r a n e t 技术的发展，尤其是w e b 的全球普及，使得w e b 上的信息量无 比丰富，越来越多的机构和个人在网络上发布信息、查找信息。网络己成为人们获得信息 的必要途径和重要手段。但是，网络在给人们带来方便的同时，也带来了许多问题。w e b 上的数据是海量的，同时，w e b 是无结构的、动态的，w e b 页面极其复杂。这样就使得人 们从成千上万的w e b 站点中找到有用的数据变得比较困难。于是，如何开发和利用w e b 上的数据资源己成为倍受关注的问题。 w e b 挖掘( w e bm i n i n g ) 是解决上述问题的一个途径，当数据挖掘技术应用于网络环境 下的w e b 中就称为w e b 挖掘，w e b 挖掘的任务就是从w e b 文档和w e b 活动中抽取感兴趣 的、潜在的有用模式和隐藏的信息。 2 1 数据挖掘简介 1 数据挖掘的概念 数据挖掘( d a mm i n i n g ，d m ) 是从大量的、不完全的、有噪声的、模糊的、随机的 数据中提取隐含在其中的、人们事先不知道的，但又是前在有用的信息和知识的过程【1 1 。 由于数据挖掘是一门来自各种不同领域的交叉性学科，因此有许多不同的术语名称。除了 数据挖掘外，主要还有如下若干种称法：“知识抽取 、“信息发现”、“智能数据分析、“探 索式数据分析 、“信息获取 、“数据考古”、“数据库中的知识发现 、“数据融合 等等。 其中，最常用的术语是“知识发现”和“数据挖掘”。相对来讲，知识发现则主要流行于 人工智能和机器学习界，而数据挖掘主要流行于统计界、数据分析、数据库和管理信息系 统界。 2 数据挖掘的任务 数据挖掘的主要任务可分为：类概念描述( c l a s s c o n c e p td e s c r i p t i o n ) 、分类 ( c l a s s i f i c a t i o n ) 、聚类分析( c l u s t e r i n ga n a l y s i s ) 、关联分析( a s s o c i a t i o na n a l y s i s ) 和序 列分析( s e q u e n c ea n a l y s i s ) 等【2 】。 分类的任务是找出描述并区分数据类或概念的模型( 或函数) ，以便能够使用模型预 测类标记未知的对象类，导出模型是基于对训练数据集( 即其类标记已知的数据对象) 的 分析【3 】o 这些算法的输出通常是“分类器 ，例如决策树或者规则等形式。一个理想的入侵 4 南京邮电大学硕士研究生学位论文第二苹w e b 挖掘技术综述 检测应用程序能够获取足够多的“正常 和“异常 审核数据，然后使用分类算法“学 到一个分类器，该分类器可以标记或预测新的审核数据是属于正常类还是异常类。有关算 法包括：分类规则、贝叶斯理论、决策树、s v m ( 支持向量机) 以及神经网络、基于案例 的推理等。 聚类是把数据划分到不同组中，组间差别尽量大，组内差别尽量小。聚类与分类的最 大区别就是，分类是有监督的，聚类是无监督的，聚类前不知道要划分成几个组和怎样的 组，也不知道根据哪些数据项来定义组，聚类后再总结以再发现共同点。 回归与分类相似，但预测值是连续的。 关联分析的任务是找出数据记录中字段之间的关系，审核数据中系统特征的相关性， 即找出以下形式的一种规则：满足条件a 的实体有x 也满足条件b 。有关算法包括：关 联规则分析( a p r i o r i 算法及其改进) 、约束关联挖掘等。 序列分析用于建模序列模式。它与关联分析相仿，并且把数据之间的关联性与时间联 系起来。这些算法可以发现哪些基于时间的审核事件序列经常一起发生的。有关算法包括： 频繁事件、趋势分析等【1 1 。时间序列模式根据数据随时间变化的一系列的值来预测将来的 值。 3 数据挖掘一般步骤 一个功能完善的、面向应用的数据挖掘过程一般应该包括如图2 1 所示的几个步骤。 下面对各步骤的功能做一个简单描述。 图2 - 1 数据挖掘过程示意图 1 ) 数据选择：选择与目标相关的数据进行数据挖掘。根据不同的数据挖掘目标，对 数据进行处理，不仅可以排除不必要的数据干扰，还可以极大地提高数据挖掘的效率。 2 ) 数据预处理【4 】：主要进行数据清理、数据集成和变换、数据归约、离散化和概念分 层生成。 3 ) 模式发现：从数据中发现用户感兴趣的模式的过程，是知识发现的主要的处理过 程。 4 ) 模式评估：通过某种度量得出真正代表知识的模式。 5 ) 知识表示：将发现的知识通过可视化技术以及其它一些知识表示技术提供给最终 s 南京邮电大学硕士研究生学位论文 第二章w e b 挖掘技术综述 用户。 2 2w e b 挖掘概念及特点 如前所述，w e b 数据挖掘是数据挖掘技术与w e b 相结合的产物【3 1 ，是一项综合技术， 是从w w w 资源上抽取信息( 或知识) 的过程，是对w e b 资源蕴涵的、感兴趣的、未知 的、有潜在应有价值的模式的提取。它反复使用多种挖掘数据算法【5 1 ，从观测数据中确定 模式或合理模型，是将数据挖掘技术和理论应用于对w w w 资源进行挖掘的一个新兴的研 究领域。 w e b 数据有其自身的特点： 1 ) 海量：对有效的数据仓库和数据挖掘而言，w e b 似乎太庞大。w e b 的数据量目前以 百万兆字节计算，而且仍然在迅速地增长。许多机构和社团都在把各自大量的可访问信息 置于网上。这使得几乎不可能去构造一个数据仓库来复制、存储或集成w e b 上的所有数据。 2 ) 复杂：w e b 页面的复杂性高于任何传统的文本文档。w e b 页面缺乏统一的结构， 它包含了远比任何一组书籍或其它文本文档多得多的风格和内容。 3 ) 动态：w e b 是一个动态性极强的信息源。w e b 不仅以极快的速度增长，而且其信 息还在不断地发生着更新。新闻、股票市场、公司广告和w e b 服务中心都在不断地更新着 各自的页面，w e b 日志更是每秒钟都会记录下大量的访问信息。 4 ) 用户群广泛：w e b 面对的是一个广泛的用户群体。因特网上连接的用户群一直在 不断地扩展，各个用户可以有不同的背景、兴趣和使用目的。w e b 上的大量信息相对于大 多数用户是无用的。用户往往只关心w e b 上的很小一部分信息，对其余信息不感兴趣。 2 3w e b 挖掘分类 根据w e b 挖掘的对象不同，大体可以分为如图2 2 所示三种类型：w e b 内容挖掘、 w e b 结构挖掘和w e b 访问信息挖掘，并且每一类下面还有具体的小的分类。以下具体介绍 了三种类型的概念及挖掘对象。 w e b 内容挖掘 文本 挖掘 多媒体 挖掘 w e b 数据挖掘 超链接 挖掘 w e b 结构挖掘 页内结构 挖掘 u i 也 挖掘 w e b 用户访问信息挖掘 访问模式 挖掘 个性化 服务 南京邮电大学硕士研究生学位论文 第二章w e b 挖掘技术综述 2 3 1w e b 内容挖掘 w e b 内容挖掘就是对w e b 页面内容进行挖掘【6 】。按照处理对象的不同，将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 o 等多媒体类型的挖掘) 。w e b 文本挖掘可以对w 曲上大量文档集合的内容进行总结、 分类、聚类、关联分析，以及利用w e b 文档进行趋势预测等。本文所做的聚类算法研究主 要就是基于w e b 文档进行的。因此，这里重点介绍一下w e b 文本挖掘的应用以及其中的 文本聚类相关技术。 1 ) w e b 文本挖掘技术及应用 w e b 文本挖掘可以对w e b 上大量文档集合的内容进行总结、分类、聚类、关联分析， 以及利用w e b 文档进行趋势预测等。 ( 1 ) 文本总结 文本总结是指从文档中抽取关键信息，用简洁的形式对文档内容进行摘要或解释。这 样，用户不需要浏览全文就可以了解文档或文档集合的总体内容。文本总结在有些场合十 分有用，例如，搜索引擎在向用户返回查询结果时，通常需要给出文档的摘要。目前，绝 大部分搜索引擎采用的方法是简单地截取文档的前几行。文献 7 】提出了使用中心文档来代 表文档集合、使用中心词汇来表示文档的方法，并给出了求取中心文档和中心词汇的算法。 ( 2 ) 文本分类 文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一个类别。这 样，用户不但能够方便地浏览文档，而且可以通过限制搜索范围来使文档的查找更为容易。 利用文本分类技术可以对大量文档进行快速、有效地自动分类。目前，文本分类算法有很 多种，比较常用的有t f i d f t 8 1 和n a i v eb a y e s 【9 】等方法。 ( 3 ) 文本聚类 与分类的不同，聚类没有预先定义好的主题类别，它的目标是将文档集合分成若干个 簇，要求同一簇内文档内容的相似度尽可能地大，而不同簇间的相似度尽可能地小。h e a r s t 等人的研究已经证明了“聚类假设”，即与用户查询相关的文档通常会聚类得比较靠近， 而远离与用户查询不相关的文档f 1 0 】。因此，我们可以利用文本聚类技术将搜索引擎的检索 结果划分为若干个簇，用户只需要考虑那些相关的簇，大大缩小了所需要浏览的结果数量。 目前，有多种文本聚类算法，大致可以分为两种类型：以g h a c 等算法为代表的层次凝 聚法和以k - m e a n s 等算法为代表的平面划分法【1 2 1 。文献【1 3 】介绍了将g h a c 和k - m e a n s 7 南京邮电大学硕士研究生学位论文 第二章w e b 挖掘技术综述 集合起来的b u c k s h o t 方法和f m e t i o n a t i o n 方法。 ( 4 ) 关联分析 关联分析是指从文档集合中找出不同词语之间的关系。b r i n 提出了一种从大量文档中 发现一对词语出现模式的算法，并用来在w e b 上寻找作者和书名的出现模式，从而发现了 数干本在a l n a z o n 网站上找不到的新书籍1 1 4 1 。w a n g 等人以w e b 上的电影介绍作为测试文 档，通过使用o e m 模型从这些半结构化的页面中抽取词语项，进而得到一些关于电影名 称、导演、演员、编剧的出现模式【1 5 】。 ( 5 ) 分布分析与趋势预测 分布分析与趋势预测是指通过对w e b 文档的分析，得到特定数据在某个历史时刻的情 况或将来的取值趋势。f e l d m a n 等人使用多种分布模型对路透社的两万多篇新闻进行了挖 掘，得到主题、国家、组织、人、股票交易之间的相对分布，揭示了一些有趣的趋势【1 6 1 。 w o t h r i c h 等人通过分析w e b 上出版的权威性经济文章，对每天的股票市场指数进行预测， 取得了良好的效果【17 】。 2 ) 文本聚类相关技术 文本聚类是根据文本内容自身的特性来组织文本集合，通过特定的处理和相应的算法 将整个集合聚成若干个类，并使得属于同一类的文本尽量相似( 即内容相关) ，属于不同 类的文本差别明显( 即内容无关) 。由于事先没有关于这些文本信息的分类知识或可以使 用的分类表，因此，文本的聚类处理是一种无监督的学习( u n s u p e r v i s e dl e a r n i n g ) 。 下面给出文本聚类的定义： 定义2 1 文本聚类( d o c u m e n tc l u s t e r i n g ) 可以描述为：对一个给定的文本集合d = d l ， d 2 ，“ ，最终要得到一个簇的集合c = c l ，c 2 ，c k ，u 叁量c l = d ，使得对每一个 v c t i ( d l d ) ，3 c ：i ( c ： c ) ，也ec ：i ，使得簇之间的相似度最小，而簇内部的相似度最大，其中 1 1 为文档的总数目，k 为聚类最终的个数，且岛n q = 叠，j 笮l 。 文本聚类的一般过程如下图2 3 所示： 8 南京邮电大学硕士研究生学位论文 第二章w e b 挖掘技术综述 图2 - 3 文本挖掘的一般过程 文本聚类的第一步是把文档表示成聚类算法可以处理的形式。要想将非结构化的文档 集进行聚类，首先需要进行文本预处理，生成中文文档的结构化表示，然后再进行聚类。 而文档预处理主要包括自动分词、词频统计、停用词过滤、向量化表示、特征提取等几步。 中文预处理的第一步是自动分词，这是把输入计算机的中文语句加入分隔符的过程。 目前有许多种基于字符匹配的计算机自动分词算法，这些算法大致可分为机械匹配方法和 理解式切分方法。自动分词完成之后，下一步是文本特征提取过程，这需要从所有出现在 一个文档中的词汇中，选取出可以表征该文档内容特征的特征词汇，同时就可以删除那些 与表达文档内容无关的词汇。在初步确定特征项后，需要对特征项进行权重评价，最广泛 使用的方法是在向量空间模型( v s m ) 中用t f i d f 权重计算方法。经过以上步骤，完成 文本特征向量维数缩减后得到一个列维数较少的文档特征矩阵，在这个二维矩阵中，一行 代表一个文档，而列代表特征，接下来的任务是使用适当的聚类算法对该矩阵进行聚类。 由于本文重点研究如何用聚类算法进行w e b 文本数据的挖掘，所以图2 3 中的前5 个 步骤地有关技术将不进行研究。 2 3 2w e b 结构挖掘 w e b 结构挖掘是从页面的超级链接中发现其结构及其相互关系。通过找到隐藏在一个 个页面之后的链接结构模型，就可以利用这个模型对w e b 页面重新分类，也可以用于寻找 9 壹室坚皇奎兰堡主塑壅生兰垡堡壅笙三兰! 竺堡塑垫查堡堕 相似的网站。基于超级链接的拓扑结构，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 等关系；同 时，他们还利用超链中的标记文本对链宿页面进行分类，取得了较好的效果【l 引。超链还反 映了文档间的引用关系，一个页面被引用的次数体现了该页面的重要性。b r i n 等人通过综 合考虑页面的引用次数和链源页面的重要性来判断链宿页面的重要性，从而设计出能够查 询与用户请求相关的“权威 页面的搜索引擎【l9 1 。 每个w r e b 页面并不是原子对象，其内部有或多或少的结构。s p e r t u s 对w e b 页面的内 部结构作了研究，提出了一些启发式规则，并用于寻找与给定的页面集合 p 1 ，p n 相关的其它页面【2 0 1 。d i p a s q u o 使用h t m l 结构树对w e b 页面进行分析，得到其内部结构 特征，从而学习公司的名称和地址等信息在页面中的出现模式【2 i 】。 w e b 页面的u r l 可能会反映页面的类型，也可能会反映页面之间的目录结构关系。 s p e r t u s 提出了与w e b 页面u r l 有关的启发式规则，并用于寻找个人主页，或者寻找改变 了位置的w e b 页面的新位置【2 0 1 。 2 3 3w e b 用户访问信息挖掘 w e b 用户访问信息挖掘是从用户“访问痕迹 中获取有价值的信息，是对w e b 上日志 数据及相关数据的挖掘。w e b 用户访问信息挖掘可分为_ 般存取路径追踪和专用化追踪。 前者是用k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，数据库中的知识发现) 技术理解一般访 问模式和趋势，如w e b 日志挖掘；后者是分析某一时刻每一个用户的访问模式，网站将根 据这些模式自动重建结构，如自适应站点。 1 ) w e b 日志挖掘流程 在对数据挖掘的研究中定义了数据挖掘的步骤为：确定业务对象，数据准备阶段，解 释并评估挖掘结果，数据挖掘阶段，知识的同化等。同样可以将w e b 日志挖掘归纳为下面 五步： ( 1 ) 获取w e b 日志数据。 ( 2 ) w e b 日志数据的预处理：根据挖掘的目的，对原始数据进行提取、分解、合并，最 1 0 童室坚皇奎堂堡圭堑壅竺兰垡笙茎墨三兰些! 堡塑茎查堡垄 后转化为适合进行数据挖掘的数据格式，并保存到关系型数据库表或数据仓库中，等待进 一步处理，这是一个“数据清洗”和数据仓库“建仓 的过程。 ( 3 ) 模式的发现：运用数据挖掘算法对数据仓库中经过清洗后的w e b 日志数据进行挖 掘，生成模式，发现知识。 ( 4 ) 模式分析：对模式进行分析，将有价值的模式提取出来。 ( 5 ) 模式的评价：将所得的模式与数据挖掘目的进行对比，对数据挖掘算法进行修正， 使得模式更靠近挖掘目的。 2 ) w e b 日志挖掘应用 互联网迅速发展，分析互联网背后的用户行为，是获取用户行为偏好的重要利器。国 外学者己经尝试着把w e b 用户访问日志挖掘研究应用在以下几个方面 2 2 1 ： ( 1 ) 为用户提供个性化的服务 根据用户访问历史，动态地向用户推荐商品，正如a l l l a z o n t o m 所做的，在电子商务 网站上进行个人营销，具有很大的商业价值。w e b 日志数据挖掘完全可以实现这一功能。 ( 2 ) 改善系统，提高性能 随着w w w 的通信量的增加，影响网站用户满意度的主要因素除了w e b 内容，其服 务效率也很重要。通过w e b 日志数据挖掘，可以提供网站服务效率全方位的信息，从而有 助于找到平衡服务器负荷、优化传输、减少拥塞的方法，缩短用户等待时间，提高系统服 务质量。 ( 3 ) 提高网站结构设计 w e b 结构的复杂度不断提高，w e b 站点和w | e b 服务器的设计和维护难度也在不断增加， 通过w e b 日志数据挖掘提供的用户使用网站信息，可以帮助网站设计者确定如何修改网站 结构。 ( 4 ) 电子商务网站确定用户群类 通过w e b 日志数据挖掘分析用户访问兴趣路径，可以识别顾客的购买行为，帮助确定 电子商务商品在w e b 页面上的布局排放，向用户有效地推荐商品以达到扩大商品销售量的 目的。同时，也有助于找到顾客访问网站的生命周期，为制定相应的营销策略提供依据。 ( 5 ) 网络安全 通过分析网上银行、网上商品交易用户日志，可以防范黑客攻击、恶意诈骗。 ( 6 ) 网站评估 互联网时代，谁占据了用户注意力，谁就占据了利润之源。但是，如何有效地衡量注 重室堂皇奎学硕士研究生学位论文 第二章w e b 挖掘技术综述 意力大小也是许多业界人士所关注的，w r e b 用户访问日志数据挖掘可获取用户对网站使用 的第一手资料，为网站评估提供依据。最近，c h i n a l a b s 研究的网站价值评估体系中就将用 户访问情况作为最重要的价值来源之一。 2 4 本章小结 本章简要介绍了数据挖掘的相关知识，重点介绍了w e b 数据挖掘的概念、分类以及特 点，对于三种类型的w e b 挖掘技术做了深入的分析，讨论了现阶段的研究热点以及现状。 在后续的研究中，将重点研究聚类算法及其在w e b 文本挖掘中的应用。 1 2 南京邮电大学硕士研究生学位论文第三章聚类算法及研究现状概述 第三章聚类算法及研究现状概述 作为数据挖掘的一项功能，聚类分析可以用作独立的工具，获得数据分布的情况，观 察每个簇的特征，集中对某些特定的簇做进一步的分析。作为替代，聚类分析可以作为其 它算法( 例如特征化、属性子集选择以及分类) 的预处理步骤，之后这些算法将对检测到 的簇和选择的属性或特征进行处理。在数据挖掘领域，聚类的研究工作已经集中在为大型 数据库的有效聚类分析寻找适当的方法。活跃的研究主题集中在聚类方法的可伸缩性、对 复杂形状和类型的数据聚类的有效性，高维聚类技术，以及针对大型数据库中混合数值和 分类数据的聚类方法等方面。 3 1 聚类概述 聚类作为数据挖掘与统计分析的一个重要的研究领域，近年来倍受关注。从机器学习 的角度看，聚类是一种无监督的机器学习方法，即事先对数据集的分布没有任何的了解， 它是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程。迄今为止，聚类 还没有一个学术界公认的定义。这里给出e v e r i t t l 2 3 1 在1 9 7 4 年关于聚类所下的定义：一个 类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点的汇聚， 同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离。 聚类分析作为一类非常重要的数据挖掘技术，其主要是依据样本间相似性的度量标准 将数据集自动分成几个群组，且使同一个群组内的样本之间相似度尽量高，而属于不同群 组的样本之间相似度尽量低的一种方法。聚类中的组不是预先定义的，而是根据实际数据 的特征按照数据之间的相似性来定义的，聚类中的组也称为簇。一个聚类分析系统的输入 是一组样本和一个度量样本间相似度( 或距离) 的标准，而输出则是簇集，即数据集的几 个类，这些类构成一个分区或者分区结构。聚类分析的一个附加的结果是对每个类的综合 描述，这种结果对于更进一步深入分析数据集的特性尤为重要。聚类方法非常适合用来讨 论样本间的相互关联从而对一个样本结构做一个初步的评价。 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的要求。对聚类的 典型要求如下【2 j ： 1 ) 可伸缩性 许多聚类算法对小于几百个数据对象的小数据集合工作得很好，但是，一个大规模数 1 3 南京邮电大学硕士研究生学位论文 第三章聚类