Mining Convex Polygon Patterns with Formal Concept Analysis

1 Introduction

Highly focused on over the past 20 years, pattern mining, the task of discovering interesting generalizations of object descriptions (subsets, subsequences, subgraphs, etc) has become a mature subfield in AI for knowledge discovery purposes [Giacometti et al., 2013]. When objects are given with a class label, discriminant patterns enable to elicit hypotheses from the data and to build intelligible classifiers [Zimmermann and Nijssen, 2014].

Dealing with numerical data, and especially spatiotemporal data is still challenging. Algorithms supporting the correct, complete and non-redundant enumeration of particular shapes, say geometrical, have surprisingly not attracted much research interest [Aggarwal and Han, 2014]. Generally, numerical attributes (even spatial) are discretized, either in a pre-processing or on-the-fly during the execution (run) of a pattern enumeration algorithm (e.g. [Grosskreutz and R¨uping, 2009]), which has the consequence of considering geo-coordinates attributes independently and thus rectangular shape patterns occur. Still, such patterns were successfully used for mining numerical data (e.g. with most of the subgroup discovery approaches [Duivesteijn et al., 2016]), and spatial data (such as urban and mobility data see e.g. [Bendimerad et al., 2016] and [Kaytoue et al., 2017]).

The problem with rectangular shapes can be observed on the right hand side figure. Each object gives a POI (Point Of Interest) of a given type (Hotel, Restaurant, University, ...) and position. An interesting pattern is understood as a geographical area for which there is a sufficient number of points, high density, and a high

proportion of objects of the same type. The candidate areas could have any shape. Rectangles, as being the products of intervals, have edges parallel to the plane axes: they may enclose both dense and sparse regions. Arbitrary polygons stick too much to the data and are hard to interpret. We consider convex polygons, a good trade-off for capturing high density areas.

Our contribution introduces a new type of patterns, convex polygons, with FCA tools [Ganter and Wille, 1999], going beyond the formalization of hyper-rectangles given by [Kuznetsov, 2005] in the early 1990s and introduced in pattern mining by [Kaytoue et al., 2011]. We thus make precise the well-known notion of Galois connection as well as several polygon enumeration techniques and associated algorithms, using several concepts from computational geometry. We introduce several polygon constraints and experiment with our algorithms. We show that polygons give a better trade-off between area, density and homogeneity for mining spatial data. These findings give the basic bricks for any pattern mining algorithm dealing with, among others, a spatial attribute. The major problem with polygons is their worst-case exponential number (in number of input points). This is probably why they were not used in pattern mining until now: Exhaustive enumerations fail at considering large datasets even with 100 objects. We finally show that embedding our enumeration techniques in a recent pattern sampling technique (Monte Carlo Tree Search) enables us to discover high quality patterns very quickly in large datasets.

In what follows, Section 2 recalls how to properly define and enumerate hyper-rectangles with FCA. Section 3 defines polygon patterns, while Section 4 details our algorithms. Before to conclude, in Section 5 we present a wide range of experiments to support our claims.

2 Interval Patterns

We recall first the formalization of interval patterns, or hyperrectangles, in terms of FCA, for understanding next our formalization of convex polygon patterns.

Numerical dataset. A numerical dataset is given by a set of objects G, a set of numerical attributes M = {mi}1≤i≤∣M∣, where the range of mi ∈ M is a finite set denoted by Wmi , mi(g) = w means that w is the value of attribute mi for object g ∈ G. Figure 1 plots 5 objects with 2 attributes on the Euclidean plane.

Interval pattern. An interval pattern is a box (hyperrectangle) with sides parallel to coordinate axes formally defined as the Cartesian product of intervals d = ⟨[ai, bi]⟩1≤i≤∣M∣. An object g is in the image of an interval pattern d when mi(g) ∈ [ai, bi] ∀i ∈ J1, ∣M∣K. The support of

