ruk·si

Clustering

Updated at 2017-11-13 16:37

Clustering the task of gathering samples into groups of similar samples according to some similarity or measure.

Common applications of clustering:

  • Building customer profiles for market analysis.
  • Grouping related web pages.
  • Grouping related stock quotes for investment portfolio management.
  • Used as a preprocessing step for recommender systems.
  • Building prototype samples for unsupervised feature extraction for supervised learning algorithms.

Terms:

  • Distance Function aka. Metric: Defines how we calculate a distance between two elements of a set. A set with a distance function is called a metric space.
  • Clustering: a collection of clusters or the act of creating clusters.
  • Outlier: an element not belonging to any cluster.
  • Hard Clustering: each element belongs to a cluster or not.
  • Soft/Fuzzy Clustering: each element belongs to a cluster to a certain degree e.g. percentage.
  • Strict Partitioning Clustering: each element belongs to exactly one cluster.
  • Strict Partitioning Clustering with Outliers: each element belongs to exactly one cluster or no cluster. Elements not belonging to a cluster are called outliers.
  • Overlapping Clustering: each element may belong to more than one cluster.
  • Hierarchical Clustering: elements that belong to a child cluster also belong to the parent cluster.

Cluster is always a group of data items. But clusters can have vastly different additional properties, depending on the algorithm that produced them. These sets of additional properties are called cluster models.

Cluster models:

  • Connectivity Models: grouped based on distance connectivity.
  • Centroid Models: define clustering centroids in metric space and each element belongs to the cluster with the shortest centroid distance.
  • Distribution Models: grouped based on statistical distribution of elements.
  • Density Models: connected dense regions in metric space.
  • Subspace Models: groups have relevant attributes in addition to elements.
  • Group Models: instead of forming element groups, provides grouping information.
  • Graph-based Models: two nodes in a graph are in the same cluster if the share an edge.

Clustering methods that work when you have samples and features:

  • k-means: Partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean.
  • Mean Shift: Locate the maxima of a density function given discrete data sampled from that function. Can work better than k-means but not scalable to high number of samples.
  • DBSCAN: Density-Based Spatial Clustering of Applications with Noise. Points are classified as core points, reachable points and outliers. Can detect irregularly shaped clusters and outliers based on density.
  • OPTICS: Ordering Points to Identify the Clustering Structure. DBSCAN variant that handles clusters with different densities much better.

TODO:

  • Locally Linear Embedding: Neighbor-based
  • Isomap: Neighbor-based

Clustering methods that work with affinity matrix of two sample sets:

  • Affinity Propagation: Based on message passing between samples.
  • Spectral Clustering: Finds normalized graph cuts if the affinity matrix is interpreted as an adjacency matrix of a graph.
  • Ward: Hierarchical clustering based on the Ward algorithm.

Sources