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

Question

У меня сейчас есть сайт типа Reddit-Clone.Я пытаюсь рекомендовать посты на основе постов, которые ранее нравились моим пользователям.

Кажется, что K ближайший сосед или k означает лучший способ сделать это.

Я могу 'Кажется, я не понимаю, как на самом деле реализовать это.Я видел некоторые математические формулы (например, те, что на странице k означают википедию), но они на самом деле не имеют смысла для меня.

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

Answer 1

K-ближайший сосед (он же KNN) - алгоритм классификации.

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

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

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

Тривиальный пример:

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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.

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

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

Answer 5

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