プログラミング + アカデミック + 何か面白いこと

  1. Academic
  2. 16 view

[CoffeeScript]Multi-Dimesional-Scaling

What I want to do

Multi-Dimension-Scaling is how to explain high dimension data as low dimension data.
This method focus on distances between data.

Try to implement MDS’s demo with cofee script.

Source Code

Model

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

実行結果

mds-result

Academic recent post

  1. [Just Touch]Microsoft Quantum Development Kit…

  2. Visualization of Neural Network and its Train…

  3. [Machine Learning]Created docker image includ…

  4. [OpenCV][Ruby]Auto check web page design corr…

  5. [MachineLearning]How to introduce to real pro…

関連記事

PAGE TOP