稀疏矩陣因子分解的快速演算法

Ⅰ 稀疏矩陣的運算

M AT L A B中對滿矩陣的運算和函數同樣可用在稀疏矩陣中.結果是稀疏矩陣還是滿矩陣,
這取決於運算符或者函數及下列的操作數:當函數用一個矩陣作為輸入參數,輸出參數為一個標量或者一個給定大小的向量時,輸出參數的格式總是返回一個滿陣形式,如命令s i z e.
當函數用一個標量或者一個向量作為輸入參數,輸出參數為一個矩陣時,輸出參數的格式也總是返回一個滿矩陣,如命令e y e.還有一些特殊的命令可以得到稀疏矩陣,如命令s p e y e.
對於單參數的其他函數來說,通常返回的結果和參數的形式是一樣的,如d i a g.
對於雙參數的運算或者函數來說,如果兩個參數的形式一樣,那麼也返回同樣形式的結果.在兩個參數形式不一樣的情況下,除非運算的需要,均以滿矩陣的形式給出結果.
兩個矩陣的組和[A B],如果A或B中至少有一個是滿矩陣,則得到的結果就是滿矩陣.
表達式右邊的冒號是要求一個參數的運算符,遵守這些運算規則.
表達式左邊的冒號不改變矩陣的形式. 假設有:
這是一個5×5的單位滿矩陣和相應的稀疏矩陣.
(a) C = 5*B,結果為:
這是一個稀疏矩陣.
(b) D = A + B,給出的結果為:
這是一個滿矩陣.
(c) x = B h,結果為:
這是一個滿向量.
有許多命令可以對非零元素進行操作.
命令集8 9矩陣的非零元素
n n z ( A )求矩陣A中非零元素的個數.它既可求滿矩陣也可求稀疏矩陣.
s p y ( A )畫出稀疏矩陣A中非零元素的分布.也可用在滿矩陣中,在
這種情況下,只給出非零元素的分布.
s p y ( A , c s t r , s i z e )用指定的顏色c s t r(見表1 3 - 1 )和在s i z e規定的范圍內畫出稀疏
矩陣A中非零元素的分布.
n o n z e r o s ( A )按照列的順序找出矩陣A中非零的元素.
s p o n e s ( A )把矩陣A中的非零元素全換為1.
s p a l l o c ( m , n ,產生一個m×n階只有n z m a x個非零元素的稀疏矩陣.這樣可以
n z m a x )有效地減少存儲空間和提高運算速度.
n z m a x ( A )給出為矩陣A中非零元素分配的內存數.不一定和n n z ( A )得
到的數相同;參見s p a r s e或者s p a l l o c.
i s s p a r s e ( A )如果矩陣A是稀疏矩陣,則返回1;否則返回0.
s p f u n ( f c n , A )用A中所有非零元素對函數f c n求值,如果函數不是對稀疏矩
陣定義的,同樣也可以求值.
s p r a n k( A )求稀疏矩陣A的結構秩.對於所有的矩陣來說,都有
s p r a n k ( A）≥r a n k ( A ). 用下面的命令定義稀疏矩陣:
創建一個大矩陣:
Big=kron(A, A)
這個矩陣B i g是什麼樣子呢?
K r o n e c k e r張量積給出一個大矩陣,它的元素是矩陣A的元素之間可能的乘積.因為參量都是稀疏矩陣,所以得到的矩陣也是一個稀疏矩陣.可以用命令 w h o s和i s s p a r s e來確認一下.
查看矩陣B i g的結構圖,可輸入s p y ( B i g ),結構圖如右圖所示. 從圖中可以看出B i g是一個塊雙對角矩陣. MATLAB中有四個基本稀疏矩陣,它們是單位矩陣,隨機矩陣,對稱隨機矩陣和對角矩陣.
命令集9 0單位稀疏矩陣
s p e y e ( n )生成n×n的單位稀疏矩陣.
s p e y e ( m , n )生成m×n的單位稀疏矩陣.
命令speye(A) 得到的結果和s p a r s e ( e y e ( A ) )是一樣的,但是沒有涉及到滿陣的存儲.
命令集9 1隨機稀疏矩陣
s p r a n d ( A )生成與A有相同結構的隨機稀疏矩陣,且元素服從均勻分布.
s p r a n d ( m , n , d e n s )生成一個m×n的服從均勻分布的隨機稀疏矩陣,有d e n s×m×
n個非零元素,0≤d e n s≤1.參數d e n s是非零元素的分布密度.
s p r a n d ( m , n , d e n s ,生成一個近似的條件數為1 /rc,大小為m×n的隨機稀疏矩
r c )陣.如果rc=rc是一個長度為l≤l ( m i n (m, n) )的向量,那麼
矩陣將rci作為它l個奇異值的第一個,其他的奇異值為0.
s p r a n d n ( A )生成與A有相同結構的隨機稀疏矩陣,且元素服從正態分布.
s p r a n d n ( m , n , d e n s ,生成一個m×n的服從正態分布的隨機稀疏矩陣,和sprand
r c )一樣.
s p r a n d s y m ( S )生成一個隨機對稱稀疏矩陣.它的下三角及主對角線部分與S的結構相同,矩陣元素服從正態分布.
s p r a n d s y m ( n , d e n s )生成一個m×n的隨機對稱稀疏矩陣.矩陣元素服從正態分布,分布密度為d e n s.
s p r a n d s y m ( n , d e n s ,生成一個近似條件數為1 /rc的隨機對稱稀疏矩陣.元素以0r c )對稱分布,但不是正態分布.如果rc=rc是一個向量,則矩陣有特徵值rci.也就是說,如果rc是一個正向量,則矩陣是正定矩陣.
s p r a n d s y m ( n , d e n s ,生成一個正定矩陣.如果k= 1,則矩陣是由一正定對稱矩r c , k )陣經隨機J a c o b i旋轉得到的,其條件數正好等於1 /rc;如果k= 2,則矩陣為外積的換位和,其條件數近似等於1 /rc.
s p r a n d s y m ( S , d e n s ,生成一個與矩陣S結構相同的稀疏矩陣,近似條件數為1 /rc.
r c , 3 )參數d e n s被忽略,但是這個參數在這個位置以便函數能確認最後兩個參數的正確與否. (a) 假設有矩陣A:
輸入R a n d o m = s p r a n d n ( A ),可得到隨機稀疏矩陣:
矩陣中隨機數的位置和矩陣A中非零元素的位置相同.
(b) 對於( a )中的矩陣A,輸入:
B = s p r a n d s y m ( A )
結果為:
這是一個用矩陣A的下三角及主對角線部分創建的對稱矩陣,在非零元素的位置用隨機數作為元素值.
用命令s p d i a g s可以取出對角線元素,並創建帶狀對角矩陣.假設矩陣A的大小為m×n,
在p個對角線上有非零元素.B的大小為m i n (m×n)×p,它的列是矩陣A的對角線.向量d的長度為p,其整型分量給定了A的對角元:
di0 主對角線上的對角線
命令集9 2對角稀疏矩陣
[ B , d ] = s p d i a g s ( A )求出A中所有的對角元,對角元保存在矩陣B中,它們的下標保存在向量d中.
s p d i a g s ( A , d )生成一個矩陣,這個矩陣包含有矩陣A中向量d規定的對角元.
s p d i a g s ( B , d , A )生成矩陣A,用矩陣B中的列替換d定義的對角元.
A = s p d i a g s ( B , d , m , n )用保存在由d定義的B中的對角元創建稀疏矩陣A.
例11 . 4給出了如何使用s p d i a g s命令來解普通微分方程組. 在許多實際應用中要保留稀疏矩陣的結構,但是在計算過程中的中間結果會減弱它的稀疏性,如L U分解.這就會導致增加浮點運算次數和存儲空間.為了避免這種情況發生,在第稀疏矩陣1 2 9
M AT L A B中用命令對矩陣進行重新安排.這些命令都列在下面的命令集9 3中.通過h e l p命令
可以得到每個命令更多的幫助信息,也可見h e l p d e s k.
命令集9 3矩陣變換
c o l m m d ( A )返回一個變換向量,使得矩陣A列的秩為最小.
s y m m m d ( A )返回使對稱矩陣秩為最小的變換.
s y m r c m ( A )矩陣A的C u t h i l l - M c K e e逆變換.矩陣A的非零元素在主對角線附近.
c o l p e r m ( A )返回一個矩陣A的列變換的向量.列按非零元素升序排列.有時這是L U因式分解前有用的變換:lu(A(:, j)).如果A是一個對稱矩陣,對行和列進行排序,這有利於C h o l e s k y分解:chol(A(j, j)).
r a n d p e r m ( n )給出正數1,2,. . .,n的隨機排列,可以用來創建隨機變換矩陣.
d m p e r m ( A )對矩陣A進行D u l m a g e - M e n d e l s o h n分解,輸入help dmperm可得更多信息. 創建一個秩為4的變換矩陣,可輸入:
一旦運行p e r m = r a n d p e r m ( 4 ),就會得到:
給出的變換矩陣為:
如果矩陣A為:
輸入命令:
運行結果為:
有兩個不完全因式分解命令,它們是用來在解大線性方程組前進行預處理的.用h e l p d e s k命令可得更多信息.命令集9 4不完全因式分解c h o l i n c ( A , o p t )進行不完全C h o l e s k y分解,變數o p t取下列值之一:
d r o p t o l指定不完全分解的舍入誤差,0給出完全分解.
m i c h o l如果m i c h o l = 1,則從對角線上抽取出被去掉的元素.
r d i a g用s q r t ( d r o p t o l*n o r m ( X ( : , j ) ) )代替上三角分
解因子中的零元素,j為零元素所在的列.
[ L , U , P ]=返回矩陣X的不完全分解得到的三個矩陣L,U和P,變數o p t取
l u i n c ( X , o p t )下列值之一:
d r o p t o l指定分解的舍入誤差.
m i l u改變分解以便從上三角角分解因子中抽取被去掉的列元素.
u d i a g用d r o p t o l值代替上三角角分解因子中的對角線上的零元素.
t h r e s h中心極限.
解稀疏線性方程組既可用左除運算符解,也可用一些特殊命令來解.
命令集9 5稀疏矩陣和線性方程組
s p p a r m s ( k e y s t r , o p )設置稀疏矩陣演算法的參數,用help spparms可得詳細信息.
s p a u g m e n t ( A , c )根據[ c*l A; A' 0 ]創建稀疏矩陣,這是二次線性方程組的最
小二乘問題.參見7 . 7節.
s y m b f a c t ( A )給出稀疏矩陣的C h o l e s k y和L U因式分解的符號分解因子.
用help symbfact可得詳細信息.
稀疏矩陣的范數計算和普通滿矩陣的范數計算有一個重要的區別.稀疏矩陣的歐幾里德范數不能直接求得.如果稀疏矩陣是一個小矩陣,則用n o r m ( f u l l ( A ) )來計算它的范數;但是對於大矩陣來說,這樣計算是不可能的.然而M AT L A B可以計算出歐幾里德范數的近似值,在計算條件數時也是一樣.
命令集9 6稀疏矩陣的近似歐幾里德范數和條件數
n o r m e s t ( A )計算A的近似歐幾里德范數,相對誤差為1 0-6.
n o r m e s t ( A , t o l )計算A的近似歐幾里德范數,設置相對誤差t o l,而不用預設時的1 0-6.
[ n r m , n i t ] =計算近似n r m范數,還給出計算范數迭代的次數n i t.
n o r m e s t ( A )
c o n d e s t ( A )求矩陣A條件數的1 -范數中的下界估計值.
[ c , v ]=求矩陣A的1 -范數中條件數的下界估計值c和向量v,使得
c o n d e s t ( A , t r )| |Av| | = ( | |A| | | |v| | ) / c.如果給定t r,則給出計算的過程.t r= 1,
給出每步過程;t r=-1,給出商c / r c o n d ( A ). 假設給出:
用n o r m A p p r o x = n o r m e s t ( S p r s )計算出:
用t h e N o r m = n o r m ( f u l l ( S p r s ) )得:
為了找到它們之間的差別,計算d i f f e r e n c e = t h e N o r m - n o r m A p p r o x,得:
在許多應用中,n o r m e s t計算得到的近似值是一個很好的近似歐幾里德范數,它的計算步數要比n o r m要少得多;可參見7 . 6節.
用e t r e e命令來找到稀疏對稱矩陣的消元樹,用向量f來描述消元樹,還可用e t r e e p l o t命令畫出來.元素fi是矩陣的上三角C h o l e s k y分解因子中i行上第1非零元素的列下標.如果有非零元素,則fi= 0.消元樹可以這樣來建立:
節點i是fi的孩子,或者如果fi= 0,則節點i是樹的根節點.
命令集9 7矩陣的消元樹
e t r e e ( A )求A的消元樹向量f,這個命令有可選參數;輸入h e l p
e t r e e獲取幫助.
e t r e e p l o t ( A )畫出向量f定義的消元樹圖形.
t r e e p l o t ( p , c , d )畫出指針向量p的樹圖形,參數c和d分別指定節點的顏色和分支數.e t r e e p l o t可以調用這個命令.
t r e e l a y o u t顯示樹的結構,t r e e p l o t可以調用這個命令. 假設有對稱稀疏矩陣B:
運行命令b t r e e = e t r e e ( B ),結果為:
開始的數字2不難理解,它是矩陣的第1列上第1個非零元素的行數,它決定了在C h o l e s k y分解因子的第1行第2列處有一個非零元素.當縮減第1列的元素時就得到第2列的數字5.B在縮減後,在( 5 , 2 )位置的元素是非零的,這樣消元樹向量中第2個元素的值為5.
s p y ( c h o l ( B ) )給出了C h o l e s k y分解因子的結構圖,如圖9 - 2所示:
圖9-2 Cholesky分解結構圖
圖9-3 矩陣B的消元樹
這個向量消元樹可以這樣來建立:上三角中只有一行有非零元素,節點8,因此這就是樹
唯一的根.節點1是節點2的孩子,節點2和3是節點5的孩子,而節點5是節點6的孩子.節點4和6是節點7的孩子,而節點7又是節點8的孩子,即根的孩子.
命令e t r e e p l o t ( B )給出了樹的結構圖,如圖9 - 3所示.
消元樹的形狀取決於列和行序,它可以用來分析消元過程.
用g p l o t命令可以畫出坐標和矩陣元素間的聯系圖形.必須在n×2的矩陣中給出n個坐標,
矩陣的每一行作為一個點.這樣就創建出點點之間連接的n×n矩陣,如果點4連接到點8,則(4, 8)的值為1.由於是一個大矩陣,而且非零元素較少,所以它應該被建成稀疏矩陣.
這個圖可以說明網路問題,如傳遞問題.它還包含有線性方程組中未知量之間的相關信息.
命令集9 8網路圖形
g p l o t ( A , K )如果矩陣A的a(i, j)不為0,則將點ki連接到點kj.K是一個n×
2的坐標矩陣,A是一個n×n的關聯矩陣.
g p l o t ( A , K , s t r )用字元串s t r給定的顏色和線型畫出的同上圖形.字元串s t r的
取值參見表1 3 - 1.
[ X , A ] = u n m e s h ( E )求網格邊界矩陣E的L a p l a c e矩陣A和網格點的坐標矩陣X.
例七
假設有下面的坐標矩陣K和關聯矩陣A:
矩陣A在稀疏化後,用命令g p l o t ( A , K )畫出圖9 - 4,給出了點(0, 1)和點(4, 1)之間所有可能的路徑.

Ⅱ 07_推薦系統演算法詳解

     基於人口統計學的推薦與用戶畫像、基於內容的推薦、基於協同過濾的推薦。

1、基於人口統計學的推薦機制( Demographic-based Recommendation)是一種最易於實現的推薦方法，它只是簡單的根據系統用戶的基本信息發現用戶的相關程度，然後將相似用戶喜愛的其他物品推薦給當前用戶。

2、對於沒有明確含義的用戶信息(比如登錄時間、地域等上下文信息)，可以通過聚類等手段，給用戶打上分類標簽。

3、對於特定標簽的用戶，又可以根據預設的規則(知識)或者模型，推薦出對應的物品。

4、用戶信息標簽化的過程一般又稱為 用戶畫像 ( User Profiling）。

（1）用戶畫像( User Profile)就是企業通過收集與分析消費者社會屬性、生活習慣、消費行為等主要信息的數據之後，完美地抽象出一個用戶的商業全貌作是企業應用大數據技術的基本方式。

（2）用戶畫像為企業提供了足夠的信息基礎，能夠幫助企業快速找到精準用戶群體以及用戶需求等更為廣泛的反饋信息。

（3）作為大數據的根基，它完美地抽象出一個用戶的信息全貌，為進一步精準、快速地分析用戶行為習慣、消費習慣等重要信息，提供了足夠的數據基礎。

1、 Content- based Recommendations(CB)根據推薦物品或內容的元數據，發現物品的相關性，再基於用戶過去的喜好記錄，為用戶推薦相似的物品。

2、通過抽取物品內在或者外在的特徵值,實現相似度計算。比如一個電影,有導演、演員、用戶標簽UGC、用戶評論、時長、風格等等，都可以算是特徵。

3、將用戶(user)個人信息的特徵(基於喜好記錄或是預設興趣標簽)，和物品(item)的特徵相匹配，就能得到用戶對物品感興趣的程度。在一些電影、音樂、圖書的社交網站有很成功的應用,有些網站還請專業的人員對物品進行基因編碼/打標簽(PGC）。

4、 相似度計算：

5、對於物品的特徵提取——打標簽(tag)

        - 專家標簽(PGC）

        - 用戶自定義標簽(UGC)

        - 降維分析數據,提取隱語義標簽(LFM)

     對於文本信息的特徵提取——關鍵詞

        - 分詞、語義處理和情感分析(NLP)

        - 潛在語義分析(LSA）

6、 基於內容推薦系統的高層次結構

7、 特徵工程

（1）特徵( feature)：數據中抽取出來的對結果預測有用的信息。

         特徵的個數就是數據的觀測維度。

         特徵工程是使用專業背景知識和技巧處理數據，使得特徵能在機器學習演算法上發揮更好的作用的過程。

         特徵工程一般包括特徵清洗(采樣、清洗異常樣本)，特徵處理和特徵選擇。

         特徵按照不同的數據類型分類，有不同的特徵處理方法：數值型、類別型、時間型、統計型。

（2）數值型特徵處理

        用連續數值表示當前維度特徵，通常會對數值型特徵進行數學上的處理，主要的做法是歸一化和離散化。

        * 幅度調整歸一化：

            特徵與特徵之間應該是平等的，區別應該體現在 特徵內部 。

            例如房屋價格和住房面積的幅度是不同的，房屋價格可能在3000000~15000000(萬)之間,而住房面積在40-300(平方米)之間，那麼明明是平等的兩個特徵，輸入到相同的模型中後由於本身的幅值不同導致產生的效果不同，這是不合理的

                        

        * 數值型特徵處理——離散化

        離散化的兩種方式：等步長——簡單但不一定有效；等頻——min -> 25% -> 75% -> max

        兩種方法對比：

            等頻的離散化方法很精準，但需要每次都對數據分布進行一遍從新計算，因為昨天用戶在淘寶上買東西的價格分布和今天不一定相同，因此昨天做等頻的切分點可能並不適用，而線上最需要避免的就是不固定，需要現場計算，所以昨天訓練出的模型今天不一定能使用。

            等頻不固定，但很精準，等步長是固定的，非常簡單，因此兩者在工業上都有應用。

（3） 類別型特徵處理

        類別型數據本身沒有大小關系，需要將它們編碼為數字，但它們之間不能有預先設定的大小關系，因此既要做到公平，又要區分開它們，那麼直接開辟多個空間。

        One-Hot編碼/啞變數：One-Hot編碼/啞變數所做的就是將類別型數據平行地展開，也就是說，經過One-Hot編碼啞變數後，這個特徵的空間會膨脹。

（4） 時間型特徵處理

        時間型特徵既可以做連續值,又可以看做離散值。

        連續值：持續時間(網頁瀏覽時長)；間隔時間(上一次購買/點擊離現在的時間間隔)。

        離散值：一天中哪個時間段；一周中的星期幾；一年中哪個月/星期；工作日/周末。

（5） 統計型特徵處理

        加減平均：商品價格高於平均價格多少，用戶在某個品類下消費超過多少。

        分位線：商品屬於售出商品價格的分位線處。

        次序性：商品處於熱門商品第幾位。

        比例類：電商中商品的好/中/差評比例。

8、 推薦系統常見反饋數據 ：

9、 基於UGC的推薦

     用戶用標簽來描述對物品的看法，所以用戶生成標簽(UGC)是聯系用戶和物品的紐帶，也是反應用戶興趣的重要數據源。

    一個用戶標簽行為的數據集一般由一個三元組(用戶,物品,標簽)的集合表示，其中一條記錄(u,i,b)表示用戶u給物品打上了標簽b。

    一個最簡單的演算法：

        - 統計每個用戶最常用的標簽

        - 對於每個標簽,統計被打過這個標簽次數最多的物品

        - 對於一個用戶，首先找到他常用的標簽，然後找到具有這些標簽的最熱門的物品，推薦給他

        - 所以用戶u對物品i的興趣公式為 ，其中 使用戶u打過標簽b的次數， 是物品i被打過標簽b的次數。

    簡單演算法中直接將用戶打出標簽的次數和物品得到的標簽次數相乘，可以簡單地表現出用戶對物品某個特徵的興趣。

    這種方法傾向於給熱門標簽(誰都會給的標簽,如「大片」、「搞笑」等)、熱門物品(打標簽人數最多)比較大的權重，如果一個熱門物品同時對應著熱門標簽,那它就會「霸榜」，推薦的個性化、新穎度就會降低。

    類似的問題,出現在新聞內容的關鍵字提取中。比如以下新聞中,哪個關鍵字應該獲得更高的權重?

10、 TF-IDF：詞頻逆文檔頻率 ( Term Frequency- -Inverse Document Frequency,TF-DF)是一種用於資訊檢索與文本挖掘的常用加權技術。

        TFDF是一種統計方法，用以評估一個字詞對於一個文件集或一個語料庫中的其中份文件的重要程度。字詞的重要性隨著它在文件中出現的次數成正比增加，但同時會隨著它在語料庫中出現的頻率成反比下降。

                    TFIDF=TF IDF

         TF-IDF的主要思想是 ：如果某個詞或短語在一篇文章中出現的頻率TF高，並且在其他文章中很少出現，則認為此詞或者短語具有很好的類別區分能力，適合用來分類。

        TF-DF加權的各種形式常被搜索引擎應用，作為文件與用戶查詢之間相關程度的度量或評級。

         詞頻( Term Frequency,TF) ：指的是某一個給定的詞語在該文件中出現的頻率。這個數字是對詞數的歸一化，以防止偏向更長的文件。(同一個詞語在長文件里可能會比短文件有更高的詞數,而不管該詞語重要與否。） ，其中 表示詞語 i 在文檔 j 中出現的頻率， 表示 i 在 j 中出現的次數， 表示文檔 j 的總詞數。

         逆向文件頻率( Inverse Document Frequency,IDF) ：是一個詞語普遍重要性的度量，某一特定詞語的IDF，可以由總文檔數目除以包含該詞語之文檔的數目，再將得到的商取對數得到 ，其中 表示詞語 i 在文檔集中的逆文檔頻率，N表示文檔集中的文檔總數， 表示文檔集中包含了詞語 i 的文檔數。

（11） TF-IDF對基於UGC推薦的改進 ： ，為了避免熱門標簽和熱門物品獲得更多的權重，我們需要對「熱門進行懲罰。

          借鑒TF-IDF的思想，以一個物品的所有標簽作為「文檔」，標簽作為「詞語」，從而計算標簽的「詞頻」(在物品所有標簽中的頻率)和「逆文檔頻率」(在其它物品標簽中普遍出現的頻率）。

           由於「物品i的所有標簽」 應該對標簽權重沒有影響，而 「所有標簽總數」 N 對於所有標簽是一定的，所以這兩項可以略去。在簡單演算法的基礎上,直接加入對熱門標簽和熱門物品的懲罰項： ，其中， 記錄了標簽 b 被多少個不同的用戶使用過， 記錄了物品 i 被多少個不同的用戶打過標簽。

（一）協同過濾（Collaborative Filtering, CF）

1、基於協同過濾(CF)的推薦：基於內容( Content based,CB)主要利用的是用戶評價過的物品的內容特徵，而CF方法還可以利用其他用戶評分過的物品內容。

    CF可以解決CB的一些局限：

         - 物品內容不完全或者難以獲得時,依然可以通過其他用戶的反饋給出推薦。

        - CF基於用戶之間對物品的評價質量，避免了CB僅依賴內容可能造成的對物品質量判斷的干。

        - CF推薦不受內容限制，只要其他類似用戶給出了對不同物品的興趣，CF就可以給用戶推薦出內容差異很大的物品(但有某種內在聯系)

    分為兩類：基於近鄰和基於模型。

2、基於近鄰的推薦系統：根據的是相同「口碑」准則。是否應該給Cary推薦《泰坦尼克號》?

（二）基於近鄰的協同過濾

1、 基於用戶（User-CF）： 基於用戶的協同過濾推薦的基本原理是，根據所有用戶對物品的偏好，發現與當前用戶口味和偏好相似的「鄰居」用戶群，並推薦近鄰所偏好的物品。

     在一般的應用中是採用計算「K-近鄰」的演算法；基於這K個鄰居的歷史偏好信息，為當前用戶進行推薦。

    User-CF和基於人口統計學的推薦機制：

        - 兩者都是計算用戶的相似度，並基於相似的「鄰居」用戶群計算推薦。

        - 它們所不同的是如何計算用戶的相似度：基於人口統計學的機制只考慮用戶本身的特徵，而基於用戶的協同過濾機制可是在用戶的歷史偏好的數據上計算用戶的相似度，它的基本假設是，喜歡類似物品的用戶可能有相同或者相似的口味和偏好。

2、基於物品（Item-CF）：基於項目的協同過濾推薦的基本原理與基於用戶的類似，只是使用所有用戶對物品的偏好，發現物品和物品之間的相似度，然後根據用戶的歷史偏好信息，將類似的物品推薦給用戶。

    Item-CF和基於內容(CB)的推薦

       - 其實都是基於物品相似度預測推薦，只是相似度計算的方法不一樣，前者是從用戶歷史的偏好推斷，而後者是基於物品本身的屬性特徵信息。

   同樣是協同過濾，在基於用戶和基於項目兩個策略中應該如何選擇呢?

        - 電商、電影、音樂網站,用戶數量遠大於物品數量。

        - 新聞網站，物品(新聞文本)數量可能大於用戶數量。

3、 User-CF和Item-CF的比較

     同樣是協同過濾，在User-CF和ltem-CF兩個策略中應該如何選擇呢？

     Item-CF應用場景

       -  基於物品的協同過濾( Item-CF ) 推薦機制是 Amazon在基於用戶的機制上改良的一種策略因為在大部分的Web站點中，物品的個數是遠遠小於用戶的數量的，而且物品的個數和相似度相對比較穩定，同時基於物品的機制比基於用戶的實時性更好一些，所以 Item-CF 成為了目前推薦策略的主流。

     User-CF應用場景

        - 設想一下在一些新聞推薦系統中，也許物品一一也就是新聞的個數可能大於用戶的個數，而且新聞的更新程度也有很快，所以它的相似度依然不穩定，這時用 User-cf可能效果更好。

    所以，推薦策略的選擇其實和具體的應用場景有很大的關系。

4、 基於協同過濾的推薦優缺點

 （1）基於協同過濾的推薦機制的優點：

        它不需要對物品或者用戶進行嚴格的建模，而且不要求對物品特徵的描述是機器可理解的，所以這種方法也是領域無關的。

       這種方法計算出來的推薦是開放的，可以共用他人的經驗，很好的支持用戶發現潛在的興趣偏好。

（2）存在的問題

        方法的核心是基於歷史數據，所以對新物品和新用戶都有「冷啟動」的問題。

        推薦的效果依賴於用戶歷史好數據的多少和准確性。

        在大部分的實現中，用戶歷史偏好是用稀疏矩陣進行存儲的，而稀疏矩陣上的計算有些明顯的問題，包括可能少部分人的錯誤偏好會對推薦的准確度有很大的影響等等。

        對於一些特殊品味的用戶不能給予很好的推薦。

（三）基於模型的協同過濾

1、基本思想

（1）用戶具有一定的特徵，決定著他的偏好選擇

（2）物品具有一定的特徵，影響著用戶需是否選擇它。

（3）用戶之所以選擇某一個商品，是因為用戶特徵與物品特徵相互匹配。

    基於這種思想，模型的建立相當於從行為數據中提取特徵，給用戶和物品同時打上「標簽」；這和基於人口統計學的用戶標簽、基於內容方法的物品標簽本質是一樣的，都是特徵的提取和匹配。

    有顯性特徵時(比如用戶標簽、物品分類標簽)我們可以直接匹配做出推薦；沒有時，可以根據已有的偏好數據，去發據出隱藏的特徵,這需要用到隱語義模型(LFM)。

2、基於模型的協同過濾推薦，就是基於樣本的用戶偏好信息，訓練一個推薦模型,然後根據實時的用戶喜好的信息進行預測新物品的得分，計算推薦

    基於近鄰的推薦和基於模型的推薦

        - 基於近鄰的推薦是在預測時直接使用已有的用戶偏好數據，通過近鄰數據來預測對新物品的偏好(類似分類)

        - 而基於模型的方法，是要使用這些偏好數據來訓練模型，找到內在規律，再用模型來做預測(類似回歸)

    訓練模型時，可以基於標簽內容來提取物品特徵，也可以讓模型去發據物品的潛在特徵；這樣的模型被稱為 隱語義模型 ( Latent Factor Model,LFM)。

（1）隱語義模型(LFM)：用隱語義模型來進行協同過濾的目標：

            - 揭示隱藏的特徵,這些特徵能夠解釋為什麼給出對應的預測評分

            - 這類特徵可能是無法直接用語言解釋描述的,事實上我們並不需要知道,類似「玄學」

        通過矩陣分解進行降維分析

            - 協同過濾演算法非常依賴歷史數據，而一般的推薦系統中，偏好數據又往往是稀疏的；這就需要對原始數據做降維處理。

            - 分解之後的矩陣，就代表了用戶和物品的隱藏特徵

        隱語義模型的實例：基於概率的隱語義分析(pLSA)、隱式迪利克雷分布模型(LDA)、矩陣因子分解模型(基於奇異值分解的模型,SVD)

（2）LFM降維方法——矩陣因子分解

（3）LFM的進一步理解

    我們可以認為，用戶之所以給電影打出這樣的分數，是有內在原因的，我們可以挖掘出影響用戶打分的隱藏因素，進而根據未評分電影與這些隱藏因素的關聯度，決定此未評分電影的預測評分。

    應該有一些隱藏的因素，影響用戶的打分，比如電影：演員、題材、年代…甚至不定是人直接可以理解的隱藏因子。

    找到隱藏因子，可以對user和Iiem進行關聯(找到是由於什麼使得user喜歡/不喜歡此Item,什麼會決定user喜歡/不喜歡此item)，就可以推測用戶是否會喜歡某一部未看過的電影。

（4）矩陣因子分解

（5）模型的求解——損失函數

（6）模型的求解演算法——ALS

    現在，矩陣因子分解的問題已經轉化成了一個標準的優化問題，需要求解P、Q，使目標損失函數取最小值。

    最小化過程的求解，一般採用隨機梯度下降演算法或者交替最小二乘法來實現交替最小二乘法( Alternating Least Squares,ALS)

    ALS的思想是，由於兩個矩陣P和Q都未知,且通過矩陣乘法耦合在一起，為了使它們解耦，可以先固定Q，把P當作變數，通過損失函數最小化求出P，這就是一個經典的最小二乘問題；再反過來固定求得的P，把Q當作變數，求解出Q：如此交替執行，直到誤差滿足閱值條件，或者到達迭代上限。

（7）梯度下降演算法