原文發(fā)表在：
Greg Linden, Brent Smith, Jeremy York, “Amazon.com Recommendations: Item-to-Item Collaborative Filtering,”?IEEE Internet Computing, vol. 7, no. 1, pp. 76-80, Jan./Feb. 2003, doi:10.1109/MIC.2003.1167344

以下全文翻譯的PDF點此下載。

Amazon.com 的推薦

從商品到商品的協(xié)同過濾

Greg Linden, Brent Smith, and Jeremy York ?Amazon.com

推薦算法以其在電子商務(wù)網(wǎng)站的用途而著稱1，它們利用有關(guān)一個顧客的興趣作為輸入，來產(chǎn)生一個推薦商品的列表。很多應(yīng)用僅僅使用顧客購買并明確表示代表其興趣的商品，但它們也可以利用其他屬性，包括已瀏覽的商品、人口統(tǒng)計特征數(shù)據(jù)、主題興趣，以及偏愛的藝術(shù)家。

在Amazon.com，我們利用推薦算法，對每位顧客提供在線商店個性化。在顧客興趣的基礎(chǔ)上，商店有了徹底的改觀，向一個軟件工程師展示編程類標(biāo)題，向一位新媽媽展示嬰兒玩具。點擊率和轉(zhuǎn)化率——基于網(wǎng)絡(luò)和郵件廣告的兩個重要評估指標(biāo)——極大地超越了那些未定向內(nèi)容，比如banner廣告和熱賣列表。

電子商務(wù)推薦算法經(jīng)常要運行在一個充滿挑戰(zhàn)的環(huán)境里。例如：
? 大型零售商有海量的數(shù)據(jù)，以千萬計的顧客，以及數(shù)以百萬計的登記在冊的不同商品。
? 許多應(yīng)用要求結(jié)果實時返回，在半秒之內(nèi)，還要產(chǎn)生高質(zhì)量的推薦。
? 新顧客很典型，他們的信息很有限，只能以少量購買或產(chǎn)品評級為基礎(chǔ)。
? 較老的顧客信息豐沛，以大量的購買和評級為基礎(chǔ)。
? 顧客數(shù)據(jù)不穩(wěn)定：每一次交互都可提供有價值的顧客數(shù)據(jù)，算法必須立即對新的信息作出響應(yīng)。

解決推薦問題有三個通常的途徑：傳統(tǒng)的協(xié)同過濾，聚類模型，以及基于搜索的方法。在此，我們就這些方法與我們的算法——我們稱之為商品到商品的協(xié)同過濾——進行對比。與傳統(tǒng)協(xié)同過濾不同，我們算法的在線計算規(guī)模，與顧客數(shù)量和產(chǎn)品目錄中的商品數(shù)量無關(guān)。我們的算法實時產(chǎn)生推薦，計算適應(yīng)海量數(shù)據(jù)集，并生成高質(zhì)量的推薦。

推薦算法

大多數(shù)推薦算法，都始于先找出一個顧客集合，他們買過和評級過的商品，與當(dāng)前用戶買過和評級過的商品有重疊2。算法把來自這些相似顧客的商品聚集起來，排除該用戶已經(jīng)購買過或評級過的商品，并向該用戶推薦其余的商品。這些算法有兩個最常見的版本：協(xié)同過濾和聚類模型。其他算法——包括基于搜索的方法以及我們自己的商品到商品協(xié)同過濾——都集中于尋找相似的商品，而不是相似的顧客。針對用戶所購買和評級的每一件商品，算法試圖找到相似的產(chǎn)品，然后聚集這些相似的商品，并給予推薦。

傳統(tǒng)的協(xié)同過濾

