先验算法

✍ dations ◷ 2025-07-04 07:11:01 #算法,数据挖掘

在计算机科学以及数据挖掘领域中, 先验算法(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。

相关

  • 饮食禁忌饮食禁忌是指一种单一社会群体或文化有自觉地避免食用特定动物或植物的现象。因此,饮食禁忌随空间、族群甚至时代而异,故并不存在全世界通用的饮食禁忌。多数饮食禁忌不是由文
  • 格物致知四配颜回 · 孟子 · 曾参 · 孔伋日本藤原惺窝 · 林罗山 · 室鸠巢新井白石 · 雨森芳洲朝鲜薛聪 · 权近 · 吉再 · 安珦 · 李穑李滉 · 王仁 · 李齐贤 
  • 烘烤烘焙(英语:Baking),又称焗烤、烘烤,是指面包、蛋糕、饼干、西点、派、挞、比萨饼、泡芙等烘烤类的食品制作技术,常见于西式烹饪,一般是用烤箱烤的。烘焙是制品在烤炉中经高温烘烤为
  • 伊斯特凡·沙宝沙宝·伊斯特凡(Szabó István)是匈牙利电影导演,柏林影展最佳导演和奥斯卡最佳外语片得主。沙宝·伊斯特凡的双亲是Szabó Mária与István,父亲是一位医生。
  • 沟渠沟渠是一种小型至中等的用来导水的洼地。沟渠可用于排水——从低洼地或沿公路、田野排水,或者将水从较远的地方引来灌溉作物。而壕沟是指狭长的沟渠。水沟常常能在耕地周围看
  • 赵 彪赵彪(1962年1月-),吉林白城人,汉族,中华人民共和国政治人物,长影集团有限责任公司董事长、党委书记,第十三届全国人民代表大会吉林地区代表。2018年,被选为全国人大代表。
  • 巴巴多斯总理巴巴多斯总理,是巴巴多斯的政府首脑。1966年11月30日巴巴多斯从英国独立,成为英联邦国家。1953年,自治政府成立,如同其他英国海外领土,总理当时的英文名为“Premier”。1958年,巴
  • 湖滨区湖滨区是中华人民共和国河南省三门峡市的中心和市辖区。面积164平方公里,2002年人口28万。下辖:湖滨街道、前进街道、车站街道、涧河街道、大安街道、会兴街道、崖底街道、交
  • 穆胡鲁穆胡鲁(Muhuru)是一种传闻出没于非洲肯尼亚的神秘生物,它通常被描述为一只四足巨型野兽,背上长着剑龙般的骨板,尾部则长着一个尾锤。目前已知第一例有记载的目击是传教士Cal Bomb
  • 全球保险集团全球保险集团(荷兰语:AEGON N.V.),是全球最大的保险企业之一,其总部位于荷兰海牙,成立于1983年。全球保险集团的业务集中于人寿保险和养老金,及具储蓄/投资性质的保险产品。集团也着