基于两阶段随机规划的聚类方法：在停车订阅服务中的使用行为模式挖掘应用

《TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES》：Clustering with two-stage stochastic programming: An application to usage behavior pattern mining in parking subscription services

　　• 从运筹学的角度出发，通过两阶段随机规划框架研究聚类问题。
• 识别和聚类订阅服务中的使用行为模式。
• 模型分析、保持最优性的改进措施以及有效的数学启发式算法。
• 实际停车订阅数据和公共数据集的案例研究展示了该方法的优势和计算效率。

**引言**
聚类是机器学习中的一个基本问题（Jain等人，1999年；Xu和Wunsch，2005年）。在给定未标记数据的情况下，聚类的目标是要识别出一小部分簇，并将每个对象分配到其中一个簇中（Xu和Wunsch，2005年）。聚类已在统计学和机器学习领域得到了广泛研究，从而发展出多种方法（Jain等人，1999年；Xu和Wunsch，2005年）。在本研究中，我们提出了一种新的视角，将聚类问题表述为一个两阶段随机程序。通过明确聚类与两阶段随机规划之间的结构对应关系，并利用这种对应关系进行模型和算法设计，所提出的方法提高了解决方案的质量和可解释性。
将聚类问题视为两阶段随机程序的关键原因在于它们都具有“一次决策，多次观测”的结构。考虑一组需要聚类的对象，将每个对象视为一次观测，即第二阶段中的一个场景。因此，这些场景集合定义了对观测样本的的经验分布（Sun和Fan，2024年）。在聚类过程中，选择一组簇中心并将每个对象分配到一个中心。在两阶段随机规划模型中，共同的簇中心构成第一阶段的决策，该决策在所有场景中都是共享的。第二阶段作为一个场景级别的评估层：在第一阶段共享的簇中心条件下，每个场景评估相应的观测值，并将其损失贡献到经验汇总中；目标是最小化整个场景集合的总损失。图1展示了聚类与两阶段随机规划之间的这种并行结构。
这种视角的价值不在于将聚类问题重新表述为优化问题本身，而在于明确其与两阶段随机规划的结构对应关系。具体来说，它阐明了传统聚类问题中隐含的决策-评估分离。这种分离在三个方面是有用的：首先，它使聚类组件的操作含义更加清晰，从而可以将簇中心解释为具有实际意义的代表；其次，它使聚类模型更易于扩展到复杂环境中；第三，它在两阶段随机规划和聚类之间建立了方法论上的桥梁，允许将分解、场景简化、场景学习、有效不等式以及定制的数学启发式/元启发式方法应用于聚类任务。

**应用**
为了评估所提出方法的有效性，我们将其应用于一个实际任务：订阅服务中的使用行为模式挖掘。订阅服务在现代交通系统中扮演着越来越重要的角色，包括出行即服务（MaaS）套餐（Bahamonde-Birke等人，2023年；Hao等人，2025年）、自动车辆订阅（Guan等人，2024年）、停车订阅（Akhavan-Tabatabaei等人，2014年）、自行车共享会员（Li等人，2025b年）、定制公交服务（Gu和Chen，2023年；Wang等人，2020年）以及电动汽车电池更换（Hu等人，2023年）。通过将按次付费交易替换为周期性预付费，订阅服务吸引了具有重复需求的用户，并降低了边际使用成本，从而促进了频繁且可预测的使用行为。为了支持运营分析和管理规划，服务提供商通常将多样化的用户行为归类为有限数量的代表性模式，以反映需求规律（Baumgarte等人，2021年；Du等人，2019年；Li等人，2020年；Xing等人，2020年；Xu等人，2019年；Yang等人，2019年）。这项任务可以自然地表述为一个聚类问题，即将用户的使用行为划分为代表性模式。因此，传统的聚类方法（如K-medians（Hakimi，1964年）、K-means（Lloyd，1982年；MacQueen，1967年）、K-medoids（Rousseeuw和Kaufman，1987年）和K-modes（Huang，1998年）已被广泛用于识别代表性模式和用户细分。

