先验算法

✍ dations ◷ 2025-07-15 06:09:31 #算法,数据挖掘

在计算机科学以及数据挖掘领域中, 先验算法(Apriori Algorithm)是关联规则学习的经典算法之一。先验算法的设计目的是为了处理包含交易信息内容的数据库(例如,顾客购买的商品清单,或者网页常访清单。)而其他的算法则是设计用来寻找无交易信息(如Winepi算法和Minepi算法)或无时间标记(如DNA测序)的数据之间的联系规则。

在关联式规则中,一般对于给定的项目集合(例如,零售交易集合,每个集合都列出的单个商品的购买信息),算法通常尝试在项目集合中找出至少有C个相同的子集。先验算法采用自底向上的处理方法,即频繁子集每次只扩展一个对象(该步骤被称为候选集产生),并且候选集由数据进行检验。当不再产生符合条件的扩展对象时,算法终止。

先验算法采用广度优先搜索算法进行搜索并采用树结构来对候选项目集进行高效计数。它通过长度为 k 1 {\displaystyle k-1} 的候选项目集来产生长度为 k {\displaystyle k} 的候选项目集,然后从中删除包含不常见子模式的候选项。根据向下封闭性引理,该候选项目集包含所有长度为 k {\displaystyle k} 的频繁项目集。之后,就可以通过扫描交易数据库来决定候选项目集中的频繁项目集。

虽然先验算法具有显著的历史地位,但是其中的一些低效与权衡弊端也进而引致了许多其他的算法的产生。候选集产生过程生成了大量的子集(先验算法在每次对数据库进行扫描之前总是尝试加载尽可能多的候选集)。并且自底而上的子集浏览过程(本质上为宽度优先的子集格遍历)也直到遍历完所有 2 | S | 1 {\displaystyle 2^{|S|}-1} 个可能的子集之后才寻找任意最大子集S。

一个大型超级市场根据最小存货单位(SKU)来追踪每件物品的销售数据。从而也可以得知哪些物品通常被同时购买。通过采用先验算法来从这些销售数据中创建频繁购买商品组合的清单是一个效率适中的方法。假设交易数据库包含以下子集{1,2,3,4},{1,2},{2,3,4},{2,3},{1,2,4},{3,4},{2,4}。每个标号表示一种商品,如“黄油”或“面包”。先验算法首先要分别计算单个商品的购买频率。下表解释了先验算法得出的单个商品购买频率。

然后我们可以定义一个最少购买次数来定义所谓的“频繁”。在这个例子中,我们定义最少的购买次数为3。因此,所有的购买都为频繁购买。接下来,就要生成频繁购买商品的组合及购买频率。先验算法通过修改树结构中的所有可能子集来进行这一步骤。然后我们仅重新选择频繁购买的商品组合:

并且生成一个包含3件商品的频繁组合列表(通过将频繁购买商品组合与频繁购买的单件商品联系起来得出)。在上述例子中,不存在包含3件商品组合的频繁组合。最常见的3件商品组合为{1,2,4}和{2,3,4},但是他们的购买次数为2,低于我们设定的最低购买次数。

因此Apriori算法中的一些低效与权衡弊端也进而引致了许多其他的算法的产生,例如FP-growth算法。候选集产生过程生成了大量的子集(先验算法在每次对数据库进行扫描之前总是尝试加载尽可能多的候选集)。并且自底而上的子集浏览过程(本质上为宽度优先的子集格遍历)也直到遍历完所有 2 | S | 1 {\displaystyle 2^{|S|}-1} 个可能的子集之后才寻找任意最大子集S。

相关

  • 自然辩证法《自然辩证法》(德语:Dialektik der Natur)是1883年德国哲学家弗里德里希·恩格斯一部尚未完成的著作。在这部作品中,恩格斯总结了自己多年来对自然科学研究,将马克思主义观点,尤
  • 人参又称为亚洲参、红参、生晒参、山晒山参、石柱参、朝鲜参、野山参、人衔、鬼盖、土精、神草,在中国东北土名棒槌,是五加科人参属的一种,具有肉质的根,可药用,主要生长在东亚,特
  • 黑色星期二1929年华尔街股灾(英语:Wall Street Crash of 1929),又称大股灾(英语:Great Crash)及1929年华尔街股市崩盘(英语:Stock Market Crash of 1929),以牵连层面和持续时间而言,是美国历史上最
  • 李登辉访问康奈尔大学1995年李登辉总统康乃尔大学之行,于1995年6月7日至12日,在美国国会两院决议及克林顿政府的同意下,中华民国总统李登辉以私人行程名义访问美国康乃尔大学,并发表公开演说。李登辉
  • 武藤章武藤章(1892年12月15日-1948年12月23日)是昭和初期的军人、陆军中将。南京大屠杀的主要责任人之一,被远东国际军事法庭判处绞刑。1892年生于熊本县一个殷实家庭,小时候被认为是做
  • 2003年12月逝世人物列表2003年逝世人物列表:1月 - 2月 - 3月 - 4月 - 5月 - 6月 - 7月 - 8月 - 9月 - 10月 - 11月 - 12月下面是2003年12月逝世的知名人士列表:
  • 沙克蒂坎塔·达斯沙克蒂坎塔·达斯(泰米尔语:சக்திகாந்த தாஸ்,英语:Shaktikanta Das,1957年2月26日-),生于印度布巴内什瓦尔,于2018年接任第25任印度储备银行总裁。过去曾出任印度财政
  • 大汉中华国大汉中华国,是指1948年至1949年期间在河南洛阳等地,由天仙庙道(简称庙道)首领朱全福为首成立的一个秘密结社政权。1948年7月21日,洛阳庙道预谋暴动,道首王建周等联络金钟罩等会道
  • 养虎为患《养虎为患》(英语:Tiger King,港台译《虎王》),原名《养虎为患:谋杀,混乱与疯狂》(英语:)是记述动物园看护怪人乔的2020年美国真实犯罪(英语:true crime)题材系列纪录片。影片于2020年3
  • 义马果义马果()是一类已灭绝的银杏类植物,包括义马果科(Yimaiaceae)。义马果科下仅有一属,即义马果属()。发现于早侏罗世到中侏罗世的地层中。义马果具有8-9个簇生在总柄顶端的大型的胚珠