Перейти к основному содержимому

Метод ближайших центроидов

Идея метода​

Метод ближайших центроидов (nearest centroids) решает задачу классификации. Рассмотрим демонстрационную обучающую выборку из двумерных объектов, разбитые на три класса. Класс объектов будем обозначать цветом.

centroids-data.png

Обучение метода заключается в вычислении центроидов для каждого класса.

μc=1Nc∑n:yn=cxn\bm{\mu}_{c}=\frac{1}{N_{c}}\sum_{n: y_{n}=c}\mathbf{x}_{n}

Ниже они обозначены крестиками соответствующего цвета.

centroids-centroids.png

На этапе предсказания класса для объекта x\mathbf{x} вычисляются расстояния до каждого из центроидов. Объекту назначается тот класс, расстояние до которого меньше всего:

y^(x)=arg min⁡cρ(x,μc)\hat{y}(\mathbf{x})=\argmin_{c}\rho(\mathbf{x},\bm{\mu}_{c})
Чему равны дискриминантные функции для этого метода?

Дискриминантная функция каждого из классов вычисляет рейтинг соответствующего класса - чем выше, тем класс более вероятен. Поэтому дискриминантная функция каждого класса будет равна расстоянию от x\mathbf{x} до центроида соответствующего класса со знаком минус (либо любой другой убывающей функции от расстояния).

Разбиение методом ближайших центроидов для демонстрационного примера приведено ниже:

centroids-regions.png

Как видим, границы между классами представляют собой прямые линии.

Всегда ли границы между классами будут линейными гиперплоскостями?

Границы между классами i и j задаются условием {x:gi(x)=gj(x)}\{\mathbf{x}: g_i(\mathbf{x})=g_j(\mathbf{x})\}, что в случае метода ближайших центроидов будет {x:ρ(x,μi)=ρ(x,μj)}\{\mathbf{x}: \rho(\mathbf{x},\bm{\mu}_i)=\rho(\mathbf{x},\bm{\mu}_j)\}. Это всегда будет линейной гиперплоскостью, если использовать Евклидову функцию расстояния.

Варианты усложнения метода​

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

За счет того, что сравнение x\mathbf{x} происходит лишь с центроидами, а не со всеми объектами выборки, прогноз будет строиться быстро. Однако метод способен выделять лишь выпуклые формы кластеров, поэтому в общем случае будет работать неточно. Его можно использовать как бейзлайн (простой метод задающий нижнюю границу на точность), а также усложнить, характеризуя каждый класс не одним центроидом, а сразу несколькими в разных позициях.

Также метод можно обобщить, используя различные функции вычисления расстояния.

Пример запуска в Python​

Метод ближайших центроидов:
from sklearn.neighbors import NearestCentroid
from sklearn.metrics import accuracy_score

X_train, X_test, Y_train, Y_test = get_demo_classification_data()  
model = NearestCentroid()      # инициализация модели
model.fit(X_train,Y_train);    # обучение модели
Y_hat = model.predict(X_test)  # построение прогнозов
print(f'Точность прогнозов: {100*accuracy_score(Y_test, Y_hat):.1f}%')

Больше информации. Полный код.