Clustering customers by their orders sequence patterns

I have dataset with clients orders. Example:

Customer_1 07.06.2017 Order_1 Product_1
Customer_1 15.06.2017 Order_2 Product_2
Customer_1 01.09.2017 Order_2 Product_1
Customer_2 07.05.2017 Order_3 Product_3
Customer_2 07.06.2017 Order_4 Product_2
Customer_2 25.09.2017 Order_5 Product_3
Customer_2 05.12.2017 Order_5 Product_1
....
Customer_N


How can I cluster these customers behavior? This dataset looks like time series. But It's difficult for me to find the right way for solving this problem. The history of each customer has different length. And I can't use simple clustering algorithms.

My major aim is to distinguish different customer behaviors, find persons who have started buy more frequently, who have changed their preferences in products (started buy other products), who have tried new for them products but back to previous products. How can I cluster patterns of behavior?

You data are timestamped event sequences. A solution to cluster your customers is to compute the pairwise dissimilarities between the sequences and then input the resulting matrix into any clustering procedure that works with such kind of input.

You can compute the pairwise dissimilarities with the optimal matching method for event sequences, OME, (see Ritschard et al., 2013) that is implemented in the TraMineRextras R package, a companion of the TraMineR package.

I illustrate below how you get the dissimilarity matrix for your two example sequences. We first need to create a TraMineR event sequence object. We need for that numeric ids and dates as integers. So we first make these transformations. Also, I use Product as the event and ignore Order (which I do not understand what it is).

library(TraMineRextras)

d <- c(
"Customer_1", "07.06.2017", "Order_1", "Product_1",
"Customer_1", "15.06.2017", "Order_2", "Product_2",
"Customer_1", "01.09.2017", "Order_2", "Product_1",
"Customer_2", "07.05.2017", "Order_3", "Product_3",
"Customer_2", "07.06.2017", "Order_4", "Product_2",
"Customer_2", "25.09.2017", "Order_5", "Product_3",
"Customer_2", "05.12.2017", "Order_5", "Product_1"
)
md <- matrix(d, nrow = 7, ncol=4, byrow=TRUE)
md <- as.data.frame(md)
md[,1] <- as.integer(gsub("Customer_", md[,1], replacement=""))
md[,2] <- as.integer(as.Date(md[,2], format ="%d.%m.%Y"))
names(md) <- c("Id","Timestamp","Order","Product")
md
##   Id Timestamp   Order   Product
## 1  1     17324 Order_1 Product_1
## 2  1     17332 Order_2 Product_2
## 3  1     17410 Order_2 Product_1
## 4  2     17293 Order_3 Product_3
## 5  2     17324 Order_4 Product_2
## 6  2     17434 Order_5 Product_3
## 7  2     17505 Order_5 Product_1

## Creating the event sequence object
eseq <- seqecreate(id=md$Id, timestamp=md$Timestamp, event=md\$Product)
## event sequences with number indicating time intervals in days
eseq
## [1] 17324-(Product_1)-8-(Product_2)-78-(Product_1)
## [2] 17293-(Product_3)-31-(Product_2)-110-(Product_3)-71-(Product_1)


Now computing the dissimilarities between sequences with OME

## you may have to play with the parameters idcost and vparam
idcost <- rep(1,3)
diss <- seqedist(eseq, idcost = idcost, vparam = .01)
diss
##           [,1]      [,2]
## [1,] 0.0000000 0.7307344
## [2,] 0.7307344 0.0000000


You can then cluster your sequences by inputting the diss matrix to a hierarchical clustering method (e.g. the hclust function) or to a partitioning around medoids method (see e.g. WeightedCluster package that is specifically designed for sequences). Note that you may have to input diss as distance matrix object as.dist(diss).

• I've tried your approach and received wrong results. Clusters distinguish from each other by their classes, but not by the nature of changing. I mean cluster #1 consists of sequences with classes 1 in the end and etc. But I'm trying to distinguish them by their behavior, in other words cluster1 consists of customers who has started buying other class of products. Cluster2 consists of customers who keeps buying similar class of products and etc. Did I do a mistake in your approach? – Andrey Apr 3 '18 at 12:12
• If your primary interest is the order of the successive buys, you could try to ignore the time between the buys by setting vparam=0. Alternatively, if you want to group together customers who experience the same transitions, you could consider your sequences as state sequences (look at the TSE_to_STS function of TraMineRextras for the conversion) and use the optimal matching between transitions (method="OMstran" option of the TraMineR seqdist function). – Gilbert Apr 3 '18 at 14:51

If you can discretize the event at each time moment "t" to some discrete (1 of M) value, you can apply the probabilistic Markov Mixture model. The model is fit using only the data (sequences), no labels are needed.

The Markov Mixture model clusters sequence data into predefined number of clusters, K. Each cluster is modeled using a square transition matrix which is learned by the algorithm. Also the algorithm learns initial state probabilities as well as cluster proportions.

Once the model is trained, the same model can be used to predict the cluster assignments as probabilities. Confident cluster assignments will have almost all mass for one of the clusters; not confident assignments will have probability mass distributed across multiple (if not most) clusters. You can compute entropy to find the reliable estimates and the difficult ones.

I have some work in progress implementation of the model in C# using Infer.NET probabilistic programming framework. The code is on GitHub: https://github.com/usptact/MarkovMixtureModel

I suggest to find a tutorial on Markov Mixture models to gain better understanding how it works. With some effort, you can implement it in your favorite language.

For your application, I see two hurdles before you can use the model:

1. how to pick the discrete states?

2. how to pick the number of clusters?

For the former, the states can be product category the purchased item belongs to. Say, if at moment "t" the person buys "can of pepsi", you can encode it with a state describing "Soda Drinks". The trick is not to have too many states as you would need exponentially more data to train your model on.

For the latter, you can sweep the range of cluster values and pick the one for which the model has the highest evidence. The Bayesian probabilistic models naturally provide this probability.

• Did you mean Hidden Markov Model when you were talking about Markov Mixture model? I've explained the problem in more simply way then it is. All my products have their classes, for example 1, 2, 3, 4 based on their components. So in one time I started sell new products with similar components and similar classes. Can I descrete states like as sequences (O - Old, N - New) {O1,O1,N1,N1}, {O1,O2,O1,N3, N3,N3} and cluster them with Markov Chains? – Andrey Apr 3 '18 at 9:18
• No, Markov Chain Mixture model. There are no hidden states in this model, only the observations. In HMM, you also have hidden random variables. I suggest you to look a for some tutorial or a video explaining shortly the model. It sometimes is one of the textbook models due to its simplicity. – Vladislavs Dovgalecs Apr 3 '18 at 15:57