第2-1節(jié)計算曼哈頓距離|寫給程序員的數(shù)據(jù)挖掘?qū)嵺`指南-學(xué)習(xí)筆記

文章原創(chuàng),最近更新：2018-08-31

1.關(guān)于本書
2.關(guān)于作者
3.內(nèi)容簡介
4.案例
5.本例完整代碼

引言:網(wǎng)上找資料覺得這本書挺通俗易懂的,剛好可以跟《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》相關(guān)章節(jié)結(jié)合一起學(xué)習(xí)。

學(xué)習(xí)參考鏈接:
1.面向程序員的數(shù)據(jù)挖掘指南

1.關(guān)于本書

寫給程序員的數(shù)據(jù)挖掘?qū)嵺`指南:豆瓣評分:7.4分
作者: [美] Ron Zacharski
出版社: 人民郵電出版社
原作名: A Programmer's Guide to Data Mining
譯者: 王斌
出版年: 2015-10-24

2.關(guān)于作者

Ron Zacharski是一名軟件開發(fā)工程師间护，曾在威斯康辛大學(xué)獲美術(shù)學(xué)士學(xué)位亦渗，之后還在明尼蘇達(dá)大學(xué)獲得了計算機(jī)科學(xué)博士學(xué)位。博士后期間汁尺，他在愛丁堡大學(xué)研究語言學(xué)法精。正是基于廣博的學(xué)識，他不僅在新墨西哥州立大學(xué)的計算研究實(shí)驗(yàn)室工作痴突，期間還接觸過自然語言處理相關(guān)的項目搂蜓，而該實(shí)驗(yàn)室曾被《連線》雜志評為機(jī)器翻譯研究領(lǐng)域翹楚。除此之外辽装，他還曾教授計算機(jī)科學(xué)帮碰、語言學(xué)、音樂等課程拾积，是一名博學(xué)多才的科技達(dá)人殉挽。

3.內(nèi)容簡介

本書是寫給程序員的一本數(shù)據(jù)挖掘指南，可以幫助讀者動手實(shí)踐數(shù)據(jù)挖掘拓巧、集體智慧并構(gòu)建推薦系統(tǒng)斯碌。全書共8章，介紹了數(shù)據(jù)挖掘的基本知識和理論玲销、協(xié)同過濾输拇、內(nèi)容過濾及分類摘符、算法評估贤斜、樸素貝葉斯、非結(jié)構(gòu)化文本分類以及聚類等內(nèi)容逛裤。本書采用“在實(shí)踐中學(xué)習(xí)”的方式瘩绒，用生動的圖示、大量的表格带族、簡明的公式锁荔、實(shí)用的Python代碼示例，闡釋數(shù)據(jù)挖掘的知識和技能蝙砌。每章還給出了習(xí)題和練習(xí)阳堕，幫助讀者鞏固所學(xué)的知識跋理。

4.案例

假設(shè)我們現(xiàn)在要為一個在線音樂網(wǎng)站的用戶推薦樂隊。用戶可以用1至5星來評價一個樂隊恬总，其中包含半星（如2.5星）前普。下表展示了8位用戶對8支樂隊的評價：

在Python中，我們可以用多種方式來描述上表中的數(shù)據(jù)壹堰，這里選擇Python的字典類型（或者稱為關(guān)聯(lián)數(shù)組拭卿、哈希表）。

