1.1研究意义
信息技术的迅速崛起和快速发展使得每个行业甚至每个单位都积累了大量的数据。这些数据总是以一定形式存储在各种类型的商业数据库或者文件系统中,并且蕴含了丰富且至关重要的信息。但是,只依赖数据库的相关技术和统计学的相关方法来查找这些蕴含的信息是很困难的。因此,数据挖掘(Data Mining)应运而生,最初是为了发现在大量数据集中蕴含的不容易被专业人员发现的有价值的信息[1]。数据挖掘是值得众多学者和公司投入更多的金钱和时间去继续深入研究和应用的一门技术。
Agrawal提出的关联规则挖掘是数据挖掘众多领域中具有巨大价值的研究方向以及研究热点之一,最初目的是为了发现事务数据库(Transaction Database)中不同商品之间的潜在规则。随后大量的研究人员对关联规则挖掘问题进行了大量更深入的研究。关联规则挖掘算法一般分为两个部分,第一个部分是从事务数据库中挖掘频繁项集,所用的方法就称为频繁项集挖掘算法;第二个部分是从频繁项集中挖掘关联规则,广泛采用“支持度-置信度”模型。目前第一部分的研究主要是解决如何使算法运行在海量数据中依然具有良好的效率和性能问题,并让该算法可以在不同领域中都得以应用。而第二个部分的研究主要是解决如何从频繁项集中挖掘出更有效果的、更加可信的、更容易理解的、用户更感兴趣的关联规则的问题。
比较经典的频繁项集挖掘算法包括以下三种:Apriori 算法、FP-Growth(Frequent Pattern-Growth)算法和Eclat(Equivalence class traversal)算法,这三种算法各有优劣,Apriori算法需要通过多次扫描数据库,从而统计出每个项目对应的支持度,然后从候选项集中查找出频繁项集,这个过程会产生大量的候选项集[2]。FP-Growth算法则规避了Apriori的缺点,仅读取两次数据库,不产生候选项集。但是,该算法需要构造新的数据结构,即 FP-tree(Frequent Pattern- tree),然后由 FP-tree递归挖掘频繁项集,并且该算法在处理稀疏型数据集的时候,其性能也会大大降低。Eclat算法则是基于垂直型数据的典型算法,仅读取一次数据库,并且可以快速求出每个项集的支持度,通常情况下,Eclat算法的运行效率都会高于Apriori算法[3]。
对于从频繁项集中挖掘关联规则这部分而言,最早采用“支持度-置信度”模型来发现关联规则。该模型的确能够提取频繁项集中的前项集和后项集之间隐秘存在的重要关系,但是,根据此模型不管用户设定的最小支持度是高是低,挖掘出来的关联规则都会存在着一些不足[4]。因此很多研究者通过引入不同定义的兴趣度,排除一些无用的规则,进而防止产生对用户有误导作用的规则。
关联分析方法是数据挖掘中常用的方法之一,它的主要作用是从大型事务数据库中挖掘隐藏的、有用的知识和信息。例如,大型商场每天有成百上千名顾客购买商品,商家记录着每位顾客购买的商品种类、购买方式和消费金额等信息。然而,商场庞大的销售记录数据中潜藏着令人无法预料的商机,使用关联规则挖掘技术,就可以从这些购买记录中发现交叉销售的商机,利用挖掘出的知识,商场就可以采取促销或捆绑销售手段来进一步提高商场销售利润。当然,关联规则挖掘不仅可以应用在商场中,还可以应用于其他领域,如生物医疗、科学分析以及社会研究。可见,关联分析技术在未来非常具有吸引力,且应用前景一片光明。
1.2 国内外研究现状、水平和发展趋势
数据挖掘技术最早起源于国外,其研究方向非常多。解决分类问题的最常见的方法是决策树归纳,相应的算法包括C4.5算法、ID3算法、ID4算法、IDS算法和Quest算法[5]等。解决聚类问题的数据挖掘技术和方法也有多种,常见的聚类的方法有k-means 算法、基本凝聚层次聚类算法等。在国内,1993年,国家自然科学基金首次同意并大力支持数据挖掘技术的研究,全国各个高校和研究所都投身进入数据挖掘领域。以清华大学为首的包括中国科学院计算技术研究所、空军第三研究所等相继开展了知识发现基础理论及其应用研究。北京大学也开展了对数据立方体代数的研究,复旦大学、中国科学技术大学、浙江大学和中国科学院数学研究所等开展了关联规则优化算法的研究[6]。南京大学、上海交通大学等单位对非结构化数据的知识发现和Web数据挖掘等领域展开了研究[7]。关联规则数据挖掘首先由Agrawal,Imiehski和Swami等提出,著名的Apriori算法由Agrawal和Srikant提出。在国内,高校和研究所的大量学者和专家们对关联规则挖掘进行了深入的研究。屈鑫乙等利用任何一个频繁k+1项集均可以表示一个频繁k项集与一个频繁1项集的交集这一性质产生频繁项集[8]。边根庆等通过富裕项和事务权重,计算项的权重支持度,从而得到频繁项集[9]。陈志飞等人通过判断连接必要性,排除无用交连接来减少事务数据库匹配的时间开销[10]。
参考文献:
[1] 肖文, 胡娟, 周晓峰. 基于MapReduce计算模型的并行关联规则挖掘算法研究综述[J]. 计算机应用研究, 2018.
[2] 杨秋翔,孙涵.基于权值向量矩阵约简的Apriori算法[J]. 计算机工程与设计,2018.
[3] 高强, 张凤荔, 陈学勤. 基于改进 Eclat 算法的资源池节点异常模式挖掘[J].计算机应用研究, 2018.
[4] 杨小廷. 基于关联规则的微博话题动态检测与演化分析[D]. 哈尔滨工业大学,2017.
[5] 王晓,王芳,邱玉辉. 经典数据挖掘方法在客户建模中的应用分析. 西南师范大学学报(自然科学版), 2003.
[6] 钱冬云. 数据挖掘中关联规则算法的研究[D]. 天津大学, 2006.
[7] 孔芳. 数据挖掘技术中关联规则算法的研究[D]. 江南大学, 2008.
[8] 屈鑫乙, 王迪, 刘滏. 关联规则挖掘Apriori算法的一种改进[J]. 中国市场, 2016.
[9] 边根庆, 王月. 一种基于矩阵和权重改进的Apriori算法[J]. 微电子学与计算机, 2017.
[10] 陈志飞, 冯钧. 一种基于Apriori算法的优化挖掘算法[J]. 计算机与现代化,2016. |