自然分類法(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)等較輕量的方式。