Введение в алгоритмы
Алгоритм классификации K-ближайших соседей (KNN) является одним из самых простых методов в технологии классификации интеллектуального анализа данных.Так называемые K ближайших соседей означают K ближайших соседей, что означает, что каждый образец может быть использован Он представлен своими K ближайшими соседями .
Основная идея алгоритма KNN заключается в том, что если большинство из K ближайших соседей выборки в пространстве признаков принадлежат к определенной категории, то выборка также принадлежит к этой категории и имеет характеристики выборок этой категории. Этот метод определяет только категорию пробы, подлежащей классификации, в соответствии с категорией ближайшей одной или нескольких проб при принятии решения о классификации. Метод KNN связан только с очень небольшим количеством соседних выборок при принятии решений о классе. Поскольку метод KNN в основном полагается на ограниченные окружающие выборки, а не на метод различения домена класса для определения класса, к которому он принадлежит, метод KNN более эффективен, чем другие методы для разделения набора выборок, который имеет больше пересечений. или перекрывается в домене класса.
Алгоритм KNN можно использовать не только для классификации, но и для регрессии. Найдя K ближайших соседей выборки и присвоив выборке среднее значение атрибутов этих соседей, можно получить атрибуты выборки. Более полезным методом является присвоение различных весов влиянию соседей с разным расстоянием на выборку, например, веса обратно пропорциональны расстоянию.
кейс
Случай здесь из книги «Иллюстрация алгоритма», а примеры из книги просто для того, чтобы иметь общее представление об алгоритме KNN.
Дело номер один
Предположим, есть фрукт (апельсин или грейпфрут), как определить, апельсин это или грейпфрут? В это время мыслительный процесс мозга в целом аналогичен: есть таблица характеристик фруктов, предполагающая, что чем больше и желтее грейпфрут, как показано на рисунке ниже, и затем будет сделан вывод о том, что характеристики плода таинственные фрукты ближе всего к апельсинам или грейпфрутам, а ближе всего к типу фруктов.
Один из способов состоит в том, чтобы судить, глядя на то, какие фрукты являются его соседями. Предположим, вы смотрите на соседей 3. Три расстояния 1, 4 и 7 являются ближайшими, как показано на рисунке выше, потому что апельсины имеют 2 узла, а именно 1 и 4 , грейпфруты.Там всего 1 или 7 узлов. Апельсинов больше, чем грейпфрутов, поэтому неизвестный фрукт, скорее всего, апельсин. Этот простой процесс оценки и классификации заключается в использовании простого алгоритма KNN для достижения цели классификации.
Чтобы рассчитать расстояние между двумя точками, вы можете использовать формулу (√ — символ квадратного корня):
d = √((x1 - x2)² + (y1 - y2)²)
Признаки, извлеченные нашей классификационной оценкой, представляют собой две характерные точки размера и цвета плода, положение узла 3 (3, 10), положение узла 7 (8, 15), тогда расстояние между двумя точками равно:
d = √((3 - 8)² + (10 - 15)²) = √(50)
Многомерные координаты такие же, как и указанные выше двумерные координаты, такие как четырехмерные (x1, y1, z1, w1) и (x2, y2, z2, w2):
d = √((x1 - x2)² + (y1 - y2)² + (z1 - z2)² + (w1 - w2)²)
косинусное сходство
При расчете расстояния между двумя пользователями используется формула расстояния. Есть ли более подходящая формула? В практической работе, Часто используется косинусное сходство. Предположим, есть два пользователя со схожими вкусами, но один из них более хранить. Им обоим понравился фильм Манмохана Десаи «Амар Акбар Энтони», но Пол поставил 5 звезд и только Роуэн. Дайте 4 звезды. Если использовать формулу расстояния, два пользователя могут не быть соседями, хотя их вкусы очень близки. Косинусное сходство не вычисляет расстояние между двумя векторами, а сравнивает их углы, поэтому оно больше подходит для обработки вышеупомянутых случаев.
Случай 2
Система рекомендаций фильмов:
Предположим, есть веб-сайт с фильмами. Когда пользователи регистрируются, их просят оценить категории любимых фильмов. Теперь они получают данные рейтинга в следующей таблице (из 5 баллов).
| название | комедия | Боевик | Ужастик | Романтика |
|---|---|---|---|---|
| Сяо Чжан | 3 | 1 | 3 | 5 |
| маленький король | 2 | 4 | 4 | 4 |
| Кобаяши | 3 | 3 | 3 | 3 |
| Сяо Ли | 5 | 1 | 1 | 3 |
| Сяо Чен | 2 | 4 | 1 | 4 |
Согласно KNN, у людей с похожими рейтингами будут более стабильные любимые фильмы.Теперь, если вам нужно порекомендовать фильмы Сяо Чжану, вы можете порекомендовать фильмы, собранные самыми близкими людьми, которые ему нравятся.
Рассчитайте расстояние между Сяо Чжаном и другими людьми:
Например, Сяо Чжан и Сяо Ван: d = √((3 - 2)² + (1 - 4)² + (3 - 4)² + (5 - 4)²) = 2√3 , различные расстояния следующие:
| название | расстояние |
|---|---|
| Сяо Чжан | 0 |
| маленький король | 2√3 |
| Кобаяши | 2√2 |
| Сяо Ли | 2√3 |
| Сяо Чен | √15 |
Видно, что Сяо Чжан и Сяо Линь самые близкие, поэтому можно порекомендовать Сяо Чжану любимые фильмы Сяо Линя. На практике, если вы оцениваете больше фильмов на веб-сайте фильмов, вы можете получать более точные сообщения, потому что веб-сайт может более точно определить, на каких пользователей вы похожи.
Предскажите значение, используя регрессию KNN:
Предполагая, что существует бессчетное количество пользователей, выберите следующие пять пользователей, наиболее близких к Сяо Яну (на практике, чем больше соседей на разумном расстоянии, тем точнее прогноз), и предскажите, как Сяо Ян оценит каждый фильм:
| название | Фильм А |
|---|---|
| Сяо Чжан | 3 |
| маленький король | 3.5 |
| Кобаяши | 3 |
| Сяо Ли | 2.5 |
| Сяо Чен | 2.5 |
Средний балл фильма А для этих 5 соседей можно просто найти: (3 + 3,5 + 3 + 2,5 + 2,5) / 5 = 2,9. Вышеприведенное использует KNN для выполнения двух задач:
- 1. Классификация: группировка, сходные группы группируются
- 2. Регрессия: прогнозирование результатов
Предполагая, что средний балл фильма B от следующих 5 пользователей должен быть окончательным средним баллом фильма B, тогда (1 + 4 + 3 + 1 + 4)/5 = 2,6, но Приведенный выше расчет основан на одних и тех же стандартах для оценки каждого человека, но, как правило, разные люди имеют разные стандарты оценки.Например, некоторые люди поставят 4-балльную оценку фильму, который им немного дайте немного лайка, если они более требовательны. Фильм оценивается 3 из 3.
| название | Фильм А | Фильм Б | Фильм С | фильм Д | средний балл | Веса |
|---|---|---|---|---|---|---|
| Сяо Чжан | 3 | 1 | 3 | 5 | 3 | 1 |
| маленький король | 2 | 4 | 4 | 4 | 3.5 | 0.85 |
| Кобаяши | 3 | 3 | 3 | 3 | 3 | 1 |
| Сяо Ли | 5 | 1 | 1 | 3 | 2.5 | 0.83 |
| Сяо Чен | 2 | 4 | 1 | 4 | 2.75 | 0.92 |
Следовательно, мы можем рассчитать приблизительный средний балл каждого человека, чтобы просто оценить стандарт оценки каждого человека.Например, если Сяо Чжан используется в качестве стандартного шаблона для каждого человека, вес Сяо Ван составляет 3/3,5 = 0,85. (поскольку оценка Сяо Вана составляет 3/3,5 = 0,85. Как правило, высокая, поэтому вес снижается),
Тогда окончательный средний балл кинофильма B: (11 + 40.85 + 31 + 10,83 + 4 * 0,92)/5 = 2,22
Java-реализация
В этом разделе представлено только базовое представление о KNN.Приведенные выше примеры представляют собой простые расчеты данных после их получения, поэтому код не будет показан.