关联规则挖掘Apriori算法的一种改进

2016-10-19 04:10屈鑫乙王迪刘滏
中国市场 2016年36期
关键词:Apriori算法关联规则数据挖掘

屈鑫乙 王迪 刘滏

"

"

"

[摘 要]Apriori算法是关联规则挖掘中的经典算法,但在算法执行中,会多次扫描数据库并产生大量的候选集,导致算法效率降低。在分析Apriori算法的基础上,利用任何一个频繁k+1项集一定可以表示成一个频繁k项集与一个频繁1项集的交集这一性质,产生频繁项集,并减少扫描数据库的次数,提高算法的效率,实验结果也表明,改进算法比Apriori算法有更好的性能。

[关键词]Apriori算法;关联规则;数据挖掘

[DOI]10.13939/j.cnki.zgsc.2016.36.086

1 引 言

随着计算机技术与数据库技术的迅猛发展,如何从海量的数据中寻找出有效的信息成为了数据挖掘问题中的一项重要研究内容。数据挖掘是从大量的数据中挖掘出隐含的、未知的、用户可能感兴趣的和对决策有潜在价值的知识和规则。[1]挖掘关联规则问题可以分解为以下两个子问题:[2]①找出所有频繁项集。这些项集出现的频繁性至少和预定义的最小支持计数一样。②根据定义,由频繁项集产生强关联规则必须满足最小支持度和最小置信度。

R.Agrawal于1994年首先提出了挖掘关联规则的Apriori算法[3],其基本思想是重复扫描数据库,根据频繁项集的超集才可能是频繁项集这一原理,由长度为k的频繁项集进行迭代计算产生长度为k+1的候选集,再对数据库进行扫描判断其是否为频繁项集。

很多文献基于Apriori算法提出改进算法,杨志刚[4]等人提出了基于压缩事务矩阵相乘的改进算法,焦学磊[5]等人提出了基于矩阵的频繁项集发现算法,将数据库信息全部以矩阵表示,该方法仅需要对数据库进行一次扫描,有效地减少了算法执行的时间,Najadat[6]等人对Apriori算法的不足之处进行了讨论,并优化了Apriori算法在剪枝过程中计算量大的问题,崔贯勋[7]等人提出对数据库进行一定的处理,使其成为水平结构再进行计算,但该方法需要占用大量的空间,也使得该方法的提高程度受到了限制。

2 改进的Apriori算法

2.1 算法的相关概念

频繁项集具有如下几个性质:[8]

性质1 频繁项集的所有非空子集都是频繁项集,非频繁项集的超集都是非频繁项集。

性质2 如果频繁k项集还能产生频繁k+1项集,则频繁k项集中的项数必须大于k。

2.2 算法思想

Apriori算法将关联规则的发现过程分成了两个步骤:

(1)找出所有支持度高于用户设定的最小支持度的项集,即发现所有的频繁项集。

(2)通过发现的频繁项集构造出满足用户最小置信度的规则。[9]

但是在执行过程中Apriori算法需要频繁地扫描数据库,这一行为会造成过重的I/O负担[10],改进算法将通过减少数据库扫描次数的方式来减轻I/O负担。

2.3 实例分析

依据上述改进的算法,以一个实例对该算法进行分析。表1为事务数据库,设最小支持度为20%,则最小支持度计数等于2。

2.4 算法实验与分析

为了验证本文改进算法的有效性,将其与Apriori经典算法进行实验对比,测试的数据库选用本校对高校教师的一次调查问卷,数据库中共有1681条记录,数据库中部分记录如表3所示。因为在本次调查中,教师只需要在24个选项中,选出最符合自己意愿的某几个选项,因此数据的存储采用简单二维表进行记录,用以节省存储空间。

采用的实验环境:CPU为Intel Core I7 2.60GHz,内存8GB,操作系统为WIN10 专业版,数据库采用SQL2014,算法采用C#语言编写并在VS2012环境下编译,下图是改进算法与Apriori经典算法在不同支持度下执行时间对比。

不同支持度下两种算法的执行时间对比

改进算法在效率上优于Apriori算法,并且在最小支持度较小时,改进算法的执行时间相对于Apriori算法具有明显优势,但是随着最小支持度的增加,两种算法的执行时间均大幅减少,Apriori算法与改进算法的执行时间开销非常接近,这是因为随着最小支持度的增加,迭代次数减少,运算过程中产生的频繁项集的数量均大幅度减少,使得算法的执行时间减少。

3 结论与思考

本文提出的算法与Apriori算法相比减少了I/O次数,在改进算法中,是以项集中包含元素的数量与最小支持度计数对比判断其是否为频繁项集,不需要对数据库进行多次扫描,而Apriori算法在每次进行剪枝时,需要对数据库进行扫描才能判断生成的项集是否为频繁项集,改进算法是从这一点出发,进行改进从而提高算法的执行效率,减少算法的执行时间。虽然改进算法虽然减少了I/O次数,提高了算法的执行效率,但是算法在执行过程中,需要保存大量的数据,因而需要占用较多的内存空间,因此如何对数据量较大的数据库执行本算法,还有待进一步的研究与改进。

参考文献:

[1]刘华婷,郭仁祥,姜浩.关联规则挖掘Apriori算法的研究与改进[J].计算机应用与软件,2009,26(1):146-149.

[2]Han J. W.,Kamber M.Data Mining:Concepts and Techniques,数据挖掘:概念与技术[M].范明,孟小峰,等,译.北京:机械工业出版社,2001.

