WordTree: Visualization Tool for Twitter

Hi all,

It has been a while since my last post. But, I am still alive!! In this post I'll be talking about one of my last projects based on natural language processing (NLP) that I've developed: A Visual Word Tree.

But what is a Word Tree ?

A word tree is a visual analyzer tool for unstructured text, such as a article, speech or a book. It is also a new visualization technique that makes easy the exploration of repetitive context. The main idea behind it includes the concordance principle.

Concordances have been used for centuries at biblical scholars to see how different words occur in religious texts. It is a special type of indexation technique, which shows near to each word some words that appears before or after that one. For instance, consider the phrase "if love" in Romeo and Juliet which occurs three times:

As the figure shown above, you will notice that in the words following 'if love' there are many repeated phrases. For example, "be" follows "if love" in all three cases. And "be blind" follows in two cases. To create a word tree, the computer merges all the matching phrases, as in this diagram:

As you can notice, this diagram has a shape of a tree of each node represented by a word, which can be easily interpreted and visualized. It emphasizes in the interactive exploration of short texts (like the short texts of the Bible). This visualization is called WordTree and is based on a well-known data structure in computer science: suffix tree (introduced in the 70's).

IBM scientists have developed a interactive graphical tool, which recently at TEDx São Paulo, Fernanda Viegas from IBM have lectured a great keynote about data visualization techniques, presenting the application of the wordTree technique. The tool is also available for public and for free use at the website ManyEyes.

But why did i developed one ?

One of the problems of ManyEyes is its forbidden use for commercial applications and based on what I've researched there is also a maximum limit of words supported by the tool. I've found other ones like the ManyEyes, but unfortunatelly was not open-source or not available for public.

Therefore, I decided to build my own implementation of concordance based on the suffix tree. Different from the ManyEyes tool, my goal is to create automatically word trees from statuses from the web microblog Twitter. I was inspired by the work done by the Vettalabs who have developed a wordTree for Twitter in Java.

Twitter has a powerful mechanism called Re-Tweet (RT) which can be used by users to repeat any tweet that was already posted by someone, in order to reinforce or support that tweet and spread to all your followers (Making a RT of a tweet you're announcing that tweet for more people in order to see it). The more the number of RT's , the more divulged that tweet had.

Thus, I've developed a simple system that monitors the Twitter in real-time, seeking for tweets that has keywords specified by the users. Furthermore, for each n tweets found, one new tree is created, which shows in a easy way what it has been discussed about that topic, i.e., related to that keyword.

Let's see an example: I've collected some tweets about the recently launched movie in the brazilian theaters: Robin Hood. The figure below illustrates the new word tree created:

WordTree related to the movie Robin Hood

As you can notice, the quantity of tweets processed can be huge - thousand of items in one day. So I decided to prune the tree in order to present only relevant information. For that, we can use some natural language processing techniques such as to choose only nodes that have verbs in the second node and a subject in the first node of the tree. This could simplify the tree and focusing on the texts that have a subject + verb in the beginning (action of the keyword), etc.

The tree presented above is a reverse tree, which shows the words that precede a keyword.(trees with higher depth). The other one is the basic tree where the keyword is the subject:

WordTree related to Brazil ( a mention to the Soccer World Cup)!

Both the suffix tree and the graph was developed using Python programming language. The most interesting part is that you can easily visualize/extract information in real-time on Twitter with this visualization tool. It also summarizes repeated words by increasing its font/letter size so the user can directly understand in a intuitive way, specially in a environment with lots of text and information.

I'd like to mention Murilo Queiroga who has given me some tips to this work. Thanks Murilo!

See you next time,

Marcel Caraciolo

Google launches their new Google Prediction API: the machine learning as cloud services!

Hi all,


I'd like to share some news that I saw yesterday about the launch of the new Google Prediction API. During the Google I/O anual event that have started yesterday, Google has released new web services including this new API.

So, What is the Google Prediction API ? The Prediction API enables access to Google's machine learning algorithms to analyze your historic data and predict likely future outcomes.  It makes possible for developers and researchers to upload their data to Google Storage for Developers (another service launched during the event), and with the Prediction API , it helps them to make real-time decisions such as recommending products, evaluating user sentiment from blogs or even tweets, routing messages or assessing suspicious activities. 

The Prediction API implements supervised learning algorithms as a RESTful web service to let you leverage patterns in your data, providing more relevant information to your users. Run your predictions on Google's infrastructure and scale effortlessly as your data grows in size and complexity.

A simple screenshot (extracted from the Google Prediction HomePage) shows the idea of the service. In this example, it assess the language of the text passed as parameter.

Google Prediction API Workflow

According to the official home page of the API,  it only implements supervised learning algorithms (no unsupervised like clustering algorithms) as a RESTful web service so you can run your predictions on Google's infrastructure and scale effortlessly as your data grows in size and complexity. 

They don't say about the specific algorithms they are using or how they select the one from several available machine learning techniques (I am very curious about it).  It supports almost the most used types of inputs: numeric or data or unstructured text. Their outputs can be hundreds of discrete categories (doesn't  work with continuous output). And the best it is accessible from many platforms like Google App Engine, web , desktop apps ( mobile apps are included?) and command line.

At least, Google introduced another tool for analyzing your data: BigQuery.  This API enables fast, interactive analysis over huge datasets (Imagine trillions of records). Using SQL-like commands via a RESTful API,  you can quickly explore and understand your massive data. It can help you, for example, analyze your network logs, identify seasonal sales trends, etc.

My opinion about this ? Google made a huge step forward to help the current applications in order to use their historical data for improving the usability, decisions and make money, of course! A new generation of applications using those techniques will appear in the next few years, using Natural Language Processing and Machine Learning for improving their services.  A lot of data is available for users and Google is helping them to analyze this data in order to quickly make decisions. With this  RESTful interface, even a young boy with some lines of code could develop a simple application to predict the weather in its city or a twitter-spam filter. Imagine the possibilities!  Now, you don't need to be under a lot of machine learning and statistics books in order to give intelligence to your application or analysis at your data.

It's the intelligence now injected in black boxes for anyone with basic knowledge of programming. Let's see what happens with this step. Anyway,  Google has made a step forward to the Cloud Data Analysis Computing (CDAC) ( I invented this name).

What do you think about it ? Let's wait for the next chapters!

Regards,

Marcel Caraciolo

Webservices and Robots: How can they help you ? Twitter Bots and Intelligent Agents

Hi folks,

During the free time (it doesn't happen often), I've worked on some projects including Twitter and Web Services. Those topics are extremely related to my current master thesis, which uses data source from social networks such as Twitter, Foursquare, Gowalla in order to monitor the behavior of the users and recommend new content, services or products based on their interest. Deliver this content means  the user receive information by web, mobile phones or through a specific interface.

One of my recent works is building Twitter robots. What's that ?!  WebServices that could be offered by the Twitter interface. For instance, imagine a service where you ask an information about a movie at Twitter through statuses updates, such as '@movieTheaters Iron man 2'.  The webservice receives this data (since you mentioned the @moviesTheaters) , parses, interpret it and as result deliver to the user the schedule of the theaters that play this movie close to the user's location or also the synopsis  of the movie, etc.

Why Twitter ?!  Twitter has been a sucessful player on this new generation of microblogs and social networks. Based on messages with 140 characters shared between users, nowadays the number of tweets (i.e. messages) have made nearly 13 billion. Yet, there's two unique things about the Twitter's content that makes it much valuable than any other public database of this size.

A Tweet has an author, a time and possibly hastags and @reply information that is all incredibly easy to access computationally. While web pages & blog posts also often have this information, it is much harder to access. For computers, there’s no simple way to respond to the author of most information on the web. Together these features lead to some very interesting possibilities for Twitter robots (bots).
 The structure of Twitter makes it relatively easy to extract the information contained in a Tweet- moreover, if it's a single question. ' Where can I find... ?' 'What's the best... ? ' , 'How much does ... cost'?  All those questions regularly appears in the Twitter stream. Building a Twitter bot that extract these Tweets & parses them for meaning within a specific field is extremely valuable. Thus, from the meta-data attached to a status update, a bot can easily answer to the author and reference the tweet is it replying too. The original author will pick up the response in their @replies or @directmessages (for privacy issues)  and see the link to the Tweet the response is to. Before presenting some examples, let's now talk about the robots. Its popular name is bots, which is an abbreviation for it.

Bots

Bots are intelligent agents that visit a number of search engines to identify information that matches a search profile provided by a user. There are a number of different kinds of bots designed to fulfil different purposes, such as software bots, stock bots, update bots, fun bots, chatter bots, and news bots. The possibilities for bots, specially on Twitter, is endless. Here I present two bots that I developed that demonstrate this concept.

TransitoRE

TransitoRe is a Twitter Bot that crawls the data provided from the many traffic cameras located along highways and streets throughout the city of Recife, Pernambuco - Brazil. The data is provided by the Recife Mayor Council and is updated every minute. Through the Twitter, the user now can obtain the real time traffic as also the location of the camera, since the Tweets come with the information about the traffic, name of the highway, images of the camera and even the geo coordinates where they are placed. It's a useful web service for the user that lives at Recife and wants to quickly gather information about the traffic in order to avoid this streets before going out. The service runs under the Google AppEngine and it'sa perfect example of how Twitter can help their users to obtain this information. The user just needs to follow the Twitter bot, and the  it will be responsible for post updates about the traffic in pre - defined intervals. It's important to notice that in this type of bot the user doesn't interact with it. It only delivers information, and is very popular in  deliver weather, stocks information.

TransitoRe : Twitter Bot

Tweetcomendas
 
This bot is another demonstration of a full operational bot that interacts with the user. Tweetcomendas was developed by me (marcelcaraciolo) and my friend (ricardocaspirro) and its design  by (lucianacns). It is a web service that runs through Twitter which the user can easily track his SEDEX shipments. SEDEX is a popular Express Courier Service, a division of Correios in Brazil. It is famous  for deliver all around Brazil  shipments and packages.

The difference of @tweetcomendas  to @transitoRE is that since the first uses direct messages, the user must follow it so it can send direct messages to him. The messages contain information from the web service at Correios, delivering the last status of the shipment at their system. The user just needs to send a reply to the system with the track code and it automatically starts to track his package by delivering real time information about it in accordance to the Correios Track System.  The bot now has a simply interaction with the user, demonstrating how this bots (robots) could deliver and talk with the user in order to deliver what he needs or based on his interests help him to discover new content.

Here are some screenshots of the web service:

Tweetcomendas bot

tweetcomendas web site

Those bots are all developed using free technologies with Python and Google App Engine. For you interested in get more details about those webservices and how we handled to develop it, post a comment at this blog! I will try to answer as soon as possible!

In conclusion, the possibilities for bots capitalising on this concept is endless. Bots that provide directions, restaurant or product recommendations, or weather information are just a few ideas. As Twitter grows the number of people a simple bot will reach continues to increase.

You can see a lot of other twitter bots here at this link. 

I expect you enjoyed this post!

See you next time,

Marcel Caraciolo

Mining data from Web 2.0 and Location Web Services for Services Recommendation and Products Offer via Mobile media

Hi all,

It has been a while since my last post, but I've returned.  During this period, I was working on master thesis project plan (and finally decided what I will research and work on) as also lecturing a Python training course for a company here at Recife - Brazil. In this post, I will talk more about what I'm planning to do at my master thesis and present some concepts related to Mobile Marketing, Web, Services, Social Media and Recommendation.

Web  2.0  and Location Web Services [ Photo from blog Arrobazona]

Here, I present a resume of my master degree plan.

With the advent of the latest Web 2.0 technologies [1] and social activities ocurring all over the world, more and more people are sharing information and building relationships. They're taking a important role in part of our lives as helping to answer critical questions such as 'what' , 'how', 'where', 'where', 'why' and 'who'.  However, regardless of these questions, one critical issue is how to give all those answers (information) effectively and recommend in a way that may interest people.

One of the possible targets for these activities are the mobile phones. They are a perfect recipient for fetching a variety of data from mobile information like location and ubiquitous content like small text messages, photos, etc. The new generation of multimedia mobile phone, like Iphone, has begun to integrate online web services and location data acquired from location providers such as  Global Positioning System (GPS) and mobile networks.  These new services formed a known and independent research area name as Location Based Services (LBS)[2] [3].  A perfect example of LBS is the Google Maps [4], which aims to help mobile users access to their destinations with real-time traffic information and road conditions. 

Futhermore, the  GPS software vendors, mobile operators and content providers have also gradually to try for the mobile terminal application development. With content created by combining GPS location-based services and latest Web 2.0 technologies (blogs, tagging, comments, social networks, etc.)  it would be possible to provide timely and personalized information and sharing services based on the user's location information. Or even more, use the content provided of the mobile user, to inform the vicinity of restaurants, entertainment and shopping information, etc.

If we look at the existing location-based services,  such as Foursquare [6], Yelp [7] , Gowalla [8] and others, its information is derived from a single content providers (such as map makers or service providers) so there are some relevant limitations [5].  Based on the traditional information retrieving, the location-based-services and companies are giving more emphasis on the dynamics of information and diversity more than the real-time and targeted content services.  Although, the  users want to be able to obtain contextual and identifying content, not just the indexed information based simply on a static database.  

Recently, those LBS services are looking to how to improve their systems by using some game components and   foucusing on the user experience and engagement with augmented-reality functionalities [9]. However, the rise of a large number of Web 2.0 applications (blogs, microblogs, Taggins, forums, Web albums, etc.) indicates that the users have the urgent requirements of direct, fast, useful and personalized information recommendation and sharing services.

So there is a big question here: How to efficiently combine new Web 2.0 applications (Twitter, Facebook, etc.) with location based services and apply to mobile phone ?  Since there are heterogeneous data and services in various formats and different application platforms, how to integrate all this data that can be used as platform-transparency specially for the user? And how to display all this information in a limited display screen of mobile devices, without prejudicing the usability and  the associated costs for the traffic data. Finally,  how to deploy a mobile discovery content  provider by identifying the user preferences and his location in a intelligent way ?

Those questions are doubtless part of a important research topic, and will have a very wide market prospect. Creating mobile advertisements to target a specific audience and a group of users is also one of the challenges in this area and in the Mobile Marketing research field.

Considering the previous statements, my proposal is to study the use of data mining techniques and recommendation engines in order to develop a  recommender system  integrated with Web technologies and location web services in the mobile enviroment. To solve that I will apply a variety of data analysis tools, algorithms to discover valid, novel, potentially useful and understandable patterns and relationships in data.  Design and implement a collaborative recommender algorithm that can analyze the user value-added data obtained from many Web 2.0 applications. Finally,  prototype a location-based data and service middleware based on web services protocols (SOA) to group all this heterogeneous data and services and publish them as one transparent-platform web service. Atacking those fields, I believe at the end of this project, to develop a real case demo and present a complete tool set for mobile data analysis.

That's all, There are many important topics to research and a lot of work to do. My aim is to build a recommender system for events/places/users using data from Twitter/Foursquare and Yelp and other possibility for recommend/offer products in ubiquitous enviroments with prices, items and shopping advertisements. I believe that there's a incredible and promising to research, specially with the  rise of new mobile social web services.

Best regards,

Marcel Caraciolo

References

[1] Tim O'Reilly (2005-09-30). "What Is Web 2.0". O'Reilly Network. 

 http://www.oreillynet.com/pub/a/oreilly/tim/news/2005/09/30/what-is-web-20.html.

[2]  Shiode, N., Li, C., Batty, M., Longley, P., & Maguire, D. The impact and penetration of  location-based services. In H. A. Karimi & A.  Hammad (Eds.), Telegeoinformatics:  location-based computing and services, 2004,  pp. 349–366, CRC Press.

[3] Jiang, B., Yao, X. B. Location-based services  and GIS in perspective. Computers, Environment and Urban Systems,Vol.30, No.6, 2006, pp. 712-725.

[4] Google.  Google Maps . At http://maps.google.com

[5] Li, C. User preferences, information transactions and location-based services: A  study of urban pedestrian way finding. Computers, Environment and Urban Systems, Vol.30, No. 6, 2004, pp.726–740.

[6] Foursquare.  Foursquare:. At http://www.foursquare.com

[7] Yelp.  Yelp:. At http://www.yelp.com

[8] Gowalla. Gowalla At http://www.gowalla.com

[9] Maria R. Ebling, Ramón Cáceres, "Gaming and Augmented Reality Come to Location-Based Services," IEEE Pervasive Computing, vol. 9, no. 1, pp. 5-6, Jan.-Mar. 2010.

Playing with the Twitter Data [Final]: Clustering/Grouping my friends with Python!

Hi all,

One of the problems I'm now facing with Twitter is how organize my friends (the users that i follow) in a way that I could easily read their posts based on similar interests or keywords. 

The idea is identify common groups of users and look at a segmentation based on user biography keywords. That biography information would allow us to segment Twitter users in groups of similar interests, professions and qualities.

I could do this manually checking each user and their last statuses and organize them in lists in accordance to their history data on Twitter. But for me, that I have more than 100 friends, it might be painful to check and place it one by one. 

So far we have seen various examples of using analytics to gain insights from Twitter. Using cluster analysis is one of my favorites.  By doing cluster analysis, it will be possible to reveal similar Twitter users and as result the possibility of creating Twitter Lists based on the groups generated by those clustering algorithms.  

Using text mining and some machine learning techniques, I'll present a simple tool to get all your Twitter Friends and organize them in lists segmented by the similar behavior. 

Step 1: Getting the Twitter User Data

In this part, i'll show the code written in Python for getting the Twitter User data. I used the python-twitter library with some custom modifications, allowing to download the Twitter user data and his last statuses/posts. In order to get my friends statuses, I've developed some functions and custom threads, accelerating the process of downloading the user profiles and dumping them into data files.

Take a look into the code provided in TwitterCollector.py. Due to rate limits (150 requests per hour) from Twitter, depending on how many friends you have, it will be not possible to fetch all of them. So for this article, i'll be using a subset of 100 friends randomly picked from my Twitter user profile ('marcelcaraciolo').  

The number of statuses selected will be up to the 200 last statuses from each user. I've chosen this number, because i thought it was a good number to summarize the user behavior on Twitter. But you can change this number if you desire, just be aware that the script may fail during the process because of the request limits for Twitter Web Service.

The Twitter Collector is really simple and effective. There is a pool of threads  (TwitterCollector) where each one grabs the statuses of the user, and then places it into a queue. This queue is repository for holding the statuses that will be parsed. The parsing involves the extraction of the words for what the user has written at his posts and remove the stop words (using some natural language techniques). Another pool of threads (TwitterMiner) joins on this queue, and is responsible for do the parsing work on the statuses. 

After the TwitterMiner finishes his job, it places it into another queue, where it will be dumped into a data file, in this case handled by the module 'pickle'. The module pickle is very efficient on storing and retrieving objects (serialization) into data files.

Step 2: Building the user profiles


Now let's start building the user profiles. In this step we'll build the user profile for each user fetched in the previous step. The user profile is summarized by the statuses collected, where for each user there's a table of word frequencies. This table will allow to check if there are groups of users that frequently write about similar subjects or write in similar styles (e.g. english or portuguese languages).

For instance, consider three users: me ('marcelcaraciolo') that writes more about python and data mining,  'symbian' writes more about  mobile and symbian stuff and the user 'parties' that write about beer and parties around the world. It will happen that after a clustering analysis it may be possible that me and symbian will be in the same group where 'parties' will be placed at another group due to the dissimilarity in behavior between us on Twitter.

The code provided on TwitterOrganizer.py will be responsible to open the data file with the statuses collected in the first step and build the user profiles by creating a table for each user with the word frequencies.

Step 3: Clustering Analysis

Now it's time to discover the groups of users that exhibit the same behavior. Until now i've presented some techniques for clustering analysis like Hierarchical clustering and MultiDimensional Scaling. But both of them have a couple of disadvantages specially on visualization and computational processing.  An alternative method of clustering is K-means clustering. The main difference from Hierarchical Clustering is the number of distinct clusters which is told in advance.  

Let's talk a little bit about  How does K-means work? 

The idea of K-means clustering is to determine the size of the clusters based on the structure of the data. It begins with k  randomly placed centroids (points in space that represent the center of the cluster), and assigns every item to the nearest one. After the assignment, the centroids are moved to the average location of all the nodes assigned to them, and the assignments are redone. Those steps repeats until the assignments stop changing.  The result is a set of clusters within the ranges of each of the variables.  The number of iterations it takes to produce the final result is quite small compared to hierarchical clustering.  It's important to notice that since the k-means uses random centroids to start with, the order of the results returned will be different most of the times. This happens because of the initial locations of the centroids. The same happens with the number of clusters (k) that may affect the results.

You can see more about k-means process here at this link.

I've run a couple of times the algorithm, and i selected one of the partitions generated by the k-means algorithm with the Twitter user profiles generated at the step 02. The k selected on this example is 15. For presenting the results, i've decided to make the things more interesting. I've used the ubigraph framework, a python library for displaying graphs and networks at 3D.  As you can see at the video below, the clusters are generated during the k-means process. Each node represents a Twitter user, and each cluster is differentiated from each other by the color. 

Grouping Twitter Users with Machine Learning Algorithms from marcel Caraciolo on Vimeo.

After running the graph, i've decided to play more with the Twitter data. In the end of the video playback, you can see that I'm clicking on some cluster centroids (represented by the non-labeled cubes). You can see that it shows the most frequently words that appears for each group. It's notable that they're are joined exactly because of the frequency of those words at their user profiles. It will be useful for the last step of this article: Creating the Twitter Lists.

Step 4: Creating the Twitter Lists

Now that i have my friends grouped by similar subjects posted on Twitter, it's time to make this data clustering useful. I've decided to create Twitter Lists, which is a new feature launched from Twitter recently. The idea is creating group of users whose the owner can follow and so other users if they are interested on the topics discussed on what the members of the list posted. It's a handful tool for organizing your friends in order to read their statuses based on what they post. For instance, my friends that talk about python i could group them altogether in a list with the name 'PythonUsers'.

Based on the clustering algorithm, i'll create the lists with members shown at each cluster. Since, the python-twitter library doesn't have at its last release support with Lists API. I've decided to create one on my own. The TwitterListAPI is a simple python wrapper for the Twitter API handling some operations with lists like: creating, updating and removing lists and adding/removing users from the list. You can check the implementation in the module twitterList.py.

You can run it after running the clustering algorithm. The methods readFile() and readFiles() are responsible for reading the files generated at the result of the last step. They contain the name of the new list that you want create, as also the description of the list, which is optional and at least the ids of the user that you would like to add to the list. If you don't have the userID, don't worry you can use the method GetUserID() to get this information for each username. You may also want edit those files at your preference in order to remove or add users, edit the list name or description.

I've run with my twitter friends, and you can see at the figure below one of the lists created after the clustering algorithm.

Conclusion

So, this is my initial attempt in order to manage my Twitter Friends and also playing with Twitter Data by clustering the users based on their statuses. It uses a initial study of text mining and a machine learning technique called K-means, clustering algorithm, for group the user profiles, in this case summarized by user statuses and word frequencies. I believe there's more work to do, specially about running other clustering algorithms and distance metrics to compare the results. I think that the K (number of the clusters) should be found automatically in a way to balance the trade-off: The number of lists x the number of friends. A lot of friends with many non-related topics in a same group could not be  useful as lists with a few members it's not necessary. The best value for 'k' is a subject for future studies. Other good result of this work is the use of 3D techniques to show the clustering process and also the new API for handling with Twitter Lists.  At least, the pre-processing of the statuses will be expanded in order to improve the identification of the topics and reduce the number of topics - variables (dimensionality), a issue for machine learning techniques due to heavy processing and time costing.

You can download all the code used at this article here. 

That's all,

Special thanks for Luciana Nunes and Ricardo Caspirro for the support during this work!

Marcel Pinheiro Caraciolo