蚁群算法在Web挖掘聚类系统的设计与实现

基于蚁群算法的Web挖掘聚类系统的设计与实现摘要本文在研究现有Web挖掘中聚类技术的基础上，将一种改进的蚁群聚类算法应用于Web挖掘聚类系统中；并引入一种改进的蚁群算法应用于Web使用挖掘的用户事务聚类中。实验结果表明：与传统的聚类算法相比，基于蚂蚁的聚类算法在Web挖掘中具有一定的优势。本文首先针对Web挖掘的过程进行概述，然后详细地分析了Web挖掘中聚类和分类技术存在的优缺点。深入讨论了几种改进的蚁群算法，在分析了现有算法应用于Web挖掘技术上的不足之后，提出一种改进后的聚类算法并应用于Web挖掘聚类系统中，重新定义构造蚂蚁的方式、相似度和行为，通过仿真实验来对比传统的算法，来证明改进的算法对于Web聚类挖掘的适用性。最后，引入了一种改进的蚁群算法(ImprovedAntColonyAlgorithm,IACA),结合其聚类分析模型并对算法进行实现，将其应用到Web使用挖掘的聚类模型上。通过实验仿真，该聚类算法在聚类过程中，很好地解决了算法中停滞的问题，并且在全局优化方面表现出较好的性能。关键词：Web挖掘；蚁群算法；Web内容挖掘；Web使用挖掘；聚类ABSTRACTBasedonthestudyofexistingWebminingtheclusteringtechnologybasedonanimprovedantclusteringalgorithmwasappliedtoclassWebminingclusteringsystem;AndintroducingakindofimprovedantcolonyalgorithmisappliedtoWebusemininguseraffairsinclustering.Theexperimentalresultsshowthat:withthetraditionalclusteringalgorithm,basedontheantclusteringalgorithminWebmininghascertainadvantage.FirstlyWebminingprocessaresummarizedinthispaper,andthenanalyzedindetailintheWebminingtheclusteringandclassificationtechnologyandtheadvantagesanddisadvantagesoftheexisting.Furtherdiscussedseveralimprovedantcolonyalgorithm,theanalysisoftheexistingalgorithmappliedinWebminingtechnologyaftershortcomings,thispaperputsforwardaimprovedclusteringalgorithmandappliedinWebminingclustersystem,redefinestructureant'sway,thesimilarityandthebehavior,throughthesimulationexperimentstocomparedwiththetraditionalalgorithm,toprovethattheimprovedalgorithmforWebclusteringminingapplicability.Finally,weintroduceakindofImprovedAntColonyAlgorithm(ImprovedAntColonyAlgorithm,IACA),combinedwithitsclusteringanalysismodelandtheAlgorithmrealization,itsapplicationtoWebuseminingclusteringmodel.Throughtheexperimentalsimulation,thisclusteringalgorithmintheclusteringprocess,providesgoodsolutionalgorithmstagnationproblems,andintheaspectsofglobaloptimizationshowsgoodperformance.Keywords:WebMining;AntColonyAlgorithm;WebContentMining;WebUsageMining；Clustering同济大学硕/博士学位论文蚁群算法在Web挖掘聚类模型的设计与实现____________________________________________________________同济大学硕士学位论文摘要第二章基于蚁群算法的Web挖掘理论2.1Web挖掘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挖掘过程Web内容挖掘的基本过程Web内容挖掘的基本过程包括文本分析、文本解释、文档分类、文档可视化，它目的在于挖掘出基于用户需求的Web文本和多媒体信息，并对Web数据进行多样查询，提取其中无结构的动态文本进行集成、建模，最终实现知识发现。Web内容挖掘可以分为两类[10]：资源查找方法和数据库方法。Web使用挖掘的基本过程Web使用挖掘是对网络日志进行挖掘，从用户访问Web时留下的访问记录中挖掘出潜在的、有用信息的过程。其目的在于要发现用户留下的浏览模式和有用信息，这有利于开发Web的最大经济潜力，按照其分类规则，将Web使用挖掘分为数据预处理、模式识别和模式分析三个阶段，如图2.2所示：Web站点文件Web站点文件日志文件用户会话文件挖掘和模式感兴趣的规则和模式预处理挖掘模式分析图2.2Web使用挖掘过程(1)数据预处理数据预处理阶段是把从Web日志文件数据中获得的使用信息、内容信息和结构信息转换成数据抽象，并将符合用户模式实现的数据从Web日志文件数据源中发掘出来，对该类型的用户会话（事务数据库）应用挖掘算法，最终得到潜在的知识和有价值的模式的过程。数据预处理主要对日志文件进行数据收集、抽取、清洗、用户会话识别、事务模式分析等处理[11]。(2)模式识别识别的困难是由本地缓存和代理服务器造成的，当完成对用户事务的数据清理之后，开始执行模式访问阶段，目的在于使用Web挖掘技术发掘隐藏在数据背后的模式和规律，常用技术有：统计分析、关联规则发掘、生成序列模式、聚类和分类、依赖关系的建模。(3)模式分析由于挖掘出来的模式复杂且数量较大，需过滤掉在挖掘阶段得到的那些没有用的规则或模式，把有用的规则和模式转换为知识，这就要通过一些工具来辅助用户的理解。因此，近年来一些分析技术和工具的开发成为了Web使用挖掘研究的一个新热点。2.1.3Web挖掘技术聚类(1)基于模糊聚类算法的Web页面聚类[13]模糊集理论是Zadeh于1965年提出的，其定义如下：设为论域，若集合R是其上的一个模糊集，则有。是模糊集R的隶属函数，为的隶属度。在两个模糊集A与B上的运算有：应用模糊算法进行Web页面聚类时，主要就是构造页面间的模糊相似矩阵。定义Web访问用户集合，某一站点所有URL集合中可用用户访问情况表示为：，其中，，n表示用户数量。此时可建立页面间的模糊相似矩阵，矩阵中的元素值为：，因该矩阵为对称矩阵，所以在计算相似度时只取一半数据，以给定的阈值构造相似类。由于模糊矩阵不满足传递性，故只能得到含有公共元素的相似类而非等价类。具体而言：对于每一个,根据给定的阈值构造相似类会具有相同的元素。如，；即。此时将具有公共元素的相似类归并得到对应的等价类即为Web页面聚类的结果。将用户Ci用浏览子图的URL序列表示为：。建立客户相似矩阵：按页面聚类相同方法即可进行用户聚类。。分类1.基于页面文本与超文本结构信息的Web页面综合分类[16]因为基于Web页面文本和超文本结构信息的Web页面分类方法各有其特色，所以可将两者相结合提高分类结果。如文献[15]提出的二者取其最大值的方法，但该方法效果不是太明显。而范炎[16]等提出的利用贝叶斯方法将基于页面文本和超文本结构信息的分类视为两个相互独立的因素结合起来进行综合分类，即：(2.3)考虑到超文本结构分类中利用的单词远远少于页面文本分类，需要对不同方法分类结果加以预处理。(2.4)其中n是D中出现的不同单词数，即根据n值不同分别为不同的分类结果赋予不同的权重。实验表明在基于贝叶斯方法的分类中，综合分类的结果好于文本分类和超文本结构分类单独分类时5%以上，就正确率而言综合分类好于前者6.75%，较后者提高5.79%。2.基于页面文本的分类方法[14](1)基于贝叶斯方法的页面分类。在页面分类的诸多算法中贝叶斯分类方法的前提是：文本特征之间是相互独立的。贝叶斯方法与阈值大小来对文本数据进行划分：(2.5)其中指C类文档第i个特征，是从C类文本中得到特征词的概率，n值d中词的个数，m是系统词典的大小，若所得的阈值大于预先设定得值，则认为文本d属于C类，否则不是。从概率大小来研究，贝叶斯分类方法可描述为：设文档d的文档向量的分量为相应的特征词在该文档中出现的频度，则d属于C类文档的概率公式为：(2.6)(2.7)(2.7)是在C类文档中出现的条件概率的拉普拉斯概率估计，是C类文档中特征词出现的频率，是d类文档中特征词出现的频度，是文档中所包含的不同特征的总数目。(2)基于文档相似性的文档分类。基于文档相似性的文档分类方法并无贝叶斯方法所需的前提假设。使用文档表示矩阵间的夹角余弦值来表示它们之间的相似程度(2.8)：(2.8)2.1.4Web挖掘算法的关键问题(1)Rank算法[17]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.9)存在问题：PageRank是对Web整体分析，通过模拟在Web上的随机游动对每一个网页计算其PageRank值。因此该算法是独立于用户查询的，可以对用户要求产生快速的响应。HITS算法是对Web的局部分析，是根据特定的查询产生不同的根集，然后计算网页的anthority值和Hub值，该算法是依赖于用户查询的，实时性差。(2)HITS算法1999年Kleinberg提出了HITS（HypertextInducedTopicSearch）算法。HITS算法的内容如下：将查询q提交给普通的基于相似度的搜索引擎，搜索引擎返回很多页面，从中取前n个页面作为根集(Rootset)，用s表示。通过向s中加入被s引用的页面和引用s的页面将s扩展成一个更大的集合T，作为基本集(Baseset)。首先，为基本集中的每一个页面赋予一个非负的权威权重ap和非负的Hub权重hp，并将所有的a和h值初始为同一个常数。Hub与权威的权重可按如下公式进行迭代计算：(2.10)(2.11)存在问题：HITS算法存在“主题漂移”的现象，如用户在查询“量子物理学”时，由于算法中需要对初次检索结果的根集扩充成基集，最终的检索结果中会包含大量的有关“物理学”的站点。因此HITS适合与宽主题的查询，而PageRank则较好地克服了“主题漂移”的现象。2.2蚁群算法蚁群算法是一种模拟蚂蚁群体智能行为在图中寻找优化路径的仿生类优化算法,它由MarcoDorigo在92年提出，其思想来源于蚂蚁在寻找食物过程中发现路径的行为,当一只蚂蚁找到食物后，会在其走过的路上释放一种挥发性分泌物Pheromone（信息素，信息素浓度的大小表征路径的远近）[5]，蚂蚁在搜寻过程中能够感知信息素的存在和强度，并吸引其他蚂蚁过来，通过这种方式形成了信息素轨迹。2.2.1蚁群算法分析数学模型为了便于理解，通常引入蚁群算法求解平面上某个城市的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为目标城市的概率为：(2.12)也即，蚂蚁选中某一个城市的可能性是问题本身所提供的启发信息与从蚂蚁目前所在城市到目标城市路径上残留信息量的函数。为了避免残留信息过多引起的残留信息淹没启发信息的问题，在每一只蚂蚁完成对所有n个城市的访问后（也即一个循环结束后），必须对残留信息进行更新处理，模仿人类记忆的特点，对旧的信息进行削弱。同时，必须将最新的蚂蚁访问路径的信息加入。这样得到(2.13) 式中：残留信息的保留部分，1-表示在时段t到(t+1)内残留信息被削弱的部分，为了防止信息的无限累积，的取值范围必须在0到1之间； 第k个蚂蚁在时段t到(t+1)内，在i到j的路径上留下的残留信息浓度。 在文献[18]中,M.Dorigo介绍了的3种不同的实现方法，分别称为ant_cycle,ant_density,ant_quantity算法。对于前一种算法：(2.14)式中：Q是一个常量，用来表示蚂蚁完成一次完整的路径搜索后，所释放的信息素总量：Lk表示蚂蚁k在本次循环中所选择路径的总花费，它等于第k个蚂蚁经过的各段路径上所需的花费Cij的总和。2.2.2蚁群算法的改进几种典型的改进蚁群优化算法如下：1.天才蚂蚁算法天才蚂蚁算法[20]主要是针对AS算法进行改进而提出的一种算法。其调度策略如下：设定搜索中已有的最优解为，调度问题解空间中存在不同类型的待优化变量，在该路径上修改信息素轨迹，以增强正反馈效果，修改公式为：(2.16)其中的定义方法和以前设定的相同，e为调整影响权重的参数，所以由下式给出：(2.17)2.最大最小蚁群算法最大最小蚁群算法是由Hoos和stutzle等人提出的，较传统的蚁群算法有明显改动。（1）基本蚁群算法中各路径的信息量具有不确定性，为了避免这个缺陷，利用与蚁群算法运行过程相关的信息熵值表示选择过程的不确定性，将所有路径上的信息素浓度控制在一定的范围内，这样就可以实现蚁群算法的自适应调节。（2）所有路径上信息素浓度在初始化时已被定义为数值的上限值，同样设置一个较小的挥发系数，这样可以在算法开始的时候探索更多的路径。（3）当系统停滞或在一定时间内系统没有产生更好的解时，路径上的信息素被重新初始化，修改信息素的方法如下：(2.18)(2.19)(2.20)其中Cbest是已知最优路径的长度，Cib是本次循环中找到的最优路径的长度，Hoos等人经过试验证明，在求解小规模的问题时，计算路径上的信息素增量使用公式(2.20)，随着问题规模的增加，公式(2.19)使用的频率也增加。2.2.3蚁群算法的关键问题(1)搜索时间较长计算的复杂度主要体现在构造模型的过程中，随着问题规模的增大，算法消耗的时间也随之增加，通过这些参数信息交换能够向着最优路径进化，但是当群体规模较大时，很难在短时间内找出一条较好的路径。通过正反馈机制，使得较优路径上的信息量逐渐增加，需要在很长的一段时间后，才能使较优路径上的信息量明显高于其他路径。目前这方面的研究开始逐步走向深入[24]。(2)运行效率与全局收敛针对蚁群算法运行效率低下这一问题，曾先后提出了带精英策略的蚂蚁系统（ASelist）和基于优化排序的蚂蚁系统（ASrank）。虽然它们在运行效率方面取得一定的进展，但是同样也付出了容易收敛于局部最优解的代价。在它们之后，MMAS以及ACS针对上述问题进行了改进，扩展了蚁群的搜索空间，但是它们在效率方面同样也付出了代价。目前的研究是将注意力集中到将蚁群算法与其他智能仿生算法相结合。2.3小结首先介绍了Web挖掘的理论知识，包括分类、架构模型等。详细地论述了Web挖掘技术中的聚类和分类技术以及指出现阶段存在的关键问题。然后，对蚁群算法进行分析，介绍了几种常用的改进算法，系统地提出了当前蚁群算法研究热点问题。最后，对比几种现有改进的算法在Web挖掘技术上的应用，并给出了各自算法在应用中存在的优势和不足。第三章聚类模型分析与设计第三章聚类模型分析与设计聚类是将复杂的事物分门别类，并对陌生繁乱的事物进行归类总结，相同类别的事物采取类似的处理方法，这样就能大大提高事物的处理效率，通过自动聚类能够识别对象空间中不同密度空间的区域，从而发现全局分布模式，并结合蚁群算法的正反馈、鲁棒性、分布式计算等优点，对聚类模型进行设计。3.1聚类模型分析聚类分析在Web挖掘中是一个很重要的技术。聚类分析可以增强对象集的可理解性，并发现对象集中数据间共同的结构和联系，保持其有效性。即按照一定的规律和需求，将一些特殊分散的对象按照其相似性进行分类，并使得对象点的集合分成若干类，且每个类中的对象点最大程度地相似，各个类之间的对象点最大程度地不同。在聚类分析过程中没有涉及关于分类方面的知识，只是依靠对象点间的相似度作为划分类的依据，因此聚类分析是一种观察式学习，是利用数学方法研究和处理所给定对象的分类，其多元的统计分析方法是统计模式识别中非监督模式识别的重要分支。为了描述对象样本间的距离，特引入特征变量类型和相似性度量这2个概念。(1)特征变量类型为了描述一个对象样本，我们通常会对对象进行特征抽象化，使用多个特征指标变量来给予每个对象一个特征向量。特征指标变量可以分为：间隔标度变量、二次变量、序数变量，处理不同类型的特征指标变量则采取不同的策略。对于间隔标度变量是使用连续的实数来表示的数量信息，一个样本点可以看作是多维空间中的一点，通过一些特殊的运算来求解各个样本在空间上的距离。对于二元变量，用两种状态（0或1）来表示样本属性，1表示变量出现，0表示变量不出现，该变量特征也可以用来分类变量尺度，标记多状态。对于序数变量，它类似于分类变量，不用于分类变量的是，其状态时无序关系的，而分类的状态是有序的。对于这两种特征变量我们不能定义合适的数学运算，需要通过特殊变换后才能进行对象相似度计算。(2)相似性度量为了更好地描述对象集中的单个样本，需要样本类型中的特征指标变量提供度量值，同样为了描述样本间的相似特性，也需要定义能合理地衡量样本间相似程度，从而合理地进行聚类的度量，以便把相似的样本归为一类，非相似的样本归为不同的类。常用刻画样本间的相似性函数有2种，分别是：相似系数函数、距离函数。相似系数函数是用来描述样本点特征性质之间的相似程度，当相似系数值越接近0时，说明两个对象样本越不相似，当相反相似系数值越接近1，则说明两个对象越相似，这才可以将它们归为一类。距离函数指的是对象样本间的距离，对于含有N个属性的样本对象来说，我们可以将每个样本点看作是N维空间中的一个点，然后使用某种距离来表示样本对象点之间的相似性，对象样本点越相似，则样本点之间的距离越小，可以将它们归为一类；对象样本点差异越大，则两者间的距离越大，就不能归为一类。3.2聚类模型设计聚类首先要做的是对样本对象的特征抽取，它所处理的对象是样本数据集，由于实际应用中的样本数据对象一般都有多种特征，要具体选取哪种特征才可以正确地描述样本对象的本质和结构对于聚类分析来说至关重要。特征抽取的结果是输出一个矩阵，每一行对应的是一个样本对象，而每一列对应的是一个特征变量。特征的抽取是另一个重要步骤，对后续的分析和决策有直接的影响。如果抽取的特征变量只是样本对象中不重要的属性，对这些无关紧要的属性进行聚类分析出的结果肯定也达不到预期的效果，因为当使用错误的特征属性来解释对象时，容易扭曲样本对象，再对这样的样本对象进行的聚类分析，即便是用最好的聚类算法来对其处理，结果也是不正确的。总结蚁群算法和聚类分析的特点，引入了一种改进的蚁群算法(ImprovedAntColonyAlgorithm，IACA)。并将其运用到Web的用户聚类上，聚类模型如下：1.初始化设定设有M个模式样本、K个模式分类，N是表示为几个样本对象；初始状态将M个样本随机分配到N个聚类中心，K表示分类出K个等级，每个模式样本是一个D维向量，定义模式样本。设聚类中心为，则目标函数表示为：(3.7)2.信息素更新计算蚂蚁的各自初始聚类中心（第k个蚂蚁将模式样本i分配到第j个聚类中心）和初始目标函数，初始化各蚂蚁的样本到各聚类中心的信息素浓度，信息素浓度更新公式为：(3.8)其中是信息素增量,是信息素强度的持久性系数（算法中1-表示信息素挥发度）。初始化，蚂蚁将M个样本随机分配到K个聚类中心初始化，蚂蚁将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的取值也很重要，取值不恰当容易使解陷入局部收敛，算法需要在稳定性和求解速度上取得平衡。3.3聚类算法源代码设计部分不要用大篇幅伪码，用流程图更好些设计部分不要用大篇幅伪码，用流程图更好些算法采用vb语言实现，整个算法的伪代码伪代码和源码是两个概念如下：伪代码和源码是两个概念DimhaveResult‘是否已经搜索出结果的标志dimMinT‘目标函数的最小值DimAntNum‘最后分类结果的蚂蚁序号Forak=1toM‘初始化Initialization(ak)'初始化蚂蚁种群中每只蚂蚁的各个样本随机分配到K个模式分类中的某个类别ClusterCenter(ak)‘计算初始时第ak只蚂蚁的K个聚类中心Distance(ak,0)’计算初始时第ak只蚂蚁的每个模式样本到聚类中心的距离以及第ak只蚂蚁的目标函数Ifak=1then‘目标函数最小值开始为初始值的最小值MinT=T(ak,0)ElseIfT(ak,0)<MinTthen‘找到所有蚂蚁当中最小的目标函数值MinT=T(ak,0)EndifEndifAST=5*Q/MinT‘定义蚂蚁的绝对感觉阈限NextInfomation(0)’初始化每只蚂蚁在各条路径上的信息素浓度CST=0.02*T(ak,0)‘定义蚂蚁的差别感觉阈限‘蚂蚁开始对N个样本进行分类Forh=1toL ‘总共进行L次搜索Forak=1toM‘M只蚂蚁分别聚类Clustering(ak)‘第ak只蚂蚁根据(5)式对每个样本进行聚类ClusterCenter(ak)‘计算第ak只蚂蚁的K个聚类中心Distance(ak,h)’计算第ak只蚂蚁的每个模式样本到聚类中心距离以及第ak只蚂蚁的目标函数Ifabs(T(ak,h)-T(ak,h-1))/T(ak,h-1)<ethenhaveResult=1‘存在满足条件的结果ifT(ak,h)<MinTthenMinT=T(ak,h)‘寻找所有蚂蚁中目标函数的最小值AntNum=akEndifEndifNextInfomation(h)’第h次搜索完成后更新每只蚂蚁在各条路径上的信息素浓度IfhaveResult=1then‘表明蚂蚁已经搜索到了解Fori=1toN‘打印出每个样本所属的类别Forj=1toKIfS(AntNum,i,j)=1thenResponse.write“第”&i&“个样本所属类别为第”&j&“类；”&vbCRLFEndifNextnextExitfor‘算法结束EndifNext3.4小结本章总结了聚类技术在Web挖掘中的重要性，认真分析了聚类模型的几种类型，并详细地论述了基于蚁群算法的聚类模型设计。第四章蚁群算法在Web挖掘聚类上的实现第四章基于改进的蚁群算法在Web内容挖掘聚类上的实现4.1基于改进的ACA的路由算法算法实现细节？改进原因与结果？算法实现细节？改进原因与结果？本算法的关键之处在于对蚁群算法中状态转移规则的启发量的设置。在TSP问题中，启发量的设置比较简单，为距离的倒数，而在QoS路由选择中，启发量的设置就比较复杂，也比较重要，因为这直接决定了蚂蚁寻路的规则。文中提出了一种新的启发量的设置方法，即在n，b两点之间的启发量η(a，b)设置为|A*COST(a，b)+B*DEIAY(a，b)+B*NODEDELAY(b)+C*LOST(b)|的倒数，其中，COST(a,b)表示a和b两点之间的费用，DELAY(a,b)表示a和b两点之间的延时，NODEDELAY(b)表示b点的节点延时，LOST(b)表示节点b的分组丢失率。A，B，C均为常数，其赋值有两个原则，一是调整各个约束条件之间的数量级，使其处于可比的状态，二是可以适当加大需重点考虑的QoS值的系数，比如算法对延时比较敏感，则可加大B的赋值，使其比重加大，从上面的设置可以看出，当η(a，b)越大，则a和b两点之间的费用、延时等就越小，符合QoS选路的原则。而在蚁群算法的信息素全局和局部更新规则中，△r均设为常数，经过多次比较，在全局更新规则中，△r设为10，在局部更新规则中，△r设为1。蚁群算法中的β，p，q0等参数由免疫算法的抗体产生。4.2Web内容挖掘聚类由于Web页面中包含了很多文本、图片、音频、视频等类型的信息。这些Web数据经过数据清理、特征抽取等数据预处理后得到数据集，由于Web页面中的内容非常丰富，这样增大了该算法的搜索空间，即系统接收的是一个特征向量矩阵，每一行代表的是一个样本对象，根据上述得到的规则进行系统设计，这样就可以大大提高算法的效率[36]。电子商务的快速增长已令商界和消费者双方均面临着新的形势。由于激烈的竞争，客户可以选择从几个备选方案挑选最合适的需求，同时商业社会也意识到需要具备聪明的营销策略和关系管理。Web使用挖掘试图发现有用的知识，并从次要数据中获得用户与Web的交互。Web使用挖掘已成为有效网站管理、创建自适应网站、商业和服务支援，个性化，网络交通流分析等等非常关键的功能。研究蚁群行为和他们的自组织能力能更系统地对感兴趣的知识进行检索/管理，因为它提供了模型分布式自适应组织，这对困难的解决优化、分类和分布控制等[17][18][16]起着非常重要的作用。本文中，我们提出的蚁群聚类算法来发现Web使用模式（数据集群）和一个线性基因编程方法来分析访问者的浏览趋势。实证结果清楚地表明，虽然对比改进的模糊聚类的[11]方法时，性能的精度并不高效，但是对比自组织地图（为Web使用模式聚类），蚁群聚类的性能更优。4.2.1数据清理由于Web数据具有异构、动态等特性，海量的数据导致Web数据呈现杂乱、冗余等问题，这些有问题的数据时常会误导聚类分析，给聚类结果带来不利的影响，因此在进行挖掘之前必须对数据进行清理工作。举例说明一下数据清理的过程，Web日志文件中历史记录如下：26—[06/Nov/2012:20:30:15+0800]”GET/2009/2009tdsh/home.htmHTTP/1.1”2002035从该条记录可以看出，由IP为26的主机发出请求，且访问Web的时间为2012年11月06日晚上8点30分15秒，+0800表示访问的服务器位于第八区，访问的方法为获取”GET”，请求的内容的是/2009/2009tdsh/home.htm，所用的协议为HTTP1.1，200表示请求成功，是服务器执行该请求的结果标记代码，2035表示浏览网页请求的字节数大小。按照要求，进行数据清理的步骤如下：(1)首先对网页的地址，如“GET/login?type=%id=%name=”的记录进行删除，因为这种记录只应用于页面的刷新，对聚类没有影响。(2)其次将页面地址“GET/HTTP/1.1”的记录删除，因为这种记录只是访问页面时使用的协议，对聚类没有影响。(3)再将字节数为0的记录删除，因为这种记录为用户发起的请求且从页面上未获得任何信息，对聚类无影响。(4)再将网页地址中后缀名为gif、jpg、mp3、mp4等的记录删除，因为这些图形、音/视频文件是用户访问页面时自动下载的，不能反映用户的兴趣。根据以上步骤完成Web数据的清理后，接下去进行特征提取操作，从清理后的数据中提取出合适的特征向量，并对每一条记录定义一个定量的描述，向Web挖掘聚类提供向量矩阵。4.2.2特征提取特征属性的提取直接影响到用户想通过聚类来获取什么样的信息，针对Web站点上用户的访问时间和浏览页面记录信息进行聚类，定义用户的IP地址、访问时间和访问页面URL三个属性作为Web日志数据的特征属性。特征属性中用户的IP、访问时间以及页面URL的表现形式为Web文本字符串，所以首先需要将其转换为实数。然后当完成数据转换并进行特征提取操作以后，抽象Web数据为一个数据矩阵，把这个数据矩阵作为源数据应用于Web聚类系统。根据特征提取的思想获得一些数据矩阵具有能使规则有效性得到最大提升，这样的操作思想即为这个蚁群聚类算法得到的最优规则。现有的特征子集选取算法一般是构造一个评价函数，对特征集中的每一个特征进行评估，然后根据其评估得分的大小对其进行排序，选取预定数目的最佳特征作为备用的特征子集。1、把文本表示成带权重的信息的词项向量，50年代就已经提出了，这种思想正是向量空间模型的所在。2、在向量空间模型中，t1tn是N维的坐标系。w1(d)wn(d)为相应的坐标值。因而文本d被看成N维空间中的一个规范化特征矢量，为了简化可以不考虑tk在文本中的顺序及相互关系。其中wk(d)为tk在文本D中的权重。计算方法为：TF乘以IDF，TermFrequency,InverseDocumentFrequency.1)词频：特征词在文本中出现的频率。2)倒排文档频率：特征词在文本集中分布情况的量化。特征词在文本集中出现的频度。工式：lg(N/nk+0.01):其中N是文本总数，nk是出现该特征词的文本数。3)归一化因子：对文本向量的各个分量进行标准化，使得具有相同匹配特征数的文本，短文本比长的重要W(t,d)为词t在文本d中的权重TF(t,d)为词在文本d中的词频N为训练文本总数nk为训练文本集中出现t的文本数4)在计算权重前应先去除停止词。词条与权重构成特征向量。4.2.3相似度计算 会话是指用户访问web服务器的浏览行为，用会话相似度来衡量，亦即2次回话浏览行为的相似程度。如果2次会话浏览的网页相同并且对多个网页浏览的顺序（浏览路径）相同，那么这2次会话的浏览行为相同。任意两次会话p和q的相似度的计算步骤为：（1）设网站上有效URL的总数为n，网站的每一URL指定一个唯一的数字j={1,2,3…,n}，用户的任意一次网页浏览行为用一个n维的布尔浏览向量T(p)表示，向量元素tj(p)定义为：（2）若已知会话p和会话q的网页浏览向量分别为T(p)和T(q)，并完全忽略网站的分层组织，则两次会话浏览网页的相似度为：（3）若会话p和会话q的网页浏览路径分别是k，r个浏览页排序而成，并分别用1,2,3….,k和1,2,3…,r进行编号，会话p和会话q的网页浏览路径差异用一个m维的布尔向量S(p,q)表示，取m=min{k,r}，且向量元素Sk(p,q)定义为：（4）会话p和会话q的浏览路径相似度为：（5）会话p和会话q的浏览行为相似度为：相似度Comp(p,q)不仅衡量了任意2次会话p和会话q浏览多个网页的相似程度而且衡量了会话p和会话q对这多个网页的浏览顺序的相似度，即衡量了这2次会话的浏览行为的相似程度。4.2.4浏览模式的挖掘方法我们把浏览行为比较类似的会话归类为一种浏览模式。在对大量会话样本的浏览行为计算彼此之间的相似度的基础上，采用聚类分析方法进行归类，从而挖掘出若干种浏览模式。我们采用基于密度聚类算法把浏览行为聚类，聚类算法的步骤为：计算会话p与会话q的距离函数D(p,q)：对会话样本空间中的所有会话行为进行聚类，对样本空间中的会话点p指定ε-邻域为：该领域中的所有会话q的浏览行为被归类为一种浏览模式p。可以通过指定邻域包含的会话点数|A,(q)|应满足最少点数MinPts来确定ε的值，即有，通过对会话样本空间的聚类实验，我们认为取MinPts=15或ε=0.55比较适宜。将邻域A,(q)中的所有会话点从会话样本空间中删除。若样本空间为空或者没有任何点存在ε邻域，则重复步骤（2）；否则，转步骤（3）。会话样本空间中还留下的会话点被确认为噪声会话模式，即不属于任何孤立的会话模式。4.3算法分析不要缩写，文中提到的算法好几个，在这里具体是哪个算法？不要缩写，文中提到的算法好几个，在这里具体是哪个算法？算法步骤如下：(1)随机产生20条21位0l二进制编码染色体作为初始抗体库。(2)进行初始化，读入网络拓扑及QoS信息，产生包含20只蚂蚁的蚁群。(3)从染色体库中按顺序取出一条染色体，产生相应的蚂蚁算法的参数，设置各边信息量的初始值，采用蚁群算法开始寻找指定源节点和目的节点之间的最优路由。当一只蚂蚁成功地完成路由选择后，判断该路由是否满足QoS约束条件，对这只蚂蚁选择的路由的各路径上的信息素根据局部更新规则进行更新。(4)当20只蚂蚁都完成寻径后，对当前满足Q。S约束的最优路径上的信息素按照全局信息素规则进行更新。如没有，则说明没找到满足QoS的路由。(5)对该蚁群进行50次迭代寻径，计算当前染色体的适应度值。(6)对步骤(3)到(5)重复进行，直到2O条染色体全部使用过一遍。(7)对20条染色体的适应度值进行排序、交叉、变异以及基于亲和度的群体更新，产生新一代20条染色体，返回步骤(3)进行寻径。循环若干次后算法结束。4.3.1算法实现根据改进后算法的原理，使用C++实现如下所示:double

