Efficiently Finding Conceptual Clustering Models with Integer Linear Programming

1 Introduction

Data clustering is one of the foundational data mining tasks. Whether it is for the purpose of "unsupervised classification", data reduction, or anomaly detection, identifying groups of similar data points is an important task. Conceptual clustering [Michalski and Stepp, 1983; Fisher, 1987; Perkowitz and Etzioni, 1999; Pensa et al., 2005] provides an additional aspect: the description of clusters by symbolic concepts, typically the domain of concept learning. Traditional approaches [Michalski and Stepp, 1983; Fisher, 1987] combine the formation of the clusters and of the descriptions, having to trade off the demands of one versus the other. Newer techniques [Perkowitz and Etzioni, 1999; Pensa et al., 2005] have instead chosen to decouple finding the descriptions - either before or after the clustering process - and the clustering step.

Given the large search space to traverse, all those techniques are heuristic, meaning that results are heavily influenced by the initialisation conditions, typically requiring numerous restarts, increasing computational costs. Once those have been performed, an additional question is how to identify the relevant result, as we will illustrate in the experimental section (Section 6).

To address this problem, we combine two exact techniques: we use closed itemset mining [Uno et al., 2004] (or formal concept analysis) to discover candidates for descriptions, and integer linear programming (ILP) to select the best clusters (according to an objective function) that can be described by those descriptions. This results in a single optimal solution to the problem setting.

In ILP, this problem has been introduced as set partitioning and set covering problems [Nemhauser and Wolsey, 1988], applied to clustering tasks in [Hansen et al., 1994], and adapted for constrained clustering in [Mueller and Kramer, 2010]. Exact techniques, such as the ones described in this latter work and in [Guns et al., 2013] tend to have problems scaling, and as a side-effect fix the number of clusters to make the problem tractable. In contrast to this, our adoption of closed itemsets cuts down on redundancy compared to other ways of selecting candidate clusters and our use of advanced ILP techniques give our approach additional flexibility.

Our contribution is therefore twofold: we propose an efficient technique for conceptual clustering, based on closed itemsets, that

1. is more flexible in terms of the constraints that can be enforced than existing approaches, and
2. gives more control and stronger guarantees to the user than existing heuristic approaches.

The next section introduces the concepts used in this paper. Section 3 describes how different clustering tasks can be expressed as ILP problems, and Section 4 how to solve them. We discuss related work in Section 5 before demonstrating our technique's performance in Section 6. Section 7 concludes and points towards future research directions.

2 Definitions

In this section we introduce the definitions and concepts that we will use throughout this paper.

2.1 Formal concepts

Let I be a set of n distinct literals called items, an itemset (or pattern) is a non-null subset of I. The language of itemsets corresponds to LI = 2I ∩;. A transactional dataset is a s3 ¶A♦

¶C♦

¶B, E, G♦

(b) Three conceptual clusterings for k=3.

Table 1: Running example (1).

multi-set of m itemsets of LI. Each itemset, usually called a transaction or object, is a database entry. For instance, Table 1a gives a transactional dataset T with m=11 transactions t1↪ ▷ ▷ ▷ ↪ t11 described by n=8 items A↪ B↪ C↪ D↪ E↪ F↪ G↪ H.

Let R be a binary relation between the set T of transactions and the set I of items s.t. (t↪ i) 2 R if the transaction t contains the item i : i 2 t. We denote by R = (T ↪ I↪R) the tuple formed by these sets of transactions, items and the binary relation. R is called formal context [Ganter and Wille, 1997]. Two operators are defined:

• ÷ Let I ✓ I↪ ext(I) = ¶t 2 T ♣ 8i 2 I↪ (t↪ i) 2 R♦
• ÷ Let T ✓ T ↪ int(T) = ¶i 2 I♣ 8t 2 T↪ (t↪ i) 2 R♦

A pair such that (I = int(T), T = ext(I)) is called formal concept. This definition defines a closure property on dataset T , closed(I) , I = int(ext(I)). An itemset I for which closed(I) = true is called closed pattern.

ext(I) is the set of transactions containing all items in I. int(T) is the set of items contained by all transactions in T. These two operators induce a Galois connection between 2T and 2I , i.e. T ✓ ext(I) , I ✓ int(T).

Using ext(I), we can define the frequency of a concept: freq(I) = ♣ext(I)♣, and its diversity: divers(I) = Pt2ext(I) ♣¶i 2 I ♣ (i ◁2 I) ^ (i 2 t)♦♣. Additionally, we can refer to its size: size(I) = ♣¶i ♣ i 2 I♦♣.

