IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,

VOL. 20,

NO. 9,SEPTEMBER 2008

1

Recommendation Method for Improving
Customer Lifetime Value
Tomoharu Iwata, Kazumi Saito, and Takeshi Yamada, Member, IEEE
Abstract—It is important for online stores to improve customer lifetime value (LTV) if they are to increase their profits. Conventional
recommendation methods suggest items that best coincide with user’s interests to maximize the purchase probability, and this does
not necessarily help improve LTV. We present a novel recommendation method that maximizes the probability of the LTV being
improved, which can apply to both measured and subscription services. Our method finds frequent purchase patterns among high-LTV
users and recommends items for a new user that simulate the found patterns. Using survival analysis techniques, we efficiently find thepatterns from log data. Furthermore, we infer a user’s interests from the purchase history based on maximum entropy models and use
the interests to improve recommendation. Since a higher LTV is the result of greater user satisfaction, our method benefits users aswell as online stores. We evaluate our method using two sets of real log data for measured and subscription services.
Index Terms—Personalization, marketing, recommender system, collaborative filtering, survival analysis.

Ç
1

INTRODUCTIONRECOMMENDER systems are widely used in online stores[1] because they can improve both user convenienceand store profits. Conventional recommendation methods
recommend items that best coincide with a user’s interests
to maximize the purchase probability [2], [3], [4], [5], [6].
Although these methods can increase short-term sales, they
do not necessarily maximize long-term profits. For example,
if an online store recommends an electronic product thathas a lot of peripheral devices, the user is likely to revisit thestore to purchase peripheral devices in the future. The
recommendation of a DVD that is the first of a series canlead to the purchase of other DVDs in the series. Long-term
profit is related to customer lifetime value (LTV) [7], which
is defined as the total profit that a customer generates overhis/her entire purchase history. Since acquiring newcustomers is not easy, it is important for stores to increase
the LTV of existing customers.
In this paper, we propose a novel recommendation
method that maximizes the probability of the LTV being
improved. Our method finds frequent purchase patterns
among high-LTV users and recommends items for a newuser that simulate the found patterns. Since the possibility ofpurchasing the recommended item depends on the user’s
interests, we take the interests into consideration in order togenerate effective recommendations. To find the patterns, we
use survival analysis techniques [8]. To estimate user’s
interests, we use maximum entropy models. Then, we
combine the found patterns and the estimated user’s. T. Iwata and T. Yamada are with NTT Communication Science
Laboratories, 2-4 Hikaridai, Seika-cho, Keihanna Science City, Kyoto
619-0237, Japan. E-mail: {iwata, yamada}@cslab.kecl.ntt.co.jp.
. K. Saito is with the School of Administration and Informatics, Universityof Shizuoka, 52-1 Yada, Suruga-ku, Shizuoka 422-8526, Japan.
E-mail: k-saito@u-shizuoka-ken.ac.jp.
Manuscript received 12 Apr. 2007; revised 4 Dec. 2007; accepted 4 Mar. 2008;
published online 14 Mar. 2008.
For information on obtaining reprints of this article, please send e-mail to:
tkde@computer.org, and reference IEEECS Log Number
TKDE-2007-04-0158.
Digital Object Identifier no. 10.1109/TKDE.2008.55.
1041-4347/08/$25.00 ß 2008 IEEE

interests in a probabilistically principled framework. Sincea higher LTV is the result of higher user satisfaction, ourmethod benefits both users and online stores. Therefore, ourmethod can be seen as a tool for customer relationshipmanagement (CRM) [9]. CRM is important in terms ofimproving relationships between online stores and theirusers.
The charges that online store users pay relate to the type ofservice they use and these can be categorized as either
measured or subscription services. With a measured service,users pay for purchased items individually. With a subscription service, users pay for the periodic (e.g., monthly or
yearly) use of, for example, magazines, music, movies,
software, and cell-phone services. To increase LTV, online
stores providing measured services must encourage users topurchase many items. On the other hand, online storesproviding subscription services need to encourage users toextend their subscription periods. Therefore, online storesshould recommend items using different strategies depending on measured or subscription services, and we propose
different recommendation methods for each of them.
The remainder of this paper is organized as follows: In
Section 2, we briefly review related work. In Section 3, we
describe our method for improving LTV for measured
services, and in Section 4, we show its validity using the log
data of an online music store. In Section 5, we modify our
method for subscription services, and in Section 6, we apply
it to the log data of an online cartoon distribution service.
Finally, we offer concluding remarks and a discussion of
future work in Section 7.

2

RELATED WORK

A number of recommendation methods have been proposed, such as collaborative filtering (CF) [4], [6], content
filtering [3], and their hybrids [2], [5]. CF is a method forpredicting a user’s interests using other users’ interests.
Content filtering predicts interests using item information.
These approaches recommend items that best coincide with
Published by the IEEE Computer Society

2IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,

VOL. 20,

NO. 9,SEPTEMBER 2008

TABLE 1An Example of a Purchase Log

Fig. 1. Framework of our method.

a user’s interests to maximize the purchase probability. Ouraim, which is to improve LTV, is different from theirs.
The use of LTV estimation to identify loyal customers
has been studied by various researchers using survival
analysis and data mining techniques [7], [10], [11], [12], [13],[14]. However, they are not used for recommendation.
Piatetsky-Shapiro and Masand [15] and Rosset et al. [16]proposed models for estimating the effects of marketing
activity on LTV. These models are related to our method
because a recommendation can be considered as a marketing activity. However, since our method focuses on therecommendation of items, our method can automatically
perform marketing for each user based on the log data. We
proposed a recommendation method for subscription
services in [17]. In this paper, we extend the method tomake it applicable to both measured and subscription
services.

