abd-clam 0.11.0

Clustered Learning of Approximate Manifolds
Documentation 
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

import operator
import unittest

from abd_clam import dataset
from abd_clam import metric
from abd_clam import search
from abd_clam import space
from abd_clam.utils import synthetic_datasets


class TestSearch(unittest.TestCase):
    def setUp(self):
        self.data = dataset.TabularDataset(
            synthetic_datasets.bullseye(n=100, num_rings=3)[0],
            name=f"{__name__}.data",
        )
        self.indices = list(range(self.data.cardinality))
        self.distance_metric = metric.ScipyMetric("euclidean")
        self.metric_space = space.TabularSpace(self.data, self.distance_metric, False)
        self.max_depth = 10
        self.cakes = search.CAKES(self.metric_space).build(max_depth=self.max_depth)

        self.search_radii = [(self.cakes.root.radius / i) for i in range(200, 100, -20)]
        self.query = self.data[0]
        self.distances = self.metric_space.distance_pairwise(self.indices)

    def test_init(self):
        self.assertTrue(isinstance(self.cakes, search.CAKES))
        _ = self.cakes.metric_space
        _ = self.cakes.root
        self.assertLessEqual(self.cakes.depth, self.max_depth)

    def test_rnn_search(self):
        self.assertEqual(1, len(self.cakes.rnn_search(self.query, 0.0)))
        self.assertLessEqual(1, len(self.cakes.rnn_search(self.query, 1.0)))

        for i in self.indices:
            for radius in self.search_radii:
                naive_results: dict[int, float] = {
                    j: d
                    for j, d in zip(self.indices, self.distances[i, :])
                    if d <= radius
                }
                rnn_results: dict[int, float] = self.cakes.rnn_search(
                    self.data[i],
                    radius,
                )

                self.assertEqual(
                    len(naive_results),
                    len(rnn_results),
                    "expected the same number of results from naive and rnn searches.",
                )
                self.assertSetEqual(
                    set(naive_results.keys()),
                    set(rnn_results.keys()),
                    "expected the same set of results from naive and rnn searches.",
                )

    def test_knn_search(self):
        distances = dict(zip(self.indices, self.distances[0, :]))
        points: list[int] = [
            p for p, _ in sorted(distances.items(), key=operator.itemgetter(1))
        ]

        ks = list(range(1, 10))
        ks.extend(range(10, self.data.cardinality, 1000))
        for k in ks:
            naive_results = points[:k]
            knn_results: list[int] = list(self.cakes.knn_search(self.query, k).keys())
            self.assertEqual(
                len(naive_results),
                len(knn_results),
                "expected the same number of results from naive and knn searches.",
            )
            self.assertSetEqual(
                set(naive_results),
                set(knn_results),
                "expected the same set of results from naive and knn searches.",
            )

    def test_tree_search_history(self):
        radius: float = self.cakes.root.radius / 10
        history, hits = self.cakes.tree_search_history(self.query, radius)

        for c in hits:
            self.assertTrue(c in history, f"The hit {c!s} was not found in history.")
        self.assertLessEqual(
            len(hits),
            len(history),
            "history should have at least a many members as hits.",
        )

        for c in history:
            if c not in hits:
                self.assertFalse(
                    c.is_leaf,
                    "A non-hit member of history must have had children.",
                )

        depths: set[int] = {cluster.depth for cluster in history}
        depth_range: set[int] = set(range(len(depths)))
        missing_depths = depths.union(depth_range) - depths.intersection(depth_range)
        self.assertEqual(
            0,
            len(missing_depths),
            f"history should contain clusters from every depth. Did not contain: {missing_depths}",
        )