d, denoted by sup(d), is the set of objects in the image of d. Interval pattern search space. The search space of interval patterns is the finite set D of all interval vectors ⟨[ai, bi]⟩1≤i≤∣M∣ with ai, bi ∈ Wmi . The size of the search

space is given by: ∣D∣ = ∏i∈J1,∣M∣K(∣Wmi ∣ × (∣Wmi ∣ + 1)/2).

Many patterns in D have exactly the same support: different hyper-rectangles contain the same objects. To avoid this redundancy, a closure operator can be defined, and only closed patterns which are unique for a given support are retained. This is achieved thanks to the formalism of pattern structures introduced by [Ganter and Kuznetsov, 2001]. An interval pattern structure is given by (G, (D, ⊓), δ) where G is the set of objects, (D, ⊓) the semi-lattice of object descriptions (boxes) and δ ∶ G → D a mapping that associates to each object g ∈ G, a vector of numerical intervals in the form of one-point interval δ(g) = ⟨[mi(g),mi(g)]⟩i∈J1,∣M∣K. Elements of D are called patterns and are ordered as follows: c ⊓ d = c ⇔ c ⊑ d. The infimum ⊓ is defined as follows. Let c = ⟨[ai, bi]⟩i∈J1,∣M∣K and d = ⟨[ei, fi]⟩i∈J1,∣M∣K we have c⊓d = ⟨[min(ai, ei), max(bi, fi)]⟩i∈J1,∣M∣K which is the minimal bounding box of the two boxes c and d. The two following operators (.)◻ , with A ⊆ G and d ∈ (D, ⊓)

form a Galois connection between (2G, ⊆) and (D, ⊑). (.)◻◻ is a closure operator, i.e., monotone, extensive, idempotent. Closed patterns, i.e., such that d = d◻◻ are smallest patterns/rectangles for a given support. We note that, for any description (box) d ∈ D, d◻◻ represents the minimal bounding box of the support of d (d◻ , objects enclosed by d). Figure 1 shows an example where G = {g1, ..., g5}, we have d = ⟨[1, 2], [1, 4]⟩ (left figure) which support is d◻ = {g1, g2, g3}. However d is not closed. Indeed, d◻◻ = {g1, g2, g3}◻ = ⟨[1, 2], [1, 3]⟩ (right figure) which represents its closure (the minimal bounding box of {g1, g2, g3}).

Interval patterns enumeration. Consider first data with a single attribute. To enumerate all interval patterns in (D,⊓), [Kaytoue et al., 2011] started from the top pattern, which is the minimal bounding box of all objects in G (G◻ ). Then, as shown in Figure 2, at every step of the algorithm two minimal changes are ap-

y

y

plied (minimal left change (minLeftChange) and minimal right change (minRightChange)). To ensure a nonredundant generation, minLeftChange are not allowed after minRightChange. For ∣M∣ numerical attributes, the algorithm is the same with two differences: (1) It considers a total order on the set of attributes M; (2) When a minimal change is applied to the attribute mi, only attributes mj >= mi can be refined in further steps from the generated pattern.

Closed interval patterns enumeration. To enumerate only closed patterns in (D,⊓) (minimal bounding boxes), [Kaytoue et al., 2011] adapted CloseByOne of [Kuznetsov, 1993]. Consider a pattern d generated by a change at attribute mj ∈ M. Its closure is given by d◻◻ . If d◻◻ differs from d for some attributes mi ∈ M such as mi < mj, then d◻◻ has already been generated: the algorithm backtracks. Otherwise, it continues the enumeration from the closed pattern d◻◻ .

3 Convex Polygon Patterns

The choice of convex polygons instead of arbitrary ones is motivated by the fact that (i) it generalizes intervals (convex) and (ii) it is a natural way to avoid non-convex polygons which would over-fit the data.

3.1 Preleminaries