[3]Pang-Ning Tan,Michael Steinbach,Vipin Kumar.数据挖掘导论[M].北京:人民邮电出版社,2006.

[4]杨志刚,何顺月.基于压缩事务矩阵相乘的Apriori改进算法[J].中国新技术新产品,2010,30(6):57-58.

[5]焦学磊,王新庄.基于矩阵的频繁项集发现算法[J].江汉大学学报:自然科学版,2007,35(1):43-46.

[6]Najadat H.M.,Al-Maolegi M.,Arkok B..An Improved Apriori Algorithm for Association Rules[J].International Research Journal of Computer Science and Application,2013,(1):1-8.

[7]崔贯勋,李梁,王柯柯,等.关联规则挖掘中Apriori算法的研究与改进[J].计算机应用.2010,30(11):2952-2955.

[8]刘兴涛,石冰,解英文.挖掘关联规则中Apriori算法的一种改进[J].山东大学学报:理学版,2008,43(11):67-71.

[9]熊平.数据挖掘算法与Clementine实践[M].北京:清华大学出版社,2011.

[10]周超发,王志坚,叶枫,等.关联规则挖掘算法Apriori的研究改进[J].计算机科学与探索,2015,9(9):105-108.

3.1.2 人员操作过程不规范

变电工作人员是整个变电设备运行中的直接操作者,是整个变电运作的核心。他们的整体素质、安全防范意识、操作熟练度以及规范度都将直接关乎整个变电运行工作的安全性和稳定性。[5]一方面,因为变电站的需要操控的设备繁多,导致变电工作人员工作次数频繁,但其劳动形式单一,却容易导致变电工作人员丧失工作热情、实际操作中注意力不集中,进而造成操作失误。另一方面,由于一些操作人员缺乏对于变电工作的了解,加之安全意识薄弱、工作态度不严谨、对操作程序不严格执行等,都会大大增加安全事故发生的可能性。

3.1.3 安全管理工作不到位

安全管理工作不到位是造成变电设备工作安全问题的重要原因,主要表现在安全管理工作不科学、不规范。由于缺乏科学的设计,管理制度上存在着安全漏洞,例如安全事故责任划分不清,领导混乱;领导层对员工的安全教育培训不重视,往往以走过场的形式组织安全教育,员工在安全意识、安全技能方面都十分匮乏。一线操作人员是保障变电设备安全运行的关键,但是心无大局,对于安全意识以及安全问题造成的后果没有明确的意识,对于安全工作往往是应付了事;监督人员没有按照规定行使好监督责任,没有及时地做好每日的安全监督记录工作,存在着监督无用的错误想法。这些现象都表明了安全工作只停留在制度层面,而安全管理工作疏忽大意,体现了管理者管理能力、水平仍有待提高。在这种管理状态下,很可能导致安全事故的进一步恶化。

3.2 变电设备安全防范措施

针对变电设备运行中存在的这些主要安全问题,我们需要采取合理的安全防范措施,才能减少甚至根除种种安全隐患。

首先,从人员层面,我们要加强变电运行人员的安全思想教育,让操作人员深刻意识到安全操作的重要性,同时加强员工素质,对变电运行操作人员进行岗前培训,在熟悉设备性能和设备操作流程的基础上,加强其操作的熟练度,培养操作规范性,并使其学会鉴别异常现象和设备维护工作。

其次,从设备层面,我们要增强设备管理,除了每天的例巡检查外,还需要对设备进行不同的等级检查,以便掌握设备的真实运行状况,根据检查结果和实际情况做出快速、有效的综合判断,并及时维修或更换故障设备。在引进新设备时,要从各个阶段对设备质量、运行安全严格把关,依靠在线诊断系统等技术对设备进行实时的检测和评价。

最后,从制度层面,我们要完善管理制度,加强监督机制,对参与变电运行的所有工作人员落实其岗位责任,实行定岗定员制度,同时加强交接班时的安全工作,做到准时交接,记录详细,在交接班时也要注意对口交接,并对现场做进一步的巡查。

4 结 论

输电工程和变电工程是电力供应中的重要且复杂的环节,两者的安全与稳定,是我国电力系统正常运行的关键保障,更是我国经济发展的重要保障工作之一。因此,为了保障变电设备安全运行,这就需要我们各部门的共同合作,加强安全意识培训,提高变电工作人员工作能力,增强其责任意识,严格按照相关规定操作电力设备,及时检修和更换设备,做到防患于未然。在保障输电设备安全运行的过程中,我们需要准确、全面、细致地识别其故障模式,对症下药,推动我国电力行业持续、健康发展。

参考文献:

[1]李盛盛.输电设备状态监测主站系统的设计与开发[J].电力信息与通信技术,2010,8(11):14-18.

[2]李涛,马薇,黄晓蓓.基于全寿命周期成本理论的变电设备管理[J].电网技术,2008,32(11):50-53.

[3]徐兴德.输电线路运行中存在的主要问题与维护管理措施[J].科技与创新,2014(17):36-37.

[4]张兵.输电线路运行中的安全隐患管控及预防对策探析[J].科技创业家,2012(21).

[5]余令勇,汪红利.试论变电运行安全管理与事故的防范[J].广东科技,2012,21(24):80-81.

猜你喜欢
Apriori算法关联规则数据挖掘
基于并行计算的大数据挖掘在电网中的应用
基于Hadoop平台的并行DHP数据分析方法
一种基于Hadoop的大数据挖掘云服务及应用
基于GPGPU的离散数据挖掘研究