Data Mining 101 (Part 01)

0.0 Introduction

ဒီတခေါက်တော့ Data Mining teachnique တွေကိုအသုံးပြုပြီး recommendation system တစ်ခုဘယ်လိုအလုပ်လုပ်သလဲဆိုတာကိုဆွေးနွေးကြပါမယ်။ အခုခေတ်မှာ online shooping ဆိုက်တွေဖြစ်တဲ့ amazon လိုကောင်မျိုးမှာဆိုကိုယ်ကြည့်နေတဲ့ product တစ်ခုရဲ့အောက်မှာ items you may like စသဖြင့်တခြား product တွေကိုဖေါ်ပြထားတာမျိုးတွေကိုတွေ့ဖူးကြမှာပါ။ သေချာတာကတော့ဒါတွေကဖြစ်ချင်ရာဖြင်ဆိုပြီးပြချင်တဲ့ product တွေပြထားတာမဟုတ်ပါဘူး။ နောက်ကွယ်မှာ Data Mining method တမျိုးမျိုးကိုအသုံးပြုထားတာပါ။

ဒီတခေါက်ကျွန်တော်ပြောပြပေးချင်တဲ့ method ကတော့ Collaborative filtering အကြောင်းပဲဖြစ်ပါတယ်။ သူ့ကို Social filtering လို့လဲခေါ်ပါတယ်။ Collaborative filtering ထဲမှာမှ user based နဲ့ item based ဆိုပြီး၂မျိုးရှိပါသေးတယ်။ အခုတော့ user-based အကြောင်းလေးနဲ့ပဲစပါမယ်။


1.0 User-based filtering

User-based filtering မှာဆိုရင် user တယောက်ကို recommend လုပ်ဖို့အတွက်အဲ့ user နဲ့ interest အတူဆုံးဖြစ်တဲ့အခြား user တစ်ယောက်ကိုရှာပါတယ်။ ဒီလို interest အတူဆုံးဖြစ်တဲ့သူကိုရှာဖို့အတွက် method တွေရှိပါတယ်။ အဲ့တာတွေကတော့
1. Manhattan Distance
2. Euclidean Distance
3. Minkowski Distance Metric
4. Approximate of Pearson
5. Cosine Similarity နဲ့
6. K-nearest neighbors တို့ဖြစ်ပါတယ်။ ဒီကောင်တွေနဲ့တွက်ထုတ်လို့ရလာသည့် value မှအနည်းဆုံးဖြစ်တဲ့ user ကို choose လုပ်ပါတယ်။

1.1 Manhattan Distance
Manhattan Distance ကတော့အလွယ်ကူဆုံး method တစ်ခုလို့ပြောလို့ရပါတယ်။ သူ့ formula ကတော့
formula အခက်ကြီးမထင်ပါနဲ့ Sigma ဆိုတာကတော့ ပထမဆုံး k ကနေ x-y ရှာမယ်ဘယ်အထိလဲဆို nth အထိပေါ့ပြီးရင်အဲ့ values တွေအကုန်ပြန်ပေါင်းလိုက်ပါ။ ဒါပါပဲ။ x-y graph မှာဆိုရင် manhattan distance formula ကတော့ |x1 - x2| + |y1 - y2| ပါ။ x1, y1 နောက် x2, y2 ကတော့ point ၂ခုကိုပြောချင်တာပါ။ | ကတော့ထွက်လာသည့် value ကို positive value ပဲယူခိုင်းတာဖြစ်ပါတယ်။ ဘာလို့လဲဆိုကျွန်တော်တို့က distance ရှာတာပါ။

Distance သည် negative value မရှိပါ။ Vector မှာမှ direction ပါလို့ negative value ရှိနိုင်တာပါ

