tgoop.com/artificial_stupid/291
Last Update:
#statistics
Прекращайте использовать метод локтя в k-means.
Так называется недавно вышедшая статья от автора из университета Дортмунда. Немного кликбейтный заголовок, но статья весьма интересная.
Итак, как выглядит метод локтя?
1. Строим много кластеризаций k-means с разным количеством k;
2. Для каждого отдельного k считаем сумму квадратов внутрикластерных расстояний до центра кластера (within-cluster sum of squares, WCSS). Для sklearn это будет атрибут inertia_.
3. "На глаз" выбираем такое k, где у нас происходит "перегиб" (отсюда и метод локтя) и WCSS перестает существенно уменьшаться. Это и будет итоговым числом кластеров k.
У такого метода есть один некоторые минусы, например, выбор k "на глаз". Потому в разных работах предлагались методы автоматизации метода локтя.
Как можно улучшить метод?
1. Jump method. Давайте искать максимум SSE_k ** -Y - SSE_k ** -Y, где степень Y может варьироваться, но авторы предлагают брать Y=1/2 * dimensionality (то есть половина от размерности пространства признаков).
2. L-method. Возьмем две линейных функции (перед перегибом и после). Выберем лучшую кусочно-линейную аппроксимацию.
3. Kneedle algorithm. Возьмем полиномиальную кривую (сплайн), нормализуем от 0 до 1. Сравним с диагональю. Берем последний максимум перед задаваемым threshold.
4. Улучшение шага 3. Давайте искать максимум для SSE_k-1 - SSE_k / (SSE_k - SSE_k+1) - 1.
5. В библиотеке pyclustering используется метод ElbowLen, которые считается (x_k*(y_0 - y_1) + (x_1 - x_0)*y_k + (x_0*y_1 - x_1*y_0)) / (sqrt((x_1 - x_0)**2 + (y_1 - y_0)**2)), где x0, x1, y0, y1 - минимумы и максимумы графика.
6. AutoElbow. Вычисляем ((x_k - 1)**2 + (y_k - 1)**2) / (x_k ** 2 * y_k **2) на нормализованном на [0,1] графике.
Все эти методы не лишены минусов. В статье приводятся примеры для разных наборов данных. Общий вывод - на достаточно разделимых кластерах и небольшом k все работает более или менее неплохо. Но если мы отходим немного от тепличных условий, все становится весьма плохо.
Мы можем отойти от эвристик над методом локтя и прочих геометрических манипуляций в сторону вариационных методов (предполагается, что они более теоретически обоснованы). В статье по ним проходятся весьма поверхностно, так что некоторые из них я не совсем понял ¯\_(ツ)_/¯
1. Variance Ratio Criterion (VRC). Считаем ((SSE_1 - SSE_k) / (k - 1)) / (SSE_k / (n-k)). Авторы рассматривают это, как некий аналог F-статистики.
2. Метод Mariott. Рассматривается детерминант ковариационной матрицы |W|.
3. KL-index. Давайте рассмотрим DIFF_k = (k - 1)**(2/p)*SSE_k-1 - k**(2/p)*SSE_k. Потом ищем максимум KL(k) = |DIFF_k / DIFF_k+1|.
4. Метод Pham. Считаем SSE_k / (alpha_k * SSE_k-1), где alpha_2 = 1 - 3/(4*d) и alpha_k = 5/6 * alpha_k-1 + 1/6 (что моделирует ожидаемое изменение равномерного распределения).
Учитывая задачу кластеризации, можно придумать и критерии, основанные на расстояниях.
1. DUNN index.
2. David-Bouldin index.
3. Silhouette score.
Но это не все. Мы еще можем использовать теоретические подходы, основанные на теории информации.
1. Bayesian information criterion (BIC).
2. Akaike Information Criterion (AIC).
Ну и, напоследок, еще можно использовать симуляционный критерий.
1. В данном случае, мы считаем GAP_k = E[log(SSE'_k)] - log(SSE_k). И выбираем наименьший k, где GAP_k >= GAP_k-1 - std_k+1. Где SSE'_k - базовый SSE, а std_k+1 - среднеквадратичное отклонение оценок.
А какой итоговый вывод?
Не использовать метод локтя. Предпочитаемыми методами авторы считают VRC (реализация sklearn), Bayesian Information Criterion (BIC) (материал с реализацией) или симуляционный критерий (GAP-статистику, материал с реализацией).
BY Artificial stupidity
Share with your friend now:
tgoop.com/artificial_stupid/291