Есть ли способ ускорить эту функцию для расчета K-ближайшего соседа? - PullRequest
Новая
       28

Есть ли способ ускорить эту функцию для расчета K-ближайшего соседа?

1 голос
/ 01 марта 2020

Я довольно новичок в программировании, и я создал функцию для вычисления ближайшего соседа 1 K (KNN1) для прогнозирования. Проблема в том, что код такой медленный, что я не могу протестировать его на обучающем наборе, который мне действительно нужен. Мой тренировочный набор ~ 1200 x 5600, где 1200 точек данных и 5600 функций. Мне нужно вычислить сумму квадратов различий для каждого объекта в каждом ряду, а затем выбрать другой ряд, который является наиболее похожим. Приведенный ниже код занимает ЧАСЫ и все еще не закончен Я полагаю, что вечность - это петли расстояния (тройные для l oop).

Я включил небольшой тренировочный набор из набора данных IRIS sklearn для тестирования.

Если кто-нибудь есть какие-либо предложения, чтобы ускорить это, чтобы я мог протестировать мой другой код в разумные сроки, это было бы очень признательно. 

from sklearn.datasets import load_iris
import numpy as np   

def l2_distance(row1, row2):
    distance = 0.0
    for i in range(len(row1)):
        #print('row one: {}'.format(row1[i]))
        #print('row two: {}'.format(row2[i]))
        distance += (row1[i] - row2[i])**2
    return sqrt(distance)

def KNN1(x, y):
    # Create sum of square distances for each feature in each row
    d_arr = []
    for i in range(0,len(x)):
        d_temp = []
        for j in range(0,len(x)):
            d = l2_distance(x[i], x[j])
            d_temp.append(d)
        d_arr.append(d_temp)
        #del d_temp

    # Find the index for the first NN
    idx_arr = []
    for i in range(0,len(d_arr)):
        temp = list(d_arr[i])
        m = min(j for j in temp if j > 0)
        idx_arr.append(temp.index(m))
        del temp

    del d_arr
    # Make a prediction based off the position in y_train for the test row
    y_hat = []
    for i in range(0,len(idx_arr)):
        y_hat.append(float(y[idx_arr[i]]))
    del idx_arr
    y_hat = np.array(y_hat)
    y_hat = np.reshape(y_hat,(len(y_hat),1))
    a = np.where(y==y_hat, 1, 0)    
    accuracy = float(np.sum(a,axis=0)/float(len(a)))*100.0
    return accuracy

iris = load_iris()
xtrain2 = iris.data[:, :2]
ytrain2 = (iris.target != 0) * 1
ytrain2 = np.reshape(ytrain2, (len(ytrain2),1))

acc = KNN1(xtrain2,ytrain2)
print('Accuracy for KNN (k=1) for the base dataset:\n\t{}\n'.format(acc))

1 Ответ

0 голосов
/ 02 марта 2020

Как упомянуто в комментарии, вам нужно рассмотреть другие алгоритмы для ускорения KNN, такие как деревья шаров (которые хорошо работают на наборах данных с большим количеством признаков) или деревья kd. Оптимизация алгоритма уменьшит временную сложность в геометрической прогрессии.

Но если вы продолжите поиск методом грубой силы, вам может пригодиться следующая информация:

Поскольку вы уже используете numpy почему бы не использовать scipy для ускорения ваших расчетов. Вы можете использовать scipy.spatial.distance.cdist вместо тройных циклов, чтобы получить метрику расстояния, и scipy.argsort, чтобы найти индекс для первого NN.

Я изменил ваш код следующим образом: 

from scipy.spatial.distance import cdist
from scipy import argsort
from scipy.stats import mode

def KNN2(x, y):
    # Create sum of square distances for each feature in each row
    d_arr = cdist(x,x)
    d_arr += np.eye(x.shape[0])*np.max(d_arr)

    # Find the index for the first NN
    idx_arr = argsort(d_arr, axis=1)[:, : 1]

    # ! I don't touch this part
    # Make a prediction based off the position in y_train for the test row
    y_hat = []
    for i in range(0,len(idx_arr)):
        y_hat.append(float(y[idx_arr[i]]))
    del idx_arr
    y_hat = np.array(y_hat)
    y_hat = np.reshape(y_hat,(len(y_hat),1))
    a = np.where(y==y_hat, 1, 0)    
    accuracy = float(np.sum(a,axis=0)/float(len(a)))*100.0

    return accuracy

Тестирование на моем P C: 

%timeit KNN1(xtrain2,ytrain2)
# 51.4 ms ± 523 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit KNN2(xtrain2,ytrain2)
# 1.24 ms ± 26.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Один крошечный KNN, который я реализовал, можно увидеть здесь .

...