Cluster rows

Status

Variants

Cluster rows by density

Find clusters as dense regions of rows, without fixing their number, and leave sparse rows as noise.

Build a hierarchy of clusters

Merge or split rows step by step into a tree of clusters, then cut the tree to get a flat clustering.

Other clustering methods

Cluster rows by methods outside the main families, such as support vector clustering or neighbourgrams.

Partition rows into a set number of clusters

Assign each row to one of a chosen number of clusters by nearest centre, as k-means and k-medoids do.

What other tools call it

Meridian's classification; an independent blind rating agreed on 86.2% of 312 rows (exact class, version 2).

Background

When to use it

The right clustering algorithm and its parameters, such as the distance function, a density threshold or the number of expected clusters, depend on the data set and the intended use of the results.^[1] Cluster analysis is not an automatic task but an iterative process of knowledge discovery that involves trial and failure.^[1] Clustering often means changing the data preprocessing and the model parameters until the result has the desired properties.^[1] Treat a first clustering as a draft: change the columns, the scaling and the settings, and see which groups survive. (Meridian's view)

Most algorithms of the k-means type, which assign each object to the cluster with the nearest mean, need the number of clusters, k, to be given in advance.^[1][2] The k-means algorithm cannot find non-convex clusters, and most traditional clustering methods assume clusters of a spherical, elliptical or convex shape.^[1] An algorithm designed for one kind of cluster will generally fail on a data set whose clusters are of a radically different kind.^[1] Before choosing an algorithm, ask what shape the groups in the rows are likely to have, and whether every row should belong to one. (Meridian's view)

In KNIME, the k-Means node uses the Euclidean distance on the selected columns and does not normalise the data, suggesting a Normalizer node as a preprocessing step where required.^[3] Put numeric columns on comparable scales before any clustering by distance, and treat the choice of columns as part of the answer. (Meridian's view)

The k-means algorithm always converges given enough time, but possibly to a local minimum that depends heavily on the starting cluster centres, or centroids.^[4] Because the result depends on the starting centroids, k-means is often run several times with different initialisations.^[4][1] In KNIME's k-Means node, random initialisation takes the starting centroids from random rows of the input table, and a static random seed makes the result reproducible.^[3] Fix and record the seed whenever a clustering is meant to be rerun and compared. (Meridian's view)

Evaluating a clustering is as difficult as the clustering itself.^[1] Neither a single quality score computed from the clustered data nor a comparison with an existing ground-truth classification can ultimately judge a clustering's quality, which needs human evaluation.^[1] Read clusters as a hypothesis about the rows, to be checked against what the rows are, rather than as a finding. (Meridian's view)

The method

Typical cluster models include connectivity models such as hierarchical clustering, centroid models such as k-means, distribution models and density models.^[1] A clustering may be a strict partitioning, in which each object belongs to exactly one cluster, or may let objects belong to no cluster, in which case they are considered outliers.^[1] In a hierarchical clustering, objects that belong to a child cluster also belong to the parent cluster.^[1]

In centroid-based clustering, each cluster is represented by a central vector, which is not necessarily a member of the data set.^[1] k-means clustering partitions n observations into k clusters so as to minimise the within-cluster sum of squares.^[2] The standard k-means algorithm alternates an assignment step, which puts each observation in the cluster with the nearest mean, and an update step, which recalculates each cluster's mean.^[2] The term k-means was first used by James MacQueen in 1967, though the idea goes back to Hugo Steinhaus in 1956.^[2] The standard k-means algorithm was first proposed by Stuart Lloyd of Bell Labs in 1957 as a technique for pulse-code modulation, though it was not published as a journal article until 1982.^[2] Variations of k-means restrict the centres to members of the data set (k-medoids), use medians (k-medians), choose the initial centres less randomly (k-means++) or allow a fuzzy assignment (fuzzy c-means).^[1]

Hierarchical clustering connects objects by distance and builds a hierarchy of clusters that merge at different distances, which a dendrogram draws as a tree.^[1] Besides a distance function, hierarchical clustering needs a linkage criterion, such as single linkage (the minimum distance between points) or complete linkage (the maximum distance).^[1] Hierarchical clustering can be agglomerative, starting from individual elements and merging them, or divisive, starting from the full data set and splitting it.^[1] A specific clustering is obtained from the hierarchy by selecting a cut level in the dendrogram, which determines how many clusters are formed.^[1] In the general case, agglomerative clustering has a complexity of O(n³), which makes it computationally expensive for large data sets.^[1] KNIME's Hierarchical Clustering node works only on small data sets, because it keeps the entire data in memory and has cubic complexity.^[5]

Model-based clustering models the data as arising from a mixture of probability distributions, and one prominent method fits Gaussian mixture models with the expectation-maximisation algorithm.^[1]

In density-based clustering, clusters are areas of higher density than the rest of the data set, and objects in the sparse areas that separate them are usually considered noise and border points.^[1] Density-based spatial clustering of applications with noise (DBSCAN) was proposed by Martin Ester, Hans-Peter Kriegel, Jörg Sander and Xiaowei Xu in 1996.^[6] DBSCAN does not require the number of clusters to be specified in advance, and it marks as outliers points that lie alone in low-density regions.^[6] A DBSCAN cluster can take an arbitrary shape, in contrast to many other methods.^[1] DBSCAN expects a drop in density at cluster borders, so on overlapping Gaussian distributions the borders it produces will often look arbitrary.^[1]

Compared with the alternatives

The unsupervised k-means algorithm is often confused with the supervised k-nearest neighbour classifier because of the name.^[2] Applying a 1-nearest neighbour classifier to the cluster centres found by k-means classifies new data into the existing clusters, which is known as the nearest centroid classifier.^[2] If ground-truth labels for the objects were available, there would be no need to cluster, and in practical applications such labels are usually missing.^[1] Where every row already carries a known class, a supervised classifier answers a sharper question than clustering does. (Meridian's view) Where a column already says which group a row belongs to, grouping by that column is simpler and exact; clustering is for when no such column exists. (Meridian's view)

Sources

1. [1]Cluster analysis - Wikipediasecondary source
2. [2]k-means clustering - Wikipediasecondary source
3. [3]k-Meansdocumentation
4. [4]2.3. Clustering — scikit-learn 1.9.1 documentationdocumentation
5. [5]Hierarchical Clusteringdocumentation
6. [6]DBSCAN - Wikipediasecondary source