{
"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
}