Example: constrained frequent subsequences of unknown length More...
Public Types | |
| enum | { SEARCH_BAB , SEARCH_DFS } |
Public Member Functions | |
| CommonPattern (const CommonPatternOptions &opt) | |
| IntVar | cost (void) const override |
| CommonPattern (CommonPattern &s) | |
| Space * | copy (void) override |
| void | print (std::ostream &os) const override |
| Print a solution to os. | |
| Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > > | |
| ScriptBase (const Options &opt) | |
| Constructor. | |
| ScriptBase (ScriptBase &e) | |
| Constructor used for cloning. | |
| virtual void | compare (const Space &home, std::ostream &os) const |
| Compare with s. | |
| Public Member Functions inherited from Gecode::Driver::IgnoreStepOption< BaseSpace > | |
| IgnoreStepOption (const Options &) | |
| Constructor. | |
| IgnoreStepOption (BaseSpace &e) | |
| Constructor used for cloning. | |
Protected Attributes | |
| OpenIntVarList | pattern |
| IntVar | frequency |
| PatternMining::Database | database |
| bool | letters |
Related Symbols | |
(Note that these are not member symbols.) | |
| int | main (int argc, char *argv[]) |
| Main-function. | |
Additional Inherited Members | |
| Static Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > > | |
| static std::ostream & | select_ostream (const char *sn, std::ofstream &ofs) |
| Choose output stream according to sn. | |
| static void | run (const Options &opt, Script *s=nullptr) |
Detailed Description
Example: constrained frequent subsequences of unknown length
A pattern must occur in at least -support percent of the input sequences. Matching preserves order and may skip items; repeated items match distinct positions. Each supporting record counts once, including duplicate records. By default the inputs ABCBC, BABC, ABDC must all support the pattern, which must start with A and end with C. AC and ABC are feasible; ABC is longest.
Ordinary length and regular constraints restrict the pattern, not the matching positions in the input records. By default, DFS enumerates every qualifying pattern; -search bab finds a longest one.
An OpenIntVarList constructs pattern positions as needed, without an end marker or unused suffix variables. Pattern languages therefore describe just the pattern, without padding transitions. The private frequency constraint maintains supporting suffixes after the assigned prefix and removes items with insufficient support. The method follows Amina Kemmar, Samir Loudni, Yahia Lebbah, Patrice Boizumault, and Thierry Charnois, "PREFIX-PROJECTION Global Constraint for Sequential Pattern Mining", CP 2015, pp. 226-243, https://doi.org/10.1007/978-3-319-23219-5_17. The supporting suffix lengths also bound how many items can follow the assigned prefix. Projection can be combined with the pattern's length, item, and language restrictions. OpenRoute is the simpler introduction to open lists.
The paper's Table 1 can be mined with: -sequences ABCBC,BABC,AB,BCD -support 50 -language none. -min-length and -required constrain length and item membership. -language also accepts motif (A, any items, C), re10, re14, re2 (expressions from the paper). Their letters mean item IDs A=1 through Z=26; integer data must use the corresponding mapping for these named expressions.
-file reads one sequence per line in -format letters, integers, or spmf. Integer IDs are positive and preserved in output. SPMF records must have singleton itemsets: "1 -1 2 -1 3 -1 -2" is the sequence ABC. Multi-item itemsets are rejected because they define a different mining problem. No gap or time restrictions are supported.
Definition at line 189 of file common-pattern.cpp.
Member Enumeration Documentation
◆ anonymous enum
| anonymous enum |
| Enumerator | |
|---|---|
| SEARCH_BAB | |
| SEARCH_DFS | |
Definition at line 196 of file common-pattern.cpp.
Constructor & Destructor Documentation
◆ CommonPattern() [1/2]
|
inline |
Definition at line 198 of file common-pattern.cpp.
◆ CommonPattern() [2/2]
|
inline |
Definition at line 215 of file common-pattern.cpp.
Member Function Documentation
◆ cost()
|
inlineoverride |
Definition at line 213 of file common-pattern.cpp.
◆ copy()
|
inlineoverride |
Definition at line 221 of file common-pattern.cpp.
◆ print()
|
inlineoverridevirtual |
Print a solution to os.
Reimplemented from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< IntMaximizeSpace > >.
Definition at line 223 of file common-pattern.cpp.
Friends And Related Symbol Documentation
◆ main()
|
Main-function.
Definition at line 248 of file common-pattern.cpp.
Member Data Documentation
◆ pattern
|
protected |
Definition at line 191 of file common-pattern.cpp.
◆ frequency
|
protected |
Definition at line 192 of file common-pattern.cpp.
◆ database
|
protected |
Definition at line 193 of file common-pattern.cpp.
◆ letters
|
protected |
Definition at line 194 of file common-pattern.cpp.
The documentation for this class was generated from the following file:
- examples/common-pattern.cpp
