Data Mining 101 (Part 02)

2.0 Item-based filtering

တခြားလုပ်စရာရှိတာလေးတွေလုပ်တာနဲ့ဆက်ရေးမယ်ဆိုပြီးမရေးတာ၁ပတ်လောက်ကြာသွားတယ်။ ဒီတစ်ခေါက်ကျွန်တော်တို့ဆွေးနွေးကြမှာက Item-based filtering အကြောင်းပေါ့။ သူ့ကို model-based collaborative filtering လို့လဲခေါ်ပါတယ်။ User-based filtering နဲ့ Item-based filtering ကကွာပါတယ်။

User-based filtering မှာတုံးကကျွန်တော်တို့မှာ recommend လုပ်ချင်တဲ့ user ရှိပါတယ် recommendation အတွက်ကသူနဲ့အနီးစပ်ဆုံးလူကိုရှာပြီး အဲ့လူ rating ပေးထားတဲ့ item တွေထဲကမှရွေးပြီး recommend လုပ်တာမှာပြန်သုံးတယ်ပေါ့။ Item-based filtering မှာက item တစ်ခုဆိုသူနဲ့ဆင်တူတဲ့တခြား items တွေကိုရှာထားပြီးသားပါ။ User က item တစ်ခုကိုကြည့်နေပြီဆိုမှအဲ့ item နဲ့ဆင်တူတဲ့အခြား items တွေနဲ့ user ကြည့်နေပြီးသူအဲ့ item ကိုပေးခဲ့တဲ့ rating နဲ့ပေါင်းပြီးတော့မှ recommendation ကိုတွက်ထုတ်ပါတယ်။


2.1 Adjusted Cosine Similarity
- သူက Model-based collaborative filtering method တစ်မျိုးပါပဲ။ သူ့ formula ကတော့

img

  • img ဆိုတာကတော့ u ဆိုတဲ့ user က i ဆိုတဲ့ item ကိုပေးတဲ့ rating ထဲကနေ mean ကိုနုတ်ခိုင်းတာပါ။ Mean ဆိုတာကတော့သူ rate လုပ်ထားတဲ့ item အားလုံးရဲ့ average ပေါ့။
  • s(i, j) ဆိုတာကတော့ item i နဲ့ j ရဲ့ similarity ကိုရှာမယ်လို့ပြောတာပါ။
  • Formula ကိုနားလည်အောင်အောက်ကဥပမာလေးနဲ့တွက်ကြည့်ကြပါမယ်။ ဥပမာကတော့ user တွေက သူတို့နှစ်သက်တဲ့အဆိုတော်တွေကို rating ပေးထားတာပေါ့။ တစ်ခုသတိထားဖို့က user တိုင်းကအဆိုတော်တိုင်းကို rating ပေးမှာမဟုတ်ပါဘူး။

table

  • အရင်ဆုံးဘာလုပ်ရမလဲဆို average ရှာပါမယ်။ Term နဲ့ပြောဆို Mean ပေါ့။
  • Formula ကတော့ img
  • David ရဲ့ Mean ဆို (4+5) / 2 = 4.5 ပေါ့။ ဆိုတော့အကုန်လုံးကိုတွက်လိုက်ရင်အောက်ကလိုရလာပါလိမ့်မယ်။

table

  • mean ရပြီဆို user တွေအချင်းချင်း similarity တွက်မယ်ပေါ့။ ဒီမှာ Fallout Boys နဲ့ Imagine Dragons ရဲ့ similarity ကိုတွက်မယ်ပေါ့။
  • ဟိုးပေါ်ဆုံးကပေးထားတဲ့ formula ထဲထည့်မယ်ဆို

img

  • အဖြေက -0.8 ရပါတယ်။
  • ပြောရမယ်ဆို Imagine Dragons နဲ့ Fallout Boys ရဲ့ similarity သည် -0.8 ပဲရှိတယ်ပေါ့။
  • Python နဲ့ ရေးမယ်ဆို
from math import sqrt

def similarity(item1, item2, ratings):  
    means = {}
    for (key, value) in ratings.items():
        means[key] = (float(sum(value.values())) / len(value.values()))

    numerator = 0
    denominator1 = 0
    denominator2 = 0
    for (key, value) in ratings.items():
        if item1 in value and item2 in value:
            mean = means[key]
            numerator += (value[item1] - mean) * (value[item2] - mean)
            denominator1 += (value[item1] - mean)**2
            denominator2 += (value[item2] - mean)**2
    return numerator / (sqrt(denominator1) * sqrt(denominator2))

