Python61-K-Means 算法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "参考资料： 机器学习sklearn19.0聚类算法——Kmeans算法https://blog.csdn.net/loveliuzz/article/details/78783773"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K-means算法思想与原理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://img-blog.csdn.net/20171214211948657?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbG92ZWxpdXp6/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K-means算法过程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://img-blog.csdn.net/20171214212003055?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbG92ZWxpdXp6/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 实例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 引入包\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.animation as animation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 加载数据集\n",
    "def load_dataset(name):\n",
    "    return np.loadtxt(name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#  欧几里得距离\n",
    "def euclidian(a,b):\n",
    "    return np.linalg.norm(a-b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://camo.githubusercontent.com/1164693b40e447b004668355b6925afccf059cfc/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f64633032383161393634656337353863636130326162396566393161376635346163303064346237)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# kmenas 算法\n",
    "def kmeans(k, epsilon=0, distance='euclidian'):\n",
    "    #list to store past centroid\n",
    "    history_centroids = []\n",
    "    #set the distance calculation type \n",
    "    if distance == 'euclidian':\n",
    "        dist_method = euclidian\n",
    "    #set the dataset\n",
    "    dataset = load_dataset('files/data/python61-data/durudataset.txt')\n",
    "    # dataset = dataset[:, 0:dataset.shape[1] - 1]\n",
    "    # get the number of rows (instances) and columns (features) from the dataset\n",
    "    num_instances, num_features = dataset.shape\n",
    "    #define k centroids (how many clusters do we want to find?) chosen randomly \n",
    "    prototypes = dataset[np.random.randint(0, num_instances - 1, size=k)]\n",
    "    #set these to our list of past centroid (to show progress over time)\n",
    "    history_centroids.append(prototypes)\n",
    "    #to keep track of centroid at every iteration\n",
    "    prototypes_old = np.zeros(prototypes.shape)\n",
    "    #to store clusters\n",
    "    belongs_to = np.zeros((num_instances, 1))\n",
    "    norm = dist_method(prototypes, prototypes_old)\n",
    "    iteration = 0\n",
    "    while norm > epsilon:\n",
    "        iteration += 1\n",
    "        norm = dist_method(prototypes, prototypes_old)\n",
    "        #for each instance in the dataset\n",
    "        for index_instance, instance in enumerate(dataset):\n",
    "            #define a distance vector of size k\n",
    "            dist_vec = np.zeros((k,1))\n",
    "            #for each centroid\n",
    "            for index_prototype, prototype in enumerate(prototypes):\n",
    "                #compute the distance between x and centroid\n",
    "                dist_vec[index_prototype] = dist_method(prototype, instance)\n",
    "            #find the smallest distance, assign that distance to a cluster\n",
    "            belongs_to[index_instance, 0] = np.argmin(dist_vec)\n",
    "            \n",
    "        tmp_prototypes = np.zeros((k, num_features))\n",
    "        \n",
    "        #for each cluster (k of them)\n",
    "        for index in range(len(prototypes)):\n",
    "            #get all the points assigned to a cluster\n",
    "            instances_close = [i for i in range(len(belongs_to)) if belongs_to[i] == index]\n",
    "            #find the mean of those points, this is our new centroid\n",
    "            prototype = np.mean(dataset[instances_close], axis=0)\n",
    "            #add our new centroid to our new temporary list\n",
    "            tmp_prototypes[index, :] = prototype\n",
    "        \n",
    "        #set the new list to the current list\n",
    "        prototypes = tmp_prototypes\n",
    "        \n",
    "        #add our calculated centroids to our history for plotting\n",
    "        history_centroids.append(tmp_prototypes)\n",
    "\n",
    "    #return calculated centroids, history of them all, and assignments for which cluster each datapoint belongs to\n",
    "    return prototypes, history_centroids, belongs_to"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 画图\n",
    "# lets define a plotting algorithm for our dataset and our centroids\n",
    "def plot(dataset, history_centroids, belongs_to):\n",
    "    #we'll have 2 colors for each centroid cluster\n",
    "    print(dataset)\n",
    "    colors = ['r', 'g']\n",
    "    #split our graph by its axis and actual plot\n",
    "    fig, ax = plt.subplots()\n",
    "\n",
    "    #for each point in our dataset\n",
    "    for index in range(dataset.shape[0]):\n",
    "        #get all the points assigned to a cluster\n",
    "        instances_close = [i for i in range(len(belongs_to)) if belongs_to[i] == index]\n",
    "        #assign each datapoint in that cluster a color and plot it\n",
    "        for instance_index in instances_close:\n",
    "            ax.plot(dataset[instance_index][0], dataset[instance_index][1], (colors[index] + 'o'))\n",
    "\n",
    "    #lets also log the history of centroids calculated via training\n",
    "    history_points = []\n",
    "    #for each centroid ever calculated\n",
    "    for index, centroids in enumerate(history_centroids):\n",
    "        #print them all out\n",
    "        for inner, item in enumerate(centroids):\n",
    "            if index == 0:\n",
    "                history_points.append(ax.plot(item[0], item[1], 'bo')[0])\n",
    "            else:\n",
    "                history_points[inner].set_data(item[0], item[1])\n",
    "                print(\"centroids {} {}\".format(index, item))\n",
    "\n",
    "                plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#main file \n",
    "def execute():\n",
    "    #load dataset\n",
    "    dataset = load_dataset('files/data/python61-data/durudataset.txt')\n",
    "    #train the model on the data\n",
    "    centroids, history_centroids, belongs_to = kmeans(2)\n",
    "    #plot the results\n",
    "    plot(dataset, history_centroids, belongs_to)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "#do everything\n",
    "execute()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib notebook\n",
    "def plot_step_by_step(dataset, history_centroids, belongs_to):\n",
    "    colors = ['r', 'g']\n",
    "\n",
    "    fig, ax = plt.subplots()\n",
    "\n",
    "    for index in range(dataset.shape[0]):\n",
    "        instances_close = [i for i in range(len(belongs_to)) if belongs_to[i] == index]\n",
    "        for instance_index in instances_close:\n",
    "            ax.plot(dataset[instance_index][0], dataset[instance_index][1], (colors[index] + 'o'))\n",
    "\n",
    "    history_points = []\n",
    "    for index, centroids in enumerate(history_centroids):\n",
    "        for inner, item in enumerate(centroids):\n",
    "            if index == 0:\n",
    "                history_points.append(ax.plot(item[0], item[1], 'bo')[0])\n",
    "            else:\n",
    "                history_points[inner].set_data(item[0], item[1])\n",
    "                print(\"centroids {} {}\".format(index, item))\n",
    "                \n",
    "                plt.pause(0.8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for item in history_centroids:\n",
    "    plot_step_by_step(dataset, [item], belongs_to)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}