In the context of stereotypes creation for recommender systems, we found that certain types of categorical variables pose particular challenges if simple clustering procedures were employed with the objective to create stereotypes. A categorical variable is defined to be complex when it cannot be easily translated into a numerical variable, when the semantic of the categories potentially plays an important role in the optimal determination of stereotypes, and when it is also multi-choice (e.g., each item can be labelled with one or more categories that may be applicable, in a non pre-defined number). The main objective of this paper is to analyse the possibility of obtaining a viable recommendation system that operates on stereotypes generated directly via the feature's metadata similarities, without using ratings information at the time the generation of the classes. The encouraging results using integrated MovieLens and Imdb data set show that the proposed algorithm performs better than other categorical clustering algorithms like k-modes when clustering complex categorical features. Notably, the representation of complex categorical features can help to alleviate cold-start issues in recommender systems.
The growing importance of recommender systems has motivated
the research community to look for diverse techniques and
approaches to solve challenges like the "new user" or "new item"
problems. A promising approach for improving recommendations in the
cold start phases for the new user/item problem is stereotype based
modeling. Rich [
Historically, in the pioneering works on stereotyping, the
majority of the stereotype classes were built manually by the
operator with knowledge of the problem and data, see for example
[
A machine learning based study should address the design of the
optimal data representation to tackle the problem at hand, and the
same applies to stereotyping; a deeper understanding of the
underlying features that are involved in the generation of the stereotypes
will help design better algorithms. The stereotyping process is made
more challenging, but at the same time more representative of
realworld applications, by the presence of categorical variables which
are multi-entry in a non-strict sense, i.e. the number of multiple
labels describing a category for an item/user is not pre-specified.
In some ways these variables can be viewed as multiple choice
answers to a questionnaire, with the underlying idea of "pick all that
applies". For example in the MovieLens and Imdb data sets, [
Complex categorical features - especially when treated via a naive one to enne encoding, and when their dimensionality is large - ends up constituting the features that dominate the stereotype creation via clustering techniques; this implies that these types of features should be potentially addressed in a diferent manner in the context of stereotyping. The present paper main contribution is to demonstrate how item stereotypes can be built automatically for complex categorical features in a way that is independent of user’s rating. Ultimately, demonstrating how the use of stereotypes can be efective during the cold start phase.
The rest of the paper is organized as follows: Section 2 summarizes related work. A correlation matrix analysis leading to discover stereotypes automatically is presented in Section 3. An experiment to benchmark our algorithm with k-modes as well as application of stereotypes to recommendation system is carried out in Section 4 and 5. Finally, conclusion and future work are given in Section 6. 2
Clustering based algorithms applied to a data set describing items can provide either a direct representation of stereotypes or provide valuable insights in what features are most distinctively driving class separations. The main challenge in the application of a clustering algorithm to the general problem of extracting classes from the data resides in the standardization of the data. In the most common scenario mixed numerical and categorical features are present; in addition, extra complexity may arise by categorical features that are not simply labels but may require machine-based insights in the language in which they are expressed.
Standard clustering algorithms, like the well-known k-means and
its variations, discover structures in the data by working with
Euclidean distances, and minimizing the total variance of the distances
between the cluster’s centroids and the individual data points, see
[
A body of research exists for the application of clustering
concepts to categorical data, in [
The authors in [
It is paramount to create a mechanism to handle complex categorical features. To the best of the authors’ knowledge all possible categorical clustering algorithms available (like k-modes and its possible variations) have been developed for single choice categorical variables, and hence they cannot be applied directly when there are multi-choice categorical features. Additionally, the majority of the clustering, similarity metrics, as well as dimensionality reduction approaches operate on the users to items rating matrix. The present work analyses a diferent aspect, namely the possibility of obtaining a viable recommendation system that operate on stereotypes that are generated directly via the feature’s metadata similarity, without using the rating at the time of the generation of the classes. 3
For a typical multi-entry categorical feature that describes a given
item, there will be a number of entries where multiple labels are
assigned to the same item. By investigating a large enough set of
items with multiple entries one can extract what type of
relationships exist, if any, between pairwise labels. This can be done by
investigating the correlation matrix of the encoded multi-entry
feature. The use of correlation, and in particular of the correlation
matrix between pairwise labels, which is defined starting from
the covariance matrix, is supported by the objective to search for
intrinsic relationships between the labels that are present in the
sample data. For a revision of the basic statistical concepts behind
covariance and correlation see for example [
The first step consists of converting the categorical feature in a multi-one-hot encoding, and then computing the correlation matrix between categories. The word multi in front refers to the fact that each item can be specified with one or more (pick all that apply) categories so the encoding has as many ones. The correlation matrix can be defined in a standard way; given a multi-one hot encoded observation for the multi-entry categorical feature, xi for i = 1, . . . , N possible categories, the covariance matrix is defined as:
CVi, j = E [(Xi − µ i )(Xj − µ j )] i, j = 1, . . . , N (1) µ k = E [Xk ]
Where E[ ] is the expected value operator. From the covariance matrix, the correlation matrix R is obtained using the product of the standard deviations along directions i, j as a normalization coeficient: (2) (3) Ri, j =
CVi, j σi σj σk2 = E [(Xk − µ k )2]
The values in the correlation matrix 2 would already suggest,
for the cases where the labels are not many, which categories can
better be coupled with each other. To enhance further the grouping
between categories, one can group (also improperly called
clustering) entries of the correlation matrix that are most related between
each other. Several algorithms have been proposed in the literature,
see for example [
Pi, j = 1 − |Ri, j |
Which constitutes a simple linear penalty: low correlations around 0 are penalized more than high positive or negative correlations (near +/- 1).
For this research a greedy grid search algorithm was developed
to rank possible permutations of columns and rows in the
correlation matrix to gain an initial understanding of the grouping in
the two large and significant complex features: "movie genre" and
"keywords" in the MovieLens/Imdb data sets [
When the greedy grid search is applied to the row/columns permutations of the "genre" feature, the correlation matrix shown in Figure 1 is obtained. The permutations make it easier to identify "groups" that can be considered as clusters for that feature, groups which we will refer to as stereotypes. In the case at hand for the feature "genre" we can see that the first group is constituted by ("Film-Noir", "Thriller", "Crime" and "Mystery"). A second group is constituted by ("Children’s", "Animation", "Family", "Fantasy") etc.
A similar correlation analysis was performed for the feature
"keywords" by restricting the attention to keywords that appear
in the training data a suficient number of times, in order to avoid
iftting any pattern to keywords that are rarely used. In this context,
only keywords that were used at least 20 times over the items of
the data were retained. Keyword correlations are in general much
weaker than those for genre, as a result of the vast "scattering" over
hundreds of keywords over the data.
The simplified analysis conducted via the permutation algorithm
motivates the use of a more rigorous clustering approach for the
definition of stereotypes in complex categorical features. Following
[
To be able to respect these properties starting from the definition
of correlation, the latter needs to be inverted, in the sense that
the closer the correlation to |1|, the smaller the distance, with the
limiting case of correlation going toward +1 (-1) and distance
approaching 0. Such an inverted correlation metric can be obtained in
several diferent ways, and it is often called dissimilarity measure,
see [
Di(,aj) = 1 − |Ri, j | Di(,aj) = q
2 1 − Ri, j
As discussed, the dissimilarity measures need to be
complimented with a linkage criterion. In the hierarchical clustering
literature there are many alternative linkages proposed, see [
The two metrics for dissimilarity 4 and 5 are applied in a hierarchical clustering algorithm via the three alternative linkages criteria to the correlation matrix for the feature "genre" and "keywords". Investigation of the results leads to several general observations. The first observation is that, regardless of the linkage adopted, dissimilarity metric 5 tends to compress excessively toward 1.0 entries that have low correlations (below 0.4 - 0.5 in absolute value). The spectrum of correlation values between 0 and 0.5 will lead to a (4) (5) dissimilarities between 0.8660 and 1.0. When these dissimilarities are investigated via the dendrogram formation the resulting dendrograms appear to be too compressed for matrices that tends to have average low correlations in magnitude. Measure 5 therefore is more suited for exploring situations where the correlations tend to be high in average over the correlation matrix, above 0.4 - 0.5 in absolute value. As a rule of thumb there should not be more than a handful of pairwise correlation entries above 0.4 to use measure 4. For this reason, attention in this paper will be focused to just dissimilarity 4 for all linkages.
The logical grouping identified by single linkage and
dissimilarity 4 (not shown) - seems to be less congruent with a "human"
subjective assignment. A metric could be used to evaluate the
hierarchical links discovered, see for example the Fowkles and Mallows
metric [
The groupings provided by the complete linkage (no shown) and Ward linkage as shown in Figure 2, are overall similar. However, the Ward linkage seems to better represent the hierarchical links between diferent levels of the groupings.
The same hierarchical clustering of the correlation matrix, and dendrogram study of the linkage dissimilarity splits, is then applied to the other complex categorical feature of the sample data under investigation: "keywords". It was previously observed, Section 3, that the average in sample correlation between keywords falls in a similar range of values, if not lower, as the average correlation among categories of the genre feature. For such a reason given the previous observation about the fact that the dissimilarity measure 5 tends to compress toward 1.0 low absolute values of correlation and to provide a greater zoom on higher correlation values, measure 5 will be put aside in favour of dissimilarity measure 4.
In a similar fashion as that observed before, the complete linkage, and the Ward linkage, have proved to be better distinctions and grouping criteria. Confirming the findings from the analysis on the feature genre, it is possible to see how the two linkages form very similar groups across keywords dendrograms (not displayed), and how such groups can be "approved" from the subjective point of view of the categorization. However, the Ward linkage appears once more to be superior in defining a better vertical separation of the logical links in the dendrogram. This characteristic is extremely important when considering possible diferent levels for cutting automatically a dendrogram as a way to create logical groups for the labels of a complex categorical feature. to finding the highest iteration exhibiting a local minimum in the iteration ratio. The only situation in which this idea would fail is in the case of a monotonically increasing dendrogram iteration ratio, that is found when there are no real underlying groups in the data, and the data is just grouped into an ever growing single cluster that will end up comprising the entire data set. In this special case the conclusion should be: the feature cannot be split into stereotypes. The algorithm to create stereotypes for complex categorical features is illustrated in Figure 4 for completeness. The application of the algorithm of Figure 4 to the genre and keyword features leads to the stereotypes of Table 1. It was observed in Section 3.1 that the vertical separation between the splits in the branches of a dendrogram, especially the one provided by Ward’s linkage criterion, would be ideal for calibrating the height of a truncation in the dendrogram, thus obtaining as a result the groups of labels, hence the stereotypes. In order to accomplish the automatic stereotype creation, a systematic cutof should be selected to decide at which height of the dissimilarity linkage one should truncate the dendrogram.
A dendrogram truncation criteria can be implemented by examining how the linkage merge iterations are shaping the clusters discovered from the bottom up (i.e. from the stronger links toward weaker links). As the iterations progress the number of clusters formed grows, then from a critical iteration onward, the structures discovered begin to merge toward a single cluster. This dynamic can be summarized by monitoring the average cluster size and the number of clusters formed up to a given iteration. The cut of procedure can therefore be implemented via a dual criterion: • By looking for the last maximum, or last local plateau in the number of clusters as a function of the iteration. • By applying a reverse elbow procedure to the average cluster size.
The two criteria can also be coupled by taking the ratio, at any iteration, of the average cluster size divided by the number of clusters formed. This is shown for convenience in Figure 3 for the genre feature, and for simplicity such quantity will be referred to as dendrogram iteration ratio. The cutof procedure then reduces
In this Section the clustering results (Table 1) of the automatic
stereotype algorithm suggested are compared with the results of
the categorical clustering algorithm k-modes [
In order to apply k-modes, for each possible label of the complex categorical feature under investigation, a new variable is introduced to represent a true/false encoding. This is not dissimilar from the concept of one to enne encoding, but in this context it is used to define not a numerical coordinate, but a multi-valued categorical representation instead.
The k-modes clustering algorithm can be initialized in diferent
ways, for example following Huang [
An inverse elbow methodology is applied to the cost function of k-modes as displayed in Figure 5 for the genre feature partitioned via k-modes with both "Huang" and "Cao" initializations. Both cost functions decay with a lower rate of decay as the number of clusters, k, increases. However, it is not straightforward to identify a single well-defined kink in the decay graphs, and for this reason the results of the k-modes clustering for the genre feature are inspected by looking at the centroid characteristics at both (k=5) and (k=10).
Table 2 displays the result for (k=5). The most interesting finding (also applied when k=10, not shown) is that the frequency approach underneath k-modes leads to absence of lower frequency labels. For example, genres like "War", "Western" and "Documentry" are not presented due to lower frequency in the item population. However, we argue that these labels should indeed be retained as they may represent specific niche users preferences, and are required in the recommendation items coordinates. Similar results were obtained concerning the application of k-mode for the feature keywords (not shown), and our empirical experience lead us to favor our algorithm over k-mode for the stereotype construction of complex categorical features. 5
In the literature related to the application of recommender systems
to predict cold start users’ ratings on movies, the predictive
algorithms applied most often aim to predict ratings. Our data set is
assembled by combining the rating data from the MovieLens data
set with the Imdb movie attributes. The combined data set contains
1,000,209 ratings, 6,040 users and 3,827 movies. The rating is an
integer value ranging from 1 to 5. Each movie can be categorised
with 24 diferent genres and 71 diferent keywords (keywords that
appear in the dataset more than 20 times). Generally, user-item
ratings exhibit diferent kinds of global efects [
In our study we normalize the ratings made by each user by converting them to standard scores: r˜ = (r − µcu ) (6) σu c
Where µcu is the mean rating per each user and σu is the standard deviation per each user.
We generated two recommendation models: a "baseline model" which uses all features available in the data in the way they are provided (this is the model against which we benchmark our results), and a "stereotypes-based model" where complex categorical features have been stereotyped but all remaining features remain the way they are. In order to measure the impact of replacing the original features with the stereotypes, and simulate cold start situations (new users/new items), the data set has been split into two alternative experimental sets: • Split A - For each item in the data set the models are trained on the preference set expressed by a subset of users (randomly selected). The remaining users are left out, and used to test the accuracy of the models; this method enables us to simulate the performance on "new users". • Split B - For each user in the data set the models is trained on all preferences expressed for a subset of items (randomly selected). The remaining items are left out, and used to the accuracy of the models; this method enables us to simulate the performances on "new items".
For each of the two experiments we have tested several machine learning algorithms from the simplest method (Linear regression) to the most popular (Neural Networks and XGBoost) with the aim to improve model performances and to confirm that our conclusions related to the application of stereotypes do not depend on the model chosen.
It should be noted that, for numerical regression style models, there is no guarantee that the rating will fall between 1 and 5, therefore the resulting prediction, when transformed back (rescaled) into a rating "r", must be capped/floored in the following manner: • 1 if r ≤ 1 • 5 if r ≥ 5 • r otherwise
The only diferences between the two experiments consist in how complex categorical features are treated. In the baseline model all features (both for items and for users) are treated as they are in the original data set. While in the stereotype model, complex categorical features are treated via the rating independent stereotypes previously generated in Section 3.2.
As a measure of accuracy of the results, we report the model performance using the Root Mean Squared Error (RMSE) along with the Mean Absolute Error (MAE). In real word recommendation problems, where we usually deal with huge databases, it is crucial to adopt algorithm that is capable of scaling up. In fact, this is one of the advantages of stereotype model. We are reporting the execution speed in seconds as measured on a Intel Core i7 -7700K CPU @ 4.2 GHz with 64.0 GB RAM.
The results reported in Table 3 for both experiments, are the average of a 6-fold cross validation. The result highlight the double benefit of a stereotype-based approach: consistence improvement in prediction accuracy in cold start, and an improved computational time, due to the inherent feature space reduction and grouping that stereotype bring to the problem. For example, using NN Regression and stereotypes lead to an accuracy that is higher than XGBoost using standard features (i.e. baseline) with a time saving of over 35 seconds in new user case. This implies that the improvements in using stereotypes are higher than the improvements in increasing the model complexity from a simple linear regression to XGBoost. Therefore, providing more grounded evidence for the use of stereotypes in cold start phases. 6
In this work, hierarchical clustering of the correlation matrix of complex categorical features is conducted, leading to the formulation of an algorithm for the automatic identification of stereotypes. This can be viewed as a form of feature engineering, where patterns discovered in the correlation matrix are used to drastically simplify a complex categorical feature. The rating independent clusters leads to subjective groups that seem to better partition into classes - stereotypes - than those suggested by the application of k-modes. The lack of a frequency overweight of the labels allows to stereotype all categories, also those that have only a small amount of samples in the data set.
The stereotypes obtained with the proposed algorithm are then used in recommendation. We have shown how, for the experimental MovieLens and Imdb data sets, the stereotype base model outperform a standard feature based recommendation approach for the new user/new item problems.
Stereotyping numerical features to study the efect of both categorical and numerical stereotypes on the recommendation is the obvious next step. More emphasis should be toward extra reduction in the dimension of the recommendation model, and to improve the quality of recommendations in the new user and new item scenarios (cold start problem). Additional future work will include measuring other metrics including computational eficiency and diversity of recommendation.