Providing Recommendations in Social Networks using Python: AtePassar Study Case

Hi all,

Recently I've been working on recommendations, specially related to social networks. One of my tasks is to investigate, create and analyze a recommendation engine capable of generating suggestions of friends,  study groups, videos and related content to a registered user in a social network.

The social network that I am working on is called AtePassar, a brazilian social network for people who wants apply for positions at brazilian civil (government) services.  One of the great features of this social network is because people can share their interests about studies and meet people all around Brazil with same interests or someone that will apply for the same exam as him.  Can you imagine the possibilities ?

It is a social network for students into a virtual space where there are several relations of friendship, studies and even exam partners.

AtePassar Social Network

Since we believe in interaction between people and discovering of relevant content a real need for users inside a social network, specially finding tasted-like users which indicate the similarity of their needs and opinions,  we decided to build a recommender system capable of recommending new users based on similar interests such as common friends,  common videos both have watched or study groups where both have joined in, etc.   We  also have developed a study group recommender, which suggests relevant  study groups based on the friends' study groups that they are participating and the active user is not.  Finally, we also have developed a video recommender,  providing suggestions for classes (on-line video classes) relevant for the users based on what his friends has already watched.

As you may have noticed that we focus on more in the collaborative filtering process, where we are more interested on finding similar users and bring unknown items closer to the active user's historical preferences  as possible recommendations.

Recommendations SideBar

One of our priorities in this recommendation process is to always explain to the users the reason of the recommendation is presented to them.  We believe it is really important for the user to know the relevance of the recommendation and even for us to improve the level of acceptance of the recommendation.  If you receive a recommendation and that recommendation is joined with extra information that 4 friends of you also liked that item, it can be more meaningful than only receiving the recommendation without knowing the reasons.

Another priority for us is to provide recommendation to all users, even new users who has started using the AtePassar network and don't have sufficient information in his profile (friends, studygroups, etc) to bring relevant recommendation. I've developed a simple algorithm that it is a solution for this common problem in recommendations called 'cold start'.  Cold Start happens specially for new users, where there is not enough user and item information and therefore it's hard for the recommendation system to produce recommendations. We decided to bring the most accepted recommendations from users in our social network (the most popular) and populate them as possible suggestions for new users.  We know this is not the best solution, because it is not personalized, but it can bring recommendations out-of-the box in cases where we are newbies in the social network.

We are doing a poll to know from Atepassar users to know more about whether they are liking the suggestions our system is providing.  More than 60% of the ones who have answered the poll said that they like most of suggestions provided.  We are working harder to even improve this recommendation process bringing more content to be recommended and the utility by considering extra information in the user's profile.

Here a brief introduction (video) to the social recommender engine running at AtePassar Social Network.





In the next posts I will bring more information in a detailed view of development and explain more about recommender engines, the area I am working on also in my master thesis. I've been using also a open-source recommendation engine in this work, it is beginning but we are improving in small steps bringing new releases every month.   Until now, our framework called Crab is only working for Collaborative-filtering  recommendations (written in Python) and we are planning for the next releases bring Content-based ones and distributed algorithms  using map-reduce features, etc.

If you want to take a look at our recommendation engine, please check it out here in this link (It is hosted in my personal GitHub repository).  In a previous post in my blog I introduced the framework and I am planning to write a series of posts to deep into recommendation engines, explaining on how to use it, evaluations, etc.

I also wrote an introduction for recommendation engines if you're starting now in this machine learning field. You can check it out here.

I hope you enjoyed,

Marcel Caraciolo

MapReduce with MongoDB and Python

Hi all,

 In this post, I'll present a demonstration of a map-reduce example with MongoDB and server side JavaScript.  Based on the fact that I've been working  with this technology recently, I thought it would be useful to present here a simple example of  how it works and how to integrate with Python.

But What is MongoDb ?

For you, who doesn't know what is and the basics of how to use MongoDB, it is important to explain a little bit about the No-SQL movement. Currently, there are several databases that break with the requirements present in the traditional relational database systems. I present as follows the main keypoints shown at several No-SQL databases:

• SQL commands are not used as query API (Examples of APIs used include JSON, BSON, etc.)
• Doesn't guarantee atomic operations.
• Distributed and horizontally scalable.
• It doesn't have to predefine schemas. (Non-Schema)
• Non-tabular data storing (eg; key-value, object, graphs, etc).

Although it is not so obvious, No-SQL is an abbreviation  to Not Only SQL. The effort and development of this new approach have been doing a lot of noise since 2009. You can find more information about it here and here.  It is important to notice that the non-relational databases does not represent a complete replacement for relational databases. It is necessary to know the pros and cons of each approach and decide the most appropriate for your needs in the scenario that you're facing.

