数据挖掘算法简介 (1/10) - 关联算法

1.   关联算法(Microsoft Association Algorithm

a.    目的

找出事务数据中项目间的相关(每个事务会有一个或多个项目)。例如你购物,一次往往会买许多物件。

b.   原理

分析每个事务中项目间的相关,找出那些显著的相关项目。

c.    方法

Microsoft 决策树算法和 Microsoft 关联规则算法均可用于分析关联,但每种算法找到的规则可能不同。 在决策树模型中,导致特定规则的拆分是基于信息获取,而在关联模型中,规则则完全基于置信度。 因此,在关联模型中,强规则或具有高置信度的规则由于不提供新信息,可能不一定会受到关注。

具体算法有很多,例如Apriori, F-P, Eclat等, Microsoft 关联规则算法主要是应用Apriori 算法。Apriori 算法不分析模式,而是生成候选项集,然后计算该项集的数目。 根据要分析的数据类型,项目可表示事件、产品或属性值。在最常见的关联模型类型布尔变量下,表示将 Yes/No Missing/Existing 值分配给每个属性,如产品名称或事件名称。 例如,市场篮分析就是关联规则模型的一个示例,它使用布尔变量表示特定产品在客户的购物篮是存在还是不存在。然后该算法为每个项集创建表示支持和置信度的分数。 这些分数可用于排名以及从项集中获取感兴趣的规则。

Microsoft 关联算法会遍历数据集以查找同时出现在某个事例中的项。 然后,该算法按照由 MINIMUM_SUPPORT 参数指定的事例数,将符合条件的关联项分组为项集。 例如,一个项集可以定义为“Mountain 200=Existing, Sport 100=Existing”,并且支持的数目可以为 710

也就是说,关联模型基于包含各事例的标识符及各事例所包含项的标识符的数据集生成。 事例中的一组项称为项集 关联模型由一系列项集和说明这些项在事例中如何分组的规则组成。 算法标识的规则可用于根据客户购物车中已有的项来预测客户将来可能购买的产品。 例如以下关系图显示了项集中的一系列规则。

正如该关系图中所示,Microsoft 关联算法可能会在数据集中找到许多规则。 该算法使用两个参数(support probability)来说明项集以及该算法生成的规则。 例如,如果 X Y 表示购物车中的两个项,则 support 参数是数据集中同时包含这两个项(X Y)的事例的数目。 通过将 support 参数与用户定义的 MINIMUM_SUPPORT  MAXIMUM_SUPPORT, 参数结合使用,该算法可控制生成的项集数。 Probability 参数(也称为置信度)表示数据集中既包含 X 也包含 Y 的一部分事例。 通过将 probability 参数与MINIMUM_PROBABILITY 参数结合使用,该算法可控制生成的规则数。

关联算法将根据项集生成规则。规则生成后, 可以使用这些规则根据是否存在该算法标识为重要项的其他特定项,预测数据库中的某项是否存在。 例如,某规则可以为“if Touring 1000=existing and Road bottle cage=existing, then Water bottle=existing”,并且其概率可能为 0.812 在此例中,该算法发现由于购物篮中存在 Touring 1000 轮胎和水壶套,因此预测购物篮中也可能存在水壶。

要注意的是Microsoft 关联规则算法不执行任何一种自动功能选择, 而是分析人员自己提供参数来控制其自身使用的数据。 这些参数设置包括每个项集大小的限制(即每个项集中项目的个数),或对将项集添加到模型中所需的最大和最小支持的设置。也可以通过设置 MINIMUM_PROBABILITY 的值来限制模型生成的规则的数目。

·       若要筛选出太常见因而不受关注的项目和事件,请减小 MAXIMUM_SUPPORT 的值以将常见项集从模型中删除。

·       若要筛选出罕见的项目和项集,请增大 MINIMUM_SUPPORT 的值。

·       若要筛选出规则,请增大 MINIMUM_PROBABILITY 的值。

d.   数据要求

一个关联模型必须包含一个键列、若干离散性输入列和一个离散性的可预测列:

·       单个键列 - 每个模型都必须包含一个用于唯一标识每条记录的数值列或文本列。 不允许复合键。

·       输入列必须为离散列 关联模型的输入数据通常包含在两个表中。 例如,一个表可能包含客户信息,而另一个表可能包含客户购物情况。 您可以使用嵌套表将该数据输入到模型中。

·       单个可预测列- 一个关联模型只能有一个可预测列。 通常它是嵌套表的键列,例如列出已购买的产品的字段。 这些值必须是离散或离散化值。

e.    查看模型

若要浏览该模型,可以使用 Microsoft 关联查看器。 查看关联模型时,Analysis Services 会从各个角度展示相关性,从而您可以更好地理解数据中所找到的关系和规则。 查看器中的项集窗格提供最常见组合或项集的详细明细。 “规则窗格显示从数据中生成的规则列表,添加概率的计算,并根据关联重要性对规则进行排名。 通过依赖关系网络查看器,您可以用可视方式浏览连接各个不同项的方式。 

f.     预测

处理完模型后,可以使用规则和项集来做出预测。 在关联模型中,如果有指定项存在,预测将告诉您有可能发生的项,而且预测可以包含诸如概率、支持或重要性等信息。

g.   自定义参数与性能优化

创建项集和对关联进行计数的过程可能会非常耗时。 尽管 Microsoft 关联规则算法使用优化技术来节省空间并使处理更快,您仍然应该了解在如下条件下可能会发生性能问题:

·       数据集很大,包含许多单个项。

·       设置的最小项集大小过小。

若要尽量缩短处理时间,并降低项集的复杂度,可以在分析数据之前尝试按照类别先对关联项进行分组。

h.   应用

关联规则一个经典的实例就是超市对顾客的购买记录数据库进行关联规则挖掘,可以发现顾客的购买习惯,例如,购买产品X的同时也购买产品Y,于是,超市就可以调整货架的布局,比如将X产品和Y产品放在一起,增进销量。所以,关联规则有时又称之为 购物篮分析(Market Basket Analysis)