# Обучение без учителя
- В задачах машинного обучения без учителя нет целевой переменной (правильных ответов), есть только признаковое описание объектов. Необходимо выявить некоторые скрытые закономерности данных, понять, как объекты устроены, есть ли в данных какая-то структура.
- **Кластеризация**: k-means, DBSCAN, ...
- **Визуализация**: PCA, t-SNE, ...
- Задача кластеризации состоит в том, чтобы разбить объекты, которые даны в выборке, на несколько кластеров, так чтобы объекты в одном кластере были похожи друг на друга, а объекты в разных кластерах были не похожи друг на друга.

# 1. k-means
Кластеры представляют собой центроиды, то есть каждый кластер задаётся координатами центра, а точки относятся к тому кластеру, чей центр к ним ближе. 


**Минимизируем полную сумму квадратов расстояний от каждой точки до среднего значения назначенного ей кластера**

Итерационный алгоритм:
1. берём k случайных центров (*k средних*)
2. присоединяем все объекты к ближайшему к ним кластеру
3. пересчитываем координаты кластеров, чтобы они оказались в центре масс точек, которые относятся к ним. То есть для каждой центроиды берём все точки, которые к ней относятся, считаем среднее.
4. снова ищем для каждой точки ближайший центроид
- Если ни у одной точки её назначение не изменилось, то останавливаемся и сохраняем кластеры.
### Достоинства:
+ Очень простой алгоритм
+ Работает даже на больших данных
### Недостатки:
- Надо задавать число k руками
- Не всегда находит кластеры правильно (ищет только кластеры выпуклой формы)
- сильно зависит от начальной инициализации центров кластеров (разный результат от запуска к запуску)


```python
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn import datasets
from sklearn.metrics import accuracy_score
```


```python
np.random.seed(42)
```


```python
X1 = np.random.normal(loc=[0,-10], size=(100,2))
X2 = np.random.normal(loc=[-10, 0], size=(100,2))
X3 = np.random.normal(loc=[0, 0], size=(100,2))
X = np.vstack((X1,X2,X3))
y = np.array([1]*100 + [2]*100 + [3]*100)
```


```python
k_means = KMeans(n_clusters=3)
```


```python
clusters = k_means.fit_predict(X)
```


```python
plt.scatter(X[:, 0], X[:, 1], c=clusters)
plt.title('K-Means')
plt.show()
```

Попробуем разное количество кластеров:


```python
plt.figure(figsize=(12, 12))
for n_c in range(2, 8):
    k_means = KMeans(n_clusters=n_c)
    clusters = k_means.fit_predict(X)
    plt.subplot(3, 2, n_c-1)
    plt.scatter(X[:, 0], X[:, 1], c=clusters)
    plt.title('n_clusters = {}'.format(n_c))
plt.show()
```

### Оценка качества разбиения, выбор числа кластеров, SSE, elbow method
Дана матрица данных $X$ и дано число $k$ предполагаемых кластеров. Цель кластеризации представить данные в виде групп кластеров $C=\{C_1, C_2, \ldots, C_k\}$. Каждый кластер имеет свой центр:

\begin{equation}
\mu_i = \frac{1}{n_i} \sum \limits_{x_j \in C_i} x_j
\end{equation}

где $n_i = |C_i|$ - это количество точек в кластере $C_i$.

Таким образом, мы имеем некоторые кластеры $C=\{C_1, C_2, \ldots, C_k\}$ и необходимо оценить качество разбиения. Для этого будем вычислять сумму квадратических ошибок (**SSE, sum of squared error**):

\begin{equation}
SSE(C) = \sum \limits_{i=1}^{k} \sum \limits_{x_j \in C_i} ||x_j - \mu_i||^2
\end{equation}

Сумма квадратов расстояний между центроидом и каждым объектом кластера. 
Цель найти
\begin{equation}
C^* = arg\min\limits_C \{SSE(C)\}
\end{equation}


Выбирается число кластеров в месте "преломления" графика


# 2. DBSCAN
Идея: хотим найти скопления точек, не зная заранее количество кластеров

Нужно задать два параметра:
- размер окрестности точки $\epsilon$
- minPts - минимальное количество точек в $\epsilon$ - окрестности

Тогда все точки можно разделить на три типа:
- Core (ядровые) точки - у которых в $\epsilon$ - окрестности от minPts соседей
- Border (граничные) точки - не Core точки, но достижимы из Core точек
- Noise (шумовые) точки - все остальные, меньше minPts соседей в $\epsilon$ - окрестности



- minPts = 4
- вокруг каждой точки есть своя $\epsilon$ - окрестность
- точка А и все красные точки - core (ядровые), так как $\epsilon$ окрестность вокруг них содержит по 4 и более точек (включая себя).
- точки B и С -border points, они не core points (ядровые), но они достижимы из A через другие ядровые точки, поэтому они тоже принадлежат кластеру
- точка N - шум

