解决方案:关联规则之Aprioi算法

　　解决方案:关联规则之Aprioi算法

　　国际权威学术会议IEEE数据挖掘国际会议（ICDM）评选出数据挖掘领域十大经典算法，它们是：C4.5、kMeans、SVM、Apriori、EM、PageRank、AdaBoost、KNN、Naive Bayes和购物车。今天就让我们来探讨一下十大算法之一的Apriori的具体应用。

　　#Apriori 算法简介

　　在算法学习的过程中，有一个经典的例子。当美国超市把尿布和啤酒放在一起时，两种产品的销量都增加了。表面上看，两者并无直接关系，却暗藏着鲜为人知的逻辑。购买纸尿裤的美国消费者多为男性消费者，其中以啤酒爱好者居多。当然，这是教科书式的故事，但是在如何提高销量这个问题上，将两种或两种以上的产品组合起来进行销售，提高一种或多种产品的销量成为了研究热点，而其他的核心问题就是找出两个项目之间的关联规则，这也是我们的主角Apriori模型[1]。

　　一、Apriori概述

　　Apriori 在拉丁语中的意思是“从前”。在定义问题时，通常会用到先验知识或假设，称为“先验”。Apriori算法的名称是基于这样一个事实，即选择项目之间的关联规则是为了寻找项目之间的潜在关系。

　　例子：

　　1. 找到频繁一起出现的项集的集合，我们称之为频繁项集。例如，超市的频繁物品集可能有（啤酒+尿布、纸巾+湿巾、苹果+西瓜）

　　2、在频繁项集的基础上，利用Apriori关联规则算法找出其中项的关联结果。

　　>综上所述，需要先找到频繁项集，然后根据关联规则找到相关项。筛选频繁项集的原因有两个：

　　1.如果商品不是高购买频率的商品，统计上无法验证其购买频率与其他项目的关系。

　　2、考虑到如果有10000个产品，如果购买频率不高，加入到模型中，会极大地影响模型的效率。所以从两个方面来说，先找到频繁项集，再根据关联规则找到相关项，将极大地帮助我们提高工作效率。

　　2. Apriori 算法基础

　　在介绍Apriori算法之前，我们首先要了解支持度、置信度和提升的基本概念。

　　以20条商品购买记录数据为例：

　　01 支持（支持）

　　

" />

　　支持度可以理解为一个项目当前的受欢迎程度。

　　◎支持度=收录

A项的记录数/记录总数

　　苹果支持：16/19

　　02 信心

　　信心意味着如果你购买了 A 项，你就更有可能购买 B 项。

　　◎置信度(A->B)=收录

A项和B项的记录数/收录

A项的记录数

　　信心（苹果→玉米）：支持（苹果→玉米）/支持（苹果）= 9/10

　　03 电梯（电梯）

　　Lift 是指当售出另一件商品时，一件商品的销售率增加了多少。

　　◎提升度（A->B）=置信度（A​​->B）/（支持度A）

　　Apple->Corn 推广为：

　　支撑（玉米）：玉米支撑=16/19

　　信心（苹果→玉米）：支持（苹果→玉米）/支持（苹果）= 9/10

　　Lift（苹果→玉米）：置信度（苹果→玉米）/支撑度（玉米）=（9/10）/（16/19）

　　其中，支持度会帮助我们确定频繁项集，而置信度和提升会在下一篇寻找项的关联规则时基于频繁项集使用。

　　3. Apriori算法特点

　　Apriori算法首先根据项与项之间的支持度找到项中的频繁项集。从上面我们知道，支持度越高，该项目越受欢迎。这种支持由我们主观决定。我们需要将这个参数传入模型，然后Apriori会返回那些支持度不低于预设支持度阈值的频繁项集。

　　

" />

　　然后按照之前给出的计算规则计算置信度，对规则apple⟹corn计算support(corn)和confidence(apple⟹corn)。置信度越高，苹果⟹玉米之间关联的可能性就越大。提升度是衡量苹果⟹玉米关系强弱的标准。简单来说，confidence是判断两者之间是否存在关系，lift是衡量关系的强弱。但是，如果用一个引擎来搜索所有的组合，一旦数据量很大，产生的计算量是无法估计的，所以Apriori给出了一个解决方案：如果一个项目集是频繁的，那么它的所有子集也是频繁的频繁; 另一种解释是：如果一个项集是不频繁的，那么它的所有子集也都是不频繁的，这个推论会大大减少我们的计算时间。有了这些基础，下面进入实战环节。

