Tracking the Evolution of Customer Purchase Behavior Segmentation via a Fragmentation-Coagulation Process

1 Introduction

Customer behavior analysis is an essential component of business intelligence and marketing [Sheth et al., 1999]. Constructing customer behavior models allows businesses to identify the customer segments that are most likely to buy their products and reach target customers effectively [Rossi et al., 1996]. With a better understanding of their customers, it is easier for the stakeholders to develop cost- and timeefficient strategies, including promotions and tailored programs with social value.

While the traditional customer segmentation approaches are based on the demographic information, the recent approaches focus on identifying different types of customers in terms of purchase behavior. For example, mixture models [Bucklin et al., 1998] can be used to discover latent groups in terms of customer behavior. In this way the purchase behavior of an individual customer can be interpreted as a mixture of different prototypes of behavior weighted by the membership in those groups.

However, the traditional mixture modeling is not suitable for behavior modeling in dynamic scenarios, e.g. for tracking a customer purchase behavior shifting across groups. For example, a customer Alice who bought potato chips regularly, may buy less of them after she embarked on a diet. Considering the group level, Alice may shift from Group 1 comprising customers who prefer snacks, to Group 2 comprising customers who prefer fruits. If all the other customers remain invariant, it is easy to track Alice's change by simply updating her group membership. However, other customers may also change their behavior at the same time, which leads to shifting the behavior of the entire group (prototype). Alice may still have a large or even unchanged membership of Group 1, if many other customers from Group 1 also shift to Group 2. This may provide misleading results to business management, who desire to know how the behavior of each customer changes across groups over time and which customers are more receptive to promotions.

A better way for dealing with the "group-level behavior shifting" problem is by adopting a split-merge approach. On one hand, a group can split into multiple smaller groups, when different types of behavior emerge in the group; on the other hand, the customers from two or more groups can merge into a large group, when they are affected by common factors, such as changes of seasons and price - which are of interest for the stakeholders. Due to the aforementioned limitations of using mixture models to address certain demands of the stakeholders, we propose a Bayesian nonparametric Customer Segmentation Model, named FCCSM, which can track the varying customer groups via a Fragmentation-Coagulation Process (FCP).

The FCP is a random partition process, which can describe the split and merge of groups over time [Bertoin, 2006]. At each time interval, the model conducts fragmentation and coagulation operations on all the existing groups in the partition. Therefore, one group can split into smaller groups in the fragmentation step, when the members start to have divergent purchase behavior. On the contrary, several groups can merge in the coagulation step, when customers from different groups exhibit similar behavior. Another advantage of FCP is that, by configuring the split and merge rates, it can be employed to analyze individuals in a minor but interesting group of customers receptive to a promotion or with abnormal behavior, which is often desired by the stakeholders.

FC-CSM facilitates customer purchase behavior analysis and is capable of answering questions such as how many types of customers exist, when and how groups split and merge, how long a group lasts for, who are the customers in each group and how receptive they are to promotions.

We conduct a case study on a purchase dataset collected by an Australian national supermarket chain. We construct FCCSM to explore the customer purchase behavior of various popular products and answer to the above practical questions. We first evaluate the fitness of FC-CSM and demonstrate that FC-CSM has achieved a higher accuracy than the mixture of Poisson processes. Then we examine the impact of promotions on purchase behavior and find that customers buying fresh products, soft drinks and confectionery are more receptive to the promotions. Most importantly, we illustrate how the customer segmentation for different products evolves over time, and track how individual customers shift across groups. The results of our work can be used by stakeholders to discover behavior change patterns that are worth noting, analyze the receptiveness of various customers to promotions, and identify target customers for the promotions.

Related Work. Extensive research has been carried out to build stochastic models of purchase behavior [Wagner and Taudes, 1987], for overall customers [Ehrenberg, 1959; Trinh et al., 2014] or individual customers [Kim et al., 2014]. However, modeling all customers together may overlook their heterogeneity, while building individual models can overfit the sparse and noisy purchase events of an individual customer. The customer segmentation based on behavior via mixture models can overcome the above disadvantages [Kotler and Armstrong, 2010]. The mixture models can discover various types of purchase behavior to support grouplevel analysis [Bucklin et al., 1998]. The models can capture the behavior changes by a dynamic temporal component in the group-level model [Iwata et al., 2013; Luo et al., 2016a; 2016b; Li et al., 2011; 2015]. Another option is Hidden Markov Models (HMM), in which the possible states of an HMM correspond to all groups of the partition [Xing and Sohn, 2007]. Since an HMM needs to label the states, it suffers from the label switching problem, where each permutation of labels generates a mode in the posterior distribution, which may lead to non-identifiability [Jasra et al., 2005].

