将时间戳集合分解为时间间隔均匀的子集的算法

Question

我有一个包含> 100,000条记录的数据集，其中每条记录都有一个时间戳记。

此数据集已从多个“控制器”节点汇总而来，每个“控制器”节点都从一组子节点收集其数据。每个控制器周期性地收集这些记录（例如，每5分钟一次或每10分钟一次），并且是将时间戳应用于记录的控制器。

---

E.g：

控制器的一个可能有20个记录在时间t时戳，共有23条记录在时间t + 10 minutes时间戳的时刻t + 5 minutes，33条记录。

控制器二可能在时间(t + 2 minutes) + 10 minutes时间戳有30个记录，时间戳记录为32个记录(t + 2 minutes) + 20 minutes,41个记录在时间(t + 2 minutes) + 30 minutes等时间戳记等。

---

现在假设你拥有的唯一信息是集所有的时间标记和多条记录怎么出现在每个时间戳的计数。也就是说，你不知道i)哪一组记录是由哪个控制器产生的，ii)是每个控制器的采集间隔或控制器总数的ii)。是否有一种算法可以将所有时间戳的集合分解为单个子集，使得每个给定子集的连续（有序）元素之间的差异变化非常接近0，而将来自一个子集i的任何元素添加到另一个子集j增加这种差异？请记住，对于此数据集，由于CPU时序/网络延迟等原因，单个控制器的“周期性”可能会波动+/-数秒。

我的最终目标是建立a)有多少个控制器，每个控制器的采样间隔为b)。到目前为止，我一直在考虑周期函数的问题，所以也许有一些可能有用的分解方法。

另外一点是我不需要知道哪个控制器的每条记录都来自我只需要知道每个控制器的采样间隔。所以例如如果有两个控制器在时间u开始采样，一个以5分钟间隔采样一个，另一个以50分钟间隔采样，那么很难在50分钟标记处将两者分开，因为5是因子50.这并不重要，只要我能够获得足够的信息来计算每个控制器的间隔，尽管偶尔会有这些重叠。

Answer 1

一个基本的方法是对数据集进行FFT分解（或者，如果你觉得奇怪，是周期图）并在结果频谱中寻找峰值。这会给你一个控制器周期的粗略近似值，甚至可以给你估计它们的数量（通过查看峰值的高度，它可以告诉你有多少记录被记录）。