算法时间估算的基本理论

自然灾害和风险评估是从公众到政府应急管理人员等各类决策者的重要基础。快速量化损失和预测未来可能的损失，通常是了解当前情况的第一步。遥感影像生成的土地利用/土地覆盖（Land Use/Land Cover，以下简称LULC）产品为此提供了重要的第一手信息。然而，由于决策过程通常具有紧迫性，在有限的时间和资源下选择合适的分类算法可能极具挑战性。除了分类精度外，算法的实际时间消耗也是运行任务前需要仔细评估的关键因素（Donoho 2012, Huang 2017, Khatami 2016）。如果无法准确预测时间消耗，在紧急情况下选择LULC分类算法可能会显得盲目和主观。

现有的分类任务时间消耗估算方法主要分为两类：(1) 基于采样数据的方法；(2) 基于时间复杂度的方法。第一类方法通过运行程序并对采样数据集进行时间计算来估算实际运行时间，假设样本与整个数据集之间的运行时间可以通过线性或非线性关系简化。然而，这种方法存在以下缺点：(1) 线性或非线性关系高度依赖于硬件环境，难以在不同计算环境中推广；(2) 算法的不同参数（操作参数和隐藏参数）的影响被视为黑箱，且其对运行时间的具体影响尚不明确。第二类方法基于时间复杂度分析，例如传统时间复杂度（Traditional Time Complexity，以下简称TTC）。TTC是输入规模（如样本数量）的函数，用于衡量随着输入规模增加，计算复杂度的变化。然而，TTC忽略了许多低阶细节，难以准确预测实际运行时间，特别是在遥感LULC分类任务中，时间消耗不仅与数据规模相关，还与其他参数（如波段数或支持向量数量）密切相关。

事实上，分类算法的时间消耗会受到以下因素的影响：(1) 数据规模；(2) 类别数量；(3) 波段/特征数量；(4) 算法的迭代结构；(5) 算法的操作参数（如随机森林中的树的数量）；(6) 算法的隐藏参数（如支持向量的数量）。这些因素通过复杂的机制共同影响算法的实际时间消耗。如何量化每个因素的贡献是准确预测运行时间的关键。

基于FPTC进行时间估算的基础理论与常见算法FPTC的推导

FPTC由两部分组成：第一部分为 $F(n,m,v,\boldsymbol{\theta}’)$，与算法结构密切相关，可通过分析特定分类器的结构推导得出。该部分是关于 $n$（样本量）、$m$（类别数）、$v$（波段数）和 $\boldsymbol{\theta}’$（算法相关参数合集）的函数。不同算法的 $\boldsymbol{\theta}’$ 可能有所不同，例如，$k$NN 的 $\boldsymbol{\theta}’$ 包括最近邻数 $u$，而 SVM 的 $\boldsymbol{\theta}’$ 包括迭代次数 $Q$ 和支持向量数量 $k$。第二部分为系数 $\omega$，反映计算环境（如CPU/GPU或RAM速度）对运行时间的影响。通过在数据集的一小部分上进行预实验，可以评估特定分类器的 $\omega$ 值。结合这两部分，FPTC定义如下：

