1:聯系使用者興趣和物品的方式
2:标簽系統的典型代表
3:使用者如何打标簽
4:基于标簽的推薦系統
5:算法的改進
6:标簽推薦
源代碼檢視位址:github檢視
一:聯系使用者興趣和物品的方式
推薦系統的目的是聯系使用者的興趣和物品,這種聯系方式需要依賴不同的媒介。目前流行的推薦系統基本上是通過三種方式聯系使用者興趣和物品。
1:利用使用者喜歡過的物品,給使用者推薦與他喜歡過的物品相似的物品,即基于item的系統過濾推薦算法(算法分析可參考:點選閱讀)
2:利用使用者和興趣使用者興趣相似的其他使用者,給使用者推薦哪些和他們興趣愛好相似的其他使用者喜歡的物品,即基于User的協同過濾推薦算法(算法分析可參考:點選閱讀)
3:通過一些特征聯系使用者和物品,給使用者推薦那些具有使用者喜歡的特征的物品,這裡的特征有不同的表現形式,比如可以表現為物品的屬性集合,也可以表現為隐語義向量,而下面我們要讨論的是一種重要的特征表現形式——标簽
二:标簽系統的典型代表
比如說豆瓣圖書(左),網易雲音樂(右)
标簽系統确實能夠幫助使用者發現他們喜歡和感興趣的物品
三:使用者如何打标簽
在網際網路中每個人的行為都是随機的,但其實這些表面的行為隐藏着很多規律,那麼我們對使用者打的标簽進行統計呢,便引入了标簽流行度,我們定義的一個标簽被一個使用者使用在一個物品上,他的流行度就加1,可以如下代碼實作:
#統計标簽流行度
def TagPopularity(records):
tagfreq = dict()
for user, item ,tag in records:
if tag not in tagfreq:
tagfreq[tag] = 1
else:
tagfreq[tag] +=1
return tagfreq
下面的是一個标簽流行度分布圖(橫坐标是标簽流行度K,縱坐标是流行度K對應的标簽數目),其也是符合典型的長尾分布,他的雙對數曲線幾乎是一條直線
在使用者看到一個物品時,我們希望他打的标簽是能夠準确的描述物品内容屬性的關鍵詞,但使用者往往不是按照我們的想法操作,而是可能給物品打上各種各樣奇奇怪怪的标簽,此時便需要我們人工編輯一些特定的标簽供使用者選擇,Scott A. Golder 總結了Delicious上的标簽,将它們分為如下幾類。
表明物品是什麼 比如是一隻鳥,就會有“鳥”這個詞的标簽;是豆瓣的首頁,就有一個标簽叫“豆瓣”;是喬布斯的首頁,就會有個标簽叫“喬布斯”。
表明物品的種類 比如在Delicious的書簽中,表示一個網頁類别的标簽包括 article(文章)、blog(部落格)、 book(圖書)等。
表明誰擁有物品 比如很多部落格的标簽中會包括部落格的作者等資訊。
表達使用者的觀點 比如使用者認為網頁很有趣,就會打上标簽funny(有趣),認為很無聊,就會打上标簽boring(無聊)。
使用者相關的标簽 比如 my favorite(我最喜歡的)、my comment(我的評論)等。
使用者的任務 比如 to read(即将閱讀)、job search(找工作)
比如在豆瓣上,标簽便被分為如下幾個類别
四:基于标簽的推薦系統
使用者用标簽來描述對物品的看法,是以标簽是聯系使用者和物品的紐帶,也是反應使用者興趣的重要資料源,如何利用使用者的标簽資料提高個性化推薦結果的品質是推薦系統研究的重要課題。
豆瓣很好地利用了标簽資料,它将标簽系統融入到了整個産品線中。
首先,在每本書的頁面上,豆瓣都提供了一個叫做“豆瓣成員常用标簽”的應用,它給出了這本書上使用者最常打的标簽。
同時,在使用者給書做評價時,豆瓣也會讓使用者給圖書打标簽。
最後,在最終的個性化推薦結果裡,豆瓣利用标簽将使用者的推薦結果做了聚類,顯示了對不同标簽下使用者的推薦結果,進而增加了推薦的多樣性和可解釋性。
一個使用者标簽行為的資料集一般由一個三元組的集合表示,其中記錄(u, i, b) 表示 使用者u 給 物品i 打上了 标簽b。當然,使用者的真實标簽行為資料遠遠比三元組表示的要複雜,比如使用者打标簽的時間、使用者的屬性資料、物品的屬性資料等。但是為了集中讨論标簽資料,隻考慮上面定義的三元組形式的資料,即使用者的每一次打标簽行為都用一個三元組(使用者、物品、标簽)表示。
1:試驗設定
本節将資料集随機分成10份。這裡分割的鍵值是使用者和物品,不包括标簽。也就是說,使用者對物品的多個标簽記錄要麼都被分進訓練集,要麼都被分進測試集,不會一部分在訓練集,另一部分在測試集中。然後,我們挑選1份作為測試集,剩下的9份作為訓練集,通過學習訓練集中的使用者标簽資料預測測試集上使用者會給什麼物品打标簽。對于使用者u,令R(u)為給使用者u的長度為N的推薦清單,裡面包含我們認為使用者會打标簽的物品。令T(u)是測試集中使用者u實際上打過标簽的物品集合。然後,我們利用準确率(precision)和召回率(recall)評測個性化推薦算法的精度。
将上面的實驗進行10次,每次選擇不同的測試集,然後将每次實驗的準确率和召回率的平均值作為最終的評測結果。為了全面評測個性化推薦的性能,我們同時評測了推薦結果的覆寫率(coverage)、多樣性(diversity)和新穎度。覆寫率的計算公式如下:
接下來我們用物品标簽向量的餘弦相似度度量物品之間的相似度。對于每個物品i,item_tags[i]存儲了物品i的标簽向量,其中item_tags[i][b]是對物品i打标簽b的次數,那麼物品i和j的餘弦相似度可以通過如下程式計算。
#計算餘弦相似度
def CosineSim(item_tags,i,j):
ret = 0
for b,wib in item_tags[i].items(): #求物品i,j的标簽交集數目
if b in item_tags[j]:
ret += wib * item_tags[j][b]
ni = 0
nj = 0
for b, w in item_tags[i].items(): #統計 i 的标簽數目
ni += w * w
for b, w in item_tags[j].items(): #統計 j 的标簽數目
nj += w * w
if ret == 0:
return 0
return ret/math.sqrt(ni * nj) #傳回餘弦值
在得到物品之間的相似度度量後,我們可以用如下公式計算一個推薦清單的多樣性:
Python實作為:
#計算推薦清單多樣性
def Diversity(item_tags,recommend_items):
ret = 0
n = 0
for i in recommend_items.keys():
for j in recommend_items.keys():
if i == j:
continue
ret += CosineSim(item_tags,i,j)
n += 1
return ret/(n * 1.0)
推薦系統的多樣性為所有使用者推薦清單多樣性的平均值。
至于推薦結果的新穎性,我們簡單地用推薦結果的平均熱門程度(AveragePopularity)度量。對于物品i,定義它的流行度item_pop(i)為給這個物品打過标簽的使用者數。而對推薦系統,我們定義它的平均熱門度如下:
2:一個簡單的算法
拿到了使用者标簽行為資料,相信大家都可以想到一個最簡單的個性化推薦算法。這個算法的
描述如下所示。
統計每個使用者最常用的标簽。
對于每個标簽,統計被打過這個标簽次數最多的物品。
對于一個使用者,首先找到他常用的标簽,然後找到具有這些标簽的最熱門物品推薦給這個使用者。
對于上面的算法,使用者u對物品i的興趣公式如下:
這裡,B(u)是使用者u打過的标簽集合,B(i)是物品i被打過的标簽集合,nu,b是使用者u打過标簽b的次數,nb,i是物品i被打過标簽b的次數。本章用SimpleTagBased标記這個算法。
在Python中,我們遵循如下約定:
用 records 存儲标簽資料的三元組,其中records[i] = [user, item, tag];
用 user_tags 存儲nu,b,其中user_tags[u][b] = nu,b;
用 tag_items存儲nb,i,其中tag_items[b][i] = nb,i。
如下程式可以從records中統計出user_tags和tag_items:
#從records中統計出user_tags和tag_items
def InitStat(records):
user_tags = dict()
tag_items = dict()
user_items = dict()
for user, item, tag in records.items():
addValueToMat(user_tags, user, tag, 1)
addValueToMat(tag_items, tag, item, 1)
addValueToMat(user_items, user, item, 1)</span>
統計出user_tags和tag_items之後,我們可以通過如下程式對使用者進行個性化推薦:
#對使用者進行個性化推薦
def Recommend(user):
recommend_items = dict()
tagged_items = user_items[user]
for tag, wut in user_tags[user].items():
for item, wti in tag_items[tag].items():
#if items have been tagged, do not recommend them
if item in tagged_items:
continue
if item not in recommend_items:
recommend_items[item] = wut * wti
else:
recommend_items[item] += wut * wti
return recommend_items
</span>
五:算法的改進
再次回顧四中提出的簡單算法
該算法存在許多缺點,比如說對于熱門商品的處理,資料洗漱性的處理等,這也是在推薦系統中經常會遇見的問題
1:TF-IDF
前面這個公式傾向于給熱門标簽對應的熱門物品很大的權重,是以會造成推薦熱門的物品給使用者,進而降低推薦結果的新穎性。另外,這個公式利用使用者的标簽向量對使用者興趣模組化,其中每個标簽都是使用者使用過的标簽,而标簽的權重是使用者使用該标簽的次數。這種模組化方法的缺點是給熱門标簽過大的權重,進而不能反應使用者個性化的興趣。這裡我們可以借鑒TF-IDF的思想,對這一公式進行改進:
這裡,
記錄了标簽b被多少個不同的使用者使用過。這個算法記為TagBasedTFIDF。
同理,我們也可以借鑒TF-IDF的思想對熱門物品進行懲罰,進而得到如下公式:
其中,
記錄了物品i被多少個不同的使用者打過标簽。這個算法記為TagBasedTF-IDF++。
2:資料稀疏性
在前邊的算法中,使用者興趣和物品的聯系是通過B(u) B(i)交集得到的,但是對于新使用者,這個交集的結果将會非常小,為了提高推薦結果的可靠性,這裡我們要對标簽進行擴充,比如若使用者曾經用過“推薦系統”這個标簽,我們可以将這個标簽的相似标簽也加入到使用者标簽集合中,比如“個性化”、“協同過濾”等标簽。
進行标簽擴充的方法有很多,比如說話題模型(參考部落格),這裡遵循簡單原則介紹一種基于鄰域的方法。
标簽擴充的本質是找到與他相似的标簽,也就是計算标簽之間的相似度。最簡單的相似度可以是同義詞。如果有一個同義詞詞典,就可以根據這個詞典進行标簽擴充。如果沒有這個詞典,我們可以從資料中統計出标簽的相似度。
如果認為同一個物品上的不同标簽具有某種相似度,那麼當兩個标簽同時出現在很多物品的标簽集合中時,我們就可以認為這兩個标簽具有較大的相似度。對于标簽b,令N(b)為有标簽b的物品的集合,n_{b,i}為給物品i打上标簽b的使用者數,我們可以通過如下餘弦相似度公式計算标簽b和标簽b'的相似度:
3:标簽清理
不是所有标簽都能反應使用者的興趣。比如,在一個視訊網站中,使用者可能對一個視訊打了一個表示情緒的标簽,比如“不好笑”,但我們不能是以認為使用者對“不好笑”有興趣,并且給使用者推薦其他具有“不好笑”這個标簽的視訊。相反,如果使用者對視訊打過“成龍”這個标簽,我們可以據此認為使用者對成龍的電影感興趣,進而給使用者推薦成龍其他的電影。同時,标簽系統裡經常出現詞形不同、詞義相同的标簽,比如recommender system和recommendation engine就是兩個同義詞。
标簽清理的另一個重要意義在于将标簽作為推薦解釋。如果我們要把标簽呈現給使用者,将其作為給使用者推薦某一個物品的解釋,對标簽的品質要求就很高。首先,這些标簽不能包含沒有意義的停止詞或者表示情緒的詞,其次這些推薦解釋裡不能包含很多意義相同的詞語。
一般來說有如下标簽清理方法:
去除詞頻很高的停止詞;
去除因詞根不同造成的同義詞,比如 recommender system和recommendation system;
去除因分隔符造成的同義詞,比如 collaborative_filtering和collaborative-filtering。
為了控制标簽的品質,很多網站也采用了讓使用者進行回報的思想,即讓使用者告訴系統某個标簽是否合适。
推薦程式(更新檢視位址:github // 資料集下載下傳):
#!/usr/bin/env python
#-*-coding:utf-8-*-
import random
#統計各類數量
def addValueToMat(theMat,key,value,incr):
if key not in theMat: #如果key沒出先在theMat中
theMat[key]=dict();
theMat[key][value]=incr;
else:
if value not in theMat[key]:
theMat[key][value]=incr;
else:
theMat[key][value]+=incr;#若有值,則遞增
user_tags = dict();
tag_items = dict();
user_items = dict();
user_items_test = dict();#測試集資料字典
#初始化,進行各種統計
def InitStat():
data_file = open('delicious.dat')
line = data_file.readline();
while line:
if random.random()>0.1:#将90%的資料作為訓練集,剩下10%的資料作為測試集
terms = line.split("\t");#訓練集的資料結構是[user, item, tag]形式
user=terms[0];
item=terms[1];
tag=terms[2];
addValueToMat(user_tags,user,tag,1)
addValueToMat(tag_items,tag,item,1)
addValueToMat(user_items,user,item,1)
line = data_file.readline();
else:
addValueToMat(user_items_test,user,item,1)
data_file.close();
#推薦算法
def Recommend(usr):
recommend_list = dict();
tagged_item = user_items[usr];#得到該使用者所有推薦過的物品
for tag_,wut in user_tags[usr].items():#使用者打過的标簽及次數
for item_,wit in tag_items[tag_].items():#物品被打過的标簽及被打過的次數
if item_ not in tagged_item:#已經推薦過的不再推薦
if item_ not in recommend_list:
recommend_list[item_]=wut*wit;#根據公式
else:
recommend_list[item_]+=wut*wit;
return sorted(recommend_list.iteritems(), key=lambda a:a[1],reverse=True)
InitStat()
recommend_list = Recommend("48411")
# print recommend_list
for recommend in recommend_list[:10]: #興趣度最高的十個itemid
print recommend
運作結果:
('912', 610)
('3763', 394)
('52503', 238)
('39051', 154)
('45647', 147)
('21832', 144)
('1963', 143)
('1237', 140)
('33815', 140)
('5136', 138)
六:标簽推薦
當使用者浏覽某個物品時,标簽系統非常希望使用者能夠給這個物品打上高品質的标簽,這樣才能促進标簽系統的良性循環。是以,很多标簽系統都設計了标簽推薦子產品給使用者推薦标簽。
1:為什麼給使用者推薦标簽
友善使用者輸入标簽 讓使用者從鍵盤輸入标簽無疑會增加使用者打标簽的難度,這樣很多使用者不願意給物品打标簽,是以我們需要一個輔助工具來減小使用者打标簽的難度,進而提高使用者打标簽的參與度。
提高标簽品質 同一個語義不同的使用者可能用不同的詞語來表示。這些同義詞會使标簽的詞表變得很龐大,而且會使計算相似度不太準确。而使用推薦标簽時,我們可以對詞表進行選擇,首先保證詞表不出現太多的同義詞,同時保證出現的詞都是一些比較熱門的、有代表性的詞。
2:标簽推薦的四種簡單算法
a:給使用者u推薦整個系統裡最熱門的标簽(這裡将這個算法稱為PopularTags)令tags[b]為标簽b的熱門程度,那麼這個算法的實作如下:
def RecommendPopularTags(user,item, tags, N):
return sorted(tags.items(), key=itemgetter(1), reverse=True)[0:N]
b:給使用者u推薦物品i上最熱門的标簽(這裡将這個算法稱為ItemPopularTags)。令item_tags[i][b]為物品i被打上标簽b的次數
def RecommendItemPopularTags(user,item, item_tags, N):
return sorted(item_tags[item].items(), key=itemgetter(1), reverse=True)[0:N]
c:是給使用者u推薦他自己經常使用的标簽(這裡将這個算法稱為UserPopularTags)。令user_tags[u][b]為使用者u使用标簽b的次數
def RecommendUserPopularTags(user,item, user_tags, N):
return sorted(user_tags[user].items(), key=itemgetter(1), reverse=True)[0:N]
d:前面兩種的融合(這裡記為HybridPopularTags),該方法通過一個系數将上面的推薦結果線性權重,然後生成最終的推薦結果。
def RecommendHybridPopularTags(user,item, user_tags, item_tags, alpha, N):
max_user_tag_weight = max(user_tags[user].values())
for tag, weight in user_tags[user].items():
ret[tag] = (1 – alpha) * weight / max_user_tag_weight
max_item_tag_weight = max(item_tags[item].values())
for tag, weight in item_tags[item].items():
if tag not in ret:
ret[tag] = alpha * weight / max_item_tag_weight
else:
ret[tag] += alpha * weight / max_item_tag_weight
return sorted(ret[user].items(), key=itemgetter(1), reverse=True)[0:N]