论文：Akane: Perplexity-Guided Time Series Data Cleaning
会议：SIGMOD 2024
作者：Xiaoyu Han, Haoran Xiong, Zhenying He, Peng Wang, Chen Wang, X. Sean Wang
简介：时间序列中存在着大量的脏数据，例如不可靠的设备采集得到的传感器数据，有故障的测量系统记录得到的能源消耗数据等。现有的算法在时间序列数据清洗方面仍存在不小的缺陷，从脏数据识别的角度来看，大多数方法都存在较多的遗漏或错误；从清洗决策的角度来看，大多数方法得到的结果与真实值相去甚远。这些问题给时间序列数据清洗增添了许多挑战。
为了解决上述的挑战，我们提出了基于困惑度的时间序列数据清洗算法Akane，以此来更敏感地甄别脏数据，并通过上下文给出更准确的清洗决策。我们通过观察发现，绝大多数的真实时间序列中存在着重复模式。借助将时间序列中的重复模式类比成自然语言文本中的固定搭配，我们首次将困惑度引入时间序列数据清洗中，定义了一条时间序列的困惑度，并将清洗问题转化为在给定预算下最小化时间序列的困惑度这一最优化问题。考虑到时间序列中数据点的取值是连续的，我们设计了一个四阶段的算法框架来解决这个问题，包含时间序列符号化，概率计算，可能性最优化，以及时间序列重建。为了确保框架的可行性，我们对脏数据的影响进行了简要分析，并设计了自动预算选择策略。此外，我们还引入了基于同态模式聚合的改进概率计算方法和基于贪心的启发式算法来增强算法的适用性和易用性。与现有的11个方法在12个数据集上的对比充分证明了我们算法的有效性。