傳統(tǒng)的協(xié)同過濾算法把顧客描繪成商品的N維向量，其中N是登記在冊的不同商品的數(shù)量。對于買過或正面評級的商品，向量分量為正，對于負面評級的商品，向量分量為負。為彌補最熱賣的商品，算法典型地會把向量分量乘以反向頻率（已購買或評級該商品的顧客數(shù)量的倒數(shù)），以使不太知名的商品更加相關(guān)3。對幾乎所有的顧客來說，這個向量非常稀疏。
在與該用戶最相似的少數(shù)顧客基礎(chǔ)上，算法產(chǎn)生推薦。算法能夠測量兩個顧客的相似性，如A和B，有多種方式；一種常見的方法是測量這兩個向量之間的夾角余弦值4：

算法也能從相似顧客的商品里選擇推薦，有多種可以利用的方法，常見的一種技術(shù)是，按照購買該商品的相似顧客數(shù)量，對每件商品進行排序。

利用協(xié)同過濾來產(chǎn)生推薦，很耗計算。最壞的情況是O(MN)，其中M是顧客數(shù)量，N是產(chǎn)品目錄中商品的數(shù)量，因為算法要驗算M個顧客，并且對每個顧客最多要計算N種商品。但是，由于顧客向量的平均值很稀疏，算法的執(zhí)行更傾向于接近O(M + N)。掃描每一個顧客大約是O(M)，而不是O(MN)，因為幾乎所有顧客向量都只含有很少的商品，無需考慮產(chǎn)品目錄的規(guī)模。但有少數(shù)顧客，他們買過或評級過的商品在產(chǎn)品目錄中占有值得注意的百分比，需要O(N)處理時間。因此，算法最終執(zhí)行的大約是O(M + N)。盡管如此，對非常大的數(shù)據(jù)集來說——比如1千萬以上的顧客，以及1百萬以上登記在冊的商品——算法也會遭受嚴峻的性能和計算量問題。
通過減小數(shù)據(jù)量，可能部分緩解這些計算量的問題4。我們能夠減小M，通過對顧客進行隨機抽樣，或丟棄那些購買很少的顧客；我們也能減小N，通過丟棄那些極熱門和極冷門的商品。我們還可能減少所需計算的商品數(shù)量，通過一個小的常數(shù)因子，在產(chǎn)品類別或主題分類的基礎(chǔ)上，對商品空間進行區(qū)隔。諸如聚類和主分量分析等維度降低技術(shù)，也能很大程度減小M和N。
不幸的是，所有這些方法也會以各種形式降低推薦的品質(zhì)。首先，如果算法只是驗算了一小部分顧客樣本，那么被選定顧客與當(dāng)前用戶會較少相似。其次，商品空間區(qū)隔會把推薦限制在特定產(chǎn)品或主題領(lǐng)域之內(nèi)。第三，如果算法丟棄了最熱門或最冷門的商品，這些商品將不會出現(xiàn)在推薦中，并且，只購買過這些商品的顧客，將不會得到推薦。向商品空間應(yīng)用維度降低技術(shù)，會得到與排除冷門商品那樣相同的效果。向顧客空間應(yīng)用維度降低技術(shù)，能有效地把相似顧客組合為群組，正如我們現(xiàn)在所說的，這樣的聚類也會降低推薦的品質(zhì)。

聚類模型

