\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{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}

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


% Includes headers with simplified name of the authors and article title
\markboth{Thiago F. Cov\~{o}es et. al.}
{Hierarchical Bottom-Up Safe Semi-Supervised Support Vector Machines for Multi-Class Transductive Learning}
%  -> \markboth{}{}
%         takes 2 arguments
%         ex: \markboth{M. M. Moro}{Any article title}


% Title of the article
\title{Hierarchical Bottom-Up Safe Semi-Supervised Support Vector Machines for Multi-Class Transductive Learning}


% 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{Thiago F. Cov\~{o}es, Rodrigo C. Barros, Tiago S. da Silva, Eduardo R. Hruschka, Andre C. P. L. F. de Carvalho}


%Affiliation and email
\institute{Instituto de Ci\^encias Matem\'aticas e de Computa\c{c}\~ao --- ICMC\\
Universidade de S\~ao Paulo --- Campus S\~ao Carlos\\
Caixa Postal 668, 13560-970 S\~ao Carlos-SP\\
\{tcovoes, rcbarros, tiago.silva, erh, andre\}@icmc.usp.br
% IF THERE IS ANOTHER INSTITUTION:
%\and Name_of_the_second_institution \\
%\email{address@whatever.com}
}


%%%%CUSTOMIZACAO PROPRIA%%%%

\usepackage[cmex10]{amsmath}
\usepackage{amsfonts}
\usepackage{algpseudocode}
\usepackage{xspace}

\usepackage{url}
\usepackage[caption=false,font=footnotesize]{subfig}


\usepackage{rotating}
\usepackage{array,booktabs,multirow}