def unitTest():  
    ratings = {"David": {"Linkin Park": 4, "Fallout Boys": 5},
               "Chris": {"Linkin Park": 3, "Fallout Boys": 2, "Imagine Dragons": 5},
               "John": {"Linkin Park": 5, "Fallout Boys": 3, "Imagine Dragons": 4}}
    print(similarity("Imagine Dragons", "Fallout Boys", ratings))


>>> unitTest()
>>> -0.8

တခြား similarity သာဆက်တွက်မယ်ဆို

img

  • Item တွေအချင်းချင်းကြားက similarity တော့ရပြီပေါ့။ ဒီတော့ဘာဆက်လုပ်မလဲဆို recommendation အတွက် user ကို item တစ်ခု recommend လုပ်ရင် rating ဘယ်လောက်ပေးမလဲဆိုတာဆက်တွက်ကြပါမယ်။

img

  • formula ကိုပြောရမယ်ဆို u ဆိုတဲ့ User ကိုသာ i ဆိုတဲ့ item recommend လုပ်ရင် rating ဘယ်လောက်ပေးမလဲပေါ့။
  • N ဆိုတာကတော့ u ဆိုတဲ့ User က rate လုပ်ထားပြီး i နဲ့ဆင်တူတဲ့ item တွေကိုပြောတာပါ။
  • S_{i, N} ဆိုတာကတော့ i နဲ့ N ကြားက similarity ကိုပြောတာပါ။
  • R_{u, N} ကတော့ N ဆိုတဲ့ item ကို user က rate လုပ်ထားတဲ့ value ကိုပြောတာပါ။

Tea Break :-)
Keywords တွေ Formula တွေကခေါင်းခြောက်စရာတွေပါ၊ ဆိုတော့ခဏလေးနားပြီးဖြစ်ဖြစ် ဖြည်းဖြည်းချင်းဖတ်သွားတာကအဆင်ပြေပါလိမ့်မယ်။

2.1.1 Normalize
- အပေါ်က formula ကိုတွက်ဖို့အတွက် value တွေကို normalize လုပ်ဖို့လိုပါတယ်။ Normalize လုပ်တယ်ဆိုတာကတော့ value တွေကို -1 and +1 ကြား scale ထဲထည့်တာပါ။ အပေါ်က table ကိုပြန်ခေါ်ရမယ်ဆိုကျွန်တော်တို့က rating ကို 1 and 5 ကြားမှာပေးခဲ့ကြပါတယ်။ အဲ့ value တွေကို -1 and +1 ကြားနဲ့ပြန်ဖေါ်ပြမှာပေါ့။ - Formula ကတော့

img

  • MaxR ကတော့အမျာဆုံးပေးနိုင်တဲ့ rating ဖြစ်ပြီး $MinR$ ကတော့အနည်းဆုံးပေးနိုင်တာပေါ့။
  • အပေါ်ကဥပမာနဲ့ဆို $MaxR$ က 5 ဖြစ်ပြီး $MinR$ က 1 ပေါ့။
  • ဥပမာ David ရဲ့ Linkin Park normalize က ( 2(4-1) -(5-1) ) / (5-1) = -0.5 ပေါ့။
  • အောက်ကတော့အပေါ်က table value တွေကို normalize လုပ်ထားတာပါ။

table

  • ဆိုတော့အပေါ်က p(u, i) ဆိုတဲ့ formula ထဲထည့်ကြည့်ရအောင်
  • David က Linkin Park နဲ့ Fallout Boys ကို rating ပေးထားပါတယ်။ ဆိုတော့

img

  • p(David, Imagine Dragons) = 0.85 ရလာပါတယ်။ ရလာတာက Normalized rating ပါ။
  • ဒါကို နကို 1-5 ကြား rating ပြန်ပြောင်းပါမယ်။ ဒီလိုလုပ်တာကို Denormalize လို့ခေါ်ပါတယ်။

2.1.2 Denormalize
img

  • ဆိုတော့ 0.5 x (0.85 + 1) x 4 + 1 = 4.7 ပေါ့
  • ဆိုတော့ Imagine Dragons သာ David ကို recommend လုပ်ရင် 4.7 rating ပေးမယ်လို့ပြောတာပါ။

2.2 Weighted Slope One
- Weighted Slope One မတွက်ခင်အရင်ဆုံး Deviation ရှာရပါတယ်။

