ズッキーニのプログラミング実験場

プログラミング + アカデミック + 何か面白いこと。 記載されているものは基本的に私が所属する団体とは関係がありません。

   Jun 13

[CoffeeScript]多次元尺度構成法

by zuqqhi2 at 2013年6月13日
Pocket

やりたいこと

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

この多次元尺度構成法のデモを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

実行結果

mds-result

Related Posts

Pocket

You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.