云计算环境下基于张量分解的缺失关联规则挖掘算法  

Missing association rule mining algorithm using tensor decomposition in cloud computing environment

作　　者：王洪峰[1] 陈立勇[1] 

机构地区：[1]周口师范学院计算机科学与技术学院,河南周口466001

出　　处：《重庆邮电大学学报（自然科学版）》2015年第3期397-403,共7页Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)

基　　金：国家自然科学基金(61103143;70890081);河南省科技厅科技发展计划项目(142300410402);河南省教育厅高校创新人才支持计划项目(2012HASTIT032);河南省教育厅科学技术研究重点项目指导计划基础前沿项目(14B520057)~~

摘　　要：针对云计算环境下由于数据缺失导致关联规则发现误差较高的问题,提出一种基于张量分解的缺失关联规则分布式发现算法,从而建模关联规则、缺失数据并近似它们的置信度。利用Apriori算法进行局部数据相关以获得频繁项集,通过CANDECOMP/PARAFAC(CP)分解方法分解张量置信度,使用共轭梯度算法进行迭代以最小化近似张量的成本,当存在缺失数据的情况下,利用分布式算法将局部相关与全局相关结合发现缺失关联规则。仿真结果显示,算法的平均误差仅为5.55%,最大误差不超过10%,低于其他几种较新的缺失关联规则算法,相比基于聚类的关联规则算法,平均执行时间减少了16.5%。结果表明,所提基于张量分解的分布式算法在缺失数据的情况下,性能优于其他的关联规则算法,能更加有效地提供缺失规则置信度的近似解。For the issue that the relative error of association rules discovering is high caused by underlying data missing on the cloud computing environment, a distributed discovering algorithm of missing association rule based on tensor decomposi- tion is proposed to model association rules, missing data and approximate their confidences. Firstly, Apriori algorithm is used to locally data related so as to obtaining frequent item sets. Then, CANDECOMP/PARAFAC （CP） decomposition method is used to decompose tensor confidence, iterate is done by using conjugate gradient algorithm to minimize the cost of the approximate tensor. Finally, local correlation and global correlation is combined to discover missing association rules by distributed algorithm in the case of missing data. The simulation results show that the average relative error of the proposed algorithm is only 5.55%, the maximum error is less than 10% , which is less than several advanced missing association rule algorithms. The proposed algorithm has reduced average execution time with 16.5% compared with clustering-based association rule algorithm, which indicates that the proposed algorithm has better performance than other missing association rules and it can provide the approximate solution of missing rules confidence.

关 键 词：分布式发现 缺失关联规则 云计算 张量分解 共轭梯度算法 

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