python实现数据的多维缩放(集体智慧编程)

bingtuag

　　多维缩放可以为数据集找到一种二维表达形式。算法根据每对数据项之间的差距情况，尝试绘制出一幅图来，图中的各数据项之间的距离远近，对应于它们彼此间的差异程度。
　　以分类聚集算法中的数据为例
　　第一步：计算所有数据项两两间的实际距离（可参考皮尔逊算法或欧几里德算法）
　　第二步：将数据项随机放置在二维图上。
　　第三步：针对每两两构成的一对数据项，将它们的实际距离与当前在二维图上的距离进行比较，求出一个误差值
　　第四步：根据误差的情况，按照比例将每个数据项的所在位置移近或移远少许量。（每一个节点的移动，都是所有其它节点施加在该节点上的推或拉的结合效应。）
　　第五步：重复第三步、第四步（节点每移动一次，其当前距离与实际距离的差距就会减少一些）。这一过程会不断地重复多次，直到无法再通过移动节点来减少总体误差为止。
　　下面我们用PYTHON来实现此算法：

def scaledown(data, distance=pearson, rate=0.01):
n = len(data)
print n
# 每一对数据项的真实距离
realdist = [[distance(data, data[j]) for j in range(n)]
for i in range(0, n)]
# 生成随机的二维LIST，表示各数据项在二维空间的初始坐标
loc = [[random.random(), random.random()] for i in range(n)]
fakedist = [[0.0 for j in range(n)] for i in range(n)]
lasterror = None
for m in range(0, 100000):
# 计算各数据项初始坐标的距离
for i in range(n):
for j in range(n):
fakedist[j] = sqrt(sum([pow(loc[x] - loc[j][x], 2) for x in range(len(loc))]))
# Move points
grad = [[0.0, 0.0] for i in range(n)]
totalerror = 0
for k in range(n):
for j in range(n):
if j == k:
continue
# 计算误差的比例
errorterm = (fakedist[j][k] - realdist[j][k]) / realdist[j][k]
# Each point needs to be moved away from or towards the other
# point in proportion to how much error it has
grad[k][0] += (
(loc[k][0] - loc[j][0]) / fakedist[j][k]) * errorterm
grad[k][1] += (
(loc[k][1] - loc[j][1]) / fakedist[j][k]) * errorterm
# 求得所有数据项的误差和
totalerror += abs(errorterm)
# 如果移动后，误差变得更大，则结束
if lasterror and lasterror < totalerror:
break
lasterror = totalerror
# 移动节点
for k in range(n):
loc[k][0] -= rate * grad[k][0]
loc[k][1] -= rate * grad[k][1]
return loc
//作图的方法
def draw2d(data, labels, jpeg='mds2d.jpg'):
img = Image.new('RGB', (1000, 1000), (255, 255, 255))
draw = ImageDraw.Draw(img)
#设置字体类型与大小
font = ImageFont.truetype('simsun.ttc', 24)
for i in range(len(data)):
x = (data[0] + 0.5) * 500
y = (data[1] + 0.5) * 500
#此处注意编码
draw.text((x, y), unicode(labels, 'utf-8'), (0, 0, 0), font=font)
img.save(jpeg, 'JPEG')
　　利用之前算法已得的数据进行测试下：

#encoding=utf-8
import clusters
blognames,words,data = clusters.readfile('blogdata1.txt')
coords = clusters.scaledown(data)
clusters.draw2d(coords,blognames)
　　得到图：