# Clustering Algorithm for sequence of events

I'm working with a transactional dataset and am trying to find a library (prefereably python) that can cluster a set of events that likely lead to another event. Any thoughts?

i.e. Suppose I have a sequence of events like the following:

A -> B -> C -> D
E -> A -> B -> C
A -> B -> B -> C
D -> C -> B


From this (albeit a small dataset) one could make the inference that B usually leads to C.

• I can contribute but do not know how much it helps. Even if such library exists I am not sure you will use it in a proper way. I will post the answer but if you want to know more about this feedback let me know Feb 26 at 20:47

When you want to find all consecutive events you just simply calculate a conditional probability.

You have a dataset of event sequences and would like to find the most probable outcome for each input and then you can decide how to summarise your result e.g. find all high probabilities (what is high? usually higher than a user-based threshold!) and sort them to find which events "most likely" lead to which events.

probability of event $$e_i$$ being $$B$$ leads to event $$e_{i+1}$$ being $$C$$ (formally $$P(e_{i+1}=C|e_i=B)$$) can be easily calculated by counting. For a small dataset just do it with no worries. I write the output for your toy example and then suggest a small Python snippet as a starter:

P(B->C) = P(C|B) = 3/4 = 0.75
P(D->C) = P(C|D) = 1
P(C->D) = P(D|C) = 1/2 = 0.5
P(A->B) = P(B|A) = 1
P(C->B) = P(B|C) = 1/2 = 0.5


and so on and so forth.

A simple (and very much not optimized) Python code would be:

S = [['A', 'B', 'C', 'D'],
['E', 'A', 'B', 'C'],
['A', 'B', 'B', 'C'],
['D', 'C', 'B']]

event_set = set([ii for l in S for ii in l])
consecutives = []

for s in S:
consecutives = consecutives + [(s[ii],s[ii+1]) for ii in range(len(s)-1)]

all_counter = Counter(consecutives)
first_event_cntr = {ii:sum([1 for c in consecutives if c[0]==ii]) for ii in event_set}

out_dict = {ii:all_counter[ii]/second_event_cntr[ii[0]] for ii in all_counter}

print(f'Set of all events consists of {sorted(event_set)}')
print(f'Number of times any two consecutive events happened:\n {all_counter}')
print(f'probability of each consecutive event pair is as bellow:\n{out_dict}')nter[ii]/second_event_cntr[ii[1]] for ii in all_counter}


where the output is

Set of all events consists of ['A', 'B', 'C', 'D', 'E']
Number of times any two consecutive events happened:
Counter({('A', 'B'): 3,
('B', 'C'): 3,
('C', 'D'): 1,
('E', 'A'): 1,
('B', 'B'): 1,
('D', 'C'): 1,
('C', 'B'): 1})
probability of each consecutive event pair is as bellow:
{('A', 'B'): 1.0, ('B', 'C'): 0.75, ('C', 'D'): 0.5, ('E', 'A'): 1.0, ('B', 'B'): 0.25, ('D', 'C'): 1.0, ('C', 'B'): 0.5}


There is a problem here which comes with uniqueness of some consecutive events. $$D$$ appears only one time as a first event so the probability of $$P(e_{i+1}=C|e_i=D)$$ is 1 but when data is small you can never inference if this is a rule or and anomaly! One idea would be to bring the number of times an event appears as "first event" into account e.g. using frequency of first event as a confidence score for the probability of output.

The last but not least, in this answer I re-invented wheel as I figured out you might be a beginner. There are different data mining solutions for this problem. If set of events are notary large or do not update, then make input-output pairs like I did and use any classification algorithm (Naive Bayes is a proper option and it is the formally well-structured version of the solution I gave you above). If set of events is very large or it is updated by new events, you turn the whole data into a Directed Graph and do any clustering, mining and inference on it.

## UPDATE

I forgot to mention the most relevant ML algorithm for your question and thanks to rapaio's comment I update the answer.

Markov Chain is a sequence model based on the history of last $$n$$ events in the sequence. It can be used to predict the next event in sequence as you want. The point is that mathematically it is again kinda similar to approach we did above but well-formed and theoretically solid instead of a bunch of messy Python codes!

The interesting (but practically not relevant to you) use of Markov chains is in a very strong probabilistic graphical model called Hidden Markov Models (widely called HMM). Traditional text-to-speech machines were mostly based on HMM (and that's why the Rabiner's tutorial is still a perfect source to start learning). HMMs calculate the probability of transition from state $$i$$ to state $$i+1$$ in a sequence, and also emit the probability of some observations which statistically depend on state. Gladly you do not need the latter and the first one, that you need, is calculated based on Markov Chains.

• Naive Bayes does not use conditional probabilities, aka all features are considered independent. Perhaps you wanted to say something about Markov Chain? Feb 27 at 16:13
• That was another point I forgot to mention, thanks for reminder. Bayes theorem is a shortcut to calculate conditional probability without calculating conditional probabilities. Independence of features is not affecting this problem as there is only 1 feature (the previous event). The idea behind NB is to calculate the probability of each class according to an input. That is also the backbone of the idea I suggested here. Thanks for your comment. I will ad HMM to the answer Feb 27 at 16:25