一、前言

算法领域也是测试同学在逐步介入和深入的领域，但这个领域的测试具有极为明显的特殊性——输出具有不确定性，算法设计技术思路和一般的工程类项目不同，允许有 badcase 存在，结果短期内不一定可见等。因为广告、信息流等业务跟算法结合紧密，团队内也在探索算法测试的方案，方法。本文给出了实际工程中最为常用的算法——推荐算法、最优化算法、预估算法、分类算法以及它们的应用场景，想入门算法领域的同学可以作为一个入门参考 list，有一定的算法基础的人可以略过。后续会基于调研和实际工作中遇到的场景，分享我们对启动算法测试的一些思考，欢迎大家持续关注

二、工程中常用算法和应用场景

要对算法进行测试，首先应该了解目前工程中常用的算法有哪些种类，及相应算法的应用主要应用场景有哪些。工程中的需求可能是某种算法单独完成的，也可能是几种算法合作完成，而且某种算法可能可以胜任多种不同场景。

2.1 推荐算法

核心思想是根据现有数据集合扩展出相似数据集合或者其他有关联的数据集合。在工业应用中要求可以根据用户兴趣和行为特点，向用户推荐所需的信息或商品，帮助用户在海量信息中快速发现真正所需的信息或商品，提高用户黏性，促进信息点击和商品销售。最为大家常见的就是购物网站或者新闻类网站的猜你喜欢模块，搜索广告行业的词包推荐模块等。现有推荐算法基于的维度主要有人口统计学，内容，关联规则，协同过滤，常常基于的数据包括用户，商品，内容，事件。LBS（Location Based Services）。下图是各类推荐算法的思想和实现步骤。

2.2 最优化算法

最优化算法顾名思义就是找到特定场景下的最优解，包含有约束最优化和无约束最优化算法，实际工程中一般都是有约束的最优化问题。优化算法的应用场景也很多，比如广告行业广告主如何设置预算、出价可以使得 ROI 最大，地图如何提供指定起始点的最短路径或者用时最短路径问题、图像识别领域的模式识别等。最优化算法的种类一般分为线性规划、非线性规划和现代最优化算法（如模拟退火算法、遗传算法、人工神经网络等）等。需要了解的基础算法有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等。

2.3 预估算法

核心思想是根据现有依据，预测事件在未来时间点发生的概率。应用也很广泛，比如广告行业最核心的 CTR 预估，大型网站的访问量预估，舆情预估，人口增长分析、股价走势预测等等。最常用的预估算法有 LR（Logistic Regression）模式，FM（Factotization Machines）模型，DNN（ Deep Neural Network）模型等。

2.4 分类算法

核心思想是将工程中的不同个体按照一定标准分成不同类别，这个类别可能是分类之前划分好的，也可能是通过算法学习后给出的类别。主要场景有，比如广告客户的行业划分，广告受众人群的划分，广告点击数据的反作弊，现阶段各金融平台的信用评估、图像识别、语音识别。主要的分类算法种类有决策树、人工神经网络、遗传算法、朴素贝叶斯、KNN、SVM 等算法。

2.5 其他算法

实际工程中还存在其他算法，待学习。

三、各类算法测试方法探究及现状

3.1 推荐算法测试方法

图 2 是常见推荐算法的整个模型框架，其他算法在业务应用中的框架大体类似，一般都是通过算法处理数据，为业务服务的模式。

推荐系统的主要目的是能吸引更多的用户看内容的详情页、促使单个用户浏览更多内容，所以一般在推荐系统中，主要有三种评测推荐效果的实验方法：

离线实验。往往是从日志系统中取得用户的行为数据，然后将数据集分成训练数据和测试数据，比如 80% 的训练数据和 20% 的测试数据（还可以交叉验证），然后在训练数据集上训练用户的兴趣模型，在测试集上进行测试。优点：只需要一个数据集即可，不需要实际的推荐系统（实际的也不可能直接拿来测试），离线计算，不需要人为干预，能方便快捷的测试大量不同的算法。缺点是无法获得很多实际推荐系统的指标，比如点击率，比如转化率。
用户调查。离线实验往往测的最多的就是准确率，但是准确率不等于满意度，所以在算法上线之前，需要用户调查一下，测试一下用户满意度。
AB 测试，通过一定的规则把用户随机分成几组，并对不同组的用户采用不同的推荐算法，这样的话能够比较公平的获得不同算法在实际在线时的一些性能指标。但是缺点是周期比较长，需要长期的实验才能得到可靠的结果。

如何判断一个推荐系统好不好，主要的测量指标如下：

