/
pam.js
105 lines (99 loc) · 2.11 KB
/
pam.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
97
98
99
100
101
102
103
104
105
/**
* Partitioning Around Medoids
*/
export default class PAM {
// http://ibisforest.org/index.php?CLARANS
/**
* @param {number} k Number of clusters
*/
constructor(k) {
this._k = k
}
_distance(a, b) {
return Math.sqrt(a.reduce((acc, v, i) => acc + (v - b[i]) ** 2, 0))
}
_argmin(arr) {
let min_v = Infinity
let min_i = -1
for (let i = 0; i < arr.length; i++) {
if (arr[i] < min_v) {
min_v = arr[i]
min_i = i
}
}
return min_i
}
_cost(centroids) {
const c = centroids.map(v => this._x[v])
const n = this._x.length
let cost = 0
for (let i = 0; i < n; i++) {
const category = this._argmin(c.map(v => this._distance(this._x[i], v)))
cost += this._distance(this._x[i], c[category])
}
return cost
}
/**
* Initialize model.
*
* @param {Array<Array<number>>} datas Training data
*/
init(datas) {
this._x = datas
const idx = []
for (let i = 0; i < this._k; i++) {
idx.push(Math.floor(Math.random() * (this._x.length - i)))
}
for (let i = this._k - 1; i >= 0; i--) {
for (let j = this._k - 1; j > i; j--) {
if (idx[i] <= idx[j]) {
idx[j]++
}
}
}
this._centroids = idx
}
/**
* Fit model and returns true if any centroids has moved.
*
* @returns {boolean} `true` if any centroids has moved
*/
fit() {
const n = this._x.length
let init_cost = this._cost(this._centroids)
let changed = false
for (let k = 0; k < this._k; k++) {
let min_cost = Infinity
let min_idx = -1
for (let i = 0; i < n; i++) {
if (this._centroids.some(c => c === i)) {
continue
}
const new_c = this._centroids.concat()
new_c[k] = i
const new_cost = this._cost(new_c)
if (new_cost < min_cost) {
min_cost = new_cost
min_idx = i
}
}
if (min_cost < init_cost) {
this._centroids[k] = min_idx
init_cost = min_cost
changed = true
}
}
return changed
}
/**
* Returns predicted categories.
*
* @returns {number[]} Predicted values
*/
predict() {
const c = this._centroids.map(v => this._x[v])
return this._x.map(x => {
return this._argmin(c.map(v => this._distance(x, v)))
})
}
}