Python序列集群练习

Question

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

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

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

例如：给定 x= [7,6,9,15,18,17,30,28,29] 和 k=3，我们将 return 聚类 (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 划分为大小 n_1, ..., n_k 的簇 C_1,..., C_k，因此误差平方和为最小化。

Answer 1

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

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

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},
        },
}

下面是如何解释 table。

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]（最好的 1 个簇在位置 0 结束），它给了我们最后一个 [52].

的簇

所以弄清楚如何编写代码来填写 table，然后是从 table 中提取答案的代码，你就会有一个自下而上的动态规划解决方案.

至于填写，例如，要填写 best_cluster_by_pos_by_clusters[3][1] 我必须做的是查看 best_cluster_by_pos_by_clusters[i][0] for i=0, 1, 2 以查看前一个集群的每个分区与当前版本相比。

Python序列集群练习

Python sequence cluster exercise

python

algorithm

cluster-analysis

dynamic-programming