{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%matplotlib inline\n",
"import pandas as pd\n",
"\n",
"import numpy as np\n",
"from __future__ import division\n",
"import itertools\n",
"\n",
"import matplotlib.pyplot as plt\n",
"import seaborn as sns\n",
"plt.rcParams['axes.grid'] = False\n",
"plt.rcParams['figure.figsize'] = (10,16)\n",
"\n",
"import logging\n",
"logger = logging.getLogger()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"7 Clustering\n",
"=======\n",
"\n",
"**Goal**: points in the same cluster have a small distance from one other, while points in different clusters are at a large distance from one another."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 7.1 Introduction to Clustering Techniques\n",
"#### 7.1.1 Points, Spaces, Distances\n",
"A dataset suitable for clustering is a collection of points, which are objects belonging to some space.\n",
"\n",
"distance measure: \n",
"1. nonnegative. \n",
"2. symmetric. \n",
"3. obey the triangle inequality. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### 7.1.2 Clustering Strategies\n",
"two groups: \n",
"1. Hierarchinal or agglomerative algorithms. \n",
" Combine, bottom-to-top.\n",
" \n",
"2. Point assignment. \n",
" iteration\n",
" \n",
" \n",
"A key distinction: \n",
"Euclidean space can summarize a collection of points by their *centroid*."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 7.1.3 The Curse of Dimensionality\n",
"It refers that a number of unintuitive properties of high-dimensional Euclidean space.\n",
"\n",
"1. Almost all pairs of points are equally far away from one another.\n",
"\n",
"2. Almost any two vectors are almost orthogomal.\n",
"\n",
"`%todo: Proof`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### 7.1.4 Exercises for Section 7.1\n",
"##### 7.1.1\n",
"\\begin{align}\n",
"E[d(x,y)] &= \\int_{y=0}^1 \\int_{x=0}^1 |x - y| \\, \\mathrm{d}x \\, \\mathrm{d}y \\\\\n",
" &= \\int_{y=0}^1 \\int_{x=0}^{y} (y-x) \\, \\mathrm{d}x + \\int_{x=y}^{1} (x-y) \\, \\mathrm{d}x \\, \\mathrm{d}y \\\\\n",
" &= \\int_{y=0}^1 \\frac{1}{2} y^2 + \\frac{1}{2} (1-y)^2 \\, \\mathrm{d}y \\\\\n",
" &= \\frac{1}{3}\n",
"\\end{align}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### 7.1.2 \n",
"Because: $$\\sqrt{\\frac{{|x_1|}^2+{|x_2|}^2}{2}} \\geq \\frac{|x_1|+|x_2|}{2}$$\n",
"We have:\n",
"$$\\sqrt{\\frac{{|x_1 - x_2|}^2+{|y_1 - y_2|}^2}{2}} \\geq \\frac{|x_1 - x_2|+|y_1 - y_2|}{2}$$\n",
"So:\n",
"$$E[d(\\mathbf{x}, \\mathbf{y})] \\geq \\frac{\\sqrt{2}}{3}$$\n",
"\n",
"While:\n",
"$$\\sqrt{{|x_1 - x_2|}^2+{|y_1 - y_2|}^2} \\leq |x_1 - x_2|+|y_1 - y_2|$$\n",
"So:\n",
"$$E[d(\\mathbf{x}, \\mathbf{y})] \\leq \\frac{2}{3}$$\n",
"\n",
"Above all:\n",
"$$\\frac{\\sqrt{2}}{3} \\leq E[d(\\mathbf{x}, \\mathbf{y})] \\leq \\frac{2}{3}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### 7.1.3\n",
"for $x_i y_i$ of numerator, there are four cases: $1=1\\times1, 1=-1\\times-1$ and $-1=1\\times-1, -1=-1\\times1$. So both 1 and -1 are $\\frac{1}{2}$ probility. So the expected value of their sum is 0.\n",
"\n",
"Hence, the expected value of cosine is 0, as $d$ grows large. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 7.2 Hierarchinal Clustering\n",
"This algorithm can only be used for relatively small datasets.\n",
"\n",
"procedure: \n",
"We begin with every point in its own cluster. As time goes on, larger clusters will be constructed by combining two smaller clusters. \n",
"Hence we have to decide in advance: \n",
"\n",
"1. How to represent cluster? \n",
" + For Euclidean space, use centriod. \n",
" + For Non-Euclidean space, use clustroid. \n",
" **clustroid**: \n",
" - the point is close to all the points of the cluster. \n",
" - minimizes the sum of the distance to the other points. \n",
" - minimizes the maximum distance to another point. \n",
" - minimizes the sum of the squares of the distances to the other points. \n",
"\n",
"2. How to choose clusters to merge? \n",
" + shortest distance between clusters. \n",
" + the minimum of the distance between any two points. \n",
" + the average distance of all pairs of points. \n",
" + Combine the two clusters whose resulting cluster has the lowerst radius(the maximum distance between all the points and the centriod). \n",
" modification: \n",
" - lowest average distance between a point and the centriod. \n",
" - the sum of the squares of the distances between the points and the centriod. \n",
" + Cobine the two clusters whose resulting cluster has the smallest diameter(the maximum distance between any two points of the cluster). \n",
" The radius and diameter are not related directly, but there is a tendecy for them to be proportional.\n",
"\n",
"3. When to stop? \n",
" + how many clusters expected? \n",
" + When at some point the best combination of existing clusters produces a cluster that is inadequate. \n",
" - threshold of average distance of points to its centriod. \n",
" - threshold of the diameter of the new cluster. \n",
" - threshold of the density of the new cluster. \n",
" - track the average diameter of all the current clusters. stop if take a sudden jump.\n",
" + reach one cluster. $\\to$ tree. \n",
" eg. genome $\\to$ common ancestor. \n",
" \n",
"There is no substantial change in the option for stopping citeria and combining citeria when we move from Euclidean to Non-Euclidean spaces."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"
\n",
" \n",
" \n",
" | \n",
" cluster | \n",
" x | \n",
" y | \n",
"
\n",
" \n",
" \n",
" \n",
" | 0 | \n",
" 0 | \n",
" 4 | \n",
" 10 | \n",
"
\n",
" \n",
" | 1 | \n",
" 1 | \n",
" 7 | \n",
" 10 | \n",
"
\n",
" \n",
" | 2 | \n",
" 2 | \n",
" 4 | \n",
" 8 | \n",
"
\n",
" \n",
" | 3 | \n",
" 3 | \n",
" 6 | \n",
" 8 | \n",
"
\n",
" \n",
" | 4 | \n",
" 4 | \n",
" 3 | \n",
" 4 | \n",
"
\n",
" \n",
" | 5 | \n",
" 5 | \n",
" 10 | \n",
" 5 | \n",
"
\n",
" \n",
" | 6 | \n",
" 6 | \n",
" 12 | \n",
" 6 | \n",
"
\n",
" \n",
" | 7 | \n",
" 7 | \n",
" 11 | \n",
" 4 | \n",
"
\n",
" \n",
" | 8 | \n",
" 8 | \n",
" 2 | \n",
" 2 | \n",
"
\n",
" \n",
" | 9 | \n",
" 9 | \n",
" 5 | \n",
" 2 | \n",
"
\n",
" \n",
" | 10 | \n",
" 10 | \n",
" 9 | \n",
" 3 | \n",
"
\n",
" \n",
" | 11 | \n",
" 11 | \n",
" 12 | \n",
" 3 | \n",
"
\n",
" \n",
"
\n",
"
\n",
"
\n",
" \n",
" \n",
" | \n",
" cluster | \n",
" x | \n",
" y | \n",
"
\n",
" \n",
" \n",
" \n",
" | 0 | \n",
" 0 | \n",
" 4 | \n",
" 10 | \n",
"
\n",
" \n",
" | 1 | \n",
" 0 | \n",
" 7 | \n",
" 10 | \n",
"
\n",
" \n",
" | 2 | \n",
" 0 | \n",
" 4 | \n",
" 8 | \n",
"
\n",
" \n",
" | 3 | \n",
" 0 | \n",
" 6 | \n",
" 8 | \n",
"
\n",
" \n",
" | 4 | \n",
" 0 | \n",
" 3 | \n",
" 4 | \n",
"
\n",
" \n",
" | 5 | \n",
" 0 | \n",
" 10 | \n",
" 5 | \n",
"
\n",
" \n",
" | 6 | \n",
" 0 | \n",
" 12 | \n",
" 6 | \n",
"
\n",
" \n",
" | 7 | \n",
" 0 | \n",
" 11 | \n",
" 4 | \n",
"
\n",
" \n",
" | 8 | \n",
" 0 | \n",
" 2 | \n",
" 2 | \n",
"
\n",
" \n",
" | 9 | \n",
" 0 | \n",
" 5 | \n",
" 2 | \n",
"
\n",
" \n",
" | 10 | \n",
" 0 | \n",
" 9 | \n",
" 3 | \n",
"
\n",
" \n",
" | 11 | \n",
" 0 | \n",
" 12 | \n",
" 3 | \n",
"
\n",
" \n",
"
\n",
"