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

第五章，原来是关联规则，现在要改成聚类的方式，算法为第四章的改进的蚁群算法。原来的功能图太宽跨界了，图不可以超过文档的内容部分。

第一章，主要是研究现状及分析进行修改，其他的文字表述做相应修改 查重率差不多达到10%

1 引言

随着Internet/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日志上信息结构排序和内容的抽取，避免了各算法之间使用的重复性。

蚁群算法是一种模拟进化的算法，它是借鉴蚂蚁在寻找食物过程中会自动搜寻最短路径而衍生出来的。该算法具有优良的分布式计算[2]、正反馈性等特点，特别是在解决组合最优的问题上已经吸引了很多中外学者的关注。它也是继遗传算法、人工神经网络算法后又一个得到大家认可的研究性课题。在本论文之中，将一种比较新型的蚁群算法的概念引入到WEB挖掘的聚类、分类技术之中，在获取更优的分类规则上面取得了较好的效果。

1.2 研究现状及分析

Web日志挖掘无论在国内还是国外都是通过挖掘服务器存储的Web日志，进而发现用户访问Web站点的访问模式。

根据对Web日志数据源处理方法的不同，Web日志挖掘可以分为以下两类：第一类是将Web日志记录中的数据进行转换，然后传递进传统的关系表中，再用常规的算法对关系表中的数据进行挖掘。第二类是在对Web日志记录的数据进行挖掘之前对数据先进行数据预处理操作。

(1) Web日志挖掘聚类和分类技术

聚类是从Web日志的访问数据中分析并整合出来具有相似特征事务的技术。Web日志使用挖掘中分为：页面聚类和使用聚类。页面聚类是通过搜索引擎在Web日志上找到具有相关内容的页面组，这更方便于用户在上网时能更容易地获得想要的信息。使用聚类就是将具有相似浏览模式的用户分为一组，这样形成了若干组，并对其量化，从中得到对用户有用的规则，当前该技术常应用于电子商务和一些个性化服务上。这两种聚类方法就是通过搜索引擎分析用户查询或访问网页信息时产生的历史记录所形成的HTML，来向用户提供超链接。

分类是对新添加的数据进行分类并将一个对象分到事先定义好的类中，根据用户群的特征来挖掘出用户群的访问特征。在Web日志挖掘中，分类可以通过访问用户信息而得到的一些用户特征，这需要抽取并选择出最好地描述这组特定

用户的特征，并根据这些特征对用户进行分类。常使用监督归纳学习算法来进行分类，如决策树、K-邻近分类法和支持向量机、机器学习法、贝叶斯分类方法等。

(2) 蚁群算法

蚁群算法，现在被称为蚁群优化(ACO,Ant Colony Optimization)是一种用来在图中寻找优化路径的机率型算法，它源于社会昆虫的群体活动所表现出来令人惊讶的行为，也这对日后研究蚁群行为提供全新的领域。

ACO技术是一种基于群体智能的算法，它源于自然解决问题的思想，并在求解组合优化类问题上有明显的优越性。Marco Dorigo在1991年他的论文中首先提出了蚂蚁系统(AS),通过正反馈、分布式协作来寻找最优路径。并且常用于解决二次指派、多维背包、Job-shop调度等问题上。AS优化算法采用了分布式计算方法，具有多代理性和较强的鲁棒性等特点，且该算法已被大量应用于机器人协作问题求解、电力、通信、数据分析等领域。

蚁群算法是学者受到蚂蚁觅食的启发而发现的，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁群体协作功能是通过遗留在来往路径上的信息素(Pheromone) 来进行信息通讯并形成正反馈。假设蚂蚁走两条不同的路径来寻找食物，刚开始的时候走两条路的蚂蚁一样多，并且在搜索过程中释放出一定量的信息素，当蚂蚁沿着一条路到达终点后返回，短路径的蚂蚁来回一次时间就短且重复频率快，因而在同一时间内走过该路径的蚂蚁数目就多，洒下的信息素也就多，自然就有更多的蚂蚁会吸引过来，这样慢慢当蚂蚁数量不断增加时（同样信息素浓度也增加），最短的路径就近似被发现了。