ဥပမာ A နဲ့ B ဆိုတဲ့ point ၂ခုရှိတယ်ဆိုပါဆို့၊ point A ရဲ့ နေရာသည် (2, 5) ဖြစ်ပြီး point B သည် (6,9) ဖြစ်တယ်ဆို Manhattan Distance သည် 8 ဖြစ်ပါတယ်။ Manhattan Distance အတွက် python code ကတော့ရှင်းပါတယ်။

def manhattan(dictionary1, dictionary2):  
    distance = 0
    for key in dictionary1.keys():
        if key in dictionary2.keys():
            distance += abs(dictionary1[key] - dictionary2[key])
    return distance

def unitTest():  
    dictionary1 = {'x': 2, 'y': 5}
    dictionary2 = {'x': 6, 'y': 9}
    print(manhattan(dictionary1, dictionary2))

>>> unitTest()
>>> 8


1.2 Euclidean Distance
သူကတော့ Pythagorean Theorem သုံးပြီး hypoteneus ရှာခိုင်းတာပါ။ သူ့ formula ကတော့ formula x-y graph မှာဆိုရင်တော့
formula ဖြစ်ပါတယ်။ အပေါ်က ဥပမာနဲ့ဆိုရင် ((2-6)^2 + (5-9)^2)^(1/2) ဒီတော့ eculidean distance သည် 5.66 ဖြစ်ပါတယ်။ Python code နဲ့ဆိုရင်တော့

def euclidean(dictionary1, dictionary2):  
    distance = 0
    for key in dictionary1.keys():
        if key in dictionary2.keys():
            distnace += (dictionary1[key] -dictionary2[key])**2
    return distance**(1/2)

def unitTest():  
    dictionary1 = {'x': 2, 'y': 5}
    dictionary2 = {'x': 6, 'y': 9}
    print(euclidean(dictionary1, dictionary2))

>>> unitTest()
>>> 5.656854249492381


1.3 Minkowski Distance Metric
အပေါ်ကပြောခဲ့တဲ့ Manhattan နဲ့ Euclidean Distance တွေကိုအလွယ်မှတ်နိုင်ဖို့ Minkowski Metric ဆိုတာရှိပါတယ်။ သူ့ formula ကတော့ formula ဖြစ်ပါတယ်။ ခေါင်းမရှုပ်သွားပါနဲ့။ - r တန်ဖိုး 1 သာဖြစ်ခဲ့ရင် Manhattan Distance ဖြစ်ပြီး - 2 သာဖြစ်ခဲ့ရင် Euclidean Distance ဖြစ်မှာပါ။

r တန်ဖိုး 1 ဖြစ်သွားရင် ညာဘက်က power တွေကြေကုန်ပြီးအပေါ်က Manhattan Distance formula ပဲပြန်ရမှာပါ။ ဒီတော့ python code နဲ့သာပြဆိုအောက်ကလိုဖြစ်မှာပါ။

def mankowski(dictionary1, dictionary2, r):  
    distance = 0
    for key in dictionary1.keys():
        if key in dictionary2.keys():
            distance += (abs(dictionary1[key] - dictionary2[key]))**r
    return distance**(1/r)

def unitTest():  
    dictionary1 = {'x': 2, 'y': 5}
    dictionary2 = {'x': 6, 'y': 9}
    for i in range(1, 3): print(mankowski(dictionary1, dictionary2, i))

>>> unitTest()
>>> 8.0
>>> 5.656854249492381

Downside: Manhattan Distance နှင့် Euclidean Distance measure တွက်တဲ့အခါ data မှာ missing values တွေပါနေလို့မဖြစ်ပါဘူး။

1.4 Approximate of Pearson
သူကတော့ data တွေရဲ့ correlation ကို measure လုပ်တာဖြစ်ပါတယ်။ Correlation ဆိုတာကတော့ numerical variables တွေရဲ့ strength နဲ့ direction ကိုတိုင်းတာတာပါ။ Statistic သင်ဖူးတယ်ဆို scatterplot ကိုမြင်ဖူးမှာပါ။ Scatterplot မှာ scatterpoints တွေချပြီးပြီဆို best fit line ဆွဲလေ့ရှိပါတယ်။ Correlation ဆိုတာကအဲ့ဒီ best fit line နဲ့ကြည့်တာပါ။

