手推Apriori算法------挖掘频繁项集
版权声明:本文为博主原创文章,未经博主允许不得转载。
Apriori算法:
使用一种称为逐层搜索的迭代方法,其中K项集用于搜索(K+1)项集。
首先,通过扫描数据库,统计每个项的计数,并收集满足最小支持度的项,找出频繁1项集的集合。该集合记为L1。然后,使用L1找出频繁2项集的集合L2,使用L2找出L3,如此下去,直到不能再找到频繁K项集。找出每个Lk需要一次数据库的完整扫描。
为了提高频繁项集逐层产生的效率,一种称为先验性质的重要性质用于压缩搜索空间。
先验性质:频繁项集的所有非空子集也一定是频繁的。
频繁1项集的集合------> L1:统计各个项的出现次数,将满足最小支持度(会给出)的项留下。
频繁2项集的集合------> L2:连接L1中各个项:例如:L1: 1,2,3,4 ------>L2:(1,2),(1,3),(1,4),(2,3),(2,4),(3,4) 。连接完成之后,需要剪枝(根据先验性质),由于L2中的每个项的子集都是频繁的,所以剪枝这步不需要删除L2中不满足的项。最后,扫描数据库(就是给出的数据),统计L2中所有项的支持计数(就是累加每个项在给出数据中出现的次数),挑出满足最小支持度的项构成L2。(一般这里会删除一些项,假设删除了(2,4)项)。 最终 L2:(1,2),(1,3),(1,4),(2,3),(3,4)
频繁3项集的集合------> L3:连接L2中的各个项: 例如:L2: (1,2),(1,3),(1,4),(2,3),(2,4),(3,4) ------->L3:(1,2,3),(1,2,4),(1,3,4),(2,3,4)。连接完成之后,需要剪枝,根据先验性质,频繁项集的所有子集必须是频繁的。所以删除(1,2,4)和(2,3,4)因为它们的子集(2,4)不在L2中所以不是频繁项集。最后,扫描数据库(就是给出的数据),统计L3中所有项的支持计数(就是累加每个项在给出数据中出现的次数),挑出满足最小支持度的项构成L3。最终L3:(1,2,3),(1,3,4)
频繁4项集的集合------> L4:正常迭代进行。
但就上面举的例子:因为连接L3中各项:L3:(1,2,3),(1,3,4)-------------->L4:(1,2,3,4) 。L4的子集(2,3,4)不是频繁项集,这样L4会为空集,所以算法迭代结束。找出的频繁项集为:(1,2,3),(1,3,4)
核心流程:集合连接-------->剪枝--------->挑选满足最小支持度的项---------->构成频繁项集
最新文章
- C#--几个数据流Stream;StreamReader;StreamWriter;MemoryStream;BufferStream;
- SDK开发断点失效
- maven + selenium + jenkins 教程收集
- MyEclipse修改
- 记载abp中Dbcontext的疑问
- Python网络编程——获取远程设备的IP地址
- uoj#179 线性规划
- 结对作业1--基于GUI的四则运算
- jQuery-01:on live bind delegate
- zabbix批量添加被监控windows客户端
- python 操作 MD5
- 深度学习 ——style reconstruction
- 注册表键值明明存在OpenSubKey始终返回null,解决方案
- 百度地图bd map使用方法
- HHH
- ubuntu16.04, git 的配置
- Linux 系统安装[Ubuntu]
- 通过java解析域名获得IP地址
- 20155217 2016-2017-2《Java程序设计》课程总结
- 创建Java不可变型的枚举类型Gender