Cluster analysis is a family of statistical and computational methods for answering a deceptively simple question:
Given a collection of things described by several characteristics, can we discover natural groups among them without deciding beforehand what those groups are?
In other words, cluster analysis starts without known labels. You can understand why cluster analysis is useful before training an AI model, as we will eventually do, because labeling data is incredibly time-intensive and therefore labor-intensive. You give the algorithm observations, such as people, plants, archaeological artifacts, musical works, genes, customers, and measurements describing them. Cluster analysis attempts to place relatively similar observations together and relatively dissimilar observations apart
The historical point is that cluster analysis did not originate as someone inventing an abstract mathematical technique and then looking for applications. It developed because researchers repeatedly encountered a practical classification problem: They had large collections of objects with many characteristics and needed a defensible way of determining which objects belonged together without going through them one by one and assigning a label or a relationship to another object.
Early examples came from biology and taxonomy. A taxonomist might have hundreds of specimens characterized by size, shape, anatomical features, habitat, and so forth. Traditional taxonomy depended heavily on expert judgment: These specimens seem sufficiently alike to constitute a species or genus. As datasets grew, researchers wanted to make that judgment more systematic and reproducible and less subjective.
That leads naturally to the core mathematical idea. If every specimen has measurable characteristics, you can define a measure of distance or similarity between every pair. Two specimens with very similar measurements have a small distance; very different specimens have a large distance. Once you have those pairwise distances, you can ask which observations should be joined together.
This produced what became hierarchical clustering. Start with each observation by itself. Join the two most similar observations (or groups), then repeatedly join the closest remaining groups. The result can be represented by something called a dendrogram, essentially a tree showing which objects join and at what level of dissimilarity. Cutting that tree at different heights produces different numbers of clusters.
A somewhat different problem produced partitioning methods, most famously “k-means“. Suppose you know you want, say, five groups in a set of objects. Rather than constructing an entire tree hierarchy, “k-means” seeks five centers and assigns observations to them so that observations are as close as possible to the center of their assigned group. The modern k-means algorithm is generally associated with work done in the 1950s and developed more fully in the 1960s when the term “k-means” was established. We will explore k-means clustering applied to melodies in a future blog.
From the late 1960s, clustering expanded dramatically because essentially the same problem suddenly appeared in many disciplines. Psychologists wanted to discover types of subjects from batteries of metrics. Economists wanted to group markets or consumers. Biologists wanted to group organisms and eventually genes. Computer scientists wanted to group documents, images and patterns. Machine learning consequently absorbed clustering as one of its principal forms of unsupervised learning, a term which has survived into the AI era.
The evolution of cluster analysis can therefore be summarized as how do I classify a bunch of objects (data) with many characteristics, and do so objectively. Then it evolved into grouping the most similar observations, which led to mathematical criteria for what constitutes a “group”, and then to algorithms able to do so with increasingly large and datasets that move from a simple two-dimensional table (like a spreadsheet of data) into data with many dimensions.
There is an important conceptual limitation built into that history: Clusters are not necessarily things that objectively exist in the data. An algorithm will often produce clusters because you asked it to. Results can change substantially depending upon which variables you include, how you scale them, what distance measure you use, and which clustering algorithm you choose. The deeper question for cluster analysis, therefore, not “What clusters did the computer find?” but “Are these clusters stable, interpretable, and meaningful for the problem we’re studying?”
That brings us to the Skiptune musical data. Cluster analysis will let us remove the labels temporarily (composer, decade, genre, etc.) and ask the following question: If the computer knew only had the raw MIDI data of the music, what pieces would it naturally put together? We could then put the labels back afterward and see whether the discovered musical structure corresponds to composer, period, genre, or something nobody explicitly labeled. That is where cluster analysis could become quite interesting. If it turns out that cluster analysis does very well at matching our human labels, we may be able to use it to save time in labeling future tunes we wish to add.
Skiptune is unusually well suited to clustering because we have both the symbolic melodies and extensive metadata. We distinguish clustering the tunes themselves from clustering composers, genres, historical periods, or musical fragments.
Our goal in the next several blogs is to establish an empirical test of how much stylistic information is actually encoded in the melodies themselves. To do that, we will approach cluster analysis from many different angles, as shown in the following table:
| Name of Analysis | Features used for clustering | Question answered |
| Melodic-style clusters | Pitch intervals + duration ratios | Do melodies naturally divide into recognizable styles? |
| Composer clusters | Aggregate melodic features per composer | Which composers are melodically most similar? |
| Historical clusters | Musical features only | Does musical style naturally divide into historical periods? |
| Genre clusters | Musical features only | Do folk, waltz, march, baroque, etc. emerge without labels? |
| Rhythmic clusters | Duration ratios, note density, rhythmic n-grams | What natural rhythmic families exist? |
| Intervallic clusters | Interval distributions/n-grams | What melodic-contour families exist? |
| Tuple clusters | Your (pitch differential, duration ratio) tuples | Do the tuple structures we’ve been using define natural musical families? |
| Transformer-embedding clusters | Learned Skiptune embeddings | What similarity structure did the trained model discover? |
Next week we will walk through our approaches for some of these analyses before diving into the cluster analyses themselves. As you can see from the table, there are a lot of approaches, and we want to order them in a way that makes sense.