unsupervised learning

notation

classification

Predict categorical labels

regression

Predict continuous-valued \n labels

unsupervised vs supervised data set

unsupervised is unlabeled, supervised is labeled

applications of clustering

* google news
* market segmentation
* social network analysis

clusters

Find natural groupings among observations and segment observations into clusters/groups such that objects within a cluster have high similarity (high intra cluster similarity) and objects across clusters have low similarity (low intra cluster similarity)

clustering algorithms

automatically find ‘classes’

challenges of unsupervised learning

* no simple goal
* validation of results is subjective
* often used more in exploratory data analysis

why use unsupervised learning

* labeled data is expensive and difficult to collect, whereas unlabeled data is cheap and abundant
* compressed representation saves on storage and computation
* reduce noise and irrelevant attributes in high dimensional data
* pre-processing step for supervised learning

clustering is

unsupervised classification

distance functions

Measures the strength of relationship between any two feature vectors

properties of distance functions

* Distance between two points is always non-negative
* Distance between a point to itself is zero
* Distance is symmetric
* Distance satisfies a triangle inequality

distance function takeaways

* Different choice of distance functions yields different measures of similarity
* Distance functions implicitly assign more weighting to features with large anges than to those with small ranges
* Rule of thumb: when no a priori domain knowledge is available, clustering should follow the principle of equal weightings to each attribute \[Mirkin, 2005\]
* This necessitates need for normalization/data pre-processing/feature scaling of feature vectors.

normalisation of feature vectors

attributes contribute approximately equally to the similarity measure

min-max normalisation

* all feature attributes rescaled to lie in the range \[0,1\]
* sensitive to outliers

Z-score standardization

* all feature attributes have mean 0 and standard deviation 1
* not bounded range

distance matrix

types of clustering algorithms

* partitional
* hierarchical
* model-based

partitional clustering algorithm

* Generates a single partition of the data to recover natural clusters
* Input: Feature vectors
* Examples: K-means, K-medoids

Hierarchical

* Generates a sequence of nested partitions
* Input: Distance Matrix
* Example: agglomerative clustering, divisive clustering

Model-Based

* Assumes that data is generated i.i.d. from a mixture of distributions, each of which determines a different cluster
* Example: Expectation-Maximization (EM)

measure of intra-cluster similarity

* Commonly used distance measure: squared Euclidean distance
* Centroid of a cluster is usually taken as the average of all examples in the cluster
* Variability determines how compact the cluster is

Dissimilarity within a clustering structure 𝑪

optimisation problem

* Find a clustering structure 𝑪 of K clusters that minimizes the following objective (see image)
* Larger clusters with high variability are penalized more than smaller clusters with high variability
* Under squared Euclidean distance, minimizing 𝑑𝑖𝑠𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑡𝑦 𝑪 is equivalent to maximizing overall inter-cluster dissimilarity (will see this in detail later).

finding the exact solution of the dissimilarity problem is

prohibitively hard and infeasible when large number of examples present

iterative greedy algorithms

* Provide a sub-optimal approximate solution
* includes K-means, K-medoids