Как рассчитать расстояние, когда у нас есть редкий набор данных в K ближайшего соседа

Question

Я реализую K алгоритм ближайшего соседа для очень разреженных данных.Я хочу вычислить расстояние между тестовым экземпляром и каждым образцом в обучающем наборе, но я в замешательстве.

Поскольку большинство функций в обучающих образцах не существует в тестовом экземпляре или наоборот (отсутствуют функции).

Как я могу вычислить расстояние в этой ситуации?

Answer 1

Чтобы убедиться, что я правильно понимаю проблему: каждый образец образует очень редко заполненный вектор.Пропущенные данные различаются в разных выборках, поэтому трудно использовать евклидову или другую метрику расстояния для измерения сходства выборок.

Если это такой сценарий, я уже видел эту проблему раньше в машинном обучении - вконкурс на призы Netflix, но не относится к KNN.Сценарий там был довольно похожим: у каждого профиля пользователя были оценки для некоторых фильмов, но почти никто не видел все 17 000 фильмов.Средний профиль пользователя был довольно скудным.

У разных людей были разные способы решения проблемы, но насколько я помню, они включали фиктивные значения для пропущенных значений, обычно среднее значение определенного значения для всехобразцы с данными.Затем они использовали евклидово расстояние и т. Д. Как обычно.Вы, вероятно, все еще можете найти обсуждения, связанные с этой проблемой отсутствующих ценностей, на этих форумах.Это было особенно распространенной проблемой для тех, кто пытался реализовать разложение по сингулярным числам, которое стало довольно популярным и поэтому обсуждалось совсем немного, если я правильно помню.

Вы можете начать здесь: http://www.netflixprize.com//community/viewtopic.php?id=1283

Вам придется немного покопаться.У Саймона Фанка был немного другой подход к этому, но он был более специфичным для SVD.Вы можете найти его здесь: http://www.netflixprize.com//community/viewtopic.php?id=1283 Он называет их пробелами, если вы хотите перейти к соответствующим разделам.

Удачи!

Answer 2

Если вы работаете в очень большом пространстве. Лучше сделать сокращение пространства, используя SVD, LDA, pLSV или аналогичные для всех доступных данных, а затем обучить алгоритм на обученных данных, преобразованных таким образом. Некоторые из этих алгоритмов являются масштабируемыми, поэтому вы можете найти реализацию в проекте Mahout. Особенно я предпочитаю использовать более общие функции, чем такие преобразования, потому что это проще для отладки и выбора функций. Для этого объедините некоторые функции, используйте стеммеры, подумайте более широко.