% by Mirella M. Moro; version: January/18/2012 @ 04:16pm
% -- 01/18/2012: more discussion on SBBD + JIDM; overall revision
% -- 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[T1]{fontenc}   % avoids warnings such as "LaTeX Font Warning: Font shape 'OMS/cmtt/m/n' undefined"
\usepackage{graphicx,url}  % for using figures and url format
\usepackage{epsf}
%\usepackage[dvips]{epsfig,graphicx}
\usepackage{subfigure}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{colortbl}

%\usepackage{cite} % NOTE: do **not** include this package because it conflicts with jidm.bst

% Standard definitions
\newtheorem{theorem}{Theorem}[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}
\newcommand{\up}[1]{\raisebox{1.3ex}[0pt]{#1}} 

% New environment definition
\newenvironment{latexcode}
{\ttfamily\vspace{0.1in}\setlength{\parindent}{18pt}}
{\vspace{0.1in}}

% ALL FIELDS UNTIL BEGIN{document} ARE MANDATORY

% The following data (volume, number and page) are given by the editors prior to publishing your article
\jidmVolume{3}
\jidmNumber{3}
\jidmYear{12}
\jidmMonth{October}
\setcounter{page}{1}

\begin{document}

% Includes headers with simplified name of the authors and article title
\markboth{Bruno Paes, Alexandre Plastino, Alex Freitas}
{Improving Local Classifier Per Level Hierarchical Classification}
%  -> \markboth{}{}
%         takes 2 arguments
%         ex: \markboth{M. M. Moro}{Any article title}


% Title of the article
\title{Improving Local Per Level Hierarchical Classification}


% 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{Bruno C. Paes\inst{1}, Alexandre Plastino\inst{1}, Alex A. Freitas\inst{2}}

%Affiliation and email
\institute{Universidade Federal Fluminense, Brazil \\ \email{\{bpaes, plastino\}@ic.uff.br}
% IF THERE IS ANOTHER INSTITUTION:
%\and Name_of_the_second_institution \\
%\email{address@whatever.com}
\and
University of Kent, United Kingdom \\ \email{a.a.freitas@kent.ac.uk}
}


% Article abstract - it should be from 100 to 300 words
\begin{abstract}

In the domain of many relevant classification problems, classes are 
organized in hierarchies, representing specialization relationships 
between them. These are the so-called hierarchical classification 
problems. Methods based on different approaches have been used 
to solve them, trying to achieve better predictive performance. 
In this work, we propose two local per level hierarchical classifiers, 
which contain distinct strategies to solve inconsistent predictions, 
common to the local per level approach. We have compared the proposed 
methods with traditional strategies from different paradigms. 
The computational experiments, conducted over 18 hierarchical classification data sets, 
showed that the proposed ideas were able to reach competitive and robust 
results in terms of prediction accuracy.

\end{abstract}


% ACM Computing Classification System categories
\category{H.2.8}{Database Applications}{Data Mining}

% 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.

% Article keywords
\keywords{classification, data mining, hierarchical classification}
%  -> \keywords{} (in alphabetical order \keywords{document processing, sequences,
%                      string searching, subsequences, substrings})


% THE ARTICLE BEGINS
% \begin{document}

% This is optional:
\begin{bottomstuff}
% similar to \thanks
% for authors' addresses; research/grant statements
The development of this work was supported by CNPq and FAPERJ research grants.
\end{bottomstuff}

\maketitle


\section{Introduction}

Classification is one of the most explored tasks in the data mining area. 
Its main objective is to predict the unknown classes of new instances, 
based on other known-class instances observed in a previous training phase. 
In the literature, most classification problems involve classes with no 
specified parent-child relationships between them. These problems are known as 
flat classification problems. By contrast, there are several problems involving classes 
organized in a hierarchical structure, defined by parent-child relationships between classes, 
where a parent class is more generic than its child classes.
These problems are known as hierarchical classification problems.

Examples of hierarchical classification problems can be found in different application areas. 
In bioinformatics, there are several works related to protein function hierarchical classification 
\cite{Costa_comparingseveral} \cite{costa_ensembles} \cite{holden_ensemble} \cite{Secker07anexperimental}. 
In text mining, documents can be categorized within hierarchical structures of subjects \cite{Dumais2000}. 
In image recognition, objects can be classified into 
hierarchical categories of geometric shapes \cite{Barutcuoglu2006}.

In hierarchical classification problems, two main types of class structures are used: 
a tree-based class hierarchy, where each class has at most one parent class, and a direct acyclic 
graph-based class hierarchy, where a child class can have multiple parent classes. Hierarchical 
classification problems can be further categorized into mandatory leaf node prediction problems, 
where every instance must be assigned a leaf class node in the hierarchy, or optional leaf node 
prediction problems, where the most specific class assigned to an instance can be at any level of the class hierarchy \cite{freitas}. 
Hierarchical classification problems can also be grouped according to the number of classes that each instance can be 
associated to. When instances have at most one class per hierarchy level, we have a single label problem. 
And when each instance can be associated to a set of classes per hierarchy level, we have a multilabel problem.

Another important issue in hierarchical classification is the trade-off between reliability and usability of predictions at different levels of class generality \cite{freitas}. In general, the closer to the root level a class prediction is, the more reliable it is, since there are fewer classes and more instances per class (simplifying the classification task) at shallower levels than at deeper levels. 
On the other hand, in general, the further from the root a class prediction is, the more useful it is to the user, since deeper classes carry more specific information than shallower classes. 

In this work, we deal with tree-based hierarchical problems, where each instance 
is associated to a single class per level of the hierarchy (single label problem) and where the prediction 
is always made at the most specific level of the class hierarchy (mandatory leaf-node prediction).

Algorithms for hierarchical classification can be divided into different categories, depending on 
whether they build a global model for the entire class hierarchy or a set of local models, where each 
model predicts a subset of classes \cite{freitas}. In this work we focus on the local classifier per 
level approach, where a flat classifier is trained, independently, for each level of the hierarchy. 
The major drawback of this approach is that classifiers at different
levels can (and often do) make inconsistent class predictions. 
E.g., a classifier at the first level could predict class 1 while a classifier at the
second level could predict class 2.2, which is inconsistent because
if an instance had class 2.2 it would necessarily have class 2, 
given the parent-child relationship between those classes.

In spite of requiring the training of a reduced number of classifiers,
one per hierarchical level, the local classifier per level approach has not been
properly addressed in the literature yet. 
Probably, this is due to the inconsistent predictions across class levels.
In this work, we propose two local per level hierarchical classification algorithms, 
with distinct strategies to solve inconsistent predictions. 
The proposed strategies are compared to other types of hierarchical algorithms across 18 datasets. 
The obtained results show the proposed strategies have a good and competitive 
predictive performance.

This article is organized as follows. Section 2 describes different approaches for hierarchical classification and 
reviews related work. In Section 3, two new algorithms for local per level hierarchical classification are proposed, 
which are the main contribution of this work. Section 4 describes the algorithms to which the proposed strategies are compared. 
Section 5 reports the results and analysis of computational experiments to evaluate the proposed algorithms. 
In Section 6, the conclusions of this work are highlighted and some future work is proposed.


\section{Hierarchical Classification Approaches and Related Work}\label{cap2.2}

In this section, we describe the hierarchical classification approaches according to the categorization described in \cite{survey}. 
This categorization criterion is related to how the hierarchical structure is explored.

\subsection{Flat Classification Approach}

The flat classification approach simplifies the hierarchical classification problem by transforming it into 
a flat classification problem. Basically, a classifier is trained to deal only with leaf classes. 
In Figure \ref{fig1}(a), the leaf nodes, which are the classes considered by the flat classification algorithm, are highlighted. 
This approach provides an indirect solution to the hierarchical classification problem, since, from a predicted leaf class,
all its ancestor classes are also assigned to the instance.

\begin{figure}[[htbp]
   \centering
   \subfigure[Flat Classification Approach] {\includegraphics[width=0.4\linewidth]{figuras/ab0.jpg}}
   \subfigure[Local Per Node Approach] {\includegraphics[width=0.4\linewidth]{figuras/ab2.jpg}}
   \subfigure[Local Per Parent Node Approach] {\includegraphics[width=0.4\linewidth]{figuras/ab3.jpg}}
   \subfigure[Local Per Level Approach] {\includegraphics[width=0.4\linewidth]{figuras/ab1.jpg}}
    \caption{Four types of hierarchical classification approaches}
    \label{fig1}
  \end{figure}
  
In \cite{Burred03}, the authors refer to this approach as "direct approach", which is considered as a global 
classifier in \cite{xiao}. In \cite{barbedo}, authors call this strategy as a bottom-up approach, since the prediction 
is given initially in leaf classes and then the ancestor classes can be inferred.

The major advantage of this approach is its simplicity, since it uses
a single flat classifier to predict a set of classes in the hierarchy. 
However, this approach has a serious disadvantage: it builds a classifier without exploiting the parent-child relationships in the hierarchy.

\subsection{Local Classification Approach}

A local classifier explores the hierarchy of classes through a local perspective. 
In \cite{survey}, local classifiers are categorized based on how they explore this local information:
local per node approach, local per parent node approach and local per level approach.

In local classifiers, class predictions in the testing phase are typically executed in a top-down fashion, that is, 
for each new instance to be classified, this approach predicts classes from the highest to the lowest
level of the hierarchy, considering, in each level, the child classes of the previous predicted class.
Hence, the local approach is often referred to as a top-down method in the literature. However, it is worth noting that this top-down procedure is adopted only during the test phase, to avoid 
inconsistent predictions, and not during the training of the 
local classifiers.

\subsubsection{Local Classifier Per Node Approach}

The local per node approach consists of training one binary classifier for each node of the class hierarchy 
(except the root node). After training, the system consists of a hierarchy of flat classifiers.
Figure \ref{fig1}(b) illustrates this kind of classifier. The dashed squares represent binary classifiers. 
In essence, each binary classifier predicts whether or not an instance belongs to its associated class.
Different criteria to define the set of positive and negative instances to build each binary classifier are discussed in \cite{Ceci07,Eisner,Fagni}.

In this approach each classifier solves just a modular binary classification problem, but, depending on the hierarchy size, a large number of classifiers must be trained. 
Another problem is related to multiple classifications obtained by the set of binary classifiers, 
allowing one instance to be associated to different classes in the same hierarchy level (horizontal inconsistency) 
or classes in different branches of the hierarchy (vertical inconsistency). 
For example, in Figure 1(b), after the classification of an instance, the binary classifiers achieved positive 
predictions for the classes 2, 2.1, 2.2 and 3.2.1. Thus, at level 2, the predicted classes 2.1 and 2.2 represent 
a horizontal inconsistency and, in addition, the predict class 3.2.1 (level 3) is not consistent with 
the predicted classes in level 2 (vertical inconsistency).

Therefore, the local per node approach must be coupled with a method to avoid vertical inconsistency 
(in single and multilabel problems) and horizontal inconsistency (in single label problems). 
We now review some local per node existing methods.

The method presented in \cite{wu}, called Binarized Structured Label Learning, is applied to a multilabel problem
and follows the idea of training a binary classifier to each class node. The classification of an instance is done 
through each branch of the hierarchy and, to avoid vertical inconsistencies, the process is stopped in 
a branch when a negative prediction is achieved.

In \cite{Dumais2000}, two local per node methods, which prevent vertical inconsistencies in multilabel problems, are proposed. 
The first method evaluates each branch of the hierarchy in a top-down fashion and, while the estimated probability of the current predicted class
is greater than a threshold, the class is assigned to the instance and the system proceeds to the next level of the hierarchy.
The second method is similar to the first one, but it assigns a class to the instance when the product of the probability of this
class and the probability of its child class is greater than a threshold.
These methods were applied in a multilabel hierarchical classification problem, of which elements were web pages.

In \cite{Barutcuoglu2006} and \cite{Valentini2009}, other methods for 
multilabel problems were proposed. The main features of these methods are: in the first work, 
the training and use of a Bayesian network and, in the second, the vertical treatment 
of inconsistencies in a bottom-up way.


\subsubsection{Local Classifier Per Parent Node Approach}

This approach consists of training a traditional flat classifier 
for each parent class of the class hierarchy. In essence, for each parent class, it is build 
a classifier that discriminates among their child classes. 
Figure \ref{fig1}(c) illustrates the local classifier per parent node approach, where the dashed squares 
represent classifiers predicting their child classes. 

This approach is also often referred to in the literature as a top-down approach. 
However, as explained earlier, this term is better used to refer to strategies to avoid inconsistent predictions in the test phase, since
the training phase is not "top-down".

In \cite{Koller}, the first local classifier per parent node method was proposed, adopting the top-down strategy in the test phase.

In \cite{Secker07anexperimental}, the authors proposed a local classifier per parent method, called Selective Classifier,
also using the top-down strategy in the test phase. For each parent node of the hierarchy, different classifiers are built
using a subset of the training set and then evaluated on the other part of the training set (the validation set). The classifier chosen  
for each parent class node is the one with the highest classification accuracy on the validation set.

In \cite{holden_ensemble}, it is proposed an improvement over the Selective Classifier. 
This proposal also builds different classifiers for each parent node, however,
the evaluation is done globally, looking for the group of classifiers that presents the best performance.
Additionally, in \cite{Secker}, it was proposed the execution of an attribute selection procedure 
before building the classifiers associated to each parent node.


\subsubsection{Local Classifier Per Level Approach}

This approach consists of training a flat classifier for each level of the class hierarchy. 
Figure \ref{fig1}(d) illustrates this approach. For each level of the hierarchy, there is a classifier 
responsible for discriminating among the classes at that level.

This approach has the advantage of naturally avoiding horizontal
class prediction inconsistencies (since each classifier predicts exactly one class at its level). However, it has a major
drawback: the possibility of vertical inconsistencies.
For example, considering the hierarchy in Figure \ref{fig1}(d), it is possible that class 3 is predicted at level 1, class 2.1 predicted at level 2, and class 3.2.1 predicted at level 3. 
In this case, the class predicted at the second level is not consistent with the classes predicted at the first and third levels.

In \cite{clare,Costa_comparingseveral}, this approach was used as a baseline in the evaluation of other hierarchical 
classifiers by comparing the outputs obtained at each level, without dealing with inconsistencies.

In order to make this approach useful, it is necessary to complement it with a post-processing method 
that tries to correct inconsistent predictions. The main contribution of this work is the proposal of two local classifier per level methods coupled with two distinct post-processing strategies. It is worth noting that, to the best of our knowledge, there is no local classifier per level method in the literature that has a specific procedure to handle inconsistency of class predictions.


\subsection{Global Classification Approach}

Global classifiers basically build a single classification model taking into account the class hierarchy as 
a whole during a single run of the classification method. This approach is often referred to as the 
big-bang approach \cite{Costa_comparingseveral,freitas}.

This approach has the ability to take into account all the classes in the hierarchy in a single training process, 
unlike the local approaches which divide the training phase in modular processes, considering parts of the hierarchy. Consequently, the global approach has the disadvantage of implementing a non-modular process, resulting in a more complex hierarchical classification algorithm.

In \cite{rocchio71}, the author proposed a global classifier where a new instance is assigned to 
the nearest class, by evaluating a distance function between the instance and each class in the hierarchy.
In \cite{Labrou99}, it is presented a multilabel system to classify web pages. In essence, during the test phase, 
each page is compared, through a similarity measure, with each category in the hierarchy. 
If the similarity value is above a threshold, the web page is associated with the category.

Another way of building global classifiers consists of modifying existing traditional flat classifiers 
to make them able to consider the hierarchical structure of classes. In \cite{clare}, it was proposed a 
new version of the decision tree induction algorithm C4.5 to consider the class hierarchy (HC4.5). 
In \cite{SillaJr2009}, the authors changed the traditional Naive Bayes algorithm in order to consider 
the relationships between classes in the estimation of class probabilities.


\section{New Local Classifier Per Level Hierarchical Classification Methods} \label{cap3}

The hierarchical classifiers proposed in this article are based on the concepts of 
the local classifier per level approach, described in Section 2. 
Generally, in this approach, a flat classifier is trained and run for each level of the class hierarchy.

Figure \ref{fig2}(a) illustrates a class hierarchy with four levels where, for each level, a flat classifier was trained ($C_{1}$, $C_{2}$, $C_{3}$, $C_{4}$). 
The different classifiers, although applied at distinct levels, can be trained using the same classification algorithm. 
For example, the four classifiers $C_{1}$, $C_{2}$, $C_{3}$ and $C_{4}$ may be decision trees induced by the algorithm C4.5.

\begin{figure}[[htbp]
   \centering
   \subfigure[Flat classifier for each level] {\includegraphics[width=0.4\linewidth]{figuras/pernivel1.jpg}}
   \subfigure[Inconsistent classification] {\includegraphics[width=0.4\linewidth]{figuras/inst1.jpg}}
    \caption{Classifier Per Level Approach}
    \label{fig2}
  \end{figure}

The major drawback of this approach, as described earlier, is the occurrence of inconsistent predictions.
Figure \ref{fig2}(b) illustrates an inconsistent classification, in which the shaded nodes represent 
the outputs of the flat classifiers applied at each level. 
The classification at level 3 is not consistent with the classification at the level 2, 
since class 3.2.1 is not a descendant of class 2.1.

In order to deal with this problem, we propose strategies that decompose the 
hierarchical classification problem into a set of flat classification problems (based on the local classifier per level approach) 
and apply a post-processing inconsistency treatment. In the next subsections, we will describe the 
proposed hierarchical classifiers.


\subsection{Sum of Votes Hierarchical Classifier}

In the first proposed classifier, called Sum of Votes (SV), the class-inconsistency treatment prioritizes the branch or path
(from the root to a leaf class) which contains the greatest number of predictions -- or votes -- from the flat classifier's output. 

Initially, the strategy identifies the branches that contain at least one vote, i.e., at least one 
class predicted by one of the flat classifiers.
Considering these branches, different scenarios can occur, which will be discussed next.

Scenario 1: There is a path $P$ with a higher 
number of votes than the other paths and the class predicted at the lowest level in $P$ is a leaf class. 
In this case, for each level $N$ where the predicted class does not belong to the path $P$, 
the treatment of inconsistency replaces the predicted class at level $N$ by the class in the path $P$ belonging to the level $N$.
 
Figure \ref{fig3} shows an example of this scenario. The predicted classes for each level are (Figure \ref{fig3}(a)): 
2, 2.1, 3.2.1, and 2.1.2.1. The path with the highest number of votes contains the classes 2, 2.1, and 2.1.2.1, 
the last one being a leaf class. The predicted class in level 3 -- 3.2.1 -- does not belong to 
this path and the inconsistency elimination procedure transforms this class into the class 2.1.2 (Figure~\ref{fig3}(b)).

\begin{figure}[[htbp]
   \centering
   \subfigure[Inconsistent classification] {\includegraphics[width=0.4\linewidth]{figuras/inst1.jpg}}
   \subfigure[Inconsistency elimination] {\includegraphics[width=0.4\linewidth]{figuras/inst1_result.jpg}}
    \caption{Illustration of Scenario 1 for Sum of Votes Strategy}
    \label{fig3}
  \end{figure}

Scenario 2: There is a path $P$ with a higher 
number of votes than the other paths, as the Scenario~1, but without a leaf predicted class in $P$. 
In this case, the class-inconsistency treatment consists of two steps: 
(1) for each level $N$ higher than the lowest level that contains a predicted class in $P$, 
if the class in $N$ does not belong to $P$, the predicted class in $N$ is replaced by the class in 
the path $P$ belonging to level $N$; 
(2) for the levels below the lowest level that contains a predicted class in $P$, the classes will be determined using the local per parent top-down strategy, i.e., 
for the class node with the lowest level in $P$, a flat classifier is built taking into 
account only its child classes. 
Then this classifier chooses one of the child classes, including it in $P$. 
If this chosen class is a leaf class, the treatment is finished. 
Otherwise the process is repeated for the next level, and so on, until a leaf class is included in $P$. 

Figure \ref{fig5} illustrates this scenario. The predicted classes for each level are (Figure \ref{fig5}(a)): 
3, 1.1, 3.2.1, and 2.1.2.1. The path with the highest number of votes contains the classes 3 and 3.2.1, 
where the level 3 is the lowest level with predicted class in $P$. The strategy, in a first step, 
verifies that there is a predicted class in level 2 (1.1) which does not belong to this path 
and eliminates the inconsistency by replacing the predicted class in this level by the class 3.2 (Figure \ref{fig5}(b)). 
In the second step, the strategy performs the training of a flat classifier assigned to the non-leaf class 3.2.1, 
which chooses one class between its child classes 3.2.1.1 and 3.2.1.2. 
The output class 3.2.1.2 is included in the path $P$, and, since it is a leaf class, 
the inconsistency treatment is concluded (Figure \ref{fig5}(b)).

\begin{figure}[[htbp]
   \centering
   \subfigure[Inconsistent classification] {\includegraphics[width=0.4\linewidth]{figuras/spc2.jpg}}
   \subfigure[Inconsistency elimination] {\includegraphics[width=0.4\linewidth]{figuras/spc22.jpg}}
    \caption{Illustration of Scenario 2 for Sum of Votes Strategy}
    \label{fig5}
  \end{figure}

Scenario 3: There are multiple paths with the highest number of votes. 
In this case, the class-inconsistency treatment initially chooses, among these tied paths, the path $P$ that contains 
the predicted class in the level nearest to the root of the hierarchy. 
After choosing the path $P$, if the predicted class of the lowest level in $P$ is a leaf class, 
the procedure of Scenario 1 is used. Otherwise, the procedure of Scenario 2 is used. 

Figure \ref{fig4} presents an example of this third scenario. The predicted classes for each level are (Figure \ref{fig4}(a)): 
3, 2.1, 2.1.2, and 3.2.1.2. There are two paths with two votes: one contains the predicted classes 3 and 3.2.1.2, 
and the other, the predicted classes 2.1 and 2.1.2. 
The system initially chooses the path that contains the predicted class 3, since this class is the 
nearest class to the root. After choosing this path, the example follows the Scenario 1, because a leaf class belongs to this path. 
Hence, the class-inconsistency elimination procedure replaces the predicted classes 2.1 and 2.1.2, which do not belong to the chosen path, by the classes 3.2 and 3.2.1 (Figure \ref{fig4}(b)).

\begin{figure}[[htbp]
   \centering
   \subfigure[Inconsistent classification] {\includegraphics[width=0.4\linewidth]{figuras/inst3.jpg}}
   \subfigure[Inconsistency elimination] {\includegraphics[width=0.4\linewidth]{figuras/inst3_result.jpg}}
    \caption{Illustration of Scenario 3 for Sum of Votes Strategy}
    \label{fig4}
  \end{figure}


\subsection{Sum of Weighted Votes Hierarchical Classifier}

The second proposed hierarchical classifier, called Sum of Weighted Votes (SWV), consists of weighting the
votes considered in the previous strategy with the probabilities estimated by the flat classifiers when
predicting the classes for each level. Similarly to the SV strategy, this method identifies the branches that 
contain at least one vote and the branch that contains the largest sum of weighted votes will be adopted 
to eliminate possible inconsistencies. 
%Again, different scenarios can occur, which will be discussed next.
For this strategy, four different scenarios will be considered.
The first three scenarios are very similar to the ones defined
for the SV strategy and their description will be abbreviated whenever possible.

Scenario 1: There is a path $P$ with a higher 
sum of weighted votes than the other paths and the predicted class of the lowest level for $P$ is a leaf class.
After identifying this path $P$, the treatment of class inconsistency follows the
same procedure presented in Scenario~1 of the SV strategy. 
% In this case, for each level $N$ where the predicted class does not belong to the path $P$, 
% the treatment of class inconsistency replaces the predicted class at level $N$ by the class in the path $P$ belonging to the level $N$. 

% Figure \ref{figp1} shows an example of this scenario. The predicted classes for each level are (Figure \ref{figp1}(a)): 
% 2, 2.1, 3.2.1, and 2.1.2.1. The path with the highest sum of weighted votes (0.9 + 0.7 + 0.9) contains the classes 2, 2.1, and 2.1.2.1, 
% the last one being a leaf class. The predicted class in level 3 -- 3.2.1 -- does not belong to 
% this path and the inconsistency elimination transforms this class into the class 2.1.2 (Figure \ref{figp1}(b)).

% \begin{figure}[[htbp]
%    \centering
%    \subfigure[Inconsistent classification] {\includegraphics[width=0.4\linewidth]{figuras/inst4.jpg}}
%    \subfigure[Inconsistency elimination] {\includegraphics[width=0.4\linewidth]{figuras/inst4_result.jpg}}
%     \caption{Illustration of Scenario 1 for Sum of Probabilities Strategy}
%     \label{figp1}
%   \end{figure}
  
Scenario 2: There is a path $P$ with a higher 
sum of weighted votes than the other paths, as in Scenario 1, but without a leaf predicted class in $P$.
After identifying this path $P$, the inconsistency treatment follows the
same procedure presented in Scenario~2 of the SV strategy.  
% In this case, the inconsistency treatment consists of two steps: 
% (1) for each level $N$ higher than the lowest level that contains a predicted class in $P$, 
% if the class of $N$ does not belong to $P$, the predicted class in $N$ is replaced by the class in 
% the path $P$ belonging to level $N$; 
% (2) for the levels below of the lowest level that contains a predicted class in $P$, the classes will be determined using the 
% top-down class prediction strategy, i.e., for the class node with the lowest level in $P$, a flat classifier is built taking into account only its child classes. 
% Then this classifier chooses one of the child classes, including it in $P$. If this chosen class is a leaf class, the class-inconsistency treatment is finished.
% Otherwise the process is repeated for the next level, and so on, until a leaf class is included in $P$.

% Figure \ref{figp2} illustrates this scenario. The predicted classes for each level are (Figure \ref{figp2}): 
% 3, 1.1, 3.2.1, and 2.1.1.2. The path with the highest sum of weighted votes (0.8 + 0.7 = 1.5) contains the classes 3 and 3.2.1, 
% where the level 3 is the lowest level with predicted class in $P$. The strategy, in the first step, 
% verifies that there is a predicted class in level 2 (1.1) which does not belong to this path 
% and eliminates the inconsistency by replacing the predicted class in this level by the class 3.2 (Figure \ref{figp2} (b)). 
% In the second step, the strategy performs the training of a flat classifier assigned to the non-leaf class 3.2.1, 
% which chooses one class between its child classes 3.2.1.1 and 3.2.1.2. 
% The output class 3.2.1.2 is included in the path $P$, and, since it is a leaf class, and
% the inconsistency treatment is concluded (Figure \ref{figp2} (b)).

% \begin{figure}[[htbp]
%    \centering
%    \subfigure[Inconsistent classification] {\includegraphics[width=0.4\linewidth]{figuras/spc3.jpg}}
%    \subfigure[Inconsistency elimination] {\includegraphics[width=0.4\linewidth]{figuras/spc32.jpg}}
%     \caption{Illustration of Scenario 2 in Sum of Probabilities Strategy}
%     \label{figp2}
%   \end{figure}
  
Scenario 3: There are multiple paths with the highest sum of weighted votes. 
In this case, the class-inconsistency treatment initially chooses, among these tied paths, the path $P$ that contains
the predicted class in the level nearest to the root of the hierarchy. 
After choosing the path $P$, if the predicted class of the lowest level in $P$ is a leaf class, 
the procedure of Scenario 1 is used. Otherwise, the procedure of Scenario 2 is used. 

% Figure \ref{figp3} presents an example of this third scenario. The predicted classes for each level are (Figure \ref{figp3}(a)): 
% 3, 2.1, 2.1.2, and 3.2.1.2. There are two paths with equal sum of weighted votes: one contains the predicted classes 3 and 3.2.1.2, 
% and the other the predicted classes 2.1 and 2.1.2. 
% The system initially chooses the path that contains the predicted class 3, since this class is the 
% nearest class to the root. After choosing this path, the example follows the Scenario 1, because a leaf class belongs to this path. 
% Hence, the class-inconsistency elimination procedure replaces the predicted classes 2.1 and 2.1.2, 
% which do not belong to the chosen path, by the classes 3.2 and 3.2.1. (Figure \ref{figp3}(b)).

% \begin{figure}[[htbp]
%    \centering
%    \subfigure[Inconsistent classification] {\includegraphics[width=0.4\linewidth]{figuras/inst6.jpg}}
%    \subfigure[Inconsistency elimination] {\includegraphics[width=0.4\linewidth]{figuras/inst6_result.jpg}}
%    \caption{Illustration of Scenario 3 in Sum of Probabilities Strategy}
%     \label{figp3}
%   \end{figure}

In addition to these three scenarios, a fourth one was motivated by the case illustrated in Figure \ref{figp4}(a),
which presents the class predictions at each level of the hierarchy for a given instance. 
Consider that, in the first two levels, the classes 1 and 1.1 are the real classes of the instance. 
Notice that these two predicted classes compose a consistent class path, including a leaf node. 
However, since the local classifier per level approach always predicts classes at all levels, 
the classes 3.2.1 and 3.2.1.1, obtained for the other two levels, are also taken into account to choose 
the path with the highest sum of probabilities. 
We observe that the path formed by the classes 3.2.1 and 3.2.1.1 would be the chosen path by the strategy,
according to what was defined in Scenario 1. Therefore, considering that the instance 
belongs to classes 1 and 1.1, the strategy would force a classification error. Hence, it is necessary to define 
a fourth scenario, described below, to consider the case in which a predicted leaf class does not belong 
to the lowest level of the hierarchy.

Scenario 4: There is a path $P$ with a predicted class in level 1, 
with a predicted leaf class in level~$i$ and with predicted classes, consistent with the two previous classes,
at each level between level 1 and level $i$. 
In this case, the strategy chooses the classes in path $P$, even if there are other paths with a higher 
sum of weighted votes, and does not assign classes at the levels below the leaf class, if any. 
The path $P$ is chosen and the process is finalized.
This fourth scenario will always occur simultaneously with one of the other three.
Then it is important to define that the fourth scenario has precedence over the others and
will be applied whenever it occurs. 

Figure \ref{figp4} illustrates the fourth scenario. The predicted classes for each level are (Figure \ref{figp4}(a)): 
1, 1.1, 3.2.1, and 3.2.1.1. The class-inconsistency elimination procedure checks the existence of a path that contains 
the predicted classes 1 and 1.1, where class 1 is at the first level and its child class 1.1 is a leaf class. 
Therefore, even though there is another path with a higher sum of weighted votes, 
the strategy decides to assign to the new instance the predicted classes in this path (Figure \ref{figp4}(b)).

\begin{figure}[[htbp]
   \centering
   \subfigure[Inconsistent classification] {\includegraphics[width=0.4\linewidth]{figuras/inst7.jpg}}
   \subfigure[Inconsistency elimination] {\includegraphics[width=0.4\linewidth]{figuras/inst7_result.jpg}}
    \caption{Illustration of Scenario 4 in Sum of Weighted Votes Strategy}
    \label{figp4}
  \end{figure}


\section{Traditional Hierarchical Classifiers}\label{cap3:1}

In order to evaluate the performance of the proposed classifiers, we implemented two hierarchical classifiers based on 
traditional hierarchical approaches described in Section 2: flat classification and local classifier per parent node approaches.


\subsection{Flat on Leaves Classifier}

The implemented hierarchical classifier Flat on Leaves (FL) is based on the concepts of the flat classification approach. 
A single flat classifier is trained taking into account only the leaf classes of the hierarchy.
Therefore, the classifier outputs a leaf class and, from this predicted class, all its ancestor classes are also assigned to the instance. 

Figure \ref{figflat}(a) illustrates the implemented FL classifier. 
All leaf classes -- the lightly shaded ones -- are included in the training of the classifier. The figure shows that, 
for a given instance, the classifier predicts the leaf class 2.1.1.2 in the fourth hierarchy level.  
From this prediction, it is possible to infer the classes from upper levels. 
In this example, the FL outputs the class 2.1.1 for level 3, the class 2.1 for level 2 and, finally, 
the class 2 for level 1.


\subsection{Per Parent Top-Down Classifier}

The implemented hierarchical classifier Per Parent Top-Down (PPTD) is based on the concepts of the local classifier per parent node approach,  
in which, a flat classifier is assigned for each non-leaf class (internal node) of the hierarchy. 
Each classifier (associated with an internal class node) is essentially a flat classifier, which distinguishes between its child classes. 
In this way, PPTD builds a hierarchy of flat classifiers.

A new instance is classified in a top-down way. 
Initially, the instance is evaluated by the root node classifier, 
which assigns one of its child classes to the instance. 
Then, in the next level, the classifier associated
with the class node predicted at the previous level will
assign one of its child classes to the instance, and so on.
This process is recursively repeated until a leaf class is reached.

\begin{figure}[[htbp]
   \centering
   \subfigure[Flat on Leaves] {\includegraphics[width=0.45\linewidth]{figuras/Flat_PPTD.jpg}}
   \subfigure[Per Parent Top-Down] {\includegraphics[width=0.45\linewidth]{figuras/Flat_PPTD_2.jpg}}
   \caption{Simulating the FL and PPTD classifiers}
    \label{figflat}
  \end{figure}

Figure \ref{figflat}(b) illustrates the implemented PPTD classifier. 
Each shaded class was included in the training of the classifier assigned to its parent class.
Initially, the classifier assigned to the root node predicts the class 2. 
Then the classifier assigned to the class 2 is executed and predicts the class~2.1.  
Repeating this procedure, the classifier assigned to the class 2.1 predicts the class 2.1.1 and, 
finally, the classifier assigned to the class 2.1.1 predicts the class 2.1.1.2.

 
% \begin{figure}[[htbp]
%   \centering
%    \subfigure[Classification in level 1] {\includegraphics[width=0.45\linewidth]{figuras/topdown1.jpg}}
%    \subfigure[Classification in level 2] {\includegraphics[width=0.45\linewidth]{figuras/topdown2.jpg}}
%    \subfigure[Classification in level 3] {\includegraphics[width=0.45\linewidth]{figuras/topdown3.jpg}}
%    \subfigure[Classification in level 4] {\includegraphics[width=0.45\linewidth]{figuras/topdown4.jpg}}
%     \caption{Simulating the classifier PPTD}
%     \label{figtopdown}
%   \end{figure}


\section{Computational Experiments}\label{cap3:3}

Computational experiments were conducted in order to evaluate the performance of the proposed hierarchical classification methods.
We used 18 bioinformatics data sets, where the hierarchical classes 
to be predicted are protein or gene functions and the predictor 
attributes are protein or gene properties. 
These datasets are organized into two large groups. 

Group A contains eight data sets of protein functions. 
These data sets are divided into two main subgroups: GPCR (G-Protein-Coupled Receptor) and EC (Enzyme Commission). 
The GPCR group consists of four data sets (GPCRpfam, GPCRprints, GPCRprosite and GPCRinterpro). GPCRs are proteins that transmit
signals from outside to inside the cell, changing the cell's
behavior. The classes refer to types of GPCRs, and the different
names of the datasets indicate the different types of predictor
attributes used in each dataset, where Pfam, Prints, Prosite
and Interpro are different types of protein motifs (or protein
signatures). The EC group consists of four data sets (ECpfam, ECprints, ECprosite and ECinterpro), where the classes represent types of
enzymes. An enzyme is a type of protein that speeds up chemical
reactions.  
These data sets are available at http://www.cs.kent.ac.uk/archive/people/rpg/nh56/datasets.zip.
These data sets have been used in several works on hierarchical classification problems 
\cite{Costa_comparingseveral,costa_ensembles,freitas,holden_ensemble,survey}. 
A pre-processing procedure was performed on these data sets to remove, from each data set, instances whose most specific class was not 
a leaf class node, since in this work we focus on the problem of
mandatory leaf node prediction, as mentioned earlier.

Group B contains ten gene function data sets, which contain information related to the {\it Yeast} fungus.
These data sets are presented in \cite{clare} and were, originally, multilabel data, where some instances had two or more labels at a 
given class level. 
In order to be used in this work (where instances are assumed to have only a single label per class level), these data sets were converted into single label data by randomly choosing one class among the classes
assigned to each level for each instance, but also guaranteeing that
there was no vertical inconsistency in the chosen classes.

All data sets have the class hierarchy represented by a non-complete tree structure with four levels. 
In addition, for each instance, 
its most specific class is always assigned to a leaf node of the hierarchy.
The main characteristics of the datasets are shown 
in Table \ref{tab_bases}:
the group of each data set (Group), the data set name (Data Set), the number of classes for each level of the hierarchy (\#Classes) 
and the total number of instances in each data set (\#Instances).

\begin{table}[htbp]
\centering
\scriptsize
  \setlength{\tabcolsep}{3pt}
  \setlength{\arrayrulewidth}{1\arrayrulewidth}
\caption{Characteristics of the Data Sets}
\begin{tabular}{c|l|c|c|c|l|c|c}
\hline
& & & & & & \\ 
\up{\textbf{Group}} & \multicolumn{1}{c|}{\up{\textbf{Data Sets}}} & \up{\textbf{\#Classes}} & \up{\textbf{\#Instances}} & \up{\textbf{Group}} & \multicolumn{1}{c|}{\up{\textbf{Data Sets}}} & \up{\textbf{\#Classes}} & \up{\textbf{\#Instances}} \\ \hline
&\textbf{GPCRpfam} & 12/52/79/49 & 6524 & & \textbf{Church} & 4/18/36/27 & 1677 \\
&\textbf{GPCRprints} & 8/46/76/49 & 4880 & & \textbf{CellCycle} & 4/17/34/23 & 1711 \\ 
&\textbf{GPCRprosite} & 9/50/79/49 & 5728 & & \textbf{Derisi} & 4/18/35/25  & 1661 \\
&\textbf{GPCRinterpro} & 12/54/82/50 & 6935 & & \textbf{Eisen} & 4/15/29/17 & 1163 \\
\up{\textbf{A}}&\textbf{ECpfam} & 6/41/96/190 & 11057 & \up{\textbf{B}} & \textbf{Expr} & 4/17/34/25 & 1688 \\ 
&\textbf{ECprints} & 6/45/92/208 & 11048 & & \textbf{Gasch1} & 4/17/34/25 & 1660 \\ 
&\textbf{ECprosite} & 6/42/89/187 & 11328 & & \textbf{Gasch2} & 4/17/33/25 & 1678 \\ 
&\textbf{ECinterpro} & 6/41/96/187 & 11101 & & \textbf{Phenotype} & 4/12/21/13 & 621 \\
& & & & & \textbf{Sequence} & 4/17/32/24 & 1680 \\ 
& & & & & \textbf{SPO}  & 4/17/34/25 &  1649  \\  \hline
\end{tabular}
\label{tab_bases}
\end{table}

All hierarchical classifiers have been implemented using the JAVA programming language. 
Some functions and algorithms were imported from the data mining tool WEKA 3.7.0 
(Waikato Environment for Knowledge Analysis)\cite{Witten}. 
In order to adopt the traditional classifiers k-NN and C4.5, used in the experiments as flat classifiers, 
we used the Ibk and J48 implementations available in the WEKA tool, respectively.

We evaluated the performance of the hierarchical classifiers using the Hierarchical F-measure (HF), defined next.  
This is an adaptation of the F-measure to the hierarchical context, described in \cite{Kiritchenko05}.
 
Let $P_{i}$ be the set of classes predicted for all levels of the hierarchy for the test instance $i$ and 
$T_{i}$ be the set of true classes for all class levels for instance $i$. Let $n$ be the total number of instances. 
The Hierarchical Precision (HP) is defined by $HP = {\sum_{i}|P_{i} \cap T_{i}| } /{\sum_{i}|P_{i}|}$ and represents the 
ratio between the sum, for all instances, of the number of common classes between the sets of predicted and true classes of each instance 
and the sum, for all instances, of the number of predicted classes of each instance. The Hierarchical Recall (HR) 
is defined by $ HR ={\sum_{i}|P_{i} \cap T_{i}| } / {\sum_{i}|T_{i}|}$ and represents the 
ratio between the sum, for all instances, of the number of common classes between the sets of predicted and true classes of each instance 
and the sum, for all instances, of the number of true classes of each instance.
The Hierarchical F-measure (HF) is defined then by $ HF = {2*HP*HR} / {(HP+HR)} $ and represents the harmonic mean of HP and HR.

The evaluation of the hierarchical classifiers was performed 
using 10-fold cross-validation and the HF measure. 
We used the paired and two-tailed version of the Student's t-test \cite{book_jain}, with significance level equal to 5\%, 
to evaluate the statistical significance when comparing two hierarchical classifiers.

We first compare the performance of the two proposed hierarchical classifiers 
-- Sum of Votes and Sum of Weighted Votes -- and then we conduct the comparisons 
between the traditional hierarchical classifiers -- Flat on Leaves and Per Parent Top-Down -- 
and the proposed hierarchical classifier which achieved the best results (out of the two proposed classifiers).


\subsection{Comparing Sum of Votes and Sum of Weighted Votes Strategies}\label{cap3:4}

The proposed class-inconsistency removal strategies, Sum of Votes (SV) and Sum of Weighted Votes (SWV), 
were compared based on six different flat classifiers: 1-NN, 3-NN, 5-NN, 7-NN, 9-NN e C4.5. 
In essence, the strategies SV and SWV apply the flat classifier in each hierarchy class level and then 
execute their heuristics for class-inconsistency elimination.

In Table \ref{compabordprop}, for each combination of data set and  classifier, 
the HF measure values achieved by 10-fold cross-validation (with the standard deviation in parentheses) 
are presented. 
For each combination of dataset and classifier, the best result
(out of the two proposed class-inconsistency removal strategies) 
is shown in bold. In addition, for each dataset, the best
result across all six classifiers is shown underlined.
The symbol (\textcolor{black}{$\bullet$}) between the two HF values
(one associated with the SV and the other associated with the SWV
strategy) indicates that the 
difference between these values are statistically significant. 
The symbol (-) indicates no statistical significance. 
For example, for the data set GPRCpfam, with flat classifier 1-NN, the SWV strategy achieved HF value equal to 70.31\%, 
overcoming, with statistical significance, the SV strategy, which achieved HF value equal to 67.31\%. 
In addition, the value 70.31\% is underlined since it was the best result found for the GPCRpfam database, across the six classifiers.
Finally, below each data set group, a total row displays, for each  classifier adopted, the number of times in which 
each of the two class-inconsistency removal strategies obtained a better or equal HF value when compared to the other.

\begin{table}[!htb]
\centering
\scriptsize
  \setlength{\tabcolsep}{2pt}
  \setlength{\arrayrulewidth}{1\arrayrulewidth}
\caption{Comparison of HF values (\%) between SV and SWV class-inconsistency removal strategies}
\begin{tabular}{l|llcll|llcll|llcll}
\hline
\multicolumn{1}{c|}{\textbf{}} & \multicolumn{ 5}{c|}{\textbf{1-NN}} & \multicolumn{5}{c|}{\textbf{3-NN}} & \multicolumn{5}{c}{\textbf{5-NN}}\\
\multicolumn{1}{c|}{\up{\textbf{Databases}}} & \multicolumn{ 3}{c}{\textbf{SV}} & \multicolumn{ 2}{c|}{\textbf{SWV}} & \multicolumn{ 3}{c}{\textbf{SV}} & \multicolumn{ 2}{c|}{\textbf{SWV}} & \multicolumn{ 3}{c}{\textbf{SV}} & \multicolumn{ 2}{c}{\textbf{SWV}} \\ \hline
\textbf{GPCRpfam} & 67.31 & (1.55) & \textcolor{black}{$\bullet$} & \textbf{\underline{70.31}} & (1.52) & 66.60 & (0.94) & \textcolor{black}{$\bullet$}  & \textbf{69.72} & (1.08) & 66.44 & (1.02) & \textcolor{black}{$\bullet$}  & \textbf{69.20} & (1.32) \\ 
\textbf{GPCRprints} & 82.17 & (1.15) & \textcolor{black}{$\bullet$}  & \underline{\textbf{83.00} }& (1.20) & 81.42 & (0.79) & \textcolor{black}{$\bullet$}  & \textbf{82.09} & (0.82) & 80.41 & (0.82) & \textcolor{black}{$\bullet$} & \textbf{81.05} & (0.87) \\ 
\textbf{GPCRprosite} & 68.92 & (1.18) &\textcolor{black}{$\bullet$}  & \underline{\textbf{69.26}} & (1.19) & 67.46 & (0.92) & \textcolor{black}{$\bullet$}  & \textbf{68.05} & (0.86) & 67.66 & (0.49) & - & \textbf{67.83} & (0.58) \\ 
\textbf{GPCRinterpro} & 80.14 & (0.81) & \textcolor{black}{$\bullet$}  &\underline{\textbf{83.09}} & (0.70) & 79.85 & (0.94) & \textcolor{black}{$\bullet$}  & \textbf{82.73} & (0.91) & 79.87 & (0.91) & \textcolor{black}{$\bullet$}  & \textbf{82.15} & (0.73) \\
\textbf{ECpfam} &\underline{\textbf{98.77}} & (0.17) & - &\underline{\textbf{98.77} }& (0.17) & \textbf{98.45} & (0.33) & - & 98.44 & (0.31) & 98.27 & (0.36) & \textcolor{black}{$\bullet$}  & \textbf{98.37} & (0.33) \\
\textbf{ECprints} & 98.16 & (0.24) & - & \underline{\textbf{98.19} }& (0.24) & \textbf{97.86} & (0.25) & - & \textbf{97.86} & (0.26) & 97.63 & (0.31) & - & \textbf{97.64} & (0.30) \\ 
\textbf{ECprosite} & 98.78 & (0.27) & \textcolor{black}{$\bullet$} & \underline{\textbf{98.80}} & (0.26) & 98.66 & (0.21) & - & \textbf{98.67} & (0.20) & 98.46 & (0.27) & - & \textbf{98.47} & (0.27) \\ 
\textbf{ECinterpro} & \underline{\textbf{99.08} }& (0.29) & - & \underline{\textbf{99.08}} & (0.29) & 98.81 & (0.40) & - & \textbf{98.83} & (0.40) & 98.78 & (0.42) & - & \textbf{98.83} & (0.41) \\ \hline
\textbf{Total A} & \multicolumn{3}{c}{2} & \multicolumn{2}{c|}{\textbf{8}} & \multicolumn{3}{c}{2} & \multicolumn{2}{c|}{\textbf{7}} &\multicolumn{3}{c}{0} & \multicolumn{2}{c}{\textbf{8}}\\ \hline
\textbf{Church} & \textbf{19.70} & (1.97) &- & \textbf{19.70} & (1.97) & 19.63 & (2.19) & \textcolor{black}{$\bullet$}  & \textbf{20.27} & (1.94) & 20.27 & (2.02) & \textcolor{black}{$\bullet$}  & \textbf{20.53} & (2.18) \\ 
\textbf{CellCycle} & \textbf{24.82} & (2.34) & - & \textbf{24.82} & (2.34) & 23.77 & (3.38) & \textcolor{black}{$\bullet$}  & \textbf{24.52} & (3.59) & 27.52 & (2.46) & - & \textbf{28.15} & (2.98) \\ 
\textbf{Derisi} & \textbf{18.73} & (2.33) & - & \textbf{18.73} & (2.33) & 16.58 & (2.26) & \textcolor{black}{$\bullet$}  & \textbf{17.94} & (2.57) & 18.88 & (2.46) & \textcolor{black}{$\bullet$}  & \textbf{20.06} & (2.54) \\ 
\textbf{Eisen} & \textbf{24.54} & (2.32) & - & \textbf{24.54} & (2.32) & 23.66 & (2.87) & \textcolor{black}{$\bullet$}  & \textbf{25.19} & (3.40) & 27.36 & (3.14) & - & \textbf{28.31} & (2.95) \\ 
\textbf{Expr} & \textbf{25.62} & (3.56) & - & \textbf{25.62} & (3.56) & 22.42 & (1.48) & \textcolor{black}{$\bullet$}  & \textbf{23.44} & (1.92) & 26.37 & (2.36) & - & \textbf{27.13} & (2.63) \\ 
\textbf{Gasch1} & \textbf{28.98} & (2.01) & - & \textbf{28.98} & (2.01) & 27.29 & (1.51) & \textcolor{black}{$\bullet$} & \textbf{28.62} & (1.77) & 29.50 & (2.42) & - & \textbf{30.07} & (1.88) \\
\textbf{Gasch2} & \textbf{25.04} & (3.03) & - & 25.03 & (3.04) & 22.92 & (2.95) & - & \textbf{23.26} & (2.71) & 23.57 & (3.43) & - & \textbf{23.92} & (3.16) \\ 
\textbf{Phenotype} & 22.04 & (2.57) & - & \textbf{22.46} & (2.91) & 23.14 & (2.05) & - & \textbf{23.66} & (3.24) & 22.75 & (1.82) & - & \textbf{23.23} & (2.11) \\ 
\textbf{Sequence} & \textbf{23.08} & (3.14) & - & \textbf{23.08} & (3.14) & 21.73 & (2.25) & - & \textbf{22.38} & (2.56) & 22.22 & (2.66) & \textcolor{black}{$\bullet$}  & \textbf{22.82} & (2.69) \\ 
\textbf{SPO} & 18.49 & (2.66) & - & \textbf{18.50} & (2.68) & 17.81 & (1.60) & \textcolor{black}{$\bullet$}  & \textbf{19.15} & (1.89) & 19.42 & (2.63) & \textcolor{black}{$\bullet$}  & \textbf{19.92} & (2.73) \\ \hline
\textbf{Total B} & \multicolumn{3}{c}{8} & \multicolumn{2}{c|}{\textbf{9}} & \multicolumn{3}{c}{0} & \multicolumn{2}{c|}{\textbf{10}} &\multicolumn{3}{c}{0} & \multicolumn{2}{c}{\textbf{10}}\\ \hline

\end{tabular}

\begin{tabular}{l|llcll|llcll|llcll}
\noalign{\bigskip}
\hline
\multicolumn{1}{c|}{\textbf{}} & \multicolumn{ 5}{c|}{\textbf{7-NN}} & \multicolumn{5}{c|}{\textbf{9-NN}} & \multicolumn{5}{c}{\textbf{C4.5}}\\
\multicolumn{1}{c|}{\up{\textbf{Databases}}} & \multicolumn{ 3}{c}{\textbf{SV}} & \multicolumn{ 2}{c|}{\textbf{SWV}} & \multicolumn{ 3}{c}{\textbf{SV}} & \multicolumn{ 2}{c|}{\textbf{SWV}} & \multicolumn{ 3}{c}{\textbf{SV}} & \multicolumn{ 2}{c}{\textbf{SWV}} \\ \hline
\textbf{GPCRpfam} & 66.15 & (0.97) & \textcolor{black}{$\bullet$}  & \textbf{68.68} & (1.16) & 65.58 & (0.93) & \textcolor{black}{$\bullet$}  & \textbf{68.07} & (1.10) & \textbf{68.79} & (1.24) & \textcolor{black}{$\bullet$}  & 68.70 & (1.21) \\ 
\textbf{GPCRprints} & 80.33 & (1.07) & \textcolor{black}{$\bullet$}  & \textbf{80.86} & (1.12) & 79.75 & (0.91) & \textcolor{black}{$\bullet$}  & \textbf{80.28} & (0.89) & 78.70 & (0.83) & \textcolor{black}{$\bullet$}  & \textbf{79.33} & (0.85) \\ 
\textbf{GPCRprosite} & 66.67 & (1.03) & - & \textbf{66.83} & (1.00) & 65.95 & (0.90) & - & \textbf{66.00} & (0.87) & \textbf{67.24} & (0.85) & - & 67.08 & (1.00) \\ 
\textbf{GPCRinterpro} & 79.57 & (0.68) & \textcolor{black}{$\bullet$}  & \textbf{81.68} & (0.53) & 79.17 & (1.18) & \textcolor{black}{$\bullet$}  & \textbf{81.31} & (0.91) & 81.26 & (1.09) & \textcolor{black}{$\bullet$}  & \textbf{81.80} & (1.03) \\ 
\textbf{ECpfam} & 98.27 & (0.34) & - & \textbf{98.30} & (0.29) & \textbf{98.19} & (0.31) & - & \textbf{98.19} & (0.31) & 98.42 & (0.23) & - & \textbf{98.43} & (0.23) \\ 
\textbf{ECprints} & \textbf{97.45} & (0.26) & - & \textbf{97.45} & (0.26) & \textbf{97.25} & (0.37) & - & 97.22 & (0.41) & 97.47 & (0.26) & - & \textbf{97.51} & (0.31) \\ 
\textbf{ECprosite} & \textbf{98.33} & (0.32) & - & \textbf{98.33} & (0.33) & \textbf{98.09} & (0.30) & - & 98.08 & (0.30) & \textbf{98.57} & (0.18) & - & \textbf{98.57} & (0.18) \\ 
\textbf{ECinterpro} & 98.80 & (0.32) & - & \textbf{98.82} & (0.34) & \textbf{98.71} & (0.34) & - & 98.70 & (0.32) & \textbf{98.79} & (0.38) & - & \textbf{98.79} & (0.38) \\ \hline
\textbf{Total A} & \multicolumn{3}{c}{2} & \multicolumn{2}{c|}{\textbf{8}} & \multicolumn{3}{c}{4} & \multicolumn{2}{c|}{\textbf{5}} &\multicolumn{3}{c}{4} & \multicolumn{2}{c}{\textbf{6}}\\ \hline
\textbf{Church} & \textbf{20.25} & (2.10) & - & 20.19 & (2.10) & 20.40 & (2.05) & - & \textbf{20.66} & (2.04) &\underline{\textbf{21.29}} & (2.39) & - &\underline{\textbf{21.29}} & (2.47) \\ 
\textbf{CellCycle} & \textbf{28.67} & (3.05) & - & 28.60 & (3.28) & 29.85 & (4.24) & - & \underline{\textbf{29.87} }& (3.86) & 23.96 & (2.70) & \textcolor{black}{$\bullet$}  & \textbf{24.83} & (3.10) \\ 
\textbf{Derisi} & 20.38 & (2.61) & \textcolor{black}{$\bullet$}  & \textbf{21.16} & (2.60) & 20.71 & (2.43) & - & \textbf{21.20} & (2.66) & 21.59 & (2.14) & - & \underline{\textbf{21.78} }& (1.97) \\ 
\textbf{Eisen} & 29.14 & (2.69) & - & \textbf{29.56} & (2.80) & 30.39 & (2.05) & - &\underline{\textbf{30.77} }& (1.83) & 25.27 & (2.86) & - & \textbf{25.79} & (2.67) \\ 
\textbf{Expr} & 27.94 & (2.99) & - & \textbf{28.12} & (3.08) & 29.22 & (3.26) & - & \underline{\textbf{29.26} }& (2.52) & \textbf{26.72} & (2.45) & - & 26.61 & (2.53) \\ 
\textbf{Gasch1} &\underline{\textbf{31.33}} & (2.23) & - & 31.24 & (2.22) & 30.59 & (2.62) & - & \textbf{30.80} & (2.56) & 25.24 & (2.69) & - & \textbf{25.86} & (2.28) \\
\textbf{Gasch2} & 25.28 & (2.54) & - & \textbf{25.55} & (2.00) & 25.47 & (1.68) & - &\underline{\textbf{26.21} }& (1.34) & \textbf{23.45} & (2.63) & - & 23.39 & (2.21) \\
\textbf{Phenotype} & 24.15 & (2.87) & - & \textbf{24.42} & (3.01) & \textbf{25.46} & (2.96) & - & 25.45 & (3.32) &\underline{\textbf{26.50}} & (2.58) & - & 26.37 & (3.35) \\ 
\textbf{Sequence} & \textbf{22.78} & (3.32) & - & 22.76 & (2.94) & 23.70 & (2.57) & - & \textbf{23.75} & (2.65) & 24.44 & (3.01) & \textcolor{black}{$\bullet$}  & \underline{\textbf{25.71}} & (2.87) \\ 
\textbf{SPO} & 21.40 & (2.30) & - & \textbf{21.59} & (2.25) & 22.01 & (1.63) & - & \underline{\textbf{22.31} }& (1.64) & 20.90 & (2.20) & - & \textbf{21.50} & (2.58) \\ \hline
\textbf{Total B} & \multicolumn{3}{c}{4} & \multicolumn{2}{c|}{\textbf{6}} & \multicolumn{3}{c}{1} & \multicolumn{2}{c|}{\textbf{9}} &\multicolumn{3}{c}{4} & \multicolumn{2}{c}{\textbf{7}}\\ \hline
\end{tabular}

\label{compabordprop}
\end{table}

In Table \ref{compabordprop}, we observe that the SWV strategy achieved a better predictive performance than the SV strategy. 
For both data set groups and all flat classifiers adopted, we note from the total rows that the number of better results (in bold) 
obtained by the SWV strategy is always greater than the number obtained by the SV strategy. 
We also observe that the number of better results per data set (underlined) obtained by the SWV strategy (16 times) 
is much greater than that achieved by the SV strategy (5 times).

We also note that, for data sets in Group A, the best results were achieved when the 1-NN classifier was adopted. 
On the other hand, for data sets in Group B, the best results were obtained when 9-NN and C.45 classifiers were adopted.

Considering these experiments, we conclude that the Sum of Weighted Votes strategy achieves a better 
performance than the Sum of Votes strategy and, therefore, 
it will be the strategy adopted for comparison 
with the traditional hierarchical classifiers 
(Flat on Leaves and Per Parent Top-Down).


\subsection{Comparing Sum of Weighted Votes and the Traditional Strategies}

In the next evaluation, the local classifier per level approach 
using the best proposed class-inconsistency removal strategy, Sum of Weighted Votes, 
is compared with two traditional hierarchical classifiers, Flat on Leaves (FL) and Per Parent Top-Down (PPTD).

Tables \ref{tabela31} and \ref{tabela32} present, for data sets of Group A and Group B, 
respectively, the results of the hierarchical approaches FL, PPTD, and SWV, considering all six flat classifiers adopted. 
For each combination of data set and flat classifier, the HF values, and their respective standard deviations, obtained by the three approaches are shown. 

For each combination of dataset and flat classifier, the best result
(out of the three approaches) is shown in bold. 
The symbol (\textcolor{black}{$\blacktriangle$}) on the right side of the HF value obtained by the FL and PPTD classifiers indicates 
that the value obtained by the local classier per level approach using the proposed SWV strategy overcame the FL or PPTD classifiers.
The symbol (\textcolor{black}{$\blacktriangledown$}) indicates that the HF value obtained by the FL or PPTD classifier 
overcame the result of the local classifier per level approach using the SWV strategy with statistical significance.
The symbol (-) indicates that the difference in predictive performance was not statistically significant.  
For example, in Table \ref{tabela31}, for the data set GPCRpfam, with the 3-NN flat classifier, 
the symbol (\textcolor{black}{$\blacktriangle$}) beside the result for the FL classifier represents 
that the performance of the local classifier per level approach with
the SWV strategy was better than the FL classifier, with statistical significance.

In Table \ref{tabela31}, we observe that, for the data sets of Group A, the difference of performance among the three classifiers compared
was not significant. From the total rows, we note that the number of better results 
associated with the SWV strategy (in bold) was equal to or higher than the number of better results 
associated with the traditional hierarchical classifiers FL and PPTD, when the flat classifiers 1-NN and 5-NN were adopted.
On the other hand, the PPTD classifier achieved a better performance when the 3-NN flat classifier was used. 
In addition, the FL classifier was superior when the flat classifiers 7-NN, 9-NN and C4.5 were adopted. 
We also observe that all best results for each data set (underlined) were obtained when the 1-NN flat classifier was used
and, in this case, the three strategies obtained similar performances. We conclude that, for the data sets in Group A, 
the local classifier per level approach using the proposed SWV strategy showed a competitive behavior 
in comparison with the traditional classifiers FL and PPTD.

\begin{table}[bhpt]
\centering
\scriptsize
  \setlength{\tabcolsep}{2pt}
  \setlength{\arrayrulewidth}{1\arrayrulewidth}
\caption{Comparison of HF values (\%) between classifiers SWV, FL and PPTD - Group A}
\begin{tabular}{l|llcllcll|llcllcll}
\hline
\multicolumn{ 1}{c|}{} & \multicolumn{ 8}{c|}{\textbf{1-NN}} & \multicolumn{ 8}{c}{\textbf{3-NN}} \\ 
\multicolumn{ 1}{c|}{\up{\textbf{Databases}}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c|}{\textbf{SWV}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c}{\textbf{SWV}} \\ \hline
\textbf{GPCRpfam} & 70.31 & (1.51) & - &\underline{\textbf{70.32}} & (1.52) & - & 70.31 & (1.52) & 69.34 & (1.14) & \textcolor{black}{$\blacktriangle$} & \textbf{70.07} & (0.88) & \textcolor{black}{$\blacktriangledown$} & 69.72 & (1.08) \\ 
\textbf{GPCRprints} & 82.98 & (1.21) & - & 82.97 & (1.19) & - & \underline{\textbf{83.00}} & (1.20) & 82.00 & (0.79) & \textcolor{black}{$\blacktriangle$} & 82.06 & (0.70) & - & \textbf{82.09} & (0.82) \\ 
\textbf{GPCRprosite} & \underline{\textbf{69.28}} & (1.19) & - & 69.25 & (1.23) & - & 69.26 & (1.19) & 67.81 & (0.99) & \textcolor{black}{$\blacktriangle$} & \textbf{68.39} & (1.11) & - & 68.05 & (0.86) \\
\textbf{GPCRinterpro} &\underline{\textbf{83.09}} & (0.71) & - & \underline{\textbf{83.09}} & (0.70) & - & \textbf{83.09} & (0.70) & 82.63 & (0.83) & - & \textbf{82.85} & (0.94) & - & 82.73 & (0.91) \\ 
\textbf{ECpfam} &\underline{\textbf{98.77} }& (0.17) & - & \underline{\textbf{98.77} }& (0.17) & - & \underline{\textbf{98.77}} & (0.17) & \textbf{98.44} & (0.33) & - & 98.42 & (0.31) & - & \textbf{98.44} & (0.31) \\
\textbf{ECprints} & \underline{\textbf{98.19}} & (0.24) & - &\underline{\textbf{98.19}} & (0.23) & - & \underline{\textbf{98.19} }& (0.24) & \textbf{97.87} & (0.27) & - & \textbf{97.87} & (0.25) & - & 97.86 & (0.26) \\ 
\textbf{ECprosite} & \underline{\textbf{98.80}} & (0.26) & - & \underline{\textbf{98.80} }& (0.26) & - &\underline{\textbf{98.80}} & (0.26) & \textbf{98.70} & (0.19) & - & 98.66 & (0.21) & - & 98.67 & (0.20) \\
\textbf{ECinterpro} & \underline{\textbf{99.08}} & (0.29) & - & 99.07 & (0.29) & - & \underline{\textbf{99.08}} & (0.29) & 98.79 & (0.42) & \textcolor{black}{$\blacktriangle$} & \textbf{98.85} & (0.37) & - & 98.83 & (0.40) \\ \hline
\textbf{Total A} & \multicolumn{ 3}{c}{\textbf{6}} & \multicolumn{ 3}{c}{5} & \multicolumn{ 2}{c|}{\textbf{6}} & \multicolumn{ 3}{c}{3} & \multicolumn{ 3}{c}{\textbf{5}} & \multicolumn{ 2}{c}{2} \\ \hline
\end{tabular}

\begin{tabular}{l|llcllcll|llcllcll}
\noalign{\bigskip}
\hline
\multicolumn{ 1}{c|}{} & \multicolumn{ 8}{c|}{\textbf{5-NN}} & \multicolumn{ 8}{c}{\textbf{7-NN}} \\ 
\multicolumn{ 1}{c|}{\up{\textbf{Databases}}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c|}{\textbf{SWV}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c}{\textbf{SWV}} \\ \hline
\textbf{GPCRpfam} & 69.24 & (1.21) & - & \textbf{69.53} & (0.93) & - & 69.20 & (1.32) & \textbf{69.33} & (1.26) & \textcolor{black}{$\blacktriangledown$} & 69.04 & (0.90) & - & 68.68 & (1.16) \\ 
\textbf{GPCRprints} & \textbf{81.55} & (0.84) & \textcolor{black}{$\blacktriangledown$} & 81.03 & (0.89) & - & 81.05 & (0.87) & \textbf{81.28} & (1.06) & \textcolor{black}{$\blacktriangledown$} & 80.89 & (1.08) & - & 80.86 & (1.12) \\ 
\textbf{GPCRprosite} & 67.97 & (0.58) & - & \textbf{68.34} & (0.64) & \textcolor{black}{$\blacktriangledown$} & 67.83 & (0.58) & \textbf{67.66} & (0.91) & \textcolor{black}{$\blacktriangledown$} & 67.31 & (0.98) & \textcolor{black}{$\blacktriangledown$} & 66.83 & (1.00) \\
\textbf{GPCRinterpro} & \textbf{82.43} & (0.75) & \textcolor{black}{$\blacktriangledown$} & 82.20 & (0.78) & - & 82.15 & (0.73) & \textbf{82.03} & (0.58) & - & 81.95 & (0.69) & \textcolor{black}{$\blacktriangledown$} & 81.68 & (0.53) \\
\textbf{ECpfam} & 98.26 & (0.42) & \textcolor{black}{$\blacktriangle$} & 98.24 & (0.38) & \textcolor{black}{$\blacktriangle$} & \textbf{98.37} & (0.33) & 98.27 & (0.41) & - & 98.16 & (0.36) & \textcolor{black}{$\blacktriangle$} & \textbf{98.30} & (0.29) \\
\textbf{ECprints} & 97.63 & (0.30) & - & 97.60 & (0.32) & - & \textbf{97.64} & (0.30) & \textbf{97.49} & (0.28) & - & 97.37 & (0.28) & \textcolor{black}{$\blacktriangle$} & 97.45 & (0.26) \\ 
\textbf{ECprosite} & \textbf{98.47} & (0.25) & - & 98.45 & (0.27) & - & \textbf{98.47} & (0.27) & \textbf{98.37} & (0.31) & \textcolor{black}{$\blacktriangledown$} & 98.29 & (0.32) & - & 98.33 & (0.33) \\ 
\textbf{ECinterpro} & 98.70 & (0.40) & \textcolor{black}{$\blacktriangle$} & 98.76 & (0.41) & - & \textbf{98.83} & (0.41) & 98.73 & (0.30) & \textcolor{black}{$\blacktriangledown$} & 98.62 & (0.32) & \textcolor{black}{$\blacktriangledown$} & \textbf{98.82} & (0.34) \\ \hline
\textbf{Total A} & \multicolumn{ 3}{c}{3} & \multicolumn{ 3}{c}{2} & \multicolumn{ 2}{c|}{\textbf{4}} & \multicolumn{ 3}{c}{\textbf{6}} & \multicolumn{ 3}{c}{0} & \multicolumn{ 2}{c}{2} \\ \hline
\end{tabular}

\begin{tabular}{l|llcllcll|llcllcll}
\noalign{\bigskip}
\hline
\multicolumn{ 1}{c|}{} & \multicolumn{ 8}{c|}{\textbf{9-NN}} & \multicolumn{ 8}{c}{\textbf{C4.5}} \\ 
\multicolumn{ 1}{c|}{\up{\textbf{Databases}}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c|}{\textbf{SWV}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c}{\textbf{SWV}} \\ \hline
\textbf{GPCRpfam} & \textbf{68.62} & (1.34) & - & 68.47 & (0.83) & - & 68.07 & (1.10) & \textbf{69.32} & (1.23) & - & 68.84 & (1.14) & - & 68.70 & (1.21) \\ 
\textbf{GPCRprints} & \textbf{80.54} & (1.06) & - & 80.41 & (0.96) & - & 80.28 & (0.89) & \textbf{81.76} & (0.52) & \textcolor{black}{$\blacktriangledown$} & 79.19 & (0.94) & - & 79.33 & (0.85) \\ 
\textbf{GPCRprosite} & \textbf{66.67} & (0.87) & \textcolor{black}{$\blacktriangledown$} & 66.57 & (0.70) & \textcolor{black}{$\blacktriangledown$} & 66.00 & (0.87) & \textbf{68.03} & (1.01) & \textcolor{black}{$\blacktriangledown$} & 67.63 & (1.17) & \textcolor{black}{$\blacktriangledown$} & 67.08 & (1.00) \\
\textbf{GPCRinterpro} & \textbf{81.99} & (0.90) & \textcolor{black}{$\blacktriangledown$} & 81.29 & (1.05) & - & 81.31 & (0.91) & \textbf{82.66} & (0.72) & \textcolor{black}{$\blacktriangledown$} & 81.54 & (0.57) & - & 81.80 & (1.03) \\ 
\textbf{ECpfam} & 98.18 & (0.33) & - & 97.88 & (0.33) & \textcolor{black}{$\blacktriangle$} & \textbf{98.19} & (0.31) & 98.33 & (0.24) & \textcolor{black}{$\blacktriangle$} & 98.39 & (0.24) & - & \textbf{98.43} & (0.23) \\ 
\textbf{ECprints} & \textbf{97.27} & (0.38) & - & 97.05 & (0.34) & \textcolor{black}{$\blacktriangle$} & 97.22 & (0.41) & \textbf{97.56} & (0.30) & - & 97.35 & (0.27) & \textcolor{black}{$\blacktriangle$} & 97.51 & (0.31) \\ 
\textbf{ECprosite} & \textbf{98.16} & (0.29) & \textcolor{black}{$\blacktriangledown$} & 98.03 & (0.31) & \textcolor{black}{$\blacktriangle$} & 98.08 & (0.30) & 98.50 & (0.19) & - & 98.46 & (0.17) & \textcolor{black}{$\blacktriangle$} & \textbf{98.57} & (0.18) \\
\textbf{ECinterpro} & \textbf{98.72} & (0.35) & - & 98.32 & (0.40) & \textcolor{black}{$\blacktriangle$} & 98.70 & (0.32) & 98.74 & (0.38) & \textcolor{black}{$\blacktriangle$} & 98.73 & (0.34) & - & \textbf{98.79} & (0.38) \\ \hline
\textbf{Total A} & \multicolumn{ 3}{c}{\textbf{7}} & \multicolumn{ 3}{c}{0} & \multicolumn{ 2}{c|}{1} & \multicolumn{ 3}{c}{\textbf{5}} & \multicolumn{ 3}{c}{0} & \multicolumn{ 2}{c}{3} \\ \hline
\end{tabular}

\label{tabela31}
\end{table}

In Table \ref{tabela32} we note that, for data sets in Group B, the proposed SWV strategy obtained a better predictive
performance than the other two strategies. We observe, from the total rows, that the number of better 
results associated with the SWV strategy (in bold) was greater than the number of better results associated with
the classifiers FL and PPTD when the flat classifiers 5-NN, 7-NN, 9-NN and C4.5 were used, many times with statistical significance. 
We note that nine out of the ten best results per data set (underlined
results) were obtained by the SWV strategy. 
We concluded that, for the data sets of Group B, the local classifier per level approach using the proposed SWV strategy has 
shown a superior behavior when 
compared to the traditional classifiers FL and PPTD.

\begin{table}[htbp]
\centering
\scriptsize
  \setlength{\tabcolsep}{2pt}
  \setlength{\arrayrulewidth}{1\arrayrulewidth}
\caption{Comparison of HF values (\%) between classifiers SWV, FL and PPTD - Group B}
\begin{tabular}{l|llcllcll|llcllcll}
\hline
\multicolumn{ 1}{c|}{} & \multicolumn{ 8}{c|}{\textbf{1-NN}} & \multicolumn{ 8}{c}{\textbf{3-NN}} \\ 
\multicolumn{ 1}{c|}{\up{\textbf{Databases}}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c|}{\textbf{SWV}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c}{\textbf{SWV}} \\ \hline
\textbf{Church} & \textbf{21.26} & (1.58) & \textcolor{black}{$\blacktriangledown$} & 19.38 & (1.90) & - & 19.70 & (1.97) & \textbf{20.44} & (1.72) & - & 20.20 & (2.24) & - & 20.27 & (1.94) \\ 
\textbf{CellCycle} & \textbf{24.83} & (2.55) & - & 24.56 & (2.10) & - & 24.82 & (2.34) & 23.00 & (3.27) & - & \textbf{24.79} & (3.62) & - & 24.52 & (3.59) \\ 
\textbf{Derisi} & 18.87 & (2.50) & - & \textbf{18.89} & (2.23) & - & 18.73 & (2.33) & 15.84 & (2.05) & \textcolor{black}{$\blacktriangle$} & \textbf{19.05} & (2.50) & \textcolor{black}{$\blacktriangledown$} & 17.94 & (2.57) \\
\textbf{Eisen} & \textbf{24.72} & (2.88) & - & 24.70 & (2.02) & - & 24.54 & (2.32) & 23.22 & (2.60) & - & \textbf{25.31} & (3.97) & - & 25.19 & (3.40) \\
\textbf{Expr} & 25.05 & (3.40) & \textcolor{black}{$\blacktriangle$} & 25.35 & (3.28) & - & \textbf{25.62} & (3.56) & 21.65 & (1.16) & \textcolor{black}{$\blacktriangle$} & \textbf{24.11} & (2.72) & - & 23.44 & (1.92) \\
\textbf{Gasch1} & 28.84 & (1.70) & - & 28.29 & (1.47) & - & \textbf{28.98} & (2.01) & 25.85 & (2.56) & \textcolor{black}{$\blacktriangle$} & \textbf{29.25} & (2.45) & - & 28.62 & (1.77) \\
\textbf{Gasch2} & 24.58 & (3.31) & - & \textbf{25.23} & (2.97) & - & 25.03 & (3.04) & 21.51 & (2.86) & \textcolor{black}{$\blacktriangle$} & \textbf{23.98} & (2.54) & - & 23.26 & (2.71) \\ 
\textbf{Phenotype} & 20.67 & (3.75) & \textcolor{black}{$\blacktriangle$} & 20.27 & (3.66) & - & \textbf{22.46} & (2.91) & 22.29 & (3.80) & - & 21.51 & (2.76) & - & \textbf{23.66} & (3.24) \\ 
\textbf{Sequence} & 22.43 & (2.97) & - & \textbf{24.02} & (3.42) & \textcolor{black}{$\blacktriangledown$} & 23.08 & (3.14) & 20.44 & (1.94) & \textcolor{black}{$\blacktriangle$} & \textbf{23.01} & (2.70) & - & 22.38 & (2.56) \\ 
\textbf{SPO} & 18.23 & (2.26) & - & \textbf{18.86} & (2.41) & - & 18.50 & (2.68) & 16.89 & (2.11) & \textcolor{black}{$\blacktriangle$} & \textbf{19.94} & (1.74) & - & 19.15 & (1.89) \\ \hline
\textbf{Total B} & \multicolumn{ 3}{c}{3} & \multicolumn{ 3}{c}{\textbf{4}} & \multicolumn{ 2}{c|}{3} & \multicolumn{ 3}{c}{1} & \multicolumn{ 3}{c}{\textbf{8}} & \multicolumn{ 2}{c}{1} \\ \hline
\end{tabular}

\begin{tabular}{l|llcllcll|llcllcll}
\noalign{\bigskip}
\hline
\multicolumn{ 1}{c|}{} & \multicolumn{ 8}{c|}{\textbf{5-NN}} & \multicolumn{ 8}{c}{\textbf{7-NN}} \\ 
\multicolumn{ 1}{c|}{\up{\textbf{Databases}}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c|}{\textbf{SWV}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c}{\textbf{SWV}} \\ \hline
\textbf{Church} & \textbf{21.82} & (1.53) & - & 19.53 & (2.84) & - & 20.53 & (2.18) & \textbf{21.72} & (1.11) & \textcolor{black}{$\blacktriangle$} & 19.66 & (2.27) & \textcolor{black}{$\blacktriangle$} & 20.19 & (2.10) \\ 
\textbf{CellCycle} & 25.52 & (2.44) & \textcolor{black}{$\blacktriangle$} & 27.36 & (2.78) & - & \textbf{28.15} & (2.98) & 27.47 & (2.16) & - & 28.38 & (3.33) & - & \textbf{28.60} & (3.28) \\
\textbf{Derisi} & 17.11 & (2.53) & \textcolor{black}{$\blacktriangle$} & 18.83 & (2.51) & - & \textbf{20.06} & (2.54) & 18.88 & (2.83) & \textcolor{black}{$\blacktriangle$} & 20.21 & (2.61) & - & \textbf{21.16} & (2.60) \\ 
\textbf{Eisen} & 25.24 & (2.63) & \textcolor{black}{$\blacktriangle$} & 26.40 & (3.36) & \textcolor{black}{$\blacktriangle$} & \textbf{28.31} & (2.95) & 28.28 & (2.49) & - & 29.25 & (2.47) & - & \textbf{29.56} & (2.80) \\
\textbf{Expr} & 23.87 & (2.33) & \textcolor{black}{$\blacktriangle$} & 26.47 & (1.99) & - & \textbf{27.13} & (2.63) & 25.92 & (1.84) & \textcolor{black}{$\blacktriangle$} & 27.21 & (3.11) & - & \textbf{28.12} & (3.08) \\
\textbf{Gasch1} & 26.62 & (2.39) & \textcolor{black}{$\blacktriangle$} & 29.76 & (2.55) & - & \textbf{30.07} & (1.88) & 29.16 & (2.86) & - & 30.97 & (2.67) & - & \underline{\textbf{31.24}} & (2.22) \\
\textbf{Gasch2} & 22.56 & (3.11) & \textcolor{black}{$\blacktriangle$} & \textbf{24.79} & (3.52) & - & 23.92 & (3.16) & 24.37 & (2.67) & - & \textbf{26.12} & (2.66) & - & 25.55 & (2.00) \\ 
\textbf{Phenotype} & 23.10 & (4.06) & - & 21.33 & (3.13) & - & \textbf{23.23} & (2.11) & \textbf{24.57} & (3.51) & - & 22.52 & (4.06) & - & 24.42 & (3.01) \\
\textbf{Sequence} & 21.85 & (2.93) & - & \textbf{23.60} & (2.24) & - & 22.82 & (2.69) & 23.59 & (2.30) & - & \textbf{23.73} & (3.39) & - & 22.76 & (2.94) \\
\textbf{SPO} & 17.35 & (2.16) & \textcolor{black}{$\blacktriangle$} & \textbf{20.41} & (2.54) & - & 19.92 & (2.73) & 19.14 & (1.79) & \textcolor{black}{$\blacktriangle$} & 21.10 & (3.19) & - & \textbf{21.59} & (2.25) \\ \hline
\textbf{Total B} & \multicolumn{ 3}{c}{1} & \multicolumn{ 3}{c}{3} & \multicolumn{ 2}{c|}{\textbf{6}} & \multicolumn{ 3}{c}{2} & \multicolumn{ 3}{c}{2} & \multicolumn{ 2}{c}{\textbf{6}} \\ \hline
\end{tabular}

\begin{tabular}{l|llcllcll|llcllcll}
\noalign{\bigskip}
\hline
\multicolumn{ 1}{c|}{} & \multicolumn{ 8}{c|}{\textbf{9-NN}} & \multicolumn{ 8}{c}{\textbf{C4.5}} \\ 
\multicolumn{ 1}{c|}{\up{\textbf{Databases}}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c|}{\textbf{SWV}} & \multicolumn{ 3}{c}{\textbf{FL}} & \multicolumn{ 3}{c}{\textbf{PPTD}} & \multicolumn{ 2}{c}{\textbf{SWV}} \\ \hline
\textbf{Church} & \underline{\textbf{22.10}} & (1.41) & - & 19.82 & (2.66) & - & 20.66 & (2.04) & \textbf{21.74} & (1.76) & - & 21.53 & (1.93) & - & 21.29 & (2.47) \\
\textbf{CellCycle} & 29.08 & (2.30) & - & 29.40 & (2.95) & - & \underline{\textbf{29.87}} & (3.86) & 21.86 & (3.75) & \textcolor{black}{$\blacktriangle$} & 22.19 & (2.41) & \textcolor{black}{$\blacktriangle$} & \textbf{24.83} & (3.10) \\ 
\textbf{Derisi} & 20.17 & (3.14) & - & 20.89 & (2.36) & - & \textbf{21.20} & (2.66) & 18.28 & (2.77) & \textcolor{black}{$\blacktriangle$} & 20.47 & (2.70) & - & \underline{\textbf{21.78}} & (1.97) \\ 
\textbf{Eisen} & 28.73 & (3.02) & \textcolor{black}{$\blacktriangle$} & 29.16 & (2.63) & - & \underline{\textbf{30.77}} & (1.83) & 22.96 & (3.14) & - & 24.24 & (3.19) & - & \textbf{25.79} & (2.67) \\ 
\textbf{Expr} & 27.58 & (2.69) & \textcolor{black}{$\blacktriangle$} & 28.29 & (2.19) & - & \underline{\textbf{29.26}} & (2.52) & 24.98 & (2.93) & - & 24.74 & (2.22) & \textcolor{black}{$\blacktriangle$} & \textbf{26.61} & (2.53) \\ 
\textbf{Gasch1} & 30.40 & (2.41) & - & 30.08 & (2.90) & - & \textbf{30.80} & (2.56) & 23.09 & (2.95) & \textcolor{black}{$\blacktriangle$} & 22.90 & (2.05) & \textcolor{black}{$\blacktriangle$} & \textbf{25.86} & (2.28) \\
\textbf{Gasch2} & 25.89 & (2.24) & - & 26.00 & (2.24) & - & \underline{\textbf{26.21}} & (1.34) & 20.76 & (3.11) & \textcolor{black}{$\blacktriangle$} & 22.52 & (3.58) & - & \textbf{23.39} & (2.21) \\
\textbf{Phenotype} & \textbf{25.77} & (3.38) & - & 22.95 & (4.75) & - & 25.45 & (3.32) & 22.86 & (3.86) & \textcolor{black}{$\blacktriangle$} & 21.39 & (3.94) & \textcolor{black}{$\blacktriangle$} & \underline{\textbf{26.37}} & (3.35) \\
\textbf{Sequence} & 23.64 & (2.41) & - & \textbf{23.90} & (2.58) & - & 23.75 & (2.65) & 19.68 & (2.31) & \textcolor{black}{$\blacktriangle$} & 22.86 & (2.59) & \textcolor{black}{$\blacktriangle$} & \underline{\textbf{25.71}} & (2.87) \\
\textbf{SPO} & 20.47 & (2.08) & \textcolor{black}{$\blacktriangle$} & 22.29 & (2.49) & - & \underline{\textbf{22.31}} & (1.64) & 19.86 & (2.45) & - & 19.36 & (2.13) & \textcolor{black}{$\blacktriangle$} & \textbf{21.50} & (2.58) \\ \hline
\textbf{Total B} & \multicolumn{ 3}{c}{2} & \multicolumn{ 3}{c}{1} & \multicolumn{ 2}{c|}{\textbf{7}} & \multicolumn{ 3}{c}{1} & \multicolumn{ 3}{c}{0} & \multicolumn{ 2}{c}{\textbf{9}} \\ \hline
\end{tabular}

\label{tabela32}
\end{table}

Table \ref{tabcons} summarizes the previous results presented in Tables \ref{tabela31} and \ref{tabela32} for the local classifier per level
approach with SWV strategy, FL and PPTD hierarchical classifiers. 
For each data set, it is shown the best result for each hierarchical classifier and the respective flat classifier used to find it.

For the data sets in Group A, we note that the results of the three hierarchical approaches are very close. 
However, we observe that the local classifier per level with the SWV
strategy presents a competitive behavior, since it obtained, in total, six best results for the eight data sets. 
For the data sets in Group B, the local classifier per level with the SWV strategy showed a better performance than the other hierarchical
classifiers in nine out of ten data sets.

From these results, we conclude that the local classifier per level with the proposed SWV strategy has shown good predictive performance, 
achieving results equal to or better than two other traditional
hierarchical classification approaches in 15 out of 18 data sets used in the experiments.

\begin{table}[htbp]
\centering
\scriptsize
  \setlength{\tabcolsep}{2pt}
  \setlength{\arrayrulewidth}{1\arrayrulewidth}
\caption{Best HF results found for each hierarchical strategy}
\begin{tabular}{l|cc|cc|cc}
\hline
\multicolumn{ 1}{c|}{} & \multicolumn{ 2}{c|}{\textbf{FL}} & \multicolumn{ 2}{c|}{\textbf{PPTD}} & \multicolumn{ 2}{c}{\textbf{SWV}} \\ 
\multicolumn{ 1}{c|}{\up{\textbf{Databases}}} & \textbf{HF(\%)} & \textbf{Flat Classifier} &  \textbf{HF(\%)} & \textbf{Flat Classifier} & \textbf{HF(\%)} & \textbf{Flat Classifier} \\ \hline
\textbf{GPCRpfam} & 70.31 & 1-NN & \textbf{70.32} & 1-NN & 70.31 & 1-NN \\ 
\textbf{GPCRprints} & 82.98 & 1-NN & 82.97 & 1-NN & \textbf{83.00} & 1-NN \\ 
\textbf{GPCRprosite} & \textbf{69.28} & 1-NN & 69.25 & 1-NN & 69.26 & 1-NN \\ 
\textbf{GPCRinterpro} & \textbf{83.09} & 1-NN & \textbf{83.09} & 1-NN & \textbf{83.09} & 1-NN \\ 
\textbf{ECpfam} & \textbf{98.77} & 1-NN & \textbf{98.77} & 1-NN & \textbf{98.77} & 1-NN \\ 
\textbf{ECprints} & \textbf{98.19} & 1-NN & \textbf{98.19} & 1-NN & \textbf{98.19} & 1-NN \\ 
\textbf{ECprosite} & \textbf{98.80} & 1-NN & \textbf{98.80} & 1-NN & \textbf{98.80} & 1-NN \\ 
\textbf{ECinterpro} & \textbf{99.08} & 1-NN & 99.07 & 1-NN & \textbf{99.08} & 1-NN \\\hline
\textbf{Total A} & \multicolumn{ 2}{c|}{\textbf{6}} & \multicolumn{ 2}{c|}{5} & \multicolumn{ 2}{c}{\textbf{6}} \\ \hline
\textbf{Church} & \textbf{22.10} & 9-NN & 21.53 & C4.5 & 21.29 & C4.5 \\ 
\textbf{CellCycle} & 29.08 & 9-NN & 29.40 & 9-NN & \textbf{29.87} & 9-NN \\ 
\textbf{Derisi} & 20.17 & 9-NN & 20.89 & 9-NN & \textbf{21.78} & C4.5 \\ 
\textbf{Eisen} & 28.73 & 9-NN  & 29.25 & 7-NN & \textbf{30.77} & 9-NN \\ 
\textbf{Expr} & 27.58 & 9-NN  & 28.29 & 9-NN & \textbf{29.26} & 9-NN \\ 
\textbf{Gasch1} & 30.40 & 9-NN & 30.97 & 7-NN & \textbf{31.24} & 7-NN \\ 
\textbf{Gasch2} & 25.89 & 9-NN & 26.12 & 7-NN & \textbf{26.21} & 9-NN \\ 
\textbf{Phenotype} & 25.77 & 9-NN & 22.95 & 9-NN & \textbf{26.37} & C4.5 \\ 
\textbf{Sequence} & 23.64 & 9-NN & 24.02 & 1-NN & \textbf{25.71} & C4.5 \\ 
\textbf{SPO} & 20.47 & 9-NN &  22.29 & 9-NN & \textbf{22.31} & 9-NN \\ \hline
\textbf{Total B} & \multicolumn{ 2}{c|}{1} & \multicolumn{ 2}{c|}{0} & \multicolumn{ 2}{c}{\textbf{9}} \\ \hline
\end{tabular}
\label{tabcons}
\end{table}

Table \ref{tabmelhores} shows the best results achieved for each data set and the hierarchical approaches that have achieved it. 
Again, we observe a balanced behavior among the three hierarchical
approaches for data sets in Group A, 
and a better performance of the local classifier per level approach
using the SWV strategy for the data sets in Group B.

\vspace{-0.3cm}

\begin{table}[htbp]
\centering
\scriptsize
  \setlength{\tabcolsep}{2pt}
  \setlength{\arrayrulewidth}{1\arrayrulewidth}
\caption{Best HF results found for each database}
\begin{tabular}{c|l|c|l|c|l|c|l}
\hline
\textbf{Group} & \multicolumn{ 1}{c|}{\textbf{Databases}} & \textbf{HF(\%)} & \textbf{Strategies} & \textbf{Group}& 
\multicolumn{ 1}{c|}{\textbf{Databases}} & \textbf{HF(\%)} & \textbf{Strategies}\\ \hline
&GPCRpfam & 70.32 & PPTD/1-NN & & Church& 22.10 & FL/9-NN\\ 
&GPCRprints & 83.00 & SWV/1-NN & & CellCycle & 29.87 & SWV/9-NN\\ 
&GPCRprosite & 69.28 & FL/1-NN & & Derisi& 21.78 & SWV/C4.5\\ 
&GPCRinterpro  & 83.09 & FL/1-NN, PPTD/1-NN, SWV/1-NN & & Eisen &30.77 &SWV/9-NN  \\
\textbf{A} &ECpfam & 98.77 & FL/1-NN, PPTD/1-NN, SWV/1-NN & \textbf{B} & Expr &29.26 & SWV/9-NN \\ 
&ECprints & 98.19 & FL/1-NN, PPTD/1-NN, SWV/1-NN & & Gasch1  &31.24 & SWV/7-NN \\ 
&ECprosite & 98.80 & FL/1-NN, PPTD/1-NN, SWV/1-NN & & Gasch2 &26.21   & SWV/9-NN\\ 
&ECinterpro & 99.08 & FL/1-NN, SWV/1-NN & &Phenotype  &26.37 & SWV/C4.5 \\
&  &   &   &   &Sequence &25.71 & SWV/C4.5\\
&  &   &   &   &SPO &22.31 & SWV/9-NN \\ \hline
\end{tabular}
\label{tabmelhores}
\end{table}

\vspace{-0.2cm}

\section{Conclusions}

Hierarchical classification problems have been explored with strategies
pertaining to different categories. 
The local classification approach is one of 
the most used and efficient paradigms for hierarchical classification,
where the algorithm is aware of the class hierarchy through a local 
(rather than global) perspective.
In spite of requiring the training of a reduced number of classifiers,
one per hierarchical level, the local classifier per level approach has not been
properly addressed in the literature yet. 
Probably, this is due to inconsistent class predictions, 
common to this hierarchical paradigm.

In this work, we proposed two local classifier per level hierarchical 
classification approaches, called Sum of Votes (SV) and Sum of Weighted Votes (SWV).
Each of these approaches uses a distinct strategy to solve inconsistent predictions.
Using 18 hierarchical classification data sets, we evaluated both strategies and concluded 
that SWV was able to reach higher predictive accuracies. 
Next, using the same data sets, we compared the SWV strategy with 
two traditional hierarchical classification approaches: the flat classification and
the local classifier per parent approach. 
The obtained results
showed that the Sum of Weighted Votes strategy presented again 
a competitive and robust performance in terms of prediction accuracy,
evidencing the importance of the local classifier per level approach.

The next step of this research is to couple attribute selection 
procedures with the hierarchical classifiers. We believe
the proposed strategy could benefit from considering only
the important features in each level of the hierarchy when
building the local classifiers in the local classifier per level approach.

	
% INCLUDE BIBLIOGRAPHY WHICH MUST FOLLOW jidm.bst TEMPLATE
\bibliographystyle{jidm}
\bibliography{jidmb}
% For information on how to write bibliography entries, 
% see file jidmb.bib

\begin{received}
\end{received}

\end{document}
