Computing Similarity Dependencies with Pattern Structures

Abstract

Functional dependencies provide valuable knowledge on the relations between the attributes of a data table. To extend their use, generalizations have been proposed, among which purity and approximate dependencies. After discussing those generalizations, we provide an alternative definition, the similarity dependencies, to handle a similarity relation between data-values, hence un-crisping the basic definition of functional dependencies. This work is rooted in formal concept analysis, and we show that similarity dependencies can be easily characterized and computed with pattern structures.

Introduction

In the relational database model, functional dependencies (FDs) are among the most popular types of dependencies [ 19 ] since they indicate a functional relation between sets of attributes: the values of a set of attributes are determined by the values of another set of attributes. To handle errors and uncertainty in real-world data, alternatives exist. Approximate Dependencies [ 12 ] are FDs that hold in a part –which is user defined– of the database. Purity Dependencies [ 15 ] express the relationship on the relative impurity induced by two partitions of the table (generated by two sets of attributes). If the impurity is zero, we have a FD.

These generalizations do not necessarily capture the semantics of some patterns that may hold in a dataset. This motivates the definition of “Similarity Dependencies”, which can be seen as a generalization of Functional Dependencies, but un-crispring the basic definition of FDs: similar values of an attribute determine similar values of another attribute. Similarity has been considered for FDs under several terms, e.g. fuzzy FDs [ 3 ], matching dependencies [ 16 ], constraint generating dependencies [ 2 ]. Moreover, it is still an active topic of research in the database community [ 4,8,16,17 ].

