Probabilistic modeling of transaction data with applications to profiling, visualization, and prediction.
Transaction data is ubiquitous in data mining applications. Examples include market basket data in retail commerce, telephone call records in telecommunications, and Web logs of individual page-requests at Web sites. Profiling consists of using historical transaction data on individuals to construct a model of each individual's behavior. Simple profiling techniques such as histograms do not generalize well from sparse transaction data. In this paper we investigate the application of probabilistic mixture models to automatically generate profiles from large volumes of transaction data. In effect, the mixture model represents each individual's behavior as a linear combination of "basis transactions." We evaluate several variations of the model on a large retail transaction data set and show that the proposed model provides improved predictive power over simpler histogram-based techniques, as well as being relatively scalable, interpretable, and flexible. In addition we point to applications in outlier detection, customer ranking, interactive visualization, and so forth. The paper concludes by comparing and relating the proposed framework to other transaction-data modeling techniques such as association rules.
INTRODUCTION
Large transaction data sets are common in data mining ap-
plications. Typically these data sets involve records of transactions
by multiple individuals, where a transaction consists
of selecting or visiting among a set of items, e.g., a market
basket of items purchased or a list of which Web pages an
individual visited during a specic session.
Transaction Data Examples
Store Department Number
Transactions
Figure

1: Examples of transactions for several in-
dividuals. The rows correspond to market baskets
and the columns correspond to particular categories
of items. The darker the pixel, the more items were
purchased (white means zero). The solid horizontal
gray lines do not correspond to transaction data but
are introduced in the plot to indicate the boundaries
between transactions of dierent individuals.
We are interested in the problem of making inferences about
individual behavior given transaction data from a large set
of individuals over a period of time. In particular we focus
on techniques for automatically inferring proles for individuals
from the transaction data. In this paper a prole is
considered to be a description or a model of an individual's
transaction behavior, specically, the likelihood that individual
will purchase (or visit) a particular item. Finding
proles is a fundamental problem of increasing interest in
data mining, across a range of transaction-related applica-
tions: retail cross-selling, Web personalization, forecasting,
and so forth.

Figure

