【JavaScript】ブラウザ上でK-means、アニメーション化する！？【canvas】

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その1 <a href="https://t.co/VoMuCoq5sd">https://t.co/VoMuCoq5sd</a><br><br>JS + canavsの勉強も兼ねて<br>機械学習とかで使われるk-meansによるクラスタリングを可視化してみた<br>そしたら、ちょっと気持ち悪い蜘蛛みたいな動きをするようになった<a href="https://twitter.com/hashtag/javascript?src=hash&amp;ref_src=twsrc%5Etfw">#javascript</a> <a href="https://twitter.com/hashtag/MachineLearning?src=hash&amp;ref_src=twsrc%5Etfw">#MachineLearning</a> <a href="https://t.co/JnPq5mDSml">pic.twitter.com/JnPq5mDSml</a></p>&mdash; s-yoshiki | スクリプトカス (@s_yoshiki_dev) <a href="https://twitter.com/s_yoshiki_dev/status/1023131943741751296?ref_src=twsrc%5Etfw">2018年7月28日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>


# 概要

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

#### 参考
[【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その1](https://tech-blog.s-yoshiki.com/entry/11)
[【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その2](https://tech-blog.s-yoshiki.com/entry/12)
[【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その3](https://tech-blog.s-yoshiki.com/entry/13)

# 環境
JavaScript
Canvas
※ライブラリ等はなし

# デモ
<a href="https://jsfiddle.net/s_yoshiki/Lxdbfey3/8/show" align="center">
<img src="https://qiita-image-store.s3.amazonaws.com/0/82419/e9e0d5ee-d70e-2734-a2df-9efd7f57f4de.gif" width="70%">
</a>
#### **[デモ1](https://jsfiddle.net/s_yoshiki/Lxdbfey3/8/show)** | **[デモ2](https://jsfiddle.net/s_yoshiki/Lxdbfey3/7/show)** |  **[デモ3](https://jsfiddle.net/s_yoshiki/Lxdbfey3/21/show)**
#### 

※gifは[デモ1](https://jsfiddle.net/s_yoshiki/Lxdbfey3/8/show)

# 実装

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

詳しい説明は[【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その1](https://tech-blog.s-yoshiki.com/2018/06/121/)


```javascript: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;
    }

})();
```

```js: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を用いて下記のように実装している。
この中の描画関連の処理を調整させることによって色々なバージョンを作っている。

```javascript: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);
    }
}
```



# 参考
[【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その1](https://tech-blog.s-yoshiki.com/2018/06/121/)
[【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その2](https://tech-blog.s-yoshiki.com/2018/06/138/)
[【JavaScript】K-meansをアニメーション・可視化したら蜘蛛みたいな動きをした｜その3](https://tech-blog.s-yoshiki.com/2018/06/147/)