やりたいこと

多次元尺度構成法とは多次元のデータを少ない次元で表現する方法。
データ間の距離の関係だけを見て決める。 この多次元尺度構成法のデモをcoffee scriptで実装してみる。

ソースコード

モデル

class Point2D
    constructor: (x, y, r, vx, vy, label, wnd_width, wnd_height, context) ->
        @x = x
        @y = y
        @r = r
        @vx = vx
        @vy = vy
        @label = label
        @wnd_width = wnd_width
        @wnd_height = wnd_height
        @context = context

    #
    # Update poistion with velocity
    #
    update_position: ->
        @x += @vx
        @y += @vy

    #
    # Return x and y with array style
    #
    get_data: ->
        return [@x, @y]

    #
    # Calculate distance between points
    # @param p : Point2D class's instance
    #
    calc_distance: (p)->
        return Math.pow(@x - p.x, 2)+ Math.pow(@y - p.y, 2)

    #
    # Draw point and label to canvas
    #
    draw: ->
        @context.beginPath()
        @context.strokeStyle = '#00F'
        @context.fillStyle = 'green'
        @context.arc(@x, @y, @r, 0, Math.PI * 2, false)
        @context.fill()
        @context.stroke()
        @context.restore()

        @context.beginPath()
        @context.font = "18px 'MS Pゴシック'"
        @context.fillStyle = "red"
        @context.fillText(@label, @x, @y-(@r*2))
        @context.restore()

    #
    # Draw point and label with scaling
    #
    draw_with_scaling: (max,min) ->
        prevX = @x
        prevY = @y

        @x = (@x - min[0]) / (max[0] - min[0]) * @wnd_width
        @y = (@y - min[1]) / (max[1] - min[1]) * @wnd_height

        @draw()

        @x = prevX
        @y = prevY

exports.Point2D = Point2D

Point2D = require('../src/point2d').Point2D

describe "Point2D", ->
    p1 = undefined
    p2 = undefined
    p3 = undefined
    p4 = undefined
    p5 = undefined

    beforeEach ->
        p1 = new Point2D(0, 0, 0, 0, 0, "", 0, 0, undefined)
        p2 = new Point2D(100, 200, 30, 2.0, 2.0, "test", 640, 480, undefined)
        p3 = new Point2D(100, 200, 30, 2.0, 2.0, "test", 640, 480, undefined)
        p4 = new Point2D(1, 2, 30, 2.0, 2.0, "test", 640, 480, undefined)
        p5 = new Point2D(2, 4, 30, 2.0, 2.0, "test", 640, 480, undefined)

    it "should be x and y axis value are 0", ->
        expect(p1.x).toEqual 0
        expect(p1.y).toEqual 0
        expect(p1.r).toEqual 0
        expect(p1.vx).toEqual 0
        expect(p1.vy).toEqual 0
        expect(p1.wnd_width).toEqual 0
        expect(p1.wnd_height).toEqual 0
        expect(p1.label).toEqual ""

    it "should be x and y axis value are 5, 10", ->
        expect(p2.x).toEqual 100
        expect(p2.y).toEqual 200
        expect(p2.r).toEqual 30
        expect(p2.vx).toEqual 2.0
        expect(p2.vy).toEqual 2.0
        expect(p2.wnd_width).toEqual 640
        expect(p2.wnd_height).toEqual 480
        expect(p2.label).toEqual "test"

    it "should add velocity for x and y to 102.0 and 202.0", ->
        p2.update_position()
        expect(p2.x).toEqual 102.0
        expect(p2.y).toEqual 202.0

    it "should get x and y value with array style", ->
        data = p3.get_data()
        expect(data[0]).toEqual 100.0
        expect(data[1]).toEqual 200.0

    it "should get 5 as distance", ->
        expect(p4.calc_distance(p5)).toEqual 5

Multi-Dimension Data

class DataPoint
    constructor: (data, label, column_name) ->
        @data = data
        @label = label
        @column_name = column_name

    #
    # Calculate distance between two points
    # @param  dp : DataPoint's instance
    #
    calc_distance: (dp) ->
        sum = 0.0
        for i in [0..@data.length-1]
            sum += Math.pow(@data[i] - dp.data[i],2)

        return Math.sqrt(sum)

    get_data: ->
        return @data

    draw: ->
        return

    draw_with_scaling: ->
        return

exports.DataPoint = DataPoint

DataPoint = require('../src/datapoint').DataPoint

describe "DataPoint", ->
    p1 = undefined
    p2 = undefined
    p3 = undefined
    p4 = undefined

    beforeEach ->
        column_name = ["a","b","c","d","e"]
        p1 = new DataPoint([1, 2, 3, 4, 5], "test", column_name)
        p2 = new DataPoint([5, 4, 3, 2, 1], "test", column_name)
        p3 = new DataPoint([1, 3, 5, 7, 9], "test", column_name)
        p4 = new DataPoint([3, 5, 2, 4, 6], "test", column_name)

    it "should be x and y axis value are 5, 10", ->
        expect(p1.data[0]).toEqual 1
        expect(p1.data[1]).toEqual 2
        expect(p1.data[2]).toEqual 3
        expect(p1.data[3]).toEqual 4
        expect(p1.data[4]).toEqual 5
        expect(p1.label).toEqual "test"
        expect(p1.column_name[0]).toEqual "a"
        expect(p1.column_name[1]).toEqual "b"
        expect(p1.column_name[2]).toEqual "c"
        expect(p1.column_name[3]).toEqual "d"
        expect(p1.column_name[4]).toEqual "e"

    it "should get x and y value with array style", ->
        data = p2.get_data()
        expect(data[0]).toEqual 5
        expect(data[1]).toEqual 4
        expect(data[2]).toEqual 3
        expect(data[3]).toEqual 2
        expect(data[4]).toEqual 1

    it "should get sqrt(35) as distance", ->
        expect(p3.calc_distance(p4)).toEqual Math.sqrt(35)

