Ordering objects via attribute preferences

          Inma P. Cabrera1 , Manuel Ojeda-Aciego1 , and Jozef Pócs2
                   1
                    Universidad de Málaga. Andalucı́a Tech. Spain?
               2
                   Palacký University, Olomouc, Czech Republic, and
                   Slovak Academy of Sciences, Košice, Slovakia??



      Abstract. We apply recent results on the construction of suitable or-
      derings for the existence of right adjoint to the analysis of the following
      problem: given a preference ordering on the set of attributes of a given
      context, we seek an induced preference among the objects which is com-
      patible with the information provided by the context.


1   Introduction

The mathematical study of preferences started almost one century ago with the
works of Frisch, who was the first to write down in 1926 a mathematical model
about preference relations. On the other hand, the study of adjoints was initiated
in the mid of past century, with works by Ore in 1944 (in the framework of lattices
and Galois connections) and Kan in 1958 (in the framework of category theory
and adjunctions). The most recent of the three theories considered in this work
is that of Formal Concept Analysis (FCA), which was initiated in the early 1980s
by Ganter and Wille, as a kind of applied lattice theory.
    Nowadays FCA has become an important research topic in which a, still
growing, pure mathematical machinery has expanded to cover a big range of
applications. A number of results are published yearly on very diverse topics
such as data mining, semantic web, chemistry, biology or even linguistics.
    The first basic notion of FCA is that of a formal context, which can be
seen as a triple consisting of an initial set of formal objects B, a set of formal
attributes A, and an incidence relation I ⊆ B × A indicating which object has
which attribute. Every context induces a lattice of formal concepts, which are
pairs of subsets of objects and attributes, respectively called extent and intent,
where the extent of a concept contains all the objects shared by the attributes
from its intent and vice versa.
    Given a preference ordering among the attributes of a context, our contribu-
tion in this work focuses on obtaining an induced ordering on the set of objects
which, in some sense, is compatible with the context.
    After browsing the literature, we have found just a few papers dealing simul-
taneously with FCA and preferences, but their focus and scope are substantially
?
   Partially supported by Spanish Ministry of Science and FEDER funds through
   projects TIN2011-28084 and TIN12-39353-C04-01.
??
   Partially supported by ESF Fund CZ.1.07/2.3.00/30.0041.
different to ours. For instance, Obiedkov [11] considered some types of preference
grounded on preference logics, proposed their interpretation in terms of formal
concept analysis, and provided inference systems for them, studying as well their
relation to implications. Later, in [12], he presented a context-based semantics
for parameterized ceteris paribus preferences over subsets of attributes (pref-
erences which are only required to hold when the alternatives being compared
agree on a specified subset of attributes).
    Other approaches to preference handling are related to the development of
recommender systems. For instance, [8] proposes a novel recommendation model
based on the synergistic use of knowledge from a repository which includes the
users behavior and items properties. The candidate recommendation set is con-
structed by using FCA and extended inference rules.
    Finally, another set of references deal with extensions of FCA, either to the
fuzzy or multi-adjoint case, or to the rough case. For instance, in [2] an approach
can be found in which, based on transaction cost analysis, the authors explore
the customers’ loyalty to either the financial companies or the company financial
agents with whom they have established relationship. In a pre-processing stage,
factor analysis is used to choose variables, and rough set theory to construct the
decision rules; FCA is applied in the post-processing stage from these suitable
rules to explore the attribute relationship and the most important factors af-
fecting the preference of customers for deciding whether to choose companies or
agents.
    Glodeanu has recently proposed in [6] a new method for modelling users’
preferences on attributes that contain more than one trait. The modelling of
preferences is done within the framework of Formal Fuzzy Concept Analysis,
specifically using hedges to decrease the size of the resulting concept lattice as
presented in [1].
    An alternative generalization which, among other features, allows for specify-
ing preferences in an easy way, is that of multi-adjoint FCA [9,10]. The main idea
underlying this approach is to allow to use several adjoint pairs in the definition
of the fuzzy concept-forming operators. Should one be interested in certain sub-
set(s) of attributes (or objects), the only required setting is to declare a specific
adjoint pair to be used in the computation with values within each subset of
preferred items.
    The combination of the two last approaches, namely, fuzzy FCA with hedges
