# Algorithm to find common sequence

Assume that "1,2,3" are the ids of users, active means that person visited the stackoverflow in last one month (0=passive, 1=active), and there are positive and negative votes.

id  question       votes                 active
1     1        -1, +1, -1, -1, -1         0
1     2        -1, +1, -1, -1, +1         0
2     1        +1, +1, -1, -1             0
3     1        +1, +1, +1, -1, +1         1
3     2        +1, +1, -1, +1, +1, +1     1
3     3        -1, +1                     1


I want to know what makes the users stop using stackoverflow. Think that, I have already calculate the how many times did they get negative votes, total vote, average vote for each question...

I wonder what kind of information could I get from these sequences. I want to find something like this: these users who are passive have two negative votes sequentially. For example, one positive vote after two negative votes in the second question of user 1, doesn't prevent the user churn. User 3 doesn't have any 2 negative votes sequentially in any of his questions. Hence he is still active.

I'm looking for something like PrefixSpan Algorithm but order is important for me. I mean, I can't write the sequences like

<(-1 +1 -1 -1 -1) (-1 +1 -1 -1 +1 )>


or

<(-1) (+1) (-1) (-1) (-1) (-1) (+1) (-1) (-1) (+1 )>.


Because the first one loses the order, and the second one jumbled the questions together. Is there any algorithm to find these sequences which is common for churners?

Not a typical problem formulation indeed. I suggest two approaches:

1. Use a simple bayesian model where the states or nodes are each of your features. Connect the nodes directly when they haven a direct time dependency (for example vote1 -> vote2 -> vote3, but not vote3 -> vote1) and calculate the probability of a final (output) node to be something (for example user type 1, user type 2, etc). You could also use a hidden markov model that naturally models transitions between states. In your case it would output just 1 state (the prediction). I am not very fan of this model for your problem, but it could be nice to try. You will need a lot of data though.
2. You could use Fuzzy Inductive Reasoning (FIR). It is definitely not a simple algorithm, but works quite well for classification having time series or time-related features. In FIR you want to find an optimal mask of a given depth. If you have, say, 5 features per sample, and for instance you want to know which features to select you will learn an optimal mask for your data that address this (and creates fuzzy rules, etc...). Also if you want to relate two or more examples you will define a depth higher than 1 for the mask. This will allow you to find a mask that for instance uses features 1,2 and 4 of sample t, features 2,3 ,4 and 5 of sample t+1 and features 1 and 4 of sample t+2. Moving t from 1 to N number of samples. So, interesting combinations of features from samples that have a time-relation (or some sort of sequence) are created.

One thing you could do is use an associations rule approach, in the sense of finding the most frequent patterns associated with being passive, or over-associated with being passive:

1. set a frequency threshold
2. figure out what kind of patterns you're looking for, for example frequent sequences. It's good if you can partially order them, similarly to set inclusion in the a priori algorithm. For example, look for sequences, and order them by "is subsequence of".
3. Starting with a reasonably small list of minimal patterns that you're looking for, go through your data counting the occurrences of these patterns.
4. Keep the most frequent patterns (above your threshold), this is your step-1 set of frequent patterns.
5. Generate candidates for step-i+1 patterns by adding something to your step-i patterns.
6. Count how many times the candidates occur. Go to step 4 until you have no more frequent patterns for step i.
7. You then have a bunch of rule candidates, and you want to use association rules metrics to find the patterns that best predict being passive.