3
$\begingroup$

Imagine a set of users who always perform the same set of tasks and in the same order. Say - user A - enters the store, reads the newspaper, looks at the TV, orders coffee, eats a donut and leaves. User B, enters the store, orders coffee, reads a magazine, leaves and eats a donut.

However, what we see are only user actions/activity and user identity isn't captured. So we see events like - someone entered the store, read the paper, ordered coffee, ordered coffee, reads a magazine, eats a donut, leaves, leaves, eats a donut.

Given the activity log, is it possible to re-thread actions to identify recurring patterns that would give us users? Obviously, we see the same "user" over and over, billions of times in the data set so the pattern repeats but is interspersed with activity of other users.

What I want to predict is - given an event at time $t_i$, does the event fit a known user's pattern/order of events or is this part of a new pattern we have not seen before.

I bit more formally, if our inputs are 1......n, the set of possible events generated A....Z (an actual sequence of events generated by an input would be a permutation with repetition), and X~i~ denotes an event where X is an event for the ith input, then the sequence of events generated by say,

input 1 is: A1, B1, E1, X1, Y 1

input 2: C2, D2, A2, X2

input 3: Z3, D3, N3, E3, Y 3

If all inputs – 1, 2 and 3 are triggered simultaneously or in close succession, the events could occur in this order: A1, B1, C2, D2, E1, Z3, D3, N3, X1, Y1, A2, X2, E 3, Y3

But what we observe as event log: A, B, C, D, E, Z, D, N, X, Y, A, X, E, Y

The idea is to take the observed events from the log, and identify what input or sequence of events does a given event belong to.

While I am not a mathematician or statistician, I have tried to research or apply the following algorithms but failed to find a match.

Fourier transform : I tried to transform the events into some sort of signal that can then be decomposed into individual components/inputs. However, while each input does repeat but interval between successive repetitions isn’t fixed. Also, the time delta between successive events in the same sequence isn’t fixed either – we just know the order is fixed.

Motif discovery : My understanding is that for motif discovery – each sequence of events appears in order and together in a dataset so events from different sequences are not interspersed. Also, looks like sequence of events are the same size which is not the same with my use case.

Hidden Markov Model : First, the observations have to be equally spaced along time. That isn’t the case with my dataset but I can flatten the time stamps and assume all events are at equal and repeated time intervals. However, the same hidden process does not generate our observations and events have dependencies – that is – for say, input 1, B1 will only happen after A1.

Frequent Pattern Mining : Intuitively, I understand these are more for identifying events that occur/appear together, at a given time. Also, order isn’t important for these patterns because, for example, if milk and eggs are always bought together then it doesn’t matter which one is bought first, the other will follow.

Few others like Association rules or Random forests – however these seem to rely on events leading up to a result of some sort – which again doesn’t match my use case since I do not have any results/marker generated by a sequence of events.

$\endgroup$
  • 1
    $\begingroup$ Do you have training data with user labels for events? Or is this more motif discovery? $\endgroup$ – GeoMatt22 Jun 10 '17 at 0:03
  • $\begingroup$ Sorry, don't have any labeled data. Looking up and reading about motif discovery now. Thanks. $\endgroup$ – Joe Nate Jun 10 '17 at 0:09
1
$\begingroup$

If you don't have training dataset and don't have a result set that you want to get but rather understand a pattern, clustering algorithms might be your best bet. There are many clustering algorithms with pros and cons of each but you would be able to feed the data in and you'd get a clusters based on distance. Since it seems that you only have categorical data, you might need to use something like k-modes algorithm which would give you a heuristic solution.

$\endgroup$
  • $\begingroup$ I have used KMeans and Gaussian Mixture Modeling (from Spark's ML library) but best I understand, a clustering algorithm with cluster all the A s, B s and other event types together. It is not going to find any pattern in sequence or occurrence of these events - nothing to do with whether the events have categorical or numerical attributes. $\endgroup$ – Joe Nate Jun 12 '17 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.