The random partition process FCP can describe the evolution of partitions using the fragmentation and coagulation operations [Bertoin, 2006]. Moreover, as the group of FCP is determined by its members rather than an explicit group label, the FCP can avoid the label switching problem. The idea of FCP has been applied in different fields such as financial markets [Eguiluz and Zimmermann, 2000], evolving networks [Tadi´c and Rodgers, 2010], and genetic variation [Teh et al., 2011; Elliott and Teh, 2012]. To the best of our knowledge, there are no reported works that track the evolution of customer groups and how individual customers shift across the groups via a split-merge approach.

2 Methodology

Given a transaction dataset, we obtain customer purchase behavior matrix XU×T of U customers during (0, T ], where xit is the behavior data for customer i during (t - 1, t]. XU×T can represent different types of purchase behavior. For example, xit can be a binary indicator of whether customer i purchased a product during (t - 1, t], or it can represent the number of purchase events in week t (time unit is one week), or it can reflect a preference level for a product. Our research tasks are to model customer behavior based on XU×T , track the evolution of customer groups and capture how individual customers shift across groups.

In this section, we describe the construction of FC-CSM from a generative perspective. We also explain how to use the Gibbs sampler to infer the parameters of our model.

2.1 Construction of FC-CSM

At time t, the set of all customers A can be divided into nt non-empty and non-overlapping groups, whose union is A. These groups form a partition πt of A, where each group contains customers with similar behavior at t. We aim to build a sequence of partitions {πt} (t ∈ {1, . . . , T}), so that we know the customers in a group at any time and how customer groups evolve over time, such as whether they split into subgroups or, on the contrary, merge.

FC-CSM is defined in a generative way as follows:

Sample Sequence of Partitions: We adopt the Chinese Restaurant Process (CRP) [Pitman, 2002], a nonparametric partition model, to describe the partitioning of all customers, that is, customer segmentation. CRP can avoid predefining the number of groups in the partition, which allows for a great flexibility of the model. From the perspective of the generative model, at t = 1, we draw π1 for customer set A from CRP(A, ρ, 0), where ρ (ρ > 0) is the parameter to control the number of groups in the partition.

We can obtain the following partition πt+1 based on FCP(πt, ρ, δ), where δ (δ ∈ [0, 1)) controls the temporal dependence between πt and πt+1. When δ = 0, the partition fully depends on the previous one, which means the partition remains the same from t to t + 1; while δ → 1 means πt and πt+1 are independent. Any group in πt can split into smaller groups and merge with the other groups to generate πt+1.

Given π1, the transition from πt to πt+1 at t ∈ {1, . . . , T - 1} can be completed in two sub-steps: the first step splits all groups in πt into smaller groups and produces an intermediate partition π′t , while the second step merges groups in π′t to produce πt+1. For example, Figure 1 illustrates the sequence of partitions for 10 customers from t to t + 2 with different scenarios. The FCP transition rules are: 1) each group in π′t either exists in πt or is a subgroup of another group in πt; 2) each group in πt+1 either exists in π′t or is a combination of other groups in π′t . These two steps correspond to the fragmentation (split) and coagulation (merge) operations, respectively. FCP assumes that the partition sequence {πt} (t ∈ {1, . . . , T}) satisfies Markov property. It means that given πt, πt+1 is conditionally independent on the partitions at the other time intervals. The fragmentation and coagulation steps do not affect the marginal distribution, so P(πt) at any t is CRP(A, ρ, 0), and the marginal distribution of intermediate partition P (π′t ) is CRP (A, ρ, δ).

Sample Behavior Data: The partition of customers is dictated by the behavior metrics determined by the requirements of analysis. For instance, if we desire to distinguish customers by the number of times they buy a product fortnightly, the purchase behavior data xit stores the number of purchase events in two weeks. The Poisson distribution can be used to model the number of events in each period of time. Specifically, the parameter λ of the Poisson distribution can be interpreted as the expected number of events per unit of time. Therefore, we draw xit from a Poisson distribution with intensity λπt(i) for customer i in group πt(i). In addition, we use the conjugate prior, Gamma(α, β) for the Poisson distribution, where α is the shape parameter and β is the scale parameter of the Gamma distribution.