and the multi-adjoint approach have been recently studied in [7], providing new
means to decrease the size of the resulting concept lattices.
    This work can be seen as a position paper towards the combination of recent
results on the existence of right adjoint for a mapping f : hX, ≤X i → Y from a
partially ordered set X to an unstructured set Y , with Formal Concept Analysis,
and with the generation of preference orderings.
    The structure of this work is the following: in Section 2, the preliminary
results related to attribute preferences and the characterization of existence of
right adjoint to a mapping from a poset to an unstructured codomain are pre-
sented; then, in Section 3 the two approaches above are merged together in order
to produce a method to induce an ordering among the objects in terms of a given
preference ordering on attributes and a formal context.


2     Preliminaries

2.1   Preference relations and lectic order on the powerset

We recall the definition of a (total) preference ordering and describe an induced
ordering on the corresponding powerset.
    In the general approach to preferences, a preference relation on a nonempty
set A is said to be a binary relation  ⊆ A×A which is reflexive (∀a ∈ A, a  a)
and total (∀a, b ∈ A, (a  b) ∨ (b  a)).
    In this paper, we will consider a simpler notion, in which a preference rela-
tion is modeled by a total ordering. Formally, by a total preference relation we
understand any total ordering of the set A, i.e., a binary relation  ⊆ A × A
such that  is total, reflexive, antisymmetric (∀a, b ∈ A, a  b and b  a implies
a = b), and transitive (∀a, b, c ∈ A, a  b and b  c implies a  c).
    Any total preference relation on a set A induces a total ordering on the
powerset 2A in a natural way.

Definition 1. Let hA, i be a nonempty set with a total preference relation. A
subset X is said to be lectically smaller than a subset Y , denoted X <lec Y , if
                                                   

                         max (X r Y ) ∪ (Y r X) ∈ Y.

If X <lec Y or X = Y we will write X ≤lec Y .

It is not difficult to show that the set 2A with the lectic order forms a totally
ordered set.


2.2   Building right adjoints

We assume basic knowledge of the properties and constructions related to par-
tially ordered sets.
    As we are including the necessary definitions for the development of the
construction of adjunctions, we state below the notion of adjunction we will be
working with.

Definition 2. Let A = hA, ≤A i and B = hB, ≤B i be posets, f : A → B and
g : B → A be two mappings. The pair (f, g) is said to be an adjunction between
A and B, denoted by (f, g) : A B, whenever for all a ∈ A and b ∈ B we have

                  f (a) ≤B b      if and only if     a ≤A g(b).

The mapping f is called left adjoint and g is called right adjoint.
    Given a mapping from a poset hA, ≤A i to an unstructured set B, the nec-
essary and sufficient conditions for f to have a right adjoint were given in [5];
the idea was to build it gradually, in terms of the canonical decomposition of
f : A → B through Af , the quotient set3 of A wrt the kernel relation ≡f , defined
as a ≡f b if and only if f (a) = f (b):

                                            f
                                        A         B
                                    π              i

                                    Af      ϕ   f (A)

where mapping π is the canonical projection onto the quotient set Af , defined
by π(a) = [a]f , ϕ is the canonical isomorphism of the quotient and the image,
defined by ϕ([a]f ) = f (a), and i is the inclusion of the image into the codomain.
    The obtained characterization is recalled in the theorem below.

Theorem 1. Given a poset A = hA, ≤A i and a mapping f : A → B, let ≡f be
the kernel relation. Then, there exists a poset structure on B, say B = hB, ≤B i,
and a mapping g : B → A such that (f, g) : A       B if and only if

1. There exists max([a]f ) for all a ∈ A.
2. For all a1 , a2 ∈ A, a1 ≤A a2 implies max([a1 ]f ) ≤A max([a2 ]f ).

   If the conditions hold, a suitable ordering on the image of f (that can also
be extended to B) can be defined as follows:

          b1 ≤B b2     if and only if
                        there exist a1 ∈ f −1 (b1 ), a2 ∈ f −1 (b2 )
                                        such that max([a1 ]f ) ≤A max([a2 ]f ).

   It is worth to notice that the theorem above can be easily adapted to char-