Convex polygon. A convex polygon P, represented as a sequence of points [p1, ..., ph] in R2 , is a simple polygon (not self-intersecting) where all interior angles are strictly less than π. The ordered point sequence [p1, ..., ph] is denoted by P and is given in counterclockwise order (ccw). Points pi are called extreme points and oriented line segments pipi+1 following this order are called edges of the polygon P (where i + 1 = 1 if i = h and i - 1 = h if i = 1).

Note that an oriented line segment AB subdivides R2 in 4 regions: (i) AB+ (resp. (ii) AB- ) the open upper (resp. lower) half-plane of AB (i.e. Q ∈ AB+ implies that ABQ is a triangle in ccw (resp. cw) order), (iii) AB0 the set of points on the segment AB and (iv) the points that are collinear with A and B but outside AB.

Let q ∈ R2 . An edge pipi+1 is said to be visible from q (or q sees pipi+1) iff q ∈ pip-i+1 . A point q is in the enclosed area of the polygon P iff q does not see any edge of P (q ∈ pip+i+1∀i ∈ {1, ...,h}). Conventionally, ∅, points and segments are considered as convex polygons.

Convex hull. Given a finite set E ⊆ R2 , the convex hull of E denoted by ch(E) is the smallest convex set that contains E, which is a convex polygon. Note that ch(E) ⊆ E. In other words, extreme points of the convex hull of E are in E. Application ch ∶ R2 → R2 is monotone, extensive, and idempotent, i.e., a closure operator.

Example. Figure 3 shows a polygon P where extreme points set P = [p1, p2, p3, p4, p5, p6]. The point I is in the area enclosed by the polygon P. The point C1 (resp. C2) sees only the edge p3p4 (resp. p4p5). Generally spoken, the green triangle (resp. yellow triangle) represents all possible points that are only visible by the edge p3p4 (resp. p4p5). The point O sees the two edges p3p4 and p4p5.

3.2 Convex Polygon Pattern Structure

Spatial attribute. A spatial attribute m takes values in R2 . Given a set of objects G, m(g) = p means that p ∈ R2 is the value of attribute m for object g ∈ G. Analogically, for a subset A ⊆ G, m(A) = {m(g) ∣ g ∈ A} ⊂ R2 . For the sake of simplicity, we will consider now a dataset G having only one spatial attribute m. For ease of notations, g and m(g) (G and m(G)) will be used interchangeably in what follows.

Convex polygon pattern. A convex polygon pattern d is a convex polygon [pi]1≤i≤h given in ccw order. An object g is in the image of a convex polygon pattern d when m(g) is in the enclosed area formed by the polygon d. The support of d, denoted by sup(d), is the set of objects g ∈ G in the image of d. In Figure 3, d = [p1, p2, ..., p6] is a convex polygon pattern which support is sup(d) = {p1, p2, ..., p6, I}.

Convex polygon pattern structure. It is defined as follows: (G, (D, ⊓), δ) where G is the set of objects described by one spatial attribute m, (D,⊓) is the semi-lattice of object descriptions (convex polygons) where D = {ch(m(A))∣A ⊆ G}. The mapping δ ∶ G → D takes each object g ∈ G to δ(g) = [m(g)] (a degenerate polygon with a singleton point). The infimum ⊓ is defined as follows. Let c and d be two descriptions in D, we have c ⊓ d = ch(c ∪d). Elements of (D,⊓) are ordered as follows: c ⊑ d ⇔ c ⊓ d = c ⇔ d ⊆ ch(c). Thus, the Galois operators (.)◻ are defined as follows, with A ⊆ G and d ∈ (D,⊓): d◻ = {g ∈ G ∣ m(g) ∈ ch(d)} and A◻ = ch(m(A)). A pair (A, d) s.t. A◻ = d and d◻ = A is a concept. Both A and d are closed under (.)◻◻ . The set A contains all objects, while d contains only extreme points in ccw order.