\[t^* = F(n,m,v,\boldsymbol{\theta}')\] \[t' = \omega \times t^*\]

其中，$t’$ 表示实际运行时间，$\omega$ 表示系数，$t^*$ 是通过分析算法结构预估的时间。在后续章节中，我们将推导遥感领域五种经典分类器的FPTC，包括 $k$NN、LR、CART、RF 和 SVM。

$k$NN的FPTC推导

$k$NN 分类器是一种懒惰学习器，其模型建立时间成本较低，但对测试样本进行分类的时间成本较高。为了计算测试样本的时间复杂度，我们将 $k$NN 分类器的 FPTC 分解为两部分：第一部分是计算训练样本 $\textbf{x}^{(e)}$ 与测试数据之间的距离，其 FPTC 为 $F(v)$；当训练集有 $n$ 个样本时，FPTC 为 $F(vn)$。第二部分是从训练集中选择距离最近的 $u$ 个样本，这是经典的最优搜索问题，其最优 FPTC 为 $F(nv + n\log_2u)$。因此，$k$NN 分类器的总 FPTC 为 $F(nv + n\log_2u)$。考虑到系数 $\omega_{kNN}$，$k$NN 分类器的实际运行时间 $t’_{kNN}$ 表达如下：

\[t'_{kNN} = \omega_{kNN} \times t^*_{kNN} = \omega_{kNN} \times F(nv + n\log_2u)\]

LR的FPTC推导

多分类 LR 分类器通过将后验概率的 Sigmoid 变换替换为 Softmax 变换来执行多分类任务。LR 通常将 L2 范数作为正则化项加入损失函数，以提高分类器的稳定性和鲁棒性。根据推导，具有 L2 范数和 Softmax 后验概率的 LR 损失函数形式如下：

\[J(\boldsymbol{\theta}) = -\frac{1}{n} \sum_{i=1}^n \sum_{j=1}^m 1\{y^{(i)}=j\} \cdot \log\frac{\exp(\boldsymbol{\theta}_j^T \textbf{x}^{(i)})}{\sum_{l=1}^m \exp(\boldsymbol{\theta}_l^T \textbf{x}^{(i)})} + \frac{\alpha}{2} \|\boldsymbol{\theta}\|_2^2\]

其中，$\boldsymbol{\theta}$ 是 $v \times m$ 的矩阵，$\boldsymbol{\theta}$ 中的元素是 LR 中的参数，$\theta_{pj}$ 是要素图层 $p$ 中 $j$ 类别的权重，$\alpha$ 的大小影响正则化强度。

LR 分类器的目标是最小化损失函数以得到 $\boldsymbol{\theta}$ 的最优值。随机平均梯度（stochastic average gradient，SAG）是优化 LR 分类器的常用策略。SAG 算法是对随机梯度下降算法（stochastic gradient descent，SGD）的一种改进。根据推导，具有 L2 范数和 Softmax 变换的 LR 分类器中的参数 $\boldsymbol{\theta}j^T = {\theta{1j}, \theta_{2j}, \theta_{3j}, \ldots, \theta_{vj}}$ 是根据以下公式进行更新：

\[\boldsymbol{\theta}_j^{r+1} = \boldsymbol{\theta}_j^r - \frac{\lambda}{n} \sum_{i=1}^n z_i^r\] \[\textbf{z}_i^r = \begin{cases} \nabla_{\boldsymbol{\theta}_j} J(\boldsymbol{\theta}) & \text{if } i = i_r \\ z_i^r & \text{otherwise} \end{cases}\] \[\nabla_{\boldsymbol{\theta}_j} J(\boldsymbol{\theta}) = \textbf{x}^{(i)} (1\{y^{(i)}=j\}) - \frac{\exp(\boldsymbol{\theta}_j^T \textbf{x}^{(i)})}{\sum_{l=1}^m \exp(\boldsymbol{\theta}_l^T \textbf{x}^{(i)})} + \alpha \boldsymbol{\theta}_j\]

其中，$\lambda$ 是学习率，$i_r$ 是从 ${1, 2, 3, \ldots, n}$ 中随机选出的第 $r$ 次迭代。

对于每次迭代，公式 (5)-(7) 更新一次。因此，损失函数根据公式 (7) 计算一次。同时，具有 $v$ 元素的 $\boldsymbol{\theta}j$ 根据公式 (6) 更新一次。基于上述分析，每次迭代的 FPTC 为 $F(mvn)$。在多分类 LR 中，假设对每个类别进行 $q$ 次迭代后收敛（$q$ 为 SAG 过程中的迭代次数），则总 FPTC 为 $F(Qmvn)$。在这种情况下，$m$ 类别的 FPTC 为 $F(Qm^2vn)$。最后，LR 的 FPTC 与实际运行时间 $t’{LR}$ 关联如下，推导 LR 的 FPTC 的关键步骤如图所示：

\[t'_{LR} = \omega_{LR} \times t^*_{LR} = \omega_{LR} \times F(Qm^2vn)\]

FPTC的验证与精度评价

为了验证 FPTC 的准确性，我们采用了三种评估方法：1) 用 1:1 的曲线图将实际运行时间与 FPTC 进行比较；2) 利用 FPTC 估计运行时间，并计算估计运行时间与观测运行时间之间的均方根误差（Root Mean Squared Error，RMSE）；3) 比较 FPTC 和 TTC 在不同特征选择下的实际运行时间。

我们从训练数据集中随机选择子训练样本，并构造子训练样本集。对这些样本进行分类，并记录真实的运行时间。如图所示，FPTC 与实际运行时间之间的线性关系表明了 FPTC 的有效性。5 个分类器的 R 平方值均大于 0.99（$k$NN：0.991，LR：0.997，CART：0.999，RF：1.000，SVM：0.999），表明 FPTC 的算法部分与实际运行时间之间存在极强的线性关系（$p < 0.001$）。

