{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem in KMeans\n",
"\n",
"While KMeans is a good algorithm, the time complexity is very poor. Kmeans works in $O(n \\cdot K \\cdot I \\cdot f)$ Where \n",
"n is number of records, K is number of clusters, I is number of iterations, f is number of features in particular record. Clearly, the algorithm will take forever to complete on a dataset of > 100,000 data points.\n",
"\n",
"## Minibatch KMeans\n",
"\n",
"Main features of Minibatch KMeans are:\n",
"1. Instead of using the entire dataset at once, it operates in batches.\n",
"2. Uses Gradient Descent update, which is way more faster than what KMeans does. \n",
"\n",
"How it works is, it takes batches of datasets and finds the centroids for the smaller dataset (minibatch) Then for the next batch, it uses the centroid found in previous batch and updates it using Gradient Descent. This simple method makes it faster by a magnitude of the input size. \n",
"\n",
"\n",
"## Gotchas of using Minibatch KMeans\n",
"1. While the performance is good, the result might or might not be good -- it totally depends on the __initial conditions__.\n",
"2. The result might be somewhat different than what is obtained from KMeans. "
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" | \n",
" CustomerID | \n",
" Genre | \n",
" Age | \n",
" Annual Income (k$) | \n",
" Spending Score (1-100) | \n",
"
\n",
" \n",
" \n",
" \n",
" | 0 | \n",
" 1 | \n",
" Male | \n",
" 19 | \n",
" 15 | \n",
" 39 | \n",
"
\n",
" \n",
" | 1 | \n",
" 2 | \n",
" Male | \n",
" 21 | \n",
" 15 | \n",
" 81 | \n",
"
\n",
" \n",
" | 2 | \n",
" 3 | \n",
" Female | \n",
" 20 | \n",
" 16 | \n",
" 6 | \n",
"
\n",
" \n",
" | 3 | \n",
" 4 | \n",
" Female | \n",
" 23 | \n",
" 16 | \n",
" 77 | \n",
"
\n",
" \n",
" | 4 | \n",
" 5 | \n",
" Female | \n",
" 31 | \n",
" 17 | \n",
" 40 | \n",
"
\n",
" \n",
"
\n",
"