A Taxonomy of Music

Genre Similarity

Releases on discogs are grouped into 15 genres, which again are pretty broad and somewhat nebulous (Synth-pop is obviously Pop but is it Electronic? Is it Rock?).

One way to visualize dissimilarities is with a dendrogram. I’ve built this one from R’s hclust hierarchical clustering. You read a dendrogram from the bottom up: close items will join each other toward the bottom of the tree. As you move up to the top of the tree, more distantly related things join together, until finally all the items are joined together and the whole dataset is together. This was put togther with average linkage: clusters join together with clusters that have the lowest average dissimilarity from them. There are other linkage approaches but this one worked best in practice.

Rock is close to blues, and both are close to Pop which makes sense historically. As does Funk/Soul, Reggae, Electronic, and Hip-Hop going together. I’d have expected Stage & Screen to be closer to classical, but I wasn’t considering the amount of Broadway soundtracks and the like.

Style Similarity

We did genres, but what about styles? There are a lot more styles than genres, and most don’t have many releases associated with them.

It’s too difficult to interpret a dendrogram with over 500 styles. So let’s restrict to releases with over 10,000 releases.

This dissimilarity measure is definitely working for us. I think most of the relationships here make sense: Punk/Hardcore, Garage Rock/Psychedelic Rock, Folk/Folk Rock/Acoustic, Synth-pop/New Wave are all very natural groupings. This group of top styles does somewhat show the bias of the dataset: Discogs is primarily a site focusing on electronic music and rock, so Jazz and Classical aren’t really represented in the top styles list.

I’d like to visualize all the styles though, so a dendrogram won’t cut it. What we have now is a dissimilarity matrix (which we can pretend is a distance matrix⁴), but these distances don’t correspond to any particular locations. One way to get positions corresponding to the distances is UMAP. UMAP makes some very mathy assumptions (that datapoints are uniformly distributed on a Riemannian manifold) and uses our distances to find low-dimensional positions.

What’s useful about UMAP in our scenario is that it tries to resolve positions locally. It’s not super-important to me that ‘Mambo’ and ‘Tech House’ are precisely the right distance from each other. They’re very unrelated styles. What’s important is that the distance between the individual Jazz styles or the individual Metal styles are right. UMAP makes its embedding based on the nearest points. The broader structure will work itself out from there. For this analysis I’ve set UMAP to look at the 25 closest styles.

I also used the clustering above to find clusters of releases, to see how the two approaches agree and disagree. There will be disagreements. I arbitrarily picked 10 clusters.

Let’s plot our UMAP styles. I’ve excluded styles with less than 100 releases, leaving us with 415 styles remaining. I’m still not going to be able to fit every style on one plot, but I’ve added a lot of ‘signposts’ to let you see the lay of the land.

This seems like a pretty good embedding, and it also mostly agrees with the clustering. The places where they differ are interesting. UMAP as ‘Hardcore’ with punk and metal styles, but the clustering puts it with electronic music. Hardcore appears as a style in both ‘Electronic’ and ‘Rock’ genres, with different meanings. Each algorithm picked up on different meanings. Cluster 9 only has ‘Hindustani’, ‘Bollywood’ and ‘Soundtrack’, which seems fair enough. Clustering places ‘Reggaeton’ with latin styles, but UMAP holds it closer to the electronic ones. Cluster 1 runs up the UMAP2 axis from ‘Nu-metal’ in the bottom, through ‘Alternative Rock’ and ‘Indie Rock’. Then it continues into the ‘Darker’ electronic genres like ‘Industrial’, ‘IDM’, ‘EBM’. Finally it reaches the top of the plot with ‘Electroclash’ and ‘Synthpop’. Cluster 1 is a very 90s/Early 2000s set of styles.

XML Extraction

Happily, Discogs makes all this data available as a gzipped well-formed XML file. The problem is that there’s enough data that trying to build parse the entire tree on my MacBook causes me to run out of memory. Python’s built-in XML ElementTree parser will let you lazily handle a huge file, but the documentation doesn’t make it particularly obvious how to do it.

Our XML is structured like this (with some tags and information we don’t need omitted):

<masters>
<master id="57416">
    <main_release>1678659</main_release>
    <images>
        <image height="600" type="primary" uri="" uri150="" width="593"/>
        ...
    </images>
    <artists>
        <artist>
            <id>3225</id>
            <name>Vince Watson</name>
            ...
        </artist>
    </artists>
    <genres>
        <genre>Electronic</genre>
    </genres>
    <styles>
        <style>Techno</style>
    </styles>
    <year>1996</year>
    <title>Tuff Trax #1 - Basic Functions</title>
    <data_quality>Correct</data_quality>
</master>
...
</masters>