每个算法的参数 $\omega$ 可以从各自相关性曲线的斜率中获得。

无论训练数据的大小如何，都可以基于两个可用的数据集粗略地估计斜率。这意味着可以通过在总数据集的两个小部分下预先运行算法来获得此值。由于系数 $\omega$ 表示 FPTC 的物理部分，因此仅当算法应用于不同的计算环境时，该值才会改变。

此外，FPTC 还可以通过不同的参数反映运行时间的变化。当 $n$ 个训练样本由低到高变化，且其他影响参数保持不变时，支持向量机的 FPTC 最容易受到这种变化的影响，其次是 RF、CART、$k$NN 和 LR。如果 $n$ 从 1 变为 128，则 LR 的 FPTC 增加 128 倍，$k$NN 增加 128 倍多，CART 和 RF 增加 896 倍，SVM 增加 16,384 倍以上。当分类数 $m$ 由低变高且其他影响参数保持不变时，支持向量机和 LR 的 FPTC 最容易受到这种变化的影响，其次是 CART 和 RF，而 $k$NN 则不受影响。例如，如果 $m$ 从两个类变为 200 个类，则 SVM 和 LR 的 FPTC 增加 10,000 倍，CART 和 RF 的 FPTC 增加 100 倍。当特征数或波段数 $v$ 由低变高且其他影响参数不变时，SVM、LR、CART 和 RF 的时间复杂度在多项式时间内变化，而 $k$NN 的时间复杂度受影响较小。

其次，为了进一步说明 FPTC 和 TTC 的差异，我们分析了在不同波段（$v = 3, 4, 5, \ldots, 10$）和不同样本大小（$n = 10, 20, 30, \ldots, 100,000$）的所有组合下，FPTC 和 TTC 的变化趋势，并与实际运行时间趋势进行了比较。在图 9 中，TTC、FPTC 和实际运行时间的值以红色到绿色从低到高映射。结果表明，TTC 对 $v$ 的变化没有反应，而 FPTC 能更好地反映 $v$ 的变化。

正如我们所看到的，在不同的带宽和数据大小下，FPTC 显示出与实际运行时间相似的模式。TTC 的模式是不同的，因为 TTC 忽略了不同特征/波段的影响。

总结

在自然灾害应急响应中，准确的时间预测有助于应急管理者在有限时间和资源下选择合适的分类算法。本研究提出了 FPTC 和系数 $\omega$，用于估算分类器的运行时间。通过研究分类器的结构及其数学原理，推导了五种常见分类器（$k$NN、LR、CART、RF 和 SVM）的 FPTC，并验证了 FPTC 的有效性。研究结果表明：

提出了一种定量评估机器学习分类器时间效率的方法——FPTC，并推导了五种通用分类器的 FPTC。结果显示，$k$NN 的 FPTC 为 $F(nv + n\log_2u)$，LR 的 FPTC 为 $F(Qm^2vn)$，CART 的 FPTC 为 $F((m+1)nv\log_2n)$，RF 的 FPTC 为 $F(s(m+1)nv\log_2n)$，SVM 的 FPTC 为 $F(m^2Qv(n+k))$。
FPTC 与运行时间之间存在显著的线性关系（$R^2 \geq 0.991$，$p \leq 0.001$），验证了 FPTC 推导过程的正确性。每种算法的修正系数可通过线性回归获得。
每个分类器的运行时间可通过 FPTC 中的系数 $\omega$ 进行估算。研究表明，实际运行时间与估算运行时间之间的平均均方根误差为 3.34s，说明了 FPTC 在预测算法运行时间上的可行性和准确性。

未来研究中，我们计划为更多算法推导 FPTC 值，以便在紧急任务中快速筛选出精度高、FPTC 低的合适算法，帮助应急管理人员根据可用遥感数据量快速决策。

原文链接

Zheng, X., Jia, J., Guo, S., Chen, J., Sun, L., Xiong, Y., & Xu, W. (2021). Full Parameter Time Complexity (FPTC): A Method to Evaluate the Running Time of Machine Learning Classifiers for Land Use/Land Cover Classification. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 14, 2222–2235. https://doi.org/10.1109/JSTARS.2021.3050166

快速评估监督学习中常用遥感分类算法的时间效率