Mining convex polygons with constraints. There are 2n convex polygons in the worst case (n points on a circle). Not all of them are interesting, we thus define several constraints a pattern shall respect. The problem is then, given a set of points in R2 , to find all polygon pattern concepts (A, d) respecting one or more of the following constraints, such as shape complexity (∣d∣ ≤ δcompl), minimal support (∣A∣ ≥ δsupp), minimal/maximal perimeter (perim(d) ≥ or ≤ δperim), and minimal/maximal area (area(d) ≥ or ≤ δarea). We also wish patterns that maximize a class homogeneity (e.g. lowGini) and density (∣A∣/area(d)).

By using minimal support we avoid considering polygons with too few points. The density has to be understood as a relative support (support normalized by area). The number of extreme points characterizes the complexity of the polygon in terms of interpretation (point, segment, triangle, quadrilateral, ...). The simpler the form the better by principle of parsimony: Minimizing the shape complexity may also avoid over-fitting the data when searching for discriminant patterns. Controlling perimeter and area is also important: It allows one to express different types of patterns (e.g. avoiding or forcing thin polygons, with a large perimeter and small surface).

4 Algorithms

Let G be a finite subset of R2 . We propose three algorithms for mining convex polygon patterns. The first one enumerates object subsets in a bottom-up way (from ∅ to G) with closures. The next one considers a top-down enumeration and does not compute costly closures. The last one considers a bottom-up enumeration of polygons by shape complexity (points, then segments, then triangles...) and performs the best.

4.1 Enumerating Point Sets

As the operators ((.)◻ , (.)◻ ) form a Galois connection, the set of all pattern concepts is given by C = {(A◻◻ ,A◻ ), ∀A ⊆ G}. The A◻ are precisely the polygon patterns and can thus be obtained by enumerating closed object subsets with the generic algorithm CloseByOne (CbO) of [Kuznetsov, 1993] and its modern efficient software realization [Andrews, 2015]. The principle is the following. The lattice (2G, ⊆) is explored with a DFS starting from ∅. A total order on G is provided, e.g. g1 < g2 < ... < gn. A new object set A is generated from a previous one by adding next object g w.r.t. < and (A◻◻ ,A◻ ) is the resulting pattern concept. The concept is discarded (DFS backtrack) if an object smaller than g w.r.t. < is added. It is proven that this algorithm outputs the correct, complete and non-redundant collection of closed patterns. Namely, EXTCBO (Algorithm 1) is the version of CbO where concepts are computed w.r.t. increasing generality order, i.e., by adding one object at a time. Algorithm EXTCBO will serve as a baseline.

Algorithm 1 EXTCBO

1: Let (G, ≤) be a totally-ordered finite subset of R2 2: procedure EXTCBO( ) 3: TRAVERSE(∅,∅,1) 4: end procedure 5: procedure TRAVERSE(c,d,pos) ▷ c is the extent, d the intent 6: Print(c,d) ▷ visit pattern concept (c, d) 7: for i ∈ pos, ..., ∣G∣ and gi /∈ c do 8: cnew ← c ∪ {gi} 9: dnew ← c◻new ▷ Compute convex hull 10: cnew ← d◻new 11: if ∀j ∈ J1, iK ∶ gj /∈ c → gj /∈ cnew then 12: TRAVERSE(cnew,dnew,i+1) 13: end if 14: end for 15: end procedure

4.2 Updating a Delaunay Triangulation

The enumeration starts from the most general pattern G◻ . Minimal changes are applied to obtain the next pattern to ensure the correctness and completeness of the enumeration: all convex polygons and only them are visited. Let us consider the convex polygon pattern d = [p1, ..., pi, ..., p∣d∣]. A minimal change to d consists in removing an extreme point (as done with interval patterns). There are ∣d∣ of such minimal changes for a polygon d for obtaining next smaller polygons e = d/{d[i]} s.t. d ⊏ e, i ∈ J1, ∣d∣K. When a new pattern e is generated, we need to compute its convex hull to discover its extreme points dnew = e◻◻ and continue the enumeration.