蚂蚁系统具有搜索最优的能力，得利于其同分布式计算和正反馈机制相结合的特点，使其具有较强的并行性和鲁棒性，但也同样存在一些缺陷，如搜索停滞以及搜索结果局部最优等问题。针对该系统存在的不足，很多中外学者提出了许多改进的蚁群算法，这些优化算法在解决局部搜索最优问题以及搜索停滞问题上有很大的提升。在当前研究形势下，蚁群算法已经成为中外学者广泛关注的热点问题。

1.3 论文组织结构

论文中较系统地分析和论述了Web日志挖掘中的各项技术。在此理论基础上，引入了改进的蚁群算法，并将其成功应用于Web日志挖掘的聚类和分类上。论文的整体构架如下：

第一章 绪论

介绍了本课题的研究背景，主要内容和论文的组织结构

第二章 基于蚁群算法的Web日志挖掘理论

介绍了Web日志挖掘理论，在论述了Web日志挖掘过程的基础上，详细地分析了Web日志挖掘中聚类和分类技术。然后分析了蚁群算法及几种改进的蚁群算法的思想。最后，对现有算法应用于Web日志挖掘技术上存在的问题做了详细地论述。

第三章 Web日志挖掘的预处理技术

对Web日志挖掘中的关键技术，即Web日志挖掘预处理技术进行了全面的分析和总结。

第四章 基本蚁群算法及其改进

对蚁群算法基本原理以传统日志挖掘算法原理进行了分析，并对基本蚁群算法进行了改进，通过仿真来说明基本蚁群算法的原理。

第五章 Web日志数据挖掘系统的实现

以中名老中医临床经验、学术思想传承研究中的Web日志数据为例，基于改进的蚁群算法设计了一套Web日志数据挖掘系统，并对系统进行了评价和分析，为改善中医系统网站提出了优化建议。

第六章 总结与展望

总结了本文的研究工作，提出进一步研究的方向。

2 基于蚁群算法的Web日志挖掘概念

2.1 Web日志挖掘

随着信息技术的普及和应用，各个领域产生了大量的数据，这些数据被获取、存储下来，其中蕴含着丰富的信息。人们持续不断地探索处理这些数据的方法，以期最大程度地从中挖掘有用的信息，面对如潮水般不断增加的数据，人们不再满足于数据的查询和统计分析，而是期望从数据中提取信息或者知识为决策服务。数据挖掘技术突破了数据分析技术的种种局限，它结合统计学、数据库、机器学习等技术解决从数据中发现新的信息，辅助决策这一难题，是正在飞速发展的前沿学科。一些大型企业对数据挖掘产品和工具的使用都超过20年，并已产生了期望的效应。此外，数据挖掘产品和工具在金融、商业、电信、医学等多个领域也得到广泛推广应用。

在数据库技术飞速发展的同时，人工智能领域的一个分支----机器学习的研究也取得了很大的进展。自20世纪50年代开始机器学习的研究以来，在不同时期的研究途径和研究目的也不尽相同。一般大致可以分为三个阶段，其研究内容则分别为：神经模型和决策理论、概念符号获取及知识加强和论域专用学习。根据人类学习的不同模式人们提出了很多机器学习方法，如：实例学习、观察和发现学习、神经网络和遗传算法等。其中某些常用且较成熟的算法已经被人们用于实际的应用系统及智能计算机的设计和实现中。正是由于数据库技术和机器学习技术的发展，也是为了满足人们实际工作的需要，数据挖掘(Data Mining)技术逐渐发展了起来。

Web日志挖掘是一项综合技术，是数据挖掘在Web日志上的应用，涉及有信息学、数据挖掘、机器语言学、Web日志技术等多个领域。它是利用数据挖掘技术从Web日志相关的行为和资源中挖掘出新颖的、有效的、潜在有用、用户易理解的模式和信息的过程。Web日志数据挖掘的基本原理过程如图2.1所示。

3 Web日志挖掘的预处理技术

聚类是将复杂的事物分门别类，并对陌生繁乱的事物进行归类总结，相同类别的事物采取类似的处理方法，这样就能大大提高事物的处理效率，通过自动聚类能够识别对象空间中不同密度空间的区域，从而发现全局分布模式，并结合蚁群算法的正反馈、鲁棒性、分布式计算等优点，对聚类模型进行设计。

3.1 聚类模型分析

