先验算法

✍ dations ◷ 2025-04-26 22:05:29 #算法,数据挖掘

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

相关

  • 产金菌门产金菌门(Chrysiogenetes)是一支独特的细菌,目前只发现了一个种,即砷酸产金菌(Chrysiogenes arsenatis)。它具有独特的生活方式和生化过程。它经营化能无机自养,利用对绝大多数生物
  • 量子引力量子引力,是对引力场进行量子化描述的理论,属于万有理论之一。研究方向主要尝试结合广义相对论与量子力学,是当前物理学尚未解决的问题。当前主流尝试理论有:超弦理论、循环量子
  • 密度制约在种群生态学中,密度制约是描述种群密度对种群增长的影响的一种假说。一般认为密度制约效应主要发生在物种的种子和幼苗阶段。
  • 法国行政区划中,直属“第一级地方行政单位”大区(法语:région)的“第二级地方行政单位”,法语为“département”,汉语将其翻译为“省”,这类行政单位英语将其与“county”或“shi
  • 纽约书评(2011)《纽约书评》(The New York Review of Books,缩写为NYRB)是一本在美国纽约市发行的半月刊(确切地说是每年二十期,学期段每月两期,寒暑假每月一期,显然是为了配合高校师生的生
  • 辐射能辐射能是指电磁辐射所具有的能量。它的大小可以通过计算辐射通量关于时间的积分得到。和所有形式的能量一样,辐射能的SI制单位是焦耳。这个术语常被用于描述电磁辐射被发射到
  • 地缚灵幽灵,在中国一般称为鬼,在日本则称幽霊(幽灵),在韩国亦称유령 (幽靈)。在英语语境中,幽灵一词多以“ghost”来称呼,也译为鬼魂;但也有对应日语中的幽霊(假名:ゆうれい)而命名Yūrei的称
  • 凝固汽油弹凝固汽油弹(英语:napalm),亦称烧夷弹,是几种武器用途的可燃液体之总称,大多以胶状汽油为主成分。“napalm”指的是凝固汽油弹中用来与汽油混合以产生胶质燃剂的黏稠剂成分。此词是
  • 列·毕顿列·毕顿(英语:Red Buttons,1919年2月5日-2006年7月13日)是一名美国电影演员及喜剧演员。曾凭《樱花恋》()中的演出赢得第30届奥斯卡金像奖最佳男配角奖。原名Aaron Chwatt,在纽约市
  • 黄琏 (成化丙戌进士)黄琏(1437年-1502年),字汝器,福建兴化府莆田县人,明朝政治人物。福建乡试第五十名。成化二年(1466年)丙戌科进士,授南戸科给事中。升浙江叅议。改云南,转贵州参政。累官贵州左布政使。