　　efficient_apriori包中的先验算法使用如下代码：

　　随机导入

　　将 numpy 导入为 np

　　将熊猫导入为 pd

　　从 efficient_apriori 导入 apriori 作为 eapriori

　　导入警告

　　ls=['南北杏', '梨', '橙柑', '桃', '玉米', '苹果', '草莓', '蓝莓', '西瓜', '香蕉'] #构造一个产品清单

　　警告。过滤警告（'忽略'）

　　lx=[]#构造一个商品列表中的排列组合，提取其中20个作为我们的购买数据

　　对于范围内的我（0,5）：

　　对于范围内的 x（2，len（ls））：

　　lx.append(random.sample(ls,x))

　　lc=random.sample(lx,20)

　　itemsets, rules = eapriori(lc, min_support=0.25, min_confidence=1) #设置最小支持度为0.25，最小置信度为1

　　result = pd.DataFrame(columns=('premise', 'consequence', 'total_support')) #建表供后续使用

　　rules_r = 过滤器（lambda 规则：len（rule.lhs）

　　解决方案:达观数据如何使用点击模型提高推荐、搜索、广告等大数据系统的算法精度的？

　　在搜索、推荐和广告引擎中，系统会通过复杂的算法生成最终的结果列表。当用户看到这个结果列表时，他们可能并不总是对排序感到满意。例如，有时他们觉得排序有问题，或者发现一些不符合自己喜好的物品。如果从算法层面去调，总会有一种按住葫芦拿起瓢的感觉。在优化一些坏情况的同时，会带来新的坏情况。在这种情况下，往往需要将模型点击到“近线端”进行修正。通过用户的点击反馈，可以从算法的另一个层面对结果进行调优：提取符合用户偏好但不符合用户偏好的item被放置在后面到前面，或降低不符合用户意图的项目的权重和分数。在引擎架构研发的实践中，大观数据大量使用了点击模型。通过与用户的隐式交互，大大提升了算法效果，积累了丰富的实践经验（姜永清，大观数据联合创始人）。

　　单击模型概述

　　随着大数据技术的发展，互联网上的数据呈现爆发式增长。通过采集

海量用户行为数据，尤其是点击数据，可以更好地预测用户行为，挖掘用户需求。机器学习领域的训练数据不再只是通过费时费力的人工标注获得，更多的是基于点击反馈采集样本，既降低了数据获取成本，又保证了最新的时效性。

　　点击模型通过获取用户的历史点击来对用户行为进行建模。模拟用户的点击偏好后，可以最大程度优化系统效果。用户的点击行为具有一定的规律性。遵循这些规则，我们可以基于以下假设构建用户的点击模型：

　　·用户的浏览总是按照一定的顺序查看，第一眼容易看到的结果会得到更多的关注；

　　·用户可以点击查看初步满足需求的标题、图片、摘要等结果；

　　·如果某个结果item完全满足用户的需求，那么再看其他item的可能性就会比较低；

　　·点击的结果越多，越有可能是好结果；

　　·最后一次点击的结果往往是最好的结果，其次是第一次点击的结果；

　　还有很多。

　　点击模型的挑战和困难

　　利用点击行为的假设，很容易构建一个初步的点击模型。但在实际应用中，一个好的模型需要面对和解决很多挑战和困难，包括：

　　第一个大问题是位置偏差。由于用户点击容易受到位置偏差的影响，因此排名靠前的结果更有可能被用户点击。在实际应用中，一般会对click bias进行一些惩罚。例如，排名靠前的结果被用户跳过。它会比后面跳过的结果更能减少权重；如果用户执行翻页操作，则上一页的结果将递减。

　　第二大问题是冷启动问题。即新商品和新广告的点击预测问题。一种常用的方法是通过已有的点击反馈数据进行挖掘和学习规则，从而预测用户可能对新物品的点击行为。

　　第三个大问题是感知相关性。用户对结果的点击反馈很大程度上基于标题、图片、摘要等感官获取，具有很强的第一主观意识。在很多情况下，它不能正确反映结果的有效性，而点击日志数据往往不能获得用户对结果的理解。展示商品“真实”满意的相关数据，所以在已有“感性”数据的基础上，需要从其他方面进行补充，比如用户点击结果后的后续操作（点击商品加入购物车） ，点击在书籍后添加书架等），或者引入点击率以外的满意率等参数来构建点击模型。