MongoDB is one of the most popular No-SQL today and what this article will focus on. It is a schemaless, document oriented, high performance, scalable database  that uses the key-values concepts to store documents as JSON structured documents. It also includes some relational database features such as indexing models and dynamic queries. It is used today in production in over than 40 websites, including web services such as SourceForge, GitHub, Eletronic Arts and The New York Times..

One of the best functionalities that I like in MongoDb is the Map-Reduce. In the next section I will explain  how it works illustrated with a simple example using MongoDb and Python.

If you want to install MongoDb or get more information, you can download it here and read a nice tutorial here.

Map- Reduce 

MapReduce is a programming model for processing and generating large data sets. It is a framework introduced by Google for support parallel computations large data sets spread over clusters of computers.  Now MapReduce is considered a popular model in distributed computing, inspired by the functions map and reduce commonly used in functional programming.  It can be considered  'Data-Oriented' which process data in two primary steps: Map and Reduce.  On top of that, the query is now executed on simultaneous data sources. The process of mapping the request of the input reader to the data set is called 'Map', and the process of aggregation of the intermediate results from the mapping function in a consolidated result is called 'Reduce'.  The paper about the MapReduce with more details it can be read here.

Today there are several implementations of MapReduce such as Hadoop, Disco, Skynet, etc. The most famous is Hadoop and is implemented in Java as an open-source project.  In MongoDB there is also a similar implementation in spirit like Hadoop with all input coming from a collection and output going to a collection. For a practical definition, Map-Reduce in MongoDB is useful for batch manipulation of data and aggregation operations.  In real case scenarios, in a situation where  you would have used GROUP BY in SQL,  map/reduce is the equivalent tool in MongoDB.

Now thtat we have introduced Map-Reduce, let's see how access the MongoDB by Python.

PyMongo

PyMongo is a Python distribution containing tools for working with MongoDB, and is the recommended way to work with MongoDB from Python. It's easy to install and to use. See here how to install  and use it.

Map-Reduce in Action

Now let's see Map-Reduce in action. For demonstrate the map-reduce I've decided to used of the classical problems solved using it: Word Frequency count across a series of documents. It's a simple problem and is suited to being solved by a map-reduce query.

I've decided to use two samples for this task. The first one is a list of simple sentences to illustrate how the map reduce works.  The second one is the 2009 Obama's Speech at his election for president. It will be used to show a real example illustrated by the code.

Let's consider the diagram below in order to help demonstrate how the map-reduce could be distributed. It shows four sentences that are split  in words and grouped by the function map and after reduced independently (aggregation)  by the function reduce. This is interesting as it means our query can be distributed into separate nodes (computers), resulting in faster processing in word count frequency runtime. It's also important to notice the example below shows a balanced tree, but it could be unbalanced or even show some redundancy.

Map-Reduce Distribution

Some notes you need to know before developing your map and reduce functions:

•  The MapReduce engine may invoke reduce functions iteratively; thus; these functions must be idempotent. That is, the following must hold for your reduce function:

                 for all k,vals : reduce( k, [reduce(k,vals)] ) == reduce(k,vals)

•  Currently, the return value from a reduce function cannot be an array (it's typically an object or a number)
• If you need to perform an operation only once, use a finalize function.

 Let's go now to the code. For this task, I'll use the Pymongo framework, which has support for Map/Reduce. As I said earlier, the input text will be the Obama's speech, which has by the way many repeated words. Take a look at the tags cloud (cloud of words which each word fontsize is evaluated based on its frequency) of Obama's Speech.

Obama's Speech in 2009

For writing our map and reduce functions, MongoDB allows clients to send JavaScript map and reduce implementations that will get evaluated and run on the server. Here is our map function.

wordMap.js

As you can see the 'this' variable refers to the context from which the function is called. That is, MongoDB will call the map function on each document in the collection we are querying, and it will be pointing to document where it will have the access the key of a document such as 'text', by calling this.text.  The map function doesn't return a list, instead it calls an emit function which it expects to be defined. This parameters of this function (key, value) will be grouped with others  intermediate results from another map evaluations that have the same key (key, [value1, value2]) and passed to the function reduce that we will define now.

wordReduce.js

The reduce function must reduce a list of a chosen type to a single value of that same type; it must be transitive so it doesn't matter how the mapped items are grouped.

Now let's code our word count example using the Pymongo client and passing the map/reduce functions to the server.

mapReduce.py

Let's see the result now:

And it works! :D

With Map-Reduce function the word frequency count is extremely efficient and even performs better in a distributed environment. With this brief experiment we  can see the potential of map-reduce model for distributed computing, specially on large data sets.

All code used in this article can be download here.

My next posts will be about  performance evaluation on machine learning techniques.  Wait for news!

Marcel Caraciolo

References

• http://nosql.mypopescu.com/post/394779847/mongodb-tutorial-mapreduce
• http://fredzvt.wordpress.com/2010/04/24/no-sql-mongodb-from-introduction-to-high-level-usage-in-csharp-with-norm/