19. Кластеризация.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3-средних:\n",
      "[[-25.857142857142854, -4.714285714285714], [20.0, 26.0], [16.666666666666664, 13.666666666666666]]\n",
      "\n",
      "2-средних:\n",
      "[[-25.857142857142854, -4.714285714285714], [18.333333333333332, 19.833333333333332]]\n",
      "\n",
      "квадратичные отклонения как функция от k\n",
      "1 15241.35\n",
      "2 4508.738095238095\n",
      "3 1209.0555555555557\n",
      "4 1060.0555555555557\n",
      "5 1037.8055555555557\n",
      "6 797.1666666666667\n",
      "7 475.1666666666667\n",
      "8 676.0\n",
      "9 417.0\n",
      "10 245.75\n",
      "11 255.66666666666666\n",
      "12 135.58333333333334\n",
      "13 199.25\n",
      "14 123.0\n",
      "15 50.5\n",
      "16 42.0\n",
      "17 42.5\n",
      "18 22.5\n",
      "19 2.5\n",
      "20 0.0\n",
      "\n",
      "восходящий метод иерархической кластеризации\n",
      "(0, [(1, [(3, [(14, [(18, [([19, 28],), ([21, 27],)]), ([20, 23],)]), ([26, 13],)]), (16, [([11, 15],), ([13, 13],)])]), (2, [(4, [(5, [(9, [(11, [([-49, 0],), ([-46, 5],)]), ([-41, 8],)]), ([-49, 15],)]), ([-34, -1],)]), (6, [(7, [(8, [(10, [([-22, -16],), ([-19, -11],)]), ([-25, -9],)]), (13, [(15, [(17, [([-11, -6],), ([-12, -8],)]), ([-14, -5],)]), ([-18, -3],)])]), (12, [([-13, -19],), ([-9, -16],)])])])])\n",
      "\n",
      "3 кластера, min:\n",
      "[[-49, 0], [-46, 5], [-41, 8], [-49, 15], [-34, -1], [-22, -16], [-19, -11], [-25, -9], [-11, -6], [-12, -8], [-14, -5], [-18, -3], [-13, -19], [-9, -16]]\n",
      "[[19, 28], [21, 27], [20, 23], [26, 13]]\n",
      "[[11, 15], [13, 13]]\n",
      "\n",
      "3 кластера, max:\n",
      "[[11, 15], [13, 13], [26, 13], [19, 28], [21, 27], [20, 23]]\n",
      "[[-41, 8], [-49, 15], [-49, 0], [-46, 5], [-34, -1]]\n",
      "[[-11, -6], [-12, -8], [-14, -5], [-18, -3], [-22, -16], [-19, -11], [-25, -9], [-13, -19], [-9, -16]]\n"
     ]
    }
   ],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "\n",
    "# clustering.py\n",
    "\n",
    "import sys\n",
    "sys.path.append(\"../code-python3-ru\")\n",
    "\n",
    "from lib.linear_algebra import squared_distance, vector_mean, distance\n",
    "import math, random\n",
    "\n",
    "import matplotlib.image as mpimg\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib as mpl\n",
    "\n",
    "class KMeans:\n",
    "    \"\"\"класс выполняет кластеризацию по методу k-средних\"\"\"\n",
    "\n",
    "    def __init__(self, k):\n",
    "        self.k = k          # число кластеров\n",
    "        self.means = None   # средние кластеров\n",
    "\n",
    "    def classify(self, input):\n",
    "        \"\"\"вернуть индекс кластера, ближайшего к входящему значению input\"\"\"\n",
    "        return min(range(self.k),\n",
    "                   key=lambda i: squared_distance(input, self.means[i]))\n",
    "\n",
    "    def train(self, inputs):\n",
    "\n",
    "        self.means = random.sample(inputs, self.k)\n",
    "        assignments = None\n",
    "\n",
    "        while True:\n",
    "            # найти новые назначения\n",
    "            new_assignments = list(map(self.classify, inputs))\n",
    "\n",
    "            # если ни одно назначение не изменилось, то завершить\n",
    "            if assignments == new_assignments:\n",
    "                return\n",
    "\n",
    "            # в противном случае сохранить новые назначения\n",
    "            assignments = new_assignments\n",
    "\n",
    "            for i in range(self.k):\n",
    "                i_points = [p for p, a in zip(inputs, assignments) if a == i]\n",
    "                # удостовериться, что i_points не пуст, чтобы не делить на 0\n",
    "                if i_points:\n",
    "                    self.means[i] = vector_mean(i_points)\n",
    "\n",
    "def squared_clustering_errors(inputs, k):\n",
    "    \"\"\"находит суммарное квадратичное отклонение (ошибку) \n",
    "    от k-средних при кластеризации входящих данных\"\"\"\n",
    "    clusterer = KMeans(k)\n",
    "    clusterer.train(inputs)\n",
    "    means = clusterer.means\n",
    "    assignments = list(map(clusterer.classify, inputs))\n",
    "\n",
    "    return sum(squared_distance(input,means[cluster])\n",
    "               for input, cluster in zip(inputs, assignments))\n",
    "\n",
    "def plot_squared_clustering_errors():\n",
    "\n",
    "    ks = range(1, len(inputs) + 1)\n",
    "    errors = [squared_clustering_errors(inputs, k) for k in ks]\n",
    "\n",
    "    plt.plot(ks, errors)\n",
    "    plt.xticks(ks)\n",
    "    plt.xlabel(\"k\")\n",
    "    plt.ylabel(\"Суммарнное квадратичное отклонение\")\n",
    "    plt.show()\n",
    "\n",
    "#\n",
    "# применение кластеризации для изменения цвета изображения\n",
    "#\n",
    "\n",
    "def recolor_image(input_file, k=5):\n",
    "\n",
    "    img = mpimg.imread(path_to_png_file)\n",
    "    pixels = [pixel for row in img for pixel in row]\n",
    "    clusterer = KMeans(k)\n",
    "    clusterer.train(pixels) # обучение может занять некоторое время\n",
    "\n",
    "    def recolor(pixel):\n",
    "        cluster = clusterer.classify(pixel) # индекс ближайшего кластера\n",
    "        return clusterer.means[cluster]     # среднее ближайшего кластера\n",
    "\n",
    "    new_img = [[recolor(pixel) for pixel in row]\n",
    "               for row in img]\n",
    "\n",
    "    plt.imshow(new_img)\n",
    "    plt.axis('off')\n",
    "    plt.show()\n",
    "\n",
    "#\n",
    "# иерархическая кластеризация\n",
    "#\n",
    "\n",
    "def is_leaf(cluster):\n",
    "    \"\"\"кластер является листом, если его длина = 1\"\"\"\n",
    "    return len(cluster) == 1\n",
    "\n",
    "def get_children(cluster):\n",
    "    \"\"\"вернуть два дочерних элемента данного кластера,\n",
    "    если он – объединенный кластер; вызывает исключение,\n",
    "    если это листовой кластер\"\"\"\n",
    "    if is_leaf(cluster):\n",
    "        raise TypeError(\"a leaf cluster has no children\")\n",
    "    else:\n",
    "        return cluster[1]\n",
    "\n",
    "def get_values(cluster):\n",
    "    \"\"\"вернуть значение в кластере (если это листовой кластер)\n",
    "    или все значения в листовых кластерах под ним (если нет)\"\"\"\n",
    "    if is_leaf(cluster):\n",
    "        return cluster # это уже одноэлементный кортеж, содержащий значение\n",
    "    else:\n",
    "        return [value\n",
    "                for child in get_children(cluster)\n",
    "                for value in get_values(child)]\n",
    "\n",
    "def cluster_distance(cluster1, cluster2, distance_agg=min):\n",
    "    \"\"\"найти агрегированное расстояние между элементами \n",
    "    кластера cluster1 и элементами кластера cluster2\"\"\"\n",
    "    return distance_agg([distance(input1, input2)\n",
    "                        for input1 in get_values(cluster1)\n",
    "                        for input2 in get_values(cluster2)])\n",
    "\n",
    "def get_merge_order(cluster):\n",
    "    if is_leaf(cluster):\n",
    "        return float('inf')\n",
    "    else:\n",
    "        return cluster[0] # 1-й элемент 2-элементного кортежа - порядковый номер merge_order \n",
    "\n",
    "def bottom_up_cluster(inputs, distance_agg=min):\n",
    "    # начать с того, что все входы - листовые кластеры (1-элементный кортеж)\n",
    "    clusters = [(input,) for input in inputs]\n",
    "\n",
    "    # пока остается более одного кластера...\n",
    "    while len(clusters) > 1:\n",
    "        # найти два ближайших кластера\n",
    "        c1, c2 = min([(cluster1, cluster2)\n",
    "                     for i, cluster1 in enumerate(clusters)\n",
    "                     for cluster2 in clusters[:i]],\n",
    "                     key=lambda p: cluster_distance(p[0], p[1], distance_agg))\n",
    "\n",
    "        # исключить их из списка кластеров\n",
    "        clusters = [c for c in clusters if c != c1 and c != c2]\n",
    "\n",
    "        # объединить их, используя переменную порядкового номера\n",
    "        # объединения merge_order = число оставшихся кластеров\n",
    "        merged_cluster = (len(clusters), [c1, c2])\n",
    "\n",
    "        # и добавить их объединение к списку кластеров\n",
    "        clusters.append(merged_cluster)\n",
    "\n",
    "    # когда останется всего один кластер, то вернуть его\n",
    "    return clusters[0]\n",
    "\n",
    "def generate_clusters(base_cluster, num_clusters):\n",
    "    # sначать со списка, состоящего только из базового кластера\n",
    "    clusters = [base_cluster]\n",
    "\n",
    "    # продолжать, пока кластеров не достаточно...\n",
    "    while len(clusters) < num_clusters:\n",
    "        # выбрать из кластеров тот, который был объединен последним\n",
    "        next_cluster = min(clusters, key=get_merge_order)\n",
    "        # исключить его из списка\n",
    "        clusters = [c for c in clusters if c != next_cluster]\n",
    "        # и добавить его дочерние элементы к списку\n",
    "        # (т. е. разъединить его)\n",
    "        clusters.extend(get_children(next_cluster))\n",
    "\n",
    "    # когда уже достаточно кластеров...\n",
    "    return clusters\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    inputs = [[-14,-5],[13,13],[20,23],[-19,-11],[-9,-16],\n",
    "              [21,27],[-49,15],[26,13],[-46,5],[-34,-1],\n",
    "              [11,15],[-49,0],[-22,-16],[19,28],[-12,-8],\n",
    "              [-13,-19],[-41,8],[-11,-6],[-25,-9],[-18,-3]]\n",
    "\n",
    "    random.seed(0) # чтобы получить  повторимые результаты\n",
    "    clusterer = KMeans(3)\n",
    "    clusterer.train(inputs)\n",
    "    print(\"3-средних:\")\n",
    "    print(clusterer.means)\n",
    "    print()\n",
    "\n",
    "    random.seed(0)\n",
    "    clusterer = KMeans(2)\n",
    "    clusterer.train(inputs)\n",
    "    print(\"2-средних:\")\n",
    "    print(clusterer.means)\n",
    "    print()\n",
    "\n",
    "    print(\"квадратичные отклонения как функция от k\")\n",
    "\n",
    "    for k in range(1, len(inputs) + 1):\n",
    "        print(k, squared_clustering_errors(inputs, k))\n",
    "    print()\n",
    "\n",
    "\n",
    "    print(\"восходящий метод иерархической кластеризации\")\n",
    "\n",
    "    base_cluster = bottom_up_cluster(inputs)\n",
    "    print(base_cluster)\n",
    "\n",
    "    print()\n",
    "    print(\"3 кластера, min:\")\n",
    "    for cluster in generate_clusters(base_cluster, 3):\n",
    "        print(get_values(cluster))\n",
    "\n",
    "    print()\n",
    "    print(\"3 кластера, max:\")\n",
    "    base_cluster = bottom_up_cluster(inputs, max)\n",
    "    for cluster in generate_clusters(base_cluster, 3):\n",
    "        print(get_values(cluster))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}