Python序列聚类练习

Question

我正在完成课本中的练习，并用 Python 实现代码以练习动态编程。我觉得我快要弄清楚了，但几个小时后，我来这里寻求帮助。

基本上，我的代码会遍历一个值列表 x，并给定一个 k，根据计算将该列表分成 k 个簇特定集群的最小平方误差和 (SSE)。

代码创建一个表，计算 1 个集群、2 个集群、...、k 个集群的 SSE，如果我们要将集群括号放在 list[0:1]< 中的所有值变体周围, list[0:2], list[0:3], ..., list[0:n],并为表中的特定步骤选择最小 SSE。

例如:给定 x= [7,6,9,15,18,17,30,28,29] 和 k=3，我们将返回集群 (7,6,9)(15,18,17)(30,28,29)，这将转化为等于 (4.666)(4.666)( 2) 对于每个集群。因此，对于该列表中的集群，我们的最大 SSE 将为 4.666。

现在当我在第二个列表 x = [52, 101, 103, 101, 6, 5, 7] 上尝试时，我应该得到聚类 (52)(101, 103, 101)(6, 5, 7)，它应该给出 (0)(2.666)(2) 或最大值 2.666，但是我没有得到那个。我相信错误存在于第二个 return 语句的 def f(s, j_down, t) 中，以及我如何递增 s 和 t .希望我没有犯一个愚蠢的错误!

非常感谢任何帮助，谢谢。

def mean(numbers):
    return float(sum(numbers)) / max(len(numbers), 1)

def sum_square(x):
    if isinstance(x, (int,)):
        return 0
    w = 0
    for i in x:
        w += (i - mean(x))**2
    return w

def f(s, j_down, t):
    if not r[s][j_down] and r[s][j_down] != 0:
        return sum_square(x[:t - s])

    return max(r[s][j_down], sum_square(x[:t-s]))

def get_min_f_and_s(j_down, t):
    """ range s from 1 to t-1 and set s to minimize f(s)
    """
    items = [(s, f(s, j_down, t)) for s in range(t)]
    s, min_f = min(items, key=lambda x:x[1])
    return s, min_f

def seq_out(n,k):
    for j in range(k):
        if j == 0:
            for t in range(n):
                r[t][j] = sum_square(x[:t+1])

                c[t][j] = x[:t+1]
        else:
            for t in range(1, n):
                s, min_f = get_min_f_and_s(j - 1, t)
                r[t][j] = min_f
                c[t][j] = [c[s][j - 1]] + x[s+1:t+1]

    print('the max SSE is: {}'.format(r[-1][-1]))
    print('the cluster centers are: {}'.format(c[-1][-1]))

#x = [7,6,9,15,18,17,30,28,29]    
x = [52, 101, 103, 101, 6, 5, 7]
k = 3
n = len(x)

r = [[[] for _ in range(k)] for _ in range(n)]
c = [[[] for _ in range(k)] for _ in range(n)]

print(seq_out(n,k))
print(r)
print(c)

编辑:问题布局

给定序列 X = [x_1, x_2, ... x_n] 和整数 k > 1，将 X 划分为簇 C_1,..., C_k 的大小为 n_1, ..., n_k，以便误差平方和最小。

Answer 1

我无法追踪您认为您的代码应该如何工作，因此我无法告诉您您犯了什么错误。此外，由于您正在努力学习，我会为您提供思考如何去做的机会，而不仅仅是魔术般出现的代码。

假设您想要采用自下而上的方法，一种方法是填写下表(最好将其作为数组的数组来完成，但我将作为词典的字典来填写，以使其更易于阅读):

best_cluster_by_pos_by_clusters = {
    0: {
        1: {'start': 0, 'error': 0.0, 'max_error': 0.0}
        },
    1: {
        1: {'start': 0, 'error': 1200.5, 'max_error': 1200.5},
        2: {'start': 1, 'error': 0.0, 'max_error': 0.0},
        }, 
    2: {
        1: {'start': 0, 'error': 1668.6666666666667, 'max_error': 1668.6666666666667},
        2: {'start': 1, 'error': 2.0, 'max_error': 2.0},
        3: {'start': 2, 'error': 0.0, 'max_error': 0.0},
        },
    3: {
        1: {'start': 0, 'error': 1852.75, 'max_error': 1852.75},
        2: {'start': 1, 'error': 2.666666666666667, 'max_error': 2.666666666666667},
        3: {'start': 3, 'error': 0.0, 'max_error': 2.0},
        },
    4: {
        1: {'start': 0, 'error': 7397.2, 'max_error': 7397.2},
        2: {'start': 4, 'error': 0.0, 'max_error': 1852.75},
        3: {'start': 4, 'error': 0.0, 'max_error': 2.666666666666667},
        },
    5: {
        1: {'start': 0, 'error': 11205.333333333334, 'max_error': 11205.333333333334},
        2: {'start': 4, 'error': 0.5, 'max_error': 1852.75},
        3: {'start': 4, 'error': 0.5, 'max_error': 2.666666666666667},
        },
    6: {
        1: {'start': 0, 'error': 13735.714285714286, 'max_error': 13735.714285714286},
        2: {'start': 4, 'error': 2.0, 'max_error': 1852.75},
        3: {'start': 4, 'error': 2.0, 'max_error': 2.666666666666667},
        },
}

下面是解释该表的方法。

事实上 best_cluster_by_pos_by_clusters[6][3] 是 {'start': 4, 'error': 2.0, 'max_error': 2.666666666666667} 意味着位置 0-6 的数字的最佳划分是让第三个簇具有位置 4、5、6 的数字。该簇的平方误差为 2.0，最大值为 2.666666666666667。这为您提供了集群 [6, 5, 7] 并找到其余的我们转到 best_cluster_by_pos_by_clusters[3][2](即最好划分为 2 个集群，结束于位置 3)，我们类似地找到集群 [101, 103, 101]。然后我们继续查看 best_cluster_by_pos_by_clusters[0][1](在位置 0 处结束的最佳 1 簇)，它为我们提供了 [52] 的最后一个簇。

因此，弄清楚如何编写代码来填充该表，然后再编写代码从该表中提取答案，您将拥有一个自下而上的动态规划解决方案。

至于填写，例如，要填写 best_cluster_by_pos_by_clusters[3][1] 我要做的是查看 best_cluster_by_pos_by_clusters[i][0] 用于 i=0, 1, 2 以查看先前集群与当前集群的每个分区。