This paper addresses the long-term problem of defining a subjective interestingness measure for BI exploration. Such a measure involves prior modeling of the belief of the user. The complexity of this problem lies in the impossibility to ask the user about the degree of belief in each element composing their knowledge prior to the writing of a query. To this aim, we propose to automatically infer this user belief based on the user's past interactions over a data cube, the cube schema and other users' past activities. We express the belief under the form of a probability distribution over all the query parts potentially accessible to the user. This distribution is learned using a random walk approach, and more specifically an adapted topic-specific PageRank. The resulting belief provides the foundations for the definition of subjective interestingness measures that can be use to improve the user's experience in their explorations. In the absence of ground truth for user belief, we simulate in our tests diferent users and their belief distributions with artificial cube explorations and evaluate our proposal based on qualitative evaluation. We finally propose a preliminary usage of our belief estimation in the context of query recommendation.
• Information systems → Relevance assessment; Data access methods; Environment-specific retrieval ; BI exploration, user belief, PageRank
Business intelligence (BI) exploration can be seen as an iterative
process that involves expressing and executing queries over
multidimensional data (or cubes) and analyzing their results, to ask
more focused queries to reach a state of knowledge that allows
to answer a business question at hand. This complex task can
become tedious, and for this reason, several approaches have
been proposed to facilitate the exploration by pre-fetching data
[
Ideally, such systems should be able to measure to which
extent a query would be interesting for a given user prior to any
recommendation. Indeed, as illustrated in [
Following the idea of subjective interestingness measures
initiated and developed by De Bie [
It is therefore crucial, before reaching the definition of such an interestingness measure for BI, to be able to transcribe with an appropriate information-theoretic formalism the prior user knowledge, also called belief, on the data. De Bie proposes to represent this belief as a probability distribution over the set of data. However, it is clearly not possible to explicitly ask a user about the degree of belief in each element composing her knowledge prior to each query, let alone identifying on which element of knowledge expressing this probability distribution.
This motivates the investigation of approaches for automatically estimating the user’s belief based on their implicit feedback. Let us now consider the following example to illustrate the dificulty of estimating probabilities for the belief.
Example. Let us consider the explorative session over the Star
Schema Benchmark schema [
A naive solution would be to use the set of all possible query context of data exploration. Section 3 introduces the concepts parts as the set of data and to express the belief based on the used in our approach: a simplified definition of a query part, frequency of each query part in the past user history. From the subjective interestingness and topic-specific PageRank. Section session in Figure 1 it is possible to compute the number of occur- 4 presents our modeling of past usage and database schema as rences of each query part (for instance, SUM REVENUE appears 3 topology and user profile for discovering user beliefs. Finally times, CUSTOMER.CITY 2 times, while SUPPLIER.REGION=AMERICA Sections 5 and 6 present our experiments on CubeLoad generated appears only once, etc.). sessions while Section 7 discusses related work and Section 8
However, this simple representation raises major problems: concludes and draws perspectives. ifrst, the vector of user belief computed from the number of occurrences will mostly contain zero values because the majority 2 USER BELIEF IN DATA EXPLORATION of users will concentrate their exploration to a certain region of the data cube. Second, this belief would not give any probability to query parts such as CUSTOMER.NATION=CANADA, while if user knows about AMERICA and USA, she is likely to have a basic knowledge about sibling countries to USA in the dimension CUSTOMER.NATION. Finally, it may also be taken advantage of other users’ former explorations, as a proxy of what the current user might find interesting.
This example stresses the need for an approach to define the
belief based on the users’ past activity, as well as an information
about how knowledge is structured, which, in the case of the
data cube, can be found in the cube schema. We note that while
previous works already investigated surprising data in cubes (see
e.g., [
As a first step in this direction, this paper proposes tracking
user belief in BI interactions for measuring subjective
interestingness of a set of queries executed on a data cube. We propose
to build a model of the user’s past explorations that will then be
used to infer the belief of the user about the query parts being
useful for the exploration. However, contrary to the context of
pattern mining [
We define the belief of a user as a probability distribution over the
set of query parts coming from the log of past activities and the
cube schema. We propose to learn this probability distribution
with a modified topic-specific PageRank algorithm, where the
topology matrix is based on previous usage and the schema of
the cube, and where the teleportation matrix corresponds to a
specific user model. Finally, in order to evaluate our approach,
we will take advantage of the artificial exploration generator
CubeLoad [
In our vision, illustrated in Figure 2, human remain in the loop of data exploration, i.e., the exploration is not done automatically, but we aim at making it less tedious. All users, naive or expert, willing to explore a dataset, express their information need through an exploration assistant. This assistant is left with the task of deriving from the user’s need the actual queries to evaluate over the data source. This exploration assistant communicates with a belief processor that is responsible for the maintenance of the user’s profile, i.e., a model of that user, in the sense that it includes an estimation of the actual belief unexpressed by the user. This belief is manifold and concerns e.g., hypotheses on the value of the data, the filters to use, how the answer should be presented, etc. The belief processor activates a series of subjective interestingness measures that drives the query generator for deriving and recommending the most interesting queries for this user, in the sense that they produce relevant, unexpected, diverse answers, avoiding undesirable artifacts such as biased or false discoveries, the so-called cognitive bubble trap, etc. These answers and recommendations are packaged (e.g., re-ranked, graphically represented) by the storytelling processor before being displayed to the user and sent to the belief processor for profile updating.
Notably, thanks to the belief processor, once enough diverse users are modeled, the storytelling processor may cope with the cold start problem of generating recommendation for unknown users (the future user of Figure 2).
The work presented in this paper is a preliminary step in the implementation of this vision. We first concentrate on cube exploration, and on expressing the belief in terms of a probability distribution over the query parts the active user may use for the next query of their exploration.
Several improvements, left as future work, are needed before integrating our belief processor into a personal data exploration assistant. A first step is to improve our belief model, either by refining the computation by taking into account more information from the schema and the usage, or to change the scale at which the belief is expressed (for example at the cell’s level rather than the query parts). Second, it is crucial to define an eficient belief update routine that scales with the size of the distribution probability that we use. Finally, we have to define a set of interestingness measures based on the information content of a sequence of queries and the complexity of these queries. Again, these definitions should take advantage of the peculiarities of the data cube exploration context to be on par with what a human analyst would consider interesting. 3 3.1
Our user belief model relies on query parts. The term query parts can undergo diferent meanings. Coherent with our objective of taking into account both usage (i.e., previous explorations) and cube schema, our query part definitions encompasses both.
First, concerning the usage, we use the definition of query part
provided by [
Second, regarding the schema, we consider as query parts all dimensional attributes and possible selection predicates, leaving measures for future work. Indeed, our approach relies on relations between query parts. While it is easy to infer relations based on the schema for dimensional attributes (based on the hierarchy) or selection conditions (based on the value selected), it is not trivial to find a relation based on the measures. 3.2
The framework proposed by De Bie [
As a consequence, a general definition for this interestingness measure (IM) is a real-valued function of a background distribution, that represents the belief of a user, and a pattern, that is to say the artifact to be presented to the explorer. Given a set Ω , the data space, and a pattern Ω ′ a subset of Ω , the belief is the probability P(Ω ′) of the event x ∈ Ω ′, i.e., the degree of belief the user attaches to a pattern characterized by Ω ′ being present in the data x . In other words, if this probability is small, then the pattern is subjectively surprising for the explorer and thus interesting. In this sense, the IM is subjective in that it depends on the belief of the explorer. De Bie also proposes to weight this surprise by the complexity of the pattern Ω ′ as follows: I MDe Bie (P , Ω ′) = −loд(P (Ω ′)) descComp(Ω ′) (1) where P represents the user belief, i.e. the background distribution of the pattern Ω ′ over the set of data x and descComp(Ω ′) denotes the descriptional complexity of a pattern Ω ′.
The data mining process consists in extracting patterns and presenting first those that are subjectively interesting, and then refining the belief background distribution based the newly observed pattern Ω ′.
The key to such modeling as proposed by De Bie lies in the definition of the belief of each user for all possible patterns and how it should evolve based on new patterns explored during time. Section 4 details how we represent the user belief and how we learn it in our context. The update of such belief based on new discovered patterns is left for future work. 3.3
Initially, the PageRank algorithm is designed to estimate the
relative importance of web pages as a probability to end up on
this web page after an infinite surf on the web [
PR = ((1 − α )M + αT ) × PR (2) where M is the stochastic transition matrix of the graph of web pages co-occurrences and T represents, in the traditional PR algorithm, a stochastic uniform distribution matrix that ensures the convergence to stable probabilities, and can conceptually be understood as the possibility for the surfer to teleport anywhere on the web graph.
The topic-specific PR [
This section addresses the following questions: (1) what is user belief in BI exploration? (2) How to estimate it? 4.1
Ideally, the user belief would be a probability the user attaches to
the statement "I believe the value of this cell is exactly this one".
Modeling such a belief is one of our long term perspectives. In a
ifrst methodological step towards this direction, we consider in
this work that the user belief is the importance the user attaches
to the statement "I believe this query part is relevant for my
exploration". In some sense, we consider query parts as pieces of
knowledge about the data that reduce the set of possible values
it may take from the original data space, inspired by the De Bie’s
view of explorative pattern mining [
We propose to define the user belief over the set of query parts
for two main reasons. First, the set of query parts is measurable
and thus respects the formal constraints in the model of De Bie
[
As we cannot "brain-dump" the user, the belief is approximated by the importance of the available query parts. The challenge lies in a way to find this probability distribution over a possibly infinite or too large set of query parts even if we restrict to the attributes in a given schema.
Practically, in order to avoid to deal with all these query parts, we restrict to those appearing in a query log and in the schema, where only the active domain of the attributes is considered. This importance attached to query parts appearing in actual users’ explorations is consistent with our objective of defining a subjective measure. 4.2
Once restricted the set of query parts that will be considered, we still need to compute their relative importance expressed as a probability distribution for a specific user. This is done by a topic-specific PageRank (PR) that computes the probability for a user u to end up on a query part q when using the cube schema during the exploration, knowing past explorations by other users and knowing the profile of u.
Let M be the topology transition matrix as defined in the topic specific PageRank (TSPR). It is computed from the directed graph of query parts G = ⟨V , A⟩ defined over the set V of all query parts found in a log of queries L, and a schema S that represents the topology of the multidimensional space. This schema can be reduced either as a set of sequence of attributes or as a set of hierarchies of attribute values. As motivated in Section 3.1, we ignore the measures in this definition. The graph G is constructed as follows: first we apply schema based construction rules and then log usage construction rules.
Schema based construction rules. (i) for each pair of attributes, there is an arc a ∈ A if one is the immediate roll-up predecessor or successor of the other in the dimension where they appear and (ii) for each pair of selected values, there is an arc if they are cousins in a dimensional hierarchy (i.e., values taken from the domain of the same attribute). These two rules are repeated when dimensions are combined. Note that, again, more complex relations could be captured in the future in our graph, like sibling relations for selected values in a dimensional hierarchy.
Log usage construction rules. there is an arc a from vertex q1 to vertex q2 and an arc a′ from q2 to q1 if q1 and q2 appear together in the same query. There is also an arc a from vertex q1 to vertex q2 if q1 is in a query that precedes another query where q2 appears.
While the graph G is a general topology of the query space, it is not however subjective in any way. It has to be biased toward a specific user, represented by the subset U of the query parts occurring in their sessions. Let Gu = ⟨V , Eu ⟩ be the user specific weighted directed graph, defined over the same set V of vertices as G, but only constructed following the specific log usage rules: there is an arc e from vertex q1 to vertex q2 (resp. from q2 to q1) with weight n if q1 and q2 are co-occurring n times in the query log of the user. Similarly, if a query part q1 is in a query that precedes another query where part q2 appears, then an arc (q1, q2) with a weight 1 is added to the graph or the weight of the existing arc is incremented.
Let P be the transition matrix of G, M be the normalized stochastic version of P, it can be interpreted as a Markov chain.
Let B be the transition matrix of Gu , T is the normalized version of this matrix, also referred to as the teleportation matrix. We can now construct a transition matrix for the underlying Markov model used by the TSPR as follows:
T SPR = αT + (1 − α )M (3)
The user specific PageRank vector can now be obtained by solving PRu = PRu × T SPR. The PRu vector represents our user belief, as a probability distribution over the set of query parts V , with parameter α ruling the importance attached to the user profile. 5
Our approach is implemented in Java using jaxen to read cube schemas and Nd4j1 for simple and eficient matrix computation. The code is open source and available in a GitHub public repository2.
Our first experiments aim at showing that the belief probability
distribution that we learn from our model is coherent with what
could be expected in realistic exploration situations. To settle such
experiments, we need to have a well formalized environment
where possible explorations are already categorized into several
prototypical user profiles that could be used to bias our model. To
this aim, we use the CubeLoad generator [
We will establish our results around two distinct measures:
• first, we use a distance between two probability
distributions to estimate to which extent they are close and
behave similarly. A classical choice could have been to use a
Kullback-Leibler divergence, but here we prefer to use the
discrete Hellinger distance that has the advantage of being
symmetric and bounded in the interval [
H (P , Q) = √
i=1 2 1 vut k
Õ(√pi − √qi )2 • second, we will plot the average probability distributions for each user model and their standard deviation to appreciate how the distribution evolves and how it is shaped, for a qualitative evaluation. 5.2
We expect the 4 templates included in CubeLoad to behave differently. The slice all template is a local user model that only explores a small fraction of the data space in terms of coverage of diferent concepts embedded in this space. It is thus expected that when comparing to a distribution probability of the whole topology, it will maximize this distance. In this case, there should also be only a few query parts that concentrate most of the interactions with a higher probability, as the user matrix is very local and is unlikely to teleport to most portions of the data space, which in turns become improbable. Similarly, the probability of knowing something from the data should be very low, which (4) could be traduced by a fast and strong drop in the probability distribution.
On the contrary, the explorative template should allow for a broader exploration of the data space. This template should lead to minimizing its distance with a topology based distribution. In this case, it is expected that there are fewer very improbable query parts but that there are more higher probabilities on most query parts, because of the coverage of the data space by the template.
The goal-oriented and slice-and-drill templates are expected to be intermediate states between the two previous templates. Indeed, both models explore the data space more than slice-all, but are a bit more constrained than explorative. 5.3 • the distribution of probabilities computed only from the topology denoted PR, that is to say the distribution probability that a traditional PageRank would have produced in our context, • and the distribution produced when the PageRank is biased toward a specific user profile, denoted TSPR here, corresponding to a specific template in CubeLoad.
We can first observe in Table 1 that the distance between the resulting distributions is proportional to α as expected. Indeed, if α is very low, the biased distribution is very close to the PR topology distribution. The higher α , the more characteristics from the user profile are introduced in the transition matrix. Second and as expected, we notice that the slice-all profile bears the larger distance with the topology as it only explores a small portion of the possible space, while the other profiles seem to have a comparable behavior in terms of distance.
Figures 4 and 5 plot, for two distinct values of parameter α , the average distribution of probabilities for the 4 user profiles and the PR distribution corresponding to the topology. As expected, when α = 0.2 all distributions heavily tend to mimic the PR distribution. On the contrary, when α = 0.8 the diference brought by the user profile become clearly visible. The slice-all profile tends to have a higher number of small probabilities as expected and then decreases very strongly as there is only a few query parts which are likely to be known by the user. Explorative user profile favors exploration and thus it is less likely that the probability of knowing already a query part is low, and consequently the distribution of value tends to decrease more smoothly in this case. Finally, and as for our Hellinger distance test, goal-oriented and slice-and-drill profiles exhibit intermediate behavior for lowprobability query parts and then tends to evolve as smoothly as the explorative profile. 6
The first experiments reported in Section 5 show that our model of belief is able to transcribe diferent exploration templates based on the shape of their probability distribution functions, although 3 templates, namely Explorative, Goal Oriented and Slice And Drill, remain very close in this respect.
However, if our belief model is to be faithful to the user intent, as it is expressed at the query part level, any change in the accessed area of a cube should be traduced by a change in the assigned probability weights in our belief model. We propose to ifrst simulate this diversity in the cube exploration by learning the belief model on diferent and independent log files generated by CubeLoad.
Second, as the long-term objective is to use belief-based
interestingness measure as an input for tailoring personalized
recommendations, we want to evaluate to which extent the output
of a recommender system could impact the belief of a specific
user. To this aim, we use a state-of-the-art OLAP recommender
system [
In both cases, we need to define beforehand a reference belief for each of the 4 CubeLoad templates in our simulations. Then a divergence measure can traditionally be used to evaluate to which extent changing the template or changing the log file on which we learn the models impacts the belief distribution. 6.1
Evaluation scenarios. Figure 6 presents the main evaluation protocol for the impact of usage and recommender system on the belief measure. The left-side of Figure 6 illustrates how to generate the reference belief. Similarly to Section 5.1, we use 50 CubeLoad sessions among which 43 are used to compute the topology graph of our PageRank (see “Log usage construction rules” in Section 4.2) and 7 sessions issued from a single CubeLoad template are used to simulate a user and bias the topic-specific PageRank.
The right-side of Figure 6 describes how we generate the test
belief based on the recommender system [
Evaluation of results. We use the Hellinger distance as described in Section 5.1 to compare the reference and test belief distributions. We generate 40 random logs (10 per profile) and we run them against randomly chosen seeds from the 4 profiles and against the 4 possible reference belief models. Results are averaged and reported in Table 2 and 3. 6.2
We expect several observable results from these experiments. First, it is expected that the belief divergence between the recommended queries from the test and the queries used as a reference is much larger in case of independent log files than in case of identical log files. As in both cases the recommender system is involved, this would mean that any observed diference would be due to the diference in log files and that our belief model while preserving the distribution probabilities of each CubeLoad template is able to reflect the diferences in usage on query parts.
Second, we expect to observe diferences between the 4 CubeLoad templates that could refine the observations of Section 5.3. Indeed, only based on the distribution it was not possible in our setting to distinguish clearly among the Explorative, Goal Oriented and Slice and Drill templates. We expect them to remain close but with slight divergence that would reflect the diferent abilities of each template to dig into new parts of the data cube. However, similarly to experiments in Section 5.3 we expect Slice All to be significantly divergent from the other profiles. Indeed, it is known that this template exhibits tendencies to explore locally the cube by only navigating a dimension following siblings relations.
Finally, if we consider our belief model as representative of the usage, we may be able to draw conclusions about the use of recommender systems with CubeLoad templates and to which extent the latter propose really distinguishable exploration patterns. To this aim, a comparison of divergence values when comparing, for each CubeLoad template, its reference to its recommended test on the same log file would indicate to which extent the template explores various portion of the cube. In other words, the more explorative a template is, the larger the divergence between a recommendation based on this template and its reference should be. 6.3
Tables 2 and 3 present experimental values of Hellinger distance for the identical and the independent scenarios and each type of recommendation based on the 4 CubeLoad templates (lines) for each reference belief model (columns).
It can be seen that, as expected, the divergence is significantly lower when considering recommendations based on the same log file that was used for the reference belief computation. This shows that our belief method is sensitive to the actual queries that are involved in the building of the model despite the general trends observed for the probability distribution in Section 5.3.
Tests\References Explorative Goal Oriented Slice All Slice and Drill Explorative 0.64 0.60 0.47 0.60 Goal Oriented 0.64 0.61 0.46 0.60 Slice All 0.67 0.63 0.47 0.62 Slice and Drill 0.63 0.60 0.43 0.58 Table 2: Average Hellinger distance values on 10 runs when log files are identical. Lines represent test and columns represents reference belief.
Tests\References Explorative Goal Oriented Slice All Slice and Drill Explorative 0.85 0.86 0.81 0.86 Goal Oriented 0.85 0.85 0.81 0.86 Slice All 0.83 0.84 0.79 0.84 Slice and Drill 0.86 0.86 0.82 0.87 Table 3: Average Hellinger distance values on 10 runs when log files are independent. Lines represent test and columns represents reference belief.
Then, results from Tables 2 and 3 corroborates that there exists diferences between the CubeLoad templates but that are more or less dificult to observe depending on the CubeLoad template, as shown by the distribution of Section 5.3.
In the identical scenario, Explorative recommendation is the most distant to its corresponding Explorative reference (distance = 0.64) and the most distant to all other recommendations as shown in column Explorative from Table 2. This can be understood by the nature of the CubeLoad template which makes it dificult to model for a recommender system, which in turns implies a higher probability to access new portions of the cube and thus new query parts.
Goal oriented column of Tables 2 and 3 presents not significantly diferent distance values whatever the recommendation profile is. This is expected as this template can generate several diferent paths in the cube to access the same region in the end. As a consequence, there is a variety in the accessed query parts which in turns tends to smooth the distance values.
Slice and Drill exhibits significant diferences and with a small distance to itself of 0.58, which means that the recommendation that is produced reflects the CubeLoad template and stays in a localized region of the data cube with more common query parts between recommendations and the reference template.
Finally, an interesting observation is that Slice All has a very low inner distance of 0.47 in Table 2 which means that the exploration is very focused and that even a recommender system based on this template will reproduce this local exploration behaviour with no surprising query parts. This reflects a sort of cognitive bubble associated to this template, which can be detected with our approach of user belief estimation.
The latter is confirmed by the analysis of the line Slice All in Table 2 where the distance between the recommended Slice All and the other CubeLoad reference templates that are higher than the other distances for each of these templates. For example, in Table 2, the distance of Slice All to Explorative is 0.67 which is the largest distance for the column Explorative.
These first results bring new insights on our belief model, and to which extent it is coherent with the CubeLoad profiles. A more thoroughful analysis of these results is needed to conclude about diferences on CubeLoad templates and is left as future work. 7
Our work deals with subjective interestingness and how to deifne such a measure by learning a belief distribution from users’ past activities in the context of BI. This section presents some interestingness measures, and how they have been used in the context of recommendation.
Interestingness has attracted researchers since a long time in the context of data mining. Indeed, there exists numerous tasks, for example in pattern mining, for which it is critical to be able to filter out uninteresting patterns such as item sets or redundant rules, to control the complexity of the mining approaches and increase their usability.
In [
On the contrary, subjective measures consider both the data
and the user and characterize the patterns’ surprise and novelty
when compared to previous user knowledge or expected data
distribution. The first work on the topic of subjective
interestingness is certainly [
The authors in [
Recently, in [
In the context of data cube exploration, to the best of our
knowledge there is no final and consensual interestingness
measure or belief distribution elicitation method, while there exists
measures that are closely related. Measures have been defined as
unexpectedness of skewness in navigation rules and navigation
paths [
In [
Finally, interestingness and related principles have been
studied in the context of recommendation but more widely used for
evaluation rather than the recommendation itself [
In the context of OLAP query recommendation, several
recommendation algorithms have been proposed that take into account
the past history of queries of a user either based on a Markov
model [
This paper describes a first attempt to model user belief as a probability distribution over query parts in the context of data cube exploration. The experiments conducted on several prototypical user templates generated with CubeLoad illustrate how a topicspecific PageRank can be used to approximate such probability distribution. Preliminary experiments show that it is already possible to use our belief model as an indicator for the type of exploration that a user favors (more global or more local exploration) or for the portion of the data cube that will be most certainly explored. Finally our belief model can be used to identify recommendations that are likely to trap user in a cognitive bubble and thus may help leveraging diversity in exploration.
This work opens up for further research avenues. Our longterm goal is the implementation and validation through user studies of the vision illustrated by Figure 2. Shorter-term research questions include: (1) how to refine our model of query parts, for example to better take into account measures in the schema? (2) How to express the user’s belief beyond query parts, for instance over the cube’s cells? (3) How to improve our model to better distinguish between less marked exploration patterns, for instance between the goal-oriented and slice-and-drill patterns, in terms of distribution? (4) How to deal with real noisy log usage? (5) How can we update the probability distribution when a new query is executed? (6) Finally, what interestingness measures can be devised from on our proposal?