Data into results

Programming Collective Intelligence is a great book. It covers most of the existing data mining algorithms and presents many applications for them.  It covers clustering (k-means, hierarchical), supervised classification (k-nearest neighbours, Naïve Bayes, decision trees, SVM), data analysis (non negative matrix factorization), optimisation (hill climbing, simulated annealing and genetic algorithms) and end with genetic programming. Along the way, it present application like spam detection, pricing, recommendation, … If you want to start in data mining this is a very good way. 0

Read more…

Now it’s time to create some clusters from our twitter data. In this post, we focus only on biographical tags and we use the old kmeans algorithms in order to find significant clusters. At least we hope so.

Read more…

After some first statistics about the twitter dataset, I try to get further. In this post, i’ve discussed how to extract token from Twitter, more precisely from the biography and the last tweets of users. The problem is that the bio attribute is composed of 11702 tokens. No way all these tokens are interesting (are itv1, rmer, 112/xm givin you some insight?). But how to remove all the uninteresting tokens while keeping the goods one. As always, there is a tradoff between keeping too much noise and removing some gold nuggets. In my view, an interesting token is a tag (as a tag is usually giving you some knowledge about an item). The problem is for each user, you have a set of token. What you want is a set of tags, i.e. token with interest.

I found two ways to create the keeped tags from all the tokens. The first, the whitelist one, check each token against the whitelist. If it’s not in, remove the token. If it’s in, this token is a tag.  The second, the blacklist one, checks also each token against the blacklist, but keeps only token which are not in the blacklist. These two methods have drawbacks. The whitelist is more likely to remove interesting tokens which were not spotted. twitter should be a tag but if you’ve made the whitelist two years ago, you won’t have whitelisted it (or you’re a visionary). Thus, you could miss some emerging trends. The blacklist has the opposite drawback, you keep to much. Considering my goals, I choose to use the whitelist way. Now it’s the time to construct the list of tokens which are really tags.

The easier solution is to check each token in the dataset. While probably the best solution, I found it boring and not in the data mining way. Thus I use some tricks , which you can call a priori knowledge or choices :

• Trick 1: A tag is in general a english noun. English because handling multiple language will be a pain. I have no idea why it should be a noun, but all the tags I think about are nouns. Thus, we can use the wordnet which is a english lexical database. We just have to dump all noun to our whitelist. This trick takes out 7159 tokens (61%).
• Trick 2: A tag should be used many times. Could we extract a pattern of a tag used only once? I know that none of the algorithm I can use on this dataset could do that. Thus, it is useless to keep them. Of course, this decision could not be made if the dataset is growing (this tag could be more used in the future). With a threshold of 10 occurrences, this discard 10911 token (93%)
• Trick 3: A tag as more than 3 characters. As for the first trick, all interesting tag in my mind have more than 3 letters. The most frequent tokens are ‘i‘, ‘my‘, ‘you‘ (and  ‘love‘, but the pattern  ‘i love you‘ has only one occurrence in a profile with bio attribute “give me a love, and i will love you more :3“, funny). This trick dismiss 1193 token (10%).
• Maybe you have other tricks?

Thus, using all these 3 tricks we end with only 430 tags. Easier to manage and read. Here are the more used tags :

+-----------+----------------------+
| token     | count(distinct user) |
+-----------+----------------------+
| twitter   |                  243 |
| love      |                  238 |
| news      |                  208 |
| life      |                  170 |
| music     |                  167 |
| world     |                  143 |
| social    |                  138 |
| more      |                  132 |
| writer    |                  130 |
| people    |                  119 |
| like      |                  111 |
| time      |                  108 |
| have      |                  104 |
| business  |                  102 |
| marketing |                   98 |
| blogger   |                   88 |
| work      |                   85 |
| internet  |                   81 |
| lover     |                   81 |
| real      |                   79 |
+-----------+----------------------+

As you can see, there is still many tokens which are likely to be meaningless (‘more‘, ‘have‘). Nevertheless it’s easier to see thing. Uninterresting tags are also unlikely to be considered as a pattern by our algorithms. At least we hope so

Ok, that’s was for the biography. Now the content attribute. It’s more challenging having 126,566 tokens ! Using these 3 tricks reduce the number to 3207. Could all these tags give an insight?

PS : Just to remember the SQL query

select twi.token, count(*) from twitterBioToken twi join WordNetTokens dico on dico.token = twi.token where type = ‘noun’ and length(twi.token) > 3 group by twi.token having count(*) >= 10

Twitter is a famous social website. It works like a blog but limits the message length (160 characters). Thus, it is also called micro blogging and should be get more frequent update about every thought you could have. Could we do something of such atrophied data?

I’m only at the begining of this project. I have settle a basic crawl infrastructure in order to extract a dataset from twitter and mine in it.

The taken data have five attributes : user name, location, followers count, following count, biography (a small who am i field) and the concatenation of theirs last messages. Below is a exemple of a profile, a public person named Richard Bacon. In this example, you could figure how complex these information are. The location is quite unclear (GPS coordinates). The biography is quite small (but really clear on this example). And the content is … confusing.

         id: 1351
       name: richardpbacon
   location: iphone 51.511682 0.224661
nbFollowing: 72
nbFollowers: 360574
        bio: minor celebrity bbc radio fivelive presenter
    content: yep she tweeted sunday her tweet alone theyd have
run monday news 10 asking susan boyle backlash she overrated
sounds like someone team listened 5live way work sounds like
someone news 10 team (...)

Actually, the content field displayed above was already treated. I’ve use Lucene in order to tokenize and clean the text part. Bellow is the text before and after applying Lucene in order to get tokens instead of free form text.

before :
News at 10 asking, is there a Susan Boyle backlash / is she
overrated? Sounds like someone on the team listened to 5live
on the way to work.

after :
news 10 asking susan boyle backlash she overrated sounds like
someone team listened 5live way work

As you can see, there is still a lot of meaningless tokens like 5live.

I have done a quick (not so much data, not a god algorithm, not so much cleaning) segmentation on only the biography tokens. Nevertheless, trying with 25 clusters, things start to emerge. For instance, a cluster has a high relative frequency of tokens like university, engineering, computer, student, science, studying, school. This is a students cluster (3% of my dataset). There is also a cluster for official public people (twitter, page, official, feed), some geeks clusters (one for geek users of mac or linux, one for open source software developers, another for web developers), a companies twitter account cluster (tokens like company, services, production, advertising, leading) and a photographs one (photography, make-up, light, photo, traveler).

More work has to be done, but the first insight are encouraging.

Last book I read was Collective Intelligence in Action from Satman Alag (ed. Manning). It covers data mining from a web 2.0 related view.  Data is generated by users in many form (ratings, tags, blogs, web pages,  …). Such data are not well defined. An user can create a new tag like gloupy without giving you the meaning. There is also some text mining issues. How to understand the meaning of a sentences?

The book is divided in three parts. First (half of the book) describe data and more especially how to get them (web crawling, blog trackers). The second part is about exploiting the data, i.e. data mining (clustering and prediction). There is also a chapter on converting text into tokens. The last part is on examples of applications. Making an intelligent search engine or a recommendation engine (with an interesting discussion on Amazon, Google News and Netflix solutions).

Being based on Java code, it relies upon some libraries like Nutch for web crawling,  Lucene for text handling and Weka for the data mining. I think there is too much java code in the book. Indeed, it’s boring an you skip easily some pages. For instance, the book use kmeans with self made code, Weka code and JDM (an data mining java api) code. It seems quite useless to see three times the same thing.

Nevertheless, I have found this book very interesting and a very good introduction to web mining, an area where I have little knowledge of.