Scatterpoints တွေသည် best fit လိုင်းနဲ့နီးနေပြီး line ကဘယ်ဘက်ကနေညာဘက်ကိုတက်သွားတာဆို strong and positive correlation လို့ပြောလို့ရပါတယ်။ best fit line ကသာဘယ်ကနေညာကိုဆင်းသွားတဲ့ line ဆိုရင်တော့ negative correlation လို့ဆိုနိုင်ပါတယ်။

Measurement scale သည် correlation ပေါ်သက်ရောက်မှုမရှိပါဘူး။ နောက် correlation value သည် -1 and +1 ကြားမှာပဲရှိပါတယ်။ -1 ဒါမှမဟုတ် +1 နှင့် value သည်နီးလေ strength သည် stronger ဖြစ်လေလို့ဆိုနိုင်ပါတယ်။ Formula ကတော့
formula

ဒီ formula ကိုဥပမာလေးတစ်ခုနဲ့ရှင်းပါမယ်။ အောက်ကဥပမာမှာတော့လူ၂ယောက်ကသူ့တို့လည်ခဲ့တဲ့နိုင်ငံတွေကို rating ပေးထားတာပေါ့။ အနှစ်သက်ဆုံးဆို 5 ဖြစ်ပြီးမကြိုက်ဆုံးကတော့ 0 ပေါ့။

table

Formula ရဲ့ formula ကိုအရင်ရှင်းမယ်။ သူ့ကို formula ထဲထည့်ရင်
(3.7 x 4.1) + (4.5 x 3.8) + (3.2 x 3.5) ဒီတော့အဖြေက 43.47 ဖြစ်ပါတယ်။

formula သူကျတော့ ((3.7 + 4.5 + 3.2) x (4.1 + 3.8 + 3.5)) / 3 ဒီတော့အဖြေက 43.32 ရပါတယ်။

နောက် formula သူကျတော့ formula = (3.7)^2 + (4.5)^2 + (3.2)^2 ဆိုတော့ 44.18 ရပါတယ်။

formula = ((3.7 + 4.5 + 3.2)^2)/3 ဆိုတော့ 43.32 ရပါတယ်။ အဲ့၂ခုကိုပြန်တွက်ထုတ်လိုက်ရင် (44.18 - 43.32)^(1/2) ကနောက်ဆုံး 0.92 ရလာပါတယ်။

^ means power

နောက်တစ်ခုကတော့ x အစား y value နဲ့တွက်ပေးလိုက်ပေါ့။ ကျွန်တော် y တန်ဖိုးတွေကိုတွက်ကြည့်တော့ 0.42 ရပါတယ်။

ရလာတာတွေအကုန်ယူပြီး Approximate of Pearson တွက်ရင်တော့
(43.47 - 43.32) / (0.92 x 0.42) = 0.3 ရလာပါတယ်။ အခု example က result အရဆိုရင်တော့ correlation ကမကောင်းပါဘူး။

Python code လေးရေးပါမယ်။ Python code မရေးခင်စဉ်းစားရမှာက formula အရဆို calculation အတွက်လိုအပ်တာက xy, x, x^2, y, y^2 နောက် n တန်ဖိုးတွေဖြစ်ပါတယ်။ Python code ကတော့အောက်မှာပါ။

from math import sqrt

def pearson(dictionary1, dictionary2):  
    n = 0
       x = 0
    y = 0
    xy = 0
    x2 = 0
    y2 = 0

    for key in dictionary1.keys():
        if key in dictionary2.keys():
            n += 1
            x += dictionary1[key]
            y += dictionary2[key]
            xy += dictionary1[key] * dictionary2[key]
            x2 += dictionary1[key]**2
            y2 += dictionary2[key]**2

    if n:
        denominator = sqrt(x2 - (x**2) / n)  * sqrt(y2 - (y**2) / n)
        if denominator:
            return (xy - (x*y) / n) / denominator
        else:
            return 0
    else:
        return 0


