Finding Similar Tweets with BERT and NMSLib

Since my initial explorations with vector search for images on Lucene some time back, several good libraries and products have appeared that do a better job of computing vector similarity than my home grown solutions. One of them is the Non-Metric Space Library (NMSLib), a C++ library that implements Approximate Nearest Neighbor (ANN) techniques for efficient similarity search in non-metric spaces.

The problem with doing any kind of ranking using vector search is that you must match the query vector against every document vector in the index, compute a similarity score, then order by that similarity score. This is a O(N) operation, so the query time will increase linearly with the number of records N in the index. ANN libraries try to do better, and NMSLib uses the idea of Hierarchical Navigable Small World (HNSW) Graphs, which effectively partition the data into a hierarchical set of small world graphs based on proximity. That way searching this structure for nearest neighbors of a given record will involve searching the proximity graph of that record, which is independent of the number of records.

Over the last year or so, search has increasingly begun to move from traditional information retrieval techniques based on TF-IDF, to techniques based on neural models. To some extent, this has coincided with the release of the Bidirectional Encoder Representations from Transformers (BERT) model by Google, and its subsequent application in the NLP and Search communities for many different tasks, including similarity based document ranking. Prof. Jimmy Lin of the University of Waterloo has published an Opinion piece The Neural Hype, Justified! A Recantation at SIGIR 2019, where he explains why this is so in more detail.

In any case, this trend has led to a need for computing vector based similarity in an efficient manner, so I decided to do a little experiment with NMSLib, to get familiar with the API and with NMSLib generally, as well as check out how good BERT embeddings are for search. This post describes that experiment.

For my dataset, I selected the Health News in Twitter dataset from the UCI Machine Learning Repository. This is a dataset containing approximately 60k tweets related to 16 different Health/News organizations, and was donated to UCI as part of the paper Fuzzy Approach to Topic Discovery in Health and Medical Corpora.

I first extracted the tweet ID and text from these files and uploaded them into a SQLite3 database, so I could look the text up by ID later. I did a little cleanup of the tweet texts, to remove (shortened) URLs from the texts. Then I set up a BERT-as-a-service sentence encoding service on a GPU box, using BERT-base uncased as the underlying model, and generated the vectors for each of the sentences. Code for both these are fairly trivial and can be easily figured out from the documentation, so I will not bother to describe it here.

I then wanted to see how NMSLib scaled with change in dataset size. I had approximately 60k tweets and their vectors, so I loaded random subsets of the dataset into the NMSLib index, then ran a batch of 50 queries (also randomly sampled from the dataset) to generate their K Nearest Neighbors for K=10. I recorded the total loading time in each case, as well as the query time averaged over the 50 queries. Plots for both are shown below.


What is interesting is that load time rises approximately linearly with the number of records, but the query time is sublinear (and on a completely different timescale from indexing) and eventually seems to flatten out. So we can expect to pay a penalty for the large number of records once during indexing, but query seems to be quite fast.

I also looked at some of the results of the similarity search, and they seem to be pretty good. It is hard to think in terms of traditional similarity in case of tweets, since there is so litle content to go by, but I include below the 10 Nearest Neighbors (or equivalently, the top 10 search results) for 3 of my query tweets, and they all intuitively seem to be good, although perhaps for different reasons. In the first case, I think it has done a good job on focusing on the main content "Ebola" and "Guinea" and fetching results around these content words. In the second case, it seems to have captured the click-bait-ey spirit of the query tweet, and retured other tweets that are along the same lines. In the third case, once again, it returns results that are similar in intent to the query document, but uses completely different words.

QUERY: Ebola in Guinea puts miners in lock down (451467465793355776)
--------------------------------------------------------------------------------------------------
dist.  tweet_id            tweet_text
--------------------------------------------------------------------------------------------------
0.104  542396431495987201  Junior doctors in Sierra Leone strike over lack of Ebola care
0.110  582950953625735168  Sierra Leone Ebola lockdown exposes hundreds of suspected cases
0.112  542714193137635328  Junior doctors in Sierra Leone strike over lack of #Ebola care
0.112  517254694029524992  West Africa Ebola crisis hits tourism, compounds hunger in Gambia
0.117  497018332881498112  Ebola kills nurse in Nigeria
0.119  565914210807599104  Ebola-hit Guinea asks for funds for creaking health sector
0.120  514098379408699393  Ebola virus shutdown in Sierra Leone yields 'massive awareness'
0.120  555734676833198081  Ebola kills Red Cross nurse in Sierra Leone
0.121  583431484905754624  Sierra Leone to start laying off Ebola workers as cases fall: president
0.122  499300095402065921  Ebola Shuts Down The Oldest Hospital In Liberia

QUERY: 1 in 3 prescriptions unfilled, Canadian study finds (450767264292167681)
--------------------------------------------------------------------------------------------------
dist.  tweet_id            tweet_text
--------------------------------------------------------------------------------------------------
0.105  564909963739287552  Study finds 1 in 12 children's ER visits medication related
0.108  321311688257306624  1 in 4 skin cancer survivors skips sunscreen, study finds
0.109  161460752803311617  Only 1 in 4 Young Teens Uses Sunscreen Regularly, Study Finds:
0.110  458662217651879936  Child abuse affects 1 in 3 Canadian adults, mental health study indicates
0.112  344601130124316672  1 in 6 women at fracture clinics have been abused, study shows
0.126  160184310849224704  Abortion ends one in five pregnancies worldwide, study finds
0.127  332579818543673346  1 in 8 Boomers report memory loss, large survey finds
0.127  148844725191979009  Nearly 1 in 3 Young U.S. Adults Have Arrest Records: Study:
0.129  468857557126512640  HPV Found in Two-Thirds of Americans, Survey Finds
0.129  119455268106018816  1 in 4 U.S. Adults Treated for High Blood Pressure: Report:

QUERY: Skip the elliptical machine and walk your way to better health: (296539570206568448)
--------------------------------------------------------------------------------------------------
dist.  tweet_id            tweet_text
--------------------------------------------------------------------------------------------------
0.000  295724160922038272  Skip the elliptical machine and walk your way to better health:
0.000  294033035731546112  Skip the elliptical machine and walk your way to better health:
0.126  399914443762855936  Sweat Your Way To A Healthier Brain
0.144  304496972419702784  How to exercise your way to better sex:
0.144  293262936804311041  How to exercise your way to better sex:
0.149  557233923621527552  Need a healthy push? Turn to your partner to lose weight, quit smoking
0.152  564595829152182273  You don't need a gym to torch calories! Try this 30-minute workout 3 times a week to drop winter weight:
0.152  293006265599262722  Keep hands off the treadmill bars while you walk; you're limiting your calorie burn! Boost your treadmill workout:
0.154  541676196686491649  Kickoff your weight loss plan! Learn 25 ways to cut 500 calories a day:
0.154  551943764198301696  Learn the expert tricks to FINALLY achieving your goal weight:

So anyway, that concludes my experiment with NMSLib. Overall, I have enough now to build something real using these components. As before, the code is pretty trivial, it is modeled after code under the Example Usage section in the NMSLib Quickstart, so I am not going to repeat it here.