　　第四个最大的问题是稀疏性。在搜索排序中，点击数据一般只覆盖排序结果的前几页，容易出现长尾覆盖不足的问题。推荐和广告引擎经常有不会被点击的冷门项目。另外，点击次数太少容易导致点击数据不可靠。因此，除了用一些均值或预测值补充数据外，通常还会对稀疏数据进行平滑处理。

　　第五大问题是点击作弊。由于点击行为很容易产生，所以作弊者通常会使用模仿用户点击的行为来攻击系统，例如使用机器人重复点击某个位置。在这种情况下，需要识别作弊数据，以免人为干扰系统结果。

　　第六个最大的问题是Session采集

。用户的会话信息非常关键。它记录了用户在进入页面、查看结果、点击结果以及后续操作（如翻页、添加购物车等）时的操作。只有通过session信息才能将用户的行为联系起来，建立一个完整的模型，所以从海量数据中充分挖掘出每个用户的所有session操作就显得非常重要（姜永清，大观数据联合创始人）。

　　点击模型类型

　　关于点击模型的研究很多，也有很多类型的模型被提出并在实践中得到应用。以下是一些常见的点击模型类型：

　　1）位置模型（position model）

　　location模型考虑到每个用户都会有一定的概率查看每个item的位置（Examination），只有查看了item后用户才会有一定的点击概率。因此，用户点击某个位置的概率计算如下：

　　其中，βp表示在位置p被查看的概率（与用户无关），αu表示用户u查看某项后点击它的概率（与位置无关）。αu和βp的值可以根据用户的历史点击记录，通过平均法、极大似然法等方法计算得到。

　　2）瀑布模型（cascademodel）

　　瀑布模型考虑了相同排序列表中项目的位置依赖性。它假定用户从上到下查看页面上的项目。如果结果令人满意，他们将单击，然后会话结束；否则，跳过该项目并继续。向后看。第i个位置的item点击概率计算如下：

　　其中 ri 表示第 i 个文档被点击的概率。

　　3）CCM模型

　　位置模型和瀑布模型都没有考虑同一session中不同排序结果之间的交互。考虑以下情况：如果第一项和第二项非常符合用户喜好，那么后续项的观看概率和点击概率就会降低；相反，如果前几项很差，后面的几项被浏览和点击的机会就会更高。CCM模型假设用户对一个item满意后可以继续查看后续结果；而第j次排序结果的查看（Examination）和点击（Click）会影响第j+1次排序结果的行为：

　　

" />

　　4）贝叶斯模型（DBN）

　　贝叶斯模型引入了满意度（satisfied rate）的概念，它考虑到用户在点击某个项目时可能对它不满意。点击代表“感知的相关性”，满意代表“真正的相关性”。Yeesian 模型很好地分离了这两种相关性。根据DBN理论，具体模型图及原理如下：

　　Fig.1 贝叶斯模型Fig.1 Bayesian modelFig.1 Bayesian model

　　图 1 贝叶斯模型

　　Ei表示用户是否浏览过第i项；Ai表示用户是否被第i个item吸引；Si表示用户点击第i项后对结果是否满意；Ci 表示用户是否点击了第 i 个项目。所以每个操作的关系传递如下：

　　此外还有几个重要的参数：au表示用户对结果的感知相关性，吸引用户点击；su表示用户点击该item之后，其相关性令人满意。au 和 su 都有 Beta 先验概率。指定γ后，au和su的值可以通过EM算法计算出来。特别地，如果 γ 指定为 1，则意味着用户将一直回头看该项目，直到找到满意的结果。这时候可以通过页面最后点击的位置来判断勾选的item（上次点击位置的上方）和看不见的item。浏览过的items（上次点击位置下方），此时，

　　点击模型的相关性得分可以简单计算为：ru = au * su，表示用户被结果吸引，点击查看并满意的概率。

　　5) UBN模型

　　与CCM和DBN模型不同，UBN模型没有采用瀑布模型的假设，而是假设用户在某个位置i查看结果的概率不仅受该位置的影响，还受某个先前的影响在同一个会话中的位置。单击项目的影响。γrd 的引入表示用户点击位置 rd 后将查看位置 r 的项目的概率：

　　其中 Ci:j = 0 表示 Ci = Ci+1 = · · · = Cj = 0。

　　如何利用点击模型提升算法效果

　　点击模型常被应用到各种系统中，以提高算法的效果。现在，我们将介绍搜索、推荐、广告和数据挖掘中的各种使用场景：