def unitTest():  
    james = {'Bangkok': 3.7, 'Singapore': 4.5, 'Kuala Lampur': 3.2}
    hailey = {'Bangkok': 4.1, 'Singapore': 3.8, 'Kuala Lampur': 3.5}
    print(pearson(james, hailey))

>>> unitTest()
>>> 0.381246425832


1.5 Cosine Similarity
သူကတော့ text mining မှာအသုံးများပါတယ်။ သူ့ကိုသုံးရတဲ့အကြောင်းအရင်းရှိပါတယ်။ ပြောရရင် ကျွန်တော့်မှာ iTunes music liabrary ရှိတယ်ဆိုပါစို့အဲ့မှာ play count ဆိုတာရှိပါတယ်။ သူကသီချင်းကိုကျွန်တော်ဘယ်နှခေါက်နားထောင်ပြီးပြီလဲဆိုတာပြတာပေါ့အဲ့မှာကျွန်တော်က သီချင်း ၁၀၀၀ ရှိတယ်ဆို ၁၀၀ လောက်သာပုံမှန်နားထောင်ဖြစ်ပါတယ်။ ပြောရရင်ကျန် ၉၀၀ရဲ့ play count က 0 ဖြစ်နေပါတယ်။ ဒီလို zero တွေအများကြီးပါနေတဲ့ data ကိုသာအပေါ်ကနည်းတွေနဲ့တွက်မယ်ဆို result ပေါ်မှာသက်ရောက်မှုတွေရှိပါတယ်။ Cosine similarity ကတော့အဲ့ဒီ 0 data တွေကိုထည့်မတွက်ပါဘူး။ Cosine Similarity value ကလဲ -1 နဲ့ +1 ကြားမှာရှိပါတယ်။ negative value ဆို negative similarity လို့ယူပါတယ်။ သူ့ formula ကတော့
formula
formula မှာ . ကမြောက်ခိုင်းတာပါ။ ပြောရရင် xi နဲ့ yi တန်ဖိုကိုမြောက်ခိုင်းတာပါပြီးရလာတဲ့ result ကိုကျန် xy value နဲ့ပေါင်းခိုင်းတာပါ။ ဘယ်အထိလဲဆို nth, formula ကိုမြင်အောင်ရေးပေးရမယ်ဆိုအောက်ကလိုပါ။
formula

နောက် ||x|| သူကတော့ vector x ရဲ့ length ကိုပြောတာပါ။ Length of vector formula ကတော့
formula
အပေါ်က example ထဲက data နဲ့ပဲတွက်ကြည့်ရအောင်

table

||x|| ဆို (3.7^2 + 4.5^2 + 3.2^2)^(1/2) = 6.65
||y|| လဲအပေါ်ကလိုတွက်ရမှာပါ။ ကျွန်တော်တွက်လိုက်တာ 6.60 ရပါတယ်။ x.y တွက်တာကတော့ 43.47 ရပါတယ်။
Cosine Similarity တွက်တော့ 43.47 / (6.65 x 6.60) = 0.99 အဖြေရပါတယ်။

Python code ကတော့အောက်ကလိုဖြစ်ပါတယ်။

from math import sqrt

def cosine_similarity(dictionary1, dictionary2):  
    xy = 0
    x2 = 0
    y2 = 0
    for key in dictionary1.keys():
        if key in dictionary2.keys():
            xy += dictionary1[key] * dictionary2[key]
            x2 += dictionary1[key]**2
            y2 += dictionary2[key]**2
    return xy / (sqrt(x2) * sqrt(y2))

