Clusters are formed by similar patterns. One common similarity metric is distance:
- Euclidean distance: shortest distance between two points
- Manhattan distance: distance between two points measured along axis at right angles
Clustering algorithms are NP-hard problems, so the number of possible ways to cluster items increases exponentially. So we look for efficient ways to find good clusters using a combination of metric and heuristic search.