/
inverse_distance_weighting.js
96 lines (92 loc) · 2.13 KB
/
inverse_distance_weighting.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
* Inverse distance weighting
*/
export default class InverseDistanceWeighting {
// https://en.wikipedia.org/wiki/Inverse_distance_weighting
// http://paulbourke.net/miscellaneous/interpolation/
/**
* @param {number} [k] Number of neighborhoods
* @param {number} [p] Power parameter
* @param {'euclid' | 'manhattan' | 'chebyshev' | 'minkowski' | function (number[], number[]): number} [metric] Metric name
*/
constructor(k = 5, p = 2, metric = 'euclid') {
this._k = k
this._p = p
this._metric = metric
if (typeof this._metric === 'function') {
this._d = this._metric
} else {
switch (this._metric) {
case 'euclid':
this._d = (a, b) => Math.sqrt(a.reduce((s, v, i) => s + (v - b[i]) ** 2, 0))
break
case 'manhattan':
this._d = (a, b) => a.reduce((s, v, i) => s + Math.abs(v - b[i]), 0)
break
case 'chebyshev':
this._d = (a, b) => Math.max(...a.map((v, i) => Math.abs(v - b[i])))
break
case 'minkowski':
this._dp = 2
this._d = (a, b) =>
Math.pow(
a.reduce((s, v, i) => s + (v - b[i]) ** this._dp, 0),
1 / this._dp
)
break
}
}
}
_near_points(data) {
const ps = []
this._x.forEach((p, i) => {
const d = this._d(data, p)
if (ps.length < this._k || d < ps[this._k - 1].d) {
if (ps.length >= this._k) ps.pop()
ps.push({
d: d,
value: this._y[i],
idx: i,
})
for (let k = ps.length - 1; k > 0; k--) {
if (ps[k - 1].d > ps[k].d) {
;[ps[k], ps[k - 1]] = [ps[k - 1], ps[k]]
}
}
}
})
return ps
}
/**
* Fit model.
*
* @param {Array<Array<number>>} x Training data
* @param {number[]} y Target values
*/
fit(x, y) {
this._x = x
this._y = y
}
/**
* Returns predicted values.
*
* @param {Array<Array<number>>} data Sample data
* @returns {number[]} Predicted values
*/
predict(data) {
return data.map(t => {
const ps = this._near_points(t)
if (ps[0].d === 0) {
return ps[0].value
}
let w = 0
let u = 0
for (let i = 0; i < ps.length; i++) {
const wi = 1 / ps[i].d ** this._p
u += wi * ps[i].value
w += wi
}
return u / w
})
}
}