基于时间的聚类推荐算法

Question

4

我对基于时间的聚类不是很了解，想知道是否有算法适用于我的使用情况。

我有一组运动数据（范围从0到500），我想将它们在时间间隔内进行聚类。

我的问题是我想找出在时间间隔内存在主要运动差异的时间点。我将确切地知道应该有多少个分组（例如5个单独的集群），但不知道一个集群何时结束，下一个集群何时开始。

这种情况下是否有好的算法可供应用？我看了K-Means，但它似乎非常擅长忽略时间进行聚类，我更多地关注运动数据的边界。

- mornindew

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

我认为使用动态程序可以获得很好的结果。对于每个区间[i，j)，让C（i，j）成为损失函数，当区间值更可能是一个簇时，它会更低。然后让L（k，r）为元素[0，r)的最多k簇的最小损失，我们有以下方程式。

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).

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

对于C(i,j)，一个合理的第一选择是该区间样本的统计方差。朴素地，每个区间的计算需要Theta(n^3)时间，但是可以使用Welford's algorithm在线计算方差，如果你将s从最大值迭代到最小值，则整体算法仍然是O(n^2)。