{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Методы кластеризации\n", "Шестаков А.В. Майнор по анализу данных 24/05/2016" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Задача кластеризации** - задача выделения групп похожих друг на друга объектов (и интерпретация полученных групп).
\n", "Кластеризация - это задача unsupervised learning (обучения без учителя), то есть на вход алгоритму поступают лишь чистые данные и никакой разметки.\n", "\n", "Методов кластеризации великое множество, выбор лежит полностью на совести исследователя. Определение метода кластеризации может зависеть от \n", "* Формата исходных данных\n", "* Необходимости в наглядности представления\n", "* Необходимости в интерпретируемости\n", "* Модельных предположений о данных\n", "* ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## K-Means" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Самый простой и известный метод кластеризации, основным понятием которого является центройд $c_k$ (центр кластера). Критерий минимизации: $$ \\min J(C) = \\min\\limits_{c_k} \\sum\\limits_k\\sum\\limits_{x_i\\in c_k} ||x_i - c_k||^2 $$\n", "Шаги алгоритма\n", "1. Случайно инициализировать центройды\n", "2. Отнести точки к ближайшим центройдам (получаем кластеры)\n", "3. Перенести центройды в центр получившихся кластеров (поправка к оценке координат центройдов)\n", "4. Повторять шаги 1-2 пока критерий не содется\\кластеры не изменятся\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* Какие недостатки сразу бросаются в глаза?\n", "* Как обстоят дела с выбором количества кластеров?\n", "* Необходимо ли нормировать данные?\n", "* Приведите пример данных, которые человек \"на глаз\" может легко кластеризовать, а k-mean - сделает это неправильно\n", "* Как поменяется алгоритм, если вместо квадрата в $J(C)$ поставить модуль?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "plt.style.use('ggplot')\n", "\n", "from sklearn.cluster import KMeans\n", "from sklearn.datasets import make_blobs\n", "from sklearn.metrics import confusion_matrix\n", "from sklearn.metrics import adjusted_rand_score\n", "\n", "%matplotlib inline" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "X, y = make_blobs(n_samples=1000, n_features=2,\n", " centers=3, random_state=15)\n", "plt.scatter(X[:,0], X[:,1], c=y)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Применяем k-means\n", "kmeans = KMeans(n_clusters=3)\n", "y_hat = kmeans.fit_predict(X)\n", "\n", "plt.scatter(X[:,0], X[:,1], c=y_hat)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Крактически идеально! А если мы слегка изковеркаем данные? Заодно, давайте узнаем, как можно таки измерять качество кластеризации, если у нас есть правдивые метки?
Adjusted Rand Index нам в помощь!" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "Trans = [[ 0.40834549, -0.43667341],\n", " [-0.10887718, 0.829]]\n", "X_t = X.dot(Trans)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Your code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Иерархическая кластеризация" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "В отличие от стандартного k-means, на входе алгоритма иерархической кластеризации лежит матрица попарных расстояний между объектами. Идея (аггломеративной) иерархической кластеризации заключается в постепенном объединении объектов во всё более массивные кластеры. \n", "\n", "Вопрос: а как пересчитывать попарные расстояние между кластерами в таком случае?\n", "\n", "" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from sklearn.datasets import load_iris\n", "iris = load_iris()\n", "X = iris.data\n", "y = iris.target" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from scipy.cluster.hierarchy import linkage\n", "from scipy.cluster.hierarchy import dendrogram\n", "from scipy.cluster.hierarchy import fcluster" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Матрицу признакового описания надо отнормировать\n", "# Your code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Приятная вещица, связанная с иерархической кластеризацией - дендрограмма!" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Your code here" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Для того, чтобы определить метки кластеров используем fcluster\n", "# Your code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Смесь гаусовских распределений (GMM)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Каждая точка представляется ввиде смести гауссовских распределений:\n", "\n", "$$P(x) = \\sum\\limits_k P(x|c_k) \\cdot P(c_k) = \\mathcal{N}(x| \\mu_k, \\Sigma_k)\\cdot\\pi_k$$\n", "\n", "В процессе итеративного алгоритма (EM-алгоритм для GMM) определяются параметры \\mu_k, \\Sigma_k, \\pi_k а так же \"вклады\" каждого распределения в объекты.\n", "\n", "* Во-первых, мы получает смягченную кластеризацию\n", "* Во-вторых, ловим чуть более сложные формы кластеров, чем k-means" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from sklearn.mixture import GMM\n", "\n", "X, y = make_blobs(n_samples=1000, n_features=2,\n", " centers=3, random_state=15)\n", "\n", "Trans = [[ 0.40834549, -0.43667341],\n", " [-0.10887718, 0.829]]\n", "X = X.dot(Trans)\n", "plt.scatter(X[:,0], X[:,1], c=y)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Your code here" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import matplotlib as mpl\n", "def make_ellipses(gmm, ax):\n", " for n, color in enumerate('rgb'):\n", " v, w = np.linalg.eigh(gmm._get_covars()[n][:2, :2])\n", " u = w[0] / np.linalg.norm(w[0])\n", " angle = np.arctan2(u[1], u[0])\n", " angle = 180 * angle / np.pi # convert to degrees\n", " v *=9\n", " ell = mpl.patches.Ellipse(gmm.means_[n, :2], v[0], v[1],\n", " 180 + angle, color=color)\n", " ell.set_clip_box(ax.bbox)\n", " ell.set_alpha(0.5)\n", " ax.add_artist(ell)\n", "plt.scatter(X[:,0], X[:,1], c=y_hat)\n", "make_ellipses(gmm, plt.gca())" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Можем посмотреть на параметры получившихся распределений\n", "# Your code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Задание\n", "1. Выберите любую (желательно красочную) картинку, подгузите её с помощью `plt.imread()`\n", "2. Выполните компрессию изображения с помощью метода k-means, т.е. задайте некоторе число кластеров, произведите кластеризацию, затем замените соответствующие пиксели на значения центройдов." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Your code here" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.11" } }, "nbformat": 4, "nbformat_minor": 0 }