论文部分内容阅读
[摘要]提出一种基于目标属性的关联规则挖掘算法，该算法对于不同目标属性的关联规则挖掘是相互独立的，虽然会产生重复工作，但是在并行计算以后效率得到了大大的提高。经过实验分析，对于同样的问题，采用该算法并引入并行计算后，效率要比采用间接挖掘方式的Apriori算法高得多。
[关键词]关联规则 目标属性 数据挖掘
中图分类号：TB9文献标识码：A 文章编号：1671－7597(2008)1020125－01
一、基于目标属性挖掘的原因
本文提出基于目标属性的关联规则挖掘主要出于以下几点考虑:
1．从产品的特性看，不同产品各有各的特点，在挖掘过程中对所有的产品都采用统一的最小支持度并不合适。如果设置min-sup为0，则Apriori算法产生的候选集是巨大的。如果对不同的商品设置不同的最小支持度min-sup，Apriori算法又无法实现。
2．基于目标属性的方法更适合于多层关联规则的挖掘，特别对一些特殊模式的挖掘更有针对性。
3．从挖掘的主体来看，厂家和商家都可以是挖掘的主体，对于目标属性不明确的间接挖掘更多地是从商家的角度考虑，对于目标属性明确的直接挖掘则与厂家有关。关于关联规则的挖掘，大多数研究都是倾向于商家的，然而厂家作为挖掘的主体有着许多优势。
通过以上三个方面的分析，本文提出了基于目标属性挖掘方法，但是并不是要否定传统的关联规则挖掘方法，间接挖掘在挖掘商品之间的关联方面仍有很大的作用，Apriori算法稍加改进也可应用于直接挖掘。
二、基于目标属性的挖掘算法分析
下面对Apriori算法作一些改进以使其适用于基于目标属性的关联规则挖掘。
算法1：
交易数据库为D，商品数组G[max]，其中第n个成员表示商品G[n]，它的最小支持度为min-sup[n]，而在D中包含G[n]的事务集记为Dn。引入G[n]的关联属性集I，指在事务集D。中，所有与商品G[n]共存于一笔交易中的所有商品。以下算法是求G[n]类商品的相关频集，由频集产生的关联规则目标属性为G [n]，对G [max]中每件商品应用以下算法即可求出所有商品的关联规则。
1．if G[n] is frequent Then LI={G[n]}Else Return;
2．get I; //找出G [n]的关联属性
3．for (k=2; Lk-1≠φ; k++) do begin
4．Ck=gen(I，Lk-1)；//根据Lk-1和关联属性集I产生k项候选集Ck
5．for each transaction t∈Dn and G[n]∈t do begin
6．Ct=subset(Ck，t)；//生成事务t的集合（其中t对应于Ck中的项集）
7．for all candidates c∈ Ct do
8．c.count++;
9．end
10．Lk={c∈Ck|c.count≥minsup[n]}
11．end
12．Result=UkLk；
和Apriori算法类似，首先产生1-项集的集合，只含一个项集G[n]，由Lk-1，生成Ck与Apriori有些不同，要将Lk-1和关联属性集I连接得到待验证的候选项集的集合，并根据Apriori性质：频繁集的子集也必须是频繁的，舍弃部分项集，舍弃时需要验证连接后得到的项集，方法是求出这些项集的所有子集，如果有非频繁子集，则舍弃该项集；然后在事务集Dn中统计候选集Ck的每一项集的支持计数count，将count值与最小支持度min-sup[n]比较得到频繁k-1项集的集合Lk。
本文还是采用一个具体例子来说明，事务数据库D如表1，共9个事务，即|D|=9，假设我们要挖掘的目标属性为I1，则可得D中包含I1的事务集D1，如表1，最小支持计数仍为2，寻找I1的频繁。
1．C1={{I1}}}，{I1}的支持计数为|D I|=6，得L1=C1。
2．扫描D1得I1的关联属性集I={I2，I3，I4，I5}。
3．连接L1与I得C2={{I1，I2}，{I1，I3}，{I1 ，I4}，{I1，I5}}。
4．扫描D1计算C2中各项集的支持计数，分别为4，4，1，2。
5．比较最小支持计数和C2中各项计数得L2={{I1，I2}，{I1，I3}，{I1，I5}}。
通过算法1我们得到了基于商品G[n]，最小支持度为min-sup[n]的所有频集，如果我们对G[max]数组中所有商品应用以上算法得出的结果应该是和Apriori算法的结果完全一样(如果最小支持度相同)。不考虑算法1实现的不同商品不同最小支持度的功能，从算法的效率来看，算法1相比普通Apriori算法会产生很多重复工作，比较它们可以看出对于频集{I1，I2}，在普通Apriori算法中只要一次就可求出，但在例1需要两次(求L(I1)和L(I2)时分别计算一次)，对于一个K-项频繁集，采用普通Apriori算法只要一次就可得到，采用算法1需要计算K次。看上去似乎普通Apriori算法的效率要比算法1效率高得多，但是我们注意到算法1中在求解每个商品的频集时，其计算都是完全独立的，也就是说，我们可以同时计算各种商品的频集。
三、结论
在基于目标属性的挖掘算法中，该算法是Apriori算法的改进，但是如果数据量过于庞大，其效率难免受到影响，另外，通过挖掘得出的有趣关联规则是在一定条件下成立的，如果条件改变，如最小支持度、最小可信度发生变化，则需要更新关联规则，这时前一次的挖掘结果如果能被应用到。
新的挖掘中，将大大提高算法的效率。面对这些问题，该算法显得无能为力，然而由于采用了基于目标属性的挖掘模式，诸如遗传算法、判定树、神经网络等技术就得以应用于关联规则的挖掘。
参考文献：
[1]Jiawei Han, Micheline Kamber.数据挖掘概念与技术[M].机械工业出版社.
[2]Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases[C]. In Proceedings of the ACM SIGMOD Conference on Management of Data，2003:207-216.
[3]Agrawal R, Mannila H, Srikant R, et al.Fast Discovery of Association Rules[M]. Advances in Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, CA, 2005.
作者简介：
丁明，女，大学本科，黑龙江农垦农业职业技术学院。
[关键词]关联规则 目标属性 数据挖掘
中图分类号：TB9文献标识码：A 文章编号：1671－7597(2008)1020125－01
一、基于目标属性挖掘的原因
本文提出基于目标属性的关联规则挖掘主要出于以下几点考虑:
1．从产品的特性看，不同产品各有各的特点，在挖掘过程中对所有的产品都采用统一的最小支持度并不合适。如果设置min-sup为0，则Apriori算法产生的候选集是巨大的。如果对不同的商品设置不同的最小支持度min-sup，Apriori算法又无法实现。
2．基于目标属性的方法更适合于多层关联规则的挖掘，特别对一些特殊模式的挖掘更有针对性。
3．从挖掘的主体来看，厂家和商家都可以是挖掘的主体，对于目标属性不明确的间接挖掘更多地是从商家的角度考虑，对于目标属性明确的直接挖掘则与厂家有关。关于关联规则的挖掘，大多数研究都是倾向于商家的，然而厂家作为挖掘的主体有着许多优势。
通过以上三个方面的分析，本文提出了基于目标属性挖掘方法，但是并不是要否定传统的关联规则挖掘方法，间接挖掘在挖掘商品之间的关联方面仍有很大的作用，Apriori算法稍加改进也可应用于直接挖掘。
二、基于目标属性的挖掘算法分析
下面对Apriori算法作一些改进以使其适用于基于目标属性的关联规则挖掘。
算法1：
交易数据库为D，商品数组G[max]，其中第n个成员表示商品G[n]，它的最小支持度为min-sup[n]，而在D中包含G[n]的事务集记为Dn。引入G[n]的关联属性集I，指在事务集D。中，所有与商品G[n]共存于一笔交易中的所有商品。以下算法是求G[n]类商品的相关频集，由频集产生的关联规则目标属性为G [n]，对G [max]中每件商品应用以下算法即可求出所有商品的关联规则。
1．if G[n] is frequent Then LI={G[n]}Else Return;
2．get I; //找出G [n]的关联属性
3．for (k=2; Lk-1≠φ; k++) do begin
4．Ck=gen(I，Lk-1)；//根据Lk-1和关联属性集I产生k项候选集Ck
5．for each transaction t∈Dn and G[n]∈t do begin
6．Ct=subset(Ck，t)；//生成事务t的集合（其中t对应于Ck中的项集）
7．for all candidates c∈ Ct do
8．c.count++;
9．end
10．Lk={c∈Ck|c.count≥minsup[n]}
11．end
12．Result=UkLk；
和Apriori算法类似，首先产生1-项集的集合，只含一个项集G[n]，由Lk-1，生成Ck与Apriori有些不同，要将Lk-1和关联属性集I连接得到待验证的候选项集的集合，并根据Apriori性质：频繁集的子集也必须是频繁的，舍弃部分项集，舍弃时需要验证连接后得到的项集，方法是求出这些项集的所有子集，如果有非频繁子集，则舍弃该项集；然后在事务集Dn中统计候选集Ck的每一项集的支持计数count，将count值与最小支持度min-sup[n]比较得到频繁k-1项集的集合Lk。
本文还是采用一个具体例子来说明，事务数据库D如表1，共9个事务，即|D|=9，假设我们要挖掘的目标属性为I1，则可得D中包含I1的事务集D1，如表1，最小支持计数仍为2，寻找I1的频繁。
1．C1={{I1}}}，{I1}的支持计数为|D I|=6，得L1=C1。
2．扫描D1得I1的关联属性集I={I2，I3，I4，I5}。
3．连接L1与I得C2={{I1，I2}，{I1，I3}，{I1 ，I4}，{I1，I5}}。
4．扫描D1计算C2中各项集的支持计数，分别为4，4，1，2。
5．比较最小支持计数和C2中各项计数得L2={{I1，I2}，{I1，I3}，{I1，I5}}。
通过算法1我们得到了基于商品G[n]，最小支持度为min-sup[n]的所有频集，如果我们对G[max]数组中所有商品应用以上算法得出的结果应该是和Apriori算法的结果完全一样(如果最小支持度相同)。不考虑算法1实现的不同商品不同最小支持度的功能，从算法的效率来看，算法1相比普通Apriori算法会产生很多重复工作，比较它们可以看出对于频集{I1，I2}，在普通Apriori算法中只要一次就可求出，但在例1需要两次(求L(I1)和L(I2)时分别计算一次)，对于一个K-项频繁集，采用普通Apriori算法只要一次就可得到，采用算法1需要计算K次。看上去似乎普通Apriori算法的效率要比算法1效率高得多，但是我们注意到算法1中在求解每个商品的频集时，其计算都是完全独立的，也就是说，我们可以同时计算各种商品的频集。
三、结论
在基于目标属性的挖掘算法中，该算法是Apriori算法的改进，但是如果数据量过于庞大，其效率难免受到影响，另外，通过挖掘得出的有趣关联规则是在一定条件下成立的，如果条件改变，如最小支持度、最小可信度发生变化，则需要更新关联规则，这时前一次的挖掘结果如果能被应用到。
新的挖掘中，将大大提高算法的效率。面对这些问题，该算法显得无能为力，然而由于采用了基于目标属性的挖掘模式，诸如遗传算法、判定树、神经网络等技术就得以应用于关联规则的挖掘。
参考文献：
[1]Jiawei Han, Micheline Kamber.数据挖掘概念与技术[M].机械工业出版社.
[2]Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases[C]. In Proceedings of the ACM SIGMOD Conference on Management of Data，2003:207-216.
[3]Agrawal R, Mannila H, Srikant R, et al.Fast Discovery of Association Rules[M]. Advances in Knowledge Discovery and Data Mining, AAAI Press, Menlo Park, CA, 2005.
作者简介：
丁明，女，大学本科，黑龙江农垦农业职业技术学院。