您好, 访客   登录/注册

Apriori算法的改进及实例

来源:用户上传      作者:

  摘要:本文对Aprior算法简介进行阐述,对这种算法进行改进,并以案例验证改进的合理性。
  [关键词]Aprior 算法 改进实例
  1Apriori算法概况
  1.1Apriori算法简介
  Apriori算法是一种数据挖据的经典算法,此算法具有关联规则模型。在1994年,由R.Agrawal等人通过研究AIS算法,在这种算法的基础上提出的一种改进算法,这种算法是以一种挖掘数据问题为主要内容。在关联规则问题上,这种算法的影响力非常大。
  Apriori算法隶属于宽度优先算法,即在关联规则中应用宽度优先。其核心就是对数据库进行扫描,由此产生出候选集,每一次扫描的时间只需要考虑同一个长度的候选集。同时还要逐级监测这个过程的频繁项集。在多次扫描结束后,会生成比较多频繁项目集。
  1.2Apriori算法概念
  对某个事件A与B:
  (1)支持度:几个事件关联出现的概率。P(A∩B),在同一时间发生A事件与B事件的概率。
  (2)置信度:事件的条件概率。
  P(B|A),如果事件A已经发生了,同时发生B的概率,可以为P(AB)P(A)。
  比如:对购物车的分析:其中有货物为泳镜和泳衣。
  [假如支持度为1%;而置信度为60%支持度1%:表示同时购买泳镜与泳衣只有2%。
  置信度60%:表示客户购买泳衣的,能够购买泳镜占据60%。
  Apriori算法构思和操作都相对比较简单,易于实现。这种算法采用了逐层搜索迭代法。算法目的是找到最大的频繁项集,使用“K-1项集”来搜集“K项集”。
  首先,从中寻找出数据库频繁的集合,此处为“1项集",采用L作为集合标志位。通过L1,就能够从中搜寻出频繁项,即为“2项集"的L2,通过相同的方法得出L3,直到无法寻找出“K项集"。在整个实施运行过程中,每次迭代找出一个Lr,都需要重新扫描一次数据库。
  在Apriori算法中,最重要的是连接与剪枝;连接步即为自动连接(将LK与LK连接起来),连接规则就能够确保每个项前K-2为相同项。按照这个步骤顺向连接,其中剪枝就是从频繁项集中产生所有的非空子集,不让这些子集参与其中。如果非空子集成为非频繁项,一定会让候选集成为非频繁,这样就可以把它从Cr中删除掉,产生出Lk。简而言之,对频繁项集计算过程进行归纳,其步骤为:扫描,计数,比较,出现频繁项集,连接与剪枝,然后生成为候选项集。
  虽然Apriori算法极大提高了计算优势,但是从计算过程方面来看,也显示出一些缺点,每次寻找出一个频繁项集,必然需要对整个原始数据库进行一次完整扫描;如果数据库中的数据量非常巨大,那么在运行过程中必定会产生出非常庞大的候选项集。当数据结构比较简单时,可通过Apriori算法对运算进行执行,但是对于数据比较大的时候,Apriori算法就比较复杂,而且运行次数会很多。例如频繁集{X1,X2,X3,....X500}的长度为500,必然会产生出10000个候选项集。因此,要想真正显示出Apriori算法的优势,就要先对Apriori算法进行改进。
  2Apriori算法的改进
  随着大数据不断深入发展,Apriori算法暴露的缺陷非常明显。在大数据时代,所有的数据几乎都成为海量,都以PB为基准,自然数据信息比较庞大,如果还是采用Apriori算法,复杂性可想而知。因此按照Apriori算法具有的基本特征,就应该对其算法进行改进。总体而言,其改进主要从两个方面进行:
  (1)对自连接与剪枝步骤上,应该采用更为优越的策略。
  (2)对数据库自身进行简化,目的是降低Apriori算法复杂度。
  本文对Apriori算法改进主要从数据库中着手,Apriori算法每执行一遍就要扫描一次数据库,事实上可以对这个过程进行优化,在计算CK支持度过程中,应该将CK中所包含各种事物均标记出来,扫描时不用再考虑标记事物,这样优化后,会产生实际候选集的支持度中各种数据库必须要比真实数据库小,随K值增大,差值自然随着增大,可有效降低扫描的时间,降低计算速度,提高效率。对Apriori算法进行改进后,步骤如下:
  (1)从其中选择最小的支持度,扫描原始数据库,由此计算得出各个1项集度,从而得出1-项集L1。
  (2)连接剪枝(此项步骤不变)
  (3)对Ck中未标记元素进行标记,将已经标志的元素删除掉,由此可获取出新数据库DK,然后对DK进行重新扫描,计算出CK-1中各元素支持度。
  (4)将CK进行搜索,要删除掉其中无法满足的最小项集,从而形成一个新项集LK;
  采用②-④,一直到无法产生出新的频繁项集时,就终止此项操作。采用实例数据进行对比。
  当上面流程来看,筛选C3时,数据库经过简化后就变成D1,而商品从10项减为9项,接下来经过执行后,数据库D2减少成7项,在这个过程中能够有效减少扫描所需时间。采用这种方法,对于数据量较大时非常节约时间,由此可见这种改进,其操作性比较强,但是虽然算法改进了,又会产生出一些新数据库,新产生的数据库需要占用时间和资源,因此改进算法仍需要不断提高。
  3Apriori算法改进后案例分析
  随着计算机网络快速发展,电子商务的地位越来越重要,对于各种繁杂的商品,在实际应用中电商平台要如何给客户推荐,如何满足客户所需,如何吸引更多的客户,这些都是投资者、经营者需要考虑的内容。
  在电商平台应用Apriori改进算法;平台必须要依据用户的消费习惯,将相关商品设置成关联度,才能为用户进行推荐,才能帮助客户在整个购物过程中减少对购买物品的搜索时间,使购物变得高效来吸引客户。
  本文通俗易懂的介绍了Apriori算法,之后对经典Apriori算法进行了改进,而且运用改进算法对电商平台进行运用,有效降低了客戶选择所需商品花费的时间,达到增加经济效益的目的。
  参考文献
  [1]刘尚辉,王露.Apriori关联规则在甲状腺结节病案分析中的应用[J].中国卫生统计,2018(02).
  [2]范明等译.Pang-NingTan,MichealeSteinbach,VipinKumar.数据挖掘导论[M].人民邮电出版社,2011.
  [3]屈展,陈雷。一种改进的Apriori算法在电子商务中的应用[J].西安石油大学学报:自然科学版,2012(01).
转载注明来源:https://www.xzbu.com/1/view-14929192.htm