rnd(intlow,doubleuper)

{

doublep=(rand()/(double)RAND_MAX)*((uper)-(low))+(low);return(p);

};

intrnd(intuper)

{

return(rand()%uper);

};classGInfo

{

public:

doublem_dDeltTrial[iCityCount][iCityCount];

doublem_dTrial[iCityCount][iCityCount];

doubledistance[iCityCount][iCityCount];

};

intant::ChooseNextCity()

{

//Updatetheprobabilityofpathselection

//selectapathfromtabu[m_iCityCount-1]tonext

inti;

intj=10000;

doubletemp=0;

intcurCity=tabu[m_iCityCount-1];

for(i=0;i<iCityCount;i++)

{

if((AllowedCity[i]==1))

{

temp+=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);

}

}

doublesel=0;

for(i=0;i<iCityCount;i++)

{

if((AllowedCity[i]==1))

{

prob[i]=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha)/temp;

sel+=prob[i];

}

else

prob[i]=0;

}if(j==10000)

{

temp=-1;

for(i=0;i<iCityCount;i++)

{

if((AllowedCity[i]==1))

if(temp<pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha))

{

temp=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);

j=i;

}

}

}

returnj;}

voidant::UpdateResult()

{

//Updatethelengthoftour

inti;

for(i=0;i<iCityCount-1;i++)

m_dLength+=Map.distance[tabu[i]][tabu[i+1]];

m_dLength+=Map.distance[tabu[iCityCount-1]][tabu[0]];

}

