一种关联规则挖掘方法及其系统

1.一种关联规则挖掘方法，其特征在于，包括：
由频繁K项集生成K+1项集；
执行多个并行的映射Map任务，其中，每个Map任务根据为其分配的数据行偏移量范围，从事务数据集中读取相应范围的数据，并将读取到的数据转换为对，其中，key1为Map任务为读取到的数据分配的标识，value1为读取到的数据内容；以及，统计K+1项集在该对中的频繁计数值，并将统计结果输出为对，其中，key2为K+1项集，value2为统计得到的频繁计数值；
通过执行简化Reduce任务获取所有Map任务输出的对，将key2值相同的对中的value2值相加，得到K+1项集在所述事务数据集中的频繁计数值，根据K+1项集的频繁计数值生成满足支持度要求的频繁K+1项集，并根据所述频繁K+1项集在判断有满足可信度要求的关联规则时输出该关联规则。
2.如权利要求1所述的方法，其特征在于，根据K+1项集的频繁计数值生成满足支持度要求的频繁K+1项集，具体为：
根据K+1项集的频繁计数值计算其中每个数据项的支持度，取其中支持度大于或等于支持度阈值的数据项组成频繁K+1项集。
3.如权利要求1所述的方法，其特征在于，生成频繁K+1项集后，还包括：若满足结束条件，则结束关联规则挖掘流程。
4.如权利要求3所述的方法，其特征在于，满足结束条件，包括：
达到最大迭代次数；或者，输出的关联规则个数超过关联规则数量阈值；或者，生成的频繁K+1项集为空。
5.如权利要求1所述的方法，其特征在于，所述Map任务分配到多个执行节点执行，其中，一个执行节点执行一个或多个处理任务。
6.一种关联规则挖掘系统，其特征在于，包括：
调用模块，用于根据频繁K项集生成K+1项集后，调用多个并行的处理任务，以及在所述多个并行的处理任务完成后调用汇总任务；
与所述多个并行的处理任务一一对应的处理任务执行模块，所述处理任务执行模块为映射Map任务执行模块，用于根据为其分配的数据行偏移量范围，从事务数据集中读取相应范围的数据，并将读取到的数据转换为对，其中，key1为Map任务为读取到的数据分配的标识，value1为读取到的数据内容；以及，统计K+1项集在该对中的频繁计数值，并将统计结果输出为对，其中，key2为K+1项集，value2为统计得到的频繁计数值；
汇总任务执行模块，所述汇总任务执行模块为简化Reduce任务执行模块，所述Reduce任务执行模块用于，获取所有Map任务输出的对，将key2值相同的对中的value2值相加，得到K+1项集在所述事务数据集中的频繁计数值，根据K+1项集的频繁计数值生成满足支持度要求的频繁K+1项集，并根据所述频繁K+1项集在判断有满足可信度要求的关联规则时输出该关联规则。
7.如权利要求6所述的系统，其特征在于，所述汇总任务执行模块进一步用于，根据K+1项集的频繁计数值计算其中每个数据项的支持度，取其中支持度大于或等于支持度阈值的数据项组成频繁K+1项集。
8.如权利要求6所述的系统，其特征在于，还包括：
判断模块，用于在生成频繁K+1项集后，若判断满足结束条件，则结束关联规则挖掘流程。
9.如权利要求8所述的系统，其特征在于，所述判断模块进一步用于，当判断达到最大迭代次数，或者判断输出的关联规则个数超过关联规则数量阈值，或者判断生成的频繁K+1项集为空时，结束关联规则挖掘流程。

