学位论文 > 优秀研究生学位论文题录展示

基于ACO的Web使用挖掘方法研究

作　者: 凌海峰
导　师: 刘业政；杨善林
学　校: 合肥工业大学
专　业: 管理科学与工程
关键词: 网站导航推荐 Web使用挖掘蚁群算法收敛性会话识别用户兴趣导航路径模式 Web用户聚类
分类号: TP393.09
类　型: 博士论文
年　份: 2009年
下　载: 247次
引　用: 2次
阅　读: 论文下载

内容摘要

互联网技术的迅速发展,实现了全球的资源共享和信息交换。然而互联网上的信息量呈指数级速度增长所导致的“信息过载”和“信息迷航”问题已日益制约用户高效地使用各种信息资源。网站通过提供Web个性化服务可以提高用户的访问效率和满意度。实现Web个性化推荐所面临的关键问题是需要对大量匿名用户的行为模型进行深层理解,传统的个性化方法很难处理匿名用户的情形,把Web使用挖掘用于Web个性化推荐是解决上述问题的有效途径。作为Web数据挖掘的一个重要组成部分,Web使用挖掘就是利用数据挖掘技术分析用户访问留下的日志文件,挖掘用户浏览模式的过程。Web使用挖掘可用于理解用户在网站的访问行为,从而可以主动为用户提供网站导航服务。蚁群算法(Ant Colony Optimization,简称ACO)作为群体智能算法的一个分支,是受真实蚁群觅食行为的启发而逐步发展起来的一种模拟蚂蚁群体智能行为的算法。由于其在求解复杂优化问题方面的优势,在许多领域都得到了应用。因此,将蚁群算法引入Web使用挖掘、发现用户的浏览模式、为用户提供导航推荐服务,具有重要的理论意义和应用价值。本文首先对蚁群算法的收敛性和Web使用数据的预处理进行了研究,在此基础上,分别将蚁群算法应用于用户导航模式和用户聚类的挖掘。所做的主要工作及创新性研究成果如下:(1)在图搜索蚂蚁系统的收敛性分析基础上,对基本蚁群算法进行了改进,并对这种改进的蚁群算法构造全局最优解的概率等收敛性问题进行了研究。首先对Dorigo Macro提出的基本蚁群算法中的Ant Cycle模型作了三点改进:其一是仅最优秀蚂蚁释放信息素,即在第t步迭代结束之后,仅对前t步迭代中所找到的最优解上的弧进行信息素的加强,这样就鼓励蚂蚁在至今发现的最好路径的邻近区域去搜索路径,使蚂蚁对解空间的探索更有方向性;其二是对残留信息素数量进行限幅控制。为了避免算法过早收敛于非全局最优解,在算法的迭代过程中,对任意弧上的残留信息素设定了下界;其三是信息素挥发系数自适应变化。通过挥发系数的自适应变化使蚁群在算法的前面阶段增加搜索的随机性,避免搜索过度集中,有利于搜寻更优解;在算法的后期,减小随机程度,增加收敛速度,使算法在已经搜索到较优解的情况下,逐渐收敛到全局最优解。在此基础上,对该算法的收敛性进行了证明。在仅需满足两个基本假设条件的前提下,证明了算法能以接近于1的概率收敛于最优解。实验结果表明,与基本蚁群算法相比,本文算法的全局搜索能力与收敛速度都有所提高,是一种有效的算法。(2)在分析现有的Web使用数据预处理过程的基础上,对预处理中的一个关键问题——会话识别问题进行了研究,并提出了一种基于自适应时间阈值的会话识别方法。传统的面向时间的方法只根据一个固定的时间阈值参数来识别会话的方法是具有局限性的,本文利用动态的时间阈值参数进行会话识别,分析每个用户的平均页面访问时间,并结合固定的时间阈值得到一个动态的自适应时间阈值,从而实现会话访问时间参数的个性化。实验结果表明,通过该方法获得的用户会话能够更加准确地描述用户的实际浏览行为,对模式发现阶段能够产生好的影响,从而可以提高基于Web使用挖掘的用户导航推荐结果的质量。(3)基于蚂蚁觅食行为与月户浏览网页行为的相似性,把Web用户看成是人工的蚂蚁,利用蚁群算法中的概念“外激素”来反映用户的访问兴趣,提出了一个蚁群导航模型来挖掘用户的兴趣导航模式。首先考虑了页面访问次数、页面访问顺序、网站结构和页面访问时间等因素对用户导航路径模式挖掘的影响,其次,考虑了早期访问者与现有访问者对导航路径模式发现的不同影响,提出了基于蚁群算法的群体用户导航模型,并应用蚁群算法来发现用户偏好的导航路径模式。实验结果表明,与传统算法相比,蚁群算法应用于用户导航推荐的准确性较高,说明蚁群算法揭示的是群体用户的兴趣路径,更能反映用户的浏览偏好。(4)将蚁群算法应用于Web使用聚类挖掘领域,提出了一种蚁群算法与K-means算法相结合的方法对访问网站的用户进行聚类。首先介绍了基于群体智能的蚁群聚类算法的四种模型,然后将基于蚁群觅食行为的蚁群算法引入Web使用聚类。蚁群算法的一个重要特征是对初始过程不敏感,在满足一定的条件下总是能收敛到全局最优解,但是收敛速度较慢;与蚁群算法相对照,K-means聚类收敛速度较快,但很可能收敛到一个局部最优解,并且由于初始聚类是随机生成的,其结果受到初始过程的影响。本文提出一种将K-means算法嵌入到蚁群算法中的混合算法,充分利用蚁群算法的全局搜索能力和K-means算法的局部搜索能力,并将该算法应用到Web用户聚类问题的求解中,实验结果表明该方法是有效的,与K-means聚类算法相比,该方法显著地改善了用户导航推荐的准确性。上述研究在理论上对于蚁群算法的发展具有积极的推动作用,同时也为Web使用挖掘的研究提供了一个新的很有前景的方法,在实践上对于提高网站导航推荐的有效性、改善客户服务具有重要的意义。