voidant::move()

{

//theantmovetonexttownandaddtownIDtotabu.

intj;

j=ChooseNextCity();

addcity(j);

}

classproject

{

public:for(i=0;i<iAntCount;i++)

{

for(j=0;j<iCityCount-1;j++)

{

Map.m_dDeltTrial[ants[i].tabu[j]][ants[i].tabu[j+1]]+=Q/ants[i].m_dLength;

Map.m_dDeltTrial[ants[i].tabu[j+1]][ants[i].tabu[j]]+=Q/ants[i].m_dLength;

}

Map.m_dDeltTrial[ants[i].tabu[iCityCount-1]][ants[i].tabu[0]]+=Q/ants[i].m_dLength;

Map.m_dDeltTrial[ants[i].tabu[0]][ants[i].tabu[iCityCount-1]]+=Q/ants[i].m_dLength;

}

for(i=0;i<iCityCount;i++)

{

for(j=0;j<iCityCount;j++)

{

Map.m_dTrial[i][j]=(rou*Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j]);

Map.m_dDeltTrial[i][j]=0;

}

}

voidproject::initmap()

{

inti;

intj;

for(i=0;i<iCityCount;i++)

for(j=0;j<iCityCount;j++)

{

Map.m_dTrial[i][j]=1;

Map.m_dDeltTrial[i][j]=0;

}

ifstreamin("eil51.tsp");

structcity

{

intnum;

intx;

int

y;

}cc[iCityCount];

for(inti=0;i<iCityCount;i++)

{

in>>cc[i].num>>cc[i].x>>cc[i].y;

besttour[i]=0;

}

intj;

for(i=0;i<iCityCount;i++)

for(j=0;j<iCityCount;j++)

{

{

Map.distance[i][j]=sqrt(pow((cc[i].x-cc[j].x),2)+pow((cc[i].y-cc[j].y),2));

}

}4.3.2实验环境软件环境：Web挖掘聚类系统的开发环境：WindowsXP、C++编译环境下完成。硬件环境：CPU：Intel酷睿双核1.5GHz内存：1GB硬盘：160GB显卡：NVIDIAGeForce5600MGS4.3.3实验结果最好有你的改进后算法和没改进或者和其他算法的比较，目前比较对象过于单一，为什么选择C5.0？这样更有说服力最好有你的改进后算法和没改进或者和其他算法的比较，目前比较对象过于单一，为什么选择C5.0？这样更有说服力仿真实验的原始数据采用美国密歇根大学机器学习数据库，选择的是经典聚类分析数据集，通过运行蚁群聚类算法，分析该算法在Web聚类上的结果，从中得到算法的性能参数，从而对该算法的性能和实用性进行分析，说明改进后的算法优于先前算法。设定网站上有效URL的总数为7，网站的每一个URL指定一个唯一的数字{1,2,3,4,5,6,7}，其网页组织结构图如图所示。图4.1流程图现有三个用户的一次网页浏览行为的布尔浏览向量T(1)、T(2)和T(3)分别表示为（1,1,1,0,1,0,0）-1，（1,1,1,0,0,1,0）-1和（1,1,1,0,1,0,0）-1，则则类似可以得到D(1,2)、D(1,3)和D(2,3)均小于0.55，说明这三个用户的访问行为相似且可归为同一个浏览模式。表4.1聚类系统实验结果（聚类簇号）TestSetAccuracyRate(%)12345678910MeanRateSimplicityAnt_Miner376.270.272.479.268.577.279.873.771.473.874.24.8C5.074.670.173.669.672.377.276.477.670.472.673.313.1在这次仿真实验中，结果证明了上述理论分析的正确性。通过大量反复的实验比较，发现改进后的算法在迭代了15000次后，就已经能达到或超越传统的蚁群算法迭代1000000次的效果，传统算法形成的聚类簇中，并不纯正，在同一个聚类簇中含有不同分类的样本对象。而改进的算法聚类簇比较纯正，并采取了距离度量相结合的策略，提高了聚类的精度。从中可以看出，改进后的算法在大大减少迭代次数提高算法效率的同时，还在一定程度上改善了Web聚类挖掘效果。4.4小结本章主要介绍了基于蚁群算法的Web页面分类模型[41]，并将其运用于Web内容挖掘中。Ant_Miner3分类算法实质上是一种序列覆盖算法：蚁群搜索到一条规则，移去他覆盖的样例，再重复这一过程，从而得到共同覆盖样例的一组规则。由于Web文档结构的特殊性，在本实验中，采用了文本预处理技术来对Web页面进行消歧和抽取词干。这样，经过处理后的文档的属性维度得到大大减小，算法的搜索空间也变的更小。经采取10维的实验交叉验证，并采用标准的质量评估预测分类规则质量，并同传统的分类算法C5.0就正确率和简洁性进行了对比。结果显示：在处理小数据量时，Ant_Miner3算法能够发现更好的分类规则，以及得出更简单的规则。第五章蚁群IACA算法在Web使用挖掘的聚类模型实现57第五章基于改进的蚁群算法在Web使用挖掘的聚类模型实现Web挖掘有其独有的特性，比传统的数据挖掘数据量大，数据结构表现为无序、结构复杂等特点。传统的聚类算法要求用户提供先验信息（聚类类别或其他参数等），使得传统聚类算法结果对输入参数较为敏感，降低了算法的适用性。针对这一问题，引入一种新的解决方案，源于每个用户在浏览Web时表现出来的特征不同。本文提出一种改进的蚁群聚类算法并应用在Web使用挖掘的用户聚类上，该蚁群聚类算法不需要用户输入先验信息，改善了聚类结果并减轻了用户负担，实验表明该算法在Web使用挖掘的聚类结果中更准确。5.1改进的蚁群算法(IACA)介绍由于传统的蚁群聚类算法在实现时过度依赖输入参数、搜索过程中停滞、以及算法的适用性不高等问题，本文引入一种改进的蚁群算法(ImprovedAntColonyAlgorithm,IACA)[42]，克服了传统蚁群算法以上的缺点。它吸收了前人提出的具有感觉和知觉特性的蚁群算法[22]和具有随机扰动的蚁群算法[19]的优点，并结合了聚类分析的实际情况。其算法原理如下：(1)信息素更新：引入随机扰动策略定义一个蚂蚁种群M并让M只蚂蚁开始搜索，如果第m只蚂蚁将第n个成员分类到第k类中，则在第m只蚂蚁的第nk路径上更新较大的信息素浓度，设置标志，其他蚂蚁在nk路径上的信息素浓度也受到第m只蚂蚁的影响。由于蚂蚁之间的相互影响，会产生一个影响程度，信息素浓度会随着影响度的增加而增加。初始化每条路径上的信息素浓度，每条路径上的信息素浓度就会随着蚂蚁的不断搜索而更新。当完成一次路径搜索后，会对各蚂蚁在其路径上的信息素浓度进行更新，得到信息素增量公式为：(5.1)其中：Q表示正常数，=1时，表示第h次的时候，第k只蚂蚁将第i个模式样本分类到第j类，反之=0；(0<<1)表示其他蚂蚁对蚂蚁k的影响程度。表示第h次的时候，第k只蚂蚁完成所有样本分类以后，各样本到各聚类中心的距离之和，由公式(3.2)计算。算法为了避免大量无效的搜索导致系统停滞的问题，提出随机扰动策略，并引入可变的扰动因子，系统可跳出局部最优。随机扰动策略由公式(5.2)来表示，为了防止最优的路径被漏选。(5.2)其中，s表示对应的城市，为扰动因子，P是(0,1)中均匀分布的随机数。由公式得出：蚂蚁在某次迭代过程中有多种选择路径，除了信息素浓度最大的那条路径的选择外，其他路径都采用随机选择方式；而对信息素浓度最大的那条路径选择时，使用转移的概率公式来选择。该公式将蚂蚁的随机选择和确定性选择相结合，随机选择使计算转移系数具有较强随机性，确定性选择使蚂蚁得到转移系数最大的路径，结合二者的优点，可使得IACA改进算法具有更好的全局搜素能力。 (2)蚂蚁选择路径：引入蚂蚁的自身感觉和知觉特性，蚂蚁在选择路径的时候，需对三个阈值来进行比较，分别是：蚂蚁的绝对感觉阈限AST、差别感觉阈限CST以及极限信息素浓度，将信息素浓度为分别与这三个阈值进行比较来确定路径的选择。由此得出则路径选择方式为：(5.3)5.2Web使用挖掘聚类模型用户事务是指从Web用户访问访问时留下的服务器日志、注册信息以及沿某一方向的最大向前引用路径中挖掘出的访问模式。主要步骤如下：5.2.1Web事务识别定义首先我们采用基于支持度的滤波方法来实现，目的在于过滤掉不频繁的用户事务模式。在Web日志预处理阶段，根据用户的兴趣度算法来计算每个用户事务模式的支持度，设定一个门限值，提高了聚类结果的准确性。同时，改进了数据预处理过程，删除了异常用户访问Web页面的访问记录以及该用户模式中包含的非频繁用户事务模式的URL。经过用户事务预处理，大量非频繁的用户事务模式被过滤掉且减少了用户事务模式特征矢量的维数，减轻了数据挖掘的任务。用于聚类用户事务集合，提高聚类结果的准确性。第二项预处理任务是Web事务识别。在对web访问记录进行挖掘之前，必须进行事务标识的工作。一次用户会话(usersession)是指某个用户对于一个web站点的一次访问过程中所引用到的全部页面，事务标识是将一次用户会话分割成多个逻辑单元，事务和会话的区别在于事务的大小是可变的，从一个页面到某个会话的全部页面，决定于所定义的粒度;和通常的数据库管理系统不同，这种粒度的定义是不明确的。5.2.2用户浏览行为模型为了将用户会话分解为有意义的事务，需要有一个潜在的模型支持它。用户访问访问一个web页面一般是出于如下两种目的之一:一是为了导航目的，二是需要其内容信息。我们分别称之为相对于该用户的导航页面和内容页面。尽管通过web页面中链接的数目或许可以容易地判定某些页面的性质，然而大多数页面是无法通过该方法被清楚归为某一类的。例如，一个仅包含了标题和一串链接列表的网页可以认定是导航页面，而一个既包含了文本信息又包含了链接的页面则无法仅依据其自身信息就认定其是导航页面还是内容页面，因为针对不同的用户，它们的页面性质可能也随之变化。根据导航页面和内容页面的概念，我们可以给出事务的定义。事务的定义根据应用的不同可分为两种，通常对事务的定义是某个用户在一个站点的一次访问过程中，从一系列的导航页面到内容页面的引用。对于此类导航一内容事务的挖掘可以得到通向某个内容页面的常用路径。另一个事务的定义是某个用户在一个站点的一次访问过程中，对所有内容页面的引用，即对一次用户会话删除了所有的导航页面后产生的页面序列;对于此类内容事务的挖掘可以得到web站点上内容页面之间的联系，这种联系与这些内容页面之间的路径信息无关。内容事务的挖掘对应于导航一内容事务挖掘的事务间分析，但是因为它省略了导航信息，所以可以得到一些导航一内容事务挖掘所得不到的用户特性。无论何种事务定义，其关键问题在于如何才能够动态确定一条服务器记录是出于导航目的还是内容浏览目的。5.2.3具体分析模型相似度将直接决定聚类的效果，因此在对用户事务进行聚类之前，必须给出用户事务相似性的定义。首先将用户事务转化成标称数据。假设T为用户事务模式集，m表示用户事务模式数，每个用户事务可表示成二进制向量的形式：，N是站点中有效的URL的总数，用户的任意一次网页浏览行为可用一个n维的布尔向量表示：(5.4)通过公式(5.4)将用户事务数据转化为标称数据。假设某用户事务访问的页面为A->B->D，网站的页面向量为(A,B,C,D,E)，则可将用户事务表示为(1,1,0,1,0)的标称数据形式。由于每个用户对Web站点都是通过其访问兴趣来访问，因此形成了一种有序关系。当这两个用户事务对多个网页浏览的顺序相同、这几个网页的访问类型相同，以及浏览网页的数量相同。所以就浏览行为来看，两个用户事务行为相同，通过取二者的平均值来衡量这两个用户事务间的相似度。任意两个用户事务和的相似度计算步骤如下:(1)若已知用户事务和的网页浏览向量分别为和，用户事务相似度计算采用公式(5.5)的余弦测度法来计算。(5.5)(2)若用户事务和的网页浏览路径分别是由p、q个页面排序而成，并分别用1,2,3,…,p和1,2,3,…,q进行编号，用户事务和的网页浏览路径差异用一个m维的布尔向量表示，取，向量元素定义为：(5.6)其中k=1,2,3,…,m(3)计算用户事务和的浏览路径相似度：(5.7)(4)计算用户事务和的浏览行为相似度：(5.8)相似度不仅衡量了任意两个用户事务和浏览多个网页的相似程度，而且衡量了用户事务和对这多个网页的浏览顺序的相似度，即衡量了这两个用户事务的浏览行为的相似度。为了提高该聚类算法的运算速度，在进行聚类之前，可首先计算所有用户事务间的相似度，并把它们存储在事务相似度矩阵R中,见公式(5.9)。(5.9)其中m表示用户事务的个数，表示事务和的相似度。由于事务间的相似关系具有对称和自反的性质，因此有=，且。5.3算法分析5.3.1流程分析本文的算法原理是指在总结了蚁群算法和K-均值算法在实现优化排列问题和聚类分析问题的基础上，引入随机扰动策略和蚂蚁仿生学特性，从而提出的改进蚁群算法(IACA)，用于实现Web使用挖掘上用户事务的聚类，并将该模型用算法来实现，具体流程如下：具体算法流程为：(1)给定一个精度以及总的搜索次数L。初始状态，让蚂蚁种群中M只蚂蚁的每一只都将N个模式样本随机分配各自的K个模式分类，根据分配结果并引入K均值算法[33]，计算蚂蚁各自的初始聚类中心，然后根据公式(3.2)计算每个蚂蚁的初始目标函数。并根据各自的随机分配结果初始化各蚂蚁的样本到各聚类中心的信息素浓度，其中Q为一正常数，表示第k只蚂蚁将第i个员工分类到第j类，否则。各个蚂蚁的绝对感觉阈限，其中C为常数，根据前面的阐述，这里我们取C＝5（表明感觉阈限是初始信息素浓度的5倍），差别感觉阈限。(2)蚂蚁群中M只蚂蚁分别对N个样本进行K个模式分类，每只蚂蚁的每次分配均按公式(5.3)将第i个样本分配到第j类，待所有的样本都已经分配完成之后，下一只蚂蚁按照同样的方式对样本进行分类。当所有的蚂蚁都已经分配完成后，则表明一个搜索周期完成。(3)一个搜索周期完成后，按公式(3.3)更新信息素浓度，并引入随机扰动公式(5.2)调整的信息素浓度。(4)根据公式(3.2)计算每只蚂蚁各自的目标函数更新并调整信息素,根据K均值算法计算出新的聚类中心，同时将已搜索次数h加1(h=h+1)。若在M只蚂蚁中满足，则选择min()即最小的值并输出分类结果，否则将搜索次数h与固定阈值L比较,如果已搜索次数h>=L，则输出结果；如果已搜索次数h<L，则在步骤(4)聚类的基础上转步骤(2)继续搜索更优的解。5.3.2算法实现同第四章问题同第四章问题根据上述描述改进算法的原理，采用Matlab语言实现，算法的伪代码如下：以下是具体代码实现算法/*初始化样本*/For样本集中的每一个样本对象alphado随机将tao投影到二维网格空间中EndFor/*主循环迭代*/function[y,val]=QACSticloadatt48att48;最大循环次数MAXIT=300;城市个数NC=50;产生一个0到1之间的随机数taotao=ones(50,50);rho=0.3;alpha=2;beta=3;IfPm>Prdo Ai随机移动区域中没有被样本对象占用的网格EndIfQ=200;mant=30;iter=1;fori=1:NCforj=1:NCdistance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2);endendIf循环次数是50的倍数do计算第一种行为蚂蚁的占所有蚂蚁的比重bestroutebestroute=zeros(1,50);routelength=inf;EndIfforite=1:MAXITforka=1:mantdeltatao=zeros(50,50);[routek,lengthk]=travel(distance,tao,alpha,beta);iflengthk<routelengthbestroute=routek;endfori=1:NC-1deltatao(routek(i),routek(i+1))=deltatao(routek(i),routek(i+1))+Q/lengthk;enddeltatao(routek(50),1)=deltatao(routek(50),1)+Q/lengthk;endfori=1:NC-1 迭代次数i+1forj=i+1:NCifdeltatao(i,j)==0deltatao(i,j)=deltatao(j,i);endendendtao=(1-rho).*tao+deltatao;endy=bestroute;val=routelength;toc/*主循环迭代*/For所有的样本对象doEndFor/*算法结束*/5.3.3实验结果数据预处理：提取了新浪网的Web服务器站点的日志数据作为实验数据,在这些实验数据中包含了2,713,124条数据记录。进行数据清理后,还有141,361条数据,其中包含985个不同的网页。分别得出了23,685个用户、35,452个会话、56,231个用户事务。测试环境:Matlab实现算法。实验条件为AMDAthlon(tm)x2250uProcessor，2G内存，操作系统为Windows7。500个用户事务,200个URL，抽取其中30个用户事务用来测试，见表5.1表5.1用户事务表编号用户事务编号用户事务1p16,p20,p21,p25,p2316p23,p20,p16,p21,p372p28,p19,p2217p17,p48,p39,p593p19,p22,p2818p16,p20,p21,p23,p254p17,p48,p8019p45,p17,p395p17,p39,p5920p17,p39,p456p35,p36,p3721p36,p35,p347p15,p19,p20,p2222p35,p36,p378p16,p40,p5123p16,p38,p58,p789p41,p53,p1724p35,p37,p36,p17210p36,p34,p3525p29,p127,p9111p24,p45,p29,p7226p17,p48,p39,p4512p53,p17,p4127p48,p95,p13313p98,p128,p2928P20,p54,p56,p6514p19,p64,p5529p72,p45,p29,p6315p45,p29,p7230p54,p56,p65经过改进算法聚类的结果为：{7,22,11,20,24}、{21,17,19,26,6}、{2,6,18,8,23}、{3,9,10,13}、{4,14,25}、{12,28,31}、{14,29,27}、{30}，聚类结果正确。在实验过程中，同时对以下算法也进行了50次聚类实验，并对聚类的结果进行比较，得出的实验结果如下：表5.2算法对比表算法K-均值算法FCM基本蚁群算法IACA算法正确率85.4%87.6689.9%93.8%计算时间322s309s280s259s由表5.2可得出：IACA算法在Web的用户聚类效果上，较其它算法，在正确率以及时间上都具有一定的优势。5.4小结传统的聚类算法对于初始值的设定很敏感，初始值的设定直接影响最终结果，也导致了聚类结果会存在较大的差异，但是蚁群算法的聚类结果并不依赖于初始值的设定。从实验结果可以看出，改进的IACA算法应用在Web使用挖掘的用户事务聚类上，聚类正确率以及算法消耗时间都有着明显的优势，会比K-均值算法、FCM算法等性能更好，速度更快。第六章总结与展望第六章总结与展望6.1总结Web挖掘中的聚类是Web挖掘技术中最重要的部分，本文主要是在Web挖掘中的聚类分析方面进行的研究工作，从复杂模式中获取知识并改善页面间的关系，研究重点对现有的蚁群算法进行改进，是算法能具有更好的适用性。本文的主要工作及创新点：1.引入一种改进的蚁群算法(IACA),并将其引入到Web使用挖掘领域，应用该算法进行Web用户事务聚类，给出其聚类模型，并对算法进行仿真实验。实验表明，改进的算法在聚类的正确性和性能上都较其他的算法有着更好的