3

PROPOSED METHOD

3.1

Recommendation for Improving Customer
Lifetime Value
Our method recommends item s^ that maximizes P ðlju; sÞ,which is the probability of improving the LTV of user u
when item s is recommended, as follows:s^ ¼ arg max P ðlju; sÞ;
s2S
S

ð1Þ

where S represents a set of items, l represents the
improvement of the LTV, and s represents the recommended item. We can also recommend m items with thehighest P ðlju; sÞ values. In real applications, candidates forrecommendation would be a subset of item set S , forexample, only items not yet purchased by the user.
In general, P ðlju; sÞ cannot be directly estimated because
it is not possible to observe whether the LTV is improved
given a recommendation. Therefore, we decompose P ðlju; sÞinto two components with a number of assumptions so thatP ðlju; sÞ can be estimated from data that can be easily
obtained by online stores. Let s0 be the item purchased byuser u when item s is recommended. If the recommendation
does not influence the user purchase behavior, it is natural tothink that the recommendation does not influence the LTV,

either. Therefore, we assume that improving LTV l andrecommendation s are independent conditioned on purchased item s0 and user u. Based on this assumption, P ðlju; sÞcan be decomposed into two components: Qðlju; s0 Þ, which isthe probability of the LTV being improved when user upurchases item s0 , and Rðs0 ju; sÞ, which is the probability ofitem s0 being purchased when item s is recommended to useru, as follows:XP ðlju; sÞ ¼
P ðl; s0 ju; sÞ
s0 2S
S

¼

X

Qðlju; s0 ÞRðs0 ju; sÞ:

ð2Þ

s0 2S
S

We can estimate Qðlju; s0 Þ and Rðs0 ju; sÞ from the log datawith survival analysis techniques and maximum entropy
models, respectively. We summarize the framework of our
method in Fig. 1.

3.2 Frequency Model
Assuming the profit generated by an item is constant for all
items, the LTV is proportional to the purchase frequency inmeasured services. We derive the probability of improving
LTV given the purchased item Qðlju; s0 Þ using purchasefrequency models.
Let ekn be the status of the kth purchase of user un as
follows:
0 if the kth purchase of user un is the last purchase;ekn ¼
1 otherwise:
ð3Þ
Let tkn be the interpurchase time of the kth purchase ofuser un as follows:
dend  dkn if ekn ¼ 0;
k
ð4Þ
tn ¼
 dkn if ekn ¼ 1;
dkþ1nwhere dkn is the time of the kth purchase of user un , and dendis the last time that the given log data were modified. We
assume that interpurchase time t is a discrete variable. The
status e and the interpurchase time t are obtained from thepurchase log. The purchase log lists the user, the item, andthe time of each purchase. Table 1 shows an example of apurchase log. Fig. 2 shows relationships among interpurchase time t, purchase time d, last modification time dend , andstatus e. As input data for modeling purchase frequencies,
we use a set of users, interpurchase times, purchasehistories, and statuses.
We model the purchase frequency, or interpurchasetime, using frailty models [18], which are used in survival
analysis for modeling repeated events. The purchases are

IWATA ET AL.: RECOMMENDATION METHOD FOR IMPROVING CUSTOMER LIFETIME VALUE

3time, and features that have low b ð< 0Þ characterize
patterns with a long interpurchase time. These patterns
are informative for the online store. For example, they
enable the store to understand the relationship between
purchase histories and purchase frequencies, or to determine new items to be distributed to increase purchasefrequency.

3.3

Fig. 2. Relationships among interpurchase time t, purchase time d, lastmodification time dend , and status e.

repeated events in the sense that a user purchases items
repeatedly, as shown in Fig. 2. The purchase frequencies
can differ among users, and some heavy users purchase
many items and some users purchase only a few items.
Frailty models can account for such heterogeneity acrossusers by incorporating a user specific effect into models. Lethðtjxxn ; un Þ be a hazard function that represents theinstantaneous rate of purchase in interpurchase time t ofuser un with purchase history x n . x n ¼ ðxnb Þb2BB is a column
vector of features for the purchase history of user un , where
B is a set of feature indices. Examples of features include
whether the user has purchased item si , and whether theuser has purchased item si directly after item sj . In frailty
models, the hazard function hðtjx
xn ; un Þ can be represented
as follows:>hðtjx
xn ; un Þ ¼ 0 ðtÞun expð xn Þ;ðn;kÞ2DðtÞ

X
tjDðtÞj log

X

hðtjx
xþs0 ; uþs0 Þhðtjx
x; uÞ þ hðtjx
xþs0 ; uþs0 Þ
1
 >
;
¼
xþs0  xÞ
1 þ exp  ðxQðlju; s0 Þ ¼

ð5Þ

where 0 ðtÞ is the baseline hazard function, un is the frailty
effect of user un for handling heterogeneity,  ¼ ðb Þb2BB isan unknown parameter vector, and  > represents thetranspose of  . Under the frailty models, the global
optimum of the estimation is guaranteed, and Qðlju; s0 Þ
can be written in a closed form as described below.
We can estimate unknown parameters  u ¼ fun g and by maximizing the log partial likelihood using optimization
methods such as quasi-Newton methods [19]. The log
partial likelihood with the Breslow approximation [8] isdefined as follows:
 k

Q
Y
xn ; unðn;kÞ2DðtÞ h tjx
P Lðu ;  Þ ¼ logPjDðtÞj
t
xjm ; um
ðm;jÞ2EðtÞ h tjx
X X 

ð6Þ
¼
log un þ  > x knt

