关联规则

“关联规则”（Association Rules）是数据挖掘的主要技术之一，用于从庞大的数据库中寻找有用或有趣的模式和规则。关联规则最初产生于购物篮分析，它通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客购买行为中隐含的有趣模式，从而指导销售商制订营销策略。单维关联规则特指只涉及单个属性项的关联规则。

设 I = { i1 , i2 ,…, im }是项的集合。设任务相关的数据D 是数据库事务的集合，其中每个事务T是项的集合，使得T ⊆ I。每一个事务有一个标识符，称作TID。设A 是一个项集，事务T 包含A当且仅当A ⊆ T。关联规则是形如A ⇒ B 的蕴涵式，其中A ⊂ I，B ⊂ I，并且A ∩ B =∅。规则A ⇒B 在事务集D 中成立，具有支持度s，其中s 是D 中事务包含A ∪ B（即A 和B 二者）的百分比。它是概率P(A ∪ B)。规则A ⇒ B 在事务集D 中具有置信度c，如果D 中包含A 的事务同时也包含B的百分比是c。这是条件概率P(B |A)。即 support (A ⇒ B ) = P(A ∪ B) confidence (A ⇒ B ) = P(B |A)

同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称作强规则。为方便计，我们用0%和100%之间的值，而不是用0 到1 之间的值表示支持度和置信度。项的集合称为项集。包含k 个项的项集称为k-项集。集合{computer, financial_management_software}是一个2-项集。项集的出现频率是包含项集的事务数，简称为项集的频率、支持计数或计数。项集满足最小支持度min_sup，如果项集的出现频率大于或等于min_sup 与D 中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集。频繁k -项集的集合通常记作Lk。关联规则的挖掘是一个两步的过程：

找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最小支持计数一样。
由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。

如果愿意，也可以使用附加的兴趣度度量。这两步中，第二步最容易。挖掘关联规则的总体性能由第一步决定。

算法背景

关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析。关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不同商品之间联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一次去超级市场，如果顾客购买牛奶，他也购买面包（和什么类型的面包）的可能性有多大？通过帮助零售商有选择地经销和安排货架，这种信息可以引导销售。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。