This algorithm is again an instance of CloseByOne, but follows a top-down enumeration. Sadly, it still forces to compute the convex hull e◻ at each step. Fortunately, it can be avoided with a Delaunay triangulation.

Delaunay triangulation. The Delaunay triangulation of a set of points P denoted by DT(P) is a partition of the convex hull ch(P) into O(n) triangles such that: (i) Triangles vertices are in P, (ii) No point in P is inside the circumcircle of any triangle in DT(P) besides the vertices of the triangle. The complexity of computing DT(P) is O(∣P∣ ⋅ log(∣P∣)) [Zalik, 2005].

Algorithm DELAUNAYENUM. The key idea is the following. Efficiently computing e◻ = (d/{d[i]})◻ , that is the next closed pattern obtained from removing the extreme point i of d, is equivalent to computing DT(d / {d[i]}) from DT(d). During this computation, one can easily update the sequence of extreme points. [Devillers, 1999] answered this problem with an efficient algorithm (O(k ⋅ log(k)) complexity), where k is the number of points sharing an edge with p (neighbor points).

0 1 2 3 4 5 6

Our algorithm DELAUNAYENUM (Algorithm 2) enumerates Delaunay triangulations dt and maintains at each step the sequence of extreme points d. It starts from pattern G◻ = ch(G) (line 4). Consider a step in the enumeration where d is the current pattern, dt the current triangulation and c the current image of d. We remove successively extreme points p ∈ d and we update the Delaunay triangulation dtnew based on dt (line 11), the new description dnew (sequence of extreme points) (line 12) and the new support cnew by removing objects with value p from c (line 13). To avoid redundancy (avoid visiting the same pattern twice), removal of extreme points before the last removed extreme point p are not allowed (argument pos in Algorithm 2) in further steps. In order to do that simply, when the extreme point sequence d is updated upon extreme point i removal, we only insert the new extreme points (extreme points not in d) at the position i while keeping the same order (counterclockwise). Figure 4 (from left to right) shows an example of how the algorithm updates the description d = [A,B,C] upon removal of the extreme point C (position 3) and produces the description dnew = [A, B, D, E] where D and E denote the new extreme points that replaced C. The enumeration continues by removing D.

Algorithm 2 DELAUNAYENUM

1: Let G be a finite subset of R2 2: procedure DELAUNAYENUM( ) 3: dt ←DELAUNAY(G) 4: d←dt ▷ dt = G◻ = ch(G) 5: TRAVERSE(G,d,dt,1) 6: end procedure 7: procedure TRAVERSE(c,d,dt,pos) 8: Print(c,d) ▷ visit pattern concept (c, d) 9: for i ∈ pos, ..., ∣d∣ do 10: p ← d[i] 11: dtnew ← DELAUNAY REMOVE(dt,p) 12: dnew ←dtnew ▷dnew[1] = d[1] or dnew[∣dnew∣] = d[∣d∣] 13: cnew ← c/[p]◻ ▷ [p]◻ = {g ∈ G ∣ m(g) = p} 14: TRAVERSE(cnew,dnew, dtnew,i) 15: end for 16: end procedure

4.3 Enumerating Simpler Shapes First

Until now, elements of (D, ⊑) were enumerated w.r.t. polygon inclusion order. Now we consider the poset (D, ¯⊑), where polygons are ordered w.r.t. extreme points inclusion: c ¯⊑ d⇔c ⊇ d. Intuitively, the ith level of (D, ¯⊑) contains all polygons with i extreme points (i = 3 are the triangles, i = 4 the convex quadrilaterals, ...). Enumerating simpler shapes first is interesting as they are easier to interpret and less stick to the data points (prevent overfitting). Note that the new order ¯⊑ will change only the enumeration order.

