[基于遗传算法的Ｗｅｂ使用挖掘研究] 遗传算法matlab程序

　　摘要：针对Web使用挖掘中的信息，提出一种基于遗传算法的关联规则挖掘模型，同时结合实例对有关信息特征进行量化，然后利用实数数组的方法进行编码以及构造适应度函数，挖掘出隐含在用户注册登记信息库中的有关用户规则。为个性化服务系统提供准确和可行的关联规则，并对用户的行为进行了预测和分析。
　　关键词：遗传算法；Web使用挖掘；关联规则
　　中图分类号：TP311文献标识码：A文章编号：1009-3044(2007)18-31628-03
　　Research on Web Usage Mining Based on Genetic Algorithm
　　GAO Huai-jin,LI Guo-hui
　　(School of Mathematics and Information Science,Weifang University,Shandong 261061,China)
　　Abstract:This paper gives a mining model of association rules based on genetic algorithm in order to mining the information of web usage log, and also quantify relevant information character by an example, code using an array of real numbers, structure a fitness function. Finallycan mining user rules that hide in the user registration information. It provide accurate and viable association rules for personalized service systems, forecast and analyse the user"s behavior.
　　Key words: GA(genetic algorithm);web usage mining;association rules
　　
　　1 引言
　　
　　Web挖掘的目的就是要从大量的Web网站上的信息中提取对用户有用的信息与知识。为了达到这一目的，可以把Web挖掘看成是搜索问题，将整个Web信息数据库看作一个大搜索空间，而把挖掘算法看成一种搜索策略。显然，当Web信息数据库容量极其巨大时，进行穷举搜索是不可行的，必须采取一种有效的搜索策略。应用遗传算法在Web数据库中进行搜索，对随机产生的一组规则进行进化，直到该Web信息数据库能够被该组规则覆盖，从而挖掘出隐含在Web数据库中的规则，找到用户所需要的信息与知识，为用户提供个性化服务。
　　
　　2 Web使用挖掘
　　
　　Web挖掘是数据挖掘在Web上的应用，可以分为Web内容挖掘、Web结构挖掘和Web使用挖掘[1][2]。其中Web使用挖掘的主要目的在于分析用户的行为模式（或称访问习惯），发现用户访问Web页面的模式规律，为智能Web服务提供知识依据，因此需要分析描述Web用户访问行为特征的关联规则。关联规则是描述Web用户行为特征的重要依据，是用户行为特征的知识表示，Web关联规则是通过分析用户访问的Web页面(URL)之间的关联关系得来的，具体应用在Web使用挖掘中有其特殊的表现形式，事实上，Web关联规则(Web Association Rules，下简称WAR)是一种知识的表现形式。与一阶逻辑的产生式大体相同，而WAR是考察用户的客观访问规律所获取的知识，用户对Web站点的访问过程是与URL访问序列、访问时间有关系，如果在挖掘WAR时忽略这种关系，那么挖掘出的关联规则就仅仅是URL之间的一种关联关系，而割裂用户的实际访问规律，因此，将通常意义上的关联规则挖掘与序列模式挖掘相结合，考察关联规则的条件与结论及其内部项的时序关系，挖掘有效的WAR，将为基于Web使用挖掘的个性化服务系统提供准确、可行的关联规则。
　　
　　3 基于遗传算法的Web使用挖掘模型
　　
　　Web使用挖掘中的信息除了服务器的日志记录外，还包括代理服务器日志、浏览器端日志、注册信息、用户会话信息、交易信息、Cookie中的信息、用户查询、鼠标点击流等一切用户与站点之间可能的交互记录。可见Web使用挖掘的数据量是非常巨大的，而且数据类型也相当丰富。通过处理服务器日志文件等这些数据，结合站点的拓扑结构信息，可以发现用户的浏览模式，如用户聚类、关联规则、序列模式等，理解用户的行为，进而实现预测用户的行为，为用户提供个性化服务。从而提出了一种基于遗传算法的关联规则挖掘模型，如图1所示：
　　图1 基于遗传算法的关联规则挖掘模型
　　该模型的工作过程如下：
　　根据用户的问题信息将其通过预处理器被编码成有限长的消息并为每个属性(字段)创建映射表，然后依据属性(字段)由SQL查询器在Web信息数据库中查询生成临时消息表，再依据属性映射表将临时消息表离散化处理之后生成消息表：由遗传算法求出满足条件的种群，最后将种群中适应度较高的个体作为解输出到优化器，然后由优化器对规则进行提取生成关联规则返回给用户。
　　
　　4 实例分析
　　
　　根据某网站的用户注册登记信息，由此建立了一个用户信息数据库。用户基本信息表的属性(字段)如表1所示。通过收集这些信息并运用遗传算法方法对其进行分析和关联规则的挖掘，从而实现了遗传算法在Web使用挖掘上的应用。具体求解步骤如下：
　　表1 用户基本信息表
　　4.1量化
　　为了能够对用户信息进行编码，必须先根据用户信息特征进行量化[3]。
　　定义1 量化(Measurement)：就是对数据库中的属性值按照一定的方法分类，并赋给一个正整数表示的方法。
　　定义2 成熟度(Mature)：是量化值的线性函数。量化值越小，成熟度越小，反之，则越大。主要来衡量某个个体对网络的依赖程度。
　　根据量化定义，先对用户基本信息表中的各个字段进行量化再进行编码。
　　(1)Province的量化
　　用户所处的地域是Web中关心的一个重要的参数。其部分省份量化表如表2所示。量化原则是先根据地域分组，同一组的具有相同的量化值。北京、上海等直辖市化为一组，具有最高的量化值5；东部省份城市化为一组，其量化值为4；中部省份城市为一组，其量化值为3；西部省份城市为一组，其量化值为2；偏远省份城市的量化值为1，各组的量化值依次降低。根据成熟度的定义可知中西部省份相对于东部省份以及直辖市而言，其对网络的依赖程度还不是很高。其余字段都遵循同样的量化原则。后面挖掘出的关联规则，其解释可能不止一种。例如：表2中，北京、天津、上海等具有相同的量化值5，在挖掘出的关联规则中只能解释为直辖市而无法指出具体的地方。
　　表2Province的量化
　　(2)Action的编码
　　用户在填写上网活动时，允许同时选择多个，同时查询中要采用关系数据库，因此首先就要满足1NF（第一范式）[4]，不能有子表，对用户的选择必须进行处理，否则是无法存储到数据库中的。Action的编码值与成熟度无关，Action的编码值与别的量化值有完全不同的意义，因此，在适应度函数构造中是不包含此项的。所采用的方法是：表3中，举出8项用户上网最有可能进行的活动，然后编号，每项活动，用户选择就赋值为1；否则为0。这样就会得到一个8位的二进制的序列，然后转换成十进制存储。最后提出规则以后，再对其解码即可知道所代表的意义。例如：编码为00110001，十进制数是49。说明该用户平时上网的主要活动是在线游戏、体育和聊天。若用户上网活动的选择项不止8项，则相应调整二进制位数。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　表3 Action的编码表
　　4.2编码
　　在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法，总的来说，可以分为三大类：二进制编码方法、符号编码方法、浮点数编码方法[6]。二进制编码方法是遗传算法中最主要的一种编码方法，它的优点是：容易产生和操作、理论上容易处理、几乎任何问题都可以用二进制编码，但是二进制编码也存在一些缺点：首先是表示精度与算法效率之间的矛盾；其次，某些问题中要将属性值先转化为实数值然后再将实数值转化为二进制编码，这样在遗传算法的操作过程中，需要不断地对码串进行译码，增加了算法的计算量，降低了算法的效率。所以本实例中不采用二进制编码，而是直接采用实数数组的方法进行编码。
　　实数数组中元素的个数与事务数据库中的字段个数相对应，元素值代表了元素的属性值，如表4所示的事务数据库。
　　表4 事务数据库的字段
　　用一个长度为N的数组来表示表2所表示的事务数据库的个体编码，A[1]表示字段1，A[2]表示字段2，…，A[R]表示字段R。例如：用数值i(i∈N)表示属性值i，就可以用数组A[R]的元素值来表示相对应的字段的属性值。另外用值0表示此属性与其它的属性无关联。由此，表4所示的数据库的编码结构如图2所示。
　　图2 编码数组结构
　　采用实数数组的编码方法，这种编码方法具有精度高、便于空间搜索的优点，实现起来也比较简便。在利用实数数组的方法进行编码过程中，实数数组的元素个数与事务数据库中的字段的个数相对应，实数数组的元素值则代表了字段的属性值。其实进行了这样的编码后交叉、变异等的操作就变成了对数组的操作。
　　根据以上对各个字段的量化，结合上面所述的实数数组的编码方法，可得到用户基本信息表的量化和编码结果。经过量化和编码后的用户基本信息表如表5所示：
　　表5 量化和编码后用户基本信息表
　　4.3 适应度函数的构造
　　适应度函数是遗传算法与应用问题的唯一接口，是种群中个体优劣的一种量化反映，它的构造直接影响问题求解的效率。为了构造适应度函数，再引入关联规则及支持度、可信度等的概念[5]：
　　定义3关联规则也称之为关联模式，是形如x?圯y的规则，其中x，y是关于数据库中属性取值的断言：由于某些事务的发生引起另外一些事件的发生。
　　定义4设T是事务数据，即T={t1,t2,...tn}，其中ti(1?燮i?燮m) 是每个事务的数据，这些数据称为数据项。I是T中所有数据项（物品）的集合即I={i1,i2,...in} ，ij是T中的一个数据项。每个事务中含有I的一个子集。关联规则是一种蕴含关系：x?圯y，其中，x∈I,y∈I且x∩y=?� 。
　　定义5支持度（support）表示x?圯y在T事务数据库中出现的普遍程度，称规则x?圯y在事务数据库T中具有大小为s%的支持度。
　　定义6可信度(confidence)说明x?圯y成立的必然性，称规则x?圯y在事务数据库T中具有大小为c%的可信度。
　　支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有的事物中有多大的代表性，显然，支持度越大，关联规则越重要。有些关联规则的可信度虽然很高，但是支持度却很低，说明该规则使用的机会很少，因此也并不重要。鉴于关联规则的如此特性，考虑用关联规则的支持度来定义它的适应度函数。可以这样来筛选规则，先用支持度来筛选规则，然后在满足最小支持度的规则中确定它的关联程度和关联性。因此规则的适应度可以简便的作如下定义：
　　fitness(Ri)=S"/S=P 当S">Sq 当S"：T(10%support，90%confidence)
　　说明：T(这只是一种合理的解释)，由此可以看出在一些家庭条件较好的女中学生经常长时间上网聊天、玩在线游戏、收发邮件。
　　②：T(32%support，78%confidence)
　　说明：T 本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文