WEB日志挖掘技术的研究及应用.docx
《WEB日志挖掘技术的研究及应用.docx》由会员分享，可在线阅读，更多相关《WEB日志挖掘技术的研究及应用.docx（58页珍藏版）》请在冰点文库上搜索。
第五章，原来是关联规则，现在要改成聚类的方式，算法为第四章的改进的蚁群算法。
原来的功能图太宽跨界了，图不可以超过文档的内容部分。
第一章，主要是研究现状及分析进行修改，其他的文字表述做相应修改
查重率差不多达到10%
1引言
随着Web日志技术的急剧增长和快速普及,以及在电子商务和信息共享等方面的广泛应用，用户可以用很低的成本从网络上获得信息，Internet已成为最丰富的信息来源地，为了更好地对这些大量、无序的网页信息进行排序和检索，需要提升搜索引擎对网络信息的处理和组织能力，因此在这样的形势下，产生了Web日志挖掘（Web日志Mining）[1]技术，目的在于从Web日志的组织结构和链接关系中发掘出有用的模式和规律，该技术无疑成为数据挖掘中的热点，包括自然规则计算方法、神经网络、统计学、机器学习为主等人工智能相关技术。
随着Internet/WWW的全球互通互连，从中取得的数据量难以计算，所以当处理这些数据并且从Web日志的服务中抽取信息时需要采用Web日志挖掘技术。
Web日志挖掘需要从非结构化、半结构化或动态易混淆的数据中,抽取潜在的、易用的信息和模式的过程。
根据Web日志数据类别的不同，可以将Web日志挖掘分为以下三类：
Web日志内容挖掘、结构挖掘和使用挖掘。
这三类挖掘分别作用于网页信息站点中的内容、结构和使用信息，并且已经在发现用户访问模式、反竞争情报活动、建立数据仓库等很多方面得到了应用。
1.1课题背景及研究意义
随着万维网的迅速发展以及良好的发展趋势，尤其是电子商务的蓬勃发展为网络应用提供了强大的支撑。
然而处理Web日志上海量的数据量，需要一种能高效快捷地从Web日志页面中获取信息的工具，由此搜索引擎产生了。
现有的搜索引擎技术在很大程度上方便了人们对信息的检索，不过仍然存在一些不足之处，比如搜索精度不高、覆盖率有限等问题，无法更好地发现Web日志上潜在、隐藏的知识。
将传统的数据挖掘同Web日志相融合，从而发展出了Web日志挖掘，该技术就传统的数据挖掘来看存在较多优势。
传统数据挖掘技术只是对数据结构中结构化的数据进行挖掘，通过数据间的存储结构不同来发现知识，而Web日志挖掘是针对半结构化、杂乱、动态的数据进行挖掘，由于Web日志页面内容的复杂程度远超过普通文本的样式结果，所以导致了Web日志挖掘技术无法直接传承传统的数据库挖掘模型和技术。
这就让挖掘的前提需要将传统数据挖掘技术与Web日志挖掘相结合，融合各自的优点，使整个数据挖掘系统同数据库能更紧密的结合在一起。
由于要对数据进行组织和整合，这就需要一个完整的Web日志挖掘体系，才能分析并得出自己需要的信息。
因此进行挖掘之前需要找到相关的Web日志文档。
各Web日志信息之间有着密切的关系，从中找到正确的数据结构特点，利用自动化搜索的方法实现对Web日志上信息结构排序和内容的抽取，避免了各算法之间使用的重复性。
蚁群算法是一种模拟进化的算法，它是借鉴蚂蚁在寻找食物过程中会自动搜寻最短路径而衍生出来的。
该算法具有优良的分布式计算、正反馈性等特点，特别是在解决组合最优的问题上已经吸引了很多中外学者的关注。
它也是继遗传算法、人工神经网络算法后又一个得到大家认可的研究性课题。
1.2研究现状及分析
Web日志挖掘无论在国内还是国外都是通过挖掘服务器存储的Web日志，进而发现用户访问Web站点的访问模式。
根据对Web日志数据源处理方法的不同，Web日志挖掘可以分为以下两类：
第一类是将Web日志记录中的数据进行转换，然后传递进传统的关系表中，再用常规的算法对关系表中的数据进行挖掘。
第二类是在对Web日志记录的数据进行挖掘之前对数据先进行数据预处理操作。
国外对Web日志挖掘的研究基本上可以从1996年算起，比较突出的有：
1996年学者M.S.Chen、H.Mannila、T.Yan提出了可以将数据挖掘方法用于Web研究领域。
Mannila和Chen在研究过程中都假设去掉了图形文件、声音文件以后的Web服务器日志如实地反映了用户在网站中访问的情况。
Mannila[2]把用户访问页面当作事件，从网站访问日志中试着寻找用户访问网站的周期。
ChenError!
Referencesourcenotfound.提出了最大向前参引路径，并提出用这种方法把用户的Session分解成为一个个访问事务，然后就可以在事务基础上，挖掘用户访问的模式。
T.Yan研究了如何动态地根据将用户进行分类，并根据同类用户访问页面的情况提供推荐页面。
1997年，PerKowitz[4]等人在人机界面研究领域提出了AdaPtiveWebSite的概念，主要研究的是如何以历史访问为依据，使服务器提供的页面可以自动或者半自动化地调整。
1998年Han把Web服务器访问日志集成到数据立方体结构（Datacubestructure）中，这样就可以对访问日志用传统的在线数据分析处理过程（oLAP）来处理日志数据了Error!
Referencesourcenotfound.。
国内互联网是从1997年开始迅速蓬勃的发展起来的。
直到1999年，国内互联网用户达到一定数量以后，国内学者才开始关注Web数据挖掘，相比国外起步较晚。
国内的学者在基于Web日志挖掘的个性化服务方面主要侧重于理论研究，比较突出的有：
沈钧毅[6]等人提出以Web站点的URL为行，以UserID为列，建立URLes-UserID关联矩阵，元素值为用户的访问次数。
然后，对列向量进行相似性分析得到相关Web页面；对相关页面进行进一步处理，便可以发现频繁访问路径。
王红侠[7]等人采用基于事务的方法,研究Web日志挖掘预处理及用户访问序列模式挖掘方法，提出了一种基于BitlnaP序列模式进行用户浏览模式识别的Web日志挖掘方法。
吴俊杰[8]等人采用Web站点的访问日志进行事务识别后，根据群体用户对Web站点的访问顺序进行路径聚类，最终的聚类结果反映出全体用户的访问兴趣。
吴跃进认为，能够成为Web用户聚类算法评价因素的参数有且仅有三个，分别是点击次数、访问时间和访问路径；并在此基础上利用Kruskal算法衍生出了K-Bacer算法，根据访问频繁路径对用户进行聚类Error!
Referencesourcenotfound.。
吴跃进将所有用户的访问序列生成无向图，通过K-Bacer算法找出其中的频繁路径。
K-Bacer算法是利用Kruskal算法的思想去产生最小生成树，溯其根源是贪心算法。
算法的时间复杂度依赖于排序算法，同时对所有用户生成同一个无向图，随着用户量的增加，其可维护性和可扩展性大大降低。
（1）Web日志挖掘聚类和分类技术
聚类是从Web日志的访问数据中分析并整合出来具有相似特征事务的技术。
Web日志使用挖掘中分为：
页面聚类和使用聚类。
页面聚类是通过搜索引擎在Web日志上找到具有相关内容的页面组，这更方便于用户在上网时能更容易地获得想要的信息。
使用聚类就是将具有相似浏览模式的用户分为一组，这样形成了若干组，并对其量化，从中得到对用户有用的规则，当前该技术常应用于电子商务和一些个性化服务上。
这两种聚类方法就是通过搜索引擎分析用户查询或访问网页信息时产生的历史记录所形成的HTML，来向用户提供超链接。
分类是对新添加的数据进行分类并将一个对象分到事先定义好的类中，根据用户群的特征来挖掘出用户群的访问特征。
在Web日志挖掘中，分类可以通过访问用户信息而得到的一些用户特征，这需要抽取并选择出最好地描述这组特定用户的特征，并根据这些特征对用户进行分类。
常使用监督归纳学习算法来进行分类，如决策树、K-邻近分类法和支持向量机、机器学习法、贝叶斯分类方法等。
（2）蚁群算法
蚁群算法，现在被称为蚁群优化（ACO,AntColonyOptimization）是一种用来在图中寻找优化路径的机率型算法，它源于社会昆虫的群体活动所表现出来令人惊讶的行为，也这对日后研究蚁群行为提供全新的领域。
ACO技术是一种基于群体智能的算法，它源于自然解决问题的思想，并在求解组合优化类问题上有明显的优越性。
MarcoDorigo在1991年他的论文中首先提出了蚂蚁系统（AS）,通过正反馈、分布式协作来寻找最优路径。
并且常用于解决二次指派、多维背包、Job-shop调度等问题上。
AS优化算法采用了分布式计算方法，具有多代理性和较强的鲁棒性等特点，且该算法已被大量应用于机器人协作问题求解、电力、通信、数据分析等领域。
蚁群算法是学者受到蚂蚁觅食的启发而发现的，蚂蚁总能找到巢穴与食物源之间的最短路径。
经研究发现，蚂蚁群体协作功能是通过遗留在来往路径上的信息素（Pheromone）来进行信息通讯并形成正反馈。
假设蚂蚁走两条不同的路径来寻找食物，刚开始的时候走两条路的蚂蚁一样多，并且在搜索过程中释放出一定量的信息素，当蚂蚁沿着一条路到达终点后返回，短路径的蚂蚁来回一次时间就短且重复频率快，因而在同一时间内走过该路径的蚂蚁数目就多，洒下的信息素也就多，自然就有更多的蚂蚁会吸引过来，这样慢慢当蚂蚁数量不断增加时（同样信息素浓度也增加），最短的路径就近似被发现了。
蚂蚁系统具有搜索最优的能力，得利于其同分布式计算和正反馈机制相结合的特点，使其具有较强的并行性和鲁棒性，但也同样存在一些缺陷，如搜索停滞以及搜索结果局部最优等问题。
针对该系统存在的不足，很多中外学者提出了许多改进的蚁群算法，这些优化算法在解决局部搜索最优问题以及搜索停滞问题上有很大的提升。
在当前研究形势下，蚁群算法已经成为中外学者广泛关注的热点问题。
1.3论文组织结构
论文中较系统地分析和论述了Web日志挖掘中的各项技术。
在此理论基础上，引入了改进的蚁群算法，并将其成功应用于Web日志挖掘的聚类和分类上。
论文的整体构架如下：
第一章绪论
介绍了本课题的研究背景，主要内容和论文的组织结构
第二章基于蚁群算法的Web日志挖掘理论
介绍了Web日志挖掘理论，在论述了Web日志挖掘过程的基础上，详细地分析了Web日志挖掘中聚类和分类技术。
然后分析了蚁群算法及几种改进的蚁群算法的思想。
最后，对现有算法应用于Web日志挖掘技术上存在的问题做了详细地论述。
第三章Web日志挖掘的预处理技术
对Web日志挖掘中的关键技术，即Web日志挖掘预处理技术进行了全面的分析和总结。
第四章基本蚁群算法及其改进
对蚁群算法基本原理以传统日志挖掘算法原理进行了分析，并对基本蚁群算法进行了改进，通过仿真来说明基本蚁群算法的原理。
第五章Web日志数据挖掘系统的实现
以中名老中医临床经验、学术思想传承研究中的Web日志数据为例，基于改进的蚁群算法设计了一套Web日志数据挖掘系统，并对系统进行了评价和分析，为改善中医系统网站提出了优化建议。
第六章总结与展望
总结了本文的研究工作，提出进一步研究的方向。
2基于蚁群算法的Web日志挖掘概念
2.1Web日志挖掘
随着信息技术的普及和应用，各个领域产生了大量的数据，这些数据被获取、存储下来，其中蕴含着丰富的信息。
人们持续不断地探索处理这些数据的方法，以期最大程度地从中挖掘有用的信息，面对如潮水般不断增加的数据，人们不再满足于数据的查询和统计分析，而是期望从数据中提取信息或者知识为决策服务。
数据挖掘技术突破了数据分析技术的种种局限，它结合统计学、数据库、机器学习等技术解决从数据中发现新的信息，辅助决策这一难题，是正在飞速发展的前沿学科。
一些大型企业对数据挖掘产品和工具的使用都超过20年，并已产生了期望的效应。
此外，数据挖掘产品和工具在金融、商业、电信、医学等多个领域也得到广泛推广应用。
在数据库技术飞速发展的同时，人工智能领域的一个分支----机器学习的研究也取得了很大的进展。
自20世纪50年代开始机器学习的研究以来，在不同时期的研究途径和研究目的也不尽相同。
一般大致可以分为三个阶段，其研究内容则分别为：
神经模型和决策理论、概念符号获取及知识加强和论域专用学习。
根据人类学习的不同模式人们提出了很多机器学习方法，如：
实例学习、观察和发现学习、神经网络和遗传算法等。
其中某些常用且较成熟的算法已经被人们用于实际的应用系统及智能计算机的设计和实现中。
正是由于数据库技术和机器学习技术的发展，也是为了满足人们实际工作的需要，数据挖掘（DataMining）技术逐渐发展了起来。
Web日志挖掘是一项综合技术，是数据挖掘在Web日志上的应用，涉及有信息学、数据挖掘、机器语言学、Web日志技术等多个领域。
它是利用数据挖掘技术从Web日志相关的行为和资源中挖掘出新颖的、有效的、潜在有用、用户易理解的模式和信息的过程。
Web日志数据挖掘的基本原理过程如图2.1所示。
网站结构、内容
目标数据集
经预处理的数据
模式、规则、统计结果
有趣的模式
预处理
模式发现
模式分析
图2.1Web日志数据挖掘原理图
2.1.1Web日志挖掘分类及架构模型
根据挖掘的对象不同，我们将其分类三类：
Web日志内容挖掘、Web日志结构挖掘和Web日志使用挖掘。
（1）Web日志内容挖掘：
又可分为Web日志页面挖掘和查询结果归纳；内容挖掘主要是指从Web日志文档的内容或其描述中提取知识以及对搜索中发现的有用信息进行分析的过程。
（2）Web日志结构挖掘：
是指通过对Web日志站点中超链接结构进行分析、变形和归纳，并对Web日志页面进行分类，最终得到有用的结果。
常用的算法有PageRank算法和HITS算法等，挖掘的对象包括Web日志的结构、页面的结构以及Web日志文档自身的结构；
（3）Web日志使用挖掘：
通过分析Web日志服务器的日志文件，以发现用户访问页面的模式，如用户访问模式分析、个性化分析、分类和聚类。
方便为站点管理员提供各种利于Web日志站点改进的信息，并将访问记录数据传给数据关系表中来实现对关系表数据的挖掘。
2.1.2Web日志挖掘过程
2.1.2.1Web日志内容挖掘的基本过程
Web日志内容挖掘的基本过程包括文本分析、文本解释、文档分类、文档可视化，它目的在于挖掘出基于用户需求的Web日志文本和多媒体信息，并对Web日志数据进行多样查询，提取其中无结构的动态文本进行集成、建模，最终实现知识发现。
Web日志内容挖掘可以分为两类[10]：
资源查找方法和数据库方法。
2.1.2.2Web日志使用挖掘的基本过程
数据挖掘的流程可以分为明确问题、数据收集和数据预处理、数据挖掘以及结果解释和评估，如图2-2所示。
图2-2数据挖掘的主要过程
（1）明确问题
数据挖掘的首要工作是研究发现何种知识，即明确问题。
在此过程中，数据挖掘人员必须和领域专家密切协作，一方面明确实际工作对数据挖掘的要求；另一方面通过对各种学习算法的对比进而确定可用的学习算法。
比如，数据分析员面对客户的流失问题，需要利用数据分析找出原因，并且找出解决问题的办法。
（2）数据收集和预处理
数据收集和预处理阶段一般要完成三项工作：
数据选取、数据预处理和数据变换。
数据选取就是确定操作对象，即目标数据，一般是从原始数据库中抽取的组数据。
数据预处理一般包括消除噪音、推导计算缺失值数据、消除重复记录、完成数据类型转换（如把连续值数据转换为离散型的数据，以便用于符号归纳，或是把离散型的转换为连续值型的，以便用于神经网络）等内容。
当数据挖掘的对象是数据仓库时，一般来说，数据预处理已经在生成数据仓库时完成了。
数据变换的主要目的是消减数据维数，即从初始特征中找出真正有用的特征，以减少数据挖掘时要考虑的特征或变量个数。
在进行数据挖掘技术的分析之前，我们还有许多准备工作要完成，通常有80%的时间和精力花费在数据预处理阶段。
数据挖掘通常有以下三种访问数据的途径：
1）从数据仓库中访问数据。
2）从关系数据库中访问数据。
3）从简单文件或电子表格中访问数据。
（3）数据挖掘
在将数据提交给数据挖掘工具前，我们要根据具体情况考虑下列问题：
1）学习应该是有监督的还是有无监督的；
2）在组合的数据中，哪些实例将用于建立模型，哪些实例将用于检验模型；
3）从可用的属性清单中选择哪些属性；
4）数据挖掘工具需要使用者制定单个或多个学习参数，什么样的参数设置可以最好的表示数据，从而用于建立模型。
根据所需解决问题的类型，确定数据挖据的任务，例如分类、聚类、关联规则发现或序列模式发现等。
确定了挖掘任务后，就要决定使用什么样的算法。
选择算法时要考虑两个因素：
一是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求，例如有的用户可能希望获取容易理解的描述型知识（采用规则表示的挖掘方法显然要好于神经网络之类的方法），有的用户则只是希望获取预测准确度尽可能高的预测型知识，而并不在意获取的知识是否易于理解。
（4）结果解释和评估
数据挖掘质量的好坏有两个影响要素：
一是所采用数据挖掘技术的有效性；二是用于挖掘的数据的质量和数量（数据量的大小）。
若选择了错误的数据或不恰当的属性，或对数据进行了不适当的转换，则挖掘不出好的结果。
对于数据挖掘出来的模式，要进行评估，删除冗余或无关的模式。
如果模式不满足要求，需要重复先前的过程，例如重新选取数据、采用新的数据变换方法、设定新的参数值改变算法等，甚至重新开始。
数据挖掘过程是一个不断反馈的过程。
另外，要对发现的模式进行可视化，把结果转换为容易理解的表示形式，以使得发现的知识更易于理解，例如，把分类决策树转换为“if…else…”规则。
Web日志使用挖掘是对网络日志进行挖掘，从用户访问Web日志时留下的访问记录中挖掘出潜在的、有用信息的过程。
其目的在于要发现用户留下的浏览模式和有用信息，这有利于开发Web日志的最大经济潜力，按照其分类规则，将Web日志使用挖掘分为数据预处理、模式识别和模式分析三个阶段，如图2.3所示：
Web站点文件
日志文件
用户会话文件
挖掘和模式
感兴趣的规则和模式
预处理
挖掘
模式分析
图2.3Web日志使用挖掘过程
（1）数据预处理
数据预处理阶段是把从Web日志日志文件数据中获得的使用信息、内容信息和结构信息转换成数据抽象，并将符合用户模式实现的数据从Web日志日志文件数据源中发掘出来，对该类型的用户会话（事务数据库）应用挖掘算法，最终得到潜在的知识和有价值的模式的过程。
数据预处理主要对日志文件进行数据收集、抽取、清洗、用户会话识别、事务模式分析等处理[11]。
（2）模式识别
识别的困难是由本地缓存和代理服务器造成的，当完成对用户事务的数据清理之后，开始执行模式访问阶段，目的在于使用Web日志挖掘技术发掘隐藏在数据背后的模式和规律，常用技术有：
统计分析、关联规则发掘、生成序列模式、聚类和分类、依赖关系的建模。
（3）模式分析
由于挖掘出来的模式复杂且数量较大，需过滤掉在挖掘阶段得到的那些没有用的规则或模式，把有用的规则和模式转换为知识，这就要通过一些工具来辅助用户的理解。
因此，近年来一些分析技术和工具的开发成为了Web日志使用挖掘研究的一个新热点。
2.1.3Web日志挖掘技术
2.1.3.1聚类
（1）基于模糊聚类算法的Web日志页面聚类
模糊集理论是Zadeh于1965年提出的，其定义如下：
设为论域，若集合R是其上的一个模糊集，则有
。
是模糊集R的隶属函数，为的隶属度。
在两个模糊集A与B上的运算有：
应用模糊算法进行Web日志页面聚类时，主要就是构造页面间的模糊相似矩阵。
定义Web日志访问用户集合，某一站点所有URL集合中可用用户访问情况表示为：
，其中，，n表示用户数量。
此时可建立页面间的模糊相似矩阵，矩阵中的元素值为：
，因该矩阵为对称矩阵，所以在计算相似度时只取一半数据，以给定的阈值构造相似类。
由于模糊矩阵不满足传递性，故只能得到含有公共元素的相似类而非等价类。
具体而言：
对于每一个,根据给定的阈值构造相似类会具有相同的元素。
如，；即。
此时将具有公共元素的相似类归并得到对应的等价类即为Web日志页面聚类的结果。
将用户Ci用浏览子图的URL序列表示为：
。
建立客户相似矩阵：
按页面聚类相同方法即可进行用户聚类。
。
2.1.3.2分类
1.基于页面文本与超文本结构信息的Web日志页面综合分类
因为基于Web日志页面文本和超文本结构信息的Web日志页面分类方法各有其特色，所以可将两者相结合提高分类结果。
如文献提出的二者取其最大值的方法，但该方法效果不是太明显。
而范炎等提出的利用贝叶斯方法将基于页面文本和超文本结构信息的分类视为两个相互独立的因素结合起来进行综合分类，即：
考虑到超文本结构分类中利用的单词远远少于页面文本分类，需要对不同方法分类结果加以预处理。
其中n是D中出现的不同单词数，即根据n值不同分别为不同的分类结果赋予不同的权重。
实验表明在基于贝叶斯方法的分类中，综合分类的结果好于文本分类和超文本结构分类单独分类时5%以上，就正确率而言综合分类好于前者6.75%，较后者提高5.79%。
2.基于页面文本的分类方法
（1）基于贝叶斯方法的页面分类。
在页面分类的诸多算法中贝叶斯分类方法的前提是：
文本特征之间是相互独立的。
贝叶斯方法与阈值大小来对文本数据进行划分：
其中指C类文档第i个特征，是从C类文本中得到特征词的概率，n值d中词的个数，m是系统词典的大小，若所得的阈值大于预先设定得值，则认为文本d属于C类，否则不是。
从概率大小来研究，贝叶斯分类方法可描述为：
设文档d的文档向量的分量为相应的特征词在该文档中出现的频度，则d属于C类文档的概率公式为：
（2.7）是在C类文档中出现的条件概率的拉普拉斯概率估计，是C类文档中特征词出现的频率，是d类文档中特征词出现的频度，是文档中所包含的不同特征的总数目。
（2）基于文档相似性的文档分类。
基于文档相似性的文档分类方法并无贝叶斯方法所需的前提假设。
使用文档表示矩阵间的夹角余弦值来表示它们之间的相似程度（2.6）：
2.1.4Web日志挖掘算法的关键问题
（1）Page-Rank算法
Page-Rank算法是Web日志超链接结构分析中最成功的代表之一，是评价网页权威性的一种重要工具。
搜索引擎Google就是利用该算法和anthortext标记、词频统计等因素相结合的方法来检索出的大量结果进行相关度排序，将最权威的网页尽量排在前面。
Page-Rank的基本思想：
设页面i的链入集合为{T1，T2,…，Tn}，即{T1，…，Tn}中的每一个页面都链接到页面i，C（i）为页面i的链出页面数，则页面i的等级值PR（i）可以通过以下两步计算得出：
（1）以概率e随机取Web日志上任一页面。
（2）以概率1-e随机取当前页面任一链出页面。
PR（i）=1-e+e*（PR（T1）/C（T1）+…+PR（Tn）/C（Tn））（2.7）
存在问题：
PageRank是对Web日志整体分析，通过模拟在Web日志上的随机游动对每一个网页计算其PageRank值。
因此该算法是独立于用户查询的，可以对用户要求产生快速的响应。
HITS算法是对Web日志的局部分析，是根据特定的查询产生不同的根集，然后计算网页的anthority值和Hub值，该算法是依赖于用户查询的，实时性差。
（2）HITS算法
1999年Kleinberg提出了HITS（HypertextInducedTopicSearch）算法。
HITS算法的内容如下：
将查询q提交给普通的基于相似度的搜索引擎，搜索引擎返回很多页面，从中取前n个页面作为根集（Rootset），用s表示。
通过向s中加
升级会员 