acterize existence of Galois connections.


3     Inducing preferences

Given the results introduced in the previous section, here we will merge them so
that, given a preference relation on the set of attributes A, an induced ordering
is obtained on the set of objects B.
    In order to simplify the presentation and minimize technicalities, we will
consider a crisp context C = (B, A, I) and a total preference ordering on the set
of attributes, say hA, i.
3
    The equivalence class of a under the kernel relation ≡f will be denoted as [a]f .
    The general idea can be depicted as the diagram below

                                   hA, i           B
                                       g            o

                                                f
                                 h2A , ≤lec i       2B

each of the three stages is explained as follows:
 1. To begin with, the preference on attributes allows for generating4 the corre-
    sponding lectic order on h2A , ≤lec i.
 2. On this lattice, the usual concept-forming operator f can be defined, see [4],
    from h2A , ≤lec i to the (unstructured) powerset of objects of B. Namely, given
    A ∈ 2A we define

                       f (A) = {b ∈ B | (b, a) ∈ I for all a ∈ A}.
    Now, under suitable conditions as stated in [5], there exists an ordering on 2B
    such that a right adjoint for f exists.
 3. Finally, this ordering is projected down to B to obtain an induced ordering
    among all the objects.

    Summarizing, given a preference ordering of the set of attributes hA, i and
a context, an induced ordering on the set of objects B is obtained, which is
compatible with the context.
    It is worth to note that, by considering the inclusion ordering on 2A , the in-
clusion ordering on 2B and the (other) standard concept-forming operator forms
a Galois connection, hence the inverse inclusion ordering leads to an adjunc-
tion. This means that the proposed approach, in a certain sense, generalizes the
standard concept-forming approach.

Some illustrative examples
To begin with, Theorem 1 characterizes when an ordering can be induced in the
codomain B so that a right adjoint to a given mapping f : hA, ≤A i → B exists.
It is not difficult to find examples in which that situation does not hold.
Example 1. Consider the context C = ({o1 , o2 , o3 }, {a1 , a2 }, I), where the inci-
dence relation I is defined as in the left of Figure 1. In addition, consider that
attribute a1 is more preferred than a2 (which we denote a1  a2 ).
    For this context it is clear that Property 2 of Theorem 1 does not hold in
general. Specifically, if we consider (singleton) sets A1 = {a1 } and A2 = {a2 },
then we have A2 ≤lec A1 but, clearly, max[A2 ]f 6≤lec max[A1 ]f , i.e. A002 6≤lec A001 ,
since A002 = {a1 , a2 }, whereas A001 = {a1 }.5
4
  Hence the g, but notice that this is just a notation, not an actual mapping from A
  to 2A .
5
  See Section 3.1.
                            a1 a2                      a1 a2
                         o1 ×                       o1    ×
                         o2 ×                       o2 ×
                         o3 × ×                     o3 × ×

                                       Fig. 1.


Example 2. Consider an alternative incidence relation defined as in the right of
Figure 1. Again, consider that attribute a1 is more preferred than a2 .
    For this alternative context, the previous problem does not arise, since A002 =
{a2 } and A001 = {a1 }. Therefore, an ordering on 2B can be given which, when
projected on the set of objects B, leads to o1 ≤ o2 ≤ o3 .

    The obtained result is compatible with the information given by the incidence
relation, in that o3 has more preferred attributes than o2 and so on. Anyway,
the existence of situations in which it is not possible to induce an ordering on B
leads to the more general problem of studying conditions on the context which
guarantee its existence.
    To begin with, property 1 automatically holds in our approach; the details
are given below.

3.1   Checking Property 1
Property 1, i.e. max([A]f ) exists for all A, always holds in this framework due
to the particular definition of f as the standard concept-forming operator.
    In effect, given A ∈ 2A , the equivalence class [A]f consists of sets of attributes
