% by Mirella M. Moro; version: September/03/2010 @ 6:04pm % -- 09/03/2010: bib file with names for proceedings and journals; cls with shrinked {received} % -- 08/27/2010: appendix, table example, more explanation within comments, editors' data \documentclass[jidm,a4paper]{jidm} % NOTE: JIDM is published on A4 paper \usepackage{graphicx,url} % for using figures and url format \usepackage[T1]{fontenc} % avoids warnings such as "LaTeX Font Warning: Font shape 'OMS/cmtt/m/n' undefined" \usepackage[latin1]{inputenc} %\usepackage{cite} % NOTE: do **not** include this package because it conflicts with jidm.bst % Standard definitions \newtheorem{theorem}{Theorem}[section] \newtheorem{example}{Example}[section] \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newdef{definition}[theorem]{Definition} \newdef{remark}[theorem]{Remark} \newenvironment{latexcode} {\vspace{0.1in}\setlength{\parindent}{18pt}} {\vspace{0.1in}} % ALL FIELDS DOWN TO BEGIN{document} ARE MANDATORY % The following data (volume, number and page) are given by the editors prior to publishing your paper \jidmVolume{1} \jidmNumber{3} \jidmYear{10} \jidmMonth{October} \setcounter{page}{1} % Includes headers with simplified name of the authors and paper title \markboth{N. F. F. Silva and S. de Amo} {\textbf{\textit{CPrefMiner}}: A Bayesian Miner of Conditional Preferences} % -> \markboth{}{} % takes 2 arguments % ex: \markboth{M. M. Moro}{Any paper title} % Title of the paper \title{\textit{CPrefMiner}: A Bayesian Miner of Conditional Preferences} % List of authors %IF THERE ARE TWO or more institutions, please use: %\author{Name of Author1\inst{1}, Name of Author2\inst{2}, Name of Author3\inst{2}} \author{N\'adia F\'elix F. da Silva, Sandra de Amo} %Affiliation and email \institute{Universidade Federal de Uberl\^andia, Brazil \\ Faculdade de Computa\c c\~ao\\ \email{nadia.felix@gmail.com, deamo@ufu.br} % IF THERE IS ANOTHER INSTITUTION: %\and Name_of_the_second_institution \\ %\email{address@whatever.com} } % Paper abstract - it should be from 100 to 300 words \begin{abstract} Customizing database queries through the use of user pre\-fe\-ren\-ces is a research topic that has been raising a lot of interest within the database community in recent years. Such preferences are used for sorting and selecting the best tuples, those which most fulfill the user wishes. A topic of interest within this context is the elicitation of preferences, consisting of methods to enable the user to inform his choice on pairs of objects belonging to a database. Depending on the size of the database, this task may require a great effort from the user, and consequently may discourage him/her to use the system. In this paper, we propose a first step towards the design and implementation of an automatic tool for inferring preferences from a given sample of user preferences. Our method \textit{CPrefMiner} we propose is based on the framework of Bayesian Networks and aims at mining a special kind of preferences, the \textit{conditional preferences}. The two main learning tasks accomplished by \textit{CPrefMiner} are: (1) Learning the graph underlying the conditional preference network; (2) Learning the preference probability tables associated with each node of the graph. This paper focus on the first task. \end{abstract} % ACM Computing Classification System categories \category{H. Information Systems}{H.m. Miscellaneous}{Databases} % Categories and Descriptors are available at the 1998 ACM Computing Classification System % http://www.acm.org/about/class/1998/ % -> \category{}{}{} % takes 3 arguments for the Computing Reviews Classification Scheme. % ex: \category{D.3.3}{Programming Languages}{Language Constructs and Features} % [data types and structures] % the last argument, in square brackets, is optional. % Paper keywords \keywords{preference mining, elicitation of preferences, conditional preferences, preference learning} % -> \keywords{} (in alphabetical order \keywords{document processing, sequences, % string searching, subsequences, substrings}) % THE PAPER BEGINS \begin{document} % This is optional: \begin{bottomstuff} We thank the Brazilian Research Agencies CNPq, CAPES and FAPEMIG for supporting this work. \end{bottomstuff} \maketitle %a very efficient formalism for modeling situations involving uncertainty % PAPER NEW SECTION \vspace{-0.2cm} \section{Introduction and Motivation} The development of recommendation systems has been attracting a lot of interest in several application areas such as electronic commerce and marketing. In order to satisfy this demand, the database community has been studying ways of employing user preferences as a tool for customizing queries. A topic of interest in this context is the \textit{elicitation of preferences} which basically consists in providing the user a way to inform his/her choice on pairs of objects belonging to a database table, with a minimal effort for the user. Preference elicitation can be formalized under either a \textit{quantitative} or a \textit{qualitative} framework. In order to illustrate the elicitation of preferences under a quantitative form, let us suppose we are given a collection of movies and we wish to know which films are most preferred by a certain user. For this, we can ask the user to rate each movie and after that we simply select those films with the higher score. This method may be impractical when dealing with a large collection of movies. In order to accomplish the same task using a \textit{qualitative} formulation of preferences, we can ask the user to inform some generic rules that reflect his/her preferences. For example, if the user says that he/she prefers romance movies to drama movies, then we can infer a class of favorite movies without asking the user to evaluate each film individually. A qualitative framework for preference elicitation consists in a mathematical model able to express user preferences. In this paper, we consider the \textit{conditional preference rules} (cp-rules) introduced in \cite{wilson2004}. A cp-rule allows to inform the preference on the values of an attribute depending on the values of some other attributes. For example in our movie database scenario, a user can specify his/her preference concerning the attribute \textit{director} depending on the value of the attribute \textit{gender}: For movies whose director is \textit{Woody Allen} he/she prefers \textit{comedy} to \textit{suspense} and for movies from director \textit{Steven Spielberg} he/she prefers \textit{action} films to \textit{dramas}. On both frameworks for expressing preferences (quantitative or qualitative), it is important to develop strategies to avoid the inconvenience for the user to report his/her preferences explicitly, a process that can be tedious and take a long time, causing the user not always willing to provide such information. In this context, the development of preference mining techniques allowing the automatic inference of user preferences turns out to be very relevant. Prior to the development of preference mining techniques we must be aware of the following questions: (1) \textit{Whose preference we are interested in mining: a single user or a group of users preferences ?}, (2) \textit{How is formatted the data from which the user preferences will be mined} ?; (3) \textit{What model will be used for expressing the preferences we are interested in mining ?}; (4) \textit{What learning technique will be employed ?} In this work we are interested in mining the preferences of a \textit{single user}. Concerning the second question, the data will consist of a set of pair of tuples ($t_1,t_2$) provided by the user, meaning that he/she prefers $t_1$ to $t_2$. Concerning the third question, the method we propose here intends to mining conditional preference expressed by a set of cp-rules \cite{wilson2004}. And finally, concerning the fourth question, the technique for preference mining we propose in this paper is based on the bayesian network technique used in classification tasks. Like Bayesian Network classifiers, our miner technique \textit{CPrefMiner} consists in the discovering of (1) a graph and (2) a set of tables of conditional probabilities expressing the user preferences on individual attributes. We call this pair of components a \textit{preference network}. The method \textit{CPrefMiner} receives as input a set of user preferences (pairs of tuples) and infer from that a set of conditional preference rules that will be used to infer new preferences about new attributes values. This paper focus on the first discovering task, that is, we are interested firstly in proposing a tool for discovering the topology of the preference network. The mining technique we propose adapts the technique for learning bayesian network structures introduced in \cite{Cooper92abayesian}. \noindent \textbf{Main contributions.} The main contributions of this paper can be summarized as follows: (1) We introduce the \textit{preference networks} which are a graph formalism to express conditional preference rules with uncertainty; (2) We propose the technique \textit{CPrefMiner} that, given a set of pair of tuples as input is able to infer the structure (topology) of the preference network; (3) We implement the technique and test it on synthetic data. The preliminary experimental results show that \textit{CPrefMiner} is able to infer a preference network compatible with the input data distribution. \noindent \textbf{Organization.} This paper is organized as follows. In Section 2 we briefly discuss some related work concerning Conditional Preference Modeling and Reasoning as well as Preference Mining in general. In Section 3 we formalize the problem of \textit{conditional preference mining}, introducing all the necessary theorectical background. In Section 4 we present \textit{CPrefMiner}, a greedy method for constructing a preference network from a set of pairs of tuples as input. Some preliminary empirical evaluation using synthetic datasets is reported in Section 5. In Section 6 we conclude the paper and discuss future work. \vspace{-0.3cm} \section{Related Work} The research literature on preference reasoning and eliciting over objects is extensive. However, to the best of our knowledge there are no research studies involving Conditional Preference Mining techniques. \noindent \textbf{Conditional Preference Modeling and Reasoning.} The approach of CP-Nets \cite{boutilier:1999,boutilier:2004:cpnets} uses a very simple graphical model which captures users qualitative conditional preference over tuples, under a \textit{ceteris paribus} semantics. The approach of TCP-Nets \cite{brafman:2006:tcpnets} generalizes the CP-Nets by introducing the ability of expressing absolute and relative importance of attributes. The approach introduced in \cite{wilson2004} uses a logical framework for expressing conditional preference statements. It consists of a formalism in the same lines of CP-Nets but with a richer language allowing to express not only the usual CP-Nets statements but also TCP-Nets statements and more general conditional statements (called \textit{stronger conditional statements}). In the present paper, we use the formalism of \cite{wilson2004} to express cp-rules, but we restrict ourselves to the fragment of this formalism corresponding to the CP-Nets. \noindent \textbf{Preference Mining.} In \cite{KiesslingPreferenceMining} the authors propose a technique for mining user preferences whose underlying model is the \textit{pareto preference model}. In this model, preferences are not conditional, that is, preferences on values of attributes do not depend on the values of other attributes. Such preference rules are obtained from log data generated by the server when the user is accessing a site. Another approach to preference mining is presented in \cite{ChinesesSuperiorAndInferiorExamples}. In this work the authors propose using preference samples provided by the user to infer an order on any pair of tuples in the database. Such samples are classified into two categories, the \textit{superior} and \textit{inferior} samples and contain information about some preferred tuples and some non-preferred ones. From these rules, an order is inferred on the tuples in the database. The underlying preference model is the \textit{pareto preference model} as in \cite{KiesslingPreferenceMining}. In \cite{Crammer} and \cite{Cohen} algorithms for mining quantitative preferences are proposed. In this work the main goal is to find automatically a prediction rule which assigns a score to each tuple of the database. The order is obtained by ranking the scores. \noindent \textbf{Use of Bayesian Networks as a Tool for Customization.} In \cite{radde2008,radde2010} an inference engine based on Bayesian Networks is proposed. It aims at inferring user preferences about values of technical attributes (such as memory size, broadband internet connectivity, etc, in a mobile communication domain). The preference elicitation is accomplished by asking the users some simple (not technical) questions about their needs and expectations. Their answers are entered as evidence into a Bayesian Network that models the relationships of user needs and technical properties of products. The Bayesian Network is built by an expert in the domain application. It is used to infer user preferences about technical attributes values. In our work, Bayesian Network represents the conditional preference rules and is built \textit{automatically} from the preference sample provided by the user. The dependence between the attributes is discovered from the input and not provided by an expert. Moreover, the preference model underlying the work of \cite{radde2008,radde2010} is the \textit{pareto preference model} (like in \cite{KiesslingPreferenceMining,ChinesesSuperiorAndInferiorExamples}), differently from our approach which uses the conditional preference model. \vspace{-0.2cm} \section{Problem Formalization} In this section we introduce the main concepts related to the problem of mining conditional preferences and also the concepts necessary to understand the \textit{CPrefMiner} method. The main goal of a preference mining method is the ability to provide a \textit{preference relation} over a given dataset. A \textit{preference relation} on a finite set of objects $A = \{a_1, a_2,...,a_n\}$ is a strict partial order over $A$, that is a binary relation $R \subseteq A \times A$ satisfying the irreflexivity and transitivity properties. Typically, a strict partial order is represented by the symbol $<$. So if $<$ is a preference relation, we denote by $a_1 < a_2 $ the fact that $a_2$ is preferred to $a_1$. \begin{definition}[Preference Sample] \label{defi:amostrasDePreferencia} \rm Let $R(A_1,A_2,...,A_n)$ be a relational schema. Let Tup($R$) be the set of all tuples over $R$. A \textit{preference sample} over $\mathcal{H}$ is a finite set $\mathcal{H} \subset$ Tup($R$) $\times$ Tup($R$) which is \textit{consistent}, that is, if $(u,v) \in \mathcal{H}$ then $(v,u) \not \in \mathcal{H}$. Intuitively, the pair $(u,v)$ represents the fact that the user prefers \textit{the tuple $u$ to the tuple $v$}. \end{definition} \begin{example}[Preference Sample] \label{ex:amostrasDePreferencias} \rm Let $R(A,B,C,D)$ be a relational schema with attribute domains given by \textbf{dom}$(A)$ = $\{a_1,a_2,a_3\}$, \textbf{dom}$(B) = \{b_1,b_2\}$, \textbf{dom}$(C)=\{c_1,c_2\}$ and \textbf{dom}$(D)=\{d_1,d_2\}$. Let $I$ be an instance over $R$ as shown in Figure \ref{fig:tuplas}. Figure \ref{fig:amostrasDePreferencias} illustrates a preference sample over $R$, comparing some tuples of $I$. \end{example} % For the sake of simplifying the presentation of the preference samples, we transform a %sample of the form $[(u,v),0]$ into $[(v,u),1]$. We suppose that the set of preference samples informed by the user is \textit{consistent}, %that is, a set of preference samples provided by the user cannot contain samples $[(u,v),0]$ and $[(u,v),1]$ simultaneously. %Figure \ref{fig:espelhamento} shows the preference samples of Figure \ref{fig:amostrasDePreferencias} after this transformation. % \begin{figure}[!htb]\vspace*{0.1cm} %\begin{minipage}[b]{0.40\linewidth} % \centering % \includegraphics[width=1.0\textwidth]{espelhamento.png}\vspace{-0.4cm} % \caption{Simplified Preference Samples simplified} % \label{fig:espelhamento} % \end{minipage} \hfill % \scriptsize % \begin{minipage}[b]{0.60\linewidth} % \centering % \includegraphics[width=.2\textwidth]{redeComMelhorScore.png}\vspace{-0.4cm} % \caption{Preference Network $PrefNet_2$} % \label{fig:redeComMelhorScore} % \end{minipage} %\end{figure} \vspace{-0.3cm} \begin{figure}[!htb] \begin{minipage}[b]{0.40\linewidth} \centering \includegraphics[width=.70\textwidth]{tuplas.eps}\vspace{-0.4cm} \caption{An instance over $R$} \label{fig:tuplas} \end{minipage} \hfill \scriptsize \begin{minipage}[b]{0.60\linewidth} \centering \includegraphics[width=.7\textwidth]{espelhamento.eps}\vspace{-0.4cm} \caption{A set of preference samples} \label{fig:amostrasDePreferencias} \end{minipage} \end{figure} \vspace{-0.1cm} \begin{definition}[Preference Network] \rm A \textit{preference network} over a relational schema $R(A_1,...,A_n)$ is a structure $(B_S,\Im)$ where: \vspace{-0.1cm} \begin{enumerate} \item $B_S$ is a directed acyclic graph whose nodes are attributes in $\{A_1,...,A_n\}$ and the edges stands for attribute dependency. \item $\Im$ is a mapping that associates to each node of $B_S$ a conditional probability table of preferences. A conditional probability table of preferences is a finite set of conditional probabilities of the form $P[E_2|E_1]$ where (1) $E_1$ is an event of type $(A_{i_1} = a_{i_1}) \wedge \ldots \wedge (A_{i_k} = a_{i_k})$ such that $\forall j \in \{1,...,k\}$, $a_{i_j} \in$ \textbf{dom}$(A_{i_j})$, and (2) $E_2$ is an event of type ``$(B = b_1$) is preferred to ($B = b_2)$'', where $B$ is an attribute of $R$, $B \not = A_{i_j}$ $\forall j \in \{1,...,k\}$ and $b_1,b_2$ $\in$ \textbf{dom}$(B)$. \end{enumerate} \end{definition} \vspace{-0.1cm} \begin{example}[Preference Network]\rm Let $R(A,B,C,D)$ be the relational schema of Example \ref{ex:amostrasDePreferencias}. Figure \ref{fig:redePreferencias} illustrates a preference network PrefNet$_1$ over $R$. \end{example} \begin{figure}[ht] \centering \includegraphics[width=.5\textwidth]{redePreferencias.eps} \caption{Preference Network PrefNet$_1$}\vspace{-0.2cm} \label{fig:redePreferencias} \end{figure} Each conditional probability in the probability table associated to a node $X$ in the graph $B_S$ represents a degree of belief of preferring some values for $X$ to other ones, depending on the values assumed by its parents in the graph. For instance $P[D =d_1 > D = d_2|C = c_1] = 0,6$ means that the probability of $D =d_1$ be preferred to $D = d_2$ is $60\%$ given that $C = c_1$ and the probability of $D = d_2$ be preferred to $D = d_1$ is $40\%$ under the same condition $C = c_1$. In classification tasks, Bayesian Networks are used as a tool to classify tuples. In our preference mining scenario, Preference Networks will be used to compare pairs of tuples. For instance the preference network PrefNet$_1$ depicted in Figure \ref{fig:redePreferencias} allows to infer a preference ordering on tuples over $R(A,B,C,D)$. According to this ordering, tuple $t_1 = (a_2,b_2,c_1,d_1)$ is preferred to tuple $t_2 = (a_2,b_2,c_1,d_2)$. Indeed, these tuples differ only on attribute $D$ and the conditional probability $P[d_1 > d_2|C = c_1] = 0,6$ in the probability table of attribute $D$ allows to conclude that $d_1 > d_2$. Thus $t_1$ is preferred to $t_2$. Note that this information may not be originally provided the user, but just inferred by the Preference Network. The quality of a preference network as an ordering tool is measured by means of its \textit{accuracy}. In order to define the \textit{accuracy} of a preference network, we would need a rigorous definition of the \textit{strict partial order} inferred by the preference network. For lack of space, we do not provide this rigorous definition here. Nonetheless, as it will be clear in the end of this section, this definition will not be needed in the remaining sections. \vspace{-0.1cm} \begin{definition}[Accuracy of a preference network] \rm Let \textbf{PNet} be a preference network over a relational schema $R$. Let $\mathcal{H}$ be a preference sample over $R$. The \textit{accuracy} of \textbf{PNet} with respect to $\mathcal{H}$ is defined by \mbox{Acc(\textbf{PNet},$\mathcal{H}$)}= $\frac{N}{M}$, where $M$ is the cardinality of $\mathcal{H}$ and $N$ is total amount of pairs of tuples $(t_1,t_2)$ $\in$ $\mathcal{H}$ compatible to the preference ordering inferred by \textbf{PNet} on the tuples $t_1$ and $t_2$. That is, the accuracy of \textbf{PNet} with respect to $\mathcal{H}$ is the percentage of \textit{bituples} of $\mathcal{H}$ which are correctly ordered by \textbf{PNet}. \end{definition} Our Preference Mining Problem is formalized as follows: \vspace{-0.2cm} \noindent \textbf{Input:} A relational schema $R(A_1,...,A_n)$, a training preference sample $T_1$ over $R$ and a testing preference sample $T_2$ of $R$. \noindent \textbf{Output:} A \textit{preference network} $(B_S,\Im)$ over the relational schema $R(A_1,...,A_n)$ with a good accuracy with respect to $T_2$. The solution of this problem consists in: (1) producing the structure $B_S$ which reflects the interdependency among the attributes as far as preferences are concerned and (2) producing the mapping $\Im$ which reflects how some attributes influence the preference over the values of other attributes. In this paper, we tackle just the subtask (1). So, we will not be able to measure the accuracy of the output, since the probability tables are needed in order to calculate the accuracy of a network. We will need another measure to evaluate the quality of the structures returned by our method. In the next section we present the algorithm \textit{PrefK2} to solve the subtask (1) as well as a suitable measure to evaluate its output. \vspace{-0.1cm} \section{Mining the Preference Network Structure} The part of the method \textit{CPrefMiner} dedicated to discover the preference network structure is based on the algorithm \textit{K2} of \cite{Cooper92abayesian} designed to learn classic bayesian networks topology. The algorithm \textit{K2} takes as input a set of classified tuples and returns a topology (graph) that has the highest probability of reflecting the distribution of the input data. Analogously, the algorithm \textit{PrefK2} we propose takes as input a set of preference samples $\mathcal{H}$ and returns a structure $B_S$ that best reflects the distribution of $\mathcal{H}$. \textit{PrefK2} is a greedy algorithm that basically consists in generating a collection of structures and associating a \textit{score$(B_S,\mathcal{H}$)} to each structure $B_S$ generated accordingly to a heuristic. This score\footnote{adapted from the function $P(B_{S}|D)$ used in \cite{Cooper92abayesian} which corresponds to the probability of the network $B_{S}$ reflecting the distribution of data in the database $D$ of tuples.} measures how the structure $B_S$ is compatible with the probability distribution of the input preference sample $\mathcal{H}$. Before defining the measure \textit{Score$(B_S,\mathcal{H}$)} (Definition \ref{defi:score}) we need to introduce some previous notation. \begin{definition}[The natural partition]\label{naturalpartition} \rm Let A be an attribute of the relational schema $R(A_1,...,A_n)$ and $\mathcal{H}$ a preference sample over $R$. Let dom$(A,\mathcal{H})$ be the projection of $\mathcal{H}$ on the attribute $A$. We denote by $Comp(A)$ the set of pairs $(a_1,a_2) \in $ dom$(A,\mathcal{H})$ satisfying the following: (1) $a_1 \not = a_2$ and (2) there exists ($t_1,t_2$) $\in$ $\mathcal{H}$ such that $t_1 [A] =a_1$ and $t_2 [A] =a_2$ or $t_1 [A] =a_2$ and $t_2 [A] =a_1$. Let $Comp(A) = \{p_1,...,p_m\}$. For each $l \in \{1,...,m\}$ let $P_l$ = \{($t_1,t_2$) $\in$ $\mathcal{H}$ $\mid (t_1[A],t_2[A]) = p_l$\}. The set $\{P_1,...,P_m\}$ defined in this way is called the \textit{natural partition} of the preference sample $\mathcal{H}$ with respect to the attribute $A$. \end{definition} \begin{example} \rm Let us consider the preference sample illustrated in Figure \ref{fig:amostrasDePreferencias}. In this example we have $Comp(A) = \{(a1,a2),(a2,a3)\}$. Figures \ref{fig:particionamento} and \ref{fig:particaoSegundoB} illustrate the natural partitions with respect to attributes $A$ and $B$ respectively. \end{example} \begin{figure}[!hb] \begin{minipage}[b]{0.5\linewidth} % A minipage that covers half the page, width-wise \centering \includegraphics[width=.9\textwidth]{particionamento.eps}\vspace{-0.4cm} \caption{ \scriptsize Natural Partition of Comp(A)}\label{fig:particionamento} \end{minipage} \begin{minipage}[b]{0.5\linewidth} \centering \includegraphics[width=1.0\textwidth]{particaoSegundoB.eps}\vspace{-0.4cm} \small \caption{ \scriptsize Natural Partition of Comp(B)}\label{fig:particaoSegundoB} \end{minipage} \end{figure} \vspace{-0.2cm} \begin{definition}[$Score(B_S,\mathcal{H})$] \label{defi:score} \rm Let $R=\{A_1,...,A_n\}$ be a relational schema and $\mathcal{H}$ a preference sample over $R$ with cardinality $k$. Let $B_S$ be a preference network structure over $R$. For each attribute $A_i$ of $B_S$ we denote by $\pi_i$ the set of its parents in $B_S$. Let $Comp(A_i) = \{p_1,...,p_m\}$. Let us consider the natural partition $P_1 \cup ... \cup P_m$ of $Comp(A_i)$ (as described in Definition \ref{naturalpartition}). For each subset $P_l$, let us consider all instantiations $w_{il}^j$ of the parent attributes $\pi_i=\{B_1,...,B_p\}$ of $A_i$ corresponding to $P_l$ and satisfying the following condition: \\ \noindent \textbf{(*)} \ \ for each $(t_1,t_2) \in$ $w^{j}_{il}$ we have $t_1[B_1]=t_2[B_1]$,..., $t_1[B_p]=t_2[B_p]$ . We denote by $q_i^l$ the total amount of such instantiations (that is, $j \in \{1,...,q_i^l\}$). Let $N_{ijl1}$ be the number of \textit{bituples} $(t_1,t_2)$ in $P_l$ such that $(t_1[A],t_2[A])= p_l$ and such that the attributes in $\pi_i$ are instantiated as $w^{l}_{ij}$. Similarly, let $N_{ijl0}$ be the number of \textit{bituples} $(t_1,t_2)$ in $P_l$ such that $(t_2[A],t_1[A])= p_l$ and such that the attributes in $\pi_i$ are instantiated as $w^{l}_{ij}$. The function $Score(B_S,\mathcal{H})$ is defined by the equation \ref{formula:probabilidadeMelhorEstrutura}. \end{definition} \vspace{-0.6cm} \small \begin{equation} \mbox{Score}(B_S,\mathcal{H}) = \prod^{n}_{i=1}\sum^{m}_{l=1}\frac{1}{m}\prod^{q^{l}_i}_{j=1} \frac{N_{ijl1}!N_{ijl0}!}{(N_{ijl1}+N_{ijl0})!}. \label{formula:probabilidadeMelhorEstrutura} \end{equation} \normalsize The formula (\ref{formula:probabilidadeMelhorEstrutura}) has been adapted from the formula given in \cite{Cooper92abayesian} for evaluating $P(B_{S}|D)$, the probability of the bayesisan network $B_{S}$ reflecting the distribution of the database $D$ of \textbf{tuples}. In our case, Score($B_S$,$\mathcal{H})$ is related to the probability of the preference network $B_S$ reflecting the preference sample $\mathcal{H}$. \vspace{-0.1cm} \begin{example} \rm Let us consider the preference network structure $B_S$ corresponding to the preference network PrefNet$_1$ of Figure \ref{fig:redePreferencias} and the preference sample $\mathcal{H}$ illustrated in Figure \ref{fig:amostrasDePreferencias}. The attributes of $B_S$ are $\{A,B,C,D\}$. For $i=1$ (corresponding to the first attribute $A$) we have $\pi_1= \{B,D\}$ and $Comp(A)$ = $\{p_1 = (a_1,a_2), p_2 = (a_3,a_2)\}$. For $l=1$, $P_1$ is the set of \textit{bituples} corresponding to identifiers 2, 3 and 4 in Figure\ref{fig:particionamento}. We have only one instantiation for B,D satisfying condition \textbf{(*)} namely $B = b1, D = d1$, corresponding to the \textit{bituple} 4. For this unique \textit{bituple} $(t_1,t_2)$ we have $t_1[A] = a_2$ and $t_2[A] = a_1$. So, $N_{1110} = 1$ and $N_{1111} = 0$ By applying equation \ref{formula:probabilidadeMelhorEstrutura} to evaluate the score of $B_S1$ with respect to the preference sample $\mathcal{H}$ we have: %\vspace{-0.1cm} \begin{equation} \footnotesize \mbox{Score}(B_S,\mathcal{H}) = \small \frac{\frac{2!2!}{(2+2)!}}{1} \frac{\frac{2!1!}{(2+1)!}}{1} \frac{\frac{1!0!}{(1+0)!}}{1}\frac{\frac{1!0!}{(1+0)!}\frac{1!0!}{(1+0)!}}{2} = 0.0277 \end{equation} \end{example} \vspace{-0.2cm} %In calculating of the $Score(PrefNet_1,\mathcal{H})$ was obtained a value of $0.0277$. However, other networks could better reflect the samples %described in Figure \ref{fig:amostrasDePreferencias}, for example, the network of the Figure \ref{fig:redeComMelhorScore} has %$Score(PrefNet_2,\mathcal{H})=0.0833$ and for being a higher value in relation to the score earlier, this network has a higher % likely to reflect such data. %%% ATE AQUI The task of learning the preference network structure is a nontrivial task since the size of the search space of the candidate structures is exponential on the number of the attributes. \textit{PrefK2} is a greedy algorithm that restricts the search space by assuming an ordering among attributes. Our method consists in applying the algorithm several times with different orders on the attributes and then choosing the best structure, that with the higher score. The algorithm \textit{PrefK2} searches for each attribute $A_i$ a set of parents that maximizes the function $g(i,\pi_i)$ below. %We assume that all structures are likely \textit{a priori}. \small \begin{equation} g(i,\pi_i) = \sum^{m}_{l=1}\frac{1}{m}\prod^{q^{l}_i}_{j=1} \frac{N_{ij1}!N_{ij0}!}{(N_{ij1}+N_{ij0})!}. \end{equation} \vspace{-0.2cm} Figure 6 describes the algorithm \textit{PrefK2} for building the preference network structure. \vspace{-0.2cm} \begin{figure}[!htp] \label{algoCPrefMiner} \footnotesize \noindent \textbf{Input}:A set $n$ of attributes \textbf{A} = $\{A_1,...,A_n\}$, an order \textbf{A}, a preference sample $\mathcal{H}$ over the relational schema $R(A_1,...,A_n)$. \\ \noindent \textbf{Output}: A graph $B_S$ with nodes in $\{A_1,...,A_n\}$.\\ \noindent 1. \textbf{For} $i$ = 1 \textbf{to} $n$ \textbf{do}\\ \noindent 2.\ \hspace*{0.1cm} \textbf{Build} the natural partition P = $\{P_1,...,P_m\}$ for each $Comp(A_i)$\\ \noindent 3.\ \hspace*{0.1cm} $\Pi_i := \emptyset;$ $//$stores the best parents for $A_i$\\ \noindent 5.\ \hspace*{0.1cm} \textbf{For each} $P_j$ $\in$ P \\ \noindent 6.\ \hspace*{0.5cm} $\pi_i := \emptyset$;$//$stores the best parents for $A_i$ with respect to each $P_j$ $\in$ P \\ \noindent 7.\ \hspace*{0.5cm} $Score_{old}:=g(i,\pi_i);$\\ \noindent 8.\ \hspace*{0.5cm} $Proceder := \textbf{TRUE};$\\ \noindent 9.\ \hspace*{0.5cm} \textbf{While} $Proceder$ \textbf{do} \\ \noindent 10.\ \hspace*{0.8cm} Given $Z$ the set of nodes in Predecessors($A_i$) $-\pi_i$ that maximizes $g(i,\pi_i \cup \{Z\});$\\ \noindent 11.\ \hspace*{0.8cm} $Score_{new}:= g(i,\pi_i \cup \{Z\});$\\ \noindent 12.\ \hspace*{0.8cm} \textbf{If} $Score_{new}>Score_{old}$ \textbf{then}\\ \noindent 13.\ \hspace*{1.1cm} $Score_{old}:=Score_{new};$ \\ \noindent 14.\ \hspace*{1.1cm} $\pi_i:=\pi_i \cup \{Z\};$ \\ \noindent 15.\ \hspace*{1.1cm} \textbf{Else }$Proceder:= \textbf{FALSE}$\\ \noindent 16.\ \hspace*{0.5cm} $\Pi_i:= \Pi_i \cup \pi_i$ \\ \noindent 17.\ \hspace*{0.1cm} \textbf{White} ('Node:',$A_i$,'Parents of this Node', $\pi_i$ ) \caption{Algorithm \emph{PrefK2}} \end{figure} \section{Experimental Evaluation} The experiments conducted so far have been limited to the validation of the topology of the preference network. For accomplish that we developed a synthetic dataset generator which generates a set of structures with random probability tables, and for each structure $S$ creates a preference sample $\mathcal{H}_S$ statistically consistent with $S$. Our method for generating synthetic data is based on the \textit{Probabilistic Logic Sample} methodology \cite{DBLP:conf/uai/Henrion86}. The quality of the preference network \textbf{PNet} generated by the algorithm \textit{PrefK2} on the synthetic preference sample $\mathcal{H}_S$ is evaluated by comparing the values of $Score(S,\mathcal{H}_S)$ and $Score$(\textbf{PNet},$\mathcal{H}_S)$. In Figure \ref{fig:validacao}, we illustrate the validation process. \begin{figure}[!htb] \centering \includegraphics[width=.7\textwidth]{validacao.eps}\vspace{-0.4cm} \caption{Validation} \label{fig:validacao} \end{figure} The experiments have been conducted by varying the following parameters: (1) the number of nodes (8, 10, 15 and 30 attributes), (2) the size of the preference samples ($100$, $200$, $300$, $1.000$, $2.000$, $3.000$ and $10.000$), (3) the number of rules in the probability tables associated with each node (8, 10, 15, 30 and 50) and the orders of the attributes. %The tests showed that the results are closely related to the order of attributes, %and that for cases where the order among the attributes is one of the possible orders %consistent with the original network, the network obtained by our method has the same score of the original structure $S$ %( $Score(S,\mathcal{H}_S)$). The tests showed that the preference networks produced by our method \textit{CPrefMiner} is fully compatible with the distribution of the training preference sample. \section{Conclusion and Further Work} Nowadays conditional preferences are aubiquitous. They can be very relevant in situations where user preferences over the values of a particular attribute depend on his/her context (\cite{holland2004}). In this paper we introduced the formalism of the \textit{preference network} for expressing the user preferences. We proposed the algorithm \textit{PrefK2} for discovering the structure of a preference network. At the best of our knowledge, there is no technique for solving the problem of mining conditional preferences in the litterature. A lot of work remains to be done in order to make \textit{CPrefMiner} a tool for preference mining. Presently, we are working on the second task of \textit{CPrefMiner}, that is, the discovery of the preference network probability tables. This first proposal opens a wide spectrum for future research. We intend to improve the \textit{Score} function in order to obtain more refined network topologies. We also intend to propose another method for learning the network topology that takes into account the complexity of the network and where there is no need for a prior ordering of the attributes. Finally, we will test the performance of \textit{CPrefMiner} on real datasets by evaluating the accuracy of the results. For that, we will use the benchmark for personalized consultations available at \url{htp://apmd.prism.uvsq.fr/SubProject4/TestPlatform/IntegratedDB.html}. This benchmark is a relational database that integrates data for movie recommendation from the sites \textit{MovieLens} (\url{http://www.movielens.org}) and IMDB (\url{http://www.imdb.com/}). This benchmark contain data about 6040 users, 3881 films and the evaluations they gave to these films. We also are investigating other methods for mining conditional preferences inspired on techniques for pattern discovery. \bibliographystyle{jidm} \bibliography{jidm-shortpaper} % For information on how to write bibliography entries, % see file jidmb.bib \begin{received} \end{received} \end{document}