基于时间聚类的推荐算法

Question

我对基于时间的集群并不是很了解，我想知道是否有任何算法适合我的用例。

我有一组消耗数据(范围从0到500)，我想沿着时间间隔对它们进行聚类。

我的问题是，我想找出在时间间隔上存在主要努力差异的时间点。我会确切地知道他们应该有多少个分组(例如5个独立的集群)，但不知道一个集群在哪里结束，下一个集群从哪里开始。

在这种情况下有没有好的算法？我在看K-Means，但它似乎在不考虑时间的情况下非常擅长聚类，我更多地是在寻找边界，查看消耗数据。

Answer 1

我认为你可以从一个动态程序中得到很好的结果。对于每个间隔[i, j)，假设C(i, j)是一个损失函数，当间隔值更有可能是一个簇时，该损失函数更低。然后，将L(k, r)设为最多k个元素簇[0, r)的最小损失，我们得到以下公式

L(1, r) = C(0, r)
L(k, r), k > 1 = min over s in [0, r) of L(k-1, s) + C(s, r).

如果需要k的O(1)值，则使用记忆法计算这些方程需要O(n^2)时间和O(n)空间，其中n是样本数。

C(i, j)的一个看似合理的首选是该区间内样本的统计方差。很简单，这需要Theta(n^3)时间来计算每个间隔，但是如果您从s的最大值迭代到最小值，则可以使用Welford's algorithm在线计算方差，因此整体算法仍然是O(n^2)。