Probability of Increasing Purchase Frequency
Given the Purchased Item
With measured services, if the interpurchase time isshortened, the purchase frequency or LTV increases.
Therefore, we assume that Qðlju; s0 Þ is the probability ofshortening the interpurchase time when user u purchases
item s0 . We derive Qðlju; s0 Þ from hazard function hðtjx
x; uÞ.
Let x be the purchase history of user u, and let x þs0 be theupdated purchase history when item s0 is purchased. For
simplicity, we refer to the user who purchases item s0 asuþs0 . We assume that either u or uþs0 purchases an item attime t, while neither user purchases the next item before
time t. At t, the hazard functions of u and uþs0 are hðtjx
x; uÞand hðtjx
xþs0 ; uþs0 Þ, respectively, where we assume that thefrailty effect does not change by the purchase u ¼ uþs0 . The
probability that user uþs0 purchases the item at t is equal tothe probability of shortening the interpurchase time whenuser u purchases item s0 as follows:um exp  > x jm ;ðm;jÞ2EðtÞ

where DðtÞ ¼ fðn; kÞjtkn ¼ t ^ ekn ¼ 1g is the set of purchases
for which the interpurchase time is equal to t and the status
is 1, and jDðtÞj is its size, EðtÞ ¼ fðn; kÞjtkn  tg is the set ofpurchases for which the interpurchase time is more than orequal to t, and x kn is the feature vector of the purchasehistory of user un at the kth purchase. Note that we do notneed to estimate the baseline hazard function 0 ðtÞ in theestimation of unknown parameters  u and .
In frailty models, features that have high b ð> 0Þ
characterize purchase patterns with a short interpurchase

ð7Þ

which is a sigmoid function. Note that the probability does
not depend on frailty effect u . While we can recommend an
item that maximizes Qðlju; s0 Þ, the user may not purchasethe recommended item when the user is not interested in
the recommended item. In this case, the recommendation isuseless with respect to improving LTV. Therefore, we needto consider whether the recommended item is purchased by
the user taking the user’s interests into consideration.

3.4

