DIV CSS 佈局教程網

自然分類法(Jenks)斷點演算法的 JavaScript 實作
編輯:關於JavaScript     

自然分類法(Jenks Natural Breaks)是地圖配色、資料分級時常用的一種斷點計算方式。它的目標很單純:把一組數值切成若干等級,讓同一等級內部的差異盡量小、等級之間的差異盡量大。做法是透過動態規劃,反覆嘗試切點,找出「組內平方和總和」最小的那組斷點。

演算法主體

<script>
function getJenksBreaks(data, numclass) {
  function sortNumber(a,b) // JS 的 sort 必須傳比較函式,否則是依字串排序
  {
    return a - b
  }
  var numdata = data.length;
  data.sort(sortNumber); // 先排序

  var mat1 = new Array(); // 記錄每個等級的切點位置
  var mat2 = new Array(); // 記錄最小的組內平方和
  var st = new Array();

  for (var j = 0; j <= numdata; j++){
    mat1[j] = new Array();
    mat2[j] = new Array();
    st[j] = 0;
    for(var i = 0; i <= numclass; i++){
      mat1[j][i] = 0;
      mat2[j][i] = 0;
    }
  }

  for (var i = 1; i <= numclass; i++) {
    mat1[1][i] = 1;
    mat2[1][i] = 0;
    for (var j = 2; j <= numdata; j++){
      mat2[j][i] = Number.MAX_VALUE;
    }
  }
  var v = 0;

  for (var l = 2; l <= numdata; l++) {
    var s1 = 0, s2 = 0, w = 0, i3 = 0;
    for (var m = 1; m <= l; m++) {
      i3 = l - m + 1;
      var val = parseInt(data[i3-1]);
      s2 += val * val;
      s1 += val;
      w++;
      v = s2 - (s1 * s1) / w; // 組內平方偏差
      var i4 = i3 - 1;
      if (i4 != 0) {
        for (var j = 2; j <= numclass; j++) {
          if (mat2[l][j] >= (v + mat2[i4][j - 1])) {
            mat1[l][j] = i3;
            mat2[l][j] = v + mat2[i4][j - 1];
          }
        }
      }
  }
  mat1[l][1] = 1;
  mat2[l][1] = v;
  }

  var k = numdata;
  var kclass = new Array();
  kclass[numclass - 1] = parseInt(data[data.length - 1]);

  for (var j = numclass; j >= 2; j--) {
    var id = parseInt(mat1[k][j]) - 2;
    kclass[j - 2] = parseInt(data[id]);
    k = parseInt(mat1[k][j] - 1);
  }
  return kclass;
}
</script>

呼叫與輸出

<body>
<button type="button" onclick="doit()">自然分類法</button>
<input id="text"></input>

<script>
function doit(){
  // 實務上這裡會換成你的真實資料來源
  var data = new Array(9, 7, 6, 10, 8, 5, 3, 161, 136, 113, 166, 182, 191, 24, 139, 172, 193, 30);

  var text = document.getElementById("text");
  text.value = "";
  var grade = getJenksBreaks(data, 5); // 切成 5 級
  for (var i = 0; i < grade.length; i++)
    text.value = text.value + grade[i] + ",";
  }
</script>
</body>

理解重點

mat2 存的是「前 j 個等級、前 l 筆資料」所能得到的最小平方偏差總和,mat1 則記下對應的切點位置,最後從 mat1 回溯就能還原出各級的起始值。這是典型的動態規劃:用空間換取避免重複計算。

三個實作細節值得注意:一是務必先排序,否則分級沒有意義;二是 sort() 一定要傳比較函式,不然 [7,8,9,10,11] 會被排成 [10,11,7,8,9];三是資料量很大時這個 O(n²k) 的做法會變慢,若只是要快速分級,可以考慮等間距或分位數(quantile)等較輕量的方式。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved