我国社会经济发展综合评价指数研究.ppt

关联规则 CARMAContinuousAssociationRuleMiningAlgorithm 报告人 徐启元指导教师 谢邦昌日期 2007年11月30日 目录 关联规则基本概念CARMA算法简介CARMA模块的基本概念案例分析及Clementine操作步骤购物篮分析 Tabular类型数据网络日志分析 Transactional类型数据值得注意的问题CARMA算法原理 参考 关联规则算法简介 关联分析的目的是寻找数据项间的相关性 常用技术 关联规则 即寻找在同一个事件中出现的不同项目的相关性例如 找出顾客经常同时购买哪些商品 网民浏览的网页之间有没有什么关联性 CARMA算法简介 CARMA是一种比较新的关联规则算法 它是1999年由Berkeley大学的ChristianHidber教授提出来的 1 2 3 4 能够处理在线连续交易流数据 仅需一次 最多两次对数据的扫描就可以构造出结果集 允许在算法执行过程中按需要重新设置支持度 占用内存少 CARMA CARMA模块中的基本概念 Antecedent Consequent它们指的是规则的前项和后项 Instances对于每一条规则 它的Instances值指的是所有记录中包含该规则的antecedent的记录的数量 前项Antecedent 后项Consequent 总共4条购买数据 其中有三条都包含bread 那么该条规则的instances等于3 CARMA模块中的基本概念 Support它的定义和instances很接近 不同的是support描述的不是数量 而是比例 RuleSupport它在Support定义的基础上更进一步 它指的是所有记录中既包含某规则的antecedent 又包含consequent的记录所占的比例 Support 3 4 100 75 四条记录中只有一条既包含了前项bread 又包含了后向milk 所以RuleSupport 1 4 100 25 CARMA模块中的基本概念 ConfidenceConfidence RuleSupport Support该指标反映的是规则预测的准确程度 DeployabilityDeployability Support RuleSupport它的作用与confidence类似 根据规则 面包 牛奶 那么购买了面包的第一 二及四行都会被预测购买了牛奶 但事实上这三个预测只有第二个是正确的 所以confidence 1 3 100 33 3 CARMA模块中的基本概念 Lift在已知某规则的consequent发生的先验概率的情况下 某规则的Lift被定义为Confidence和该先验概率的比率值 那么对于一条记录 那么不采用任何规则进行预测 随便猜测该顾客是否该买牛奶的正确率是50 已知有50 的人购买了牛奶 如果采用 面包 牛奶 的规则进行预测的话 正确率 即confidence 33 3 比随便猜测的正确率还低 那么此时的Lift值为多少呢 Lift 33 3 50 66 6 1 所以只有那些Lift 1的规则才是有意义的规则 源数据格式 CARMA模块能够处理一下两种格式的数据Tabular数据格式Transactional数据格式 案例研究之购物篮分析 数据准备使用数据为clementine自带的Baskets1n数据集 该数据集样本量为1000 每笔交易包含了顾客的卡号 性别 年龄 收入 付款方式等一系列个人信息 以及其购买的各种食品清单 该数据集为Tabular格式的数据 研究目的为超市货架的摆放提供科学的依据 为超市商品促销决策提供支持 案例研究 购物篮分析 加入type模块对变量类型进行设置 购物篮分析 将CARMA模块加入流中 并双击打开进行参数设置 点击 点击 购物篮分析 对Model选项卡进行设置 修改RuleSupport RuleConfidence以及RuleSize的大小 点击此处 打开Model选项卡编辑 对这三个选项进行编辑以控制输出的规则的数目 购物篮分析 对Expert选项卡进行设置 如果对CARMA算法比较了解的用户 可以对该选项卡进行设定以获得使CARMA模块具有更好的性能 选择此项 则输出的规则中后项 consequent 只能由一个元素 选择该选项可以让CARMA算法周期性的剔除掉当前不太重要的规则 加速建模 设定周期的大小 周期设定的越小 则越省内存 但是CARMA算法执行时间常 反之 则短 设定该选项可以加速CARMA算法的执行 其大致思想是 一开始先给定一个较高的support值 将不显著的规则排除在外 然后再一次降低support值 设定support值降低的速度 选择该项 则CARMA模型会输出不包含antecedent的规则 购物篮分析 执行后建立的模型会显示在Canvas内 共产生16条规则 每一行分别显示了一组规则 以及度量该规则的一组指标 如 Lift support等 点击该图标可以按指定规则筛选出自己想要的规则 生成对应规则集的节点 包括三种节点 SelectNode FilteredNode以及Ruleset节点 购物篮分析 置信度 Confidence 最高的前三个规则 Cannedveg Beer Frozenmeal Frozenmeal Beer Cannedveg Cannedveg Frozenmeal Beer 促销 购物篮分析 CARMA模型可以直接放在流中对数据进行打分预测 scoring 在打分之前可以双击模型打开Settings选项卡进行相关的参数设置 设定用于预测的规则个数 为选取规则设定标准 从而可以根据该规则选出最显著的n条规则 n由上一个选项设定 设定该项 则允许用于预测的n条规则可以有相同的后项 即可以允许几条规则有相同的预测结果 勾选该项 则在应用规则进行预测之前 系统会剔除掉不符合要求的数据行 不对其进行预测 购物篮分析 对CARMA模型设置好了以后就可以将CARMA模型加入流中对数据进行预测了 本文仅用一条规则进行预测 结果存入表中 见下页 购物篮分析 预测值 预测置信度 所使用规则的编号 购物篮分析 用CARMA模型预测顾客的购买行为 Confectionery Freshmeat Dairy Wine 购物篮分析 除了直接使用生成的CARMA模型进行预测外 还有一种预测方式即使用RuleSet 使用Generate菜单生成想要的RuleSet节点 并将该节点放入流中进行预测 点击确定以后可以生成一个规则集节点 将该节点加入流中就可以进行预测了 案例研究之网络日志分析 数据准备使用数据为某网站五天的访问日志 该数据集记录数为173665 每行记录对应用户对服务器的一个页面请求 记录了用户IP地址 请求时间 请求页面URL 访问协议 请求状态以及端口号等信息 本文为了简化仅引入前三个变量 且页面已经过分类 访问已按事务划分 该数据集为Transactional格式的数据 研究目的找出用户的访问模式 为网站结构上的调整和网站经营决策提供支持 网络日志分析 加载数据集 网络日志分析 使用CARMA模块来处理Transactional格式的网络日志数据 并从中找出关联规则 双击打开打开Fields选项卡进行编辑 勾选该项 将CARMA模型处理的数据格式改为Transactional格式 指定数据的唯一标识 标识相同的记录属于同一个事务 该栏用以指定交易数据字段 本文中这里指定的是当前请求的页面种类 网络日志分析 双击打开Model选项卡进行编辑 设定RulesSupport RuleConfidence以及RuleSize等参数 网络日志分析 查看CARMA模型生成的规则集 网络日志分析 数据中定义的第一类页面为娱乐新闻版面 第二类是灌水版面 整合 将灌水版和娱乐新闻版整合为一个 我主娱乐 新版 值得注意的问题 CARMA模型运算速度不是最快的 但是它只需要对数据集一至两遍的扫描就可以构造规则集 CARMA模型及可以处理Tabular格式的数据 也可以处理Transactional格式的数据 CARMA模型中需要设定的RuleSupport的大小 而不是Support CARMA模型不能处理数值型的数据 CARMA算法原理 Carma算法也包括两个部分寻找频繁项集在频繁项集的基础上产生关联规则Carma寻找频繁项集的过程又分为PhaseI和PhaseIIPhaseI 产生频繁项集的超集 即产生潜在频繁项集V在PhaseI中可以随时调整最小支持度PhaseII 对潜在频繁项集V进行删减得到最终的频繁项集 CARMA算法原理 初始V为空集 将事务按照序号排序 逐条读入事务数据 并计算以下三个整数存储在V的支持格 SupportLattice 中 Count v v被插入V以后在事务数据库中出现的次数firstTrans v v被插入V时所在事务的事务序号maxMissed v v被插入V之前已读入的事务个数 例如 项集 a b 在j时刻进入V 当j时刻时以上三个整数的情况 CARMA算法原理 根据Count v maxMissed v 定义了v项集的支持度的上限和下限 minSupport v 是项集的实际支持度maxSupport v 用来判断项集v用来是否可以保留在V中 CARMA算法原理 PhaseI中V产生的基本过程 初始V为空集 此时只可添加1 项集 读入第i条事务数据v 给出当前的最小支持度 i 在计算过程中 算法自动调整最小支持度 即给每个事务以一个最小支持度 会形成一个最小支持度序列t个事务 1 2 3 如果v是1 项集 如果第一次出现 则令Count v 1 maxMissed v 0 1 项集的maxMissed v 规定为0 firstTrans v i 且将v加入V 1 项集自动进入V 如果不是第一次出现 则Count v Count v 1 CARMA算法原理 如果v是k 项集 k 2 则先按前述方式处理包含的所有1 项集 且 如果第一次出现 判断该k 项集是否可以进入V 且令Count v 1 firstTrans i 且如果不是第一次出现 则项集各子集的Count v Count v 1 修剪 默认每读入500个事务作一次修剪 从效率角度考虑 其实可以读入一条修剪一次 即判断支持格中所有k 项集的maxSupport v 如果小于当前的最小支持度 i 则剔除相应项集出V CARMA算法原理 在PhaseI阶段 k 项集v进入V的主要原则如果一个项集是频繁项集 则其所有子集必定也是频繁项集 反之 如一个项集的某个子集不是频繁项集 则该项集必定也不是频繁项集 Carma在决定k 项集v进入频繁项集V时 应确保v的所有真子集已在当前事务之前进入V中 这是v进入V的条件之一 要看所有子集 若2项无所谓 若3项则需要检验其2项子集是否也在内 项集v加入V的必要条件表述为 i为当前的事务序号 即v的所有真子集w都是频繁项集且已在当前事务之前进入V中 CARMA算法原理 在PhaseI阶段 k 项集v进入V的主要原则判断v的真子集时应从包含项目较多的子集开始判断 如果包含项目较多的子集已在V中 则包含项目较少的子集也一定在V中 因此 不必检查所有子集 只需要检验那些包含项目最多的子集即可 为提高效率不必检验所有真子集 只需要检查那些 其中 w v 为所包含的项目数k CARMA算法原理 计算maxSupport v 的关键是计算maxMissed v maxMissed计算的依据一 其最大子集的频繁程度在第i个时刻 v的具有最大firstTrans的真子集w w v 1 其支持度一定大于v的 即 CARMA算法原理 计算maxSupport v 的关键是计算maxMissed v 依据二 用户以往定义的最小支持度的情况 在i 1时刻 以往最小支持度序列表示为 i 1 2 3 i Carma中定义了关于 i的天花板 ceilingof 序列 记为天花板的含义是 当 j i时 j 1 2 i 1 当 j i时 j 1 2 i 1 例如 0 3 0 7 0 9 0 5 CARMA算法原理 计算maxSupport v 的关键是计算maxMissed v 依据二 用户以往定义的最小支持度的情况总之有 主要取决于以往的一系列最小支持度 b 0 1 3 1 1 CARMA算法原理 PhaseI举例事务序列T a b a b c b c 定义的支持度阀值序列 0 3 0 9 0 5 V t1 a b 1 0 3 V a b t2 a b c 2 0 9 V a b c a b a b的maxSupport均大于0 3 不能剔除出V a 0 1 1 1 1 b 0 1 1 1 1 a 0 1 2 1 1 b 0 1 2 1 1 c 0 2 1 0 5 0 5 a b 1 2 1 0 5 1 t3 b c V a b c a b b c 1 0 5 a 0 1 2 0 66 0 66 c 0 2 2 0 66 0 66 a b 1 2 1 0 33 0 66 b c 1 3 1 0 33 0 66 maxMissed fir