Введение в Unsupervised learning

Автор: | 01.02.2022

Введение 
Обзор методов кластеризации
Пример секционной кластеризации (K-Means и K-Nearest Neighbors)
Пример иерархической кластеризации (агломеративная и разделительная)
Пример кластеризации на основе плотности (DBSCAN)
Метод главных компонент
Полезные ссылки

Введение

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

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

Неконтролируемое обучение — самообучение машин  без необходимости в явном указании, правильно ли все, что они делают, является ключом к «настоящему искусственному интеллекту».

Наиболее известными методами обучения без учителя являются кластеризация данных и анализ основных компонентов.

Кластеризация (англ. cluster analysis) — это не что иное, как деление на разные группы. Элементы одной группы похожи друг на друга. И предметы в разных группах непохожи друг на друга. Задача группировки множества объектов на подмножества (кластеры) таким образом, чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.

Кластеризация, в отличие от классификации, подразумевает организацию данных без явно определяемых для этого признаков. Здесь существенные признаки автоматически выделяются из множества признаков, неявно заложенных в данных — например, в результате частоты их повторяемости.

Разница заключается в том, как оба работают. Классификация — это контролируемый алгоритм, в котором каждой точке входных данных (Xi) присваиваются предопределенные метки (yi). Кластеризация — это неконтролируемый алгоритм, в котором метки отсутствуют.

Анализ основных компонентов (англ. Principal Components Analysis, PCA) позволяет визуализировать сложный набор данных в пространстве меньшего размера. Мы можем исключить избыточные признаки. Таким образом, мы можем уменьшить исходное пространство признаков до более низкого размерного пространства, что значительно уменьшает вычислительные ресурсы. Мы можем использовать его как метод выбора признаков.

Обзор методов кластеризации

Три популярные категории алгоритмов кластеризации:

  1. Секционная кластеризация (Partitional Clustering)
  2. Иерархическая кластеризация (Hierarchical Clustering)
  3. Кластеризация на основе плотности (Density-Based Clustering)

Секционная кластеризация делит объекты данных на непересекающиеся группы. Другими словами, ни один объект не может быть членом более чем одного кластера, и в каждом кластере должен быть хотя бы один объект.

Иерархическая кластеризация определяет назначения кластеров путем построения иерархии. Это реализуется либо восходящим, либо нисходящим подходом:

  • Агломеративная кластеризация — это восходящий подход. Он объединяет две наиболее похожие точки до тех пор, пока все точки не будут объединены в один кластер.
  • Разделительная кластеризация — это нисходящий подход. Он начинается со всех точек как одного кластера и разбивает наименее похожие кластеры на каждом шаге, пока не останутся только отдельные точки данных.

Кластеризация на основе плотности определяет кластеры там, где есть высокая плотность точек данных, разделенных областями с низкой плотностью.

Примеры секционной кластеризации (K-Means и K-NN)

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

Чтобы использовать кластеризацию K-средних, пользователю необходимо присвоить значение K, которое соответствует количеству кластеров в наборе данных. Алгоритм (на примере с K = 2):

  1. Случайным образом создает 2 центроида (звездочки на рис. B).
  2. Генерирует 2 кластера, сопоставляя каждую точку данных с ее ближайшим центроидом (красные и синие квадраты в B).
  3. Вычисляет новые центроиды для каждого из 2 кластеров (C).
  4. Переназначает точки данных, используя новый набор центроидов (C).
  • Если есть какие-либо новые назначения, возвращается к шагу 3
  • Если новых назначений не происходит, алгоритм завершает работу (D)

Основным ограничением K-Means является то, что он требует, чтобы пользователь заранее знал количество кластеров, связанных с данными. Однако определение базового количества кластеров является сложной задачей. Один из подходов, пытающихся решить эту проблему, основан на внутрикластерной сумме квадратов (Cluster Sum of Squares, WCSS). Нужно определить WCSS для диапазона номеров кластеров и построить график зависимости WCSS от номера кластера. Затем K выбирается в качестве номера кластера, соответствующего изгибу графика, или номера кластера, после которого падение WCSS начинает затухать.

K-means Clustering Python Example

from matplotlib import pyplot as plt
from sklearn.datasets.samples_generator import make_blobs
from sklearn.cluster import KMeans

X, y = make_blobs(n_samples=300, centers=4,
                 cluster_std=0.60, random_state=0)
plt.scatter(X[:,0], X[:,1])
plt.show()
wcss = []
for i in range(1, 11):
    kmeans = KMeans(n_clusters=i, init='k-means++',
                   max_iter=300, n_init=10, random_state=0)
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)
plt.plot(range(1, 11), wcss)
plt.title('Elbow Method')
plt.xlabel('Number of clusters')
plt.ylabel('WCSS')
plt.show()
kmeans = KMeans(n_clusters=4, init='k-means++',
               max_iter=300, n_init=10, random_state=0)
pred_y = kmeans.fit_predict(X)
plt.scatter(X[:,0], X[:,1])
plt.scatter(kmeans.cluster_centers_[:, 0],
           kmeans.cluster_centers_[:, 1], s=300, c='red')
plt.show()

 

Алгоритм K-NN (K-Nearest Neighbors) позволяет соотнести новые данные к определенной категории:

По заданному нечетному числу K (обычно более 5) находим K ближайших соседа (через расстояние Евклида).  Из какой категории соседей окажется больше, к той и относим новые данные. Иллюстрация для примера с 3 категориями и K=7:

k nearest neighbors Python Example

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn import neighbors, datasets

n_neighbors = 5

# import some data to play with
iris = datasets.load_iris()

