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