Of course, NMSLib is by no means the only library in this area. Others in this space that I know of are FAISS from Facebook, another similarity search library that is optimized to run on GPUs, and Vespa, a full-fledged search engine that allows for both traditional and vector search. In addition, there are plugins for vector scoring for both Elasticsearch (elasticsearch-vector-scoring) and Solr (solr-vector-scoring). So these might be options for vector search as well.

For my part, I am happy with my choice. I needed something which was easy to learn and embed, so the preference was for libraries rather than products. I also wanted it to run on a CPU based machine for cost reasons. FAISS does run on CPU as well, but based on results reported by Ben Fredrickson here, NMSLib has better performance on CPU. Also NMSLib installation is just a simple "pip install" (with the pre-compiled binary). In any case, I haven't ruled out using FAISS completely. In this system, we extract BERT embeddings for the tweets in an offline batch operation. In a real system, it is likely that such embeddings will have to be generated on demand, so such setups would be forced to include a GPU box, which could be used to also serve a FAISS index (based on Ben Fredrickson's evaluation, FAISS on GPU is approximately 7x faster than NMSLib is on CPU).

Efficient Reverse Image Search on Lucene using Approximate Nearest Neighbors

I wrote last week about our Search Summit, an internal conferences where engineers and product managers from Elsevier, LexisNexis, and various other organizations that make up the RELX Group, get together to share ideas and best practices on search. The Search Summit is in its third year, and given that its a single track conference and runs for two days, there are limited speaking slots available, and competition for these slots is quite fierce. Our acceptance rate this year was around the 40-50% mark, which I guess puts us on par with some big external conferences in terms of exclusivity. In any case, I guess that was my long-winded way of saying that this year I didn't get accepted for a speaking slot, and was offered the opportunity to present a poster instead, which I accepted.

This was the first time I made a poster for work, and quite honestly, I didn't know where to begin. My only experience with posters was back when I was at school, where I remember that we used crayons a lot, and then helping my kids build posters for their school, which involved a lot of cutting out pictures and glueing them on to a posterboard. Fortunately, as I learned from some googling, technology has progressed since then, and now one can build the poster as a single Microsoft Powerpoint (or Apple Keynote or Google slides) slide (I used Powerpoint). Quite a few sites provide free templates for various standard poster sizes as well, I ended up choosing one from Genigraphics. One you are done designing the poster, you save it as a PDF, and upload the PDF to sites such as Staples Print Services for printing. And that's pretty much all there is to it. Here is the poster I ended up presenting at the search summit.

Basically, the poster describes a Proof of Concept (POC) application that attempts to do reverse image search, i.e., given an image, it returns a ranked list of images, similar to the given image, in the corpus. My dataset for my experiments was a set of approximately 20,000 images from the ImageCLEF 2016 competition. The notion of similarity that I use is the one learned by a RESNET network pre-trained on ImageNet. The idea is that this sort of network, trained on a large generic image corpus such as ImageNet, learns how to recognize colors, edges, shapes, and other more complex features in images, and these features can be used to provide a notion of similarity across images, much like tokens in a document.

RESNET (and other pre-trained networks like it) generate dense and (comparatively) low-dimensional vectors of features. For example, the last layer of a trained RESNET model will generate feature vectors of size 2048. On the other hand, text is typically vectorized for Information Retrieval as a vector over all the tokens (and sometimes token combinations as well) in its vocabulary, so feature vector sizes of 50,000 or 100,000 are not uncommon. In addition, such vectors tend to be quite sparse as well, since a given token is relatively unlikely to occur in many documents. Lucene (and probably other search engines) leverage the high-dimensionality and sparseness of text feature vectors using its Inverted Index data structure (aka Postings List), where the key is the token and the value is a priority queue of document ids that the token occurs in.

In order to present a ranked list of similar images, a naive (and exhaustive) solution would be to compute some measure of vector similarity (such as Cosine similarity or Euclidean similarity) between the input image and every other image in the corpus, a O(N) operation. A better solution might be to partition the similarity space using something like a KD-tree such that comparison is done against a subset of most similar images, and that is a O(log N) operation. However, the Lucene inverted index makes the search an almost O(1) operation -- first looking up by token, and then navigating down a priority queue of a subset of document IDs containing that token. My reasoning went as follows -- if I could somehow project the dense, low-dimensional vectors from RESNET back into a sparse, high-dimensional space similar to that used for text vectors without losing too much information, I would be able to do image search as efficiently as text search.

I experimented with two such projection techniques -- Random K-Means and Random Projections.

• Random K-Means involves running a bunch of K-Means clusterings over the image set, typically 50-200 of them, each with some random value for k. Each image (point in similarity space) is represented by a sequence of its cluster memberships across all the clusterings. The intuition here is that similar images, represented by two points that are close in the similarity space, will share cluster memberships across more clusterings than dissimilar images, represented by points that are further apart. A 2D schematic on the bottom center of the poster illustrates the idea.
• Random Projections is similar, but instead of partitioning the space into a random number of circular clusters, we partition the space itself using a (D-1) dimensional hyperplane, where D is the size of the dense feature vector (2048). The number of random projections used is typically much higher than the number of K-Means, typically 1,000-10,000. This effectively results in binary clusters where points behind the hyperplane get assigned a 0 and points in front get assigned a 1. As before, each image is represented by a sequence of its membership across all the random projections. The intuition here is similar to random K-Means. The 2D schematic on the bottom right of the poster illustrates how random projections work.

My baseline for experiments was caption based text search, i.e., similar images were found by doing text search on their captions. I took a random set of 20 images, and manually evaluated the relevance for top 10 similar images for each on a 4-point scale. Its only one person, so its not very objective, but I needed a place to start. The guideline I followed was to give it the highest rating (4) if the image is identical, or almost identical, to the source image -- possibly either the same image, or a composite containing the same image, or a minor modification. The second highest rating (3) was for images that were basically the same thing -- for example, if the source image was an X-ray of the left lung, I would rate an X-ray of the right as very similar. The third rating (2) were for images that I couldn't rate 4 or 3, but which I would expect to see in the set of similar images. Finally, the lowest rating (1) is for images that I don't expect to see in the results, i.e., irrelevant images.

I used the ratings to compute Discounted Cumulative Gain (DCG) for k=1, 3, 5, and 10, where k is the number of top results taken from the ranked list of similar images for each image, and then averaged them across the 20 images. I then computed the Ideal DCG (IDCG) for k=10 by sorting the ranked list based on my ratings, and then divided the computed DCG by the IDCG to get the Normalized Discounted Cumulative Gain (NDCG). These numbers are shown in the table under the Results section in the poster. The bolded numbers indicate the best performers. Results for k=1 serve as a sanity check, since all the searches in my evaluation returned the source image as the top result in the ranked list of similar images. Overall, the numbers seem quite good, and Random K-Means with 250 clusters produced the best results.

