All the existing MDL-based approaches compute only one model, i.e., search for a set of mutually optimal
(nonredundant) patterns. In [
The idea of using several models to describe data is widely used in supervised methods. The closest to PM
class of supervised learning methods is the one based on decision trees [
The tree-based methods are known to have the following properties: (i) an ensemble of trees is better than a single decision tree, (ii) an ensemble of \shallow" trees outperforms an ensemble of deeper trees, (iii) an ensemble of boosted trees (an ensemble of trees where each new tree is focused on the examples misclassi ed by the previous trees) outperforms other models of tree ensembles. These rules of thumb work well in general, for a wide variety of datasets.
PM approaches have never been considered from this perspective. Based on the assumption that the best
practices of supervised learning may work well in unsupervised settings, we propose to adapt the aforementioned
principles for building an ensemble of classi ers to PM approaches. As a basic method for computing a pattern
set, we consider the state-of-the-art MDL-based PM approach called Krimp [
The proposed MDL-based multi-model approach (i) uses at most a quadratic number of \easily-derivable" candidates to optimal patterns, (ii) builds a sequence of models (pattern sets), where each successive model describes the data fragments that have been insu ciently well described by previous models, (iii) evaluates interestingness of patterns by their informativeness based on MDL. Non-redundancy of patterns within a single model (in a pattern set) is ensured by MDL, while non-redundancy of patterns among models is ensured by a proposed data projection strategy, i.e., using only poorly described data fragments for computing the next model.
The paper has the following structure. In Section 2, we introduce the basic notations. In Section 3.1 we consider principles of computing simply-derivable itemsets (an analogue of shallow trees). In Section 3.2 we present an approach for computing a sequence of models (pattern sets), where each new model (pattern set) describes those regions of a dataset that are insu ciently well described by the previous models. In Section 4 we study the quality of the proposed approach in experiments. In Section 5 we conclude and give the direction of future work.
We work with transactional datasets and represent them as binary tables. In binary datasets, attributes are also called items, and patterns are called itemsets. As patterns we consider itemsets consisting of at least 2 attributes and describing at least 2 objects.
Let I = fi1; : : : ; iM g be a set of attributes. A dataset D is a bag of N transactions over attributes in I, where
each transaction t is a subset of I, i.e., t I. The pattern search space consists of all possible subsets of I, i.e.,
it is the powerset P(I) of size 2jIj. An itemset X occurs in a transaction t, i X t, we call the set of objects
where it occurs the extent of X, i.e., ext(X) = ft 2 D j X tg. The frequency of X is the (relative) size of
its image, i.e., f req(X) = jext(X)j (or jext(X)j=N ). An equivalence class Equiv(X) of a pattern X is a set of
itemsets with the same extent, Equiv(X) = fY 2 P(I) j ext(Y ) = ext(X)g. In our study we use closed itemsets
as patterns. A closed itemset C is the maximal set of items common to a set of objects [
The probability of a pattern is based on its usage in a data covering (i.e., how many times a pattern is used to cover dataset). The probability of X 2 CT is given by
P (X) = PX 2CT usage(X )
: usage(X) (1)
An example of code table CT and covering with the patterns from CT is given in Figure 1, d and e, respectively. The computation of CT is guided by the MDL principle { a pattern is added to CT only if it allows for reducing the total description length.
The total length is given by L(D; CT ) = L(CT jD) + L(DjCT ), where the length of the dataset D encoded by this CT is L(DjCT ) = PX2CT usage(X)L(code(X)): The length of CT is given by L(CT jD) = PX2CT L(XjST ) + L(code(X)).
The code table is lled greedily. We explain the principle of covering by means of a small example given in Figure 2. The candidates to optimal patterns (e.g., patterns from Figure 1, b) are arranged in the standard candidate order, i.e., by \frequency" #, \jXj" # and lexicographically ", where #/" denotes the descending/ascending order, respectively. Then, one-by-one, patterns are added to the code table, where they are arranged in the standard cover order, i.e., by \jXj" #, \frequency" #, and lexicographically ". Only those patterns that reduce L(D; CT ) are retained in the code table. The steps of building the optimal CT using candidates AB, ABC, AD, BE (the candidates are considered in the standard candidate order) is shown in Figure 2. The rst pattern AB is added to the standard code table ST (Figure 2, a), it reduces L(D; CT ), thus the optimal pattern set is fABg. Then ABC is added to CT (Figure 2, b), it reduces L(D; CT ) and the updated code table contains fABC; ABg. Then AD is added (Figure 2, c), it does not reduce L(D; CT ), the optimal pattern set remains unchanged. The same for BE (Figure 2, d), it does not reduce L(D; CT ). For the sake of simplicity, we show only covering by patterns, the corresponding code tables can be reconstructed based on the covering as in the example in Figure 1 (d, e). 3 3.1
One of the main di culties of PM approaches is that they compute candidates to optimal patterns in advance (in contrast to the tree-based approaches, where a tree is built on the y). Considering all frequent patterns as candidates is infeasible in practice and implies dealing with redundant (similar) patterns. Restricting the set of frequent patterns by increasing the frequency threshold does not solve this problem. Moreover, some interesting and infrequent patterns can be omitted. Using only closed itemsets partially solves the redundancy problem, however, the number of closed itemsets is still exponential.
We propose a deterministic threshold-free approach for building a candidate set comprising of at most a quadratic number of patterns w.r.t. the number of attributes. These patterns are \easily-derivable," since they are computed based on the closure of a union of two attributes, i.e., for a dataset D over attributes I, the set of candidates is given by F = fcl(fikij g) j ik; ij 2 I; k > jg. in what follows we call these patterns biclosed itemsets. For a dataset from Figure 1, a, the set of biclosed itemsets is fAB; AD; BE; ABC; ABDE; ABCDEg. For biclosed itemsets of size at least 3 there are several ways to derive them, e.g., cl(AC) = cl(BC) = ABD, cl(CD) = cl(CE) = ABCDE. On the one hand, it is easy to reproduce a biclosed itemset { it is enough to know only two attributes. On the other hand, a biclosed itemset is maximal (cannot be extended without reducing the support). The number of biclosed itemsets is bounded by jIj(jIj 1)=2. 3.2
Since the number of biclosed candidates is much lower than the number of frequent patterns, they do not cover a dataset as good as patterns from an exponentially large pattern set, like candidates in Krimp. Thus, larger fragments of data remain uncovered. Using the principle of \boosting", i.e., building a new model based on the data fragments that have been poorly described by the previous models, we propose to explore gradually patterns by a sequence of models (pattern sets). At each iteration, we consider a data fragment (projection) U of the binary dataset D that has not been entirely described by the models from the previous iterations. We propose an algorithm, called KeepItSimple (KIS), the pseudocode is given in Algorithm 1. We consider two versions of the algorithm that di er in the way of computing projections (i.e., de ning which fragments are insu ciently well described).
To compute a single model we use Krimp algorithm. However, instead of frequent (closed) patterns, we use biclosed itemsets as candidates. We also change the probability estimates (in Formula 1), we give details in Section 3.3. At the beginning, KIS works as follows: the initial code table is the standard code table (line 1), the candidates F are biclosed itemsets (line 3). Then candidates F are used to cover greedily the dataset. We use the same cover principles as in Krimp (see Section 2.2 for details). When the rst pattern set (model) is computed there are two possibilities to de ne projections, i.e., the fragments U of data that will be used instead of D at the next iteration to nd a new set of optimal patterns. We consider a simple (S) and detailed (D) projections. To compute projection (line 12), we consider attributes I I that are partially covered by patterns from the current code table. To compute S-projection, we keep the whole columns corresponding to partially covered attributes, while to compute D-projection we keep only uncovered fragments in columns (see line 12 S and D, respectively). The process of computing new tables stops when there are no biclosed patterns or the next optimal code table is the standard one.
Example. Let us consider how the algorithms work using the dataset from Figure 1. The steps of Algorithm 1 are given to the right of the pseudocode. At the rst step we use the original dataset D instead of projections. The optimal pattern set is C = fAB; ABCg. For covered data Cover(US;D; C) the projections US and UD are given in Step 2. For S-projection, the whole columns are used, while for D-projection we use only uncovered fragments (US and UD, respectively). These projections are used to compute new candidates. Biclosed itemsets computed on the projected data US and UD are F = fAD; BEg and F = fg, respectively. The optimal patterns are C = fAD; BEg and C = ;, for S and D-projections, respectively. Step 3 is performed only for the S-projected data. Since the only possible biclosed itemset AB is already in the set of optimal patterns, the candidate set F is empty. The optimal pattern sets are C = fAB; ABC; AD; BEg and C = fAB; ABCg, for S- and D-projections, respectively.
Algorithm 1 KeepItSimple(D) Require: binary dataset D over set of attributes I Ensure: itemset collection P 1: L StandardCodeT ableLength(D) 2: U D; I I 3S: F ComputeBiclosed(U ) 4: run T rue 5: while run do 6: Lold L 7S: F ComputeInducedBiclosed(F ; I ) 7D: F ComputeBiclosed(U ) 8: C M DLOptimal(U ; F ) 9: L L(U j C) + L(C j U ) 10: U U n Cover(U; C) 11: I U ncoveredAttributes(U ) 12S: U P rojection(D; I ) 12D: U P rojection(U; I ) 13: P P [ C 14: run run and (Lold > L) and (I 6= ;) 15: end while 16: return P 3.3
We also propose alternative estimates of pattern probability, instead of the usage in covering (Formula 1) we propose to use frequency:
P (X) = PX 2CT f requency(X )
: f requency(X) (2)
Replacing usage by frequency means that patterns may overlap. According to the compression principle, repetitive encoding does not provide the best compression (reduction of L(D; CT ) w.r.t. L(D; ST )), but imposes a heavier penalty on pattern similarity. We leave the study of the side e ects of these changes out of the scope of this paper. In Figure 3 we show how covering changes w.r.t. Krimp (see Figure 2) for the same candidates arranged in the same order. The set of MDL-optimal patterns fABC; ABg computed by Krimp (Figure 2, b) and the set of MDL-optimal patterns fAB; AD; BEg computed with the proposed estimates (Figure 3, d) are di erent. The latter set covers a larger fragment of data and the optimal patterns are less similar.
In our experiments we show that the frequency-based estimate allows one to improve the quality of obtained pattern sets.
In this section we report the results of an experimental study. We compare the following algorithms: Krimp [
As quality measures, we consider the following ones.
Size of pattern sets. The pattern sets of a smaller size can be more easily checked by experts. Thus, the smaller sizes are preferable.
Descriptiveness (coverage ratio). We de ne the coverage ratio as the ratio of entries that are covered by patterns to all non-empty entries. A pattern set is more descriptive if it covers a larger portion of data.
Redundancy (average number of patterns that describe an entry). For non-redundant pattern sets, this value is close to 1. The high values indicate redundancy, i.e., an entry is described by several patterns.
Interestingness (F -measure, precision, recall). We understand interestingness as the ability of patterns to describe \hidden interesting groups of objects". To evaluate interestingness we consider labeled datasets, where class labels were used only to evaluate patterns. As quality measure we choose F-measure (F1 score), as it allows us to take into account both precision and recall of a description:
F1 = 2 precision recall precision + recall :
The results of the experiments are given in Figure 4. The bars/dashes correspond to the averaged values/standard deviation, respectively. Figure 4 shows that KIS provides more stable results, i.e., the standard deviation is smaller for the rst three characteristics, namely the number of optimal patterns, coverage ratio and the number of patterns per cell. The quality of patterns (evaluated with F 1 measure) is higher for KIS (any settings) than for Krimp. Further, we compare approaches in more detail.
Models with disjoint estimates. Let us compare Krimp and KIS based on S- and D-projections. To estimate pattern probability, we use Formula 1 (\disjoint" estimates). Among KIS(S), KIS(D), and Krimp, KIS(S) has the largest average number of patterns (Figure 4, the \disjoint" bar), the highest coverage ratio and the largest number of patterns per cell. That allows us to conclude that KIS(S)-optimal pattern sets are as redundant as Krimp-optimal ones. However, having a larger number of patterns, KIS(S)-optimal pattern sets describe better datasets. KIS(D) generates roughly the same number of patterns as Krimp and has similar redundancy, but allows describing fragments of data larger than those described by Krimp.
From these results we conclude that replacing frequent closed itemsets with biclosed ones and using a multimodel description allows us to improve the descriptiveness (coverage ratio) of pattern sets. In the case of S projections, the complexity of the model (i.e., # patterns, # patterns per cell) does not increase.
Models with overlapping estimates. New probability estimates (in Formula 2) were proposed to improve redundancy of patterns. Let us compare Krimp with KIS algorithm (both simple (S) and detailed (D) projections), where in KIS we use new estimates (Figure 4, \overlapping" bar). The results show that KIS (w.r.t.
Krimp) returns smaller pattern sets that describe larger data fragments and have a lower amount of patterns per cell. Thus, using overlapping estimates we get more descriptive models (coverage ratio) that contain less amount of patterns. It is important to notice that the quality of patterns (F 1-measure) for pattern set computed using overlapping estimates is higher than that for Krimp-optimal.
For KIS we also consider the average number of models computed with two types of estimates. On average, the number of KIS(D)-generated models is lower (2.69 and 2.54 for \disjoint" and \overlapped" estimates, respectively). The average number of KIS(S)-generated models is 4.08 and 3.54 for \disjoint" and \overlapped" estimates, respectively. Thus, KIS based on S-projections converges faster than that based on D-projections, i.e., it needs a lower number of steps to compute the whole set patterns.
To sum up, the proposed modi cations, namely (i) (simply-derivable) biclosed itemsets, (ii) multi-model description, and (iii) new probability estimates allow us to improve the results of PM w.r.t. Krimp. Depending on chosen settings we can signi cantly improve a particular quality measure. The best overall results are achieved for KIS based on D-projections with the proposed (overlapping) estimates. Applying KIS with these settings allows us to reduce considerably the size of pattern sets and pattern redundancy, improving descriptiveness and quality of patterns. 5
In this paper, we have proposed an MDL-based multi-model approach to PM. It is based on an e cient method for computing candidates and combines the best practices of building tree-based supervised models with the state-of-the-art approach called Krimp. The results of experiments show that the proposed approach allows one to obtain non-redundant, interesting pattern sets that describe a large portion of data.
The work of Sergei O. Kuznetsov presented in Sections 2-3 was carried out at St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Science and supported by the Russian Science Foundation grant no. 17-11-01276. [1] Charu C. Aggarwal and Jiawei Han, Frequent pattern mining, Springer, 2014. [2] Mario Boley, Claudio Lucchese, Daniel Paurat, and Thomas Gartner, `Direct local pattern sampling by e cient two-step random procedures', in Proceedings of the 17th ACM SIGKDD DMCD, pp. 582{590, (2011). [3] Leo Breiman, `Random forests', Machine learning, 45(1), 5{32, (2001).