聚类分析在Web日志挖掘中是一个很重要的技术。聚类分析可以增强对象集的可理解性，并发现对象集中数据间共同的结构和联系，保持其有效性。即按照一定的规律和需求，将一些特殊分散的对象按照其相似性进行分类，并使得对象点的集合分成若干类，且每个类中的对象点最大程度地相似，各个类之间的对象点最大程度地不同。在聚类分析过程中没有涉及关于分类方面的知识，只是依靠对象点间的相似度作为划分类的依据，因此聚类分析是一种观察式学习，是利用数学方法研究和处理所给定对象的分类，其多元的统计分析方法是统计模式识别中非监督模式识别的重要分支。为了描述对象样本间的距离，特引入特征变量类型和相似性度量这2个概念。

(1) 特征变量类型

为了描述一个对象样本，我们通常会对对象进行特征抽象化，使用多个特征指标变量来给予每个对象一个特征向量。特征指标变量可以分为：间隔标度变量、二次变量、序数变量，处理不同类型的特征指标变量则采取不同的策略。

对于间隔标度变量是使用连续的实数来表示的数量信息，一个样本点可以看作是多维空间中的一点，通过一些特殊的运算来求解各个样本在空间上的距离。对于二元变量，用两种状态（0或1）来表示样本属性，1表示变量出现，0表示变量不出现，该变量特征也可以用来分类变量尺度，标记多状态。对于序数变量，它类似于分类变量，不用于分类变量的是，其状态时无序关系的，而分类的状态是有序的。对于这两种特征变量我们不能定义合适的数学运算，需要通过特殊变换后才能进行对象相似度计算。

(2) 相似性度量

为了更好地描述对象集中的单个样本，需要样本类型中的特征指标变量提供度量值，同样为了描述样本间的相似特性，也需要定义能合理地衡量样本间相似程度，从而合理地进行聚类的度量，以便把相似的样本归为一类，非相似的样本

归为不同的类。常用刻画样本间的相似性函数有2种，分别是：相似系数函数、距离函数。

相似系数函数是用来描述样本点特征性质之间的相似程度，当相似系数值越接近0时，说明两个对象样本越不相似，当相反相似系数值越接近1，则说明两个对象越相似，这才可以将它们归为一类。

距离函数指的是对象样本间的距离，对于含有N个属性的样本对象来说，我们可以将每个样本点看作是N维空间中的一个点，然后使用某种距离来表示样本对象点之间的相似性，对象样本点越相似，则样本点之间的距离越小，可以将它们归为一类；对象样本点差异越大，则两者间的距离越大，就不能归为一类。

3.2 聚类模型设计

聚类首先要做的是对样本对象的特征抽取，它所处理的对象是样本数据集，由于实际应用中的样本数据对象一般都有多种特征，要具体选取哪种特征才可以正确地描述样本对象的本质和结构对于聚类分析来说至关重要。特征抽取的结果是输出一个矩阵，每一行对应的是一个样本对象，而每一列对应的是一个特征变量。特征的抽取是另一个重要步骤，对后续的分析和决策有直接的影响。如果抽取的特征变量只是样本对象中不重要的属性，对这些无关紧要的属性进行聚类分析出的结果肯定也达不到预期的效果，因为当使用错误的特征属性来解释对象时，容易扭曲样本对象，再对这样的样本对象进行的聚类分析，即便是用最好的聚类算法来对其处理，结果也是不正确的。

总结蚁群算法和聚类分析的特点，引入了一种改进的蚁群算法(Improved Ant Colony Algorithm，IACA)。并将其运用到Web日志的用户聚类上，聚类模型如下： 1. 初始化设定

