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?

• Could you explain what "common sequences with percentages" means?
– whuber
Nov 28, 2018 at 22:19
• Are you looking for something the length of the longest common sub-sequence? This might be helpful: en.wikipedia.org/wiki/Longest_common_subsequence_problem Apr 29, 2019 at 20:41

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? Apr 25, 2015 at 19:40
• I edited the original answer to explain what the rle function does. Apr 25, 2015 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? Apr 25, 2015 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, 2015 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. Apr 25, 2015 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

I think you are getting ahead of yourself in looking at algorithms before considering the kind of information you need to analyse this effectively. Before getting to the effect/non-effect of votes, the first thing to note here is that your proposed data has very little useful information on the use of StackOverflow. Although you have a variable for whether or not the user has been active in the last month, this is very crude. I recommend you see if you can get the actual data on daily visitation to the site from which this variable is calculated. Alternatively, if this is impossible to get, you could take the dates of quetions and answers posted by the user as a proxy for their presence on the site.

As a secondary matter, the voting information you have in your data is only going to be useful if you have times associated with those votes, so that you can see which votes had occurred at whatever cut-off time you are considering when the user stopped using the site. So, for example, for your inactive users, which of these votes occurred prior to the one-month cut-off time and which came after that.

I recommend you think more deeply about these preliminary questions and see if you can get better data for your analysis. You should consider these issue before worrying about the specific algorithm to use to make your inferences.