数据挖掘方法之三学生.docVIP

数据挖掘方法之三关联分析与遗传算法5、关联分析关联分析：对事务中物品之间同时出现的规律知识模式进行分析的方法。关联规则：通过量化的数字描述事务中物品之间同时出现的规律的关联表示。问题引入：1）事务1中出现了手机，事务2中出现了电池、储值卡，事务3中出现了手机和电池，问手机、电池、储值卡在事务中出现，其相互之间有没规律可循？ 2）开通的手机业务中，如语音信箱，移动秘书，信息点播，呼叫转移等，相互之间是否有关联关系？主要概念：1）可信度：（confidence）设W是一组事务集，每个事务T是一组物品。若W中支持物品集A的事务中，有C%的事务也支持物品集B，则C%称为关联规则A B的可信度，其中， A B表示A出现则B也出现，且AB=。可信度表示为P（B/A）。2）支持度（Support）：设W中有S%的事务同时支持物品集A和B，则S%称为关联规则A B的支持度。支持度表示为P（AB）。3）期望可信度(expected confidence)：设W中有E%的事务支持物品集B，则E%称为关联规则A B期望可信度。期望可信度表示为P（B）。4）作用度（lift）：作用度是可信度与期望可信度的比值。表示为P（B/A）/ P（B）。 关联规则挖掘算法常用的有apriori算法。apriori算法的主要思想是找出存在于事务数据库中的所有大物品集（也称频繁集），利用获取的大物品集生成关联规则。其中，大物品集是指支持度不少于用户给定支持度的物品集。案例： 设通过统计用户主叫号码的业务使用情况，进行业务的关联分析。设有10项业务，记0语音信箱，5移动秘书，6信息点播，9呼叫转移，统计的10个主叫号码及使用业务如下所示： 主叫号码 使用的业务类型0，5，6，71，5，6，71，4，78，7，90，1，2，5，6 138111254311 1，2，3，64，5，6，90，2，34，5，7，83，6，7记A为业务5，B为业务6，T为事务总数（主叫号码统计数），则有： 规则A B的支持度为0.4，可信度为0.8。 规则B A的支持度为0.4，可信度为0.67。若用户给出的最小可信度为0.3，支持度为0.3，则这两条规则满足条件，形成关联规则。问题：如何确定那些业务可以生成不少于用户支持度与可信度的关联规则？ apriori算法特点：设物品集I含有N个项，T是事务，用户给定的最少支持度为P。1） 计算所有的1-项集（K项集表示元素只含K项），记为C1；2） 用给定最少支持度（用户给定支持度）对C1进行过滤，选出满足最少支持度的项， 记为L1；3） 由L1通过L1*L1生成2-项集C2，其中C2为C2=L1*L1=XY，XL1，YL1，XYTi, Ti是某一事务，XY 是2-项元素；4） 用给定最少支持度（用户给定支持度）对C2进行过滤，选出满足最少支持度的项，记为L2；5） 由L2通过L2*L1生成3-项集C3，其中C3为C3=L2*L1=ZY，ZL2，YL1，ZYTi, Ti是某一事务，ZY 是3-项元素，且ZY 的任一子集的最少支持度仍大于P ；6） 用给定最少支持度（用户给定支持度）对C3进行过滤，选出满足最少支持度的项，记为L3；7） 以此类推，可以选出K项集Ck，Ck为Ck=L（k-1）*L1=GY，GL（k-1），YL1，GYTi, Ti是某一事务，GY 是k-项元素，且GY 的任一子集的最少支持度仍大于P；当用给定最少支持度对Ck进行过滤不能选出更大项的元素时，Ck就是最大物品集。例：设有四项业务，用T-ID表示，用户的最少支持度和可信度均为0.4 ,如下所示：T-ID 项 100 ACD 200 BCE 300 ABCE 400 BC 通过apriori算法，可以找出BCE是大物品集，可以生成关联规则：B BCE-B 即 B C conf=2/3, Sup=2/4,B E conf=1, Sup=3/4 C B conf=2/3, Sup=2/4 C E conf=2/3, Sup=2/4 E B conf=1, Sup=3/4 E C conf=2/3, Sup=2/4思考问题：（1）如何利用关联分析，挖掘手机销售中的零配件业务关系，从而制定有利的销售策略？ （2）如果以利润最大为目标，如何从关联业务中，形成利润最大的促销（套餐，如买一送一，或买十送一）策略？ 6、遗传算法概述遗传算法主要思想：遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。该算法从一组随机产生的初始解，称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，称为染色体。染色体在后续迭代中不断进化，称为遗传。在每一代中用“适值”来测量染色体的好坏。生成的下一代染色体，称为后代。后代是由前一代染色体通过交叉或变异运算形成。新一代染色体形成中，根据适值大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。适值高的染色体被选中的概率较高。这样，经过若干代之后，算法收敛于最好的染色体，这很可能就是问题的最优解或次优解。基本概念（1） 基因链码 生物的形状是由生物的遗传基因的链码所决定的。使用遗传算法时，需要把问题的每一解编码成为一个基因链码，称为个体或染色体，每一基因链码的位称为基因。（2） 群体群体（种群）是若干个个体的集合。由于每个个体代表了问题的一个解，所以一个群体就是问题的一些解的集合。例如，P1=x1,x2,x100就是由100个解（个体）构成的群体。（3） 交叉 两个染色体某些基因的交换。交叉的作用在于使新的群体中的个体具有多样性，由此扩大解的搜索空间。（4） 变异通过在染色体上的某些基因位置产生突变使得新产生的个体与其它个体有所不同。变异的作用在于提供初始群体中不含有的基因，为种群提供新的内容。（5） 适应度表示染色体对环境的适应程度。适应度越大，染色体越好，对应的解越好。（6） 选择根据染色体的适应性，选择适应度大的染色体而淘汰适应度小的染色体。遗传算法的流程：1 令进化代数g=0,随机给出初始化群体P(g)；2 对P(g)中每个个体估值；3 根据估值进行个体选择（复制）；4 对已选择个体，进行交叉和变异操作，得到新一代群体P(g+1)。令g=g+1。5 如果终止条件满足，则算法结束。否则，转到2。随机产生初始种群对每一个体计算适应值满足终止条件 Y N对个体进行选择复制按一定概率和定义进行交叉显示适应值或最优解按一定概率和定义进行变异遗传算法的实现1编码方法 （1）二进制编码：把问题解用01串的编码形式表示。 如整数1552是问题的一个解，则可以用1552的二进制形式1100001000来表示这个解所对应的基因链码（染色体）。二进制、十进制相互转换方法：例：二进制数110010012转换为十进制：110010012=127+126+025+024+123+022+021+120+ =128+64+8+1=20110十进制数N10转换为二进制数 (除2取余)： N10=bm2m+ bm-12m-1+ b121+ b020由十进制数与二进制数的转换规律， bi 由2除N10的余数决定。例：将15710转换为二进制数： 余数 2 157 1=b0 2 78 0= b1 2 39 1= b2 2 19 1= b3 2 9 1= b4 2 4 0= b5 2 2 0= b6 2 1 1= b7 0把余数按顺序排列，有15710=100111012遗传算法的一个显著特点是它交替地在编码空间与解空间中工作，它在编码空间对染色体进行遗传运算，而在解空间对解进行评估和选择。二进制串表达的编码很难描述问题的实质，产生了各种非01串的编码方法，如实数编码等。（2）实数编码：每个染色体编码为一个和解向量维数相同的实向量表示。如优化问题 ：maxf(x)s.t. gi(x)0 hi(x)=0 xX的解实向量x=(x1,x2,xn) 就用作表示解的染色体。2适应度函数设计 （1）对g(x)的最大值问题，可以定义适应度函数为： 当g(x)0时，适应度函数 f(x)= g(x) 当g(x)0时不成立时，取Cmin= g(x),适应度函数 f(x)可以定义为： f(x)= - Cmin+ g(x) (2)对g(x)的最小值问题，可以定义适应度函数为： 当g(x) 0时，适应度函数 f(x)= 1/g(x) 当g(x)0时不成立时，取Cmax= g(x),适应度函数 f(x)可以定义为： f(x)= Cmax-g(x)3、选择算子的设计 适应度比例方法（轮盘赌选择方法）： 设群体大小为n，其中个体i的适应度值为fi，则被选择的概率Pi为 Pi=fi/这种选择的方式非常类似轮盘赌中的转盘，当被选择的概率越大时，个体的适应值越大，被选择到的机会也越多，其基因结构被遗传到下一代的可能性越大。 期望值方法 每个个体在下一代生存的期望数目:为 M= fi/（/n）=n fi/可以通过期望数M的取值决定个体i的复制数目。4、交叉算子设计 （1）单点交叉单点交叉又叫简单交叉。对两染色体，在随机选择的一个交叉位之后（或之前）的所有基因交换，生成两个新个体。当基因链码的长度为n时，可能有n-1个交叉点位置。 例：若双亲为：x=(x1,x2,xn), y=(y1,y2, yn),在随机的第K位交叉，生成的后代为： x=(x1,x2,xk, yk+1,yk+2, yn), y=(y1,y2, yk, xk+1,xk+2,xn) （2）两点交叉对两染色体，在随机选择的两个交叉位之间的部分基因交换，生成两个新的个体。一个两点交叉的例如下： 父辈个体 aaaaaaaaaa aaabbbbaaa父辈个体 bbbbbbbbbb bbbaaaabbb即2个交叉点需要设定两个基因交叉位置，父辈两个个体在这两个差点之间的基因链码相互交换，从而生成新个体。对于两点交叉而言，若染色体长为n，则可能有（n-1）(n-2)/2种交叉点的设置。（3）多点交叉多点交叉是前述两种交叉方法的推广。多点交叉有时又被称为广义交叉。若用参数c表示交叉数，则当c=1时，广义交叉就是单点交叉。C=2时，广义交叉就是两点交叉。 一般地，多点交叉不经常被采用。这是因为当基因链码的长度n较小，或交叉点数c较大时，具有优良特性的模式也很容易被破坏。（4）均匀交叉对两染色体，随机生成与两染色体编码位数相同的摸板，根据摸板进行基因交换。即均匀交叉的过程是：先随机的产生一个与父辈个体基因串具有同样长度的二进制串，其中0表示不交换，1表示交换。这个二进制串称为交叉模版；然后根据该模板对两个父辈基因串进行交叉，得到的两个新基因串即为后代新个体。例如：父辈个体 1：110010111000父辈个体 2：101011101011模板： ：001101011100后代个体 1：111011101000后代个体 2：100010111011 由于均匀交叉在交换位时并不考虑其所在位置，破坏模式的概率较大。但另一方面它能搜索到一些前面基于点的交叉方法无法搜索到的模式。（5）基于实向量算术运算的交叉 设两向量为 x1、x2，则有凸交叉：x1= x1+ x2 x2= x2+ x1 =0。5仿射交叉：x1= x1+ x2 x2= x2+ x1 =1。5， =-0。5 线性交叉：x1= x1+ x2 x2= x2+ x1 +0 0， 0在很多的应用中，交叉算子是以一定的概率实现的。这一概率称作交叉概率。在解决实际问题时，由于问题的特殊性，以及编码的方式的不同，交叉算子也会不同。5、变异算子设计（1） 基本变异算子基本变异算子是针对二值基因链码而言。其具体操作是：指对群体中基因链码随机挑选c个基因位置并对这些基因位置的基因值以变异概率P取反，即0变成1，1变成0。当c=1时，表示一个 基因值取反。（2） 均匀变异算子该变异方法是针对实数编码方式的。为叙述方便，设v=(v1,v2,.vm)是群体中的一个个体，z=(z1,z2,zm)是变异产生的后代。均匀性变异则是先在个体v中随机的选择一个分量vk，然后，在一个定义的区间ak,bk中均匀随机地取一个数vk1代替vk以得到z，即z=(v1,vk1,vm)。简单的函数极值求解例：设函数f(x)=x2 ,x0,311. 编码由于x0，31，因此把变量x编码为5位长的二进制无符号整数表示形式。比如 x=13可表示为01101的形式。2初始群体的生成初始群体的每个个体是通过随机方法产生的。设随机生成的4个个体组成的群体，其选择、复制、交叉过程见下表：个体号初始群体X值适应度选择概率i/i选择次数交叉处位置配对交叉位置新一代群体X值适应度1011011316901405610110|12401100121442110002457604919621100|0141100125625301000864006024001|00042110112772941001119361031124110|011321000016256适应度总和11701004001754平均适应度=/n293025100437最大适应度576049196729第二代遗传优化过程：个体号初始群体X值适应度选择概率i/i选择次数交叉处位置（设第2点交叉）配对交叉位置新一代群体X值适应度10110012144008032011|0112211001256252110012562503514111|00112110112772931101127729042168211|0114211000245764100001625601506110|000321001119361改进遗传算法概述1、分层遗传算法对于一个问题，首先随机地生成Nn个样本（N2，n2），然后将它们分成N个子种群，每个子种群包含n个样本，对每个子种群独立地运行各自的遗传算法，称为低层遗传算法，记它们为（i=1，2，N）。这N个遗传算法在设置特性上尽可能有较大的差异，目的是产生更多种类的优良模式。在每个子种群的遗传算法运行到一定代数后，将N个遗传算法的结果记为新的个体，i=1，2N，表示结果种群的n个个体,相应新个体的平均适应度记为，对新个体形成的种群进行遗传算法，称为高层遗传算法。高层遗传算法与普通遗传算法的操作相类似，分成如下三个步骤：1、选择对新的个体，以个体的平均适应度进行选择操作，适应度高的新个体被复制，甚至复制多次；另一些新个体由于它们的种群平均适应度值低而被淘汰。2、交叉如果和被随机地匹配到一起，而且从位置x进行交叉（1i，jtN；1xn1），则和相互交换相应的部分。这一步骤相当于交换GAi；和GAj中结果种群的个体。3变异以很小的概率将少量的随机生成的新个体替换中随机抽取的个体。至此，高层遗传算法的第一轮运行结束。N个遗传算法GAi；（i=1，2，N）可以从进化一代后的新个体种群中继续各自的操作。在N个GAi各自运行到一定代数后，再次更新数组，并开始高层遗传算法的第二轮运行。继续循环操作，直至得到满意的结果。分层遗传算法（Mierarchic Gentle Algorithm， HGA）特点：局部优化后进行全局优化，即通过高层遗传算法的操作，GAi（i=1，2，N）可以获得包含不同种类的优良模式的新个体，从而为各种个体提供了更加平等的竞争机会。2、自适应遗传算法遗传算法的参数交叉概率和变异概率的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性，越大，新个体产生的速度就越快。然而，过大时遗传模式被破坏的可能性也越大，使得具有高适应度的个体结构很快就会被破坏；但是如果过小，会使搜索过程缓慢，以至停滞不前。对于变异概率，如果过小，就不易产生新的个体结构；如果取值过大，那么遗传算法就变成了没有遗传特征的纯粹随机搜索算法。针对不同的优化问题，需要反复实验来确定和，这是一件繁琐的工作，而且很难找到适应于每个问题的最佳值。自适应遗传算法（Adaptive GA），和能够随适应度自动改变。当种群各个体适应度趋于一致或者趋于局部最优时，使和增加，而当群体适应度比较分散时，使和减少。同时，对于适应值高于群体平均适应值的个体，对应于较低的和，使该解得以保护进入下一代；而低于平均适应值的个体，相对应于较高的和，使该解被淘汰掉。因此，自适应的和能够提供相对某个解的最佳和。自适应遗传算法在保持群体多样性的同时，保证遗传算法的收敛性。在自适应遗传算法中，和按如下公式进行自适应调整：式中，群体中最大的适应度值； 每代群体的平均适应度值；要交叉的两个个体中较大的适应度值；要变异个体的适应度值。这里，只要设定是取（0，1