1 shows a set of transactions for 5 dierent individuals
where rows correspond to market baskets (transactions)
and columns correspond to categories of items (store departments
in this example). The data set from which these
examples are taken involves over 200,000 transactions from
50,000 customers over a two-year period in a set of retail
stores. The heterogeneity of purchasing behavior is clear
even from this simple plot. Dierent customers purchase
dierent numbers of items, in dierent departments, and in
dierent amounts. Our goal in this paper is to investigate
parsimonious and accurate models for each individual's purchasing
behavior, i.e., individual proles.
The paper begins by dening the general problem of prol-
ing and the spectrum between sparse individual-specic information
and broadly supported global patterns. We then
dene some general notation for the problem and introduce
a mixture model framework for modeling transaction \be-
havior" at the individual level. We describe the model and
illustrate with some examples. We then conduct a number
of experiments on a real-world transaction data set and
demonstrate that the proposed approach is feasible on real-world
data and provides performance that is interpretable,
accurate, and scalable. We brie
y sketch how the model can
support several data mining tasks, such as exploratory data
analysis, ranking of customers, novelty detection, forecast-
ing, and so forth and conclude with a discussion of related
work.
2. THE PROFILING PROBLEM
Proling is essentially the problem of converting transaction
data (such as that in gure 1) into a model for each
individual that can be used to predict their future behav-
ior. Clearly human behavior is highly unpredictable and,
thus, uncertainty abounds. Nonetheless, there are likely to
be regularities in the data that can be leveraged, and that,
on average, can lead to a systematic method for making
predictions.
A facet of many transaction data sets is the fact that the
data are quite sparse. For example, for many transaction
data sets (including the particular data set corresponding
to gure 1), a histogram of \number of transactions" peaks
at 1 (i.e., more customers have a single transaction than
any other number of transactions) and then decreases exponentially
quickly. Thus, for many customers there are very
few transactions on which to base a prole, while for others
there are large numbers of transactions.
Assume for example that we model each individual via a simple
multinomial probability model to indicate which items
are chosen, namely, a vector of probabilities pC , one for
each of the C categories of items, with
assume that this is combined with a histogram that models
how many items in total are purchased per visit, and
a \rate parameter"  that governs how often the individual
conducts transactions per unit time on average (e.g.,
per month).
The crux of the proling problem is to nd a middle-ground
between two proling extremes. At one modeling extreme,
we could construct a general model, of the general form described
above, for the whole population and assume that
individuals are homogeneous enough in behavior that such
a single model is adequate. This is unlikely to be very
accurate given the heterogeneity of human behavior (e.g.,
see gure 1). At the other extreme we could construct a
unique model for each individual based only on past trans-action
data from that individual, e.g., the multinomial, the
histogram, and the rate parameter are all estimated from
raw counts for that individual. This will certainly provide
individual-specic prole models. However, it suers from
at least two signicant problems. Firstly, for individuals
with very small amounts of data (such as those with only
one item in one transaction) the proles will be extremely
sparse and contain very little information. Secondly, even
for individuals with signicant amounts of data, the raw
counts do not contain any notion of generalization: unless
have purchased a specic item in the past the prole
probability for that item is zero, i.e., the model predicts
that you will never purchase it.
These limitations are well-known and have motivated the
development of various techniques for borrowing strength,
i.e., making inferences about a specic individual by combining
both their individual data with what we know about
the population as a whole. Collaborative ltering can be
thought of as a non-parametric nearest-neighbor technique
in this context. Association rule algorithms also try to address
the problem of identifying rules of generalization that
allow identication and prediction of novel items that have
not been seen in an individual's history before (e.g., Brijs et
al., 2000; Lawrence et al., 2001).
However, while these methods can support specic inferences
about other items that an individual is likely to pur-
chase, they do not provide an explicit model for an indi-
vidual's behavior. Thus, it is di-cult to combine these
approaches with other traditional forecasting and prediction
techniques, such as, for example, seasonal modeling
techniques that utilize information about annual seasonal
shopping patterns. Similarly, it is not clear how covariate
information (if available: such as an individual's income,
sex, educational background, etc.) could be integrated in
a systematic and coherent manner into an association rule
framework (for example).
In this paper we take a model-based approach to the proling
problem, allowing all information about an individual
to be integrated within a single framework. Specically we
propose a
exible probabilistic mixture model for the trans-
actions, t this model in an e-cient manner, and from the
mixture model infer a probabilistic prole for each individ-
ual. We compare our approach with baseline models based
on raw or adjusted histogram techniques and illustrate how
the mixture model allows for more accurate generalization
from limited amounts of data per individual.
3. NOTATION
We have an observed data set
is the observed data on the ith customer, 1  i  N . Each
individual data set D i consists of one or more transactions
for that customer , i.e., D fy
g, where
y ij is the jth transaction for customer i and n i is the total
number of transactions observed for customer i.
An individual transaction y ij consists of a description of the
set of products that were purchased at the same time by the
same customer. For the purposes of the experiments described
below, each individual transaction y ij is represented
as a vector of d counts y
component n ijc indicates how many items of type c are in
transaction ij, 1  c  C. One can straightforwardly generalize
this representation to include (for example) the price
for each product, but here we focus just on the number of
items (the counts). Equally well the components n ijc could
indicate the time since the last page request from individual
when they request Web page c during session j. For the
purposes of this paper we will ignore any information about
the time or sequential order in which items are purchased
or in which pages are visited within a particular transaction
y, but it should be clear from the discussion below that it
is straightforward to generalize the approach if sequential
order or timing information is available.
We are assuming above that each transaction is \keyed"
unique identier for each individual. Examples of such keys
can include driver's license numbers or credit card numbers
for retail purchasing or login or cookie identiers for Web
visits. There are practical problems associated with such
identication, such as data entry errors, missing identiers,
fraudulent or deliberately disguised IDs, multiple individuals
using a single ID, ambiguity in identication on the Web,
and so forth. Nonetheless, in an increasing number of trans-action
data applications reliable identication is possible,
via methodologies such as frequent shopper cards, \opt-in"
Web services, and so forth. In the rest of the paper we
will assume that this identication problem is not an issue
(i.e., either the identication process is inherently reliable,
or there are relatively accurate techniques to discern iden-
tity). In fact in the real-world transaction data set that we
use to illustrate our techniques, ambiguity in the identica-
tion process is not a problem.
4. MIXTUREBASISMODELSFORTRANS-
ACTIONS
We propose a simple generative mixture model for the trans-
actions, namely that each transaction y ij is generated by one
of K components in a K-component mixture model. Thus,
the kth mixture component, 1  k  K is a specic model
for generating the counts and we can think of each of the
K models as \basis functions" describing prototype trans-
actions. For example, one might have a mixture component
that acts as a prototype for suit-buying behavior, where the
expected counts for items such as suits, ties, shirts, etc.,
Probability
COMPONENT 3
Probability
COMPONENT 4
COMPONENT 5
Department
Probability
COMPONENT 6
Department

