Классификация данных методом k-ближайших соседей

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

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

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

Отнесение классификации к интеллектуальным технологиям анализа данных обусловлено тем, что в повседневной жизни сознание человека, в поле которого постоянно попадают новые объекты окружающего мира, сопоставляет их с уже известными объектами и оценивает степень их сходства. Затем, на основе этой оценки объект ассоциируется с определённой группой (классом). Таким образом, классификация является наиболее «естественным» для человеческого интеллекта способом получения знаний о процессах и явлениях, происходящих в окружающем мире.

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

В метрических методах мерой сходства является расстояние (например, евклидово) в векторном пространстве, где каждый объект представлен своим вектором признаков. Логика здесь проста: новый объект скорее всего принадлежит к тому же классу, что и большинство соседних с ним объектов. Метрические методы как правило используются для построения классификаторов на основе машинного обучения.

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

Недостатком метрических методов является их эвристический характер — они могут дать неточное и неоднозначное решение, но считающееся приемлемым в большинстве практически значимых случаев. Однако при этом они имеют высокую объясняющую способность и поэтому их результаты проще интерпретировать. В простейшем случае можно использовать правило: объект относится к тому же классу, что и большинство его ближайших соседей.

Типичным представителем методов классификации, использующих эту логику, является метод k-ближайших соседей — k-nearest neighbors algorithm (KNN). Метод был впервые разработан Эвелином Фиксом и Джозефом Лоусоном Ходжесом в 1951 году, и позднее развит Томасом Ковером.

Метод относится к классу непараметрических, т.е. не требует предположений о том, из какого статистического распределения была сформирована обучающее множество. Следовательно, классификационные модели, построенные с помощью метода KNN также будут непараметрическими. Это означает, что структура модели не задаётся жёстко изначально, а определяется данными.

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

Алгоритм

Пусть имеется набор данных, состоящий из n наблюдений X_i (i=1,...,n), для каждого из которых задан класс C_j (j=1,...,m). Тогда на его основе может быть сформировано обучающее множество, все примеры которого представляют собой пары {X_i,C_j}.

Алгоритм KNN можно разделить на две простые фазы: обучения и классификации. При обучении алгоритм просто запоминает векторы признаков наблюдений и их метки классов (т.е. примеры). Также задаётся параметр алгоритма k, который задаёт число «соседей», которые будут использоваться при классификации.

На фазе классификации предъявляется новый объект, для которого метка класса не задана. Для него определяются k ближайших (в смысле некоторой метрики) предварительно классифицированных наблюдений. Затем выбирается класс, которому принадлежит большинство из k ближайших примеров-соседей, и к этому же классу относится классифицируемый объект.

Поясним работу алгоритма с помощью рисунка.

Кружком представлен объект, который требуется классифицировать, отнеся к одному из двух классов «треугольники» и «квадраты». Если выбрать k=3, то из трёх ближайших объектов два окажутся «треугольниками» и один «квадратом». Следовательно новому объекту будет присвоен класс «треугольник». Если задать k=5, то из пяти «соседей» два будут «треугольники» и три «квадраты», в результате классифицируемый объект будет распознан как «квадрат».

Определение класса нового объекта

В простейшем случае класс нового объекта может быть определён простым выбором наиболее часто встречающегося класса среди k примеров. Однако на практике это не всегда удачное решение, например, в случае когда частота появления для двух или более классов оказывается одинаковой. Кроме этого разумно предположить, что не все обучающие имеют одинаковую значимость для определения класса. В этом случае используют некоторую функцию, с помощью которой определяется класс, называемую функцией сочетания (combination function).

В обычном случае используют так называемое простое невзвешенное голосование (simple unweighted voting). При это предполагается, что все k примеров имеют одинаковое право «голоса» независимо от расстояние до классифицируемого объекта.

Однако, логично предположить, что чем дальше пример расположен от классифицируемого объекта в пространстве признаков, тем ниже его значимость для определения класса. Поэтому для улучшения результатов классификации вводят взвешивание примеров в зависимости от их удалённости. В этом случае используют взвешенное голосование (weighted voting).

В основе идеи взвешенного голосования лежит введение «штрафа» для класса, в зависимости от того, насколько относящиеся к нему примеры удалены от классифицируемого объекта. Такой «штраф» представляется как сумма величин, обратных квадрату расстояний от примера j-го класса до классифицируемого объекта (часто данное значение называют показателем близости):

Q_{j}=\sum\limits_{i=1}^{n_{j}}\frac{1}{D^{2}(x,a_{ij})}

где D — оператор вычисления расстояния,x — вектор признаков классифицируемого объекта,a_{ij} — i-й пример j-го класса. Таким образом, «побеждает» тот класс, для которого величина Q_j окажется наибольшей. При этом также снижается вероятность того, что классы получат одинаковое число голосов.

Выбор значения параметра k

