基于上三角矩阵构造多叉树的多维关联规则挖掘算法  

A Multi-Dimensional Association Rules Mining Algorithm Based on Upper Triangular Matrix-Tree Union

作　　者：叶涛[1] 于利霞[2] 张亚平[2] YE Tao;YU Lixia;ZHANG Yaping(College of Computer,Qinghai Nationalities University ,Xining 810007,China;School of Computer Science and Technology ,Tianjin University,Tianjin 300072,China)

机构地区：[1]青海民族大学计算机学院,青海西宁810007 [2]天津大学计算机学院,天津300072

出　　处：《软件工程》2017年第6期8-11,4,共5页Software Engineering

基　　金：天津大学-青海民族大学自主创新基金;国家自然科学基金项目(61572351);天津市自然科学基金(15JCQNJC00200)

摘　　要：针对基于Iapriori算法的多维关联规则数据挖掘存在I/O负载过大,候选项集指数倍增加,优化算法随机性强,容易陷入局部最优解等问题。本文提出一种基于上三角矩阵和多叉树结合(UTMTU)的多维关联规则挖掘算法,算法对原数据编码筛选后映射为上三角矩阵,再映射为频繁项集树,实现整个过程只扫描一次数据库而不产生候选项集,将时间和空间成本尽量降到最低,并利用有效属性层次数提高内存和I/O的利用率。通过UTMTU与Iapriori对比分析表明,其算法的效率和精度得到显著地提高,有效改善原始算法的两个瓶颈问题。Many problems exist in the multi-dimensional association rules mining algorithm based on IApriori.The I/O load is too heavy,the size of the candidate set is increased exponentially,and the optimization algorithm is random and easy to fall into the local optimal solution.Accordingly,the paper proposes a multi-dimensional association rules mining algorithm based on Upper Triangular Matrix-Tree Union(UTMTU).The algorithm filters and maps the original coding data to the upper triangular matrix,and then maps it into the frequent item sets.In the whole process,UTMTU only scans the database once and does not generate the candidate item sets,which reduces the time and space cost to the minimum.The utilization rate of memory and I/O is improved by using the number of effective attribute layers.Compared with the algorithm based on IApriori,the efficiency and accuracy of the algorithm based on UTMTU has been effectively improved.Consequently,the UTMTU-based algorithm is more suitable for multi-layer and multi-attribute MARP.

关 键 词：多维关联规则 上三角矩阵 频繁项集树 有效属性层次数 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]