def unitTest():  
    james = {'Bangkok': 3.7, 'Singapore': 4.5, 'Kuala Lampur': 3.2}
    hailey = {'Bangkok': 4.1, 'Singapore': 3.8, 'Kuala Lampur': 3.5}
    print(cosine_similarity(james, hailey))

>>> unitTest()
>>> 0.9915900401999774


1.6 K-nearest neighbors
သူကတော့ similarity အတွက် source တစ်ခုထဲကိုအခြေမခံပါဘူး။ k တန်ဖိုးဖေါ်မူတည်ပြီး source ဘယ်နှခုကနေ reply လုပ်မလဲဆုံးဖြတ်ပါတယ်။ k က 3 ဆို source 3 ခုကပေါ့။ တကယ်တန်း k value ဘယ်လောက်ယူမယ်ဆိုတာကတော့ experiments တွေကနေဆုံးဖြတ်ပါတယ်။ ဥပမာ James ဆိုတဲ့လူတစ်ယောက်ကို သီချင်း recommend လုပ်မယ်ပေါ့။ k = 3 ဆို အပေါ်က method တစ်ခုခုသုံးပြီးရှာလိုက်လို့ James နဲ့အကြိုက်အနီးစပ်ဆုံး ၃ယောက်ကိုယူမှာပေါ့။ အဲ့လူ၃ယောက်က Hailey, John, Amanda ဆိုပါစို့ အောက်က table လေးကိုကြည့်လိုက်ပါ။

table

Pearson Value အကုန်ပေါင်းလိုက်ရင် 2.0 ရပါတယ်။ K-nearest neighbor တွက်ရင် Influence Percent တွက်ပေးရပါတယ်။ သူက suggest လုပ်မယ့်သူအပေါ် ရွေးထားတဲ့ source တွေက ဘယ် source က suggest လုပ်မယ့်သူအပေါ်ဘယ်လောက် influence ဖြစ်တယ်ဆိုတာပေါ့။ သူ့ formula ကတော့
formula အပေါ်ကဥပမာနဲ့ဆို Hailey သည် 35% influence ဖြစ်ပါတယ် ((0.70/2.0) x 100%)။ John က 40% နောက် Amanda က 25% ဖြစ်ပါတယ်။

ဒါဆို Projected rating ဆက်ရှာပါမယ်။ သူကတော့ k sources တွေကိုကြည့်ပြီးတော့မှရလာတဲ့ value ပေါ့။
formula ပြောရရင် source rating နဲ့ သူ့ influences တွေကိုမြောက်ပြီးတော့အကုန်ပေါင်းခိုင်းတာပါ။ အပေါ်ကဥပမာနဲ့ဆို

(3.5 x 0.35) + (4.5 x 0.40) + (3.7 x 0.25) = 3.95 ပြောရရင် recommend လုပ်လိုက်တဲ့ music ကို James သာနားထောင်ရင် rating ကို 3.95 ပေးမယ်ပေါ့။


User-based filtering အကြောင်းကတော့ဒီလောက်ပါပဲ။ သူ့မှာအဓိက limitation ၂ခုရှိပါတယ်။ အဲ့တာကတော့
1. Scalability: ဘာလို့လဲဆို code မှာသာဆို data များလာသမျှ computation capacity လဲမြင့်လာပါတယ်
2. Sparsity: လက်တွေ့မှာက amazon လို market မှာဆို user တိုင်းက rating ပေလေ့းပါဘူး။ product အားလုံးရဲ့ တချို့ကိုသာ rate လုပ်လေ့ရှိကြပါတယ်။ ဆိုတော့ဒီမျိုးမှာဆို nearest neighbor ရှာတဲ့အချိန်မှာအခက်တွေ့နိုင်ပါတယ်ဘာလို့လဲဆိုကျွန်တော်တို့အပေါ်ကပြောခဲ့တာတွေက user ပေါ်မူတည်ပြီး evaluate လုပ်ကြတာမို့ပါ။

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


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