程序代写代做代考 algorithm Plan today – cscodehelp代写

Plan today
• Why recommender systems?
• Recommender systems and collaborative filtering
– Popularity based
– Collaborative filtering – memory based
• Item-Item • User-User
• Friday’s lecture
– Content-based and model-based collaborative filtering – System evaluation

Why recommender systems?
• Scarcity to Abundance
• Internet changed shopping behaviours
• Online business is heavily dependent on recommender systems.
item sorted by popularity
– long tail –
popularity

Why recommender systems?
• The Long Tail by : “In 1988, a British mountain climber named wrote a book called ‘Touching the Void’, a harrowing account of near death in the Peruvian Andes. It got good reviews but, only a modest success, it was soon forgotten. Then, a decade later, a strange thing happened. wrote ‘Into Thin Air’, another book about a mountain-climbing tragedy, which became a publishing sensation. Suddenly Touching the Void started to sell again”.
• “A lot of times, people don’t know what they want until you show it to them” –

++
Total price: $27.19
Recommender systems – examples
Ad feedback
Kids Categories Search Kids… Exit Kids
The Wiggles My Little Pony Mako Mermaids H2O: Just Add Water Good Luck Charlie Pokémon
Boys in the
at: Nine
The Revenant: A Novel of Revenge
›
Ready Player One: A Novel ›
The Life We Bury ›
The 5th Wave: The First Book of the 5th Wave Series
›
Paperback
$9.52
2,006
1,250
Paperback
$8.37
Paperback
$8.75
9,210
1,896
Paperback
$6.70
This item: The Martian by Paperback $8.92
The Revenant: A Novel of Revenge by Paperback $9.52 • LinkedIn
The Life We Bury by Paperback $8.75 • Facebook
• Twitter
Customers Who Bought This Item Also Bought
Netflix
Page 1 of 15
13/03/2016 10:03 26am
• Youtube • Netfix
• Amazon
Recently watched
Popular
Top Picks for Kids
The
Americans and Their Epic QuestAcftoiorn Gold at the…
› Brown
17,056
#1 in Boating Paperback $9.1ht5tps://www.netflix.com/Kids
Bo
Page 1 of 4

Recommender systems
• “75% of what people watch is from some sort of recommendation” (Netflix)
• “If I have 3 million customers on the web, I should have 3 million stores on the web.” (Amazon CEO)
Movie recommender systems
– finding best matched movies,
– reducing search times and frustration.
Users
Titanic
Batman
Inception
Superman
The Martian
Jurassic World
Harry
3
2
–
–
1
–
Ming
–
–
1
2
–
–
Peter
1
–
–
3
2
1

Recommender systems – How it works
• An online system where many users interact with many items.
• Each user has a profile
• User rate items
– Explicitly: give a score
– Implicitly: web usage mining: Time spent on viewing the item, etc.
• System does the rest, How?

Popularity based recommendation
• Show popular items.
• Which item is popular?
• Simple but not personalised.

Collaborative filtering
• Collaborative Filtering: Making predictions about a user’s missing data according to the collective behaviour of many other users
– Look at users’ collective behavior (e.g. ratings) – Active user history
– Combine!
• Item-based collaborative filtering (Item-Item)
• User-based collaborative filtering (User-User)

Collaborative filtering – A framework
𝑹
𝒖𝟏
𝒊𝟏
3
1
𝒊𝟐
4
𝑰: 𝒏-items
⋯
2
𝒊𝒋
⋯
𝒊𝒏
1
𝒖𝟐
2
5
⋮
2
1
𝒖𝒊
3
4
𝑟𝑖𝑗?
𝑓: 𝑈 𝑥 𝐼 → 𝑅
⋮
5
3
2
4
3
3
𝒖𝒎
• Given
– A set of 𝑚 users 𝑼 and a set of 𝑛 Items 𝑰
– A𝑚×𝑛InteractionMatrixorRatingMatrix𝑹
• Find unknown ratings 𝑟𝑖𝑗
: -users

Item-based method: Intuition
People like things similar to other things they like
• Search for similarities among items
– Many users like both Batman and Superman→ the two movies are similar.
– Similarity is collective similarity in ratings by many users.
• Recommend items similar to those rated by the target user.
– Superman and Batman are similar – If Peter liked Batman then
recommend Superman to Peter.
Superman Batman

Item based collaborative filtering
Three questions to address:
• How to measure item similarities?
• How to find similar items?
• How to combine ratings of these items?
i1 ii ij in u1
um

Q1: Measure item-similarity
Example similarity between item 𝑖 and item 𝑖 : 𝑖𝑗
• Euclidean distance with mean imputation – Imputation with their mean values
3+3+2
• 𝑚𝑒𝑎𝑛𝑖𝑖 = 3 =2.7
𝑖𝑖 𝑖𝑖 𝑖𝑗 𝑖𝑗
– Similarity score based on Euclidean distance
𝐬𝒊𝒎 𝒊𝒊,𝒊𝒋 = 𝟏 where𝒅 𝒊𝒊,𝒊𝒋 = σ𝒎 (𝒓 −𝒓 )𝟐
– 𝒅𝒊𝒊,𝒊𝒋 =3.24
= (3 − 3.75)2+(2.7 − 3.5)2 + (2.7 − 3)2+(3 − 3.5)2 +(2 − 4)2 +(2.7 − 4)2+ (2.7 − 4.5)2
–𝒔𝒊𝒎𝒊𝒊,𝒊𝒋= 𝟏 =𝟎.𝟐𝟒 𝟏+𝟑.𝟐𝟒
3 −
− 3.5 − 3
3 3.75 2.7 3.5 2.7 3
3 3.5
𝑗 − 4 2.7 4
3 3.5 •𝑚𝑒𝑎𝑛𝑖=3.75 2 24
− 4 2.7 4.5 4.5
𝟏+𝒅 𝒊𝒋,𝒊𝒊 𝒌=𝟏 𝒌𝒊 𝒌𝒋