用户满意度。这是最关键的指标。一般有两种方法，一是用户问卷调查，二是在线评测满意度，比如豆瓣的推荐物品旁边都有满意和不满意的按钮，亚马逊等购物网站可以计算推荐的物品有没有被用户购买等等，一般用点击率，用户停留时间，转化率等指标来度量。
预测准确度。如果是类似电影评分机制，一般计算均方根误差 (误差平方和取均值) 和平均绝对误差（误差绝对值和取平均）。如果是 topN 推荐的话，则主要计算召回率和准确率。准确率就是指我推荐的 n 个物品中有多少个是对的，其所占的比重。召回率则是指正确结果中有多少比率的物品出现在了推荐结果中。
覆盖率。是指推荐出来的结果能不能很好的覆盖所有的商品，是不是所有的商品都有被推荐的机会。最简单的方法就是计算所有被推荐的商品占物品总数的比重，当然这个比较粗糙，更精确一点的可以信息熵和基尼系数来度量。
多样性。推荐结果中要体现多样性，比如一个用户既喜欢看格斗类的电影，同时又喜欢爱装文艺，那么推荐结果中就应该涵盖这两个类型，而且得根据用户爱好的比例推荐，比如用户平时 80% 是看格斗类的，20% 是看文艺类的，那么推荐结果中最好也是这个比例。可以根据物品间的相似度来计算，一个推荐列表中如果所有物品间的相似度都比较高，那么往往说明都是同一类物品，缺乏多样性。
新颖性。购物网站一般都希望推荐一些用户不知道的商品或者没看过没买过的商品。方法一是取出已经看到过买过的商品，但这还不够，一般会计算推荐商品的平均流行度，因为通常越不热门的物品越会让用户觉得新颖。
惊喜度。这个和新颖度还是有区别的，比如推荐了用户之前未观看电影类型，但是用户看了之后觉得很符合自己的胃口，这就是惊喜度。注：新颖性和惊喜度暂时没有什么可以度量的标准
信任度。如果用户信任推荐系统，那么往往会增加与推荐系统的互动，从而获得更好的个性化推荐。增加信任的方法往往是提供推荐解释，即为什么推荐这个商品，做到有理有据。也可以通过类似 facebook 间的好友关系来增加信任度，一般相比于陌生人的推荐，总会选择好友给的推荐。
实时性。新闻等一些物品具有很强的实时性，一般得在具有有效性的时候进行推荐，必须考虑推荐系统处理物品冷启动的能力。
健壮性。要能防止被攻击，例如有些商家为了提高自己的排名，注册很多假的帐号，给与自己的商品高分这样类似的情况，要能防止。
商业目标。比如收入、转化率，成单率等。

3.2 最优化算法测试方法

最优化算法的校验比较困难，因为确定最优解一直是优化算法界要解决的问题。工程中一些求解结果只能说是相对最优解。
最优解算法的校验方法除了上线后的 AB 测试还未找到合适的校验方法。

3.3 预估算法测试方法

预估算法在软件工程界最典型的应用就是 CTR 预估，分为离线评测指标和在线评测指标。通用的 ctr 预估框架如图 3。离线评测指标主要从三个指标着手：AUC, LogLoss，pCTR bias。在线评估一般使用 AB Test 来验证点击率预估模型的有效性。

AUC：主要是评估序。
LogLoss：主要是评估距。
pCTR bias（mean(pctr) - CTR）：主要是弥补 LogLoss 的问题，给出另一种距的差异。

在线评估是必须的，不应该离线评估后直接全部流量使用新模型，原因是模型是在老的模型产生的数据上学习的，验证的，而直接全部新模型上线所产生的数据与之前是不同的，可能在新的数据下效果很差。当然这样解释让 AB Test 也失去了合理性，模型是应该在新的数据上学习，验证的，现在是在新老混杂的数据上学习，新老混杂的数据上验证，似乎也不合理（因为如果只用新数据训练，往往训练样本不够），认为这样是合理的是因为我们认为模型的效果好来源于它对数据的学习能力，而不在于它对特定数据的学习能力。

3.4 分类算法测试方法

分类算法的校验目标比较明确，一般是人工标注校验集合，主要从正确率、错误率、灵敏度等角度出发验证分类的效果。
正确率（accuracy）
正确率是我们最常见的评价指标， accuracy =（TP+TN）/(P+N)，即被分对的样本数除以所有的样本数，正确率越高，分类器越好；
错误率（error rate)
错误率则与正确率相反，描述被分类器错分的比例，error rate = (FP+FN)/(P+N)，对某一个实例来说，分对与分错是互斥事件，所以 accuracy =1 - error rate；
灵敏度（sensitive）
sensitive = TP/P，表示的是所有正例中被分对的比例，衡量了分类器对正例的识别能力；
特效度（specificity)
specificity = TN/N，表示的是所有负例中被分对的比例，衡量了分类器对负例的识别能力；
精度（precision）
精度是精确性的度量，表示被分为正例的示例中实际为正例的比例， precision=TP/（TP+FP）；
召回率（recall）
召回率是覆盖面的度量，度量有多个正例被分为正例， recall=TP/(TP+FN)=TP/P= sensitive，可以看到召回率与灵敏度是一样的。
上述常见的模型评价术语备注如下：
假设分类目标只有两类，计为正例（positive）和负例（negtive）。

