In this work, we address an extension of the contrast sequential pattern mining problem which aims at detecting condensed representations for contrast sequential patterns. The problem is encoded with Answer Set Programming (ASP). The eficiency and scalability of the ASP encoding are evaluated on two publicly available dataset, iPRG and UNIX. The continuous increase in available data makes efective and eficient techniques necessary to extrapolate key information to be used to make decisions in various application contexts. An example is temporal data (e.g. system logs, banking transactions, telephone records, ...) that must be analyzed using suitable methodologies such as Sequential Pattern Mining (SPM) [1]. In SPM, the goal is to find frequent and non-empty temporal sequences (i.e. sequential patterns) from a sequence dataset. It also happens that available temporal data is labeled or grouped according to precise semantics. For example, in the domain of network security it is possible to label the network behavior as normal or as anomalous and in this last case an attack could be underway. The idea behind Contrast Pattern Mining (CPM) [2] is to find statistically significant diferences between two or more disjoint datasets or portions of the same dataset. The possibility of merging the two previous concepts for finding significant diferences between frequent sequences of diferent classes is known as Contrast Sequential Pattern Mining (CSPM) [3]. CSPM is the pattern mining task considered in this paper. In recent years there has been an increasing interest in the so-called Declarative Pattern Mining (DPM), a research stream in which the objective is to develop declarative approaches to pattern mining. Several encodings have been presented so far, to cover pattern mining tasks such as sequence mining [4, 5] and frequent itemset mining [6, 7]. Answer Set Programming (ASP) is widely used in DPM. The ifrst proposal is described by Guyet et al. [8]. The authors explore the SPM problem with ASP and compare their method with a dedicated algorithm. Gebser et al. [5] use ASP for extracting condensed representations of sequential patterns. Samet et al. in [9] mine rare sequential patterns with ASP. In [10], Guyet et al. propose a real world application to ASP-based DPM investigating the possible association between hospitalization for seizure and antiepileptic drug switch from a French medico-administrative database. Guyet et al. [11] present the use of ASP to mine sequential patterns within two representations of embeddings (fill-gaps vs skip-gaps) and compare them with CP. An hybrid ASP approach is proposed
by Paramonov et al. [
The paper is organized as follows. In Section 2 we briefly recall the basics of ASP and give the necessary background on CSPM. In Section 3 we define the problem of mining condensed representations for the CSPM task and report the experimental results obtained on the a couple of datasets. Section 4 concludes the paper with final remarks.
Answer Set Programming (ASP) [17, 18] is a declarative programming paradigm that allows for the representation and solving of complex combinatorial problem. It is based on the logical formalism of logic programs, specifically disjunctive logic programs with answer set semantics. ASP provides a powerful tool for solving problems in various domains such as planning, scheduling, reasoning about actions, and knowledge representation. In an ASP program, rules are defined using predicates and logical connectors such as conjunction, disjunctions, and negations. The program consists of a set of rules which define relationships between diferent elements in the problem domain. These rules are then used to generate answer sets - sets of consistent interpretations that satisfy all constraints specified in the program. One advantage of ASP over other declarative programming paradigms is its expressiveness and flexibility in representing complex problems concisely through logical constraints. Additionally, ASP programs can be easily modified or extended without changing their overall structure due to their modular nature. ASP solvers use sophisticated algorithms based on eficient search techniques to compute answer sets, the most important are Clingo [19] and DLV [20]. An example of general rule is: 1 ∨ . . . ∨ ← 1, . . . , , +1, . . . , . The rule says that if 1, . . . , are true and there is not reason for believing that +1, . . . , are true then at least one of the 1, . . . , is believed to be true. The left hand side and the right hand side of the ← are called head and body respectively. Rules without body are called facts. The head is unconditionally true and the arrow is usually omitted. Conversely, rules without head are called constraints and are used to discard stable models, thus reducing the number of answers returned by the ASP solver.
Contrast sequential Pattern Mining (CSPM) [
Sequence ⟨ ⟩ ⟨ ⟩ ⟨ ⟩
⟨⟩ ⟨ ⟩ ⟨ ⟩ ⟨ ⟩ ⟨ ⟩
Let be a database containing a set of sequences = {1, 2, . . . , }, where each sequence consists of ordered elements or items from an alphabet Σ. A sequence is represented as = ⟨1, 2, . . . , ⟩, where each item belongs to Σ and appears in the sequence in order according to some timestamp or position information. A sequential pattern is defined as an ordered list of items = ⟨1, 2, . . . , ⟩ such that each ∈ Σ and occurs consecutively in at least one sequence in . The of a sequential pattern is the number of sequences in which it occurs. Given a minimum support threshold minsup, SPM aims to find all frequent sequential patterns , such that ( ) ≥ . frequent sequential patterns are those that occur frequently enough within the dataset base on the specified support threshold. A contrast sequential pattern is defined as a sequential pattern tha occurs frequently in one sequence dataset but not in the others. It is necessary to introduce the concept of growth rate and contrast rate to find contrast sequential patterns. Given two sequences dataset, 1 labeled with the 1 class and 2 labeled as 2, first we compute the growth rate from 2 to 1 of a sequential pattern as 1 ( ) = ((,, 12))//||12|| . If the (, 2) = 0 and (, 1) ̸= 0 then 1 ( ) = ∞. After, the growth rate from 1 to 2 of is defined as 2 ( ) = ((,, 21))//||21|| . If the (, 1) = 0 and (, 2) ̸= 0 then 2 ( ) = ∞. The contrast rate of is defined as ( ) = {1 ( ), 2 ( )} and if 1 ( ) = 0 and 2 ( ) = 0 then ( ) = ∞. is a contrast sequential pattern if ( ) ≥ , where mincr is the minimum contrast rate threshold.
Table 1 shows a sequences dataset that we split in 1 and 2 according to the classes 1 and 2, respectively. We start by finding sequential patterns first and given = 2, ⟨ ⟩ is a sequential pattern because in occurs in sequences 1, 2, 3, and 8. Another example is ⟨ ⟩ within sequences number 6, 7, and 8. Assuming we have found all the sequential patterns, we check whether these are contrasting for one of the two classes. Given = 2, 1 = ⟨ ⟩ and the metrics ( 1, 1) = 3, ( 1, 2) = 1, 1 ( 1) = 3, 2 ( 1) = 0.33, and ( 1) = 3, 1 is a contrast sequential pattern for 1 because ( 1) ≥ . Given 2 = ⟨ ⟩ and its metrics ( 2, 1) = 0, ( 2, 2) = 3, 1 ( ) = 0, 2 ( ) = ∞, 2 is a contrast sequential pattern for 2. In this specific case it has = ∞ therefore it is only a pattern for the 2 class.
In traditional pattern mining, algorithms often generate a large number of patterns that may contain
redundant or overlapping information. This can lead to issues such as increased computational
complexity, dificulty in interpretation, and ineficiency in storing and processing the discovered patterns.
Condensed representation techniques address these challenges by summarizing the set of mined
patterns into a more compact form without losing important insights or key relationship within data.
One common method used for condensed representation concerns the concept of closed and maximal
patterns [
In the next section we examine the computational behavior of the condensed representations for the
CSPM task comparing with the results obtained in [16] in Figures 1, 2 and, 3. In pattern mining, it is
usual to evaluate the efectiveness (number of extracted patterns), runtime and memory consumption
of an algorithm. Moreover in ASP-based DPM approaches it is important to know the solver and
grounder time. To this end, we conducted experiments on two datasets (Table 2) creating several
subsets of increasing size. In iPRG, each transaction is a sequence of peptides that is known to cleave in
presence of a Trypsin enzyme,3 while in UNIX User, each transaction is a sequence of shell commands
executed by a user during one session.4. We have chosen these datasets because (i) they are suitable
for the task considered in this paper (classified sequences), (ii) they have been already used in the
DPM literature, in particular in [
Due to lack of space we do not report the ASP encodings and all the experiments carried out, which however can be found in the Github repository devoted to MASS-CSP.5
In the following we report and discuss the results obtained from scalability tests on iPRG and UNIX User. We have used the version 5.4.0 of Clingo, with default solving parameters. The timeout (T.O) has been set to 1 hour. The ASP programs were run on a laptop computer with Windows 10 (with Ubuntu 20.04.4 subsystem), AMD Ryzen 5 3500U @ 2.10 GHz, 8GB RAM without using the multi-threading mode of clingo. Multi-threading reduces the mean runtime but introduces variance due to the random allocation of tasks. Such variance is inconvenient for interpreting results with repeated executions.
Tables 3 and 4 summarize the experiments conducted on iPRG and UNIX. It is clear that with the extraction of maximal patterns the output is further reduced compared to closed ones. Obviously a pattern can be both closed and maximal as shown for all sub-datasets when minsup grows up to 20%. As the input to the program increases, the total execution time and occupied memory increases accordingly as well as grounding time (time - solv. t.) but not much. Only when the size of the dataset reaches the order of thousands of rows (iPRG_1000_1000) or when minsup is 10% (iPRG_500_500 maximal) the process ends because of the timeout. The reason is that a high value of minsup is able to reduce the search space and runtime. Figures 1, 2 (iPRG), and 3 (UNIX) compare basic, closed and maximal representations. 3https://dtai.cs.kuleuven.be/CP4IM/cpsm/datasets.html 4https://archive.ics.uci.edu/ml/datasets/UNIX+User+Data 5https://github.com/mpia3/Contrast-Sequential-Pattern-Mining It seems that maximal representation requires more time compared to the closed one while closed representation requires more memory compared to the maximal one. The advantage of using condensed representations instead of the basic frequent formulation is when we want to reduce the output size. It is strange that for UNIX_100_100 (Figure 3) the number of condensed patterns is higher than the basic ones and it will be necessary to delve deeper into this phenomenon to understand the underlying reasons. As the reader can see from the Figures mentioned before, condensed representations require more execution time and memory due to the increase in new atoms to be derived to represent these new patterns which increment the program size. Also in this case, as in various other contexts, it is necessary to define a trade-of between what types of information are wanted and at what cost.
Contrast Sequential Pattern Mining ofers a powerful tool for exploring sequential data and discovering meaningful patterns by highlighting diferences between groups of sequences. It has applications across various domains such as market analysis, healthcare research, fraud detection, and more where understanding contrasts in sequential data is crucial for decision-making and problem-solving. Combinatorial explosion is typically involved in pattern mining. Condensed representation for patterns are the solutions proposed in the literature to address this issue. We have reported the results of the evaluation of closed/maximal contrast sequential patterns comparing with the basic CSPM representation in ASP. We have used two datasets from two diferent domains for our evaluation. The experiments illustrate what are the advantages and weaknesses of condensed representations and in particular pros and cons of closed and maximal patterns. On one hand, they reduce the number of patterns, on the other hand, they tend to consume more computational resources. Overall, condensed representations for pattern mining ofers a valuable tool for extracting actionable insights from data by simplifying complex pattern structures into concise yet informative summaries that facilitate better decision-making processes across various domains such as market analysis, bioinformatics research, customer behavior prediction among others where understanding underlying trends is crucial for making informed decisions.
This work was partially supported by the project FAIR - Future AI Research (PE00000013), under the NRRP MUR program funded by the NextGenerationEU. minsup 10% 20% 30% 40% 50% memory 68.95 58.94 58.00 57.99 57.99 memory 487.08 494.34 483.34 483.21 483.21 1017/S1471068418000467. [13] F. A. Lisi, G. Sterlicchio, Declarative pattern mining in digital forensics: Preliminary results, in: R. Calegari, G. Ciatto, A. Omicini (Eds.), Proceedings of the 37th Italian Conference on Computational Logic, Bologna, Italy, June 29 - July 1, 2022, volume 3204 of CEUR Workshop Proceedings, CEUR-WS.org, 2022, pp. 232–246. URL: http://ceur-ws.org/Vol-3204/paper_23.pdf. [14] F. A. Lisi, G. Sterlicchio, Mining sequences in phone recordings with Answer Set Programming, in: P. Bruno, F. Calimeri, F. Cauteruccio, M. Maratea, G. Terracina, M. Vallati (Eds.), Joint Proceedings of the 1st International Workshop on HYbrid Models for Coupling Deductive and Inductive ReAsoning (HYDRA 2022) and the 29th RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA 2022) co-located with the 16th International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR 2022), Genova Nervi, Italy, September 5, 2022, volume 3281 of CEUR Workshop Proceedings, CEUR-WS.org, 2022, pp. 34–50. URL: http://ceur-ws.org/Vol-3281/paper4.pdf. [15] F. A. Lisi, G. Sterlicchio, A declarative approach to contrast pattern mining, in: A. Dovier, A. Montanari, A. Orlandini (Eds.), AIxIA 2022 - Advances in Artificial Intelligence - XXIst International Conference of the Italian Association for Artificial Intelligence, AIxIA 2022, Udine, Italy, November 28 - December 2, 2022, Proceedings, volume 13796 of Lecture Notes in Computer Science, Springer, 2022, pp. 17–30. URL: https://doi.org/10.1007/978-3-031-27181-6_2. doi:10.1007/978-3-031-27181-6\_2. [16] F. A. Lisi, G. Sterlicchio, Mining contrast sequential patterns with ASP, in: R. Basili, D. Lembo, C. Limongelli, A. Orlandini (Eds.), AIxIA 2023 - Advances in Artificial Intelligence - XXIInd International Conference of the Italian Association for Artificial Intelligence, AIxIA 2023, Rome, Italy, November 6-9, 2023, Proceedings, volume 14318 of Lecture Notes in Computer Science, Springer, 2023, pp. 44–57. URL: https://doi.org/10.1007/978-3-031-47546-7_4. doi:10.1007/ 978-3-031-47546-7\_4. [17] V. Lifschitz, Answer sets and the language of answer set programming, AI Magazine 37 (2016) 7–12. [18] G. Brewka, T. Eiter, M. Truszczynski, Answer set programming at a glance, Communications of the ACM 54 (2011) 92–103. URL: http://doi.acm.org/10.1145/2043174.2043195. doi:10.1145/ 2043174.2043195. [19] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, Clingo= ASP+ control: Preliminary report, arXiv preprint arXiv:1405.3694 (2014). [20] N. Leone, C. Allocca, M. Alviano, F. Calimeri, C. Civili, R. Costabile, A. Fiorentino, D. Fuscà, S. Germano, G. Laboccetta, B. Cuteri, M. Manna, S. Perri, K. Reale, F. Ricca, P. Veltri, J. Zangari, Enhancing DLV for large-scale reasoning, in: M. Balduccini, Y. Lierler, S. Woltran (Eds.), Logic Programming and Nonmonotonic Reasoning - 15th International Conference, LPNMR 2019, Philadelphia, PA, USA, June 3-7, 2019, Proceedings, volume 11481 of Lecture Notes in Computer Science, Springer, 2019, pp. 312–325. URL: https://doi.org/10.1007/978-3-030-20528-7_23. doi:10.1007/978-3-030-20528-7\_23.