k-means （python）算法

# liukaiyi   
# 注 k-means ，维度类型 - 数值形式 ( 199 或 23.13 ) 
import  sys, math, random

#  -- 类化 '数据' 
#  在 n-维度空间
class  Point:
     def   __init__ (self, coords, reference = None):
        self.coords  =  coords
        self.n  =  len(coords)
        self.reference  =  reference
     def   __repr__ (self):
         return  str(self.coords)

#  -- 类化 '聚集点 / 聚类平均距离 点 ' 
#  -- 在 n-维度空间
#  -- k-means 核心类
#  -- 每次 聚集各点 围绕她 进行聚集 
#  -- 并提供方法 求-聚集后的计算中心点，同时记入 此次 中心点(聚集各点平均距离)，为下一次聚集提供中心点.
class  Cluster:
     def   __init__ (self, points):
         if  len(points)  ==  0:  raise  Exception( " ILLEGAL: EMPTY CLUSTER " )
        self.points  =  points
        self.n  =  points[0].n
     for  p  in  points:
             if  p.n  !=  self.n:  raise  Exception( " ILLEGAL: MULTISPACE CLUSTER " )
         #  求 聚集各点后 平均点
    self.centroid  =  self.calculateCentroid()
     def   __repr__ (self):
         return  str(self.points)
    
     #  更新 中心点，并返回 原中心点 与 现中心点(聚集各点平均距离)距离  
     def  update(self, points):
        old_centroid  =  self.centroid
        self.points  =  points
        self.centroid  =  self.calculateCentroid()
         return  getDistance(old_centroid, self.centroid)
    
     #  计算平均点 （聚集/收集各点（离本类的中心点）最近数据,后生成新的 中心点 ）
     def  calculateCentroid(self):
        centroid_coords  =  []
         #   维度 迭代
     for  i  in  range(self.n):
            centroid_coords.append( 0.0 )
             #  收集各点 迭代 
         for  p  in  self.points:
                centroid_coords[i]  =  centroid_coords[i] + p.coords[i]
            centroid_coords[i]  =  centroid_coords[i] / len(self.points)
         return  Point(centroid_coords)

#  -- 返回根据 k-means 聚集形成的 数据集 
def  kmeans(points, k, cutoff):
     #  Randomly sample k Points from the points list, build Clusters around them
    initial  =  random.sample(points, k)
    clusters  =  []
     for  p  in  initial: clusters.append(Cluster([p]))
     #  迭代 k-means 直到 每次迭代 各收集点 别的 最多 不超过 0.5 
     while  True:
         #   k 个收集 数组
        lists  =  []
         for  c  in  clusters: lists.append([])
     #  迭代 每个 数据点 ，并计算与每个中心点距离
     #  并把数据点添加入相应最短的中心点收集数组中
     #  在迭代中 smallest_distance 为每个点与各中心点最短距离 参数，请注意看
         for  p  in  points:
            smallest_distance  =  getDistance(p, clusters[0].centroid)
            index  =  0
             for  i  in  range(len(clusters[ 1 :])):
                distance  =  getDistance(p, clusters[i + 1 ].centroid)
                 if  distance  <  smallest_distance:
                    smallest_distance  =  distance
                    index  =  i + 1
             #  添加到 离最短中心距离的 数组中
        lists[index].append(p)
    
         #  聚集完，计算新 中心点
     #  并 cluster.centroid 属性记入下 新中心点（下一次 聚集的中心点 ）
     #  并 计算与上一次 中心点 距离 ，如果 差值在 cutoff 0.5 以下 ,跳出迭代 （结束，返回最后一次 聚集集合）
    biggest_shift  =   0.0
         for  i  in  range(len(clusters)):
            shift  =  clusters[i].update(lists[i])
            biggest_shift  =  max(biggest_shift, shift)
         if  biggest_shift  <  cutoff:  break
     return  clusters


#  -- 得到欧几里德距离两点之间 
def  getDistance(a, b):
     #  Forbid measurements between Points in different spaces
     if  a.n  !=  b.n:  raise  Exception( " ILLEGAL: NON-COMPARABLE POINTS " )
     #  Euclidean distance between a and b is sqrt(sum((a[i]-b[i])^2) for all i)
    ret  =   0.0
     for  i  in  range(a.n):
        ret  =  ret + pow((a.coords[i] - b.coords[i]),  2 )
     return  math.sqrt(ret)

#  -- 在 n-维度 空间中创建 随机点
#  -- 随机生成 测试数据
def  makeRandomPoint(n, lower, upper):
    coords  =  []
     for  i  in  range(n): coords.append(random.uniform(lower, upper))
     return  Point(coords)

#  main 
def  main(args):
     #  参数说明
     #  num_points,    n,    k,      cutoff,         lower,        upper 
     #  随机数据数量 , 维度, 聚集数, 跳出迭代最小距离 ,   维度数最大值,维度数最小值
    num_points, n, k, cutoff, lower, upper  =   10 ,  2 ,  3 ,  0.5 ,  - 200 ,  200

     #  在 n-维度空间里 , 创建 num_points 随机点
     #  测试数据生成 
    points  =  []
     for  i  in  range(num_points): points.append(makeRandomPoint(n, lower, upper))

     #  使用 k-means 算法，来 聚集数据点 (算法入口点)
    clusters  =  kmeans(points, k, cutoff)

     print   " \nPOINTS: "
     for  p  in  points:  print   " P: " , p
     print   " \nCLUSTERS: "
     for  c  in  clusters:  print   " C: " , c
if   __name__   ==   " __main__ " : main(sys.argv)