欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！

估算送达时间

1. 问题陈述

构建一个模型来估算在给定订单详情、市场条件和交通状况下的总送达时间。

为了简化，我们不考虑在此练习中对订单进行分批处理（在餐馆将多个订单合并处理）。

在构建估算总送达时间的模型时，“市场条件”指的是可能影响送餐过程的各种外部因素。一些市场条件的例子包括：

星期几：送达时间可能在工作日和周末之间有所不同。

一天中的时间：送达时间可能会受到高峰用餐时间（例如午餐或晚餐时间）或非高峰时间的影响。

天气状况：不利的天气如雨、雪或极端高温可能会延缓送达时间。

特殊事件：如体育比赛、音乐会或节日等当地事件可能会导致交通拥堵和送达时间延长。

假期：由于订单量增加和交通模式变化，假期期间的送达时间可能会更长。

促销和折扣：特殊促销或折扣期间，订单量增加可能会影响送达时间。

送达时间计算

$$\text{DeliveryTime}=\text{PickupTime}+\text{PointtoPointTime}+\text{DropoffTime}$$

2. 指标设计和要求

指标

离线指标: 使用均方根误差（RMSE）
$$\text{RMSE}=\sqrt{\frac{\sum _{k=1}^n(\text{predict}-y{)}^2}{n}}$$
其中，

• $n$ 是样本总数，
• $\text{predict}$ 是估算的等待时间，
• $y$ 是实际等待时间。

在线指标: 使用 A/B 测试并监控 RMSE、客户参与度、客户留存率等。

RMSE 是回归问题中常用的指标，包括估算送达时间。RMSE 衡量预测值与实际值之间误差的平均大小。通过取 MSE 的平方根，RMSE 将误差转换回目标变量的原始单位。这意味着 RMSE 与送达时间（分钟）具有相同的单位，更易于解释。例如，2.9 分钟的 RMSE 直接告诉我们，预测值平均偏差约为 2.9 分钟。

A/B 测试：将用户分为两组，一组使用新的送达时间估算模型，另一组使用现有模型。比较这些组之间的结果。

客户参与度：衡量客户与应用程序的互动，例如检查送达时间、订单频率和应用使用时长。

客户留存率：跟踪客户是否继续使用服务，这表明对送达体验的满意度。

要求

训练

• 在训练期间，我们需要处理大量数据。为此，训练管道应具有高吞吐量。为实现此目的，数据可以组织在 Parquet 文件中。
• 模型应每隔几小时重新训练一次。送达操作处于动态环境中，受许多外部因素影响：交通、天气状况等。因此，模型必须学习并适应新环境。例如，在比赛日，某些地区的交通状况会变差。如果没有重新训练的模型，当前模型将持续低估送达时间。调度器负责每天多次重新训练模型。
• 平衡高估和低估。为此，每天多次重新训练以适应市场动态和交通状况。

高吞吐量：在机器学习中，“高吞吐量”指的是快速高效地处理大量数据的能力。

为实现高吞吐量，训练管道应优化速度和效率。这涉及使用允许快速读写数据的数据存储和处理技术。因此我们可以考虑使用 Parquet 文件 ：Apache Parquet 是一种专为高效数据处理而设计的列式存储文件格式。

以下是使用 Parquet 文件帮助实现高吞吐量的原因：

Parquet 以列式格式存储数据，这意味着某个列的所有值都存储在一起。这与行式格式（如 CSV）形成对比，其中每行的数据存储在一起。对于许多机器学习任务，操作是在整个列上进行的（例如计算平均值、数据标准化）。列式存储使这些操作更高效。

Parquet 文件支持多种压缩算法（例如 Snappy、Gzip），减少了磁盘上的数据大小。
速度：较小的文件大小意味着需要从磁盘读取到内存的数据较少，加快了数据加载时间。

推理