If you naively use ElementTree.parse() it will try to build the entire data structure in one go and you’ll run out of memory and your computer will grind to a halt. An alternative method is ElementTree.iterparse(). This is a generator that emits the XML tags and events (e.g. ‘start of tag’, ‘end of tag’) as it gets to them. Now you can process the file as you go through it. When you get an ‘end’ event from iterparse, you can work with the tag as if it were a normal XML element⁵.

If you naively use ElementTree.iterparse() it will also try to build the entire data structure and you’ll run out of memory and your computer will grind to a halt. It’s not lazily going over it like a generator, it’s just letting you know whats going on as you build the tree. What you can do, though, is modify the tree as you’re building it. In this code I grab the root node of the element tree (the first one parsed out of the file), and after every master release I process, I call clear() on the root node to erase what’s in the tree.

import gzip
import xml.etree.ElementTree as et

# outer_delimiter separates release id, genres, and styles
# inner_delimiter separates individual genres and styles
outer_delimiter, inner_delimiter = '\t', '|'


def get_info(node):
    "Returns genres and styles for a discogs master release"
    genres_node, styles_node = node.find('genres'), node.find('styles')

    genres = ([g.text for g in genres_node.findall('genre')] 
              if genres_node else [])
    styles = ([s.text for s in styles_node.findall('style')] 
              if styles_node else [])

    return genres, styles

def delimit(seq, delim):
    "Clearer helper function for delimiting sequences"
    return delim.join(str(x) for x in seq)

with gzip.open(input_filename) as xml_file:
    root = None
    for event, element in et.iterparse(xml_file, events=('start', 'end')):
        
        # This is ugly but it lets us keep track of the
        # root node
        if root is None:
            root = element

        if event == 'end' and element.tag == 'master':
            release_id = element.attrib['id']
            genres, styles = get_info(element)

            print(release_id,
                  delimit(genres, inner_delimiter),
                  delimit(styles, inner_delimiter),
                  sep=outer_delimiter)

            # Clear the root so that it doesn't keep the data we've already
            # processed in memory.
            root.clear()

Now we have we have our data in a more useful format. We only have the data we need: master release IDs, genres, and styles. This is a plain text file, and the three fields are delimited by a tab. Genres and styles can have multiple values, so they’re delimited with a pipe.

229069  Electronic      Techno|Minimal|Tech House
229134  Electronic      Techno
229474  Rock    Thrash|Stoner Rock|Heavy Metal
229556  Electronic      House|Downtempo
229960  Electronic|Rock House|Electro|Indie Rock|Disco

Processing with pySpark

So now what I have is releases with styles attached to them. What I actually want is the reverse: styles with releases attached to them. The reason this feels natural⁶ to me in Spark is that, because of its distributed nature, you can just “shake out” all the styles-release pairs into a pile and put them back together the way you want. Like sorting socks.

If you’re familiar with Python’s list comprehensions or generator expressions, you’ve got most of what you need to understand working with Spark RDD’s on a basic level. Let’s sum up the squares of even numbers below 100 with a python generator expression: sum(x**2 for x in range(100) if x % 2 == 0). This expression is doing a couple things here. The x**2 for x in range(100) is the map component. We’re applying a transformation to every element in range(100). This doesn’t have to be a small expression either, f(x) for x in q is valid for any function f. The next part, if x % 2 == 0 is the filter component. As we’re going through range(100), we’re only keeping values of x that don’t have a remainder when divided by two. The function sum is a reducing function: it takes every element in a sequence and applies a function as it goes through. In this case that function is simple addition. Finally notice that this is a generator expression: ignoring the call to sum() for a second, we are performing these transformations when we need the result. You can do a lot with just these three concepts⁷.

Spark lets you process large datasets in parallel on multiple cores (and computers) if you program this way. It does this via the Resilient Distributed Dataset (RDD) API. Spark distributes the data across its workers. RDD’s are resilient in the sense that that Spark keeps track of what data it sends where, and if one of the worker nodes dies it can regenerate it. With an RDD we can use map, filter, and a few other functions to define transformations on a dataset. Then when we either need the data (or need to compute a reducing function on the data), Spark distributes the data and computes it.

Analysis of genres and styles are basically the same, so I’ll only present styles here.

Our first step is to parse our input text file. You could accomplish this by a lot of small anonymous lambda functions⁸ (this is what most Spark tutorials do), but writing out a slightly bigger function with a name helps with code clarity.

# Creating the named tuple lets us make code a little clearer
from collections import namedtuple
Release = namedtuple('Release', ['release_id', 'genres', 'styles'])

def process_line(item):
    toks = item.strip().split(outer_delimiter)
    release_id = toks[0]
    genres_styles = [set(x.split(inner_delimiter)) for x in toks[1:]]
 
    # Some releases may not have styles or genres attached. If they have a 
    # style but not a genre, we'll still have a regular 3-tuple. If they don't
    # have either we'll need add empty collections for both.
    while len(genres_styles) < 2:
        genres_styles.append([])

    return Release(release_id, genres_styles[0], genres_styles[1])

