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

多维缩放可以为数据集找到一种二维表达形式。算法根据每对数据项之间的差距情况，尝试绘制出一幅图来，图中的各数据项之间的距离远近，对应于它们彼此间的差异程度。

 

以分类聚集算法中的数据为例

第一步：计算所有数据项两两间的实际距离（可参考皮尔逊算法或欧几里德算法）

第二步：将数据项随机放置在二维图上。

第三步：针对每两两构成的一对数据项，将它们的实际距离与当前在二维图上的距离进行比较，求出一个误差值

第四步：根据误差的情况，按照比例将每个数据项的所在位置移近或移远少许量。（每一个节点的移动，都是所有其它节点施加在该节点上的推或拉的结合效应。）

第五步：重复第三步、第四步（节点每移动一次，其当前距离与实际距离的差距就会减少一些）。这一过程会不断地重复多次，直到无法再通过移动节点来减少总体误差为止。

 

 

下面我们用PYTHON来实现此算法：

 

def scaledown(data, distance=pearson, rate=0.01):
    n = len(data)
    print n
    # 每一对数据项的真实距离
    realdist = [[distance(data[i], 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[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
                # 计算误差的比例
                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[i][0] + 0.5) * 500
        y = (data[i][1] + 0.5) * 500
        #此处注意编码
        draw.text((x, y), unicode(labels[i], '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)

 

 

得到图：