分类的两个步骤

模型创建: 对一个已经事先确定的类别创建模型

每个元组属于一个事先确定的类别，使用分类标签属性予以确定 用于创建模型的数据集叫: 训练集。单个元组称为训练样本 模型可以用分类规则，决策树，或者数学方程的形式来表达。

模型使用: 用创建的模型预测未来或者类别未知的记录
Item1 A B B B C C D D Item2 B A C D B D B C 置信度 C 1 0.33 0.33 0.66 1 1 1 0.5 支持度 S 0.33 0.33 0.33 0.66 0.33 0.33 0.66 0.33
交易号 顾客号 1 甲 甲 2 乙 乙 乙 3 乙 乙
频繁项集及其基本特征

Apriori算法 — 例子
数据库 D
TID 100 200 300 400 Items 134 235 1235 25
itemset sup. C1 {1} 2 {2} 3 扫描 D {3} 3 {4} 1 {5} 3
L1 itemset sup.
{1} {2} {3} {5} 2 3 3 3
L2 itemset sup
{1 3} {2 3} {2 5} {3 5} 2 2 3 2
C2 itemset sup
{1 {1 {1 {2 {2 {3 2} 3} 5} 3} 5} 5} 1 2 1 2 3 2
C2 itemset {1 2} 扫描 D
{1 {1 {2 {2 {3 3} 5} 3} 5} 5}
关联分析
关联规则挖掘的提出

关联规则挖掘的典型案例：购物篮问题

在商场中拥有大量的商品（项目），如：牛奶、面包等，客户将 所购买的商品放入到自己的购物篮中。 通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的 购买习惯


哪些物品经常被顾客购买？ 同一次购买中，哪些商品经常会被一起购买？ 一般用户的购买过程中是否存在一定的购买时间序列？
的事务包含Z

根据置信度和频繁项集F, 产生关联规则。具体方法如下：

conf(X Y) = supp(X)/supp(X Y) 如果 conf(X Y) c 成立，则产生 X Y 的规则, 因为:


supp(X Y) = supp(X Y) s 且 conf(X Y) c

性别＝“女” 职业＝“ 秘书” [1%, 75%] 布尔型关联规则 性别＝“女” 收入 = 2000 [1%, 75%] 数值型关联规则

单维 vs. 多维 关联
age(x, “30..39”) ^ income(x, “42..48K”) buys(x, “PC”) [1%, 75%] buys(x, “Book”) ^buys(x, “Pen”) buys(x, “Ink”) [1%, 75%]
关联规则兴趣度的度量值：支持度

推导出的数据间的相关性可称为规则（或模式），对规则兴趣度的描 述采用支持度、置信度概念。 支持度（Support）：规则XY在交易数据库D中的支持度是交易集 中包含X和Y的交易数与所有交易数之比，记为support(XY)，即 support(XY)=|{T:XY T，TD}|/ |D|，它是概率P（ XY ），具 体表示为：
同时购买商品X和Y的交易 购买商品Y的交易

S =
同时包含项目集X 和 Y 的交易数 总交易数
购买商品X的交易
关联规则兴趣度的度量值：置信度

置信度（Confidence），规则XY在交易集中的置信度是指包
含X和Y的交易数与包含X的交易数之比，记为confidence(XY)， 即confidence(XY)=|{T: XYT，TD}|/|{T:XT，TD}|，它
什么是关联规则挖掘?

关联规则挖掘

简单的说，关联规则挖掘发现大量数据中项集之间有 趣的关联 在交易数据、关系数据或其他信息载体中，查找存在 于项目集合或对象集合之间的频繁模式、关联、相关 性、或因果结构。 购物篮分析、交叉销售、产品目录设计、 lossleader analysis、聚集、分类等。

对于 A C：

support = support({A 、C}) = 50% confidence = support({A 、C})/support({A}) = 66.6%
关联规则挖掘的优缺点

优点

它可以产生清晰有用的结果
它支持间接数据挖掘 可以处理变长的数据

它的计算的消耗量是可以预见的


单层 vs. 多层 分析

那个品种牌子的啤酒与那个牌子的尿布有关系? 相关性、因果分析

各种扩展

关联并不一定意味着相关或因果
最大模式和闭合相集 添加约束