Figure

2: An example of 6 \basis" mixture components
t to the transaction data of Figure 1.
given this component, would be relatively higher than for
the other items.
There are several modeling choices for the component trans-action
models for generating item counts. In this paper we
choose a particularly simple memoryless multinomial model
that operates as follows. Conditioned on n ij , the total number
of items in the basket, each of the individual items is
selected in a memoryless fashion by n ij draws from a multinomial
distribution on the C possible
items. Other models are possible: for example, one could
model the data as coming from C conditionally independent
random variables, each taking non-negative integer values.
This in general involves more parameters than the multinomial
model, and allows (for example) the modeling of
the purchase of exactly one suit and one pair of shoes in
a manner that the multinomial multiple trials model cannot
achieve. In this paper, however, we only investigate the
multinomial model since it is the simplest to begin with.
We can also model the distribution on the typical number
of items purchased within a given component, e.g., as a
Poisson model, which is entirely reasonable (a gift-buying
component model might have a much higher mean number
of items than a suit-buying model). These extensions are
straightforward and not discussed further in this paper.

Figure

2 shows an example of
components that have been learned from the transaction
data of gure 2 (more details on learning will be discussed
below). Each window shows a a particular set of multinomial
probabilities that models a specic type of transaction.
The components show a striking bimodal pattern in that the
multinomial models appear to involve departments that are
either above or below department 25, but there is very little
probability mass that crosses over. In fact the models are
capturing the fact that departments numbered lower than
correspond to men's clothing and those above 25 correspond
to women's clothing. We can see further evidence
of this bimodality in the data itself in gure 1 noting that
some individuals do in fact cross over and purchase items
Number
of
items TRAINING PURCHASES
5026Number
of
items
Department
TEST PURCHASES

Figure

3: Histograms indicating which products
a particular individual purchased, from both the
training data and the test data.
from \both sides" depending on the transaction.
4.1 Individual-Specific Weights
We further assume that for each individual i there exists a
set of K weights, and in the general case these weights are
individual-specic, denoted by
represents the probability that
when individual i enters the store their transactions will be
generated by component k. Or, in other words, the  ik 's
govern individual i's propensity to engage in \shopping be-
(again, there are numerous possible generalizations
such as making the  ik 's have dependence over time,
that we will not discuss here). The  ik 's are in eect the
prole coe-cients for individual i, relative to the K component
models.
This idea of individual-specic weights (or proles) is a key
component of our proposed approach. The mixture component
models Pk are xed and shared across all individuals,
providing a mechanism for borrowing of strength across individual
data. In contrast, the individual weights are in
principle allowed to freely vary for each individual within
a K-dimensional simplex. In eect the K weights can be
thought as basis coe-cients that represent the location of
individual i within the space spanned by the K basis functions
(the component Pk multinomials). This approach is
quite similar in spirit to the recent probabilistic PCA work
of Hofmann (1999) on mixture models for text documents,
where he proposes a general mixture model framework that
represents documents as existing within a K-dimensional
simplex of multinomial component models.
Given the assumptions stated so far, the probability of a
particular transaction y ij , assuming that it was generated
by component k, can now be written as
Y
kc (1)
SMOOTHED HISTOGRAM PROFILE (MAP)

Figure

