FLCHUS-X: Cost-Aware Pruning for Mining Frequent Sequences with Low Average Cost and High Average Utility
本文介绍了 FLCHUS-X，一种用于挖掘具有低平均成本和高平均效用的频繁序列的成本感知剪枝算法，该算法通过建立平均成本的单调下界来改进了最先进的 FLCHUSPM，从而实现更激进且安全的剪枝策略，进而显著缩短了执行时间。
原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在浩瀚的数字历史档案中，从在线购物篮到学习平台，数据很少静止不动。它以事件流的形式到来，即一种一个动作引发另一个动作的序列。几十年来，计算机科学家一直在开发寻找这些流中模式的方法，寻找那些发生频率足够高、足以被视为具有显著性的序列。但仅靠频率本身是一种粗糙的工具。一个模式可能频繁出现却毫无用处，或者它可能很罕见却价值连城。为了解决这个问题，研究人员引入了“效用”（utility）的概念，这是一种衡量一个序列实际价值或利润的方法，而不仅仅是衡量它出现的次数。想象一位零售分析师，他不仅想知道人们是否购买面包，还想知道哪种特定的面包与黄油的组合能产生最多的收入。
然而，这种对利润的关注往往忽略了获取利润的代价。在现实世界中，高回报通常伴随着高成本，无论这种成本是以金钱、时间还是精力的形式来衡量。一个学习活动序列可能会带来极佳的效果，但如果它需要难以想象的学习时间，那么对于学生来说，它就不是一个有用的模式。因此，挑战在于找到那个“甜点”：既频繁、价值极高，又实现成本较低的序列。这就是挖掘具有低平均成本和高平均效用的频繁序列的问题。这是一个困难的谜题，因为通常能帮助计算机快速寻找模式的规则在这里并不适用；一个序列的成本和价值会随着你增加更多步骤而发生不可预测的变化，使得计算机很容易迷失在可能性的海洋中。
一位研究人员最近通过开发一种名为 FLCHUS-X 的新方法解决了这个问题。他们的工作针对了之前用于解决这一难题的一个算法中的特定缺陷。早期的这种方法试图通过仅观察数据中一个序列的第一次出现来估算其成本。研究人员发现，这种方法在本质上是不安全的。因为一个序列可以在单个记录中以多种不同的方式出现，该序列第一次出现时可能很昂贵，而稍后出现的同类序列可能非常便宜。如果计算机仅依赖于那第一次昂贵的出现，它可能会错误地判定一个序列成本过高，从而将其丢弃，连同所有可以基于其构建的潜在价值模式一并丢弃。在测试中，这种旧方法在一些测试的随机数据库中实际上遗漏了有效的模式。
为了修复这个问题，研究人员设计了一种新的成本估算方法，它观察的是一个序列可以出现的最低成本方式，而不是仅仅看第一次出现。他们从数学上证明了这种新的估算方式表现得非常可预测：如果一个短序列在其最低成本形式下已经过于昂贵，那么由它构建的任何更长的序列也必然过于昂贵。这一简单而强大的特性允许计算机在搜索过程中及早安全地丢弃大量的可能性，从而节省大量时间。他们还为从特定点分支出的搜索部分创建了第二种更专门的估算方法，确保在保持搜索效率的同时，不会遗漏任何有效的模式。
结果表明，该算法既准确又显著提高了速度。在与不使用任何捷径、检查每一个可能性的暴力破解法进行对比测试时，新算法得出了完全相同的结果，证实了它不会遗漏任何模式。在利用从在线点击流到体育统计数据的六个真实数据集进行的实验中，新方法的运行速度比之前的最佳方法快 1.4 到 3.1 倍。与剥离了不安全捷径后的旧方法版本相比，新算法的速度提升了高达 266 倍。它在实现这一速度提升的同时并没有消耗更多的内存，这意味着它不仅是理论上的改进，更是能够处理大型复杂数据集的实用性改进。
研究人员还发现，新方法通过旧方法无法实现的路径来剪枝搜索空间。通过在搜索开始前利用成本估算来过滤掉项目和连接，计算机在探索死胡同时花费的时间更少。这在项目频繁重复的稠密数据上特别有效。研究结论指出，虽然该算法是一个重大进步，但它继承自旧方法的效用边界仍有改进空间，这表明下一代工具可能会更加高效。不过，目前这项工作为在人类活动的无尽流动中寻找最有价值且最具成本效益的模式提供了一种可靠且快速的方法。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。