### Алгоритм:
1. берём следующую точку, ищем соседей в $\epsilon$ окрестности
2. если их как минимум minPts, то начинаем поиск связной компоненты из этой core-точки (обход в ширину)
3. иначе помечаем точку как noise, она может быть позднее к какой-то Core-точке как Border-точка




Начинаем с точки P2. minPts=2. Нашли ближайших соседей P2 - P1 и P3, они внутри окрестности. Всего в окрестности находится 3 точки, это больше minPts, поэтому P2 - это core-точка. Из неё нужно запустить поиск связной компоненты. Для этого проверим соседей P1 и P3. 






В окрестности P1 находится две точки, она тоже core. Но никаких новых точек из неё не было найдено. 





Проверим теперь P3 точку. У неё в окрестности три точки (core), причем P4 - новая точка. То есть из начальной точки P2 можно достичь точки P4 по цепочке из core точек. 





Core. Достигаем новой точки P5. Проверяем P5, больше не находим непосещенных точек. Это значит, что кластер найден. 











Берём следующую непомеченную точку P6. Ищем соседей в окрестности. Их нет. Noise.




### Достоинства:
+ Не нужно задавать количество кластеров
+ Кластеры могут быть любой формы
+ Может работать с шумными данными
### Недостатки:
- Долго работает на больших данных
- Чувствителен к выбору гиперпараметров (лучше использовать иерархический HDBSCAN)


```python
from sklearn.cluster import DBSCAN
```


```python
from sklearn.cluster import DBSCAN
plt.figure(figsize=(12, 36))
i = 1
for sample in [2, 5, 10]:
    for e in [0.2, 1, 3, 5, 10]:
        dbscan = DBSCAN(eps=e, min_samples=sample)
        clusters = dbscan.fit_predict(X)
        plt.subplot(9, 2, i)
        plt.scatter(X[:, 0], X[:, 1], c=clusters)
        plt.title('eps = {}, min_samples = {}'.format(e, sample))
        i += 1
    i += 1
plt.show()
```

- Если маленький радиус е и мало объектов, то DBSCAN находит много выбросов
- Если увеличить радиус и не менять количество объектов, то часть из них остается выбросами
- Если еще увеличить радиус, то выбросы пропадают
- Если еще сильнее увеличить радиус, то выделяется только один кластер и т.д.

### Kmeans и DBSCAN на более сложных данных


```python
n_samples = 1500
X = datasets.make_circles(n_samples=n_samples, 
                          factor = 0.5, 
                          noise = 0.05)
X = X[0]
X.shape
```




    (1500, 2)




```python
dbscan = DBSCAN(eps=0.1, min_samples=5)
clusters = dbscan.fit_predict(X)
```


```python
plt.scatter(X[:, 0], X[:, 1], c=clusters)
plt.title('DBSCAN');

```


```python
k_means = KMeans(n_clusters=2)
clusters = k_means.fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c = clusters);
```

# Пример


```python
from sklearn.datasets import load_digits
```


```python
digits = load_digits()
X, y = digits['data'], digits['target']
```


```python
plt.imshow(X[1].reshape(8, 8), cmap='gray')
```


```python
km = KMeans(n_clusters=10)
```


```python
clusters = km.fit_predict(X)
```


```python
pred = np.zeros(X.shape[0])
```


```python
for i in range(10):
    bc = np.bincount(y[clusters == i])
    pred[clusters == i] = bc.argmax() # преобладающая метка в кластере
```


```python
from sklearn.metrics import accuracy_score
```


```python
accuracy_score(y, pred)
```




    0.7924318308291597



Ошибки кластеризации для нуля:


```python
incorrect_indices = np.where(np.logical_and(pred == 0, y!=0))[0]
```


```python
for i in range(2):
    plt.imshow(X[incorrect_indices[i]].reshape(8, 8), cmap='gray')
    plt.title('Real digit is {}'.format(y[incorrect_indices[i]]))
    plt.show()
```


```python
correct_indices = np.where(np.logical_and(pred == 0, y == 0))[0]
```


```python
for i in range(2):
    plt.imshow(X[correct_indices[i]].reshape(8, 8), cmap='gray')
```

## Другие алгоритмы кластеризации



# Домашнее задание 2
## Задание 1
1. Реализовать kmeans
2. Визуализировать сходимость центров кластеров
3. Оценить $SSE$ для значений $k = 1, \ldots, 10$ и построить график зависимости $SSE$ от количества кластеров.





