(function(e, a) { for(var i in a) e[i] = a[i]; }(exports, /******/ (function(modules) { // webpackBootstrap /******/ // The module cache /******/ var installedModules = {}; /******/ /******/ // The require function /******/ function __webpack_require__(moduleId) { /******/ /******/ // Check if module is in cache /******/ if(installedModules[moduleId]) { /******/ return installedModules[moduleId].exports; /******/ } /******/ // Create a new module (and put it into the cache) /******/ var module = installedModules[moduleId] = { /******/ i: moduleId, /******/ l: false, /******/ exports: {} /******/ }; /******/ /******/ // Execute the module function /******/ modules[moduleId].call(module.exports, module, module.exports, __webpack_require__); /******/ /******/ // Flag the module as loaded /******/ module.l = true; /******/ /******/ // Return the exports of the module /******/ return module.exports; /******/ } /******/ /******/ /******/ // expose the modules object (__webpack_modules__) /******/ __webpack_require__.m = modules; /******/ /******/ // expose the module cache /******/ __webpack_require__.c = installedModules; /******/ /******/ // define getter function for harmony exports /******/ __webpack_require__.d = function(exports, name, getter) { /******/ if(!__webpack_require__.o(exports, name)) { /******/ Object.defineProperty(exports, name, { enumerable: true, get: getter }); /******/ } /******/ }; /******/ /******/ // define __esModule on exports /******/ __webpack_require__.r = function(exports) { /******/ if(typeof Symbol !== 'undefined' && Symbol.toStringTag) { /******/ Object.defineProperty(exports, Symbol.toStringTag, { value: 'Module' }); /******/ } /******/ Object.defineProperty(exports, '__esModule', { value: true }); /******/ }; /******/ /******/ // create a fake namespace object /******/ // mode & 1: value is a module id, require it /******/ // mode & 2: merge all properties of value into the ns /******/ // mode & 4: return value when already ns object /******/ // mode & 8|1: behave like require /******/ __webpack_require__.t = function(value, mode) { /******/ if(mode & 1) value = __webpack_require__(value); /******/ if(mode & 8) return value; /******/ if((mode & 4) && typeof value === 'object' && value && value.__esModule) return value; /******/ var ns = Object.create(null); /******/ __webpack_require__.r(ns); /******/ Object.defineProperty(ns, 'default', { enumerable: true, value: value }); /******/ if(mode & 2 && typeof value != 'string') for(var key in value) __webpack_require__.d(ns, key, function(key) { return value[key]; }.bind(null, key)); /******/ return ns; /******/ }; /******/ /******/ // getDefaultExport function for compatibility with non-harmony modules /******/ __webpack_require__.n = function(module) { /******/ var getter = module && module.__esModule ? /******/ function getDefault() { return module['default']; } : /******/ function getModuleExports() { return module; }; /******/ __webpack_require__.d(getter, 'a', getter); /******/ return getter; /******/ }; /******/ /******/ // Object.prototype.hasOwnProperty.call /******/ __webpack_require__.o = function(object, property) { return Object.prototype.hasOwnProperty.call(object, property); }; /******/ /******/ // __webpack_public_path__ /******/ __webpack_require__.p = ""; /******/ /******/ /******/ // Load entry module and return exports /******/ return __webpack_require__(__webpack_require__.s = 0); /******/ }) /************************************************************************/ /******/ ([ /* 0 */ /***/ (function(module, __webpack_exports__, __webpack_require__) { "use strict"; __webpack_require__.r(__webpack_exports__); /* harmony export (binding) */ __webpack_require__.d(__webpack_exports__, "getRanges", function() { return getRanges; }); /* harmony export (binding) */ __webpack_require__.d(__webpack_exports__, "classIdx", function() { return classIdx; }); /* harmony export (binding) */ __webpack_require__.d(__webpack_exports__, "getClass", function() { return getClass; }); /* harmony export (binding) */ __webpack_require__.d(__webpack_exports__, "classify", function() { return classify; }); /* harmony import */ var _equalInterval_js__WEBPACK_IMPORTED_MODULE_0__ = __webpack_require__(1); /* harmony reexport (safe) */ __webpack_require__.d(__webpack_exports__, "classifyEqInterval", function() { return _equalInterval_js__WEBPACK_IMPORTED_MODULE_0__["classifyEqInterval"]; }); /* harmony import */ var _jenks_geostats_js__WEBPACK_IMPORTED_MODULE_1__ = __webpack_require__(2); /* harmony reexport (safe) */ __webpack_require__.d(__webpack_exports__, "classifyJenks", function() { return _jenks_geostats_js__WEBPACK_IMPORTED_MODULE_1__["classifyJenks"]; }); /* harmony import */ var _quantile_js__WEBPACK_IMPORTED_MODULE_2__ = __webpack_require__(3); /* harmony reexport (safe) */ __webpack_require__.d(__webpack_exports__, "classifyQuantile", function() { return _quantile_js__WEBPACK_IMPORTED_MODULE_2__["classifyQuantile"]; }); /* harmony import */ var _stdDeviation_js__WEBPACK_IMPORTED_MODULE_3__ = __webpack_require__(4); /* harmony reexport (safe) */ __webpack_require__.d(__webpack_exports__, "classifyStdDeviation", function() { return _stdDeviation_js__WEBPACK_IMPORTED_MODULE_3__["classifyStdDeviation"]; }); /* harmony import */ var _ckmeans_js__WEBPACK_IMPORTED_MODULE_4__ = __webpack_require__(5); /* harmony reexport (safe) */ __webpack_require__.d(__webpack_exports__, "classifyCkmeans", function() { return _ckmeans_js__WEBPACK_IMPORTED_MODULE_4__["classifyCkmeans"]; }); /** * Get a ranges array from a bounds array * @param {array} bounds * @param {string} separator * @param {number} precicion */ const getRanges = (bounds, separator = ' - ', precicion = 2) => { const multiplier = Math.pow(10, precicion) const ranges = [] for (let i = 0; i < bounds.length - 1; i++) { ranges.push( Math.round(bounds[i] * multiplier) / multiplier + separator + Math.round(bounds[i + 1] * multiplier) / multiplier ) } return ranges } /** * Get the index of a concrete value in a bounds array * The index ranges from "0" to "bounds.length - 2" (= nbClass - 1) * returns -1 if val not in bounds * @param {array} bounds * @param {number} val */ const classIdx = (bounds, val) => { if (val < bounds[0]) { return -1 } for (let i = 1; i < bounds.length; i++) { if (val <= bounds[i]) { return i - 1 } } return -1 } /** * Returns the corresponding class for a value. The value comes from the * provided classes-array. If the value is out of bounds oob is returned. * @param {array} bounds * @param {number} val * @param {array} classes * @param {*} oob */ const getClass = (bounds, val, classes, oob) => { const idx = classIdx(bounds, val) return typeof classes[idx] !== 'undefined' ? classes[idx] : oob } /** * Wrap up all classification algorithms in one function. * @param {('eqInterval'|'jenks'|'quantile'|'stdDev'|'ckmeans')} algorithm * @param {array} serie * @param {number} nbClass */ const classify = (algorithm, serie, nbClass) => { switch (algorithm) { case 'eqInterval': return Object(_equalInterval_js__WEBPACK_IMPORTED_MODULE_0__["classifyEqInterval"])(serie, nbClass) case 'jenks': return Object(_jenks_geostats_js__WEBPACK_IMPORTED_MODULE_1__["classifyJenks"])(serie, nbClass) case 'quantile': return Object(_quantile_js__WEBPACK_IMPORTED_MODULE_2__["classifyQuantile"])(serie, nbClass) case 'stdDev': return Object(_stdDeviation_js__WEBPACK_IMPORTED_MODULE_3__["classifyStdDeviation"])(serie, nbClass) case 'ckmeans': return Object(_ckmeans_js__WEBPACK_IMPORTED_MODULE_4__["classifyCkmeans"])(serie, nbClass) default: throw Error( 'Can not classify series. Algorithm "' + algorithm + '" not known' ) } } /* harmony default export */ __webpack_exports__["default"] = (classify); /***/ }), /* 1 */ /***/ (function(module, __webpack_exports__, __webpack_require__) { "use strict"; __webpack_require__.r(__webpack_exports__); /* harmony export (binding) */ __webpack_require__.d(__webpack_exports__, "classifyEqInterval", function() { return classifyEqInterval; }); /** * Classify the series in equal intervals from minimum to maximum value. * @param {array} serie * @param {number} nbClass * @param {number} forceMin * @param {number} forceMax */ const classifyEqInterval = (serie, nbClass, forceMin, forceMax) => { if (serie.length === 0) { return [] } const tmpMin = typeof forceMin === 'undefined' ? Math.min(...serie) : forceMin const tmpMax = typeof forceMax === 'undefined' ? Math.max(...serie) : forceMax const bounds = [] const interval = (tmpMax - tmpMin) / nbClass let val = tmpMin for (let i = 0; i <= nbClass; i++) { bounds.push(val) val += interval } bounds[nbClass] = tmpMax return bounds } /***/ }), /* 2 */ /***/ (function(module, __webpack_exports__, __webpack_require__) { "use strict"; __webpack_require__.r(__webpack_exports__); /* harmony export (binding) */ __webpack_require__.d(__webpack_exports__, "classifyJenks", function() { return classifyJenks; }); /** * Based on jenks implementation of geostats * https://github.com/simogeo/geostats * https://raw.githubusercontent.com/simogeo/geostats/a5b2b89a7bef3c412468bb1062e3cf00ffdae0ea/lib/geostats.js */ const classifyJenks = (serie, nbClass) => { if (serie.length === 0) { return [] } serie.sort((a, b) => a - b) // define two matrices mat1, mat2 const height = serie.length + 1 const width = nbClass + 1 const mat1 = Array(height) .fill() .map(() => Array(width).fill(0)) const mat2 = Array(height) .fill() .map(() => Array(width).fill(0)) // initialize mat1, mat2 for (let y = 1; y < nbClass + 1; y++) { mat1[0][y] = 1 mat2[0][y] = 0 for (let t = 1; t < serie.length + 1; t++) { mat2[t][y] = Infinity } } // fill matrices for (let l = 2; l < serie.length + 1; l++) { let s1 = 0.0 let s2 = 0.0 let w = 0.0 let v = 0.0 for (let m = 1; m < l + 1; m++) { const i3 = l - m + 1 const val = parseFloat(serie[i3 - 1]) s2 += val * val s1 += val w += 1 v = s2 - (s1 * s1) / w const i4 = i3 - 1 if (i4 !== 0) { for (let p = 2; p < nbClass + 1; p++) { if (mat2[l][p] >= v + mat2[i4][p - 1]) { mat1[l][p] = i3 mat2[l][p] = v + mat2[i4][p - 1] } } } } mat1[l][1] = 1 mat2[l][1] = v } const bounds = [] bounds.push(serie[serie.length - 1]) let k = serie.length for (let i = nbClass; i >= 2; i--) { const idx = parseInt(mat1[k][i] - 2) bounds.push(serie[idx]) k = parseInt(mat1[k][i] - 1) } bounds.push(serie[0]) return bounds.reverse() } /***/ }), /* 3 */ /***/ (function(module, __webpack_exports__, __webpack_require__) { "use strict"; __webpack_require__.r(__webpack_exports__); /* harmony export (binding) */ __webpack_require__.d(__webpack_exports__, "classifyQuantile", function() { return classifyQuantile; }); const classifyQuantile = (serie, nbClass) => { if (serie.length === 0) { return [] } serie.sort((a, b) => a - b) const bounds = [] bounds.push(serie[0]) const step = serie.length / nbClass for (let i = 1; i < nbClass; i++) { const qidx = Math.round(i * step + 0.49) bounds.push(serie[qidx - 1]) } bounds.push(serie[serie.length - 1]) return bounds } /***/ }), /* 4 */ /***/ (function(module, __webpack_exports__, __webpack_require__) { "use strict"; __webpack_require__.r(__webpack_exports__); /* harmony export (binding) */ __webpack_require__.d(__webpack_exports__, "classifyStdDeviation", function() { return classifyStdDeviation; }); const mean = (serie) => { const sum = serie.reduce((sum, val) => sum + val, 0) return sum / serie.length } const variance = (serie) => { let tmp = 0 for (let i = 0; i < serie.length; i++) { tmp += Math.pow(serie[i] - mean(serie), 2) } return tmp / serie.length } const stddev = (serie) => { return Math.sqrt(variance(serie)) } const classifyStdDeviation = (serie, nbClass) => { if (serie.length === 0) { return [] } const _mean = mean(serie) const _stddev = stddev(serie) const bounds = [] // number of classes is odd if (nbClass % 2 === 1) { // Euclidean division to get the inferior bound const infBound = Math.floor(nbClass / 2) const supBound = infBound + 1 // we set the central bounds bounds[infBound] = _mean - _stddev / 2 bounds[supBound] = _mean + _stddev / 2 // Values < to infBound, except first one for (let i = infBound - 1; i > 0; i--) { const val = bounds[i + 1] - _stddev bounds[i] = val } // Values > to supBound, except last one for (let i = supBound + 1; i < nbClass; i++) { const val = bounds[i - 1] + _stddev bounds[i] = val } // number of classes is even } else { const meanBound = nbClass / 2 // we get the mean value bounds[meanBound] = _mean // Values < to the mean, except first one for (let i = meanBound - 1; i > 0; i--) { const val = bounds[i + 1] - _stddev bounds[i] = val } // Values > to the mean, except last one for (let i = meanBound + 1; i < nbClass; i++) { const val = bounds[i - 1] + _stddev bounds[i] = val } } // set first value bounds[0] = Math.min(...serie) // set last value bounds[nbClass] = Math.max(...serie) return bounds } /***/ }), /* 5 */ /***/ (function(module, __webpack_exports__, __webpack_require__) { "use strict"; __webpack_require__.r(__webpack_exports__); /* harmony export (binding) */ __webpack_require__.d(__webpack_exports__, "classifyCkmeans", function() { return classifyCkmeans; }); const numericSort = arr => arr.slice().sort((a, b) => a - b) const uniqueCountSorted = arr => new Set(arr).size /** * Based on https://github.com/simple-statistics/simple-statistics/blob/master/src/ckmeans.js * Ckmeans clustering is an improvement on heuristic-based clustering * approaches like Jenks. The algorithm was developed in * [Haizhou Wang and Mingzhou Song](http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf) * as a [dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming) approach * to the problem of clustering numeric data into groups with the least * within-group sum-of-squared-deviations. * * Minimizing the difference within groups - what Wang & Song refer to as * `withinss`, or within sum-of-squares, means that groups are optimally * homogenous within and the data is split into representative groups. * This is very useful for visualization, where you may want to represent * a continuous variable in discrete color or style groups. This function * can provide groups that emphasize differences between data. * * Being a dynamic approach, this algorithm is based on two matrices that * store incrementally-computed values for squared deviations and backtracking * indexes. * * This implementation is based on Ckmeans 3.4.6, which introduced a new divide * and conquer approach that improved runtime from O(kn^2) to O(kn log(n)). * * Unlike the [original implementation](https://cran.r-project.org/web/packages/Ckmeans.1d.dp/index.html), * this implementation does not include any code to automatically determine * the optimal number of clusters: this information needs to be explicitly * provided. * * ### References * _Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic * Programming_ Haizhou Wang and Mingzhou Song ISSN 2073-4859 * * from The R Journal Vol. 3/2, December 2011 * @param {Array} x input data, as an array of number values * @param {number} nClusters number of desired classes. This cannot be * greater than the number of values in the data array. * @returns {Array>} clustered input * @throws {Error} if the number of requested clusters is higher than the size of the data * @example * ckmeans([-1, 2, -1, 2, 4, 5, 6, -1, 2, -1], 3); * // The input, clustered into groups of similar numbers. * //= [[-1, -1, -1, -1], [2, 2, 2], [4, 5, 6]]); */ function classifyCkmeans(x, nClusters) { if (nClusters > x.length) { return [] } const sorted = numericSort(x) // we'll use this as the maximum number of clusters const uniqueCount = uniqueCountSorted(sorted) // if all of the input values are identical, there's one cluster // with all of the input in it. if (uniqueCount === 1) { return [sorted] } // named 'S' originally const matrix = makeMatrix(nClusters, sorted.length) // named 'J' originally const backtrackMatrix = makeMatrix(nClusters, sorted.length) // This is a dynamic programming way to solve the problem of minimizing // within-cluster sum of squares. It's similar to linear regression // in this way, and this calculation incrementally computes the // sum of squares that are later read. fillMatrices(sorted, matrix, backtrackMatrix) // The real work of Ckmeans clustering happens in the matrix generation: // the generated matrices encode all possible clustering combinations, and // once they're generated we can solve for the best clustering groups // very quickly. const clusters = [] let clusterRight = backtrackMatrix[0].length - 1 // Backtrack the clusters from the dynamic programming matrix. This // starts at the bottom-right corner of the matrix (if the top-left is 0, 0), // and moves the cluster target with the loop. for (let cluster = backtrackMatrix.length - 1; cluster >= 0; cluster--) { const clusterLeft = backtrackMatrix[cluster][clusterRight] // fill the cluster from the sorted input by taking a slice of the // array. the backtrack matrix makes this easy - it stores the // indexes where the cluster should start and end. clusters[cluster] = sorted.slice(clusterLeft, clusterRight + 1) if (cluster > 0) { clusterRight = clusterLeft - 1 } } const bounds = [] bounds.push(clusters[0][0]) for (const cluster of clusters) { bounds.push(cluster[cluster.length - 1]) } return bounds } /** * Create a new column x row matrix. * * @private * @param {number} columns * @param {number} rows * @return {Array>} matrix * @example * makeMatrix(10, 10); */ function makeMatrix(columns, rows) { const matrix = [] for (let i = 0; i < columns; i++) { const column = [] for (let j = 0; j < rows; j++) { column.push(0) } matrix.push(column) } return matrix } /** * Generates incrementally computed values based on the sums and sums of * squares for the data array * * @private * @param {number} j * @param {number} i * @param {Array} sums * @param {Array} sumsOfSquares * @return {number} * @example * ssq(0, 1, [-1, 0, 2], [1, 1, 5]); */ function ssq(j, i, sums, sumsOfSquares) { let sji // s(j, i) if (j > 0) { const muji = (sums[i] - sums[j - 1]) / (i - j + 1) // mu(j, i) sji = sumsOfSquares[i] - sumsOfSquares[j - 1] - (i - j + 1) * muji * muji } else { sji = sumsOfSquares[i] - (sums[i] * sums[i]) / (i + 1) } if (sji < 0) { return 0 } return sji } /** * Function that recursively divides and conquers computations * for cluster j * * @private * @param {number} iMin Minimum index in cluster to be computed * @param {number} iMax Maximum index in cluster to be computed * @param {number} cluster Index of the cluster currently being computed * @param {Array>} matrix * @param {Array>} backtrackMatrix * @param {Array} sums * @param {Array} sumsOfSquares */ function fillMatrixColumn( iMin, iMax, cluster, matrix, backtrackMatrix, sums, sumsOfSquares ) { if (iMin > iMax) { return } // Start at midpoint between iMin and iMax const i = Math.floor((iMin + iMax) / 2) matrix[cluster][i] = matrix[cluster - 1][i - 1] backtrackMatrix[cluster][i] = i let jlow = cluster // the lower end for j if (iMin > cluster) { jlow = Math.max(jlow, backtrackMatrix[cluster][iMin - 1] || 0) } jlow = Math.max(jlow, backtrackMatrix[cluster - 1][i] || 0) let jhigh = i - 1 // the upper end for j if (iMax < matrix.length - 1) { jhigh = Math.min(jhigh, backtrackMatrix[cluster][iMax + 1] || 0) } let sji let sjlowi let ssqjlow let ssqj for (let j = jhigh; j >= jlow; --j) { sji = ssq(j, i, sums, sumsOfSquares) if (sji + matrix[cluster - 1][jlow - 1] >= matrix[cluster][i]) { break } // Examine the lower bound of the cluster border sjlowi = ssq(jlow, i, sums, sumsOfSquares) ssqjlow = sjlowi + matrix[cluster - 1][jlow - 1] if (ssqjlow < matrix[cluster][i]) { // Shrink the lower bound matrix[cluster][i] = ssqjlow backtrackMatrix[cluster][i] = jlow } jlow++ ssqj = sji + matrix[cluster - 1][j - 1] if (ssqj < matrix[cluster][i]) { matrix[cluster][i] = ssqj backtrackMatrix[cluster][i] = j } } fillMatrixColumn( iMin, i - 1, cluster, matrix, backtrackMatrix, sums, sumsOfSquares ) fillMatrixColumn( i + 1, iMax, cluster, matrix, backtrackMatrix, sums, sumsOfSquares ) } /** * Initializes the main matrices used in Ckmeans and kicks * off the divide and conquer cluster computation strategy * * @private * @param {Array} data sorted array of values * @param {Array>} matrix * @param {Array>} backtrackMatrix */ function fillMatrices(data, matrix, backtrackMatrix) { const nValues = matrix[0].length // Shift values by the median to improve numeric stability const shift = data[Math.floor(nValues / 2)] // Cumulative sum and cumulative sum of squares for all values in data array const sums = [] const sumsOfSquares = [] // Initialize first column in matrix & backtrackMatrix for (let i = 0, shiftedValue; i < nValues; ++i) { shiftedValue = data[i] - shift if (i === 0) { sums.push(shiftedValue) sumsOfSquares.push(shiftedValue * shiftedValue) } else { sums.push(sums[i - 1] + shiftedValue) sumsOfSquares.push(sumsOfSquares[i - 1] + shiftedValue * shiftedValue) } // Initialize for cluster = 0 matrix[0][i] = ssq(0, i, sums, sumsOfSquares) backtrackMatrix[0][i] = 0 } // Initialize the rest of the columns let iMin for (let cluster = 1; cluster < matrix.length; ++cluster) { if (cluster < matrix.length - 1) { iMin = cluster } else { // No need to compute matrix[K-1][0] ... matrix[K-1][N-2] iMin = nValues - 1 } fillMatrixColumn( iMin, nValues - 1, cluster, matrix, backtrackMatrix, sums, sumsOfSquares ) } } /***/ }) /******/ ])));