Алгоритм к-ближайших соседей

Алгоритм к-ближайших соседей использует гипотезу компактности векторного пространства, которая заключается в том, что документы одного класса образуют в пространстве терминов компактную область, причём области разных классов не пересекаются. Тогда можно ожидать, что тестовый документ будет иметь такую же метку класса, как и окружающие его документы из обучающего множества. Алгоритм к-ближайшего соседа относит тестовый документ к преобладающему классу его к соседей. При к = 1 алгоритм относит документ к классу, самого ближайшего ему документа.

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

Рис. 4.6. Иллюстрация работы алгоритма к-ближайших соседей

Это в случае к = 1. В случае к> 1 внутри ячеек также множество к- ближайших соседей остаётся инвариантным. На рис. 4.7 видно, что новый документ «звёздочка» попадает в ячейку объекта класса «треугольников», и при к = 1 будет отнесён к этому же классу. Однако при к =3 «звёздочка» будет отнесён к классу «кружочков». При к = 1 алгоритм неустойчив, так как классификация зависит всего от одного обучающего документа, а он может быть нетипичным или иметь неверную метку класса. На практике значение к выбирают на основе опыта эксперта и имеющихся знаний о решаемой задаче. Кроме того, число соседей можно подобрать на обучающем множестве так, чтобы максимизировать качество классификации.