One of the main reasons of the rapid growth and development of e-commerce is the ability of on-line stores to provide large varieties of products, unlike their off-line counterparts, confined by stock spaces. This also means that on-line stores have products, which have few individual purchases but form a large chunk of revenue all together. They are known as "long-tail" products. Long-tail data sparsity makes it challenging to apply recommender algorithms. In this paper, we consider cross-sell recommendations using association rule mining. We consider application of clustering techniques to tackle this problem, and compare different clustering and distance calculation methods. Behavioral data, such as product views, and content data, such as category tree and product names, are used to calculate product similarity. Also, we develop a cross-validation method that allows stable metric calculations for algorithms that focus on long-tail products. We show that product clustering that uses session-based distances improve cross-sell recommendations for long-tail items.
Nowadays, recommender systems are omnipresent in on-line retail. In the last
decade, recommender systems have greatly developed. The growth of Internet
and e-commerce sites such as Amazon.com, Netflix, and the iTunes Music Store,
has opened the door to so-called "infinite-inventory" retailers, which offer large
variety of products. This distinguishes them in a positive way from off-line stores
which focus more on top-sellers and hits due to physical limitations of shops and
costly stock spaces [
Recommendations are called "cross-sell" when recommended items are
"complementary" to item being viewed (external battery and cases for phones; cables
and supports for TV) [
However, data sparsity makes it challenging to apply recommender algorithms. In our paper, we investigate item clustering approaches that group similar items together, and use such dense representation of data to improve quality of cross-sell recommendations generated by the association rule mining algorithm.
Below we consider related research, describe the approach to a decision of the problem, list the methods of the clustering and methods of measuring the distances between items, describe the experiments and see the results. 2
association rule mining (ARM) is a technique that extracts rules from dataset.
These rules are often written as X ) Y , where X is condition (antecedent,
driver), and Y is consequent. Both X and Y are sets of items. X represents the
set of items that a user has already purchased, and Y is the set of items that
the user is likely to purchase next. This technique was formalized in [
For given rule X ) Y , support is defined as
support(X ) Y ) = P (A \ B)
P (T ) is probability to find the transaction T in dataset. Support shows how often spe cified items appear in the dataset. Confidence of rule X ) Y is the ratio of the number of the transactions that contain X and Y over the number of the transaction containing Y , and defined as
conf idence(X ) Y ) = P (A \ B)=P (A)
Lift of rule X ) Y is the ratio of the observed support to that expected if X and Y were independent: (1) (2) lif t(X ) Y ) = P (X [ Y )=(P (X) P (Y )) (3)
ARM is an effective method for generating cross-sell recommendations. The
authors of [
In practice, recommendation systems face a long-tail problem when many
items were purchased and viewed few times in the dataset. It was shown in [
Long-tail effect is well-known, and many authors tried to improve the
recommendations for long-tail. Authors of [
Park in [
Lift is used to determine, which items are the best to be recommended for
given user’s history [
Item clustering is used to reinforce individual item data. For the item of
interest, we pick several nearest neighbors using some distance metric, and treat
this set as a single item [
We also have to employ some distance between products that can capture semantic similarity. For example, if many users have viewed specific pair of products together, these products are likely to be similar. 3.1
We considered two methods of clustering: total clustering and adaptive clustering
[
Total clustering For a specified item, this method picks into cluster K nearest neighbors to the item of interest, according to some distance metric. Adaptive clustering Premise of this method is that we want bigger clusters if the products have few records available for them, and smaller clusters if the products have enough data. So, let us define some threshold N , and pick the nearest neighbors one by one until the total sum of the picked items’ records exceeds the threshold. In our case, we count purchase orders. Note that different items will have different size of neighborhood. For instance, if an item is popular, it may even contain only the item itself. 3.2
Category Distance. Hierarchical category structure is commonly found in
ecommerce resources. We have a few top-level categories that have successors,
categories-successors has their successors and so on until we come to the leaves
of this structure — items. Category Distance between two items is the length of
the shortest path between these items [
Session Distance. We build the bipartite user-item graph [
Prod2Vec Distance. Prod2Vec model was proposed in [
We have to evaluate how well we are giving recommendations for users, for
given clustering algorithm and distance metric. NDCG [
In order to determine the best way of computing item similarity and the best clustering method, all combinations of the clustering methods and distance formulas are run. Also, we have to pick the best clustering hyperparameters. Therefore, each clustering-pair distance is evaluated several times, each time with different cluster size. Number of items per cluster is varied from 2 to 10 with step of 1 for total clustering, and number of purchases per cluster is varied from 15 to 300 with step of 15 for adaptive clustering. 4.1
We use data provided by e-commerce resource that have agreed to conduct experiments. Date ranges of datasets are non-disclosed, datasets contain a anonymized sampled data. Page views other than item page views are not used in this research. We have 2.3M of unique sessions, 8.5 of item view events, 50k products in catalog, 1k categories, and 434k of purchase orders. Most commonly purchased product has 130 purchases, and top-1% of most commonly purchased items account for 78% of revenue. 4.2
One of the challenges of working with a long-tail is cross-validation. If we split data with conventional k-fold split, then we would end up with dozen samples in train and test sets, and some products may have no samples in the test set at all. Therefore, we have designed the cross-validation procedure in a way that it would stratify data by products, guaranteeing data entries in both train and test for each item. Also, we considered highly-purchased products in order to have enough data to work with, and emulated long-tail sparsity by moving majority of the records to the test set. In order to ensure reproducibility, random seed was fixed.
Full evaluation procedure is described below: 1. Take all top-sellers (top-1% of items, ordered by sold quantity). Randomly assign half of them to "test items" set. 2. For every item in test items:
(a) Mark random 10% of sessions that have viewed this item 3. Put all events from sessions that have been marked, or have not viewed items from test item set, into train set, and move all other events to the test set. This action leaves only a small portion (10%..20% of original record count of test items) of data in the train set, effectively emulating environment with sparse data. Howewer, we keep a lot of records (80%..90%) in the test set to accurately assess the algorithm performance. 4. For each session in the test set: (a) For each item from the test item set, which was purchased within this session: i. Build recommendations for this particular purchase event, item and session: A. Run clustering with specified distance and settings to determine nearest neighbors to the item being purchased.
B. Fetch all orders that contain at least one item from the previous step.
C. Iterate over all items in these orders, and calculate Lif t(C; Y ), where C is purchased item neighbor cluster, and Y is a candidate item.
D. Exclude all the items selected at stage A from the result obtained at stage C.
E. Take 20 items with the highest lift value from obtained in stage D list, and recommend these items to user. ii. Assess recommendations quality for this particular purchase event, item and session.
Conventional stratified k-fold split would hide a portion (1/k) of data for each product. We are interested in long-tail, so we have to pick products with few records in train set. This also means that we would have even less records in test set for metric measurement. If we simply put most of the data in test set, it would put models in unrealistic situation where all items in train set have few records. For example, models would not be able to reinforce data by picking nearest popular product to the long-tail ones because all products will have few records left. This can be solved by hiding majority of records only for some products, and leave other products unaffected.
Also, users sessions can have complex structure. This is important for models
that use sequence of events, for example Prod2Vec [
Thus, our algorithm takes portion of popular products, and puts majority of sessions that have viewed these products in test set, leaving only few sessions in train set. After that, we measure how well algorithm makes recommendations for these products. Such cross-validation procedure forces algorithm to make recommendations using sparse train data for these products, but we also have large amount of records for metric measurement. This way we can properly assess recommender performance for long-tail products. 4.3
We use well known and often used NDCG@20 to asses recommendations quality
[
N DCG =
DCG IDCG
: n DCG = X i=1
reli log(i + 1) ; IDCG = jorderedRelj orderedReli
X
; i=1 log(i + 1) where reli is relevance of ith recommended item, orderedRel is the set of items ordered in descending order by their relevance. So, IDCG is normalization coefficient that ensures that N DCG lies between 0 and 1.
NDCG metric is calculated at step 5.a.ii of our algorithm for each instance when a test user buys a test item; after that, the values are averaged. Our (5) (6) goal is to guess what the user is going to purchase in the future. Therefore, we evaluate rel of the the recommended item as 1 if the user is going to purchase recommended item in future, and 0 otherwise. We skip instances when the user will not purchase any items in the future. 5
We can see that session-based distance works best for both types of clustering. Category-based distance provides low performance. We account this for the fact that categories ofter contain diverse sets of products, so clustering that uses category-based distance may include unrelated items in cluster. Prod2Vec distance also have not beaten baseline. This can be explained by the fact that long-tail products do not have enough data for this model. 6
We have used association rule mining in order to generate recommendations. We have shown that by using Jaccard’s measure as a distance between products, we can cluster similar items together; such clustering improves cross-sell quality for long-tail. Adaptive clustering that increases cluster size when there is lack of data works better than total clustering that always picks constant amount of neighbors.
In future works, we will should extend our approach. For example, we can combine several distance measures into one that works better. Also, currently we mine only rules with single cluster in antecedents, and item in consequents. We should consider mining rules with multiple clusters in antecedents, and clusters (instead of items) in consequents.