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.

Is there any algorithm to find common sequences with percentages?

2 Answers

I think you could use the rle function to detect particular sequences

x = c(+1,+1,-1,-1,+1)
(t = rle(x))


rle computes the lengths and values of runs of equal values in a vector:

> (t = rle(x))
Run Length Encoding
lengths: int [1:4] 2 2 1 2
values : num [1:4] 1 -1 1 -1


Hence, you can organize such an output in the following way:

sequence = data.frame(lenght = t$lengths, value = t$values)
sequence


and then add a column to your original data frame with elements equal to 1 if in the sequence there are subsequent -1, and 0 otherwise.

newColumn = 0 # here a scalar coz I have only one sequence!
if (sequence$length[sequence$value == -1] > 1) {
newColumn = 1
}
newColumn


Now you can apply a logistic regression (or whatever) to see the effect of subsequent -1s on the active state. I hope this can help.

• First thanks for your attention. I think this code belong to R, but I don't know it. Hence, I couldn't understand the finding subsequent part. Can you explain that part? – ahmet Apr 25 '15 at 19:40
• I edited the original answer to explain what the rle function does. – stochazesthai Apr 25 '15 at 19:51
• Does it always give the common pattern for all of them or can I get a result like 80% of them have "-1 -1" pattern? – ahmet Apr 25 '15 at 20:22
• @ahmet no - it just counts values that appear in a vector on subsequent positions. (see stat.ethz.ch/R-manual/R-devel/library/base/html/rle.html) So it does not find patterns but rather count values. – Tim Apr 25 '15 at 20:46
• Actually 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. – ahmet Apr 25 '15 at 20:57

You can convert the sequences to features and then use an algorithm of your choice

• Important Sequences
    from prefixspan import PrefixSpan
db = [
[-1, 1, -1, -1, -1],
[-1, 1, -1, -1, 1],
[1, 1, -1, -1],
[1, 1, 1, -1, 1],
[1,1,-1,1,1,1],
[-1,1]
]

ps = PrefixSpan(db)
importantSequences=[x for x in ps.topk(10) if len(x[1]) > 2]

- **Sequences to Features**

import pandas as pd
results=[]
for curSequence in importantSequences:
results.append([1 if ''.join([str(x) for x in curSequence[1]]) in ''.join([str(y) for y in x]) else 0 for x in db])

results=pd.DataFrame(np.array(results).T)

data=pd.DataFrame()
data['data']=db
for curCol in results.columns.values:
data[curCol]=results[curCol]
data['id']=[1,1,2,3,3,3]
data['question']=[1,2,1,1,2,3]
data['active']=[0,0,0,1,1,1]

• Final Data