Chapter 4

• In clustering the class labels of training data are unknown

• Given a set of measurements, observations with the aim of establishing the existence of classes or clusters in the data

  
  

• Classification is supervision for training data are accompanied by labels indicating the class of the observations

  • Classes are known in advance

• Data is classified based on information extracted from the training set

• Grouping a set of data objects into clusters which are collections of data objects

  • Similar to one another within the same cluster

  • This is similar to the objects in other clusters

• As a stand-alone tool to get insight into data distribution

• As a preprocessing step for other algorithms

• Preprocessing - as a data reduction

• Pattern recognition

• Image processing

• Spatial data analysis (creating thematic maps)

• Business intelligence

• Biology e.g. clustering of gene expression data

• Partitioning algorithms

• Probabilistic Model-Based Clustering

• Density-based (connectivity and density functions)

• Hierarchical algorithms

• Choose k representatives for clusters e.g. randomly

• Improve these representatives randomly iteratively:

  • assign each object to the cluster it “fits best” in the current clustering

  • Compute new cluster representatives based on these assignments

  • Repeat until the change in the objective function from one iteration to the next drops below a threshold

• By the center of the cluster in k-means

• By one of its objects in k-medoid

  
  

Idea

• Find a clustering such that the intra-cluster variation of each cluster is small and use the center of the centroid as representative

Objective

• For a given k, form k groups so that the sum of the (squared) distances between the mean of the groups and their elements is minimal

• Objects p = (p1,…,pd) are points in a d-dimensional vector space

• Optimal partitioning: argmin SSE(C) is NP-hard

• For a given set of points P = p1,…,pk, a Voronoi diagram partitions the data space into Voronoi cells, one cell per point

• The cell of a point p covers all data points in the data space for which p is the nearest neighbor among the points from P

  
  

• The Voronoi cells of two neighbouring points pi, pj are separated by the perpendicular hyperplane between pi and pj

• Voronoi cells are intersections of half spaces and this convex regions