In order to enumerate all the polygons w.r.t. the new order ¯⊑ in a bottom-up fashion as simpler shapes are preferred, one can simply adapt EXTCBO. Indeed, polygons are represented as extreme points sets which can be enumerated starting from ∅. However, it requires to compute at each step the convex hull of the set of points (closure) which is extremely slow. To avoid this, we propose an enumeration technique relying on basic geometry: points used to extend a pattern produce a new closed pattern for sure. That is to say: (i) there is no need to compute the convex hull and (ii) there is no need to discard a pattern as done in EXTCBO since every generated pattern is new. This can be done thanks to pattern candidate maintenance as explained below.

In what follows, without loss of generality and for the sake of simplicity, elements of G are pairwise distinct. Moreover, for any oriented line segment AB: AB+ , AB- and AB0 will denote finite sets where only points of G are considered (rather than R2 ).

Pattern candidate points array. Consider a convex pattern d = [p1, ..., ph] where ∀i ∈ J1, hK ∶ pi ∈ G. We define a samesize array nd called candidate points array where nd[i] gives the set of points that are visible from and only from the edge pipi+1. Formally, if h ≥ 2:

In case of h = 1, we have nd[1] = G/{p1}. The proposition below gives a simpler formula for n[i] when h ≥ 2:

Proposition 1. If h ≥ 2, ∀i ∈ J1,hK we have:

Extending a pattern and candidate maintenance. We have the following proposition:

Proposition 2. ∀i ∈ J1, hK, ∀q ∈ nd[i], we have:

In other words, extending a pattern d by adding a candidate point q creates a new pattern e = d ⊓ [q] s.t. e ⊑ d.

Proposition 3 gives a method to compute the support and the candidate points of the new pattern e:

Proposition 3. If h ≥ 2, ∀i ∈ J1,hK, ∀q ∈ nd[i], if e = d⊓ [q] and ne its candidate points array, we have:

Note that [pi, q, pi+1]◻ is the subset of objects enclosed in the area formed by the triangle [pi, q, pi+1]. Formally: [pi, q, pi+1]◻ = piq0 ∪qp0i+1 ∪pip0i+1 ∪(pip-i+1 ∩piq+ ∩qp+i+1 ).

Propositions 1 and 2 are direct results from planar geometry [Overmars and van Leeuwen, 1981], while Proposition 3 is a direct reformulation of Proposition 1.

Figure 3 shows a description d = [p1, p2, p3, p4, p5, p6] with candidate points nd = [∅,∅, {C1}, {C2},∅,∅]. More generally, every point that falls in the green (resp. yellow) zone is a candidate point for the edge p3p4 (resp. p4p5). However, the point O is not a candidate point for any edge. Indeed, O sees two edges p3p4 and p4p5.

Algorithm EXTREMEPOINTSENUM. The algorithm EXTREMEPOINTSENUM (Algorithm 3) follows almost the same enumeration principle as that of EXTCBO. The difference lies in maintaining the list of object candidates that can be added to a pattern d to generate patten e ⊏ d. The other difference is that the two first levels are enumerated in BFS manner. This allows one to build the segment index S that for each distinct object pair gigj of G stores the support gig0 j (objects in segment gigj) and its candidates gigj and gig+ j . Note that the segment index S can be seen as a strictly upper triangular matrix. The algorithm continues in a DFS-fashion to enumerate higher levels (k ≥ 2). To prevent redundancy, an arbitrary total order on G is provided, e.g. g1 < g2 < ... < gn. When extending a pattern d = [p1, ..., ph], which candidate points array is nd, with a point q ∈ nd[i], only points q s.t. pj < q ∀j ∈ J1, hK are considered.

Algorithm 3 EXTREMEPOINTSENUM

