Recommendation System

from math import sqrt
def euclid(prefer,person1,person2):
s=0
flag=0
for p in prefer[person1]:
if p in prefer[person2]:
flag=1
s=s+pow((prefer[person1][p]-prefer[person2][p]),2)
if flag==0:
return 0
return 1/(1+s)
def pearson(prefer,person1,person2):
s={}
for p in prefer[person1]:
if p in prefer[person2]:
s[p]=1
if len(s)==0:
return 0
n=len(s)
sum1=sum(prefer[person1][p] for p in s)
sum2=sum(prefer[person2][p] for p in s)
sq1=sum(pow(prefer[person1][p],2) for p in s)
sq2=sum(pow(prefer[person2][p],2) for p in s)
ps=sum(prefer[person1][p]*prefer[person2][p] for p in s)
num=ps-(sum1*sum2/n)
den=sqrt((sq1-pow(sum1,2)/n)*(sq2-pow(sum2,2)/n))
if den==0:
return 0
return num/den

def ranking(prefer,person1,n,pe=pearson):
rank=[( pe(prefer,person1,other),other) for other in prefer if other != person1 ]
rank.sort()
rank.reverse()
return rank[0:n]
def getRecommendations(prefs,person,similarity=pearson):
totals={}
simSums={}
for other in prefs:
if other==person: continue
sim=similarity(prefs,person,other)
if sim<=0: continue
for item in prefs[other]:
if item not in prefs[person] or prefs[person][item]==0:
totals.setdefault(item,0)
totals[item]+=prefs[other][item]*sim
simSums.setdefault(item,0)
simSums[item]+=sim
rankings=[(total/simSums[item],item) for item,total in totals.items( )]
rankings.sort( )
rankings.reverse( )
return rankings
def loadMovieLens(path=’/home/prashant/Downloads/ml-100k’):
movies={}
for line in open(path+’/u.item’):
(id,title)=line.split(‘|’)[0:2]
movies[id]=title
prefs={}
for line in open(path+’/u.data’):
(user,movieid,rating,ts)=line.split(‘\t’)
prefs.setdefault(user,{})
prefs[user][movies[movieid]]=float(rating)
return prefs
prefs=loadMovieLens()
critics={‘Lisa Rose’: {‘Lady in the Water’: 2.5, ‘Snakes on a Plane’: 3.5,’Just My Luck’: 3.0, ‘Superman Returns’: 3.5, ‘You, Me and Dupree’: 2.5,
‘The Night Listener’: 3.0},
‘Gene Seymour’: {‘Lady in the Water’: 3.0, ‘Snakes on a Plane’: 3.5,’Just My Luck’: 1.5, ‘Superman Returns’: 5.0, ‘The Night Listener’: 3.0,
‘You, Me and Dupree’: 3.5},
‘Michael Phillips’: {‘Lady in the Water’: 2.5, ‘Snakes on a Plane’: 3.0,’Superman Returns’: 3.5, ‘The Night Listener’: 4.0},
‘Claudia Puig’: {‘Snakes on a Plane’: 3.5, ‘Just My Luck’: 3.0,’The Night Listener’: 4.5, ‘Superman Returns’: 4.0,’You, Me and Dupree’: 2.5},
‘Mick LaSalle’: {‘Lady in the Water’: 3.0, ‘Snakes on a Plane’: 4.0,’Just My Luck’: 2.0, ‘Superman Returns’: 3.0, ‘The Night Listener’: 3.0,’You, Me and Dupree’: 2.0},
‘Jack Matthews’: {‘Lady in the Water’: 3.0, ‘Snakes on a Plane’: 4.0,’The Night Listener’: 3.0, ‘Superman Returns’: 5.0, ‘You, Me and Dupree’: 3.5},
‘Toby’: {‘Snakes on a Plane’:4.5,’You, Me and Dupree’:1.0,’Superman Returns’:4.0}}
print “Printing Similiarilty between Lisa and Gene using Euclid Method”, euclid(critics,’Lisa Rose’,’Gene Seymour’)
print “Printing Similiarilty between Lisa and Gene using Pearson Method”, pearson(critics,’Lisa Rose’,’Gene Seymour’)

