What algorithms do "the big ones" use to cluster news?

Question

I want to cluster texts for a news website.

At the moment I use this algorithm to find the related articles. But I found out that PHP's similar_text() gives very good results, too.

What sort of algorithms do "the big ones", Google News, Topix, Techmeme, Wikio, Megite etc., use? Of course, you don't know exactly how the algorithms work. It's secret. But maybe someone knows approximately the way they work?

The algorithm I use at the moment is very slow. It only compares two articles. So for having the relations between 5,000 articles you need about 12,500,000 comparisons. This is quite a lot.

Are there alternatives to reduce the number of necessary comparisons? [I don't look for improvements for my algorithm.] What do "the big ones" do? I'm sure they don't always compare one article to another and this 12,500,000 times for 5,000 news.

It would be great if somebody can say something about this topic.

Answer 1

I find Apache Solr's related items algorithm to be phenomenal, and as it's open source the algorithms are freely available. Well worth a look. Add in a boost when the dates of the items are similar and you'd be well on your way.

Answer 2

Variations or combinations of standard clustering algorithms:

• K-means
• Fuzzy c-means clustering
• Support Vector Machines

Also, using tags is an easy way to do it. If people tag things for you you can automatically suggest based on tags (and probably a clustering over the title of the articles will be useful).

A good thing to try is to use the CLUTO on the data and test various algorithms.

BTW, there is no need to compare the whole contents of the articles each time, only the feature vector, which gets recalculated only when the docyment changes, if ever.

Answer 3

The key idea is usually to turn the text into feature vectors that can be easily compared. One (quite simple) solution is to create a dictionary and then build a bit vector for every text where every bit indicates the presence of a specific word from the dictionary.

Dictionary: animal, cat, dog, house, tree, eat, garden, gras, love, flower

Text 1: Our cat loves to eat flowers in the garden in front of our house.
Feature vector: 01010 11011

Text 2: We have two animals - a dog and a cat.
Feature vector: 11100 00000

Text 3: There are many kinds of flowers in our garden and a huge tree.
Feature vector: 00001 01001

Now you can just compare the feature vectors using Hamming distance. In the example the distances are the following.

Text 1: 01010 11011        Text 1: 01010 11011        Text 2: 11100 00000 
Text 2: 11100 00000        Text 3: 00001 01001        Text 3: 00001 01001
        10110 11011 => 7           01011 10010 => 6           11101 01001 => 5

A real implementation has to solve some linguistic problems - for example stemming.

Answer 4

Cluto is a good tool for clustering but I have used another algorithm that converges extremely fast and very efficient. Here is the link to it. You should be able to implement it in any language of your choice. It works on labelled graphs.

If your webhost supports PHP then it must support python/Perl. I would suggest you use standard graph packages in PERL and python that does this sort of computations. You can find a whole lot of PERL packages for clustering, similarity, collaborative filtering etc on cpan

I have also used networkx for python which is pretty awesome for basic graph algorithms. Of course, all this is assuming you can represent your content as graphs.

Answer 5

There was an NPR interview with a NYTimes Senior Software Architect where he stated that they used Cosine Similarity to cluster words and phrases in their news search trends:

Answer 6

Here is an optimization that you can do:

One of our major performance optimizations for the “related questions” query is removing the top 10,000 most common English dictionary words (as determined by Google search) before submitting the query to the SQL Server 2008 full text engine. It’s shocking how little is left of most posts once you remove the top 10k English dictionary words. This helps limit and narrow the returned results, which makes the query dramatically faster.

It's from Stack Overflow podcast #32.

Answer 7

Not exactly an answer but here is some 3rd party software that might help you out: http://www.krollontrack.com/ndmetric/

Answer 8

The trick isn't in the similarity algorithm, but in identifying the features of each article. In general, features should include only the most representative words, you can start by using words that are much more frequent in the article itself then in a general corpus.

Answer 9

I sat through a talk by a guy from the Google AdWords / AdSense team recently on just this subject. His comments were specifically for analyzing similarity content for optimizing ad choice, but from other things he said I gather they use similar techniques for news, search results, etc.

Specifically, he said that they make heavy use of latent semantic indexing (via singular value decomposition, which is an algorithm you could implement in PHP, though it would be slow for large data sets). The seminal paper on the subject is Deerwester, Dumais, Furnas, Landauer, and Harshman, 1990, with some influential follow-up work by Blei, Ng, and Jordan. The wikipedia pages (linked above) give some reference implementations of the technique, though I haven't found one in PHP. The singular value decomposition step effectively eliminates words that are common enough as to have little contribution to the semantic content of the paper, and is more robust than, e.g., removing the 10,000 most common English words from the corpus.

Answer 10

Google uses distributed process for almost everything (not only very smart algorithms). It published papers on its proprietary architeture that enables algorithms to actually make it:

• Google File System is the distributed file system. Base of it all
• Map Reduce is a framework for using functional programming concepts and making distributed programming easier.
• Big Table is the distributed non-relational database. In spite of being non-relational, Google made it avaible throguh JPA, as it can be seen on Google App Engine for Java.
• Chubby is a distributed lock server used on all the server/client failover/election management.
• Sawzall is a domain specific language that allows developers to craft common Map Reduce applications with a lot less coding. Uses the now open source Protocol Buffers as a multi-language, blindling fast, serialization mechanism.

Answer 11

Some others have provided excellent explanations and I had fun reading them.

This is not an algorithmic description but since you are using PHP, it could provide you the straight up working solution. I would strongly recommend going with the Standard Analyzer which is an implementation of the Zend port of Lucene from Java. It does:

• Stem words for greater search relevancy
• Use the pre-existing Zend lowercase filter
• Filter out a standard set of stop words using the Zend stop words filter

While you will need the Zend library, you can have an independent install as well. The author wrote the wpSearch which is a working implementation and in my opinion the best search engine available for the CMS. You could take your cue from the plugin implementation and get it off the ground.