CrossCult (http://www.crosscult.eu) is a European project whose idea is to support the emergence of a European cultural heritage by allowing visitors in different cultural sites (e.g. museum, historic city, archaeological site) to improve the quality of their visit by using adapted computer-based devices and to consider the visit at a European level. Such improvement can be accomplished by studying, among others, the possibility to build a dynamic recommendation system. This system should be able to produce a relevant suggestion on which part of a cultural site may be interesting for a specific visitor. Here, our objective is to study a dynamic recommendation system for visitors in a museum. Given a new visitor V n , the task is to suggest a museum item that may be interesting for him/her. Based on how a suggestion is made to a new visitor V n , a recommendation system can be classified into one of the three following categories [1]:
-Content-based recommendations: The system makes a suggestion based only on the previous visited items of V n . For example, if V n visited mostly the items from prehistoric era, then the system recommends another item from that era. -Collaborative recommendations: The system looks for previous users who have similar interest to V n , and makes a suggestion based on their visited items. For example, if many of V n 's similar users have visited item I, then the system recommends this item. -Hybrid approaches: The combination of content-based and collaborative approaches.
In this work, we explore the second category (collaborative recommendation) for museum visitors.
2 State-of-the-Art
Formal Concept Analysis (FCA) is a mathematical framework based on lattice theory and used for classification, data analysis, and knowledge discovery, introduced in [4]. From a formal context, FCA detects all formal concepts, who can be arranged in a concept lattice. If an object g has an attribute m, then (g, m) ∈ I. An example of a formal context is shown in Figure 1. From Figure 1, we see that {g 3 , g 4 } = {m 2 , m 3 } and {m 2 , m 3 } = {g 3 , g 4 }. Therefore, ({g 3 , g 4 }, {m 2 , m 3 }) 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 = A and
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 defines 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 specific 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 [3]. Definition 3. A pattern structure is a triple (G, (D, ), δ), where G is a set of objects, (D, ) is a complete meet-semilattice of descriptions, and δ : G → D maps an object to a description.
The operator 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, corresponds to set intersection (∩), i.e. {a, b, c} {a, b, d} = {a, b}, and corresponds to subset inclusion (⊆). The order between any two descriptions is given by the subsumption relation:
Definition 4. The Galois connection for a pattern structure (G, (D, ), δ) is defined by: 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 = {g 1 , g 2 , g 3 } is the set of objects and M = {m 1 , m 2 , m 3 , m 4 } is the set of attributes. Here the description of g 1 is δ(g 1 ) = [5,5], [7,7], [6,6] , while the description of g 4 is δ(g 4 ) = [4,4], [9, 9], [8,8] .
The similarity operator is the smallest interval containing both descriptions in each attribute. Therefore, δ(g 1 ) δ(g 4 ) = [4,5], [7,9], [6,8] . A description with larger interval is "subsumed by" ( ) descriptions with smaller ones. The corresponding Galois connection is illustrated as follows: 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 [5]. Fig. 3. Lattice of interval pattern concept for g1, g2, and g3 in Table 1.
In a numerical dataset, a gradual pattern is a pattern that is observed from at least two objects across at least two attributes. Usually this pattern is described as a correlation between two (or more) attributes: "the more/less A corresponds to the more/less B". This type of pattern was originally proposed in [2] and studied by [7] as an instrument to aid fuzzy controllers.
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 (g 1 , g 2 ) has ' ' in m 1 because according to this attribute, g 1 < g 2 . Then, from this sign matrix, we can find a coherent-sign-changes bicluster (for detailed explanation about biclustering, please refer to [6]). One of such bicluster is ({p 3 , p 5 , p 6 , p 7 , p 8 , p 9 , p 10 }, {m 1 , m 2 , m 3 }). This bicluster represent the pattern "the more/less m 1 , the less/more m 2 , the less/more m 3 (the '=' can be regarded as either ' ' or ' ').
Table 2. Sign matrix for Table 1.
3 Proposed Approach
Table 1 can be regarded as a rating matrix, where G is the set of users and M is the set of movies. Here we have a target user g t for which we will estimate his/her rating for movie m 3 . Based on this estimation, we can decide whether we recommend m 3 to g t .
To do that we can traverse the lattice in Figure 3 from the top node. Here we search the concept(s) with the most specific interval that contains m 1 : 4 and m 2 : 7. We will arrive at concept ({g 1 , g 3 , g 5 }, [4,5], [7,8], [5,6] ). Therefore, we can estimate that g t will likely give a rating between 5 and 6 for m 3 .
For explaining this approach, we will also use the example in Table 1 as usermovie rating matrix. The user g t has rated the movie m 1 and m 2 , and his/her rating for m 3 is to be estimated. Therefore, from the sign matrix in Table 2, we have to find the largest bicluster that contains m 1 and m 2 .
Suppose that the largest bicluster is ({p 3 , p 5 , p 6 , p 7 , p 8 , p 9 , p 10 }, {m 1 , m 2 , m 3 }) that represents the pattern R 1 "the more/less m 1 , the less/more m 2 , the less/more m 3 . Then, we have to compare the ratings from g t to the ratings from every other users, as shown in Table 3. Here the pairs that follow R 1 are p a , p c , and p d , and the estimation of m 3 's rating from g t is in the range [6,8].
Comparison of gt and every other users in Table 1.
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 financed by the Région Grand-Est and the European project CrossCult (http://www.crosscult.eu/), under the supervision of Amedeo Napoli, Chedy Raïssi, and Miguel Couceiro.