Какие данные мне нужны для реализации k ближайших соседей?

K-Nearest Neighbor (он же KNN) — это алгоритм классификации.

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

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

То, как вы определяете «ближайшего соседа», сильно зависит от того, как вы классифицируете свои данные. Очень часто данные отображаются в N-мерном пространстве, где N представляет собой количество различных классификационных характеристик, которые вы изучаете.

Простой пример:

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

Если бы я спросил вас, в какой стране находится случайная точка долготы и широты, смогли бы вы это выяснить? Что бы вы сделали, чтобы понять это?

Данные долготы/широты естественным образом отображаются в виде графика X,Y. Итак, если вы нанесете на этот график все города, а затем неизвестную точку, как вы определите страну неизвестного? Вы можете начать рисовать круги вокруг этой точки, увеличиваясь до тех пор, пока круг не охватит 10 ближайших городов на графике. Теперь вы можете посмотреть на страны этих 10 городов. Если все 10 находятся в США, то можно с достаточной долей уверенности сказать, что ваша неизвестная точка тоже находится в США. Но если только 6 городов в США, а остальные 4 в Канаде, можете ли вы сказать, где находится ваша неизвестная точка? Вы все еще можете предположить, США, но с меньшей уверенностью.

Самая сложная часть KNN — выяснить, как классифицировать ваши данные таким образом, чтобы вы могли определить «соседей» аналогичного качества и расстояние до этих соседей.

То, что вы описали, похоже на механизм рекомендательной системы, а не на алгоритм кластеризации, такой как k-means, который по сути является неконтролируемым подходом. Я не могу составить четкое представление о том, что на самом деле использует Reddit, но я нашел интересный пост, погуглив «рекомендатор + Reddit», например. Reddit, Stumbleupon, Del.icio.us и Hacker Новостные алгоритмы раскрыты! Во всяком случае, алгоритм k-NN (описанный в десять лучших алгоритмов интеллектуального анализа данных с псевдокодом в Википедии) может или другие методы, такие как совместная фильтрация (используется Amazon, например), описанный в этом хорошем руководство.

Кластеризация k-средних в своей простейшей форме представляет собой усреднение значений и сохранение других средних значений вокруг одного центрального среднего значения. Предположим, у вас есть следующие значения

1,2,3,4,6,7,8,9,10,11,12,21,22,33,40

Теперь, если я выполняю кластеризацию k-средних и помню, что кластеризация k-средних будет иметь механизм смещения (среднее/усреднение), который будет либо помещать значения близко к центру, либо далеко от него. И получаем следующее.

cluster-1 
1,2,3,4,5,6,7,8

cluster-2
10,11,12

cluster-3
21,22

cluster-4
33

cluster-5
40

Помните, я только что составил эти кластерные центры (кластер 1-5). Таким образом, в следующий раз, когда вы будете выполнять кластеризацию, числа окажутся вокруг любого из этих центральных средних (также известных как k-центры). Приведенные выше данные являются одномерными.

Когда вы выполняете кластеризацию kmeans для больших наборов данных с несколькими измерениями (многомерные данные — это массив значений, у вас будут миллионы значений одного и того же измерения), вам понадобится что-то большее и масштабируемое. Сначала вы усредните один массив, вы получите одно значение, аналогично повторите то же самое для других массивов, а затем выполните кластеризацию kmean.

Прочитайте один из моих вопросов здесь

Надеюсь это поможет.

Чтобы сделать k-ближайших соседей, вам в основном нужно понятие расстояния и способ найти k ближайших соседей к точке, которую вы можете себе позволить (вероятно, вы не хотите искать по всем своим точкам данных одну за другой). Существует библиотека для приблизительного ближайшего соседа по адресу http://www.cs.umd.edu/~mount/ANN/. Это очень простой алгоритм классификации — классифицировать новую точку p, найти ее k ближайших соседей и классифицировать p в соответствии с наиболее популярными классами среди этих k соседей.

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

Если вы заинтересованы в поиске особенно хорошего алгоритма обучения для ваших целей, загляните на http://www.cs.waikato.ac.nz/ml/weka/ — позволяет опробовать большое количество различных алгоритмов, а также написать свои в виде плагинов.

Вот очень простой пример KNN для набора данных MINST. Как только вы сможете рассчитать расстояние между вашими документами, тот же алгоритм будет работать.

http://shyamalapriya.github.io/digit-recognition-using-k-nearest-neighbors/