多维缩放
参考：
http://book.51cto.com/art/200812/103661.htm
《集体智慧编程》
多维缩放是一种可视化的数据表达方式，现实生活中数据远超2维，多维缩放可以为数据集找到一种二维表达形式。算法根据每对数据项之间的差距情况，尝试绘制出一幅图来，图中的各数据项之间的距离远近，对应于它们彼此间的差异程度。
步骤：
（1）计算所有数据项之间的目标距离，即所有项两两之间的实际距离作为目标距离。距离的度量可采用欧氏距离或皮尔逊距离等。
例：有一个如表所示的4维数据集（每一项数据有4个相关的值）
一个待缩放的简单的4维表格
|
A |
0.5 |
0.0 |
0.3 |
0.1 |
|
B |
0.4 |
0.15 |
0.2 |
0.1 |
|
C |
0.2 |
0.4 |
0.7 |
0.8 |
|
D |
1.0 |
0.3 |
0.6 |
0.0 |
利用欧几里德距离公式，我们可以得到每两项间的距离值。所有数据项两两之间的距离矩阵如下表所示。
上述示例的距离矩阵
|
|
A |
B |
C |
D |
|
A |
0.0 |
0.2 |
0.9 |
0.8 |
|
B |
0.2 |
0.0 |
0.9 |
0.7 |
|
C |
0.9 |
0.9 |
0.0 |
1.1 |
|
D |
0.8 |
0.7 |
1.1 |
0.0 |
（2）将数据项随机放置在二维图上。所有数据项两两之间的当前距离是随机放置在二维图后的实际测量距离。（即当前随机距离）
（3）针对每两两构成的一对数据项，将它们的实际距离与当前在二维图上的距离进行比较，求出一个误差值
（4）根据误差的情况，按照比例将每个数据项的所在位置移近或移远少许量。每一个节点的移动，都是所有其它节点施加在该节点上的推或拉的结合效应。节点每移动一次，其当前距离和目标距离之间的差距就会减少一些。
（5）重复第三步、第四步。这一过程会不断地重复多次，直到无法再通过移动节点来减少总体误差为止。
输入与输出：实现这一功能的函数接受一个数据向量作为参数，并返回一个只包含两列的向量，即数据项在二维图上的X坐标和Y坐标。
例：输入
trainset=[[0.5,0.0,0.3,0.1],
[0.4,0.15,0.2,0.1],
[0.2,0.4,0.7,0.8],
[1.0,0.3,0.6,0.0]]
输出为（距离度量采用皮尔逊度量）：
[[0.069, 0.638],
[-0.028, 0.679],
[1.581, 0.191],
[-0.045, 0.639]]
在缩放过程中一些信息可能会丢失掉，但是缩放后的结果会更加有助于我们理解算法的原理。
实现此功能的python代码：
def scaledown(data,distance=pearson,rate=0.01):
n=len(data)
# The real distances between every pair of items
realdist=[[distance(data[i],data[j]) for j in range(n)]
for i in range(0,n)]
# Randomly initialize the starting points of the locations in 2D
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,1000):
# Find projected distances
for i in range(n):
for j in range(n):
fakedist[i][j]=sqrt(sum([pow(loc[i][x]-loc[j][x],2)
for x in range(len(loc[i]))]))
# 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
# The error is percent difference between the distances
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
# Keep track of the total error
totalerror+=abs(errorterm)
print totalerror
# If the answer got worse by moving the points, we are done
if lasterror and lasterror<totalerror: break
lasterror=totalerror
# Move each of the points by the learning rate times the gradient
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',(2000,2000),(255,255,255))
draw=ImageDraw.Draw(img)
for i in range(len(data)):
x=(data[i][0]+0.5)*1000
y=(data[i][1]+0.5)*1000
draw.text((x,y),labels[i],(0,0,0))
img.save(jpeg,'JPEG')
if __name__ == '__main__':
blognames,words,data = readfile('blogdata.txt')
coords = scaledown(data)
draw2d(coords,blognames,jpeg='blogs2d.jpg')
绘制结果如下图所示：
