Google’s Word2Vec and Stanford’s GloVe have recently offered two fantastic open source software packages capable of transposing words into a high dimension vector space. In both cases, a vector’s position within the high dimensional space gives a good indication of the word’s semantic class (among other things), and in both cases these vector positions can be used in a variety of applications. In the post below, I’ll discuss one approach you can take to clustering the vectors into coherent semantic groupings.
Both Word2Vec and GloVe can create vector spaces given a large training corpus, but both maintain pretrained vectors as well. To get started with ~1GB of pretrained vectors from GloVe, one need only run the following lines:
If you unzip and then glance at glove.42B.300d.txt, you’ll see that it’s organized as follows:
Each new line contains a token followed by 300 signed floats, and those values appear to be organized from most to least common. Given this ready format, it’s fairly straightforward to get straight to clustering!
There are a variety of methods for clustering vectors, including density-based clustering, hierarchical clustering, and centroid clustering. One of the most intuitive and most commonly used centroid-based methods is K-Means. Given a collection of points in a space, K-Means uses a Hunger Games style random lottery to pick a few lucky points (colored green below), then assigns each of the non-lucky points to the lucky point to which it’s closest. Using these preliminary groupings, the next step is to find the “centroid” (or geometric center) of each group, using the same technique one would use to find the center of a square. These centroids become the new lucky points, and again each non-lucky point is again assigned to the lucky point to which it’s closest. This process continues until the centroids settle down and stop moving, after which the clustering is complete. Here’s a nice visual description of K-Means [source]:
To cluster the GloVe vectors in a similar fashion, one can use the sklearn package in Python, along with a few other packages:
It will also be helpful to build a class to mimic the behavior of autovivification in Perl, which is essentially the process of creating new default hash values given a new key. In Python, this behavior is available through collections.defaultdict(), but the latter isn’t serializable, so the following class is handy. Given an input key it hasn’t seen, the class will create an empty list as the corresponding hash value:
We also want a method to read in a vector file (e.g. glove.42B.300d.txt) and store each word and the position of that word within the vector space. Because reading in and analyzing some of the larger GloVe files can take a long time, to get going quickly one can limit the number of lines to read from the input file by specifying a global value (n_words), which is defined later on:
Scikit-Learn’s implementation of K-Means returns an object (cluster_labels in these snippets) that indicates the cluster to which each input vector belongs. That object doesn’t tell one which word belongs in each cluster, however, so the following method takes care of this. Because all of the words being analyzed are stored in labels_array and the cluster to which each word belongs is stored in cluster_labels, the following method can easily map those two sequences together:
Finally, we can call the methods above, perform K-Means clustering, and print the contents of each cluster with the following block:
The full script is available here. To run it, one needs to specify the vector file to be read in, the number of words one wishes to sample from that file (one can of course read them all, but doing so can take some time), and the “reduction factor”, which determines the number of clusters to be made. If one specifies a reduction factor of .1, for instance, the routine will produce n*.1 clusters, where n is the number of words sampled from the file. The following command reads in the first 10,000 words, and produces 1,000 clusters:
The output of this command is the series of clusters produced by the K-Means clustering:
I’m currently using these word clusters for fuzzy plagiarism detection, but they can serve a wide variety of purposes. If you find them helpful for a project you’re working on, feel free to drop me a note below!