火龙果?整理 uml.org.cn
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（A∩B）。
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个主叫号码及使用业务如下所示：
主叫号码 使用的业务类型 13910772332 0，5，6，7 13801233660 1，5，6，7，
13910634261 1，4，7
13801138653 8，7，9 13901537797 0，1，2，5，6 138111254311 1，2，3，6 13988612322 4，5，6，9 13933245176 0，2，3 13966445588 4，5，7，8 13934221282 3，6，7
记A为业务5，B为业务6，T为事务总数（主叫号码统计数），则有：
21
火龙果?整理 uml.org.cn
规则A B的支持度为0.4，可信度为0.8。 规则B A的支持度为0.4，可信度为0.67。
若用户给出的最小可信度为0.3，支持度为0.3，则这两条规则满足条件，形成关联规则。 问题：如何确定那些业务可以生成不少于用户支持度与可信度的关联规则？
apriori算法特点：设物品集I含有N个项，T是事务，用户给定的最少支持度为P。
1） 2）
计算所有的1-项集（K项集表示元素只含K项），记为C1；
用给定最少支持度（用户给定支持度）对C1进行过滤，选出满足最少支持度的项， 记为L1；
3）
由L1通过L1*L1生成2-项集C2，其中C2为 C2=L1*L1={XY，XL1，YL1，XY
4）
???Ti, Ti是某一事务，XY 是2-项元素}；
用给定最少支持度（用户给定支持度）对C2进行过滤，选出满足最少支持度的项，记为L2；
5） 由L2通过L2*L1生成3-项集C3，其中C3为
C3=L2*L1={ZY，ZL2，YL1，ZY
???Ti, Ti是某一事务，ZY 是3-项元素，且ZY 的任
一子集的最少支持度仍大于P }； 6）
用给定最少支持度（用户给定支持度）对C3进行过滤，选出满足最少支持度的项，记为L3；
7）
以此类推，可以选出K项集Ck，Ck为
Ck=L（k-1）*L1={GY，GL（k-1），YL1，GY
???Ti, 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
22
火龙果?整理 uml.org.cn
思考问题：（1）如何利用关联分析，挖掘手机销售中的零配件业务关系，从而制定有利的
销售策略？
（2）如果以利润最大为目标，如何从关联业务中，形成利润最大的促销（套餐，
如买一送一，或买十送一）策略？
6、遗传算法概述 遗传算法主要思想：
遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。该算法从一组随机产生的初始解，称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，称为染色体。染色体在后续迭代中不断进化，称为遗传。在每一代中用“适值”来测量染色体的好坏。生成的下一代染色体，称为后代。后代是由前一代染色体通过交叉或变异运算形成。新一代染色体形成中，根据适值大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。适值高的染色体被选中的概率较高。这样，经过若干代之后，算法收敛于最好的染色体，这很可能就是问题的最优解或次优解。 基本概念
（1） 基因链码
生物的形状是由生物的遗传基因的链码所决定的。使用遗传算法时，需要把问题的每 一解编码成为一个基因链码，称为个体或染色体，每一基因链码的位称为基因。
（2） 群体
群体（种群）是若干个个体的集合。由于每个个体代表了问题的一个解，所以一个群体就是问题的一些解的集合。例如，P1={x1,x2,?x100}就是由100个解（个体）构成的群体。 （3） 交叉
两个染色体某些基因的交换。交叉的作用在于使新的群体中的个体具有多样性，由此扩大解的搜索空间。 （4） 变异
通过在染色体上的某些基因位置产生突变使得新产生的个体与其它个体有所不同。变异的作用在于提供初始群体中不含有的基因，为种群提供新的内容。
（5） 适应度
表示染色体对环境的适应程度。适应度越大，染色体越好，对应的解越好。 （6） 选择
根据染色体的适应性，选择适应度大的染色体而淘汰适应度小的染色体。
遗传算法的流程：
1． 令进化代数g=0,随机给出初始化群体P(g)；
23
火龙果?整理 uml.org.cn
2． 对P(g)中每个个体估值； 3． 根据估值进行个体选择（复制）；
4． 对已选择个体，进行交叉和变异操作，得到新一代群体P(g+1)。令g=g+1。 5． 如果终止条件满足，则算法结束。否则，转到2。
随机产生初始种群
对每一个体计算适应
值
Y 满足终止 条件
N 对个体进行选择复制
按一定概率和定义进
行交叉
按一定概率和定义进 行变异
遗传算法的实现 1．编码方法
（1）二进制编码：把问题解用0—1串的编码形式表示。
如整数1552是问题的一个解，则可以用1552的二进制形式1100001000来表示这个解所对应的基因链码（染色体）。
二进制、十进制相互转换方法： 例：二进制数110010012转换为十进制：
110010012=1?2+1?2+0?2+0?2+1?2+0?2+0?2+1?2+
7
6
5
4
3
2
1
0
显示适应值或最优解 =128+64+8+1=20110
24
火龙果?整理 uml.org.cn
十进制数N10转换为二进制数 (除2取余)： N10=bm2+ bm-12+ ?b12+ b02
由十进制数与二进制数的转换规律， bi 由2i?1除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
遗传算法的一个显著特点是它交替地在编码空间与解空间中工作，它在编码空间对染色体进行遗传运算，而在解空间对解进行评估和选择。二进制串表达的编码很难描述问题的实质，产生了各种非0—1串的编码方法，如实数编码等。 （2）实数编码：每个染色体编码为一个和解向量维数相同的实向量表示。
如优化问题 ：
maxf(x) s.t. gi(x)≤0 hi(x)=0 x?X
的解实向量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)
25
m
m-1
1
0