如, 哪些“小东西”的销售促发了“大家伙”的买卖？
关联规则挖掘的基本过程

找出所有的频繁项集 F，其中对于任何的 Z F，在交易集合D中至少 s%
仅当项集的所有子集均为频繁项集.也就是说，如果supp(l)s，当且仅
当 supp(l’ )s, l’ l

因此，我们可以采用层次顺序的方法来实现频繁项集的挖掘。首先，
挖掘一阶频繁项集L1。在此基础上，形成二阶候选项集，挖掘二阶频
繁项集。依此类推。
Apriori算法

连接: 用 Lk-1自连接得到Ck 剪枝: 一个k-项集，如果它的一个k-1项集（它的子集 ）不是频繁 的，那他本身也不可能是频繁的。 伪代码:

104 个频繁1-项集要生成 107 个候选 2-项集，并且累计和检 查它们的频繁性
要找长度为100的频繁模式，如 {a1, a2, …, a100}, 你必须 先产生2100 1030 个候选集
如果最长的模式是n的话，则需要 (n +1 ) 次数据库扫描

重复扫描数据库：

关联规则结果显示 (Table Form )
白
{111, 121, 211, 221} {111, 211, 222, 323} {112, 122, 221, 411} {111, 121} {111, 122, 211, 221, 413}
扩展知识：多维关联规则

单维关联规则（维内关联规则）

关联规则中仅包含单个谓词（维） 通常针对的是事务数据库


应用

关联规则挖掘形式化定义

给定:

交易数据库
每笔交易是：一个项目列表 (消费者一次购买活动中购买的商 品)

查找:

所有描述一个项目集合与其他项目集合相关性的规则

应用


* 护理用品 (商店应该怎样提高护理用品的销售？)
家用电器 * (其他商品的库存有什么影响?) 在产品直销中使用附加邮寄

频繁项集的定义

如果项集满足最小支持度，则称之为频繁项集（高频项集）

频繁项集的基本特征

任何频繁项集的子集均为频繁项集。例如：ABC是频繁项集，则 AB、AC、BC均为频繁项集

在数据库表分区的情况下，一个项集是频繁的，则至少在一个分 区内是频繁的
关联规则挖掘的种类

布尔 vs. 数值型关联 (基于 处理数据的类型)

预测:


典型应用


客户/用户分类
信用评分 目标营销
医疗诊断
分类的相关概念

训练集（Training Set）：由一组数据库记录或者元组构成，每
个记录由有关字段值组成特征向量，这些字段称为属性。

用于分类的属性称为标签属性。标签属性也就是训练集的类别标 记。

标签属性的类型必须是离散的，而且标签属性的可能值的数目越 少越好。

具体应用：利润最大化

商品货架设计：更加适合客户的购物路径 货存安排 ：实现超市的零库存管理

用户分类
：提供个性化的服务
其他典型应用

相关文献的收集

购物篮 = 文档（Document） 项 站的收集

购物篮 = 词句（Sentences） 项 目 =链接文档（Document）
Ck: 长度为k的候选项集 Lk :长度为k的频繁项集 L1 = {frequent items}; for (k = 1; Lk !=; k++) do begin Ck+1 = 从Lk 生成候选项集; 对于数据库中的任一交易 t do 如果 t 中包含 Ck+1中所包含的项集，则计数加 1 Lk+1 = Ck+1 中超过最小支持度的频繁项集 end return k Lk;
关联规则可视化Using Rule Graph
扩展知识：多层关联规则
食品

项通常具有层次 面包 牛奶 底层的项通常支持度也低 某些特定层的规则可能更有 脱脂奶 酸奶 黄 意义 统一 光明 交易数据库可以按照维或层 编码 TID Items 可以进行共享的多维挖掘
T1 T2 T3 T4 T5

数据项为商品，记录集合为交易记录集合 规则为：“购买商品X的顾客，同时购买商品Y”，即X
Y；
设最小支持度为0 .3；最小置信度也为0.3。 分析结果：
商品号 A B C B D B D 数量 14 3 2 3 13 10 12 日期 3/4/95 3/4/95 5/6/95 5/6/95 5/6/95 8/6/95 8/6/95


因此关联规则的挖掘可以转换为频繁项集的挖掘和频繁项集之间的关联。