我对基于时间的聚类不是很了解,想知道是否有算法适用于我的使用情况。
我有一组运动数据(范围从0到500),我想将它们在时间间隔内进行聚类。
我的问题是我想找出在时间间隔内存在主要运动差异的时间点。我将确切地知道应该有多少个分组(例如5个单独的集群),但不知道一个集群何时结束,下一个集群何时开始。
这种情况下是否有好的算法可供应用?我看了K-Means,但它似乎非常擅长忽略时间进行聚类,我更多地关注运动数据的边界。
我对基于时间的聚类不是很了解,想知道是否有算法适用于我的使用情况。
我有一组运动数据(范围从0到500),我想将它们在时间间隔内进行聚类。
我的问题是我想找出在时间间隔内存在主要运动差异的时间点。我将确切地知道应该有多少个分组(例如5个单独的集群),但不知道一个集群何时结束,下一个集群何时开始。
这种情况下是否有好的算法可供应用?我看了K-Means,但它似乎非常擅长忽略时间进行聚类,我更多地关注运动数据的边界。
[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)
。