|
关联规则是形如A=>B的蕴涵式，挖掘关联规则分为两步：第一步是识别所有的频繁项集，即支持度不小于用户指定的最小支持度的项集；第二步是从频繁项集中构造其置信度不低于用户给定最小置信度的规则，即强规则。这种基于支持度-置信度框架理论的关联规则挖掘方法存在如下问题： paper51.com （1）不能有效地发现低支持度高置信度的有趣规则 paper51.com
基于支持度-置信度框架理论的关联规则挖掘方法找到的强规则必须同时满足最小支持度阈值和最小置信度阈值，但有时人们感兴趣的规则往往是低支持度高置信度的[8]。例如，超市中两物品A和B，它们的销售量虽然很低，但经常是同时被顾客购买，管理人员希望将这种低支持度高置信度的规则找出来。 paper51.com （2）不能确定“相互依赖”的规则 paper51.com 关联规则反映A、B同时出现的概率和A出现的条件下B出现的条件概率。这样的规则只能确定A对B的“依赖”，不能同时确定B对A的“依赖”，但很多时候人们感兴趣的是“相互依赖”的规则。例如，中药的药组药对中，药之间必须是“相互依赖”的，如果药物A和B是药对，则必须是A通常与B配伍，同时B也是通常与A配伍。如果只是A通常与B配伍，但B并不常与A配伍，则A和B不是药对，因为B通常是只起辅助药性作用的药，这类药常在各种方剂中出现。用基于支持度-置信度框架理论的关联规则挖掘方法不能找出上述中药药组药对。 内容来自论文无忧网 www.paper51.com （3）找到的强规则并不一定是有趣的，甚至是错误的 copyright paper51.com 假定对分析涉及的家用电脑和VCD播放机的事务感兴趣。在所分析的10000个事务中，6000个事务包含家用电脑，7500个事务包含VCD播放机，4000个事务同时包含家用电脑和VCD播放机。运行传统的关联规则挖掘程序，最小支持度30%，最小置信度60%，将发现下面的关联规则： copyright paper51.com buys(X,“computer”) buys(X,“vcd-player”) 内容来自论文无忧网 www.paper51.com [support=40%,confidence=66%] copyright paper51.com 该规则是强关联规则。可事实上，电脑和VCD播放机是负相关的，买其中之一实际上减少了买另一种的可能性，因为购买VCD播放机的可能性是75%，大于66%。 copyright paper51.com 2.2 双向关联规则 paper51.com 定义1（双向关联规则）：设I={i1,i2,…,im}是项的集合，任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得T I。每个事务有一个标示符，称作TID。设A是一个项集，事务T包含A当且仅当 AT。如果AI，BI，并且A∩B=Æ，则形如AóB的表达式称为双向关联规则。 内容来自www.paper51.com 显然双向关联规则是同时满足A=>B和B=>A的规则。反过来也可以说同时满足A=>B和B=>A的规则是双向关联规则。所有双向关联规则Aó B有两个置信度。一个是关联规则A=>B的置信度： 内容来自论文无忧网 www.paper51.com conf(A=>B) = P(B|A) = P(AB) / P(A) paper51.com
另一个是关联规则B=>A的置信度： http://www.paper51.com conf(A=>B) = P(A|B) = P(AB) / P(B) paper51.com
置信度conf(A=>B)表示A出现的条件下B出现的条件概率，也就是A和B同时出现的概率与A出现的概率的比值。它反映了A对B的依赖程度。它的值越大，则A对B的依赖越强；反之，值越小，则A对B的依赖越弱。如果值为1，则意味着A的每一次出现都伴随着B的出现（反过来则不一定），A对B是100%的依赖。 http://www.paper51.com 置信度conf(B=>A)表示B出现的条件下A出现的条件概率，也就是B和A同时出现的概率与B出现的概率的比值。它反映了B对A的依赖程度。它的值越大，则B对A的依赖越强；反之，值越小，则B对A的依赖越弱。如果值为1，则意味着B的每一次出现都伴随着A的出现（反过来则不一定），B对A是100%的依赖。 内容来自论文无忧网 www.paper51.com 双向关联规则A óB的这两个置信度共同反映了A和B的相互依赖程度。我们很多时候对相互依赖程度高的规则——即下面定义的强双向规则感兴趣。 内容来自论文无忧网 www.paper51.com 定义2（强双向规则）：规则A=>B和B=>A同时满足最小置信度阈值（min_conf）的双向规则称作强双向规则。 copyright paper51.com 下面把上述概念推广到多个项集之间的情况。 http://www.paper51.com 定义3（n个项集的双向关联规则）：设CiÌI(2<i≤n),并且Ci∩Cj=Æ paper51.com (2<i≤n，2<j≤n,i≠j)，n项集C1、C2、…,Cn的双向关联规则为同时满足C1=>C2C3…Cn、C2=>C1C3…Cn、…、Ci=>C1C2…Ci-1Ci+1…Cn、…、Cn=>C1C2…Cn-1的规则，此时C1=>C2C3…Cn、C2=>C1C3…Cn、…、Ci=>C1C2…Ci-1Ci+1…Cn、…、Cn=>C1C2…Cn-1的置信度分别为： copyright paper51.com Conf(C1=>C2C3…Cn) = P(C2C3…Cn|C1) = P(C1C2…Cn) / P(C1) 内容来自www.paper51.com Conf(C2=>C1C3…Cn) = P(C1C3…Cn|C2) = P(C1C2…Cn) / P(C2) paper51.com …… 内容来自www.paper51.com Conf(Cn=>C1C3…C(n-1)) = P(C1C2…C(n-1)|Cn) = P(C1C2…Cn) / P(Cn) http://www.paper51.com
如果C1=>C2C3…Cn、C2=>C1C3…Cn、…、Ci=>C1C2…Ci-1Ci+1…Cn、…、Cn=>C1C2…Cn-1同时满足最小置信度阈值（min_conf），则项集C1、C2、…、Cn的双向关联规则是强双向规则。 内容来自论文无忧网 www.paper51.com 项的集合称为项集(itemset)，包含k个项的项集称为k-项集。我们把上述概念用于k-项集，可得到如下定义： 内容来自www.paper51.com 定义4（项的置信度）：设Tk={I1,I2,…,Ik}是一个k-项集，Ii（1≤I≤k）是Tk的一项，则k-项集Tk的项Ii的置信度conf(Ii,Tk)为事务数据库D中包含{Ii}的事务同时包含{I1,I2,…,I(i-1),I(i+1),…,Ik}的百分比，即： 内容来自论文无忧网 www.paper51.com Conf(Ii,Tk) = P({I1,I2,…,I(i-1),I(i+1),,Ik}|{Ii})=P({I1,I2, …,Ii, …,Ik})/P({Ii}) paper51.com 定义5（k-项集强双向规则）：设Tk={I1,I2,…,Ik}是事务数据库D中一个k-项集，如果Tk的任一项的置信度都满足最小置信度阈值(min_conf)，则称k-项集Tk为符合强双向规则的k-项集，简称k-项集强双向规则。 copyright paper51.com 2.3 遗传算法简介 http://www.paper51.com 遗传算法（GeneticAlgorithm, GA）是近几年发展起来的一种崭新的全局优化算法。1962年霍兰德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。 paper51.com
这一点体现了自然界中"物竞天择、适者生存"进化过程。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价,把问题的解表示成染色体，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群染色体，也即是假设解。然后，把这些假设解置于问题的“环境”中，也即一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染色体进行复制, 淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化，至到最适合环境的值。 内容来自论文无忧网 www.paper51.com 由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是将会用到的一些术语说明： paper51.com 一、染色体(Chromosome) 内容来自论文无忧网 www.paper51.com 染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。 内容来自论文无忧网 www.paper51.com
二、基因(Gene) 内容来自www.paper51.com 基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。 内容来自www.paper51.com 三、适应度(Fitness) http://www.paper51.com 各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数. 这个函数是计算个体在群体中被使用的概率。 paper51.com
四、种群（population） paper51.com 染色体带有特征的个体的集合称为种群。该集合个体数称为种群个体的大小。 内容来自www.paper51.com |