2
$\begingroup$

I have a data-set in which all features are binary and the class of each data-point is also binary. I am trying to use KNearestClassifier with a user-defined distance function as follows:

KNN = KNeighborsClassifier(n_neighbors=3,
                           algorithm='ball_tree',
                           metric='pyfunc',
                           metric_params={"func": lev_metric})
x_train, x_test, y_train, y_test = train_test_split(df_sum,
                                                    y,
                                                    test_size=0.1,
                                                    random_state=0)
KNN.fit(x_train, y_train)

and my custom metric function is as follows:

def lev_metric(a, b):
    print(a)
    print(b)
    return levenshtein(a, b)

the metric function expects two ndarrays of binary values of 0s and 1s. When knn.fit calls the metric function, "b" looks as expected (e.g. [0 1 1 0 0 1 0 1...) but "a" looks like gibberish and is an ndarray with real valued elements between 0 and 1, for example :

[0.32222222 0.42222222 0.34444444 0.47777778 0.41111111 0.38888889
 0.4        0.31111111 0.35555556 0.35555556 0.42222222 0.46666667
 0.36666667 0.32222222 0.41111111 0.32222222 0.36666667 0.35555556
 0.41111111 0.33333333 0.4        0.42222222 0.3        0.37777778
 0.38888889 0.48888889 0.41111111 0.43333333 0.34444444 0.35555556
 0.43333333 0.38888889 0.43333333 0.32222222 0.47777778 0.34444444...

what am I missing? I have also checked that the "x_train" is correct. Also, isn't knn an instance based learner? why is it calling the distance function in fit anyways? is it not supposed to just memorise the training examples? Thanks.

$\endgroup$
1
$\begingroup$

Neighbors-based methods are known as non-generalizing machine learning methods, since they simply “remember” all of its training data (possibly transformed into a fast indexing structure such as a Ball Tree or KD Tree).

(emphasis mine. Source: https://scikit-learn.org/stable/modules/neighbors.html#nearest-neighbors )

You are using algorithm='ball_tree', which roughly speaking uses Euclidean balls to cluster the points, making use of the ball distances for bounds on the distances between actual datapoints (wiki). So, I suspect the "a" value you're seeing is actually one of the balls' centers.

For the Levenshtein distance, you probably should use the 'brute' algorithm.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Oh, and I just found a duplicate from SO: stackoverflow.com/q/49638947/10495893 $\endgroup$ – Ben Reiniger Aug 15 '19 at 13:42
  • 1
    $\begingroup$ Yes, I came to the same conclusion after some testing. I tried some simple values and it seems that "a" value is in fact the mean of all my training examples (at least in the case when number of training examples is only 4). The way it seems to work is that during training, each training example is compared with this mean value. and during fit time, the training example to be classified is first compared with this mean value and then and then it is compared to every training example in the data-set. Also 'brute' algorithm cannot be used with a user defined metric it seems. $\endgroup$ – Ash Aug 15 '19 at 23:20
  • $\begingroup$ @Ash At first glance, it seems like you can use a custom metric in 'brute', but in that case you use your lev_metric callable directly as metric (no pyfunc and metric_params shenanigans). $\endgroup$ – Ben Reiniger Aug 16 '19 at 14:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.