WEB日志挖掘技术的研究及应用

引言随着Web日志技术的急剧增长和快速普及,以及在电子商务和信息共享等方面的广泛应用，用户可以用很低的成本从网络上获得信息，Internet已成为最丰富的信息来源地，为了更好地对这些大量、无序的网页信息进行排序和检索，需要提升搜索引擎对网络信息的处理和组织能力，因此在这样的形势下，产生了Web日志挖掘(Web日志Mining)[1]技术，目的在于从Web日志的组织结构和链接关系中发掘出有用的模式和规律，该技术无疑成为数据挖掘中的热点，包括自然规则计算方法、神经网络、统计学、机器学习为主等人工智能相关技术。随着Internet/WWW的全球互通互连，从中取得的数据量难以计算，所以当处理这些数据并且从Web日志的服务中抽取信息时需要采用Web日志挖掘技术。Web日志挖掘需要从非结构化、半结构化或动态易混淆的数据中,抽取潜在的、易用的信息和模式的过程。根据Web日志数据类别的不同，可以将Web日志挖掘分为以下三类：Web日志内容挖掘、结构挖掘和使用挖掘。这三类挖掘分别作用于网页信息站点中的内容、结构和使用信息，并且已经在发现用户访问模式、反竞争情报活动、建立数据仓库等很多方面得到了应用。课题背景及研究意义随着万维网的迅速发展以及良好的发展趋势，尤其是电子商务的蓬勃发展为网络应用提供了强大的支撑。然而处理Web日志上海量的数据量，需要一种能高效快捷地从Web日志页面中获取信息的工具，由此搜索引擎产生了。现有的搜索引擎技术在很大程度上方便了人们对信息的检索，不过仍然存在一些不足之处，比如搜索精度不高、覆盖率有限等问题，无法更好地发现Web日志上潜在、隐藏的知识。将传统的数据挖掘同Web日志相融合，从而发展出了Web日志挖掘，该技术就传统的数据挖掘来看存在较多优势。传统数据挖掘技术只是对数据结构中结构化的数据进行挖掘，通过数据间的存储结构不同来发现知识，而Web日志挖掘是针对半结构化、杂乱、动态的数据进行挖掘，由于Web日志页面内容的复杂程度远超过普通文本的样式结果，所以导致了Web日志挖掘技术无法直接传承传统的数据库挖掘模型和技术。这就让挖掘的前提需要将传统数据挖掘技术与Web日志挖掘相结合，融合各自的优点，使整个数据挖掘系统同数据库能更紧密的结合在一起。由于要对数据进行组织和整合，这就需要一个完整的Web日志挖掘体系，才能分析并得出自己需要的信息。因此进行挖掘之前需要找到相关的Web日志文档。各Web日志信息之间有着密切的关系，从中找到正确的数据结构特点，利用自动化搜索的方法实现对Web日志上信息结构排序和内容的抽取，避免了各算法之间使用的重复性。蚁群算法是一种模拟进化的算法，它是借鉴蚂蚁在寻找食物过程中会自动搜寻最短路径而衍生出来的。该算法具有优良的分布式计算、正反馈性等特点，特别是在解决组合最优的问题上已经吸引了很多中外学者的关注。它也是继遗传算法、人工神经网络算法后又一个得到大家认可的研究性课题。研究现状及分析Web日志挖掘无论在国内还是国外都是通过挖掘服务器存储的Web日志，进而发现用户访问Web站点的访问模式。根据对Web日志数据源处理方法的不同，Web日志挖掘可以分为以下两类：第一类是将Web日志记录中的数据进行转换，然后传递进传统的关系表中，再用常规的算法对关系表中的数据进行挖掘。第二类是在对Web日志记录的数据进行挖掘之前对数据先进行数据预处理操作。国外对Web日志挖掘的研究基本上可以从1996年算起，比较突出的有：1996年学者M.S.Chen、H.Mannila、T.Yan提出了可以将数据挖掘方法用于Web研究领域。Mannila和Chen在研究过程中都假设去掉了图形文件、声音文件以后的Web服务器日志如实地反映了用户在网站中访问的情况。Mannila[2]把用户访问页面当作事件，从网站访问日志中试着寻找用户访问网站的周期。ChenREF_Ref435648169\r[3]提出了最大向前参引路径，并提出用这种方法把用户的Session分解成为一个个访问事务，然后就可以在事务基础上，挖掘用户访问的模式。T.Yan研究了如何动态地根据将用户进行分类，并根据同类用户访问页面的情况提供推荐页面。2021年，PerKowitz[4]等人在人机界面研究领域提出了AdaPtiveWebSite的概念，主要研究的是如何以历史访问为依据，使服务器提供的页面可以自动或者半自动化地调整。2021年Han把Web服务器访问日志集成到数据立方体结构(Datacubestructure)中，这样就可以对访问日志用传统的在线数据分析处理过程(oLAP)来处理日志数据了REF_Ref435648229\r[5]。国内互联网是从2021年开始迅速蓬勃的发展起来的。直到2021年，国内互联网用户达到一定数量以后，国内学者才开始关注Web数据挖掘，相比国外起步较晚。国内的学者在基于Web日志挖掘的个性化服务方面主要侧重于理论研究，比较突出的有：沈钧毅[6]等人提出以Web站点的URL为行，以UserID为列，建立URLes-UserID关联矩阵，元素值为用户的访问次数。然后，对列向量进行相似性分析得到相关Web页面；对相关页面进行进一步处理，便可以发现频繁访问路径。王红侠[7]等人采用基于事务的方法,研究Web日志挖掘预处理及用户访问序列模式挖掘方法，提出了一种基于BitlnaP序列模式进行用户浏览模式识别的Web日志挖掘方法。吴俊杰[8]等人采用Web站点的访问日志进行事务识别后，根据群体用户对Web站点的访问顺序进行路径聚类，最终的聚类结果反映出全体用户的访问兴趣。吴跃进认为，能够成为Web用户聚类算法评价因素的参数有且仅有三个，分别是点击次数、访问时间和访问路径；并在此基础上利用Kruskal算法衍生出了K-Bacer算法，根据访问频繁路径对用户进行聚类REF_Ref404608443\r[9]。吴跃进将所有用户的访问序列生成无向图，通过K-Bacer算法找出其中的频繁路径。K-Bacer算法是利用Kruskal算法的思想去产生最小生成树，溯其根源是贪心算法。算法的时间复杂度依赖于排序算法，同时对所有用户生成同一个无向图，随着用户量的增加，其可维护性和可扩展性大大降低。(1)Web日志挖掘聚类和分类技术聚类是从Web日志的访问数据中分析并整合出来具有相似特征事务的技术。Web日志使用挖掘中分为：页面聚类和使用聚类。页面聚类是通过搜索引擎在Web日志上找到具有相关内容的页面组，这更方便于用户在上网时能更容易地获得想要的信息。使用聚类就是将具有相似浏览模式的用户分为一组，这样形成了若干组，并对其量化，从中得到对用户有用的规则，当前该技术常应用于电子商务和一些个性化服务上。这两种聚类方法就是通过搜索引擎分析用户查询或访问网页信息时产生的历史记录所形成的HTML，来向用户提供超链接。分类是对新添加的数据进行分类并将一个对象分到事先定义好的类中，根据用户群的特征来挖掘出用户群的访问特征。在Web日志挖掘中，分类可以通过访问用户信息而得到的一些用户特征，这需要抽取并选择出最好地描述这组特定用户的特征，并根据这些特征对用户进行分类。常使用监督归纳学习算法来进行分类，如决策树、K-邻近分类法和支持向量机、机器学习法、贝叶斯分类方法等。(2)蚁群算法蚁群算法，现在被称为蚁群优化(ACO,AntColonyOptimization)是一种用来在图中寻找优化路径的机率型算法，它源于社会昆虫的群体活动所表现出来令人惊讶的行为，也这对日后研究蚁群行为提供全新的领域。ACO技术是一种基于群体智能的算法，它源于自然解决问题的思想，并在求解组合优化类问题上有明显的优越性。MarcoDorigo在1991年他的论文中首先提出了蚂蚁系统(AS),通过正反馈、分布式协作来寻找最优路径。并且常用于解决二次指派、多维背包、Job-shop调度等问题上。AS优化算法采用了分布式计算方法，具有多代理性和较强的鲁棒性等特点，且该算法已被大量应用于机器人协作问题求解、电力、通信、数据分析等领域。蚁群算法是学者受到蚂蚁觅食的启发而发现的，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁群体协作功能是通过遗留在来往路径上的信息素(Pheromone)来进行信息通讯并形成正反馈。假设蚂蚁走两条不同的路径来寻找食物，刚开始的时候走两条路的蚂蚁一样多，并且在搜索过程中释放出一定量的信息素，当蚂蚁沿着一条路到达终点后返回，短路径的蚂蚁来回一次时间就短且重复频率快，因而在同一时间内走过该路径的蚂蚁数目就多，洒下的信息素也就多，自然就有更多的蚂蚁会吸引过来，这样慢慢当蚂蚁数量不断增加时（同样信息素浓度也增加），最短的路径就近似被发现了。蚂蚁系统具有搜索最优的能力，得利于其同分布式计算和正反馈机制相结合的特点，使其具有较强的并行性和鲁棒性，但也同样存在一些缺陷，如搜索停滞以及搜索结果局部最优等问题。针对该系统存在的不足，很多中外学者提出了许多改进的蚁群算法，这些优化算法在解决局部搜索最优问题以及搜索停滞问题上有很大的提升。在当前研究形势下，蚁群算法已经成为中外学者广泛关注的热点问题。论文组织结构论文中较系统地分析和论述了Web日志挖掘中的各项技术。在此理论基础上，引入了改进的蚁群算法，并将其成功应用于Web日志挖掘的聚类和分类上。论文的整体构架如下：第一章绪论介绍了本课题的研究背景，主要内容和论文的组织结构第二章基于蚁群算法的Web日志挖掘理论介绍了Web日志挖掘理论，在论述了Web日志挖掘过程的基础上，详细地分析了Web日志挖掘中聚类和分类技术。然后分析了蚁群算法及几种改进的蚁群算法的思想。最后，对现有算法应用于Web日志挖掘技术上存在的问题做了详细地论述。第三章Web日志挖掘的预处理技术对Web日志挖掘中的关键技术，即Web日志挖掘预处理技术进行了全面的分析和总结。第四章基本蚁群算法及其改进对蚁群算法基本原理以传统日志挖掘算法原理进行了分析，并对基本蚁群算法进行了改进，通过仿真来说明基本蚁群算法的原理。第五章Web日志数据挖掘系统的实现以中名老中医临床经验、学术思想传承研究中的Web日志数据为例，基于改进的蚁群算法设计了一套Web日志数据挖掘系统，并对系统进行了评价和分析，为改善中医系统网站提出了优化建议。第六章总结与展望总结了本文的研究工作，提出进一步研究的方向。基于蚁群算法的Web日志挖掘概念Web日志挖掘随着信息技术的普及和应用，各个领域产生了大量的数据，这些数据被获取、存储下来，其中蕴含着丰富的信息。人们持续不断地探索处理这些数据的方法，以期最大程度地从中挖掘有用的信息，面对如潮水般不断增加的数据，人们不再满足于数据的查询和统计分析，而是期望从数据中提取信息或者知识为决策服务。数据挖掘技术突破了数据分析技术的种种局限，它结合统计学、数据库、机器学习等技术解决从数据中发现新的信息，辅助决策这一难题，是正在飞速发展的前沿学科。一些大型企业对数据挖掘产品和工具的使用都超过20年，并已产生了期望的效应。此外，数据挖掘产品和工具在金融、商业、电信、医学等多个领域也得到广泛推广应用。在数据库技术飞速发展的同时，人工智能领域的一个分支机器学习的研究也取得了很大的进展。自20世纪50年代开始机器学习的研究以来，在不同时期的研究途径和研究目的也不尽相同。一般大致可以分为三个阶段，其研究内容则分别为：神经模型和决策理论、概念符号获取及知识加强和论域专用学习。根据人类学习的不同模式人们提出了很多机器学习方法，如：实例学习、观察和发现学习、神经网络和遗传算法等。其中某些常用且较成熟的算法已经被人们用于实际的应用系统及智能计算机的设计和实现中。正是由于数据库技术和机器学习技术的发展，也是为了满足人们实际工作的需要，数据挖掘(DataMining)技术逐渐发展了起来。Web日志挖掘是一项综合技术，是数据挖掘在Web日志上的应用，涉及有信息学、数据挖掘、机器语言学、Web日志技术等多个领域。它是利用数据挖掘技术从Web日志相关的行为和资源中挖掘出新颖的、有效的、潜在有用、用户易理解的模式和信息的过程。Web日志数据挖掘的基本原理过程如图2.1所示。网站结构、内容网站结构、内容目标数据集经预处理的数据模式、规则、统计结果有趣的模式预处理模式发现模式分析图2.1Web日志数据挖掘原理图Web日志挖掘分类及架构模型根据挖掘的对象不同，我们将其分类三类：Web日志内容挖掘、Web日志结构挖掘和Web日志使用挖掘。(1)Web日志内容挖掘：又可分为Web日志页面挖掘和查询结果归纳；内容挖掘主要是指从Web日志文档的内容或其描述中提取知识以及对搜索中发现的有用信息进行分析的过程。(2)Web日志结构挖掘：是指通过对Web日志站点中超链接结构进行分析、变形和归纳，并对Web日志页面进行分类，最终得到有用的结果。常用的算法有PageRank算法和HITS算法等，挖掘的对象包括Web日志的结构、页面的结构以及Web日志文档自身的结构；(3)Web日志使用挖掘：通过分析Web日志服务器的日志文件，以发现用户访问页面的模式，如用户访问模式分析、个性化分析、分类和聚类。方便为站点管理员提供各种利于Web日志站点改进的信息，并将访问记录数据传给数据关系表中来实现对关系表数据的挖掘。Web日志挖掘过程Web日志内容挖掘的基本过程Web日志内容挖掘的基本过程包括文本分析、文本解释、文档分类、文档可视化，它目的在于挖掘出基于用户需求的Web日志文本和多媒体信息，并对Web日志数据进行多样查询，提取其中无结构的动态文本进行集成、建模，最终实现知识发现。Web日志内容挖掘可以分为两类[10]：资源查找方法和数据库方法。Web日志使用挖掘的基本过程数据挖掘的流程可以分为明确问题、数据收集和数据预处理、数据挖掘以及结果解释和评估，如图2-2所示。图2-2数据挖掘的主要过程明确问题数据挖掘的首要工作是研究发现何种知识，即明确问题。在此过程中，数据挖掘人员必须和领域专家密切协作，一方面明确实际工作对数据挖掘的要求；另一方面通过对各种学习算法的对比进而确定可用的学习算法。比如，数据分析员面对客户的流失问题，需要利用数据分析找出原因，并且找出解决问题的办法。数据收集和预处理数据收集和预处理阶段一般要完成三项工作：数据选取、数据预处理和数据变换。数据选取就是确定操作对象，即目标数据，一般是从原始数据库中抽取的组数据。数据预处理一般包括消除噪音、推导计算缺失值数据、消除重复记录、完成数据类型转换（如把连续值数据转换为离散型的数据，以便用于符号归纳，或是把离散型的转换为连续值型的，以便用于神经网络）等内容。当数据挖掘的对象是数据仓库时，一般来说，数据预处理已经在生成数据仓库时完成了。数据变换的主要目的是消减数据维数，即从初始特征中找出真正有用的特征，以减少数据挖掘时要考虑的特征或变量个数。在进行数据挖掘技术的分析之前，我们还有许多准备工作要完成，通常有80%的时间和精力花费在数据预处理阶段。数据挖掘通常有以下三种访问数据的途径：从数据仓库中访问数据。从关系数据库中访问数据。从简单文件或电子表格中访问数据。数据挖掘在将数据提交给数据挖掘工具前，我们要根据具体情况考虑下列问题：学习应该是有监督的还是有无监督的；在组合的数据中，哪些实例将用于建立模型，哪些实例将用于检验模型；从可用的属性清单中选择哪些属性；数据挖掘工具需要使用者制定单个或多个学习参数，什么样的参数设置可以最好的表示数据，从而用于建立模型。根据所需解决问题的类型，确定数据挖据的任务，例如分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样的算法。选择算法时要考虑两个因素：一是不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求，例如有的用户可能希望获取容易理解的描述型知识（采用规则表示的挖掘方法显然要好于神经网络之类的方法），有的用户则只是希望获取预测准确度尽可能高的预测型知识，而并不在意获取的知识是否易于理解。结果解释和评估数据挖掘质量的好坏有两个影响要素：一是所采用数据挖掘技术的有效性；二是用于挖掘的数据的质量和数量（数据量的大小）。若选择了错误的数据或不恰当的属性，或对数据进行了不适当的转换，则挖掘不出好的结果。对于数据挖掘出来的模式，要进行评估，删除冗余或无关的模式。如果模式不满足要求，需要重复先前的过程，例如重新选取数据、采用新的数据变换方法、设定新的参数值改变算法等，甚至重新开始。数据挖掘过程是一个不断反馈的过程。另外，要对发现的模式进行可视化，把结果转换为容易理解的表示形式，以使得发现的知识更易于理解，例如，把分类决策树转换为“if…else…”规则。Web日志使用挖掘是对网络日志进行挖掘，从用户访问Web日志时留下的访问记录中挖掘出潜在的、有用信息的过程。其目的在于要发现用户留下的浏览模式和有用信息，这有利于开发Web日志的最大经济潜力，按照其分类规则，将Web日志使用挖掘分为数据预处理、模式识别和模式分析三个阶段，如图2.3所示：WebWeb站点文件日志文件用户会话文件挖掘和模式感兴趣的规则和模式预处理挖掘模式分析图2.3Web日志使用挖掘过程(1)数据预处理数据预处理阶段是把从Web日志日志文件数据中获得的使用信息、内容信息和结构信息转换成数据抽象，并将符合用户模式实现的数据从Web日志日志文件数据源中发掘出来，对该类型的用户会话（事务数据库）应用挖掘算法，最终得到潜在的知识和有价值的模式的过程。数据预处理主要对日志文件进行数据收集、抽取、清洗、用户会话识别、事务模式分析等处理[11]。(2)模式识别识别的困难是由本地缓存和代理服务器造成的，当完成对用户事务的数据清理之后，开始执行模式访问阶段，目的在于使用Web日志挖掘技术发掘隐藏在数据背后的模式和规律，常用技术有：统计分析、关联规则发掘、生成序列模式、聚类和分类、依赖关系的建模。(3)模式分析由于挖掘出来的模式复杂且数量较大，需过滤掉在挖掘阶段得到的那些没有用的规则或模式，把有用的规则和模式转换为知识，这就要通过一些工具来辅助用户的理解。因此，近年来一些分析技术和工具的开发成为了Web日志使用挖掘研究的一个新热点。Web日志挖掘技术聚类(1)基于模糊聚类算法的Web日志页面聚类模糊集理论是Zadeh于1965年提出的，其定义如下：设为论域，若集合R是其上的一个模糊集，则有。是模糊集R的隶属函数，为的隶属度。在两个模糊集A与B上的运算有：应用模糊算法进行Web日志页面聚类时，主要就是构造页面间的模糊相似矩阵。定义Web日志访问用户集合，某一站点所有URL集合中可用用户访问情况表示为：，其中，，n表示用户数量。此时可建立页面间的模糊相似矩阵，矩阵中的元素值为：，因该矩阵为对称矩阵，所以在计算相似度时只取一半数据，以给定的阈值构造相似类。由于模糊矩阵不满足传递性，故只能得到含有公共元素的相似类而非等价类。具体而言：对于每一个,根据给定的阈值构造相似类会具有相同的元素。如，；即。此时将具有公共元素的相似类归并得到对应的等价类即为Web日志页面聚类的结果。将用户Ci用浏览子图的URL序列表示为：。建立客户相似矩阵：按页面聚类相同方法即可进行用户聚类。。分类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)：Web日志挖掘算法的关键问题(1)Rank算法Rank算法是Web日志超链接结构分析中最成功的代表之一，是评价网页权威性的一种重要工具。搜索引擎Google就是利用该算法和anthortext标记、词频统计等因素相结合的方法来检索出的大量结果进行相关度排序，将最权威的网页尽量排在前面。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算法2021年Kleinberg提出了HITS（HypertextInducedTopicSearch）算法。HITS算法的内容如下：将查询q提交给普通的基于相似度的搜索引擎，搜索引擎返回很多页面，从中取前n个页面作为根集(Rootset)，用s表示。通过向s中加入被s引用的页面和引用s的页面将s扩展成一个更大的集合T，作为基本集(Baseset)。首先，为基本集中的每一个页面赋予一个非负的权威权重ap和非负的Hub权重hp，并将所有的a和h值初始为同一个常数。Hub与权威的权重可按如下公式进行迭代计算：存在问题：HITS算法存在“主题漂移”的现象，如用户在查询“量子物理学”时，由于算法中需要对初次检索结果的根集扩充成基集，最终的检索结果中会包含大量的有关“物理学”的站点。因此HITS适合与宽主题的查询，而PageRank则较好地克服了“主题漂移”的现象。蚁群算法蚁群算法是一种模拟蚂蚁群体智能行为在图中寻找优化路径的仿生类优化算法,它由MarcoDorigo在92年提出，其思想来源于蚂蚁在寻找食物过程中发现路径的行为,当一只蚂蚁找到食物后，会在其走过的路上释放一种挥发性分泌物Pheromone（信息素，信息素浓度的大小表征路径的远近），蚂蚁在搜寻过程中能够感知信息素的存在和强度，并吸引其他蚂蚁过来，通过这种方式形成了信息素轨迹。蚁群算法分析为了便于理解，通常引入蚁群算法求解平面上某个城市的TSP问题来说明蚁群算法的模型。由于TSP是典型的组合优化难题，常常用来验证某一算法的有效性。1.TSP问题的描述给定n个城市的集合{1,2,…,n}及城市之间环游的花费Cij(1in,1jn,ij)。TSP问题是要找到一条经过每个城市一次且回到起点的最小花费的环路。若将每个顶点看成是图上的节点，花费Cij为连接顶点Vi、Vj边上的权，则TSP问题就是在一个具有n个节点的完全图上找到一条花费最小的Hamilton回路。2.蚁群算法的描述假设将m只蚂蚁放入到给定的n个城市中，那么每一只蚂蚁每一步的行动将符合下列规律：根据路径上的信息素浓度，以相应的概率来选取下一个城市；不再选取自己本次循环已经经过的城市为下一个城市；当完成一步（从一个城市到达另一个城市）或者一个循环（完成对所有n个城市的访问）后，更新所有路径上的残留信息浓度。蚂蚁在选择下一个城市的依据主要是两点：(1)(t)t时刻连接城市i和j的路径上残留信息的浓度，即由算法本身提供的信息；(2)由城市i转移到城市j的启发信息，该启发信息是由要解决的问题给出的，由一定的算法实现。在TSP问题中一般取=1/Cij。那么，t时刻位于城市i的蚂蚁k选择城市j为目标城市的概率为：也即，蚂蚁选中某一个城市的可能性是问题本身所提供的启发信息与从蚂蚁目前所在城市到目标城市路径上残留信息量的函数。为了避免残留信息过多引起的残留信息淹没启发信息的问题，在每一只蚂蚁完成对所有n个城市的访问后（也即一个循环结束后），必须对残留信息进行更新处理，模仿人类记忆的特点，对旧的信息进行削弱。同时，必须将最新的蚂蚁访问路径的信息加入。这样得到 式中：残留信息的保留部分，1-表示在时段t到(t+1)内残留信息被削弱的部分，为了防止信息的无限累积，的取值范围必须在0到1之间； 第k个蚂蚁在时段t到(t+1)内，在i到j的路径上留下的残留信息浓度。 M.Dorigo介绍了的3种不同的实现方法，分别称为ant_cycle,ant_density,ant_quantity算法。对于前一种算法：式中：Q是一个常量，用来表示蚂蚁完成一次完整的路径搜索后，所释放的信息素总量：Lk表示蚂蚁k在本次循环中所选择路径的总花费，它等于第k个蚂蚁经过的各段路径上所需的花费Cij的总和。蚁群算法的关键问题(1)搜索时间较长计算的复杂度主要体现在构造模型的过程中，随着问题规模的增大，算法消耗的时间也随之增加，通过这些参数信息交换能够向着最优路径进化，但是当群体规模较大时，很难在短时间内找出一条较好的路径。通过正反馈机制，使得较优路径上的信息量逐渐增加，需要在很长的一段时间后，才能使较优路径上的信息量明显高于其他路径。目前这方面的研究开始逐步走向深入。(2)运行效率与全局收敛针对蚁群算法运行效率低下这一问题，曾先后提出了带精英策略的蚂蚁系统（ASelist）和基于优化排序的蚂蚁系统（ASrank）。虽然它们在运行效率方面取得一定的进展，但是同样也付出了容易收敛于局部最优解的代价。在它们之后，MMAS以及ACS针对上述问题进行了改进，扩展了蚁群的搜索空间，但是它们在效率方面同样也付出了代价。目前的研究是将注意力集中到将蚁群算法与其他智能仿生算法相结合。本章小结首先介绍了Web日志挖掘的理论知识，包括分类、架构模型等。详细地论述了Web日志挖掘技术中的聚类和分类技术以及指出现阶段存在的关键问题。然后，对蚁群算法进行分析，系统地提出了当前蚁群算法研究热点问题。Web日志挖掘的预处理技术聚类是将复杂的事物分门别类，并对陌生繁乱的事物进行归类总结，相同类别的事物采取类似的处理方法，这样就能大大提高事物的处理效率，通过自动聚类能够识别对象空间中不同密度空间的区域，从而发现全局分布模式，并结合蚁群算法的正反馈、鲁棒性、分布式计算等优点，对聚类模型进行设计。聚类模型分析聚类分析在Web日志挖掘中是一个很重要的技术。聚类分析可以增强对象集的可理解性，并发现对象集中数据间共同的结构和联系，保持其有效性。即按照一定的规律和需求，将一些特殊分散的对象按照其相似性进行分类，并使得对象点的集合分成若干类，且每个类中的对象点最大程度地相似，各个类之间的对象点最大程度地不同。在聚类分析过程中没有涉及关于分类方面的知识，只是依靠对象点间的相似度作为划分类的依据，因此聚类分析是一种观察式学习，是利用数学方法研究和处理所给定对象的分类，其多元的统计分析方法是统计模式识别中非监督模式识别的重要分支。为了描述对象样本间的距离，特引入特征变量类型和相似性度量这2个概念。(1)特征变量类型为了描述一个对象样本，我们通常会对对象进行特征抽象化，使用多个特征指标变量来给予每个对象一个特征向量。特征指标变量可以分为：间隔标度变量、二次变量、序数变量，处理不同类型的特征指标变量则采取不同的策略。对于间隔标度变量是使用连续的实数来表示的数量信息，一个样本点可以看作是多维空间中的一点，通过一些特殊的运算来求解各个样本在空间上的距离。对于二元变量，用两种状态（0或1）来表示样本属性，1表示变量出现，0表示变量不出现，该变量特征也可以用来分类变量尺度，标记多状态。对于序数变量，它类似于分类变量，不用于分类变量的是，其状态时无序关系的，而分类的状态是有序的。对于这两种特征变量我们不能定义合适的数学运算，需要通过特殊变换后才能进行对象相似度计算。(2)相似性度量为了更好地描述对象集中的单个样本，需要样本类型中的特征指标变量提供度量值，同样为了描述样本间的相似特性，也需要定义能合理地衡量样本间相似程度，从而合理地进行聚类的度量，以便把相似的样本归为一类，非相似的样本归为不同的类。常用刻画样本间的相似性函数有2种，分别是：相似系数函数、距离函数。相似系数函数是用来描述样本点特征性质之间的相似程度，当相似系数值越接近0时，说明两个对象样本越不相似，当相反相似系数值越接近1，则说明两个对象越相似，这才可以将它们归为一类。距离函数指的是对象样本间的距离，对于含有N个属性的样本对象来说，我们可以将每个样本点看作是N维空间中的一个点，然后使用某种距离来表示样本对象点之间的相似性，对象样本点越相似，则样本点之间的距离越小，可以将它们归为一类；对象样本点差异越大，则两者间的距离越大，就不能归为一类。聚类模型设计聚类首先要做的是对样本对象的特征抽取，它所处理的对象是样本数据集，由于实际应用中的样本数据对象一般都有多种特征，要具体选取哪种特征才可以正确地描述样本对象的本质和结构对于聚类分析来说至关重要。特征抽取的结果是输出一个矩阵，每一行对应的是一个样本对象，而每一列对应的是一个特征变量。特征的抽取是另一个重要步骤，对后续的分析和决策有直接的影响。如果抽取的特征变量只是样本对象中不重要的属性，对这些无关紧要的属性进行聚类分析出的结果肯定也达不到预期的效果，因为当使用错误的特征属性来解释对象时，容易扭曲样本对象，再对这样的样本对象进行的聚类分析，即便是用最好的聚类算法来对其处理，结果也是不正确的。总结蚁群算法和聚类分析的特点，引入了一种改进的蚁群算法(ImprovedAntColonyAlgorithm，IACA)。并将其运用到Web日志的用户聚类上，聚类模型如下：1.初始化设定设有M个模式样本、K个模式分类，N是表示为几个样本对象；初始状态将M个样本随机分配到N个聚类中心，K表示分类出K个等级，每个模式样本是一个D维向量，定义模式样本。设聚类中心为，则目标函数表示为：2.信息素更新计算蚂蚁的各自初始聚类中心（第k个蚂蚁将模式样本i分配到第j个聚类中心）和初始目标函数，初始化各蚂蚁的样本到各聚类中心的信息素浓度，信息素浓度更新公式为：其中是信息素增量,是信息素强度的持久性系数（算法中1-表示信息素挥发度）。初始化，蚂蚁将初始化，蚂蚁将M个样本随机分配到K个聚类中心计算蚂蚁的各自初始聚类中心和初始目标函数初始化各蚂蚁的样本到各聚类中心的信息素浓度M只蚂蚁到N个样本进行K个模式分类更新并调整信息素，计算出新的聚类中心，计算目标函数搜索次数h=h+1h>=L?选取，输出分类结果算法结束否否是是图3.1流程图3.聚类中心的计算方法对于聚类中心的计算方法，我们选择了K均值算法[54]来计算每个聚类中心。4.有关参数的选择由于算法参数的选择会对蚁群算法的性能产生较大的影响。从蚂蚁搜索最短路径的原理出发，我们定义了一些参数：种群数N、常数Q、绝对感觉阈值CST和差别感觉阈值AST以及信息素挥发度1-等等。蚂蚁数量N决定蚁群算法的循环次数呈线性变化。当蚂蚁数量过大时,搜索的全局性和稳定性有所提高，但是算法的收敛速度变慢。蚁群搜索过程中信息素挥发度1-的大小关系到蚁群算法运行过程中的收敛速度和全局搜索能力：当1-过小时，搜索过的路径被选择的概率降低，虽然算法全局搜索能力和随机性能有所提高，但是收敛速度却下降；当1-过大时，表示搜索过的路径被再次选择的概率增加，影响算法的全局搜索能力；所以对信息素挥发度的选择，需要平衡算法的收敛速度和全局搜索能力。另外，AST和CST的取值也很重要，取值不恰当容易使解陷入局部收敛，算法需要在稳定性和求解速度上取得平衡。Web日志预处理相关技术在对Web日志进行挖掘之前，有一个很重要的数据处理过程，称之为Web日志预处理，也就是对Web日志数据进行过滤、清洗以及重新组合的过程。我们都知道服务器端的Web日志中记录了用户访问网站的各种信息，但是这些信息中有些数据是自动产生，而有些信息可能并不是我们需要研究的，这些都属于无用的，所以我们应该对其进行数据预处理。而Web日志预处理技术主要包括有以下五个阶段：（1）数据清理；（2）用户识别；（3）会话识别； （4）路径补充；（5）事物识别。服务器产生的Web日志文件是Web日志挖掘中数据预处理所要研究的对象。在这些日志文件中存在许多对研究没有任何意义的数据，所以直接用这些文件将会导致研究出的结果有偏差或出错等问题。所以，Web日志数据预处理过程是Web日志挖掘的第一个阶段，也是非常重要的阶段。这个阶段会对Web服务器日志或者代理日志进行数据清洗、数据规范化和数据集成等操作，最终把原始的日志数据通过一系列操作，处理成便于进行挖掘算法的数据。不同的Web日志文件中记录的数据也会相应的有各自的数据特点，是不一样的，因为每个服务器设置的参数不一样，但是有一些基本的信息是无论任何服务器都应该有记录的。如表3-1所示。表3-1Web访问日志记录的主要信息属性日志的说明日期以及时间用户请求页面的日期以及具体的时间用户IP地址客户端主机的IP地址或者DNS入口用户名服务器IP地址客户端的用户名服务器的IP地址服务器端口服务器端口号方法用户请求数据的方法URL查询用户将要进行的查询协议状态返回http的状态的标识发送的字节数服务器发送数据的字节数接受的字节数客户端收到数据的字节数用户代理服务的提供者Web日志数据预处理的过程Web日志数据预处理主要任务是，把输入数据为Web服务器日志或其他的日志记录文件转化为可以进行挖掘的用户会话文件以及事务数据库，而处理数据的结果将直接影响Web日志挖掘质量的好坏。一般来说，Web日志数据的预处理过程由以下五个阶段构成，分别是数据清理、用户识别、会话识别、路径补充以及事物识别。如图3-2所示。接下来针对这五个阶段来详细的进行下介绍。图3-2Web日志数据预处理的过程数据清理Web服务器日志文件中有很多与研究没有任何意义的“脏数据”，数据清理这个操作就是把“脏数据”进行“清洗”的过程。首先把从服务器取出来的Web日志记录进行合并，然后将其存进对应的数据字段中，因为Web日志文件一般只有html文件才会跟用户会话相关，所以在这一过程中一般都要根据实际情况去掉日志中的图像文件以及其他不相关的文件。比如图像文件的后缀有gif，jpg，jpeg等等，除图像文件之外还有一些js、css、swf等文件根据具体情况也进行相应的删除。除此之外，以cgi为后缀的一些脚本文件也应该被剔除掉。清理流程如图3-3所示。开始开始N日志清理完成日志数据中是否有记录N日志清理完成日志数据中是否有记录从日志数据库中读取一条记录YY从日志数据库中读取一条记录YYN请求url的后缀是否为.gif、N请求url的后缀是否为.gif、.jpg等格式N从日志数据库中删除记录状态码是否以2开头状态码是否以2开头Y将该记录添加到表中将该记录添加到表中图3-3数据清理流程图纵向缩减（也称行缩减）为了让Web日志文件的数据能够更加可靠，更加适应挖掘的需要，对Web日志文件中无用信息进行删除是必需的一个过程。根据具体的挖掘研究，可以对Web日志文件的清洗任务进行以下三个方面纵向缩减：1）URL扩展名：在Web日志数据中，像一些以gif、jpg、css、cgi为后缀的文件通常被认为是与日志挖掘没有关联的，应该将这些文件剔除掉，因为只有html格式的文件说明与用户会话相关。当然，凡是也有例外，如果要研究的网站是图片网站，那想要对网站的流量进行分析的话，这些格式的文件就要根据具体情况进行相应保存了。2）动作：用户访问网站的方式通常有get和post两种，post动作一般是需要过滤掉的，因为post方式一般是用户提交表单数据时使用，而get动作是用户进行请求页面的，一般要保留。3）状态码：状态码表示用户请求页面的结果，主要分以下几种情况：第一种，以2开头状态码表示页面请求成功，比如200代表服务器成功返回页面，202代表服务器已经接受请求，但还没有处理，206代表服务器成功处理了get请求；第二种，以3开头的状态码表示重定向，比如301代表请求的页面已经永久移动到新位置，304代表自从上次请求后，请求的网页没有修改过；第三种：以4开头的状态码表示请求可能出错，比如400代表（错误提示）服务器不理解请求的语法，401代表（未授权）请求要求身份验证，403代表（禁止）服务器拒绝请求，404代表（未找到）服务器找不到请求的网页；第五种：以5开头的状态码表示服务器错误，比如500代表因服务器内部错误而无法完成请求，502表示网关错误。由此，在进行数据清洗过程中应该把以4和5开头的信息删除。横向缩减（也称列缩减）当使用数据挖掘的算法对数据进行挖掘的时候，很多web日志中的属性是非必需的，所以仅仅只考虑纵向缩减来减少日志文件是远远不够的。比如，对用户信息进行聚类分析时只需要使用用户的ip地址、用户请求访问的url、用户访问的时间、用户使用的代理等属性就可以；而分析web站点的流量时，只需要使用用户请求url用户访问时间等属性。这种缩减日志记录中属性的方法就是横向缩减，也叫列缩减。与纵向缩减不同，横向缩减不会缩减日志文件的行数，而只会减少属性列。用户识别用户就是指通过一个浏览器访问一个或几个服务器的个体。我们在实际中唯一确定一个用户是非常困难的，因为有防火墙、高速缓存、代理服务器等进行阻碍。辨别一个用户可以有用户IP和Cookie标识两种方法。Cookie是站点根据浏览器写入本地的唯一的一个标识，当用户再通过url请求服务器时，请求中就会加上这个标识，然后返回给服务器，这样就可以识别用户了。不过这种情况也有缺点，那就是当若干个用户使用同一个电脑的时候，一旦有用户删除Cookie，那么下一次登陆服务器就会被当做第一次登陆。当然也有可能因为隐私不会被写到Cookie中，所以，有的时候要把代理、服务器日志、参引页面等综合考虑才能确定一个用户。图3-4简单的Web站点因为本地代理服务器和高速缓存机制的存在，极有可能会使用户在网站上的浏览情况歪曲，这就可能会导致我们漏掉了重要的访问内容，从而不能比较精确地描述用户浏览网页的情况。因为各个网站都有后退键，这就导致一个访问记录只列出了一次，而实际是很有可能被多个用户参考了很多次。针对该问题目前主要有以下三种解决方法：关闭高速缓存、利用Cookie以及利用用户注册。但这三个方法都存在问题，首先，用户是可以随意删除Cookie的。其次，高速缓存是为了提高网站加载的速度，关闭高速缓存之后也是可以再次打开的。最后，用户的注册涉及到了个人隐私，而且是自发的，所以很多用户注册的信息是不真实的。高速缓存问题的解决方法可以采用站点拓扑学的知识或利用参考日志和时间信息来判断遗失的参考。表3-2列出了目前用于用户识别的几种方法。表3-2中的方法多多少少也有一些不足之处，目前在Web日志挖掘中，对如何准确识别用户而又不涉及用户的隐私的问题的研究已经成为热门的研究。本文只对用户识别作简单介绍，不进行深入的研究。表3-2用于用户识别的方法方法IP地址和代理嵌入会话ID用户注册软件代理Cookie描述假定每个IP地址和一个用户代理组合表示一个用户利用动态网页将ID插入每个链接用户显示的登录网站当程序调入浏览器后可以发回使用数据在用户端保存一个唯一的用户标识隐私程度低低中中中/高中优点可用性好，不需要另外的技术和信息简单可行，独立于IP地址可以精确的跟踪每一个注册用户可以跟踪重复访问可以精确跟踪用户访问一个站点的信息缺点不能保证用户的唯一性，一个IP多个用户代理的情况无法处理没有重复的访问概念，需要完全动态网页无法跟踪大量的非注册用户用户可以禁止该软件用户可以中止使用cookie，可用性不高会话识别一个会话就是指用户在一次访问过程中所访问的Web页面的序列。会话识别的目的是将每个用户的访问信息划分成若干个独立的会话进程，最简单的方法是采用超时估计的办法，即当对页面之间的请求时间间隔超出所给定值时，即可以认为用户已经开始了一次新的会话。JPitkow的实验证明：比较合理的时间长度应该是25.5分钟，通常使用30分钟作为一个用户点击流会话的时间长度。会话识别的流程图如图3-5所示。开始开始读出表中一个用户放的日志记录读出表中一个用户放的日志记录判断判断url是否超时NNYY在用户会话表里插入新的用户会话在用户会话表里插入新的用户会话Y判断是否有访问记录未处理Y判断是否有访问记录未处理NN结束结束图3-5会话识别流程图路径补充由于本地缓存和代理服务器缓存的存在，使得服务器的日志会遗漏一些重要的页面请求。路径补充的任务就是将这些遗漏的请求补充到用户会话当中，解决的方法类似于用户识别中采用的方法。如果当前请求的页面与用户上一次请求的页面之间没有超文本链接，那么用户很可能使用了浏览器上的“后退”按钮调用缓存在本机中的页面。检查引用日志确定当前请求来自哪一个页面，如果在用户的历史访问记录上有多个页面都包含当前请求页面的链接，则将请求时间最接近当前请求页面的页面作为当前请求的来源。若引用日志不完整，可以使用站点的拓扑结构代替。通过这种方法将遗漏的页面请求添加到用户的会话文件中。经过以上几个过程的数据预处理，就形成了事务数据库，这个数据库是下一阶段数据挖掘的基础。路径补充流程图如图3-6所示。读取一个用户的会话序列开始读取一个用户的会话序列开始判断当前页是否可从上一页直接访问判断当前页是否可从上一页直接访问YYNN将该页面加到用户会话列表中结合将该页面加到用户会话列表中结合inter结构将访问路径补充完整Y判断用户会话中有无未处理的会话序列Y判断用户会话中有无未处理的会话序列NN结束结束图3-6路径补充流程图事务识别用户会话是Web日志挖掘中唯一具有自然事务特征的元素，但对数据挖掘来说，还有些粗糙不够精确，需要把会话进一步分成具有一定语义的事务，这儿只是借用了“事务”的叫法，也称作情景识别（EpisodeIdentification）。常用的事务分割方法有：引用长度（ReferenceLength）、最大向前路径（MaximalForwardPath）、时间窗口（TimeWindow）等，事务识别（TransactionIdentification）的方法在资料上有详细的说明。事务识别的流程图如图3-7所示。Flag=1Flag=1判断当前访问页面是否是前一个页面的直接后继判断当前访问页面是否是前一个页面的直接后继NYNYYFlag=0？YFlag=0？Flag=0？NYNYFlag=0，开始新的事务将当前及第一页面加到新事务中，Flag=0，开始新的事务将当前及第一页面加到新事务中，flag=1将当前及第一页面加到新事务中所有页面是否已处理完？读出用户会话表的用户访问序列开始所有页面是否已处理完？读出用户会话表的用户访问序列开始NN结束结束图3-7事务识别流程图本章小结本章介绍数据挖掘的预处理的相关理论，然后详细阐述了Web日志挖掘前期工作——数据预处理的整个过程，主要包括数据清理、用户识别、会话识别、路径补充和事务识别五个部分。应用于Web日志挖掘的改进蚁群算法设计下面介绍基本蚁群算法及其典型的改进算法和对基本蚁群算法进行了改进及计算机仿真。蚁群算法在Web日志挖掘中的应用分析随着互联网用户的不断增加，Web服务器上保存大量的网络日志数据，网络日志数据中隐藏着用户浏览模式信息，Web日志挖掘帮助用户快速找到用户浏览服务器资源的兴趣路径序列。一个Web站点模型可通过一个二元节点图(N，E)进行描述，其中E表示Web页页之间的超链接集合，N表示Web页页的集合，具体如图4.1所示：图4.1简单Web站点模型从图4.1可知，当用户进行网站浏览时，事先不知道那一条路径达到用户感兴趣页面(节点)最优，可以通过Web日志挖掘技术找出一条用户达到目标的最优节点序列，即最短路径。因此通常情况下，用户浏览行为具有如下特点：(1)盲目性与从众性，例如新闻的点击排行等，一般都根据历史浏览人数较多路径进行浏览。(2)到达用户寻找目标的路径越短，那么被浏览效率越高，浏览的频率增加越快，不然，用户烦琐操作会失去该类用户。对上述用户浏览行为分析可知，其与自然界蚂蚁觅食十分相似。大量研究表明，蚂蚁可以通过相互协作和信息交流找到一条食物源和蚁巢之间的最短路径。蚂蚁觅食时，原本盲目行走的孤立蚂蚁可以通过以前蚂蚁在路径上留下信息素进行搜索，同时对该路径上信息素加强，形成一种正反馈机制，使该路径被蚂蚁选择概率越来越大，由于路径信息素不断的发挥，时间较长的路径保留的信息素相对较少，这样蚂蚁最终找到一条最优路径。蚂蚁群体的路径寻优机制如图4.2所示，在图4.2中，其中，CD为一障碍物，蚂蚁通过由B或E绕过障碍物进行觅食。图4.2蚂蚁群体的路径寻找机制比较图4.1和图4.2可知，Web日志挖掘与蚁群觅食本质极相似，因此采用蚁群算法对Web日志挖掘问题进行求解是可行的。传统日志数据挖掘算法本小节将介绍传统的web日志挖掘算法及蚁群算法。Apriori算法在对Web日志进行挖掘的各种算法中，比较传统的是Apriori频繁项集算法，这是一种挖掘关联规则的算法，在很多领域中都有应用，例如在网络安全问题中可以用来检测各项事件和攻击的关联，从而预测下一个攻击行为；在商业中可以对消费者的大数据进行分析，对消费者的购买行为进行统计并预测。从机制上说，Apriori是一种广度优先搜索算法，由频繁k-1项集产生候选频繁k项集，当候选频繁k项集的支持度超过闻值时，则选取为频繁k项集。Apriori算法则建立在频繁一项集开始，算法终止的条件是不能产生更多项数的频繁项集时。而在这个算法中，通过2个阶段来生成频繁项集：第一阶段是候选频繁项集的建立阶段，第二阶段是计算项集支持度阶段。在候选频繁项集产生阶段中，由已知的频繁k-1项集中获得候选频繁k项集。在计算支持度阶段中，通过遍历数据集对每个候选频繁项集进行支持度计数。对支持度大于闭值的候选频繁项集选为频繁k项集。频繁项集通过计算生成后，可以使用频繁项集生成关联规则，这些规则可以进一步在日常的应用中应用于各种预测分析，例如网络中反映的用户的习惯预测。此外，在对于处理较小的数据集时，Apriori算法拥有很好的表现，不过其缺点会在数据集中项数多时表现，即算法效率较低。造成这种短板的原因是Apriori算法中为了产生一个频繁k项集{x1,x2,……xk}，需要先生成2k-2个频繁的子集。当频繁k项集的项数k很大时，子集的数量变得很多，频繁项集树的节点数也将变多。因此，计算机将会反复的对数据集合进行遍历，从而生成频繁项集，而对频繁项集树进行保存也会占用大量缓存空间，影响整个算法效率。蚁群系统算法蚁群算法在Web日志挖掘中的应用也是非常广泛的，它本身有仿生学的机制，又包含了路径概率选择与信息的正负反馈，即如果一条路径被几乎全部的蚂蚁所选择行走，则该路径为最佳路径。这种思路在很多数据控制领域应用广泛。其具体机理为：假设用户对Web网页的游览记录如下：S={(n1，n4，n8)，(n1，n4)，(n1，n4，n7)，(n1，n3，n7)，(n1，n3，n6)，(n1，n3，n7)，(n1，n3，n6)，(n1，n2，n5，n3，n7)，(n1，n2，n5)，(n6，n7))根据图4.1可知，蚁群算法的Web日志管理模型如图4.3所示：图4.3蚁群系统在Web日志挖掘中的应用模型在对一个网页或者网站进行浏览时，用户对网页的阅读频率和阅读时长可以体现出对此网站的兴趣，当用户对内容有兴趣时，会表现在阅读时间增长，阅读页面增多，因此采用蚁群算法进行日志挖掘时，会考虑采用定义用户的浏览序列并建立一条路径，而将浏览序列作为支持度，成为整个算法的启发式信息，并对用户的浏览兴趣进行描述。一种改进的适用于Web日志挖掘的蚁群算如同前面所介绍，在初始阶段，每只蚂蚁分配到一个空的解集合，所有的信息素初始化为一个相同的值，随着迭代过程的进行，信息素值将依赖于产生的解的质量得以更新。下面结合一个具体问题来详细分析如何调整蚁群算法求解聚类问题，蚁群聚类算法采用的硬件/软件环境分别为：CPU2.4GHz内存256M硬盘容量80G安装的是MicrosoftwindowsXP（ServicePack2）操作系统开发平台MATLAB7.0。下面结合一个具体问题来详细分析如何调整蚁群算法求解聚类问题，数据集见表4-1。表4-1为包含10个样本的数据集，每个样本有4个属性，设置10只蚂蚁欲将样本划分为3类。表4-110个样本划分为3类的聚类问题的数据集序号12343.03.04.00.3下面本文介绍具体的迭代过程，为了便于描述，用t（本次取值1000）来表示迭代的次数。每只人工蚂蚁依赖于第t次迭代提供的信息来实现分类。表4-2中列出本次迭代中最好解S1继承的信息素矩阵。表4-2S1解的t次迭代后的信息素矩阵 序号12311.66440.680161.220721.64460.119691.664431.30270.011.664441.38150.011.664451.21521.66440.5011460.110021.66441.094971.66441.56421.283281.66440.010.7107191.14661.66440.11904101.66440.011.2349τ11=1.6644，τ12=0.68016，τ13=1.2207为第1个样本对应与每一个类的信息素值。这组数据表明，由于τ11的值较大，第1个样本将以较大的概率归于第1类。事实上，每只蚂蚁按照以前介绍过的随机加确定方法来选择第i个样本将所属的类。在此，结合聚类问题再次加以叙述。方法如下：(i)以预先定义好的几率q0(0<q0<1，q0=0.9)，选择与样本间具有最大信息素的类为样本要归属的类。(ii)以(1-q0)的几率根据转换概率随机选择样本要划分的类。由人工蚂蚁遍历所有的样本构建出的候选解的质量是由特定的聚类问题的目标函数值来决定的。下面表4-3为蚂蚁数目为10的蚁群聚类算法(排好了顺序)的结果：表4-3为蚂蚁数目为10的蚁群聚类算法(排好了顺序)的结果序号12345678910F113332211213.0041213332211213.0041313332211213.0041413332211213.0041513332211213.0041613332211213.0041713332211113.0275811332211213.0568933332211213.62261013131211213.9488本文还将实验的最优解结果使用Matlab实现了2维和3维图，使得结果显示更加直观明了，如图4-4和图4-5所示。图4-42维效果图4-53维效果本文还将实验的最优解结果的分类值使用Excel保存了，如图4-3。图4-6结果输出自动保存到Excel中为提高算法中蚂蚁找到的近似解的效率，很多改进的蚁群算法都加入了局部搜索，特别是当问题域的启发信息不易获得时，加入局部搜索可以帮助找到更好的解。目前，局部搜索对所有解都实行，也可以只对部分解实行，本文只对当前可行解实行局部搜索。在局部搜索前，把所有的解按照目标函数值进行升序排列。本文将对具有高的目标函数值的头两个解进行局部搜索操作。局部搜索操作有很多种，这里选择交换操作。方法如下：预先产生一个(0，1)间的随机数pls，以pls=0.01为例。对表4-3中具有最高目标函数值的解集S10进行交换。为解集中的每个样本产生随机0.56367，0.35746，0.77456，0.46634，0.00139，0.54636，0.25635，0.35646，0.46324，0.14663。只有第五个样本的随机值小于pls，所以这个样本要被分到其他类当中。选择类中心与这个样本的距离最短的类为第5个样本要去的类。第5个样本原来在第二个类中，那么就要在另两个类中选取，经过计算将第5个样本重新分到第三类中去。继而对解集S9也进行交换操作。对于通过交换而产生的新的解集要重新计算其目标函数值，与原解集的目标函数值比较，择优。执行过局部搜索之后，要对信息素值进行更新。信息素更新公式采用蚂蚁系统中的公式：其中，τij(t)及τij(t+1)为样本i与类j在t及t+1时间的信息素浓度。为蚂蚁k所找到的最小目标函数值。Q为一参数值。ρ为信息素蒸发参数，0<ρ<1。至此，一次迭代结束。改进后蚁群聚类算法流程改进的蚁群聚类算法的主要步骤叙述如下：步骤1：初始化，包括蚂蚁数目R、类的个数K、转换规则参数q0、局部搜索阈值等。步骤2：所有人工蚂蚁根据上一次的信息构建解集，计算各类中心。步骤3：在产生的解集找到要交换样本的Sk实施局部搜索操作。步骤4：更新信息素值。步骤5：如果没有达到迭代次数预定值并且没有稳定解，则转步骤2，否则输出最优的分类解集。算法基本流程如图4-7。图4-7蚁群算法流程图当然，迄今为止蚁群算法已经有了很多的变型或改进算法，但基于蚁群算法（ACA）寻找问题近似解的思想及实现优化过程的机制还是没有改变。由上图可见，蚁群算法区别于其他传统优化算法，因为它具有以下3个特点：(1)模拟了一种大自然真实存在的现象，并建立模型；(2)不可确定性；(3)总是表现出一种并行性，不是在系统中强行加入，而是算法本身隐含具有的。仿真实验对比分析在4.2小节中本文详细介绍了基本蚁群算法的原理等，在本小节中将通过计算机仿真来理解基本蚁群算法的原理，并将作出的路径图和最终结果自动保存到文本文档(.txt)与Excel(.xls)中。仿真环境与数据为了详细对比出两种不同算法（改进前与改进后）算法优劣，本文实验采用同一种实验数据：样例网站则名老中医系统的日志数据，实验数据中纪录数共8136条，经过对这些日志数据的预处理，可以获取到能够用于传统蚁群算法与增加局部搜索算法后的蚁群算法条件的数据。蚁群算法在实际问题的求解过程当中往往具有较高的效率，尽管在不同程度上取得了一定的效果，但是仍然存在着一些不足之处，主要表现在：1）如果一些参数α、β、ρ、m、Q设置不合理，那么就会导致迭代速度非常慢，并且结果误差较大；2）从蚁群算法本身来讲，其计算量非常大，相应的计算周期比较长；3）蚁群算法可以通过选取不同的路线来获得最优解，在具体循环次数的条件下，还可以根据不同的实际问题来对图像的内容进行优化处理，根据处理的结果来找到相应的最优解，这样就能够保证计算效率不会受到影响。从目前来看，蚁群算法的参数设置以及属性方面的研究仍然存在着较多的难点，其研究进度仍然只是停留在实验阶段，尚未大规模投入到实际应用当中。M.Dorigo等人结合具体的实验类型和数据来对蚁群算法的基本属性进行了全面性的分析和研究。所以本实验中重要参数设置如下：信息素浓度影响力参数α：所有算法α设为1.0。启发式信息影响力参数β：所有算法β设为5.0。信息素蒸发系数ρ((1-ρ)表示信息素的持久性系数)：所有算法ρ设为0.5(1-ρ即为0.5)。蚂蚁数目m：本文将m设为问题规模n的2/5即m=n*2/5在算法开始时蚂蚁随机分布在各个城市上。（n为其中TSP问题中后面的数字，如:ATT48.TSP中48即为n值）。TSP问题：本文使用ATT48.TSP的TSP问题。对比实验用4.2传统蚁群算法与4.3改进后蚁群算法的条件进行计算机仿真，为了有效的、科学的对算法有效性进行评价，采用准确度作为模型的评价标准。准确度定义如下：Precision=R/(R+W)*100%其中，R表示正确的结果，W表示错误结果。设定θ为网页之间的转移概率的阈值，当转移概率大于该θ的路径即为用户感兴趣路径。若感兴趣路径阈值θ的值较低，那么不相关的网页被推荐。大量实验表明，θ=0.5最好，因此本文的θ值为0.5，本文改进后的蚁群算法与对比的传统蚁群算法对于不同的事务长度，用户感兴页面进行日志挖掘后预测的准确度如表4.4所示：表4.4挖掘准确度对比事务长度本文改进后蚁群算法传统的蚁群算法36556473625826968781783798868598989图4.8两种算法的预测准确度（蓝色为改进后，红色为传统算法）根据图4.8可知，相对于传统蚁群算法，本文设计的改进后的蚁群算法的日志挖掘准确度更高，能更加有效地跟踪用户的兴趣变化，主要由于蚁群算法采用信息素机制实现正负反馈机制。对比结果表明，基于蚁群算法的Web网站日志挖掘模型可以很好挖掘用户的兴趣路径，蚂蚁之间的协作作用改善了用户浏览页面预测的准确度，动态跟踪用户浏览行为。另外，本文选取另外的网页页面个数分别为50、100、200的网站，对其网站日志采用本文的日志获取方法进行了提取，然后根据大小将其划分为四个测试用命，大小分别为1M，2M，3M，4M，并继续对数据进行预处理，使之符合本文算法与传统蚁群算法条件，然后考察其CPU执行时间。实验结果为传统蚁群算法的CPU时间大于本文算法的CPU时间；而且随着测试用例的日志数量的增加，本文改进后的算法执行时间增加速率较慢，对传统蚁群算法的执行时间增加的幅度相对较大；缺点为本文算法对于网站上的链接数目敏感，如果网站上的URL数目增多，本文算法的执行时间延长，而传统蚁群算法执行时间与URL个数无关。最后，本文也评测了网站服务器的性能受用户行为获取机制的影响。本文统计了50次在用户行为获取机制加载前后，用户计算机浏览器中载入网站页面所需的时间，加载时间的平均增量为140毫秒，用户基本的上网行为不会受到影响。本节将改进后的蚁群算法引入到Web日志挖掘建模中，通过蚁群算法的正负反馈机制和路径概率选择机制快速找到用户目标网页，仿真实验结果对比表明，改进后的蚁群算法提高了网页日志挖掘中的预测精度，更能反映出用户的浏览兴趣与意图。改进后的蚁群聚类算法应用场景实验上节利用蚁群聚类算法对人工数据进行了分析，现在本文会利用该算法对2021年中国24所高校综合实力进行分类，同时来验证蚁群聚类算法的实际应用效果。下面是2021年中国24所高校综合实力数据集，见表4-5，表4.5主要表示的是24个样本集合，每个样本集合都有其独特的属性，通过设置10只蚂蚁来对下列3个样本进行分析，迭代次数1000次。表4-52021年中国24所高校综合实力数据表：指标序号声誉得分学术资源得分学术成果得分学生情况得分教师资源得分物资资源得分1清华大学100.093.1100.0100.0100.0100.02中国科大88.089.152.389.160.447.33复旦大学91.967.452.183.863.160.94浙江大学90.945.854.480.169.284.45南开大学83.963.433.483.564.151.56北京师大79.652.646.978.257.048.87中山大学78.956.829.376.238.966.48武汉大学82.040.523.378.958.858.59天津大学78.436.625.376.959.447.410吉林大学74.831.518.268.048.958.611北京理工67.434.913.083.245.647.712东北大学63.331.649.413中南大学67.738.616.266.446.156.514湖南大学62.326.49.963.344.541.115暨南大学16重庆大学63.538.744.317上海财经57.522.87.865.931.042.318苏州大学52.820.811.956.039.839.519云南大学54.422.112.550.641.125.120上海大学56.639.746.321辽宁大学49.336.824.322郑州大学5157.66.923福州大学52.815.87.550.330.619.324江苏大学43.710.13.349.027.130.0资料来源：http://rank2021./cn/rnk_1_0_0.htm对表4-6的数据本文使用蚁群聚类算法进行分类最好结果如表4-3。表4-6蚁群聚类算法进行分类最好结果111111113333232222222222通过上面表4.6我们可以看出用蚁群聚类算法将24所高校综合实力（6个不同的综合数据）进行了分类的结果与网大（http://rank2021./cn/rnk_1_0_0.htm）公布的大学排行榜基本一致。通过本研究可以发现，蚁群算法聚类分析能够获得较为满意的结果，但是必须保证分析数据是准确可靠的。本章小结本章首先对Web日志挖掘中蚁群算法的应用背景进行分析，然后对蚁群算法基本原理以及传统蚁群算法原理进行了分析，然后分析传统蚁群算法的缺点，针对效率低下的问题，采用局部搜索的方法对基本蚁群算法进行了改进，通过仿真采用网站真实数据对两种算法进行了效率对比，确认了新的算法的效率高的特点。Web日志数据挖掘系统的实现目前，由于Web站点规模和范围的不断扩大，以及业务流程的不断复杂化，要想对一个Web站点进行合理高效的管理变得越来越艰难。那么，设计一个Web日志数据挖掘系统就显得尤为重要了。通过运行该系统，不仅可以收集用户访问站点的日志数据，同时还能对服务器的运行情况进行监视，系统还可以分析与查询每个用户的操作行为，掌握用户浏览的相关规律，更好的为整个Web站点服务。除此之外，建立Web日志挖掘系统，还可以为网络管理人员提供可视化的操作界面，降低了网络管理的难度，同时也满足了不断变化的网络故障排除以及设备升级等需求。在上文的研究中，我们对原始的蚁群算法进行了改进。因此，本章在前文的研究基础上，将Web日志数据挖掘出的信息以图形化的形式在网页上展示出来，基于改进的蚁群算法以及Web日志数据挖掘的基本思路，设计了一套基于J2EE体系的日志挖掘系统。系统的设计系统的功能设计本套系统主要包含了数据获取、预处理、建模、查看模型以及分析与评价模型等五个功能模块，具体功能设计如图5-1所示。WebWeb日志数据挖掘系统挖掘模型分析与评价挖掘模型查看挖掘模型构建数据预处理数据获取挖掘模型分析与评价挖掘模型查看挖掘模型构建数据预处理数据获取模型评价模型分析依赖关系网络绘制频繁关联项集展现频繁项集模型显示频繁项集模型挖掘处理后数据显示原始数据显示数据备份数据加载模型评价模型分析依赖关系网络绘制频繁关联项集展现频繁项集模型显示频繁项集模型挖掘处理后数据显示原始数据显示数据备份数据加载图5-1数据挖掘系统功能模块设计 在本套系统中，数据获取模块的主要功能是对服务器上的Web日志数据进行导入，同时还要负责完成数据的备份保存工作；完