Notes

import numpy as np
import random as rnd
import matplotlib.pyplot as plt
from matplotlib import cm
import numpy as np
import math
rnd.seed(1)


def gen_rnd_pts(num):
pts=[]
for _ in range(num):
while 1:
x=rnd.randint(0,180)
y=rnd.randint(0,180)
if (x,y) not in pts:
pts.append((x,y))
break
return pts


def kmeans(pts):
center_pts=rnd.sample(pts,math.sqrt(len(pts)/2))
belong_to=[]
for p in pts:
mindist_idx=-1
for i,c in enumerate(center_pts):
dist_sq=(c[0]-p[0])**2+(c[1]-p[1])**2
if mindist_idx==-1 or dist_sq<(center_pts[mindist_idx][0]-p[0])**2+(center_pts[mindist_idx][1]-p[1])**2:
mindist_idx=i
belong_to.append(mindist_idx)
return center_pts,belong_to


def group_by_closest_to_centers(pts,center_pts):
belong_to=[]
for p in pts:
mindist_idx=-1
for i,c in enumerate(center_pts):
dist_sq=(c[0]-p[0])**2+(c[1]-p[1])**2
if mindist_idx==-1 or dist_sq<(center_pts[mindist_idx][0]-p[0])**2+(center_pts[mindist_idx][1]-p[1])**2:
mindist_idx=i
belong_to.append(mindist_idx)
return belong_to

def get_new_centers(pts,belong_to):
maxidx=max(belong_to)
pts_in_cluster=[None for _ in range(maxidx+1)]
new_center=[None for _ in range(maxidx+1)]
for cluster_idx in range(maxidx+1):
pts_in_cluster[cluster_idx]=[pts[i] for i in range(len(pts)) if belong_to[i]==cluster_idx]
new_center[cluster_idx]=[0,0]
for pt in pts_in_cluster[cluster_idx]:
new_center[cluster_idx][0]+=pt[0]
new_center[cluster_idx][1]+=pt[1]
new_center[cluster_idx][0]*=1./(len(pts_in_cluster[cluster_idx]))
new_center[cluster_idx][1]*=1./(len(pts_in_cluster[cluster_idx]))
return new_center

def point_with_max_distance(pts,last_pts):
max_dist_index=-1
max_dist=0
for i,pt in enumerate(pts):
#print pt
#print last_pts
dist=sum(math.sqrt( (p[0]-pt[0])**2 + (p[1]-pt[1])**2 ) for p in last_pts )
if max_dist_index==-1 or dist>max_dist:
max_dist_index=i
max_dist=dist
return pts[max_dist_index]



def kmeans2(pts,refine=0):
ret_val=[]
num_clusters=int(math.floor(math.sqrt(len(pts)/2)+0.5))
print "num_clusters",num_clusters

#center_pts=rnd.sample(pts,num_clusters)
center_pts=rnd.sample(pts,1)
while len(center_pts)<num_clusters:
next_pt=point_with_max_distance(pts,center_pts)
center_pts.append(next_pt)


#for pt in pts:


belong_to=group_by_closest_to_centers(pts,center_pts)
ret_val.append((center_pts,belong_to))
#print "belong_to",belong_to
for i in range(refine):
print "iter",i
center_pts=get_new_centers(pts,belong_to)
belong_to=group_by_closest_to_centers(pts,center_pts)
ret_val.append((center_pts,belong_to))
#print "belong_to iter %d"%i,belong_to
#center_pts=get_new_centers(pts,belong_to)
return ret_val
"""
new_center_pts=[]
new_center=[]
for cluster_idx in range(len(num_clusters)):
new_center_pts[cluster_idx]=[pts[i] for i in range(len(pts)) if belong_to[i]==cluster_idx]
new_center[cluster_idx]=(0,0)
for pt in new_center_pts[cluster_idx]:
new_center[cluster_idx][0]+=pt[0]
new_center[cluster_idx][1]+=pt[1]
return center_pts,belong_to
"""


def main():
pts=gen_rnd_pts(200)

#20 1 refinments
#20 5 refinments
#

plotidx=441
kms=kmeans2(pts,5)
print "done"
print "l",len(kms)
for i in range(5):
km=kms[i]
idx=i

center_points=km[0]
ax = plt.subplot(3,3,idx+1,axisbg='black')
#plt.title("idx %d"%idx)
x = [p[0] for p in pts]
y = [p[1] for p in pts]
z = [idx for idx in km[1]]
#print "z",z
ax.scatter(x,y,c=z, marker = 's',cmap="RdYlGn" )

x=[c[0] for c in center_points]
y=[c[1] for c in center_points]
z=[idx for idx,_ in enumerate(center_points)]
#print "z",z
ax.scatter(x,y,c=z, marker = '+',cmap="RdYlGn")
#for i,c in enumerate(center_points):
#ax.scatter([c[0]],[c[1]],c=[i], marker = 'o', cmap = cm.hot )
print "drawing",i
"""
km=kmeans2(pts,5)
ax = plt.subplot(222,axisbg='white')
x = [p[0] for p in pts]
y = [p[1] for p in pts]
z = [idx for idx in km[1]]
ax.scatter(x,y,c=z, marker = 's', cmap = cm.hot, );

km=kmeans2(pts,5)
ax = plt.subplot(223,axisbg='white')
x = [p[0] for p in pts]
y = [p[1] for p in pts]
z = [idx for idx in km[1]]
ax.scatter(x,y,c=z, marker = 's', cmap = cm.hot, );
"""
plt.show()

main()