数据挖掘

• 参数化方法

优点是用少量的参数简化了建模问题,
缺点是初始假设在许多实际问题中不成立,导致误差过大。

包括分类、回归等模型

• 非参数化方法

仅假定近似的输入会产生近似的输出,这类方法没有假设任何先验密度或参数形式,没有单个全局模型,仅估计局部模型,局部模型仅受邻近训练样本的影响。

包括关联规则模型

关联规则

       是在无指导学习系统中发现局部模式的最常见形式。

关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务。（频繁项集产生所需的计算开销远大于产生规则所需的计算开销）

• 频繁项集产生：其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集（frequent itemset）。
• 规则的产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。

基本概念

购物篮分析的重要性不言而喻，而其可应用性则由关联分析完成。购物篮是一个顾客在一次事务中所购买商品的集合，事务是一个明确定义的商业行为，常称为购物篮事务（market basket transaction）。

一个事务T，包含一个唯一标识TID，以及项目的集合（如下图所示）。

项目 item 对交易来说就是指一个商品（比如：尿布）

项目的集合则称为项集 itemset（比如：{啤酒，尿布}）

根据其包含的项目数 i , 称为 i-项集，比如{啤酒，尿布} 该项集为 2-项集

所有项集的合集则称为全项集 itemsets 。

关联规则 association rule : 如 {啤酒} → {尿布} ，表征由项集 {啤酒} 指向项集 {尿布} ，关联规则都含有方向。
形如 X→Y的蕴涵表达式，其中X和Y是不相交的项集，即 X∩Y=∅ 

关联规则的强度可以用它的支持度（support）和置信度（confidence）来度量，支持度是对规则重要性的度量，而置信度是对规则准确性的度量，那么对于产生的规则我们也就能判断它们的实用性了。

支持度 support ：项集{ 啤酒, 尿布 }在全项集中出现的概率。通常用项集出现的频率去估计其概率。从概率的角度去解释即 P( {啤酒，尿布} ) 。

置信度 confidence ：在先决条件 {啤酒} 发生的条件下，由关联规则 {啤酒} → {尿布}  推出 {尿布} 的概率 ， 表征关联规则正确的概率。从概率的角度去解释即 P( 尿布 | 啤酒 ) 。

格结构（Lattice structure）常被用来枚举所有可能的项集，一般来说，排除空集后，一个包含k个项的数据集可能产生2^k −1个频繁项集

暴力搜索（Brute-force）发现频繁项集的一种原始方法是确定格结构中每个候选项集（candidate itemset）的支持度计 数。为了完成这一任务，必须将每个候选项集与每个交易进行比较，如下图所示。如果候选项集包含在交易中，则候选项集的支持度计数增加。例如，由于项集{Bread, Milk}出现在事务1、4 和5中，其支持度计数将增加3次。这种方法的开销可能非常大，因为它需要进行O(NMw)次比 较，其中N是交易数，M=2^k-1是候选项集数，而w是交易的最大宽度（也就是交易中最大的项数）。

 

关联规则分类

1. 基于规则中处理的数据类型

布尔型：买啤酒 → 买尿布

量化型：月收入5000元 → 每月交通费800元 ； 性别女 → 每月服装花费2000元

2. 基于规则中数据的抽象层次

单层关联规则（所有项在同一个抽象层）： NIKE球鞋 → 安踏球鞋  

多层关联规则（项集涉及不同抽象层）：球鞋 → NIKE 球鞋， 球鞋对于确定了品牌的NIKE 的球鞋的层次要高，相当于是 类目 与 品目 之间跨层次的规则

3. 基于规则中涉及的数据维度

单维关联规则：啤酒 → 尿布，只涉及到用户的购买的物品，表示在一个属性内的规则

多维关联规则：性别=”女” → 职业=”秘书”，涉及到两个属性维度性别和职业

 

Apriori

       Apriori算法是一种用于关联规则挖掘的代表性算法，主要任务就是设法发现事物之间的内在联系

利用支持度对候选项集进行剪枝，这也是Apriori所利用的先验原理：

Apriori定律1：如果一个集合是频繁项集，则它的所有子集都是频繁项集。

Apriori定律2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。

当我们发现{A,B}是非频繁集时，就代表所有包含它的超级也是非频繁的，即可以将它们都剪除。

1、全项集大小为k，设置频度阈值e，e<k
2、生成1-项集L，删去不符合阈值的项，得到频繁项集L1
3、迭代生成i-项集，删除不符合阈值的项，得到频繁项集，直至i=k
      其中生成规则为，已有频繁项集Li-1，其中两项t1、t2的前i-2值相同，则t1、t2可以合并，得到项集Li，然后对其中每一项t，如果t的长为i的子集没有在项集Li-1，则删去项t（满足Apriori定律2）