Компромисс ближайших соседей — работайте быстрее с менее точными результатами

Я работаю с набором данных среднего размера (shape=(14013L, 46L)). Я хочу сгладить каждый образец с его knn. Я тренирую свою модель с помощью:

NearestNeighbors(n_neighbors, algorithm='ball_tree',    
    metric=sklearn.metrics.pairwise.cosine_distances)

А гладкость следующая:

def smooth(x,nbrs,data,alpha):
    """
    input:
        alpha: the smoothing factor
        nbrs: trained NearestNeighbors from sklearn
        data: the original data 
             (since NearestNeighbors returns only the index and not the samples)
        x:    what we want to smooth
    output:
        smoothed x with its nearest neighbours
    """
    distances, indices = nbrs.kneighbors(x)
    distances = map(lambda z:abs(-z+1),distances)[0]
    norm = sum(distances)
    if norm == 0:
        "No neighbours were found."
        return x
    distances = map(lambda z: (1-alpha)*z/norm ,distances)
    indices = map(lambda z: data[z],indices)[0]
    other = np.array([indices[i] * distances[i] for i in range(len(distances))])
    z = x * alpha
    z = z.reshape((1,z.shape[0]))
    smoothed = sum(np.concatenate((other,z),axis=0))
    return smoothed

Мои вопросы:

  1. Как это возможно, что соседи не были найдены? (Я испытал это на своем наборе данных, поэтому условие if)
  2. Подгонка ("обучение") занимает 18 секунд, а сглаживание ~1000 образцов занимает более 20 минут. Я готов получить менее точные результаты, если процесс сглаживания будет короче. Является ли это возможным? какие параметры следует изменить чтобы этого добиться?

python scikit-learn nearest-neighbor smooth
person omerbp    schedule 11.06.2015    source источник
comment
Я не знаю, как knn используется в Python, но где вы передаете параметры? Или вы позволяете им получать значения по умолчанию?   -  person gsamaras    schedule 12.06.2015
comment
@gsamaras см. первый блок кода - инициация NearestNeighbors   -  person omerbp    schedule 12.06.2015
comment
Я это уже видел. Однако из этого я могу предположить, что вы используете параметры по умолчанию, верно?   -  person gsamaras    schedule 12.06.2015
comment
@gsamaras Да, любому неуказанному параметру присваивается значение по умолчанию. Вы можете увидеть его в документация   -  person omerbp    schedule 12.06.2015
comment
Да, я видел ссылку, спасибо, хороший вопрос, кстати, +1.   -  person gsamaras    schedule 12.06.2015

Ответы (2)


arrow_upward
1
arrow_downward

Во-первых, зачем использовать шаровое дерево? Возможно, ваша метрика подразумевает это для вас, но если это не так, вы также можете использовать kd-дерево.

Подойду к вашему вопросу с теоретической точки зрения. Параметр radius по умолчанию имеет значение 1.0. Это может быть слишком мало для вашего набора данных, поскольку, если я правильно понимаю, это будет указывать радиус запроса для изучения. Итак, я бы предложил запускать ваш код с увеличением этого значения, пока вы не получите какие-то результаты. Затем уменьшайте его, пока не получите никаких результатов. Еще немного увеличьте его, и вы получите оптимальный параметр для вашего набора данных.

Важным параметром является leaf_size, который фактически влияет на то, сколько точек вы собираетесь проверять при поступлении запроса. Небольшое значение этого параметра может привести к более быстрому выполнению с меньшей точностью.

Вы также можете проверить ">этот мой ответ, который объясняет компромисс между скоростью и точностью, компромисс, который имеет решающее значение для понимания при выполнении поиска ближайших соседей.

person gsamaras    schedule 12.06.2015

arrow_upward
1
arrow_downward

Без вашего набора данных и полного кода сложно сказать наверняка. Вот что я думаю.

distances = map(lambda z:abs(-z+1),distances)[0]
norm = sum(distances)

Поскольку вы индексируете результат карты, вы должны получить только первого соседа. Если x на самом деле является одной из точек, с которыми вы тренировались, то первым ближайшим соседом будет...x. Поскольку вы используете косинусное расстояние, это расстояние равно: 1. abs(1-1) == 0. Прежде чем я предложу поправку, давайте поговорим о производительности.

Что касается производительности: вы везде используете функцию map, встроенную в Python. Scikit-learn построен на numpy, который предназначен для выполнения математических операций намного быстрее, чем собственный код Python. Вот почему обучение происходит намного быстрее, чем ваш код. Вы должны использовать арифметику numpy вместо map. Один пример: эта строка

distances = map(lambda z: (1-alpha)*z/norm ,distances)

должно быть это

distances *= ((1-alpha)/norm)

Если norm является массивом, он должен иметь правильные размеры, чтобы правила вещания numpy срабатывали и выполнялись «правильные действия», полностью на C.

Итак, поскольку я предлагаю использовать массивы numpy (вместо map и списков Python), я считаю, что правильно для двух строк перед вашим оператором if будет отбрасывать индексацию. (Остальная часть вашего кода, вероятно, тоже повреждена индексацией; после второй строки вашей функции distances — это не массив или список, а скаляр.)

distances = np.abs( distances-1 )
norm = np.sum(distances)

Кроме того, вам не следует вызывать функцию smooth() много раз, по одному разу для каждого образца. Вы должны вызвать его в массиве N_samples на N_dimensions==46 numpy и соответствующим образом настроить код smooth(). (Например, метод NearestNeighbors вернет массив N_samples на N_neighbors гораздо быстрее, чем N_samples отдельных массивов длиной N_samples.)

person Andreus    schedule 12.06.2015
comment
Спасибо за советы. distances *= ((1-alpha)/norm) проблематичен, так как norm для каждого представляет собой l1 сумму расстояний. Вы, вероятно, имеете в виду distances *= ((1-alpha)/sum(distances)). кроме того, я вызываю smooth() один раз для каждого образца, а не много раз. - person omerbp; 12.06.2015
comment
Что касается звонка smooth(): Извините, непонятно. Вы хотите вызвать smooth() один раз для всех образцов, а не один раз для каждого образца. - person Andreus; 12.06.2015