05_Clustering

• deals with identifying similarities and differences between different data points

• and dividing data into groups

• clustering usually starts with all data present (without label)

• -> then divides data into differetn groups…

• => does not result in model but clustering of data…

• can be used for pre-processing (e.g. cluster lidar points) to deal with individual clusters rather than all available points…

• take lidar points

• -> cluster them

• -> create hulls representing surrounding obejcts / bodies…

• camera images

• -> segmentation…

• both terms interchangeable…

• -> statistical background: clusetering

• business background: segment

• clustering produces segments and vice versa…

• elements e ∈ E

• cluster c ∈ C with c ⊆ E

  • Union U_{c ∈ C} = E

  • Intersectoin ⋂_{c ∈ C} = ∅

  • => we have datapoints e

  • => we have clusters that are subset of these elements

  • => the union of all cluseters results in the set of datapoints

  • => the intersection of clusters yields the empty set (datapoints can only belong to a single cluster…)

• Representative r_{c} = mean(c)

  • Cluster Center

• Variablility(c) = ∑_{e∈C} distance(r_{c}, e)^2

  • => Sum over the squared distances of all datapoints in cluseter to the cluster center…

  • -> how distributed are the points from the center in each cluster…

• Manhattan

  • |x1 - x2| + |y1 - y2|

    • => sum of absolute x and y distances…

• Euclidian

  • sqrt((x1 - x2)^2 + (y1 - y2)^2)

    • -> basically the true distance

• cebyshev

  • max(|x1 - x2|, |y1 - y2|)

    • maximum (x distance, y distance)

• most important metric in clustering

• -> not only spatial distance but also any numerically representable property (e.g. color, size, weight,…)

• grouping a set of data objects into clusters

• -> cluster: a collection of elements

• -> similar to one another within the same cluster

• -> dissimilar to the objects in other clusters

• no classes (labels) given

• unsupervised learning

• get insights in large datasets

• pre-processing for other algorithms

• distance to representatives

• similarity

• dissimilarity

• silhouette coefficient

• highly dependent on number of clusters

• e.g. only two clusters -> high distances

• almost as many clusters as data points -> small distances…

• individual datapoint based

• average distance to all elements within same cluster

• again individual element based metric

• average distance to all elements of second closest cluster

• -> thus, like similarity but to closest other cluster…

1. start with one cluster per element

2. combine two closest (most similar) clusters

3. repeat until all elements are in one cluster…

• single link

  • smallest distance between two point of differetn clusters (distance between nearest points of clusters…)

• complete link

  • largest distance between two points of different clusters

• average link

  • average distance between all points of one cluster to all points of a differetn cluster

  • => basically calcualte distances to all point combinations and divide by number of combinations…

• “map” to represent clustering…

• root: cluster with all points

• leaf: cluster with one point

• edges: combine two clusters

• depth: distance between two combined clusters

=> gives insight into distribution of datapoints in space…

• see positive and negative …

• => e.g. negative values not reaonale -> similar to second cluster as well….

• => e.g. happens when evenly distributed stuff tried to cluster in two clusters…

• clusters within clusters

• variable densities within dataset

=> idea

• cluster hierarchies

• noise filtering

• generic

  • no cluste rnumber or other parameter must be defined

• visualization

  • dendogram shows hierarchy

• heirarchy:

  • relationship between clusters

• deterministic:

  • generates always same clusters

  
  

• scalability

  • runtime: O(n^3)

• choice:

  • final clustering result (number of clusters) must be chosen from hierarchy

  • => by cutting dendogram at some depth level…

• given desired number of clusters

• -> minimize cluser variability…

=> larege sum of cluster variablilites:

• poor clustering

• or bad choice for k

• e.g. choose a single cluster…

=> minimal sum of cluster variabiliteis

• optimal clustering

• choose one cluster for each dense region…

input:

• number of desired clusters k

• dataset

initializatoin:

• choose k arbitrary representatives

repeat until stable

• assign objects to nearest representatives

• compute center of each cluster as new representative (compute new, do not use existing datapoint…)

• a priori knowlege of an expert

  • e.g. “there are five different types of bacteria” -> k = 5

• search for a good k

  • naive approach: brute force, iterating k = 2,3,4,5,…

  • run hierarchical clustering on subset of data beforehand…

• calculate average silhouette coefficietn for each k

• -> choose k with best value…

• (can e.g. also see negative coefficients -> bad clustering…)

• 0.7

• randomly

• k-means sensitive to initialization

• -> bad initialization can cause bad results

• => not really good to initialize randomly…

naive approach:

• use small random subset D from E

• cluster D and user found representatives in intialization

• still arbitrary choice could yield bad result…

• given dataset E, get m small random subsets

• cluster the subsets and save representatives of each cluster

• cluster the merged set of the subsets

  • m times with the different representatives from each subset

• select representation from the different representatives which yielded best result on the previous step and use for whole dataset

• convex clusters

• -> compare to vronoi model

• partitions space in convex vronoi cells for each point

• => vronoi cell for a point covers area which is nearest to this data point

• => vronoi is result from k-means for its representatives…

• efficiency:

  • O(tkn)

    • n = #objects

    • k = #clusters

    • t = #iterations

  • implementation: easy to use

• applicabilty: mean must exist

• noise: sensitive to outliers

• specification: k must be defined

• initialization: might run into local optimum

• cluster form: convex space partitions

  • no other space shape found…

• k medoios

• k-median clustering

=> different center than mean -> useful when mean not exists (which is not always the case…)

• medoid: representative is not point in space but actual datapoint that is closest to that point…

• use the median of (sorted) cluster

=> half on left side, half on right side…

-> less sensitive to outliers

• influence increases if squared distance is used -> use normal distance…

• implementation: easy to use

• specification: k must be defined

• cluster form: convex space partitions

• initialization: might run into local optimum

• density based clustering application with noise

• two

• epsilon-radius neighborhood

• minimum points (MP)

• core

• border

• outlier

• specify epsilon radius neighborhood

• specify MP

• assign each data point a class

• if there are at least MP number of datapoints in the epsiloin-radious neighborhood

  • -> core point

• if there are less points than MP in e-radius but a core is there

  • -> border

• if less than MP in neighborhood and no core in neighborhood

  • -> outlier

!! count the point in question to the number of MP…

• all points in cluster are reachable from eachother

• -> meaning: we can create path from each point that has only cores in between…

• => endpoints can be border…

• => reachable: epsilon-neighborhood (else: not assigned as border…)

• cluster form: arbitrary (convex and non-convex) space partitions

• specification: k determined automatically

• noise: separates clusters from noise

• efficiency O(n^2)

• specification: parameters difficult to determine

• sensitivity: very sensitive to parameter changes

• news articles based on key words?

• genome patterns -> groups of people

• computing clusters (which to put close together to compute same thing)

• clustering people on social media

• online shopping -> cluster to segment customers and provide customized product suggestions

• netflix -> movie suggestions

• traffic analysis

  • collect mobility data of cars or density of certain reginos

  • use cluseter algos to identify different gorups

    • e.g. commuters, points of interests

  • extract generalization of trajectories and traffic flow

  • use knowledge for city planning and to identify bottlenecks

• cluster lidar datapoints

• classify clustered object from image

• => high level fusion: fuse both to segment image

• => yields object list (position, velocity, classification=)

• overlay lidar and camera image directly

• find clusters in augmented point-cloud

• object detecion and classification based on fused raw data

• raw imate -> pixel segmentation

• raw point cloud

• => fusion

• -> detection & classification

=> give clusters meaning afterwards

• bad clustering

• bad convergence speed

• => sensitive to initialization

O(n log n)