python kmeans

python-kmeans

реализация кластеризации k-средних на Python. k-средние — это метод обучения без учителя, который пытается сгруппировать похожие точки данных в указанное пользователем количество групп. В приведенном ниже примере показано развитие кластеров для набора данных Iris с использованием алгоритма инициализации центроида k-means++.

Описание

k-means пытается идентифицировать указанное пользователем количество k(<N) кластеров из набора N d-мерных векторов с действительными значениями. Алгоритм пытается минимизировать сумму квадратов расстояний от центра кластера до его членов. Канонический алгоритм состоит из трех этапов:

1. Инициализировать k случайных центроидов (центров кластеров);
2. назначить точки данных ближайшему кластеру в соответствии с метрикой расстояния (обычно евклидово расстояние);
3. обновить центроиды до среднего значения членов кластера;
4. повторяйте шаги 2 и 3 до тех пор, пока назначения из шага 2 не изменятся.

Результатом работы алгоритма является назначение кластера для каждой точки данных и окончательный уровень «искажения». Алгоритм не дает доказуемо оптимального решения, а начальные центры кластеров могут привести к тому, что алгоритм застрянет в локально оптимальном решении, которое явно неоптимально (см. базовый 2d-пример в разделе «Результаты»).

Многие исследования были сосредоточены на:

• выбор начальных центров кластеров. K-Means++ — это хорошо известный метод, включенный в эту реализацию. Алгоритм описан в следующем подразделе.
• вычисление расстояний, т.е. использование мер, отличных от евклидовых, см. здесь.

K-средние++

Вместо инициализации случайных центроидов, как на шаге 1 выше, k-means++ вероятностно распределяет начальные центроиды, чтобы избежать плохой начальной конфигурации, алгоритм следующий:

1. Случайным образом выберите первый центроид.
2. Для каждой точки данных x вычислите расстояние d(x) от x до ближайшего центроида, который уже был выбран.
3. Выберите точку данных, которая будет следующим центроидом, используя взвешенную вероятность, пропорциональную d(x)2.

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

Ресурсы

Основной алгоритм

• K-Means описано в «10 лучших алгоритмах интеллектуального анализа данных»;

• K-средние описаны в книге «Теория информации, умозаключение и алгоритмы обучения», отрывок здесь;

• Профессор Эндрю Мур из CMU сделал здесь несколько хороших замечаний;

• Пример Эдуреки с использованием данных о преступности

Инициализация кластеров

• K-Means++ и полная статья здесь

• Сравнительное исследование эффективных методов инициализации алгоритма кластеризации K-средних

Почему бы не использовать SciPy?

В SciPy есть реализация k-средних. Цель этой работы — создать чистую реализацию Python для целей обучения и помочь другим изучить алгоритм k-средних. Заинтересованные читатели с минимальным опытом работы с Python смогут прочитать и изучить этот код без усложнения такой библиотеки, как SciPy. Он ни в коем случае не предназначен для производственного использования :)

Запуск кода

Зависимости

• питон 3.6.3
• matplotlib 2.1.1 — инструкции по установке см. здесь.

Исполнение

Запустите код с помощью интерпретатора Python:

python kmeans.py ./resources/<config.cfg>

Где config.cfg — это текстовый файл конфигурации. Формат файла конфигурации — это словарь Python со следующими полями:

 {
   'data_file' : '\resources\iris.csv',
   'data_project_columns' : ['sepal_length','sepal_width','petal_length','petal_width','class'],
   'k' : 3,
   'cluster_atts' : ['sepal_length','sepal_width','petal_length','petal_width'],
   'init_cluster_func' : 'kmeans_plus_plus',
   'plot_config' :
    {'output_file_prefix' : 'iris',
     'plots_configs': [
        {'plot_atts' : ['sepal_length','sepal_width']},
        {'plot_atts' : ['sepal_length','petal_length']},
        {'plot_atts' : ['sepal_length','petal_width']},
        {'plot_atts' : ['sepal_width','petal_length']},
        {'plot_atts' : ['sepal_width','petal_width']},
        {'plot_atts' : ['sepal_width','petal_width']}
     ]
   }
}

Вам необходимо указать:

• файл данных csv;
• подмножество полей для проецирования из файла;
• количество образуемых кластеров, k;
• подмножество атрибутов, используемых в процессе кластеризации;
• опционально указать начальную функцию кластера (по умолчанию='rand_init_centroids'), заинтересованные авторы могут добавить свою собственную в код и указать ее здесь;
• конфигурация графика, которая включает в себя
  • префикс для созданных в процессе png-файлов в рабочем каталоге, если он не указан, изображения создаваться не будут;
  • индивидуальные конфигурации графиков, ограниченные двумя измерениями на график.

Результаты

Набор данных радужной оболочки

Набор данных Iris (iris.config), от Личмана, М. (2013). Репозиторий машинного обучения UCI. Ирвин, Калифорния: Школа информатики и компьютерных наук Калифорнийского университета. Это очень известный набор данных в сообществе машинного обучения. Вот результаты моих случайных начальных кластеров:

Базовые синтетические 2D-данные

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

Преступление

Набор данных о преступлениях (crime.config) взят из Edureka, здесь.