[发明专利]一种应用于游戏道具推荐的频繁项集挖掘方法

摘要

本发明实现了一种频繁项集挖掘方法，属于数据挖掘技术领域。本发明方法首先在MapReduce上得到每项出现次数，经过排序以及阈值筛选，剔除不符合的项，得到F‑List，然后划分F‑List得到G‑List，根据G‑List的划分，数据传给Mapper，并经过Mapper处理，将数据传给Reducer，在Reducer上进行MapReduce的挖掘。挖掘首先需要得到每个Reducer上的PPCTree，得到PPCTree后进而得到N‑List，以及各个Reducer上对应项的G‑Subsume，最后根据N‑List和G‑Subsume递归得到最终的频繁项集。本发明依据负载预测合理划分数据，保证负载均衡；通过优化递归挖掘流程，大大减少密集型数据挖掘时间。

主权项

一种频繁项集挖掘方法，其特征在于，包括以下步骤：(1)通过Mapreduce统计原始数据中各项的出现次数；(2)依据各项出现次数筛选出频繁一项，将频繁一项按照出现次数由高到低排序构成F‑List；(3)按照负载均衡原则对F‑List中的各项分组，得到包含项和其所属组号信息的G‑List；(4)Mapper对原始数据进行分配：(4‑1)对每条原始数据的各项按照F‑List中项顺序进行重新排序；(4‑2)从每条原始数据的最后一项开始读取项item，在G‑List中查找item的组号gid，然后以gid作为键key，将数据中排在item前面的所有项作为值value构成键值对<key＝gid，value＝items>，作为Mapper输出的键值对，若组号gid已出现过，则忽略，继续取前一项进行相同操作，直到一条数据处理完毕；(5)Reducer对Mapper输出的键值对进行频繁项集挖掘：(5‑1)根据Mapper输出的key＝gid，将value＝items分配给相应的reducer，reducer构建PPCtree；PPCtree为树状结构，每个节点包含五个属性值：名字、支持度frequency、子节点、前序遍历序号pre和后序遍历序号post；(5‑2)对于PPC‑tree中每个节点Ni，将<Ni.pre,Ni.post,Ni.frequency>命名为PP‑code，将各PP‑code按照pre的升序排序，构建得到F‑List中每个频繁一项的N‑List；(5‑3)构建Reducer的G‑Subsume：其中，A和B表示两个不同的频繁一项，A.gid表示项A的组号，Reducer.gid表示Reducer对应的组号，g(X)表示包含频繁一项X的数据ID的集合，X＝A或B，I1表示频繁一项的集合；(5‑4)递归挖掘，其子步骤如下：a)以F‑List作为第一轮的递归初始数据，在F‑List中取最后一项L，将最后一项L与其G‑Subsume(L)结合，生成频繁二项集，写入结果数组Result；b)在递归初始数据中从前往后逐一取项X，将其N‑List即NX的PP‑code与L的N‑List即NLast的PP‑code进行比较，若X存在于G‑Susbume(L)中，则继续取后一项，否则：当NX的PP‑code的pre小于NLast的PP‑code，且NX的PP‑code的post大于NLast的PP‑code的post，则生成频繁二项集XL，将<NX.PP‑code.pre,NX.PP‑code.post,NLast.PP‑code.frequency>加入频繁二项集XL的N‑List即NXL，且NLast的PP‑code后移；当NX的PP‑code的pre小于NLast的PP‑code，且NX的PP‑code的post小于NLast的PP‑code的post，则NX的PP‑code后移；当NX的PP‑code的pre大于NLast的PP‑code，则NLast的PP‑code后移，直到NLast和NX的PP‑code都遍历完毕；NX的PP‑code遍历完毕后，若最后结果XL的N‑List的PP‑code的支持度之和不满足阈值，则删除XL，若满足则XL为频繁二项集；c)继续从递归初始数据中取下一项，重复步骤b)，直至递归初始数据中最后一项L之前的所有项比较完毕，即得到了以最后一项L为后缀的频繁二项集及其N‑List，写入结果数组Result并将其N‑List作为频繁三项集挖掘的初始数据，该频繁二项集直接与G‑Subsume(L)合并得到以L为后缀的部分频繁三项集，加入数组Result；d)在递归初始数据中取倒数第二项，重复上述步骤a)、b)、c)，直至递归初始数据中所有项操作完毕，即得到了所有的频繁二项集和部分频繁三项集；e)提取仅前缀不一样的频繁二项集作为第二轮的递归初始数据，从最后一项开始，按照与步骤b)‑d)的相同方式处理，得到所有的频繁三项集，并将频繁三项集中后缀有G‑Subsume的项与其G‑Subsume结合得到频繁四项集；f)以此类推，直到最后通过N‑List比较得到唯一的频繁K项集，递归结束；(5‑5)Reducer输出<key＝item∈gid,value＝Result>，至此完成所有的频繁项集挖掘过程。