為了尋找與當(dāng)前用戶相似的顧客，聚類模型對顧客基礎(chǔ)進行細分，并把這個任務(wù)當(dāng)做為分類問題。算法的目標(biāo)是，把該用戶分配到含有最相似顧客的細分人群里，然后，算法再利用該細分顧客人群的購買和評級，來生成推薦。典型地說，顧客細分的建立，會采用一種聚類或其他無人管理的學(xué)習(xí)算法，盡管某些應(yīng)用也用了手工決定的人群細分。利用一種相似性度量標(biāo)準(zhǔn)，聚類算法把最相似的顧客，分組聚合起來，形成聚類或細分人群。由于對大型數(shù)據(jù)集進行最理想的聚類不切合實際，大多數(shù)應(yīng)用都采用了各種形式的greedy聚類生成。典型的情況是，這些算法始于各細分人群的一個初始集，每個初始集通常包含一個隨機選定的顧客，然后算法不斷重復(fù)地把顧客與現(xiàn)有的細分人群進行匹配，一般也會某些規(guī)定，以創(chuàng)建新的細分人群或是合并人群6。對于非常大的數(shù)據(jù)集——尤其是維度很高——抽樣或維度降低也是必要的。
一旦算法生成了細分人群，就計算當(dāng)前用戶與概要描述每一細分人群的向量的相似性，然后選擇相似性最大的細分人群，并因此而對該用戶進行分類。某些算法把用戶分類進入多個細分人群，并對每組關(guān)系的強度進行描述。
較之協(xié)同過濾，聚類模型有更好的在線可擴展性和性能3，因為它們把當(dāng)前用戶與可控數(shù)量的細分人群進行對比，而不是整個顧客基數(shù)。復(fù)雜和昂貴的聚類計算會離線運行。然而，推薦品質(zhì)卻是低的1。聚類模型把無數(shù)的顧客分組進入細分人群，匹配一個用戶與一個細分人群，然后，以相似顧客細分人群里的所有顧客，來考慮產(chǎn)生推薦的目的。由于聚類模型發(fā)現(xiàn)的相似顧客并不是最相似的顧客，因而產(chǎn)生的推薦較少相關(guān)。通過大量精細粒度的細分人群，也可能提高推薦的品質(zhì)，但那樣一來，在線的用戶-細分人群分類，就會變得與利用協(xié)同過濾來尋找相似顧客幾乎一樣昂貴。

基于搜索的方法

基于搜索或內(nèi)容的方法，將推薦問題視為相關(guān)商品的搜索8。給定該用戶已買過和評級過的商品，算法構(gòu)造一個搜索查詢，以尋找其他熱賣的商品，通過同一作者、藝術(shù)家或?qū)а?，或利用相似的關(guān)鍵詞或主題。例如，如果一個顧客買了Godfather（教父）的DVD系列，系統(tǒng)就會推薦其他的犯罪劇，Marlon Brando出演的其他劇目，或由Francis Ford Coppola導(dǎo)演的其他電影。
如果該用戶只有少數(shù)購買或評級，基于搜索的推薦算法在計算量和性能上都不錯。然而，對于有數(shù)千次購買的用戶，要以針對所有商品的查詢?yōu)榛A(chǔ)也不太可行。算法必須使用一個數(shù)據(jù)的子集或概要，因此降低了推薦的品質(zhì)。在所有各種情況下，推薦品質(zhì)相對較差。推薦通常就是要么太寬泛（比如最熱賣的劇集DVD），要么太狹窄（比如同一個作者的全部圖書）。推薦應(yīng)該要幫助顧客找到和發(fā)現(xiàn)新的、相關(guān)的、有趣的商品。同一作者或同一主題領(lǐng)域的熱賣商品，沒有滿足這一目標(biāo)。

商品到商品的協(xié)同過濾
Amazon.com在很多郵件營銷活動，以及在其大多數(shù)的網(wǎng)頁上，包括流量極大的網(wǎng)站首頁，都把推薦作為一種定向營銷工具。點擊“你的推薦”鏈接，會把顧客引向一個區(qū)域，在那里，顧客可以通過產(chǎn)品線和主題領(lǐng)域，進行推薦的篩選，為被推薦的商品進行評級，為以前的購買進行評級，并查看為什么這些商品被推薦了（見圖1，圖在最后）。
如圖2（圖在最后）所示，即我們的購物車推薦，以其購物車中的商品為基礎(chǔ)，向顧客給出產(chǎn)品建議。這一特性與超市結(jié)賬臺路線上的沖動購買類商品很類似，但我們的沖動購買類商品定向到每位顧客。
Amazon.com廣泛地采用推薦算法，針對每個顧客的興趣進行網(wǎng)站的個性化。因為現(xiàn)有的推薦算法，與Amazon.com千萬級的用戶和產(chǎn)品數(shù)量不能相稱，我們開發(fā)了自己的算法。我們的算法，也就是商品到商品的協(xié)同過濾，符合海量的數(shù)據(jù)集和產(chǎn)品量，并能實時得到高品質(zhì)的推薦。