Выбор параметра k является важным для получения корректных результатов классификации. Если значение параметра мало, то возникает эффект переобучения, когда решение по классификации принимается на основе малого числа примеров и имеет низкую значимость. Это похоже на переобучение в деревьях решений, когда в них много правил, относящихся к небольшому числу примеров. Если установить k=1, то алгоритм будет просто присваивать любому новому наблюдению метку класса ближайшего объекта.

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

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

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

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

Особенности работы алгоритма

Если значения признаков непрерывные, то в качестве меры расстояния между объектами обычно используется расстояние Евклида, а если категориальные, то может использоваться расстояние Хэмминга.

Алгоритм KNN является чувствительным к дисбалансу классов в обучающих данных: алгоритм «склонен» к смещению решения в сторону доминирующего класса, поскольку относящиеся к нему объекты просто чаще попадают в число ближайших соседей. Одним из способов решения данной проблемы является применение различных способов взвешивания при «голосовании».

Следует отметить, что отношение соседства не является коммутативным, т.е. если для записи B ближайшем соседом является запись A, то это не означает, что B– ближайший сосед A. Данная ситуация представлена на рисунке 2.

При k=1 ближайшей для точки B будет точка A, а для A — точка C. Даже при увеличении коэффициента до k=7, точка B по-прежнему не будет входить в число соседей A.

Ещё одной проблемой алгоритма KNN, характерной, впрочем, и для большинства методов классификации, является различная значимость признаков с точки зрения определения класса объектов. Учет фактора значимости признаков в алгоритме может позволить повысить точность классификации.

Для этого аналитик или эксперт на основе субъективной, либо некоторой формальной оценки может задать уровень значимости признака, выразив его с помощью числового коэффициента (обозначим его s от англ significance — значимость), который учитывается при вычислении расстояния между примерами и классифицируемым объектом:

D_{E}=\sqrt{s_{1}\cdot (x_{1}-a_{1})^{2}+s_{2}\cdot (x_{2}-a_{2})^{2}+...+s_{p}\cdot (x_{p}-a_{p})^{2}}

где s_i (i=1..p) — коэффициент значимости для i-го признака, p — количество признаков исходного набора данных. Такой приём называется растяжением осей и он позволяет увеличить или уменьшить вклад признака в вычисление расстояния от примера до классифицируемого объекта. Если s_i>1, то благодаря соответствующему признаку расстояние между примером классифицируемым объектом растёт и вклад в определение класса падает, а если 0<s_i<1, то наоборот.

Численный пример

Рассмотрим простой численный пример работы алгоритма KNN, проиллюстрированный на рисунке 3.

Пусть имеется набор данных о заёмщиках банка часть из которых допустили просрочку по платежу (таблица 1). Признаками являются возраст и среднемесячный доход. Метками класса в поле «Просрочено» будут «Да» и «Нет».

На рисунке 3 оранжевыми кружками представлены объекты класса «Нет», а фиолетовыми класса «Да». Синим квадратом отображается классифицируемый объект (новый заёмщик).

Задача заключается в том, чтобы выполнить классификацию нового заёмщика для которого A_1=42 и A_2=34 с целью оценить возможность просрочки им платежей.

1. Зададим значение параметра k=3.
2. Рассчитаем расстояние между вектором признаков классифицируемого объекта и векторами обучающих примеров по формуле D(A,X)=\sqrt{(A_{1}-X_{1})^{2}+(A_{2}-X_{2})^{2}} и установим для каждого примера его ранг (таблица 2).
3. Исключим из рассмотрения пример, который при k=3 не является соседом и рассмотрим классы оставшихся (таблица 3).

Таким образом, из трёх ближайших соседей (на рисунке расположены внутри круга) классифицируемого объекта два имеют класс «Да», а один — «Нет». Следовательно, путём простого невзвешенного голосования определяем его класс как «Да». На основании работы классификатора делаем вывод, что заёмщик с заданными характеристиками может допустить просрочку по выплате кредита.

Области применения алгоритма

Алгоритм KNN может применяться практически во всех задачах классификации, особенно в тех случаях, когда оценить параметры вероятностного распределения данных сложно или невозможно. Наиболее типичными приложениями алгоритма KNN являются:

• классификация клиентов (например, по уровню лояльности);
• медицина — классификация пациентов по медицинским показателям;
• маркетинг — классификация товаров по уровню популярности и т.д.

Достоинства и недостатки алгоритма

В заключение отметим достоинства и недостатки алгоритма KNN. К достоинствам алгоритма можно отнести.

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

К недостаткам алгоритм KNN можно отнести:

• данный метод не создает каких-либо моделей, обобщающих предыдущий опыт, а интерес могут представлять и сами правила классификации;
• при классификации объекта используются все доступные данные, поэтому метод KNN является достаточно затратным в вычислительном плане, особенно в случае больших объёмов данных;
• высокая трудоёмкость из-за необходимости вычисления расстояний до всех примеров;
• повышенные требования к репрезентативности исходных данных.

Литература

Другие материалы по теме:

Деревья решений - C4.5 математический аппарат | Часть 2

Классификация данных при помощи нейронных сетей