The main advantage of our model is that we can customize the grouping of customers according to the requirements of the analysis. As mentioned above, the customer behavior can be defined in different ways, by storing different data in XU×T . The changes would only affect the sampling of behavior data, which means that we could replace Gamma-Poisson by other distributions, but the sampling of partition sequence remains unchanged. For example, if the behavior data xit is the binary purchase indicator, xit could be sampled from a Bernoulli distribution with a Beta prior; if xit is a preference rating, xit could be sampled from a Multinomial distribution with a Dirichlet prior.

For each customer i, we can trace how they shift across groups and their purchase rate at any time based on the sequence of their group membership {πt(i)}, where πt(i) is the group of customer i at t. The purchase rate λi(t) is defined as a stepwise function λπt(i)(t). Therefore, we can obtain purchase rate curve λi(t) of customer i, which captures the changes of their purchase behavior, besides the main output of FC-CSM - partition sequence.

2.2 Inference of FC-CSM

In FC-CSM (Equation 1), CRP has exchangeable and projective properties, which means that: 1) the order of allocating customers to groups does not affect the marginal distribution P(π) and 2) the projection of π on a subset A′ of the complete set A follows CRP(A′ , ρ, 0). Since FCP is a Markov chain with a series of split and merge operations, it is also exchangeable and projective [Teh et al., 2011]. These two properties allow us to infer the group allocation for customer i based on the current partition of the other customers, assuming customer i is the last customer who needs to be mapped to a group. Then we can update the sequence of group allocations for customer i, complying with the split and merge rules. In one sampling round, due to the exchangeability, we go through all customers to update their group allocations from t = 1 to t = T , as if this customer is the last one to join the existing customer groups.

The notation used in the description is summarized as follows: π¬i t represents the projection of πt on A excluding customer i; zt is the latent group index for customer i at t; set Sk is the selected group for the customer, with group index k; |Sk| is the number of customers in Sk; |πt| is the number of groups in πt. The variables with the prime (′ ) are for the intermediate partition π′t .

The inference of FC-CSM proceeds as follows. Firstly, we describe the conditional probabilities of allocating groups for a behavior sequence xi according to FCP. At t = 1, the conditional probability of group allocation is:

where the condition Sk ∈ π¬i t in the first case means that the selected group for customer i is Sk, an existing group in π¬i t . The second case Sk = φ means that customer i will start a new group. Therefore, the possible space for Sk is φ ∪ π¬i t .

When t > 1, the conditional probabilities of selecting a group for customer i in the two sub-steps are:

These two equations are for the split and merge steps, respectively. Specifically, Ft(Sk) refers to the set of groups in π′¬i t which are split from Sk; it is formally defined as Ft(Sk) = {B|B ∈ π′¬i t ,B ⊆ Sk,B ̸= φ}. Similarly, Ct(Sl) refers to the set of groups in π′¬i t which are merged into Sl; it is defined as Ct(Sl) = {B|B ∈ π′¬i t ,B ⊆ Sl,B ̸= φ}.

Given the conditional probabilities, we use the forwardbackward (F-B) algorithm [Fr¨uhwirth-Schnatter, 1994] to infer the partition sequence for all customers. The F-B algorithm is a commonly used inference framework for dynamic latent variable models. The posterior distributions used to sample the group for customer i at t = 1 is represented as:

where {π¬i τ }T1 refers to the sequence of partitions projected on A \ {i} from τ = 1 to τ = T .

When t > 1, we sample k′ for the split step as follows:

After that, we sample l for the merge step as follows:

To compute the posterior distributions in Equations 5 - 7, we need the conditional probabilities of observations after the current t given the partition sequences {π¬i τ }Tt and {π′¬i τ }T-1 t , which are called "messages". The messages for the split and merge steps are denoted as mf and mc:

Given mcT (k) = 1 at t = T, the messages at other time intervals can be computed in a backward manner recursively.

The likelihood term P(xit|zt = k) in the sampling and messages is determined by the selected distribution for xit. Assuming xit has Poisson distribution, the likelihood of xit in group k is defined as:

Based on the partition sequence {πt} (t ∈ {1, . . . , T}), we can estimate the intensity parameter λk of the GammaPoisson distribution by maximum a posteriori (MAP):

It means that when Sk is an existing group in π¬i t , we compute λk based on the other customers in Sk. Otherwise, if Sk is a new group without any customers, we compute the default λk based on all the other customers in A \ {i}. When customizing our model to handle different types of behavior data, the only change in terms of inference is the computation of the likelihood term.