2.2 Conceptual clustering

Clustering is the task of assigning the transactions in the data to relatively homogeneous groups. Conceptual clustering aims to also provide a distinct description for each cluster - the concept characterizing the transactions contained in it.

This problem can be formalized as: "find a set of k clusters, each described by a closed pattern P1↪ P2↪ ▷▷▷↪ Pk, covering all transactions without any overlap between clusters". For instance, Table 1b reports the various clusterings for k=3.

An evaluation function f is needed to express the goodness of the clustering. So, conceptual clustering looks for a disjoint set of clusters of T that optimizes a given criterion of clustering quality. For instance, for dataset T and k=3, minimizing f(P1↪ ▷▷▷↪ Pk) = P1ik divers(Pi) provides one clustering s1, with optimal value 18 (see Table 1b).

2.3 Other clustering settings

Other clustering settings [Berkhin, 2006], e.g. soft clustering, co-clustering, and soft co-clustering, can also be expressed by the relationship between transactions and closed patterns.

1. Co-clustering consists of finding k clusters covering both the set of transactions and the set of items, without any overlap on transactions or on items. For instance, s1 provides a co-clustering on the transactional dataset T (see Table 1b).

b. Soft clustering consists of relaxing:

• ÷ either the coverage relation: not all transactions are covered, but at least δt transactions must be covered, where threshold δt  ♣T ♣(= m)
• ÷ or the non-overlap relation: small overlaps are allowed, but a transaction t cannot occur in more than δo clusters, where threshold δo ≥ 1
• Soft co-clustering consists of relaxing the coverage or the non-overlap relations for transactions (as for soft clustering), but also the coverage or the non-overlap relations for items:
• ÷ not all items are covered, but at least γi items must be covered, where threshold γi  ♣I♣(= n)
• ÷ small overlaps are allowed, but an item i cannot occur in more than γo co-clusters, where threshold γo ≥ 1

Example 1 For δt=6, δo=1, γi=7, γo=2, sr = [¶A↪E♦↪ ¶B↪E↪G♦↪ ¶C↪ F↪G↪H♦] is a soft co-clustering since D is the only missing item, items E and G occur twice and ¶t1↪ t7↪ t8↪ t9↪ t10♦ are the uncovered transactions.

2.4 Integer Linear Programming

Integer Linear Programming (ILP) [Nemhauser and Wolsey, 1988] is one of the most widely used methods for handling optimization problems, due to its rigorousness, flexibility and extensive modeling capability. An ILP program is a linear program with the added restriction that all the variables must be integer. Typically, an ILP model involves: (i) a set of decision variables, (ii) a set of linear constraints, where each constraint requires that a linear function of the decision variables is either equal to, less than, or greater than, a scalar value, and (iii) an objective function that assesses the quality of the solution. Solving an ILP problem consists of finding the best solution w.r.t. the objective function in the set of solutions that satisfy the constraints. Formally, an ILP problem takes the form:

where x represents the vector of decision variables, n is the total number of integer variables, cj (1j n) are referred to as objective coefficients, A is an m⇥n matrix of coefficients, and b is an m⇥ 1 vector of the right-hand-side values of the constraints.

3 ILPmodels

This section describes ILP models for the different clustering problems introduced in the previous section.

3.1 Conceptual clustering

Let T be a dataset with m transactions defined on a set of n items I. Let C be the set of p closed patterns (w.r.t. the frequency measure). Let at↪c be an m⇥p binary matrix where (at↪c = 1) iff c ✓ t, i.e., the transaction t belongs to the cluster represented by the closed pattern c.

Hence, the conceptual clustering problem can be modeled as an ILP (see Fig. 1) using p boolean variables xc↪ (c 2 C), where (xc = 1) iff the cluster represented by the closed pattern c belongs to the clustering. Constraints (1) state that each transaction t must be covered by exactly one cluster c. Constraint (2) restricts the number of clusters to k=k0 clusters. The objective function is defined by associating to each cluster c a value vc reflecting the interest (maximize) or cost (minimize) of the cluster c, e.g. minimizing each concept's diversity or maximizing their size.

