Nearest Neighbors on mixed data types in high dimensions

Question

I would like to be able to use nearest neighbors to attempt to find the most similar samples to a subclass of samples (think treated vs untreated) in a dataset with continuous, categorical, and text features.

Toy data set:

import numpy as np
import pandas as pd
from sklearn.preprocessing import OneHotEncoder, QuantileTransformer
from sklearn.neighbors import NearestNeighbors
from sklearn.compose import ColumnTransformer
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.pipeline import Pipeline
from sklearn.decomposition import TruncatedSVD    

np.set_printoptions(suppress=True)

a = [20, 100, 10000, 500]
b = [1, 2, 3, 2]
c = ['dog', 'cat', 'foo', 'cat']
d = ['apple apple fruit',
     'mercedes bmw chevrolet',
     'monster dragon snake',
     'mercedes chevrolet bmw buick']

z = [a,b,c,d]

names = {0: 'col1', 1:'col2', 2:'col3', 3:'col4'}

X = pd.DataFrame(z).T
X = X.rename(names, axis='columns')
X

Will create:

   col1    col2 col3    col4
0   20      1   dog     apple apple fruit
1   100     2   cat     mercedes bmw chevrolet
2   10000   3   foo     monster dragon snake
3   500     2   cat     mercedes chevrolet bmw buick

As we can see, samples 1 and 3 are the most related. They have many of the same vocabulary, share two labels (col2 + col3) and considering the distribution of col1 they are fairly close together. We transform them into a feature array and ask for nearest neighbors like so:

numeric = ['col1']
numeric_transformer = Pipeline(steps=[('scaler', QuantileTransformer())])

cat = ['col2', 'col3']
cat_transformer = Pipeline(steps=[('onehot', OneHotEncoder())])

text = ['col4']
text_transformer = Pipeline(steps=[('tfidf', TfidfVectorizer()),
                                   ('svd', TruncatedSVD(n_components=2))])

prep = ColumnTransformer(transformers=[('num', numeric_transformer, numeric), 
                                       ('cat', cat_transformer, cat),
                                       ('text', text_transformer, 'col4')], sparse_threshold=0)

X_transformed = prep.fit_transform(X)

nn = NearestNeighbors(n_neighbors=2)
nn.fit(X_transformed)

d, i = nn.kneighbors(X_transformed[1].reshape(1,-1))
i

Correctly returns array([[1, 3]], dtype=int64) with the 1 indicating the self match and the 3 being the nearest neighbor.

But on a real world dataset, across 100+ dimensions, should I be using a custom distance function? for nearest neighbors with sklearn, if the column was one of the ones that was text, we could use cosine distance, another distance across the high dimensional one hot encoded variables, and another distance calculation with real continuous transformed variables (col1).

But is this....hacky? Is there some way to deal with the heterogenous data for nearest neighbors search without this? I worry that my decisions as to how to weight each of the three types of variables make the end results very subjective and open to criticism.

Answer 1

Conceptually, there's no reason why this 'could' not work, but practically speaking, there are probably better approaches than using KNN.

Suitability of KNN

One immediate problem with KNN is that each new instance must be compared to each existing reference instance before a class can be determined. As the number of reference instances increases, the time to classify a new instance increases. With highly dimensional data, you're going to need a lot of reference instances.

Dimensionality of the Data

If you are set on using KNN, you will want to do everything you can to reduce the number of dimensions, particularly on the categorical columns. In your example, you may be better off reducing the animals down to some larger groups, for example: [Pet, Domesticated, Wild] or biological family. If not, once you encode the categorical values, you will maybe have thousands (to millions) of animal columns alone. If you don't have many examples of each, you're going to match on everything but the animal because $$Distance\ between:\ dog\ and\ cat = 1$$ $$Distance\ between:\ dog\ and\ giraffe = 1$$ So, this will mean other attributes in the data will likely be more similar, yet, they may be uninformative to the classification process. For example, number of legs.

On the positive side though, KNN may deal with the introduction of new attributes a little better than others because the classification is based on the currently available data, so adding a new column is not as big a deal as say adding a new column to a neural network, which will need to be retrained to be able to accept a new data set.

Conclusion

While there are other pros and cons to KNN and ways to optimize it for performance; based on your description of the data, and perhaps making a few assumptions, KNN does not sound like a good fit for your classification problem.

Most models are going to perform better if you can reduce the number of dimensions, but if the number and nature of attributes is relatively static, I would start with something like a Decision Tree. The benefit of starting with a decision tree is that you can get a feel for the importance of the columns to the class assigned.

Answer 2

It's been a while since this but I did eventually get around to a solution:

from scipy.spatial.distance import euclidean, cosine, dice

cat_vars = ['col2', 'col3']
uniques = []
for c in cat_vars:
    uniques.append(X[c].nunique()) 
cat_vars_width = sum(uniques)
con_vars = ['col1']

# use a custom distance func to apply appropriate
# distance calcs to specific columns

con_vars_indices = list(range(0, con_vars_width))
cat_vars_indices = list(range(con_vars_width, con_vars_width + cat_vars_width))    
tfidf_indices = list(range(con_vars_width + cat_vars_width, X_normal.shape[1]))

def custom_distance_maker(con_vars_indices, cat_vars_indices, tfidf_indices):
    def custom_distance(x,y):
         x_con = x[con_vars_indices]
         y_con = y[con_vars_indices]
         x_cat = x[cat_vars_indices]
         y_cat = y[cat_vars_indices]
         x_tfidf = x[tfidf_indices]
         y_tfidf = y[tfidf_indices]

         d_con = euclidean(x_con,y_con)
         d_cat = dice(x_cat,y_cat)
         d_tfidf = cosine(x_tfidf,y_tfidf)
         return d_con + d_cat + d_tfidf
    return custom_distance

So we use the knowledge of how many columns are going to be created by the one hot encoding and how many columns are just real continuous variables and apply distance calculations appropriate for those data types to that specific portion of the big array. It's slow but honestly gives some pretty good results that satisified my client.

The custom distance function is easy enough to modify as well, allowing you to 'weight' the different variables you want to match on. For example, if you cared more about text matching, just multiply it in such a fashion as to magnify any differences in the cosine similarity search.

I hope some one else finds this hacky solution useful for similarity searches in heterogenuous data.