天际线数量-效用序列模式挖掘：一种高效且有效的方法

《Knowledge-Based Systems》：Skyline quantity-utility sequential pattern mining: An efficient and effective approach

高效用顺序模式挖掘需兼顾数量与效用双目标，现有方法依赖阈值或Top-k策略，导致计算复杂度高且稳定性不足。本文提出SQUMiner算法，通过QU-array和QUPro投影数据库优化存储结构，设计全局与局部剪枝策略，结合最大效用数量数组与序列帕累托前沿数组动态筛选非支配模式，在20个真实数据集和8个合成数据集上验证其效率提升达两个数量级，内存占用低于400MB，且稳定性显著优于基线方法。

　　在当今数据驱动的决策环境中，挖掘有价值的数据模式是支持商业分析、用户行为预测和网页点击流研究的重要手段。传统的序列模式挖掘方法主要依赖于单一的指标，如最低效用阈值或Top-k策略，这些方法在实际应用中常常面临一些挑战。例如，设定合适的阈值需要用户具备一定的专业知识，而这种依赖性使得算法在面对复杂数据集时容易产生不稳定的输出。此外，这些方法在处理大规模数据时往往需要较高的计算资源和存储空间，特别是在涉及复杂效用上限计算和低效剪枝策略的情况下。因此，为了提高算法的鲁棒性和稳定性，同时降低计算和存储成本，研究者们开始探索将多个因素纳入考虑范围的序列模式挖掘方法。

在现有研究中，高效用序列模式挖掘（High Utility Sequential Pattern Mining, HUSPM）已经成为一个重要的研究方向。HUSPM不仅关注序列的出现频率，还特别关注其带来的经济价值，例如在零售数据库中，跟踪商品数量和单位利润，可以发现某些看似罕见但具有高利润的序列模式。这些模式可能在某些应用场景中对决策具有重要影响。然而，HUSPM仍然存在一些局限性，特别是在如何平衡多个因素以及如何高效处理数据方面。

为了克服这些局限性，研究者们提出了基于天空线技术（Skyline Technique）的序列模式挖掘方法。天空线技术最初应用于多目标优化问题，其核心思想是确保没有一个单一目标能够主导整个决策过程。在序列模式挖掘中，这一技术可以帮助识别那些在多个因素上都具有相对优势的模式，从而避免传统方法可能遗漏的重要信息。然而，将天空线技术应用于高数量-高效用序列模式挖掘仍然面临两大挑战。

第一个挑战是如何设计一种高效且具有选择性的天空线数量-效用剪枝策略。传统的HUSPM方法主要依赖于效用上限计算和剪枝策略，这些方法在处理数据时需要大量的计算资源和存储空间。例如，一些研究提出使用复杂的效用上限计算来减少候选模式的数量，但这种方法往往需要多次遍历存储结构，导致计算开销较大。此外，一些剪枝策略可能过于保守，生成过多的候选模式，从而影响算法的效率。因此，设计一种能够同时考虑数量和效用因素的剪枝策略，是提高算法性能的关键。

第二个挑战是如何开发一种紧凑的存储结构，以支持数量-效用序列模式挖掘。在HUSPM中，候选模式的数量通常会随着序列长度和项目集规模的增加而呈指数增长，尤其是在使用最低效用阈值或Top-k策略的情况下。为了应对这一问题，一些研究提出了不同的存储结构，如UL-list，用于高效存储候选子序列的效用信息。这些结构可以减少重复计算，提高算法的运行效率。然而，这些结构在某些情况下可能过于复杂，导致存储成本过高，从而影响算法的稳定性。因此，开发一种既能有效存储序列信息，又能减少存储开销的结构，是实现高数量-高效用序列模式挖掘的重要任务。

为了应对上述挑战，我们提出了一种名为SQUMiner的新型算法，该算法结合了天空线数量-效用（Skyline Quantity-Utility, SQU）技术，旨在同时考虑数量和效用因素，以支持更精确的多目标决策。SQUMiner的核心思想是通过引入高效的剪枝策略和紧凑的存储结构，减少冗余计算并优化算法性能。具体来说，我们设计了两种紧凑的数据结构：QU-array和QUPro投影数据库。QU-array用于高效存储序列的数量和效用信息，从而减少存储开销并提高计算效率。QUPro投影数据库则基于父序列的QUPro信息构建，通过使用扩展列表来避免重复遍历原始数据库，从而显著提升算法的运行效率。

