## Sunday, October 28, 2012

Hi all,

In this post I will present one of the tecnhiques used at Atépassar, a brazilian social network that help students around Brazil in order to pass the exams for a civil job, our recommender system.

I will describe some of the data models that we use and discuss our approach to algorithmic innovation that combines offline machine learning with online testing.  For this task we use distributed computing since we deal with over with 140 thousand users. MapReduce is a powerful technique and we use it by writting in python code with the framework MrJob.  I recommend you to read further about it at my last post here.

One of our recommender techniques is the simple 'people you might know' recommender algorithm.  Indeed, there are several components behind the algorithm since at Atépassar, users can follow other people  as also be followed by other people.  In this post I will talk about the basic idea of the algorithm which can be derivated for those other components.  The idea of the algorithm is that if person A and person B do know each other but they have a lot of mutual friends, then the system should recommend that they connect with each other.

 Person A and Person B has common friends, it should recommend each other

We will implement this algorithm using the MapReduce architecture in order to use Hadoop,  which is a open source software for highly reliable, scalable distributed computing.  I assume that you already familiar with those concepts, if not please take a look at those posts and see what map and reduce jobs are.

But before introducing the algoritm, let's present a simple algorithm in case of the bi-directional connections, that is, if I am your friend, you are also my friend. In order to recommend such friends, we first need to count the number of mutual friends that each pair of users have in the network. For this, we will need to implement a map reduce job that works similar to  the job that count the frequency of words in a file.  For every pair of friends in a list, we output the tuple {friend1, friend2}, 1:

In addition to this, we also output a tuple with -1 for every pair of users who are friends {user_id, friend}, -1.

Now, the reducer gets a input key denoting a pair of friends along with their list of their number of common friends.

In the reduce function, we can check if the first record has a -1 in the value. If there is such a reccord, we can ignore that pair of friends, because they already have a direct connection between them. Finally we aggregate the values of all the keys in the reducer and output the tuple for all the pair of friends which don't have third attribute as -1 in the key.

After the first map-reduce job, we obtain a list of pair of persons along the number of common friends that they have. Our final map-reduce job looks at this list {[friend1, friend2], numberOfMutualFriends} and outputs a list of persons they have maximum number of common friends with. Our map job outputs {friend1,[numberOfMutualFriends, friend2]}, {friend2,  [numberOfMutualFriends, friend1]}  .

The reducer would look at the person in the key and our comparator would look at the numberOfCommonFriends to sort the keys. This would ensure that the tuples for the same person go on the same reducer and in a sorted order by the number of common friends. Our reducer then just need to look at the top 5 values and output the list (TOP_N).

Now, we run through our social network data.

marcel;jonas,maria,jose,amanda
maria;carol,fabiola,amanda,marcel
amanda;paula,patricia,maria,marcel
carol;maria,jose,patricia
fabiola;maria
paula;fabio,amanda
patricia;amanda,carol
jose;marcel,carol
jonas;marcel,fabio
fabio;jonas,paula
carla

Let's see some interesting stuff. The recommended friends to me are:

"marcel" [["carol", 2], ["fabio", 1], ["fabiola", 1], ["patricia", 1], ["paula", 1]]
"maria" [["jose", 2], ["patricia", 2], ["jonas", 1], ["paula", 1]]
"patricia" [["maria", 2], ["jose", 1], ["marcel", 1], ["paula", 1]]
"paula" [["jonas", 1], ["marcel", 1], ["maria", 1], ["patricia", 1]]
"amanda" [["carol", 2], ["fabio", 1], ["fabiola", 1], ["jonas", 1], ["jose", 1]]
"carol" [["amanda", 2], ["marcel", 2], ["fabiola", 1]]
"fabio" [["amanda", 1], ["marcel", 1]]
"fabiola" [["amanda", 1], ["carol", 1], ["marcel", 1]]
"jonas" [["amanda", 1], ["jose", 1], ["maria", 1], ["paula", 1]]
"jose" [["maria", 2], ["amanda", 1], ["jonas", 1], ["patricia", 1]]

As I expected the person with most common friends to me is carol, with maria and jose.

There are  still plenty of things that can be done here in the implementation in order to have our final recommender, for example here we are not considering the followers in common or whether if we live at the same state.  Even the results and scalability can be improved.

