Industry Report Amazon.com Recommendations - UMD

1 Industry Report76 JANUARY FEBRUARY 2003 Published by the IEEE Computer Society1089-7801/03/$ 2003 IEEEIEEE INTERNET Item-to-Item collaborative FilteringRecommendation algorithms are bestknown for their use on e-commerce Websites,1where they use input about a cus-tomer s interests to generate a list of recommend-ed items. Many applications use only the itemsthat customers purchase and explicitly rate to rep-resent their interests, but they can also use otherattributes, including items viewed, demographicdata, subject interests, and favorite artists. At , we use recommendation algo-rithms to personalize the online store for each cus-tomer.

2 The store radically changes based on cus-tomer interests, showing programming titles to asoftware engineer and baby toys to a new click-through and conversion rates twoimportant measures of Web-based and emailadvertising effectiveness vastly exceed those ofuntargeted content such as banner advertisementsand top-seller lists. E-commerce recommendation algorithms oftenoperate in a challenging environment. For example: A large retailer might have huge amounts ofdata, tens of millions of customers and millionsof distinct catalog items. Many applications require the results set to bereturned in realtime, in no more than half asecond, while still producing high-quality rec-ommendations.

3 New customers typically have extremely limit-ed information, based on only a few purchasesor product ratings. Older customers can have a glut of information,based on thousands of purchases and ratings. Customer data is volatile: Each interaction pro-vides valuable customer data, and the algorithmmust respond immediately to new information. There are three common approaches to solving therecommendation problem: traditional collabora-tive filtering, cluster models, and search-basedmethods. Here, we compare these methods withour algorithm, which we call item-to-item collab-orative filtering. Unlike traditional collaborativefiltering, our algorithm s online computation scalesindependently of the number of customers andnumber of items in the product catalog.

4 Our algo-rithm produces Recommendations in realtime,scales to massive data sets, and generates high-quality AlgorithmsMost recommendation algorithms start by findinga set of customers whose purchased and rateditems overlap the user s purchased and algorithm aggregates items from thesesimilar customers, eliminates items the user hasalready purchased or rated, and recommends theremaining items to the user. Two popular versionsof these algorithms are collaborative filteringandcluster models. Other algorithms includingsearch-based methods and our own item-to-itemcollaborative filtering focus on finding similaritems, not similar customers.

5 For each of the user spurchased and rated items, the algorithm attemptsto find similar items. It then aggregates the simi-lar items and recommends them. Traditional collaborative FilteringA traditional collaborative filtering algorithm rep-resents a customer as an N-dimensional vector ofitems, where Nis the number of distinct catalogitems. The components of the vector are positivefor purchased or positively rated items and nega-tive for negatively rated items. To compensate forGreg Linden, Brent Smith, and Jeremy York items, the algorithm typically multi-plies the vector components by the inverse fre-quency (the inverse of the number of customerswho have purchased or rated the item), making lesswell-known items much more almostall customers, this vector is extremely algorithm generates recommendationsbased on a few customers who are most similar tothe user.

6 It can measure the similarity of two cus-tomers, A and B, in various ways; a commonmethod is to measure the cosine of the anglebetween the two vectors:4 The algorithm can select Recommendations fromthe similar customers items using various meth-ods as well, a common technique is to rank eachitem according to how many similar customerspurchased collaborative filtering to generate recom-mendations is computationally expensive. It isO(MN) in the worst case, where Mis the numberof customers and Nis the number of product cat-alog items, since it examines Mcustomers and upto Nitems for each customer.

7 However, becausethe average customer vector is extremely sparse,the algorithm s performance tends to be closer toO(M+ N). Scanning every customer is approxi-mately O(M), not O(MN), because almost all cus-tomer vectors contain a small number of items,regardless of the size of the catalog. But there area few customers who have purchased or rated asignificant percentage of the catalog, requiringO(N) processing time. Thus, the final performanceof the algorithm is approximately O(M + N). Evenso, for very large data sets such as 10 million ormore customers and 1 million or more catalogitems the algorithm encounters severe perfor-mance and scaling issues.

8 It is possible to partially address these scalingissues by reducing the data We can reduce Mby randomly sampling the customers or discardingcustomers with few purchases, and reduce Nby dis-carding very popular or unpopular items. It is alsopossible to reduce the number of items examinedby a small, constant factor by partitioning the itemspace based on product category or subject classi-fication. Dimensionality reduction techniques suchas clustering and principal component analysis canreduce Mor Nby a large , all these methods also reducerecommendation quality in several ways. First, ifthe algorithm examines only a small customersample, the selected customers will be less similarto the user.

9 Second, item-space partitioningrestricts Recommendations to a specific product orsubject area. Third, if the algorithm discards themost popular or unpopular items, they will neverappear as Recommendations , and customers whohave purchased only those items will not get rec-ommendations. Dimensionality reduction tech-niques applied to the item space tend to have thesame effect by eliminating low-frequency reduction applied to the customerspace effectively groups similar customers intoclusters; as we now describe, such clustering canalso degrade recommendation quality. Cluster ModelsTo find customers who are similar to the user, clus-ter models divide the customer base into many seg-ments and treat the task as a classification algorithm s goal is to assign the user to the seg-ment containing the most similar customers.

10 It thenuses the purchases and ratings of the customers inthe segment to generate segments typically are created using a clus-tering or other unsupervised learning algorithm,although some applications use manually deter-mined segments. Using a similarity metric, a clus-tering algorithm groups the most similar customerstogether to form clusters or segments. Becauseoptimal clustering over large data sets is imprac-tical, most applications use various forms ofgreedy cluster generation. These algorithms typi-cally start with an initial set of segments, whichoften contain one randomly selected customereach.