　　1）搜索系统

　　在搜索系统中，点击模型可以通过以下方式进行整合： 可以直接用于排名，比如简单的对点击模型在“近线端”的相关性得分进行加权，将点击模型的排名位置结果可以直接调整；也可以通过排序来学习，样本获取就是以排序页面被点击的item为正样本，显示的未被点击的item为负样本，每天积累足够的训练样本。通过选择丰富的特征，可以使用分类器来学习合适的排序模型。这些丰富的特征包括文档中查询词的词频信息、查询词的IDF信息、文档长度、网页的传入链接数、网页的pageRank值、查询词的邻近值等，从而可以充分反映query查询与document之间的关系。当用户下次查询时，分类器可以用来预测新的排序结果。

　　2）推荐系统

　　推荐系统在计算推荐结果时也大量使用了点击模型。例如在协同过滤算法中，如果没有明确的评分机制，就需要采集

点击行为作为正分。不同类型的点击（如查看、添加购物车、添加关注等）可以生成不同维度的二维相似度矩阵，最终的推荐结果由这些矩阵计算生成的中间结果进行加权。推荐系统也可以调整“近线端”的权重。例如，如果用户“不喜欢”某个商品，则不会推荐下次展示；算法引擎，实现效果效益最大化。

　　3) 广告引擎

　　CTR预估在广告引擎中使用最多。LR模型用于CTR预估，由于其算法简单，计算速度快，输出概率值为0~1，刚好满足广告引擎的需要。广告选择的特点也很丰富。在用户层面，包括用户的性别、年龄、地域等；在广告层面，包括广告尺寸、广告类别、广告文字、广告所属行业等。广告属于。广告引擎使用的样本也是根据点击反馈采集

的。用户点击过的广告作为正样本，用户看过但没有点击的广告作为负样本。在采集

到足够的样本后，使用 LR 训练最优模型。当用户查询广告时，LR模型根据用户和候选广告的特征，预测每个候选广告被用户点击的概率。计算出的预估概率是广告引擎中非常重要的评分结果，对广告排名的展示有着重要的作用。决定性的作用。

　　图 2 LogisticRegression 模型

　　单击模型系统架构

　　一般来说，点击模型需要采集

大量的用户点击位置、页面浏览时间、页面关闭、点击次数等交互信息。只有对采集到的大量数据进行数据清洗和反作弊处理后，才能得到有效的点击数据，为后续的数据分析和挖掘提供支持（姜永清，大观数据联合创始人）。

　　1）数据采集模块

　　点击模型数据获取是一个非常重要的模块，因为所有的原创

数据都是从这里导入的。移动端和PC端的采集还是略有不同。目前移动端主要采用SDK采集，将SDK嵌入APP，业务端调用接口上报采集数据；而PC端一般都是在页面中植入js。在 中，用户的每一个重要行为都会触发数据上报。只有将移动端的数据采集与PC端连接起来，才能发挥数据的最大价值。上报数据通过数据采集模块进入系统后，由于存在大量非法格式数据和损坏数据，需要经过繁琐的数据清洗阶段。

　　2）数据挖掘模块

　　在数据仓库中进行数据反作弊和数据挖掘处理时，由于数据量巨大，通常采用集群计算。通过反作弊算法剔除虚假数据后，利用数据挖掘模块对点击展示数据进行处理，最终生成各种具有巨大潜在价值的数据结果。这些结果不仅包括点击模型，还有其他丰富的数据产品，包括数据关联信息、数据预测、数据报告等。

　　

" />

　　3）系统集成

　　点击数据挖掘的结果将反馈给引擎架构，优化系统的算法，提升整体效果。用户在新的点击模型作用下的点击结果会在接下来的数据采集中采集

，形成一个闭环。整个闭环图如下：

　　图3 点击模型系统架构

　　点击模型，防止作弊

　　点击模型在排序结果中起着至关重要的作用，因此是一个易受攻击的部分。攻击的目的无非有两个，一是提升目标物品的排名（推荐攻击），二是降低目标物品的排名（压制攻击）。用户对系统的攻击一般都是通过点击插入伪造的数据产生的，所以基本的对策也是识别用户的恶意点击结果和反作弊。

　　1) 基于规则的识别

