Предварительно вычисленная матрица для подгонки с соседями по scikit / классификация радиуса

Question

Я работаю с классификацией ближайших соседей / радиусов Scikit-Learn с предварительно вычисленной метрикой. Это означает, что я передаю матрицу парных расстояний n_samples_train x n_samples_train в метод подгонки классификатора.

Теперь мне интересно, почему это должно быть сделано. Изучение с помощью knn просто должно означать "хранить выборки", но вычисление расстояний должно происходить только позже, во время обобщения (на этом этапе я, конечно, вычисляю матрицу расстояний между моими тренировочными выборками и моими тестовыми образцами, поэтому матрица размером n_samples_train x n_samples_test).

Например, в случае SVM я передаю предварительно вычисленную матрицу (Gramian, матрицу подобия) методу fit объекта smv.SVC. Затем происходит оптимизация, определяются векторы поддержки и так далее. Там эта матрица абсолютно необходима во время тренировок.

Но я не вижу причин, почему существует необходимость в предварительно вычисленной матрице с подгонкой в ​​классификации соседей / радиусов.

Может кто-нибудь дать мне соответствующую подсказку, пожалуйста?

Я бы хотел пропустить расчет тренировочной матрицы для knn с scikit learn.

С наилучшими пожеланиями и спасибо.:-)

Answer 1

Это старый, но я нашел его, когда искал связанную проблему.

По сути, это вопрос производительности. Возьмите случай, когда вы подходите к классификатору k соседей / радиусу один раз, а затем используйте его для классификации нескольких различных наборов контрольных точек. Если матрица ядра предварительно не вычисляется, то она должна будет вычислять матрицу ядра каждый раз, когда вы вызываете fit(). Способ реализации этих классификаторов использует тот факт, что вы работаете с положительной (полу) определенной функцией и можете использовать ее для ускорения поиска ближайшего соседа / радиуса для поиска новых точек с использованием дерева kd или дерева шаров, которая строит структуру, которая устанавливает границы расстояний до точек за пределами каждого поддерева. Построение такой структуры может быть выполнено за время iirc O(k*log(n)) для n выборок и k соседей (по крайней мере для дерева шаров). Таким образом, выполняя некоторую работу заблаговременно, можно значительно ускорить классификацию новых точек.

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

Итак, подведем итог: вы абсолютно правы в том, что предварительно вычисленная матрица расстояний не является строго необходимой для подбора общего k классификатора ближайших соседей. Однако, предварительно вычислив это - независимо от того, делаете ли вы это или передаете вызываемому элементу - последующая классификация намного эффективнее. Sklearn, очевидно, сделал выбор для предварительных вычислений для пользовательских метрик - вероятно, потому что накладные расходы с использованием функции Python n*(n-1)/2 раза делают этот маршрут намного медленнее, чем с использованием высокооптимизированных встроенных метрик, многие из которых частично или полностью реализовано в Cython. Но вам не нужно рассчитывать это как явный шаг перед установкой.