#!/usr/bin/env python
# coding: utf-8

# # Метод ближайших соседей

# Разберёмся как тренировать модели машинного обучения и, в частности, метод ближайших соседей в sklearn.

# ![](https://upload.wikimedia.org/wikipedia/commons/e/e7/KnnClassification.svg)

# In[1]:


import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
import seaborn as sns

get_ipython().run_line_magic('matplotlib', 'inline')

sns.set(style='dark')


# ### Генерация данных

# Сгенерируем данные

# In[2]:


np.random.seed(13)
n = 100
a = np.random.normal(loc=0, scale=1, size=(n, 2))
b = np.random.normal(loc=3, scale=2, size=(n, 2))


# Визуализируем полученный набор данных

# In[3]:


plt.figure(figsize=(8, 8))

plt.scatter(a[:, 0], a[:, 1], c='blue', s=50, alpha=0.6)
plt.scatter(b[:, 0], b[:, 1], c='red', s=50, alpha=0.6)

plt.xlabel('$x_1$')
plt.ylabel('$x_2$')
plt.grid()
plt.legend(['class 0', 'class 1'], loc='upper right');


# Объединим матрицы в единую матрицу данных и создадим отдельный столбец меток класса

# In[4]:


X = np.vstack([a, b])
y = np.hstack([np.zeros(n), np.ones(n)])

X.shape, y.shape


# Для визуализации воспользуемся следующий палитрой:

# In[5]:


cmap = sns.diverging_palette(240, 10, n=9, as_cmap=True)
sns.palplot(sns.diverging_palette(240, 10, n=9))


# Можно визуализировать одной командой scatter

# In[6]:


plt.figure(figsize=(8, 8))

plt.scatter(X[:, 0], X[:, 1], c=y, s=50, alpha=0.6, cmap=cmap)
plt.xlabel('$x_1$')
plt.ylabel('$x_2$')
plt.grid()


# ## Обучение моделей

# Попробуем обучить разные варианты [метода ближайших соседей](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html) из scikit-learn:
# 
# ```python
# class KNeighborsClassifier(...):
#     def __init__(self, n_neighbors=5,
#                  weights='uniform', algorithm='auto', leaf_size=30,
#                  p=2, metric='minkowski', metric_params=None, n_jobs=None,
#                  **kwargs):
# ```

# Для начала обучим метод 3 ближайших соседей

# In[7]:


from sklearn.neighbors import KNeighborsClassifier as KNN
clf = KNN(n_neighbors=3)
clf.fit(X, y)
clf


# Предскажем метки для каких-нибудь точек

# In[8]:


X_test = [
    [2, 0],
    [10, 20],
    [-10, -20]
]
clf.predict(X_test)


# Предскажем вероятности каждой из меток

# In[9]:


clf.predict_proba(X_test)


# А что, если мы хотим помотреть, как обученный алгоритм проводит разделяющую поверхность между объектами из признакового пространства?
# 
# Для начала напишем функцию для генерации карты точек

# In[10]:


def get_grid(data, border=1.0, step=0.01):
    x_min, x_max = data[:, 0].min() - border, data[:, 0].max() + border
    y_min, y_max = data[:, 1].min() - border, data[:, 1].max() + border
    return np.meshgrid(np.arange(x_min, x_max, step),
                       np.arange(y_min, y_max, step))


# In[11]:


xx, yy = get_grid(X, step=0.5)
plt.plot(xx, yy, 'b.');


# Примерним классификатор к карте точек и визуализируем её

# In[12]:


from matplotlib.colors import ListedColormap

plt.figure(figsize=(8, 8))
xx, yy = get_grid(X)
predicted = clf.predict_proba(np.c_[xx.ravel(), yy.ravel()])[:, 1].reshape(xx.shape)

plt.pcolormesh(xx, yy, predicted, cmap=cmap)
plt.scatter(X[:, 0], X[:, 1], c=y, s=100., edgecolor='k', cmap=cmap)
plt.xlabel('$x_1$')
plt.ylabel('$x_2$');


# Обернём все вышеописанное (обучение + предсказание + визуализацию) в одну функцию

# In[13]:


def plot_model(X, y, clf):
    clf.fit(X, y)
    xx, yy = get_grid(X)
    predicted = clf.predict_proba(np.c_[xx.ravel(), yy.ravel()])[:, 1].reshape(xx.shape)
    plt.axis('equal')
    plt.xlabel('$x_1$')
    plt.ylabel('$x_2$')
    cmap = sns.diverging_palette(240, 10, n=9, as_cmap=True)
    plt.pcolormesh(xx, yy, predicted, cmap=cmap)
    plt.scatter(X[:, 0], X[:, 1], c=y, s=70, edgecolors='k', cmap=cmap, alpha=0.7)


# Будем перебирать параметр "число соседей" и визуализировать полученное разбиение пространства объектов

# In[14]:


plt.figure(figsize=(20, 12))
for index, n_neighbors in enumerate(np.logspace(0, 7, 8, base=2, dtype=np.int16)):
    plt.subplot(2, 4, index + 1)
    plot_model(X, y, KNN(n_neighbors=n_neighbors))
    plt.title(f'{n_neighbors} nearest neighbours')


# ## Как выбрать число соседей?

# ### Оценка качества

# Разобьём данные на 2 части: обучение и контроль

# In[15]:


from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)


# In[16]:


