Несколько полезных настроек для K-средних
При использовании K-средних мы можем столкнуться с двумя проблемами:
- В итоге мы получаем кластеры очень разных размеров, одни из которых содержат тысячи наблюдений, а другие - всего несколько
- В нашем наборе данных слишком много переменных, и алгоритм K-средних изо всех сил пытается определить оптимальный набор кластеров.
Ограниченные K-средние: контроль размера группы
Алгоритм основан на статье Bradley et al. и был реализован Джошуа Леви-Крамером: https://github.com/joshlk/k-means-constrained с использованием превосходной библиотеки Google OR-Tools (https://developers.google.com/optimization/ расход / минимальный расход )
В алгоритме используются идеи из линейного программирования, в частности Сетевые модели. Сетевые модели используются, среди прочего, в логистике для оптимизации потока товаров по сети дорог.
На приведенном выше простом рисунке видно, что у нас есть 5 узлов с направленными дугами (стрелки) между ними. Каждый узел имеет значение спроса (отрицательное) или предложение (положительное), а дуги имеют значения расхода и стоимости. Например, дуга 2–4 имеет поток 4 и стоимость 2 доллара. Точно так же узел 1 поставляет 20 единиц, а узел 4 требует 5 единиц.
Эти проблемы могут быть решены с помощью алгоритмов оптимизации, таких как симплексный алгоритм.
На очень высоком уровне мы можем представить эту ограниченную задачу K-средних с помощью сети, где мы хотим минимизировать сумму расстояний между каждой точкой и центроидом ее кластера, с некоторыми ограничениями на размеры кластера.
Мы можем увидеть, как это будет выглядеть на рисунке ниже. Каждая точка x (i) является узлом снабжения со значением, равным единице, и направленной дугой для каждого отдельного кластера C. Стоимость этих дуг - это расстояние между точкой и центроидом соответствующего кластера. Кластеры C1, C2 и т. Д. Являются кластерами спроса со значениями, равными минимальному требуемому размеру. Наконец, мы добавляем искусственный узел спроса, чтобы убедиться, что сумма поставок равна сумме потребностей.
Более подробное объяснение можно найти в исходной статье.
Реализация Python
Пакет был разработан Джошуа Леви-Крамер и другими, он доступен здесь.
Может быть установлен с помощью пипа
pip install k-means-constrained
А затем, легко применив его к набору данных, мы повторно воспользуемся одним из предыдущих статей, но нам нужно преобразовать наш фреймворк pandas в массив.
X=np.array(X).transpose()
А затем мы можем подогнать метод KMeansConstrained к данным с желаемым количеством кластеров (n_clusters), минимальным и максимальным размером кластеров (size_min и size_max).
from k_means_constrained import KMeansConstrained
clf = KMeansConstrained(
n_clusters=4,
size_min=8,
size_max=12,
random_state=0
)
clf.fit_predict(X)print(clf.cluster_centers_)
print(clf.labels_)
Затем мы можем получить доступ к центроидам с помощью clf.cluster_centers_ и кластерам с помощью clf.labels_
Как мы видим ниже, мы получаем 4 кластера по 8 элементов в каждом.
В этом примере мы использовали набор данных с двумя функциями, поэтому он может быть хорошо визуализирован на 2D-диаграмме рассеяния. В большинстве случаев мы будем иметь дело с наборами данных с большим количеством функций. Работа с ними в контексте кластеризации будет рассмотрена в следующем разделе.
Выбор функций для K-средних
В этом разделе мы увидим, как выбирать переменные, когда мы имеем дело с наборами данных, содержащими большое количество переменных. Уменьшение размеров обычно помогает найти лучшие кластеры.
Когда мы имеем дело с наборами данных большой размерности, мы можем столкнуться с проблемами при использовании методов кластеризации. Выбор функций - это хорошо известный метод обучения с учителем, но гораздо меньше для методов обучения без учителя (например, кластеризации). Здесь мы разработаем относительно простой жадный алгоритм для выполнения выбора переменных в наборах данных Европы на Kaggle.
Алгоритм будет состоять из следующих этапов:
0. Убедитесь, что переменная числовая и масштабируется, например, с помощью StandardScaler () и его метода fit_transform ().
- Выберите максимум переменных, которые вы хотите сохранить (maxvars), минимальное и максимальное количество кластеров (kmin и kmax) и создайте пустой список: selected_variables.
- Цикл от kmin до kmax. Затем, используя каждую переменную по очереди, запишите значение силуэта для каждой комбинации переменной и количества кластеров (от kmin до kmax) с помощью K-средних.
- Выберите переменную, дающую максимальное значение силуэта, добавьте ее в selected_variables и удалите из списка переменных для проверки.
- Повторите процесс для пунктов 2 и 3, используя список selected_variables и добавляя к нему по очереди каждую оставшуюся переменную, пока не будет достигнут некоторый критерий остановки (в данном случае количество сохраняемых переменных maxvars).
Итак, для шага 1 мы определяем и инициализируем некоторые переменные.
maxvars=3
kmin=2
kmax=8kmeans_kwargs = {"init": "random","n_init": 20,"max_iter": 1000,"random_state": 1984}
cut_off=0.5
# We define a cols variables containing a list of all features:
cols=list(df.columns)
'''We set a list and a dictionary to store the silhouette values
for each number of clusters tested so we can choose the k value
maximising the silhouette score, with its corresponding features'''
results_for_each_k=[]
vars_for_each_k={}
Затем мы создаем три вложенных цикла, во внешнем цикле проверяются значения k, количества кластеров. Затем у нас есть цикл while, проверяющий, что количество сохраненных переменных ниже порога, установленного maxvars. Список selected_variables будет содержать имена сохраненных функций. Список результаты будет содержать значения силуэтов для каждой переменной.
for k in range(kmin,kmax+1):
selected_variables=[]
while(len(selected_variables)<maxvars):
results=[]
selected_variables=[]
print(k)
while(len(selected_variables)<maxvars):
results=[]
Внутренний цикл проходит по всем элементам один за другим, добавляет их к уже выбранным переменным, если они есть, и оценивает значения силуэтов. Затем он выбирает переменную, получающую наибольшее значение, и добавляет ее в список selected_variables.
for col in cols:
scols=[]
scols.extend(selected_variables)
scols.append(col)
kmeans = KMeans(n_clusters=k, **kmeans_kwargs)
kmeans.fit(df[scols])
results.append(silhouette_score(df[scols], kmeans.predict(s)))
''' We identify the best variable, add it to our list and remove it
from the list of variables to be tested on the next iteration '''
selected_var=cols[np.argmax(results)]
selected_variables.append(selected_var)
cols.remove(selected_var)
Затем мы можем обновить списки переменных и оценки для этого конкретного значения k в нашем цикле.
results_for_each_k.append(max(results)) vars_for_each_k[k]=selected_variables
Наконец, после прохождения трех циклов мы можем определить лучшую комбинацию k и переменных, подобрать модель и построить ее.
best_k=np.argmax(results_for_each_k)+kmin selected_variables=vars_for_each_k[best_k] kmeans = KMeans(n_clusters=best_k, **kmeans_kwargs) kmeans.fit(df_[selected_variables]) clusters=kmeans.predict(df[selected_variables])
Если мы выберем 3 кластера, мы получим другой выбор
Некоторые примеры стран в каждой группе:
Кластер1: Исландия, Швейцария, Бельгия, Германия, Люксембург, Нидерланды, Австрия и Великобритания.
Кластер 2: Греция, Испания, Франция, Хорватия, Италия, Кипр, Латвия, Литва, Венгрия, Мальта, Польша, Португалия.
Кластер 3: Норвегия, Дания, Финляндия и Швеция.
Вот весь код, включая трехмерный сюжет.
Конечно, мы можем комбинировать выбор переменной с алгоритмом K-средних с ограничениями, чтобы получить четные кластеры.
Я надеюсь, что это руководство было полезным, не стесняйтесь комментировать, если у вас есть вопросы.
Ссылки
П. С. Брэдли, К. П. Беннетт и А. Демириз, Ограниченная кластеризация K-средних (2000)
Брэдли, Хакс и Маньянти, Прикладное математическое программирование, Эддисон-Уэсли (1977)