users = {"Angelica": {"Blues Traveler": 3.5, "Broken Bells": 2.0, "Norah Jones": 4.5, "Phoenix": 5.0, "Slightly Stoopid": 1.5, "The Strokes": 2.5, "Vampire Weekend": 2.0},
         "Bill":{"Blues Traveler": 2.0, "Broken Bells": 3.5, "Deadmau5": 4.0, "Phoenix": 2.0, "Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
         "Chan": {"Blues Traveler": 5.0, "Broken Bells": 1.0, "Deadmau5": 1.0, "Norah Jones": 3.0, "Phoenix": 5, "Slightly Stoopid": 1.0},
         "Dan": {"Blues Traveler": 3.0, "Broken Bells": 4.0, "Deadmau5": 4.5, "Phoenix": 3.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 2.0},
         "Hailey": {"Broken Bells": 4.0, "Deadmau5": 1.0, "Norah Jones": 4.0, "The Strokes": 4.0, "Vampire Weekend": 1.0},
         "Jordyn":  {"Broken Bells": 4.5, "Deadmau5": 4.0, "Norah Jones": 5.0, "Phoenix": 5.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 4.0},
         "Sam": {"Blues Traveler": 5.0, "Broken Bells": 2.0, "Norah Jones": 3.0, "Phoenix": 5.0, "Slightly Stoopid": 4.0, "The Strokes": 5.0},
         "Veronica": {"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0, "Slightly Stoopid": 2.5, "The Strokes": 3.0}
        }

可以用以下方式來獲取某個用戶的評分：

users["Veronica"]
Out[3]: 
{'Blues Traveler': 3.0,
 'Norah Jones': 5.0,
 'Phoenix': 4.0,
 'Slightly Stoopid': 2.5,
 'The Strokes': 3.0}

計算曼哈頓距離

曼哈頓距離就是：

$|x_1- x_2|+|y_1- y_2|$

如果用數(shù)學(xué)方法計算Hailey與Veronica的曼哈頓距離,那么結(jié)果又是多少呢?

	Veronica	distance	distance
Blues Traveler	-	3
Broken bells	4	-
Deadmau	1	-
Norah Jones	4	5	1
Phoenix	-	4
Slightly Stoopid	-	2.5
The Strokes	4	3	1
Vampire Weekend	1	-

最后距離即是上方數(shù)據(jù)的加和：(1+ 1)=2贱纠。

那么又如何用代碼來表示以上的計算過程呢?具體如下:


def manhattan(rating1, rating2):
    """計算曼哈頓距離峻厚。rating1和rating2參數(shù)中存儲的數(shù)據(jù)格式均為
    {'The Strokes': 3.0, 'Slightly Stoopid': 2.5}"""
    distance=0
    for key in rating1:
        if key in rating2:
            distance += abs(rating1[key]-rating2[key])
    return distance

測試及其結(jié)果如下:

>>> manhattan(users['Hailey'], users['Veronica'])
2.0
>>> manhattan(users['Hailey'], users['Jordyn'])
7.5
>>>

下面我們編寫一個函數(shù)來找出距離最近的用戶（其實(shí)該函數(shù)會返回一個用戶列表，按距離排序）：

def computeNearestNeighbor(username, users):
    """計算所有用戶至username用戶的距離谆焊，倒序排列并返回結(jié)果列表"""
    distances=[]
    for user in users:
        if user !=username:
            distance=manhattan(users[user],users[username])
            distances.append((distance,user))
            distances.sort()
    return distances

測試結(jié)果及其代碼如下:

computeNearestNeighbor("Hailey", users)
Out[21]: 
[(2.0, 'Veronica'),
 (4.0, 'Chan'),
 (4.0, 'Sam'),
 (4.5, 'Dan'),
 (5.0, 'Angelica'),
 (5.5, 'Bill'),
 (7.5, 'Jordyn')]

假設(shè)我想為Hailey做推薦惠桃，這里我找到了離他距離最近的用戶Veronica。然后懊渡，我會找到出Veronica評價過但Hailey沒有評價的樂隊刽射，并假設(shè)Hailey對這些陌生樂隊的評價會和Veronica相近。

比如剃执，Hailey沒有評價過Phoenix樂隊誓禁，而Veronica對這個樂隊打出了4分，所以我們認(rèn)為Hailey也會喜歡這支樂隊肾档。下面的函數(shù)就實(shí)現(xiàn)了這一邏輯：

def recommend(username, users):
    """返回推薦結(jié)果列表"""
    # 找到距離最近的用戶
    recommendations = []
    nearest= computeNearestNeighbor(username, users)[0][1]
    # 找出這位用戶評價過摹恰、但自己未曾評價的樂隊
    for artist in users[nearest]:
        if artist not in users[username]:
            recommendations.append((artist,users[nearest][artist]))
    # 按照評分進(jìn)行排序
    return sorted(recommendations,key=lambda  recommendations:recommendations[:][1],reverse = True)

可以用它來為Hailey做推薦了：

recommend('Hailey', users)
Out[31]: [('Phoenix', 4.0), ('Blues Traveler', 3.0), ('Slightly Stoopid', 2.5)]

運(yùn)行結(jié)果和我們的預(yù)期相符。我們看可以看到怒见，和Hailey距離最近的用戶是Veronica俗慈，Veronica對Phoenix樂隊打了4分。我們再試試其他人：

recommend('Chan', users)
Out[32]: [('The Strokes', 4.0), ('Vampire Weekend', 1.0)]

recommend('Sam', users)
Out[33]: [('Deadmau5', 1.0)]

我們可以猜想Chan會喜歡The Strokes樂隊遣耍，而Sam不會太欣賞Deadmau5闺阱。

作業(yè):實(shí)現(xiàn)一個計算閔可夫斯基距離的函數(shù)，并在計算用戶距離時使用它舵变。

我們可以將曼哈頓距離和歐幾里得距離歸納成一個公式酣溃，這個公式稱為閔可夫斯基距離：

其中：

r = 1 該公式即曼哈頓距離
r = 2 該公式即歐幾里得距離
r = ∞ 極大距離

def minkowski(rating1, rating2, r):
    distance = 0
    for key in rating1:
        if key in rating2:
            distance += pow(abs(rating1[key] - rating2[key]), r)
    return pow(distance, 1.0 / r)

備注:
修改computeNearestNeighbor函數(shù)中的一行
distance = minkowski(users[user], users[username], 2)
這里2表示使用歐幾里得距離

5.本例完整代碼

users = {"Angelica": {"Blues Traveler": 3.5, "Broken Bells": 2.0, "Norah Jones": 4.5, "Phoenix": 5.0, "Slightly Stoopid": 1.5, "The Strokes": 2.5, "Vampire Weekend": 2.0},
         "Bill":{"Blues Traveler": 2.0, "Broken Bells": 3.5, "Deadmau5": 4.0, "Phoenix": 2.0, "Slightly Stoopid": 3.5, "Vampire Weekend": 3.0},
         "Chan": {"Blues Traveler": 5.0, "Broken Bells": 1.0, "Deadmau5": 1.0, "Norah Jones": 3.0, "Phoenix": 5, "Slightly Stoopid": 1.0},
         "Dan": {"Blues Traveler": 3.0, "Broken Bells": 4.0, "Deadmau5": 4.5, "Phoenix": 3.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 2.0},
         "Hailey": {"Broken Bells": 4.0, "Deadmau5": 1.0, "Norah Jones": 4.0, "The Strokes": 4.0, "Vampire Weekend": 1.0},
         "Jordyn":  {"Broken Bells": 4.5, "Deadmau5": 4.0, "Norah Jones": 5.0, "Phoenix": 5.0, "Slightly Stoopid": 4.5, "The Strokes": 4.0, "Vampire Weekend": 4.0},
         "Sam": {"Blues Traveler": 5.0, "Broken Bells": 2.0, "Norah Jones": 3.0, "Phoenix": 5.0, "Slightly Stoopid": 4.0, "The Strokes": 5.0},
         "Veronica": {"Blues Traveler": 3.0, "Norah Jones": 5.0, "Phoenix": 4.0, "Slightly Stoopid": 2.5, "The Strokes": 3.0}
        }

def manhattan(rating1, rating2):
    """計算曼哈頓距離。rating1和rating2參數(shù)中存儲的數(shù)據(jù)格式均為
    {'The Strokes': 3.0, 'Slightly Stoopid': 2.5}"""
    distance=0
    for key in rating1:
        if key in rating2:
            distance += abs(rating1[key]-rating2[key])
    return distance

def computeNearestNeighbor(username, users):
    """計算所有用戶至username用戶的距離纪隙，倒序排列并返回結(jié)果列表"""
    distances=[]
    for user in users:
        if user !=username:
            distance=manhattan(users[user],users[username])
            distances.append((distance,user))
            distances.sort()
    return distances
        
def recommend(username, users):
    """返回推薦結(jié)果列表"""
    # 找到距離最近的用戶
    recommendations = []
    nearest= computeNearestNeighbor(username, users)[0][1]
    # 找出這位用戶評價過赊豌、但自己未曾評價的樂隊
    for artist in users[nearest]:
        if artist not in users[username]:
            recommendations.append((artist,users[nearest][artist]))
    # 按照評分進(jìn)行排序
    return sorted(recommendations,key=lambda  recommendations:recommendations[:][1],reverse = True)
    
def minkowski(rating1, rating2,r):
    distance=0
    for key in rating1:
        if key in rating2:
            distance += pow(abs(rating1[key]-rating2[key]),r)
    return pow(distance,1.0/r)