Как эффективно выбирать точки, которые снижают среднее расстояние до известных точек? - PullRequest
Новая
       9

Как эффективно выбирать точки, которые снижают среднее расстояние до известных точек?

2 голосов
/ 12 марта 2020

Итак, у вас есть набор «исследованных» точек в пространстве, а также набор «неисследованных» точек. Вы хотите выбрать K неисследованных точек для исследования, чтобы среднее расстояние от неизведанных точек до их ближайшей исследуемой точки было минимальным.

Sketch of the problem

Может ли это быть сделано более эффективно, чем грубой силой, выбирая неизведанные точки одну за другой и измеряя среднее расстояние?

У меня ниже есть функция python, которая выполняет работу. Но это не выполнимо для больших наборов, поскольку это становится очень медленным. Я хочу использовать это для набора не менее сотен тысяч неизведанных точек. Так что это должно быть более эффективным. Мне не нужно оптимальное решение, хорошее приближение подойдет!

Можно ли это как-то сделать без вложенных циклов for?

Или можно как-то выбрать только наиболее вероятные точки для оценки ?

Все идеи будут высоко оценены! 

import numpy as np

explored = np.random.rand(100,3)
unexplored = np.random.rand(100000,3)

def k_anchors(explored, unexplored, K):

    anchors = np.empty((K, unexplored.shape[1]))

    for j in range(K):
        proximity_sum = np.zeros((len(unexplored),))

        for k in range(len(unexplored)):
            temp_results = np.concatenate(( explored, unexplored[k].reshape((-1,3)) ))
            proximity = np.zeros((len( unexplored ),))

            for i in range(len( unexplored )):
                i_prox = (abs((unexplored[i,:] - temp_results))).sum(axis=1)
                proximity[i] = i_prox.min()

            proximity_sum[k] = proximity.sum()

        idx = np.argmin( proximity_sum )
        anchors[j,:] = unexplored[ idx ]
        unexplored = np.delete(unexplored, idx, 0)
        explored = np.concatenate(( explored, unexplored[ idx ] ))

    return anchors

print( k_anchors(explored, unexplored, 5) )

РЕШЕНИЕ

Проблема была решена с помощью варианта алгоритма K средних, предложенного Barış Can Tayiz, и Оно работало завораживающе.

Короче говоря, я инициализировал исследуемые точки как центроиды вместе с K случайными точками. Только K случайных точек были затем изменены при подборе данных. Для меня число K не нуждается в оптимизации, так как теперь я каждый раз, когда вызывается функция, сколько точек я смогу исследовать.

Спасибо всем, кто нашел драгоценное время, чтобы обсудить и ответить на этот вопрос!

1 Ответ

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

Для этой цели вы можете использовать неконтролируемые алгоритмы обучения. Например, если вы выберете k = 3 для k означает, следует изучить ближайшие точки к центрам. Выбор k - еще одна проблема. Вы можете достичь этого, посмотрев эту статью https://medium.com/analytics-vidhya/how-to-determine-the-optimal-k-for-k-means-708505d204eb. Вы можете использовать для внутрикластерной суммы квадратов ошибок (WSS) разницу n + 1-й / n-й / n-й - n-1-й. Это соотношение даст наилучшее значение k при измерении WSS.

...