Rafazwonull vs Joe I/O

Again, I was pointed at something by a friend which I had not thought of before. Of course it had occurred to me that the issue I am covering with my thesis might be interested to the English-speaking world, but up until now I was quite unsure whether to change the way I write (and publicly and unchangebly leave my English traces in the never-forgetting web). However, the decision is taken and this will be my first English post.

Aquaint Blog crawler project

As I introduced before, I am currently writing my master thesis on an issue which may be drafted „Quality Models and Data Mining in Blogs“. I explained to the German speaking readers, that I was going to implement a webcrawler based on an implementation from the Hildesheim University AQUAINT project. The bot is to crawl through a controlled collection of Weblogs and record attributes (currently 150) which could be of interest for the statistical creation of binary, quality based model. Using the popular WEKA-toolset, I am confident that it will be possible to find signigicant patterns in the entity of the quality-labeled blogs. These patterns will help us discriminating from a random collection of much bigger size, equally „good“ (i.e. reliable, of high quality, high reputation, A-Listers) blogs from blogs which do not reach up to the standard of the controlled collection. However, this is not the only goal of collecting those features: we might find different structures in e.g. German and English blogs, or which is even more probable European and Asian blogs. The range of possibilites is huge once the crawler is running in a stable version and I am sure the features I am recording really express what I think they do.

The current implementation…

Currently, the crawler is runs on a server and collects a number of random German blogs. I have run some trials with WEKA and it seems my idea is not all that dumb as I am able to successfully tell apart high-quality blogs from a random collection using the learned model using different algorithms (the weakest of which is Naive Bayes with an accuracy of 50%, the strongest being (currently) J48 with about 92%).

… and my current challenge: Coherence Analyis

What I am currently working at is a notion of cohesiveness of a blog, which I would like to explain in this post. What do I mean by „cohesiveness“? I would like to introduce this as a measure determining the topic variation of a certain blog. There may be blogs which cover e.g. the issues „dogs“ and „cats“, which occupy themselves with pets. On the other hand there may be bloggers writing on „cats“, „cars“, „computers“. As you can see, the range of different topics is bigger in the latter example. This means the blogger is less focussed on a specific range of topics.

How can we measure this cohesiveness and see how many topics the blogger is writing about? I consider the usage of tags and categories an important clue, as most bloggers use them to organize their post semantically. And what is more important, tags are even linked to a page which collects and displays all the posts marked with the specific tag. This page may be considered the blogger’s concept of the tag he uses. This is an important notion, as one blog might use the tag „cats“ to write on animals, while another one might use it as an acronym for „Computer Assisted Trading System„. So we can assume, the absolute meaning of the terms and their distane does not determine as good the actual topical difference of the blog as the blog-specific term-usage.

If (Cats!=Cats)...

Now we can assume, that each of our tag-pages (or respectively categories page) which links to a same host page is representing one of the issues the blog is dealing with. How can we determine the similarity of the issues? One way, and this is the most obvious one, I guess, is to determine the similarity of each tag page as a basis to calculate the overall cohesiveness. This approach is not all new and it has been successfully used by a group of dutch scientist some time ago. I modified it to fit my needs and I would like to introduce some of the results here, including their shortcomings.

Jiyin He Coherence

There are a couple of possible approaches. The one I currently consider most applicable and quite sophisticated uses a package called simmetrics which allows the application of various string comparison algorithms, including some vector space models as cosine similarity and euclidean distance. It offers some other, more basic functionalities as qgram or dice, but I was primarily focussing on the vector space models.

Simmetrics Performance (by http://www.dcs.shef.ac.uk/~sam)

One of my latest approaches is to use the cohesiveness notion introduced by the above mentioned group to calculate the similarity of all the links to the tag pages. The coherence ranges from 0 (meaning none) to 1 (meaning same documents). In my crawler, it is called „JiyinHeCoherencePerUrls“ after the person who introduced it (to me!). The pseudo-code is as follows:

For a given Blog, get  all the Tag-Pages.
Take the first Tag-Page and get all the text on the page;

For each of the Tag-Pages,
{
take the next Tag-Page and get all the text on the page;
Compare the two texts using the simmetrics package and save the result;
Cummulate the results of the comparisons;
Count how many comparisons we have done;
Set first Tag-Page to next Tag-Page.
}
Set the Coherence to the cumulated similarities per number of thecomparisons.

However, this way of measurement has some offsides which I can only partly compensate:

• The simmetrics calculation using Vector space models is not stable. It sometimes just hangs up. I don’t know why. However, I am not sure if  using character-based models is an appropriate alternative.
• As you see, I copy the text of the second page once. This is to avoid double server access to download the same page. We are opening up 10 pages per second if we do not reduce server strain, so this is why I set a delay to each page access which is between 4 seconds (trial) and 12 seconds (real crawling situation).
• This method eats up a lot of resources. I reduced the size of the strings to compare using just the link labels of a page, which is an approach which had been favoured by a lot of search engines in former times (maybe up till now). This is due to the fact that usually the content of pages can be quite well determined if you take into account the links they use. However, I still have the problem with the Vector space calculation hang-up with some pages…

Simple Term-based coherence

Another notion of coherence I have been experimenting with is a more simple, but also more stable one. I have refrained from calculating the similarity, I have just defined the coherence from to pages as the number of same words on two pages per number of all words on the pages. Of course we only consider unique terms, ignore double occurences, space, punctuation etc. This leads to a really simple model, the pseudo code of which is following:

For a given Blog,
get  all the Tag-Pages.

Take the first Tag-Page and get all the text on the page;
Tokenize the content to words.

For each of the Tag-Pages,
{
take the next Tag-Page and get all the text on the page;
Tokenize the content to words.

For each of the words of  the first Tag page
For each of the words of the next Tag page
If word#1 equals word#2
increment nr of same words per url;

Division: Divide the nr of same words pre url per words first Tag page + words on next Tag page;
Set first Tag page text to next Tag page text
}

Calculate Standard Deviation, Mean and Median for all the Divisions done throughout the page comparisons.

This approach is much faster and more stable, however one can doubt (as Max usually does), the validity of the calculated feature.

After all, I am not sure which algorithm to use in the end. Actually I prefer the first one, but as the Vector based similarity approach is not working, I doubt whether the second one is worse than qGram analyis. After all we must not forget, that the feature I am discussing here will not be used as an isolated instance but is an attribute next to about 149 which are less complicated I feel. While you can surely argue the validity of the coherence measure, there is less uncertainty on attributes as the number of H1 tags or outlinks. But I need to say, this one has been most interesting so far.

Anyway, hints on how to use  to Vector based simmetrics here and why they hang up are highly appreciated, and so are ideas on which measure is the more appropriate one. I will happily provide the source code of the classes upon request. Usually I would publish it right away, but you see, I am still to be evaluated so I will better avoid bumbing into allegations I had commited plagiarism from an Internet source… So, if you like it, there is more to come.

Good Night.

-r-