Классификация по ближайшему соседу

Предположим, что имеются образцы, полученные для каждого класса. Пусть x_i,j - вектор признаков для j-го образца i-го класса. Один из возможных путей для классификации неизвестного вектора х заключается в нахождении образца, ближайшего к неизвестному, и определении класса, к которому он относится. Для некоторых k и l это означает, что если |x_k,l -x|<|х_i,j - x| для всех i и j, то неизвестный х принадлежит классу k.

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

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

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

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

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

Классификация по ближайшей центроиде

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

Использование этого метода позволяет значительно уменьшить и память, и вычисления. Более того, классы здесь разделяются гладкими границами. Отметим, что эти компоненты являются гипермногогранниками, ограниченными гиперплоскостями. (Гипермногогранники — это обобщение выпуклого многогранника для числа измерений больше трех. Они образуются пересечением полупространств.) Чтобы показать, что границы являются гиперплоскостями, предположим, что х — точка на границе между частями, содержащими центроиды и , тогда . Возведя в квадрат обе части равенства, получим или . Это уравнение линейно по х. Оно описывает гиперплоскость с нормалью , проходящую через точку . Таким образом, границей является гиперплоскость, ортогонально секущая пополам отрезок, соединяющую две центроиды.

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

Рис. 1. Диаграмма разброса площадей цитоплазмы и ядра для пяти типов белых кровяных телец. Буква обозначает различные классы, подчеркнутая буква — центроиду. Штриховые линии показывают линейные границы, оптимально разделяющие классы. Несколько образцов классифицировано неверно.