• 对于每次送达，系统需要尽可能频繁地进行实时估算。为了简单起见，我们假设每次送达需要进行 30 次预测。
• 近实时更新：任何状态变化都需要尽快通过模型评分，即餐馆开始准备餐食，司机开始驾车前往客户。
• 每当送达有变化时，模型运行新估算并向客户发送更新。
• 捕获近实时聚合统计数据，即特征管道从多个源（Kafka、数据库）聚合数据以减少延迟。
• 延迟为 100ms 至 200ms

特征管道是一个系统，它从不同来源收集原始数据，处理并将其转化为机器学习模型用于预测的特征。

总结

类型	期望目标
指标	优化为低 RMSE。估算时间应小于 10-15 分钟。如果我们高估，客户下单的可能性较低。低估可能会导致客户不满。
训练	高吞吐量，能够每天多次重新训练
推理	延迟为 100ms 至 200ms

3. 模型

特征工程

特征	特征工程	描述
订单特征	小计、菜系
商品特征	价格和类型
订单类型	团体、餐饮
商户详情
商店ID	商店嵌入
实时特征	订单数量、骑手数量、交通状况、旅行时间估算
时间特征	一天中的时间（午餐/晚餐）、星期几、周末、假日
历史汇总	过去X周的平均送达时间：商店/城市/市场/一天中的时间
相似度	平均停车时间、历史时间的方差
经纬度	测量订单送达时间（到消费者）与餐馆之间的预计驾驶时间

订单特征：从订单详情中提取的特征。例如，订单的总成本（小计）和菜系类型（如意大利菜、中国菜）。这些特征可能会影响送达时间，因为不同菜系的准备时间可能不同。小计 是所有商品价格的总和。不包括税费、配送费或小费。

商品特征：从订单中的单个商品中提取的特征。商品价格和类型（如饮料、主菜）可以影响整体准备和包装时间。

订单类型：标识订单类型。与单个订单相比，团体订单和餐饮服务的准备和送达时间通常更长。

商户详情：关于商户（餐馆）的详细信息，如他们的历史表现、准备速度和受欢迎程度。这些因素会影响送达时间。

商店ID：商店的数值表示（嵌入），捕捉各种特征和历史表现。这有助于模型理解不同商店之间的差异。

实时特征：捕捉实时条件的特征，如当前正在处理的订单数量、可用的送餐员数量、当前交通状况和旅行时间估算。这些对准确预测实时送达时间至关重要。

时间特征：指示订单下单时间的时间特征。送达时间可能会根据是否在高峰时间（午餐或晚餐）、周末或假日期间显著变化。

历史汇总：汇总的历史数据，如特定商店、城市、市场和一天中某些时间段的过去几周的平均送达时间。这有助于根据过去的表现预测未来的送达时间。

相似度：捕捉条件相似性的特征，如送达地点的平均停车时间和历史送达时间的方差。这些可能表明潜在的延迟。

经纬度：测量从餐馆到送达地点的距离和预计驾驶时间的地理空间特征。这对于准确估算旅行时间至关重要。

训练数据

我们可以使用过去6个月的历史送达数据作为训练数据。历史送达数据包括送达数据和实际总送达时间、商店数据、订单数据、客户数据、位置和停车数据。

模型

梯度提升决策树

• 梯度提升决策树示例

  

• 梯度提升决策树的工作原理

1. 计算基线：给定历史送达数据，模型首先计算平均送达时间。此值将用作基线。

2. 测量残差：模型测量预测值与实际送达时间之间的残差（误差）。

   $$\text{Error}=\text{Actual Delivery Time}-\text{Estimated Delivery Time}$$

3. 构建决策树：构建决策树以预测残差。每个叶子节点将包含对残差值的预测。

4. 使用所有树进行预测：使用所有树进行预测。使用以下公式构建送达时间预测值：

   $$\text{Estimated Delivery Time}=\text{Average Delivery Time}+\text{learning rate}\times \text{residuals}$$

5. 计算新残差：给定新的估算送达时间，计算新的残差。使用这些值在步骤3中构建新的决策树。

