Repository: mitre/menelaus (language: python)

Issue:
Address indiscriminate drift alarm in NN-DVI
### Task
When currently applied to 'realistic' and sizable data, the NNDVI implementation alarms drift constantly and irrespective of the user-selected k (for k-NN) and number of sampling times for drift-threshold estimation. Until this is fixed, NNDVI is bugged and unusable. 

**_Note:_** the referenced dataset is a private dataset of ~180K data points, split into ~9 batches. A MRE of such data is needed for testing and development in this issue.

### Impact
This will debug and un-block an otherwise completed drift detector and partitioner, and hence expand the zoo of detectors provided by `menelaus`. 

### Details
At minimum:

- [x] reproduce a dataset which causes the above behavior
- [ ] debug `NNSpacePartitioner.build()`, `NNSpacePartitioner.compute_nnps_distance()` for any partitioner-side problems
- [ ] debug `NNDVI.update()` and `NNDVI.compute_drift_threshold()` for any detector-side problems
Address indiscriminate drift alarm in NN-DVI
### Task
When currently applied to 'realistic' and sizable data, the NNDVI implementation alarms drift constantly and irrespective of the user-selected k (for k-NN) and number of sampling times for drift-threshold estimation. Until this is fixed, NNDVI is bugged and unusable. 

**_Note:_** the referenced dataset is a private dataset of ~180K data points, split into ~9 batches. A MRE of such data is needed for testing and development in this issue.

### Impact
This will debug and un-block an otherwise completed drift detector and partitioner, and hence expand the zoo of detectors provided by `menelaus`. 

### Details
At minimum:

- [x] reproduce a dataset which causes the above behavior
- [ ] debug `NNSpacePartitioner.build()`, `NNSpacePartitioner.compute_nnps_distance()` for any partitioner-side problems
- [ ] debug `NNDVI.update()` and `NNDVI.compute_drift_threshold()` for any detector-side problems
Address indiscriminate drift alarm in NN-DVI
### Task
When currently applied to 'realistic' and sizable data, the NNDVI implementation alarms drift constantly and irrespective of the user-selected k (for k-NN) and number of sampling times for drift-threshold estimation. Until this is fixed, NNDVI is bugged and unusable. 

**_Note:_** the referenced dataset is a private dataset of ~180K data points, split into ~9 batches. A MRE of such data is needed for testing and development in this issue.

### Impact
This will debug and un-block an otherwise completed drift detector and partitioner, and hence expand the zoo of detectors provided by `menelaus`. 

### Details
At minimum:

- [x] reproduce a dataset which causes the above behavior
- [ ] debug `NNSpacePartitioner.build()`, `NNSpacePartitioner.compute_nnps_distance()` for any partitioner-side problems
- [ ] debug `NNDVI.update()` and `NNDVI.compute_drift_threshold()` for any detector-side problems


Discussion / hints:

Fix patch:
diff --git a/docs/source/examples/data_drift/data_drift_examples.ipynb b/docs/source/examples/data_drift/data_drift_examples.ipynb
index ccdbd970..a94f4e3f 100644
--- a/docs/source/examples/data_drift/data_drift_examples.ipynb
+++ b/docs/source/examples/data_drift/data_drift_examples.ipynb
@@ -30,7 +30,6 @@
    "source": [
     "## Imports ##\n",
     "\n",
-    "import os\n",
     "import numpy as np\n",
     "import pandas as pd\n",
     "import seaborn as sns\n",
@@ -40,6 +39,7 @@
     "from menelaus.data_drift.hdddm import HDDDM\n",
     "from menelaus.data_drift import PCACD\n",
     "from menelaus.data_drift import KdqTreeStreaming, KdqTreeBatch\n",
+    "from menelaus.data_drift import NNDVI\n",
     "from menelaus.datasets import make_example_batch_data, fetch_circle_data"
    ]
   },
