基于时间的聚类推荐算法

我认为你可以从动态程序中得到好的结果。每次间隔 [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).

如果有的话 O(1) 价值观 需要,用记忆法计算这些方程 O(n^2) 时间和 O(n) 空间 n 是样本数。

一个合理的第一选择 C(i,j) 将是该区间内样本的统计方差。天真地说,这需要 Theta(n^3) 计算每个间隔的时间,但是 Welford's algorithm 可用于在迭代时在线计算方差 s O(n^2) .