关联规则的定义及应用优化

为方便起见，下面以交易数据库作为关联分析的主要研究对象。

例3.1：体育用品商场收集存储大量售货数据，这些数据是一条条交易记录，每条记录存储了交易处理的时间、顾客购买的物品、物品的数量及金额等属性的值。通过对销售数据进行关联分析可以发现这些数据中隐含形式如下的规律：

规律1：“购买篮球的顾客中有70%的人同时购买篮球服”；

规律2：“购买羽毛球拍的顾客中有70%的人同时购买羽毛球”等。

这些规律我们称为关联规则。

关联规则的形式化定义如下：

定义3.1（项与全项集，itema nd itemsets）：元素i称为项，如购买的物品“篮球”、“篮球服”等。全项集是所研究的对象数据集中所有项的集合，它是一个非空有限集，记为∑，∑=｛i1，i2，…， im，… ，ip，其中im（m= 1，2，…，p）是一个项，如体育用品商场的售货数据中共有500种商品：｛篮球，足球，排球，……，乒乓球拍，羽毛球拍，……，篮球服，足球服｝。

如果是多维关联规则，项可以是数据集中的属性，读者将会在后面的小节中看到这一点。

定义3.2（项集，itemset）：全项集的子集称为项集，记为I，如｛篮球，篮球服｝是一个项集。项集中项的数目称为项集的长度（size），一个长度为k的项集称为k-项集，如项集｛篮球，篮球服｝的长度为2，它是一个2-项集。

定义3.3（交易，transaction）：形如T（T.id， T.I）的一条数据记录T称为一个交易，其中，T.id为交易标识（如交易号等）， T.I为项集。设X是一个项集，如果XT.I，那么称交易T包含项集X（注：当上下文清楚时，T.id可省略，记为XT）。

定义3.4（交易数据集，transaction data set）：一系列交易组成的集合称为交易数据集，记为D，D=｛T1， T2， …， Tk， …， Tn ｝ ，其中，Tk（k = 1， 2，…， n）是一个交易。

定义3.5（关联规则）：关联规则是形如XY ［Interest］的蕴涵式，X， Y为项集，X∑ ， Y∑，且X∩Y=Φ，X称为输入或左部（LHS），Y称为输出或右部（RHS），并用兴趣度（ Interest）度量评估关联规则。

如购买“篮球”的顾客中有70%的人同时购买“篮球服”是一个关联规则，其左部X是“篮球”，右部Y是“篮球服”，“70%”是该关联规则的一个评估度量兴趣度。

需要注意的是，尽管产生的规则是用蕴涵式“XY”形式表示，但并不表示规则的左部导致右部的发生，例如购买篮球不一定会引起购买篮球服，尽管“篮球篮球服”这条规则成立的可能性很大，但规则并不表示因果关系，它只是对数据之间相关性的一种描述。

数据集中有限的项能产生大量的关联规则，例3.1中，由购买物品项集“篮球、足球、篮球服、足球鞋”，可能产生大量关联规则，如：“篮球篮球服”、“篮球服篮球”、“篮球和足球篮球服和足球鞋”、“篮球、篮球服、足球足球鞋”等，我们发现，一条关联规则可以有一个或多个输入或输出项，它的一个输出项也可能是另一条关联规则的输入项，如“篮球服”在第一条规则中作为输出而在第二条规则中作为输入，第三条规则更为复杂，输入与输出都有两个项。可见，关联规则挖掘的规模十分巨大，所有可能的模式都可能被系统地抽取出来，然而大量的规则模式中，只有一小部分是特定用户感兴趣的。用户要在挖掘后评估发现的规则，进一步限制挖掘过程产生的不感兴趣的规则数量，这就要求有更多的度量来辅助挖掘，这种度量被称为兴趣度度量，目的是帮助用户评估得到的关联规则。

与关联规则评估相关的兴趣度度量包括：简洁性、正确性、实用性、新颖性。