它如何工作

與把當(dāng)前用戶匹配到相似顧客的做法不同，商品到商品的協(xié)同過濾，把該用戶所購買和評級的商品，匹配到相似的商品，然后組合這些相似的商品進入推薦列表9。
對于給定的一件商品，為了決定最相似的匹配，算法通過發(fā)現(xiàn)顧客傾向于一起購買的商品，建立一個相似商品的表格。利用對所有產(chǎn)品配對的迭代，以及為每個產(chǎn)品配對計算相似性測度，我們能建立一個產(chǎn)品到產(chǎn)品的矩陣。然而，許多產(chǎn)品配對沒有普通顧客，因此在處理時間和內(nèi)存使用上，這種方法沒有效率。下述迭代算法提供了一種更好的方法，通過計算一件商品與所有相關(guān)產(chǎn)品之間的相似性：

For 每件商品 in 產(chǎn)品目錄,?I1
For 每位顧客?C?購買過?I1 的
For 每件商品?I2 ?由顧客?C?所購買的
記錄一顧客所購買的?I1??和?I2
For 每件商品?I2
計算相似度 在?I1 與?I2 之間

計算兩個商品之間的相似性可以有多種方法，但通常的方法是，利用我們前面描述的余弦值，其中每個向量對應(yīng)于一件商品而不是一位顧客，并且向量的M維度對應(yīng)于已購買過該商品的顧客。
這個相似商品表格的離線計算極費時間，最糟糕時需要O(N2M)。但在實際運行中，它接近O(NM)，因為大多數(shù)顧客只有很少的購買。對購買最熱門商品顧客的抽樣，進一步減少了運行時間，同時對推薦的品質(zhì)略有降低。
對于給定的相似商品表格，算法發(fā)現(xiàn)與當(dāng)前用戶每次購買和評級相似的商品，把這些商品聚集起來，然后推薦最暢銷或關(guān)聯(lián)最強的商品。這一計算很快速，僅僅取決于該用戶購買或評級過商品的數(shù)量。

可擴展性：比較

Amazon.com有超過2900萬顧客，以及數(shù)百萬登記在冊的商品。其他主要零售商也有同等大小的數(shù)據(jù)源。在所有這些數(shù)據(jù)提供機會的同時，也是一種詛咒，遠遠突破了那些針對小三個數(shù)量級的數(shù)據(jù)集所設(shè)計的算法的限度。幾乎全部的現(xiàn)有算法，都是在小數(shù)據(jù)集上評估的。如，MovieLens數(shù)據(jù)集4包含35000名顧客和3000件商品，EachMovie數(shù)據(jù)集3包含4000名顧客和1600件商品。
對于非常大的數(shù)據(jù)集，一個可擴展的推薦算法必須離線運行最昂貴的計算。正如下面的簡要對比所顯示的，現(xiàn)有方法達不到這樣的要求：
? 傳統(tǒng)的協(xié)同過濾只做很少或不做離線計算，其在線計算量取決于顧客和登記在冊商品的數(shù)量。在大數(shù)據(jù)集的情況下，這樣的算法不可行，除非使用維度降低、抽樣或區(qū)隔——所有這些都降低了推薦的品質(zhì)。
? 聚類模型能離線運行大量的計算，但推薦品質(zhì)相對較差。出于改進，可以增加人群細分的數(shù)量，但這會使在線的用戶-細分人群的分類變得昂貴。
? 基于搜索的模型離線建立起關(guān)鍵詞、范疇、作者索引，但不能提供符合興趣、定向內(nèi)容的推薦。對于購買和評級很多的顧客來說，這些算法的擴展性不佳。
商品到商品協(xié)同過濾的可擴展性和性能的關(guān)鍵是，它離線建立耗時巨大的相似商品表格。該算法的在線部分——針對當(dāng)前用戶的購買和評級來尋找相似的商品——計算量獨立于商品目錄的規(guī)?；蝾櫩偷目倲?shù)；僅僅取決于該用戶買過或評級過多少個商品。因此，甚至是對于超大數(shù)據(jù)集，算法也很快速。由于該算法能推薦高度關(guān)聯(lián)的相似商品，推薦的品質(zhì)就很出色10。與傳統(tǒng)的協(xié)同過濾不同，該算法在用戶數(shù)據(jù)有限的情況下也能運行良好，在少至2到3件商品的基礎(chǔ)上，產(chǎn)生高品質(zhì)的推薦。