print(X_train.shape, y_train.shape)
print(X_test.shape, y_test.shape)


# Оценим качество работы для n_neighbors=3

# In[17]:


from sklearn.metrics import accuracy_score
accuracy_score(y_test, KNN(n_neighbors=3).fit(X_train, y_train).predict(X_test))


# Оценим качество для каждого из значений n_neighbors из [1, n) и построим график зависимости качества от n_neighbors

# In[18]:


n = 100
scores = []
for k in range(1, n):
    scores.append(accuracy_score(y_test, KNN(n_neighbors=k).fit(X_train, y_train).predict(X_test)))


# In[19]:


plt.figure(figsize=(18, 8))
plt.plot(range(1, n), scores)
plt.xlim(1, n)
plt.ylim(np.min(scores) - 0.1, 1)
plt.xticks(np.arange(1, n, 2))
plt.xlabel('Number of nearest neighbours')
plt.ylabel('Accuracy score')
plt.grid()


# Из-за небольшого количества данных в тесте график получается шумным, и не до конца ясно, какое число соседей оптимально. Проведем кроссвалидацию средствами библиотеки sklearn

# In[20]:


from sklearn.model_selection import GridSearchCV
params = {'n_neighbors': range(1, n)}
grid_searcher = GridSearchCV(clf, params, cv=5)
grid_searcher.fit(X, y)


# Визуализируем полученные оценки качества и их $1\sigma$-доверительный интервал

# In[21]:


df = pd.DataFrame(grid_searcher.cv_results_)
df


# In[22]:


means = df['mean_test_score']
stds = df['std_test_score']
n_neighbors = df['params'].apply(lambda x: x['n_neighbors'])


# In[23]:


plt.figure(figsize=(18, 8))
plt.plot(n_neighbors, means)
plt.fill_between(range(len(means)), means + stds, means - stds, alpha = 0.2, facecolor='blue')
plt.xlim(1, n)
plt.ylim(np.min(means - stds) - 0.1, 1)
plt.xticks(np.arange(1, n, 2))
plt.xlabel('Number of nearest neighbours')
plt.ylabel('Accuracy score')
plt.grid()


# ## Какие параметры ещё можно настраивать?

# Помимо числа соседей, мы можем подбирать следующие параметры:
# 
# 1. weights ('uniform', 'distance', [callable])
# 2. metric 
# 3. p (для метрики Минковского)

# Кроме того, у KNeighborsClassifier есть параметр algorithm, который отвечает за алгоритм поиска ближайших соседей, который может позволить ускорить работу по сравнению с наивным подходом:
# 
# 1. Brute force
# 2. [BallTree](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.html#sklearn.neighbors.BallTree)
# 3. [KDTree](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html#sklearn.neighbors.KDTree)
# 4. Auto
# 
# При использовании этих алгоритмов появляется и параметр для более детальной их настройки: leaf_size (для BallTree и KDTree)

# ## Масштабирование признаков

# Загрузим набор данных [Wine](https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data), где требуется предсказать сорт винограда, из которого изготовлено вино, используя результаты химических анализов. Более подробное описание данных можно посмотреть [здесь](https://archive.ics.uci.edu/ml/datasets/Wine).

# In[24]:


data = pd.read_csv('wine.data', header=None)
print(data.shape)
data.head()


# In[25]:


data[0].value_counts()


# Сохраним отдельно матрицу объектов и столбец ответов

# In[26]:


y = data[0].values
X = data.drop(0, axis=1).values
print(X.shape, y.shape)


# Подберём число соседей по кроссвалидации. Для этого напишем функцию, которая сделает это за нас

# In[27]:


from sklearn.model_selection import KFold
from sklearn.model_selection import cross_val_score

def cv_nn(n_neighbors, X, y):
    average_scores = []
    cv = KFold(n_splits=5, shuffle=True, random_state=42)
    for k in n_neighbors:
        knn_clf = KNN(n_neighbors=k)
        scores = cross_val_score(knn_clf, X, y, cv=cv)
        average_scores.append(scores.mean())
    return average_scores


# In[28]:


n_neighbors = range(1, 51)
average_scores = cv_nn(n_neighbors, X, y)


# Посмотрим на то, что получилось:

# In[29]:


plt.figure(figsize=(18, 8))
l1 = plt.plot(n_neighbors, average_scores)
plt.xticks(n_neighbors)
plt.xlim(np.min(n_neighbors), np.max(n_neighbors))
plt.ylim(0, 1)
plt.xlabel('Number of nearest neighbours')
plt.ylabel('Accuracy score')
plt.grid()


# А теперь сперва отмасштабируем данные и проделаем то же самое

# In[30]:


from sklearn.preprocessing import scale
X_scaled = scale(X)
average_scores_scaled = cv_nn(n_neighbors, X_scaled, y)


# Сравним полученные результаты

# In[31]:


plt.figure(figsize=(18, 8))
l1 = plt.plot(n_neighbors, average_scores)
l2 = plt.plot(n_neighbors, average_scores_scaled)
plt.xticks(n_neighbors)
plt.xlim(np.min(n_neighbors), np.max(n_neighbors))
plt.ylim(0, 1)
plt.xlabel('Number of nearest neighbours')
plt.ylabel('Accuracy score')
plt.legend(['Initial data', 'Scaled data'], loc='lower right')
plt.grid()


# Видно, что масштабирование данных сильно сказалось на качестве классификации.