Главная > Интеллектуальные системы > Зрение роботов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

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

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

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

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

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление