Большая картинка
Машинное обучение - это наука о создании надежных прогнозов выходных данных для входных данных, которые машина никогда раньше не видела. Он состоит из трех основных этапов:
- Составление обучающего набора. Обучающие наборы содержат образцы (точки данных), так что каждая выборка классифицируется в группу, или набор должен пройти определенную процедуру для классификации своих выборок перед переходом к следующему этапу. Эта процедура отличает обучение с учителем от обучения без учителя.
- Создание модели и передача ей классифицированного обучающего набора.
- Доработка модели.
Давайте посмотрим, как это вписывается в общую картину:
- Машинное обучение направлено на создание модели, которая может принимать решения в отношении новых входных данных.
- В модель подается обучающий набор. Обычно представлены набором образцов (строк), каждая из которых описывается набором характеристик (столбцов).
- Если образцы обучающего набора помечены (существует последняя функция, определяющая, к какому классу принадлежит каждый образец), процедура обучения контролируется. В противном случае - без присмотра.
- В случае обучения без учителя мы должны классифицировать каждый образец перед тем, как передать его модели.
- Этот процесс категоризации называется кластеризацией. Формально: кластеризация - это процесс, после которого наши образцы классифицируются по группам, так что образцы в одной группе похожи друг на друга, чем другие образцы в разных группах.
- Существуют различные типы алгоритмов кластеризации, каждый из которых имеет свои сильные и слабые стороны.
- Один конкретный тип кластеризации называется многораздельной кластеризацией.
- Разделенная кластеризация делит образцы на неперекрывающиеся группы. То есть ни одна выборка не может быть членом более чем одного кластера, и каждый кластер должен иметь хотя бы одну выборку.
- Наш интересующий алгоритм (кластеризация K-средних) является широко известной техникой секционированной кластеризации.
Это было много для понимания. Не стесняйтесь перечитывать вышесказанное несколько раз, пока не почувствуете это.
K-means: Подробнее
Как это работает
Основная идея k-средних состоит в том, чтобы установить 𝑘 точек (выборок) в качестве наших центроидов, и каждый из этих центроидов будет перемещаться, пытаясь сосредоточиться в середине одного из 𝑘 кластеров. у нас есть.
Псевдокод
- Из данного набора данных случайным образом выберите 𝑘 точек в качестве начальных выбранных нами центроидов.
- Установите ближайший центроид каждой точки как ее метку.
- Возьмите среднее значение точек, принадлежащих каждому центроиду, и установите его как новое значение центроида.
- Остановитесь при схождении. То есть новые центроиды равны старым центроидам. В противном случае установите старые центроиды на значения новых центроидов и повторите шаги со 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.
За и против
Плюсы
- Простота и популярность.
- Гарантирует сходимость. "Доказательство".
- Служит хорошей оценкой начального положения центроидов.
Минусы
- Необходимо указать количество кластеров 𝑘.
- Зависит от случайных начальных значений, что может привести к противоречивым результатам между разными запусками.
- Некоторые данные необходимо масштабировать перед кластеризацией.
Ссылки
- Как работает кластеризация K-средних в машинном обучении? Автор Анас Аль-Масри.
- Глубоко: К-означает кластеризацию, Джейк Вандерплас.
- K-means Clustering in Python: A Practical Guide, Кевин Арвай.
- Алгоритм K-средних с нуля, Рама Салахат.