• Relatively efficient: O(tkn

  • n: # objects

  • k: # clusters

  • t # iterations

• Easy implementation

• Applicable only when the mean is defined

• Need to specify k, the number of clusters, in advance

• Sensitive to noisy data and outliers

• Clusters are forced to convex space partitions (Voronoi cells)

• Result and runtime strongly depend on the intial partition; often terminates at a local optmum: however methods for a good intialization exist

• Median: (artificial) representative object “in the middle”

• Mode: value that appears most often

• Medoid: representative object “in the middle”

• Find k representatives so that the sum of total distances (TD) between objects and their closest representative is minimal (more robust against outliers)

• If there is an ordering on the data use median instead of mean

• Compute median separately per dimension

• Choose sample A of the dataset

• Cluster A and use centers as initialization

• Select first center uniformly at random

• Choose next point with probability proportional to the squared distance to the nearest center already chosen

• Repeat until k centers have been selected

• Guarantees an approximation ratio of O(logk)

• Repeat with different initial centers and choose result with lowest clustering error

• Quality measure for k-means or k-medoid clusterings that is not monotonic over k

• Monotonic means that an increase in k does not guarantee an increase or decrease in the quality of the clustering

• How good is the clustering = how appropriate is the mapping of objects to clusters

• Elements in cluster should be “similar to their representative

  • measure the average distance of objects to their representative

• Elements in different clusters should be “dissimilar

  • measure the average distance of objects to alternative clusters (i.e. second close cluster)

• Statistical approach for finding maximum likelihood estimates of parameters in probabilistic models

• EM can be used as a clustering algorithm

• Define clusters as probability distributions -> each object has a certain probability of belonging to each cluster

• Iteratively improve the parameters of each distribution until some qiu

• Non-linear mutual dependencies

• Optimizing the Gaussian of cluster j depends on all other Gaussians

• There is no closed-form solution

• Approximation through iterative optimization procedures

• Break the mutual dependencies by optimizing the cluster means and s.d. independently

• EM obtains a soft clustering (each object belongs to each cluster with a certain probability) reflecting the uncertainty of the most appropriate assignment

• It is modified to obtain a partitioning variant: assign each object to the cluster to which is belongs with the highest probability

• Superior to k-Means for clusters of varying size or clusters having differing variances

  • more accurate data representation

• Computational effort for t iterations = O(tnk), t is quite high in many cases

• Strongly dependent on the initial assignment

  • do multiple random starts and choose the final estimate with highest likelihood

  • initialize with clustering algorithms

  • local maxima and initialization issues have been addressed in EM extensions

• Also depend on a proper choice of k

• If k is too high, the mixture may overfit the data

• If k is too love, the mixture may not be flexible enough to approximate the data

Find modes in the point density

1. Select a window size epsilon and a starting position m

2. Calculate the mean of all points inside the window W(m)

3. Shift the window to that position

4. Repeat until convergence

• Apply iterative mode search for each data point. Group those that converge to the same mode (basin of attraction)

• It has a relatively high complexity

• Clusters can have arbitrary shape/size -> no restriction to convex shapes

• Number of clusters is determined automatically

• Robust to outliers

• Easy implementation and parallelization

• Single parameter - epsilon

• Suppose by spatial indexing to reduce complexity

• Clusters are dense regions in the data space, separated by regions of lower density

By 2 parameters:

• epsilon radius for the neighbourhood of point q

  • N_eps(q) = {p in D | dist(p,q) <= eps}

• MinPts: minimum number of points in the given neighbourhood N_eps(q)

Core point:

• q is called a core point w.r.t eps, MinPts if |N_eps(q)| >= MinPts

Density-reachable:

• p is directly density-reachable from q w.r.t. eps, MinPts if:

1. p is in N_eps(q) and

2. q is a core object w.r.t eps, MinPts

Density-connected:

• p is density-connected to a point q w.r.t. eps, MinPts if there is a point o such that both, p and q are density-reachable from o w.r.t eps, MinPts

• Maximality:

  • if q is in C and p is density-reachable from q then p is in C

• Connectivity:

  • Each object in C is density-connected to all other objects in C

• Density-Based Spatial Clustering of Applications with Noise

1. Fix a value for MinPts (default 2d-1)

2. Compute the k-distance for all points p in D (distance from p to its nearest k-neighbour), with k=MinPts

3. Create a k-distance plot, showing the k-distances of all objects, in decreasing order

4. The user selects “border object” o from the MinPts-distance plot: eps is set to MinPts-distance(o)

• DBSCAN can be efficiently built on top of similarity join operations

• For very large DB, efficient join techniques are available

• Input parameters may be difficult to determine

• In some situations very sensitive to input parameters setting

• Clusters can have arbitrary shape and size -> no restriction to convex shapes

• Number of clusters is determined automatically

• Can separate clusters from surrounding noise

• Good complexity O(n^2)

• Can be supported by spatial index structures -> O(nlogn)

1. Construct fully-connected KNN graph with eps neigbourhood

2. Created adjacency, degree, laplacian matrix

3. Compute eigenvalues, eigenvalues of L matrix, select top eigenvectors

4. Apply k-means on k eigenvectors

5. Map results back to original data

• Easy to implement (cap)

• No assumptions on the shape of the clusters

• May be sensitive to the construction of the similarity graph

• Slow runtime - k smallest eigenvectors can be computed in O(n^3)

• Hierarchical decomposition of the dataset into a set of nested clusters, given a set of nested clusters

• Results represented by dendrogram

  • Nodes in the dendrogram represent possible clusters

  • Dendrograms can be constructed bottom up (agglomerative approach) or top down (divisive aproach)

• The root represents the whole dataset

• A lead represents a single object in the data set

• An internal node represents the union of all objects in its sub tree

• The height of an internal node represents the distance between its two child nodes

1. Initially each object forms its own cluster

2. Consider all pairwise distances between initial clusters

3. Merge the closest pair (A,B) in the set of the current clusters into a new cluster C = A U B

4. Remove A and B from the set of current clusrters, insert C

5. If the set of current clusters contains only C, STOP

6. Else: determine the distance between C and all other clusters in the set of current clusters and go to step 3

• Agglomerative hierarchical clustering begins by treating each individual data point as its own cluster. It then iteratively merges the most similar clusters until all the data points belong to a single, large cluster.

• It requires a distance function for clusters

• Single-link: min distance between 2 elements in diff clusters

• Complete-link: max distance between 2 elements in diff clusters

• Average-link: the average distance between all points in diff clusters

• Initially all objects form one cluster

• Repeat until all clusters are singletons:

  • Choose a cluster to split

  • Replace the chose cluster with the sub-clusters and split into two

    
    

• Top down divisive clustering method

• Both need n-1 steps

  • Agg has to consider (n,2) combinations in the first step

  • Div has to potentially consider 2^(n-1) -1 possibilities to split the data

• Div more complex since it needs a second “flat” clustering algorithm to split

• Agg decides based on local patterns

• Div uses global data distribution

Ordering Points To Identify the Clustering Structure

• Density based hierarchical clustering algorithm

Main idea:

• Visit each point

  • Always make a shortest jump

• Maintain two data structures

  • seedList: stores all objects with shortest reachability distance seen so far (‘distance of a jump to that point’) in ascending order; organized as a heap

  • clusterOrder: resulting cluster order is constructed sequentially (order of objects + reachability distances)

• Plot the points together with their reachability distances. Use the order in whih they were returned by the algorithm, this plot:

  • represents the density-based clustering structure

  • is easy to analyse

  • independent of the dimensionality of the data

  • significant valleys represent clusters

• Relative insensitivity to parameter settings

• Good result if parameters are just “large enough”

• May not scale well

  • Runtime O(n^2logn^2) for standard methods, O(n^2) for OPTICS

• User has to choose final clustering

• Does not require the number of clusters to be known in advance

• No (standard methods) or very robust parameters (OPTICS)

• Computes a complete hierarchy of clusters

• Good result visualizations integrated into the methods

• A “flat” partition can be derived afterwards (via cut through dendrogram or reachability plot)

• Given a dataset D, a clustering C = C1,…,Ck and a ground truth G = G1,…Gl

• Instead of comparing cluster and ground truth labels directly, consider all pairs of objects. Check whether they have the same label in G and if they have the same in C.

• They are suitable for convex clusters, but not for stretched clusters