|
摘要：本文介紹了手工藝品電商平臺Etsy的個性化推薦算法實踐及優(yōu)化思路，計算過程分為基于歷史數(shù)據(jù)建模和計算推薦結(jié)果兩個階段，采用的手段主要包括矩陣分解、交替最小二乘、隨機SVD（奇異值分解）和局部敏感哈希等。 提供個性化推薦對網(wǎng)上購物市場非常重要。個性化推薦對買賣雙方都是有利的：購買者不用自己去搜索就可以直接獲得他們感興趣的產(chǎn)品信息，賣家則可以以較小的市場營銷代價獲得更好的產(chǎn)品曝光度。在這篇文章中，我們將介紹我們在Esty（美國網(wǎng)絡商店平臺，以手工藝成品買賣為主要特色——譯者注）中使用的一些推薦方法。所有這些方法的MapReduce實現(xiàn)都包含在我們的開源機器學習包“[Conjecture]”之中，這個包在[上一篇文章]中已有描述。 推薦的計算過程基本上由兩個階段組成。第一個階段，我們基于歷史數(shù)據(jù)矩陣建立一個用戶興趣模型。例如，他們的購買記錄或他們的收藏清單。這個模型提供了用戶和物品的特征向量，它們的內(nèi)積給出了一個用戶對于某個物品感興趣的程度（較高的值代表更大的預估感興趣程度）。第二個階段，我們會計算出推薦結(jié)果，通過最大化興趣度的估值，為每一位用戶找出一組物品。 關于用戶和物品的模型也可被用于其他方面，例如用于發(fā)現(xiàn)具有相同興趣愛好的用戶，從某一“品味”角度上看具有相似性的物品，以及可以一起購買的互補性物品等。 矩陣分解 產(chǎn)生推薦結(jié)果的第一階段是將用戶和物品的模型與數(shù)據(jù)相適應。在Esty中，我們處理的是“隱式反饋”的數(shù)據(jù)，只觀察用戶與物品的交互（如收藏或者購買）的指標。這和用戶給體驗過的物品打分（例如在5分制下打3分）的“顯示反饋”恰恰相反。我們用一個二進制矩陣代表這個隱式反饋，每個元素的值為0或1，1代表用戶喜歡（如收藏）這個物品，0代表用戶沒有這么做。0并不一定表示用戶對這個物品不感興趣，而只是意味著他們對該物品尚未表現(xiàn)出興趣。這可能是由于他們不關心或者不感興趣，或者是由于用戶在瀏覽的時候還沒看到這個物品。 隱式反饋數(shù)據(jù)集中，一組用戶對各種物品感興趣。請留意我們并不收集顯式的不喜歡行為，只是收集用戶收藏與否。 矩陣分解模型能夠生效的支撐假設是：在用戶和物品之間的相關度，能通過一個低維線性模型進行解釋。這意味著每一個物品和用戶確實對應一個未觀察的實數(shù)向量，在某些細小維度上?？臻g的坐標對應物品項的潛在特征（可以是：該物品是否是服裝，它是否有V形標識，畫面的背景是否為褐色等），用戶向量的元素描述了用戶對這些特征的偏好。我們可以將這些向量組成矩陣，一個用于用戶，一個用于物品，這樣觀察到的數(shù)據(jù)是通過取兩個位置矩陣和添加噪聲來產(chǎn)生的。 基礎低維模型是從觀察隱式反饋產(chǎn)生的，“d”是該模型的維度。 因此，我們?yōu)槊總€用戶和每個物品找到了一個的可以表示它們的向量。我們計算這些向量，使得用戶向量和物品向量之間的內(nèi)積，接近在隱式反饋矩陣所觀察到的值（在用戶喜歡這個物品的情況下，這個值接近1，否則接近0）. 將一個二維模型用于上述數(shù)據(jù)集的結(jié)果是，在這個小例子中，第一個被發(fā)現(xiàn)的特征是物品是否是一個架子，第二個特征是：是否是一個“幾何”風格。 因為在矩陣中的零不一定表示對物品不感興趣，我們不希望強制讓模型適合它們，因為用戶實際上可能是對其中的一些物品是有興趣。因此，我們找到分解，最小化加權(quán)誤差函數(shù)，其中，數(shù)據(jù)矩陣的非零項比零項的權(quán)重更高。這個來源于之前的一篇[文章]，這篇文章提出過這種方法。如何設置這些權(quán)重取決于矩陣的稀疏程度，并且可以通過某種形式的[交叉驗證]來發(fā)現(xiàn)。 當我們優(yōu)化上述的加權(quán)損失函數(shù)時會重構(gòu)矩陣（兩個因素的乘積），而這個矩陣在輸入矩陣中包含0的時候會包含一些積極的元素，因為我們不強制模型適用于這些以及非零的情況。這些都是用戶可能感興趣的但還沒見過的物品。出現(xiàn)這種情況的原因是為了使模型更好的適用，那些已經(jīng)對交叉的物品集感興趣的用戶會有相似的向量，對物品同樣是這樣。所以，沒有瀏覽過，但是被其他有相同興趣的用戶喜歡的物品，在重構(gòu)后的矩陣中，會有一個比較高的值。 交替最小二乘法 為了優(yōu)化這個模型，我們在物品矩陣和用戶矩陣之間進行交替計算，并在每個階段對加權(quán)平均誤差進行最小化，保持另一個矩陣的穩(wěn)定（因此命名為交替最小二乘）。在每個階段，因為有可行的分析方案，我們可以計算加權(quán)平方誤差的精確最小化。這意味著，每一次迭代都保證不會增加總誤差，而是降低到兩個矩陣構(gòu)成一個局部最小誤差函數(shù)。因此，整個過程將逐步減小誤差直到達到局部最小值。最小值的量可能會有所不同，所以它可能是一個合理的想法，重復上述步驟，并選擇最好的一個，雖然我們不這樣做。 這種方法的R Demo代碼在[這里]。 這個計算過程在MapReduce中實現(xiàn)起來是非常自然的。因為例如，當更新一個用戶向量時，所需要的就是：他互動過的物品向量，以及一個小的平方矩陣：通過將物品矩陣和它自己的轉(zhuǎn)置矩陣相乘。用這種方式計算每個用戶，可以用很有限的內(nèi)存，并且每個用戶可以被并行更新。更新物品的方法類似。有些用戶喜歡了很多物品，或者有些物品被很多用戶喜歡，這些計算需要更多的內(nèi)存。在這種情況下，我們對輸入矩陣進行抽樣，或者過濾掉這些物品，或者只取每一個用戶的最近喜歡寶貝。 當我們對模型滿意之后，我們可以持續(xù)的更新它（通過每晚重復ALS的幾個步驟），隨著越來越多信息，包括用戶，商品，收藏……流入線上系統(tǒng)。新物品和用戶能夠被方便的融入模型中，只要它們與模型中已有的用戶和物品之間有足夠多的交互。 這種方法的生產(chǎn)化MapReduce代碼在[這里]。 隨機SVD（奇異值分解） 上面描述的交替最小二乘法，給了我們一種簡單通過MapReduce對用戶偏好矩陣進行因式分解的方法。然而，它的缺點是需要多次迭代，有時花費很長時間達才能到一個好的結(jié)果。一個有吸引力的替代方案是隨機SVD。這個是一種較新的方法，類似于在一個超大矩陣上進行有名的SVD，采用了一個非迭代的MapReduece實現(xiàn)。我們將它實現(xiàn)為一個函數(shù)，它可以被任何一個可擴展的MapReduce Job調(diào)用。 線性代數(shù)中的一個基本結(jié)論是：通過對幾個緯度進行奇異值截斷后形成的矩陣，是所有同秩的矩陣中（從平方差角度來看）最佳近似的矩陣。然而，我們注意到，使用這種方法時，我們不能采用在ALS中使用的優(yōu)化方法：為錯誤值賦于同樣的“權(quán)重”的方法。但是對于某些數(shù)據(jù)集，如果其零的個數(shù)沒有壓倒性的超過非零，則此方法是可行的。舉個例子，我們可以用它成功地為用戶的收藏行為構(gòu)建一個模型，而不能用它對購買行為來構(gòu)建一個有用的模型，因為購買稀疏得多，權(quán)重是必要的。 這種方法的一個優(yōu)點是，它產(chǎn)生的矩陣有不錯的正則化結(jié)構(gòu)，因此能更容易的在線為新用戶構(gòu)造向量，因為沒有矩陣反轉(zhuǎn)是必須的。我們還使用這個方法產(chǎn)生除了用戶喜好以外其他物品清單的向量，例如珍藏品，或者其他用戶在Etsy創(chuàng)建的列表。用這種方法，我們可以從其它清單中，推薦其他相關物品。 產(chǎn)品推薦 一旦我們有了用戶和物品模型，我們就可以用它來構(gòu)建產(chǎn)品推薦。這是大多數(shù)研究文獻容易忽略的一個步驟。例如，我們不能期望以計算用戶和物品矩陣的乘積，然后為每個用戶找到最好的未發(fā)現(xiàn)的物品，因為這需要和時間成正比的物品數(shù)和用戶數(shù)的乘積，而這兩者都是在數(shù)億級。 一篇研究論文建議使用一種樹型數(shù)據(jù)結(jié)構(gòu)，以允許所述空間的非窮盡搜索，通過削減內(nèi)積太小的整個物品集中。但是，我們觀察到這種方法在實踐中沒有很好地工作，可能是由于維數(shù)與我們使用的模型類型的禍因（數(shù)百維度）。 因此我們用近似方法去計算推薦結(jié)果。這樣做是為了產(chǎn)生物品的第一候選集，然后根據(jù)內(nèi)積對它們進行排序，并取最高的。有幾種方法可以產(chǎn)生候選集，例如從用戶喜歡收藏的商店的清單，或者那些文本上類似于用戶收藏的。但是我們使用的主要方法是局部敏感性散列（LSH），其中我們把用戶和物品向量的空間分成幾個散列箱，再為取那些被映射到相同箱中的物品集作為每個用戶化的物品集。 局部敏感哈希 局部敏感哈希是一種用于在大型數(shù)據(jù)集中查找近似最小近鄰的技術。這個技術有幾種變種，但是我們專注于其中一個，設計用于處理實數(shù)數(shù)據(jù)和基于歐氏距離的近似最近鄰。 該方法的思想是將空間分隔成一組散列桶，以使它們在空間中靠近彼此的點有可能落入相同的桶中。我們這樣做是通過在空間中構(gòu)建平面中的一些數(shù)字“p”使他們都通過原點。這種劃分空間分成2 ^ P凸錐體，其中每一個構(gòu)成一個散列桶。 實際上，我們可以通過代表平面的法向量來實現(xiàn)這一點。一個點落在平面的一側(cè)，然后由點及法線矢量內(nèi)積的符號決定（如果平面是隨機的，毫無疑問我們將得到非零內(nèi)積，但原則上我們可以將這些點任意的分配到一側(cè)或者另一側(cè)）。產(chǎn)生這些法向量我們只需要空間中的各個方向隨機均勻。眾所周知，各項同性的高斯分布繪制有這樣的特性。 我們對散列桶進行標號，如果一個點和第i個平面的內(nèi)積為正，使得散列碼的第i位為1，否則為0，這意味著每個平面負責哈希碼中的一個比特。 在我們將每個點映射到各自對應的散列桶中，我們可以計算近似最近鄰或者等價的近似推薦，通過檢查同一個桶中的向量。平均每個桶中的數(shù)量將是2 ^ { - P}的點的總次數(shù)，因此，使用更多的平面使得過程非常有效率。但是它也降低了近似的準確度，因為它減少了附近指向任何目標點會在同一個桶的機會。 因此，要達到效率和質(zhì)量的折中，我們需要重復多次散列過程，然后再合并輸出。最后，為了獲得更多對計算過程的控制度，我們拋棄了較大的散列箱，從而實現(xiàn)高效的最近鄰計算。 使用Conjecture實現(xiàn)的代碼在[這里]。 其他思路 以上所述是個性化推薦的基本技術。在開發(fā)這些推薦系統(tǒng)的過程中，我們發(fā)現(xiàn)了一些可以改進的地方，幫助我們提高推薦的質(zhì)量。
結(jié)論 綜上所述，我們描述了如何基于隱式反饋數(shù)據(jù)為電子商務構(gòu)建推薦系統(tǒng)。我們建立了一個系統(tǒng)，在Hadoop上計算推薦結(jié)果，這是現(xiàn)在我們的開源機器學習包Conjecture的一部分。最后，我們分享了一些額外的技巧，關于如何做一些額外的調(diào)整來潛在地提高推薦的質(zhì)量。 |
|
|