设有M个模式样本、K个模式分类，N是表示为几个样本对象；初始状态将M个样本随机分配到N个聚类中心，K表示分类出K个等级，每个模式样本是一个D维向量，定义模式样本Xn?(Xn1,Xn2,...Xnd)。设聚类中心为 Zj?(j?1,2,...k，则目标函数表示为：,KNT?min?2. 信息素更新

j?1i?1且Xi?第j类?||Xi?Zj||（3-1）

计算蚂蚁的各自初始聚类中心Zkj（第k个蚂蚁将模式样本i分配到第j个聚类中心）和初始目标函数，初始化各蚂蚁的样本到各聚类中心的信息素浓度Pijk，信息素浓度更新公式为：

kkkP(new)??P(old)??Pijijij（3-2）

k其中?Pij是信息素增量,?是信息素强度的持久性系数（算法中1-?表示信息素

挥发度）。

初始化，蚂蚁将M个样本随机分配到K个聚类中心 计算蚂蚁的各自初始聚类中心Zj和初始目标函数Tk? 初始化各蚂蚁的样本到各聚类中心的信息素浓度 kM只蚂蚁到N个样本进行K个模式分类 更新并调整信息素，计算出新的聚类中心Zj，计算目标函数Tk hk'搜索次数h=h+1 |T?TT是 hhkh?1kh?1k|否 ?? 否 h>=L? 选取min(Tk)，输出分类结果 是 算法结束

图3.1 流程图

3. 聚类中心的计算方法

对于聚类中心Zj(j?1,2,...,k)的计算方法，我们选择了K均值算法[12]来计算每个聚类中心。 4. 有关参数的选择

由于算法参数的选择会对蚁群算法的性能产生较大的影响。从蚂蚁搜索最短路径的原理出发，我们定义了一些参数：种群数N、常数Q、绝对感觉阈值CST和差别感觉阈值AST以及信息素挥发度1-?等等。

蚂蚁数量N决定蚁群算法的循环次数呈线性变化。当蚂蚁数量过大时,搜索的全局性和稳定性有所提高，但是算法的收敛速度变慢。蚁群搜索过程中信息素挥发度1-?的大小关系到蚁群算法运行过程中的收敛速度和全局搜索能力：当1-?过小时，搜索过的路径被选择的概率降低，虽然算法全局搜索能力和随机性能有所提高，但是收敛速度却下降；当1-?过大时，表示搜索过的路径被再次选择的概率增加，影响算法的全局搜索能力；所以对信息素挥发度的选择，需要平衡算法的收敛速度和全局搜索能力。另外，AST和CST的取值也很重要，取值不恰当容易使解陷入局部收敛，算法需要在稳定性和求解速度上取得平衡。

3.3 Web日志预处理相关技术

在对Web日志进行挖掘之前，有一个很重要的数据处理过程，称之为Web日志预处理，也就是对 Web 日志数据进行过滤、清洗以及重新组合的过程。我们都知道服务器端的Web日志中记录了用户访问网站的各种信息，但是这些信息中有些数据是自动产生，而有些信息可能并不是我们需要研究的，这些都属于无用的，所以我们应该对其进行数据预处理。而Web日志预处理技术主要包括有以下五个阶段：

（1）数据清理； （2）用户识别； （3）会话识别； （4）路径补充； （5）事物识别。

服务器产生的Web 日志文件是Web日志挖掘中数据预处理所要研究的对象。在这些日志文件中存在许多对研究没有任何意义的数据，所以直接用这些文件将会导致研究出的结果有偏差或出错等问题。所以，Web日志数据预处理过程是Web日志挖掘的第一个阶段，也是非常重要的阶段。这个阶段会对Web服务器

日志或者代理日志进行数据清洗、数据规范化和数据集成等操作，最终把原始的日志数据通过一系列操作，处理成便于进行挖掘算法的数据。

不同的Web日志文件中记录的数据也会相应的有各自的数据特点，是不一样的，因为每个服务器设置的参数不一样，但是有一些基本的信息是无论任何服务器都应该有记录的。如表3-1所示。

表3-1 Web访问日志记录的主要信息

属性 日期以及时间 用户IP地址 用户名 服务器IP地址 服务器端口 方法 URL查询 协议状态 发送的字节数 接受的字节数 用户代理 日志的说明 用户请求页面的日期以及具体的时间 客户端主机的IP地址或者DNS入口 客户端的用户名 服务器的IP地址 服务器端口号 用户请求数据的方法 用户将要进行的查询 返回http的状态的标识 服务器发送数据的字节数 客户端收到数据的字节数 服务的提供者 3.4 Web日志数据预处理的过程

Web日志数据预处理主要任务是，把输入数据为Web服务器日志或其他的日志记录文件转化为可以进行挖掘的用户会话文件以及事务数据库，而处理数据的结果将直接影响Web日志挖掘质量的好坏。一般来说，Web日志数据的预处理过程由以下五个阶段构成，分别是数据清理、用户识别、会话识别、路径补充以及事物识别。如图3-2所示。接下来针对这五个阶段来详细的进行下介绍。

图 3-2 Web 日志数据预处理的过程

3.4.1 数据清理

Web服务器日志文件中有很多与研究没有任何意义的“脏数据”，数据清理这个操作就是把“脏数据”进行“清洗”的过程。

首先把从服务器取出来的Web日志记录进行合并，然后将其存进对应的数据字段中，因为Web日志文件一般只有html文件才会跟用户会话相关，所以在这一过程中一般都要根据实际情况去掉日志中的图像文件以及其他不相关的文件。比如图像文件的后缀有gif，jpg，jpeg等等，除图像文件之外还有一些js、css、swf等文件根据具体情况也进行相应的删除。除此之外，以cgi为后缀的一些脚本文件也应该被剔除掉。清理流程如图3-3所示。

将该记录添加到表中 Y 从日志数据库中删除记录 N 状态码是否以2开头 请求url的后缀是否为.gif、.jpg等格式 N Y 从日志数据库中读取一条记录 日志数据中是否有记录 N 日志清理完成 开始 Y 图3-3数据清理流程图

（1） 纵向缩减（也称行缩减）

为了让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开头的信息删除。

（2） 横向缩减（也称列缩减）

当使用数据挖掘的算法对数据进行挖掘的时候，很多web日志中的属性是非必需的，所以仅仅只考虑纵向缩减来减少日志文件是远远不够的。比如，对用户信息进行聚类分析时只需要使用用户的ip地址、用户请求访问的url、用户访问的时间、用户使用的代理等属性就可以；而分析web站点的流量时，只需要使用用户请求url用户访问时间等属性。

这种缩减日志记录中属性的方法就是横向缩减，也叫列缩减。与纵向缩减不同，横向缩减不会缩减日志文件的行数，而只会减少属性列。

3.4.2 用户识别

用户就是指通过一个浏览器访问一个或几个服务器的个体。我们在实际中唯一确定一个用户是非常困难的，因为有防火墙、高速缓存、代理服务器等进行阻碍。辨别一个用户可以有用户IP和Cookie标识两种方法。Cookie是站点根据浏览器写入本地的唯一的一个标识，当用户再通过url请求服务器时，请求中就会

加上这个标识，然后返回给服务器，这样就可以识别用户了。不过这种情况也有缺点，那就是当若干个用户使用同一个电脑的时候，一旦有用户删除Cookie，那么下一次登陆服务器就会被当做第一次登陆。当然也有可能因为隐私不会被写到Cookie中，所以，有的时候要把代理、服务器日志、参引页面等综合考虑才能确定一个用户。

图3-4简单的Web站点

因为本地代理服务器和高速缓存机制的存在，极有可能会使用户在网站上的浏览情况歪曲，这就可能会导致我们漏掉了重要的访问内容，从而不能比较精确地描述用户浏览网页的情况。因为各个网站都有后退键，这就导致一个访问记录只列出了一次，而实际是很有可能被多个用户参考了很多次。

针对该问题目前主要有以下三种解决方法：关闭高速缓存、利用Cookie以及利用用户注册。但这三个方法都存在问题，首先，用户是可以随意删除Cookie的。其次，高速缓存是为了提高网站加载的速度，关闭高速缓存之后也是可以再次打开的。最后，用户的注册涉及到了个人隐私，而且是自发的，所以很多用户注册的信息是不真实的。

高速缓存问题的解决方法可以采用站点拓扑学的知识或利用参考日志和时间信息来判断遗失的参考。表 3-2 列出了目前用于用户识别的几种方法。

表 3-2 中的方法多多少少也有一些不足之处，目前在 Web 日志挖掘中，对如何准确识别用户而又不涉及用户的隐私的问题的研究已经成为热门的研究。本文只对用户识别作简单介绍，不进行深入的研究。

表3-2 用于用户识别的方法

方法 描述 IP地址和代理 假定每个IP地址和一个用户代理组合表示一个用户 低 可用性好，不需要另外的技术和信息 不能保证用户的唯一性，一个IP多个用户代理的情况无法处理 嵌入会话ID 利用动态网页将ID插入每个链接 用户注册 用户显示的登录网站 软件代理 当程序调入浏览器后可以发回使用数据 中/高 可以跟踪重复访问 Cookie 在用户端保存一个唯一的用户标识 隐私程度 优点 低中 简单可行，独立于IP地址 没有重复的访问概念，需要完全动态网页 中 可以精确的跟踪每一个注册用户 无法跟踪大量的非注册用户 中 可以精确跟踪用户访问一个站点的信息 用户可以中止使用cookie，可用性不高 缺点 用户可以禁止该软件 3.4.3 会话识别

一个会话就是指用户在一次访问过程中所访问的 Web 页面的序列。会话识别的目的是将每个用户的访问信息划分成若干个独立的会话进程，最简单的方法是采用超时估计的办法，即当对页面之间的请求时间间隔超出所给定值时，即可以认为用户已经开始了一次新的会话。JPitkow 的实验证明：比较合理的时间长度应该是 25.5 分钟，通常使用30 分钟作为一个用户点击流会话的时间长度。会话识别的流程图如图3-5所示。

Y 判断url是否超时 N 读出表中一个用户放的日志记录 开始

择概率越来越大，由于路径信息素不断的发挥，时间较长的路径保留的信息素相对较少，这样蚂蚁最终找到一条最优路径。蚂蚁群体的路径寻优机制如图4.2所示，在图4.2中，其中，CD为一障碍物，蚂蚁通过由B或E绕过障碍物进行觅食。

图4.2蚂蚁群体的路径寻找机制

比较图4.1和图4.2可知，Web日志挖掘与蚁群觅食本质极相似，因此采用蚁群算法对Web日志挖掘问题进行求解是可行的。

4.2 传统日志数据挖掘算法

本小节将介绍传统的web日志挖掘算法及蚁群算法。

4.2.1 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很大时，子集的数量变得很多，频繁项集树的节点数也将变多。因此，计算机将会反复的对数据集合进行遍历，从而生成频繁项集，而对频繁项集树进行保存也会占用大量缓存空间，影响整个算法效率。

4.2.2 蚁群系统算法

蚁群算法在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日志挖掘中的应用模型

在对一个网页或者网站进行浏览时，用户对网页的阅读频率和阅读时长可以体现出对此网站的兴趣，当用户对内容有兴趣时，会表现在阅读时间增长，阅读页面增多，因此采用蚁群算法进行日志挖掘时，会考虑采用定义用户的浏览序列并建立一条路径，而将浏览序列作为支持度，成为整个算法的启发式信息，并对用户的浏览兴趣进行描述。

4.3 一种改进的适用于Web日志挖掘的蚁群算

如同前面所介绍，在初始阶段，每只蚂蚁分配到一个空的解集合，所有的信息素初始化为一个相同的值，随着迭代过程的进行，信息素值将依赖于产生的解的质量得以更新。下面结合一个具体问题来详细分析如何调整蚁群算法求解聚类问题，蚁群聚类算法采用的硬件/软件环境分别为：CPU 2.4 GHz内存 256 M 硬盘容量 80G 安装的是Microsoft windows XP （Service Pack 2）操作系统开发平台MATLAB 7.0。

下面结合一个具体问题来详细分析如何调整蚁群算法求解聚类问题，数据集见表4-1。表4-1 为包含10个样本的数据集，每个样本有4个属性，设置 10 只蚂蚁欲将样本划分为 3 类。

表 4-1 10个样本划分为 3 类的聚类问题的数据集

序号 1 2 3 4 5 6 7 8 9 10 1 5.4 4.8 4.8 4.3 5.8 5.7 5.4 5.1 5.7 5.1 2 3.7 3.4 3.0 3.0 4.0 4.4 3.9 3.5 3.8 3.8 3 1.5 1.6 1.4 1.1 1.2 1.5 1.3 1.4 1.7 1.5 4 0.2 0.2 0.1 0.1 0.2 0.4 0.4 0.3 0.3 0.3

下面本文介绍具体的迭代过程，为了便于描述，用 t（本次取值1000）来表示迭代的次数。每只人工蚂蚁依赖于第 t 次迭代提供的信息来实现分类。表4-2

中列出本次迭代中最好解S1继承的信息素矩阵。

表 4-2 S1解的t次迭代后的信息素矩阵

序号 1 2 3 4 5 6 7 8 9 10 1 1.6644 1.6446 1.3027 1.3815 1.2152 0.11002 1.6644 1.6644 1.1466 1.6644 2 0.68016 0.11969 0.01 0.01 1.6644 1.6644 1.5642 0.01 1.6644 0.01 3 1.2207 1.6644 1.6644 1.6644 0.50114 1.0949 1.2832 0.71071 0.11904 1.2349 τ

11=1.6644，τ12=0.68016，τ13=1.2207

11

为第 1 个样本对应与每一个类的

信息素值。这组数据表明，由于τ的值较大，第 1 个样本将以较大的概率归

于第 1 类。事实上，每只蚂蚁按照以前介绍过的随机加确定方法来选择第 i 个样本将所属的类。在此，结合聚类问题再次加以叙述。方法如下：

(i)以预先定义好的几率 q0(0

(ii)以(1-q0)的几率根据转换概率随机选择样本要划分的类。

由人工蚂蚁遍历所有的样本构建出的候选解的质量是由特定的聚类问题的目标函数值来决定的。下面表4-3为蚂蚁数目为10的蚁群聚类算法(排好了顺序)的结果：

表4-3为蚂蚁数目为10的蚁群聚类算法(排好了顺序)的结果

序号 1 1 2 3 4 1 1 1 1 2 3 3 3 3 3 3 3 3 3 4 3 3 3 3 5 2 2 2 2 6 2 2 2 2 7 1 1 1 1 8 1 1 1 1 9 2 2 2 2 10 1 1 1 1 F 3.0041 3.0041 3.0041 3.0041 5 6 7 8 9 10 1 1 1 1 3 1 3 3 3 1 3 3 3 3 3 3 3 1 3 3 3 3 3 3 2 2 2 2 2 1 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 2 2 1 1 1 1 1 1 3.0041 3.0041 3.0275 3.0568 3.6226 3.9488 本文还将实验的最优解结果使用Matlab实现了2维和3维图，使得结果显示更加直观明了，如图4-4和图4-5所示。

图4-4 2维效果图4-5 3维效果

本文还将实验的最优解结果的分类值使用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也进行交换操作。对于通过交换而产生的新的解集要重新计算其目标函数值，与原解集的目标函数值比较，择优。执行过局部搜索之后，要对信息素值进行更新。信息素更新公式采用蚂蚁系统中的公式：

k?ij(t?1)?(1??)?ij(t)????ij i=1,...,N j=1,...,K

k?1k其中，τij(t)及τij(t +1)为样本 i 与类 j 在 t 及 t+1 时间的信息素浓度。

Q if ij?Lk?LK?k??ij??

??0 otherwiseLk为蚂蚁 k 所找到的最小目标函数值。

Q 为一参数值。

ρ为信息素蒸发参数，0<ρ<1。 至此，一次迭代结束。

4.3.1 改进后蚁群聚类算法流程

改进的蚁群聚类算法的主要步骤叙述如下：

步骤 1：初始化，包括蚂蚁数目 R、类的个数 K、转换规则参数 q0、局部搜索阈值等。

步骤 2：所有人工蚂蚁根据上一次的信息构建解集，计算各类中心。 步骤 3：在产生的解集找到要交换样本的 Sk实施局部搜索操作。 步骤 4：更新信息素值。

步骤 5：如果没有达到迭代次数预定值并且没有稳定解，则转步骤2，否则输出最优的分类解集。

算法基本流程如图4-7。

初始化每只蚂蚁分配到初始节点每只蚂蚁根据转换概率选择要转移的下一个节点进行信息素局部更新所有蚂蚁构建出问题的近似解？是否进行全局信息素更新否到达设定的迭代次数或出现稳定解？是结束搜索

图 4-7蚁群算法流程图

当然，迄今为止蚁群算法已经有了很多的变型或改进算法，但基于蚁群算法（ACA）寻找问题近似解的思想及实现优化过程的机制还是没有改变。由上图可见，蚁群算法区别于其他传统优化算法，因为它具有以下3个特点：

(1) 模拟了一种大自然真实存在的现象，并建立模型； (2) 不可确定性；

(3) 总是表现出一种并行性，不是在系统中强行加入，而是算法本身隐含具有的。

4.4 仿真实验对比分析

在4.2小节中本文详细介绍了基本蚁群算法的原理等，在本小节中将通过计算机仿真来理解基本蚁群算法的原理，并将作出的路径图和最终结果自动保存到文本文档(.txt)与Excel(.xls)中。

4.4.1 仿真环境与数据

为了详细对比出两种不同算法（改进前与改进后）算法优劣，本文实验采用同一种实验数据：样例网站则名老中医系统的日志数据，实验数据中纪录数共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.4.2 对比实验

用4.2传统蚁群算法与4.3改进后蚁群算法的条件进行计算机仿真，为了有效的、科学的对算法有效性进行评价，采用准确度作为模型的评价标准。准确度定义如下：

Precision=R/(R+W)*100%

其中，R表示正确的结果，W表示错误结果。

设定θ为网页之间的转移概率的阈值，当转移概率大于该θ的路径即为用户感兴趣路径。若感兴趣路径阈值θ的值较低，那么不相关的网页被推荐。大量实验表明，θ=0.5最好，因此本文的θ值为0.5，本文改进后的蚁群算法与对比的传统蚁群算法对于不同的事务长度，用户感兴页面进行日志挖掘后预测的准确度如表4.4所示：

表4.4挖掘准确度对比

事务长度 本文改进后蚁群算法 3 4 5 6 7 8 9 65 73 82 87 83 86 89 56 62 69 81 79 85 89 传统的蚁群算法

图4.8两种算法的预测准确度（蓝色为改进后，红色为传统算法）

根据图4.8可知，相对于传统蚁群算法，本文设计的改进后的蚁群算法的日

志挖掘准确度更高，能更加有效地跟踪用户的兴趣变化，主要由于蚁群算法采用信息素机制实现正负反馈机制。对比结果表明，基于蚁群算法的Web网站日志挖掘模型可以很好挖掘用户的兴趣路径，蚂蚁之间的协作作用改善了用户浏览页面预测的准确度，动态跟踪用户浏览行为。

另外，本文选取另外的网页页面个数分别为50、100、200的网站，对其网站日志采用本文的日志获取方法进行了提取，然后根据大小将其划分为四个测试用命，大小分别为1 M，2 M，3 M，4 M，并继续对数据进行预处理，使之符合本文算法与传统蚁群算法条件，然后考察其CPU执行时间。实验结果为传统蚁群算法的CPU时间大于本文算法的CPU时间；而且随着测试用例的日志数量的增加，本文改进后的算法执行时间增加速率较慢，对传统蚁群算法的执行时间增加的幅度相对较大；缺点为本文算法对于网站上的链接数目敏感，如果网站上的URL数目增多，本文算法的执行时间延长，而传统蚁群算法执行时间与URL个数无关。

最后，本文也评测了网站服务器的性能受用户行为获取机制的影响。本文统计了50次在用户行为获取机制加载前后，用户计算机浏览器中载入网站页面所需的时间，加载时间的平均增量为140毫秒，用户基本的上网行为不会受到影响。

本节将改进后的蚁群算法引入到Web日志挖掘建模中，通过蚁群算法的正负反馈机制和路径概率选择机制快速找到用户目标网页，仿真实验结果对比表明，改进后的蚁群算法提高了网页日志挖掘中的预测精度，更能反映出用户的浏览兴趣与意图。

4.5 改进后的蚁群聚类算法应用场景实验

上节利用蚁群聚类算法对人工数据进行了分析，现在本文会利用该算法对2005年中国24所高校综合实力进行分类，同时来验证蚁群聚类算法的实际应用效果。

下面是2005年中国24所高校综合实力数据集，见表 4-5，表4.5主要表示的是24个样本集合，每个样本集合都有其独特的属性，通过设置10只蚂蚁来对下列3个样本进行分析，迭代次数1000次。

表 4-52005年中国24所高校综合实力数据表：

指标 序号 1 清华大学 100.0 声誉得分 学术资源得分 93.1 学术成果得分 100.0 学生情况得分 100.0 教师资源得分 100.0 物资资源得分 100.0

本文来源：https://www.bwwdw.com/article/hch6.html