The next set is to ‘dump’ out all these genres and styles into a pile. The function unnest_styles ‘flattens’ the styles and genres⁹. For example data that looks like [('release_a', ['genre'], ['style_a', 'style_b']), ('release_b', ['genre'], ['style_b', 'style_c'])] will be transformed to [('release_a', 'style_a'), ('release_a', 'style_b'), ('release_b', 'style_b'), ('release_b', 'style_c')]. Now that we have release-style pairs, we can use invert_kvp to invert the key-value pair so that ('229134', 'Techno') becomes ('Techno', '229134'). Now that it’s in that form, Spark will collect everything corresponding to the key for us.

def unnest_styles(item):
    release, genres, styles = item

    for style in styles:
        yield release, style

def invert_kvp(kvp):
    key, value = kvp
    return value, key

Certain RDD functions work with keys. They treat each item in the dataset as a key-value pair, and use that key to let you work on subsets of the data, like a GROUP BY clause in SQL. For example countByKey is the equivalent of the SQL query SELECT key, count(*) FROM [table] GROUP BY key. The RDD function combineByKey lets us make collections out of all of the items corresponding to a key. The first one makes a collection out of an item. For our purposes, we need to make a set containing just one item. The next argument adds an item to an existing collection. And the last merges two collections together. Because Spark RDDs immutable, these functions should return new objects, not modify existing objects. For example, set.add doesn’t work here, because, while it adds items to a set, it doesn’t return a value.

# Collection creator
def create_set(item):
    return set([item])

# Add to a collection
def add_to_set(current_set, new_item):
    return set.union(current_set, create_set(new_item))

# Merge two collections
def join_sets(set_a, set_b):
    return set.union(set_a, set_b)

We need functions to compute the Yule’s \(Q\) dissimilarity. yuleq(a,b) computes this for two sets a and b (naturally). The function compute_distances_with_sample_size wraps yuleq, transforming the data as it comes out of the RDD into \(a\), \(b\), \(c\) and \(d\). Since distance metrics are symmetric (\(D(a,b) = D(b,a)\)), compute_distances returns them both.

def yuleq(a, b, c, d):
    return (2 * b * c) / (a * d + b* c)    

def compute_distances_with_sample_size(pair, n):
    "Helper function to compute distance"
    # pair is a tuple in the form:
    # ((style_name, [releases]), (style_name, [releases]))
    kvp1, kvp2 = pair
    key1, values1 = kvp1
    key2, values2 = kvp2

    if key1 == key2:
        score = 0.0
    else:
        a = len(values1 & values2)
        b = len(values1 - values2)
        c = len(values2 - values1)
        d = n - (a + b + c)

        score = yuleq(a, b, c, d)
        
    yield key1, key2, score
    yield key2, key1, score

Now we’re ready to build an RDD. Lets build one that gives each style and the corresponding releases. You can tell the current Spark Context (sc) to read a file line by line with textFile(). We’ve already written all our important functions, so now it’s just a matter of combining them. map() applies a function to every element in the RDD. flatMap() is similar, but allows the number of elements in the RDD to change. filter() only keeps elements that evaluate to True by a specified function. We’ve already discussed combineByKey() above.

lines = sc.textFile('genres_styles.txt')

style_releases = (
    lines.map(process_line)
         .filter(lambda x: len(x.styles) > 1)
         .flatMap(unnest_styles)
         .map(invert_kvp)
         .combineByKey(create_set, 
                       add_to_set, 
                       join_sets)
         )

At this point we haven’t done anything. The RDD we’ve made here only describes the steps we’ll use to get what we want. It’s a recipe, but not the meal. This will only turn into data when we tell Spark to go get it. We can use collect() to completely execute the RDD (If you only need a subset take() will also give you a user-specified number of records). Certain ‘reducing’ functions (sum, max, etc.) will also cause Spark to go evaluate an RDD. In my code I also call persist() at the end of the RDD creation to force Spark to hang on to the results from the RDD because I use it a couple times.

The last step is computing the distances. We already created the distance functions before, we just need to evaluate it for every pair of styles. The RDD method cartesian() produces each possible combination of values from two RDDs. Evaluating style_releases.cartesian(style_releases) gives every combination of items in style_releases. Since we wrote compute_distances to exploit the symmetry of distances, we filter out half of the pairs.

style_distances = (style_releases.cartesian(style_releases)
                                 .filter(lambda x: x[0] < x[1])
                                 .flatMap(compute_distances))

style_distances_evalutated = style_distances.collect()

Now style_distances_evaluated has all the data we wanted. It’s a list in the format [('style_a', 'style_b', dist) ...], and we write it to disk in whatever format is convenient to us. I picked a ‘melted’ csv.