『壹』 鍒╃敤 SVD 瀹炵幇鍗忓悓榪囨護鎺ㄨ崘綆楁硶
濂囧紓鍊煎垎瑙(Singular Value Decomposition錛屼互涓嬬畝縐癝VD)
鏄鍦ㄦ満鍣ㄥ︿範棰嗗煙騫挎硾搴旂敤鐨勭畻娉曪紝瀹冧笉鍏夊彲浠ョ敤浜 闄嶇淮綆楁硶涓鐨勭壒寰佸垎瑙 錛岃繕鍙浠ョ敤浜 鎺ㄨ崘緋葷粺 錛屼互鍙婅嚜鐒惰璦澶勭悊絳夐嗗煙銆
浼樼偣錛 綆鍖栨暟鎹錛屽幓闄ゅ櫔澹幫紝鎻愰珮綆楁硶鐨勭粨鏋溿
緙虹偣錛 鏁版嵁鐨勮漿鎹㈠彲鑳介毦浠ョ悊瑙ｃ
搴旂敤棰嗗煙錛 鎺ㄨ崘寮曟搸錛堝崗鍚岃繃婊ゃ佺浉浼煎害璁＄畻錛夈佸浘鍍忓帇緙╃瓑銆
SVD瀹氫箟錛 濡傛灉鎴戜滑奼傚嚭浜嗙煩闃礎鐨刵涓鐗瑰緛鍊嘉1鈮の2鈮...鈮の籲錛屼互鍙婅繖n涓鐗瑰緛鍊兼墍瀵瑰簲鐨勭壒寰佸悜閲弡w1,w2,...wn}錛屽傛灉榪檔涓鐗瑰緛鍚戦噺綰挎ф棤鍏籌紝閭ｄ箞鐭╅樀A灝卞彲浠ョ敤涓嬪紡鐨勭壒寰佸垎瑙ｈ〃紺猴細A=W危W−1錛屽叾涓璚鏄榪檔涓鐗瑰緛鍚戦噺鎵寮犳垚鐨刵脳n緇寸煩闃碉紝鑰屛ｄ負榪檔涓鐗瑰緛鍊間負涓誨硅掔嚎鐨刵脳n緇寸煩闃點備竴鑸鎴戜滑浼氭妸W鐨勮繖n涓鐗瑰緛鍚戦噺鏍囧噯鍖栵紝鍗蟲弧瓚硘|wi||2=1, 鎴栬厀iTwi=1錛屾ゆ椂W鐨刵涓鐗瑰緛鍚戦噺涓烘爣鍑嗘ｄ氦鍩猴紝婊WTW=I錛屽嵆WT=W−1, 涔熷氨鏄璇碬涓洪厜鐭╅樀銆傝佽繘琛岀壒寰佸垎瑙ｏ紝鐭╅樀A蹇呴』涓烘柟闃點傞偅涔堝傛灉A涓嶆槸鏂歸樀錛屽垯鐢ㄥ埌SVD銆
鐭╅樀A鐨凷VD涓猴細A=U危VT錛屽叾涓璘鏄涓涓猰脳m鐨勭煩闃碉紝危鏄涓涓猰脳n鐨勭煩闃碉紝闄や簡涓誨硅掔嚎涓婄殑鍏冪礌浠ュ栧叏涓0錛屼富瀵硅掔嚎涓婄殑姣忎釜鍏冪礌閮界О涓哄囧紓鍊礆紝V鏄涓涓猲脳n鐨勭煩闃點俇鍜孷閮芥槸閰夌煩闃碉紝鍗蟲弧瓚砋TU=I,VTV=I銆
瀵逛簬濂囧紓鍊,瀹冭窡鎴戜滑鐗瑰緛鍒嗚В涓鐨勭壒寰佸肩被浼礆紝鍦ㄥ囧紓鍊肩煩闃典腑涔熸槸鎸夌収浠庡ぇ鍒板皬鎺掑垪錛岃屼笖濂囧紓鍊肩殑鍑忓皯鐗瑰埆鐨勫揩錛屽湪寰堝氭儏鍐典笅錛屽墠10%鐢氳嚦1%鐨勫囧紓鍊肩殑鍜屽氨鍗犱簡鍏ㄩ儴鐨勫囧紓鍊間箣鍜岀殑99%浠ヤ笂鐨勬瘮渚嬨備篃灝辨槸璇達紝鎴戜滑涔熷彲浠ョ敤鏈澶х殑k涓鐨勫囧紓鍊煎拰瀵瑰簲鐨勫乏鍙沖囧紓鍚戦噺鏉ヨ繎浼兼弿榪扮煩闃點
鍥犳SVD 涔熸槸涓縐嶅己澶х殑闄嶇淮宸ュ叿 錛屽彲浠ュ埄鐢 SVD 鏉ラ艱繎鐭╅樀騫朵粠涓鑾峰緱涓昏佺殑鐗瑰緛銆傞氳繃淇濈暀鐭╅樀鐨 80%~90% 鐨勮兘閲忥紝灝卞彲浠ュ緱鍒伴噸鐢ㄧ殑鐗瑰緛騫跺幓闄ゅ櫔澹般
鎺ㄨ崘緋葷粺 鏄鍒╃敤鐢靛瓙鍟嗗姟緗戠珯鍚戝㈡埛鎻愪緵鍟嗗搧淇℃伅鍜屽緩璁錛屽府鍔╃敤鎴峰喅瀹氬簲璇ヨ喘涔頒粈涔堜駭鍝侊紝妯℃嫙閿鍞浜哄憳甯鍔╁㈡埛瀹屾垚璐涔拌繃紼嬨
涓昏佹湁浠ヤ笅鍑犵嶆帹鑽愮畻娉曪細
鍩轟簬鍐呭圭殑鎺ㄨ崘錛堢敤鍒拌嚜鐒惰璦澶勭悊錛夛紝 鍗忓悓榪囨護錛堜富嫻侊級 錛屽熀浜庤勫垯鎺ㄨ崘錛堝熀浜庢渶澶氱敤鎴風偣鍑伙紝鏈澶氱敤鎴鋒祻瑙堢瓑錛夛紝娣峰悎鎺ㄨ崘錛堢被浼奸泦鎴愮畻娉曪紝鎶曠エ鍐沖畾錛夛紝鍩轟簬浜哄彛緇熻′俊鎮鐨勬帹鑽愶紙鏍規嵁鐢ㄦ埛鍩烘湰淇℃伅錛
鍗忓悓榪囨護鎺ㄨ崘鍒嗕負涓夌嶇被鍨嬨 絎涓縐嶆槸鍩轟簬鐢ㄦ埛(user-based)鐨勫崗鍚岃繃婊わ紙闇瑕佸湪綰挎壘鐢ㄦ埛鍜岀敤鎴蜂箣闂寸殑鐩鎬技搴﹀叧緋伙級錛岀浜岀嶆槸鍩轟簬欏圭洰(item-based)鐨勫崗鍚岃繃婊わ紙鍩轟簬欏圭洰鐨勫崗鍚岃繃婊ゅ彲浠ョ葷嚎鎵劇墿鍝佸拰鐗╁搧涔嬮棿鐨勭浉浼煎害鍏崇郴錛夛紝 絎涓夌嶆槸鍩轟簬妯″瀷(model based)鐨勫崗鍚岃繃婊わ紙鐢ㄦ埛鍜岀墿鍝侊紝涓繪祦錛夈
涓鑸鍦ㄦ帹鑽愮郴緇熶腑錛屾暟鎹寰寰鏄浣跨敤 鐢ㄦ埛-鐗╁搧 鐭╅樀鏉ヨ〃紺虹殑銆 鐢ㄦ埛瀵瑰叾鎺ヨЕ榪囩殑鐗╁搧榪涜岃瘎鍒嗭紝璇勫垎琛ㄧず浜嗙敤鎴峰逛簬鐗╁搧鐨勫枩鐖辯▼搴︼紝鍒嗘暟瓚婇珮錛岃〃紺虹敤鎴瘋秺鍠滄㈣繖涓鐗╁搧銆傝岃繖涓鐭╅樀寰寰鏄紼鐤忕殑錛岀┖鐧介」鏄鐢ㄦ埛榪樻湭鎺ヨЕ鍒扮殑鐗╁搧錛屾帹鑽愮郴緇熺殑浠誨姟鍒欐槸閫夋嫨鍏朵腑鐨勯儴鍒嗙墿鍝佹帹鑽愮粰鐢ㄦ埛銆
瀵逛簬榪欎釜 鐢ㄦ埛-鐗╁搧 鐭╅樀錛岀敤宸叉湁鐨勯儴鍒嗙█鐤忔暟鎹鏉ラ勬祴閭ｄ簺絀虹櫧鐨勭墿鍝佸拰鏁版嵁涔嬮棿鐨勮瘎鍒嗗叧緋伙紝鎵懼埌鏈楂樿瘎鍒嗙殑鐗╁搧鎺ㄨ崘緇欑敤鎴楓
鍏蜂綋鍩轟簬妯″瀷鐨勬柟娉曟湁錛
鐢ㄥ叧鑱旂畻娉曞仛鍗忓悓榪囨護錛圓priori綆楁硶銆丗P Tree綆楁硶錛
鐢ㄨ仛綾葷畻娉曞仛鍗忓悓榪囨護錛堥拡瀵瑰熀浜庣敤鎴鋒垨鑰呭熀浜庢ā鍨嬶紝Kmeans錛孌BSCAN錛
鐢ㄥ垎綾葷畻娉曞仛鍗忓悓榪囨護錛堣懼畾璇勫垎闃堝礆紝楂樹簬鎺ㄨ崘錛屼綆浜庝笉鎺ㄨ崘錛岄昏緫鍥炲綊鍜屾湸緔犺礉鍙舵柉錛岃В閲婃у緢寮猴級
鐢ㄥ洖褰掔畻娉曞仛鍗忓悓榪囨護錛圧idge鍥炲綊錛屽洖褰掓爲錛
鐢ㄧ煩闃靛垎瑙ｅ仛鍗忓悓榪囨護錛堢敱浜庝紶緇熺殑濂囧紓鍊煎垎瑙SVD瑕佹眰鐭╅樀涓嶈兘鏈夌己澶辨暟鎹錛屽繀欏繪槸紼犲瘑鐨勶紝鑰岀敤鎴風墿鍝佽瘎鍒嗙煩闃墊槸涓涓鍏稿瀷鐨勭█鐤忕煩闃碉紝涓昏佹槸SVD鐨勪竴浜涘彉縐嶏紝姣斿侳unkSVD錛孊iasSVD鍜孲VD++銆傝繖浜涚畻娉曞拰浼犵粺SVD鐨勬渶澶у尯鍒鏄涓嶅啀瑕佹眰灝嗙煩闃靛垎瑙ｄ負U危VT鐨勫艦寮忥紝鑰屽彉鏄涓や釜浣庣З鐭╅樀PTQ鐨勪箻縐褰㈠紡銆傦級
鐢ㄧ炵粡緗戠粶鍋氬崗鍚岃繃婊わ紙闄愬埗鐜誨皵鍏規浖鏈篟BM錛
鍦 Python 鐨 numpy 涓錛宭inalg宸茬粡瀹炵幇浜哠VD
『貳』 協同過濾演算法
用戶行為數據在網站上最簡單的存在形式就是日誌，比如用戶在電子商務網站中的網頁瀏覽、購買、點擊、評分和評論等活動。 用戶行為在個性化推薦系統中一般分兩種——顯性反饋行為(explicit feedback)和隱性反饋 行為(implicit feedback)。顯性反饋行為包括用戶明確表示對物品喜好的行為。網站中收集顯性反饋的主要方式就是評分和喜歡/不喜歡。隱性反饋行為指的是那些不能明確反應用戶喜好 的行為。最具代表性的隱性反饋行為就是頁面瀏覽行為。 按照反饋的明確性分，用戶行為數據可以分為顯性反饋和隱性反饋，但按照反饋的方向分， 又可以分為正反饋和負反饋。正反饋指用戶的行為傾向於指用戶喜歡該物品，而負反饋指用戶的 行為傾向於指用戶不喜歡該物品。在顯性反饋中，很容易區分一個用戶行為是正反饋還是負反饋， 而在隱性反饋行為中，就相對比較難以確定。
在利用用戶行為數據設計推薦演算法之前，研究人員首先需要對用戶行為數據進行分析，了解 數據中蘊含的一般規律，這樣才能對演算法的設計起到指導作用。
(1) 用戶活躍度和物品流行度
(2) 用戶活躍度和物品流行度的關系
一般認為，新用戶傾向於瀏覽熱門的物品，因為他 們對網站還不熟悉，只能點擊首頁的熱門物品，而老用戶會逐漸開始瀏覽冷門的物品。如果用橫坐標表示用戶活躍度，縱坐標表示具有某個活躍度的所有用戶評過分的物品的平均流行度。圖中曲線呈明顯下 降的趨勢，這表明用戶越活躍，越傾向於瀏覽冷門的物品。
僅僅基於用戶行為數據設計的推薦演算法一般稱為協同過濾演算法。學術界對協同過濾演算法進行了深入研究，提出了很多方法，比如基於鄰域的方法(neighborhood-based)、隱語義模型 (latent factor model)、基於圖的隨機遊走演算法(random walk on graph)等。在這些方法中， 最著名的、在業界得到最廣泛應用的演算法是基於鄰域的方法，而基於鄰域的方法主要包含下面兩種演算法。
基於用戶的協同過濾演算法 ：這種演算法給用戶推薦和他興趣相似的其他用戶喜歡的物品
基於物品的協同過濾演算法： 這種演算法給用戶推薦和他之前喜歡的物品相似的物品
基於鄰域的演算法是推薦系統中最基本的演算法，該演算法不僅在學術界得到了深入研究，而且在 業界得到了廣泛應用。基於鄰域的演算法分為兩大類，一類是基於用戶的協同過濾演算法，另一類是 基於物品的協同過濾演算法。現在我們所說的協同過濾，基本上就就是指基於用戶或者是基於物品的協同過濾演算法，因此，我們可以說基於鄰域的演算法即是我們常說的協同過濾演算法
(1) 基於用戶的協同過濾演算法（UserCF）
基於用戶的協同過濾演算法的基本思想是：在一個在線個性化推薦系統中，當一個用戶A需要個性化推薦 時，可以先找到和他有相似興趣的其他用戶，然後把那些用戶喜歡的、而用戶A沒有聽說過的物品推薦給A。
Ø 從上面的描述中可以看到，基於用戶的協同過濾演算法主要包括兩個步驟。 第一步：找到和目標用戶興趣相似的用戶集合。 第二步： 找到這個集合中的用戶喜歡的，且目標用戶沒有聽說過的物品推薦給目標用戶。
這里，步驟1的關鍵是計算兩個用戶的興趣相似度，協同過濾演算法主要利用行為的相似度計算興趣的相似度。給定用戶u和用戶v，令N(u)表示用戶u曾經有過正反饋的物品集合，令N(v) 為用戶v曾經有過正反饋的物品集合。那麼我們可以通過以下方法計算用戶的相似度：
基於餘弦相似度
(2) 基於物品的協同過濾演算法（itemCF）
與UserCF同理
(3) UserCF和itemCF的比 較
首先我們提出一個問題，為什麼新聞網站一般使用UserCF，而圖書、電商網站一般使用ItemCF呢？ 首先回顧一下UserCF演算法和ItemCF演算法的推薦原理。UserCF給用戶推薦那些和他有共同興 趣愛好的用戶喜歡的物品，而ItemCF給用戶推薦那些和他之前喜歡的物品類似的物品。從這個算 法的原理可以看到，UserCF的推薦結果著重於反映和用戶興趣相似的小群體的熱點，而ItemCF 的推薦結果著重於維系用戶的歷史興趣。換句話說，UserCF的推薦更社會化，反映了用戶所在的小型興趣群體中物品的熱門程度，而ItemCF的推薦更加個性化，反映了用戶自己的興趣傳承。 在新聞網站中，用戶的興趣不是特別細化，絕大多數用戶都喜歡看熱門的新聞。個性化新聞推薦更加強調抓住 新聞熱點，熱門程度和時效性是個性化新聞推薦的重點，而個性化相對於這兩點略顯次要。因 此，UserCF可以給用戶推薦和他有相似愛好的一群其他用戶今天都在看的新聞，這樣在抓住熱 點和時效性的同時，保證了一定程度的個性化。同時，在新聞網站中，物品的更新速度遠遠快於新用戶的加入速度，而且 對於新用戶，完全可以給他推薦最熱門的新聞，因此UserCF顯然是利大於弊。
但是，在圖書、電子商務和電影網站，比如亞馬遜、豆瓣、Netflix中，ItemCF則能極大地發 揮優勢。首先，在這些網站中，用戶的興趣是比較固定和持久的。一個技術人員可能都是在購買 技術方面的書，而且他們對書的熱門程度並不是那麼敏感，事實上越是資深的技術人員，他們看 的書就越可能不熱門。此外，這些系統中的用戶大都不太需要流行度來輔助他們判斷一個物品的 好壞，而是可以通過自己熟悉領域的知識自己判斷物品的質量。因此，這些網站中個性化推薦的 任務是幫助用戶發現和他研究領域相關的物品。因此，ItemCF演算法成為了這些網站的首選演算法。 此外，這些網站的物品更新速度不會特別快，一天一次更新物品相似度矩陣對它們來說不會造成 太大的損失，是可以接受的。同時，從技術上考慮，UserCF需要維護一個用戶相似度的矩陣，而ItemCF需要維護一個物品 相似度矩陣。從存儲的角度說，如果用戶很多，那麼維護用戶興趣相似度矩陣需要很大的空間， 同理，如果物品很多，那麼維護物品相似度矩陣代價較大
下表是對二者的一個全面的表較：