print “Printing Top Three user similiar to Toby “,ranking(critics,’Toby’,3)
print “Getting Recommendation for Toby “, getRecommendations(critics,’Toby’)
print “Movies  “, getRecommendations(prefs,’87’)[0:20]
print “Printing Top Three user similiar to Toby “,ranking(critics,’Toby’,3)

print “Movies  “, getRecommendations(prefs,’87’)[0:20] #Applying above algorithm on large data set

http://1drv.ms/1aWoPa4 #data for movie set function

Advertisements

nCr mod MOD (Lucas Theorem)

Hello folks, problem that i am gonna discuss is one of the standard problem that we very usually see in contest and it is as follow. You are given certain combinatoric problem which finally ends up with answer n Cr (n choose r),adding to the constraint since value of n Cr can be very large then you are asked to take modulus of the answer.

Solution to above problem : there are two case, first case when MOD is prime and case two when MOD is not prime, in this post i will be sharing answer to when MOD is prime. To solve above problem we use Lucas Theorem which states as follow.

LUCAS THEOREM

If MOD is a prime number, and N has base MOD representation (aj,…,a1,a0) and r has base MOD representation (bj,…,b1,b0), then (N CHOOSE R) is congruent [mod MOD] to

(N choose R) modulus MOD = ((aj CHOOSE bj)…(a1 CHOOSE b1) (a0 CHOOSE b0)) modulus MOD

Let me make it more clear with example, for instance  you have answer as (588 choose 277) % 5, then

     (588 choose 277) % 5 = ?
    Representation of 588 in base of 5 = 4323

    Representation of 277 in base of 5 = 2102

    Now your answer reduces to = ((4 choose 2)(3 choose 1)(2 choose 0)(3choose 2)) % 5
                               = (6 * 3 * 1 * 3) % 5
                               = 54 % 5
                               = 4

Important tip to calculate (aj choose bj) you can pre compute factorial upto MOD-1 and store that in array and hence you can compute (aj choose bj) in O(1) time.

Important observation : their might be certain cases when (aj < bj) in that case simply return 0 as your answer, why ? left for you geek 😛

One of the limitation of this theorem is, it works fine when the value of MOD is small if value of MOD is itself large then it become difficult to store factorial of values upto MOD-1.

How Microsoft has impacted your life and how you plan to bring a change to the society being a Microsoft Student Associate?

Hello!! everyone, well this is my first blog, care has been take to avoid error please suggest if any, which might have crept into, i am from NIT Surat 3rd year computer engineering guy.I am writing this blog as the first step of selection process of MSA -“Tell Your Story”.

In this blog i will be making clear how Microsoft impacted my life and how I plan to bring a change to the society being a Microsoft Student Associate.

From the very first day i started using computer it was windows ,the ubiquitous OS which assisted me in utilizing all the resources of my machine. As a student for every need – be it making presentation, developing software , making notes ,making school project its was always indeed Windows .Microsoft has really affected our live intensely and had delivered lot of services to us .It would be a nightmare realizing our life without Microsoft . Microsoft has delivered its one of the best Widows 8 Operating system to the users with many boosting features. Microsoft doesn’t stops only with  Operating System, it provides many other products like Tablet PC’s, Surface Pro, Xbox one, Skype, Skydrive, developers tools and more . Microsoft even entered into the world of mobiles by purchasing the tech giant Nokia . Microsoft feats doesn’t ends  here its world class search engine Bing provides result no less than Google.

Microsoft has always provided educational opportunities via Microsoft Virtual Academy ,it has always provided very important courses which are usually not taught in any of the
Engineering college. Even to pass the first selection process of Microsoft Student Associates round i need to complete two of the best suited courses ,Microsoft always try to disseminate knowledge among peer at every level. Microsoft conducts various competitions such as Imagine Cup with a handsome price money which give a very good platform to students to interact and to gain a lot.

Things I planned to do as a Microsoft Student Associates.

After being a MSA my very first task will be, boost the use of Microsoft products and technology .I would also share the knowledge that i gained from Microsoft Virtual Academy .More over i will discuss with my colleagues to bring more Microsoft Student Associates and Microsoft Student Partners from my Campus. Those who are interested on coding with more creativity, I would suggest them to participate in Imagine Cup like event . I would love to conduct various event in my college to bring out the best coder as an MSP.