2.2.1 Finding Deviation
img

  • img ဆိုတာကတော့ item i and j ၂ခုစလုံးကို rate လုပ်ထားတဲ့လူအရေအတွက်ကိုပြောတာပါ။
  • ဆိုတော့ထုံးစံအတိုင်း ဥပမာလေးနဲ့သွားကြတာပေါ့။

table

  • Deviation of Linkin Park to Fallout Boys ဆို img
  • အဖြေက 2 ရပါတယ်။ -Deviation of Fallout Boys to Linkin Park ကျ img
  • သူကျတော့ -2 ရပါတယ်။
  • ဆိုတော့ပြောရမယ်ဆို User တွေ rating အရ Linkin Park သည် Fallout Boys ထက် 2 unit ပိုကောင်းတယ်ပေါ့။
  • ဒါဆို Deviation ကို table လေးဆွဲကြည့်လိုက်ပါတယ်။

table

  • ဒီ method မှာအားသာချက်တစ်ခုရှိပါတယ်။ ဥပမာ music streaming site (like Spotify) မှာသီချင်းအပုဒ်၁၀၀၀ရှိမယ်ပေါ့။ အသစ်အပုဒ်၁၀၀ထပ်ဝင်လာရင် algorithm ကိုအစကပြန် run စရာမလိုပါဘူး။

2.2.2 Prediction with Weighted Slope One
- deviation ရှာပြီးပြီဆို prediction ပိုင်းကိုဆက်လုပ်ပါမယ်။ Formula ကတော့

img

  • img
  • img ဆိုတာကတော့ User u ကနေ item j ကို weighted slope one သုံးရှာထားတဲ့ predicted value ကိုပြောတာပါ။
  • ဒီဥပမာမှာကျွန်တော်တို့က John ကို Imagine Dragon recommend လုပ်ပေးဖို့တွက်မှာပါ
  • img ဆိုတာကတော့ User u ကနေ j ကလွဲလို့တခြား rate လုပ်ထားတဲ့ item တွေရဲ့ total value ကိုပြောတာပါ။
  • အပေါ်ကဥပမာနဲ့ဆို John က Fallout Boys ကို rating 2 ပေးထားပါတယ်။ ဒီတော့ $u_i$ က 2 ပါ။
  • နောက်အပေါ်မှာရှာခဲ့တာ Deviation of Imagine Dragons (j) to Fallout Boys (i) က -0.25 ပါ။ ဒီတော့ dev_{j, i} သည် -0.25 ပါ။
  • img ကျ Fallout Boys ကော Imagine Dragons ကောကို rate လုပ်ထားတာ ၂ယောက်ရှိပါတယ်။ ဆိုတော့အဖြေက 2 ပေါ့။
  • img တွက်တော့ (-0.25 + 2) x 2 = 3.5 ရပါတယ်။
  • John က Linkin Park ကိုလဲ rate လုပ်ထားပါတယ်။ အဲ့တာကိုပါအပေါ်ကလိုတွက်လိုက်ရင် (1 + 5) x 2 = 8 ရပါတယ်။
  • ဆိုတော့ရလဲတဲ့အဖြေ၂ခုကိုပေါင်းလိုက်တော့ 11.5 ဒါသည် fraction အပေါ်က numerator value ကိုရသွားပါတယ်။ အောက်က denominator ဆက်တွက်မယ်ဆို
  • img ကတော့ John rate လုပ်ထားတဲ့အဆိုတော်ကော နောက် John ကို recommend လုပ်မယ့်အဆိုတော်ကိုကော rate လုပ်ထားတဲ့လူအရေအတွက်ကိုပြောတာပါ။
  • Linkin Park and Imagine Dragons ကို rate လုပ်ထားတာသည်အားလုံးပေါင်း၂ယောက်နောက် Fallout Boys and Imagine Dragons ကို rate လုပ်ထားတာကလဲ ၂ယောက်ဆိုတော့ Denominator က 4 ရသွားပါတယ်။
  • ဆိုတော့ numerator 11.5 ကို denominator 4 နဲ့စားလိုက်တော့နောက်ဆုံးအဖြေသည် 2.875 ရသွားပါတယ်။ ဒီတော့ Imagine Dragon ကိုသာ John နားထောင်ရင် 2.875 rating ပေးမယ်ပေါ့။

For best experience of reading, download Markdown version of the post here
Read with an editor that also support LaTeX