And what about recommending friends from Facebook?  I decided to mine some data based on connections between my connections.

\$python  friends_recommender.py - r emr --num-ec2-instances 5  facebook_data.csv > output.dat

Let's see some results:

Let's pick my friend Rafael Carício. The top suggestions for him would be:

"Rafael_Caricio_584129827" [["Alex_Sandro_Gomes_625299988", 28], ["Oportunidadetirecife_Otir_100002020544265", 26], ["Thiago_Diniz_784848380", 20], ["Guilherme_Barreto_735956697", 18], ["Andre_Ferraz_100001464967635", 17], ["Sofia_Galvao_Lima_1527232153", 16], ["Edmilson_Rodrigues_1003183323", 15], ["Pericles_Miranda_100001613052998", 14], ["Andre_Santos_100002368908054", 14], ["Edemilson_Dantas_100000732193812", 13]]
Rafael is my old partner and studied with me at UFPE (University). All recommended are entrepreneurs or old students from CIN/UFPE.

And about my colleague Osvaldo Santana, one of the most famous python developers in Brazil.

"Osvaldo_Santana_Neto_649598880" [["Hugo_Lopes_Tavares_100000635436030", 14], ["Francisco_Souza_100000560629656", 12], ["Daker_Fernandes_Pinheiro_100000315704652", 8], ["Flavio_Ribeiro_100000349831236", 6], ["Jinmi_Lee_1260075333", 5], ["Alex_Sandro_Gomes_625299988", 5], ["Romulo_Jales_100001734547813", 5], ["Felipe_Andrade_750803015", 5], ["Adones_Cunha_707904846", 5], ["Flavio_Junior_100000544023443", 4]]

Interesting! Recommended other Python Developers as also some entrepreneurs! :)

We could play more with it, but if you want to test with your own data download it by using this app.

Great, but how can I use this algorithm in Twitter for example ?! It's a little different. In this scenario we don't assume the bi-directional link. Only because I follow you on Twitter it does not mean that you also follow me. We have now two entities: followers and the friends.

The basic idea is to count the number of directed paths. See the full code below:
Let's see how I can get some new friends to recommend based on the list of users that posts about #recsys that I created.

Running over twitter and that is:

"@marcelcaraciolo" [["@alansaid"  24],   ["@zennogantner"  21], ["@neal_lathia"  21] ]

Great I didn't know! :D I liked the recommendations. By the way they are great references in recsys.  But let's go further...  Let's check the explanations?  Why those users are recommended to me ?  It is an important feature for improving the acceptance of the given recommendation.

Making some changes at my code,  it gives us the output below:

