Contents
やりたいこと
多次元尺度構成法とは多次元のデータを少ない次元で表現する方法。データ間の距離の関係だけを見て決める。 この多次元尺度構成法のデモを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 = Point2DPoint2D = 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 5Multi-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 = DataPointDataPoint = 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 = PointCloudPointCloud = 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 10main
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実行結果
