Skynet

---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks

转:http://www.daniweb.com/forums/thread31449.html
什么都不说了,直接看代码吧。
注解 应该写的比较详细


# 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 = 10230.5-200200

    
# 在 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)



整理 www.blogjava.net/Good-Game
posted on 2009-08-07 16:20 刘凯毅 阅读(2033) 评论(0)  编辑  收藏 所属分类: python算法/函数

只有注册用户登录后才能发表评论。


网站导航: