This work focuses on the application of Formal Concept Analysis and pattern structures in the problem of recommendation. We focus on the collaborative recommendation, where we give a suggestion to a new user based on a database of previous users. Here we can look the pattern in the database using two approaches: interval pattern structures or gradual pattern mining.
Formal Concept Analysis and Pattern Structures
Formal Concept Analysis (FCA) is a mathematical framework based on lattice
theory and used for classi cation, data analysis, and knowledge discovery,
introduced in [
De nition 1. A formal context is a triple (G; M; I), where G is a set of objects, M is a set of attributes, and I is a binary relation between G and M, i.e. I G M .
If an object g has an attribute m, then (g; m) 2 I. An example of a formal context is shown in Figure 1.
g1 g2 g3 g4
m1 m2 m3 m4 De nition 2. For a subset of objects A G, A0 is the set of attributes that are possessed by all objects in A, i.e.: A0 = fm 2 M j8g 2 A; (g; m) 2 Ig
Dually, for a subset of attributes B M , B0 is the set of objects that have all attributes in B, i.e.: B0 = fg 2 Gj8m 2 B; (g; m) 2 Ig
A formal concept is the pair (A; B), where A G and B M , and such that A0 = B and B0 = A. For such concept, A is called its extent and B is its intent.
From Figure 1, we see that fg3; g4g0 = fm2; m3g and fm2; m3g0 = fg3; g4g. Therefore, (fg3; g4g; fm2; m3g) is a formal concept. It should be noticed that the extent and the intent of a concept (A; B) are closed sets, i.e. A = A00 and B = B00. A formal concept (A; B) is a subconcept of a formal concept (C; D) { denoted by (A; B) (C; D) { if A C (or equivalently D B).
If (A; B) < (C; D) and there is no (E; F ) such that (A; B) < (E; F ) < (C; D), then (A; B) is a cover of (C; D). A concept lattice can be formed using the relation which de nes the partial order among concepts. For the context in Figure 1, the formal concepts and their corresponding lattice are shown in Figure 2 (extent and intent is below and above each concept respectively).
FCA is restricted to speci c datasets where each attribute is binary (e.g.
has only yes/no value). For more complex values (e.g. numbers, strings, trees,
graphs. . . ), FCA is then generalized into pattern structures [
De nition 3. A pattern structure is a triple (G; (D; u); ), where G is a set of objects, (D; u) is a complete meet-semilattice of descriptions, and : G ! D maps an object to a description.
The operator u is a similarity operator that returns the common elements to two descriptions. A description can be a set, a sequence, or other complex structure. In the binary case where descriptions are sets, u corresponds to set intersection (\), i.e. fa; b; cg u fa; b; dg = fa; bg, and v corresponds to subset inclusion ( ). The order between any two descriptions is given by the subsumption relation:
d1 v d2 () d1 u d2 = d1 De nition 4. The Galois connection for a pattern structure (G; (D; u); ) is de ned by:
A = gF2A (g); A G, d = fg 2 Gjd v (g)g; d 2 D.
A pattern concept is a pair (A; d), A G and d 2 D, where A = d and d = A.
Interval pattern structures (ip-structures) is one of possible extensions of FCA to study more complex descriptions. In ip-structures, the description of an object is an interval for each attribute. Consider the dataset given in Table 1 where G = fg1; g2; g3g is the set of objects and M = fm1; m2; m3; m4g is the set of attributes. Here the description of g1 is (g1) = h[5; 5]; [7; 7]; [6; 6]i, while the description of g4 is (g4) = h[4; 4]; [9; 9]; [8; 8]i.
The similarity operator u is the smallest interval containing both descriptions in each attribute. Therefore, (g1) u (g4) = h[4; 5]; [7; 9]; [6; 8]i. A description with larger interval is \subsumed by" (v) descriptions with smaller ones. The corresponding Galois connection is illustrated as follows: fg1; g4g = (g1) u (g4) = h[4; 5]; [7; 9]; [6; 8]i = fg1; g4g h[4; 5]; [7; 9]; [6; 8]i = fg 2 Gjh[4; 5]; [7; 9]; [6; 8]i v (g)g
Similar to formal concept, interval pattern concept (ip-concept) can also be
arranged in a lattice. The ip-concept lattice for Table 1 is illustrated in Figure 3.
For further background concerning ip-structures, see [
Consider again the matrix in Table 1. This numerical matrix can be transformed into a sign matrix as shown in Table 2. It contains information about the attribute comparison between any pair of objects. For example, pair (g1; g2) has `%' in m1 because according to this attribute, g1 < g2. Then, from this sign matrix, we can nd a coherent-sign-changes bicluster (for detailed explanation about biclustering, please refer to [6]). One of such bicluster is (fp3; p5; p6; p7; p8; p9; p10g; fm1; m2; m3g). This bicluster represent the pattern \the more/less m1, the less/more m2, the less/more m3 (the `=' can be regarded as either `&' or `%').
Pair m1 m2 m3 p1 = (g1; g2) % % & p2 = (g1; g3) & % & p3 = (g1; g4) & % % p4 = (g1; g5) = % & p5 = (g2; g3) & = % p6 = (g2; g4) & % % p7 = (g2; g5) & = % p8 = (g3; g4) = % % p9 = (g3; g5) % = = p10 = (g4; g5) % & & For explaining this approach, we will also use the example in Table 1 as user{ movie rating matrix. The user gt has rated the movie m1 and m2, and his/her rating for m3 is to be estimated. Therefore, from the sign matrix in Table 2, we have to nd the largest bicluster that contains m1 and m2.
Suppose that the largest bicluster is (fp3; p5; p6; p7; p8; p9; p10g; fm1; m2; m3g) that represents the pattern R1 \the more/less m1, the less/more m2, the less/more m3. Then, we have to compare the ratings from gt to the ratings from every other users, as shown in Table 3. Here the pairs that follow R1 are pa, pc, and pd, and the estimation of m3's rating from gt is in the range [6,8].
Pairs m1 m2 m3 estimation pa = (g1; gt) & = 6 pb = (g2; gt) & & { pc = (g3; gt) = & 5 pd = (g4; gt) = & 8 pe = (g5; gt) & & { Our research problem is to build a more sophisticated collaborative recommendation system for visitors in a museum. The problem is then formulated as rating prediction, i.e. predicting the given rating from a new user based on patterns studied from previous users. We focus on whether FCA and pattern structures are applicable to our problem. In literature, certain types of pattern structures have been studied to solve the task of recommendation. On the other hand, the applicability of interval pattern structures for this task is not yet explored, and this becomes our objective.
Finally, the proposed recommendation system is evaluated based on the accuracy of recommended items. Given that the CrossCult project doesn't have any substantial visitor{item rating dataset, the approaches will be tested on a movie dataset.
Currently, the authors work on gradual pattern mining using coherent-signchanges biclustering. In order to take into account the `=' sign, we will apply the interval pattern structures.
The thesis of the author is nanced by the Region Grand-Est and the European project CrossCult (http://www.crosscult.eu/), under the supervision of Amedeo Napoli, Chedy Rassi, and Miguel Couceiro. 6. Madeira, S.C., Oliveira, A.L.: Biclustering algorithms for biological data analysis: a survey. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 1(1), 24{45 (2004) 7. Subasic, P., Hirota, K.: Similarity rules and gradual rules for analogical and interpolative reasoning with imprecise data. Fuzzy Sets and Systems 96(1), 53{75 (1998)