week 8

Page 1

in supervised learning : data had labels : spam | no spam ; tumor | no tumor etc

in unsupervised learning : data does not have any lables

training set : { x1x2,x3,......xn}

and algorithm such as clustering are used to assign the labels to the data:

examples of unsupervised learning :

market segments , social network analysis, organize computing clusters, astronomical data analysis

Page 2

K-means algorithm:

how does it work:

input : number of clusters K

training data set : {x1,x2,x3....xn}

for each cluster : define centroid location

assign training set data to each cluster based on distance : c(1) = 2 , c(2) =2 ; etc

for each cluster : compute the new centroid location (Mu-k)

Page 3

Random initialization:

for i = 1 to 100 {

random initialize K clusters to training set data

Run K-means

get ci, cj....cK

Mu1,Mu2...Muk

compute cost function J

}

pick clustering that gave the lowest cost!

Page 4

How to identify number of clusters?

plot cost function J against different values of K (1....10)

see if there is an elbow joint....

then that is the optimal number of cluster;

typically you dont see the elbow;

Number of clusters is difficult to predict due to the ambiguity in data

so you can use a downstream purpose (such as how many Tshirts sizes to manufacture to zoom in on number of Ks)

Page 5

Dimensionality reduction:

when features are redundant or correlated, it is useful to reduce the data from multiple dimensions to few dimensions:

ex., 3D -> 2D

1000D -> 100D;

ie., reduces xi (of dimensions n) to zi (of dimensions <=n)

{x1,x2,x3,....xm} => {z1,z2,z3,....zm}

xi => dimension n ;

zi => dimension <= n ;

Page 6

Principal component analysis:

take an example of 2d data : X1, X2;

objective of PCA : find a vector U ; such that

projection of the 2D data on the vector , will minimize the projection error

in case of 3D data : project the 3D point cloud data on to 2D surface;

Page 7

How to compute the PCA?

Step 1 : Use Feature Scaling

Step 2: compute covariance matrix : sigma = 1/m *( sigma: xi*xiT)

Step 3: Compute Eigen vectors U : from above sigma

Step 4: use first k columns of U

Page 8

Choosing the number of dimensions 'k': PCA

step 1: try PCA with k=1,2,3,4,

step 2: compute Uresuce , z1,z2,,,,,zm; x1-approx,x2-approx,...xm-approx;

step 3: compute sigma [(xi - xapprox)^2] ( 1 to m)

step 4 : compute variance of data 1/m *sigma(xi^2)

step 5: verify if step3/step5 <= 1% ;

choose the min k that satisfies above criteria!

Page 9

advice for applying PCA:

PCA is mapping of X =>E=>R^nto z=>E=>R^k

PCA can be used for speed up of supervised learning algorithms:

h-theta(x) = 1/1+e-thetaT*x => h-theta(z) = 1/1+e-thetaT*z;

reduce memory / disk size needed to store the data

Misuse of PCA: where PCA should be avoided

PCA should not be used for addressing problem of overfitting; regularization should be used

PCA should not be the first choice for running unsupervised algorithms; try running with raw data first;