The quality measures we have introduced are related individually to the given patterns. The number of clusters k can also be defined as a variable whose value will be determined by the ILP solver. Constraint (2') illustrates how to control k by specifying a lower bound kmin and/or an upper bound kmax. Relaxing k removes constraints on the clustering and hence enables finding results from a larger solution space, giving our approach more flexibility (see Section 6.b).

Example 2 Consider the dataset T of Table 1a. The (at↪c) matrix associated with T is outlined in Table 2a. If we consider vc=size(c), then the solution that maximizes the objective function is x2=x12=x15=1, and all other variables xc are equal to 0 (so, k=3). This solution corresponds to the clustering s1 (see Table 1b).

3.2 Co-clustering

Co-clustering consists of finding k clusters covering both the set of transactions and the set of items, without any overlap on transactions and on items. Let wi↪c be an n ⇥ p binary matrix where (wi↪c = 1) iff the item i belongs to the closed pattern c. Fig. 2 depicts the ILP model. Constraints (3) state that each item i must be covered by exactly one cluster c.

Example 3 The optimal solution x2=x12=x15=1 and all other variables xc equal to 0, corresponding to s1 (see Table 1b) is a co-clustering since the associated clusters cover both sets I and T without overlap.

3.3 Soft clustering and soft co-clustering

For soft conceptual clustering (see Section 2.3b), we introduce m boolean variables yt↪ (t 2 T ) such that (yt = 1) iff transaction t belongs to at least one cluster. Fig. 3 depicts the ILP model. First, as Pt2T yt indicates the number of covered transactions, Constraint (5) states that at least δt transactions must be covered. Second, as a transaction t belongs to Pc2C at↪cxc clusters, Constraint (4) states that each transaction t must belong to at most δo clusters. Note that if yt=0, then transaction t is not covered and Constraint (4) is satisfied.

We proceed in the same way for soft co-clustering (see Section 2.3c), by introducing n boolean variables zi↪ (i 2 I) such that (zi = 1) iff item i belongs to at least one cluster. First, as Pi2I zi indicates the number of covered items, Constraint (7) states that at least γi items must be covered. Second, as an item i belongs to Pc2C wi↪cxc clusters, Constraint (6) states that each item i must belong to at most γo clusters. Note that if zi=0, then item i is not covered and Constraint (6) is satisfied. Example 1 provides an example of soft co-clustering.

Additional constraints can be added in order to avoid undesired clusterings. For instance, one can specify extra constraints on the frequency of closed patterns (e.g. freq(c) > 1) which leads to a more balanced clustering for the dataset T , and may avoid outliers receiving their own clusters. In this case, the optimal solution to our running example is x4=x7=x8=1, and all other variables xc are equal to 0. It corresponds to the conceptual clustering s3 (see Table 1b).

4 Preprocessing and solving

We have defined an ILP framework to express various kinds of clusterings. The strength of this framework lies in its flexibility in terms of the constraints that can be enforced. In Section 3, we defined constraints that enforce global restrictions on the clusters such as: clusters cover all of the transactions (or a minimum number of them), clusters should be disjoint (or have restricted overlaps), etc. But, in practice, there might be local constraints that should be defined on each individual closed pattern such as :

• minimum and maximum frequency constraints,
• MustLink(ti↪ tj) requires that transaction ti should be in the same cluster as tj,
• CannotLink(ti↪ tj) requires that transaction ti should not be in the same cluster as tj.

The more selective local constraints are, the fewer the number of closed patterns for the solving step. Finally, the whole clustering process consists of the following two main steps:

• Preprocessing step: compute closed patterns using efficient state-of-the-art extractors, e.g. LCM, and filter those violating local constraints. Constraints like minimum frequency and size are directly handled by the extractor. For CannotLink(ti↪ tj), any cluster c s.t. ti and tj belongs to ext(c) is removed. MustLink constraints are handled similarly.
• Solving step: solve one of the ILP clustering models detailed in Section 3 using efficient ILP solvers.

5 Related work

Conceptual clustering has been introduced in [Michalski, 1980], and extended in [Michalski and Stepp, 1983; Fisher, 1987]. Numerous approaches have been devised for tackling this problem, e.g. of statistical, syntactic or hierarchical nature [Schalkoff, 2008], with hierarchical conceptual clustering arguably the most prominent one among them [Fisher, 1987; Thompson and Langley, 1991].

Heuristic approaches Several methods have explored the idea of decoupling cluster-formation from finding the conceptual descriptions. Notably, Pensa et al. [Pensa et al., 2005] also begin by mining closed (or δ-closed) patterns (itemsets) and their extensions and then perform k-Means clustering on them. Perkowitz and Etzioni [Perkowitz and Etzioni, 1999], reverse the two phases: their cluster-mining first uses a clustering technique to form clusters. From the resulting clustering, descriptions are learned by a rule-learning technique. Instances are matched to descriptions, potentially leading to overlapping clusters. Finally, [Geerts et al., 2004] introduced tiling. A tile is a formal concept, and in that work two settings are considered: i) finding k tiles that cover as many transactions as possible, and ii) finding the minimum number of tiles that cover all transactions. Both are clearly conceptual clustering settings but since tiles can overlap, so can clusters.

