|
基于用戶的最近鄰算法（User-Based Neighbor Algorithms），是一種非概率性的協(xié)同過(guò)濾算法，也是推薦系統(tǒng)中最最古老，最著名的算法，我們稱那些興趣相似的用戶為鄰居，如果用戶n相似于用戶u，我們就說(shuō)n是u的一個(gè)鄰居。起初算法，對(duì)于未知目標(biāo)的預(yù)測(cè)是根據(jù)該用戶的相似用戶的評(píng)分作出預(yù)測(cè)的 本文中以電影推薦為例： 假設(shè)有7個(gè)人像向你分別推薦了電影，你是其中的小明，你自己也看過(guò)一些電影，你自己看過(guò)的不想看，只想看沒有看過(guò)的，且推薦度高，評(píng)分高的電影，示例數(shù)據(jù)如下： { '小明':{ '中國(guó)合伙人':5, '太平輪':3, '荒野獵人':4.5, '老炮兒':5, '我的少女時(shí)代':3, '肖洛特?zé)?:4.5, '火星救援':5 }, '小紅':{ '小時(shí)代4':4, '荒野獵人':3, '我的少女時(shí)代':5, '肖洛特?zé)?:5, '火星救援':3, '后會(huì)無(wú)期':3 }, '小陽(yáng)':{ '小時(shí)代4':2, '中國(guó)合伙人':5, '我的少女時(shí)代':3, '老炮兒':5, '肖洛特?zé)?:4.5, '速度與激情7':5 }, '小四':{ '小時(shí)代4':5, '中國(guó)合伙人':3, '我的少女時(shí)代':4, '匆匆那年':4, '速度與激情7':3.5, '火星救援':3.5, '后會(huì)無(wú)期':4.5 }, '六爺':{ '小時(shí)代4':2, '中國(guó)合伙人':4, '荒野獵人':4.5, '老炮兒':5, '我的少女時(shí)代':2 }, '小李':{ '荒野獵人':5, '盜夢(mèng)空間':5, '我的少女時(shí)代':3, '速度與激情7':5, '蟻人':4.5, '老炮兒':4, '后會(huì)無(wú)期':3.5 }, '隔壁老王':{ '荒野獵人':5, '中國(guó)合伙人':4, '我的少女時(shí)代':1, 'Phoenix':5, '甄嬛傳':4, 'The Strokes':5 }, '鄰村小芳':{ '小時(shí)代4':4, '我的少女時(shí)代':4.5, '匆匆那年':4.5, '甄嬛傳':2.5, 'The Strokes':3 } } 這里我們需要用到一個(gè)公式：皮爾遜公式 假設(shè)有兩個(gè)變量X、Y，那么兩變量間的皮爾遜相關(guān)系數(shù)可通過(guò)以下公式計(jì)算： 公式一：
皮爾遜相關(guān)系數(shù)計(jì)算公式 公式二：
皮爾遜相關(guān)系數(shù)計(jì)算公式 公式三：
皮爾遜相關(guān)系數(shù)計(jì)算公式 公式四：
皮爾遜相關(guān)系數(shù)計(jì)算公式 以上列出的四個(gè)公式等價(jià)，其中E是數(shù)學(xué)期望，cov表示協(xié)方差，N表示變量取值的個(gè)數(shù) 皮爾遜算法過(guò)于復(fù)雜，如果要有點(diǎn)理解的話，可以使用把維數(shù)降到二維，這樣就跟余弦定理有點(diǎn)相識(shí)了，相識(shí)度就是兩條直線的夾角，角度為0的時(shí)候，皮爾遜的值為1，就是最相識(shí)的，如果角度為180度，代表兩個(gè)牛馬不相干，皮爾遜的值為-1。 皮爾遜相關(guān)系數(shù)是比歐幾里德距離更加復(fù)雜的可以判斷人們興趣的相似度的一種方法。該相關(guān)系數(shù)是判斷兩組數(shù)據(jù)與某一直線擬合程序的一種試題。它在數(shù)據(jù)不是很規(guī)范的時(shí)候，會(huì)傾向于給出更好的結(jié)果。 如圖，Mick Lasalle為<<Superman>>評(píng)了3分，而Gene Seyour則評(píng)了5分，所以該影片被定位中圖中的(3,5)處。在圖中還可以看到一條直線。其繪制原則是盡可能地靠近圖上的所有坐標(biāo)點(diǎn)，被稱為最佳擬合線。如果兩位評(píng)論者對(duì)所有影片的評(píng)分情況都相同，那么這條直線將成為對(duì)角線，并且會(huì)與圖上所有的坐標(biāo)點(diǎn)都相交，從而得到一個(gè)結(jié)果為1的理想相關(guān)度評(píng)價(jià)。 PYTHON實(shí)現(xiàn)： 此處我以python代碼為例向大家展示，文末附上java代碼的實(shí)現(xiàn) # 構(gòu)造一份打分?jǐn)?shù)據(jù)集，可以去movielens下載真實(shí)的數(shù)據(jù)做實(shí)驗(yàn) users = {'小明': {'中國(guó)合伙人': 5.0, '太平輪': 3.0, '荒野獵人': 4.5, '老炮兒': 5.0, '我的少女時(shí)代': 3.0, '肖洛特?zé)?: 4.5, '火星救援': 5.0}, '小紅': {'小時(shí)代4': 4.0, '荒野獵人': 3.0, '我的少女時(shí)代': 5.0, '肖洛特?zé)?: 5.0, '火星救援': 3.0, '后會(huì)無(wú)期': 3.0}, '小陽(yáng)': {'小時(shí)代4': 2.0, '中國(guó)合伙人': 5.0, '我的少女時(shí)代': 3.0, '老炮兒': 5.0, '肖洛特?zé)?: 4.5, '速度與激情7': 5.0}, '小四': {'小時(shí)代4': 5.0, '中國(guó)合伙人': 3.0, '我的少女時(shí)代': 4.0, '匆匆那年': 4.0, '速度與激情7': 3.5, '火星救援': 3.5, '后會(huì)無(wú)期': 4.5}, '六爺': {'小時(shí)代4': 2.0, '中國(guó)合伙人': 4.0, '荒野獵人': 4.5, '老炮兒': 5.0, '我的少女時(shí)代': 2.0}, '小李': {'荒野獵人': 5.0, '盜夢(mèng)空間': 5.0, '我的少女時(shí)代': 3.0, '速度與激情7': 5.0, '蟻人': 4.5, '老炮兒': 4.0, '后會(huì)無(wú)期': 3.5}, '隔壁老王': {'荒野獵人': 5.0, '中國(guó)合伙人': 4.0, '我的少女時(shí)代': 1.0, 'Phoenix': 5.0, '甄嬛傳': 4.0, 'The Strokes': 5.0}, '鄰村小芳': {'小時(shí)代4': 4.0, '我的少女時(shí)代': 4.5, '匆匆那年': 4.5, '甄嬛傳': 2.5, 'The Strokes': 3.0} } # 定義幾種距離計(jì)算函數(shù) # 更高效的方式為把得分向量化之后使用scipy中定義的distance方法
from math import sqrt
def pearson_dis(rating1, rating2): '''計(jì)算2個(gè)打分序列間的pearson距離. 輸入的rating1和rating2都是打分dict 格式為{'小時(shí)代4': 1.0, '瘋狂動(dòng)物城': 5.0}''' sum_xy = 0 sum_x = 0 sum_y = 0 sum_x2 = 0 sum_y2 = 0 n = 0 for key in rating1: if key in rating2: n += 1 x = rating1[key] y = rating2[key]
sum_xy += x * y sum_x += x sum_y += y sum_x2 += pow(x, 2) sum_y2 += pow(y, 2) # now compute denominator denominator = sqrt(sum_x2 - pow(sum_x, 2) / n) * sqrt(sum_y2 - pow(sum_y, 2) / n) if denominator == 0: return 0 else: return (sum_xy - (sum_x * sum_y) / n) / denominator
# 查找最近鄰 def computeNearestNeighbor(username, users): '''在給定username的情況下，計(jì)算其他用戶和它的距離并排序''' print('查找最近鄰') distances = for user in users: if user != username: # distance = manhattan_dis(users[user], users[username])
distance = pearson_dis(users[user], users[username]) distances.append((distance, user)) # 根據(jù)距離排序，距離越近，排得越靠前 distances.sort print('distances => ', distances) return distances
# 推薦 def recommend(username, users): print('輸入=》', username) '''對(duì)指定的user推薦電影''' # 找到最近鄰 nearest = computeNearestNeighbor(username, users)[0][1]
recommendations = # 找到最近鄰看過(guò)，但是我們沒看過(guò)的電影，計(jì)算推薦 neighborRatings = users[nearest]
print('nearest -> ', nearest) print('neighborRatings -> ', neighborRatings)
userRatings = users[username]
print('userRatings -> ', userRatings) for artist in neighborRatings: if not artist in userRatings: recommendations.append((artist, neighborRatings[artist])) print('recommendations -> ', recommendations) results = sorted(recommendations, key=lambda artistTuple: artistTuple[1], reverse=True) for result in results: print(result[0], result[1])
if __name__ == '__main__': recommend('小明', users) 運(yùn)行效果如下： JAVA實(shí)現(xiàn)： 1.數(shù)據(jù)集合類 import java.util.ArrayList; import java.util.List;
/** * Created by ccwant on 2018-12-14. */ public class UserSet {
public List<User> users = new ArrayList<>;
public UserSet { }
public User put(String username) { return new User(username); }
public User getUser(int position) { return users.get(position); }
public User getUser(String username) { for (User user : users) { if (user.username.equals(username)) { return user; } } return null; }
public final class User { public String username; public List<Set> list = new ArrayList<>;
private User(String username) { this.username = username; }
public User set(String username, int score) { this.list.add(new Set(username, score)); return this; }
public void create { users.add(this); }
public Set find(String username) { for (Set set : list) { if (set.username.equals(username)) { return set; } } return null; }
@Override public String toString { return 'User{' + 'username='' + username + '\'' + '}'; } }
public final class Set implements Comparable<Set> { public String username; public int score;
public Set(String username, int score) { this.username = username; this.score = score; }
@Override public String toString { return 'Set{' + 'username='' + username + '\'' + ', score=' + score + '}'; }
@Override public int compareTo(Set o) { return score > o.score ? -1 : 1; } }
} 2. 核心算法 import java.util.*;
/** * Created by ccwant on 2018-12-14. */ public class Recommend {
/** * 在給定username的情況下，計(jì)算其他用戶和它的距離并排序 * @param username * @param set * @return */ private Map<Double, String> computeNearestNeighbor(String username, UserSet set) { Map<Double, String> distances = new TreeMap<>;
UserSet.User u1 = set.getUser(username); for (int i = 0; i < set.users.size; i++) { UserSet.User u2 = set.getUser(i);
if (!u2.username.equals(username)) { double distance = pearson_dis(u2.list, u1.list); distances.put(distance, u2.username); }
} System.out.println('distance => ' + distances); return distances; }
/** * 計(jì)算2個(gè)打分序列間的pearson距離 * * @param rating1 * @param rating2 * @return */ private double pearson_dis(List<UserSet.Set> rating1, List<UserSet.Set> rating2) { int sum_xy = 0; int sum_x = 0; int sum_y = 0; double sum_x2 = 0; double sum_y2 = 0; int n = 0; for (int i = 0; i < rating1.size; i++) { UserSet.Set key1 = rating1.get(i); for (int j = 0; j < rating2.size; j++) { UserSet.Set key2 = rating2.get(j); if (key1.username.equals(key2.username)) { n += 1; int x = key1.score; int y = key2.score; sum_xy += x * y; sum_x += x; sum_y += y; sum_x2 += Math.pow(x, 2); sum_y2 += Math.pow(y, 2); }
} } double denominator = Math.sqrt(sum_x2 - Math.pow(sum_x, 2) / n) * Math.sqrt(sum_y2 - Math.pow(sum_y, 2) / n); if (denominator == 0) { return 0; } else { return (sum_xy - (sum_x * sum_y) / n) / denominator; } }
public List<UserSet.Set> recommend(String username, UserSet set) { //找到最近鄰 Map<Double, String> distances = computeNearestNeighbor(username, set); String nearest = distances.values.iterator.next; System.out.println('nearest -> ' + nearest);
List<UserSet.Set> recommendations = new ArrayList<>;
//找到最近鄰看過(guò)，但是我們沒看過(guò)的電影，計(jì)算推薦 UserSet.User neighborRatings = set.getUser(nearest); System.out.println('neighborRatings -> ' + neighborRatings.list);
UserSet.User userRatings = set.getUser(username); System.out.println('userRatings -> ' + userRatings.list);
for (UserSet.Set artist : neighborRatings.list) { if (userRatings.find(artist.username) == null) { recommendations.add(artist); } } Collections.sort(recommendations); System.out.println('recommendations -> ' + recommendations.toString); return recommendations; }
} 3.測(cè)試類 import sys.Recommend; import sys.UserSet;
import java.util.*;
/** * Created by ccwant on 2018-12-14. */ public class Demo {
public static void main(String args) {
//輸入用戶總量 UserSet userSet = new UserSet; userSet.put('小明') .set('中國(guó)合伙人', 50) .set('太平輪', 30) .set('荒野獵人', 45) .set('老炮兒', 50) .set('我的少女時(shí)代', 30) .set('肖洛特?zé)?, 45) .set('火星救援', 50) .create;
userSet.put('小紅') .set('小時(shí)代4', 40) .set('荒野獵人', 30) .set('我的少女時(shí)代', 50) .set('肖洛特?zé)?, 50) .set('火星救援', 30) .set('后會(huì)無(wú)期', 30) .create;
userSet.put('小陽(yáng)') .set('小時(shí)代4', 20) .set('中國(guó)合伙人', 50) .set('我的少女時(shí)代', 30) .set('老炮兒', 50) .set('肖洛特?zé)?, 45) .set('速度與激情7', 50) .create;
userSet.put('小四') .set('小時(shí)代4', 50) .set('中國(guó)合伙人', 30) .set('我的少女時(shí)代', 40) .set('匆匆那年', 40) .set('速度與激情7', 35) .set('火星救援', 35) .set('后會(huì)無(wú)期', 45) .create;
userSet.put('六爺') .set('小時(shí)代4', 20) .set('中國(guó)合伙人', 40) .set('荒野獵人', 45) .set('老炮兒', 50) .set('我的少女時(shí)代', 20) .create;
userSet.put('小李') .set('荒野獵人', 50) .set('盜夢(mèng)空間', 50) .set('我的少女時(shí)代', 30) .set('速度與激情7', 50) .set('蟻人', 45) .set('老炮兒', 40) .set('后會(huì)無(wú)期', 35) .create;
userSet.put('隔壁老王') .set('荒野獵人', 50) .set('中國(guó)合伙人', 40) .set('我的少女時(shí)代', 10) .set('Phoenix', 50) .set('甄嬛傳', 40) .set('The Strokes', 50) .create;
userSet.put('鄰村小芳') .set('小時(shí)代4', 40) .set('我的少女時(shí)代', 45) .set('匆匆那年', 45) .set('甄嬛傳', 25) .set('The Strokes', 30) .create;
Recommend recommend = new Recommend; List<UserSet.Set> recommendations = recommend.recommend('小明', userSet); System.out.println(''); for (UserSet.Set set : recommendations) { System.out.println(set.username+' '+set.score); } }
} 運(yùn)行結(jié)果：  |
|
|
