# Use KNN as a clustering method

I am trying to use KNN as an Unsupervised clustering. Yes, I know KNN is supposed to be a used as a classifier, using I was given a task to use it as a clustering model).

I am using this link from sklearn documentation as a reference:

>>> from sklearn.neighbors import NearestNeighbors
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> nbrs = NearestNeighbors(n_neighbors=2, algorithm='ball_tree').fit(X)
>>> distances, indices = nbrs.kneighbors(X)
>>> indices
array([[0, 1],
[1, 0],
[2, 1],
[3, 4],
[4, 3],
[5, 4]]...)
>>> distances
array([[0.        , 1.        ],
[0.        , 1.        ],
[0.        , 1.41421356],
[0.        , 1.        ],
[0.        , 1.        ],
[0.        , 1.41421356]])

>>> dist_matrix = nbrs.kneighbors_graph(X).toarray()
array([[1., 1., 0., 0., 0., 0.],
[1., 1., 0., 0., 0., 0.],
[0., 1., 1., 0., 0., 0.],
[0., 0., 0., 1., 1., 0.],
[0., 0., 0., 1., 1., 0.],
[0., 0., 0., 0., 1., 1.]])


To help you visualize the problem, this is the data (X):

And this is the desired result:

desired_result = [[0, 1, 2], [3, 4, 5]]


My question is what is a computationally efficient way to construct the underlying clusters from the dist_matrix (or from the indices array)

• How do you construct the clusters from dist_matrix? Depending on the approach one may think about improving efficiency – Kalsi Apr 26 '20 at 17:34
• I changed the question. I am not looking for the most efficient solution right now, just for a solution that is "good enough". I have a feeling that this problem already have an implemented solution somewhere – justadev Apr 26 '20 at 18:09