In a sampling round, for each customer, we first update the sequence of messages based on the current partition sequence using Equations 8 and 9. Then we sample new group allocations for the current customer based on Equations 5-7. After updating the group allocations of all the customers, we start the next sampling round and repeat this process until convergence. The output is the partition sequence of all customers.

To summarize, FC-CSM offers several notable advantages. First, it can track the evolution of customer groups and find the size, duration, ancestors and descendants of each customer group. Second, it can capture the trajectories of customers shifting across groups and the variations of individual purchase rates. Third, it is customizable and can analyze various types of purchase behavior.

3 Case Study

Our case study is based on a transaction dataset of an Australian national-wide supermarket chain, collected through the supermarket loyalty cards between January 1 and December 31, 2014. Each transaction contains a unique customer identifier, product metadata (id, category, brand and name), timestamp, purchased quantity and cost. There are 931 customers in this dataset. We select 38 most popular products based on the number of customers who bought these products at least 10 times during the observation period. There are 21 fresh products including fruits and vegetables and 17 other products such as soft drinks and biscuits.

The supermarket stakeholders desire to construct accurate models to understand the purchase behavior, including what types of customers they have and whether supermarket promotions are effective. They also want to track the dynamics of purchase behavior such as how the customer groups evolve over time and how individual customers shift across groups. Therefore, we conduct the case study aiming to: 1) evaluate the fitness of our model and compare it with two mixture models - Homogeneous Poisson Process (PP) and NonHomogeneous Poisson Process (NHPP) [Luo et al., 2016a; 2017]; 2) explore the impact of promotions on purchase behavior of customers for different products; 3) demonstrate the trajectories of customer partitions and how customer shifts across groups.

The parameters of our model are configured as: ρ = 0.2, δ = 0.1, α = 2, β = 0.5, and the unit of time is 14-day. We conducted 500 iterations of Gibbs sampling for each product to obtain the sequence of partitions.

3.1 Fitness of Purchase Rate

We use the Mean Absolute Error (MAE) metric to evaluate the fitness of purchase rate. For each customer, we first compute the absolute difference between the estimated and actual number of purchase events for each interval, and average the values across T intervals. Then, the MAE for a product is the mean absolute difference obtained for all customers, computed by ∑|A| i=1 (∑Tt=1 |λi(t) - xit|)/(|A|T ).

We compare the model with: 1) the baseline PP, and 2) the NHPP, which uses a mixture of Poisson processes with a polynomial and periodic component in the intensity functions. Figure 2 shows that the MAE of our model is lower than the MAE of both PP and NHPP for all 38 products. The MAE of our model is 0.63, which is significantly lower than the MAE of PP, 0.73 (p < 0.001) and of NHPP, 0.70 (p = 0.002). On average, our model has decreased MAE of NHPP by 10%. We also notice that our model achieves greater improvements for fruits (14.35%), soft drinks (21.72%) and chilled desserts (13.93%), which jointly have an average improvement of 16.67%. For the other products, the average increase of fitness is 6.99%. The possible reason is that the change of seasons have a stronger impact on fruits, soft drinks and chilled desserts than on the other products. Although NHPP captures the long-term patterns via the polynomial component, the dynamic partition of our model is more flexible and can generate a lower MAE for these products.

3.2 Impact of Promotions

We examine the impact of promotion via the correlation between the average purchase rate and the price. Negative correlation means the purchase rate is higher when the price decreases, so smaller correlation values indicate a larger impact of promotions.

The results are presented by the bar chart in Figure 2. Among all products, 20 correlation values are lower than -0.2, which means the customers buying these products are more receptive to promotions. At the category level, the average correlation of all fruits except for bananas is strongly negative, -0.67. The vegetables also have low correlation values, -0.23 on average. The prices of fruits and vegetables generally have more significant changes than other products, due to the varying product availability. It makes sense that the price of these fresh products impacts the purchase decisions. As for the other categories, the promotions of soft drinks and confectionery are generally more effective than of biscuits, snacks and chilled desserts. Thus, regular promotions with high discount rates of the soft drinks may play an important role in attracting customers.

3.3 Trajectory of Purchase Behavior Changes

Given the partition sequence for all customers, we first summarize the group and customer statistics. The total number of groups for different products over the observation period varies between 21 and 48. The average lifetime of one group is 2.15, which corresponds to 30.1 days, as the unit of time is 14-day. About 14% of the groups lasted for more than 8 weeks, which indicates that the partition changes at a moderate pace. The number of groups at each time interval varies from 1 to 6, and the average value is 2.57, which shows the dynamics of the group allocation. As for PP and NHPP, their numbers of groups remain at 3 over time.

