基于粒子群优化算法的Web挖掘技术的研究

摘要：Web是目前最大的信息系统。Web挖掘就从Web文档和Web活动中发现和抽取用户感兴趣的、潜在的、有用模式和隐藏的知识。本文介绍了有关web挖掘的任务和存在问题，同时介绍了PSO算法以及各种改进措施。

关键词：Web；挖掘；PSO

随着Internet的迅速发展，World Wide Web已深入到社会生活的方方面面。Web可以说是目前最大的信息系统，其数据具有海量、多样、异构、动态变化等特性。人们使用Web，一般有如下需求[1]：

获取相关信息或服务；

从Web信息中发现新的知识；

提供个性化服务：不同的用户对信息、服务有不同的要求。

为了解决上述问题，人们迫切需要能自动地从Web上发现、抽取和过虑信息的工具，由此产生了Web挖掘。

Web挖掘就是从Web文档和Web活动中发现和抽取潜在的、用户感兴趣的有用模式和隐藏的知识[2]。

1.Web挖掘

WEB挖掘可以认为包括以下四个子任务[3,4]：资源发现、信息选择和预处理、概括和泛化、分析。

资源发现是一个从Web上的联机资源中检索数据的过程。信息选择和预处理是一个信息转变的过程。它可以是除去停用词，词干处理，发现训练集中的短语，以及得到关系或逻辑表示等。概括过程是应用数据采掘技术获得知识。最后的分析是对采掘结果的验证和解释，在此过程中应该发挥人的作用。

Web文本信息的特征获取是指自动地从Web文本信息中抽取出代表其内容主题的特征词条形成特征矢量来表示Web文本。它影响到下一步Web文本分类的质量。文本挖掘问题的一个主要难点是特征矢量的维数过高，对于大多数学习算法来说都难以承受。目前已有多种方法被用于特征抽取，比如文档频次门限方法、信息增益方法、χ2分布方法、互信息熵方法、基于奇异值分解的潜在语义索引方法（LSI）以及基于遗传算法的特征提取算法等。

聚类技术是对符合某一访问规律特征的用户进行用户特征挖掘。Web使用挖掘中存在两种类型的聚类：使用聚类(用户聚类)和页面聚类。根据聚类的结果聚类方法可分为层次聚类与非层次聚类。在不同的方法中，人们研究了获得较高的计算效率的问题。

在Web使用挖掘过程中，对用户、Web页面等Web对象进行聚类时，存在明显的模糊性，模糊聚类也因此成为目前Web聚类分析研究的主流。

2.Web挖掘中存在的问题

Web数据挖掘[5]与传统数据挖掘不同，Web页面的结构比一般文本文件复杂很多，它可以支持多种媒体的表达。人们最初是希望通过Web来实现世界各种信息的互通，在这个平台上自然希望任何的信息都可以表达了。因此也造成了互联网数据的复杂性这个特点。而在互联网上文档一般是分布的，异构的，无结构或者半结构的。许多新技术的产生为解决这个难题提供了一条可行的道路，如XML技术。还有，互联网上的数据动态性极强，页面本身的内容和相关的链接经常更新。而互联网面对的客户也各不相同，这些都造成了用户行为模式分析的困难度。

现行Web挖掘方法很多，解决Web信息应用部分问题，但存在一定的不足，如：由于用户查询固有的主观性、不精确性和不确定性，大多数Web检索系统仅用一个简单的检索模型，侧重于检索效率，忽视了检索的准确性。不能进行软决策，现有查询是基于“硬抛弃”法，而且取决于查询与检索出文档的相关性，但相关性只是文档的部分属性，不是很分明的界限。页面分级还不全面，还没有考虑各种参数的权重，如点击位置、相邻性和频率等,分级还很少考虑用户的特点。

为处理Web数据特征，克服目前现有的Web挖掘方法的局限，软计算方法是一个很好的方法。软计算是一组协同的方法，它提供一种处理现实中模糊状态信息灵活处理能力。它们的目标是通过探索不精确、不确定、近似推理和局部正确的最大可能限度，达到易理解的、健壮的和低代价的解决方案，类似人的决策过程。软计算技术包括模糊逻辑(fuzzy logic，FL)、粗糙集(rough set，RS)、人工神经网络(artificial neural network，ANN)和遗传算法(genetic algorithm，GA)[ 5-8]。

现有的Web文档特征抽取算法文章证明这些特征抽取方法都有一些局限。传统的聚类分析把每个待辨识的对象严格地划分到某个类中，各个类别的界限是分明的。然而现实世界存在着大量的界限划分不严格的聚类问题。即问题具有一定的模糊性，如在区分“优”和“良”等级时，就需要模糊划分。在Web使用挖掘过程中，对用户、Web页面等Web对象进行聚类时，存在明显的模糊性，模糊聚类也因此逐渐成为Web聚类分析研究的主流。

3.粒子群优化算法

粒子群优化(Particle Swarm Optimization, PSO)算法[1]是Kennedy和Eberhart受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法，与其他进化算法一样，也是基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索；同时，PSO又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是将群体(swarm)中的个体看作是在D维搜索空间中没有质量和体积的粒子(particle)，每个粒子以一定的速度在解空间运动，并向自身历史最佳位置pbest和邻域历史最佳位置gbest聚集，实现对候选解的进化。PSO算法具有很好的生物社会背景而易理解、参数少而易实现,对非线性、多峰问题均具有较强的全局搜索能力,在科学研究与工程实践中得到了广泛关注[3-8] 。

由于PSO 中粒子向自身历史最佳位置和邻域或群体历史最佳位置聚集，形成粒子种群的快速趋同效应，容易出现陷入局部极值、早熟收敛或停滞现象。同时，PSO的性能也依赖于算法参数。为了克服上述不足，国内外学者相继提出了各种改进措施。主要有粒子群初始化、邻域拓扑、参数选择和混合策略四类。

4.结论

由此可见，由于Web信息的独特性，和传统的数据挖掘相比，Web挖掘还有很多需要解决的难题需要我们针对实际应用加以解决。

参考文献：

[1]吉林大学博士学位论文 Web挖掘中若干问题的研究 许建潮 2005.6.10.

[2]Raymond Kosala,Hendrik Blockeel, Web Mining Research: A Survey, SIGKDD Explorations,2(1),pages 1-15,July 2000.

[3]中国科学院博士学位论文 WEB信息检索与分类中的数据采掘研究 李晓黎 2001.5.21.

[4]周龙镶，阳小华．基于用户访问模式的WWW浏览路径优化[J]．软件学报，2001，12(6)，846～850.

[5]Jianhan Zhu，Jun Hong,John G Hughes．Using Markov Models for Web Site Link Prediction．In：Proceedings ofthe thirteenth ACM conference on Hypertext and hypermedia．Maryland(USA)，2002，169~170.

[6]浙江大学博士毕业论文 Web访问信息挖掘若干关键技术的研究 余轶军 2006.4.1.

[7]S.Mitra,S.K.Pal,P.Mitra.Data mining in soft computing framework:A survey.IEEE Transactions on Neural Networks,2001,13:3~14.

[8]刘清.Rough集及Rough推理，北京:科学出版社，2003.