The main objective of the present article is to give a characterization of similarity dependencies within FCA [ 10 ], thanks to the formalism of pattern structures [ 9 ]. Indeed, characterizing and computing FDs is strongly related to lattice theory and FCA. For example, the lattice characterization of a set of FDs is studied in [ 5,6,7 ], while a characterization within a formal context in c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 33{44, ISBN 978{2{7466{6566{8, Laboratory L3i, University of La Rochelle, 2013. Copying permitted only for private and academic purposes. FCA is proposed in [ 10 ]. The latter is based on a binarization, which is the transformation of the original set of data into a binary context. To overcome the burden usually induced by such a transformation, pattern structures [ 9 ] have emerged as a valuable alternative to avoid arbitrary transformations and complexity problems [ 1 ].

Accordingly, our purpose here is threefold. Firstly, we propose a definition of Similarity Dependencies, and secondly a formalization based on pattern structures in FCA, avoiding a transformation of data into a binary table. It follows that classical algorithms of FCA can be –almost directly– applied to compute similarity dependencies. This work is based on [ 1 ] where FDs are characterized thanks to pattern structures, and on [ 13 ] where similarity is introduced in pattern structures as a tolerance relation (reflexive, symmetric, but not transitive). Finally, we also report preliminary experiments showing the capabilities of the approach.

The paper is organized as follows. In Section 2 we introduce the definition of Functional, Approximate and Purity Dependencies. In Section 3 we propose a definition and a characterization of Similarity Dependencies with pattern structures. Finally, Section 4 reports preliminary experimental results showing the capabilities of our approach. 2 2.1

Notation

Functional, Approximate and Purity Dependencies

We deal with datasets which are sets of tuples. Let U be a set of attributes and Dom be a set of values (a domain). For the sake of simplicity, we assume that Dom is a numerical set. A tuple t is a function t : U 7→ Dom and then a table T is a set of tuples. Usually a table is presented as a matrix, as in the table of Example 1, where the set of tuples (or objects) is T = {t1, t2, t3, t4} and U = {a, b, c, d} is the set of attributes.

The functional notation allows to associate an attribute with its value. We define the functional notation of a tuple for a set of attributes X as follows, assuming that there exists a total ordering on U . Given a tuple t ∈ T and X = {x1, x2, . . . , xn} ⊆ U , we have:

t(X) = ht(x1), t(x2), . . . , t(xn)i In Example 1, we have t2({a, c}) = ht2(a), t2(c)i = h4, 4i. In this paper, the set notation is usually omitted and we write ab instead of {a, b}.

Example 1. This is an example of a table T = {t1, t2, t3, t4}, based on the set of attributes U = {a, b, c, d}.

id a b c d

We are also dealing with the set of partitions of a set. Let S be any arbitrary finite set, then, Part(S) is the set of all possible partitions that can be formed with S. The set of partitions of a set is a lattice [ 11 ]. We recall that partitions can also be considered as equivalence classes induced by an equivalence relation.

Now, we define the set of the “maximal subsets” of a set.

Definition 1. Given a finite base set S and X = {X1, X2, . . . , Xn} a set of subsets of S, a subset Xi is maximal in X if there does not exist any other subset Xj in X such that Xi ⊂ Xj .

Then XMax is the set of the maximal subsets of X.

For example, let S = {a, b, c} and X = {{a, b}, {b, c}, {a}, {b}}. Then X is a subset of ℘(S) the powerset of S, but not all elements of X are maximal subsets. Indeed, XMax = {{a, b}, {b, c}}.

Moreover, we define the function maxS which applies to a set of sets such as X and returns the set of maximal subsets of X, i.e. XMax.

Definition 2. Given a finite set S and a subset X = {X1, X2, . . . , Xn} of ℘(S), the function maxS returns the set XMax of maximal subsets of X: maxS (X) = XMax = {Xi ∈ X | @Xj ∈ X : Xi ⊂ Xj } 2.2

Functional Dependencies

We now introduce functional dependencies (FDs).

Definition 3 ([ 19 ]). Let T be a set of tuples (or a data table), and X, Y ⊆ U . A functional dependency (FD) X → Y holds in T if:

∀t, t0 ∈ T : t(X) = t0(X) ⇒ t(Y ) = t0(Y )

For example, the functional dependencies a → d and d → a hold in the table of Example 1, whereas the functional dependency a → c does not hold since t2(a) = t4(a) but t2(c) 6= t4(c).

There is an alternative way of considering Functional Dependencies using partitions of the set of tuples T . Taking a set of attributes X ⊆ U , we define the partition of tuples induced by this set as follows.

Definition 4. Let X ⊆ U be a set of attributes in a table T . Two tuples ti and tj in T are equivalent w.r.t. X when:

Then, the partition of T induced by X is a set of equivalence classes:

ti ∼ tj ⇐⇒ ti(X) = tj (X) ΠX (T ) = {c1, c2, . . . , cm}

For example, if we consider the table in Example 1, we have Πa(T ) = {{t1, t3}, {t2, t4}}.

Given X, ΠX (T ) is a partition or alternatively an equivalence relation. Then we have: 1. S ΠX (T ) = T , for all X ⊆ U . 2. ci ∩ cj = ∅ for all ci, cj ∈ ΠX (T ), i 6= j.

The classes in a partition induced by X are disjoint and they cover all the tuples in T . The set of all partitions of a set T is Part(T ). We can also notice that the set of partitions of any set Part(T ) induces an ordering relation ≤: ∀Pi, Pj ∈ Part(T ) : Pi ≤ Pj ⇐⇒ ∀c ∈ Pi : ∃c0 ∈ Pj : c ⊆ c0

For example: {{t1}, {t2}, {t3, t4}} ≤ {{t1}, {t2, t3, t4}}. According to the partitions induced by a set of attributes, we have an alternative way of defining the necessary and sufficient conditions for a functional dependency to hold: Proposition 1 ([ 12 ]). A functional dependency X → Y holds in T if and only if ΠY (T ) ≤ ΠX (T ).

Again, taking the table in Example 1, we have that a → d holds and that Πd ≤ Πa since Πa(T ) = {{t1, t3}, {t2, t4}} and Πd(T ) = {{t1, t3}, {t2, t4}} (actually d → a holds too). 2.3

Purity and Approximate Dependencies Approximate Dependencies [ 12 ]. In a table, Example 2. This table is an exthere may be some tuples that prevent a func- cpeerrpatturoef AthrechiAvveer4agferomDaTilyheTUemni-tional dependency from holding. Those tuples versity of Dayton, that shows the can be seen as exceptions (or errors) for that de- fmeroenntthcaitvieersa.ge temperatures for difpendency. Removing such tuples allows the dependency to exist: then a threshold can be set to id Month Year Av. Temp. City define a set of “approximate dependencies” hold- t1 1 1995 36.4 Milan ing in a table. For example, a threshold of 10% tt32 51 11999966 6333..18 MRoilmane means that all functional dependencies holding t4 5 1997 59.6 Rome after removing up to 10% of the tuples of a ta- t5 1 1998 41.4 Dallas ble are valid approximate dependencies. The set tt67 15 11999996 4864..85 HDoaulsltaosn of tuples to be removed for validating a func- t8 5 1998 80.2 Houston tional dependency does not need to be the same for each approximate dependency. Considering in Example 2 the dependency M onth → Av.T emp, we can check that 6 tuples should be removed before verifying the dependency: we keep only one tuple for Month 1 and one tuple for Month 5 (actually just as if we remove “duplicates”). Then, if the threshold is equal to or larger than 75%, M onth → Av.T emp is a valid Approximate Dependency.

Purity Dependencies [ 15 ] are a generalization of the relationship between partitions induced by the left-hand side and right-hand side of a functional dependency. These dependencies are based on the relative impurity measure of two partitions. In order to compute this impurity measure, we need a concave and subadditive function defined on the interval [ 0, 1 ] (for example, the binary entropy function). The intuition about this measure is that it computes how much those partitions disagree, i.e. how far two partitions π and σ are from fulfilling the relation π ≤ σ. If the impurity measure is zero (or close to zero), then π ≤ σ.

For example, the impurity measure (details on this measure are given in [ 14 ]) of partition {{1, 2, 3}, {4, 5}} w.r.t. partition {{1, 2}, {3, 4, 5}} is 5.6, whereas the impurity measure of partition {{1, 3}, {2, 5}, {4}} w.r.t. partition {{1, 2}, {3, 4, 5}} is 8.2. In the first pair of partitions, only tuple 3 is misplaced, i.e. moving 3 from one partition to another leads to the the same partitions, whereas in the second example, the number of misplaced elements is larger (2, 3, and 4 should be moved).

An important feature of this measure is that if a partition is finer than another, then, their relative impurity measure is exactly 0. This implies that a purity dependency X → Y holds if and only if the relative impurity of ΠX (T ) w.r.t. ΠY (T ) is below a user-defined threshold. Therefore, if ΠY (T ) ≤ ΠX (T ), a functional dependency is a valid purity dependency, regardless of the threshold.

For example, we consider all the possible dependencies having the attribute Average Temperature in their right-hand side. The purpose of this choice is to find out which attributes determine the values of the average temperature (Av. Temp.) in Example 2. Considering Approximate Dependencies, we introduce the two metrics # Tuples and Percentage: # Tuples denotes the minimal number of tuples that must be removed from the dataset for allowing the dependency to hold, and Percentage denotes the percentage that # Tuples represents for the whole dataset. For example, the Approximate Dependency M onth → Av.T emp holds when we remove at least 6 (well-chosen) tuples, which represent 75% of the whole dataset.

Example 3. Dependencies with Average Temperature in their right-hand and the metrics related to Approximate and Purity Dependencies. #Tuples Percentage Purity 6 75% 12.98 1 12.5% 4.0 4 50% 4.0 3 37.5% 8.26 0 0% 0.0 4 50% 4.0

As for the purity measure, we use the measure of relative entropy of two partitions described in [ 14 ]. If we examine the dependency M onth → Av.T emp, we should the relative entropy of the partitions induced by Month and Av. Temp., which are, respectively: ΠMonth = {{t1, t2, t5, t6}, {t3, t4, t7, t8}} ΠAv.T emp. = {{t1}, {t2}, {t3}, {t4}, {t5}, {t6}, {t7}, {t8}}

Then, the relative entropy of ΠMonth and ΠAv.T emp. is 12.98, i.e. the largest of the conditional entropies that are computed. Actually the number of tuples that need to be reallocated for ΠAv.T emp. ≤ ΠMonth is significantly large. It is also significant that the number of tuples that need to be removed for the dependency Y ear, City → Av.T emp to hold is zero and that the relative entropy of ΠY ear,City and ΠAv.T emp. is zero as well. The Functional Dependency Y ear, City → Av.T emp holds because there is no pair of tuples ti, tj such that ti(Y ear, City) = tj (Av.T emp.), i.e. there is no need to remove any tuple to verify this dependency. In addition the relative entropy of ΠY ear,City and ΠAv.T emp. is zero, because the partitions induced by both sides, ΠY ear,City and ΠAv.T emp are exactly the same: {{t1}, {t2}, {t3}, {t4}, {t5}, {t6}, {t7}, {t8}}. Therefore, the relation ΠY ear,City ≤ ΠAv.T emp holds, i.e. the relative entropy is zero and this dependency trivially holds.

Yet, the intuition about this dataset is that the “Average Temperature” depends, to some extent, on the location and the month, i.e. given a city and a month, we should be able to predict the average temperature. But this intuitive relationship is somehow difficult to deduce with Approximate and Purity Dependencies. For example, the metrics for the dependency M onth, City → Av.T emp indicate that 4 tuples must be removed (50% of the dataset) for checking this dependency, or alternatively, the relative entropy of the partitions ΠMonth,City and ΠAv.T emp is 4.0. Considering the number of tuples, removing 50% of the whole dataset is a lot, especially if the intuition tells that this dependency should hold. Considering the entropy rate, the smallest entropy rate is zero and the largest computed rate is 12.98. Thus, it seems difficult to deduce the right threshold in each case.

Instead of considering measures that deal with the sets of tuples as a whole, dependencies could be directly related with the notion of “similarity”: if two tuples have similar values for the attributes Month and City, then they should have a similar value for the attribute Av. Temp. This can be interpreted as follows: if two cities are close enough and the corresponding months are also close enough, then the average temperature in the cities should be close enough or “similar” as well. In such a context, “having similar values” depends on the type of the attributes. For temperatures it mean that the absolute difference of the values is less than a given threshold. For months, it could mean that they are adjacent. For cities, it could mean that their locations are close enough.

Such a kind of dependency would provide more control and a more intuitive explanation of the relations existing between attributes. 3

Similarity Dependencies

First, we define a tolerance relation in a set S:

Definition 5. θ ⊆ S × S is a tolerance relation if: 1. ∀si ∈ S : siθsi (reflexivity) 2. ∀si, sj ∈ S : siθsj ⇐⇒ sj θsi (symmetry) A tolerance relation is not necessarily transitive and induces blocks of tolerance: Definition 6. Given a set S, a subset K ⊆ S, and a tolerance relation θ ⊆ S×S, K is a block of tolerance of θ if: 1. ∀x, y ∈ K : xθy (pairwise correspondence) 2. ∀z 6∈ K, ∃u ∈ K : ¬(zθu) (maximality)

All elements in a tolerance block are in pairwise correspondence, and the block is maximal with respect to the relation θ. The set of all tolerance blocks induced by a tolerance relation θ on the set S is denoted by S/θ (by analogy with the notation of equivalence classes). S/θ is a set of maximal subsets of S and as such, S/θ ∈ ℘(℘(S)). Thus we have: Property 1. ∀Ki, Kj ∈ S/θ : Ki * Kj and Kj * Ki for all i 6= j

Then, we define a partial ordering on the set of all possible tolerance relations in a set S as follows:

Definition 7. Let θ1 and θ2 two tolerance relations in the set S. We say that

θ1 ≤ θ2 if and only if ∀Ki ∈ S/θ1 : ∃Kj ∈ S/θ2 : Ki ⊆ Kj

This relation is a partial ordering and induces a lattice where the meet and join operations of two tolerance relations θ1 and θ2, or, equivalently, on the sets of blocks of tolerance of θ1 and θ2 are:

Definition 8. Let θ1 and θ2 two tolerance relations in the set S.

θ1 ∧ θ2 = θ1 ∩ θ2 = maxS ({ki ∩ kj | ki ∈ S/θ1, kj ∈ S/θ2}) θ1 ∨ θ2 = θ1 ∪ θ2 = maxS (S/θ1 ∪ S/θ2)

The meet θ1 ∧ θ2 is the set of pairwise intersections of all blocks in S/θ1 and S/θ2, and then removing intersections that are not maximal. The join is simpler as it consists in simply joining the blocks of tolerance in S/θ1 and S/θ2 and then removing the unions that are not maximal.

An example of a tolerance relation is the similarity that can be defined within a set of integer values as follows. Given two integer values v1, v2 and a threshold (user-defined): v1θv2 ⇐⇒ |v1 − v2| ≤ . For example, when S = {1, 2, 3, 4, 5} and = 2, then S/θ = {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}}. S/θ is not a partition as transitivity does not apply.

We now come back to the set of tuples T and the set of attributes M . For each attribute m ∈ M , we define a tolerance relation on the values of that attribute: θm. The set of tolerance blocks induced by the tolerance relation of the attribute m is T /θm. All the tuples in a tolerance block K ∈ T /θm are similar one to the other according to their values w;r.t. the attribute m.

Example 4. Let us define a tolerance relation on an attribute m ∈ {a, b, c, d} as follows: tiθmtj ⇐⇒ |ti(m) − tj (m)| ≤ .

Now, assuming that = 1 in example 1, we have:

T /θa = {{t1, t3}, {t2, t4}}, T /θb = {{t1, t2, t4}, {t3}}, T /θc = {{t1, t2, t3}, {t4}} and S/θd = {{t1, t3}, {t2, t4}}.

We can also extend this definition to sets of attributes. Given X ⊆ U , the similarity relation θX is defined as follows:

(ti, tj) ∈ θX ⇐⇒ ∀m ∈ X : (ti, tj) ∈ θm

Two tuples are similar w.r.t. a set of attributes X if and only if they are similar w.r.t. each attributes in X. We now can define a similarity dependency : Definition 9. Let X, Y ⊆ U : X → Y is a similarity dependency iff: ∀ti, tj ∈ T : tiθX tj ⇒ tiθY tj

In the case of a functional dependency, X → Y holds if and only if, for each pair of tuples having the same value w.r.t. the attributes in X, then, they have the same value w.r.t. the attributes in Y .

In the case of a similarity dependency, X → Y holds if and only if, for each pair of tuples having similar values w.r.t. the attributes in X, then, they have similar values w.r.t. the attributes in Y .

Example 5. We revisit the table in Example 4 and we define the tolerance relation: tiθmtj ⇐⇒ |ti(m)−tj(m)| ≤ 2. Then the following similarity dependencies hold: a → d, ab → d, abc → d, ac → d, b → d, bc → d, c → d.

It is interesting to notice that b → d is a similarity dependency but not a functional dependency, as t1(b) = t2(b) and t1(d) 6= t2(d). Because of the same pair of tuples, the similarity dependency bcd → a does not hold, as t1θbcdt2 but we do not have t1θat2, since |t1(a) − t2(a)| 2.

By contrast, the functional dependency bcd → a holds because there is no pair of tuples ti, tj such that ti(bcd) = tj(bcd).

Example 6. Going back to example 2, let us compute the Similarity Dependencies that hold and that have the attribute Av. Temp. in their right-hand side).

Holds N N Y

N N N

The only similarity dependency that holds is M onth, City → Av.T emp, using the following similarity measures for each attribute: x θMonth y ⇐⇒ |x − y| ≤ 0, x θY ear y ⇐⇒ |x − y| ≤ 0, x θCity y ⇐⇒ distance(x, y) ≤ 500 and x θAv.T emp y ⇐⇒ |x − y| ≤ 10.

The similarity imposes that the month and year must be the same, whereas the distance between cities should be less than 500 kilometers and the difference between average temperatures should be less than 10 degrees (all these values are of course arbitrary).

In particular, considering the tuples t1, t2: t1θMonth,Cityt2 since t1(M onth) = t2(M onth) = h 1 i and t1(City) = t2(City) = h M ilan i. From the other side, we have that t1θAv.T emp.t2 since |36.4 − 33.8| ≤ 10.

Computing Similarity Dependencies with Pattern Structures A pattern structure allows one to apply FCA directly on non-binary data [ 9 ]. Formally, let G be a set of objects, let (D, u) be a meet-semi-lattice of potential object descriptions and let δ : G −→ D be a mapping associating each object with its description. Then (G, (D, u), δ) is a pattern structure. Elements of D are patterns and are ordered thanks to a subsumption relation v: ∀c, d ∈ D, c v d ⇐⇒ c u d = c. A pattern structure (G, (D, u), δ) is based on two derivation operators (·) . For A ⊆ G and d ∈ (D, u):

A = l δ(g) g∈A d = {g ∈ G|d v δ(g)}.

These operators form a Galois connection between (℘(G), ⊆) and (D, u). Pattern concepts of (G, (D, u), δ) are pairs of the form (A, d), A ⊆ G, d ∈ (D, u), such that A = d and A = d . For a pattern concept (A, d), d is a pattern intent and is the common description of all objects in A, the pattern extent. When partially ordered by (A1, d1) ≤ (A2, d2) ⇔ A1 ⊆ A2 (⇔ d2 v d1), the set of all concepts forms a complete lattice called pattern concept lattice.

Thanks to the formalism of pattern structures, similarity dependencies can be characterized (and computed) in an elegant manner. Firstly, the description of an attribute m ∈ M is given by δ(m) = G/θm which is given by the set of tolerance blocks w.r.t. θm and G = T . As tolerance relations can be ordered as presented and discussed in Definitions 7 and 8, then descriptions can be ordered within a lattice.

Then, a dataset can be represented as a pattern structure (M, (D, u), δ) where M is the set of original attributes, and (D, u) is the set of sets of blocks of tolerance over G provided with the meet operation defined in Definition 8.

An example of concept formation is given as follows. Starting from the set {a, c} ⊆ M and assuming that tiθmtj ⇐⇒ |ti(m)−tj (m)| ≤ 2 for all attributes: {a, c} = δ(a) u δ(c) = {{t1, t3}, {t2, t4}} u {{t1, t2, t3}, {t4}}

= {{t1, t3}, {t2}, {t4}} {{t1, t3}, {t2}, {t4}}

= {m ∈ M |{{t1, t3}, {t2}, {t4}} v δ(m)} = {a, c}

This pattern concept lattice allows us to characterize all similarity dependencies holding in M : Proposition 2. A similarity dependency X → Y holds in a table T if and only if: {X} = {XY } in the pattern structure (M, (D, u), δ).

Proof. First of all, we notice that (t, t0) ∈ {X} if and only if t(X)θX t0(X), since (t, t0) ∈ {X} if and only if ∀x ∈ X : t(x)θxt0(x), if and only if t(X)θX t0(X). We also notice that {X, Y } ⊆ {X} . (⇒) We prove that if X → Y holds in T , then, {X} = {X, Y } , that is, {X} ⊆ {X, Y } . We take an arbitrary pair (t, t0) ∈ {X} , that is: t(X)θX t0(X). Since X → Y holds, it implies that t(XY )θXY t0(XY ), and this implies that (t, t0) ∈ {X, Y } . (⇐) We take an arbitrary pair t, t0 ∈ T such that t(X)θX t0(X). Therefore, we have that (t, t0) ∈ {X} , and by hypothesis, (t, t0) ∈ {XY } , that is: t(XY )θXY t0(XY ). Since this is for all pairs t, t0 ∈ T such that t(X) = t0(X), this implies that X → Y holds in T . 4

Experiments

Dataset description. Electronic sport denotes the extreme practice of video games where so-called cyber-athletes compete in world-wide tournaments. As for any sport, such professionals are surrounded by sponsors and practice within professional teams. These professional games are even broadcast by commentators over specialized TV channels [ 18 ]. StarCraft II (Blizzard Entertainment) is the most competitive video game. Since e-sport is a digital entertainment, one can easily find game statistics and recording in great numbers on the Web. We list more than 209, 000 games between two opponents and their associated statistics (attributes). For each game, we derive two tuples (one for each of the players involved). Each player in a game (tuple) is described by 31 attributes such as his faction, the result, and several indicators of his game play.

Experimental settings. The final dataset has about 400, 000 tuples described by 31 attributes with different domain types (Boolean, qualitative, and numerical). For attributes with Boolean or non-ordered qualitative domains, the similarity parameters are set to 0 as for classical FDs, since we do not have similarity constraints between their values. For the others, parameters are set by an expert of the domain, helped with the distribution of that attribute values. Thanks to the genericity of pattern structures, we slightly modified the very simplistic Java version of CloseByOne used in [ 1 ] for extracting classical FDs. The only modification lies in building the descriptions, i.e. producing tolerance blocks instead of partitions over the set of objects. We experimented on 1.8GHz and 4GB of RAM machines.

Preliminary results. We build first several different sub-datasets with randomly chosen set of tuples and different subsets of attributes. We report execution times for extracting pattern concepts (and their count) to characterize functional dependencies and similarity dependencies for three datasets in Figure 1. We also report the average number of tolerance classes of each attribute (that allows to build their description). In Figure 1 (a), the dataset is composed of qualitative and not comparable attributes only. Thus, we set the similarity parameters to 0 and observe that extracting FDs and SDs requires the same amount of time and returns the same concepts (since setting the similarity parameter to 0 leads to partitions). Naturally, the number of tolerance blocks is high, corresponding to the cardinality of attribute domains. We added more attributes, among which 5 numerical, and introduce the similarity parameters, see Figure 1 (b) and (c). The number of tolerance blocks is still high since it is an average for all attributes, and attribute domains are very dense. We notice that there are more concepts to characterize SDs than FDs. This is due to our choice of similarity parameters. Finally, we face memory issues when computing pattern concepts for SDs, when the algorithms terminates for FDs. This is due to our pattern implementations, i.e. how a pattern is represented in the memory. We used striped partitions, i.e. not store any part of size 1, which can strongly reduce the pattern size in memory. For FDs, this experimentally happens more often than for SDs, due to the relaxation of the equality constraint. We need to investigate other pattern implementations.

100000 10000 t oun 1000 C 100 10 100000 t 10000 n u o C 1000 100 10 0 )( s e m it

100000 t 10000 n u o C 1000

100 100 250 500 0100 5000 7500 00001 50000 (a) 8 attributes 800 700 600 500 ) 400 (se 300 t m i 200 100 0 100 250 500 0100 5000 7500 00001 50000 (c) 17 attributes We discussed how Functional, Approximate and Purity Dependencies may not capture some relationships among attributes that intuitively exist in a dataset. We presented alternatively Similarity Dependencies, to express relationships between attributes based on a similarity measure that depends on the semantics of each attribute. We showed that similarity dependencies are easily characterized in FCA with pattern structures and we gave a preliminary experimental study.

Future work is in concern with a deeper investigation of the best in-memory pattern representations for fast and scalable computation, the introduction of a minimal support as well as a qualitative evaluation of similarity dependencies. Acknowledgments. This research work has been supported by the Spanish Ministry of Education and Science (project TIN2008-06582-C03-01), EU PASCAL2 Network of Excellence, and by the Generalitat de Catalunya (2009-SGR-980 and 2009-SGR-1428) and AGAUR (grant 2010PIV00057).

References

1. J. Baixeries , M. Kaytoue , and A. Napoli . Computing functional dependencies with pattern structures . In L. Szathmary and U. Priss, editors, CLA , volume 972 of CEUR Workshop Proceedings , pages 175 - 186 . CEUR-WS.org, 2012 .

2. M. Baudinet , J. Chomicki , and P. Wolper . Constraint-generating dependencies . J. Comput. Syst. Sci. , 59 ( 1 ): 94 - 115 , 1999 .

3. R. Belohla ´vek and V. Vychodil. Data tables with similarity relations: Functional dependencies, complete rules and non-redundant bases . In M.- L. Lee , K.-L. Tan , and V. Wuwongse, editors, DASFAA , volume 3882 of Lecture Notes in Computer Science, pages 644 - 658 . Springer, 2006 .

4. L. Bertossi , S. Kolahi , and L. V. S. Lakshmanan . Data cleaning and query answering with matching dependencies and matching functions . In Proceedings of the 14th International Conference on Database Theory, ICDT '11 , pages 268 - 279 , New York, NY, USA, 2011 . ACM.

5. N. Caspard and B. Monjardet . The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey . Discrete Applied Mathematics , 127 ( 2 ): 241 - 269 , 2003 .

6. A. Day . The lattice theory of fonctionnal dependencies and normal decompositions . International Journal of Algebra and Computation , 02 ( 04 ): 409 - 431 , 1992 .

7. J. Demetrovics , G. Hencsey , L. Libkin , and I. B. Muchnik . Normal form relation schemes: A new characterization . Acta Cybern. , 10 ( 3 ): 141 - 153 , 1992 .

8. W. Fan , H. Gao , X. Jia , J. Li , and S. Ma . Dynamic constraints for record matching . The VLDB Journal , 20 ( 4 ): 495 - 520 , Aug. 2011 .

9. B. Ganter and S. O. Kuznetsov . Pattern structures and their projections . In H. S. Delugach and G. Stumme, editors, Conceptual Structures: Broadening the Base, Proceedings of the 9th International Conference on Conceptual Structures (ICCS 2001 ), LNCS 2120 , pages 129 - 142 . Springer, 2001 .

10. B. Ganter and R. Wille . Formal Concept Analysis . Springer, Berlin, 1999 .

11. G. Graetzer, B. Davey , R. Freese , B. Ganter , M. Greferath , P. Jipsen , H. Priestley , H. Rose , E. Schmidt , S. Schmidt , F. Wehrung , and R. Wille . General Lattice Theory. Freeman , San Francisco, CA, 1971 .

12. Y. Huhtala , J. Ka¨rkka¨inen, P. Porkka, and H. Toivonen . Tane: An efficient algorithm for discovering functional and approximate dependencies . Computer Journal , 42 ( 2 ): 100 - 111 , 1999 .

13. M. Kaytoue , Z. Assaghir , A. Napoli , and S. O. Kuznetsov . Embedding tolerance relations in formal concept analysis: an application in information fusion . In J. Huang, N. Koudas , G. J. F. Jones , X. Wu , K. Collins-Thompson , and A . An, editors, CIKM , pages 1689 - 1692 . ACM, 2010 .

14. D. Simovici and S. Jaroszewicz . An axiomatization of partition entropy . Information Theory , IEEE Transactions on, 48 ( 7 ): 2138 - 2142 , 2002 .

15. D. A. Simovici , D. Cristofor , and L. Cristofor . Impurity measures in databases . Acta Inf. , 38 ( 5 ): 307 - 324 , 2002 .

16. S. Song and L. Chen . Efficient discovery of similarity constraints for matching dependencies . Data & Knowledge Engineering , ( 0 ):-, 2013 . (in press).

17. S. Song , L. Chen , and P. S. Yu . Comparable dependencies over heterogeneous data . The VLDB Journal , 22 ( 2 ): 253 - 274 , Apr. 2013 .

18. T. L. Taylor . Raising the Stakes: E-Sports and the Professionalization of Computer Gaming . MIT Press, 2012 .

19. J. Ullman . Principles of Database Systems and Knowledge-Based Systems, volumes 1-2 . Computer Science Press, Rockville (MD), USA, 1989 .