21
$\begingroup$

Has anyone used (and liked) any good "frequent sequence mining" packages in Python other than the FPM in MLLib? I am looking for a stable package, preferable stilled maintained by people. Thank you!

$\endgroup$
1
  • $\begingroup$ For that purpose, I don't think implementations in python or in R are going to help at all. Patterning libraties in R and Python do the least work only for frequent patterns but you you want to find some specific patterns other than frequent one, they are not going to be any help at all. $\endgroup$
    – StoryMay
    Feb 3, 2021 at 2:52

7 Answers 7

8
$\begingroup$

I am actively maintaining an efficient implementation of both PrefixSpan and BIDE in Python 3, supporting mining both frequent and top-k (closed) sequential patterns.

$\endgroup$
8
  • $\begingroup$ I'd like to implement those in javascript, but I don't fully understand how these algorithms work. Can you explain it in plain English? $\endgroup$
    – inf3rno
    May 25, 2018 at 10:51
  • $\begingroup$ I suggest you check my original minimal implementation of PrefixSpan. Its core part takes only 15 lines. gist.github.com/chuanconggao/4df9c1b06fa7f3ed854d5d96e2ae499f $\endgroup$ May 28, 2018 at 5:18
  • $\begingroup$ Thanks! I'll try to translate it to js, but won't be easy. :-) Afaik PrefixSpan is building projected databases based on where the prefix matches. I am currently reading about BIDE, which is theory is an even better algorithm. $\endgroup$
    – inf3rno
    May 28, 2018 at 10:45
  • 1
    $\begingroup$ @inf3rno It's not too different from A-priori. The only difference is that you also allow for recombining a frequent pattern with itself. An example, assume we have a tx database with rows 1) ABCD 2) AB 3) BD 4) AD) and min support=2. Then the first iteration: Candidate set 1(C(1)] will be the individual patterns: A, B, C and D. Support for each is 3, 3, 1, 3. So the set of Frequent items (1) will be A, B and D. C is pruned because it was not frequent. Now comes the part where it differs from A-priori from level 2 onwards. C(2) will be: AA, AB, AD, BB, BD, DD. Repeat til candidateset is empty $\endgroup$
    – user21398
    Nov 15, 2021 at 2:06
  • 1
    $\begingroup$ @user21398 Yes, I already coded PrefixSpan in JS since then. I read the scientific article about BIDE several times, but I did not fully understand its pseudocode. I think something was missing from the article, idk. I'll give it a try again later when I need it. I was thinking on my own algorithms too and I found that the definition of sequential pattern is not necessarily the best either. $\endgroup$
    – inf3rno
    Nov 15, 2021 at 10:47
6
$\begingroup$

The only Python package I've found is on Github.

They have an implementation of BIDE there, but it's not maintained code.

$\endgroup$
2
  • $\begingroup$ Just to clarify, it did not implement BIDE which mines frequent closed sequences. It actually implemented PrefixSpan which mines all frequent sequences. PrefixSpan and BIDE share the same pattern enumeration framework, and that is why the authors cited the BIDE paper. $\endgroup$ Apr 20, 2018 at 21:44
  • $\begingroup$ What I did in the end is used: philippe-fournier-viger.com/spmf - It's a JAVA lib but I've wrapped it with python to match my needs $\endgroup$
    – yossico
    Jun 26, 2018 at 19:14
2
$\begingroup$

Have you considered to write it by yourself? Because there is probably no up-to-date maintained library right now.

Check this out, its the basic - PrefixSpan and Closed/Maximal patterns are actually not that hard to implement.

$\endgroup$
1
$\begingroup$

I've used fim's fpgrowth function in the past and it worked well. It's kind of a pain to install on Windows machines however. It seems to be an academic website so I'm not sure if they're doing many updates to the code over time...

$\endgroup$
1
$\begingroup$

SPMF sounds like a useful library for pattern mining.

$\endgroup$
1
$\begingroup$

To complement some of the great answers/libraries:

Seq2Pat: Sequence-to-Pattern Generation Library might be relevant to your case.

The library is written in Cython to take advantage of a fast C++ backend with a high-level Python interface. It supports constraint-based frequent sequential pattern mining.

Here is an example that shows how to mine a sequence database while respecting an average constraint for the prices of the patterns found.

# Example to show how to find frequent sequential patterns
# from a given sequence database subject to constraints
from sequential.seq2pat import Seq2Pat, Attribute

# Seq2Pat over 3 sequences
seq2pat = Seq2Pat(sequences=[["A", "A", "B", "A", "D"],
                             ["C", "B", "A"],
                             ["C", "A", "C", "D"]])

# Price attribute corresponding to each item
price = Attribute(values=[[5, 5, 3, 8, 2],
                          [1, 3, 3],
                          [4, 5, 2, 1]])

# Average price constraint
seq2pat.add_constraint(3 <= price.average() <= 4)

# Patterns that occur at least twice (A-D)
patterns = seq2pat.get_patterns(min_frequency=2)

Notice that sequences can be of different lengths, and you can add/drop other Attributes and Constraints. The sequences can be any string, as in the example, or integers.

The underlying algorithm uses Multi-valued Decision Diagrams, and in particular, the state-of-the-art algorithm from AAAI 20019.

Hope this helps!

Disclaimer: I am a member of the research collaboration between Fidelity & CMU on the Seq2Pat Library.

$\endgroup$
0
$\begingroup$

Since none of the existing solutions were satisfactory for me, I created my own Python Wrapper for SPMF (the Java library mentioned in other answers here).

$\endgroup$

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