What are Effective Regression Techniques for Linguistic Analysis of Linked Data?

Question

Cross-post from MathOverflow where it was suggested that I might get better results here.

I am in the early stages of a problem that involves parsing a large number ($\approx 5 \times 10^9$) of documents (web pages) and estimating values from them. In particular I need to identify pages that offer downloads of pirated files and estimate their traffic. Whereas some websites make their traffic statistics public, many do not. I am left with a sparse data set with which to fill in a large number of blanks. The good news is that flagged pages are verified by a human, who extracts any page view data they can find. This means I don't have to worry about writing software to recognize or collect that data when it's present. My hopes are to apply my techniques from this problem to many others if I'm successful.

As you can see this is actually a two-part question. There is a classification stage, where I estimate whether a site is likely to yield a pirated file, and an estimation stage, where I use regression techniques to estimate how many views the page might have.

My (naive) approach would be to extract n-gram count vectors from each document (n-word-gram, not n-character-gram), which gives me a mapping from a symbolic set into a (high dimensional) integer set. It's a lot of dimensions, but I've done it before with some success. I could use this n-gram "profile" to apply logistic regression or angle comparison for classification, then linear regression for estimation. There are some really sophisticated machine learning algorithms out there, but I'm not sure what sort of performance evaluation techniques I could use on them in the estimation phase.

However, I'm sure there's a better way to do this. I can't imagine how a linguistic profile of a web page has much correlation at all with its traffic. I believe that site traffic has a lot more to do with the pages that link to it, and I could imagine using graph theory to model the propagation of page views. However, unless the site is flagged for viewing that data won't be collected. Only a small amount of pages will have their page views recorded. I could perhaps write a regular expression to match common phrases used when expressing "how many views" they got, but I'm not willing to commit time writing some sort of complex classification algorithm for that particular feature.

I'm also sure there's a large number of other measurements I could extract from a web page that I'm not thinking of. Really it's a problem of converting web page content and link topology into meaningful variables that can be used in regression analysis. So my questions to you are these:

• What techniques have proven effective for classification of documents?
• Where would I even begin to learn about modeling and estimating internet traffic?

I'm sorry if these are not rigorous enough questions, but at this stage I need more of a lay of the land than advice on a particular theorem. These subjects are not my primary area of expertise.

Answer 1

Both questions are hard, I'll give a shot at the first one.

A straightforward approach to classify documents is to compute their tf-idf. In short, you consider the text is a bag of words, i.e. that it has no linear structure, and you compute a score that says how much the word is specific of a document. I explain a little bit about how to do this here.

Once this is done, texts are often compared with the cosine similarity measure, which is the cosine of their tf-idf vectors. If they have a high similarity, they have similar specific words and you can guess they are about the same topic.

You can compute cosines, but you can do all sorts of geometric operations. In particular you can fit Support Vector Machines which give good results in text classifications.

Finally, a last idea would be to use keyword extraction tools, such as the Alchemy API to summarize your documents to 10-20 relevant keywords. You can then use standard classification techniques on this dataset of reduced dimension.

As a good primer on text classification, I suggest Introduction to Information Retrieval (free), and Mining the Social Web... not free but probably available from the best pirate sites ;-)