基于群智能和随机索引的网络聚类算法研究

论文摘要

聚类（Clustering）是将数据对象划分为有意义的组（或簇）的过程。作为数据挖掘中的一种重要的技术,聚类分析在很多领域中都扮演着重要的角色。尤其是,随着当今世界各种信息的数据量不断增大、研究问题的复杂度不断增加,现有的聚类分析技术也面临着越来越多的挑战,因此,研究新的聚类算法已经成为数据挖掘、机器学习、统计学和生物学等多个相关研究领域中的前沿和热点问题之一。群居昆虫的社会性行为,诸如寻找最好的食物源、搭建结构最优的巢穴、孵卵、保护幼虫、守卫种群等都表现出群体层面的宏观智能行为。群体智能（Swarm Intelligence,简称为SI）是为了解决复杂优化问题而创立的一类分布式智能范式体系,其灵感最初就源于对自然界中昆虫群体的观察,通过模拟自然界生物的这种群体行为来实现人工智能。因为聚类策略在多个领域应用的重要性,一些基于群体智能思想的优化算法,如蚂蚁种群优化和粒子群优化等,已经被引入数据挖掘领域,来解决聚类问题。由于聚类用的评价标准函数（Criterion Functions）通常是非凸的或者是非线性的,传统的聚类方法,特别是k均值（k-means）算法,具有对聚类的初始值敏感并且容易使搜索陷入局部最优的缺点。随着实际应用中数据集的维度不断增长,寻找标准函数的最优解是一个"NP-难”的问题。Web用户在浏览网站时,会根据他们不同的信息需求或潜在的任务和目的,而表现出多种多样的行为,这些行为都被Web访问日志跟踪并且记录下来。Web日志挖掘可以通过发现和分析网络用户访问行为的特征和规律,从而达到识别网站的潜在客户、提高对用户的服务质量的目的。基于聚类算法的Web日志挖掘与用户行为分析方法发展的较晚,并且在Web聚类技术中,目前比较常见的是针对Web会话和Web页面内容的聚类方法研究,针对Web用户浏览模式的聚类方法的研究还相对较少。而且,目前已有的Web用户行为分析和聚类技术只关注用户在页面级别的浏览行为,而对于Web用户活动之间的潜在联系或隐含特征很少关注,并且对与特定浏览模式之间隐藏或无法观察的因素也研究的很少。因此,需要研究和开发新的Web用户聚类技术和用户建模技术,发掘用户行为中潜在的隐藏信息,从而有助于有效地改进用户聚类技术的性能。Web用户行为聚类的结果可以用于各种途径的高级应用任务,例如Web缓存和预取。目前有很多Web挖掘方法被用于提高从Web访问日志中预测用户访问模式的准确率,以便高效地对Web对象进行预取。目前在预取领域,现有的这些技术大部分都仅仅局限于对单个用户请求的预测,而关于对群体用户的请求预测方面的研究还较少。本论文的主要创新工作可以归纳如下：（1）针对现有的聚类算法大多存在局限于单一类型的数据集、在搜索时容易陷入局部最优并难以在高维数据集上达到理想效果的问题,本论文在已有的混沌蚂蚁群（Chaotic Ant Swarm,简写为CAS）)算法的基础上受蚂蚁混沌搜索和蚁群全局智能优化等行为的启发,根据数据聚类应用的特点,提出了一种新的基于蚂蚁混沌行为的聚类算法（简称为CAS-C算法）)。本论文拓展了混沌蚂蚁群算法的应用领域,大量的数值仿真对比实验结果表明了本论文所提的CAS-C算法具有对中心初值不敏感、能够找到全局最优解、具有较高的算法稳定性和准确率的优点。本论文所提的算法更适合于对真实的数据集进行聚类。（2）菌群觅食（Bacterial Foraging,简写为BF）优化算法是一种基于细菌群体行为和进化过程的优化搜索算法,但目前它还不够完善,菌群觅食优化算法的改进及参数调整是目前研究的一个重要问题,尤其是,基于菌群觅食行为的聚类算法方面目前的研究还很少。本论文受菌群觅食行为的启发,提出了一种新的基于菌群觅食优化思想的聚类算法（简称为BF-C算法）,通过模仿细菌觅食过程,寻找聚类的最优中心。本论文同时对算法中的各个参数在数据聚类领域的设置进行了详细地讨论与分析。与其他全局优化算法相比,本论文所提出的BF-C算法具有易于理解、计算简单、收敛速度快的优点,但其趋化步长由于缺少对环境的自适应性,需要根据具体应用问题的不同而需要进行具体的讨论。（3）应用传统的数据挖掘方法进行Web用户行为识别时,具有初值敏感、容易陷入局部最优和在高维数据的挖掘上性能有所下降的缺点。本论文针对Web聚类技术中目前面临的这些问题,将所提出的基于蚂蚁混沌行为的CAS-C聚类算法应用到Web日志分析与用户聚类当中,以发现用户的浏览模式,从而提高Web用户聚类的性能。为了检验所提方案的有效性和可行性,本论文将基于CAS-C的Web用户聚类结果与目前在Web挖掘领域广泛应用的两种算法（k值聚类算法和FCMdd算法）的Web用户聚类结果进行了比较。大量的计算机数值仿真实验表明了使用我们所提出的CAS-C算法能够获得凝聚度和分散度更好的Web用户聚类结果,可以有效地识别用户的公共兴趣。（4）在对Web用户日志进行分析和挖掘的过程中,需要对Web用户的浏览行为进行形式化的表示,这个过程一般被称为用户建模。目前已有的Web用户行为分析和聚类技术只关注用户在页面级别的浏览行为,而对于Web用户活动之间的潜在联系或隐含特征却很少关注,并且对与特定浏览模式之间隐藏或无法观察的因素也研究甚少。因此,我们提出基于随机索引的用户建模方式,借助自然语言处理领域“上下文”的概念,对URL进行分段索引建模。这样,在用户建模的过程中,能够将浏览模式中的隐藏信息加入其中,进而有效地指导Web用户聚类算法,改进聚类的效果。我们通过聚类实验比较了这两种建模方式：特征向量方法和随机索引方法,大量相关的聚类实验的结果表明了随机索引建模方式的优越性。（5）本论文所提的聚类算法可以用于各种高级应用任务,例如Web缓存和预取。同时,为了检验我们用户聚类算法的聚类效果,本文基于随机索引建模方法和CAS-C算法,提出了一种新的群体用户的行为预测和网页预取方案,通过建立用户公共档案,总结用户的共同兴趣,并且基于用户聚类结果,建立群体用户的网页预取规则,预取用户未来可能点击的网页,并存入网站的缓存中。为了使实验结果具有说服力,我们仍然选取经典的k均值聚类算法和在Web挖掘领域广泛应用的FCMdd算法作为比较算法。大量的预取实验结果表明了在随机索引用户模型的帮助下,基于CAS-C的Web用户聚类方案能够获得较高的网页预取的准确率。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 群智能优化算法
• 1.3 聚类分析
• 1.3.1 聚类分析算法
• 1.3.2 基于优化的聚类问题
• 1.3.3 聚类效果评价
• 1.4 Web用户行为分析
• 1.5 本论文的主要工作
• 1.6 本论文的组织结构
• 第二章 基于混沌蚂蚁群优化的聚类算法
• 2.1 引言
• 2.2 混沌蚂蚁群（CAS）算法
• 2.3 基于混沌蚂蚁群优化的聚类算法（CAS-C）
• 2.3.1 CAS-C算法原理与流程
• 2.3.2 比对算法
• 2.3.3 评价指标
• 2.4 聚类实验
• 2.4.1 数据集
• 2.4.2 参数设置
• 2.4.3 实验结果分析
• 2.5 本章小结
• 第三章 基于菌群优化的聚类算法
• 3.1 引言
• 3.2 菌群优化算法
• 3.3 基于菌群优化的聚类算法（BF-C）
• 3.3.1 BF-C算法原理与流程
• 3.3.2 BF-C算法参数设定原则
• 3.3.3 评价指标
• 3.3.4 比对算法
• 3.4 聚类实验
• 3.4.1 数据集
• 3.4.2 参数讨论
• 3.4.3 实验结果分析
• 3.5 本章小结
• 第四章 基于随机索引的Web用户建模和聚类算法
• 4.1 引言
• 4.2 随机索引
• 4.3 加权随机索引
• 4.4 基于加权随机索引的用户建模和聚类过程
• 4.4.1 单个用户兴趣页面集合
• 4.4.2 URL分段
• 4.4.3 用户浏览模式矩阵
• 4.4.4 基于k值算法的Web用户聚类
• 4.5 评价指标和比对方法
• 4.5.1 评价指标
• 4.5.2 比对方案
• 4.6 参数讨论
• 4.6.1 类别数目k
• 4.6.2 权重
• 4.6.3 维度d
• 4.6.4 其他参数
• 4.7 实验结果分析
• 4.8 本章小结
• 第五章 基于CAS-C的Web用户聚类
• 5.1 引言
• 5.2 实验方案
• 5.2.1 数据来源
• 5.2.2 比对算法
• 5.2.3 评价指标
• 5.3 数据预处理
• 5.3.1 数据清洗
• 5.3.2 用户识别
• 5.3.3 会话识别
• 5.4 Web用户访问模型建立
• 5.4.1 基于特征向量的用户建模
• 5.4.2 基于随机索引的用户建模
• 5.5 Web用户聚类实验
• 5.5.1 参数讨论
• 5.5.2 实验结果及分析
• 5.6 本章小结
• 第六章 基于公共用户访问行为的Web预取
• 6.1 引言
• 6.2 算法评价
• 6.2.1 评价指标
• 6.2.2 比对算法
• 6.3 预取方案
• 6.3.1 用户行为预测
• 6.3.2 预取规则
• 6.4 实验结果及分析
• 6.5 本章小结
• 第七章 工作小结与展望
• 7.1 本论文研究工作总结
• 7.2 研究工作展望
• 参考文献
• 致谢
• 攻读学位期间学术成果目录