With the increase in Web of Data (WOD) many new challenges regarding exploration, interaction, analysis and discovery have surfaced. One of the basic building blocks of data analysis is classi cation. Many studies have been conducted concerning Formal Concept Analysis (FCA) and its variants over WOD. But one fundamental question is, after these concept lattices are obtained on top of WOD, how the user can interactively explore and analyze this data through concept lattices. To achieve this goal, we introduce a new tool called as LatViz, which allows the construction of concept lattices and their navigation. LatViz proposes some remarkable improvements over existing tools and introduces various new functionalities such as interaction with expert, visualization of Pattern Structures, AOC posets, concept annotations, ltering concept lattice based on several criteria and nally, an intuitive visualization of implications. This way the user can e ectively perform an interactive exploration over a concept lattice which is a basis for a strong user interaction with WOD for data analysis.
In the last decade, there has been a huge shift from the Web of Documents to the
Web of Data (WOD). Web of Documents represents data in the form of HTML
pages which linked with other HTML pages through hyperlinks. This web of
documents has evolved into WOD where all the information contained is represented
in the form of entity and relations allowing the semantics to be embedded in the
representation of the this data. This data are in the form of a (node-arc) labeled
graph belonging to several domains such as newspapers, publications,
biomedical data etc. The growth in the publication of data sources in WOD has made it
an important source of data, which has led towards many challenges pertaining
to e ective utilization of this data. WOD mainly represents data in the form of
Resource Description Framework (RDF)1. There are several ways such as data
1 http://www.w3.org/RDF/
dumps and SPARQL queries to access this data, which can be utilized for many
purposes, one of which is visualization and interactive exploration for data
analysis purposes. Several visualization tools have been developed for this purpose,
one of which is LODLive2 [
In order to provide the user with the ability to perform data analysis and
knowledge discovery over such kind of data, there is a need to perform
classication, where the obtained classes are further made available to the user for
exploration and subjective interpretation. In the current study we use Formal
Concept Analysis as the basis for classi cation. Several studies have already been
conducted using FCA and its variants over RDF graphs or its generalization to
knowledge graphs. Out of these studies so far RV-Xplorer [
The paper is structured as follows: Section 2 introduces a motivating example, Section 3 introduces the background required for understanding the rest of the paper while Section 4 introduces some of the important functionalities of LatViz. Then in Section 5, we discuss some of the related tools already developed and nally Section 6 details the future perspectives of the current work. 2
Let us consider that an expert is searching for papers published by a particular team in conferences or journals related to his/her eld of research. In order to locate the papers of his/her interest (s)he has to search for speci c keywords
or authors in the local portal. For getting the view of which kind of papers are contained (s)he has to run a broad query and then narrow down his/her query to obtain papers on speci c keywords or authors or group of keywords or authors. The expert will end up running several queries to get what (s)he wants. Moreover, if the expert wants to know the collaborations of the team with other members of the research community outside the team, as well as the diversity and the specialization of the team members, this cannot be directly obtained by simple querying. To obtain such kind of knowledge there is a need to introduce a support for data analysis. Based on this scenario, we show how the expert can be guided thanks to an adapted visualization tool to obtain such information of interest with the help of concept lattices. 3 3.1
In this section we provide a brief introduction to pattern structures [
f or A G
dl :
tg P G|d pgqu
f or d P D
Each element in D is referred to as a pattern. The subsumption order over these
patterns is given as: c d ô c [ d c. The operator p:ql makes a Galois
connection. Then, a pattern concept of a pattern structure pG; pD; ; q is a
q
pair pA; dq where A G and d P D such that Al d and A dl, where A
is called the concept extent and d is called the concept intent. Pattern concept
lattices are de ned in the same way as concept lattices in standard FCA.
Interval Pattern Structures. Interval Pattern Structures were rst introduced
in [
Web of Data (WOD) is represented in the form of entity and relationships. A standard representation of WOD represents data in the form of RDF (Resource Description Framework) triples written as xsubject; predicate; objecty. Here, subject can be a URI or a blank node, predicate can be a URI and object can be a URI, a blank node or a literal. Several RDF triples connect together to form an RDF graph. Table 1 shows an example of RDF triple store from DBLP where each row represents one triple. The subject is the title of the paper, predicates are the relations such as dc:subject and dc:creator (interpreted as \has keyword" and \ has author" respectively) and the objects are the keywords and the authors. The triple t1 is read as \paper s1 has keyword Pattern Structures ".
In order to allow interactive data exploration over RDF data, an initial set of restrictions is posed by the expert by de ning the task requirement based on which a SPARQL query is created by the expert to obtain the speci c data. Then the most important step for interactive data exploration is to perform classi cation of RDF data. Finally, the expert is allowed to interact with the obtained classi cation. In the rest of this paper, we further improve the functionalities of the existing tools by introducing several new interactive operations in a new tool called LatViz.
The display of LatViz resembles Conexp3, which provides basic functionalities
for building a concept lattice. LatViz implements two algorithms for building a
concept lattice from a binary context, one of which is introduced in [
The concept lattice for the scenario in section 2 was created by mapping the RDF data to a formal context K pG; M; Iq. Based on Table 1, the subjects of the triples were considered as the set of objects G, the objects in the RDF triples i.e., keywords and authors were considered as the set of attributes M . In this example, the RDF triples were created from the publications of the
Knowledge Discovery (KDD) team in LORIA. The number of objects in the
context are 343 and attributes are 1516. Figure 1 shows a complete concept
lattice built using LatViz. The information about a concept can be displayed
by selecting the concept. Very often huge concept lattices are obtained based
on the context size. LatViz provides several interactive operations allowing for
reduction of exploration space of the expert. To-date this is the most interactive
tool having many unique functionalities such as handling numeric data with
the help of interval pattern structures, AOC-posets, ltering concept lattice and
implications which provides support for data analysis. Other functionalities such
as annotating the lattice, level-wise display of a concept lattice etc. are discussed
in many contexts but are not yet directly implemented in the commonly used
tools. In the following we detail each of these functionalities for data analysis.
AOC-poset is a partially ordered set of the attribute and object concepts, rst
introduced in [
In case of huge concept lattices sometimes it is hard to keep track of the ordering
relations between the concepts. LatViz allows the expert to only highlight
sub/super concepts of a concept. For example, if the expert wants to display all the
publications along with the collaborations of the author Amedeo Napoli, (s)he
can highlight the associated sub-lattice of the attribute concept of \Amedeo
Napoli". Figure 4 shows the highlighted sub-lattice in brown. An expert can
highlight the super-concepts connected to a concept. If the expert is looking for
all the papers having some keywords common with the paper Knowledge
Organization and Information Retrieval Using Galois Lattices having one or more of
the keywords in the intent of the concept then (s)he can highlight the sub-lattice
of super concepts associated to it (see Figure 5).
This functionality was partially implemented in RV-Xplorer [
In the running scenario, we extracted three attributes for the papers i.e., year of publications, rank of the conference in which the paper was published and nally the number of pages. The ranks of the conferences were considered based on COmputing Research and Education (CORE) rankings4. The ranks were A*, A, B, C and other which were coded as 1, 2, 3, 4 and 5 respectively. The nal concept lattice generated for the last ve years of publications of Knowledge Discovery Team is shown in Figure 8. 4.7
There are two categories of ltering provided by LatViz; one is for the concept lattice created with the binary data and the other one is provided for the pattern concept lattice built with the help of interval pattern structures. Filtering Concept Lattice. After a concept lattice is built by applying FCA, expert is allowed to set several ltering criteria such as stability, lift, extent size, intent size and nally speci c object or attribute names. Let us consider that in the running example, the expert is looking for the papers published by Amedeo Napoli on the topic of pattern structures and FCA. A lter on the number of attributes in the intent is set to 3. The ltered concept lattice obtained over the complete lattice in Figure 1 is shown in Figure 9. It further shows the authors with who Amedeo Napoli has worked i.e., Sergei O. Kuznetsov and Mehdi Kaytoue. This part of concept lattice shows the community of authors working with Amedeo Napoli on the topic of pattern structures. 4 http://portal.core.edu.au/conf-ranks/ Filtering Pattern Concept Lattice. Interval Pattern Concept Lattices can also be ltered by specifying the number of attributes to be considered, the upper and the lower limits for the intervals in the intent of each attribute along with stability, lift and extent size. Let us consider the pattern concept lattice in Figure 8, it can be seen that the concept lattice is hard to interpret. To make it more readable based on what an expert wants, (s)he is allowed to specify lters. For example, if the expert is looking for a paper published in a conference of a rank 1-4 in the year 2012 - 2015 and has the number of pages not less than 2 and no more than 42 then the respective lters can be set for the values of all three attributes. The ltered pattern concept lattice will then only contain the part of lattice needed by the user. Figure 8 shows the concept containing group of papers published from 2014-2015 in conferences with rank 2 having number of pages 2-42. One of the many proposed visualization techniques for implications includes table-based views. It keeps each column for rule ID, LHS and RHS of the rule, support and con dence measures. These views were used because of the simplicity of storage. However, while expert interaction it is not very convenient to obtain interesting rules at a simple glance as the number of rules can be too many. Another way of visualizing association rules are Matrix Views, where rows represent the LHS and columns represent the RHS of the rules. Support and condence are displayed by di erent colors in the intersection of the LHS and RHS. In case of a formal context, the number of objects/attributes can be very big leading to problems in displaying the matrix. By carefully taking into account the above drawbacks, we nally settle on visualizing implications with the help of scatter plots, where the x-axis shows the increasing support and the y-axis shows the increasing lift (as we are considering implications the con dence of the rule is always 100%). Such kind of display helps the expert to single-out the rules (s)he wants to visualize based on the values of support and lift. Figure 11 shows implications of the running example, x-axis keeps the support in percentage and y-axis keeps lift. The number on top of the circle shows the number of rules existing in the same point in the plot. On mouse over, expert can view the implications.
Fig. 10: Filtered Pattern Concept
Lattice.
In [
LatViz is a tool built for allowing expert interaction for data analysis purposes.
It provides many new functionalities for reducing the exploration space of the
expert and enable him to interpret the results. As a future perspective, we also want
to implement other variations of pattern structures such as Pattern Structures
introduced for structured set of attributes discussed in [