whose image coincides with that of A, this is independent from the particular
ordering chosen in 2A .
    We know that, under the inclusion ordering, the closure of A, denoted A00 ,
is the maximum of [A]f : i.e. Ai ⊆ A00 for all Ai ∈ [A]f . Furthermore, as the
inclusion ordering implies lectic ordering we have that Ai ≤lec A00 for all Ai ∈
[A]f , which states that A00 is also the maximum of [A]f in the chain h2A , ≤lec i.

3.2   Checking Property 2 (a first approach to its complexity)
As shown in the previous examples, property 2 does not always hold.
    A first naive step would be simply checking Property 2 in all the pairs of
subsets A1 ≤lec A2 . Fortunately, not all of them have to be checked since the
lectic ordering contains the inclusion ordering and, for this ordering the property
holds (this is just a consequence of the fact that the usual concept-forming
operators form a Galois connection), but there are other possibilities to be taken
into account, which are pairs of sets of attributes satisfying A1 ≤lec A2 but
A1 6⊆ A2 .
    Specifically, in order to study the complexity of checking property 2 (by brute
force) we have firstly to solve the following
    Problem: Given an ordered set A = {a1 , . . . , an } with n elements, we
    want to count the pairs of subsets A1 and A2 such that A1 is lectically
    less than A2 wrt the ordering given by the subscripts of the elements
    in A, but is NOT included in it.

because those are the cases in which the property is not known to hold and,
hence, are called problematic pairs.
    For the computation, we will interpret a subset as a chain [d1 , . . . , dn ] of n
digits, indicating membership or not to the subset.
    The key idea for counting the number of problematic pairs is related to two
important places in the chain, for which we introduce a special notation:
 1. Digit d` represents the first attribute a` which is in A2 but not in A1 (the `
    should recall the first `ectic discrepancy).
 2. Digit di represents the first attribute ai which is in A1 but not in A2 , that
    is, the first discrepancy wrt the i nclusion ordering.
It is obvious that, in any given pair of subsets, d` is more preferred, i.e. occurs
before, than di .
    Now, we can state that every attribute more preferred than ai , except a` ,
either belongs to both sets or does not belong to any of them; so in every such
position only two possibilities arise (either two 1s or two 0s), this means that a
factor 2 is associated to any such digit. In addition, there is no restriction for
attributes less preferred than ai , that is, in every such position four possibilities
can occur, and this means that a factor 4 is associated to any such digit.
    In order to see the general pattern of possible cases, let us consider a set
with four attributes, so n = 4. There are three possible positions for di , namely,
second, third and fourth, which are handled separately.

i-discrepancy in 4th digit In this case, d` can be in any of the three first
    places, and the remaining two positions should have coincident values. Then,
    there are 3 · 22 possibilities.
i-discrepancy in 3th digit Now, there are only two possible positions for d` ,
    and the remaining one should have coincident values (so two possibilities).
    In the last digit there is no restriction (4 possibilities). All in all, there are
    2 · 21 · 4 cases.