6. 重复：重复步骤3-5，直到达到超参数中定义的迭代次数。

在 梯度提升决策树（GBDT） 中，目标是最小化预测值与实际值之间的差异。这些差异称为残差。通过构建决策树来预测残差，模型关注于先前预测所犯的错误。其思想是通过后续迭代纠正这些错误。

RMSE 优化问题

优化RMSE的一个问题是，它对低估预测和高估预测的惩罚是相同的。考虑下表。两个模型都使用提升决策树。

实际值	模型1预测值	模型1平方误差	模型2预测值	模型2平方误差
30	34	16	26	16
35	37	4	33	4

虽然模型1和模型2有相同的RMSE误差，但模型1高估了送达时间，这会阻止客户下单。模型2低估了送达时间，可能会导致客户不满。

4. 计算与估算

假设

为简化，我们可以做以下假设：

• 每月有200万活跃用户，总共有2000万用户，30万家餐馆，20万名司机送餐。
• 平均每年有2000万次送达。

数据量

• 1个月内，我们收集了200万次送达的数据。每次送达相关特征大约有500字节。

• 总大小：$500\text{ bytes}\times 2\times 10^6=10^9\text{ bytes}=1\text{ Gigabytes}$

规模

• 支持2000万用户。

5. 系统设计

• 特征存储：提供快速查找以实现低延迟。具有高可用性的任何键值存储的特征存储是一个不错的选择，如 Amazon DynamoDB。
• 特征管道：从 Kafka 读取数据，进行转换并汇总近实时统计数据。然后将它们存储在特征存储中。
• 数据库：送达订单数据库存储历史订单和送达数据。数据准备是一个从数据库创建训练数据的过程。我们可以将训练数据存储在云存储中，例如 S3。
• 我们有三个服务：状态服务、通知服务和估算送达时间服务。前两个服务处理实时更新，估算送达时间服务使用我们的机器学习模型来估算送达时间。
• 我们有一个调度器，负责协调每天多次重新训练模型。训练后，我们将模型存储在模型存储中。

让我们检查系统的流程：

1. 用户请求估算送达时间

4. 估算送达时间服务返回时间估算给应用服务器。应用服务器将时间估算返回给用户

• 主要有三种类型的用户：消费者/用户、送餐员和餐馆。

• 用户流程：

  • 用户访问主页，检查他们的食物订单，并请求应用服务器估算送达时间。
  • 应用服务器将请求发送到估算送达时间服务。
  • 估算送达时间服务从模型存储中加载最新的机器学习模型，并从特征存储中获取所有特征值。然后使用机器学习模型预测送达时间并将结果返回给应用服务器。

• 餐馆/送餐员流程：

  • 当餐馆有进展时，例如开始制作菜肴或包装食物，他们会将状态发送给状态服务。
  • 状态服务更新订单状态。此事件通常会在队列服务（如 Kafka）中更新，因此其他服务可以订阅并相应地获取更新。
  • 通知服务订阅消息队列（如 Kafka），并实时接收最新的订单状态。

6. 设计扩展

• 我们扩展服务以处理大量每秒请求。我们还使用负载均衡器在应用服务器之间平衡负载。
• 我们利用流处理系统如 Kafka 来处理通知以及模型预测。一旦我们的机器学习模型完成预测，它会将预测结果发送到 Kafka，以便其他服务可以立即获取通知。

7. 后续问题

问题	答案
使用 StoreID 嵌入作为特征的缺点是什么？	我们需要评估使用 StoreID 嵌入在处理新店方面是否有效。
我们需要多久重新训练一次模型？	这取决于，我们需要有基础设施来监控在线指标。当在线指标下降时，我们可能需要触发模型重新训练。

缺点：处理新店：使用 StoreID 嵌入的一个重大挑战是处理没有历史数据的新店。由于新店的嵌入未定义，模型可能无法很好地处理这些新店。

8. 总结

