將時間戳集合分解爲時間間隔均勻的子集的算法

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分解（或者，如果你覺得奇怪，是週期圖）並在結果頻譜中尋找峯值。這會給你一個控制器週期的粗略近似值，甚至可以給你估計它們的數量（通過查看峯值的高度，它可以告訴你有多少記錄被記錄）。