此外，我们还提出了全局和局部剪枝策略，这些策略基于效用上限计算，能够有效减少搜索空间。具体来说，我们引入了最大效用数量数组（Maximum Utility Quantity Array, MUQA）和序列帕累托前沿数组（Sequence Pareto Front Array, SPFA）。MUQA用于存储每个序列的最大效用，从而帮助剪枝那些效用较低的1-序列。SPFA则用于对MUQA的输出进行非支配排序，评估扩展序列是否支配现有序列。如果扩展序列具有更高的效用和数量，则会被保留并递归扩展。这些策略能够有效减少候选模式的数量，同时保持较高的剪枝效率。

在实验部分，我们使用了20个真实数据集和8个合成数据集来评估SQUMiner的性能。这些数据集涵盖了多种类型，包括基因组数据、商业数据、点击流数据、时间序列数据、文本数据、信号数据、位置数据和合成数据。通过这些数据集的测试，我们发现SQUMiner在多个指标上均优于现有的六种先进算法（State-of-the-Art, SOTA）。例如，在运行时间方面，SQUMiner在某些数据集上实现了高达两个数量级的加速，同时在存储使用方面也表现出更高的效率。此外，SQUMiner在大多数数据集上的处理时间均在5秒以内，且所需的内存不超过400MB。

SQUMiner的主要贡献包括以下几个方面。首先，我们设计了QU-array和QUPro两种紧凑的数据结构，这些结构能够高效管理序列的数量和效用信息，同时减少冗余的数据库投影和存储开销。其次，我们提出了全局和局部剪枝策略，这些策略基于效用上限计算，能够有效减少搜索空间并提高算法的运行效率。第三，我们开发了一个包含20个真实数据集和8个合成数据集的基准数据库，这些数据集涵盖了多种类型，以评估SQUMiner的泛化能力。通过这些数据集的测试，我们发现SQUMiner在多个指标上均优于现有的SOTA方法，实现了更高的运行效率和存储效率。

在实际应用中，SQUMiner的性能优势使其能够更好地支持决策过程。例如，在推荐系统中，SQUMiner可以挖掘用户行为序列，如浏览、购买或内容消费，从而预测未来的偏好。在市场篮子分析中，SQUMiner可以识别那些在数量和效用上都具有优势的模式，从而帮助商家优化库存管理和营销策略。在DNA序列分析中，SQUMiner可以挖掘具有高数量和效用的基因序列，从而支持生物学研究和医学诊断。在文本数据处理中，SQUMiner可以识别具有高数量和效用的文本模式，从而支持自然语言处理和信息检索。

此外，SQUMiner的灵活性和适应性使其能够在多种数据类型和应用场景中发挥作用。例如，在点击流数据处理中，SQUMiner可以挖掘用户在网页上的行为序列，从而支持网站优化和用户体验提升。在时间序列数据处理中，SQUMiner可以识别具有高数量和效用的时间模式，从而支持时间预测和分析。在信号数据处理中，SQUMiner可以挖掘具有高数量和效用的信号模式，从而支持信号处理和数据分析。在位置数据处理中，SQUMiner可以挖掘具有高数量和效用的位置模式，从而支持位置分析和优化。

通过这些应用，我们可以看到SQUMiner在多个领域中的潜力。例如，在推荐系统中，SQUMiner可以挖掘用户行为序列，从而提高推荐的准确性和相关性。在市场篮子分析中，SQUMiner可以识别那些在数量和效用上都具有优势的模式，从而帮助商家优化库存管理和营销策略。在DNA序列分析中，SQUMiner可以挖掘具有高数量和效用的基因序列，从而支持生物学研究和医学诊断。在文本数据处理中，SQUMiner可以识别具有高数量和效用的文本模式，从而支持自然语言处理和信息检索。

总之，SQUMiner作为一种基于天空线数量-效用的序列模式挖掘方法，能够有效克服传统方法在处理多目标决策时的局限性。通过引入高效的剪枝策略和紧凑的存储结构，SQUMiner在运行时间和存储使用方面均表现出显著的优势。这些优势使其在多个应用场景中具有广泛的适用性，能够更好地支持数据驱动的决策过程。未来，随着数据量的不断增加和应用场景的多样化，SQUMiner的研究和应用前景将更加广阔。