4: Inferred \eective" proles from global
weights, smoothed histograms, and individual-
specic weights for the individual whose data was
shown in gure 3.
where kc is the probability that the cth item is purchased
given component k and n ijc is the number of items of category
c purchased by individual i, during transaction ij.
When the component that generated transaction y ij is not
known, we then have a mixture model, where the weights
are specic to individual i:
ik
Y
An important point in this context is that this probability
model is not a multinomial model, i.e., the mixture has richer
probabilistic semantics than a simple multinomial.
As an example of the application of these ideas, in g-
ure 3 the training data and test data for a particular individual
is displayed. Note that there is some predictability
from training to test data, although the test data contains
(for example) a purchase in department 14 (which was not
seen in the training data). Figure 4 plots eective proles 1
for this particular individual as estimated by three dier-
ent schemes in our modeling approach: (1) global weights
that result in everyone being assigned the same \generic"
prole, (2) a smoothed histogram (maximum a posterior
or MAP) technique that smooths each individual's training
histogram with a population-based histogram, and (3) individual
weights that are \tuned" to the individual's specic
behavior. (Details on each of these methods are provided
later in the paper).
One can see in gure 4 that the global weight prole re-
We call these \eective proles" since the predictive model
under the mixture assumption is not a multinomial that can
be plotted as a bar chart: however, we can approximate it
and we are plotting one such approximation here
ects broad population-based purchasing patterns and is
not representative of this individual. The smoothed histogram
is somewhat better, but the smoothing parameter
has \blurred" the individual's focus on departments below
25. The individual-weight prole appears to be a better representation
of this individual's behavior and indeed it does
provide the best predictive score on the test data in g-
ure 3. Note that the individual-weights prole in gure 4
\borrows strength" from the purchases of other similar cus-
tomers, i.e., it allows for small but non-zero probabilities
of the individual making purchases in departments (such as
6 through or she has not purchased there in the
past. This particular individual's weights, the  ik 's, are
(0:00; 0:47; 0:38; 0:00; 0:00:0:15) corresponding to the 6 component
models shown in gure 2. The most weight is placed
on components 2, 3 and 6, which agrees with our intuition
given the individual's training data.
4.2 Learning the Model Parameters
The unknown parameters in our model consist of both the
parameters of the K multinomials,
C, and the individual-specic prole weights
In learning these parameters from the data we have two main
choices: either we treat all of these parameters as unknown
and use EM to estimate them, or we can rst learn the
K multinomials using EM, and then determine weights for
the N individuals relative to these previously-learned basis
functions. The disadvantage of the rst approach is that
it clearly may overt the data, since unless we have large
numbers of transactions and items per customer, we will end
up with as many parameters as observations in the model.
In the Appendix we outline three dierent techniques for estimating
individual-specic prole weights (including \full
EM"), and later in the experimental results section we investigate
the relative performance of each. We also include
a generic baseline version of the model in our experiments
for comparison, namely Global weights where each individ-
ual's weights  i are set to a common set of weights , where
is the set of K weights returned by EM from learning
a mixture of K multinomials. Intuitively we expect that
these global weights will not be tuned particularly well to
any individual's behavior, and thus, should not perform as
well as individual weights. Nonetheless, the parsimony of
the global weight model may work in its favor when making
out-of-sample predictions, so it is not guaranteed that
individual-weight models will beat it, particularly given the
relative sparsity of data per individual.
4.3 Individual Histogram-based Models
We also include for baseline comparison a very simple smoothed
histogram model dened as a convex combination of the
maximum likelihood (relative frequency or histogram) estimate
of each individual's multinomial estimated directly
from an individual's past purchases and a population multinomial
estimated from the pooled population data. The
idea is to smooth each individual's histogram to avoid having
zero probability for items that were not purchased in the
past. This loosely corresponds to a maximum a posteriori
(MAP) strategy. We tuned the relative weighting for each
term to maximize the overall logp score on the test data set,
which is in eect \cheating" for this method. A limitation
of this approach is that the same smoothing is being applied
to each individual, irrespective of how much data we have
available for them, and this will probably limit the eective-
ness of the model. A more sophisticated baseline histogram
model can be obtained using a fully hierarchical Bayes ap-
proach. In fact all of the methods described in this paper
can be formulated within a general hierarchical Bayesian
framework: due to space limitations we omit the details of
this formulation here.
5. EXPERIMENTAL RESULTS
5.1 Retail Transaction Data
To evaluate our mixture models we used a real-world trans-action
data set consisting of approximately 200,000 separate
transactions from approximately 50,000 dierent individu-
als. Individuals were identied and matched to a transaction
(a basket of items) at the point-of-sale using a card system.
The data consists of all identiable transactions collected
at number of retail stores (all part of the same chain). We
analyze the transactions here at the store department level
(50 departments, or categories of items). The names of individual
departments have been replaced by numbers in this
paper due to the proprietary nature of the data.
5.2 Experimental Setup
We separate our data into two time periods (all transactions
are time-stamped), with approximately 70% of the data being
in the rst time period (the training data) and the remainder
in the test period data. We train our mixture and
weight models on the rst period and evaluate our models
in terms of their ability to predict transactions that occur in
the subsequent out-of-sample test period. In the results reported
here we limit attention to individuals for who have at
least transactions over the entire time-span of the data,
a somewhat arbitrary choice, but intended to focus on individuals
for whom we have some hope of being able to extract
some predictive power.
The training data contains data on 4339 individuals, 58,866
transactions, and 164,000 items purchased. The test data
consists of 4040 individuals, 25,292 transactions, and 69,103
items purchased. Not all individuals in the test data set
appear in the training data set (and vice-versa): individuals
in the test data set with no training data are assigned a
global population model for scoring purposes.
To evaluate the predictive power of each model, we calculate
the log-probability (\logp scores") of the transactions
as predicted by each model. Higher logp scores mean that
the model assigned higher probability to events that actually
occurred. The log probability of a specic transaction
from individual (i.e. a set of counts
of items purchased in one basket by individual i), under
mixture model M , is dened as
ik
Y
Note that the mean negative logp score over a set of trans-
actions, divided by the total number of items, can be interpreted
as a predictive entropy term in bits. The lower
this entropy term, the less uncertainty in our predictions
(bounded below by zero of course, corresponding to zero
uncertainty).
2.93.13.33.5Out-of-Sample, Individuals with 10 or more transactions, time split
Model Complexity k
Negative
log-likelihood
per
item

Figure

5: Predictive entropy on out-of-sample transactions
for the three dierent individual weight tech-
niques, as a function of K, the number of mixture
components.
5.3 Performance of Different Individual Profile
Weight Models

Figure

5 shows the predictive entropy scores for each of the
three dierent individual weighting techniques (described in
the

Appendix

), as a function of K the number of components
in the mixture models. From the plot, we see that in general
that mixtures (K > 1) perform better than single multinomial
models, with an order of 20% reduction in predictive
entropy. Furthermore, the simplest weight method
(\wts1") is more accurate than the other two methods, and
the worst-performing of the weight methods is the method
that allows the individual prole weights to be learned as parameters
directly by EM. While this method gave the highest
likelihood on in-sample data (plots not shown) it clearly
overtted, and led to worse performance out-of-sample. The
wts1 method performed best in a variety of other experiments
we conducted, and so, for the remainder of this paper
we will focus on this particular weighting technique and refer
to the results obtained with this method as simple \Individ-
ual weights."
5.4 Comparison of Individual and Global Weight
Models

Figure

6 compares the out-of-sample predictive entropy scores
as a function of number of mixture components K for the
Individual weights, the Global weights (where all individuals
are assigned the same marginal mixture weights), and
the MAP histogram baseline method (for reference). The
MAP method is the solid line: it does better than the default
(leftmost points in the plot)
because it is somewhat tuned to individual behavior, but
the mixture models quickly overtake it as K increases. The
performance of both Individual and Global weight mixtures
steadily improves up to about then somewhat
attens out above that, providing about a 15% reduction in
predictive uncertainty over the simple MAP approach. The
(Number of Mixture Components K)
Negative
log-likelihood
per
item
Global Weights
Individual Weights
MAP histogram

Figure

Plot of the negative log probability scores
per item (predictive entropy) on out-of-sample
transactions, for global and individual weights as a
function of the number of mixture components K.
Also shown for reference is the score for the non-
mixture MAP model.
Individual weights are systematically better than the Global
weights, with a roughly 3% improvement in predictive accuracy

Figure

7 shows a more detailed comparison of the dierence
between Individual and Global weight models. It contains
a scatter plot of the out-of-sample total logp scores for spe-
cic individuals, for a xed value of
that the Global weight model is systematically worse than
the Individual weights model (i.e., most points are above
the bisecting line). For individuals with the lowest likelihood
(lower left of the plot) the Individual weight model is
consistently better: typically lower weight total likelihood
individuals are those with more transactions and items, so
the Individual prole weights model is systematically better
on individuals for whom we have more data (i.e., who shop
more).

Figure

7 contains quite a bit of overplotting in the top left-
corner. Figure 8 shows an enlargement of a part of this
region of the plot. At this level of detail we can now clearly
see that at relatively low likelihood values that the Individual
prole models are again systematically better, i.e., for
most individuals we get better predictions with the Individual
weights than with the Global weights. Figure 9 shows a
similar focused plot where now we are comparing the scores
from Individual weights (y-axis again) with those from the
MAP method (x-axis). The story is again quite similar,
with the Individual weights systematically providing better
predictions. We note, however, that in all of the scatter
plots that there are a relatively small number of individuals
who get better predictions from the smoother models. We
conjecture that this may be due to lack of su-cient regularization
in the Individual prole method, e.g., these may be
individuals who buy a product they have never purchased
before and the Individual weights model has in eect over-
global weight model
logP,
model

Figure

7: Scatter plot of the log probability scores
for each individual on out-of-sample transactions,
plotting individual weights versus global weights.
logP, global weights
logP,
individual
weights

Figure

8: A close up of a portion of the plot in

Figure

7.
-10logP, MAP model
logP,
individual
weights

Figure

9: Scatter plot of the log probability scores
for each individual on out-of-sample transactions,
plotting log probability scores for individual weights
versus log probability scores for the MAP model.
committed to the historical data, whereas the others models
hedge their bets by placing probability mass more smoothly
over all 50 departments.
5.5 Scalability Experiments
We conducted some simple experiments to determine how
the methodology scales up computationally as a function of
model complexity. We recorded CPU time for the EM algorithm
(for both Global and Individual weights) as a function
of the number of components K in the mixture model.
The experiments were carried out on a Pentium III Xeon,
500Mhz with 512MB RAM (no paging).
For a given number of iterations, the EM algorithm for mixtures
of multinomials is linear in both the number of components
K and the number of total items n. We were interested
to see if increasing the model complexity might cause the
algorithm to take more iterations to converge, thus causing
computation time to increase at a rate faster than linearly
with K.

Figure

shows that this does not happen in prac-
tice. It is clear that the time taken to train the models scales
roughly linearly with model complexity. Note also that there
is eectively no dierence in computation time between the
Global and Individual weight methods, i.e., the extra computation
to compute the Individual weights is negligible.
6. APPLICATIONS: RANKING, OUTLIER
DETECTION, AND VISUALIZATION
There are several direct applications of the model-based approach
that we only brie
y sketch here due to space lim-
itations. In particular, we can use the scores to rank the
most predictable customers. Customers with relatively high
logp scores per item are the most predictable and this infor-
0Model complexity (number of components K)
Time
Global weights
Individual Weights

Figure

10: Plot of the CPU time to t the global and
individual weight mixture models, as a function of
model complexity (number of components K), with
a linear t.
Population Multinomial
Training Data Purchases for Customer 2084
Probability Test Data Purchases for Customer 2084

Figure

11: An example of a customer that is automatically
detected as having unusual purchasing
patterns: population patterns (top), training purchases
(middle), test period purchases (bottom).
mation may be useful for marketing purposes. The proles
themselves can be used as the basis for accurate personaliza-
tion. Forecasts of future purchasing behavior can be made
on a per-customer basis.
We can also use the logp scores to identify interesting and
unusual purchasing behavior. Individuals with low per item
logp score tend to have very unusual purchases. For exam-
ple, one of the lowest ranked customers in terms of this score
(in the test period) is customer 2084. He or she made several
purchases in the test period in department 45: this is
interesting since there were almost zero purchases by any individual
in this department in the training data (Figure 11).
This may well indicate some unusual behavior with this individual
(for example the data may be unreliable and the test
period data may not really belong to the same customer).
Clustering and segmentation of the transaction data may
also be performed in the lower dimensional weight-space,
which may lead to more stable estimation than performing
clustering directly in the original \item-space".
We have also developed an interactive model-based trans-action
data visualization and exploration tool that uses the
mixture models described in this paper as a basic framework
for exploring and predicting individual patterns in transaction
data. The tool allows a user to visualize the raw trans-action
data and to interactively explore various aspects of
both an individual's past behavior and predicted future be-
havior. The user can then analyze the data using a number
of dierent models, including the mixture models described
in this paper. The resulting components can be displayed
and compared and simple operations such as sorting and
ranking of the multinomial probabilities are possible. Finally
proles in the form of expected relative purchasing
behavior for individual users can be generated and visual-
ized. The tool also allows for interactive simulation of a
user prole. This allows a data analyst to add hypothetical
items to a user's transaction record (e.g., adding several
simulated purchases in the shoe department). The tool
then updates a user's prole in real-time to show how this
aects the user's probability of purchasing other items. This
type of model-based interactive exploration of large trans-action
data sets can be viewed as a rst-step in allowing a
data analyst to gain insight and understanding from a large
transaction data set, particularly since such data sets are
quite di-cult to capture and visualize using conventional
multivariate graphical methods.
7. RELATED WORK
The idea of using mixture models as a
exible framework
for modeling discrete and categorical data has been known
for many years in the statistical literature, particularly in
the social sciences under the rubric of latent class analysis
(Lazarsfeld and Henry, 1968; Bartholemew and Knott,
1999). Typically these methods are applied to relatively
small low-dimensional data sets. More recently there has
been a resurgence of interest in mixtures of multinomials
and mixtures of conditionally independent Bernoulli models
for modeling high-dimensional document-term data in text
analysis (e.g., McCallum, 1999; Homan, 1999).
In the marketing literature there have also been numerous
relatively sophisticated applications of mixture models to
retail data (see Wedel and Kamakura, 1998, for a review).
Typically, however, the focus here is on the problem of brand
choice, where one develops individual and population-level
models for consumer behavior in terms of choosing between
a relatively small number of brands (e.g., 10) for a specic
product (e.g., coee).
The work of Breese, Heckerman and Kadie (1998) and Heckerman
et al. (2000) on probabilistic model-based collaborative
ltering is also similar in spirit to the approach described
in this paper except that we focus on explicitly treating
the problem of individual proles (i.e., we have explicit
models for each individual in our framework).
Our work can be viewed as being an extension of this broad
family of probabilistic modeling ideas to the specic case of
transaction data, where we deal directly with the problem
of making inferences about specic individuals and handling
multiple transactions per individual.
Other approaches have also been proposed in the data mining
literature for clustering and exploratory analysis of trans-action
data, but typically in a non-probabilistic framework
(e.g., Strehl and Ghosh, 2000). Transaction data has always
received considerable attention from data mining re-
searchers, going back to the original work of Agrawal, Imie-
lenski, and Swami (1993) on association rules. Association
rules present a very dierent approach to transaction data
analysis, searching for patterns that indicate broad correlations
(associations) between particular sets of items. Our
work here complements that of association rules in that we
develop an explicit probabilistic model for the full joint dis-
tribution, rather than sets of \disconnected" joint and conditional
probabilities (one way to think of association rules).
Indeed, for forecasting and prediction it can be argued that
the model-based approach (such as we propose here) is a
more systematic framework: we can in principle integrate
time-dependent factors (e.g., seasonality, non-stationarity),
covariate measurements on customers (e.g., knowledge of
the customer's age, educational-level) and other such infor-
mation, all in a relatively systematic fashion. We note also
that association rule algorithms depend fairly critically on
the data being relatively sparse. In contrast, the model-based
approach proposed here should be relatively robust
with respect to the degree of sparseness of the data.
On the other hand, it should be pointed out that in this paper
we have only demonstrated the utility of the approach on
a relatively low-dimensional problem (i.e., 50 departments).
As we descend the product hierarchy from departments, to
classes of items, all the way down to specic products (the
so-called \SKU" level) there are 50,000 dierent items in the
retail transaction database used in this paper. It remains to
be seen whether the type of probabilistic model proposed
in this paper can computationally be scaled to this level of
granularity. We believe that the mixture models proposed
here can indeed be extended to model the full product tree,
all the way down to the leaves. The sparsity of the data,
and the hierarchical nature of the problem, tends to suggest
that hierarchical Bayesian approaches will play a natural
role here. We leave further discussion of this topic to future
work.
8. CONCLUSIONS
The research described in this paper can be viewed as a rst
step in the direction of probabilistic modeling of transaction
data. Among the numerous extensions and generalizations
to explore are:
The integration of temporal aspects of behavior, building
from simple stationary Poisson models with individual
extending up to seasonal and non-stationary
eects. Mathematically these temporal aspects
can be included in the model rather easily. For
example, traditionally in modeling consumer behavior,
to a rst approximation, one models the temporal rate
process (how often an individual shops) independently
from the choice model (what an individual purchases),
e.g., see Wedel and Kamakura (1998).
\Factor-style" mixture models that allow a single trans-action
to be generated by multiple components, e.g., a
customer may buy a shirts/ties and camping/outdoor
clothes in the same transaction.
Modeling of product and category hierarchies, from
department level down to the SKU-level.
To brie
y summarize, we have proposed a general probabilistic
framework for modeling transaction data and illustrated
the feasibility, utility, and accuracy of the approach
on a real-world transaction data set. The experimental results
indicate that the proposed probabilistic mixture model
framework can be a potentially powerful tool for exploration,
visualization, proling, and prediction of transaction data.




A. PARAMETER ESTIMATION
A.1 Learning of Individual Weights
Consider the log likelihood function for a set of data points
D where mixture weights are individual-specic, letting
denote all the mixture model parameters and k denote mixture
component (multinomial) parameters:
log
This is very similar to the standard mixture model but uses
individual-specic weights  ik .
The learning problem is to optimize this log{likelihood with
respect to parameters  which consists of mixture component
parameters k and individualized weights  ik subject
to a set of N constraints
In addition, we can
dene a Global weights model that has an additional constraint
that all the individual-specic weights are equal to a
global set of weights :
This particular log{likelihood can be optimized using the
Expectation{Maximization (EM) algorithm where the Q function
becomes:
In this equation P ijk represents the class{posterior of trans-action
evaluated using the \old" set of parameters, such
that The Q function is very similar to the
Q function of the standard mixture model; the only difference
is that individualized weights are used in place of
global weights and additional constraints exist on each set
of individualized weights.
Optimizing the Q function with respect to the mixture component
parameters k does not depend on weights  ik (it
does depend on the \old" weights through P ijk , though).
Therefore this optimization is unchanged. Optimization with
respect to  ik with a set of Lagrange multipliers leads to the
following intuitive update equation:
which reduces to the standard equation:
when global weights are used.
Since the models with individualized weights have a very
large number of parameters and may overt the data, we
consider several dierent methodologies for calculating weights:
1. Global weights: this is the standard mixture model
above.
2. wts1: in this model the weights are constrained to be
equal during EM and a global set of weights together
with mixture component parameters are learned. After
the components are learned, the individual-specic
weights are learnt by a single EM iteration using the
Q function with individual-specic weights.
3. wts2: this model is similar to wts1 model, but instead
of a single iteration it performs a second EM
algorithm on the individualized weights after the mixture
component weights are learned. Eectively, this
model consists of two consecutive EM algorithms: one
to learn mixture component parameters and another
to learn individualized weights.
4. wts3: in this model a full EM algorithm is used, where
both the mixture component weights and individualized
weights are updated at each iteration.
Each of the methods as described represent a valid EM algorithm
since the update equations are always derived from
the appropriate Q function. Therefore, the log-likelihood is
guaranteed to increase at each iteration and consequently,
the algorithms are guaranteed to converge (within the standard
EM limitations).
A.2 General Parameters for Running the EM
Algorithm
The EM algorithm was always started from 10 random initial
random starting points for each run and the highest likelihood
solution then chosen. The parameters were initialized
by sampling from a Dirichlet distribution using single cluster
parameters as a hyperprior and an equivalent sample size
of 100. The EM iterations were halted whenever the
relative change in log likelihood was less than 0.01% or after
100 iterations. In practice, for the results in this paper, the
algorithm typically converged to the 0.01% criterion within
20 to 40 iterations and never exceeded 70 iterations.
A.3

Acknowledgements

The research described in this paper was supported in part
by NSF CAREER award IRI-9703120. The work of IC was
supported by a Microsoft Graduate Research Fellowship.
A.4



--R

Mining association rules between sets of items in large databases

A data mining framework for optimal product selection in retail supermarket data: the generalized PROFSET model
Latent Variable Models and Factor Analysis
Dependency networks for in- ference
Journal of Machine Learning Research

Personalization of supermarket product recommendations
Latent Structure Analysis


Market Segmen- tation: Conceptual and Methodological Foundations
--TR
Mining association rules between sets of items in large databases
Probabilistic latent semantic indexing
A data mining framework for optimal product selection in retail supermarket data
Personalization of Supermarket Product Recommendations
Dependency networks for inference, collaborative filtering, and data visualization

--CTR
Chidanand Apte , Bing Liu , Edwin P. D. Pednault , Padhraic Smyth, Business applications of data mining, Communications of the ACM, v.45 n.8, August 2002
Ella Bingham , Heikki Mannila , Jouni K. Seppnen, Topics in 0--1 data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Chun-Nan Hsu , Hao-Hsiang Chung , Han-Shen Huang, Mining Skewed and Sparse Transaction Data for Personalized Shopping Recommendation, Machine Learning, v.57 n.1-2, p.35-59, October-November 2004
EM algorithm;mixture models;profiles;transaction data