The process of predicting news stories popularity from several news sources has become a challenge of great importance for both news producers and readers. In this paper, we investigate methods for automatically predicting the number of clicks on a news story during one hour. Our approach is a combination of additive regression and bagging applied over a M5P regression tree using a logarithmic scale (log10). The features included are social-based (social network metadata from Facebook), content-based (automatically extracted keyphrases, and stylometric statistics from news titles), and time-based. In 1st Sapo Data Challenge we obtained 11.99% as mean relative error value which put us in the 4th place out of 26 participants. 1 http://labs.sapo.pt/blog/2011/03/10/1st-sapo-data-challenge/ Predicting the popularity of a news story is a difficult task [9]. Popularity of a story can be measured in terms of the number of views, votes or clicks it receives in a period of time. Clickthrough rate (CTR) is the most popular way of measuring success [7, 10]. It is defined as the ratio of the number of times the user clicked on a page link and the total number of times the link was presented. Popularity of a news story is influenced by many factors, including the item's quality, social influence and novelty. The item's quality is mixture of fluency, rhetoric devices, vocabulary usage, readability level, and the ideas expressed which makes quality hard to measure [15]. The social influence consists on knowing about other people's choices and opinions [9]. Salganik et al. [15] show that item's quality is a weaker predictor of popularity than social influence. This partially explains the difficulty of predicting article popularity based solely on its content and novelty. Most popular portals such as Digg and Slashdot allow users to submit and rate news stories by voting on them. This information is often used by a collaborative filtering algorithm to predict popularity, select and order news items [8, 9, 16]. Typically, these models perform linear regression [18] on a logarithmically transformed data. In this paper, we present an approach for predicting the click rate based on a combination of content-based, social network-based, and time-based features. The main novelty of the approach is the type of content-based features we extract (e.g.: number of keyphrases), the inclusion of time-based features, and the prediction process that combines several regression methods to produce and estimate of a number of clicks per hour. This paper is organized as follows: Section 2 presents the dataset used to train and test our predictions system; the description of the proposed prediction methodology is presented in Section 3; the results are described in Section 4, and Section 5 contains conclusions and suggestions for future work.
1. INTRODUCTION “Can we predict the number of clicks that a news story link receives during one hour”? This was the main research question proposed in the 1st Sapo Data Challenge – Traffic prediction1 launched by PT Comunicações. Sapo is the largest Portuguese web portal. Its home page (http://www.sapo.pt) receives about 13 million daily page views and 2.5 million daily visits2. The home page has several sections that link to different types of content, such as news, videos, opinion articles, blog previews, etc. Currently, the selection and ordering of news stories is done mostly manually by the site editors. Obviously, manual solutions do not scale and we need to find a method for automatically predicting popularity of news stories.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The dataset contains 13140 link-hour entries from 1217 news story links gathered from several news sources over 15 consecutive days. Each link-hour entry records the number of clicks on a particular link shown in Sapo Portal (Figure 1) during a particular hour. Each entry contains 8 fields: 1.
Line Number: number identifying the entry.
which the hits took place as a string.
Channel ID: a number identifying Sapo’s source (channel) that produced the content. There are contents from 18 different sources.
Section (topic): there are 5 possible sections: general, sport, economy, technology, and life.
Subsection: each placeholder is further divided in five subsections: “manchete”, “headlines” and “related”, “footer” and “null”. This is an important parameter because each subsection is visually smaller than the previous ones when presented to the user (Figure 1).
News ID: an integer identifying the content.
Number of hits/clicks: the number of hits that the linked content received, during one hour (see field 2 above).
Title: the title of the news story.
Example: [13116] [2011-03-08 23:00:00] [
To address the prediction of clicks challenge, we adopted a
supervised learning framework, based on WEKA [
Figure 6 provides an overview of the feature extraction process which starts with the initial (base) features taken from the dataset entries and produces an enriched set of 3 types of features: content-based, social network-based, and time-based. The content-based features include: the number of web pages containing the same title (F1), the number of occurrences of certain key phrases in news articles (F3), and the stylometric features of the title (F4).
We use the news title as query in the Sapo RSS search interface to get the total number of stories with the same title (F1). Initial Features
Title
URL extraction
Facebook Stats
Extraction Text Extraction
AKE Title Features Extraction
All
Features
The main textual content is extracted using the boilerpipe library
[
We filtered key phrases, extracted using the AKE system, with a confidence level lower than 50%. Their number of occurrences is used as features of an article (F3). The final list of key phrases contains 34 key phrases, e.g.: Portugal, United States, market. These key phrases are used to compare the content of news stories.
The stylometric features of the title (F4) include: the number of words, maximum word length, minimum word length, the number of quotes, the number of capital letters, and the number of named entities identified by MorphAdorner Name Recognizer3.
The social network-based features are metadata information retrieved from Facebook (F2). The social-based features are extracted by calling the Facebook API and retrieving Facebook Metadata or statistics containing the URL of the article: the number of shares, the number of likes, the number of comments, and the total number of occurrences in Facebook data. We have also extracted Twitter metadata, i.e., the number of tweets, but it was excluded because Portuguese news tweets containing URLs are rare.
There are 3 time-based features: day, time and the number of hours elapsed from the initial publication of the article (F5). The number of hours elapsed from the initial publication of an article (F5) is used as the initial approximation of its novelty.
The goal of regression methods is to build a function f(x) that maps a set of independent variables or features (X1, X2,..., Xn) into a dependent variable or label Y. In our case, we aim to build regression models using a training dataset to predict the number of clicks in the test set.
In this work we explored a combination of regression algorithms. We explored linear regression, regression trees: REPTree and M5P.To further improve the results, we combined the best performing regression algorithm (M5P) with two metaalgorithms: Additive Regression and Bagging.
The REPTree algorithm is fast regression tree learner based on
C4.5 [
The M5P algorithm is used for building regression-based
trees[
Bagging, also known as Bootstrap aggregating, is a machine
learning meta-algorithm proposed by Breiman [
The idea consists of using multiple versions of a training set; each version is created by randomly selecting samples of the training dataset, with replacement. For each subset, a regression model is built by applying a previously selected learning algorithm. The learning algorithm must remain the same in all iterations. The final prediction is given by averaging the predictions of all the individual classifiers.
Additive regression, or Stochastic Gradient boosting [
This method is an iterative algorithm, which constructs additive models (sum of weak learners – Equation 2) by fitting a base learner to the current residue at each iteration. The residue is the gradient of the loss function L(ti, si); where ti is the true value of the sample and si = Hk-1(xi). The default loss function is least squares. At each iteration, a subsample of data is drawn uniformly at random, without replacement, from the full training set. This random subsample is used to train the base learner ℎ! ! to produce a model (Equation 2) for the current iteration.
! !! ! =
!! ℎ! ! (2) !!! where !! denotes the learning rate (expansion coefficients), k is the number of iterations and x is the features vector.
Because bagging is more robust than additive regression in noisy
datasets, but additive regression performs better in reduced or
noise-free data, Sotiris [
In this section, we describe the evaluation procedures used during this work. We divided the evaluation in 2 stages: at first, the test set was not available and we used the training set for the experiments using 10-fold cross-validation. When the test set became available, we trained on the whole training set and evaluated on the test set. We evaluated our results using Mean Absolute Error and Relative Absolute Error. Assume that pi is the predicted number of clicks and ti is the true value, then: !"#
! !"# ! ! !!! ! !!! !"(!)
!! !"#$%&'( !""#": !"(!) = |!! − !!| (3) !"#$%&'" !""#": !" ! =
(4) !"#"$%&'() !"#$%&'( !""#": !"# = !"(!) (5) !"#"$%&'() !"#$%&'" !""#": !"# = !"(!) (6) !"#$ !"#$%&'( !""#": !"# = (7) !"#$ !"#$%&'" !""#": !"# = (8) The challenges results were presented in Cumulative Absolute Error and Cumulative Relative error. In this paper we opted to provide their means to make the results comparable (cumulative results depend on the number of examples). It is important to note that relative absolute error displayed in the WEKA interface differs from the equations above, and as a result it was not used in this work. In the WEKA interface this measure divides the mean absolute error by the corresponding error of the ZeroR classifier on the data (i.e.: the classifier predicting the prior probabilities of the classes or values observed in the data).
Table 1 shows the results using several supervised machinelearning techniques obtained in the first evaluation stage. This evaluation was performed in the training set using 10 fold cross validation. We tried both REPTree and linear regression, because they have a faster training time. In addition, linear regression is the most frequent method selected for popularity estimation. Nevertheless, they were outperformed by M5P.
M5P regression generates outlier predictions, i.e.: a negative number of clicks or very large number of clicks. We have considered two possibilities to solve this problem: either setting all outliers to 1; or changing the negative outliers values to 1 and the positive outliers to the maximum number of clicks. The first solution gave better results. The lack of information justifies the occurrence of these outliers. Therefore, we used the most frequent value (1) given the number of clicks distribution (Figure 2). The conversion of the number of clicks to a logarithmic scale helped to approximate a linear distribution to which our methods could be better suited. This fact is easy to understand by comparing the distribution of clicks in Figure 2 and 3. In addition, it also helped to eliminate outliers.
Table 1 – Results obtained in the training set using all features and 10 fold cross-validation (p-value ≈ 0.0).
Linear Regression
REPTree
M5P
AR+Bag.+M5P AR+Bag.+M5P + (outliers
values set to 1) AR+Bag.+M5P+log10
AR+Bag.+M5P+ln
MAE
The best performing features were the keyphrase based features. They capture semantic information at a more detailed level than topic information does. Information about locations, such as Lisbon and Oporto (the capital of Portugal and the second most important city in Portugal); sports clubs e.g.: Benfica, (Futebol Clube do) Porto, politics e.g.: European Union, Greece, Europe; economics, e.g.: fee, market; and technology, e.g.: computers. The stylometric features extracted from the title (F4) were also useful to reduce both MAE and MRE. The number of hours from the initial publication (F5) conveys a very small improvement in the results. We observed improvement with the Base features and when we include bagging and additive regression.
Without applying the logarithmic transformation, our system falls into 7th place.
We noticed the MRE for the test set was higher. Close examination of the test set revealed that some of its characteristics were different from the training set. For example, the average number of clicks and the variance in the number of clicks were significantly higher in the training set which caused the algorithm overestimate the number of clicks in its predictions for the test set. That may explain the discrepancy in the results.
In this paper we described the problem of predicting the number of clicks that a news story link receives during one hour. Real data from the largest Portuguese web portal, Sapo, was used to train and test our proposed prediction methodology. The data was made available to all participants of the 1st Sapo Data Challenge Traffic Prediction.
Despite the fact that predicting item’s popularity per hour is a very difficult task, our approach obtained results that are close to the real number of clicks (12% MRE and 152 MAE). These results yield us a 4th place (in all categories) in the challenge over 26 participants.
Results have shown that the social-based and time-based features
had little correlation with the number of clicks in the portal. In
contrast, the content-based features had a very large impact. This
contradicts the results obtained by Lerman [
In future work, we will investigate ways to increase the use of automatic key-phrase extraction, e.g.: including a larger set of concepts that better capture the document contents and topics. We will also explore if the inclusion of sentiment analysis features can improve the accuracy of our predictions.
The authors would like to thank PT Comunicações for providing the dataset and creating the 1st Sapo Data Challenge – Traffic Prediction. We want to thank Professors Mário Figueiredo and Isabel Trancoso for fruitful comments. Support for this research by FCT through the Carnegie Mellon Portugal Program and under FCT grant SFRH/BD /33769/2009. This work was also partially funded by European Commission under the contract FP7-SME262428 EuTV, QREN SI IDT 2525, and SI IDT 5108. Support by FCT (INESC-ID multiannual funding) through the PIDDAC Program funds.