2014年11月14日金曜日

デンドログラムを jQuery + Underscore.js + Canvas で描いてみる

『集合知プログラミング』に載ってる、デンドログラムを書いてみる。 この ブログエントリに display:none で見えなくした div が含まれていて、『集合知プログラミング』のサンプルデータを納めてある。

データの形式は、行に「ブログ」、列に「単語」をとった表形式で、あるブログに含まれる単語の数が集計してあるというもの。

このデータをブラウザ上の Javascript で分析し、ブログ同士でピアソン相関を算出して近いものからペアにしてまとめあげていくと、クラスタができあがる。

それをツリー状に図示すると以下ようなデンドログラムになる。

ピアソン相関が 1に近づくほど（距離が小さいほど）赤みを増すように、canvas の strokeStyle を調整している。
      (function(ch03Plot01, $, undefined) {
        var $this = ch03Plot01;
        function peason(v1, v2) {
          var sums = _.chain(_.zip(v1, v2))
            .reduce(function(acc, vs){
              var a = vs[0];
              var b = vs[1];
              return [acc[0]+a, acc[1]+b, acc[2]+a*a, acc[3]+b*b, acc[4]+a*b];
            }, [0.0, 0.0, 0.0, 0.0, 0.0]).value();
          var n = v1.length;
          var num = sums[4] - sums[0]*sums[1]/n;
          var den = Math.pow((sums[2]-sums[0]*sums[0]/n)*(sums[3]-sums[1]*sums[1]/n), 0.5);

          return den==0 ? 0 : 1.0-num/den;
        }
        function Bicluster(args) {
          this.id = args.id;
          this.vec = args.vec;
          this.distance = args.distance ? args.distance : 0.0;
          this.left = args.left;
          this.right = args.right;
        }
        $this.hcluster = function (rows) {
          var distances = {};
          var currentclustid = -1;
          var clust = _.chain(_.zip(_.range(rows.length), rows))
            .map(function(idRow) {
              return new Bicluster({vec:idRow[1], id:idRow[0]});
            }).value();
          while (clust.length > 1) {
            var lowestpair = [0, 1];
            var closest = peason(clust[0].vec, clust[1].vec);
            for (var i =0; i<clust.length; ++i) {
              var x = _.range(i+10, clust.length);
              var idi = clust[i].id;
              for (var j=i+1; j<clust.length; ++j) {
                var idj = clust[j].id;
                var key = [idi, idj];
                if (!distances[key]) {
                  distances[key] = peason(clust[i].vec, clust[j].vec);
                }
                var d = distances[key];
                if (d < closest) {
                  closest=d;
                  lowestpair=[i, j];
                }
              }
            }
            var mergevec = _.chain(_.range(clust[0].vec.length))
                .map(function(i){
                  return (clust[lowestpair[0]].vec[i]+clust[lowestpair[1]].vec[i])/2.0;
                })
                .value();
            var newcluster=new Bicluster({
              vec:mergevec,
              left:clust[lowestpair[0]],
              right:clust[lowestpair[1]],
              distance:closest,
              id:currentclustid
            });
            currentclustid = currentclustid-1;
            clust.splice([lowestpair[1]], 1);
            clust.splice([lowestpair[0]], 1);
            clust.push(newcluster);
          }
          return clust[0];
        };
      } (window.ch03Plot01 = window.ch03Plot01 || {}, jQuery));
      function remove(arr, index) {
        arr.aplice(arr, index)
      }
      function getHeight(clust) {
        if (!clust.left && !clust.right) return 1;
        else return getHeight(clust.left) + getHeight(clust.right);
      }
      function getDepth(clust) {
        if (!clust.left && !clust.right) return 0;
        else Math.max(getDepth(clust.left), getDepth(clust.right))+clust.distance;
      }
      function drawDendrogram(clust, labels) {
        var h = getHeight(clust)*15;
        var w = 1200;
        var depth = getDepth(clust);
        var scalling = (w-150)/depth;

        var ctx = $('#pci-ch03-dendrogram').get(0).getContext('2d');

        $('#pci-ch03-dendrogram').attr('height', h);
        drawNode(ctx, clust, 10, h/2, scalling, labels);
        ctx.stroke();
      }

      function drawLine(ctx, x1, y1, x2, y2) {
        ctx.beginPath();
        ctx.moveTo(x1, y1);
        ctx.lineTo(x2, y2);
        ctx.stroke();
      };
      function rgbToHex(R,G,B) {return toHex(R)+toHex(G)+toHex(B)}
      function toHex(n) {
       n = parseInt(n,10);
       if (isNaN(n)) return "00";
       n = Math.max(0,Math.min(n,255));
       return "0123456789ABCDEF".charAt((n-n%16)/16)
            + "0123456789ABCDEF".charAt(n%16);
      }
      function drawNode(ctx, clust, x, y, scaling, labels) {
        if (clust.id < 0) {
          var h1 = getHeight(clust.left)*15;
          var h2 = getHeight(clust.right)*15;
          var top = y-(h1+h2)/2;
          var bottom = y+(h1+h2)/2;
          var ll = clust.distance*scaling;

          ctx.lineWidth=0.5;
          var lineColor ="#"+rgbToHex(
            Math.floor(127*(2-clust.distance*1.9)),
            Math.floor(64*(clust.distance*1.9)),
            Math.floor(127*(clust.distance*1.9)));

          ctx.strokeStyle=lineColor;

          drawLine(ctx, x, top+h1/2, x, bottom-h2/2);
          drawLine(ctx, x, top+h1/2, x+6, top+h1/2);
          drawLine(ctx, x, bottom-h2/2, x+6, bottom-h2/2);
          ctx.stroke();
          drawNode(ctx, clust.left, x+6, top+h1/2, scaling, labels);
          drawNode(ctx, clust.right, x+6, bottom-h2/2, scaling, labels);
        } else {
          ctx.fillStyle="#AAAAAA";
          ctx.fillText(labels[clust.id], (x+5), (y+2));
        }
      }
      $(function() {
        var lines = $('#blogdata').text().match(/[^\r\n]+/g);
        var colnames = _.rest(lines[0].match(/[^_]+/g));
        var $ol = $('ol');
        var size = null;
        var rowname_and_data = _.chain(_.rest(lines))
          .reduce(function(acc, line){
            var cells = line.match(/[^_]+/g);
            acc[0].push(cells[0]);
            acc[1].push(_.chain(_.rest(cells)).map(function(ch){return parseInt(ch);}).value());
            if (size == null) size = _.rest(cells).length;
            return acc;
          }, [[], []])
          .value();
        var rownames = rowname_and_data[0];
        var data=rowname_and_data[1];
        var clust = ch03Plot01.hcluster(data);
        drawDendrogram(clust, rownames);
      });

書籍では Python を使って jpg ファイルを出力していたが、ここでは計算も描画も Javascript を使ってみた。

jQuery と Underscore.js を使って、Canvas に描画している。

一昔かふた昔くらいまえは、よくこういうのに VB を使った解説とか書籍があったが、今だと Javascript + Canvas が一番お手軽かもしれない。
投稿者 時刻:
ラベル: ,

0 件のコメント:

コメントを投稿