全文目录

摘要  8-10
Abstract  10-13
致谢  13-19
第一章绪论  19-26
  1.1 研究背景  19-21
    1.1.1 Web个性化  19
    1.1.2 Web使用挖掘  19-21
  1.2 研究目的和意义  21-22
  1.3 研究内容及研究成果  22-24
  1.4 论文的结构安排  24-26
第二章 Web使用挖掘概述  26-39
  2.1 数据预处理  26-28
  2.2 模式发现  28-36
    2.2.1 统计分析  28
    2.2.2 聚类  28-31
    2.2.3 关联规则  31-33
    2.2.4 序列模式  33-35
    2.2.5 分类  35-36
  2.3 模式分析  36-37
  2.4 Web使用挖掘的应用  37-38
    2.4.1 Web个性化  37-38
    2.4.2 Web系统优化  38
  2.5 本章小结  38-39
第三章蚁群算法及其收敛性分析  39-59
  3.1 基本蚁群算法的思想起源与算法描述  39-43
    3.1.1 思想起源  39-40
    3.1.2 基本蚁群算法描述  40-43
  3.2 蚁群算法模型  43-44
  3.3 蚁群算法的研究现状  44-46
    3.3.1 算法应用现状  44-45
    3.3.2 算法改进研究现状  45
    3.3.3 算法收敛性研究现状  45-46
  3.4 图搜索蚂蚁系统(GBAS)的收敛性分析  46-48
    3.4.1 GBAS的数学模型  46-47
    3.4.2 GBAS的收敛性分析  47-48
    3.4.3 GBAS的局限性  48
  3.5 一类改进的蚁群算法及其收敛性分析  48-58
    3.5.1 极小化问题的数学表示  48-49
    3.5.2 改进的蚁群算法描述  49-52
    3.5.3 算法收敛性分析  52-57
    3.5.4 实验结果  57-58
  3.6 本章小结  58-59
第四章 Web使用数据预处理及会话识别  59-72
  4.1 相关概念  59
  4.2 数据收集  59-63
    4.2.1 服务器端数据  60-62
    4.2.2 客户端数据  62
    4.2.3 代理服务器端数据  62-63
  4.3 数据净化  63
  4.4 用户识别  63
  4.5 基于自适应时间闽值的会话识别  63-71
    4.5.1 会话识别问题描述  63-66
    4.5.2 相关研究工作  66-67
    4.5.3 基于自适应时间阈值的会话识别方法  67-69
    4.5.4 实验结果  69-71
  4.6 本章小结  71-72
第五章基于蚁群算法的用户兴趣导航路径模式挖掘  72-84
  5.1 引言  72
  5.2 用户导航模式研究现状  72-74
  5.3 用户浏览行为与蚁群觅食行为的相似性  74-76
    5.3.1 网站的基本模型  74
    5.3.2 群体用户导航模型  74-76
  5.4 基于蚁群算法的群体用户兴趣导航路径发现  76-78
    5.4.1 蚁群导航模型  76-77
    5.4.2 挖掘偏好导航路径的算法  77-78
    5.4.3 实验  78
  5.5 引入页面访问时间的用户导航模式挖掘  78-83
    5.5.1 页面访问时间  79-80
    5.5.2 引入页面访问时间的蚁群模型  80-81
    5.5.3 偏好导航路径的挖掘算法  81-82
    5.5.4 实验  82-83
  5.6 本章小结  83-84
第六章基于混合蚁群算法的Web用户聚类  84-97
  6.1 引言  84-85
  6.2 相关工作  85-86
  6.3 蚁群聚类算法  86-89
    6.3.1 基于蚁堆形成原理的聚类算法  86-88
    6.3.2 基于蚂蚁觅食行为的聚类算法  88-89
  6.4 基于混合蚁群算法的聚类方法  89-94
    6.4.1 Web用户聚类的数学规划模型  89-90
    6.4.2 蚁群算法与K-means算法的融合思想  90-92
    6.4.3 算法流程  92-94
  6.5 实验  94-96
    6.5.1 面向用户聚类的数据预处理  94-95
    6.5.2 实验评价  95
    6.5.3 实验结果  95-96
  6.6 本章小结  96-97
第七章总结与展望  97-100
  7.1 研究总结  97-98
  7.2 研究展望  98-100
参考文献  100-110
攻读博士学位期间参加的科研项目和发表的论文  110-111

基于ACO的Web使用挖掘方法研究

内容摘要

全文目录

相似论文