我正在学习课本中的一个练习,并用python实现代码来练习动态编程。我觉得自己正处于解决问题的边缘,但几个小时后,我来到这里寻求帮助。
基本上,我的代码是遍历一个值列表x,并给出一个k,根据计算特定集群的最小平方误差之和(SSE)将该列表分成k个集群。
如果要在list[0:1]list[0:2]list[0:3],…,list[0:n],…,x= [7,6,9,15,18,17,30,28,29]内的所有值变量周围放置簇括号,并为表中的特定步骤选择最小的SSE,则代码将创建一个表,计算1个簇,2个簇,…,k个簇的SSE。
例如:给定k=3(7,6,9)(15,18,17)(30,28,29),我们将返回集群(4.666)(4.666)(2),它将转换为每个集群的平方误差之和,等于4.666。因此,对于该列表上的集群,我们的最大sse将x = [52, 101, 103, 101, 6, 5, 7]
现在,当我在第二个列表中尝试它时,我应该得到clustering(52)(101, 103, 101)(6, 5, 7),它应该给出(0)(2.666)(2)或最大值2.666,但没有得到。我相信错误存在于第二个return语句的def f(s, j_down, t)中,以及我如何递增st。希望我没有犯一个愚蠢的错误!
非常感谢您的帮助,谢谢。

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,从而使平方误差之和最小化。

最佳答案

我无法跟踪您认为您的代码应该如何工作,因此我无法告诉您您犯了什么错误。另外,既然你在努力学习,我会给你一个机会来思考如何去做,而不仅仅是魔术般的代码。
假设您希望使用自底向上的方法,一种方法是填写下表(最好以数组数组的形式填写,但我将以字典的形式填写以便于阅读):

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.66666666667这就给了你聚类[6, 5, 7]并且要找到其余的,我们转到best_cluster_by_pos_by_clusters[3][2](也就是说,最好分割成两个以位置3结尾的聚类),我们同样也找到了聚类[101, 103, 101]然后我们继续观察best_cluster_by_pos_by_clusters[0][1](最好的1个簇结束于位置0),这给了我们最后一个[52]簇。
因此,找出如何编写代码来填充该表,然后从该表中提取答案的代码,您将得到一个自下而上的动态编程解决方案。
至于填充,举个例子,填充best_cluster_by_pos_by_clusters[3][1]我要做的是查看best_cluster_by_pos_by_clusters[i][0]i=0, 1, 2以查看前一个集群与当前集群的每个分区。

关于python - Python序列聚类练习,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/55190965/

10-11 17:53