Ленивые ученики против нетерпеливых учеников
Такие методы классификации, как байесовский, SVM, на основе правил и т. Д., Используют модель обобщения (классификации) для классификации новых тестовых кортежей. Эта модель строится до получения неизвестных кортежей на основе обучающего набора данных. Другими словами, такого рода методы классификации уже хотят (или готовы) классифицировать неизвестные кортежи. Их называют «Активными учениками».
«Ленивые ученики» ждут до последней минуты, чтобы классифицировать новый кортеж. Они не используют и не строят никаких обобщающих моделей. Ленивые ученики просто сохраняют обучающий набор. Для данного неизвестного кортежа эти учащиеся находят аналогичный кортеж из набора обучающих данных (уже сохраненного). Ленивые ученики делают меньше работы, когда берут обучающие кортежи, и больше работают, когда классифицируют новые неизвестные кортежи. Таким образом, это дорого с точки зрения вычислений и требует эффективного хранилища, но они очень подходят для реализации на параллельном оборудовании.
Классификация K-NN (K ближайшего соседа)
Метод классификации KNN был предложен в 1950-х годах, но стал популярным примерно в 1960-х годах, когда мощность компьютеров начала расти. Широко используемый метод классификации в приложениях поиска (или распознавания) образов. Это ленивый ученик, который учится по аналогии (означает, что он сравнивает тестовый кортеж с набором обучающих кортежей, которые на него похожи). «K» означает, что алгоритм сравнивает тестовый кортеж с «K» ближайшими соседями для классификации.
если k = 1, алгоритм выбирает ближайшего соседа к тестируемому кортежу в пространстве шаблонов
Если k ›1, предположим, что k = n, тогда алгоритм выбирает n соседей, ближайших к тестируемому кортежу. Выберите класс выбранных соседей, получивший большинство голосов, для класса тестового кортежа.
Как найти ближайших соседей?
KNN использует метрику расстояния для определения «близости» (сходства). Используя это, возьмем k ближайших соседей. Он может использовать евклидово расстояние, манхэттенское расстояние и т. Д. В качестве матриц расстояний. В следующем примере показано, как использовать евклидово расстояние.
Например: - Предположим, что X = (x1, x2, …… ..xn), где X находится в n-мерном пространстве шаблонов. А x1, x2… xn - значения атрибутов A1, A2,… .An. Предположим, что две точки (кортежи) X и Y такие, что X = (x1, x2 …… .xn) и Y = (y1, y2 …… .yn), тогда Евклидово расстояние между X и Y равно
Нормализация атрибутов
Обычно перед вычислением расстояния лучше нормализовать атрибуты. Причина в том, что могут быть атрибуты, которые изначально находятся в большом диапазоне (например: - зарплата), и они могут перевешивать атрибуты с изначально меньшими диапазонами (например: - двоичные атрибуты). Нормализация атрибутов решает эту проблему.
например: - Нормализация Min-Max
v ’ находится в диапазоне [0,1]
расстояние для категориальных нечисловых атрибутов
Предположим, что X и Y - два экземпляра атрибута, представляющего цвета (синий, красный, зеленый, белый и т. Д.). Расстояние Хэмминга - одна из возможных метрик.
если два идентичны (X и Y имеют одинаковый цвет, синий), то разница принимается как 0.
если X и Y не идентичны, тогда разница устанавливается на 1. А также существуют более сложные схемы, которые могут выполнять дифференциальную оценку (например: - назначить больший балл для синего и белого, чем для синего и черного).
Что делать с отсутствующими значениями
Если экземпляры атрибута X и / или Y (экземпляры атрибута A) отсутствуют, предполагайте максимально возможное расстояние. Для нечисловых категориальных значений выберите 1, если одно или оба значения отсутствуют.
Если A - числовой атрибут. Выберите 1, если отсутствует как в X, так и в Y. в противном случае выберите max (| v ’|, | 1 - v’ |)
Выбор значения для «k»
Используйте коэффициент ошибок классификатора для каждого значения k, увеличивая значение k с 1. Затем выберите значение k, которое дает минимальную частоту ошибок.
K-NCC для прогнозов
В качестве прогнозируемого значения тестового кортежа возьмите среднее значение всех меток с действительными значениями, связанных с k-ближайшими соседями.
Недостатки и методы повышения эффективности
K-NNC страдает низкой точностью с зашумленными и несущественными атрибутами. Этого можно избежать, включив методы отсечения кортежей и взвешивания атрибутов.
Чрезвычайно медленно при классификации тестовых кортежей (ленивый ученик). При k = 1 для сравнения требуется O (| D |) временной сложности (D - размер обучающих наборов). Но это можно улучшить, используя такие методы, как сортировка и различные структуры для хранения кортежей (используя древовидную структуру, мы можем уменьшить временную сложность до O (log (| D |))). Если мы используем параллельную реализацию, то временная сложность будет O (1) и не зависит от D.
Другое расстояние, такое как вычисление частичного расстояния (используйте порог расстояния и измерьте расстояние только для подмножества атрибутов в наборе A, если значение расстояния для подмножества превышает пороговое значение, тогда остановите сравнение и проверьте со следующим ближайшим соседом), отсечение (удаление бесполезных кортежей), и т. д. также можно использовать.