"@marcelcaraciolo" [["@alansaid"  24, ["@pankaj", "@recsyschallenge", "@kdnuggets",
"@mitultiwari", "@sidooms", "@recsys2012", "@khmcnally", "@McWillemsem", "@LensKitRS",
"@totopampin",  "@recsyshackday", "@plamere", "@usabart", "@mymedialite', "@reclabs",
"@elehack","@omdb", "@osbourke", "@siah"]],    ["@zenogantner"  21, ["@sandrewge",
"@nokiabetalabs", "@foursquareAPI",  "@mitultiwari", "@kiwitobes", "@directededge",
"@plista", "@twitterapi", "@recsys2012",  "@xamat", "@tlalek", "@namp",
"@totopampin", "@ushahidi",  "@kaythaney", "@gj_uk", "@hmason",
"@jure", "@ahousley", "@peteskomoroch",  "@xamat", "@tnhh", "@elizabethmdaly",
"@recsys2012",  "@sandrewge", "@matboehmer",  "@abellogin", "@pankaj', "@jerepick",  "@alsothings","@edchi", "@zenogantner"]]

Recommendations with explanations and also distributed :D

Atépassar Extension

Ok, I haven't talked yet about Atépassar. How we recommend new friends at Atepassar ?  Atepassar is designed as Twitter, so we also have the entities friends and followers. Besides the common friends we add other attributes in the final score. For instance let's consider now the state where each user lives informed by his user profile at Atepassar. The idea is to recommend people with mutual friends and also weighted by people who lives at the same state.  For the purpose of illustration, let's start with a simple scoring approach by choosing our function to be a linear combination of state and mutual friends similarity. This gives an equation of the form
fsim(u,i) = w1 f1(u,i) + w2 f2(u,i) + b,

where u = user, i = the new friend, f1 = the friendship similarity and f2 = the state similarity.  This equation defines a two-dimensional space like the one illustrated below:

This is a sample of the my input:

murilodumps;SC;marcoscampelo
dan_sampaio;RJ
hugofsantiago;PE;daianefarias
kauanny;PE
Dayanne_F;PE;jwalker
guilhermepaiva;PE;marvinslap;jwalker;veronicacordeiro
italo;PE;marcoscampelo;jwalker;romero_britto;Syl;mariana_mbs
maria;PE

And the output sample:

"marcelcaraciolo" [["Gileno", 0.44411764705882351], ["raphaelalex", 0.43999999999999995], ["marcossouza", 0.43611111111111112], ["roberta_gama", 0.42352941176470588], ["anagloriaflor", 0.40937499999999999], ["rodrigo3n", 0.40769230769230769], ["alissonpontes", 0.40459770114942528], ["andreza_cristina", 0.40370370370370368], ["naevio", 0.40370370370370368], ["adonescunha", 0.40327868852459015]]

Interesting among the top  10,  5 worked with me at Atepassar (it means lots of common friends).  Let's see the code:

Conclusions

That's a simple algorithm used at Atépassar for recommending friends using some basic graph analysis concepts.  You can extend this code or use it for free at your social network! Go ahead :)   In the next post I will present the map-reduce jobs for course recommendation analysis at PyCursos.

Best regards,
Marcel Caraciolo

1. http://www.blogger.com/comment.g?blogID=13674163&postID=1391385784776498111&page=1&token=1361351179324

2. Great Content.I have appreciate with getting lot of good and reliable information with your post.......
Thanks for sharing such kind of nice and wonderful information......again, beautiful :) I love reading your posts. They make me happy .

3. I like totally and agree. And I think that in order to be comfortable with your style is to wear it more often. So wear your style to the lab on days that you don't have to do anything bloody, muddy or otherwise gross!

4. Welcome to Wiztech Automation - Embedded System Training in Chennai. We have knowledgeable Team for Embedded Courses handling and we also are after Job Placements offer provide once your Successful Completion of Course. We are Providing on Microcontrollers such as 8051, PIC, AVR, ARM7, ARM9, ARM11 and RTOS. Free Accommodation, Individual Focus, Best Lab facilities, 100% Practical Training and Job opportunities.

Embedded System Training in chennai
Embedded System Training Institute in chennai
Embedded Training in chennai
Embedded Course in chennai
Best Embedded System Training in chennai
Best Embedded System Training Institute in chennai
Best Embedded System Training Institutes in chennai
Embedded Training Institute in chennai
Embedded System Course in chennai
Best Embedded System Training in chennai

5. WIZTECH Automation, Anna Nagar, Chennai, has earned reputation offering the best automation training in Chennai in the field of industrial automation. Flexible timings, hands-on-experience, 100% practical. The candidates are given enhanced job oriented practical training in all major brands of PLCs (AB, Keyence, ABB, GE-FANUC, OMRON, DELTA, SIEMENS, MITSUBISHI, SCHNEIDER, and MESSUNG)

PLC training in chennai
Automation training in chennai
Best plc training in chennai
Process automation training in chennai
Final year eee projects in chennai
VLSI training in chennai

6. Embedded system training: Wiztech Automation Provides Excellent training in embedded system training in Chennai - IEEE Projects - Mechanical projects in Chennai. Wiztech provide 100% practical training, Individual focus, Free Accommodation, Placement for top companies. The study also includes standard microcontrollers such as Intel 8051, PIC, AVR, ARM, ARMCotex, Arduino, etc.

Embedded system training in chennai
Embedded Course training in chennai
Matlab training in chennai
Android training in chennai
LabVIEW training in chennai
Robotics training in chennai
Oracle training in chennai
Final year projects in chennai
Mechanical projects in chennai
ece projects in chennai

7. Wiztech Automation is the Leading Best quality PLC, Scada, DCS, Embedded, VLSI, PLC Automation Training Centre in Chennai. Wiztech’s Industrial PLC Training and the R & D Lab are fully equipped to provide through conceptual and practical knowledge aspects with hands on experience to its students.

PLC training in Chennai
PLC training institute in Chennai
PLC training centre in Chennai
Automation training in Chennai
DCS training in Chennai

8. Shree Ram Techno Solutions Provides CCTV Camera, Security Camera, Wireless Security, Attendance System, Access Control System, DVR, NVR, Spy Camera, Fire Alarm, Security Alarm, PCI, IP Network Camera, Dome Camera, IR Camera, CCTV, Camera Price, HIKVISION, SCATI, Time Machine

CCTV CAmera in jaipur at Rajasthan
Home security system in jaipur
Wireless Home Security System in jaipur
Realtime attendance machine in jaipur
cctv camera dealer in jaipur
Hikvision DVR in jaipur at Rajasthan
security system solutions in jaipur

9. Thanks to shared nice information with us, Its really useful stuff for us. keep sharing, We develop professionals for multiple streams through detailed and systematic training. Our approach instills a passionate training , making them ready to contribute to the ever-changing industries.
Hotel management colleges in Chennai

10. Hey, nice site you have here! Keep up the excellent work!

Best Bridal Makeup Artist in Chennai

11. Best Article, Great Programming Tips which helps lot to analyze the studies.. Bridal Makeup Artist in Bangalore, Bridal Makeup Artist in Chennai

12. Wiztech Automation- the front line training institute - is one of the best coaching centres for the students of engineering and also the qualified and employed engineers in Industrial Automation. Training is offered for all the automation based domains – PLC range of automations systems, Embedded and VLSI systems, apart from IT and Software, Mechanical designing, Web designing, SEO, etc. Wiztech has earned a name of repute in providing training and project services. It has been possible for Wiztech to enjoy the niche status since the company has the right infrastructure and facilities apart from qualified and experienced faculty members in the institute.
PLC training in Cochin, Kerala
Automation training in Cochin, Kerala
Embedded System training in Cochin, Kerala
VLSI training in Cochin, Kerala
PLC training institute in Cochin, Kerala
Embedded training in Cochin, Kerala
Best plc training in Cochin, Kerala

13. Really its very useful information that you have shared and thanks for sharing the information with us.

Best Bridal Makeup Artist in Madurai

14. Thank you for sharing valuable information’s like this post
Best bridal makeup in Chennai

15. The information which you have provided is very good. It is very useful who is looking for
Java online training Bangalore

16. Hadoop concepts, Applying modelling through R programming using Machine learning algorithms and illustrate impeccable Data Visualization by leveraging on 'R' capabilities.With companies across industries striving to bring their research and analysis (R&A) departments up to speed, the demand for qualified data scientists is rising.
data science training in bangalore

17. myTectra offers Big Data and Hadoop training in Bangalore using Class Room.
myTectra offers Live Online Big Data and Hadoop training Globally.
Big Data and Hadoop training Unlike traditional systems, Big Data and Hadoop enables multiple types of analytic workloads to run on the same data, at the same time, at massive scale on industry-standard hardware.myTectra Big Data and Hadoop training is designed to help you become a expert Hadoop developer. myTectra offers Big Data Hadoop Training in Bangalore using Class Room. myTectra offers Live Online Big Data and Hadoop training Globally.

18. Python has adopted as a language of choice for almost all the domain in IT including the most trending technologies such as Artificial Intelligence, Machine Learning, Data Science, Internet of Things (IoT), Cloud Computing technologies such as AWS, OpenStack, VMware, Google Cloud, etc.., Big Data Analytics, DevOps and Python is prepared language in traditional IT domain such as Web Application Development, Infrastructure Automation ,Software Testing, Mobile Testing.

python online training

python certification

20. Great post and informative blog.it was awesome to read, thanks for sharing this great content to my vision.
Good discussion.
PMP Training Course in Bangalore
PMP Training Course in Dammam
PMP Training Course in Dubai
PMP Training Course in Jeddah

21. Great Article… I love to read your articles because your writing style is too good, its is very very helpful for all of us. Do check Six Sigma Training in Bangalore | Six Sigma Training in Dubai & Get trained by an expert who will enrich you with the latest trends.