### Алгоритм к-средних
На вход алгоритм получает матрицу данных $D$, количество кластеров $k$, и критерий остановки $\epsilon$:
1. t = 0
2. случайным образом инициализируем $k$ центров кластеров: $\mu_1^t, \mu_2^t, \ldots, \mu_k^t \in R^d$;
3. повторять
    4. $t = t + 1$;
    5. $C_j = 0$ для всех $j = 1, \ldots, k$
    6. для каждого $x_j \in D$
        7. $j^* = arg\min\limits_C \{||X_j - \mu_i^{t-1}||^2\}$ \\\ присваиваем $x_j$ к ближайшему центру
        8. $C_{j^*} = C_{j^*} \cup {x_j}$
    9. для каждого i=1 до k
        10. $\mu_i = \frac{1}{|C_i|} \sum_{x_j \in C_i} x_j$
11. пока $\sum_{i=1}^k ||\mu_i^{t} - \mu_i^{t-1}||^2 \leq \epsilon$


```python
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
X, Y = make_blobs(n_samples = 1000, n_features=2, centers=5, cluster_std = 1.2, random_state=17)
plt.scatter(X[:,0], X[:,1])
```

## Задание 2
1. Исследуйте данные с помощью pandas. Посмотрите на признаки и их распределения. (Например, постройте график распределения автомобилей по годам, типу топлива и т.д.)
2. Кластеризуйте данные с помощью KMeans из sklearn.clustering. Найдите оптимальное число кластеров
3. Произведите анализ получившихся кластеров:

Пример: первый кластер содержит полноприводные автомобили немецкого производства с АКПП, небольшим пробегом и высокой стоимостью, второй - японцы с правым рулём ...


```python
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

df = pd.read_csv('data/2.csv', encoding='cp1251')
df = df.drop(columns=['Модель', 'Цвет'])
df.head()
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>Марка</th>
      <th>Год</th>
      <th>Состояние</th>
      <th>Пробег</th>
      <th>Объем</th>
      <th>Топливо</th>
      <th>Мощность</th>
      <th>Кузов</th>
      <th>Привод</th>
      <th>КПП</th>
      <th>Руль</th>
      <th>Хозяев в ПТС</th>
      <th>Цена</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>Volkswagen</td>
      <td>2013.0</td>
      <td>БУ</td>
      <td>42000.0</td>
      <td>1200.0</td>
      <td>бензин</td>
      <td>105.0</td>
      <td>хэтчбек</td>
      <td>передний</td>
      <td>автомат</td>
      <td>левый</td>
      <td>1 владелец</td>
      <td>689196.0</td>
    </tr>
    <tr>
      <td>1</td>
      <td>Skoda</td>
      <td>2012.0</td>
      <td>БУ</td>
      <td>62000.0</td>
      <td>1800.0</td>
      <td>бензин</td>
      <td>152.0</td>
      <td>кроссовер</td>
      <td>полный</td>
      <td>механика</td>
      <td>левый</td>
      <td>1 владелец</td>
      <td>639196.0</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Renault</td>
      <td>2015.0</td>
      <td>БУ</td>
      <td>4700.0</td>
      <td>1600.0</td>
      <td>бензин</td>
      <td>106.0</td>
      <td>хэтчбек</td>
      <td>передний</td>
      <td>механика</td>
      <td>левый</td>
      <td>1 владелец</td>
      <td>629196.0</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Nissan</td>
      <td>2012.0</td>
      <td>БУ</td>
      <td>70000.0</td>
      <td>1600.0</td>
      <td>бензин</td>
      <td>110.0</td>
      <td>хэтчбек</td>
      <td>передний</td>
      <td>автомат</td>
      <td>левый</td>
      <td>1 владелец</td>
      <td>479196.0</td>
    </tr>
    <tr>
      <td>4</td>
      <td>УАЗ</td>
      <td>2014.0</td>
      <td>БУ</td>
      <td>50000.0</td>
      <td>2700.0</td>
      <td>бензин</td>
      <td>128.0</td>
      <td>внедорожник</td>
      <td>полный</td>
      <td>механика</td>
      <td>левый</td>
      <td>1 владелец</td>
      <td>599196.0</td>
    </tr>
  </tbody>
</table>
</div>



f50d398c08132d17bce9a38f3837c1e5721f7469
ipynb
Jupyter Notebook
02_kmeans_dbscan.ipynb
aicherepanov/ml-course-2021
90502f715b7424ead555d3ab75697cdbc79b142e
MIT
02_kmeans_dbscan.ipynb
aicherepanov/ml-course-2021
90502f715b7424ead555d3ab75697cdbc79b142e
MIT
02_kmeans_dbscan.ipynb
aicherepanov/ml-course-2021
90502f715b7424ead555d3ab75697cdbc79b142e
MIT
2021-09-10T11:10:24.000Z
2021-11-04T08:31:10.000Z
Qwen/Qwen-72B
1. YES
2. YES