Random K-Means provided the best results in qualitative terms as well. The block of images at the center of the poster show a brain MRI as the source image, and the top 3 results from the baseline, the best random K-Means (250 clusters), and the best Random Projections (10000 projections). A green box indicates relevant results, and a red box indicates irrelevant results. As you can see, the caption text search based baseline produces more diverse results, but doesn't do very well otherwise. Random K-Means and Random Projections produce similar images that are more visually similar to the source image, and between the two, Random K-Means tends to produce better results.

In the future, I hope to extend this approach to text vectors as well. Specifically, I want to capitalize on the increase in recall that I noticed with caption based text search, by building embeddings (word2vec, ELMo, BERT, etc.) from the caption and treat these embeddings as additional feature vectors for the image. On the other hand, I do notice that the trend has been to use special purpose backends for vector search, such as the Non-Metric Space Library (NMSLib) based on Numpy, or the GPU-based FAISS Library for efficient similarity search, or hybrid search engines such as Vespa. So while it might be intellectually satisfying to try to make a single platform serve all your search needs, it might more worthwhile to see if one of these other toolkits might provide better results.

I also wanted to acknowledge the work of Simon Hughes. The approaches used in this poster are based heavily on ideas originally proposed by him on his DiceTechJobs/VectorsInSearch project, as well as ideas and suggestions proposed by him and others on the Relevancy and Matching Technology #vectors-in-search slack channel.

IR Math in Java : Experiments in Clustering

