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
106
107
108
109
110
111
112
113
use crate::arrayadapter::ArrayAdapter;
use crate::fasterpam::{do_swap, find_best_swap, initial_assignment, update_removal_loss};
use crate::util::*;
use core::ops::AddAssign;
use num_traits::{Signed, Zero};
use std::convert::From;
pub fn fastpam1<M, N, L>(
mat: &M,
med: &mut Vec<usize>,
maxiter: usize,
) -> (L, Vec<usize>, usize, usize)
where
N: Zero + PartialOrd + Copy,
L: AddAssign + Signed + Zero + PartialOrd + Copy + From<N>,
M: ArrayAdapter<N>,
{
let (n, k) = (mat.len(), med.len());
if k == 1 {
let assi = vec![0; n];
let (swapped, loss) = choose_medoid_within_partition::<M, N, L>(mat, &assi, med, 0);
return (loss, assi, 1, if swapped { 1 } else { 0 });
}
let (mut loss, mut data) = initial_assignment(mat, med);
debug_assert_assignment(mat, med, &data);
let mut removal_loss = vec![L::zero(); k];
let (mut n_swaps, mut iter) = (0, 0);
while iter < maxiter {
iter += 1;
let mut best = (L::zero(), usize::MAX, usize::MAX);
update_removal_loss(&data, &mut removal_loss);
for j in 0..n {
if j == med[data[j].near.i as usize] {
continue;
}
let (change, b) = find_best_swap(mat, &removal_loss, &data, j);
if change >= best.0 {
continue;
}
best = (change, b, j);
}
if best.0 < L::zero() {
n_swaps += 1;
let newloss = do_swap(mat, med, &mut data, best.1, best.2);
if newloss >= loss {
break;
}
loss = newloss;
} else {
break;
}
}
let assi = data.iter().map(|x| x.near.i as usize).collect();
(loss, assi, iter, n_swaps)
}
#[cfg(test)]
mod tests {
use crate::{arrayadapter::LowerTriangle, fastpam1, silhouette, util::assert_array};
#[test]
fn test_fastpam1_simple() {
let data = LowerTriangle {
n: 5,
data: vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 1],
};
let mut meds = vec![0, 1];
let (loss, assi, n_iter, n_swap): (i64, _, _, _) = fastpam1(&data, &mut meds, 10);
let (sil, _): (f64, _) = silhouette(&data, &assi, false);
assert_eq!(loss, 4, "loss not as expected");
assert_eq!(n_swap, 1, "swaps not as expected");
assert_eq!(n_iter, 2, "iterations not as expected");
assert_array(assi, vec![0, 0, 0, 1, 1], "assignment not as expected");
assert_array(meds, vec![0, 3], "medoids not as expected");
assert_eq!(sil, 0.7522494172494172, "Silhouette not as expected");
}
}