转: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 = 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)
整理 www.blogjava.net/Good-Game
|