简洁性度量用以衡量一个规则结构的复杂程度，复杂结构的规则难以解释与理解，造成其兴趣度降低；正确性度量用以判断规则令人信服的程度有多高，在关联规则中用置信度表示；实用性度量用以判断该规则再次出现的可能性有多大，在关联规则中用支持度表示；新颖性度量用以判断规则是否已被导出的规则集中的另一规则所蕴涵，用以去除冗余规则。有了这些兴趣度度量，可以根据它们对所得到的规则进行评估和选择。（注：有些文献也将支持度和置信度分别称为正确率和覆盖率。）

下面给出支持度和置信度的形式化定义以及计算方法：

定义3.6（ 支持度，support）：关联规则XY在交易数据集D中的支持度是指交易数据集中包含项X和Y的交易数与所有交易数之比，表示在所有交易中同时含有X与Y的概率（P（X∪Y），其中P表示概率），记为support（ XY ）。

支持度表示关联规则出现的概率是多少。它是对关联规则重要性（或适用范围）的衡量，反映了这条规则在所有交易中的普遍程度。

支持度的计算方法：

support（ XY ） =P（X ∪Y） = | ｛T: X ∪YT， T∈D｝ |/ | D | ×100%

式中，|D|是数据集D中的所有交易数。

定义3.7（置信度，confidence）：关联规则XY在交易数据集D中的置信度是指交易数据集中包含项X和Y的交易数与包含X的交易数之比，表示在所有出现了X的交易中出现Y的概率（P（Y | X），其中P表示概率），记为confidence（ XY） 。

置信度表示关联规则正确的概率是多少。它是对关联规则准确度的衡量，反映了关联规则前提成立的条件下结果成立的概率。(www.xing528.com)

置信度的计算方法：

confidence（XY） = P（Y | X） = | ｛T: X ∪ Y T， T ∈ D｝ |/

　　　　　　　　　　　　　　　|｛T: XT， T∈D｝ |×100%

下面是一个关于支持度和置信度计算的例子。

例3.2：某体育用品商场九月份的7000笔销售交易中，购买篮球的交易有1000笔，购买篮球同时购买了篮球服的交易有700笔，有关联规则“篮球篮球服”，下面计算该规则的支持度和置信度：

support（篮球篮球服）=P（篮球∪篮球服）=两者同时购买的交易数/所有的交易数× 100%

　　　　　　　　　　　　=700/7000× 100%=10%；

confidence（篮球篮球服）=P（篮球服|篮球）=两者同时购买的交易数/购买篮球的交易数× 100%

　　　　　　　　　　　　= 700/1000×100%=70% 。

不难发现，一方面，支持度越大的关联规则越重要，应用越广泛；另一方面，有些关联规则虽然具有较高的置信度，但支持度却很低，说明该关联规则虽然很准确，但并不普遍，因而并不重要，比如，篮球只有一个人买，但是这个人每次购买篮球时，一定会购买篮球服，尽管这条规则置信度很高（正确率100%），但仅适用于100000条销售记录中的一条，根据这个规则可以重新安排货架，但意义不大，因为这一事件不太可能发生，这可能意味着此关联规则并不是很重要（因为其支持度很低），或者出现了错误的数据（如，“男性和怀孕”）。

一般地，支持度高、置信度低的规则很少是正确的，但可以经常使用；支持度高、置信度高的规则多数情况是正确的且可以经常使用；支持度低、置信度低的规则很少是正确的且很少被使用；支持度低、置信度高的规则多数情况是正确的，但很少被使用。因此，置信度、支持度满足什么样的值才是有趣的规则呢？为了发现符合特定应用和用户感兴趣的关联规则，需要给每个度量指定一个可以由用户控制的阈值。常用的是最小置信度阈值（min_conf）和最小支持度阈值（min_supp）。前者是用户规定的关联规则必须满足的最小置信度，它反映了关联规则的最低可靠度；后者是用户规定的关联规则必须满足的最小支持度，它反映了关联规则的最低普遍程度。（注：最小置信度阈值、最小支持度阈值一般由用户和领域专家设定。）

定义3.8（强关联规则）：强关联规则是指同时满足用户定义的最小支持度阈值和最小置信度阈值的关联规则。相反，不满足用户定义的最小支持度阈值和最小置信度阈值的规则，表示它们可能是噪声、少见或异常情况，称为弱关联规则。

综上，给定一个交易数据集D，挖掘关联规则的问题就是产生支持度和置信度分别大于用户给定的最小支持度阈值和最小置信度阈值的强关联规则。但需要注意的是，支持度和置信度度量可以清除一部分被认为是“无趣”（相对兴趣度度量而言）的规则，但并不说明所有强关联规则对所有用户都是有趣的，也就是说，支持度-置信度框架的关联规则挖掘对于大多数应用是有用的，但在某些情况下支持度-置信度框架也可能会产生误导，下面看一个例子：

例3.3：某体育用品商场十月份的1000笔销售交易中，购买篮球的交易有600笔，购买足球的交易有750笔，购买篮球同时购买了足球的交易有400笔，最小支持度阈值min_supp=30%，最小置信度阈值min_conf =60%。

有一条关联规则“篮球足球（support = 40% ， confidence= 66% ） ”，根据支持度-置信度框架，知道该规则是强关联规则。但可以发现买足球的可能性是75%（750/1000），大于66 %。这样的关联规则对用户产生了误导，因为购买篮球和购买足球形成了一种负相关，即购买其中一种反而减少了购买另一种的可能性，在这种情况下，要过滤这样具有误导性的“强”关联规则（XY），可以进一步考虑X和Y出现之间的相关性，因此除支持度、置信度度量外还常用到以下几个度量属性加以辅助。

定义3.9（ 期望可信度，expected confidence）：描述了对于关联规则（XY），在没有任何条件影响时，Y在所有交易中出现的概率［P（Y），其中P为概率］有多大。即没有X的作用下，Y本身的支持度。

定义3.10（改善度，lift）：描述了对于关联规则（XY），X的出现对Y的出现影响多大，是置信度与期望可信度的比值。

改善度越高，X的出现对Y出现的可能性影响越大。一般情况下，有意义的关联规则的改善度应该大于1，只有置信度大于期望置信度，才说明X的出现对Y的出现有促进作用，也说明他们之间某种程度的相关性；如果改善度不大于1，则此关联规则也就没有意义。

改善度可以发现例3.3中出现的负相关性，例3.3中规则的期望可信度为75%，改善度lift=66%/75%＜1。表明购买篮球对购买足球没有促进作用。

这些用于度量关联规则的参数各自都描述了关联规则在某些方面的特性（表3-1），但是被应用得最广泛的仍然是支持度和置信度。

表3-1　四种主要的兴趣度度量参数的计算公式

上述的度量是基于系统客观层面的度量，但一个规则的有用兴趣程度最终取决于用户的要求，只有用户可以决定规则的有效性、可行性，这属于另一个用户主观层面的度量，这方面的应用可以采用一种基于约束（constraint-based）的关联规则挖掘。

挖掘关联规则在实际应用中非常有价值。已经知道可以根据关联规则在商品销售方面做各种促销活动，例如商家将顾客经常同时购买的商品摆放在邻近的位置，或者对顾客进行有针对性的广告宣传以增加销售量。但也应该注意的是，在应用关联规则时，有时很难决定利用所发现的关联规则可以做些什么，比如，在超市货架的摆放策略上，按照发现的关联规则把相关性很强的物品放在一起，反而可能会使整个超市的销售量下降，因为顾客如果可以很容易地找到他要买的商品，他就不会再买那些本来不在他购买计划内的商品。另外，有些关联规则XY，其支持度和置信度都很低，却常常会在超市货架上摆放在一起（如可口可乐饮料和百事可乐饮料）。因此，即使是利用数据挖掘得到的知识，在采取任何行动之前也一定要经过更多的分析和实验。