　　传统的反作弊是基于规则的识别，比如cookie去重，IP反作弊：通过记录和监控cookies和ip的重复行为，防止同一用户/设备在一个时间内多次点击同一个位置一定时期；有效期设置：限制显示/点击的有效期。有效期内转换为合理收益，超过有效期的操作将被丢弃；黑名单处理：一些周期性的作弊行为在超过一定范围后可以被标记为黑名单。用于长期过滤，防止其持续攻击系统。基于规则的反作弊有很多方法，因业务而异，

　　2）分类方法

　　然而，今天的攻击方法非常多样化。简单的基于规则的反作弊不足以有效识别攻击者。因此，需要更复杂的基于机器学习的方法来区分真实点击和虚假点击。例如，使用监督学习方法，通过手动标记点击，或人为伪造记录来训练分类器。由于点击数据样本种类多、数量大、维度高，所使用的记录特征均采用聚合方式生成。这些特征不是普通的记录属性，而是收录

各种统计信息的信息特征。通过监督学习的方法，可以识别出大量无法被规则区分的攻击行为。

　　3）聚类方法

　　聚类方法主要用于识别系统中多个用户联合攻击的场景。这些攻击的用户群体普遍具有非常相似和异常的攻击行为，往往攻击的物品很多。在反作弊模块中，通过聚类来区分正常行为和异常行为簇，然后将异常行为的点击、评分等操作从计算点击模型的数据集中剔除。聚类方法在防止“群钓”等攻击行为方面尤为有效。

　　4）信息论方法

　　通过样本的信息变化来检测作弊者也是一种有效的方法。可以通过检测一段时间内某些物品的一些评分值来检测异常，比如描述物品随时间变化的样本均值，物品评分值分布变化的样本熵等。通过观察有限时间窗口内各种信息值的变化，相对容易检测到攻击者的行为。

　　使用机器方法可以有效识别大部分无法根据规则解决的问题，使攻击者更难作弊。然而，点击反作弊是一个与恶意攻击者斗智斗勇的过程。简单的一两种方法并不能彻底解决作弊问题。对于问题，往往将多种方法组合在一起。例如，基于规则的方法首先排除大多数简单的攻击，然后结合多种机器学习方法来识别更复杂的作弊记录。由于攻击者的攻击手段不断升级，正所谓“道高一尺，魔高一尺”，反作弊必须不断改进策略，才能有效阻止作弊者。

　　点击模型效果评估

　　评价搜索、推荐、广告效果的指标有很多，包括点击位置计算的MRR和MAP分数，点击结果计算的准确率、召回率、长尾覆盖率等。在搜索引擎、广告引擎和推荐引擎的研发过程中，大观数据一直在进行充分、细致的数据评估，确保每一次算法升级的效果。以 MRR 和 MAP 分数的评估为例。这两个分数的计算方法一直是信息检索领域评价算法好坏的重要指标：

　　1）MAP（平均精度）

　　MAP 为每个查询的相关排名结果分配一个评分数字，然后对这些数字进行平均。比如q1对应的d排名分别是1、2、5、7（假设q1有4个相关d），那么q1的ap（平均精度）的计算就是（1/1+2/2+3 /5+ 4/7)/4 = ap1，相关d在q2排序结果中的排名为2,3,6（假设q2有5个相关d），那么q2的ap为（1/2+ 2/3+3/6+0+0)/5 = ap2，那么这个排序算法的MAP就是(ap1+ap2)/2；

　　在大观搜索引擎中，原系统与点击模型的MAP评分对比如下：

　　图4 使用点击模型的地图得分对比

　　2）MRR（平均倒数排名）

　　MRR的评估假设是基于唯一相关的结果。比如q1最相关的排在第3位，q2最相关的排在第4位，那么MRR=(1/3+1/4)/2。

　　在大观搜索引擎中，原系统与点击模型的MRR得分对比如下：

　　图5 使用点击模型后mrr得分对比

　　从效果图可以看出，使用点击模型后，系统的性能有了近30%的大幅提升。此外，使用NDCG、F值、长尾覆盖率等评价方法，可以看出点击模型的应用会给系统带来一定的效果和收益。在搜索引擎、智能推荐、广告系统中，使用点击模型后，系统的效果会得到很好的提升。

　　结语

　　在大数据公司中，点击模型是用于搜索、推荐和广告系统的强大工具。对于优化算法模型，实现“千人千面”的个性化效果至关重要。点击模型是数据挖掘领域的一个研究热点问题。随着大数据的发展，各种新技术和解决方案应运而生。大观数据在大数据领域拥有丰富的行业经验，可以通过点击模型等先进技术帮助合作企业充分发挥大数据的潜力。