1
$\begingroup$

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):

enter image description here

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)

$\endgroup$
2
  • $\begingroup$ How do you construct the clusters from dist_matrix? Depending on the approach one may think about improving efficiency $\endgroup$ – Kalsi Apr 26 '20 at 17:34
  • $\begingroup$ 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 $\endgroup$ – justadev Apr 26 '20 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.