I am working through an exercise in my textbook and implementing the code in Python to practice dynamic programming. I feel like I am right on the edge of figuring it out, but after many hours, I come here for help.
Basically, my code is going through a list of values x
, and given a k
, breaks that list into k
clusters based on calculating the minimum sum of squared errors (SSE) for a particular cluster.
The code creates a table, calculating the SSE for 1 cluster, 2 clusters, ..., k clusters, if we were to put the cluster parentheses around all variations of values within list[0:1]
, list[0:2]
, list[0:3]
, ..., list[0:n]
, and choosing the minimum SSE for that particular step in the table.
For example:
Given x= [7,6,9,15,18,17,30,28,29]
and k=3
we would return clusters (7,6,9)(15,18,17)(30,28,29)
, which would translate to sum of squared error equal to (4.666)(4.666)(2)
for each cluster. So our max SSE would be 4.666
for that clustering on that list.
Now when I try it on my second list x = [52, 101, 103, 101, 6, 5, 7]
, I should get clustering (52)(101, 103, 101)(6, 5, 7)
, which should give (0)(2.666)(2)
or a max of 2.666
, but am not getting that. I believe the error lives in the def f(s, j_down, t)
for the 2nd return statement, and how I increment s
and t
. Hopefully, I have not made a silly mistake!
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)
Edit: Question layout
Given a sequence X = [x_1, x_2, ... x_n]
and integer k > 1
, partition X
into clusters C_1,..., C_k
of sizes n_1, ..., n_k
, so that the sum of squared errors is minimized.