Similarity research : K-Nearest Neighbour(KNN) using a linear regression to determine the weights

Question

I have a set of houses with categorical and numerical data. Later I will have a new house and my goal will be to find the 20 closest houses. The code is working fine, and the result are not so bad but it is way too long. With a sample of 10 000 houses it takes 6 minutes, using Python 2.7. My actual dataset is about 100 000 houses.

# -*- coding: utf-8 -*-

import csv
import random
import math
import operator
import numpy as np
import pandas as pd, os
from sklearn.preprocessing import OneHotEncoder
from sklearn.feature_extraction import DictVectorizer
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LinearRegression
from unidecode import unidecode
import sys


# The function I use to deal with categorical data
def one_hot_dataframe(data, cols, replace=False):
    vec = DictVectorizer()
    mkdict = lambda row: dict((col, row[col]) for col in cols)
    vecData = pd.DataFrame(vec.fit_transform(data[cols].apply(mkdict, axis=1)).toarray())
    vecData.columns = vec.get_feature_names()
    vecData.index = data.index
    if replace is True:
        data = data.drop(cols, axis=1)
        data = data.join(vecData)
    return (data, vecData, vec)

# New data set with numerical data only
data_encode, _, _= one_hot_dataframe(data, ['Type', 'Bord_de_mer', 'Bord_de_plan_deau', 'Campagne', 'Centre_ville', 'Complexe_de_vacances', 'Lac', 'Montagne', 'Plage', 'Riviere', 'Village', 'Ville', 'Acces_haut_debit', 'Acces_internet', 'Climatisation', 'Linge_de_maison_fourni', 'Serviettes_de_bain', 'Wifi', 'Terrasse', 'Veranda_Loggia', 'Balcon', 'Jardin', 'location_non_fumeur', 'fumeurs_acceptes', 'animaux_autorises', 'animaux_non_admis', 'acces_handicape', 'Piscine_commune', 'Piscine_privee', 'Piscine_dinterieur', 'Piscine_chauffee', 'Bain_a_remous', 'Sauna'], replace=True)


#convert string to float
data = data.convert_objects(convert_numeric=True)

# deleting an useless column
data = data_encode.drop('SizeIn',1)

# I create a column for the index 
data.insert(0, 'index', range(0,len(data)))

# scaled_col the columns to standardize
scaled_col = ['Capacity', 'BedRooms', 'Latitude', 'Longitude', 'Size', 'Acces_haut_debit=No', 'Acces_haut_debit=Yes', 'Acces_internet=No', 'Acces_internet=Yes', 'Bain_a_remous=No', 'Bain_a_remous=Yes', 'Balcon=No', 'Balcon=Yes', 'Bord_de_mer=No', 'Bord_de_plan_deau=No', 'Bord_de_plan_deau=Yes', 'Campagne=No', 'Campagne=Yes', 'Centre_ville=No', 'Centre_ville=Yes', 'Climatisation=No', 'Climatisation=Yes', 'Complexe_de_vacances=No', 'Complexe_de_vacances=Yes', 'Jardin=No', 'Jardin=Yes', 'Lac=No', 'Lac=Yes', 'Linge_de_maison_fourni=No', 'Linge_de_maison_fourni=Yes', 'Montagne=No', 'Montagne=Yes', 'Piscine_chauffee=No', 'Piscine_chauffee=Yes', 'Piscine_commune=No', 'Piscine_commune=Yes', 'Piscine_dinterieur=No', 'Piscine_privee=No', 'Piscine_privee=Yes', 'Plage=No', 'Plage=Yes', 'Riviere=No', 'Riviere=Yes', 'Sauna=No', 'Sauna=Yes', 'Serviettes_de_bain=No', 'Serviettes_de_bain=Yes', 'Terrasse=No', 'Terrasse=Yes', 'Type=Appartement', 'Type=Chalet', "Type=Chambre d'h\xc3\xb4tes", 'Type=G\xc3\xaete', 'Type=Maison', 'Type=Studio', 'Type=Villa', 'Veranda_Loggia=No', 'Veranda_Loggia=Yes', 'Village=No', 'Village=Yes', 'Ville=No', 'Ville=Yes', 'Wifi=No', 'Wifi=Yes', 'acces_handicape=No', 'acces_handicape=Yes', 'animaux_autorises=No', 'animaux_autorises=Yes', 'animaux_non_admis=No', 'animaux_non_admis=Yes', 'fumeurs_acceptes=No', 'fumeurs_acceptes=Yes', 'location_non_fumeur=No', 'location_non_fumeur=Yes']

# standardization of the dataset   
scaled_features = data.copy()
features = scaled_features[scaled_col]
scaler = StandardScaler().fit(features.values)
features = scaler.transform(features.values)
scaled_features[scaled_col] = features




# That's the part where I find weights for the knn algorithm
# I'm using a simple regression and I keep the parameters

#create a new dataframe with the concerned features
weightframe = scaled_features
weightframe = weightframe.drop('DetailUrl', axis = 1)
weightframe = weightframe.drop('index', axis = 1)

X = weightframe.drop('Moyenne', axis = 1)
y = weightframe['Moyenne']