\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
%a forma abaixo nao deixa espaco entre o arg e o max
%\newcommand{\argmax}{\operatornamewithlimits{argmax}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\cent}{\boldsymbol{\mu}}
\newcommand{\ie}{\textit{i.e.},\xspace}
\newcommand{\eg}{\textit{e.g.},\xspace}
\newcommand{\kmeans}{$k$-means\xspace}
\newcommand{\ML}{\overline{ML}}
\newcommand{\CL}{\overline{CL}}
\newcommand{\hbust}{\textit{HiBUST}\xspace}
\newcommand{\sqvm}{\text{S$^4$VM}\xspace}
\newcommand{\sqvms}{\text{S$^4$VMs}\xspace}
\newcommand{\norm}[2]{\mathcal{N}(\x_#1|\bs{\mu}_#2,\mathbf{I})}
\newcommand{\bs}[1]{\boldsymbol{#1}}

\renewcommand{\algorithmiccomment}[1]{\hspace{0.5cm}// #1}
\renewcommand{\algorithmicforall}{\textbf{for each}}
\renewcommand{\algorithmicindent}{0.3cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




% Article abstract - it should be from 100 to 300 words
\begin{abstract}
Semi-supervised approaches have been successfully applied to many machine learning problems. A particular case of semi-supervised settings is transductive learning, in which the goal is solely to label the available unlabeled data, instead of generating a predictive model that should generalize well to unseen data. Nevertheless, there are cases in which a transductive learner may perform even worse than an inductive learner that is trained with only the labeled data. For alleviating this problem, an effort towards safe semi-supervised support vector machines (\sqvm) was made, so that a transductive SVM would never degenerate the performance when compared to its inductive counterpart. Even though robust, \sqvm still lacks the ability of naturally dealing with multi-class problems, having to rely on multi-class encoding schemes, such as one-vs-one and one-vs-all strategies. These schemes may not take advantage of the full potential of \sqvm, specially in complex multi-class problems with overlapping classes. In this article, we address this problem by providing a binary-tree scheme for aggregating distinct \sqvms in a bottom-up fashion. The proposed approach is named \hbust, which stands for Hierarchical Bottom-Up \sqvm Tree. Experimental results show that \hbust can provide increased predictive performance for many multi-class problems when compared to a one-vs-one \sqvm. In addition, we show that \hbust is also beneficial for complex binary-class problems.
\end{abstract}


% ACM Computing Classification System categories
\category{H.2.8}{Database Management}{Database Applications}[Data mining]
\category{I.5.2}{Pattern Recognition}{Design Methodology}[Classifier design and evaluation]

% 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{multi-class SVMs, safe support vector machines, semi-supervised learning, transductive learning}
%  -> \keywords{} (in alphabetical order \keywords{document processing, sequences,
%                      string searching, subsequences, substrings})


% THE ARTICLE BEGINS
\begin{document}

% This is optional:
\begin{bottomstuff}
The authors would like to thank Funda\c{c}\~{a}o de Amparo \`{a} Pesquisa do Estado de S\~{a}o Paulo (FAPESP) and Conselho Nacional de Desenvolvimento Cient\'{i}fico e Tecnol\'{o}gico (CNPq) for funding this research. 
\end{bottomstuff}

\maketitle






\section{Introduction}\label{sec:introduction}
% no \IEEEPARstart

In transductive learning, given a labeled sample $\mathcal{X}^{(L)}=\{(\x_i, y_i)\}_{i=1}^l$ and an unlabeled sample $\mathcal{X}^{(U)}=\{\hat{\x}_j\}_{j=1}^u$ where $\x_i,\hat{\x}_j \in \mathbb{R}^d$ and $y_i \in \{1,\dots,c\}$, the goal is to infer a function $f: \mathcal{X}^{(U)} \mapsto \mathcal{Y}^{(U)}$ so that $f$ is expected to be a good predictor of the unlabeled data $\mathcal{X}^{(U)}$. Note that $f$ is defined only on the given training sample, and it is not required to make predictions on a distinct set of data, \eg on a (new) test set \cite{TR01_Seeger,NIPS99_Chapelle,BOOK09_Zhu,AAAI10_Zhang,ICDM11_Bahadori,NC12_Yu}. 
While the inductive approach is useful when a global model is needed in an approximate form, the transductive approach is more appropriate for applications where the focus is not on the generalization capability of the model, but rather on particular cases \cite{Vapnik98,UAI98_Gammerman98}. 

Recently, a robust approach for transductive learning, named \textit{Safe Semi-Supervised Support Vector Machines} (\sqvms) \cite{Li2011}, has been proposed. 
\sqvms exploit multiple candidate low-density separators simultaneously, instead of looking for a single optimal low-density separator resulting from the set of labeled and unlabeled data. Considering that the amount of unlabeled data is usually much larger than that of labeled data, there exists more than one large-margin low-density separator that properly fits the data, and a poor choice may result in degenerated performance. The predictive accuracy of \sqvms, on the other hand, is never significantly worse when compared to inductive SVMs \cite{Li2011}.


Even though \sqvms present several advantages over other transductive learners, they do not naturally deal with multi-class problems. Due to various complexities, a direct mathematical solution for multi-class problems using a single SVM formulation is usually avoided \cite{Duan2005}. Popular strategies for multi-class SVM classification include \textit{one-versus-all} classification with a \textit{winner-takes-all} strategy (\textit{OVA-WTA} SVM) and \textit{one-versus-one} classification with \textit{max-wins voting} (\textit{OVO-MWV} SVM). 



Due to its formulation, \sqvm does not output confidence values for its predictions, thus the strategy \textit{OVA-WTA} cannot be employed. In order to circumvent such a difficulty, one can use the \textit{OVO-MWV} strategy, in which $\frac{c\times(c-1)}{2}$ \sqvms are executed for a $c$-class problem. 
According to \cite{JMLR04_Rifkin}, assuming that the base classifiers are properly tuned, there is not much difference among these schemes.
However, classifiers that exploit relationships between classes could offer superior performance \cite{JMLR04_Rifkin}, which is precisely the assumption we try to demonstrate herein.
%However, the \textit{OVO-MWV} strategy is susceptible to the classes distribution within the input space. In particular, complex multi-class problems with overlapping classes, or with unevenly spatially-distributed classes, may degenerate the \textit{max-wins voting} framework, leading to a decreased performance of \sqvms.

Another problem that arises regards the small number of labeled objects available in transductive learning settings, where selecting a kernel and optimizing its parameters becomes impractical due to the lack of enough data. In the case of multiple classes, this problem gets even worse because of the need for multiple classifiers. Bearing in mind that classes may not be linearly-separable in the input space, a method capable of combining multiple linear SVMs can be of interest in such settings. To illustrate this problem, let us consider Figure \ref{fig:example}. In its first part (Figure \ref{fig:ex1}) a data set with 2 classes (red circles and black diamonds) and 9 labeled objects is presented. One can see that the class represented by red circles is composed by two clusters. Besides, note that the classes are not linearly separable. Thus, even tough this problem can be considered simple, only one linear SVM will not obtain good results. However, if we decompose the problem in such a way that a linear SVM is constructed to differentiate between pairs of clusters of different classes, the problem can be solved by using two linear SVMs. The result of this approach is presented in Figure \ref{fig:ex2}.

\begin{figure}[h]
\captionsetup[subfloat]{width=\linewidth}
%\centerline{
\begin{center}
\subfloat[Training data --- blue squares represent unlabeled objects, red circles and black diamonds represent labeled objects of (two) different classes.]{\includegraphics[scale=0.2]{../fig/example_part.pdf}
\label{fig:ex1}}\\
%\hspace{0.5cm}
	\subfloat[Classification obtained using problem decomposition.]{\includegraphics[scale=0.2]{../fig/example.pdf}
	\label{fig:ex2}}
%	}	
\end{center}
	\caption{Pedagogical example for problem decomposition.}
	\label{fig:example}
\end{figure}


Having similar scenarios in mind, we propose a hierarchical \sqvm approach that is capable of \textit{naturally} dealing with multi-class problems. By taking advantage of both class information and distances between data objects, our approach builds a bottom-up binary tree structure that divides the complex input space into sub-spaces, with the underlying (and intuitive) assumption that the respective sub-problems are easier to solve than the whole classification problem. More precisely, the assumption we make is that classes may be distributed across distinct clusters, and thus objects from the same class can lie on different regions of the input space. The proposed algorithm, named Hierarchical Bottom-Up \sqvm Tree (\hbust), performs semi-supervised constrained clustering to divide the input space into sub-regions, and then recursively merges the closest sub-regions from distinct classes. Next, it makes use of \sqvm to separate two regions of different classes. Experimental results obtained from a variety of different data sets show that \hbust is capable of naturally dealing with transductive multi-class problems, increasing the accuracy of a single \sqvm over the whole data set.

The remainder of this article is organized as follows. In Section~\ref{sec:s3vm}, we contextualize our contribution by briefly reviewing the literature on semi-supervised support vector machines. Section~\ref{sec:hbus} addresses the proposed \hbust algorithm, whereas Section~\ref{sec:experiments} presents an experimental analysis to validate its applicability. We conclude the article in Section~\ref{sec:conclusions}.

\section{Related Work}\label{sec:s3vm}

Semi-supervised support vector machines (S$^3$VMs) --- also known as \textit{Transductive SVMs} (TSVMs) --- are extensions of supervised SVMs for performing semi-supervised learning by simultaneously learning the optimal hyperplane and the labels for unlabeled objects \cite{Joachims1999,Fung2001,Chapelle2005,Chapelle2006}. 
They find the large-margin separator by favoring the decision boundary that lies in low-density data regions. More formally, the goal is to find a function $f: \x \mapsto \{\pm 1\}$ and $\mathbf{\hat{y}} \in \{\pm 1\}^{u}$, where $u=\vert \mathcal{X}^{(U)}\vert $, \ie the number of unlabeled objects. In order to find $f$, one formulates a (minimization) optimization problem as follows:

\begin{equation} \label{eq:s3vm}
	\min_{f,\mathbf{\hat{y}} \in \mathcal{B}} \frac{||f||_{\mathcal{H}}}{2} + C_1 \sum_{i=1}^{l}{\ell(y_i,f(\mathbf{x}_i))} + C_2 \sum_{j=1}^{u}{\ell(\hat{y}_j,f(\mathbf{\hat{x}}_j))}
\end{equation} 
where $\mathcal{B} = \{\mathbf{\hat{y}} \in \{\pm 1\}^{u} | -\beta \leq  \frac{\sum_{j=1}^{u}\hat{y}_j}{u} - \frac{\sum_{i=1}^{l}\hat{y}_i}{l}  \leq \beta \}$ is induced through the balancing constraint that avoids the trivial solution of classifying all unlabeled data to the same class; $\mathcal{H}$ is the \textit{Reproducing Kernel Hilbert Space} induced by a given kernel $K$; $\ell(y,f(\mathbf{x}))$ is the Hinge loss; and $C_1$ and $C_2$ are regularization parameters for trading-off complexity and empirical error on labeled and unlabeled data, respectively.

Note, however, that the minimization problem in~(\ref{eq:s3vm}) is \textit{non-convex}, and thus subject to local minima. Avoiding inappropriate local minima when approaching the optimal solution for the problem in~(\ref{eq:s3vm}) is the main goal towards safe semi-supervised support vector machines, \ie SVMs that never degenerate the performance achieved by a standard supervised approach that only makes use of the labeled data. 

An approach towards safe SVMs was implemented by \cite{Li2011} in the so-called \textit{safe semi-supervised support vector machines} (\sqvms), which works as follows. Let $\mathcal{M} = \{\mathbf{\hat{y}}\}_{t=1}^{T}$ be the set of predictions provided by low-density separators, $\mathbf{y}^*$ be the ground truth label-assignment, and $\mathbf{y}^{svm}$ be the label-assignment provided by an inductive SVM trained with the labeled data. For any given label-assignment $\mathbf{y} = \{\pm 1\}^u$, consider that $earn(\mathbf{y},\mathbf{y^*},\mathbf{y}^{svm})$ denotes the accuracy improvement over the inductive SVM, and that $loss(\mathbf{y},\mathbf{y^*},\mathbf{y}^{svm})$ denotes the respective accuracy loss. If the ground truth $\mathbf{y^*}$ was indeed known, the solution would be trivially found by looking for the $\mathbf{y}$ that maximizes $J(\mathbf{y},\mathbf{y^*},\mathbf{y}^{svm}) = earn(\mathbf{y},\mathbf{y^*},\mathbf{y}^{svm}) - \lambda loss(\mathbf{y},\mathbf{y^*},\mathbf{y}^{svm})$. Since the ground truth is unknown, \sqvm assumes that $y^* \in \mathcal{M}$, and hence the problem can be seen as the one of optimizing the worst-case improvement over the inductive SVM, that is:

\begin{equation}
\mathbf{\bar{y}} = \argmax_{\mathbf{y}\in \{\pm 1\}^u} \min_{\mathbf{\hat{y}}\in \mathcal{M}}J(\mathbf{y},\mathbf{\hat{y}},\mathbf{y}^{svm}).
\end{equation}

Note that \sqvm takes into account all large-margin low-density separators for discovering the optimal labeling $\mathbf{\hat{y}}$. To find diverse low-density separators $\{f_t\}_{t=1}^T$ and their respective label-assignments $\{\mathbf{\hat{y}}_t\}_{t=1}^T$, consider $h(f,\mathbf{\hat{y}})$ as being the function to be minimized in~(\ref{eq:s3vm}). Thus, one has the following objective function:

\begin{equation} \label{eq:diversity}
\min_{\{f_t,\mathbf{\hat{y}}_{t}\in \mathcal{B}\}_{t=1}^T} \sum_{t=1}^{T} h(f_t,\mathbf{\hat{y}}_{t}) + M\Omega(\{\mathbf{\hat{y}}_{t}\}_{t=1}^T)
\end{equation} where $T$ is the number of separators, $\Omega$ is a penalty function regarding their diversity, and $M$ is a large constant (\textit{e.g.}, $10^5$) to enforce large diversity. The objective function in~(\ref{eq:diversity}) favors separators with large-margin as well as with large diversity. Since the optimization problem in~(\ref{eq:diversity}) is non-convex, the authors in~\cite{Li2011} propose a simple heuristic sampling search, based on $k$-means clustering, to find representative separators. For more details on \sqvms, please refer to the original reference \cite{Li2011}.

%DESVANTAGENS DO S4VM - MULTI-CLASS 
As already mentioned, even though \sqvms present several advantages over other transductive learners, they do not naturally deal with multi-class problems (which is also the case of inductive SVMs). Due to various complexities, a direct mathematical solution for multi-class problems using a single SVM formulation is usually avoided \cite{Duan2005}. Multi-class encoding schemes addressed in Section~\ref{sec:introduction}, such as \textit{OVA-WTA}, \textit{OVO-MWV}, and error-correcting output codes \cite{Dietterich1994}, are usually adopted for extending binary classifiers such as SVMs, though each scheme has advantages and disadvantages \cite{Lorena2008}.

It is our impression that the research community does not concentrate enough efforts on providing robust solutions for employing SVMs in multi-class problems (either for supervised or semi-supervised learning). This is probably due to the fact that SVMs can achieve higher accuracy rates with the current multi-class encoding schemes compared to natural multi-class classifiers, such as Decision Trees and Neural Networks. However, extra gains can be achieved by considering better algorithms for learning SVMs  \cite{JMLR04_Rifkin}.


We focus on \textit{divide-and-conquer} approaches which consist of strategies for problem decomposition and aggregation. The use of clustering for decomposing classification problems was studied in \cite{Vilalta03} in the context of Na\"{i}ve Bayes classification. The parameters of the clusters for each class were estimated separately to avoid poor estimates caused by objects in different regions of the input space. In \cite{Barros2012}, the authors propose a mixture of experts algorithm that generates several decision trees from clusters generated by the EM algorithm \cite{Dempster1977}. In \cite{Rida99,Cheng10,Pang11}, a SVM\footnote{In \cite{Rida99}, any classifier can be employed in the framework.} is induced on each cluster found in the input space. If the region covered by one local expert contains objects from more than two classes, it is necessary to use a multi-class scheme, such as OVA-WTA. These approaches require critical parameters to be set, such as the number of clusters per class, which are usually unknown \textit{a priori}.


In \cite{Vural04,Fei06,Tibshirani07,Lorena2010,Liu11}, the multi-class problem is decomposed into a binary tree of SVM classifiers. These algorithms assume that each class is comprised of a single cluster. They also require the selection of a suitable kernel, as well as its parameters, a task which is often determined by a cross-validation procedure. However, for transductive learning settings in which only a small number of labeled objects is available, cross-validation procedures become impractical. Hence, there is a need for algorithms able to combine different linear SVMs, which are known for being state-of-the-art classifiers for binary problems, in order to create complex decision boundaries for multi-class problems when classes are multimodal. In \cite{Barros2011}, the authors propose a decomposition scheme with SVM for inductive learning that does not consider the one-cluster-per-class assumption. Nevertheless, the authors employ a cross-validation procedure for discovering the number of clusters per class, which is not possible when only a few labeled objects are available, as just discussed.

Our approach differs from the previously presented algorithms as it is the first attempt that simultaneously circumvents three of their fundamental issues by: (i) employing a constrained clustering algorithm capable of estimating the number of clusters for each class; (ii) using an aggregation scheme based on a binary tree that guarantees that we always consider binary problems, regardless of how many classes the problem is comprised of; and (iii) not requiring additional user-defined parameters other than the ones already needed for \sqvm.


\section{Hierarchical Bottom-Up \sqvm Tree (\hbust)} \label{sec:hbus}

As briefly anticipated in Section~\ref{sec:s3vm}, we propose a new method for addressing \sqvm issues regarding multi-class problems. Our approach is named \textit{Hierarchical Bottom-Up \sqvm Tree} (\hbust). Essentially, our underlying premise is that some transduction problems are quite difficult to solve when executing a single \sqvm and, in such problems, clustering the data set into smaller sub-problems and addressing these smaller problems can make it easier to solve the original problem. Formally speaking, our algorithm approximates the target function in specific regions of the input space, instead of making use of the full input space. These specific regions are not randomly chosen, but defined through a constrained \kmeans-based clustering algorithm. 


More specifically, \hbust's main steps can be summarized as follows:
\begin{enumerate}
\item decompose classes into clusters (sub-problems) by using a semi-supervised constrained clustering algorithm;
\item label some objects \textit{iff} the data partition generated by the constrained clustering algorithm provides confidence-levels suitable for such, and then make use of them accordingly (as discussed later); 
\item build a binary tree in a bottom-up fashion by merging sub-problems according to the distances between centroids;
\item process unlabeled objects, in a top-down fashion, by traversing them through the tree according to the output of the \sqvm for each node of the tree, and then label these objects according to the classes of the leaves they have reached.
\end{enumerate}

Step (2) is optional --- it may be used to increase the number of labeled objects so that more evidence is available to \sqvm. Each of these steps is described in detail in the next subsections.



\subsection{Step 1 --- Problem Decomposition}
\label{sec:mcck}

To perform clustering considering the information about the classes of each object, we adopt what we call a Multiple Clusters per Class \kmeans (MCCK) algorithm \cite{SBRN12_Sestaro}.
MCCK receives partial information about the desired partition in the form of must-link (ML) and cannot-link (CL) constraints \cite{ICML01_Wagstaff}.
A ML constraint indicates that two objects should lie in the same cluster, whereas a CL constraint  indicates that two objects should lie in different clusters.
For a review on constrained clustering, we refer the reader to \cite{BOOK08_Basu} and references therein.

Since we assume the availability of a small set of labeled objects, we can derive pairwise constraints from the class labels. However, there is a caveat on the use of the information provided by class labels, particularly due to the (sometimes subtle) difference between class and cluster labels. Since classes can be comprised of multiple clusters, the use of the information provided by class labels for enhancing clustering results may be misleading. More specifically, if two objects belong to the same class but to different clusters, a ML constraint between them will guide the clustering algorithm to merge these two clusters, which can be detrimental to the clustering process.

Note that CL constraints are valid as long as the \textit{cluster assumption}, which states that objects in the same cluster are likely to come from the same class \cite{BOOK06_Chapelle}, holds. In other words, the use of class labels as if they were cluster labels, implies in the \textit{one-cluster-per-class} assumption.
Although this assumption is often employed in practice, it is rarely explicitly stated in constrained clustering studies, possibly causing misunderstandings. To avoid this confusion, we denote constraints deduced from class labels by $\ML$ and $\CL$, \ie $\ML$ indicates that two objects belong to the same class, whereas $\CL$ indicates that two objects belong to different classes. A set of constraints is represented by a symmetric matrix $\mathbf{R}_{N \times N}$ ($N$ is the total number of objects), where:

\begin{equation}
	r_{ij} = \begin{cases}
		1, & \mbox{if a $\ML$ constraint between $\x_i$ and $\x_j$ exists,} \\
		-1, & \mbox{if a $\CL$ constraint between $\x_i$ and $\x_j$ exists,} \\
		0, & \mbox{otherwise.}
	\end{cases}
	\label{eqn:const_matrix}
\end{equation}


The intuition behind MCCK is that if a constraint is violated as an object is assigned to a cluster, the current number of clusters (for that particular class) may be insufficient, and a new cluster should be created from that object. Initially, there are $c$ clusters, \ie one for each class. Due to the process of creating clusters, a mapping is necessary to control which clusters belong to each class. Initially, this mapping has a one-to-one correspondence between classes and clusters. The mapping is updated when new clusters are created --- later this update procedure is described in more detail. MCCK sequentially assigns objects to the nearest clusters. However, objects involved in constraints are only assigned to a cluster if the constraints are not violated. Since we do not assume that there is only a single cluster per class, the constraints are not verified by simply taking into account the objects of each cluster. Instead, we do so by jointly considering classes and their respective clusters.

For instance, suppose that we have two objects, $\x_i$ and $\x_j$. Suppose $\x_i$ has been assigned to cluster $C_n$, whose prototype is $\mu_n$. Further assume that $r_{ij}=1$ and that $\cent_m$ is the nearest prototype to $\x_j$. Then, $\x_j$ will be assigned to $C_m$ only if $C_m$ and $C_n$ belong to the same class --- this is verified through the mapping previously mentioned. If the clusters belong to different classes, a new cluster is created, and its prototype is $\x_j$. For the mapping update, first the class that $\x_j$ belongs to is identified. Next, the new cluster is added to the mapping of that class. Clearly, this process is order-dependent. To alleviate this problem, at each iteration the objects are processed in a random order. After all objects have been assigned to clusters, their prototypes (in this case centroids) are updated.

As the creation of clusters is also order-dependent, \textit{unnecessary} clusters may arise. A pair of unnecessary clusters occurs when their prototypes are nearest neighbors, and both belong to the same class. Hence, after the prototypes have been updated, we verify if a pair of clusters meets this criterion. If this is the case, those two clusters are merged. The prototype of this new cluster will be the average vector of the two merged prototypes. Again, the mapping between clusters and classes is updated accordingly.

The main steps of MCCK are described in Figure \ref{alg:ckmeans}, where $d(\x_i,\cent_n)=\|\x_i-\cent_n\|^2$.
Step~\ref{algl:check} verifies if the assignment will cause a constraint to be violated.
Note that even though $\ML$ constraints are not directly verified, they are implicitly examined by checking the classes.
As each cluster belongs to a single class, the $\ML$ constraints will not be violated, as long as two objects in a $\ML$ constraint belong to clusters of the same class.
The same termination criteria commonly used in \kmeans can be adopted, \eg a maximum number of iterations or a minimum distance between consecutive centroids.
At the end of its execution, MCCK provides a mapping $\{\mathcal{H}_i\}_{i=1}^c$ with the indices of the clusters that belongs to each class, as well as the partition itself ($\{C_i\}_{i=1}^k$).



\begin{figure}[ht]
	\center
	\small
	\begin{algorithmic}[1]
		\Function{MCCK}{$\mathcal{X}=\{\mathcal{X}^{(U)} \cup \mathcal{X}^{(L)}\},\mathbf{R}$}
		%\State Derive (new) constraints by using transitivity and entailment properties
		\State $k \gets c$ \Comment{One cluster for each class}
		\ForAll{$j \in \{1,\dots,k\}$}
		\State Let $\x_r$ be an object randomly selected from the $j$th class
		\State $\cent_j \gets \x_r$
	%	\State $C_j \gets \{\x_r\}$
		\State $\mathcal{H}_j \gets \{j\}$ \Comment{Mapping between clusters and classes}
		\EndFor
		\ForAll{$\x_i \in \mathcal{X}$}\label{algl:pick}
		\State $n \gets \argmin_{n \in \{1,\dots,k\}} d(\x_i,\cent_n)$
		\State Consider that $n \in \mathcal{H}_{c_n}$ 
		%\State $c_n \gets \{ c | n \in \mathcal{H}_c \}$
		\If{$\{\exists a,j,s | (r_{ia}=-1) \wedge (\x_a \in C_j) \wedge (C_j \in \mathcal{H}_s) \wedge (s = c_n) \}$}\label{algl:check}
		\State $k \gets k + 1$
		\State Consider that $\x_i$ belongs to the $v$th class
		\State $\mathcal{H}_{v} \gets \mathcal{H}_{v} \cup \{k\}$
		\State $\cent_k \gets \x_i$
		\State $C_k \gets \{\x_i\}$
		\Else
		\State $C_n \gets C_n \cup \{\x_i\}$
		\EndIf
		\EndFor
		\State Update prototypes \label{algl:updMu}
		\ForAll{pair $(C_p,C_q)$ of clusters}
		\State $n \gets \argmin_{n \in \{1,\dots,k\}\backslash\{p\}} d(\cent_p,\cent_n)$
		\State $m \gets \argmin_{m \in \{1,\dots,k\}\backslash\{q\}} d(\cent_q,\cent_m)$
		\State Consider that $p \in \mathcal{H}_{c_p}$
		\State Consider that $q \in \mathcal{H}_{c_q}$
		%\State $c_i \gets \{ c | i \in \mathcal{H}_c \}$
		%\State $c_j \gets \{ c | j \in \mathcal{H}_c \}$
		\If{$c_p = c_q \wedge n = q \wedge m = p$}
		\State Merge clusters $C_p$ and $C_q$ \label{algl:merge}
		\State Update the mapping $\mathcal{H}_{c_p}$ \label{algl:updH}
		\EndIf
		\EndFor
		\State If the convergence criterion was not met, then go to Step \ref{algl:pick}
		\State Return $\{\mathcal{H}_i\}_{i=1}^c$ (mapping) and $\{C_i\}_{i=1}^k$ (data partition)
		\EndFunction
	\end{algorithmic}
\caption{Multiple Clusters per Class \kmeans algorithm (MCCK)}
\label{alg:ckmeans}
\end{figure}


\subsection{Step 2 --- Confidence-based Labeling}
\label{sec:lbl_auto}

When performing \kmeans-based clustering, the assumption is that the data is generated by a Gaussian Mixture Model (GMM), where each component (Gaussian distribution) is a cluster. In this case, the component mean is the cluster centroid and the covariance matrix is the identity matrix. In addition, it is well-known that \kmeans performs hard-assignments, \ie the probability that one object is generated by a component is either 0 or 1. For the purpose of obtaining a degree of belief with respect to which cluster generated each object, one can convert the crisp partition obtained by MCCK into a soft partition by computing the posterior probabilities given by the GMM that represents the respective data partition. Specifically, the probability that ($\x_i$) is generated by the component ($C_j$) is:

\begin{equation}
	P(j|\x_i) = \frac{\pi_j \norm{i}{j}}{\sum_{n=1}^k \pi_n \norm{i}{n}},
	\label{eqn:posterior}
\end{equation}
where $\mathcal{N}(\cdot)$ is the Gaussian distribution, $\mathbf{I}$ is the identity matrix, $\pi_j$ is the mixing coefficient of the $j$th component, \ie the proportion of objects assigned to it by the hard-assignment, and $k$ is the number of components.

Assuming a user-defined threshold, $\theta$, one can label objects that have a high probability of belonging to a cluster, following standard procedures widely used in semi-supervised settings. More precisely, assuming that every cluster centroid is a representative vector of a given class, $y_i = c_j$ \textit{iff} $P(j|\hat{\x}_i) > \theta$, $\forall \hat{\x}_i \in \mathcal{X}^{(U)}$ , where $c_j$ is the class represented by the cluster centroid ($\cent_j$). Both $\mathcal{X}^{(L)}$ and $\mathcal{X}^{(U)}$ are updated accordingly.
Informally speaking, the confidence level ($\theta$) can be seen as a certainty measure that the model has about an object being sampled from a particular cluster and, as a consequence, from a particular class.

\subsection{Step 3 --- Tree Construction}
\label{sec:tc}


The clusters obtained by MCCK correspond to the leaves of the binary tree to be constructed. Note that several different groups may have labeled objects that share the same class, since we generate at least one leaf~per~class.

After creating the leaves, a recursive procedure is initiated. A new group (internal node) is generated by merging the two most similar nodes, \ie those whose centroids are the closest according to the Euclidean distance. Once a node is created, its corresponding objects (that came up from its children) have their class label replaced by a new unique \textit{pseudo-class}. Since we focus on binary trees, each node is merged only once. If the two closest leaf nodes are from the same class, a new leaf node is created with the union of the objects belonging to each node, and the old nodes are deleted, \ie they do not appear in the resulting tree. The recursion stops when there is only one group (root node) that has not been merged.  The tree construction procedure is described in Figure~\ref{alg:treec}.

Each node in the tree (leaf or internal) is comprised of three components:
\begin{enumerate}
\item \textit{labeledInst}: the set of labeled objects in the node;
\item \textit{class}: the actual class (\textit{pseudo-class}) that this leaf (internal) node corresponds to;
\item \textit{centroid}: the mean vector of the labeled objects.
\end{enumerate}




\subsection{Step 4 --- Tree-based Labeling}
\label{sec:lbl}

Once the tree has been built, we can distribute the unlabeled objects through the tree, starting from the root node. 
For such, a \sqvm is created for each internal node, which will be responsible for defining which path (left or right) the objects will be distributed to.
Recall that the children of a node come from two different classes (for leaf nodes) or pseudo-classes (for internal nodes). Thence, \sqvm needs only to deal with binary problems, regardless of the number of classes in the original data set --- which means its application is straightforward and does not rely on any voting scheme between pairwise class subsets.
At the end of the process, each object will be at a leaf node, and its predicted label is the label of the class corresponding to that leaf.
This recursive process is summarized in Figure \ref{alg:trans}.

\begin{figure}
	\center
	\small
	\begin{algorithmic}[1]
		\Function{TreeConstruction}{$\mathcal{X}^{(L)}, \{\mathcal{H}_i\}_{i=1}^c, \{\mathcal{C}_i\}_{i=1}^k$}
		\State $Leaves \leftarrow \emptyset$\;
		\ForAll{$\mathcal{H}_i \in \{\mathcal{H}_i\}_{i=1}^c$}
			\ForAll{$j \in \mathcal{H}_i$}
				\State 	create new leaf node $n$
				\State $n.labeledInst \leftarrow \{ \x_r \in C_j \mid \x_r \in \mathcal{X}^{(L)}\} $
				\State $n.centroid \leftarrow$ mean vector of $n.labeledInst$
				\State $n.class \leftarrow i$ 
				\State $Leaves \leftarrow Leaves \cup \{n\} $
			\EndFor
		\EndFor
		\State $root \leftarrow \textsc{Merging}(Leaves)$
		\State Return $root$
		\EndFunction
		\Statex
		\setcounter{ALG@line}{0}
		 \Function{Merging}{$L$} 
		\If{$|L|$ = 1}
			\State Return unique node in $L$ (root)
		\Else
			\State Let $n_1$ and $n_2$ be the two nodes from $L$ with the closest centroids according to the Euclidean distance
					\If{$n_1.class = n_2.class$}
				\Comment{Merge leaves}
				\State create leaf node $t$
				\State $t.class \leftarrow n_1.class$
			\Else
				\State create new internal node $t$
				\State $t.leftChild \leftarrow n_1$
				\State $t.rightChild \leftarrow n_2$
				\State $t.class \leftarrow$ new unique pseudo-class
			\EndIf
			\State $t.labeledInst \leftarrow n_1.labeledInst \cup n_2.labeledInst$
			\State $t.centroid \leftarrow$ mean vector of $t.labeledInst$
			\State $L \leftarrow L \cup \{t\}$
			\State $L \leftarrow L \setminus  \{n_1\}$
			\State $L \leftarrow L \setminus  \{n_2\}$
			\State Return \textsc{Merging}$(L)$	
		\EndIf
		\EndFunction
	\end{algorithmic}
	\caption{Tree construction procedure.}
	\label{alg:treec}
\end{figure}

\begin{figure}
	\center
	\small
	\begin{algorithmic}[1]
		\Function{Classify}{$root, \mathcal{X}^{(U)}$}
		\If{\textsc{isLeaf}($root$)}
			\State $Pred \leftarrow \emptyset$
			\ForAll{$\hat{\x}_i \in \mathcal{X}^{(U)}$}
				\State $Pred \leftarrow Pred \cup \{(\hat{\x}_i,root.class)\}$
			\EndFor
		\Else
			\State $negObj \leftarrow root.leftChild.labeledInst$
			\State $posObj \leftarrow root.rightChild.labeledInst$
			\State $r \leftarrow \sqvm(negObj, posObj, \mathcal{X}^{(U)})$
			\State Let $\mathcal{X}^{(n)}$ be all unlabeled objects classified as negative
			\State Let $\mathcal{X}^{(p)}$ be all unlabeled objects classified as positive
			\State $Pred \leftarrow \textsc{Classify}(root.leftChild$, $\mathcal{X}^{(n)}$)
			\State $Pred \leftarrow Pred \cup \textsc{Classify}(root.rightChild, \mathcal{X}^{(p)}$)
		\EndIf 
			\State \Return $Pred$
		\EndFunction
	\end{algorithmic}
	\caption{\hbust's classification procedure.}
	\label{alg:trans}
\end{figure}


\subsection{An Illustrative Example}

Now that each step of \hbust has been detailed, it is useful to present an illustrative example of its execution mode. For such, consider again the pedagogical example from Figure~\ref{fig:ex1}. The result of the decomposition applied in Step~1 is presented in Figure~\ref{fig:exm}. We can observe that the class previously represented by red circles (a few labeled objects) has been split into two clusters (red stars and green pentagons). For the sake of simplicity, we assume that confidence levels (Step~2) are here not employed to label objects, \ie the optional parameter $\theta$ has not been informed by the user. 

\begin{figure}
	\begin{center}
	\captionsetup[subfloat]{width=\linewidth}
	\subfloat[Result of classes to clusters decomposition (Step~1). Different markers represent different clusters and the centroid of each cluster is denoted by a square. See Fig. \ref{fig:ex1} for a description of the classes.]{\includegraphics[scale=0.3]{../fig/ex_part_mcck_final.pdf}
	\label{fig:exm}}\\ 
%\hspace{0.5cm}
	\subfloat[Tree obtained after the first merge performed by the aggregattion scheme (Step~3). Leaves are represented by circles with the symbol of the corresponding class inside, and the labeled objects  are presented in each leaf according to the cluster they were assigned to. Each internal node is represented by a rectangle with the definition of the binary sub-problem that it addresses.]{\includegraphics[scale=0.3]{../fig/ex_part_arvore_p1.pdf}
	\label{fig:exa1}}\\
	\subfloat[Final tree obtained by the aggregattion scheme (Step~3).]{\includegraphics[scale=0.3]{../fig/ex_part_arvore_final.pdf}
	%Leaves are represented by circles with the symbol of the corresponding class inside, and the labeled objects  are presented in each leaf according to the cluster they were assigned to. Each internal node is represented by a rectangle with the definition of the binary sub-problem that it addresses.
	\label{fig:exaf}}
	\end{center}
	\caption{\hbust's main steps for the pedagogical example.}
	\label{fig:examp}
\end{figure}


Considering the three clusters generated by MCCK (sub-problems), the binary tree can be built in a bottom-up fashion. First, the closest pair of centroids is identified --- in this case, the centroids of the clusters represented by yellow left-triangles and green pentagons. An internal node is thus created by merging these sub-problems. 
Figure \ref{fig:exa1} illustrates the tree at this stage.
Next, the root node is created by merging the recently created internal node with the sub-problem related to the cluster represented by the red stars. The final tree is illustrated in Figure \ref{fig:exaf}.




In order to label the unlabeled data (blue squares in Figure~\ref{fig:ex1}), the tree is used as a mechanism to filter the data, starting from the root node down to the leaves. A \sqvm is used to label the objects as belonging to either the red-star class or to the pseudo-class that represents the remaining data. Objects classified as belonging to the red-star class follow directly to the corresponding red-circle's leaf node. 

The remaining objects are processed in another internal node, which uses a \sqvm to label objects as either belonging to the green-pentagon class or to the yellow-left-triangle class. Again, according to the result of this particular \sqvm, objects follow to their corresponding leaf (red circles or black diamonds).


\section{Experimental Analysis} \label{sec:experiments}

In this section, we present the experimental methodology and the results obtained to validate the effectiveness of \hbust for solving semi-supervised transductive learning problems.

           
\subsection{Methodology}

We compare \hbust to \sqvm \cite{Li2011}, which is a state-of-the-art transductive SVM method. Experiments were performed on 10 data sets commonly used as benchmarks in the literature. 
Most of them are available at the UCI repository \cite{Frank+Asuncion2010}. 
We have used the 9Gauss data set \cite{Campello2009}, which is comprised of 9 balanced clusters (each cluster is considered as a class) arranged according to Gaussian distributions that have some degree of overlapping. Besides, we have employed the USPS data set, which is a well-known semi-supervised learning benchmark data set \cite{BOOK06_Chapelle}. Following \cite{Bilenko2004}, for the Pendigits data set, only the classes 3, 8, and 9 were considered, since they represent a difficult classification problem \cite{Bilenko2004}. Table~\ref{tab:data} describes the data sets employed in the experiments.

For all data sets, we randomly selected 10, 20, and 30 objects per class to be used as labeled data, and the remaining objects were used as unlabeled data. 
The experiments were repeated 10 times and the average accuracies and standard deviations were recorded. 
Since MCCK is initialization-dependent, for each experiment we run MCCK 10 times and selected the partition with the best simplified silhouette value \cite{IS06_Hruschka}. The simplified silhouette is a relative validity criterion that can be used to choose, among a set of different data partitions, the best available clustering.
For all the employed \sqvm, we used the MATLAB implementation from the authors of \cite{Li2011}\footnote{\url{http://lamda.nju.edu.cn/Default.aspx?Page=code_S4VM}}, using default values for its parameters and a linear kernel.
In \cite{Li2011}, the authors show evidence that \sqvm is robust to the selection of its parameters.
For data sets with more than two classes, we execute \sqvm in a \textit{one-versus-one} classification scheme with a \textit{max-wins-voting} strategy (\textit{OVO-MWV}).

\begin{table}
\caption{Summary of the employed data sets.}
\label{tab:data}
\centering
\begin{tabular*}{\columnwidth}
	{@{\extracolsep{\fill}}lrrrrr}
\toprule
 data set & \#objects & \#attributes & \#classes & class distribution & source \\
\midrule
9Gauss & 900 & 2 & 9 & 100 (all) & \cite{Campello2009} \\
Balance-Scale & 625 & 4 & 3 & 288-49-288 &  \cite{Frank+Asuncion2010} \\
Ionosphere & 351 & 34 & 2 & 126-225 & \cite{Frank+Asuncion2010} \\
Iris & 150 & 4 & 3 & 50 (all) & \cite{Frank+Asuncion2010} \\
Mfeat & 2000 & 6 & 10 &  200 (all) & \cite{Frank+Asuncion2010}\\
Pendigits & 3165 & 16 & 3 & 1055 (all) &  \cite{Frank+Asuncion2010} \\
Segment & 2310 & 19 & 7 & 330 (all) & \cite{Frank+Asuncion2010} \\
USPS & 1500 & 241 & 2 & 1200-300 & \cite{BOOK06_Chapelle} \\
Vehicle & 846 & 18 & 4 & 212-217-218-199 & \cite{Frank+Asuncion2010} \\
Wine & 178 & 13 & 3 & 59-71-48 & \cite{Frank+Asuncion2010} \\
\bottomrule
\end{tabular*}
\end{table}

We report two kinds of experimental analyses. 
First, in Section \ref{sec:cmp}, we compare the results of \hbust to the \sqvm algorithm \cite{Li2011}.
For these comparisons, we assume that the user has not provided a value for the $\theta$ parameter, \ie we do not use confidence-based labeling (optional Step~2).
Later, in Section \ref{sec:cmp_lbl}, we analyze the impact of using the confidence-based labeling in the classification accuracy.



\subsection{Results} %or discussion
\label{sec:cmp}

\begin{table}
\caption{Average accuracy $\pm$ standard deviation for different amounts of labeled objects per class (\#LO).}
\label{tab:results}
\centering
\begin{tabular*}{\columnwidth}
	{@{\extracolsep{\fill}}clrr}
\toprule
\multirow{2}{*}{\#LO} &  \multirow{2}{*}{Data sets}  &   \multirow{2}{*}{\sqvm}  &   \multirow{2}{*}{\hbust}   \\
& & &  \\
 \midrule

\multirow{11}{*}{10}  &  Ionosphere  &  0.74 $\pm$ 0.04  &  \textbf{0.78 $\pm$ 0.05}  \\
        	  &        USPS  &  \textbf{0.75 $\pm$ 0.05}  &  \textbf{0.75 $\pm$ 0.05}  \\
            &      9Gauss  &  0.67 $\pm$ 0.04  &  \textbf{0.85 $\pm$ 0.02}  \\
            &        Iris  &  0.81 $\pm$ 0.04  &  \textbf{0.92 $\pm$ 0.02}  \\
            &       Mfeat  &  0.60 $\pm$ 0.04  & \textbf{ 0.64 $\pm$ 0.01}  \\
            &        Wine  &  0.87 $\pm$ 0.02  &  \textbf{0.94 $\pm$ 0.01}  \\
            &   Pendigits  &  0.96 $\pm$ 0.02  &  \textbf{0.96 $\pm$ 0.01}  \\
            &     Segment  &  \textbf{0.84 $\pm$ 0.03}  &  0.81 $\pm$ 0.02  \\
            &  Balance-Scale  &  \textbf{0.82 $\pm$ 0.04}  &  0.57 $\pm$ 0.04  \\
            &     Vehicle  &  \textbf{0.59 $\pm$ 0.03}  &  0.50 $\pm$ 0.03  \\

 \midrule

\multirow{11}{*}{20}   &  Ionosphere  &  0.74 $\pm$ 0.04  &  \textbf{0.81 $\pm$ 0.03}  \\
            &        USPS  &  0.77 $\pm$ 0.04  &  \textbf{0.78 $\pm$ 0.04}  \\
            &      9Gauss  &  0.70 $\pm$ 0.05  &  \textbf{0.88 $\pm$ 0.01}  \\
            &        Iris  &  0.86 $\pm$ 0.02  &  \textbf{0.94 $\pm$ 0.01}  \\
            &       Mfeat  &  0.59 $\pm$ 0.02  &  \textbf{0.65 $\pm$ 0.01}  \\
            &        Wine  &  0.90 $\pm$ 0.04  &  \textbf{0.94 $\pm$ 0.01}  \\
            &   Pendigits  &  \textbf{0.98 $\pm$ 0.00}  &  0.97 $\pm$ 0.01  \\
            &     Segment  &  \textbf{0.87 $\pm$ 0.02}  &  0.85 $\pm$ 0.01  \\
            &  Balance-Scale  &  \textbf{0.90 $\pm$ 0.01}  &  0.60 $\pm$ 0.02  \\
            &     Vehicle  &  \textbf{0.66 $\pm$ 0.02}  &  0.55 $\pm$ 0.01  \\

 \midrule

 \multirow{11}{*}{30}   &  Ionosphere  &  0.74 $\pm$ 0.04  &  \textbf{0.84 $\pm$ 0.01} \\
             &        USPS  &  0.78 $\pm$ 0.02  &  \textbf{0.83 $\pm$ 0.04} \\
             &      9Gauss  &  0.69 $\pm$ 0.04  &  \textbf{0.88 $\pm$ 0.02}  \\
             &        Iris  &  0.94 $\pm$ 0.02  &  \textbf{0.94 $\pm$ 0.01}  \\
             &       Mfeat  &  0.61 $\pm$ 0.03  &  \textbf{0.66 $\pm$ 0.01}  \\
   			   &        Wine  &  \textbf{0.93 $\pm$ 0.01}  &  \textbf{0.93 $\pm$ 0.01} \\
   			   &   Pendigits  &  \textbf{0.98 $\pm$ 0.00}  &  0.97 $\pm$ 0.01 \\
   			   &     Segment  &  0.85 $\pm$ 0.02  &  \textbf{0.86 $\pm$ 0.01} \\
             &  Balance-Scale  &  \textbf{0.91 $\pm$ 0.00}  &  0.62 $\pm$ 0.03  \\
             &     Vehicle  &  \textbf{0.69 $\pm$ 0.02} &  0.57 $\pm$ 0.02  \\
            \bottomrule
            \end{tabular*}
\end{table}

Table \ref{tab:results} presents the mean accuracy obtained by \sqvm and \hbust for each data set.
First, consider the results for the two binary-class data sets, namely Ionosphere and USPS.
For both of them, \hbust obtained equal or better results than \sqvm, regardless of the number of labeled objects. These results suggest that these data sets fit into the category of data whose number of clusters per class is greater than one. For this kind of data set, combining different linear boundaries indeed results in an increased classification performance, as we have previously assumed when presenting our method. Hence, we believe \hbust can be a better option than \sqvm even for binary-class problems, specially considering the lack of sufficient labeled objects for tuning a kernel.

Now, consider the 9Gauss and Iris data sets, which have 9 and 3 classes, respectively. Roughly speaking, one could take for granted that these data sets are comprised by one cluster per class --- although this is somehow arguable for the Iris data, as it has been extensively discussed in the literature. Both of them have overlapping classes, which is detrimental for SVM-based methods. Bearing this in mind, the use of a decomposition scheme that breaks the problem into sub-problems is, once again, beneficial. More specifically, MCCK creates clusters in the overlapping areas among classes, which is helpful for classifying objects in such specific regions.
This can be seen by the accuracy results of \hbust in these data sets, which are better than the ones obtained by \sqvm for all amounts of labeled objects.

The results for the Mfeat and Wine data sets are also favorable for \hbust. For the Pendigits and Segment data sets, \sqvm presented slightly better results than \hbust on average.
In the remaining data sets --- Balance-Scale and Vehicle --- \sqvm outperformed \hbust. Note that Balance-Scale is a highly imbalanced data set, and this seems to indicate that \hbust is sensitive to imbalanced data. Considering that imbalanced problems are common in several applications, we plan to investigate in detail this problem in future work.


\subsection{Sensitivity of confidence-based labeling}
\label{sec:cmp_lbl}


For assessing the impact of Step~2 (confidence-based labeling) in \hbust, we varied $\theta$ within $\{0.7, 0.8, 0.9\}$.
We believe that these values cover distinct scenarios --- from average to high confidence --- for increasing the number of labeled objects available to induce the classifier.
For most data sets, there were no objects labeled considering these probabilities. 
Thus, their respective results with these different values of $\theta$ are the same as those presented in the previous section.

Nevertheless, for two data sets (USPS and Ionosphere) different results were obtained through the confidence-based labeling.
For instance, consider Figures~\ref{fig:vartheta_usps}~and~\ref{fig:vartheta_iono}, which present the number of objects labeled from Step~2 and the mean accuracy obtained by \hbust for the different values of $\theta$.
For the mean accuracy, we replicate the results without using the confidence-based labeling (\ie $\theta=1.0$).
Observe that, for the USPS data set, the number of objects labeled was quite large (more than 100) even for $\theta = 0.9$.
This suggests that some of its clusters are very dense and well-separated. Through this mechanism of confidence-based labeling, more labeled data were available for each \sqvm within an internal nodes of \hbust. Hence, \sqvm was able to select better hyperplanes which, in turn, resulted in better predictive performance. 

For the Ionosphere data set, the clusters seem to be less dense, and just a few objects had probabilities greater than 0.9 of being generated by the Gaussian that represents its cluster.
When labeling objects with smaller values of $\theta$ ($\theta=0.8$ and $\theta=0.7$), the accuracy of \hbust decreases comparatively to the results obtained without confidence-based labeling.
As expected, these results suggest that it is worth employing a high value of $\theta$ (such as $\theta = 0.9$), given that in most cases an equal or better predictive performance was achieved when compared to the absence of the confidence-based labeling scheme.


\begin{center}
\begin{figure}
	\subfloat[Accuracy.]{
	\begin{minipage}{0.45\linewidth}
	\begin{sideways} \hspace{2cm} Accuracy \end{sideways}
	\includegraphics[scale=0.25]{../fig/usps-accuracy.pdf}
	\begin{center} \hspace{0.6cm} Initial amount of labeled objects \end{center}				
	\end{minipage}
	\label{fig:theta_acc_usps}}
	\hspace{0.05\linewidth}
	\subfloat[Number of objects labeled based on confidence.]{
	\begin{minipage}{0.45\linewidth}
	\begin{sideways} \hspace{0.3cm}Objects (\#) labeled in Step 2\end{sideways}
	\includegraphics[scale=0.25]{../fig/usps-objetos.pdf}
	\begin{center} \vspace{-0.2cm} \hspace{0.3cm} Initial amount of labeled objects \end{center}				
	\end{minipage}
	\label{fig:theta_nlo_usps}}
	\caption{Results obtained varying $\theta$ --- USPS data set.}
	\label{fig:vartheta_usps}
\end{figure}
\end{center}

\begin{figure}
	\begin{center}
	\subfloat[Accuracy.]{
	\begin{minipage}{0.45\linewidth}
	\begin{sideways} \hspace{2cm} Accuracy \end{sideways}
	\includegraphics[scale=0.25]{../fig/ionosphere-accuracy.pdf}
	\begin{center} \vspace{-0.1cm} \hspace{0.6cm} Initial amount of labeled objects \end{center}				
	\end{minipage}
	\label{fig:theta_acc_iono}}
	\hspace{0.05\linewidth}
	\subfloat[Number of objects labeled based on confidence.]{
	\begin{minipage}{0.45\linewidth}
	\begin{sideways} \hspace{0.3cm} Objects (\#) labeled in Step 2\end{sideways}
	\includegraphics[scale=0.25]{../fig/ionosphere-objetos.pdf}
	\begin{center} \vspace{-0.2cm} \hspace{0.3cm} Initial amount of labeled objects \end{center}			
	\end{minipage}
	\label{fig:theta_nlo_iono}}\\
	\end{center}
	\caption{Results obtained varying $\theta$ --- Ionosphere data set.}
	\label{fig:vartheta_iono}
\end{figure}




\section{Conclusions}\label{sec:conclusions}

In this article, we presented a new aggregation scheme for safe semi-supervised support vector machines based on a binary tree built in a bottom-up fashion. This method, named \hbust, allows a binary SVM to naturally deal with multi-class transductive problems. It takes advantage of both class information and distances between data objects for dividing the complex input space into sub-spaces, with the underlying assumption that sub-problems are easier to solve than the whole classification problem. In addition, it assumes that the objects of the classes may be distributed across distinct clusters and thus objects from the same class can lie on different regions of the input space. 

We performed an empirical analysis of \hbust by comparing it to \sqvm \cite{Li2011} in 10 classification problems, considering different amounts of labeled objects.
In the performed analyses, \hbust presented equal or better predictive performance than \sqvm in the majority of the cases.
Besides, results for two binary-class data sets suggested that \hbust can also be useful for such problems, specially if the amount of labeled objects is insufficient for tuning a kernel.
We also analyzed a scheme to label objects based on the confidence provided by the constrained clustering algorithm employed by \hbust.
Results suggest that the confidence-based labeling scheme can provide increased performance. Indeed, when high-confidence objects are labeled, each \sqvm within an internal node of the tree created by \hbust presented better capability of separating objects from different classes.

As future work, we plan to investigate the use of the Expectation Maximization (EM) algorithm \cite{Dempster1977} for refining the parameters of each cluster obtained by MCCK and thus obtaining better estimates of the confidence-based labeling probabilities.
In addition, an analysis on the use of \hbust for imbalanced multi-class problems is a promising future work.




	
% INCLUDE BIBLIOGRAPHY WHICH MUST FOLLOW jidm.bst TEMPLATE
\bibliographystyle{jidm}
\bibliography{refs.bib}

\begin{received}
\end{received}

\end{document}