1: Let (G, ≤) be a totally-ordered set of pairwise distinct points 2: Let S be the segment index 3: procedure TRAVERSE(c, d, n, pos) 4: Print(c,d) ▷ visit pattern concept (c, d) 5: for i ∈ 1, ..., ∣d∣ do 6: for j ∈ n[i] and j >= pos do ▷ j ≥ pos for non redundancy 7: s1 ← S[d[i]][j] ▷ first new segment d[i] → j 8: s2 ← S[j][d[i + 1]] ▷ second new segment j → d[i + 1] 9: dnew ← [d[1], ..., d[i], j, d[i + 1], ..., d[∣d∣]] 10: cnew ← c ∪ s10 ∪ s20 ∪ (n[i] ∩ s1+ ∩ s2+ ) 11: nnew ← [n[1], ..., n[i], n[i], n[i + 1], ..., n[∣d∣]] 12: nnew[i] ← n[i] ∩ s1- ∩ s2+ 13: nnew[i + 1] ← n[i] ∩ s2- ∩ s1+ 14: nnew[i - 1] ← n[i - 1] ∩ s1+ 15: nnew[i + 2] ← n[i + 1] ∩ s2+ 16: TRAVERSE(cnew,dnew, nnew,j + 1) 17: end for 18: end for 19: end procedure 20: procedure EXTREMEPOINTSENUM( ) 21: Print(∅,∅) ▷ visit the empty pattern concept (∅,∅) 22: Enumerate in BFS-fashion all distinct points G 23: Compute segment index S 24: for i ∈ 1, ..., ∣P ∣ - 1 do 25: for j ∈ i + 1, .., ∣P ∣ do 26: s ← S[i, j] 27: TRAVERSE(s◻ ,[i, j], [s- , s+ ],j+1) 28: end for 29: end for 30: end procedure

Detailed example. Figure 5 gives a detailed step-by-step partial enumeration of convex patterns related to G w.r.t. ⊑ partial order. In each subfigure, red points are extreme points, yellow points are part of the support of the pattern but not extreme points, green points are candidate points and black points are not candidates (points located in the red zones).

5 Experiments

We report an experimental study of the different algorithms, carried out on a machine equipped with Intel Core i72600 CPUs 3.4 Ghz machine with 16 GB RAM. Algorithms are implemented in Java. All materials are available on https://github.com/BelfodilAimene/ MiningConvexPolygonPatterns.

Mining polygon patterns. We compare our three algorithms without any constraint: EXTCBO, DELAUNAYENUM and EXTREMEPOINTSENUM. Figure 6 plots for each one their run times and the number of pattern candidates they generated. Datasets consist of n objects drawn from the IRIS dataset uniformly from the three different classes for the attributes sepal-length and sepal-width (or petal-lentgh and petal-width). First, notice that EXTCBO generates a lot of candidates discarded by the canonicity test (redundant), while the two others generate each pattern only once. This implies that EXTCBO is from one to two orders of magnitude slower (it is the only one computing closures). Interestingly, EXTREMEPOINTSENUM is faster than DELAUNAYENUM as it does not require to compute and update a Delaunay triangulation (even when the state-of-the-art [The CGAL Project, 2016] is used).

Impact of the constraints. EXTCBO enumerates convex polygons in a bottom-up fashion w.r.t. inclusion. It can thus only handle maximum perimeter and area constraints that are monotone (the proof is given, e.g. by [Bogomolny, 2017]): when a pattern is generated and does not satisfy the constraint, the algorithm backtracks (a well-known property in pattern mining). DELAUNAYENUM enumerates convex polygons in a top-down fashion w.r.t. inclusion. It can thus naturally prune w.r.t. minimal support, area and perimeter. EXTREMEPOINTSENUM enumerates patterns by inclusion but also from simpler to more complex shapes (extreme points inclusion). It can thus handle maximum shape complexity, perimeter and area constraints.

Figure 7 reports the run time of our three algorithms on the IRIS Sepal length vs. Sepal Width dataset when introducing each constraint separately and varying the associated threshold (min. and max. perimeter are computed as they have the same behavior as min. and max. area, respectively). It also reports the number of generated patterns: The lower, the better. Some algorithms output more patterns as they cannot efficiently handle the constraints (such invalid patterns need to be removed during post-processing). As such, depending on the constraints the user is interested in, one algorithmmay be preferred to another.