一种关联规则挖掘方法及其系统\n技术领域\n[0001] 本发明涉及通信领域中的数据挖掘技术，尤其涉及一种关联规则挖掘方法及其系统。\n背景技术\n[0002] 在数据挖掘处理中，关联规则(Association Rule)的数据挖掘目的，是发现在大量的数据项之间存在的值得关注的关联或相关关系，典型应用是零售业的购物篮分析。所谓购物篮分析是指对数据进行关联规则研究有助于发现交易数据库中不同商品(或不同项)之间的联系，找出顾客购买行为的模式，例如，如果面包和牛奶经常被顾客同时购买，则把它们摆放在一起有助于增加两种商品的销售量。为了衡量一条规则的重要程度，关联规则通常采用支持度(support)和可信度(confidence)作为度量标准。支持度可以表示商品在超市销售中的重要程度，可信度反映了商品之间的关联程度。如果在购买面包的交易中，有60％的交易既购买了面包又购买了牛奶，则称关联规则 (表示如果购买面包则购买牛奶)的可信度为60％。\n[0003] 关联规则 (表示A与B同时存在)在事务数据库D中的支持度，可用概率P(A∪B)表示；\n[0004] 关联规则 在事务数据库D中的可信度，是在事务数据库D中的那些包含A的事务中，B也同时出现的概率，即条件概率P(B|A)。\n[0005] 一个项集X在事务数据库D中的支持度，是事务数据库D中包含X的事务count(X)占事务总数N的百分比，即概率P(X)。对于一个项集X，如果其支持度大于或等于预先给定的支持度阈值min_sup，则称X为频繁项集(FI：Frequent Itemset)或频繁模式。\n[0006] 现有技术中，关联规则的数据挖掘处理一般包括两部分：\n[0007] 第一部分：找出所有支持度大于等于最小支持度阈值的频繁项集；\n[0008] 第二部分：由频繁项集生成满足可信度阈值的关联规则。\n[0009] 上述第一部分工作是相当费时的，而第二部分工作在第一部分的基础上较容易实现，因此关联规则挖掘算法的总体性能主要由第一部分工作决定。\n[0010] 现有技术中的Apriori算法是一种经典的挖掘布尔关系规则频繁项集的算法。\nApriori算法在进行上述第一部分工作，即，找出频繁项集时，需要反复扫描数据库，当面临海量数据挖掘时，由于内部存储器容量的限制，数据无法全部加载到内部存储器当中运算，甚至无法在单机(或单节点)上存储，而且，Apriori算法作为一种串行算法，在一定程度上限制了挖掘的效率。\n发明内容\n[0011] 本发明实施例提供了一种关联规则挖掘方法及其系统，以解决现有关联规则挖掘处理效率低的问题。\n[0012] 本发明实施例提供的关联规则挖掘方法，包括：\n[0013] 由频繁K项集生成K+1项集；\n[0014] 执行多个并行的映射Map任务，其中，每个Map任务根据为其分配的数据行偏移量范围，从事务数据集中读取相应范围的数据，并将读取到的数据转换为对，其中，key1为Map任务为读取到的数据分配的标识，value1为读取到的数据内容；以及，统计K+1项集在该对中的频繁计数值，并将统计结果输出为对，其中，key2为K+1项集，value2为统计得到的频繁计数值；\n[0015] 通过执行简化Reduce任务获取所有Map任务输出的对，将key2值相同的对中的value2值相加，得到K+1项集在所述事务数据集中的频繁计数值，根据K+1项集的频繁计数值生成满足支持度要求的频繁K+1项集，并根据所述频繁K+1项集在判断有满足可信度要求的关联规则时输出该关联规则。\n[0016] 本发明实施例提供的关联规则挖掘系统，包括：\n[0017] 调用模块，用于根据频繁K项集生成K+1项集后，调用多个并行的处理任务，以及在所述多个并行的处理任务完成后调用汇总任务；\n[0018] 与所述多个并行的处理任务一一对应的处理任务执行模块，所述处理任务执行模块为映射Map任务执行模块，用于根据为其分配的数据行偏移量范围，从事务数据集中读取相应范围的数据，并将读取到的数据转换为对，其中，key1为Map任务为读取到的数据分配的标识，value1为读取到的数据内容；以及，统计K+1项集在该对中的频繁计数值，并将统计结果输出为对，其中，key2为K+1项集，value2为统计得到的频繁计数值；\n[0019] 汇总任务执行模块，所述汇总任务执行模块为Reduce任务执行模块，所述简化Reduce任务执行模块进一步用于，获取所有Map任务输出的对，将key2值相同的对中的value2值相加，得到K+1项集在所述事务数据集中的频繁计数值，根据K+1项集的频繁计数值生成满足支持度要求的频繁K+1项集，并根据所述频繁K+1项集在判断有满足可信度要求的关联规则时输出该关联规则。\n[0020] 本发明的上述实施例，在用频繁K项集生成频繁K+1项集的过程中，通过多个并行执行的处理任务获取事务数据集中的部分数据，并分别统计K+1项集在各部分事务数据中的频繁计数值，然后再进行汇总，得到K+1项集在整个事务数据集中的频繁计数值，从而生成满足支持度要求的频繁K+1项集以及输出满足可信度要求的关联规则，实现了多个处理任务并行执行，与现有技术相比，提高了关联规则挖掘的处理效率。\n附图说明\n[0021] 图1为本发明实施例中并行关联规则挖掘流程示意图；\n[0022] 图2为本发明实施例中采用Map/Reduce机制实现并行关联规则挖掘流程的示意图；\n[0023] 图3为本发明实施例中的数据挖掘系统结构示意图。\n具体实施方式\n[0024] 下面结合附图对本发明实施例进行详细描述。\n[0025] 在关联规则挖掘过程中，生成频繁项集时，需要用前一个生成的频繁项集生成下一个频繁项集。\n[0026] 参见图1，为本发明实施例提供的关联规则挖掘流程的示意图，包括：\n[0027] 步骤101、生成频繁k项集；\n[0028] 步骤102、利用频繁k项集生成满足支持度要求的频繁k+1项集，根据该频繁k+1项集判断出有满足可信度要求的关联规则时，输出该关联规则；较佳地，可将处理结果输出至分布式文件系统保存；\n[0029] 步骤103、判断是否满足结束条件，若是，则结束本流程；否则，将k值递增并返回步骤102进行下一次迭代过程。\n[0030] 上述流程的步骤103中，结束条件可以包括：达到设定的最大迭代次数，或者输出的关联规则数量达到设定的数量阈值，或者生成的频繁k+1项集为空。\n[0031] 上述流程的步骤102中的利用频繁k项集生成满足支持度要求的频繁k+1项集的过程，可采用Map/Reduce(映射/简化)机制实现。Map/Reduce是一个分布式处理海量数据集的编程模式，通过该机制可让程序自动分布到一个由普通机器组成的超大集群上并发执行。采用Map/Reduce机制实现的生成频繁k+1项集的过程可如图2所示。\n[0032] 参见图2，为本发明实施例中采用Map/Reduce机制实现并行关联规则挖掘流程示意图。以商品购物篮的应用为例，I：{i1，i2，...}为商品集合，D：{T1，T2，...}为购物单集合，最小支持度为min_sup，最小可信度为min_conf，如图所示，最大迭代次数为k的关联规则的流程包括：\n[0033] 根据集合D生成支持度大于或等于min_sup的频繁1-项集。该步骤中，可通过扫描集合D的方式生成满足大于等于支持度阈值min_sup条件的频繁1-项集。项集是指商品的集合，是I的子集。1-项集是指商品集合中只包括1种商品(如i1)，项集的支持度是指该项集在D中出现的次数除以D中交易总次数(如项集i1在D中共出现30次，D中交易总数为100，则该项集的支持度为30％)。如果支持度阈值是20％，则该1-项集会作为频繁1-项集输出。\n[0034] 根据频繁1-项集生成2-项集，2-项集是指商品集合中包括2种商品(如i2，i3)。\n考虑不需要计算每一种2-项集的可能情况，可做剪枝处理。\n[0035] 生成多个并行的Map任务，以及Reduce任务。其中，每个Map任务负责获取集合D中相应部分的数据，并统计2-项集在该部分数据中的频繁计数值；Reduce任务负责对所有Map任务的统计结果进行汇总得到2-项集在集合D中的频繁计数值(例如，集合D中的所有购物单中，i1和i2在同一购物单中同时出现的次数即为2-项集中的{i1，i2}在集合D中的频繁计数值)，根据2-项集的频繁计数值生成满足支持度要求的频繁2-项集，并根据频繁2-项集判断出有满足可信度要求的关联规则时输出该关联规则。\n[0036] 这些Map任务并行执行，其中，对于每个Map任务，执行：\n[0037] 根据为其分配的数据行偏移值范围从集合D获取相应范围的数据，具体可以是：\n根据预先设定的数据行偏移量key的范围，读入集合D的数据，并将读入的数据转换为对，其中，key为Map任务为读取到的数据分配的标识，value为读取到的数据的内容；根据读取到的对，统计2-项集的频繁计数值，并将统计结果输出为新的对，其中，key为2-项集，value为统计出的频繁计数值。\n[0038] 执行Reduce任务，Reduce任务将所有Map任务输出的对中key值相同的对中的value值相加，得到2-项集在集合D中的频繁计数值；根据2-项集的频繁计数值计算2-项集中各项的支持度，例如，可通过计算购物单中同时出现i2和i3的次数与购物单总和的比值得到支持度，删除2-项集中支持度小于min_sup的项，保留其中支持度大于或等于min_sup的项，从而得到频繁2-项集。Reduce任务还可根据得到的频繁2-项集判断是否有可信度大于等于min_conf的关联规则，如果有，则输出该关联规则。\n例如，当包含i2的商品清单中i3也同时出现的概率P(i3|i2)大于或等于min_conf时，输出关联规则i2＝＞i3。\n[0039] 判断当前的迭代次数是否达到k，如果达到，则结束流程；如果没有达到，则进行下一次迭代过程，即利用频繁2-项集生成频繁3-项集，依此类推，直到满足结束条件为止。\n[0040] 上述流程中的Reduce任务的数量可以是一个也可以是多个。如果是多个，则这些Reduce任务可并行执行，其中，每个Reduce任务可从所有Map任务的处理结果中查找key值相同的对进行汇总。\n[0041] 上述流程中，由于通过多个并行执行的Map任务统计K+1项集在事务数据库中的部分数据中的频繁计数值，再根据所有Map任务的统计结果汇总得到K+1项集的频繁计数值，从而实现了多个处理任务并行执行数据处理过程。\n[0042] 上述流程中，较佳地，可将Map任务分配给多个执行节点完成，还可根据节点的负荷情况，将一个或多个Map任务分配给一个节点处理。在处理过程中，各执行节点并行执行被分配的Map任务，若一个执行节点被分配有多个Map任务，则在该节点上，这些Map任务也是并行执行。\n[0043] 基于相同的技术构思，本发明实施例提供了一种关联规则挖掘系统。\n[0044] 参见图3，为本发明实施例提供的关联规则挖掘系统的结构示意图，该系统包括：\n调用模块31、多个处理任务执行模块32(图中只示出3个)、汇总任务执行模块33，还可进一步包括判断模块34，其中：\n[0045] 调用模块31，用于根据频繁K项集生成K+1项集后，调用多个并行的处理任务，以及在所述多个并行的处理任务完成后调用汇总任务；\n[0046] 处理任务执行模块32与所述多个并行的处理任务一一对应，用于执行处理任务，包括：获取事务数据集中相应部分的数据，并统计K+1项集在该部分数据中的频繁计数值；\n[0047] 汇总任务执行模块33，用于执行汇总任务，包括：对所有处理任务的统计结果进行汇总得到K+1项集在事务数据集中的频繁计数值，根据K+1项集的频繁计数值计算其中每个数据项的支持度，取其中支持度大于或等于支持度阈值的数据项组成频繁K+1项集，并根据所述频繁K+1项集在判断有满足可信度要求的关联规则时输出该关联规则。\n[0048] 上述系统可采用Map/Reduce机制，此时，处理任务执行模块32可以是Map任务执行模块，该Map任务执行模块在进行处理时，可根据为其分配的数据行偏移量范围，从事务数据集中读取相应范围的数据，并将读取到的数据转换为对，其中，key为Map任务为读取到的数据分配的标识，value为读取到的数据内容；根据该对统计K+1项集的频繁计数值，并将统计结果输出为新的对，其中，key为K+1项集，value为统计得到的频繁计数值。汇总任务执行模块33可以是Reduce任务执行模块，该模块在进行处理过程中，获取所有Map任务输出的对，将key值相同的对中的value值相加，得到K+1项集的频繁计数值。\n[0049] 判断模块34，用于在生成频繁K+1项集后，若判断满足结束条件，则结束关联规则挖掘流程。例如，当判断模块34判断达到最大迭代次数，或者判断输出的关联规则个数超过关联规则数量阈值，或者判断生成的频繁K+1项集为空时，结束关联规则挖掘流程。\n[0050] 需要说明的是，本发明实施例可应用于Apriori算法的实现过程，以及其他类似算法的实现过程。\n[0051] 从以上描述可以看出，本发明实施例基于Map/Reduce实现并行的关联规则挖掘方法，与现有技术相比，其技术效果包括：\n[0052] (1)算法效率得到提升。针对经典Apriori算法的串行缺点，基于Map/Reduce机制来完成算法最主要的工作(计算频繁项集)，有效解决提高了海量数据关联规则挖掘中的性能效率等问题。将算法代价较大且并行成分较高的计算频繁项集工作并行化可获得较高的并行效率和加速比。\n[0053] (2)存储能力得到提升。采用分布式文件系统解决实现了海量数据关联规则挖掘时的高效存储、冗余备份、负载平衡和并行访问等技术问题。\n[0054] (3)运算规模得到提升和高可扩展性。基于Map/Reduce和DFS结合的集群环境为大规模并行数据挖掘提供了一个坚实的计算平台，同时拥有良好的可扩展性，预计部署节点数达256左右，运算规模的大幅提升有利于解决海量数据挖掘中的许多瓶颈问题，可进一步改善挖掘效果和提高实用性。\n[0055] 显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。