@@ -762,6 +762,72 @@
     "\n",
     "- Drift 5: change mean and var just for a year of J in 2021\n"
    ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "\n",
+    "# Nearest-Neighbor Density Variation Identification (NN-DVI)\n",
+    "\n",
+    "This example shows up how to set up, run, and produce output from the NN-DVI\n",
+    "detector, which is implemented to run in the batch setting. NN-DVI uses k-nearest \n",
+    "neighbors to partition the data, then uses measures defined with the adjacency \n",
+    "matrix for the reference and test data to determine whether drift has occurred."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "data = make_example_batch_data()\n",
+    "drift_years = data.groupby(\"year\")[\"drift\"].apply(lambda x: x.unique()[0]).reset_index()\n",
+    "drift_years.loc[drift_years[\"year\"].isin([2010, 2013, 2016]), \"drift\"] = True\n",
+    "\n",
+    "data_grouped = data.groupby('year')\n",
+    "\n",
+    "# Note that a small subsample is used, to decrease the runtime for the purpose\n",
+    "# of example.\n",
+    "batches = {year: (group.sample(frac=.1)\n",
+    "\t\t\t\t\t\t.drop(['year', 'cat', 'confidence', 'drift'], axis=1)\n",
+    "\t\t\t\t\t\t.values)\n",
+    "\t\t   for year, group in data_grouped}\n",
+    "\n",
+    "status = pd.DataFrame(columns=[\"year\", \"drift\"])\n",
+    "\n",
+    "det = NNDVI(k_nn=2, sampling_times=50)\n",
+    "det.set_reference(batches.pop(2007))\n",
+    "\n",
+    "for year, batch in batches.items():\n",
+    "\tdet.update(batch)\n",
+    "\tstatus = pd.concat([status, pd.DataFrame({\"year\":[year], \"drift\":[det.drift_state]})], \n",
+    "\t\t\t\t\t\taxis=0, \n",
+    "                        ignore_index=True)"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "Using this small subsample of data runs quickly, but yields inaccurate results \n",
+    "for the test data. A run with the full data takes much longer, but gives the \n",
+    "correct result in 9 of 13 years."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "(\n",
+    "    status.merge(drift_years, how=\"left\", on=\"year\", suffixes=[\"_nndvi\", \"_true\"])\n",
+    "    .replace({True: \"drift\", False: None})\n",
+    "    # .to_csv(\"example_nndvi_drift_comparison.csv\", index=False)\n",
+    ")"
+   ]
   }
  ],
  "metadata": {
diff --git a/examples/data_drift_examples.py b/examples/data_drift_examples.py
index ac60765b..9dd7a9a3 100644
--- a/examples/data_drift_examples.py
+++ b/examples/data_drift_examples.py
@@ -18,7 +18,6 @@
 
 ## Imports ##
 
-import os
 import numpy as np
 import pandas as pd
 import seaborn as sns
@@ -28,6 +27,7 @@
 from menelaus.data_drift.hdddm import HDDDM
 from menelaus.data_drift import PCACD
 from menelaus.data_drift import KdqTreeStreaming, KdqTreeBatch
+from menelaus.data_drift import NNDVI
 from menelaus.datasets import make_example_batch_data, fetch_circle_data
 
 
@@ -607,3 +607,53 @@ def distance_metric(reference_histogram, test_histogram):
 # 
 # - Drift 5: change mean and var just for a year of J in 2021
 # 
+
+# 
+# # Nearest-Neighbor Density Variation Identification (NN-DVI)
+# 
+# This example shows up how to set up, run, and produce output from the NN-DVI
+# detector, which is implemented to run in the batch setting. NN-DVI uses k-nearest 
+# neighbors to partition the data, then uses measures defined with the adjacency 
+# matrix for the reference and test data to determine whether drift has occurred.
+
+# In[ ]:
+
+
+data = make_example_batch_data()
+drift_years = data.groupby("year")["drift"].apply(lambda x: x.unique()[0]).reset_index()
+drift_years.loc[drift_years["year"].isin([2010, 2013, 2016]), "drift"] = True
+
+data_grouped = data.groupby('year')
+
+# Note that a small subsample is used, to decrease the runtime for the purpose
+# of example.
+batches = {year: (group.sample(frac=.1)
+						.drop(['year', 'cat', 'confidence', 'drift'], axis=1)
+						.values)
+		   for year, group in data_grouped}
+
+status = pd.DataFrame(columns=["year", "drift"])
+
+det = NNDVI(k_nn=2, sampling_times=50)
+det.set_reference(batches.pop(2007))
+
+for year, batch in batches.items():
+	det.update(batch)
+	status = pd.concat([status, pd.DataFrame({"year":[year], "drift":[det.drift_state]})], 
+						axis=0, 
+                        ignore_index=True)
+
+
+# Using this small subsample of data runs quickly, but yields inaccurate results 
+# for the test data. A run with the full data takes much longer, but gives the 
+# correct result in 9 of 13 years.
+
+# In[ ]:
+
+
+(
+    status.merge(drift_years, how="left", on="year", suffixes=["_nndvi", "_true"])
+    .replace({True: "drift", False: None})
+    # .to_csv("example_nndvi_drift_comparison.csv", index=False)
+)
+
diff --git a/menelaus/data_drift/__init__.py b/menelaus/data_drift/__init__.py
index e790f0ee..c14608c8 100644
--- a/menelaus/data_drift/__init__.py
+++ b/menelaus/data_drift/__init__.py
@@ -16,5 +16,6 @@
 from menelaus.data_drift.hdddm import HDDDM
 from menelaus.data_drift.kdq_tree import KdqTreeStreaming, KdqTreeBatch
 from menelaus.data_drift.pca_cd import PCACD
+from menelaus.data_drift.nndvi import NNDVI
 from menelaus.data_drift.cdbd import CDBD
 from menelaus.data_drift.histogram_density_method import HistogramDensityMethod
diff --git a/menelaus/data_drift/nndvi.py b/menelaus/data_drift/nndvi.py
new file mode 100644
index 00000000..3866b55c
--- /dev/null
+++ b/menelaus/data_drift/nndvi.py
@@ -0,0 +1,132 @@
+import numpy as np
+from scipy.stats import norm
+import warnings
+
+from menelaus.detector import BatchDetector
+from menelaus.partitioners import NNSpacePartitioner
+
+
+class NNDVI(BatchDetector):
+    """
+    This class encodes the Nearest Neigbors Density Variation
+    Identification (NN-DVI) drift detection algorithm, introduced
+    in Liu et al. (2018). Note that this implementation is intended
+    for batch datasets, rather than the streaming context.
+
+    Broadly, NN-DVI combines a reference and test data batch, creates
+    a normalized version of the subsequent adjacency matrix (after a
+    k-NN search), and then analyzes distance changes in the reference
+    and test sections of the combined adjacency matrix. Those changes
+    are compared against a threshold distance value, which is found
+    by randomly sampling new reference and test sections, then fitting
+    a Gaussian distribution to distance changes for those trials.
+
+    Attributes:
+        total_samples (int): number of batches the drift detector has ever
+            been updated with.
+        samples_since_reset (int): number of batches since the last drift detection.
+        drift_state (str): detector's current drift state. Can take values
+            ``"drift"``, ``"warning"``, or ``None``.
+        k_nn (int): the 'k' in k-Nearest-Neighbor (k-NN) search
+        reference_batch (numpy.array): initial batch of data
+        sampling_times (int): number of times to perform sampling for threshold estimation
+        alpha (float): significance level for detecting drift
+    """
+
+    def __init__(self, k_nn: int = 30, sampling_times: int = 500, alpha: float = 0.01):
+        """
+        Attributes:
+            k_nn (int, optional): the 'k' in k-Nearest-Neighbor (k-NN) search. Default 30.
+            sampling_times (int, optional): number of times to perform sampling for threshold
+                estimation. Default 500.
+            alpha (float, optional): significance level for detecting drift. Default 0.01.
+        """
+        super().__init__()
+        self.k_nn = k_nn
+        self.sampling_times = sampling_times
+        self.alpha = alpha
+
+    def update(self, X: np.array, y_true=None, y_pred=None):
+        """
+        Update the detector with a new test batch. If drift is detected, new
+        reference batch becomes most recent test batch.
+
+        Args:
+          X (numpy.array): next batch of data to detect drift on.
+          y_true (numpy.array): true labels, not used in NN-DVI
+          y_pred (numpy.array): predicted labels, not used in NN-DVI
+        """
+        if self._drift_state == "drift":
+            self.reset()
+
+        X, _, _ = super()._validate_input(X, None, None)
+
+        super().update(X=X, y_true=None, y_pred=None)
+        test_batch = np.array(X)
+
+        nnsp = NNSpacePartitioner(self.k_nn)
+        nnsp.build(self.reference_batch, test_batch)
+        M_nnps = nnsp.nnps_matrix
+        v_ref, v_test = nnsp.v1, nnsp.v2
+        d_act = NNSpacePartitioner.compute_nnps_distance(M_nnps, v_ref, v_test)
+
+        theta_drift = self._compute_drift_threshold(
+            M_nnps, v_ref, v_test, self.sampling_times, self.alpha
+        )
+        if d_act > theta_drift:
+            self._drift_state = "drift"
+            self.set_reference(test_batch)
+
+    def set_reference(self, X, y_true=None, y_pred=None):
+        """
+        Set the detector's reference batch to an updated value; typically
+        used in ``update``.
+
+        Attributes:
+            X (numpy.array): updated reference batch
+            y_true (numpy.array): true labels, not used in NNDVI
+            y_pred (numpy.array): predicted labels, not used in NNDVI
+        """
+        X, _, _ = super()._validate_input(X, None, None)
+        self.reference_batch = X
+
+    def reset(self):
+        """
+        Initialize relevant attributes to original values, to ensure information
+        only stored from samples_since_reset onwards. Intended for use
+        after ``drift_state == 'drift'``.
+        """
+        super().reset()
+
+    @staticmethod
+    def _compute_drift_threshold(M_nnps, v_ref, v_test, sampling_times, alpha):
+        """
+        Compute critical value for drift detection, by repeatedly sampling
+        NNPS distance calculations and estimating a normal distribution from
+        the same. Takes an NNPS matrix, indices of reference/test sections in
+        the same, number of times to sample, and a significance level for which
+        to determine the critical value. Intended for use within ``update`` after
+        the data has been partitioned.
+
+        Attributes:
+            M_nnps (numpy.array): NNPS matrix that results from ``NNSpacePartitioner.build``
+            v_ref (numpy.array): 1D array of same length as ``M_nnps``, with a one-hot encoding
+                of reference data point locations in ``M_nnps``.
+            v_test (numpy.array): 1D array of same length as ``M_nnps``, with a one-hot
+                encoding of test data point locations in ``M_nnps``.
+            sampling_times (int): number of times to perform sampling for threshold estimation
+            alpha (float): significance level for detecting drift
+        """
+        # TODO - Would like to parallelize this - Anmol
+        d_shuffle = []
+        for _ in range(sampling_times):
+            v1_shuffle = np.random.permutation(v_ref)
+            v2_shuffle = 1 - v1_shuffle
+
+            d_i_shuffle = NNSpacePartitioner.compute_nnps_distance(
+                M_nnps, v1_shuffle, v2_shuffle
+            )
+            d_shuffle.append(d_i_shuffle)
+        mu, std = norm.fit(d_shuffle)
+        drift_threshold = norm.ppf(1 - alpha, mu, std)
+        return drift_threshold
diff --git a/menelaus/partitioners/NNSpacePartitioner.py b/menelaus/partitioners/NNSpacePartitioner.py
new file mode 100644
index 00000000..c83448c8
--- /dev/null
+++ b/menelaus/partitioners/NNSpacePartitioner.py
@@ -0,0 +1,105 @@
+import numpy as np
+from sklearn.neighbors import NearestNeighbors
+
+
+class NNSpacePartitioner:
+    """
+    This class encodes the Nearest Neighbors Space Partitioning
+    scheme (NNPS) for use in the Nearest Neigbors Density Variation
+    Identification (NN-DVI) drift detection algorithm, both of which
+    are introduced in Liu et al. (2018).
+
+    Broadly, NNSP combines two input data samples, finds the adjacency
+    matrix using Nearest Neighbor search, and transforms the data points
+    into a set of shared subspaces for estimating density and changes in
+    density between the two samples, via a distance function.
+
+    Attributes:
+        k (int): the 'k' in k-Nearest-Neighbor (k-NN) search
+        D (numpy.array): combined data from two samples
+        v1 (numpy.array): indices of first sample data within ``D``
+        v2 (numpy.array): indices of second sample data within ``D``
+        nnps_matrix (numpy.array): NNSP shared-subspace representation of ``D``
+            and its adjacency matrix
+        adjacency_matrix (numpy.array): result of k-NN search on ``D``
+    """
+
+    def __init__(self, k: int):
+        """
+        Args:
+            k (int): the 'k' in k-NN search, describing size of searched neighborhood
+        """
+        self.k = k
+        self.D = None
+        self.v1 = None
+        self.v2 = None
+        self.nnps_matrix = None
+        self.adjacency_matrix = None
+
+    def build(self, sample1: np.array, sample2: np.array):
+        """
+        Builds an NNSP representation matrix given two samples of data.
+        Internally stores computed union set, adjacency matrix, index
+        arrays for the two samples, and NNSP representation matrix.
+
+        Args:
+            sample1 (numpy.array): first (possibly the 'reference') sample set
+            sample2 (numpy.array): second (possibly the 'test') sample set
+        """
+        data = np.vstack((sample1, sample2))
+        D, inverted_indices = np.unique(data, axis=0, return_inverse=True)
+        self.D = D
+        v1, v2 = np.array_split(inverted_indices, 2)
+        v1_onehot = np.zeros(D.shape[0])
+        v2_onehot = np.zeros(D.shape[0])
+        # XXX - Alternatively, v1_onehot = np.identity(adjacency_matrix.shape[0])[v1] - Anmol
+        v1_onehot[v1] = 1.0
+        v2_onehot[v2] = 1.0
+        self.v1 = v1_onehot
+        self.v2 = v2_onehot
+        nn = NearestNeighbors(n_neighbors=self.k).fit(D)
+        # TODO: maybe we can gain performance by performing operations using the returned
+        # scipy.sparse array, as opposed to converting this way.
+        M_adj = nn.kneighbors_graph(D).toarray()
+        self.adjacency_matrix = M_adj
+        # XXX - NearestNeighbors already adds the self-neighbors
+        # TODO - check about order preservation
+        P_nnps = M_adj
+        weight_array = np.sum(P_nnps, axis=1).astype(int)
+        Q = np.lcm.reduce(weight_array)
+        m = Q / weight_array
+        m = m * np.identity(len(m))
+        self.nnps_matrix = np.matmul(m, P_nnps)
+
+    @staticmethod
+    def compute_nnps_distance(nnps_matrix, v1, v2):
+        """
+        Breaks NNSP reprsentation matrix into NNPS matrices
+        for two samples using indices, computes difference in
+        densities of shared subspaces, between samples.
+
+        Args:
+            nnps_matrix (numpy.array): NNSP representation matrix
+            v1 (numpy.array): indices of first sample in ``D``, ``nnps_matrix``,
+                in one-hot encoding format
+            v2 (numpy.array): indices of second sample in ``D``, ``nnps_matrix``,
+                in one-hot encoding format
+
+        Returns:
+            float: distance value between samples, representing difference
+                in shared subspace densities
+        """
+        M_s1 = np.dot(v1, nnps_matrix)
+        M_s2 = np.dot(v2, nnps_matrix)
+
+        # These commented lines would only be relevant if there were overlap
+        # between the two vectors, which there never should be for our use case.
+        # Otherwise, this is always going to be the number of elements.
+        # membership = np.sum(np.array([v1, v2]), axis=0)
+        # membership = membership >= 1  # in case of overlap
+        # denom = sum(membership)
+        denom = len(v1)
+
+        d_nnps = np.sum(np.abs(M_s1 - M_s2) / (M_s1 + M_s2))
+        d_nnps /= denom
+        return d_nnps
diff --git a/menelaus/partitioners/__init__.py b/menelaus/partitioners/__init__.py
index f6ec58a8..36be53eb 100644
--- a/menelaus/partitioners/__init__.py
+++ b/menelaus/partitioners/__init__.py
@@ -7,3 +7,4 @@
 """
 
 from menelaus.partitioners.KDQTreePartitioner import KDQTreePartitioner, KDQTreeNode
+from menelaus.partitioners.NNSpacePartitioner import NNSpacePartitioner
diff --git a/setup.cfg b/setup.cfg
index 4df610a4..64f7b533 100644
--- a/setup.cfg
+++ b/setup.cfg
@@ -27,7 +27,7 @@ install_requires =
    numpy >= 1.22.0 # This is due to the call to np.quantile in data_drift.kdq_tree, which uses an updated arg name. The code is otherwise compatible with python >= 3.5.
    pandas
    scipy
-   sklearn
+   scikit-learn
 
 [options.extras_require]
 test =


Test patch:
diff --git a/tests/menelaus/data_drift/test_nndvi.py b/tests/menelaus/data_drift/test_nndvi.py
new file mode 100644
index 00000000..2edae726
--- /dev/null
+++ b/tests/menelaus/data_drift/test_nndvi.py
@@ -0,0 +1,84 @@
+import numpy as np
+import pytest
+
+from menelaus.data_drift import NNDVI
+
+
+def test_nndvi_init():
+    """Test correct default initialization for NN-DVI"""
+    det = NNDVI()
+    assert det.k_nn == 30
+    assert det.sampling_times == 500
+    assert det.alpha == 0.01
+    assert det.batches_since_reset == 0
+    assert det.drift_state is None
+
+
+def test_nndvi_set_reference():
+    """Assert NN-DVI.set_reference works as intended"""
+    det = NNDVI()
+    ref = np.random.randint(0, 5, (3, 3))
+    det.set_reference(ref)
+    assert np.array_equal(ref, det.reference_batch)
+
+
+def test_nndvi_update_1():
+    """Ensure NN-DVI can update with small random batches"""
+    det = NNDVI(k_nn=3, sampling_times=10)
+    det.set_reference(np.random.randint(0, 5, (10, 10)))
+    det.update(X=np.random.randint(0, 5, (10, 10)))
+
+
+def test_nndvi_update_2():
+    """Ensure NN-DVI can update with drift actions triggered"""
+    det = NNDVI(k_nn=5, sampling_times=10)
+    # XXX - AS added this method of forcing drift in NNDVI, which
+    #       is otherwise hard to induce drift in, for small data
+    #       examples. More stable alternatives may exist
+    np.random.seed(123)
+    det.set_reference(np.random.randint(0, 5, (10, 10)))
+    det.update(X=np.random.randint(10, 40, (10, 10)))
+    assert det.drift_state is not None
+
+
+def test_nndvi_update_3():
+    """Check NNDVI.update behavior after drift alarm"""
+    det = NNDVI(k_nn=3)
+    det.set_reference(np.random.randint(0, 5, (5, 5)))
+    det._drift_state = "drift"
+    det.update(X=np.random.randint(0, 5, (5, 5)))
+    assert det.drift_state is None
+
+
+def test_nndvi_update_4():
+    """Check failure when batch shapes don't match"""
+    det = NNDVI()
+    det.set_reference(np.random.randint(0, 5, (5, 6)))
+    with pytest.raises(ValueError):
+        det.update(np.random.randint(0, 5, (5, 5)))
+
+
+def test_nndvi_reset():
+    """Check NNDVI.reset works as intended"""
+    det = NNDVI()
+    det.batches_since_reset = 1
+    det.drift_state = "drift"
+    det.reset()
+    assert det.batches_since_reset == 0
+    assert det.drift_state is None
+
+
+def test_nndvi_compute_threshold_1():
+    """Check NNDVI._compute_threshold works correctly"""
+    det = NNDVI()
+    # XXX - Hardcoded known example added by AS, in the future a
+    #       dynamic way to test this function may be used
+    np.random.seed(123)
+    threshold = det._compute_drift_threshold(
+        M_nnps=np.random.randint(0, 5, (5, 5)),
+        v_ref=np.random.randint(0, 2, 5),
+        v_test=np.random.randint(0, 2, 5),
+        sampling_times=50,
+        alpha=0.01,
+    )
+    assert threshold >= 0.6 and threshold <= 0.7
diff --git a/tests/menelaus/partitioners/test_nn_space_partitioner.py b/tests/menelaus/partitioners/test_nn_space_partitioner.py
new file mode 100644
index 00000000..94139ed5
--- /dev/null
+++ b/tests/menelaus/partitioners/test_nn_space_partitioner.py
@@ -0,0 +1,40 @@
+import numpy as np
+
+from menelaus.partitioners import NNSpacePartitioner
+
+def test_nnsp_init():
+    ''' Check correct initialization state for NNSpacePartitioner'''
+    part = NNSpacePartitioner(30)
+    assert part.k == 30
+    attrs = [part.adjacency_matrix, part.nnps_matrix, part.D, part.v1, part.v2]
+    for attr in attrs:
+        assert attr is None
+
+def test_nnsp_build():
+    ''' Check basic correct execution for NNSpacePartitioner.build '''
+    part = NNSpacePartitioner(k=5)
+    part.build(np.random.randint(0,5,(6,6)), np.random.randint(0,5,(6,6)))
+    assert part.D.shape[0] <= 6*2
+    assert part.D.shape[1] == 6
+    assert len(part.v1) <= 6*2
+    assert len(part.v2) <= 6*2
+    assert part.adjacency_matrix.shape[0] <= 6*2
+    assert part.nnps_matrix.shape[0] <= 6*2
+
+def test_nnsp_compute_nnps_distance_1():
+    ''' Check correct computation for NNPS distance function in 0-case '''
+    nnps_mat = np.random.randint(0,5,(6,6))
+    v1 = np.random.randint(0,2,6)
+    distance = NNSpacePartitioner.compute_nnps_distance(nnps_mat, v1, v1)
+    assert distance == 0
+
+def test_nnsp_compute_nnps_distance_2():
+    ''' Check correct computation for NNPS distance in normal case '''
+    # XXX - Hard-coded example added by AS as it becomes complicated to
+    #       test dynamically
+    np.random.seed(123)
+    nnps_mat = np.random.randint(0,5,(6,6))
+    v1 = np.random.randint(0,2,6)
+    v2 = 1-v1
+    distance = NNSpacePartitioner.compute_nnps_distance(nnps_mat, v1, v2)
+    assert distance >= 0.29 and distance <= 0.3
\ No newline at end of file