Probability of Purchasing an Item Given the
Recommendation
We explain the estimation of Rðs0 ju; sÞ, which is theprobability that user u purchases item s0 when item s isrecommended. Let Rðs0 juÞ be the probability that user upurchases item s0 without recommendation, where
P
0
s0 2S
S Rðs juÞ ¼ 1. The recommendation of item s will
increase the probability of the item being purchased. We
assume that the probability increases  times as follows:( 00Zðu;sÞ Rðs juÞ s ¼ s ;0
Rðs ju; sÞ ¼
ð8Þ
10
Zðu;sÞ Rðs juÞ otherwise;
where Zðu; sÞ ¼ 1 þ ð  1ÞRðsjuÞ is the normalization term,and   1.  represents the effect of the recommendation onpurchase behavior and depends on the way that therecommendation is presented in the online store, including
considerations such as display size and position.
If an item matches the user’s interests, the probabilityof the user purchasing the item becomes high, and if it
does not match, the probability is low. Therefore, Rðs0 juÞ

4IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,TABLE 2
Number of Users, Transactions, and Features in the Log Data
for Frequency Model Evaluation

represents the degree of agreement between the interestsof user u and item s0 . Since conventional recommendation
methods suggest items that coincide with a user’s
interests, we can use conventional methods to obtain
Rðs0 juÞ. We employ maximum entropy models [2], [4],[20], which estimate a probabilistic distribution thatmaximizes entropy under the constraints of the given
data. Maximum entropy models can integrate arbitrary
features such as purchase histories and user attributes,
and they are used for a variety of natural language tasks[21], [22] as well as recommendation. In maximum
entropy models, the probability that user u purchases
item s0 is represented as follows:
!
X
1
0
0
exp
c yc ðu; s Þ ;ð9ÞRðs juÞ ¼
ZðuÞ
c
P

P
where ZðuÞ ¼ s2SS exp c c yc ðu; sÞ is the normalization
term, yc is a feature of the purchase history, c is an
unknown parameter to be estimated, and c is an index ofeach feature.
The unknown parameters  ¼ fc g can be estimated by
maximizing the following log likelihood using optimization
techniques such as quasi-Newton methods:
XX


Lð
Þ ¼
log R snk junk
¼

n

k

n

k

XXX



c

XX
n



c yc unk ; snk

k

log

X
s

exp

X

!

ð10Þ



c yc unk ; s ;cwhere snk is the kth item in the purchase sequence of user un ,and unk is the purchase history of user un before the kth item
is purchased. In maximum entropy models, we can obtain a
global optimum solution. By using a Gaussian prior with azero mean on unknown parameter , overfitting can be
reduced [23]. We use a Gaussian prior in our experiments.

4

EXPERIMENTAL RESULTS FOR A MEASUREDSERVICEWe evaluated our method by employing the log data of an
online music download service in Japan from 1 April 2005.
We set the unit time as one day.

4.1 Evaluation of Frequency Models
We model purchase frequencies with frailty models, inwhich we use purchase histories as their covariates. To
evaluate our purchase frequency model, we compared thefrailty models hðtjx
xn ; un Þ ¼ 0 ðtÞun expð
> x n Þ that use boththe purchase history and the user heterogeneity information
described in Section 3.2 with the Cox proportional hazards

VOL. 20,

NO. 9,SEPTEMBER 2008

TABLE 3
Average Log Partial Likelihoods of Frequency Models

models [24] hðtjx
xn Þ ¼ 0 ðtÞ expð
> x n Þ that use the purchasehistory but not the user heterogeneity information, andmodels that do not use the purchase history information
hðtÞ. We used the following features for the frailty models
and Cox proportional hazards models:
1 if user un has purchased item si ;ð11Þ
xn;i ¼0 otherwise;
where we omitted features that appeared fewer than
10 times in the training data.
We used three data sets consisting of the log data up to
31 August 2005, 30 September 2005, and 31 October 2005.
We used the last interpurchase time of each user as test data
and used others as training data, in which the number ofusers, transactions, and features were as listed in Table 2.
For the evaluation measurement, we used the average log
partial likelihood for test data, which is the log partial
likelihood divided by the number of transactions. A higher
average log partial likelihood indicates a higher predictive
performance of the model. Table 3 shows the results. The
average log partial likelihoods of the frailty models werehigher than those of the Cox proportional hazards models
and the models that do not use purchase histories. This
result shows that frailty models with both purchase history
and user heterogeneity information can predict purchasefrequencies more precisely than models without them.

4.2 Evaluation of Purchase Models
We evaluated purchase models based on the maximum
entropy models described in Section 3.4, which is theprobability that user u purchases item s0 , Rðs0 juÞ. We used
first-order Markov transitions as features, since we considered the last purchased item revealed the user’s interests:
8< 1 if item sa is the last purchased
ysa ;sb ðu; sj Þ ¼
item of user u and sb ¼ sj ;ð12Þ:
0 otherwise:
We used three data sets consisting of the log data up to
31 August 2005, 30 September 2005, and 31 October 2005,
from which we omitted transitions to the same item, items
that appeared fewer than 10 times, and users thatpurchased fewer than five items. We divided each set ofdata into training and test data. The number of users,
transactions, and items were as shown in Table 4. We
compared maximum entropy models with uniform distributions, multinomial distributions, item-based CF [25],and probabilistic latent semantic analysis (PLSA) [26].
Uniform distributions do not use the information in thelog data at all. Multinomial distributions use the information about the number of each item purchased by all users
but do not consider individual interests. The unknown
parameters of the multinomial distribution were estimatedby the maximum likelihood method. In item-based CF, weused the cosine similarity that is defined as follows:

IWATA ET AL.: RECOMMENDATION METHOD FOR IMPROVING CUSTOMER LIFETIME VALUETABLE 4
Number of Users, Transactions, and Items in the Log Data of a
Measured Service for Purchase Model Evaluationsimðsi ; sj Þ ¼ cosðw
wi ; w j Þ ¼

w>
i wj
;
kw
wi k kw
wj k

s2u

which implies that items similar to purchased items arelikely to be purchased. In PLSA, the probability that user upurchases item s0 is represented as follows:Z
X

P ðs0 jzÞP ðzjuÞ;TABLE 6
Accuracies (Percent) of Purchase Models
for a Measured Service

ð13Þ

where wi ¼ ðwi1 ; . . . ; wiN Þ> is a column vector, in which
win ¼ 1 if user un has purchased item si , win ¼ 0 otherwise,
and k  k is the euclidean norm. The probability ofpurchasing item s0 is proportional to the summation of
the cosine similarities of items in the purchase history u asfollows:XRðs0 juÞ /simðs0 ; sÞ;
ð14Þ

Rðs0 juÞ ¼

5

ð15Þ

z¼1

where z is a latent class, Z is the number of latent classes,
P ðs0 jzÞ is the probability that a user in class z purchases item
s0 , and P ðzjuÞ is the probability that user u belongs to classz. The probabilities P ðs0 jzÞ and P ðzjuÞ can be estimated by
maximizing the likelihood using the EM algorithm. We
used Z ¼ 10.
For the evaluation measurements, we used the averagelog likelihood and the accuracy of the next purchasepredictions. Tables 5 and 6 show the results. The predictive
performance of the maximum entropy models was thehighest. Even though item-based CF and PLSA are widelyused for unknown rating prediction, this result indicatesthat they are inadequate for the prediction of the next
purchase items since they do not consider purchase orders.
Maximum entropy models with purchase histories canpredict user purchase behavior and interest more precisely
than those without them.

investigated the relationship between LTV or purchasefrequencies and purchase probabilities using the frailty
model estimated using the log data up to 31 October 2005.
The hazard function in frailty models is multiplied byexpði Þ with the existence of feature xi . We expressed theeffect on improving LTV of the purchase of an item si byexpði Þ, and we expressed the purchase probability by themultinomial distribution parameter estimated by the maximum likelihood. Fig. 3 shows a scatter plot of the
improving LTV effect of the purchase, expði Þ, and thepurchase probability, Rðsi Þ. The correlation coefficient was0:052, and the improving LTV effect and the purchaseprobability were negatively correlated. This result implies
that the recommendation that suggest items that have ahigh probability of being purchased does not necessarily
improve LTV.

4.4 Simulation
In Section 4.1, we showed that frailty models could predictpurchase frequencies, and in Section 4.2, we revealed thatmaximum entropy models could predict user purchasebehavior. Here, we examine the effectiveness of our methodby simulation. We simulate user behavior using the frailty
model and the maximum entropy model that are estimatedusing the log data from 1 April 2005 to 31 October 2005.
The function of Algorithm 1 is to generate a purchasehistory, where t is the time, u is the purchase history, uþs isthe updated history when item s is purchased,  is an empty
history, MaxTime is the time period for the simulation,
Multinomialð Þ is the multinomial distribution of one eventwith j’s success probability j , and ExponentialðÞ is the
exponential distribution with parameter . The first itemthat the user purchases is determined according to RðsÞ,4.3

Purchase Frequencies and Purchase
Probabilities
Conventional recommendation methods recommend items
that have a high probability of being purchased. If high-LTV
users tend to purchase high-purchase-probability items,
conventional methods are sufficient to improve LTV. We
TABLE 5
Average Log Likelihoods of Purchase Models
for a Measured Service

Fig. 3. Purchase probability versus LTV improving effect.

6IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,

VOL. 20,

NO. 9,SEPTEMBER 2008

which is the probability of purchasing item s first (line 4). If
the user has purchased items, we perform a recommendation using our method (line 6), and the item that the userpurchases is determined according to Rðsju; s^Þ (line 7). Theinterpurchase time is sampled from the exponential distribution (line 10), and the time is updated (line 11). We
estimated unknown parameters RðsÞ and un using the log
data by the maximum likelihood method.
Algorithm 1 Simulation algorithm of a user behavior in ameasured service.
1: Set t0, u
2: while t  MaxTime do
3: if u ¼  then4:
Sample s  MultinomialðRðsÞÞ
5: else6:s^ arg maxs P ðlju; sÞ7:
Sample s  MultinomialðRðsju; s^ÞÞ
8: end if
9: Set u
uþs


10:
Sample   Exponential 0 un expð
> x Þ
11:
Set t
tþ
12: end while
13: Output u
We compared our method with the following recommendation methods:.

Q Recommend recommends an item that is most
likely to increase the purchase frequency when theuser purchases the item. Line 6 in Algorithm 1 ischanged as follows:
s^

.

s

ð16Þ

This recommendation does not take the user’s
interests into consideration.
R Recommend recommends an item that best
coincides with the user’s interests. Line 6 is changed
as follows:s^.

arg max Qðlju; sÞ:arg max RðsjuÞ:s

ð17ÞThis recommendation is the same strategy as that ofconventional methods.
No Recommend does not recommend any items.
The item that the user purchases is determinedsolely according to the user’s interests. Line 6 isomitted, and line 7 is changed as follows:
Sample s  MultinomialðRðsjuÞÞ:ð18Þ

This recommendation can also be achieved by using
 ¼ 1 with Algorithm 1, which means that therecommendation has no effect on purchase behavior.
We generated 171,230 user histories with recommendations by each method where 1    10, in which we usedeach estimated u 10 times. We set the time period for thesimulation at 365 days. Fig. 4 shows the average numberof purchased items with different . Our method wasmore successful than the others in increasing the numberof purchased items. The number of purchased items
increases with an increase in . This result indicates that

Fig. 4. Average number of purchased items in simulations withparameters estimated from log data.

if recommendations can influence user behavior, or  > 1,
our method can increase the purchase frequency. Moreover, the purchase frequency can be increased further byimproving the effect of the recommendations. Q Recommend also increases the number of purchased items,
although the effect was smaller than that of our method.
This is because Q Recommend may recommend items thathave low probabilities of being purchased by the user. On
the other hand, our method recommends items taking
user’s interests into account in order to improve therecommendations. R Recommend reduces the number ofpurchased items because the purchase frequency isnegatively correlated with the purchase probability as
shown in Fig. 3.

5

RECOMMENDATION FOR SUBSCRIPTION SERVICES

In this section, we describe a recommendation method
designed to improve LTV for subscription services, which is
obtained by modifying our method for measured services
described in Section 3. With subscription services, the LTV
is proportional to the subscription period and does notdepend on the purchase frequency. Therefore, we modify
the probability of improving the LTV given the purchased
item to the probability of extending the subscription period
given the purchased item.

5.1 Subscription Period Model
We model the subscription period using Cox proportional
hazards models. Let hðtjx
xÞ be the hazard function, which
represents the instantaneous rate of unsubscription atperiod t of users with purchase history x. In Cox
proportional hazards models, the hazard function hðtjx
xÞ isdefined as follows:hðtjxxÞ ¼ 0 ðtÞ expð > x Þ;

ð19Þ

where  is an unknown parameter vector, and 0 ðtÞ is thebaseline hazard function.
Let en be the status of user un as follows:
0 if user un is still subscribing;
ð20Þ
en ¼
1 if user un has already unsubscribed:

IWATA ET AL.: RECOMMENDATION METHOD FOR IMPROVING CUSTOMER LIFETIME VALUE

7

TABLE 7
An Example of a Subscription Log

Fig. 5. Relationships among subscription period t, subscribed time dstart ,unsubscribed time dend , last modification time dend , and status e.

The subscription period tn of user un is obtained as follows:
if en ¼ 0;
dend  dstart
n
tn ¼
ð21Þ
start

d
if en ¼ 1;
dendnn
is the subscribed time of user un , dendis thewhere dstartnnunsubscribed time of user un , and dend is the last time thelog was modified. We assume that subscription period t is adiscrete variable. The status en and the subscription period
tn are obtained from the subscription log. The subscription
log consists of the subscribed time, the status (still
subscribing or already unsubscribed), and, where relevant,the unsubscribed time of each user. Table 7 shows anexample of a subscription log. Fig. 5 shows the relationships
among subscription period t, subscribed time dstart , unsubscribed time dend , last modification time dend , and status e.
Note that unsubscription is not a repeated event in thesense that one user can only unsubscribe once.
We can estimate unknown parameters  by maximizing
the log partial likelihood as follows:QY
xn ðtÞÞ
n2DðtÞ hðtjx
P Lð Þ ¼ logPjDðtÞj
txm ðtÞÞ
m2RðtÞ hðtjx
X X
ð22Þ
¼
 > x n ðtÞtn2DðtÞ

XtjDðtÞj log

X
exp  > x m ðtÞ ;m2RðtÞ

where DðtÞ is the set of users unsubscribed at t, RðtÞ is theset of users subscribing at t, and x n ðtÞ is the feature vector ofuser u at t. Note that we need to treat purchase history x n as
time-dependent variables since purchase history x n change
when user un purchases an item. Features that have lowb ð< 0Þ are characteristic purchase patterns for longsubscription users, and features that have high b ð> 0Þ
are characteristic patterns for short-subscription users.

5.2

Probability of Extending Subscription Period
Given Purchased Item
With subscription services, if the subscription period islong, the LTV increases. We assume that Qðlju; s0 Þ is theprobability of extending the subscription period whenuser u purchases item s0 . We estimate Qðlju; s0 Þ from hazard
function hðtjx
xÞ in a manner similar to that described in
Section 3.3.
Let x be the purchase history of user u, and xþs0 be theupdated purchase history when item s0 is purchased. For
simplicity, we refer to the user when item s0 is purchased as
uþs0 . We assume that either u or uþs0 unsubscribed at t while
the other is still subscribing. At t, the hazard functions of u

and uþs0 are hðtjx
xÞ and hðtjx
xþs0 Þ, respectively. The probability that user u unsubscribed at t is equal to theprobability of extending the subscription period whenuser u purchases item s0 as follows:
hðtjx
xÞ
hðtjx
xÞ þ hðtjx
xþs0 Þ
1 >;¼
x  xþs0 Þ
1 þ exp  ðxQðlju; s0 Þ ¼ð23Þ

which is a sigmoid function.
Our method for subscription services recommends items^ that maximizes P ðlju; sÞ, which is the probability ofextending the subscription period of user u when item s isrecommended as follows:s^ ¼ arg max P ðlju; sÞ;s2SSX¼ arg maxQðlju; s0 ÞRðs0 ju; sÞ;
s2S
S

ð24Þ

s0 2S
S

where we use (23) as Qðlju; s0 Þ.

6

EXPERIMENTAL RESULTS FOR A SUBSCRIPTIONSERVICEWe evaluated our method for extending subscription
periods by using the log data of an online cartoon
distribution service for cell phones in Japan. With thisservice, users pay monthly to read cartoons on their cell
phones. Some cartoons have several volumes, and someusers purchased an item more than once. We regarded a
cartoon that had several volumes as one item, and the unit
time was one day. This service began on 16 August 2004, andthe last modification date of the log was 28 October 2005.

6.1 Evaluation of Subscription Period Models
With our method, we assume that we can estimate
subscription periods more precisely using purchase histories. To evaluate this assumption, we compared the Cox
proportional hazards models hðtjx
xÞ ¼ 0 ðtÞ expð > x Þ that
use the purchase histories described in Section 5.1 andmodels that do not use purchase histories hðtÞ. We used thefollowing three sets of features for the Cox proportional
hazards models:.

F1: whether user u has purchased item si ,
1 if user un has purchased item si ;xn;i ¼0 otherwise;

ð25Þ

8

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,TABLE 8
Number of Features of Subscription Period Models.

F2: whether user un has purchased item si anditem sj ,8< 1 if user un has purchased
ð26Þ
xn;i;j ¼
item si and item sj ;:0 otherwise;.

F3: whether user un has purchased item sj next toitem si ,8< 1 if user u has purchased
item sj next to item si ;ð27Þ
xn;i!j ¼:
0 otherwise;

where we omitted features that appeared fewer than
10 times in the purchase histories.
We used three sets of training and test data. The training
data were the log data up to 30 June 2005, 31 July 2005, and
31 August 2005. The test data were the log data of subscriberson the end date of the training data, and the end date of thetest data was 28 October 2005. The number of features was asshown in Table 8, and the number of subscribers andunsubscribers were as shown in Table 9.
For the evaluation measurement, we used the averagelog partial likelihood for test data. Table 10 shows theresults. The average log partial likelihoods of the Cox
proportional hazards models (F3) were higher than thosefor the model that does not use purchase histories. This
result shows that Cox proportional hazards models canpredict subscription periods more precisely by usingpurchase histories.

6.2 Evaluation of Purchase Models
We evaluated purchase models in a subscription service
based on the maximum entropy models described in
Section 3.4, which estimate the probability that user upurchases item s0 , Rðs0 juÞ as in Section 4.2. We used firstorder Markov transitions as features. We used three sets oftraining and test data. The training data were the log data
up to 30 June 2005, 31 July 2005, and 31 August 2005, fromwhich we omitted transitions to the same item, items thatappeared fewer than 10 times, and users that purchased
fewer than five items. The test data were the log data fromthe end date of the training data to 28 October 2005, fromwhich we omitted transitions to the same item and
TABLE 9Number of Subscribers and Unsubscribers in the Log Data for
Subscription Period Model Evaluation

VOL. 20,

NO. 9,SEPTEMBER 2008

TABLE 10
Average Log Partial Likelihoods of Subscription Period Models

transitions that contained items that had not been distributed during the training data period. The number ofusers, transactions, and items were as shown in Table 11.
We compared maximum entropy models with uniform
distributions, multinomial distributions, item-based CF,
and PLSA.
We used the average log likelihood and accuracy for theevaluation measurements. Tables 12 and 13 show theresults. The maximum entropy models had higher averagelog likelihoods and accuracies than those of other methods
except for the PLSA accuracy of 31 August 2005 data. These
results show that we can predict next purchase items using
the maximum entropy models in this subscription service
as well as in the measured service.

6.3

Subscription Periods and Purchase
Probabilities
We investigated the relationship between the effect on
extending subscription periods and the purchase probabilities as in Section 4.3, where we used the Cox proportional
hazards model (F3) and the maximum entropy model
estimated using the log data up to 31 August 2005.
The expected subscription period given the purchasehistory in Cox proportional hazards models is multiplied byexpði!j Þ with the existence of feature xi!j . We expressed
the effect on extending subscription periods of a transition
by expði!j Þ. The probability of the transition was
estimated using maximum entropy models. The featuresof the Cox proportional hazards model (F3) and the
maximum entropy model are both first-order Markov
transitions. Fig. 6 shows a scatter plot of the extending
effects of transitions, expði!j Þ, and their transition
probabilities, Rðsj jsi Þ. The correlation coefficient was
0.159, and there was little correlation. This result implies
that the recommendation of high-purchase probability
items does not necessarily lead to extend the subscription
period.
6.4 Simulation
We examined the effectiveness of our method for subscription services by simulation. We simulated user behavior
using the Cox proportional hazards model and the
maximum entropy model that we estimated using the log
data from 16 August 2004 to 28 October 2005. The log datacomprised 107 items.
TABLE 11
Number of Users, Transactions, and Items in the Log Data of a
Subscription Service for Purchase Model Evaluation

IWATA ET AL.: RECOMMENDATION METHOD FOR IMPROVING CUSTOMER LIFETIME VALUE

9TABLE 12
Average Test Log Likelihoods of Purchase Models
for a Subscription Service

The function of Algorithm 2 is to generate a subscription
period t, where BernoulliðÞ is the Bernoulli distribution
with success probability . First, from lines 3 to 4 in
Algorithm 2, we decide whether the user unsubscribes or
not in unit time using the unsubscription probability in unit
time of a subscriber hðtjx
xÞ. Second, from lines 7 to 8, we
decide whether the user purchases or not in unit time using
the purchase probability in unit time, g. We assumed that g
is constant over subscription period t. The first item that theuser purchases is determined according to RðsÞ, where RðsÞis the probability of purchasing item s first (line 10). If theuser has purchased some items, we perform a recommendation using our method (line 12), and the item that the userpurchases is determined according to Rðsju; s^Þ (line 13). We
estimated unknown parameters 0 ðtÞ, g, and RðsÞ using thelog data by the maximum likelihood method.
Algorithm 2 Simulation algorithm of a user behavior in a
subscription service.
1: Set t0, u
2: while t  MaxTime do
3: Sample r1  Bernoulliðhðtjx
xÞÞ
4: if r1 is success then5:break
6: end if
7: Sample r2  BernoulliðgÞ
8: if r2 is success then9:
if u ¼  then10:
Sample s  MultinomialðRðsÞÞ
11:
else
12:
s^ arg maxs P ðlju; sÞ13:
Sample s  MultinomialðRðsju; s^ÞÞ
14:
end if
15:
Set u
uþs
16:
end if
17:
Set t
tþ1
18: end while
19: Output t

Fig. 6. Transition probability versus extension effect.

We compared our method with Q Recommend,
R Recommend, and No Recommend. We generated
100,000 user subscription periods with recommendations
by each method where 1    10. We set the maximum
subscription period at 365 days. Fig. 7 shows the average
subscription periods. Our method was more successful thanthe others in extending subscription periods. Since
Q Recommend may recommend items that have noprobability of being purchased by the user, the effect of
Q Recommend is smaller than that of our method.
R Recommend only slightly extended subscription periods
because there was little correlation between the subscription
periods and the purchase probability as in Fig. 6.

7

CONCLUSION

In this paper, we have proposed a novel recommendation
method for improving LTV, which encourages users topurchase more items for measured services and to extend
their subscription periods for subscription services. We
used basic features in the experiments to make the noveltyof our framework easy to understand. Our method can use
other features such as high-order Markov transitions and

TABLE 13
Accuracies (Percent) of Purchase Models
for a Subscription Service

Fig. 7. Average subscription periods in simulations with parameters
estimated from the log data.

10IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,

user attributes. Since our method is divided into two
modules, namely, the estimation of LTV and the estimationof user’s interests, it can be further enhanced using survival
analysis or CF techniques. For example, we can combine
our approach with content filtering to estimate user’s
interests.
Although we have already obtained encouraging results,
some directions remain in which we must extend ourapproach before it can become a useful tool for recommendation. First, it is important to improve the frailty model orCox proportional hazards model and the feature selection inorder to find informative purchase patterns among highLTV users. Second, we need to estimate the effect ofrecommendations on purchase behavior from the log data
automatically. This can be achieved by using the log data ofpurchase histories with and without recommendations.
Finally, we want to apply our method to an online store andshow how it can improve the LTV of real users.

REFERENCES
[1]
[2]
[3]
[4]

[5]

[6]

[7]
[8]
[9]
[10]
[11]
[12]
[13]

[14]

[15]
[16]

J.B. Schafer, J.A. Konstan, and J. Riedl, “E-Commerce Recommendation Applications,” Data Mining and Knowledge Discovery, vol. 5,
pp. 115-153, 2001.
X. Jin, Y. Zhou, and B. Mobasher, “A Maximum Entropy Web
Recommendation System: Combining Collaborative and Content
Features,” Proc. ACM SIGKDD, 2005.
R.J. Mooney and L. Roy, “Content-Based Book Recommending
Using Learning for Text Categorization,” Proc. Fifth ACM Conf.
Digital Libraries (ACM DL ’00), pp. 195-204, 2000.
D.Y. Pavlov and D.M. Pennock, “A Maximum Entropy Approachto Collaborative Filtering in Dynamic, Sparse, High-Dimensional
Domains,” Proc. Advances in Neural Information Processing Systems(NIPS ’02), pp. 1441-1448, 2002.
A. Popescul, L. Ungar, D. Pennock, and S. Lawrence, “Probabilistic Models for Unified Collaborative and Content-Based Recommendation in Sparse-Data Environments,” Proc. 17th Conf.
Uncertainty in Artificial Intelligence (UAI ’01), pp. 437-444, 2001.
P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl,“Grouplens: An Open Architecture for Collaborative Filtering ofNetnews,” Proc. ACM Conf. Computer Supported Cooperative Work(CSCW ’94), pp. 175-186, 1994.
D.R. Mani, J. Drew, A. Betz, and P. Datta, “Statistics and Data
Mining Techniques for Lifetime Value Modeling,” Proc. ACM
SIGKDD ’99, pp. 94-103, 1999.
M. Cleves, W.W. Gould, and R. Gutierrez, An Introduction to
Survival Analysis Using Stata, revised ed. Stata Press, 2004.
M.J.A. Berry and G.S. Linoff, Data Mining Techniques: For Marketing, Sales, and Customer Relationship Management. John Wiley, 2004.
W.H. Au, K.C.C. Chan, and X. Yao, “A Novel Evolutionary Data
Mining Algorithm with Applications to Churn Prediction,” IEEE
Trans. Evolutionary Computation, vol. 7, no. 6, pp. 532-545, 2003.
P.S. Fader, B.G.S. Hardie, and K.L. Lee, ““Counting Your
Customers” The Easy Way: An Alternative to The Pareto/NBD
Model,” Marketing Science, vol. 24, no. 2, pp. 275-284, 2005.
L. Jen, C.-H. Chou, and G.M. Allenby, “A Bayesian Approach toModeling Purchase Frequency,” Marketing Letters, vol. 14, no. 1,
pp. 5-20, 2003.
M.C. Mozer, R. Wolniewicz, D.B. Grimes, E. Johnson, and H.
Kaushansky, “Predicting Subscriber Dissatisfaction and Improving Retention in The Wireless Telecommunications Industry,”
IEEE Trans. Neural Networks, vol. 11, no. 3, pp. 690-696, 2000.
Y. Shono, Y. Takada, N. Komoda, H. Oiso, A. Hiramatsu, and K.
Fukuda, “Customer Analysis of Monthly-Charged Mobile Content
Aiming at Prolonging Subscription Period,” Proc. IEEE Int’l Conf.
Computational Cybernetics (ICCC ’04), pp. 279-284, 2004.
G. Piatetsky-Shapiro and B. Masand, “Estimating Campaign
Benefits and Modeling Lift,” Proc. ACM SIGKDD ’99, pp. 185193, 1999.
S. Rosset, E. Neumann, U. Eick, and N. Vatnik, “Customer
Lifetime Value Models for Decision Support,” Data Mining andKnowledge Discovery, vol. 7, pp. 321-339, 2003.

VOL. 20,

NO. 9,SEPTEMBER 2008[17] T. Iwata, K. Saito, and T. Yamada, “Recommendation Method forExtending Subscription Periods,” Proc. ACM SIGKDD ’06, pp. 574579, 2006.
[18] J. Box-Steffensmeier and B. Jones, Event History Modeling. Cambridge Univ. Press, 2004.
[19] D.C. Liu and J. Nocedal, “On the Limited Memory BFGS Methodfor Large Scale Optimization,” Math. Programming, vol. 45, no. 3,
pp. 503-528, 1989.
[20] L. Zitnick and T. Kanade, “Maximum Entropy for Collaborative
Filtering,” Proc. 20th Conf. Uncertainty in Artificial Intelligence (UAI’04), pp. 636-643, 2004.
[21] K. Nigam, J. Lafferty, and A. McCallum, “Using Maximum
Entropy for Text Classification,” Proc. Int’l Joint Conf. Artificial
Intelligence Workshop Machine Learning for Information Filtering,pp. 61-67, 1999.
[22] A. Ratnaparkhi, “A Maximum Entropy Model for Part-of-Speech
Tagging,” Proc. First Conf. Empirical Methods in Natural Language
Processing (EMNLP ’96), pp. 133-142, 1996.
[23] S.F. Chen and R. Rosenfeld, “A Gaussian Prior for Smoothing
Maximum Entropy Models,” CMUCS-99-108, technical report,
1999.
[24] D.R. Cox, “Regression Models and Life-Tables,” J. Royal Statistical
Soc., Series B, vol. 34, no. 2, pp. 187-220, 1972.
[25] B. Sarwar, G. Karypis, J. Konstan, and J. Reidl, “Item-BasedCollaborative Filtering Recommendation Algorithms,” Proc. 10thInt’l World Wide Web Conf. (WWW ’01), pp. 285-295, 2001.
[26] T. Hofmann, “Probabilistic Latent Semantic Analysis,” Proc. 15th
Conf. Uncertainty in Artificial Intelligence (UAI ’99), pp. 289-296,
1999.
Tomoharu Iwata received the BS degree inenvironmental information from Keio University,
Kanagawa, Japan, in 2001 and the MS degree inarts and sciences from the University of Tokyo,
Japan, in 2003. He is currently a researcher at
Emergent Learning and Systems ResearchGroup, NTT Communication Science Laboratories, Kyoto, Japan. His research interests
include data mining, machine learning, information visualization, and recommender systems.

Kazumi Saito received the BS degree inmathematics from Keio University, Kanagawa,Japan, in 1985 and the PhD degree in engineering from the University of Tokyo, Japan, in 1998.
In 1985, he joined the NTT Electrical Communication Laboratories, Kanagawa. In 2007, hejoined the University of Shizuoka, Japan. He iscurrently a professor in the School of Administration and Informatics. His current researchinterests include machine learning and statisticalanalysis of complex networks.
Takeshi Yamada received the BS degree inmathematics from the University of Tokyo in
1988 and the PhD degree in informatics from
Kyoto University, Japan, in 2003. He is currently
a senior research scientist, supervisor, andleader of Emergent Learning and Systems
Research Group, NTT Communication Science
Laboratories. His research interests include data
mining, statistical machine learning, graph visualization, metaheuristics, and combinatorial
optimization. He is a member of the IEEE.

. For more information on this or any other computing topic,
please visit our Digital Library at www.computer.org/publications/dlib.