True positives(TP): 被正确地划分为正例的个数，即实际为正例且被分类器划分为正例的实例数（样本数）；
False positives(FP): 被错误地划分为正例的个数，即实际为负例但被分类器划分为正例的实例数；
False negatives(FN):被错误地划分为负例的个数，即实际为正例但被分类器划分为负例的实例数；
True negatives(TN): 被正确地划分为负例的个数，即实际为负例且被分类器划分为负例的实例数

四、如何进行算法测试

4.1 算法测试背景及难点

开启算法测试的前提是测试人员具备一定的算法基础，对算法设计和算法在工程中的应用有一定的了解。如上篇文章提到的常用算法和其应用场景，算法设计一般来源于统计学和概率论，需要有一定的数学建模和推理基础，同时算法仿真离不开大数据处理，所以最好还要具备一定的大数据处理分析能力。
算法相关的业务和工程产出是经验丰富的算法工程师在进行大量模拟，仿真和实验和自测后得出的结果，大部分测试工程师短期内可能不能达到这一高度；而且每种算法实现思路和应用场景也不一致，不能应用统一的测试方法。实际项目中，算法和策略工程师会对上线的算法工程进行上线前自测和上线后观察，部分开发者会对测试介入有一定的排斥心理。
同时最重要的，算法测试和传统测试方法有着本质的不同，传统测试方法是设计输入数据校验输出是否和期望一致。算法测试的输入和输出都有不确定性。
所以算法测试的全面启动有一定难度。但是算法测试仍有可以切入的点。

4.2 算法测试如何切入

我认为对接业务和算法相关时，比较好的切入方式是先从算法为其他业务模块提供的数据输出入手，结合应用其数据的业务校验输出是否合理，循序渐进，逐渐深入。

即先从上图中的 1,2 模块入手，最后再深入算法处理模块。
举例说明，我们所测的业务曾经有一个场景：广告主在投放广告时，有部分广告主希望自己的预算花费较为均匀，以覆盖不同时段的用户。为了使广告主的消费在一天内分布的比较均匀，算法 server 需要根据广告主当天消费情况、预算、历史消耗分布，为广告主计算最佳的消耗速率值，并提供给引擎，引擎检索时实时根据该值确定是否展示某个物料。为了测试该场景，我们从以下几个步骤出发：

首先从算法和引擎的数据交互入手，校验算法的数据落地方式和落地频率等是否准确并生效；
其次根据算法同学提供的算法设计方案结合所测业务，设计输入数据，校验其脚本是否准确执行了其算法设计的步骤和算法流程中各步输入输出；
最后依据算法设计基础，结合所测具体业务，从算法设计维度校验算法设计是否合理，比如模型的选取是否合适，提取特征是否全面，提取的哪些特征有效，哪些无效且干扰较大，阈值的设定是否合理，这一步也是算法测试实施比较困难的一步。

忠告，哈哈，不一定用得到：因为算法设计师算法工程师大量实验和优化后的产出，他们一般都对自己的设计有比较高的自信，初期往往对算法类缺陷接纳度不高。所以开始先不要对算法开发同学设计的算法提出过多质疑，尽量从测试的业务优势上出发，先从业务角度给出建议，因为测试同学是对整个系统和流程最为了解的角色，相较算法同学有优势，然后逐渐深入。测试在同算法同学不断讨论沟通过程中，也会对算法的测试也会不断深入，学习到很多实际工程中算法工程师对算法自测时的方法和思想。

4.3 算法效果测试常用方法

因为算法的产出具有不确定性，导致算法的效果测试不能够用传统测试方法进行验证。实际工程中，对算法合理性的评判维度主要有：

失效率：比如 UV 失效率、PV 失效率；
覆盖率：UV 覆盖率、PV 覆盖率；
多样性：类目多样性、分散度、推荐结果多样分布、基尼系数；
准确率、召回率：类目准确率、类目召回率、商品准确率、商品召回率；
共现度：数据源比例、商品类型比例；
新颖性：推荐对象更新率、推荐结果更新率；
排序质量：DCG、NDCG；
时效性：用户实时行为比例；常采用 AB 路和抽样测试方法。AB 路和抽样测试的思路在此不再赘述。

4.4 算法测试框架

综上，算法测试可以遵从以下框架进行，见下图：

首先，在准备阶段，清晰算法所在业务模块整体业务流程，明确算法的目的，算法数据输入和输出；
其次，在离线测试阶段，校验算法的准确性和合理性。对算法脚本或代码白盒测试，结合业务校验算法设计是否合理，比如提取的特征，选用的模型，数据实时性等，同时离线执行算法，校验算法结果，在这个过程中要注意算法处理的性能，因为现在业务大多涉及大数据，能否准确及时提供服务也是算法 server 的指标之一；
最后，上线观测算法效果和服务稳定性。通过线上运行结果做 AB 路对比，抽样数据校验等方法校验算法效果，同时观察线上数据的稳定性；
依据算法线上表现修正算法表现不足的方面，并在线下实验，依此反复，直至算法效果在线上表现符合预期；

算法测试现在也在追求平台化，流程化，并能够对外提供服务。在这条道路上我们还有很长路要走。

↙↙↙阅读原文可查看相关链接，并与作者交流

一、 前言

二、 工程中常用算法和应用场景