結(jié)論

通過為每位顧客建立個性化的購物體驗，推薦算法提供了一種有效的定向營銷形式。對于Amazon.com這樣的大型零售商，良好的推薦算法可在海量顧客基數(shù)和商品目錄上進行擴展，只需要子秒處理時間就能產(chǎn)生在線推薦，能對用戶數(shù)據(jù)里的變化立即做出反應(yīng)，并能為所有用戶提供引人關(guān)注的推薦，而無需考慮購買和評級的數(shù)量。與其他算法不同，商品到商品的協(xié)同過濾能滿足這樣的挑戰(zhàn)。
未來，我們期望零售業(yè)為定向營銷更廣泛地應(yīng)用推薦算法，包括網(wǎng)上和網(wǎng)下。對個性化來說，電子商務(wù)擁有最方便的工具，而同時，較之傳統(tǒng)撒大網(wǎng)的方式，該技術(shù)對轉(zhuǎn)化率的提升，也會引起網(wǎng)下零售商的關(guān)注，可用于信件、優(yōu)惠券及其他顧客通信中。

作者

Greg Linden是Amazon.com個性化部門的共同創(chuàng)始人、研究員及高級經(jīng)理，他設(shè)計和開發(fā)了推薦算法。他目前是斯坦福大學(xué)商業(yè)研究生院Sloan Program中的管理學(xué)研究生。他的研究興趣包括推薦系統(tǒng)、個性化、數(shù)據(jù)挖掘以及人工智能。Linden在華盛頓大學(xué)獲得了計算機科學(xué)的理學(xué)碩士。聯(lián)系方式：Linden_Greg@gsb.stanford.edu。

Brent Smith領(lǐng)導(dǎo)著Amazon.com的自動化銷售團隊。他的研究興趣包括數(shù)據(jù)挖掘、機器學(xué)習(xí)以及推薦系統(tǒng)。他在San Diego的加州大學(xué)獲得了數(shù)學(xué)的學(xué)士，在華盛頓大學(xué)獲得了數(shù)學(xué)的理學(xué)碩士，并在那里做了些微分幾何的研究工作。聯(lián)系方式：smithbr@amazon.com。

Jeremy York領(lǐng)導(dǎo)著Amazon.com的自動化內(nèi)容選擇和交付團隊。他的興趣包括分類數(shù)據(jù)的統(tǒng)計模型、推薦系統(tǒng)，以及網(wǎng)站展示內(nèi)容的最佳選擇。他從華盛頓大學(xué)獲得了統(tǒng)計學(xué)的博士學(xué)位，在那里，他的論文獲得了Leonard J. Savage獎的貝葉斯應(yīng)用計量經(jīng)濟學(xué)和統(tǒng)計學(xué)的最佳論文獎。聯(lián)系方式：jeremy@amazon.com。

圖1 Amazon.com主頁上“你的推薦”特性。
利用這一特性，顧客能夠?qū)ν扑]進行排序，并加入他們自己的產(chǎn)品評級。

圖2 Amazon.com的購物車推薦。
該推薦的基礎(chǔ)是顧客購物車中的商品：Pragmatic Programmer 和 Physics for Game Developers。

來源：http://blog.sina.com.cn/s/blog_586631940100pduh.html