Intervals vs. polygons. Our main motivation for introducing convex polygon patterns is to discover shapes with high density and area, and possibly with high class homogeneity (e.g., low Gini). Figure 8 (left) considers the IRIS dataset (Sepal length vs. Sepal Width). It presents the three most frequent polygons that have null Gini, and either 3 or 4 extreme points for a fair comparison: convex polygons better stick to the data without extremely over-fitting.

We also compare interval and polygon patterns in several datasets and plot their area, density and Gini. Figure 8 (center) plots all discovered patterns area (Y), Gini (X), and density (point diameter). It appears that convex polygons enable to find shapes with higher density, yet smaller area, over the same Gini range. Rectangles with high area are exactly those that we want to avoid for spatial data: they have high chances to enclose both zones of high and low density, and high impurity (high gini).

Sampling polygon patterns with MCTS. Our algorithms are clearly not scalable as their complexity depends on the number of polygons which can be very large. We propose to sample the pattern search space with a recent technique introduced by [Bosc et al., 2016] relying on Monte Carlo Tree Search [Browne et al., 2012]. Without entering into the details, MCTS requires a proper enumeration technique: we choose EXTREMEPOINTSENUM as it is generally the most efficient. MCTS iteratively draws a random pattern, following a path of EXTREMEPOINTSENUM: the best pattern quality measure is returned as a reward. This reward is used to update a memory (the Monte Carlo tree) and drives the search for the next iterations (thanks to the upper confidence bound, a formula that expresses a trade-off between exploration and exploitation of the search space). If given enough budget (maximum number of iterations allowed), MCTS will perform an exhaustive search. The quality of a pattern p is given by Q(p) = 2 ⋅ max{sup(p, i)} - ∣sup(p)∣ where sup(p, i) is made of the points of sup(p) belonging to the ith class. This choice favors polygons with high support and class homogeneity, but one could choose any other measure.

[Falher et al., 2015] propose several spatial datasets (cities) containing Foursquare users check-in places of different kinds ("College & university", "Art & Entertainement", ...). We randomly choose the city of Saint-Louis (Missouri, USA) containing 3464 points. Running our exhaustive algorithms on this dataset is impossible. The MCTS sampling however quickly returns patterns of high quality: Figure 8 (right) displays the average pattern quality measure of the best patterns (after a redundancy post-processing as done by [Bosc et al., 2016]): a plateau is reached with a maximum budget of 20K iterations (about 2 minutes). Note that each point corresponds to a different execution with a different budget. Figure 8 (right) presents the top-3 patterns, which are homogeneous zones with a large support. Designing a quality measure can be achieved in many ways (e.g., involving density).

6 Conclusion

In pattern mining, hyper-rectangles cannot always properly capture interesting areas although they are widely used. We formally defined convex polygon patterns by means of Formal Concept Analysis (FCA) and proposed three enumeration techniques. Although these algorithms do not scale, they serve as a basis for efficient pattern sampling approaches, which are shown to be scalable to very large pattern spaces and data. Tuning Monte-Carlo Tree Search (MCTS) sampling technique remains to be a subject of our further study. We also plan to extend our approach to other convex forms, like oriented rectangles, parallelograms, circles and ellipses. Moreover, we want to investigate how to enumerate this new type of patterns in high dimensions (more than two dimensions) as well as to apply this approach in machine learning settings (generating pattern-based classifiers).

Acknowledgments

This work has been partially supported by the European project GRAISearch (FP7-PEOPLE-2013-IAPP) and the ANRt French program. Sections 2 and 3 were written by Sergei O. Kuznetsov supported by the Russian Science Foundation under grant 17-11-01294 and performed at National Research University Higher School of Economics, Russia. The authors would like to warmly thank David Coeurjolly, Eric Gu´erin, Cl´ement Jamin, Mikhail Vyalyi and Adnene Belfodil for interesting discussions on computational geometry among others.