上一篇文章《基于使用者的協同過濾算法實踐》中，基于使用者的相似度生成推薦清單，本文将基于Item的相似度闡述。
1 相似度
基于物品的協同過濾算法（簡稱ItemCF）給使用者推薦那些和他們之前喜歡的物品相似的物品。不過ItemCF不是利用物品的内容計算物品之間相似度，而是利用使用者的行為記錄。
該算法認為，物品A和物品B具有很大的相似度是因為喜歡物品A的使用者大都也喜歡物品B。這裡蘊含一個假設，就是每個使用者的興趣都局限在某幾個方面，是以如果兩個物品屬于同一個使用者的興趣清單，那麼這兩個物品可能就屬于有限的幾個領域。而如果兩個物品同時出現在很多使用者的興趣清單，那麼它們可能就屬于同一領域，因而具有很大的相似度。
從上述概念出發，定義物品i和j的相似度為
其中，|N(i)||N(i)|是喜歡物品i的使用者數，|N(i)⋂N(j)||N(i)⋂N(j)|是同時喜歡物品i和物品j的使用者數。分母是懲罰物品i和j的權重，是以懲罰了熱門物品和很多物品相似的可能性。
在ItemCF中，兩個物品産生相似度是因為它們共同出現在很多使用者的興趣清單中。假設有這麼一個使用者，他是開書店的，并且買了當當網上 80% 的書準備用來自己賣。那麼，
他的購物車裡包含當當網 80% 的書。是以這個使用者對于他所購買書的兩兩相似度的貢獻應該遠遠小于一個隻買了十幾本自己喜歡的書的文學青年。
提出一個稱為 IUF （ Inverse User Frequence ），即使用者活躍度對數的倒數的參數，來修正物品相似度的計算公式。認為活躍使用者對物品相似度的貢獻應該小于不活躍的使用者。
2 興趣程度
在得到物品相似度之後，ItemCF通過以下公式計算使用者u對未産生行為的物品j的感興趣程度。
這裡的N(u)N(u)是使用者喜歡的物品集合，S(j,K)S(j,K)是和物品j最相似的K個物品的集合，wijwij是物品j和i的相似度，ruirui是使用者u對物品j的興趣評分（簡單的，如果使用者u對物品i有過行為，即可令ruirui=1）
對于已經得到的物品相似度矩陣w，按照以下公式對w進行按列歸一化，不僅可以增加推薦的準确度，它還可以提高推薦的覆寫率和多樣性。
假設物品分為兩類—— A 和 B ， A 類物品之間的相似度為 0.5 ， B 類物品之間的相似度為 0.6 ，而 A 類物品和 B 類物品之間的相似度是 0.2 。在這種情況下，如果一個使用者喜歡了 5個 A 類物品和 5 個 B 類物品，用 ItemCF 給他進行推薦，推薦的就都是 B 類物品，因為 B 類物品之間的相似度大。但如果歸一化之後， A 類物品之間的相似度變成了 1 ， B 類物品之間的相似度也是 1 ，那麼這種情況下，使用者如果喜歡 5 個 A 類物品和 5 個 B類物品，那麼他的推薦清單中 A 類物品和 B 類物品的數目也應該是大緻相等的。從這個例子可以看出，相似度的歸一化可以提高推薦的多樣性。
一般來說，熱門的類其類内物品相似度一般比較大。如果不進行歸一化，就會推薦比較熱門的類裡面的物品，而這些物品也是比較熱門的。是以，推薦的覆寫率就比較低。相反，如果進行相似度的歸一化，則可以提高推薦系統的覆寫率。
3 電影推薦代碼
1 生成使用者資料集： 使用者， 興趣程度， 物品
{使用者i： {物品1：興趣程度, 物品2：興趣程度， 物品3：興趣程度}}
2 物品被多少個使用者購買
{物品1： 2， 物品2： 5， 物品3： 1}
物品--物品共現矩陣
{物品1 ：{物品2： 2， 物品3： 1}，
物品2： {物品1： 2， 物品3： 2， 物品4： 1}
......
}
3 物品相似度矩陣
物品1 : {物品2： (物品1 和 物品2 共現次數 ) / sqrt(物品1出現的次數 * 物品2出現的次數) }
代碼說明：
代碼中的檔案u.data參考上一篇文章。
import math
from texttable import Texttable
import importlib
import sys
class ItemBasedCF:
def __init__(self, train_file):
self.train_file = train_file
self.readData()
"""
讀取資料，處理成字典格式
生成使用者資料集： 使用者， 興趣程度， 物品
{使用者i： {物品1：興趣程度, 物品2：興趣程度， 物品3：興趣程度}}
"""
def readData(self):
self.train = dict()
#print('train_file:', self.train_file)
for line in self.train_file:
#print('type(line):', type(line))
user, score, item = line.strip().split(",")
self.train.setdefault(user, {})
self.train[user][item] = int(float(score))
"""
N: {物品1： 2， 物品2： 5， 物品3： 1}
C: {
物品1 ： {物品2： 2， 物品3： 1}，
物品2 ： {物品1： 2， 物品3： 2， 物品4： 1}
}
"""
def ItemSimilarity(self):
N = dict() #物品被多少個不同使用者購買
C = dict() #物品和物品的共現矩陣
for user, items in self.train.items():
#print('user:', user)
#print('item:', items)
for ikey in items.keys(): #ikey: {'a': 1, 'b': 1, 'd': 1}
#print('ikey:', ikey)
N.setdefault(ikey, 0)
N[ikey] += 1
C.setdefault(ikey, {})
for jkey in items.keys(): #物品和物品的共現矩陣 jkey: {'a': 1, 'b': 1, 'd': 1}
if ikey==jkey:
continue
#print('jkey:', jkey)
C[ikey].setdefault(jkey, 0)
#C[ikey][jkey] += 1
C[ikey][jkey] += 1 / math.log( 1+len(items)*1.0 ) #用使用者活躍度來修正相似度，len(items)來衡量使用者活躍度
#print('N:', N)
#print('C:', C)
#根據N，C計算物品之間的相似度
#根據C得到物品和物品共現的次數，根據N得到物品分别出現的次數
self.W = dict()
self.W_max = dict() #記錄每一列的最大值
for ikey, relateij in C.items():
#print('ikey:', ikey)
#print('relateij:', relateij)
self.W.setdefault(ikey, {})
for jkey, Wij in relateij.items():
self.W_max.setdefault(jkey, 0.0) #初始化當列最大值為0
self.W[ikey][jkey] = Wij / ( math.sqrt(N[ikey] * N[jkey]) ) #計算相似度
if self.W[ikey][jkey] > self.W_max[jkey]:
self.W_max[jkey] = self.W[ikey][jkey] #更新列中最大值
#print('jkey:', jkey, 'self.W_max:', self.W_max[jkey])
#歸一化處理, Wij / Wij_max
for ikey, relateij in C.items():
for jkey, Wij in relateij.items():
self.W[ikey][jkey] = self.W[ikey][jkey] / self.W_max[jkey]
#for k, v in self.W.items():
#print(k + ':' + str(v))
"""
函數功能：生成推薦清單
函數參數：
@user：需要推薦的使用者
@K ：取物品相似度矩陣前k物品
@N : 最多推薦N個物品
"""
def Recommend(self, user, K=3, N=10):
rank = dict() #推薦字典
action_item = self.train[user] #擷取使用者user的物品和評分資料
for item, score in action_item.items(): #item為使用者購買的物品，score為評分
for j, Wj in sorted(self.W[item].items(), key=lambda x:x[1], reverse = True)[0:K]: #self.W[item].items()為物品item的相似度矩陣
if j in action_item.keys(): #使用者已經購買過的物品，不再推薦
continue
rank.setdefault(j, 0)
rank[j] += (Wj * score) #j為根據相似度推薦的物品，Wj為推薦的物品和使用者的物品item的相似度，score為item的評分
return sorted(rank.items(), key=lambda x:[1], reverse = True)[0:N]
def readFile(filename):
contents = []
f = open(filename, "rb")
contents = f.readlines()
f.close()
return contents
def getRatingInfo(ratings):
rates = []
for line in ratings:
rate = line.split("\t".encode(encoding="utf-8"))
rate_str = str(int(rate[0])) +','+ str(int(rate[2])) +',' + str(int(rate[1]))
rates.append(rate_str)
return rates
#擷取電影的清單
def getMovieList(filename):
contents = readFile(filename)
movies_info = {} #dict
for movie in contents:
single_info = movie.split("|".encode(encoding="utf-8")) #把目前行按|分隔，儲存成list
movies_info[int(single_info[0])] = single_info[1:] #将第0個元素作為key，第二個到最後作為value儲存成字典dict傳回
return movies_info
#uid_score_bid = ['A,1,a','A,1,b','A,1,d','B,1,b','B,1,c','B,1,e','C,1,c','C,1,d','D,1,b','D,1,c','D,1,d','E,1,a','E,1,d']
#擷取所有電影的清單
if __name__ == '__main__':
importlib.reload(sys)
movies = getMovieList("u.item") #movies為dict
#print('movies:', movies)
contents = []
contents = readFile("u.data")
rates = getRatingInfo(contents)
Item = ItemBasedCF(rates)
#print('train:', Item.train)
Item.ItemSimilarity()
recommend_dict = Item.Recommend('50', 5, 20) #k=5, N=20
print('推薦清單：')
recommend_list = []
for k, v in recommend_dict:
print(k + ':' + str(v))
recommend_list.append(int(k))
print(recommend_list)
table = Texttable()
table.set_deco(Texttable.HEADER)
table.set_cols_dtype(['t', 't', 't'])
table.set_cols_align(["l", "l", "l"])
rows=[]
rows.append([u"movie name",u"release", u"from userid"])
for movie_id in recommend_list[:20]:
rows.append([movies[movie_id][0],movies[movie_id][1]," "])
table.add_rows(rows)
print (table.draw())
運作結果：
movie name release from userid
=============================================================
Smilla's Sense of Snow (1997) 14-Mar-1997
Private Parts (1997) 07-Mar-1997
Trees Lounge (1996) 11-Oct-1996
Welcome to the Dollhouse (1995) 24-May-1996
Kansas City (1996) 16-Aug-1996
City Hall (1996) 16-Feb-1996
Chamber, The (1996) 11-Oct-1996
Arrival, The (1996) 31-May-1996
Kama Sutra: A Tale of Love (1996) 07-Mar-1997
Waiting for Guffman (1996) 31-Jan-1997
Daytrippers, The (1996) 21-Mar-1997
Kissed (1996) 18-Apr-1997
City of Lost Children, The (1995) 01-Jan-1995
Swingers (1996) 18-Oct-1996
Mis�rables, Les (1995) 01-Jan-1995
Georgia (1995) 01-Jan-1995
Cry, the Beloved Country (1995) 01-Jan-1995
Street Fighter (1994) 01-Jan-1994
Scarlet Letter, The (1995) 01-Jan-1995
Kolya (1996) 24-Jan-1997 參考文章清單：
《推薦系統實踐》——基于物品的協同過濾算法（代碼實作）