关联规则(65页).ppt

关联规则 鲁明羽 lumingyu@tsinghua.org.cn 大连海事大学计算机学院 智能技术研究中心 关联规则 1、概述 2、关联规则形式化定义 3、Apriori 算法 4、FP-树频繁模式增长法 5、多层关联规则 6、多维关联规则 7、关联规则对发展新方向 1 概 述 (1) 起因 (2) 例子 (3) 一些概念 (1) 起 因 在商店或超市中，由于大量条码机和POS机的广泛使用，顾客的购买事务被记录下来。条码和收款机为商店的积累数据起了较大作用。 为了使商品经营得更好，人们开始分析数据，发现购买某些商品的人同时可能会购买另外一些商品。 如：购买计算机、打印机，还会购买科技书籍。 计算机∧打印机→科技书籍 (1) 起 因 在保险公司发现： 60岁（R）购买了汽车保险（A)、人身意外伤害 保险（B）的人， 50%也会购买人寿保险（C）。 这样就可形成如下规则： R ∧A ∧ B → C （可信度为 50%） 这就是关联规则最初起因。类似的例子还有啤酒与尿布、伐木锯子与帐篷，等等。 在购买的事物中 常常出现购买一 种物品还会购买 另一种物品。说 明这两种物品的 关联。 也可以是多种物品的关联。 (2) 一个购物数据库例子 面包 5 占 62.5% 牛奶 4 占 50% 水果 2 占 25% 面包+牛奶 3 占 37.5% 面包+水果 2 占 25% 面包+水果+牛奶 1 占12.5% 面包+水果+鸡蛋1 占12.5% 支持度 : 购买物占总数的比例。 购买面包支持度为 62.5% ,购买面包和牛奶为36.3% 置信度: 购买面包中又购买牛奶的比例,购买面包中又购买牛奶置信度60% 关联规则: 购买面包又购买牛奶 支持度为36.3%,置信度60% (3) 概 念 项目(item)：一个具体的物品，如面包. 用 i 表示 项目集(Item set): 一组项目称为项目集 I={i1, i2,…in} 如I={面包,水果,牛奶,鸡蛋,蔬菜, 猪肉,黄油 鱼,牛排,鲤鱼,鸡,白菜,大米,花生油} 一个事物T：一次购物记录，如T1={面包,水果,牛奶,鸡蛋} 支持度(s, Support): 在数据库事物中存在某类项目集数占数据库中记录总数的比例。 如：{面包} 5 占 62.5%，则 支持度为 62.5% {面包, 水果, 牛奶 } 1 占 12.5% ，支持度为12.5% (3) 概 念(续1） 置信度(c, Confidence)： 在某类项目集中，同时还存在另一些项目集数，另一些项目集数占某类项目集数的比例。 如:存在{面包} 为 5，存在面包，又牛奶 {面包，牛奶} 3 ，3占5的比例，置信度为 60%，就是说买面包的人也有人不买牛奶的。 这样置信度就很有价值 （3）概 念（续2） 频繁项目集： 某些项目集的支持度超过定义的支持度阈值 如：支持度阈值定义为：30%，例子的中 频繁项目集为{面包,牛奶 }，{面包}，{牛奶}； {水果} 25 %就不是. 关联规则： 用蕴含式规则的形式表示 {面包} {牛奶}，支持度为： 36