HW_kNN_Clustering.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# kNN & Clustering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Суммарное количество баллов: 10__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## kNN и рак (3 балла)\n",
    "\n",
    "В этом части домашнего задания Вам предлагается при помощи классификации методом k ближайших соседей научиться отличать тип опухоли в организме"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib\n",
    "import copy\n",
    "import pandas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Данные (0.5 балла)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Реализуйте метод `read_cancer_dataset` . Он принимает на вход путь к набору данных и возвращает выборку `X` и соответствующие метки `y`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CANCER_DATA_PATH = # YOUR_CODE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def read_cancer_dataset(path_to_csv):\n",
    "    # Возвращает пару из X и y. X - массив векторов. y - соответствующие векторам метки\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_cancer, y_cancer = read_cancer_dataset(CANCER_DATA_PATH)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Начиная работать с данными, нам необходимо их предобработать и подготовить. В частности, нам необходимо разделить выборку на две: тренировочную и тестовую. Тренировочная выборка необходима для обучения алгоритма, а тестовая для проверки результатов обучения. Обычно используют коэффициент разделения `0.7`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train_test_split(X, y, ratio):\n",
    "    # Возвращает X_train, y_train, X_test, y_test\n",
    "    # X_train и X_test - массив векторов - две части массива X, разделенного в состветсви с коэффициентом ratio\n",
    "    # y_train и y_test - соответствующие X_train и X_test метки классов\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Метрики (0.5 балла)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Также прежде чем приступать к решению задачи, нам необходимо определиться с метриками, которые позволят нам оценить полученное решение. Для задач классификации мы можем использовать precision, recall и accuracy. Эти метрики считаются для каждого класса. \n",
    "\n",
    "__Precision__ отражает то, насколько редко мы ошибаемся, когда говорим, что объект пренадлежит к классу. \n",
    "\n",
    "__Recall__ же отражает то, насколько редко классификатор неправильно классифицирует объекты данного класса.\n",
    "\n",
    "__Accuracy__ отражает то, какую часть выборки классификатор отнес к правильному классу."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_precision_recall_accuracy(y_pred, y_true):\n",
    "    # Возвращает precision, recall и accuracy\n",
    "    # precision - набор значений метрики precision для каждого класса\n",
    "    # recall - набор значений метрики recall для каждого класса\n",
    "    # accuracy - число, отражающее общую точность предсказания\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь, имея этот метод, мы можем построить кривые зависимости Precision, Recall и Accuracy от параметра `k`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_precision_recall(X_train, y_train, X_test, y_test, max_k=30):\n",
    "    ks = list(range(1, max_k + 1))\n",
    "    classes = len(np.unique(list(y_train) + list(y_test)))\n",
    "    precisions = [[] for _ in range(classes)]\n",
    "    recalls = [[] for _ in range(classes)]\n",
    "    accuracies = []\n",
    "    for k in ks:\n",
    "        classifier = KNearest(k)\n",
    "        classifier.fit(X_train, y_train)\n",
    "        y_pred = classifier.predict(X_test)\n",
    "        precision, recall, acc = get_precision_recall_accuracy(y_pred, y_test)\n",
    "        for c in range(classes):\n",
    "            precisions[c].append(precision[c])\n",
    "            recalls[c].append(recall[c])\n",
    "        accuracies.append(acc)\n",
    "    def plot(x, ys, ylabel, legend=True):        \n",
    "        plt.figure(figsize = (12, 3))\n",
    "        plt.xlabel(\"K\")\n",
    "        plt.ylabel(ylabel)\n",
    "        plt.xlim(x[0], x[-1])\n",
    "        plt.ylim(np.min(ys)-0.01, np.max(ys)+0.01)\n",
    "        for cls, cls_y in enumerate(ys):\n",
    "            plt.plot(x, cls_y, label=\"Class \" + str(cls))\n",
    "        if legend:\n",
    "            plt.legend()\n",
    "        plt.tight_layout()\n",
    "        plt.show()\n",
    "    \n",
    "    plot(ks, recalls, \"Recall\")\n",
    "    plot(ks, precisions, \"Precision\")\n",
    "    plot(ks, [accuracies], \"Accuracy\", legend=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Также для оценки качества классификации построим __ROC-кривую__. Она отражает зависимость __True Positive Rate__ (TPR) от __False Positive Rate__ (FPR) для заранее фиксированного класса. Чем график выше побочной диагонали - тем лучше."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_roc_curve(X_train, y_train, X_test, y_test, max_k=30):\n",
    "    positive_samples = sum(1 for y in y_test if y == 0)\n",
    "    ks = list(range(1, max_k + 1))\n",
    "    curves_tpr = []\n",
    "    curves_fpr = []\n",
    "    colors = []\n",
    "    for k in ks:\n",
    "        colors.append([k / ks[-1], 0, 1 - k / ks[-1]])\n",
    "        knearest = KNearest(k)\n",
    "        knearest.fit(X_train, y_train)\n",
    "        p_pred = [p[0] for p in knearest.predict_proba(X_test)]\n",
    "        tpr = []\n",
    "        fpr = []\n",
    "        for w in np.arange(-0.01, 1.02, 0.01):\n",
    "            y_pred = [(0 if p > w else 1) for p in p_pred]\n",
    "            tpr.append(sum(1 for yp, yt in zip(y_pred, y_test) if yp == 0 and yt == 0) / positive_samples)\n",
    "            fpr.append(sum(1 for yp, yt in zip(y_pred, y_test) if yp == 0 and yt != 0) / (len(y_test) - positive_samples))\n",
    "        curves_tpr.append(tpr)\n",
    "        curves_fpr.append(fpr)\n",
    "    plt.figure(figsize = (7, 7))\n",
    "    for tpr, fpr, c in zip(curves_tpr, curves_fpr, colors):\n",
    "        plt.plot(fpr, tpr, color=c)\n",
    "    plt.plot([0, 1], [0, 1], linestyle=\"--\")\n",
    "    plt.xlabel(\"False positive rate\")\n",
    "    plt.ylabel(\"True positive rate\")\n",
    "    plt.xlim(-0.01, 1.01)\n",
    "    plt.ylim(-0.01, 1.01)\n",
    "    plt.tight_layout()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. KNN (2 балла)\n",
    "Осталось реализовать сам классификатор. Реализуйте его, используя KD-дерево. (При желании можно воспользоваться библиотечной реализацией дерева)\n",
    "\n",
    "Метод `__init__` принимает на вход количество соседей, по которым предсказывается класс, и размер листьев KD-дерева.\n",
    "\n",
    "Метод `fit` должен по набору данных и меток \"обучать\" классификатор. \n",
    "\n",
    "Метод `predict_proba` должен предсказывать вероятности классов для заданного набора данных основываясь на классах соседей"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KNearest:\n",
    "    def __init__(self, n_neighbors=5, leaf_size=30):\n",
    "        raise NotImplementedError()    \n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        raise NotImplementedError()\n",
    "        \n",
    "    def predict_proba(self, X):\n",
    "        # Возвращает матрицу, в которой строки соответствуют элементам X, а столбцы - классам. На пересечении строки и столбца должна быть указана вероятность того, что элемент относится к классу\n",
    "        # Вероятность рассчитывается как количество ближайших соседей с данным классом деленное на общее количество соседей\n",
    "        raise NotImplementedError()\n",
    "        \n",
    "    def predict(self, X):\n",
    "        return np.argmax(self.predict_proba(X), axis=1)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Наконец, протестируем наш классификатор на датасете _cancer_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train, y_train, X_test, y_test = train_test_split(X_cancer, y_cancer, 0.9)\n",
    "plot_precision_recall(X_train, y_train, X_test, y_test)\n",
    "plot_roc_curve(X_train, y_train, X_test, y_test, max_k=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "Проанализируйте полученные графики. Какой параметр `k` кажется лучшим? Какая из метрик лучше всего отражает качество модели? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Ваш ответ_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Clustering (7 баллов)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этой части домашнего задания предлагается реализовать три различных метода кластеризации, понять, в каких случаях стоит применять те или иные методы."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.neighbors import KDTree\n",
    "from sklearn.datasets import make_blobs, make_moons, make_swiss_roll\n",
    "import numpy as np\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib\n",
    "import copy\n",
    "import cv2\n",
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def visualize_clasters(X, labels):\n",
    "    unique_labels = np.unique(labels)\n",
    "    unique_colors = np.random.random((len(unique_labels), 3))\n",
    "    colors = [unique_colors[l] for l in labels]\n",
    "    plt.figure(figsize=(9, 9))\n",
    "    plt.scatter(X[:, 0], X[:, 1], c=colors)\n",
    "    plt.show()\n",
    "\n",
    "def clusters_statistics(flatten_image, cluster_colors, cluster_labels):\n",
    "    fig, axes = plt.subplots(3, 2, figsize=(12, 16))\n",
    "    for remove_color in range(3):\n",
    "        axes_pair = axes[remove_color]\n",
    "        first_color = 0 if remove_color != 0 else 2\n",
    "        second_color = 1 if remove_color != 1 else 2\n",
    "        axes_pair[0].scatter([p[first_color] for p in flatten_image], [p[second_color] for p in flatten_image], c=flatten_image, marker='.')\n",
    "        axes_pair[1].scatter([p[first_color] for p in flatten_image], [p[second_color] for p in flatten_image], c=[cluster_colors[c] for c in cluster_labels], marker='.')\n",
    "        for a in axes_pair:\n",
    "            a.set_xlim(0, 1)\n",
    "            a.set_ylim(0, 1)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Генерируем два синтетических набора данных для кластеризации. Далее будем тестировать наши алгоритмы на них."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_1, true_labels = make_blobs(400, 2, centers=[[0, 0], [-4, 0], [3.5, 3.5], [3.5, -2.0]])\n",
    "visualize_clasters(X_1, true_labels)\n",
    "X_2, true_labels = make_moons(400, noise=0.075)\n",
    "visualize_clasters(X_2, true_labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. K-means (2.5 балла)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Первый метод, который предлагается реализовать - метод K средних.\n",
    "\n",
    "__Описание методов__\n",
    "\n",
    "`fit(X, y=None)` ищет и запоминает в `self.centroids` центроиды кластеров для набора данных.\n",
    "`predict(X)` для каждого элемента из `X` возвращает номер кластера, к которому относится данный элемент.\n",
    "\n",
    "__Инициализация кластеров__\n",
    "\n",
    "Есть несколько вариантов инициализации кластеров. Нужно реализовать их все:\n",
    "1. `random` - центроиды кластеров являются случайными точками\n",
    "2. `sample` - центроиды кластеров выбираются случайно из набора данных\n",
    "3. `k-means++` - центроиды кластеров инициализируются при помощи метода K-means++\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KMeans:\n",
    "    def __init__(self, n_clusters, init=\"random\", max_iter=300):\n",
    "        raise NotImplementedError()\n",
    "        \n",
    "    def fit(self, X, y=None):\n",
    "        raise NotImplementedError()\n",
    "    \n",
    "    def predict(self, X):\n",
    "        raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Протестируйте алгоритм на синтетических данных. При необходимости подберите гиперпараметры для достижения лучшего качества кластеризации."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kmeans = KMeans(n_clusters=4)\n",
    "kmeans.fit(X_1)\n",
    "labels = kmeans.predict(X_1)\n",
    "visualize_clasters(X_1, labels)\n",
    "\n",
    "kmeans = KMeans(n_clusters=2)\n",
    "kmeans.fit(X_2)\n",
    "labels = kmeans.predict(X_2)\n",
    "visualize_clasters(X_2, labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. DBScan (3.5 балла)\n",
    "В отличии от K-means, DBScan не позволяет задать количество кластеров, на которое будут разбиты данные. Руководствуясь геометрической интерпретацией, он позволяет выделять кластеры более сложной формы.\n",
    "\n",
    "__Описание методов__\n",
    "\n",
    "`fit_predict(X, y=None)` для каждого элемента `X` возвращает метку кластера, к которому он относится.\n",
    "\n",
    "__Возможные метрики__\n",
    "\n",
    "* `euclidean`\n",
    "* `manhattan`\n",
    "* `chebyshev`\n",
    "\n",
    "__Для быстрого поиска соседей используйте `sklearn.neighbors.KDTree`__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DBScan:\n",
    "    def __init__(self, eps=0.5, min_samples=5, leaf_size=40, metric=\"euclidean\"):\n",
    "        raise NotImplementedError()\n",
    "        \n",
    "    def fit_predict(self, X, y=None):\n",
    "        raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Протестируйте алгоритм на синтетических данных. При необходимости подберите гиперпараметры для достижения лучшего качества кластеризации."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dbscan = DBScan()\n",
    "labels = dbscan.fit_predict(X_1)\n",
    "visualize_clasters(X_1, labels)\n",
    "\n",
    "dbscan = DBScan()\n",
    "labels = dbscan.fit_predict(X_2)\n",
    "visualize_clasters(X_2, labels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Оценка качества моделей (1 балл)\n",
    "Проанализируйте полученные результаты. \n",
    "\n",
    "Какой метод лучше справился с кластеризацией? Почему? \n",
    "\n",
    "Сравните значения метрик  `Davies-Bouldin index` и `Silhouette score` для определения качества кластеризации. \n",
    "\n",
    "Какие значения метрики свидетельствуют о хорошей кластеризации - большие или маленькие?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Ваш ответ_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics import davies_bouldin_score\n",
    "from sklearn.metrics import silhouette_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# YOUR_CODE"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}