As I mentioned last week, I have been trying to teach myself clustering algorithms. Having used the Carrot API to do some clustering work about 6 months ago, I have been curious about the clustering algorithms themselves. Carrot offers you a choice of several built-in clustering algorithms, so you just use one depending on your needs. Obviously, this presupposes that you know enough about the algorithms themselves to make the decision (which wasn't the case for me, unfortunately). So what better way to learn than to implement the algorithms in code? So this post covers some popular clustering algorithms implemented in Java.

The code in this post is based on algorithms from various sources. Sources are mentioned in the individual sections as well as listed in the references section below. I describe my implementations and test results for the following algorithms:

1. K-Means Clustering
2. Quality Threshold (QT) Clustering
3. Simulated Annealing Clustering
4. Nearest Neighbor Clustering
5. Genetic Algorithm Clustering

K-Means Algorithm

For K-Means clustering, one seeds a random number of clusters with a few random seed documents from the collection. An estimate k of the number of clusters to use for a document collection of N documents is given by the heuristic below:

  k = floor(sqrt(N))
  where:
    N = number of documents in collection.
    k = the estimate of the number of clusters.

The algorithm starts by seeding the clusters with one random document each from the collection. It computes the centroid μ for each cluster using the following formula:

  μ = sqrt(sum(xi2)) / N
  where:
    μ = centroid of a cluster.
    N = number of documents in the collection.
    xi = the i-th document vector.

For each document, we compute the similarity between the centroids of the clusters, and assign the document to the cluster whose centroid is most similar. The similarity measure used is Cosine Similarity - I use code from my article on similarity metrics.

At the end of this step, we have a list of clusters fully populated with the documents from the collection. We then recompute the centroid based on the documents in these clusters, and repeat the above step until the new cluster is no better than the previous cluster.

Although common sense would suggest that we should use the same measure, ie Eucledian distance, for both similarity and centroid calculations, this does not work in practice - there will be no improvement in the cluster after the initial population. So it is important to use a different measure to calculate similarity.

Here is the code for my K-Means clusterer. The algorithm used is the one in the TMAP book^[1].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98

// Source: src/main/java/com/mycompany/myapp/clustering/KMeansClusterer.java package com.mycompany.myapp.clustering; import java.util.ArrayList; import java.util.List; import org.apache.commons.collections15.CollectionUtils; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; import Jama.Matrix; public class KMeansClusterer { private final Log log = LogFactory.getLog(getClass()); private String[] initialClusterAssignments = null; public void setInitialClusterAssignments(String[] documentNames) { this.initialClusterAssignments = documentNames; } public List<Cluster> cluster(DocumentCollection collection) { int numDocs = collection.size(); int numClusters = 0; if (initialClusterAssignments == null) { // compute initial cluster assignments IdGenerator idGenerator = new IdGenerator(numDocs); numClusters = (int) Math.floor(Math.sqrt(numDocs)); initialClusterAssignments = new String[numClusters]; for (int i = 0; i < numClusters; i++) { int docId = idGenerator.getNextId(); initialClusterAssignments[i] = collection.getDocumentNameAt(docId); } } else { numClusters = initialClusterAssignments.length; } // build initial clusters List<Cluster> clusters = new ArrayList<Cluster>(); for (int i = 0; i < numClusters; i++) { Cluster cluster = new Cluster("C" + i); cluster.addDocument(initialClusterAssignments[i], collection.getDocument(initialClusterAssignments[i])); clusters.add(cluster); } log.debug("..Initial clusters:" + clusters.toString()); List<Cluster> prevClusters = new ArrayList<Cluster>(); // Repeat until termination conditions are satisfied for (;;) { // For every cluster i, (re-)compute the centroid based on the // current member documents. (We have moved 2.2 above 2.1 because // this needs to be done before every iteration). Matrix[] centroids = new Matrix[numClusters]; for (int i = 0; i < numClusters; i++) { Matrix centroid = clusters.get(i).getCentroid(); centroids[i] = centroid; } // For every document d, find the cluster i whose centroid is // most similar, assign d to cluster i. (If a document is // equally similar from all centroids, then just dump it into // cluster 0). for (int i = 0; i < numDocs; i++) { int bestCluster = 0; double maxSimilarity = Double.MIN_VALUE; Matrix document = collection.getDocumentAt(i); String docName = collection.getDocumentNameAt(i); for (int j = 0; j < numClusters; j++) { double similarity = clusters.get(j).getSimilarity(document); if (similarity > maxSimilarity) { bestCluster = j; maxSimilarity = similarity; } } for (Cluster cluster : clusters) { if (cluster.getDocument(docName) != null) { cluster.removeDocument(docName); } } clusters.get(bestCluster).addDocument(docName, document); } log.debug("..Intermediate clusters: " + clusters.toString()); // Check for termination -- minimal or no change to the assignment // of documents to clusters. if (CollectionUtils.isEqualCollection(clusters, prevClusters)) { break; } prevClusters.clear(); prevClusters.addAll(clusters); } // Return list of clusters log.debug("..Final clusters: " + clusters.toString()); return clusters; } }

The K-Means algorithm seems to be reasonably fast. However, the problem with it is that the solution is very sensitive to initial cluster seeding. Here are some results I got from using a random number generator to seed the clusters.

1 2 3 4 5 6 7

==== Results from K-Means clustering ==== (seeds: [D5,D2]) C0:[D1, D3, D4, D5, D6] C1:[D2, D7] ==== Results from K-Means clustering ==== (seeds: [D3,D2]) C0:[D1, D3, D4, D5, D6] C1:[D2, D7]

However, if I seed the clusters manually, using the results from my cluster visualization article last week, then I get results which look reasonable:

1 2 3

==== Results from K-Means clustering ==== (seeds: [D1,D3]) C0:[D1, D2, D5, D6, D7] C1:[D3, D4]

Quality Threshold (QT) Algorithm

The Quality Threshold (QT) algorithm uses a maximum diameter settable by the user to cluster documents. The first cluster is built with the first document in the collection. As long as other documents are close enough to be within the diameter specified, they are added to the cluster. Once all documents are read, the documents that have been added to the cluster are set aside and the algorithm repeated recursively on the rest of the document collection. The program stops when there are no more documents. The number of levels that the program recurses down to corresponds to the number of clusters formed as a result.

The distance between a document and a cluster is computed using Complete Linkage Distance, ie the distance from the document and the furthest document in the cluster.

Here is the code for my QT Clustering program. The algorithm used was from this Wikipedia article^[2].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

// Source: src/main/java/com/mycompany/myapp/clustering/QtClusterer.java package com.mycompany.myapp.clustering; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.Set; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; import org.apache.commons.math.stat.descriptive.moment.Mean; import Jama.Matrix; import com.mycompany.myapp.similarity.CosineSimilarity; public class QtClusterer { private final Log log = LogFactory.getLog(getClass()); private double maxDiameter; private boolean randomizeDocuments; public void setMaxRadius(double maxRadius) { this.maxDiameter = maxRadius * 2.0D; } public void setRandomizeDocuments(boolean randomizeDocuments) { this.randomizeDocuments = randomizeDocuments; } public List<Cluster> cluster(DocumentCollection collection) { if (randomizeDocuments) { collection.shuffle(); } List<Cluster> clusters = new ArrayList<Cluster>(); Set<String> clusteredDocNames = new HashSet<String>(); cluster_r(collection, clusters, clusteredDocNames, 0); return clusters; } private void cluster_r(DocumentCollection collection, List<Cluster> clusters, Set<String> clusteredDocNames, int level) { int numDocs = collection.size(); int numClustered = clusteredDocNames.size(); if (numDocs == numClustered) { return; } Cluster cluster = new Cluster("C" + level); for (int i = 0; i < numDocs; i++) { Matrix document = collection.getDocumentAt(i); String docName = collection.getDocumentNameAt(i); if (clusteredDocNames.contains(docName)) { continue; } log.debug("max dist=" + cluster.getCompleteLinkageDistance(document)); if (cluster.getCompleteLinkageDistance(document) < maxDiameter) { cluster.addDocument(docName, document); clusteredDocNames.add(docName); } } if (cluster.size() == 0) { log.warn("No clusters added at level " + level + ", check diameter"); } clusters.add(cluster); cluster_r(collection, clusters, clusteredDocNames, level + 1); } }

The algorithm is easy to understand, and always returns the exact same clusters, regardless of the input. Using a diameter threshold of 0.4, I was able to get two clusters which is shown below:

1 2 3

==== Results from Qt Clustering ==== (diameter: 0.4D) C0:[D6, D7] C1:[D2, D1, D4, D5, D3]

Simulated Annealing Algorithm

The Simulated Annealing clustering algorithm is based on the Annealing process in metallurgy, where it is used to harden metals by cooling the molten metal in steps.

The algorithm starts by setting an initial "temperature", and builds an initial set of clusters using some population process. Mod based partitioning to used populate the initial clusters, although a degree of randomness can be added by shuffling the collection.

At each temperature setting, we exchange two random documents between two random clusters for a specified number of times. We then check to see if the solution improved or degraded based on the average radius of the cluster. Depending on the current temperature setting, we compute a probability that we should accept the degraded solution (aka downhill move). The probability is given by:

  P = exp((Si-1 - Si) / T)
  where:
    Si-1 = value of solution at loop (i-1)
    Si = value of solution at loop (i)
    T = current temperature setting

If the probability is higher than a specified threshold, we accept a downhill move. We then decrease the temperature by a specified step value. We then go back to exchanging random documents between random clusters in a loop. We keep doing this until the temperature is below a certain cutoff point.

From the probability equation above, the algorithm will allow more downhill moves towards its end, when the temperature gets lower. This allows more exploration of the solution space than K-Means or QT clustering methods.

The code for my Simulated Annealing Clusterer is shown below. The algorithm comes from the TMAP book^[1].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146

// Source: src/main/java/com/mycompany/myapp/clustering/SimulatedaAnnealingClusterer.java package com.mycompany.myapp.clustering; import java.util.ArrayList; import java.util.List; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; public class SimulatedAnnealingClusterer { private final Log log = LogFactory.getLog(getClass()); private boolean randomizeDocs; private double initialTemperature; private double finalTemperature; private double downhillProbabilityCutoff; private int numberOfLoops; public void setRandomizeDocs(boolean randomizeDocs) { this.randomizeDocs = randomizeDocs; } public void setInitialTemperature(double initialTemperature) { this.initialTemperature = initialTemperature; } public void setFinalTemperature(double finalTemperature) { this.finalTemperature = finalTemperature; } public void setDownhillProbabilityCutoff( double downhillProbabilityCutoff) { this.downhillProbabilityCutoff = downhillProbabilityCutoff; } public void setNumberOfLoops(int numberOfLoops) { this.numberOfLoops = numberOfLoops; } public List<Cluster> cluster(DocumentCollection collection) { // Get initial set of clusters... int numDocs = collection.size(); int numClusters = (int) Math.floor(Math.sqrt(numDocs)); List<Cluster> clusters = new ArrayList<Cluster>(); for (int i = 0; i < numClusters; i++) { clusters.add(new Cluster("C" + i)); } // ...and set initial temperature parameter T. double temperature = initialTemperature; // Randomly assign documents to the k clusters. if (randomizeDocs) { collection.shuffle(); } for (int i = 0; i < numDocs; i++) { int targetCluster = i % numClusters; clusters.get(targetCluster).addDocument( collection.getDocumentNameAt(i), collection.getDocument(collection.getDocumentNameAt(i))); } log.debug("..Initial clusters: " + clusters.toString()); // Repeat until temperature is reduced to the minimum. while (temperature > finalTemperature) { double previousAverageRadius = 0.0D; List<Cluster> prevClusters = new ArrayList<Cluster>(); // Run loop NUM_LOOP times. for (int loop = 0; loop < numberOfLoops; loop++) { // Find a new set of clusters by altering the membership of some // documents. Start by picking two clusters at random List<Integer> randomClusterIds = getRandomClusterIds(clusters); // pick two documents out of the clusters at random List<String> randomDocumentNames = getRandomDocumentNames(collection, randomClusterIds, clusters); // exchange the two random documents among the random clusters. clusters.get(randomClusterIds.get(0)).removeDocument( randomDocumentNames.get(0)); clusters.get(randomClusterIds.get(0)).addDocument( randomDocumentNames.get(1), collection.getDocument(randomDocumentNames.get(1))); clusters.get(randomClusterIds.get(1)).removeDocument( randomDocumentNames.get(1)); clusters.get(randomClusterIds.get(1)).addDocument( randomDocumentNames.get(0), collection.getDocument(randomDocumentNames.get(0))); // Compare the difference between the values of the new and old // set of clusters. If there is an improvement, accept the new // set of clusters, otherwise accept the new set of clusters with // probability p. log.debug("..Intermediate clusters: " + clusters.toString()); double averageRadius = getAverageRadius(clusters); if (averageRadius > previousAverageRadius) { // possible downhill move, calculate the probability of it being // accepted double probability = Math.exp((previousAverageRadius - averageRadius)/temperature); if (probability < downhillProbabilityCutoff) { // go back to the cluster before the changes clusters.clear(); clusters.addAll(prevClusters); continue; } } prevClusters.clear(); prevClusters.addAll(clusters); previousAverageRadius = averageRadius; } // Reduce the temperature based on the cooling schedule. temperature = temperature / 10; } // Return the final set of clusters. return clusters; } private List<Integer> getRandomClusterIds( List<Cluster> clusters) { IdGenerator clusterIdGenerator = new IdGenerator(clusters.size()); List<Integer> randomClusterIds = new ArrayList<Integer>(); for (int i = 0; i < 2; i++) { randomClusterIds.add(clusterIdGenerator.getNextId()); } return randomClusterIds; } private List<String> getRandomDocumentNames( DocumentCollection collection, List<Integer> randomClusterIds, List<Cluster> clusters) { List<String> randomDocumentNames = new ArrayList<String>(); for (Integer randomClusterId : randomClusterIds) { Cluster randomCluster = clusters.get(randomClusterId); IdGenerator documentIdGenerator = new IdGenerator(randomCluster.size()); randomDocumentNames.add( randomCluster.getDocumentName(documentIdGenerator.getNextId())); } return randomDocumentNames; } private double getAverageRadius(List<Cluster> clusters) { double score = 0.0D; for (Cluster cluster : clusters) { score += cluster.getRadius(); } return (score / clusters.size()); } }

Results for Simulated Annealing runs vary across runs, which is expected, since this is essentially a Monte Carlo simulation. Some results from multiple runs, with the initial and final temperatures set to 100 and 1, and the downhill probability threshold set to 0.7, are shown below. One way to come by a good set of final results may be to consider aggregating results from multiple runs into a single one.

1 2 3 4 5 6 7 8 9 10 11

==== Results from Simulated Annealing Clustering ==== C0:[D1, D3, D2, D4] C1:[D5, D6, D7] ==== Results from Simulated Annealing Clustering ==== C0:[D3, D4, D2, D5] C1:[D7, D1, D6] ==== Results from Simulated Annealing Clustering ==== C0:[D1, D7, D5, D6] C1:[D4, D2, D3]

Nearest Neighbor Algorithm

This algorithm is classified as a Genetic algorithm in the TMAP book, but a subsequent section in the book describes a genetic clustering algorithm that involves mutations and crossovers. I guess the latter type is commonly associated with genetic algorithms in general. However, the Nearest Neighbor algorithm is is popular for clustering genes as well, so I guess calling it a genetic algorithm is not incorrect.

The algorithm first sorts the documents according to the sum of similarities with its 2r neighbors. It then loops through the documents in descending order of the sum of similarities. If a document is already assigned to a cluster, it is skipped, otherwise a new cluster is created with the document as its seed. Then all neighboring documents to the right and left of the current document that are not already assigned and have a simularity greater than a specified threshold are added to the cluster.

My code for the Nearest Neighbor algorithm is shown below. The algorithm comes from the TMAP book^[1].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

// Source: src/main/java/com/mycompany/myapp/clustering/NearestNeighborClusterer.java package com.mycompany.myapp.clustering; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import org.apache.commons.lang.StringUtils; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; public class NearestNeighborClusterer { private final Log log = LogFactory.getLog(getClass()); private int numNeighbors; private double similarityThreshold; public void setNumNeighbors(int numNeighbors) { this.numNeighbors = numNeighbors; } public void setSimilarityThreshold(double similarityThreshold) { this.similarityThreshold = similarityThreshold; } public List<Cluster> cluster(DocumentCollection collection) { // get neighbors for every document Map<String,Double> similarityMap = collection.getSimilarityMap(); Map<String,List<String>> neighborMap = new HashMap<String,List<String>>(); for (String documentName : collection.getDocumentNames()) { neighborMap.put(documentName, collection.getNeighbors(documentName, similarityMap, numNeighbors)); } // compute sum of similarities of every document with its numNeighbors Map<String,Double> fitnesses = getFitnesses(collection, similarityMap, neighborMap); List<String> sortedDocNames = new ArrayList<String>(); // sort by sum of similarities descending sortedDocNames.addAll(collection.getDocumentNames()); Collections.sort(sortedDocNames, Collections.reverseOrder( new ByValueComparator<String,Double>(fitnesses))); List<Cluster> clusters = new ArrayList<Cluster>(); int clusterId = 0; // Loop through the list of documents in descending order of the sum // of the similarities. Map<String,String> documentClusterMap = new HashMap<String,String>(); for (String docName : sortedDocNames) { // skip if document already assigned to cluster if (documentClusterMap.containsKey(docName)) { continue; } // create cluster with current document Cluster cluster = new Cluster("C" + clusterId); cluster.addDocument(docName, collection.getDocument(docName)); documentClusterMap.put(docName, cluster.getId()); // find all neighboring documents to the left and right of the current // document that are not assigned to a cluster, and have a similarity // greater than our threshold. Add these documents to the new cluster List<String> neighbors = neighborMap.get(docName); for (String neighbor : neighbors) { if (documentClusterMap.containsKey(neighbor)) { continue; } double similarity = similarityMap.get( StringUtils.join(new String[] {docName, neighbor}, ":")); if (similarity < similarityThreshold) { continue; } cluster.addDocument(neighbor, collection.getDocument(neighbor)); documentClusterMap.put(neighbor, cluster.getId()); } clusters.add(cluster); clusterId++; } return clusters; } private Map<String,Double> getFitnesses( DocumentCollection collection, Map<String,Double> similarityMap, Map<String,List<String>> neighbors) { Map<String,Double> fitnesses = new HashMap<String,Double>(); for (String docName : collection.getDocumentNames()) { double fitness = 0.0D; for (String neighborDoc : neighbors.get(docName)) { String key = StringUtils.join( new String[] {docName, neighborDoc}, ":"); fitness += similarityMap.get(key); } fitnesses.put(docName, fitness); } return fitnesses; } }

Although there are extra pre-sorting work that needs to be done, the algorithm is relatively simple to understand. With a similarity threshold set to 0.25, I get the following results:

1 2 3 4 5 6

=== Clusters from Nearest Neighbor Algorithm === (sim threshold = 0.25) C0:[D4, D3] C1:[D7, D6] C2:[D2] C3:[D1] C4:[D5]

Genetic Algorithm

The code for this algorithm was written using an algorithm described in the paper by Maulik and Bandopadhayaya^[5]. In the language of genetics, a document is a gene and a cluster is a chromosome. Clusters get fitter by a reproducing and passing on their best traits, in a process similar to Darwinian evolution.

The algorithm starts by estimating the number of clusters, partitioning the document collection by mod value into the clusters. It then computes the fitness across all clusters in the current generation. After that, it will execute a few (configurable) crossover operations followed by a mutation operation. Crossover involves selecting two cut points, and exchanging the documents for the portion between the cut points, and thus creating a new cluster. Mutation selects two random documents from two random clusters and exchanges them. At the end of each generation, the fitness of the clusters are recomputed. The algorithm terminates when the fitness does not increase any more across generations.

My code for the genetic clustering algorithm is shown below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200

// Source: src/main/java/com/mycompany/myapp/GeneticClusterer.java package com.mycompany.myapp.clustering; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; public class GeneticClusterer { private final Log log = LogFactory.getLog(getClass()); private boolean randomizeData; private int numCrossoversPerMutation; private int maxGenerations; public void setRandomizeData(boolean randomizeData) { this.randomizeData = randomizeData; } public void setNumberOfCrossoversPerMutation(int ncpm) { this.numCrossoversPerMutation = ncpm; } public void setMaxGenerations(int maxGenerations) { this.maxGenerations = maxGenerations; } public List<Cluster> cluster(DocumentCollection collection) { // get initial clusters int k = (int) Math.floor(Math.sqrt(collection.size())); List<Cluster> clusters = new ArrayList<Cluster>(); for (int i = 0; i < k; i++) { Cluster cluster = new Cluster("C" + i); clusters.add(cluster); } if (randomizeData) { collection.shuffle(); } // load it up using mod partitioning, this is P(0) int docId = 0; for (String documentName : collection.getDocumentNames()) { int clusterId = docId % k; clusters.get(clusterId).addDocument( documentName, collection.getDocument(documentName)); docId++; } log.debug("Initial clusters = " + clusters.toString()); // holds previous cluster in the compute loop List<Cluster> prevClusters = new ArrayList<Cluster>(); double prevFitness = 0.0D; int generations = 0; for (;;) { // compute fitness for P(t) double fitness = computeFitness(clusters); // if termination condition achieved, break and return clusters if (prevFitness > fitness) { clusters.clear(); clusters.addAll(prevClusters); break; } // even if termination condition not met, terminate after the // maximum number of generations if (generations > maxGenerations) { break; } // do specified number of crossover operations for this generation for (int i = 0; i < numCrossoversPerMutation; i++) { crossover(clusters, collection, i); generations++; } // followed by a single mutation per generation mutate(clusters, collection); generations++; log.debug("..Intermediate clusters (" + generations + "): " + clusters.toString()); // hold on to previous solution prevClusters.clear(); prevClusters.addAll(clusters); prevFitness = computeFitness(prevClusters); } return clusters; } /** * Come up with something arbitary. Just compute the sum of the radii of * the clusters. * @param clusters * @return */ private double computeFitness(List<Cluster> clusters) { double radius = 0.0D; for (Cluster cluster : clusters) { cluster.getCentroid(); radius += cluster.getRadius(); } return radius; } /** * Selects two random clusters from the list, then selects two cut-points * based on the minimum cluster size of the two clusters. Exchanges the * documents between the cut points. * @param clusters the clusters to operate on. * @param sequence the sequence number of the cross over operation. */ public void crossover(List<Cluster> clusters, DocumentCollection collection, int sequence) { IdGenerator clusterIdGenerator = new IdGenerator(clusters.size()); int[] clusterIds = new int[2]; clusterIds[0] = clusterIdGenerator.getNextId(); clusterIds[1] = clusterIdGenerator.getNextId(); int minSize = Math.min( clusters.get(clusterIds[0]).size(), clusters.get(clusterIds[1]).size()); IdGenerator docIdGenerator = new IdGenerator(minSize); int[] cutPoints = new int[2]; cutPoints[0] = docIdGenerator.getNextId(); cutPoints[1] = docIdGenerator.getNextId(); Arrays.sort(cutPoints); Cluster cluster1 = clusters.get(clusterIds[0]); Cluster cluster2 = clusters.get(clusterIds[1]); for (int i = 0; i < cutPoints[0]; i++) { String docName1 = cluster1.getDocumentName(i); String docName2 = cluster2.getDocumentName(i); cluster1.removeDocument(docName1); cluster2.addDocument(docName1, collection.getDocument(docName1)); cluster2.removeDocument(docName2); cluster1.addDocument(docName2, collection.getDocument(docName2)); } // leave the documents between the cut points alone for (int i = cutPoints[1]; i < minSize; i++) { String docName1 = cluster1.getDocumentName(i); String docName2 = cluster2.getDocumentName(i); cluster1.removeDocument(docName1); cluster2.addDocument(docName1, collection.getDocument(docName1)); cluster2.removeDocument(docName2); cluster1.addDocument(docName2, collection.getDocument(docName2)); } // rebuild the Cluster list, replacing the changed clusters. List<Cluster> crossoverClusters = new ArrayList<Cluster>(); int clusterId = 0; for (Cluster cluster : clusters) { if (clusterId == clusterIds[0]) { crossoverClusters.add(cluster1); } else if (clusterId == clusterIds[1]) { crossoverClusters.add(cluster2); } else { crossoverClusters.add(cluster); } clusterId++; } clusters.clear(); clusters.addAll(crossoverClusters); } /** * Exchanges a random document between two random clusters in the list. * @param clusters the clusters to operate on. */ private void mutate(List<Cluster> clusters, DocumentCollection collection) { // choose two random clusters IdGenerator clusterIdGenerator = new IdGenerator(clusters.size()); int[] clusterIds = new int[2]; clusterIds[0] = clusterIdGenerator.getNextId(); clusterIds[1] = clusterIdGenerator.getNextId(); Cluster cluster1 = clusters.get(clusterIds[0]); Cluster cluster2 = clusters.get(clusterIds[1]); // choose two random documents in the clusters int minSize = Math.min( clusters.get(clusterIds[0]).size(), clusters.get(clusterIds[1]).size()); IdGenerator docIdGenerator = new IdGenerator(minSize); String docName1 = cluster1.getDocumentName(docIdGenerator.getNextId()); String docName2 = cluster2.getDocumentName(docIdGenerator.getNextId()); // exchange the documents cluster1.removeDocument(docName1); cluster1.addDocument(docName2, collection.getDocument(docName2)); cluster2.removeDocument(docName2); cluster2.addDocument(docName1, collection.getDocument(docName1)); // rebuild the cluster list, replacing changed clusters List<Cluster> mutatedClusters = new ArrayList<Cluster>(); int clusterId = 0; for (Cluster cluster : clusters) { if (clusterId == clusterIds[0]) { mutatedClusters.add(cluster1); } else if (clusterId == clusterIds[1]) { mutatedClusters.add(cluster2); } else { mutatedClusters.add(cluster); } clusterId++; } clusters.clear(); clusters.addAll(mutatedClusters); } }

To measure the fitness of a generation (ie the list of clusters), I decided on the sum of the radii of the clusters. I guess I could have used a fancier function such as the sum of similarities in the Nearest Neighbor algorithm. In any case, I terminated the algorithm after 500 generations, and the result it came up with is shown below:

1 2 3

=== Clusters from Genetic Algorithm === C0:[D2, D1, D3, D4] C1:[D5, D7, D6]

Supporting classes

In order to make the code for the clusterers clean and readable, a lot of code is factored out into supporting classes. They are shown below:

Cluster.java

This class models a cluster as a list of named document objects. It provides various methods to compute properties of a cluster given its members, such as centroid, Eucledian Distance or Cosine Similarity of a document from the cluster centroid, etc. The code is shown below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188

// Source: src/main/java/com/mycompany/myapp/clustering/Cluster.java package com.mycompany.myapp.clustering; import java.util.Arrays; import java.util.LinkedHashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Set; import org.apache.commons.lang.ArrayUtils; import org.apache.commons.lang.StringUtils; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; import org.apache.commons.math.stat.descriptive.rank.Max; import Jama.Matrix; public class Cluster { private final Log log = LogFactory.getLog(getClass()); private String id; private Map<String,Matrix> docs = new LinkedHashMap<String,Matrix>(); private List<String> docNames = new LinkedList<String>(); private Matrix centroid = null; public Cluster(String id) { super(); this.id = id; } public String getId() { return id; } public Set<String> getDocumentNames() { return docs.keySet(); } public String getDocumentName(int pos) { return docNames.get(pos); } public Matrix getDocument(String documentName) { return docs.get(documentName); } public Matrix getDocument(int pos) { return docs.get(docNames.get(pos)); } public void addDocument(String docName, Matrix docMatrix) { docs.put(docName, docMatrix); docNames.add(docName); log.debug("...." + id + " += " + docName); } public void removeDocument(String docName) { docs.remove(docName); docNames.remove(docName); log.debug("...." + id + " -= " + docName); } public int size() { return docs.size(); } public boolean contains(String docName) { return docs.containsKey(docName); } /** * Returns a document (term vector) consisting of the average of the * coordinates of the documents in the cluster. Returns a null Matrix * if there are no documents in the cluster. * @return the centroid of the cluster, or null if no documents have * been added to the cluster. */ public Matrix getCentroid() { if (docs.size() == 0) { return null; } Matrix d = docs.get(docNames.get(0)); centroid = new Matrix(d.getRowDimension(), d.getColumnDimension()); for (String docName : docs.keySet()) { Matrix docMatrix = docs.get(docName); centroid = centroid.plus(docMatrix); } centroid = centroid.times(1.0D / docs.size()); return centroid; } /** * Returns the radius of the cluster. The radius is the average of the * square root of the sum of squares of its constituent document term * vector coordinates with that of the centroid. * @return the radius of the cluster. */ public double getRadius() { double radius = 0.0D; if (centroid != null) { for (String docName : docNames) { Matrix doc = getDocument(docName); radius += doc.minus(centroid).normF(); } } return radius / docNames.size(); } /** * Returns the Eucledian distance between the centroid of this cluster * and the new document. * @param doc the document to be measured for distance. * @return the eucledian distance between the cluster centroid and the * document. */ public double getEucledianDistance(Matrix doc) { if (centroid != null) { return (doc.minus(centroid)).normF(); } return 0.0D; } /** * Returns the maximum distance from the specified document to any of * the documents in the cluster. * @param doc the document to be measured for distance. * @return the complete linkage distance from the cluster. */ public double getCompleteLinkageDistance(Matrix doc) { Max max = new Max(); if (docs.size() ==0) { return 0.0D; } double[] distances = new double[docs.size()]; for (int i = 0; i < distances.length; i++) { Matrix clusterDoc = docs.get(docNames.get(i)); distances[i] = clusterDoc.minus(doc).normF(); } return max.evaluate(distances); } /** * Returns the cosine similarity between the centroid of this cluster * and the new document. * @param doc the document to be measured for similarity. * @return the similarity of the centroid of the cluster to the document. */ public double getSimilarity(Matrix doc) { if (centroid != null) { double dotProduct = centroid.arrayTimes(doc).norm1(); double normProduct = centroid.normF() * doc.normF(); return dotProduct / normProduct; } return 0.0D; } @Override public boolean equals(Object obj) { if (!(obj instanceof Cluster)) { return false; } Cluster that = (Cluster) obj; String[] thisDocNames = this.getDocumentNames().toArray(new String[0]); String[] thatDocNames = that.getDocumentNames().toArray(new String[0]); if (thisDocNames.length != thatDocNames.length) { return false; } Arrays.sort(thisDocNames); Arrays.sort(thatDocNames); return ArrayUtils.isEquals(thisDocNames, thatDocNames); } @Override public int hashCode() { String[] docNames = getDocumentNames().toArray(new String[0]); Arrays.sort(docNames); return StringUtils.join(docNames, ",").hashCode(); } @Override public String toString() { return id + ":" + docs.keySet().toString(); } }

DocumentCollection.java

The DocumentCollection represents the collection of documents previously represented by the term-document matrix. It provides convenience accessor methods, and other methods to compute similarity of documents to its collection and get neighboring documents by similarity. These were used by the nearest neighbor algorithm.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

// Source: src/main/java/com/mycompany/myapp/DocumentCollection.java package com.mycompany.myapp.clustering; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import org.apache.commons.lang.StringUtils; import Jama.Matrix; import com.mycompany.myapp.similarity.CosineSimilarity; public class DocumentCollection { private Matrix tdMatrix; private Map<String,Matrix> documentMap; private List<String> documentNames; public DocumentCollection(Matrix tdMatrix, String[] docNames) { int position = 0; this.tdMatrix = tdMatrix; this.documentMap = new HashMap<String,Matrix>(); this.documentNames = new ArrayList<String>(); for (String documentName : docNames) { documentMap.put(documentName, tdMatrix.getMatrix( 0, tdMatrix.getRowDimension() - 1, position, position)); documentNames.add(documentName); position++; } } public int size() { return documentMap.keySet().size(); } public List<String> getDocumentNames() { return documentNames; } public String getDocumentNameAt(int position) { return documentNames.get(position); } public Matrix getDocumentAt(int position) { return documentMap.get(documentNames.get(position)); } public Matrix getDocument(String documentName) { return documentMap.get(documentName); } public void shuffle() { Collections.shuffle(documentNames); } public Map<String,Double> getSimilarityMap() { Map<String,Double> similarityMap = new HashMap<String,Double>(); CosineSimilarity similarity = new CosineSimilarity(); Matrix similarityMatrix = similarity.transform(tdMatrix); for (int i = 0; i < similarityMatrix.getRowDimension(); i++) { for (int j = 0; j < similarityMatrix.getColumnDimension(); j++) { String sourceDoc = getDocumentNameAt(i); String targetDoc = getDocumentNameAt(j); similarityMap.put(StringUtils.join( new String[] {sourceDoc, targetDoc}, ":"), similarityMatrix.get(i, j)); } } return similarityMap; } public List<String> getNeighbors(String docName, Map<String,Double> similarityMap, int numNeighbors) { if (numNeighbors > size()) { throw new IllegalArgumentException( "numNeighbors too large, max: " + size()); } final Map<String,Double> differenceMap = new HashMap<String,Double>(); List<String> neighbors = new ArrayList<String>(); neighbors.addAll(documentNames); for (String documentName : documentNames) { String key = StringUtils.join( new String[] {docName, documentName}, ":"); double difference = Math.abs(similarityMap.get(key) - 1.0D); differenceMap.put(documentName, difference); } Collections.sort(neighbors, new ByValueComparator<String,Double>(differenceMap)); return neighbors.subList(0, numNeighbors + 1); } }

IdGenerator.java

IdGenerator is a "safe" random number generator that will always return unique different numbers till its numbers are exhausted. It is seeded with a maximum number, so it will return unique numbers from 0 to the (maximum - 1) as long as can, then it starts repeating the numbers.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

// Source: src/main/java/com/mycompany/myapp/IdGenerator.java package com.mycompany.myapp.clustering; import java.util.HashSet; import java.util.Random; import java.util.Set; public class IdGenerator { private int upperBound; private Random randomizer; private Set<Integer> ids = new HashSet<Integer>(); public IdGenerator(int upperBound) { this.upperBound = upperBound; randomizer = new Random(); } public int getNextId() { if (ids.size() == upperBound) { ids.clear(); } for (;;) { int id = randomizer.nextInt(upperBound); if (ids.contains(id)) { continue; } ids.add(id); return id; } } }

ByValueComparator.java

The ByValueComparator is a generic comparator that allows you to sort a List based on a supporting map. The idea for this came from Jeffrey Bigham's blog post Sorting Java Map by Value, although I have used Java Generics to allow it to sort any kind of Map.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// Source: src/main/java/com/mycompany/myapp/clustering/ByValueComparator.java package com.mycompany.myapp.clustering; import java.util.Comparator; import java.util.HashMap; import java.util.Map; public class ByValueComparator<K,V extends Comparable<? super V>> implements Comparator<K> { private Map<K,V> map = new HashMap<K,V>(); public ByValueComparator(Map<K,V> map) { this.map = map; } public int compare(K k1, K k2) { return map.get(k1).compareTo(map.get(k2)); } }

Test case

The test case is a simple JUnit test case that runs through all the clustering code using my little collection of seven document titles to build the term document matrix off of. Here is the code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117

// Source: src/test/java/com/mycompany/myapp/clustering/ClusteringTest.java package com.mycompany.myapp.clustering; import java.io.BufferedReader; import java.io.FileReader; import java.io.Reader; import java.io.StringReader; import java.util.ArrayList; import java.util.LinkedHashMap; import java.util.List; import java.util.Map; import org.apache.commons.lang.StringUtils; import org.junit.Before; import org.junit.Test; import org.springframework.jdbc.datasource.DriverManagerDataSource; import Jama.Matrix; import com.mycompany.myapp.indexers.IdfIndexer; import com.mycompany.myapp.indexers.VectorGenerator; public class ClusteringTest { private Matrix tdMatrix; private String[] documentNames; private DocumentCollection documentCollection; @Before public void setUp() throws Exception { VectorGenerator vectorGenerator = new VectorGenerator(); vectorGenerator.setDataSource(new DriverManagerDataSource( "com.mysql.jdbc.Driver", "jdbc:mysql://localhost:3306/tmdb", "irstuff", "irstuff")); Map<String,Reader> documents = new LinkedHashMap<String,Reader>(); BufferedReader reader = new BufferedReader( new FileReader("src/test/resources/data/indexing_sample_data.txt")); String line = null; while ((line = reader.readLine()) != null) { String[] docTitleParts = StringUtils.split(line, ";"); documents.put(docTitleParts[0], new StringReader(docTitleParts[1])); } vectorGenerator.generateVector(documents); IdfIndexer indexer = new IdfIndexer(); tdMatrix = indexer.transform(vectorGenerator.getMatrix()); documentNames = vectorGenerator.getDocumentNames(); documentCollection = new DocumentCollection(tdMatrix, documentNames); } @Test public void testKMeansClustering() throws Exception { KMeansClusterer clusterer = new KMeansClusterer(); clusterer.setInitialClusterAssignments(new String[] {"D1", "D3"}); List<Cluster> clusters = clusterer.cluster(documentCollection); System.out.println("=== Clusters from K-Means algorithm ==="); for (Cluster cluster : clusters) { System.out.println(cluster.toString()); } } @Test public void testQtClustering() throws Exception { QtClusterer clusterer = new QtClusterer(); clusterer.setMaxRadius(0.40D); clusterer.setRandomizeDocuments(true); List<Cluster> clusters = clusterer.cluster(documentCollection); System.out.println("=== Clusters from QT Algorithm ==="); for (Cluster cluster : clusters) { System.out.println(cluster.toString()); } } @Test public void testSimulatedAnnealingClustering() throws Exception { SimulatedAnnealingClusterer clusterer = new SimulatedAnnealingClusterer(); clusterer.setRandomizeDocs(false); clusterer.setNumberOfLoops(5); clusterer.setInitialTemperature(100.0D); clusterer.setFinalTemperature(1.0D); clusterer.setDownhillProbabilityCutoff(0.7D); List<Cluster> clusters = clusterer.cluster(documentCollection); System.out.println( "=== Clusters from Simulated Annealing Algorithm ==="); for (Cluster cluster : clusters) { System.out.println(cluster.toString()); } } @Test public void testNearestNeighborClustering() throws Exception { NearestNeighborClusterer clusterer = new NearestNeighborClusterer(); clusterer.setNumNeighbors(2); clusterer.setSimilarityThreshold(0.25); List<Cluster> clusters = clusterer.cluster(documentCollection); System.out.println("=== Clusters from Nearest Neighbor Algorithm ==="); for (Cluster cluster : clusters) { System.out.println(cluster.toString()); } } @Test public void testGeneticAlgorithmClustering() throws Exception { GeneticClusterer clusterer = new GeneticClusterer(); clusterer.setNumberOfCrossoversPerMutation(5); clusterer.setMaxGenerations(500); clusterer.setRandomizeData(false); List<Cluster> clusters = clusterer.cluster(documentCollection); System.out.println("=== Clusters from Genetic Algorithm ==="); for (Cluster cluster : clusters) { System.out.println(cluster.toString()); } } }

References

References to books and Internet articles that the above code is based on, in no particular order:

1. Text Mining Application Programming, by Dr. Manu Konchady.
2. Wikipedia article on QT (Quality Threshold) clustering.
3. Wikipedia article on Nearest-Neighbor algorithm.
4. Research article on Hierarchic document clustering using a genetic algorithm by Robertson, Santimetrvirul and Willet, of the University of Sheffield, UK.
5. Research article on Genetic algorithm-based clustering technique (requires PDF download) by Maulik and Bandopadhyay, of Government Engineering College, Kalyani, India and Indian Statistical Institute, Calcutta, India.

Update 2009-04-26: In recent posts, I have been building on code written and described in previous posts, so there were (and rightly so) quite a few requests for the code. So I've created a project on Sourceforge to host the code. You will find the complete source code built so far in the project's SVN repository.