• 我们学习了如何使用梯度提升决策树将估算送达时间表述为一个机器学习问题。
• 我们学习了如何收集和使用数据来训练模型。
• 我们学习了如何使用 Kafka 处理日志和模型预测以实现近实时预测。

附录

离线指标示例

假设我们有5个送达订单，实际送达时间和预测送达时间如下（单位：分钟）：

送达订单	实际时间 (y)	预测时间 (predict)
1	30	32
2	25	28
3	40	36
4	35	38
5	20	22

首先，计算平方差：
$$(32-30{)}^2=4$$
$$(28-25{)}^2=9$$
$$(36-40{)}^2=16$$
$$(38-35{)}^2=9$$
$$(22-20{)}^2=4$$

将这些平方差相加：
$$4+9+16+9+4=42$$

除以样本数 (n = 5) 并取平方根：
$$\text{RMSE}=\sqrt{\frac{42}{5}}=\sqrt{8.4}\approx 2.9$$

因此，此示例中的RMSE约为2.9分钟。

梯度提升决策树的示例解释

让我们通过一个具体示例来逐步解释梯度提升决策树（GBDT）的工作原理。假设我们有以下历史送达数据（单位：分钟）：

送达订单	实际时间 (y)	特征 (X)
1	30	10
2	25	8
3	40	12
4	35	11
5	20	7

为了简化，假设只有一个特征 ( X ) 代表一些关于订单和交通状况的汇总信息。

第一步：计算基线

首先，我们计算所有历史数据的平均送达时间。此平均值作为所有送达的初始预测。

$$\text{平均送达时间}=\frac{30+25+40+35+20}{5}=30\text{ 分钟}$$

所以，我们对所有送达的初始预测为30分钟。

第二步：测量残差

接下来，我们计算实际送达时间和初始预测之间的残差（误差）。

送达订单	实际时间 (y)	初始预测	残差 (误差)
1	30	30	0
2	25	30	-5
3	40	30	10
4	35	30	5
5	20	30	-10

第三步：构建决策树

我们使用特征 ( X ) 构建决策树来预测残差。

特征 (X)	残差 (误差)
10	0
8	-5
12	10
11	5
7	-10

假设决策树如下所示：

   X <= 9.5
  /      \
-7.5     X <= 11.5
        /       \
       7.5       5

此树将数据划分为不同区域，并预测每个区域的平均残差。

第四步：使用所有树进行预测

使用学习率调整预测值。假设学习率为0.1。更新后的预测值为：

$$\text{新预测}=\text{初始预测}+\text{学习率}\times \text{残差预测}$$

让我们计算更新后的预测值：

送达订单	初始预测	残差预测	新预测
1	30	7.5 (对 $X>9.5$)	30 + 0.1 * 7.5 = 30.75
2	30	-7.5 (对 $X\le 9.5$)	30 + 0.1 * -7.5 = 29.25
3	30	7.5 (对 $X>11.5$)	30 + 0.1 * 7.5 = 30.75
4	30	7.5 (对 $9.5<X\le 11.5$)	30 + 0.1 * 7.5 = 30.75
5	30	-7.5 (对 $X\le 9.5$)	30 + 0.1 * -7.5 = 29.25

第五步：计算新残差

使用更新后的预测值计算新残差。

送达订单	实际时间 (y)	新预测	新残差 (误差)
1	30	30.75	30 - 30.75 = -0.75
2	25	29.25	25 - 29.25 = -4.25
3	40	30.75	40 - 30.75 = 9.25
4	35	30.75	35 - 30.75 = 4.25
5	20	29.25	20 - 29.25 = -9.25

第六步：重复

我们根据超参数定义的迭代次数重复步骤3-5。每次迭代都会构建一个新的决策树来预测新残差并相应地调整预测值。

通过迭代地构建决策树来预测残差并调整预测值，GBDT模型逐步提高其估算送达时间的准确性。学习率确保每棵树仅做出小幅调整，以避免过拟合。

参考文献:

• 来自educative的机器学习系统设计