**研究方法**
在本研究中，我们从两阶段随机规划的角度来构建订阅服务中的使用行为模式挖掘模型。第一阶段识别一组代表性模式，并将每个用户分配到其中一个模式中。第二阶段评估每个观测记录与其分配模式的偏差，并将这些偏差汇总到各个场景中。这使得领域知识能够structured地整合到聚类过程中。例如，可以明确建模在订阅使用中常见的周期性节奏和记录结构，并适当权重具有不同信息价值的观测值。因此，所提出的框架通过清晰逻辑结构和有效结合领域特定特征来提高可解释性。

**模型复杂性和改进措施**
由于所提出的模型本质上是NP难的，我们引入了三种模型改进措施，将其重新表述为更紧凑但等效的结构。同时，为了高效解决大规模实例，我们开发了一种基于列生成的定制数学启发式算法。使用来自中国深圳的实际停车订阅数据和公共聚类数据集进行的数值实验验证了所提出框架和算法的有效性。

**主要贡献**
1. 从运筹学的角度提出了一种新的聚类方法，强调了聚类与两阶段随机规划之间的结构对齐。这种视角为聚类组件的操作和物理解释提供了清晰度，为在目标和约束中嵌入领域知识提供了系统框架，并建立了将两阶段随机规划方法应用于聚类问题的算法桥梁。我们在停车订阅服务中的使用行为模式聚类中应用了这一视角。在实际数据集上，与K-medians相比，所提框架将聚类损失减少了7.29%至17.57%；与K-medoids相比，减少了7.80%至17.57%；与K-modes相比，减少了5.74%至16.99%；与BanditPAM++相比，减少了5.74%至16.99%。除此之外，所提框架还可以推广到其他旨在最小化观测对象引起的经验分布总损失的聚类问题。
2. 证明了该问题的NP难度，并提出了改进模型以提高可解性。我们首先确立了使用行为模式挖掘问题的NP难度。为了提高计算可行性，分析了其结构特性，并提出了三种保持最优性的改进措施。计算实验表明，这些改进措施平均加速了20.68倍，扩大了可解实例的范围，并实现了更丰富的最优性基准测试。
3. 为解决实际问题开发了一种基于列生成的定制数学启发式算法（ET-CG），其中包含了一个定制的提前终止规则（ET-CG），以减轻标准列生成的长尾效应。数值结果表明，ET-CG在30.94-47.53秒内解决了实际规模的问题，与基于机器学习的基线相比，聚类损失减少了超过10%，同时保持了接近最优的解决方案质量。

**研究结构**
其余部分的结构如下：第2节回顾相关文献；第3节介绍用于订阅服务中使用行为模式聚类的两阶段随机规划框架；第4节提出了三种保持最优性的模型改进措施，以提高可解性同时保持精确性；第5节介绍了用于大规模实现的ET-CG数学启发式算法；第6节报告了一个实际停车案例研究，评估了所提出的方法并为订阅运营提供了管理见解；第7节使用公共数据集检验了该框架在更广泛聚类场景中的适用性；第8节总结了研究并讨论了未来的研究方向。

**文献回顾**
我们从五个方面回顾了相关文献：统计和机器学习聚类、基于优化的聚类、两阶段随机规划、基于列生成的启发式和元启发式方法以及订阅使用行为分析。

**模式聚类：问题描述和两阶段随机规划视角**
接下来，我们通过两阶段随机规划（2SP）视角来构建聚类模型。由于聚类是一个通用任务，其优化模型必须指定目标、相似性或损失度量以及结构或上下文约束。这些组件通常是特定于应用的，而不是通用的。我们使用订阅服务中的使用行为模式挖掘作为一个示例环境，来说明如何进行聚类。