# prepare data
X = iris.data[:, :2]
y = iris.target
h = .02

# take the first two features
X = iris.data[:, :2]
y = iris.target
h = .02 # step size in the mesh

# Calculate min, max and limits
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                    np.arange(y_min, y_max, h))

# Put the result into a color plot
plt.figure()
plt.scatter(X[:, 0], X[:, 1])
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
plt.title("Data points")
plt.show()

# Create color maps
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA','#00AAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00','#00AAFF'])

# we create an instance of Neighbours Classifier and fit the data.
clf = neighbors.KNeighborsClassifier(n_neighbors, weights='distance')
clf.fit(X, y)

# predict class using data and kNN classifier
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])

# Put the result into a color plot
Z = Z.reshape(xx.shape)
plt.figure()
plt.pcolormesh(xx, yy, Z, cmap=cmap_light)

# Plot also the training points
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold)
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
plt.title("3-Class classification (k = %i)" % (n_neighbors))
plt.show()

Пример иерархической кластеризации (агломеративная и разделительная)

Hierarchical Clustering with Python. AgglomerativeClustering (подход «снизу вверх»):

  • Смотрим, насколько далеко каждая точка данных находится друг от друга.
  • Формируем Кластер между S1 и S2, потому что они были ближе друг к другу. Среднее значение оценок для S1 и S2 будут представлять этот кластера.
  • Снова находим ближайшие точки и создаем еще один кластер
  • Продолжим кластеризацию, пока у нас не останется только один кластер
  • Определяем количество кластеров по пороговому евклидовому расстоянию на дендрограмме.
#Importing required libraries
from sklearn.datasets import load_iris
from sklearn.cluster import AgglomerativeClustering
import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram , linkage
 
#Getting the data ready
data = load_iris()
df = data.data
#Selecting certain features based on which clustering is done 
df = df[:,1:3]
 
#Creating the model
agg_clustering = AgglomerativeClustering(n_clusters = 3, affinity = 'euclidean', linkage = 'ward')
 
#predicting the labels
labels = agg_clustering.fit_predict(df)
 
#Plotting the results
plt.figure(figsize = (8,5))
plt.scatter(df[labels == 0 , 0] , df[labels == 0 , 1] , c = 'red')
plt.scatter(df[labels == 1 , 0] , df[labels == 1 , 1] , c = 'blue')
plt.scatter(df[labels == 2 , 0] , df[labels == 2 , 1] , c = 'green')
plt.show()

#Linkage Matrix
Z = linkage(df, method = 'ward')
 
#plotting dendrogram
dendro = dendrogram(Z)
plt.title('Dendrogram')
plt.ylabel('Euclidean distance')
plt.show()

Разделительная кластеризация (сверху вниз) противоположна агломеративной. Здесь мы начинаем с одного кластера, состоящего из всех точек данных. С каждой итерацией мы отделяем точки, которые удалены от других, на основе показателей расстояния, пока в каждом кластере не будет ровно 1 точка данных.

Пример кластеризации на основе плотности (DBSCAN)

DBSCAN: Этот алгоритм требует только 2 параметра:

eps (эпсилон):  Если расстояние между двумя точками данных меньше eps, то они считаются соседями. При меньших значениях eps большое количество точек данных считается шумом, что тоже нехорошо. Для нахождения оптимального значения eps мы используем граф k-расстояний.
minPoints(n): Чтобы считать пространственную область плотной, нам требуется минимальное количество точек ‘n‘ для кластеризации вместе. Его значение зависит от размера набора данных, для большого набора данных ‘n‘ тоже должно быть большим, и наоборот.

  • Шаг 1: случайным образом выберите точку «p» из набора данных и назначьте ее как кластер 1.
  • Шаг 2: Подсчитайте количество точек ‘z’, расположенных на расстоянии eps от p. Если z больше или равно minPoints(n), то p будет считаться центральной точкой, а все eps-соседи будут частью кластера 1.
  • Шаг 3: Затем он найдет eps-соседка каждой точки данных в кластере 1 и расширит кластер 1, добавив эти точки.
  • Шаг 4: Как только в кластере 1 не останется точек данных для заполнения, из набора данных будет выбрана другая невидимая случайная точка данных, которая будет назначена кластеру 2.
  • Шаг 5: он повторит те же шаги для кластера 2, но не будет учитывать те точки, которые уже являются частью кластера 1.
  • Шаг 6: Таким же образом будет создано N кластеров, пока все точки данных не будут сгруппированы.
from sklearn.cluster import DBSCAN
import numpy as np
#Create random data
X = np.array([[1, 2], [2, 2], [2, 3],
 [8, 7], [8, 8], [25, 80]])
#Create model
clustering = DBSCAN(eps=3, min_samples=2)
#Feed data to model
clustering.fit(X)
#Predict the output for X
print(clustering.labels_)

Метод главных компонент

Метод главных компонент (PCA – principal component analysis) позволяет выразить несколько признаков через один и работать уже с более простой моделью (при снижении размерности сохраняется большее количество информации).

import numpy as np
from sklearn.decomposition import PCA

#Create random data
x = np.arange(1,11)
y = 2 * x + np.random.randn(10)*2
X = np.vstack((x,y))
print("X:\n",X)

pca = PCA(n_components = 1)
XPCAreduced = pca.fit_transform(np.transpose(X))
print ('\nSklearn reduced X:\n', XPCAreduced)

print ('\nMean vector: ', pca.mean_)
print ('Projection: ', pca.components_)
print ('Explained variance ratio: ', pca.explained_variance_ratio_)

См. Introduction To Principal Component Analysis In Machine Learning

Полезные ссылки:

 

Автор: Николай Свирневский