Search the k nearest neighbours for the given example.
(m: &Matrix<T>, example: &[T], k: usize, df: D)
| 25 | |
| 26 | /// Search the k nearest neighbours for the given example. |
| 27 | pub fn scan<D, T: Float>(m: &Matrix<T>, example: &[T], k: usize, df: D) -> Option<Vec<usize>> |
| 28 | where D : Fn(&[T], &[T]) -> T { |
| 29 | |
| 30 | if example.len() != m.cols() { |
| 31 | return None; |
| 32 | } |
| 33 | |
| 34 | let mut near: Vec<(usize, T)> = Vec::with_capacity(k); |
| 35 | |
| 36 | for (idx, row) in m.row_iter().enumerate() { |
| 37 | let d = df(row, example); |
| 38 | |
| 39 | // search the first neighbour for which the distance is larger |
| 40 | // than the distance to the current example and insert it at that |
| 41 | // position |
| 42 | let p = near.iter().position(|&(_, val)| val > d); |
| 43 | match p { |
| 44 | Some(pos) => { |
| 45 | near.insert(pos, (idx, d)); |
| 46 | if near.len() > k { |
| 47 | near.pop(); |
| 48 | } |
| 49 | } |
| 50 | _ => { |
| 51 | if idx < k { |
| 52 | near.push((idx, d)) |
| 53 | } |
| 54 | } |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | Some(near.iter().map(|&(idx, _)| idx.clone()).collect()) |
| 59 | } |
| 60 | |
| 61 | pub fn classify<T, L, D>(m: &Matrix<T>, labels: &Vec<L>, example: &[T], k: usize, df: D) -> L |
| 62 | where T: Float, L: Clone + Ord, D: Fn(&[T], &[T]) -> T { |