The best kittens, technology, and video games blog in the world.

Monday, January 28, 2008

PageRank - a new addition to your Data Processing Toolkit

G0321 by Piez from flickr (CC-BY)

Back when I was at Universität des Saarlandes we had a great seminar at MPII. It was called "Data Processing Tips and Tricks" and covered some important data processing techniques. These techniques varied a lot. What they had in common was their universality - you could throw pretty much any data at them and extract something. And by preprocessing your data differently, and postprocessing the results differently, you could get loads of interesting things without inventing any new algorithms.

Here's a partial list of the classic universal data processing methods, in no particular order:

  • Bayesian statistics
  • EM algorithm
  • Wavelets
  • Levenberg-Marquardt optimization
  • Lloyd clustering
  • Karhunen-Loeve Transform (aka Principal Component Analysis)
  • Singular Value Decomposition
  • multi-dimensional scaling
  • Algebraic reconstruction technique
  • Support Vector Machines
  • Graph Cut Optimization
  • Level-Set Methods
  • RANSAC
  • Neural Networks
  • Hidden Markov Models
  • Regular expressions

By simply being aware of their existence you greatly increase your chances of solving really big problems you'll be facing. For example naive Bayesian statistics was famously used for fighting spam, and in spite of its striking simplicity is much more effective than all the custom and complicated methods that preceded it.

In the last few years the data processing toolkit got one a new tool - PageRank. Pretty much everybody knows how it works for scoring websites, but the algorithm is capable of much more than that. One great example is extracting keywords from documents. It has nothing to do with the original problem of website scoring, but if you treat words as nodes (websites), create links between words that occur close to each other, and run PageRank on such a graph, you get very decent keywords. Of course you might want to add some pre- and post-processing to improve keyword quality (obviously removing HTML tags, also stemming, removing stopwords, weighting words by part of speech or whatever you feel like doing), but so does Google in determining pages' scores. And I bet you expected keyword extractors to either actually understand what's written (not possible yet) or to simply count number of occurences (really horrible results).

You can use PageRank to asses importance of countries in international trade, importance of people in organization's communication flow, and many other problems. Or you could simply throw arbitrary graphs at PageRank, look at the results and simply guess what they mean. Perhaps that will be enough to solve the problem you've been thinking about for such a long time. If not, you still have two dozen of other universally applicable techniques to choose from.

2 comments:

ali said...

beautiful kitties

indera said...

when google update his page rank?