K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その1 https://t.co/VoMuCoq5sd

JS + canavsの勉強も兼ねて
機械学習とかで使われるk-meansによるクラスタリングを可視化してみた
そしたら、ちょっと気持ち悪い蜘蛛みたいな動きをするようになった#javascript #MachineLearning pic.twitter.com/JnPq5mDSml
— s-yoshiki | スクリプトカス (@s_yoshiki_dev) 2018年7月28日

概要

canavsの勉強も兼ねて、
機械学習とかで使われるk-meansをJavasctiptで実装しアニメーション化した。
動きは下記のデモの通りとなった。

参考

【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その1
【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その2
【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その3

環境

JavaScript
Canvas
※ライブラリ等はなし

デモ

デモ1 | デモ2 | デモ3

※gifはデモ1

実装

index.jsがメインの計算処理を行う。
draw.jsが実際にcanvasに描画を行う。

詳しい説明は【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その1

index.js


(function(){
    //クラスタ数
    var class_n = 9;
    //次元数
    var dim = 2;
    var animationFrame = 9;
    var textArrayMax = 500;
    var range = 256;

    init();

    var arg = {
        "map" : randMat(dim,textArrayMax), //乱数データ
        "n" : class_n, // クラスタ数
        "transaction_max" : 100 //試行回数上限
    };

    try {
        var km = new KMeans(arg);
        var grvArrColor = randMat(3,arg.n,0,256);

        showPoints(arg.map,3,"rgb(0,0,0)");
        for(var i=0;i<km.result.length;i++){
            drawPoint(km.result[i],7,vec2rgb(grvArrColor[i],true));
        }
    } catch (e) {
        alert(e)
    }

    function init() {
        clearCanvas();
        class_n = parseInt(document.getElementById("claster").value,10);
        textArrayMax= parseInt(document.getElementById("node").value,10);
        animationFrame = parseInt(document.getElementById("frame").value,10);
    }

    function KMeans(obj) {
        var ptnMap = obj.map;
        var ptnMapBuffer = new Array(obj.map.length) ;
        var grvArr = initMat(2, obj.n);
        var transaction = obj.transaction_max
        var count = 0;

        runClusterLoop()
        return {
            "result" : grvArr,
            "count" : count
        };

        //クラスタリング メインロジック
        function runClusterLoop() {
            var buffer = grvArr.slice();
            var result  = calcClaster(ptnMap,grvArr);

            if (isEqualArray(buffer,grvArr)) {
                return;
            }

            if (count > transaction) {
                return
            }
            count++;
            runClusterLoop();
        }

        // 配列の比較
        function isEqualArray(arr1,arr2){
            var a = JSON.stringify(arr1);
            var b = JSON.stringify(arr2);
            return (a === b);
        }

        // クラスタの計算
        function calcClaster(node,clusters){
            //配列初期化
            var store = new Array(clusters.length);

            for(var i=0;i<store.length;i++){
                store[i] = []; 
            }

            //ノードループ
            for(var i = 0;i<node.length;i++){
                var minVal = calcDistance(node[i],clusters[0]);
                var minCount = 0;

                //クラスタループ
                for(var j= 0;j<clusters.length;j++){
                    if(calcDistance(node[i],clusters[j])< minVal){
                        minCount = j;
                        minVal = calcDistance(node[i],clusters[j]);
                    }
                }
                store[minCount].push(node[i].slice());
            }

            for(var i = 0;i<clusters.length;i++){
                clusters[i] = calcGravity(store[i]);
            }

            return clusters;
        }

        // 重心
        function calcGravity(vec){
            var sum = vec[0];
            for(var i = 1;i<vec.length;i++){
                for(var j = 0;j<sum.length;j++){
                    sum[j] += vec[i][j];
                }
            }
            for(var j = 0;j<sum.length;j++){
                sum[j] /= vec.length;
            }
            return sum;
        }

        // 距離
        function calcDistance(vec1,vec2){
            var result = 0;
            for(var i=0;i<vec1.length;i++){
                result += Math.pow(2,Math.abs(vec1[i] - vec2[i]));
            }
            return (Math.sqrt(result));
        }

        //配列初期化
        function initMat(n,m,min,max){
            if(min === undefined || min === null){
                min = 0;max = 512;
            }
            if(max === undefined){
                max = 512;
            }
            var array = [];
            for(var i = 0;i<m;i++){
                var tmp=  [];
                for(var j=0;j<n;j++){
                    tmp.push(getRandomInt(min,max));
                }
                array.push(tmp);
            }
            return array;
        }

        function getRandomInt(min, max) {
          return Math.floor( Math.random() * (max - min + 1) ) + min;
        }
    }

    //
    // その他処理
    //

    function randMat(n,m,min,max){
        if(min === undefined || min === null){
            min = 0;max = 512;
        }
        if(max === undefined){
            max = 512;
        }
        var array = [];
        for(var i = 0;i<m;i++){
            var tmp=  [];
            for(var j=0;j<n;j++){
                tmp.push(getRandomInt(min,max));
            }
            array.push(tmp);
        }
        return array;
    }

    function getRandomInt(min, max) {
        return Math.floor( Math.random() * (max - min + 1) ) + min;
    }

})();

draw.js

function showPoints(array,rad,color){
    for(var i=0;i<array.length;i++){
        drawPoint(array[i],rad,color);
    }
}

function drawPoint(point,rad,color){
    var canvas = document.getElementById("canvas");
    var ctx = canvas.getContext('2d');
    ctx.beginPath();
    ctx.fillStyle = color; 
    ctx.arc(point[0], point[1], rad, 0, Math.PI*2, false);
    ctx.fill();
    ctx.closePath();
}

function drawLine(p1,p2,thick,color){
    var canvas = document.getElementById("canvas");
    var ctx = canvas.getContext('2d');
    ctx.beginPath();
    ctx.strokeStyle = color; 
    ctx.lineWidth = thick;
    ctx.moveTo(p1[0], p1[1]);
    ctx.lineTo(p2[0], p2[1]);
    ctx.stroke();
}

function clearCanvas(){
    var canvas = document.getElementById("canvas");
    var ctx = canvas.getContext('2d');
    ctx.clearRect(0,0,range,range);
}

function vec2rgb(v3,r){
    if(r === true){
        return "rgb("+(255-v3[0])+","+(255-v3[1])+","+(255-v3[2])+")";
    }else{
        return "rgb("+v3[0]+","+v3[1]+","+v3[2]+")";
    }    
}

上記のソースはアニメーションに関する処理は省かれているが、
setTimeoutを用いて下記のように実装している。
この中の描画関連の処理を調整させることによって色々なバージョンを作っている。

index.js

function main() {
    //
    // 省略
    //

    function runClusterLoop(){
        clearCanvas();

        var buffer = JSON.stringify(grvArr); //計算前の行列
        calcClaster();
        var result = JSON.stringify(grvArr); //計算後の行列

        for(var i=0;i<grvArr.length;i++){
            drawPoint(grvArr[i],7,vec2rgb(grvArrColor[i],true));
        }

        if(buffer === result){
            setTimeout(main, animationFrame);
            return;
        }
        count++;
        setTimeout(runClusterLoop, animationFrame);
    }
}