Clementine-第十讲

Clementine的关联分析主要内容关联分析概述简单关联规则及其有效性简单关联分析的Apriori算法时序关联分析的GRI算法序列关联分析的Sequence算法关联分析概述目的：寻找事物之间的联系规律，发现它们之间的关联关系关联关系包括：简单关联关系、序列关联关系关联分析的主要技术是关联规则（AssociationRule）最早用于研究超市顾客购买商品之间的规律，称为购物篮分析简单关联规则简单关联规则，属于无指导学习方法，能够有效揭示数据中隐含的关联特征，一般不直接用于分类预测简单关联规则的算法种类如何提高关联规则的分析效率如何使关联规则分析有更广泛的应用，包括如何处理数值型变量，如何将单一概念层次的关联推广到多概念层次的关联等Clementine中的简单关联规则算法：Apriori、GRI、Carma简单关联规则：基本概念事务：简单关联规则的分析对象可理解为一种商业行为等事务(T):由事务标识（TID）和项目集合(简称项集)X组成事务标识唯一确定一个事务I为包含k个项目的全体，即I={i1,i2,……Ik}。事务TI，项集XI。如果项集X中包含p个项目，则称项集X为p-项集简单关联规则：基本概念事务数据的存储格式：事务表、事实表事务数据事务表事实表简单关联规则：基本概念简单关联规则的一般表示形式：XY（规则支持度，规则置信度）•X为规则的前项，可为项目或项集或包含逻辑与（∩）或（∪）非（）的逻辑表达式•Y为规则的后项，一般为一个项目，表示某种结论或事实面包牛奶性别(女)∩收入(5000)品牌(A)简单关联规则的有效性有效性的测度指标规则置信度(Confidence)：对准确度的测量，描述了包含项目X的事务中同时包含项目Y项的概率，反映X出现条件下Y出现的可能性置信度高说明X出现则Y出现的可能性高面包牛奶（S=85%,C=90%），表示购买面包则同时购买牛奶的可能性为90%|)(||)(|XTYXTCYX条件概率简单关联规则的有效性有效性的测度指标规则支持度（Support）：测度了规则的普遍性，是项目X和项目Y项同时出现的概率面包牛奶（S=85%,C=90%），表示顾客中同时购买面包和牛奶的概率为85%|||)(|TYXTSYX简单关联规则的有效性前项支持度和后项支持度规则支持度和规则置信度的关系只需计算规则支持度和前项支持度XYXYXSSXTYXTC|)(||)(||||)(|TXTSX|||)(|TYTSY|||)(|TYXTSYX简单关联规则的有效性有效的关联规则应具有较高的置信度和支持度给定最小置信度和最小支持度阈值大于最小置信度和支持度阈值的规则才是有效规则例:1000个顾客购买行为的事务，只有1人购买了野炊用的烧烤炉，同时也只有他购买了碳)()(Smin)(min)(XCCSYXY简单关联规则的有效性对于关联规则XY•置信度：A/R1•规则支持度：A/T•前项支持度：R1/T•后项支持度：C1/T简单关联规则的实用性规则的实用性问题所揭示的关联关系可能仅是一种随机关联关系例：牛奶性别（男）（S=40%，C=40%）最小置信度和支持度为20%后项支持度40%简单关联规则的实用性规则的实用性问题所揭示的关联关系可能是反向关联关系例：成绩(优异)吃(鸡蛋)（S=30%，C=60%）后项支持度70%简单关联规则的实用性实用性的测度指标规则提升度（Lift）一般大于1才有意义，意味着X的出现对Y的出现有促进作用。规则提升度越大越好|||)(|/|)(|)(|SCLYYXyxTYTXTYXT简单关联规则的实用性实用性的测度指标置信差（ConfidenceDifference）例：后项支持度80%，规则置信度82%，置信差为2%，学习所获得的关联规则提供的信息量不高，相应的提升度仅为1.025置信差应大于给定的阈值||YYXSCD简单关联规则的实用性实用性的测度指标置信率（ConfidenceRatio）适合于稀有样本的分析例:某种病症的发生概率很低为1%。如果关联规则表示某种特征的人得此种病症的概率为10%，尽管它置信差不高仅为9%，但置信率却较高为90%置信率应大于给定的阈值),min(1YXYYYXCSSCR简单关联规则的实用性实用性的测度指标正态卡方（NormalizedChi-square）从分析前项与后项的统计相关性角度评价规则的有效性当项目X和项目Y独立,N为0;当项目X和项目Y完全相关时，N为1正态卡方应大于给定的阈值YYXXYSYXSSSSSSSN2)(实用性的测度指标信息差（InformationDifference）以交互熵为基础计算niniiiiiqqppQPH1122loglog)|()2log(1log)1(log)(log)(logcarcarcacarcrccararaacrrE•第一项替换为X条件下Y的分布，第二项为X独立于Y下的期望分布•a前项支持度，c为后项支持度，r为规则支持度•第一行数据的分布为X和Y独立条件下的期望概率分布简单关联规则的Apriori算法Apriori(Agrawal,Srikant,1994)，特点：只能处理分类型变量，无法处理数值型变量数据可以按事务表方式存储，也可以按事实表方式存储算法为提高关联规则的产生效率而设计Apriori算法包括两大部分：第一，产生频繁项集；第二，依据频繁项集合产生关联规则Apriori算法：产生频繁项集频繁项集：对包含项目A的项集C，其支持度大于等于用户指定的最小支持度，C(A)为频繁项集包含1个项目的频繁项集称为频繁1-项集，记为L1；包含k个项目的频繁项集称为频繁k-项集，记为Lk确定频繁项集的目的：确保后续生成的关联规则是在具有普遍代表性的项集上生成的，否则，生成的关联规则不可能具有较高的支持度min|||)(|STATApriori算法：产生频繁项集寻找频繁项集：自底向上，即从包含少量项目的项集开始依次向包含多个项目的项集搜索基本原则：如果最底层中只包含D项的1-项集不是频繁项集，则包含D项的其他所有项集都不可能是频繁项集，后续无需再对这些项集进行判断Apriori算法：产生频繁项集Apriori寻找频繁项集的过程:不断迭代每次迭代包含两个步骤：第一，产生候选集Ck，即可能成为频繁项集的项集第二，基于候选集Ck，计算支持度并确定频繁项集Lk设最小支持度阈值为0.5Apriori算法：产生关联规则产生关联规则的步骤：依频繁项集产生所有简单关联规则，选择大于最小置信度阈值的关联规则组成有效规则集合对每个频繁项集L，计算L所有非空子集L’的置信度例：频繁项集L包含项目B、C、E。若L的子集L’包含B和C，则L－L’包含E。计算：C({B,C}E)=S(B,C,E)/S(B,C)=0.50/0.50=100%若大于最小置信度阈值，生成关联规则)'()(|)'(||)(|)'('LSLSLTLTCLLL)'('LLLC)(''LLLApriori算法的应用以BASKETS.txt为例(1000名顾客),事实表:个人信息：会员卡号（cardid）、消费金额（value）、支付方式（pmethod）、性别（sex）、是否户主（homeown）、年龄（age）、收入（income）；一次购买商品的信息:果蔬（fruitveg）、鲜肉（freshmeat）、奶制品（dairy）、蔬菜罐头（cannedveg）、肉罐头（cannedmeat）、冷冻食品（frozenmeal）、啤酒（beer）、葡萄酒（wine）、软饮料（softdrink）、鱼（fish）、糖果（confectionery目标：分析商品的连带购买简单关联规则的GRI算法GRI（GeneralizedRuleInduction）算法,Smyth和Goodman,1992特点：前项可是分类型变量，也可为数值型变量数据只能按事实表方式存储采用深度优先搜索（DepthFirstSearch）策略实现算法第一，对数值型前项如何分组？第二，J-值的含义是什么，如何计算？分组步骤第一，将前项的N个数据（数值型）从小到大升序排列，分组组限值取最小值第二，试分组：小于等于组限值的数据为组1，大于组限值的数据为组2第三，计算J-值第四步，取下一个值作为组限值，返回到第二步重复上述步骤，直到组限值取完第N—1个数据，得到N—1个J-值。正式分组，以J-值最大时的组限值作为最终分组组限，分成两组J-值反映收入组1中是否购买汽车的条件概率分布与不考虑收入时是否购买汽车的先验概率分布的差异的调整结果])(1)|(1log))|(1()()|(log)|()[()|(ypxypxypypxypxypxpxyJ简单关联规则的GRI算法以BASKETS.txt为例，目标：顾客消费偏好研究，分析不同性别、年龄以及家庭主妇有怎样的消费偏好GRI算法的应用目的：从所收集到的众多序列中，找到事务发展的前后关联性，进而推断其后续的发生可能Sequence算法，Agrawal和Srikant,1995研究对象:事务序列，简称序列例：C(香肠,花生米)C(饮料)C(啤酒)序列关联分析•序列由项集和顺序标志组成•项集用C表示•顺序标志用表示序列可被拆分为若干个子序列子序列可继续拆分成项集项集可看成最小子序列例：C(香肠,花生米)C(饮料)C(啤酒)拆分为：C(香肠,花生米)C(饮料)C(饮料)C(啤酒)、C(香肠,花生米)C(啤酒)序列关联分析序列测度指标：序列长度是序列所包含的项集个数序列大小是序列所包含的项目个数例：001号的购买序列，包含3个项集，序列长度为3；序列共包括4个具体项目，序列大小为4序列关联分析序列测度指标：序列支持度：包含某序列的事务序列数占总事务序列数的比例例：C(饮料)C(啤酒)的序列支持度为4/6=0.67序列关联分析序列关联研究的目标：生成序列关联规则序列关联规则的一般形式通常为：XY（支持度，置信度）例：C(香肠,花生米)C(饮料)C(啤酒)序列关联规则序列关联规则的支持度：包含某序列规则的事务数占总事务的比例例：C(香肠,花生米)C(饮料)C(啤酒)的支持度1/6=0.17C(饮料)C(啤酒)的支持度4/6=0.67序列关联规则序列关联规则的置信度：同时包含前项和后项的事务数与包含前项的事务数的比，也是规则支持度与前项支持度的比例：C(香肠)C(饮料)的置信度为1/5=0.2C(饮料)C(香肠)的置信度为3/4=0.75序列关联规则Sequence算法包括两大部分第一，产生频繁序列集频繁序列是指，序列的支持度大于等于用户指定的最小支持度的序列第二，依据频繁序列集生成序列关联规则序列关联分析的Sequence算法Sequence算法的基本出发点：只有最小频繁子序列（频繁项集）才可能构成频繁子序列，应首先寻找最小频繁子序列（频繁项集）只有频繁子序列才可能构成频繁序列，应继续寻找频繁子序列。当序列所包含的子序列为频繁序列时，序列才可能成为频繁序列Sequence：产生频繁序列集动态处理策略：边读入边计算；批量筛选设：最小支持度为40%频繁序列在时间点上不一定连续，允许有间隔将频繁序列组织成邻接格（Adjacencylattice）邻接:如果对序列A增加一个最小子序列后就能够得到序列B，则称序列A和序列B是邻接的邻接格能够有效反映频繁序列的内在关系C(饮料)C(香肠)(50%,75%)、C(饮料)C(啤酒)(66.7%,100%)C(啤酒)C(香肠)(50%,60%)Sequence：产生序列关联规