Большая картинка

Машинное обучение - это наука о создании надежных прогнозов выходных данных для входных данных, которые машина никогда раньше не видела. Он состоит из трех основных этапов:

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

Давайте посмотрим, как это вписывается в общую картину:

  • Машинное обучение направлено на создание модели, которая может принимать решения в отношении новых входных данных.
  • В модель подается обучающий набор. Обычно представлены набором образцов (строк), каждая из которых описывается набором характеристик (столбцов).
  • Если образцы обучающего набора помечены (существует последняя функция, определяющая, к какому классу принадлежит каждый образец), процедура обучения контролируется. В противном случае - без присмотра.
  • В случае обучения без учителя мы должны классифицировать каждый образец перед тем, как передать его модели.
  • Этот процесс категоризации называется кластеризацией. Формально: кластеризация - это процесс, после которого наши образцы классифицируются по группам, так что образцы в одной группе похожи друг на друга, чем другие образцы в разных группах.
  • Существуют различные типы алгоритмов кластеризации, каждый из которых имеет свои сильные и слабые стороны.
  • Один конкретный тип кластеризации называется многораздельной кластеризацией.
  • Разделенная кластеризация делит образцы на неперекрывающиеся группы. То есть ни одна выборка не может быть членом более чем одного кластера, и каждый кластер должен иметь хотя бы одну выборку.
  • Наш интересующий алгоритм (кластеризация K-средних) является широко известной техникой секционированной кластеризации.

Это было много для понимания. Не стесняйтесь перечитывать вышесказанное несколько раз, пока не почувствуете это.

K-means: Подробнее

Как это работает

Основная идея k-средних состоит в том, чтобы установить 𝑘 точек (выборок) в качестве наших центроидов, и каждый из этих центроидов будет перемещаться, пытаясь сосредоточиться в середине одного из 𝑘 кластеров. у нас есть.

Псевдокод

  1. Из данного набора данных случайным образом выберите 𝑘 точек в качестве начальных выбранных нами центроидов.
  2. Установите ближайший центроид каждой точки как ее метку.
  3. Возьмите среднее значение точек, принадлежащих каждому центроиду, и установите его как новое значение центроида.
  4. Остановитесь при схождении. То есть новые центроиды равны старым центроидам. В противном случае установите старые центроиды на значения новых центроидов и повторите шаги со 2 по 4.

Примечание: исходные выбранные центроиды не обязательно должны быть фактическими выборками.

Анализ сложности

K-средство имеет временную сложность 𝑂 (pkif) и пространственную сложность:
𝑂 ((p + 𝑘) f). Мы здесь:

  • p: количество баллов.
  • 𝑘: количество кластеров.
  • i: количество итераций до сходимости.
  • f: количество функций.

Реализация

Реализация указанного выше псевдокода на Python:

K-means: в действии

Создание фиктивных данных

Давайте воспользуемся описанной выше реализацией. Во-первых, мы воспользуемся утилитой make_bloks из модуля sklearn.datasets, чтобы сгенерировать фиктивные сэмплы и распределить их между кластерами.

dataset, true_labels = make_blobs(
   n_samples=300,
   n_features=2,
   centers=4,
   cluster_std=.6,
   random_state=0
)

Здесь мы говорим нашей функции сгенерировать 300 выборок, каждая с 2 функциями, распределенными по 4 кластерам, и со стандартным отклонением кластера (интервалом между кластерами) 0,6. Аргумент random_state - это начальное число случайности (полезно для создания одного и того же набора данных из разных прогонов). Он возвращает набор данных и true_labels его образцов (полезно для проверки нашей реализации позже).

Построение набора данных

second_feature_vals, first_feature_vals = np.rot90(dataset)
plt.scatter(first_feature_vals, second_feature_vals)
plt.title("Scatter Plot of Dummy Data Generated by make_blobs Utility")
plt.xlabel("First Feature")
plt.ylabel("Second Feature")
plt.show()

Мы извлекаем значения первой и второй характеристик отдельно, затем рисуем их диаграмму рассеяния, используя matplotlib.pyplot. Полученный сюжет:

Глядя на сгенерированный график рассеяния, мы можем сделать вывод, что установка 𝑘 на 4 кластера звучит достаточно разумно. Мы также уверены, что это точное количество кластеров, поскольку мы установили его равным 4, когда создавали наши капли с помощью make_blobs.

Запуск нашей реализации

labels = k_means(dataset, 4)
plt.subplot(1, 2, 1)
plt.scatter(first_feature_vals, second_feature_vals, c=labels)
plt.title("Our Implementation Generated Labels")
plt.subplot(1, 2, 2)
plt.scatter(first_feature_vals, second_feature_vals, c=true_labels)
plt.title("The True Labels of the Dataset")
plt.subplots_adjust(right=2, wspace=0.2)
plt.show()

Рисуем 2 точечных графика:

  • Один передает ему метки, созданные в нашей реализации,
  • а другой передает ему true_labels, сгенерированный ранее утилитой make_blobs.

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

Для полной реализации и экспериментов с реальными данными посетите это репозиторий GitHub.

За и против

Плюсы

  • Простота и популярность.
  • Гарантирует сходимость. "Доказательство".
  • Служит хорошей оценкой начального положения центроидов.

Минусы

  • Необходимо указать количество кластеров 𝑘.
  • Зависит от случайных начальных значений, что может привести к противоречивым результатам между разными запусками.
  • Некоторые данные необходимо масштабировать перед кластеризацией.

Ссылки