我正在学习课本中的一个练习,并用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)
中,以及我如何递增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
,从而使平方误差之和最小化。 最佳答案
我无法跟踪您认为您的代码应该如何工作,因此我无法告诉您您犯了什么错误。另外,既然你在努力学习,我会给你一个机会来思考如何去做,而不仅仅是魔术般的代码。
假设您希望使用自底向上的方法,一种方法是填写下表(最好以数组数组的形式填写,但我将以字典的形式填写以便于阅读):
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/