CP/SAT for pattern set mining. The CP-paradigm is at the core of generic approaches to deal with k-pattern sets [Khiari et al., 2010; Guns et al., 2013]. These methods allow to model sets of patterns, satisfying properties on the whole set, in a declarative and flexible way, such as conceptual clustering, k-tiling, to name a few, but they look for sets containing a fixed number of patterns and tend to have problems scaling. In [M´etivier et al., 2012], the authors formulate the conceptual clustering task as queries in given language. These queries are then translated into SAT clauses and resolved by a SAT solver. However, the proposed framework does not allow to express optimization criteria and has problems scaling.

ILP/CP for distance-based clustering. Distance-based clustering relies upon dissimilarities (or similarities) between numerical attributes. In this line, several declarative approaches have been proposed. In [Dao et al., 2013], a CP approach has been used. The proposed approach supports various kinds of user constraints. In [Babaki et al., 2014], an exact approach, which uses column generation in an ILP setting, is presented. This approach extends the one proposed in [Aloise et al., 2012]. In [Mueller and Kramer, 2010], a constrained clustering approach using ILP is proposed. This approach takes as input a set of possible base clusters and builds a clustering by selecting a suitable subset. The number of clusters k must be given upfront. In contrast, our proposal allows relaxing k by specifying lower/upper bounds. In their experiments, the set of base clusters is generated from frequent patterns. This makes the approach less applicable, because the number of base clusters is huge and selecting a suitable subset is challenging. Our adoption of closed patterns cuts down on redundancy compared to other ways of selecting candidate clusters and makes the solving step more efficient by reducing dramatically the number of candidate clusters.

6 Experiments and Results

The experimental evaluation is designed to address the following questions:

1. How (in terms of CPU-times) does our approach (CCLP) compare to the CP approach of Guns et al. (KPatternSet) and the approach of Mueller et al.?
2. How do the resulting clusters compare w.r.t. different objective functions?
3. In light of the exact nature of our approach, how do the resulting clusters and their descriptions compare qualitatively with those resulting from existing heuristic approaches that operate in a similar framework? The two approaches with which we compare ourselves are those of Pensa et al. (CDKMeans) and Perkowitz et al. (CM).

Experimental protocol. Experiments were carried out on the same datasets which were used in [Guns et al., 2013] and available from the UCI repository. Table 3 shows the characteristics of these datasets. All experiments were conducted on AMD Opteron 6282SE with 2▷60 GHz of CPU and 512 GB of RAM. We used LCM to extract the set of all closed patterns and CPLEX v▷12▷4 to solve the different ILP models. For all methods, a time limit of 24 hours has been used.

Experiments have been performed without any local constraints on individual closed patterns. To evaluate the quality of a clustering, we test the coherence of a clustering, measured by the intra-cluster similarity (ICS) and the interclusters dissimilarity (ICD), both of which should be as large as possible. Given a similarity measure s between two trans-