Q2: How to find similar items?
• We have an answer to Q1, for item 𝑥1, we have the similarities between it and other items:
𝒔𝒊𝒎(𝒙𝟏, 𝒙𝟐)
𝒔𝒊𝒎(𝒙𝟏, 𝒙𝟑)
𝒔𝒊𝒎(𝒙𝟏, 𝒙𝟒)
𝒔𝒊𝒎(𝒙𝟏, 𝒙𝟓)
𝒔𝒊𝒎(𝒙𝟏, 𝒙𝟔)
0.48
0.4
0.20
0.33
0.35
• The target user 𝒂 has rated some items:
𝒙𝟏
𝒙𝟐
𝒙𝟑
𝒙𝟒
𝒙𝟓
𝒙𝟔
𝒂
?4
-5
3
3
• Choose a number 𝒌, find k-most similar items to 𝑥1 for user a
• Let 𝑘 = 3, which 3 items?
– Items 𝑥2, 𝑥6, and 𝑥5
– scores 0.48, 0.35, and 0.33.

Q3: How to combine ratings of similar items?
• Predict the rating of item 𝑥1 for user 𝑎
• From Q1 and Q2, we get:
– For user 𝑎, the 3 (k = 3) most similar items to 𝑥1: 𝑥2, 𝑥6, 𝑥5
𝒔𝒊𝒎(𝒙𝟏, 𝒙𝟐)
𝒔𝒊𝒎(𝒙𝟏, 𝒙𝟑)
𝑺𝒊𝒎(𝒙𝟏, 𝒙𝟒)
𝒔𝒊𝒎(𝒙𝟏, 𝒙𝟓)
𝒔𝒊𝒎(𝒙𝟏, 𝒙𝟔)
0.48
0.4
0.20
0.33
0.35
– The ratings of these 3 items by user a: 4, 3.5, 3
𝒙𝟏
𝒙𝟐
𝒙𝟑
𝒙𝟒
𝒙𝟓
𝒙𝟔
𝒂
?
4
–
5
3
3
• Rating = weighted average over the ratings of the 3 most similar items
– 𝑟 =0.48×4+0.33×3+0.35×3=3.41
𝑎,𝑥1
0.48 + 0.33 + 0.35

Item-based Collaborative Filtering – Algorithm
• Phase 1 – For each item j,
– Compute similarities between j and other items.
similarity: e.g. Euclidean distance with mean imputation.
– Batch, Off-line
• Phase 2 – Predict rating of item j by user 𝑎 based on the k-most similar items (among items rated by 𝑎)
– Predicted rating = weighted average over the ratings of the k-most similar items.
𝑟= 𝑎𝑗
– Online
σ 𝑠𝑖𝑚𝑖,𝑗 ×𝑟
𝑖∈𝑘−𝑠𝑖𝑚𝑖𝑙𝑎𝑟−𝑖𝑡𝑒𝑚𝑠 σ𝑖∈𝑘−𝑠𝑖𝑚𝑖𝑙𝑎𝑟−𝑖𝑡𝑒𝑚𝑠 𝑠𝑖𝑚 𝑖, 𝑗
𝑎𝑖

Item-based filtering – Practice example
• Predict 𝑟 (𝑎 = 𝑇𝑖𝑚; 𝑗 = 𝐼𝑛𝑐𝑒𝑝𝑡𝑖𝑜𝑛) 𝑎𝑗
Users
Titanic
Batman
Inception
Superman
The Martian
Jurassic World
Michelle
2.5
3
3.5
2.5
3
Tom
3
3.5
5
3
3.5
Lao
2.5
3
3.5
4
Chan
3.5
3
4
2.5
Mary
4
2
3
2
3
Tim
3
4
raj?
5
3.5
3
John
4.5
4
1
Phase – 1 offline: similarities between Inception and other movies
sim( Inception, Titanic)
sim( Inception, Batman)
sim( Inception, Superman)
sim( Inception, The Martian)
sim( Inception, Jurassic World)
0.48 (d=1.08)
0.24 (d=3.24)
0.20 (d=3.89)
0.33 (d=2.05)
0.34 (d=1.97)

Item-based filtering – Practice example cont.
• Phase – 2 online:
– select 3-most similar items (k=3) w.r.t. (Tim, Inception)
–
sim( Inception, Titanic)
sim( Inception, Batman)
sim( Inception, Superman)
sim( Inception, The Martian)
sim( Inception, Jurassic World)
0.48
0.24
0.20
0.33
0.34
Users
Titanic
Batman
Inception
Superman
The Martian
Jurassic World
Michell e
2.5
3
3.5
2.5
3
Tom
3
3.5
5
3
3.5
Lao
2.5
3
3.5
4
Chan
3.5
3
4
2.5
Mary
4
2
3
2
3
Tim
3
4
?
5
3.5
3
John
4.5
4
1
– weighted avg over the ratings of the 3-most similar items
– 𝑟 = 0.48×3 + 0.33×3.5 + 0.34×3 = 3.14
𝑎𝑗
0.48 + 0.33 + 0.34

Item-based collaborative filtering Summary
• Item similarities computation is off-line
• So, efficient at runtime.
• Developed by Amazon, suited for situations #users >> #items
• What do we do with new items?