Algorithmic Clustering of Music

by Rudi Cilibrasi, Paul Vitányi and Ronald de Wolf

A fully automatic method for music classification has been developed at CWI. It is based only on compression of strings that represent the music pieces. The method uses no background knowledge about music whatsoever: it is completely general and can, without change, be used in different areas like linguistic classification and genomics. It is based on an ideal theory of the information content in individual objects (Kolmogorov complexity), information distance, and a similarity metric.

Recognition of similarities between music pieces is crucial for the design of efficient music information retrieval systems. The ever increasing wealth of digitized music on the Internet calls for an automated organisation of the material based on similarity, which enables users to navigate and which gives them advice. Current methods of automated classification utilize specific musical features related to pitch, rhythm, harmony, etc., just as a human expert categorizes the material manually. One can extract such features using for instance Fourier transforms or wavelet transforms, and classification is done by existing software, based on various standard statistical pattern recognition classifiers, Bayesian classifiers, hidden Markov models, ensembles of nearest-neighbour classifiers, or neural networks. However, this approach requires specific and detailed knowledge of the problem area, since one needs to know what features to look for.

Our approach does not require specific musical knowledge, as it is based on a general mathematical theory of similarity. It uses a metric derived from the notion of ’information distance’. Roughly speaking, two objects (represented as strings of bits) are close if we can significantly compress one given the information in the other. Compression is based on the ideal notion of Kolmogorov complexity, which unfortunately is not effectively computable. Hence we replace this ideal version by standard compression techniques (the program bzip2). We lose theoretical optimality in some cases, but gain an efficiently computable similarity metric. This new metric has been shown to work well in very different applications, including the fully automatic construction of the phylogeny tree based on whole mitochondrial genomes and of a language tree for over 50 Euro-Asian languages, as well as the detection of plagiarism in student programming assignments, and the phylogeny of chain letters.

The result for a set of 12 classical piano pieces.

Now we have applied our compression-based method to the classification of pieces of music, and performed various experiments on sets of mostly classical pieces given as MIDI files. We computed the distances between all pairs of pieces, and then built a tree (using the so-called quartet method) containing those pieces in a way that is consistent with those distances. After the successful completion of three controlled experiments we turned to the real world. The method distinguishes quite well between various musical genres (classical, jazz, rock), and in the classical genre even between composers - a remarkable fact indeed, given the method’s complete ignorance of music. The Figure shows the result for a set of 12 classical piano pieces: the 4 movements from Debussy’s Suite Bergamasque, 4 parts from Bach’s Wohltemperierte Klavier II, and 4 preludes from Chopin’s op.28.

Future applications may include the use of the program as a data mining machine to discover hitherto unknown similarities between music pieces of different composers or genres, and the selection of a plausible composer for a newly discovered piece of music of which the composer is not known.

Please contact:
Rudi Cilibrasi, Paul Vitányi, or Ronald de Wolf, CWI
Tel: +31 20 592 9333.
E-mail: {Rudi.Cilibrasi, Paul.Vitanyi, Ronald.de.Wolf}@cwi.nl