actions t and t0 , where s : T ⇥T 7! [0↪ 1], s(t↪ t0 ) = ♣t\t0 ♣ ♣t[t0 ♣

(a) Comparing CCLP with KPatternSet. Figs. 4a and 4c compare the performance of the two methods on model M1 for various values of k on different datasets w.r.t. the first optimization setting (i.e. description size). The CPU-times of CCLP-M1 include those for the preprocessing step. For (k = 3), KPatternSet dominates CCLP-M1 except on Soybean, Zoo-1 and Mushroom. But, for (k ≥ 4), CCLP-M1 outperforms KPatternSet by several orders of magnitude on all datasets. Finally, KPatternSet fails to find a solution within the time limit for (k > 5). On Audiology dataset, both approaches were not able to find a solution. This is in part explained by the number of closed patterns (106 ) in comparison to the other datasets (from 103 to 105 ). For the second optimization setting (see Fig. 4b), the same observations can be made. Note that on Tic-Tac-Toe no conceptual clustering exists for (k = 4).

(b) Impact of relaxing k. To assess the interest of relaxing k, Fig. 4d compares the performance of CCLP-M1 with k relaxed (CCLP-M1-relaxed) against CCLP-M1 in terms of the best value found for k (Col. 2 vs. Col. 5) and CPU-times (Col. 4 vs. Col. 7). Reported in Col. 5 are the best values found for k (3k10) that maximize the description size. Both settings obtain the same best value for k. Indeed, there is a bias towards a k near kmax when using the description size. When comparing the CPU-times, CCLP-M1-relaxed is often faster, particularly on the two most difficult datasets Anneal and Hepatitis (speed-up of up to 3▷84).

Contrary to Mueller et al., our approach allows to relax k. To compare the two, we implemented the mean of inner cluster similarities (i.e., s(x↪ y)), the objective function used by that work, for fixed k (denoted CCLP-M1-Dist). Fig. 4d compares CCLP-M1-relaxed with CCLP-M1-Dist in terms of the best k found, and CPU-times. Both approaches almost always agree on the best value for k and obtain comparable CPU-times on the first 7 datasets, while on the two difficult datasets CCLP-M1-relaxed is clearly better. Fig. 5d shows that clusterings found by relaxing k are close to those found with fixed k

Finally, in Fig. 4d, one can see that the preprocessing step is negligible as compared to the solving step, except on the two last datasets due to the high number of closed patterns.

(c) Qualitative analysis of clusterings. To assess the quality of clusterings, we have plotted their values according to measures ICS and ICD. Points (see Fig. 5) represent the optimal clusterings obtained for different values of k on the selected datasets. A specific color is assigned to each dataset. A label, representing the value of k, is associated to some points with the same color. Moreover, we omitted to plot points that are on the Pareto front in Figs. 5b and 5c since they are incomparable. Fig. 5a shows the two optimization criteria of CCLP-M1. Except for the Vote and Tic-Tac-Toe datasets, the diversity measure sacrifices ICS to achieve higher ICD values. This is indicative of more balanced clusters: the ICS is necessarily limited by the number of instances per cluster but the ICD increases if there are more instances in other clusters to compare against. The size measure shows the opposite behavior, which is indicative of one (or a few) large clusters, and numerous smaller ones.

To compare with CDKMeans and CM, 1 we first have to identify a good comparison clustering. To that end, (i) we ran each technique 100 times to smooth out the random initialization effects typical for k-Means, (ii) then we grouped the resulting into equivalence classes, in which clusterings agree on the composition of all clusters, (iii) finally, we chose the largest equivalence class and used its representative (i.e. one of the clusterings in it, since all have the same composition). If there were several equally large equivalence classes, we used a representative from each class.

The results show how difficult it can be to control the results of heuristic techniques: the representative clusterings of the CM approach never cover all transactions in the data, and often have overlapping clusters. Fig. 5b shows that the clusterings computed by CM have a qualitative disadvantage compared to the clusterings found by CCLP-M1 (points of CM are always dominated by those of CCLP-M1). For the sake of fair comparison, we run CCLP-M3 with settings that allowed

1 For CM we used SimpleKMeans and JRip in Weka. We reimplemented CDKMeans : http://www.scientific-datamining.org/software/cdkmeans.zip.

(a) Maximizing description size.

(b) Minimizing pattern diversity.

(c) Maximizing the description size.

Figure 4: Comparing CPU-times.

similar amounts of non-coverage. In case that several equally large equivalence classes existed, we chose the clustering that maximized ICS and ICD and used its coverage as constraint for CCLP-M3. Figure 5c shows that our framework can approximate the results of the heuristic technique.

CDKMeans is even more difficult to control by the user: when using all closed patterns, the algorithm usually assigns all instances to one or two clusters, no matter k. Enforcing frequency constraints improves this situation somewhat even though ♣C♣  k for k ≥ 4. Additionally, the clusterings occasionally fail to stabilize, resulting in 100 different clusterings. Finally, the particular representation of clusters in CDKMeans can result in clusters that have descriptions yet no transactions assigned to them.

7 Conclusions

We have proposed an efficient approach for conceptual clustering that uses closed itemset mining to discover candidates for descriptions, and ILP to select the best clusters. Closed itemsets cut down on redundancy compared to other ways of selecting candidate clusters and ILP gives our approach more flexibility than exact ones, and stronger guarantees to the user than heuristic ones. We plan to exploit local search techniques to enhance the solving step.

Acknowledgements.

This work was partially supported by the Eiffel Excellence program - French Ministry of Foreign Affairs and International Development, REFERENCE: UR / EIFFELDOCTORAT 2015 / 840868H.

This work was partly supported by the ANR (French Research National Agency) funded project Hybride ANR-11BS002-002.