Point Cloud Model

class PointCloud
    constructor: (points)->
        @points = points

        @distances = []
        for i in [0..points.length-1]
            @distances.push([])
            for j in [0..points.length-1]
                @distances[i].push(0.0)

    #
    # Calc distances between points and make distance matrix
    #
    calc_distance: ->
        for i in [0..@points.length-1]
            for j in [0..@points.length-1]
                @distances[i][j] = @points[i].calc_distance(@points[j])

    #
    # Draw points
    #
    draw_points: ->
        for i in [0..@points.length-1]
            @points[i].draw()

    #
    # Draw points with scaling
    #
    draw_points_with_scaling: ->
        max = @points[0].get_data()
        min = @points[0].get_data()

        for i in [0..@points.length-1]
            for j in [0..max.length-1]
                if max[j] > @points[i].get_data()[j]
                    max[j] = @points[i].get_data()[j]
                if min[j] < @points[i].get_data()[j]
                    min[j] = @points[i].get_data()[j]

        for i in [0..@points.length-1]
            @points[i].draw_with_scaling(max, min)

exports.PointCloud = PointCloud

PointCloud = require('../src/pointcloud').PointCloud
Point2D = require('../src/point2d').Point2D

describe "PointCloud", ->
    pc = undefined
    points = []

    beforeEach ->
        p1 = new Point2D(1, 2, 30, 2.0, 2.0, "test", 640, 480, undefined)
        p2 = new Point2D(2, 4, 30, 2.0, 2.0, "test", 640, 480, undefined)
        p3 = new Point2D(5, 3, 30, 2.0, 2.0, "test", 640, 480, undefined)
        points.push(p1)
        points.push(p2)
        points.push(p3)
        pc = new PointCloud(points)

    it "should calculate distances", ->
        pc.calc_distance()
        expect(pc.distances[0][0]).toEqual 0
        expect(pc.distances[1][1]).toEqual 0
        expect(pc.distances[2][2]).toEqual 0

        expect(pc.distances[0][1]).toEqual 5
        expect(pc.distances[0][2]).toEqual 17

        expect(pc.distances[1][0]).toEqual 5
        expect(pc.distances[1][2]).toEqual 10

        expect(pc.distances[2][0]).toEqual 17
        expect(pc.distances[2][1]).toEqual 10

main

Point2D = require('../src/point2d').Point2D
DataPoint = require('../src/datapoint').DataPoint
PointCloud = require('../src/pointcloud').PointCloud

main = ()->
    # Draw area
    canvas = document.getElementById('canvas')
    # Canvas interface
    context = canvas.getContext('2d')

    # Make blog name array
    keys = []
    for key of blog_data
        keys.push(key)
    num_points = keys.length

    # Make data point's cloud
    data_points = []
    for i in [0..num_points-1]
        data_points.push(new DataPoint(blog_data[keys[i]], keys[i], column_name))
    realpc = new PointCloud(data_points)

    # Make 2d(for canvas) point's cloud
    points = []
    for i in [0..num_points-1]
        x = canvas.width /2 + Math.floor(Math.random() * 200) - 100
        y = canvas.height /2 + Math.floor(Math.random() * 200) - 100
        vx = 0.0
        vy = 0.0

        points.push new Point2D(x, y, 2, vx, vy, keys[i], canvas.width, canvas.height, context)
    fakepc = new PointCloud(points)
    fakepc.draw_points_with_scaling()

    # Calculate realdist
    realpc.calc_distance()

    # Calculate initial fakedist
    fakepc.calc_distance()

    # Error tmp
    lasterror = 0.0
    # Learning Rate
    rate = 0.0001
    # Done flg of calculation
    endflg = false

    mainloop = ()->
        context.save()
        context.beginPath()
        context.clearRect(0, 0, canvas.width, canvas.height)
        context.restore()

        if endflg
            fakepc.draw_points_with_scaling()
        else
            totalerror = 0

            # Calculate initial fakedist
            fakepc.calc_distance()

            # Calculate velocity of canvas point
            for i in [0..num_points-1]
                for j in [0..num_points-1]
                    if i==j
                        continue

                    errorterm = (fakepc.distances[j][i] - realpc.distances[j][i])/realpc.distances[j][i]

                    points[i].vx += ((points[i].x - points[j].x)/fakepc.distances[j][i])*errorterm
                    points[i].vy += ((points[i].y - points[j].y)/fakepc.distances[j][i])*errorterm

                    totalerror += Math.abs(errorterm)

            # Check local minimum
            console.log(totalerror)
            if lasterror > 1.0 and lasterror < totalerror
                endflg = true
            else
                # Save totalerror
                lasterror = totalerror

                # Update canvas point's position
                for i in [0..num_points-1]
                    points[i].x -= rate * points[i].vx
                    points[i].y -= rate * points[i].vy

                # Draw points
                fakepc.draw_points_with_scaling()

        # Do again after 30 millisecond
        setTimeout(mainloop, 30)

    mainloop()

window.onload = main

実行結果