最大模糊频繁模式挖掘算法  

Mining algorithm of maximal fuzzy frequent patterns

作　　者：张海清[1] 李代伟[1] 刘胤田[1] 龚程[1] 于曦[2] ZHANG Haiqing LI Daiwei LIU Yintian GONG Cheng YU Xi(College of Software Engineering, Chengdu University of Information Technology, Chengdu Sichuan 610225, China College of Information Science and Engineering, Chengdu University, Chengdu Sichuan 610106, China)

机构地区：[1]成都信息工程大学软件工程学院,成都610225 [2]成都大学信息科学与工程学院,成都610106

出　　处：《计算机应用》2017年第5期1424-1429,1465,共7页journal of Computer Applications

基　　金：国家自然科学基金青年基金资助项目(61602064;61502059);成都信息工程大学科研基金资助项目(KYTZ201615)~~

摘　　要：针对有效模式挖掘的组合爆炸及挖掘结果信息如何有效表达的问题,提出了一种基于"核心-牵引"结构的修剪候选模式和考虑项目不确定性的最大模糊模式挖掘算法(MFFP-Tree)。首先,综合分析项目的模糊性,提出模糊支持度,分析项目在事务数据集中的模糊权重,依据模糊修剪策略修剪候选项集;其次,仅扫描数据集一次,就能成功构建模糊模式挖掘树,依据模糊剪枝策略减少模式提取的开销,采用FFP-array阵列结构使得搜索方式更精简,从而进一步降低时空开销。根据基准数据集的实验结果,与最大模式挖掘算法PADS和FPMax*对比分析,MFFP-Tree挖掘出的最大模糊模式能够更准确地反映项目与项目之间的关系;算法的时间复杂度能减半甚至低1个数量级;算法的空间复杂度降低1~2个数量级。Combinatorial explosion and the effectiveness of mining results are the essential challenges of meaningful pattern extraction, a Maximal Fuzzy Frequent Pattern Tree Algorithm （MFFP-Tree） based on base-（second-order-effect） pattern structure and uncertainty consideration of items was proposed. Firstly, the fuzziness of items was analyzed comprehensively, the fuzzy support was given, and the fuzzy weight of items in the transaction data set was analyzed, the candidate item set was trimmed according to the fuzzy pruning strategy. Secondly, the database was scanned once to build FFP-Tree, and the overhead of pattern extraction was reduced based on fuzzy pruning strategy. The FFP-array structure was used to streamline the search method to further reduce the space and time complexity. The experimental results gained from the benchmark datasets reveal that the proposed MFFP-Tree has outstanding performance by comparing with PADS and FPMax ＊ algorithms： the time complexity of the proposed algorithm is optimized by twice to one order of magnitude for different datasets, and the spatial complexity of the proposed algorithm is optimized by one order of magnitude to two orders of magnitude, respectively.

关 键 词：高级模式挖掘 最大模糊模式 模糊支持度 核心-牵引模式结构 模糊修剪策略 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]