We analyze the trajectory of customer partition for each product and illustrate the duration, size and purchase rate of all customer groups using the bubble plots in Figure 3. We select 3 representative plots as examples, corresponding to products with: 1) stable behavior (Arnott's biscuits, top), 2) behavior strongly affected by seasonal availability (grapes, middle) and 3) varying behavior, with customers dynamically shifting across groups (avocado, bottom).

The top plot for Arnott's biscuits shows that there are two different values of λ. About 25% customers have λ above 1.5, while the other 75% have λ below 0.7. We notice that there are not many shifts between the two levels, which means the purchase behavior is relatively stable.

The middle plot for grapes shows the impact of the seasonal product availability on the purchase behavior. There is a major group steadily including about 90% of customers. Overall, the λ curve of this group has a U shape, which is the result of the high price and low supply in mid-year, when it is winter in Australia. Our model has also identified minor groups of customers (in contrast to mixture models which would have included these customers in the major group); this information can be used by stakeholders to discover customers who differ from the majority but are worth noting.

The bottom plot for avocado illustrates different responses to promotions from different customers. There is only one major group at the first 7 time intervals. The λ values increased from t = 8 for all customers and the major group split into two streams, due to different responses to promotions. About 30% of the customers are more receptive to promotions and form groups with λ values from 1.5 to 2.2. The remaining customers are less receptive to promotions and have λ values between 0.5 and 1. Some customers shift from one level to the other. For example, at t = 18, most of the customers in Group 19 increased their purchase rate and formed For an individual customer, the purchase rate curve λi(t) can track how they change behavior and shift across groups, which supports the fine-grained personal analysis. It also facilitates the comparison of customers in order to identify their similarities and differences. We present 3 sets of customers with contrasting behavior in Figure 4 (the group index has been omitted for clarity). When the lines with different colors join together, it means that the corresponding customers are in the same group during that period of time.

Group 21, while a small number of customers decreased λ and joined Group 20.

The top plot includes three customers buying avocado. The turning points of their purchase curves are at t = 8 and t = 15, when the price changed substantially. For example, at t = 15, customer 2 (red) decreased λ and joined customer 3 (yellow), whereas customer 1 (blue) maintained her high purchase rate until the end. The middle plot displays two customers buying Coca-Cola who are in the same group for 22 weeks. However, customer 1 (blue) used to have significantly larger λ than customer 2 (red) before t = 11. They split again after t = 22, when customer 1 decreased λ gradually, whereas customer 2 increased λ abruptly. It shows that customers with similar total number of purchases can have contrasting behavior changes. Similarly, the bottom plot contains three customers buying broccoli. The model successfully captures that customer 2 joined customer 1 at t = 12 and all of them joined the same group at t = 21.

4 Conclusions

In this paper, we propose the Bayesian customer segmentation model FC-CSM, which can track the evolution of customer groups using a fragmentation-coagulation process. The FC-CSM can split groups when customer behavior diverges Figure 4: Individual purchase rate curves of different customers for avocado (top), Coca-Cola (middle) and broccoli (bottom). Each plot demonstrates contrasting behavior of multiple customers for one product, and each line corresponds to one customer. The dashed lines highlight the time intervals discussed in the text.

and merge multiple groups when their behavior becomes similar. The model outputs the sequence of customer partitions over time, which can capture the dynamics of customer behavior and address the group-level behavior shifts. Moreover, FC-CSM is also flexible and can be applied to various types of behavior data.

Our case study uses a real-world supermarket transaction dataset. We analyze the evolution of customer groups and how it is affected by product promotions and seasonal changes. The case study shows that FC-CSM is more accurate than a mixture of Poisson processes. We find that customers were more receptive to promotions of fresh fruits, soft drinks and confectionery. The sequence of customer partitions shows that for products with high impact of promotions, customer groups tend to split during promotions and merge when the price stabilizes. FC-CSM also shows the trajectories of individual customers, which track how they shift across groups and how customers with similar number of purchases may have contrasting behavior patterns.

In summary, FC-CSM offers a strong and sensitive tool for analyzing customer purchase behavior and tracking the effects of promotions and seasonal campaigns. In future work, we will explore how to process the model outputs with a systematic and comprehensive procedure, so that we can provide analytical results to the stakeholders based on their needs, such as identifying interesting groups based on different criteria, and generating a list of target customers for marketing campaigns. We believe that the information provided by FCCSM can be used by stakeholders in order to understand customer behavior changes, identify customer groups, and also optimize the timing and focus of promotion campaigns and business strategies.