i-discrepancy in 2nd digit Then d` should be the first one. There are two
    digits with no restriction, so 42 cases.

Summarizing, we have 3 · 22 · 40 + 3 · 21 · 41 + 1 · 20 · 42 possibilities.

   The previous example shows a clear pattern by which the number of prob-
lematic cases for n attributes is given by the following expression

    (n − 1) · 2n−2 · 40 + (n − 2) · 2n−3 · 41 + · · · + 2 · 21 · 4n−3 + 1 · 20 · 4n−2
                             n−1
                             X
or, in compressed form as          (n − k)2n+k−3 .
                             k=1
     This sum can be expressed in closed form as follows
         n−1
         X                              n−1
                                        X
               (n − k)2n+k−3 = 2n−3           (n − k)2k
         k=1                            k=1
                                         n−1              n−1
                                                                      !
                                         X                X
                             = 2n−3             n2k −           k2k
                                         k=1              k=1
                                              n−1         n−1
                                                                      !
                                              X           X
                                  n−3               k             k
                             =2          n          2 −         k2
                                              k=1         k=1
                             ..
                              .   sums of (arithmetic-)geometric progressions
                             = 22n−2 − n2n−2 − 2n−2

    It is clear that, as there are 22n possible pairs of subsets, the ratio between
the number of problematic pairs and the number of possible pairs tends asymp-
totically to 1/4.


4     Seeking sufficient conditions on the context

We have just seen that checking Property 2 by brute force on every problematic
pair has exponential complexity on the size of the set of attributes, therefore we
introduce in this section some possible ways to establish sufficient conditions on
the context so that the proposed approach can be applied to define an induced
ordering on the set of objects.
    To begin with, the following result states a partial sufficient condition.

Proposition 1. Consider a context such that the following conditions hold for
all pair of attributes satisfying b ≺ a (a is more preferred than b):

1. There exists an object in which b holds but a does not.
2. Whenever b implies6 a less preferred attribute, say c, then a implies c as
   well.

Then property 2 holds for all the singleton sets of attributes.

Proof. Consider ak ≺ aj , and the singletons Ak = {ak } and Aj = {aj }. It is
clear that Ak ≤lec Aj , therefore we have to show that A00k ≤lec A00j .
      By contradiction, assume that A00k 6≤lec A00j . This means that the most pre-
ferred discrepant attribute between both closures, say ad , is in A00k and not in
A00j , i.e. ad ∈ A00k r A00j .
      We will reason by cases, according to the relative position of ak and ad wrt
the preference ordering.
6
    As the usual implication of attributes.
 – It cannot occur that attribute ad is more preferred than ak , since in that case
   ad should hold in every object satisfying ak , since ad ∈ A00k rA00j , contradicting
   the first hypothesis.
 – Furthermore, it cannot be the case that ad ≺ ak either. We have once again
   that ad (now less preferred than ak ) holds in very object satisfying ak . Now,
   the second hypothesis states that ad is also implied by aj and, that is ad ∈ A00j
   which contradicts that ad ∈ A00k r A00j .
 – Finally, the case ad = ak means that aj is not a discrepant attribute; now,
   as it is the case that aj ∈ A00j , it should happen that aj ∈ A00k and, hence, ak
   should imply aj , violating hypothesis 1.
                                                                                      t
                                                                                      u
   Obviously, this proposition alone does not imply the fulfillment of property 2,
but gives a clue of a general sufficient condition, albeit too strong, which is stated
below:
Proposition 2. Consider a context with a preference ordering such that, for all
subset of attributes A, satisfying the following properties:
1. There exists an object failing to satisfy the most preferred attribute in A, but
   satisfying all the other attributes.
2. Whenever A implies an attribute, say ad , then any other subset of attributes,
   more preferred in the lectic order, implies ad as well.
Then property 2 holds.
    It is worth to introduce some comments on the conditions used in the previous
proposition.
    To begin with, the first condition makes sense: as we wish to establish an
ordering on the objects, according to a prescribed order of preference among the
attributes and information in the context, the not-so-trivial cases are precisely
those containing objects failing to satisfy most preferred attributes, but satisfy-
ing several less preferred ones. Otherwise, the user should not need any formal
tool to choose according to his/her preferences.
    Specifically, consider a context containing lines as in Figure 2, again assuming
a1 more preferred than a2 more preferred than a3 . In such a case, it might not
be clear whether to choose car 1 because it satisfies the most preferred attribute
(being cheap, but without safety measures like ABS or airbag, and without the
comfort of an air-conditioned system) or car 2 , which is not cheap but includes
safety and comfort measures.
    The second hypothesis is reasonable as well, since it somehow implies the
coherence of the preference ordering between attributes. It is worth to remark
that it is not just a technical requirement which can be avoided by considering
contexts without any implied attributes because in practical situations it can
make sense to admit certain implications. For instance, back to the previous
example of cars and its attributes, it might be convenient consider simultaneously
the attributes Automatic Climate Control (ACC) and Air Conditioned (A/C)
since, although ACC always implies A/C, it could be the case that a user would
be satisfied just with a basic A/C system.
                                Cheap ABS Airbag A/C ACC
                         ..
                          .
                       car 1     ×
                          ..
                           .
                       car 2          ×     ×     ×
                           ..
                            .

                                      Fig. 2.


5   Conclusions and future work
In this paper, we have sketched a method for inducing an ordering in the set
of objects from a preference ordering in the set of attributes which is based
on the machinery of FCA and recent results concerning the existence of right
adjoints to a given mapping. Some sufficient conditions have been given in order
to guarantee that the proposed framework can be applied to a given context.
    The problem has been stated in its simplest version, with a specification of
preferences as a total ordering, and considering a crisp context. We have just
started to scratch the surface of the problem and, to be honest, there is much
more work to be done than contributed results to the topic presented in this
paper.
    We enumerate below a number of possible alternatives to be developed in
the short and mid term:
1. Obtain weaker sufficient conditions for property 2 to hold and, if possible,
   characterize those contexts for which property 2 automatically holds. For this
   characterisation it seems crucial to obtain information about the greatest
   discrepant attribute of two given closed sets of attributes.
2. Consider general preference relations (reflexive and total) or even other ap-
   proaches to the notion of preference, see [3].
3. Consider preference relations which allow to assign weights to each attribute,
   so that the comparison between objects satisfying different sets of attributes
   can be made more in consonance with the user.
4. The previous item naturally leads to the consideration of one-sided concept
   lattices, in which it is possible to specify that objects satisfy attributes only
   to a certain degree.
   ...


References
 1. R. Belohlavek and V. Vychodil. Formal concept analysis and linguistic hedges.
    Int. J. General Systems, 41(5):503–532, 2012.
 2. S.-K. Fang, J.-Y. Shyng, W.-S. Lee, and G.-H. Tzeng. Exploring the preference
    of customers between financial companies and agents based on TCA. Knowledge-
    Based Systems, 27:137–151, 2012.
 3. P. Fishburn. Preference structures and their numerical representations. Theoretical
    Computer Science, 217:359–383, 1999.
 4. B. Ganter and R. Wille. Formal Concept Analysis: Mathematical Foundation.
    Springer Verlag, 1999.
 5. F. Garcı́a-Pardo, I. Cabrera, P. Cordero, M. Ojeda-Aciego, and F. Rodrı́guez. On
    the definition of suitable orderings to generate adjunctions over an unstructured
    codomain. Information Sciences, 286:173–187, 2014.
 6. C. V. Glodeanu. Exploring users’ preferences in a fuzzy setting. Electronic Notes
    in Theoretical Computer Science, 303:37–57, 2014. Proceedings of the Workshop
    on Algebra, Coalgebra and Topology (WACT 2013).
 7. J. Konecny, J. Medina, and M. Ojeda-Aciego. Multi-adjoint concept lattices with
    heterogeneous conjunctors and hedges. Annals of Mathematics and Artificial In-
    telligence, 2014. Accepted. http://dx.doi.org/10.1007/s10472-014-9405-y.
 8. X. Li and T. Murata. A knowledge-based recommendation model utilizing formal
    concept analysis and association. In 2nd Intl Conf on Computer and Automation
    Engineering (ICCAE), pages 221–226, 2010.
 9. J. Medina and M. Ojeda-Aciego. Multi-adjoint t-concept lattices. Information
    Sciences, 180(5):712–725, 2010.
10. J. Medina, M. Ojeda-Aciego, and J. Ruiz-Calviño. Formal concept analysis via
    multi-adjoint concept lattices. Fuzzy Sets and Systems, 160(2):130–144, 2009.
11. S. Obiedkov. Modeling preferences over attribute sets in formal concept analysis.
    In F. Domenach, D. Ignatov, and J. Poelmans, editors, Formal Concept Analysis,
    volume 7278 of Lecture Notes in Computer Science, pages 227–243. Springer Berlin
    Heidelberg, 2012.
12. S. Obiedkov. Modeling ceteris paribus preferences in formal concept analysis. In
    P. Cellier, F. Distel, and B. Ganter, editors, Formal Concept Analysis, volume 7880
    of Lecture Notes in Computer Science, pages 188–202. Springer Berlin Heidelberg,
    2013.