Unsupervised Learning
Clustering: K-means Algorithm
K-means Algorithm:
- randomly initialize K cluster centroids $\mu_1,\mu_2,...,\mu_K$
- cluster assignment: for i=1:m, $c^{(i)}$:=index of cluster centroid closest to x(i)
- move centroid: for k=1:K, $\mu_k$:=average (mean) of points assigned to cluster k
-
Input:
-
K(number of clusters)
-
Training set {$x^{(1)},x^{(2)},...,x^{(m)}$}
-
K-means Optimization Objective:
min\,J(c^{(1)},...,c^{(m)},\mu_1,...,\mu_K) = \frac{1}{m}\sum_{i=1}^m||\,x^{(i)}-\mu_{c^{(i)}}||^2
- $c^{(i)}$ = index of cluster (1,2,...,K) to which example x(i) is currently assigned
- $\mu_k$ = cluster centroid k
- $\mu_{c^{(i)}}$ = cluster centroid of cluster to which example x(i) has been assigend
Random Initialization
- should have K < m
- randomly pick K training examples
- Set $\mu_1,...,\mu_K$ equal to these K examples
For i = 1:100 {
Randomly initialize K-means
Run K-means. Get $c^{(1)},...,c^{(m)},\mu_1,...,\mu_K$
Compute cost function (distortion) $J(c^{(1)},...,c^{(m)},\mu_1,...,\mu_K)$
}
=>Pick clustering that gave lowest cost J
Dimensionality Reduction: Principal Component Analysis (PCA)
Purposes:
- To reduce the dimension of the input data so as to speed up a learning algorithm
- To compress data to reduce the memory of disk space
- To visualize high-dimensional data (by choosing k=2 or 3)
PCA Algorithm
- Data Preprocessing(feature scaling/mean normalization)
- Compute "covariance matrix"
Σ(Sigma) = \frac{1}{m}\sum_{i=1}^n(x^{(i)})(x^{(i)})^T
-
Compute “eigenvectors” of matrix Σ(Sigma):
[U,S,V] = svd(Sigma); -
$U_{reduce} = U(:, 1:k)$
-
z = $U_{reduce}'*x$
Reconstruction from compressed representation
$X_{approx} = U_{reduce} * Z$
Choosing the number of principal components k
