Blaise Pascal University, LIMOS laboratory, Clermont-Ferrand, France ISBN 978–2–9544948–0–7
Blaise Pascal University, LIMOS laboratory, Clermont-Ferrand, France The Twelfth International Conference on Concept Lattices and Their Applications
C L A 2015 Clermont-Ferrand, France
October 13–16, 2015
CLA 2015 c paper author(s), 2015, for the included papers c Sadok Ben Yahia, Jan Konecny, Editors, for the volume Copying permitted only for private and academic purposes.
This work is subject to copyright. All rights reserved. Reproduction or publication of this material, even partial, is allowed only with the editors’ permission. Cover photo from blognature.fr
Impression: Edition: First published: 2015 xiii+254 50 1st
CLA 2015 was organized by the Blaise Pascal University, LIMOS laboratory, Clermont-Ferrand.
Radim Belohlavek Sadok Ben Yahia Jean Diatta Peter Eklund Sergei O. Kuznetsov Engelbert Mephu Nguifo Amedeo Napoli Manuel Ojeda-Aciego Jan Outrata
Sadok Ben Yahia Jan Konecny
Simon Andrews Jaume Baixeries
Cynthia Vera Glodeanu Alain Gély Tarek Hamrouni Marianne Huchard Dmitry Ignatov Mehdi Kaytoue Stanislav Krajči Francesco Kriegel Michal Krupka Marzena Kryszkiewicz Sergei O. Kuznetsov Léonard Kwuida Jesús Medina Engelbert Mephu Nguifo Rokia Missaoui Amedeo Napoli Lhouari Nourine Sergei Obiedkov Manuel Ojeda-Aciego Petr Osička Jan Outrata Uta Priss Francois Rioult Sebastian Rudolph Christian Sacarea Barış Sertkaya László Szathmáry Petko Valtchev Francisco Valverde Technische Universität Dresden, Dresden, Germany Université de Lorraine, Metz, France ISAMM, Manouba University, Tunisia LIRMM – Université Montpellier 2, Montpellier, France State University HSE, Moscow, Russia Liris – Insa, Lyon, France Univerzita Pavla Jozefa Šafárika v Košiciach, Košice, Slovakia Technische Universität Dresden, Dresden, Germany Palacký University, Olomouc, Czech Republic Warsaw University of Technology, Warsaw, Poland State University HSE, Moscow, Russia Bern University of Applied Sciences, Bern, Switzerland Universidad de Cádiz, Cádiz, Spain LIMOS, Clermont-Ferrand, France LARIM – Université du Québec en Outaouais, Gatineau, Canada LORIA, Nancy, France LIMOS, Clermont-Ferrand, France State University HSE, Moscow, Russia Universidad de Málaga, Málaga, Spain Palacký University, Olomouc, Czech Republic Palacký University, Olomouc, Czech Republic Ostfalia University of Applied Sciences, Wolfenbüttel, Germany GREYC – Université de Caen Basse-Normandie, Caen, France Technische Universität Dresden, Dresden, Germany Babes,-Bolyai University, Cluj-Napoca, Romania SAP Research Center, Dresden, Germany University of Debrecen, Debrecen, Hungary Université du Québec, Montréal, Canada Universidad Carlos III, Madrid, Spain
Olivier Raynaud (chair)
LIMOS, Clermont-Ferrand, France LIMOS, Clermont-Ferrand, France LIMOS, Clermont-Ferrand, France INRA Theix, Clermont-Ferrand, France LIMOS, Clermont-Ferrand, France LIMOS, Clermont-Ferrand, France LIMOS, Clermont-Ferrand, France
LIMOS, Clermont-Ferrand, France An Aho-Corasick Based Assessment of Algorithms Generating Failure Deterministic Finite Automata : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Madoda Nxumalo, Derrick G. Kourie, Loek Cleophas and Bruce W. Watson Probabilistic Implicational Bases in FCA and Probabilistic Bases of GCIs in EL? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 193
Francesco Kriegel Category of isotone bonds between L-fuzzy contexts over different structures of truth degrees : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 205
Jan Konecny, Ondrej Krídlo From an implicational system to its corresponding D-basis : : : : : : : : : : : : : 217 Estrella Rodríguez-Lorenzo, Kira Adaricheva, Pablo Cordero,
Manuel Enciso, Angel Mora Using Linguistic Hedges in L-rough Concept Analysis : : : : : : : : : : : : : : : : : : 229
Eduard Bartl, Jan Konecny Revisiting Pattern Structures for Structured Attribute Sets : : : : : : : : : : : : : 241 Mehwish Alam, Aleksey Buzmakov, Amedeo Napoli, Alibek
Sailanbayev Author Index : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 253 Formal Concept Analysis is a method of analysis of logical data based on formalization of conceptual knowledge by means of lattice theory. It has proved to be of interest to various applied fields such as data visualization, knowledge discovery and data mining, database theory, and many others.
The International Conference “Concept Lattices and Their Applications (CLA)” is being organized since 2002 and its aim is to bring together researchers from various backgrounds to present and discuss their research related to FCA. The Twelfth edition of CLA was held in Clermont-Ferrand, France from October 13 to 16, 2015. The event was jointly organized by the LIMOS laboratory, CNRS, and Blaise Pascal university, France.
This volume includes the selected papers and the abstracts of 5 invited talks. We would like to express our warmest thanks to the keynote speakers. This year, there were initially 39 submissions, from which the Program Committee selected 20 papers which represents an acceptance rate of 51.2%. The program of the conference consisted of five keynote talks given by the following distinguished researchers: Didier Dubois, Lhouari Nourine, Gabriella Pasi, Jan Ramon, and Takeaki Uno, together with twenty communications authored by researchers from 11 countries, namely: Austria, Czech republic, France, Germany, Kazakhstan, Republic of South Africa, Russia, Slovakia, Spain, Sweden, and Ukraine.
Each paper was reviewed by 3–4 members of the Program Committee and/or additional reviewers. We thank them all for their valuable assistance. It is planned that extended versions of the best papers will be published in a well-established journal, after another reviewing process.
The success of such event is mainly due the hard work and dedication of many people and a collaboration of several institutions. We thank the contributing authors, who submitted high quality works, we thank to the CLA Steering Committee, who gave us the opportunity of chairing this edition, and we thank the Program Committee, the additional reviewers, and the local Organization Committee. We are also thankful to the following institutions, which have helped the organization of the twelfth edition of CLA: Coffreo, IPLeanware, Axège, and Oorace.
We also thank the Easychair conference system as it made easier most of our administration tasks related to paper submission, selection, and reviewing. Last but not least we thank Jan Outrata, who offered his files for preparing the proceedings.
User Models as Personal Ontologies
Laboratorio di Information Retrieval – Università degli Studi di Milano Bicocca,
Milano, Italia Abstract. The problem of defining user profiles has been a research issue since a long time; user profiles are employed in a variety of applications, including Information Filtering and Information Retrieval. In particular, considering the Information Retrieval task, user profiles are functional to the definition of approaches to Personalized search, which is aimed at tailoring the search outcome to users. In this context the quality of a user profile is clearly related to the effectiveness of the proposed personalized search solutions. A user profile represents the user interests and preferences; these can be captured either explicitly or implicitly. User profiles may be formally represented as bags of words, as vectors of words or concepts, or still as conceptual taxonomies. More recent approaches are aimed at formally representing user profiles as ontologies, thus allowing a richer, more structured and more expressive representation of the knowledge about the user.
This talk will address the issue of the automatic definition of personal ontologies, i.e. user-related ontologies. In particular, a method that applies a knowledge extraction process from the general purpose ontology YAGO will be described. Such a process is activated by a set of texts (or just a set of words) representatives of the user interests, and it is aimed to define a structured and semantically coherent representation of the user topical preferences. The issue of the evaluation of the generated representation will be discussed too.
Formal Concept Analysis from the Standpoint of Possibility Theory
IRIT – Université Paul Sabatier, Toulouse, France Abstract. Formal concept analysis (FCA) and possibility theory (PoTh) are two theoretical frameworks that are addressing different concerns in the processing of information. Namely FCA builds concepts from a relation linking objects to the properties they satisfy, which has applications in data mining, clustering and related fields, while PoTh deals with the modeling of (graded) epistemic uncertainty. This difference of focus explains why the two settings have been developed completely independently for a very long time. However, it is possible to build a formal analogy between FCA and PoTh. Both theories heavily rely on the comparison of sets, in terms of containment or overlap. The four set-functions at work in PoTh actually determine all possible relative positions of two sets. Then the FCA operator defining the set of objects sharing a set of properties, which is at the basis of the definition of formal concepts, appears to be the counterpart of the set function expressing strong (or guaranteed) possibility in PoTh. Then, it suggests that the three other set functions existing in PoTh should also make sense in FCA, which leads to consider their FCA counterparts and new fixed point equations in terms of the new operators. One of these pairs of equations, paralleling the one defining formal concepts, define independent sub-contexts of objects and properties that have nothing in common.
The parallel of FCA with PoTh can still be made more striking using a cube of opposition (a device extending the traditional square of opposition existing in logic, and exhibiting a structure at work in many theories aiming at representing some aspects of the handling of information). The parallel of FCA with PoTh extends to conceptual pattern structures, where objects, may, e.g., be described by possibilistic knowledge bases.
In the talk we shall indicate various issues pertaining to FCA that could be worth studying in the future. For instance, the object-property links in formal contexts of FCA may be a matter of degree. These degrees may refer to very different notions, such as the degree of satisfaction of a gradual property, the degree of certainty that an object has, or not, a property, or still the typicality of an object with respect to a set of properties. These different intended semantics call for distinct manners of handling the degrees, as advocated in the presentation. Lastly, applications of FCA to the mining of association rules, to the fusion of conflicting pieces of information issued from multiple sources, to clustering of sets of objects on the basis of approximate concepts, or to the building of conceptual analogical proportions, will be discussed as other examples of lines of interest for further research.
Clarifying Lattice Structure by Data Polishing
Institute of Informatics (NII) of Japan, Tokyo, Japan Abstract. Concept lattice is made from many kinds of data. We want to use large scale data for the construction to capture wide and deep meanings but the result of the construction usually yields a quite huge lattice that is impossible to handle. Several techniques have been proposed to cope with this problem, but to best of our knowledge no algorithm attains good granularity, coverage, size distribution, and independence of concepts at the same time. We consider this difficulty comes from that the concepts are not clear in the data, so a good approach is to clarify the concepts in the data by some operations. In this direction, we propose “data polishing” that modify the data according to feasible hypothesis so that the concepts becomes clear.
Tractable Interesting Pattern Mining in Large Networks
University of Leuven – INRIA, Leuven, Belgium Abstract. Pattern mining is an important data mining task. While the simplest setting, itemset mining, has been thoroughly studied real-world data is getting increasingly complex and network structured, e.g. in the context of social networks, economic networks, traffic networks, administrative networks, chemical interaction networks and biological regulatory networks.
This presentation will first provide an overview of graph pattern mining work, and will
then discuss two important questions. First, what is an interesting concept, and can
we obtain suitable mathematical properties to order concepts in some way, obtaining
a lattice or other exploitable structure?
Second, how can we extract collections of interesting patterns from network-structured
data in a computationally tractable way? In the case of graphs, having a lattice on
the class of patterns turns out to be insufficient for computational tractability. We
will discuss difficulties related to pattern matching and related to enumeration, and
additional difficulties arising when considering condensed pattern mining variants.
for each a, b P L. A truth-depressing hedge is a (truth function of) logical
connective ‘slightly true’, see [
On every complete residuated lattice L, there are two important truthdepressing hedges: (i) identity, i.e. a “ a pa P Lq; (ii) antiglobalization, i.e.
a “ " 0, if a “ 0,
1, otherwise . ˚G ˚1 ˚2 ˚3 ˚4 ˚5 ˚6 G 1 2 3 4 5 6 id id 1 Fig. 1. Truth-stressing hedges (top) and truth-depressing hedges (bottom) on 5-element chain with Łukasiewicz operations L “ xt0, 0.25, 0.5, 0.75, 1u, min, max, b, Ñ, 0, 1y. The leftmost truth-stressing hedge ˚G is the globalization, leftmost truth-depressing hedge G is the antiglobalization. The rightmost hedges denoted by id are the identities.
For truth-stressing/truth-depressing hedge ˚ we denote by fixp˚q set of its idempotent elements in L; i.e. fixp˚q “ ta P L | a˚ “ au.
Let ˚1, ˚2 be truth-stressing hedges on L such that fixp˚1q Ď fixp˚2q; then for each a P A, a˚1˚2 “ a˚1 holds. The same holds true for ˚1, ˚2 being truthdepressing hedges.
We naturally extend application of truth-stressing/truth-depressing hedges to L-sets: A˚pxq “ Apxq˚ for all x P U. 3
Results The L-rough concept-forming operator M gives for each L-set of objects two L-sets of attributes. The first one represents a necessity of having the attributes and second one a possibility of having the attributes. We add linguistic hedges to the concept-forming operators to control shape of the two L-sets.
Since the L-rough concept-forming operators are defined viaxÒ, Óy and xX, Yy,
we first recall the parametrization of these operators as described in [
Let r and ♠ be truth-stressing hedge and truth-depressing hedge on L, respectively. The isotone concept-forming operators parametrized by r and ♠ induced by I are defined as
AÒr pyq “ BÓq pxq “ ľ Apxqr Ñ Ipx, yq, xPX ľ Bpyqq Ñ Ipx, yq yPY AXr pyq “ BY♠ pxq “ ł Apxqr b Ipx, yq, xPX ľ Ipx, yq Ñ Bpyq♠ yPY for all A P LX, B P LY.
Properties of the hedges in the setting of multi-adjoint concept lattices with
heterogeneous conjunctors were studied in [
AN “ xAÒr , AXr y and xB, ByH “ BÓq X BY♠ (3) for A P LX, B, B P LY.
Remark 1. When the all three hedges are identities the pair xN, Hy is equivalent to xM, Oy; so it is an pL, L ˆ L´1q-Galois connection. For arbitrary hedges this does not hold.
The following theorem describes properties of xN, Hy.
Theorem 1. The pair xN, Hy of L-rough concept-forming operators parametrized by hedges has the following properties. (a) AN “ ArM “ ArN and xB, ByH “ xBq, B♠yO “ xBq, B♠yH (b) AM Ď AN and xB, ByO Ď xB, ByH (c) SpA1r, A2rq ď SpA2N, A1Nq and SpxB1, B1y, xB2, B2yq ď SpxB2, B2yH, xB1, B1yHq (d) Ar Ď ANH and xBq, B♠y Ď xB, ByHN; (e) A1 Ď A2 implies AN
2 Ď A1N and xB1, B1y Ď xB2, B2y implies xB2, B2yH Ď xB1, B1yH (f) SpAr, xB, ByHq “ SpxBq, B♠y, ANq (g) pŤiPI AirqN “ ŞiPI AiN and pxŤiPI Biq, ŞiPI Bi♠yqH “ ŞiPIxBi, BiyH (h) ANH “ ANHNH and xB, ByHN “ xB, ByHNHN.
Proof. (a) Follows immediately from definition of N and H and idempotency of hedges.
(b) From (2) we have Ar Ď A; by properties of Galois connections the inclusion implies AM Ď ArM, which is by (a) equivalent to AM Ď AN. Proof of the second statement in (b) is similar.
(c) Follows from (a) and properties of Galois connections.
(d) By [2, Corollary 1(a)] we have Ar Ď ArMO. Using (a) we get Ar Ď ANO and from (b) we have ANO Ď ANH, so Ar Ď ANH. Similarly for the second claim.
(e) Follows directly from [2, Corollary 1(c)] and properties of Galois connections.
(f) Since xM, Oy forms pL, L ˆ L´1q-Galois connection and using (a) we have SpAr, xB, ByHq “ SpAr, xBq, B♠yOq “ SpxBq, B♠y, ArMq “ SpxBq, B♠y, ANq.
(g) We can easily get and pď AirqN “ xpď AirqÒr , pď AirqXr y “ xč AiÒr , ď AiXr y iPI iPI iPI iPI iPI “ čxAiÒr , AiXr y “ č AiN, iPI pxď Biq, č Bi♠yqH “ pď BiqqÓq X pč Bi♠qY♠ “ iPI iPI iPI iPI č BiÓq X iPI č BiY♠ (h) Using (a), (d) and (e) twice, we have ANH Ď ANHNH. Using (d) for xB, By “ AN we have ANr Ď ANrHN “ ANHN. Then applying (e) we get ANHNH Ď ANH proving the first claim. The second claim can be proved analogically.
The set of fixed points of xN, Hy endowed with partial order ď given by xA1, B1, B1y ď xA2, B2, B2y iff A1 Ď A2 iff xB1, B1y Ď xB2, B2y is denoted by BrNH,q,♠pX, Y, I, Iq.
Remark 2. Note that from (4) it is clear that if a concept has non-natural L-rough intent then all its subconcepts have non-natural intent. If such concepts are not desired, one can simply ignore them and work with the iceberg lattice of concepts with natural L-rough intents.
The next theorem shows a crisp representation of BrNH,q,♠pX, Y, I, Iq.
NH Theorem 2. Br,q,♠pX, Y, I, Iq is isomorphic to ordinary concept lattice BÒÓpXˆfixprq, Yˆ fixpqq ˆ fixp♠q, Iˆq where
xxx, ay, xy, b, byy P Iˆ iff a b b ď Ipx, yq and a Ñ b ě Ipx, yq.
Proof. This proof can be done by following the same steps as in [
The following theorem explains the structure of BrNH,q,♠pX, Y, I, Iq.
NH Theorem 3. Br,q,♠pX, Y, I, Iq is a complete lattice with suprema and infima defined as (4) \[ \[ (5) (6) ľxAi, xBi, Biyy “ xpč AiqNH, xď Biq, č Bi♠yHNy,
i i i łxAi, xBi, Biyy “ xpď AirqNH, xč Bi, ď BiyHNy
i i i i for all Ai P LX, Bi P LY, Bi P LY.
Proof. Follows from Theorem 2.
Remark 3. Note that if we alternatively define (3) as or or or
AN “ xpAÒr qq, pAXr q♠y and xB, ByH “ pBÓq X BY♠ qr
AN “ xpAÒqq, pAXq♠y and xB, ByH “ pBÓ X BYqr AN “ xpAÒr qq, pAXr q♠y and xB, ByH “ xB, ByO
AN “ AM and xB, ByH “ pBÓq X BY♠ qr
we obtain an isomorphic concept lattice. In addition (5) and (6) produce the
same concept lattice.
3.3 Size Reduction of Fuzzy Rough Concept Lattices
This part provides analogous results on reduction with truth-stressing and
truthdepressing hedges as [
For the next theorem we need the following lemma.
Lemma 1. Let r, ♥, q, ♦ be truth-stressing hedges on L such that fixprq Ď fixp♥q, fixpqq Ď fixp♦q; let ♠, s be truth-depressing hedges on L such that and fixp♠q Ď fixpsq. We have
AN♥ Ď ANr and xB, ByH♦,s Ď xB, ByHq,♠ .
Proof. We have Ar♥ Ď A♥ from (2). From the assumption fixprq Ď fixp♥q we get Ar♥ “ Ar; whence we have Ar Ď A♥. Theorem 1(e) implies A♥N Ď ArN which is by the claim (a) of this theorem equivalent to AN♥ Ď ANr . The second claim can be proved similarly. \[ Theorem 4. Let r, ♥, q, ♦ be truth-stressing hedges on L such that fixprq Ď fixp♥q, fixpqq Ď fixp♦q; let ♠, s be truth-depressing hedges on L s.t. and fixp♠q Ď fixpsq,
NH NH |Br,q,♠pX, Y, I, Iq| ď |B♥,♦,spX, Y, I, Iq| for all L-rough contexts xX, Y, I, Iy.
In addition, if r “ ♥ “ id, we have Similarly, if q “ ♦ “ ♠ “ s “ id, we have
ExtrNH,q,♠pX, Y, I, Iq Ď Ext♥NH,♦,spX, Y, I, Iq.
IntrNH,q,♠pX, Y, I, Iq Ď Int♥NH,♦,spX, Y, I, Iq.
Proof. (4) follows directly from Theorem 2 and results on subcontexts in [
Now, we show (4). Note that each A P ExtrNH,q,♠pX, Y, I, Iq we have
A “ ANrHq,♠ “ AN♥Hq,♠ Ě AN♥H♦,s Ě A.
Thus we have A P Ext♥NH,♦,spX, Y, I, Iq. The inclusion (4) can be proved similarly. \[ Example 1. Consider the truth-stressing hedges ˚G, ˚1, ˚2, id and truth-depressing hedges G, 1, 2, id from Figure 1. One can easily observe that fixp˚Gq Ď fixp˚1q Ď fixp˚2q Ď fixpidq fixp Gq Ď fixp 1q Ď fixp 2q Ď fixpidq.
Consider the L-context of books and their graded properties in Fig. 2 with L being 5-element Łukasiewicz chain. Using various combinations of the hedges we obtain a smooth transition in size of the associated fuzzy rough concept lattice going from 10 concepts up to 498 (see Tab. 1). When the 5-element G o¨del chain is used instead, we again get a transition going from 10 concepts up to 298 (see Tab. 2). 1 2 3 4 5 6
Conclusion and further research We have shown that the L-rough concept-forming operators can be parameterized by truth-stressing and truth-depressing hedges similarly as the antitone and isotone fuzzy concept-forming operators.
Our future research includes a study of attribute implications using whose
semantics is related to the present setting. That will combine results on fuzzy
attribute implications [
Revisiting Pattern Structures for Structured
Attribute Sets Mehwish Alam1, Aleksey Buzmakov1, Amedeo Napoli1, and
Alibek Sailanbayev2? 1LORIA (CNRS – Inria NGE – U. de Lorraine), Vandoeuvre-l`es-Nancy, France 2Nazarbayev University, Astana, Kazakhstan { mehwish.alam, aleksey.buzmakov, amedeo.napoli, } @loria.fr,
alibek.sailanbayev@nu.edu.kz Abstract. In this paper, we revisit an original proposition on pattern structures for structured sets of attributes. There are several reasons for carrying out this kind of research work. The original proposition does not give many details on the whole framework, and especially on the possible ways of implementing the similarity operation. There exists an alternative definition without any reference to pattern structures, and we would like to make a parallel between two points of view. Moreover we discuss an efficient implementation of the intersection operation in the corresponding pattern structure. Finally, we discovered that pattern structures for structured attribute sets are very well adapted to the classification and the analysis of RDF data. We terminate the paper by an experimental section where it is shown that the provided implementation of pattern structures for structured attribute sets is quite efficient.
Keywords: Formal Concept Analysis, Pattern Structures, Structured Attribute Sets, Least Common Ancestor, Range Minimum Query. 1
Introduction
In this paper, we want to make precise and develop a section of [
Accordingly, in this paper, we will go back to the two original definitions and
show how they are related. For completing the history, it is worth mentioning
that antichains, whose intersection is the basis of the similarity operation in
the pattern structure for structured attribute sets, our paper, are studied in the
book [
Then, we proceed to present a way of efficiently working with antichains and intersection of antichains, which can be very useful, especially in case of large sets of data. The last section details a series of experiments where it is shown that pattern structures can be implemented with an efficient intersection operation and that they have a generally better behavior than scaled contexts. 2
Pattern Structures for Structured Attributes
Formal Concept Analysis [
A pattern structure is a triple (G, (D, u), δ), where G is the set of objects, (D, u) is a meet-semilattice of descriptions, and δ : G → D maps an object to its description. In other words, a pattern structure composed of a set of objects, a set of descriptions equipped with a similarity operation denoted by u. This similarity operation is idempotent, commutative and associative. If (G, (D, u), δ) is a pattern structures then the derivation operators (Galois connection) are defined as:
A := l δ(g) g∈A d := {g ∈ G|d v δ(g)} for A ⊆ G for d ∈ D Each element in D is referred to as a pattern. The natural order on (D, u), given by c v d ⇔ c u d = c is called the subsumption order. Now a pattern concept can be defined as follows: Definition 1 (Pattern Concept). A pattern concept of a pattern structure (G, (D, u), δ) is a pair (A, d) where A ⊆ G and d ∈ D such that A = d and A = d , where A is called the concept extent and d is called the concept intent.
A pattern extent corresponds to the maximal set of objects A whose descriptions subsume the description d, where d is the maximal common description for objects in A. The set of all pattern concepts is partially ordered w.r.t. inclusion on extents, i.e., (A1, d1) ≤ (A2, d2) iff A1 ⊆ A2 (or, equivalently, d2 v d1), making a lattice, called pattern lattice. 2.2
Two original propositions on structured attribute sets
We briefly recall two original propositions supporting the present study. The first
work is firstly published by Carpineto & Romano in [
In [
In other words, this intersection operation corresponds to the intersection of
two antichains as this is explained in [
{m ∈ P | ∃ac1 ∈ AC1, ∃ac2 ∈ AC2, m ≤ ac1 and m ≤ ac2}.
There is a “canonical representation context” (or an associated scaling operator) for the pattern structure (G, (D, u), δ) related to structured attribute sets, which is defined by the set of “principal ideals ↓ p” as follows: (G, P, I) with (g, p) ∈ I ⇐⇒ p ≤ δ(g).
In the next section, we make precise and discuss the pattern structure for
structured attribute sets by taking the point of view of filters and not of ideals
in agreement with the order from [
From Structured Attributes to Tree-shaped Attributes An important case of structured attributes is “tree-shaped attributes”, i.e., when the attributes are organized within a partial order corresponding to a rooted tree. If it is the case, then the root of the tree, denoted by >, can be matched against the description of any object, while the leaves of this tree are the most detailed descriptions. For example, the root can correspond to the attribute ‘Animal’ and a leaf can correspond to the attribute ‘Cat’; somewhere in between there could be attribute ‘Mammal’.
An example of such kind of data naturally appears in the domain of semantic web data. For example, Figure 1 gives a small part of ACCS1. This attribute tree will be used as a running example and should be read as follows. If an object belongs to class C1 (and probably to some other classes), then it necessarily belongs to classes C10, C12, and >, e.g., if an object is a cat, then it is a mammal and an animal. Accordingly, the description of an object can include several classes, e.g., classes C1, C5 and C8. Thus, some of the tree-shaped attributes can be omitted from the description of an object. However, they should be always taken into account when computing the intersection between descriptions. Thus, in order to avoid redundancy in the descriptions, we can allow only antichains of the tree as possible elements in the set D of descriptions, and then, accordingly compute the intersection of antichains.
An efficient way of computing intersection of antichains is explained in the next section. Here it is important to notice that although it is a hard task to efficiently compute intersection of antichains in an arbitrary partial order of attributes, the intersection of antichains in a tree can help in computing this more general intersection. Indeed, in a partial order of attributes, we can add an artificial attribute > that can be matched against any description. Then, instead of considering an intersection of antichains in an arbitrary poset we can take a spanning tree of it with > taken as the root. Although we have lost some relations between attributes, and, thus, the size of the antichains is probably larger, we can apply the efficient intersection of antichains of tree discussed below.
On Computing Intersection of Antichains in a Tree In this subsection we show how to efficiently solve the problem of intersection of antichains in a tree. The problem is formalized as follows. A partial order is 1 https://www.acm.org/about/class/2012
C12 C10
C11 >
C6 C13
C8 C1
C2
C4
C5
C7
C9
Fig. 1: A small part from ACM Computing Classification System (ACCS). described by the Hasse diagram corresponding to the tree. The root is denoted by > and it is larger w.r.t. the partial order than any other element in the tree. Given a rooted tree T and two antichains X and Y , we should find an antichain Z such that (1) for all x ∈ X ∪ Y there is z ∈ Z such that x ≤ z and (2) no z ∈ Z can be removed or changed to z˜ < z without violating requirement (1).
If the cardinality of antichains X and Y is 1 then this task is reduced to
the well-known problem of a Least Common Ancestor (LCA). In 1984 it was
already shown that the LCA problem can be reduced to Range Minimum Query
(RMQ) problem [
Reduction of LCA to RMQ. Given an array of numbers, the RMQ problem consists in efficient answering queries on the position of the minimal value in a given range (interval) of positions for this array. For example, given an array
Array [ 2 1 0 3 2 ]
Positions 1 2 3 4 5
where the first value is in position 1 and the last value is in position 5, the answer
to the query on the position of the minimal number in the range 2–4, i.e., the
corresponding part of array is [1;0;3], is 3 (the value of the 3rd element in the
array is 0 and it is the minimal value in this range). Accordingly, the position
of the minimal number in the range 1–2 (the part of the array is [2;1]) is 2. The
good point about this problem is that it can be solved in O(n) preprocessing
computational time and in O(1) computational time per one query [
In order to introduce the reduction of LCA to RMQ we need to know what is the depth of a tree vertex. The depth of a vertex in a rooted tree is the number of edges in the shortest path from that vertex to the root of the tree.
We create the array of depths of the vertices in the tree that is used as an input array for RMQ. We build this array in the following way. We traverse the tree in depth first order (see Figure 2). Every time the algorithm considers a 4 Depth array D [ 0 1 2 1 2 3 2 3 2 1 0 1 2 1 0 ] Corresponding vertex v0 v1 v2 v1 v3 v4 v3 v5 v3 v1 v0 v6 v7 v6 v0 Positions 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Fig. 2: Reducing RMQ task to LCA. Arrows show the depth first order traversal. The depth array D is accompanied by the corresponding vertices and positions. vertex, i.e., the first visit or a return to the vertex, we should put the depth of that vertex at the end of the depth array D. We also keep track of a vertex corresponding to each depth in D. The depth array D has 2|T | − 1 values, where |T | is the number of vertices in the tree.
Now for any value in D we know the corresponding vertex of the tree and
any vertex of the tree is associated with several positions in D. For example, in
Figure 2 the value in the first position of D, i.e., D[
Given two vertices A, B ∈ T , let a be one of the positions in D corresponding to vertex A, let b be one of the positions in D corresponding to B. Then it can be shown that the vertex corresponding to the minimal value in D in the range a–b is the least common ancestor of A and B. For example, to find LCA between vertices 3 and 6 in Figure 2, one should first take two positions in D corresponding to vertices 3 and 6. Positions 5,7, and 9 in array D correspond to vertex 3, positions 12 and 14 correspond to vertex 6. Thus, we can query RMQ for ranges 5–14, 7–14, 7–12, etc. The minimal value in D for all these ranges is 0 located at position 11 in D, i.e., RMQ(5, 14) = 11. Thus, the vertex corresponding to position 11, i.e., vertex 0, is the least common ancestor for vertices 3 and 6.
Let us notice that if A ∈ T is an ancestor of B ∈ T and a and b are two positions corresponding to the vertices A and B, then the position RMQ(a, b) in D always corresponds to the vertex A, in most of the cases RMQ(a, b) = a. Thus we are also able to check if a vertex of T is an ancestor of another vertex of T .
Now we know how to solve the LCA problem in O(|T |) preprocessing computational time and O(1) computational time per query. Let us return to the problem of intersecting antichains of a tree.
Antichain intersection problem. Let us first discuss the naive approach to this problem. Given two antichains A, B ⊂ T , one can compute the set D [ 0 1 2 3 2 3 2 1 2 3 2 3 2 1 0 1 2 3 2 3 2 3 2 1 0 ] > C12 C10 C1 C10 C2 C10 C12 C11 C4 C11 C5 C11 C12 > C6 C13 C7 C13 C8 C13 C9 C13 C6 > 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Fig. 3: Depth array, the corresponding vertices, and indices for the tree in Figure 1. {LCA(a, b) | ∀a ∈ A and ∀b ∈ B}. Then this set should be filtered for removing the comparable elements in order to get an antichain. It is easy to see that the result is the intersection of A and B but it requires at least |A|·|B| operations.
Let us reformulate this naive approach in terms of RMQ. Given a depth array D and two sets of indices A, B ⊆ N|D| forming an antichain, we should compute the set Z = {RMQ(a, b) | ∀a ∈ A and ∀b ∈ B} and then remove all elements z ∈ Z such that there is x ∈ Z \ {z} with the position RMQ(z, x) corresponding to the same vertex as z, i.e., elements z corresponding to an ancestor of another element from Z.
Let us consider for example the tree T given in Figure 1. Figure 3 shows the depth array, the corresponding vertices, and indices of this array. Let us show how to compute the intersection of A = {C1, C5, C8} and B = {C1, C7, C9}. The expected result is {C1, C13}. First we translate the sets A and B to the indices in array D for RMQ, i.e., A = {4, 12, 20} and B = {4, 18, 22}. Then we compute RMQ for all pairs from A and B:
{RMQ(4, 4) = 4, RMQ(4, 18) = 15, RMQ(4, 22) = 15, · · · , RMQ(20, 18) = 19, · · · }. Now we should remove positions corresponding to ancestors in the tree, e.g., RMQ(4, 15) = 15 and, hence, 15 should be removed. The result is {4, 13} representing exactly {C1, C13}.
Let us discuss two points that help us to reduce the complexity of the naive
approach. Consider the positions i ≤ l ≤ m ≤ j and k = RMQ(i, j), n = RMQ(l, m).
Then the depth in the position k is not larger than the depth in the position
n, D[k] ≤ D[n]. Hence the position RMQ(k, n) corresponds to the same vertex as
position k. For example, in Figure 3 RMQ(4, 6) = 5 and RMQ(2, 7) = 2. The value
in position 5 in the array D is D[
Thus, given two sets of indices A, B ⊆ N|D| corresponding to antichains, we can modify the naive algorithm by ordering the set A ∪ B and computing RMQ only for consecutive elements from different sets, rather then for all pairs from different sets. For example, for intersecting A = {4, 12, 20} and B = {4, 18, 22}, we join them to the set Z = {4A, 4B, 12A, 18B, 20A, 22B}. Then, we compute RMQ only for consecutive elements from different sets, i.e., RMQ(4, 4) = 4, RMQ(4, 12) = 8, RMQ(12, 18) = 15, RMQ(18, 20) = 19, and RMQ(20, 22) = 21. The cardinality of A ∪ B is less then |A| + |B|, hence, the number of the consecutive elements is O(|A| + |B|), and, thus, the number of RMQs of consecutive elements is O(|A| + |B|).
However, the set Z of RMQs of consecutive elements does not not necessarily correspond to an antichain in T . Thus we should filter this set, in order to remove all ancestors of another elements form Z. Accordingly, it is clear that to filter the set Z it is enough to check only consecutive elements of Z. For example, the intersection of A = {4, 12, 20} and B = {4, 18, 22} gives us the following set Z = {4, 8, 15, 19, 21}. Let us now check the RMQs of consecutive elements. RMQ(4, 8) = 8, thus, 8 is an ancestor of 4 and 8 can be removed. Since 8 is removed, we compare RMQ(4, 15) = 15, thus, 15 should be also removed. Then we compute RMQ(4, 19) = 15, i.e., the indices 4 and 19 are not ancestors and both are kept. Now we compute RMQ(19, 21) = 19 and, thus, 19 should be removed (actually positions 19 and 21 correspond to the same vertex C13 and one of them should be removed). Thus, the result of intersecting A and B is {4, 21} corresponding to the antichain {C1, C13}.
Since the number of elements in the set Z is O(|A| + |B|), then overall complexity of computing intersection for two antichains A, B ⊂ T of a tree T is O(|A| + |B|) or, taking into account that the cardinality of an antichain in a tree is less then the number of leaves (vertices having no descendants) in this tree, the complexity of computing intersection of two antichains is O(|Leaves(T )|). Antichain intersection by scaling. An equivalent approach for computing intersection of antichains is to scale the antichains to the corresponding filters. A filter corresponding to an antichain in a poset is the set of all elements of the poset that are larger then at least one element from the antichain. For example, let us consider a tree-shaped poset in Figure 1. A filter corresponding to the antichain {C1, C5, C8} is the set of all ancestors of all elements from the antichain, i.e., it is equal to {C1, C10, C12, >, C5, C11, C8, C13, C6}.
The set-intersection of filters corresponding to the given antichains is a filter corresponding to the antichain resulting from intersection of the antichains. However this approach has a higher complexity. Indeed, the size of a filter is O(|T |) and, thus, the computational complexity of intersecting two antichains by means of a scaling is O(|T |) which is harder then O(|Leaves(T )|) for intersecting antichains directly. Indeed, the number of leaves in a tree can be dramatically smaller than the number of vertices in this tree. For example, the number of vertices in Figure 1 is 13, while the number of leaves is only 7. Thus, the direct intersection of antichains is more efficient than the intersection by means of a scaling procedure.
Relation to intersection of antichains in partially ordered sets of attributes. As it was mentioned in the previous section, the intersection of antichains in arbitrary posets can be reduced to the intersection of antichains in a tree. However, the size of the antichain representing a description of an object can increase. Indeed, since we have reduced a poset to a tree, some relations have been lost, and thus the attributes that are subsumed in the poset for a given antichain A are no more subsumed in the tree for A, and hence should be added to A. However, the reduction is still more computationally efficient than
(a) Real data experiments. (b) Numerical data experiments.
Dataset
BK
LO
NT
PO
PT
PW
PY
QU
TZ
VY
computing the intersection of antichains in a poset by means of a scaling as it
is discussed in the previous paragraph. However, for the reduction it could be
interesting to find the spanning tree with the minimal number of leaves.
Unfortunately, this is an NP-complete task and it thus cannot be applied for increasing
the computational efficiency [
Experiments and Discussion Several experiments are conducted using publicly available data on a MacBook with a 1.3GHz Intel Core i5, 4GB of RAM running OS X Yosemite 10.3. We have used FCAPS2 software developed in C++ for dealing with different kinds of pattern structures. It can build a concept lattice starting from a standard formal context or from object descriptions given as antichains of a given tree. The last one is based on the similarity operation that is discussed above.
We performed our experiments on two datasets from different domains namely DBLP and biomedical data. In these datasets, object descriptions are given as subsets of attributes. A taxonomy of the attributes is already known based on domain knowledge. We compute a concept lattice in two different ways. In the first one, we directly compute the concept lattice from the antichains in a taxonomy. In the second one we scale every description to the corresponding filter of the taxonomy. After this we do not rely on the taxonomy and process the scaled context with standard FCA.
The first data set is DBLP, from which we extracted a subset of papers with their keywords published in conferences in Machine Learning domain. The taxonomy used for classifying such kind of triples is ACM Computing Classification System (ACCS)3.
The second data set belongs to the domain of life sciences. It contains information about drugs, their side effects (SIDER4), and their categories (DrugBank5). The taxonomies related to this dataset are MedDRA 6 for side effects and MeSH7 for drug categories.
The parameters of the datasets and the computational results are shown in Table 1a. It can be noticed that for DBLP the context consists of 5293 objects and 33207 attributes, in the taxonomy of the attributes we have 33198 leaves meaning that most of attributes are mutually incomparable. It took 45 seconds to produce a lattice having 10134 concepts directly from the descriptions given by antichains of the taxonomy. To produce the same lattice starting from a scaled context the program only takes 21 seconds. However, if we consider the biomedical data, the approach based on antichains is better. Indeed, it takes 145 seconds, while the computation starting from the scaled contexts takes 162 seconds. In this case, the dataset contains 1490 attributes with 933 leaves. Thus, the direct approach works faster if the number of leaves is significantly smaller than the number of vertices. It is worth noticing that the size of antichains is significantly smaller than the size of the filters, and thus our approach is more efficient. However, when the number of leaves is comparable to the number of vertices, our approach is slower. Although in this case our approach has the same 2 https://github.com/AlekseyBuzmakov/FCAPS 3 https://www.acm.org/about/class/2012 4 http://sideeffects.embl.de/ 5 http://www.drugbank.ca/ 6 http://meddra.org/ 7 http://www.ncbi.nlm.nih.gov/mesh/ computational complexity as the scaling approach, the antichain intersection problem requires more efforts than the set intersection.
Since the efficiency of the antichain approach is high for the trees with a low number of leaves, we can use this method to increase efficiency of standard FCA for special kind of contexts. In a context (G, M, I) an attribute m1 can be considered as an ancestor of another attribute m2 if any object containing the attribute m2 also contains the attribute m1. Accordingly we can construct an attribute tree T and rely on it for computing intersection operation. In this case the set of attributes M and the set of vertices of T are the same and |M | = |T |. The second part of the experiment was based on this observation.
We used numerical data from Bilkent University in the second part of the
experiments8. It was converted to formal contexts by the standard interodinal
scaling. The scaled attributes are closely connected, i.e., there are a lot of pairs
of attributes (m1, m2) such that the set of objects described by m1 is a subset
of objects described by m2, i.e., (m1)0 ⊆ (m2)0. Thus, we can say that m1 ≤ m2.
Using this property we built attribute trees from the scaled contexts. These
trees have many more vertices than leaves, thus, the approach introduced in this
paper should be efficient. We compare our approach with the scaling approach.
Moreover, recently, it was shown that interval pattern structures (IPS) can be
efficiently used to process such kind of data [
The results are shown in Table 1b. Compared to Table 1a it has several additional columns. First of all, since for numerical data we typically got large lattices, in most of the cases we considered only part of the objects. The actual number of used objects is given in the column |G|, while the total size of the dataset is given in the column ‘#objects’, e.g., BK dataset contained 96 objects, while we have used only 35. In addition for every dataset we also provide the number of the numerical attributes, e.g., BK has 5 numerical attributes. We should notice that when we built the lattice from some datasets by standard FCA, the lattice was so large that the memory was swapping and we stopped the computation. It was not the case for our approach since antichains requires less memory to store than the corresponding filters. The fact of swapping is shown by ‘*’ next to computational time in column tK. In addition we also show the time for IPS to process the same dataset. For example, the processing of BK dataset took 37 seconds by our approach, took more than 42 seconds by standard FCA and memory had started swapping, and took 19 seconds by IPS.
This experiment shows that our approach takes not only less time to compute concept lattice, but also requires less memory, since there is no memory swapping. We can also see that the computation time for IPS is smaller than for our approach. However, IPS is only applicable for numerical data, while our approach can be applied for all cases when attributes of a context are structured. For example, we can deal with graph data scaled to the set of frequent subgraphs where many such attributes are subgraphs of other attributes. 8 http://funapp.cs.bilkent.edu.tr/DataSets/
Conclusion In this paper we recalled two approaches for dealing with structured attributes and explained how we can compute intersection of antichains in tree-shaped posets of attributes, an essential operation for working with structured attributes. Our experiments showed the computational efficiency of the proposed approach. Accordingly, we are interested in applying our approach to other kinds of data such as graph data. Moreover, the generalization of our approach to other kinds of posets is also of high interest.
References Adaricheva, Kira, 217 Akhmatnurov, Marat, 99 Alam, Mehwish, 23, 241 Albano, Alexandre, 73 Antoni, Ľubomír, 147 Bartl, Eduard, 229 Borchmann, Daniel, 181 Buzmakov, Aleksey, 241 Cabrera, Inmaculada P., 147 Chornomaz, Bogdan, 73 Cleophas, Loek, 87 Cordero, Pablo, 217 Derras, Mustapha, 111 Deruelle, Laurent, 111 Dubois, Didier, 3 Enciso, Manuel, 217 Gnatyshak, Dmitry V., 47 Huchard, Marianne, 111 Ignatov, Dmitry I., 47, 99
Lumpe, Lars, 171 Makhalova, Tatyana P., 59 Miclet, Laurent, 159 Miralles, André, 111 Molla, Guilhem, 111 Mora, Angel, 217 Napoli, Amedeo, 23, 241 Nebut, Clémentine, 111 Nicolas, Jacques, 159 Nourine, Lhouari, 9, 123 Nxumalo, Madoda, 87 Ojeda-Aciego, Manuel, 147 Osmuk, Matthieu, 23 Pasi, Gabriella, 1 Priss, Uta, 135 Quilliot, Alain, 123 Ramon, Jan, 7 Revenko, Artem, 35 Rodríguez-Lorenzo, Estrella, 217 Sailanbayev, Alibek, 241 Schmidt, Stefan E., 171 Toussaint, Hélène, 123 Uno, Takeaki, 5 Watson, Bruce W., 87 Zudin, Sergey, 47 CLA 2015, Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications
50