lm = LinearRegression(fit_intercept=False)
lm.fit(X,y)

# df with the features and their weights
weights = pd.DataFrame(zip(X.columns, lm.coef_))

# df with positive values
weights_abs = weights
weights_abs[1] = weights_abs[1].abs()


# Now I can start my knn algorithm
# First I define a distance which is divided by the weights 
def euclideanDistance(instance1, instance2, start, stop):
  distance = 0
  for x in range(start, stop):
    distance += (1/abs(weights.iloc[x-3,1]))*pow((instance1[x] - instance2[x]), 2)
  return math.sqrt(distance)

# Then I find the neighbors
def getNeighbors(trainingSet, testInstance, k):
  distances = trainingSet
  ncol = []
  for x in range(len(trainingSet)):
    dist = euclideanDistance(testInstance, trainingSet.iloc[x,:], 3, len(testInstance))
    ncol.append(dist)
  distances['distance'] = ncol
  distances = distances.sort(['distance'])
  neighbor = distances.head(k)
  return neighbor


# I test my function with the 314th line of the dataset
test = scaled_features.iloc[314,:]
# test_response returns the 20 closest houses
test_response = getNeighbors(scaled_features, test, 20)

#I want to have test_response in its original form (not standardized)
test_response[scaled_col] = scaler.inverse_transform(test_response[scaled_col])

print test_response

My dataset looks like this :

Moyenne                                          DetailUrl  Capacity  \
0    483.0   http://www.abritel.fr/location-vacances/p1325324         6   
1    790.0   http://www.abritel.fr/location-vacances/p1390219         4   
2    490.0   http://www.abritel.fr/location-vacances/p1383713         2   
3    535.0   http://www.abritel.fr/location-vacances/p1358629         3   
4    545.0  http://www.abritel.fr/location-vacances/p2227515a         7   

  BedRooms         Type   Latitude  Longitude  Size SizeIn Bord_de_mer  \
0        2         Gîte  47.879710   7.303924  75.0     m²          No   
1        2  Appartement  47.592455   7.579941  80.0     m²          No   
2   Studio       Studio  48.593275   7.769792  27.0     m²          No   
3        1  Appartement  48.075133   7.358069  33.0     m²          No   
4        2  Appartement  48.204212   7.570381  95.0     m²          No   

  Bord_de_plan_deau Campagne Centre_ville Complexe_de_vacances Lac Montagne  \
0                No      Yes           No                   No  No       No   
1               Yes       No          Yes                   No  No       No   
2                No       No           No                   No  No       No   
3                No       No          Yes                   No  No       No   
4                No      Yes           No                   No  No       No   

  Plage Riviere Village Ville Acces_haut_debit Acces_internet Climatisation  \
0    No      No     Yes    No               No            Yes            No   
1    No     Yes      No   Yes               No            Yes            No   
2    No      No      No    No               No            Yes            No   
3    No      No     Yes   Yes               No            Yes            No   
4    No      No     Yes    No               No            Yes            No   

  Linge_de_maison_fourni Serviettes_de_bain Wifi Terrasse Veranda_Loggia  \
0                     No                 No   No      Yes             No   
1                    Yes                Yes   No      Yes             No   
2                    Yes                Yes   No      Yes             No   
3                    Yes                Yes   No       No             No   
4                     No                 No   No       No            Yes   

  Balcon Jardin location_non_fumeur fumeurs_acceptes animaux_autorises  \
0     No    Yes                 Yes               No               Yes   
1    Yes    Yes                 Yes               No                No   
2     No     No                 Yes               No                No   
3     No     No                 Yes               No                No   
4     No    Yes                 Yes               No                No   

  animaux_non_admis acces_handicape Piscine_commune Piscine_privee  \
0                No             Yes              No             No   
1               Yes             Yes              No             No   
2               Yes             Yes              No             No   
3               Yes             Yes              No             No   
4               Yes             Yes              No             No   

  Piscine_dinterieur Piscine_chauffee Bain_a_remous Sauna  
0                 No               No            No    No  
1                 No               No            No    No  
2                 No               No            No    No  
3                 No               No            No    No  
4                 No               No            No    No 

I made some quick test and the part which is the longer to execute is the KNN part. The standardization and the regression part are quite quick.

What do you think of my script ? Do you have ideas to increase its performance ? It is definitely too slow.

Answer 1

To my eye, what sticks out is:

  for x in range(len(trainingSet)):
    dist = euclideanDistance(testInstance, trainingSet.iloc[x,:], 3, len(testInstance))
    ncol.append(dist)

because if you inline euclideanDistance, it becomes:

  for x in range(len(trainingSet)):
    dist = 0
    instance1, instance2 = testInstance, trainingSet.iloc[x,:]
    for xx in range(3, len(testInstance)):
        dist += (1/abs(weights.iloc[xx-3,1]))*pow((instance1[xx] - instance2[xx]), 2)
    ncol.append(math.sqrt(dist))

so your alg is order n^2 over the dataset. See if you can convert this into some DataFrame operations - they're (I think) backed by numpy so are vectorized for better efficiency.