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

\usepackage[utf8x]{inputenc}
\usepackage[english]{babel}

%adicionei
%\RequirePackage{fix-cm}
\usepackage[ruled, linesnumbered, vlined]{algorithm2e}
\usepackage{multirow}
\usepackage{bigstrut}
\usepackage{scalefnt}
\usepackage{ tipa }



%\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{5}
\jidmNumber{1}
\jidmYear{16}
\jidmMonth{June}
\setcounter{page}{1}


% Includes headers with simplified name of the authors and article title
\markboth{author names, omitted due to blind review}
{Combining semi-supervision and \textit{hubness} to enhance high-dimensional data clustering}
%  -> \markboth{}{}
%         takes 2 arguments
%         ex: \markboth{M. M. Moro}{Any article title}


% Title of the article
\title{Combining semi-supervision and \textit{hubness} to enhance high-dimensional data clustering}


% 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{omitted due to blind review}



\institute{omitted\\ \email{xxxxx@dominio}
%\and Universidade Federal Fluminense, Brazil \\ \email{vanessa@ic.uff.br}
% IF THERE IS ANOTHER INSTITUTION:
%\and Name_of_the_second_institution \\
%\email{address@whatever.com}
}


% Article abstract - it should be from 100 to 300 words
\begin{abstract}
The \textit{curse of dimensionality} turns the high-dimensional data analysis a challenging task for data clustering techniques.
Recent works have efficiently employed an aspect inherent to high-dimensional data in the proposal of clustering approaches guided by \textit{hubs} which provide information about the distribution of the data instances among the \textit{$K$-nearest neighbors}.
Though, \textit{hubs} can not well reflect the implicit data semantics, leading to an unsuitable data partition. 
In order to cope with both issues (i.e., high-dimensional data and meaningful clusters), this paper presents a clustering approach that explores the combination of two strategies: semi-supervision and density estimation based on \textit{hubness scores}.
The experimental results conducted with 23 real datasets show that the proposed approach has a superior performance when applied on datasets with different characteristics.
\end{abstract}


% ACM Computing Classification System categories
\category{H.2.8}{Database Applications}{Data mining} 
\category{H.3.3}{Information Storage and Retrieval}{Clustering}

% 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{Data Mining, High-dimensional Data Analysis, \textit{Hubness}, Semi-Supervised Clustering.}
%  -> \keywords{} (in alphabetical order \keywords{document processing, sequences,
%                      string searching, subsequences, substrings})


% THE ARTICLE BEGINS
\begin{document}

% This is optional:
\begin{bottomstuff}
This work has been supported by CNPq (Conselho Nacional de Desenvolvimento Cient\'ifico e Tecnol\'ogico) and by CAPES (Coordena\c c\~ao de Aperfei\c coamento de Pessoal de N\'ivel Superior).
\end{bottomstuff}

\maketitle


\section{INTRODUCTION}

There exist various application domains for which the employment of data mining techniques is useful such where the dimensionality of the data is notably elevated. 
Among such are databases where each data instance is described by a collection of features, as in the case of images and gene expressions. 
The so-called \textit{curse of dimensionality} \cite{Samet:2005} makes data analysis in higher dimensions a challenge for any data mining technique based on distance calculations, since the extent to which the dimension increases, the sparseness of data also increases, and so does the difficulty to differentiate data instances. 
In this context, it is interesting to consider the employment of techniques that allow for the mitigation of these prejudicial effects on the effectiveness and efficiency of data mining algorithms.         

Traditionally, the question of higher dimensions has been dealt with in scientific literature through use of strategies that look to mitigate the effects of the \textit{curse of dimensionality} by means of the extraction and the selection of features or through the proposal of methods that work in subspaces. 
However, information can be lost when the dimensionality is reduced \cite{Silvestre:2007}. 
In an opposing manner, more recent strategies have employed in an efficient manner an aspect inherent to high-dimensional data in the proposal of techniques that allow for the classification \cite{Tomasev:2013}\cite{Buza:2016}, the search for the \textit{nearest neighbors} \cite{Flexer:2013}\cite{Tomasev:2014i} and the clustering \cite{Tomasev:2014}\cite{Nenad:2015} in high-dimensionality databases. 
This aspect, denominated \textit{hubness}, consists of the tendency that some data instances, called \textit{hubs}, occur with greater frequency in the list of \textit{$K$-nearest neighbors} than other instances.

Although clustering techniques directed by the \textit{hubness score} have presented good results when dealing with high-dimensional data, it is of importance to highlight that as the \textit{hubs} are centers of influence, possible inaccuracies associated with these can be easily propagated \cite{Tomasev:2013}.
A particular strategy that can be used in order to minimize the risk of inducing an unsuitable partitioning in the data, since the \textit{hubs} may not reflect the implicit data semantics, is the incorporation of semi-supervision \cite{Basu:2008}. 

This article presents a new clustering approach that explores the combination of semi-supervision strategies and the use of \textit{hubness score} in respect to the instances of data, with the focus being high-dimensional data. This approach revisited the algorithm \textit{HPKM} \cite{Tomasev:2011}, which gave rise to method denominated as \textit{Algorithm X} (the real name was omitted due to blind review).
Although a preliminary version of the work described herein was presented in a previous short paper (omitted reference), new aspects are dealt with in this article.
The present article integrates the concepts introduced in the previous paper and goes beyond these through the presentation of a more detailed description of an improved version of the proposed algorithm and the results obtained through an exhaustive set of experiments that used 23 sets of real data. 
By analyzing the obtained experimental results, it is possible to state that the \textit{Algorithm X} achieved better performance when applied to real datasets of different sizes, which surpassed the effectiveness of the four selected algorithms used on a comparison basis.

The remainder of the article is organized as detailed in the following. Section \ref{background} presents the fundamental concepts and correlated research. 
The \textit{Algorithm X} is described in Section \ref{prop}. 
The discussion regarding the obtained experimental results is presented in Section \ref{exp}. 
Finally, the conclusions and future work are described in Section \ref{conc}.


\section{BACKGROUND AND RELATED WORK} \label{background}

This section presents the fundamental concepts for the presentation of the proposed \textit{Algorithm X} algorithm. 
The symbols and definitions described in Table \ref{tab1} are used throughout this article.   

\begin{table}[htbp]
\scalefont{0.86}
\centering
  \caption{Summary of Symbols and Definitions.}

    \begin{tabular}{|l|l|}
    \hline
    Symbols & Definitions \bigstrut\\
    \hline
    $k$     & number of clusters \bigstrut\\
    \hline
    $C$ = $\left\{c_{1}; ...; c_{k}\right\}$     & partition set \bigstrut\\
    \hline
    $X = \{x_{1}; ...; x_{n}\}$     & set of data instances to be clustered \bigstrut\\
    \hline
     $K$     & neighborhood cardinality of each instance (\textit{$K$-nearest neighbors}) \bigstrut\\
    \hline
     $h_{K}(x)$     & \textit{hubness score} of the instance $x$ considering the neighborhood $K$\bigstrut\\
    \hline
     $N = \{h_{K}(x_{1}); ...; h_{K}(x_{n})\}$    & set of data instances \textit{hubness scores} \bigstrut\\
    \hline
    $p_{i}$     & main representative of cluster $c_{i}$ \bigstrut\\
    \hline
    $a_{i}$     & auxiliary representative of cluster $c_{i}$ \bigstrut\\
    \hline
    $A_{i}$     & set of auxiliaries representatives of cluster $c_{i}$\bigstrut\\
                \hline
    $Q_{i}$     & set of representatives (main and auxiliaries) of cluster $c_{i}$\bigstrut\\
    \hline
    $r_{ml}(x_i,x_j)$     & \textit{must-link}  constraint between $x_i$ and $x_j$ \bigstrut\\
    \hline
    $r_{cl}(x_i,x_j)$     & \textit{cannot-link}  constraint between $x_i$ and $x_j$ \bigstrut\\
        \hline
    $R_{m}$     & set of $r_{ml}$   \bigstrut\\
            \hline
    $R_{c}$     & set of $r_{cl}$   \bigstrut\\
    \hline
    $R$     &  $R_{ml}$ $\cup$ $R_{cl}$   \bigstrut\\
    \hline

    \end{tabular}%
  \label{tab1}%
\end{table}%

In a general sense, the data-clustering task aims to find clusters according to a similarity measure, in a manner that the data instances from a related cluster possess high similarity, while data instances from different clusters possess low similarity \cite{Aggarwal:2013}. 
To compute this measure it is necessary to have a description of the data instances and a distance function. 
Thus, depending on the data domain, the instances can be described by a set of attributes of traditional domains (for example, text or numbers) or by a collection of pre-defined feature descriptors inherent to the data (considering the image domain, for example: color, texture and form, among others). 
The choice of distance function to be employed also depends on the deployed data domain, being that among the most commonly used are the distance functions from the family of \textit{Minkowski} \cite{Taniar:2011}.           

It is important to highlight here that the expressiveness of this similarity measure is an important factor for obtaining good results in data clustering processes.
When dealing with high-dimensional data this desirable feature of the similarity measure degrades due to the effects of the so-called \textit{curse of dimensionality}. 
In an attempt to mitigate the undesirable effects of this curse in high-dimensional data clustering processes, two approaches may be employed: 1) apply techniques to reduce the dimensionality as a first step before performing data clustering, or 2) use specialized solutions for analyzing high-dimensional data.      

The strategies proposed in the scientific literature from this area for reducing dimensionality arise from research areas, such as Pattern Recognition, Statistics and Information Theory, which aim at reducing the number of dimensions while excluding irrelevant or redundant features from the description of the data instances. 
This strategy can be divided into two categories: 1) feature selection, and 2) feature extraction.        

The techniques based on the approach of feature selection have as their objectives to choose a small subset of features according to a given criterion. 
Here are some examples of feature selection techniques: techniques based on the calculation of the \textit{Fractal Dimension} \cite{Traina:2010}, \textit{Information Gain} \cite{Kullback:1951} and \textit{Relief} \cite{Kira:1992}, among others. 
On the other hand, those techniques based on the feature extraction approach map the original data space in a lower dimensional space. 
Among the feature extraction techniques proposed one can cite, \textit{Principal Component Analysis} (PCA) \cite{Hair:1995}, \textit{Multidimensional Scaling} (MDS) \cite{Borg:2005} and \textit{FastMap} \cite{Faloutsos:1995}.
 
The techniques for reducing dimensionality, in general, provide only a subspace of original data, in which the data clustering process can be performed. 
However, for situations where different features can be relevant to different groups in one singular data clustering, such methods tend to fail. 
In these cases, algorithms for subspace clustering appear as a new strategy for analyzing high-dimensional data \cite{Aggarwal:2000}\cite{Kailing:2003}\cite{Kailing:2004}\cite{Muller:2009}.

Another example of a specialized solution for analyzing high-dimensional data are the clustering algorithms based on \textit{hubness} \cite{Tomasev:2011}. 
Different from the previous approaches, instead of trying to avoid the effects associated with high-dimensional data analysis, this approach employs information on \textit{hubness} to obtain data clustering solutions. 
This is the focus of the research work described herein. 
Thus, the fundamental concepts regarding the aspect of \textit{hubness} are presented in Section \ref{hubness}.    

Still further, another aspect that can interfere in the expressivity of similarity measures arises when it becomes necessary to deal with more complex data domains, such as images. 
This is due to the existence of the so-called ``\textit{semantic gap}'' between the low-level features that represent the data instances and the high-level of human perception, which can produce clusters, obtained from information based only on low-level features, that do not correspond to the notion of similarity of the user. 
Among such proposals for dealing with this question are the techniques for the semi-supervised clustering. 
More details concerning these techniques are described in Section \ref{ss}. 

\subsection{The \textit{hubness} aspect} \label{hubness}

\textit{Hubness} is an aspect inherent to data that presents high dimensionality. 
As the intrinsic dimensionality of the data increases the distribution of the \textit{$K$-occurrences} in the list of \textit{nearest neighbors} of each data instance becomes distorted and more variable. 
Hence, some data instances (called \textit{hubs}) appear frequently in the list of \textit{\textit{$K$-nearest neighbors}}, and at the same time, other data instances (called \textit{anti-hubs}) become infrequent neighbors. According to \cite{Tomasev:2014}  \textit{hubness score}, \textit{hubs} and \textit{anti-hubs} can be defined in the following manner:          


\begin{itemize}
\item \textbf{\textit{\textit{Hubness} score}}: Let $X = \{x_{1}; ...; x_{n}\}$ be a set of data instances, $h_K(x)$ represents the number of \textit{$K-$occurrences} of instances $x \in X$, that is, the number of times that $x$ occurs in the list of \textit{$K$-nearest neighbors} of other data instances which belong to $X$. 
Values commonly used for $K$ are in the interval [5, 20] \cite{Tomasev:2011};


\item \textbf{\textit{$K-$occurrences}} $h_{K}(x)$: Let $Y = \{y_{1}, y_{2}, ... , y_{n}\}$, be a set that contains $n$ listings of \textit{$K$-nearest neighbors} of data instances that belong to $X$, the number of \textit{$K$-occurrences} $h_{K}(x)$ is the quantity of times that $x \in X$ occurs in listings of $Y$;

\item \textbf{\textit{hubs}}: Correspond to the data instances $x \in X$ that appear in many more listings of \textit{$K$-nearest neighbors} than do the remaining data instances, that is, they possess \textit{hubness scores} $h_K(x)$ significantly above the average;
	
\item \textbf{\textit{anti-hubs}}: Correspond to the data instances $x \in X$ that do not appear in practically any listing of \textit{$K$-nearest neighbors} of the remaining data instances, that is, they possess a very low $h_K(x)$ or even $h_K(x) = 0$.

\end{itemize}

According to \cite{Tomasev:2011}, \cite{Tomasev:2013} and \cite{Tomasev:2014} the \textit{hubness} aspect can perform an important role in the task of clustering high-dimensional data, as it is a good reference to the centroid of the clusters. 
The main \textit{hubs} can be used effectively as representatives to guide the process of assigning data instances to clusters, in a similar manner as occurs in techniques based on centroids.

Among the proposals for the use of the \textit{hubness} aspect in the task of high-dimensional data clustering, one of the most promising is the \textit{HPKM} (\textit{Hubness-proportional $k$-means}) algorithm proposed in \cite{Tomasev:2011}. 
The \textit{HPKM} is a variation of the traditional $k$-\textit{means} algorithm, which employs a stochastic hybrid clustering approach, that is, it uses both \textit{hubs} and centroids as representatives of clusters. 
The general idea of the algorithm consists of using the information concerning \textit{hubness scores} from the data instances to guide partitions in the first iterations and choosing a clustering configuration based on centroids at the end.   

Besides the good effectiveness demonstrated for dealing with high-dimensional data, the computational efficiency of the clustering algorithms based on \textit{hubs} can be a cause of concern when one wishes to analyze large data sets. 
Through, considering the fact that the computational complexity of these algorithms is directly related to the \textit{hubness score} calculation of the data instances, it is important to consider strategies that allow for the optimization of these calculations. 
Among such strategies, one can mention the use of an approximate $K$-\textit{NN} graph for obtaining the \textit{hubness score} with a time complexity of \textbaro$(ndt)$, where $n$ is the number of instances,  $d$ the quantity of dimensions and $t$ represents the construction of the graph \cite{Chen:2009}. 
Another alternative pointed out in \cite{Tomasev:2014} consists of using approaches based on \textit{locality-sensitive hashing} \cite{Satuluri:2012}.  

It is also important to highlight that, as the \textit{hubs} are centers of influence, possible inaccuracies associated to them can be easily propagated causing a negative impact on clustering. 
One way of dealing with the question, considering that \textit{hubs} may not reflect well the implicit semantics of the data, is to allow the incorporation of semi-supervised techniques into the data clustering process.

\subsection{Semi-supervised data clustering} \label{ss}

Different to the traditional approach for data clustering, the semi-supervised clustering approach counts on some additional information that guides data partitioning into clusters. 
This additional information can be obtained by means of labelling a small portion of the dataset \cite{Chapelle:06} or informed in the form of data constraints \cite{Davidson:2007}\cite{Xiong:2014}.

These constraints can be defined in different ways, for example: in instance level \cite{Wagstaff:2000}, in feature level \cite{Schmidt:2011}, in group level \cite{Dubey:2010}, relative \cite{Kumar:2008} and ranked \cite{Ahmed:2012}. 
Among them, the instance level are the type that are most employed by clustering algorithms based on partitioning, thus significantly improving the performance of these algorithms \cite{Dubey:2010}.

The instance level constraints are divided into two types, \textit{must-link} and \textit{cannot-link} constraints. The \textit{must-link} constraints define that a pair of instances must belong to the same cluster. On the other hand, the \textit{cannot-link} constraints define that a pair of instances must not belong to the same cluster \cite{Wagstaff:2000}.
Formally, let us consider a set of data instances $X = \{x_{1}; ...; x_{n}\}$, a must-link constraint $r_{ml} (x_{1}, x_{2})$ indicates that the instances $x_{1}$ and $x_{2}$ must be in the same cluster, whereas a cannot-link constraint $r_{cl} (x_{1}, x_{3})$ indicates that the instances $x_{1}$ and $x_{3}$ must not be in the same cluster. 
It is important to highlight that the instance level constraints, although apparently simple, possess interesting properties.
The \textit{must-link} constraints, for example, are symmetric, reflexive and transitive. 
Another important question is related to the selection of data instances for obtaining the \textit{must-link} and \textit{cannot-link} constraints.
When this selection is random, the resultant clusters may not reach the desired structure.
In the interest of resolving this limitation, \textit{active learning} strategies are a viable option. 
The main goal of these strategies is to allow the selection of the most significant instances (or instance pairs) for labelling.
This allows obtaining better clustering results while analysing a small number of data instances \cite{Li:2014}.

The available approaches for the incorporation of constraints on the data clustering algorithms can be divided into two categories: those based on similarity and those based on search. 
The strategies that employ the approach based on similarity alter the similarity measure used in the clustering process, looking to satisfy the labels or constraints in the data in a manner that instances that should be together in the same cluster are close and instances that should not be together are separated.
The strategies that employ the approach based on search use the labels or constraints supplied by the users in order to guide the clustering detection process for a data partition closer to the real dataset structure \cite{Barioni:2014}. 
The \textit{Algorithm X} algorithm fits into the latter category.

\section{\textit{Algorithm X}} \label{prop}

The clustering approach employed by the algorithm described herein combines semi-supervised and density estimation strategies based on \textit{hubness score}, which aim at contributing toward the analysis of high-dimensional data.
This algorithm is named \textit{Algorithm X}  
and it is described in Algorithm \ref{alg1}.

Given a dataset $X = \{x_{1}; ...; x_{n}\}$, a set $H$ of \textit{hubness scores} $h_K(x)$ for each instance $x_{i}$, and a percentage $f$ of borderline elements that are to be analyzed for the definition of the \textit{must-link} and \textit{cannot-link} constraints.
The \textit{Algorithm X} employs a semi-supervised clustering approach based on the partitioning of $X$ into a quantity of $k$ clusters. 
Each cluster is represented by multiple prototypes, one main $p_{i} \in P$ and various auxiliaries $a_{i} \in A$. This representation strategy was adopted with the intention of allowing the algorithm to deal with clusters with hyperspherical formats as well as with clusters that present formats of greater complexity.

\begin{algorithm}[htb]
	\KwData{Dataset $X$, Number of clusters $k$, \textit{Hubness} $H$, Borderline instances $f$, MaxIterations $maxIt$}
	\KwResult{ $C$ $\left\{c_{1}, ..., c_{k}\right\}$ }
	\Begin{	
		$P \gets$  Selection of $k$ initial representatives; \\
                     	$A \gets \lbrace\rbrace$;\\
		$R \gets \lbrace\rbrace$;\\
		$N \gets H$;\\
		$it = 0$;\\
		
		\For{each representative $p_{i} \in P$}{
			$A_i$ = $A_i$ $\cup$ $p_{i}$;
		}
				
		\Repeat{convergence or it = maxIt}{
		           $it$++;\\
			\For{each instance $x_{i} \in X$}{
				Assign $x_{i}$ to the cluster with the smaller aggregated distance;

				\If{$x_{i}$ do not change cluster}{
				      $N_{i}$ = $N_{i}$ $\cdot$ $N_{i}$;
				}
				\Else{
				      $N_{i}$ = $H_{i}$;
				}
				
			}
			\For{each $c_{i}$}{
				Update the representative $p_{i}$;
			}
			
      ConstraintDefinition($C, H, f, A, R$);			
		}
		\Return{$C$}
	}
	\caption{\textit{Algorithm X}}
	\label{alg1}
\end{algorithm}

In order to create the initial data partition, the \textit{Algorithm X} algorithm starts out by selecting, in a semi-supervised manner, a main representative for each cluster (line 2 of the Algorithm \ref{alg1}). 
The strategy proposed for this initial phase of the algorithm allows guiding the user to select $k$ main representatives from a ranking of the data instances with the highest \textit{hubness score}.
The remaining auxiliary representatives are derived from the \textit{must-link} constraints $r_{m}(x_i, x_j) \in R_{m}$, starting from the second iteration of the algorithm. 
It is important to highlight that the initial main representatives are considered permanent cluster representatives, that is, even if they are updated in the following iterations, they remain as auxiliary representatives (line 8 of the Algorithm \ref{alg1}).

\begin{figure}[ht]
\centering
\includegraphics[width=.7\textwidth]{fig/fig1}
\caption{Selection of $k=4$ initial representatives. (a) \textit{Hubs} (b) $k$ selected \textit{hubs} and the initial data partitioning.}
\label{fig1}
\end{figure}

Figure \ref{fig1} illustrates the initial selection phase of the \textit{Algorithm X} algorithm considering $K=5$ \textit{nearest neighbors} for calculating the \textit{hubness score} ($h_{K}(x)$) of each data instance. 
Considering the existence of various \textit{hubs} in the dataset (white circles with the $h_{K}$ values in Figure \ref{fig1}(a)), the idea of the strategy adopted in this phase is to provide the possibility to the user of interfering at the outset of the clustering process for selecting the initial $k$ representatives from among these \textit{hubs} (Figure \ref{fig1}(b)). 
This algorithm feature is especially useful in the analysis of complex data domains that can be affected by the ``\textit{semantic gap}'' problem. 
Figure \ref{fig2} presents a practical example of the selection of initial representatives in image data domains. 
Considering the existence of an application, which exhibits thumbnails that correspond to higher \textit{hubness score} instances (calculated based on low level features, such as color, texture or form) from an image dataset, a user can, based on their data domain knowledge, select initial representatives for each desired cluster.   

\begin{figure}[ht]
\centering
\includegraphics[width=.6\textwidth]{fig/fig2}
\caption{Selection of $k$ ($k = 2$) initial representatives in an image dataset. Adapted from \protect\cite{Wang:2009}.}
\label{fig2}
\end{figure}

After the selection of the initial representatives, the assignment of the instances to the clusters is performed (line 12 of Algorithm \ref{alg1}) by taking into account both main and auxiliary-representatives. 
In this phase, the \textit{Algorithm X} algorithm considers the smaller aggregated distance calculated as defined in Equation \ref{equ}, while respecting the previously informed \textit{must-link} and \textit{cannot-link} constraints. 
In this equation, $Q_{k}$ is the set of representatives (main and auxiliary) of a cluster $c_{k}$, and $\delta()$ is a distance function. 
It is important to emphasize that in the first iteration of the algorithm, there do not exist constraints and no auxiliary representatives. 
This information is considered only from the second iteration of the algorithm. 

\begin{equation}
\delta_{g}(Q_{k}, x_{i}) = \min_{q_{j} \in Q_{k}}\left(\delta(q_{j},x_{i}) \right)
			\label{equ}
\end{equation}

The updating of the main representatives of each cluster is based on the \textit{hubness score} of the instances that belong to each cluster (lines 13 to 18 of Algorithm \ref{alg1}). 
However, this score can be changed over the iterations of the algorithm. 
Inspired upon the approach put forward for the algorithm \textit{HPKM} \cite{Tomasev:2014}, instances that do not change cluster over the iterations are privileged through the squared elevation of their \textit{hubness score} (line 14 of Algorithm \ref{alg1}). 
Should there be noted changes in the cluster, the \textit{hubness score} returns to its original value (line 16 of Algorithm \ref{alg1}). 
In this manner, the representative of each cluster corresponds to the instance with the highest accumulated \textit{hubness score} (line 18 of Algorithm \ref{alg1}).      

The constraint definition phase of the \textit{Algorithm X} (line 19 of Algorithm \ref{alg1}) aims at selecting a subset of instances in such a way that to find additional knowledge about them allows obtaining a more adequate data partitioning.
Therefore, the $f$ instances farthest from each $p_{i} \in P$ with a \textit{hubness score} $\geq$ 1 are evaluated. This restriction to the \textit{hubness score} is to avoid the possibility of selecting \textit{anti-hubs}. 
The sub-routine responsible for this task is described in Algorithm \ref{alg2}.

\begin{algorithm}[H]
	 \KwData{Clusters $C$, \textit{Hubness} $H$, Borderline instances $f$, Representatives $A$, Constraints $R$}
	\Begin{
		          $t = |N| \cdot f $;\\
			\For{each $c_{i} \in C$}{			
			          $q = (|c_{i}|/|N|) \cdot t $;\\
	          			\For{$j$ = 1 until $j$ = $q$}{
				  $x_{j}$ = select the farthest instance from the main prototype $p_{i}$ in $c_{i}$, with $h_{K} \geq $ 1;

				  $x_{w}$ = select the nearest instance from $x_{j}$ in $c_{w}$ $|$ $w \neq i$;\\
			             \If{$p_{i}$ and $x_{j}$ should be in the same cluster}{
			                    $R$ = $R$ $\cup$ $r_{ml}$$(p_{i}, x_{j})$;\\
					$A_i$ = $A_i$ $\cup$ $x_{j}$;
			             }
			            \Else{
			            	$R$ = $R$ $\cup$ $r_{cl}$$(p_{i}, x_{j})$;	            			  	
			            }
			            
			            \If{$x_{w}$ and $x_{j}$ should be in the same cluster}{
			                    $R$ = $R$ $\cup$ $r_{ml}$($x_{w}$, $x_{j}$);\\
			                    }
			                    \Else{
			            	$R$ = $R$ $\cup$ $r_{cl}$($x_{w}$, $x_{j}$);\\
				            }
			            
			            Define transitive constraints;\\
			            $j$++;
				}
			}		
		
	}
	\caption{ConstraintDefinition}
	\label{alg2}
\end{algorithm}

The definition of the quantity of instances $q$ that should be analyzed in each cluster, in the constraint definition phase, is performed in a manner that is proportional to the quantity of instances assigned to each cluster (line 4 of Algorithm \ref{alg2}). 
Considering each borderline instance $x_y$ of a given cluster $c_{i}$, the constraint definition sub-routine selects the nearest instance $x_w \in c_{j}$ to $x_y$, such that $c_{i} \neq c_{j}$. 
Through such, it is possible to analyze distinct pairs of borderline instances and question whether or not they should be in the same cluster.
This analysis strategy allows to create \textit{must-link} constraints $r_{ml}(x_y,x_w)$ (line 14 of Algorithm \ref{alg2}) or \textit{cannot-link} constraints $r_{cl}(x_y,x_w)$ (line 16 of Algorithm \ref{alg2}).

Moreover, to obtain auxiliary representatives for the clusters, each $x_y$ of a given cluster $c_{i}$ is analyzed to question if $x_y$ and $p_i$ should be in the same cluster or not. 
If the answer is positive, a \textit{must-link} constraint $r_{ml}(x_y,p_i)$ is created (line 9 of Algorithm \ref{alg2}) and $x_y$ is attributed to $A$ (line 10 of Algorithm \ref{alg2}). 
On the other hand, a \textit{cannot-link} constraint $r_{cl}(x_y,p_i)$ is created (line 12 of Algorithm \ref{alg2}). 
Finally, constraints are created via transitivity (line 17 of Algorithm \ref{alg2}). 
For example, if there exist the $r_{ml}$$(p_{i}, x_{y})$ and the $r_{ml}$$(x_{y}, x_{w})$ constraints, then the $r_{ml}$$(p_{i}, x_{w})$ constraint should also exist.

Figure \ref{fig3} illustrates the four possible scenarios of the analysis process for the borderline elements ( see the Algorithm \ref{alg2}). 
Figure \ref{fig3}(a) presents the scenario in which only the \textit{must-link} constraints are generated, that is, $p_i$, $x_y$ and $x_w$ should be from the same cluster. 
Figure \ref{fig3}(b) presents the scenario in which a \textit{must-link}  constraint is generated between the borderline instance $x_y$ with its main respective representative $p_i$, and a \textit{cannot-link} constraint between the borderline instance $x_y$ and the instance from another cluster $x_w$, or be it, $p_i$ and $x_y$ should be in the same cluster, where $x_y$ and $x_w$ should not be in the same cluster.       

Figure \ref{fig3}(c) presents the scenario in which a \textit{cannot-link} constraint is generated between the borderline instance $x_y$ and its main respective representative $p_i$ and a \textit{must-link} constraint is generated between the borderline $x_y$ and the instance $x_w$ from another cluster. 
In this case, the two borderline instances $x_y$ and $x_w$ should be in the same cluster. 
Figure \ref{fig3}(d) presents the last scenario in which only \textit{cannot-link} constraints are generated. 
In this scenario, a \textit{cannot-link} constraint is generated between the borderline instance $x_y$ and its main respective representative $p_i$ and a \textit{cannot-link} constraint between the borderline instance $x_y$ and the instance $x_w$ of another cluster, or be it, $p_i$, $x_y$ and $x_w$ should not be part of the same cluster. 

\begin{figure}[H]
\centering
\includegraphics[width=.7\textwidth]{fig/fig3}
\caption{Possible scenarios for creating \textit{must-link} and \textit{cannot-link} constraints.}
\label{fig3}
\end{figure}

In summary, the steps performed by the \textit{Algorithm X} algorithm are presented below:

(1) Select $k$ instances with high \textit{hubness score} as initial representatives  $P = \{p_{i}, ..., p_{k}\}$ and make $A = P$;

(2) Assign each instance $x_{i} \in X$ to the cluster with the smaller aggregated distance $\delta_{g}$ in relation to $Q$, respecting the constraints $R_{m}$ and $R_{c}$;

(3) Update the main representatives $P$ of each cluster based on the \textit{hubness scores} of the instances assigned to each cluster;

(4) Analyze the $f$ borderline instances to define \textit{must-link} and \textit{cannot-link} constraints and other auxiliary representatives;

(5) Return to step (2) until convergence or until reaching the maximum number of iterations.

The stop criterion for the algorithm \textit{Algorithm X} (step 5) checks two possibilities, 1) if the maximum number of iterations was reached or 2) if the convergence of the algorithm was obtained. 
The convergence function considered verifies the sum of the distances for the representatives (main and auxiliary) for the current iteration in relation to the previous iteration. 
Equation \ref{converge} presents how this calculation is performed:    

\begin{equation}
\sum^{k}_{k = 1} \sum^{}_{x_{i} \in C_{k}}  \min_{q_{j} \in Q_{k}}\left(\delta(q_{j},x_{i}) \right )
\label{converge}
\end{equation}

\noindent ,  where $x_{i}$ is an instance of a cluster $C_{k}$, $Q_{k}$ is a set of representatives (main and auxiliary) of the respective cluster, and $\delta()$ is a distance function.    

\section{EXPERIMENTS} \label{exp}

To perform the experiments 23 real datasets were considered. 
The details concerning each one are presented in Table \ref{tab2}. 
From these datasets, 22 were obtained from \textit{UCI Machine Learning} \cite{Lichman:2013} and the \textit{NBA} dataset, which is available in the repository BasketballStats \cite{NBA:2011}. 
It is important to highlight that the datasets were selected with different class numbers, densities and dimensions with the aim of checking the performance of the proposed algorithm against other four algorithms described in the literature in different scenarios.

\begin{table}[htbp]
\caption{Datasets employed in the experiments.}
\scalefont{0.86}
\centering
    \begin{tabular}{|c|r|r|r|r|}
    \hline
    ID    & \multicolumn{1}{c|}{Datasets} & \multicolumn{1}{c|}{No. of Data instances} & \multicolumn{1}{c|}{No. of Dimensions} & \multicolumn{1}{c|}{No. of Classes} \bigstrut\\
    \hline
    1     & \multicolumn{1}{l|}{Abalone} & \multicolumn{1}{l|}{4,176} & \multicolumn{1}{l|}{8} & \multicolumn{1}{l|}{3} \bigstrut\\
    \hline
    2     & \multicolumn{1}{l|}{Aloi} & \multicolumn{1}{l|}{1,098} & \multicolumn{1}{l|}{64} & \multicolumn{1}{l|}{10} \bigstrut\\
    \hline
    3     & \multicolumn{1}{l|}{Breast} & \multicolumn{1}{l|}{683} & \multicolumn{1}{l|}{9} & \multicolumn{1}{l|}{2} \bigstrut\\
    \hline
    4     & \multicolumn{1}{l|}{Churn} & \multicolumn{1}{l|}{5,000} & \multicolumn{1}{l|}{14} & \multicolumn{1}{l|}{2} \bigstrut\\
    \hline
    5     & \multicolumn{1}{l|}{Covertype} & \multicolumn{1}{l|}{19,229} & \multicolumn{1}{l|}{54} & \multicolumn{1}{l|}{7} \bigstrut\\
    \hline
    6     & \multicolumn{1}{l|}{Digits389} & \multicolumn{1}{l|}{3,165} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{3} \bigstrut\\
    \hline
    7     & \multicolumn{1}{l|}{Ecoli} & \multicolumn{1}{l|}{336} & \multicolumn{1}{l|}{7} & \multicolumn{1}{l|}{8} \bigstrut\\
    \hline
    8     & \multicolumn{1}{l|}{Hepmass} & \multicolumn{1}{l|}{45,000} & \multicolumn{1}{l|}{27} & \multicolumn{1}{l|}{2} \bigstrut\\
    \hline
    9    & \multicolumn{1}{l|}{Isolet} & \multicolumn{1}{l|}{6,237} & \multicolumn{1}{l|}{617} & \multicolumn{1}{l|}{26} \bigstrut\\
    \hline
    10    & \multicolumn{1}{l|}{Musk2} & \multicolumn{1}{l|}{6,598} & \multicolumn{1}{l|}{166} & \multicolumn{1}{l|}{2} \bigstrut\\
    \hline
    11    & \multicolumn{1}{l|}{NBA} & \multicolumn{1}{l|}{22,064} & \multicolumn{1}{l|}{17} & \multicolumn{1}{l|}{2} \bigstrut\\
    \hline
    12    & \multicolumn{1}{l|}{Page blocks} & \multicolumn{1}{l|}{5,473} & \multicolumn{1}{l|}{10} & \multicolumn{1}{l|}{5} \bigstrut\\
    \hline
    13    & \multicolumn{1}{l|}{Pendigits} & \multicolumn{1}{l|}{10,992} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{10} \bigstrut\\
    \hline
    14    & \multicolumn{1}{l|}{Segment} & \multicolumn{1}{l|}{2,310} & \multicolumn{1}{l|}{19} & \multicolumn{1}{l|}{7} \bigstrut\\
    \hline
    15    & \multicolumn{1}{l|}{Sonar} & \multicolumn{1}{l|}{208} & \multicolumn{1}{l|}{60} & \multicolumn{1}{l|}{2} \bigstrut\\
    \hline
    16    & \multicolumn{1}{l|}{Spambase} & \multicolumn{1}{l|}{4,599} & \multicolumn{1}{l|}{57} & \multicolumn{1}{l|}{2} \bigstrut\\
    \hline
    17    & \multicolumn{1}{l|}{Urbanlandcover} & \multicolumn{1}{l|}{675} & \multicolumn{1}{l|}{147} & \multicolumn{1}{l|}{9} \bigstrut\\
    \hline
    18    & \multicolumn{1}{l|}{Vehicle} & \multicolumn{1}{l|}{846} & \multicolumn{1}{l|}{18} & \multicolumn{1}{l|}{4} \bigstrut\\
    \hline
    19    & \multicolumn{1}{l|}{Vowel} & \multicolumn{1}{l|}{990} & \multicolumn{1}{l|}{13} & \multicolumn{1}{l|}{11} \bigstrut\\
    \hline
    20    & \multicolumn{1}{l|}{Wine} & \multicolumn{1}{l|}{178} & \multicolumn{1}{l|}{13} & \multicolumn{1}{l|}{3} \bigstrut\\
    \hline
    21    & \multicolumn{1}{l|}{WDBC} & \multicolumn{1}{l|}{569} & \multicolumn{1}{l|}{30} & \multicolumn{1}{l|}{2} \bigstrut\\
    \hline
    22    & \multicolumn{1}{l|}{Yeast} & \multicolumn{1}{l|}{1,484} & \multicolumn{1}{l|}{8} & \multicolumn{1}{l|}{10} \bigstrut\\
    \hline
    23    & \multicolumn{1}{l|}{Zoo} & \multicolumn{1}{l|}{101} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{7} \bigstrut\\
    \hline
    \end{tabular}%
  \label{tab2}%
\end{table}%

All these datasets were preprocessed according to the recommendations indicated in these repositories. 
In addition, for the dataset Covertype (5) a sample with 19,229 randomly selected instances from the original set was considered, maintaining the proportion of instances per class. 
For the dataset Hepmass (8) a sample of 45,000 instances from the original set were considered, equally divided between the two classes. 
Finally, for the dataset Digits389 (6) only the instances for classes 3, 8 and 9 from the dataset Pendigits were considered, as was performed in \cite{Xiong:2014}.    

The experiments were run on a computer equipped with a processor of the following specifications: Intel Core i5-3230M CPU @ 2.60GHz with 6 GB of RAM, hard drive 500 GB SATA (7.200 rpm) using the operating system Microsoft Windows 7 Ultimate SP1 64 bits. 
The algorithms \textit{HPKM}, \textit{Kernel $k$-means} \cite{Dhillon:2004}, \textit{DBSCAN} \cite{Sander:1998} and \textit{SSDBSCAN} \cite{Li:2014} were selected as the baseline for comparison. 
The \textit{hub} based \textit{HPKM} was the clustering algorithm that inspired the proposal of the \textit{Algorithm X} algorithm. 
The \textit{Kernel $k$-means} is a classic representative of kernel based clustering algorithms, which are known for dealing well with non-hyperspherical clusters, and the \textit{DBSCAN} is a standard representative of clustering algorithms based on density. 
As a representative of the semi-supervised clustering algorithms the extension of the \textit{DBSCAN}, called \textit{SSDBSCAN} \cite{Li:2014}, was chosen. 
This algorithm incorporates additional information in the form of labels in the clustering process based on density. 
The implementation of this algorithm was made available by the authors of the work-study and was performed in the Java language. 
The implementation of all the other algorithms – \textit{HPKM}, \textit{Kernel $k$-means} and \textit{DBSCAN} – were made available by the authors of the work-study described in \cite{Tomasev:2014} in repository \cite{NenadGitHub:2014}, all in Java. 
With the aim of allowing for the comparison of the algorithms, \textit{Algorithm X} was also implemented using Java.

Considering that the ideal neighborhood size that should be analyzed in the calculation of the \textit{hubness score} may vary according to the data domain, four distinct neighborhood values were considered ($K$ = 5, 10, 15 and 20) for the \textit{Algorithm X} and \textit{HPKM} algorithms. 
The number of requested clusters (k) was defined according to the number of classes defined for each dataset and described in Table \ref{tab2}. 
All the algorithms take into consideration the Euclidean distance function.  

In order to automate the execution of the experiments with the \textit{Algorithm X} algorithm, the user interaction phase for choosing the initial representatives was simulated in the following manner. 
Considering the label information of the datasets, the initial representatives were chosen among the five instances of each cluster with the highest \textit{hubness scores}. 
In this manner, it is possible to simulate the fact that at each run, the user can choose different instances of high \textit{hubness} scoring as representatives. 
In addition, the total quantity of borderline elements ($f$) analyzed by the \textit{Algorithm X} was defined at 1\% of the total instances. 
The same value of 1\% was considered for the instances labeled from the \textit{SSDBSCAN} algorithm. 
This limit for semi-supervised information was defined at 1\% due to the fact that in real applications, where the user interacts with the semi-supervised clustering process, it is not expected that the user be required to provide a high quantity of constraints.

As shown in \cite{Tomasev:2011}, the use of \textit{hubs} as initial representatives results in a rapid convergence of the algorithm, i.e. only a few iterations are necessary for the algorithm to converge. 
This fact was also observed in trials conducted on the work-study described herein. 
Therefore, the maximum number of iterations for the \textit{Algorithm X} algorithm was defined as $15$. 
For the \textit{Kernel $k$-means}, \textit{DBSCAN} and \textit{SSDBSCAN} algorithms, the best parameters known in the literature were selected for each dataset.

The main objective of the experiments was to evaluate and to compare the effectiveness of the algorithm in different scenarios, especially in those where there exist a higher number of dimensions. 
In this context, it was necessary to use an evaluation measure that allowed for measuring to which extent an algorithm is capable of finding the true structure of a dataset. 
By considering the existence of knowledge regarding the desired partitioning for the datasets, the adjusted Rand index was used \cite{Hubert:1985} for evaluating the effectiveness of the algorithms. 
In this index, the quality of the results is represented in the interval $[−1,1]$, being that the closer it is to 1, the better will be the correspondence between the obtained cluster and the desired partitioning for the evaluated dataset.

As the algorithms employed in the experiments present nondeterministic startup features, they were run $50$ times for each evaluation performed. 
Therefore, each presented measurement considers an average of $50$ algorithm runs, without considering the best or the worst for each of them. 
Sections \ref{exp1} and \ref{exp2} present the analyzes of the results obtained throughout the experiments.    

\subsection{Comparison of the algorithms} \label{exp1}

This section presents the results of the experiments that allow for the comparison of the \textit{Algorithm X} algorithm effectiveness in regards to the \textit{HPKM}, the \textit{Kernel $k$-means}, the \textit{DBSCAN} and the \textit{SSDBSCAN} algorithms. 
Moreover, the time required by each one of the algorithms during the running of these experiments are also presented. 
The results achieved are shown in Tables \ref{tab3} and \ref{tab4}. 
In these tables, the labels \textit{KerKM} and \textit{SSDBS} represent the \textit{Kernel $k$-means} and the \textit{SSDBSCAN} algorithms, respectively.

\begin{table}[htbp]
    \caption{Experimental results. The values in bold highlight the best performances. The numbers between () show the position in the ranking.}
    \scalefont{0.70}
    \centering
    \setlength{\tabcolsep}{2pt}    
    \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|r|}
\cline{2-9}    \multicolumn{1}{r|}{} & \multicolumn{4}{c|}{\textbf{\textit{Algorithm X}}} & \multicolumn{4}{c|}{\textit{\textbf{\textit{HPKM}}}} & \multicolumn{1}{r}{} & \multicolumn{1}{r}{} & \multicolumn{1}{r}{} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{Dataset} & \multicolumn{1}{c|}{$K=5$} & \multicolumn{1}{c|}{$K=10$} & \multicolumn{1}{c|}{$K=15$} & \multicolumn{1}{c|}{$K=20$} & \multicolumn{1}{c|}{$K=5$} & \multicolumn{1}{c|}{$K=10$} & \multicolumn{1}{c|}{$K=15$} & \multicolumn{1}{c|}{$K=20$} & \multicolumn{1}{c|}{\textit{\textbf{KerKM}}} & \multicolumn{1}{c|}{\textit{\textbf{\textit{DBSCAN}}}} & \multicolumn{1}{c|}{\textit{\textbf{SSDBS}}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{1} & \multicolumn{1}{l|}{0.08} & \multicolumn{1}{l|}{\textbf{0.17 (1)}} & \multicolumn{1}{l|}{0.10} & \multicolumn{1}{l|}{0.11} & \multicolumn{1}{l|}{0.14 (2.5)} & \multicolumn{1}{l|}{0.14} & \multicolumn{1}{l|}{0.14} & \multicolumn{1}{l|}{0.13} & \multicolumn{1}{l|}{0.00 (4.5)} & \multicolumn{1}{l|}{0.00 (4.5)} & \multicolumn{1}{l|}{0.14 (2.5)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{2} & \multicolumn{1}{l|}{0.65} & \multicolumn{1}{l|}{0.61} & \multicolumn{1}{l|}{0.62} & \multicolumn{1}{l|}{\textbf{0.72 (1)}} & \multicolumn{1}{l|}{0.53} & \multicolumn{1}{l|}{0.52} & \multicolumn{1}{l|}{0.53} & \multicolumn{1}{l|}{0.54 (3)} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.28 (4)} & \multicolumn{1}{l|}{0.68 (2)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{3} & \multicolumn{1}{l|}{\textbf{0.90 (1)}} & \multicolumn{1}{l|}{0.88} & \multicolumn{1}{l|}{0.86} & \multicolumn{1}{l|}{0.85} & \multicolumn{1}{l|}{0.85 (2)} & \multicolumn{1}{l|}{0.85} & \multicolumn{1}{l|}{0.85} & \multicolumn{1}{l|}{0.85} & \multicolumn{1}{l|}{0.78 (4)} & \multicolumn{1}{l|}{0.01 (5)} & \multicolumn{1}{l|}{0.84 (3)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{4} & \multicolumn{1}{l|}{-0.02} & \multicolumn{1}{l|}{\textbf{0.15 (1)}} & \multicolumn{1}{l|}{0.03} & \multicolumn{1}{l|}{0.02} & \multicolumn{1}{l|}{-0.09} & \multicolumn{1}{l|}{-0.09} & \multicolumn{1}{l|}{-0.09} & \multicolumn{1}{l|}{-0.05 (5)} & \multicolumn{1}{l|}{0.00 (3.5)} & \multicolumn{1}{l|}{0.00 (3.5)} & \multicolumn{1}{l|}{0.10 (2)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{5} & \multicolumn{1}{l|}{0.20} & \multicolumn{1}{l|}{0.23} & \multicolumn{1}{l|}{0.24 (2)} & \multicolumn{1}{l|}{0.19} & \multicolumn{1}{l|}{0.18} & \multicolumn{1}{l|}{0.19} & \multicolumn{1}{l|}{0.19} & \multicolumn{1}{l|}{0.20 (3)} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.11 (4)} & \multicolumn{1}{l|}{\textbf{0.37 (1)}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{6} & \multicolumn{1}{l|}{0.10} & \multicolumn{1}{l|}{0.74} & \multicolumn{1}{l|}{0.79 (2)} & \multicolumn{1}{l|}{0.47} & \multicolumn{1}{l|}{0.33} & \multicolumn{1}{l|}{0.54 (4)} & \multicolumn{1}{l|}{0.33} & \multicolumn{1}{l|}{0.35} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.66 (3)} & \multicolumn{1}{l|}{\textbf{0.95 (1)}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{7} & \multicolumn{1}{l|}{0.70} & \multicolumn{1}{l|}{0.73} & \multicolumn{1}{l|}{0.63} & \multicolumn{1}{l|}{\textbf{0.74 (1)}} & \multicolumn{1}{l|}{0.44} & \multicolumn{1}{l|}{0.42} & \multicolumn{1}{l|}{0.43} & \multicolumn{1}{l|}{0.49 (2)} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.06 (4)} & \multicolumn{1}{l|}{0.31 (3)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{8} & \multicolumn{1}{l|}{0.32 (2)} & \multicolumn{1}{l|}{0.22} & \multicolumn{1}{l|}{0.30} & \multicolumn{1}{l|}{0.19} & \multicolumn{1}{l|}{0.33} & \multicolumn{1}{l|}{0.32} & \multicolumn{1}{l|}{\textbf{0.34 (1)}} & \multicolumn{1}{l|}{0.32} & \multicolumn{1}{l|}{0.00 (4.5)} & \multicolumn{1}{l|}{0.00 (4.5)} & \multicolumn{1}{l|}{0.05 (3)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{9} & \multicolumn{1}{l|}{\textbf{0.52 (1)}} & \multicolumn{1}{l|}{0.49} & \multicolumn{1}{l|}{0.49} & \multicolumn{1}{l|}{0.50} & \multicolumn{1}{l|}{0.43} & \multicolumn{1}{l|}{0.40} & \multicolumn{1}{l|}{0.44 (2)} & \multicolumn{1}{l|}{0.43} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.02 (4)} & \multicolumn{1}{l|}{0.39 (3)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{10} & \multicolumn{1}{l|}{0.07 (2)} & \multicolumn{1}{l|}{-0.01} & \multicolumn{1}{l|}{-0.01} & \multicolumn{1}{l|}{-0.02} & \multicolumn{1}{l|}{-0.06} & \multicolumn{1}{l|}{-0.03 (5)} & \multicolumn{1}{l|}{-0.04} & \multicolumn{1}{l|}{-0.03} & \multicolumn{1}{l|}{0.02 (3)} & \multicolumn{1}{l|}{0.00 (4)} & \multicolumn{1}{l|}{\textbf{0.27 (1)}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{11} & \multicolumn{1}{l|}{-0.01} & \multicolumn{1}{l|}{\textbf{0.74 (1)}} & \multicolumn{1}{l|}{-0.03} & \multicolumn{1}{l|}{0.63} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{-0.01} & \multicolumn{1}{l|}{0.00} & \multicolumn{1}{l|}{0.00} & \multicolumn{1}{l|}{0.07 (4)} & \multicolumn{1}{l|}{0.13 (3)} & \multicolumn{1}{l|}{0.14 (2)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{12} & \multicolumn{1}{l|}{-0.04} & \multicolumn{1}{l|}{0.11} & \multicolumn{1}{l|}{0.10} & \multicolumn{1}{l|}{0.17 (3)} & \multicolumn{1}{l|}{0.10} & \multicolumn{1}{l|}{0.11 (4)} & \multicolumn{1}{l|}{0.08} & \multicolumn{1}{l|}{0.10} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.36 (2)} & \multicolumn{1}{l|}{\textbf{0.55 (1)}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{13} & \multicolumn{1}{l|}{0.67 (2)} & \multicolumn{1}{l|}{0.49} & \multicolumn{1}{l|}{0.56} & \multicolumn{1}{l|}{0.54} & \multicolumn{1}{l|}{0.54} & \multicolumn{1}{l|}{0.55} & \multicolumn{1}{l|}{0.56 (3)} & \multicolumn{1}{l|}{0.53} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.37 (4)} & \multicolumn{1}{l|}{\textbf{0.87 (1)}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{14} & \multicolumn{1}{l|}{0.37} & \multicolumn{1}{l|}{0.50 (3)} & \multicolumn{1}{l|}{0.46} & \multicolumn{1}{l|}{0.50} & \multicolumn{1}{l|}{0.48} & \multicolumn{1}{l|}{0.48} & \multicolumn{1}{l|}{0.51 (2)} & \multicolumn{1}{l|}{0.48} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.28 (4)} & \multicolumn{1}{l|}{\textbf{0.65 (1)}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{15} & \multicolumn{1}{l|}{0.02} & \multicolumn{1}{l|}{0.00} & \multicolumn{1}{l|}{0.02} & \multicolumn{1}{l|}{\textbf{0.03 (1)}} & \multicolumn{1}{l|}{0.00} & \multicolumn{1}{l|}{0.00} & \multicolumn{1}{l|}{0.00} & \multicolumn{1}{l|}{0.01 (2)} & \multicolumn{1}{l|}{0.00 (4)} & \multicolumn{1}{l|}{0.00 (4)} & \multicolumn{1}{l|}{0.00 (4)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{16} & \multicolumn{1}{l|}{-0.03} & \multicolumn{1}{l|}{-0.01} & \multicolumn{1}{l|}{-0.01} & \multicolumn{1}{l|}{0.00 (4)} & \multicolumn{1}{l|}{-0.01 (5)} & \multicolumn{1}{l|}{-0.01} & \multicolumn{1}{l|}{-0.03} & \multicolumn{1}{l|}{-0.02} & \multicolumn{1}{l|}{0.10 (2)} & \multicolumn{1}{l|}{0.03 (3)} & \multicolumn{1}{l|}{\textbf{0.22 (1)}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{17} & \multicolumn{1}{l|}{0.08} & \multicolumn{1}{l|}{0.42 (2)} & \multicolumn{1}{l|}{0.42} & \multicolumn{1}{l|}{0.42} & \multicolumn{1}{l|}{0.44} & \multicolumn{1}{l|}{0.44} & \multicolumn{1}{l|}{\textbf{0.51 (1)}} & \multicolumn{1}{l|}{0.42} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.06 (4)} & \multicolumn{1}{l|}{0.23 (3)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{18} & \multicolumn{1}{l|}{0.13 (2)} & \multicolumn{1}{l|}{0.07} & \multicolumn{1}{l|}{0.08} & \multicolumn{1}{l|}{0.09} & \multicolumn{1}{l|}{0.08 (3)} & \multicolumn{1}{l|}{0.08} & \multicolumn{1}{l|}{0.08} & \multicolumn{1}{l|}{0.07} & \multicolumn{1}{l|}{0.00 (4.5)} & \multicolumn{1}{l|}{0.00 (4.5)} & \multicolumn{1}{l|}{\textbf{0.17 (1)}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{19} & \multicolumn{1}{l|}{0.05} & \multicolumn{1}{l|}{0.07} & \multicolumn{1}{l|}{\textbf{0.09 (1.5)}} & \multicolumn{1}{l|}{0.06} & \multicolumn{1}{l|}{0.07} & \multicolumn{1}{l|}{0.07} & \multicolumn{1}{l|}{0.08 (3)} & \multicolumn{1}{l|}{0.08} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{\textbf{0.09 (1.5)}} & \multicolumn{1}{l|}{0.04 (4)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{20} & \multicolumn{1}{l|}{0.37} & \multicolumn{1}{l|}{0.83} & \multicolumn{1}{l|}{0.86 (2)} & \multicolumn{1}{l|}{0.77} & \multicolumn{1}{l|}{\textbf{0.91 (1)}} & \multicolumn{1}{l|}{0.85} & \multicolumn{1}{l|}{0.86} & \multicolumn{1}{l|}{0.85} & \multicolumn{1}{l|}{0.00 (4)} & \multicolumn{1}{l|}{-0.01 (5)} & \multicolumn{1}{l|}{0.45 (3)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{21} & \multicolumn{1}{l|}{0.60} & \multicolumn{1}{l|}{0.73 (2)} & \multicolumn{1}{l|}{0.19} & \multicolumn{1}{l|}{0.26} & \multicolumn{1}{l|}{\textbf{0.74 (1)}} & \multicolumn{1}{l|}{0.74} & \multicolumn{1}{l|}{0.74} & \multicolumn{1}{l|}{0.71} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.01 (4)} & \multicolumn{1}{l|}{0.30 (3)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{22} & \multicolumn{1}{l|}{\textbf{0.16 (1.5)}} & \multicolumn{1}{l|}{0.15} & \multicolumn{1}{l|}{0.15} & \multicolumn{1}{l|}{0.15} & \multicolumn{1}{l|}{0.14} & \multicolumn{1}{l|}{0.15} & \multicolumn{1}{l|}{\textbf{0.16 (1.5)}} & \multicolumn{1}{l|}{0.15} & \multicolumn{1}{l|}{0.00 (5)} & \multicolumn{1}{l|}{0.02 (4)} & \multicolumn{1}{l|}{0.08 (3)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{23} & \multicolumn{1}{l|}{0.80} & \multicolumn{1}{l|}{\textbf{0.96 (1)}} & \multicolumn{1}{l|}{0.91} & \multicolumn{1}{l|}{0.91} & \multicolumn{1}{l|}{0.68} & \multicolumn{1}{l|}{0.61} & \multicolumn{1}{l|}{0.67} & \multicolumn{1}{l|}{0.77 (2)} & \multicolumn{1}{l|}{0.73 (3)} & \multicolumn{1}{l|}{0.40 (4)} & \multicolumn{1}{l|}{0.10 (5)} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{Sum \textit{ranks}} & \multicolumn{4}{c|}{40}       & \multicolumn{4}{c|}{63}       & \multicolumn{1}{c|}{101} & \multicolumn{1}{c|}{87.5} & \multicolumn{1}{c|}{53.5} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{AVG \textit{ranks}} & \multicolumn{4}{c|}{1.74}     & \multicolumn{4}{c|}{2.74}     & \multicolumn{1}{c|}{4.39} & \multicolumn{1}{c|}{3.8} & \multicolumn{1}{c|}{2.32} \bigstrut\\
    \hline
    \end{tabular}%
  \label{tab3}%
\end{table}%

Analyzing the results shown in Table \ref{tab3}, one notes that the semi-supervised algorithms \textit{Algorithm X} and \textit{SSDBSCAN} present higher effectiveness in $17$ of the $23$ tested datasets (and two more draws in the first place).
And of these $17$ datasets, the Algorithm X presented a superior effectiveness in $9$ of them.
These results help to corroborate the claim that semi-supervised approaches help to obtain a data partitioning closer to the real dataset structure.

It is also possible to notice that the neighborhood defined for the \textit{hubness score} calculation can impact on the partitions generated by the \textit{Algorithm X}. 
This fact can be seen mainly by observing sets (2), (6), (7), (8), (11), (13), (14), (17), (20), (21) and (23). 
The same behavior is not evident in the results presented by the \textit{HPKM} algorithm. 
Therefore, it becomes necessary to investigate to which extent each one of the strategies employed by the \textit{Algorithm X} collaborate toward obtaining good results. 
The results of this evaluation are presented in Section \ref{exp2}. 

Aiming to verify if there exists a significant difference between the effectiveness of the evaluated algorithms, the \textit{Friedman} \cite{Demsar:2006} and the \textit{post-hoc of Bonferroni-Dunn} \cite{Zar:2007} statistics tests were used.
Both tests were applied in order to discover if with a 95\% of certainty one can conclude that the \textit{Algorithm X} algorithm surpasses the \textit{HPKM}, \textit{Kernel $k$-means}, \textit{DBSCAN} and \textit{SSDBSCAN} algorithms.

The \textit{Friedman} and the \textit{Bonferroni-Dunn} tests are based on the comparison of performance ranks (see Table \ref{tab3}). 
To apply the \textit{Friedman} test, we consider the sum of the \textit{ranks} ($R$) of each algorithm for the calculation of  $F_{F}$ such that:$F_{F} = (( N - 1)\chi^{2}_{F})/(N (A - 1) - \chi^{2}_{F})$, where $\chi^{2}_{F} = (12 / (NA(A + 1)) . \sum^{A}_{i=1} R^{2}_{i} - (3N(A + 1))  )$, $N$ is the number of datasets and $A$ is the number of tested algorithms. 
As the $F_{F}$ statistic (19.46) is greater than the critical value \textit{FDistribution} (2.47), this result shows that there exists a significant difference among the effectiveness of the algorithms.  

In pursuance of indicating which of the algorithms had the best performance, the \textit{post-hoc Bonferroni-Dunn} test was used, setting \textit{Algorithm X} as the control algorithm. 
In this test, the performance of two algorithms is statistically different, if the difference between the average \textit{ranks} divided by $\sqrt{\frac{A (A + 1)}{6 N}}$ is greater or equal to the critical difference ($CD$), which is calculated as: $CD = q_{\alpha}\sqrt{\frac{A (A + 1)}{6 N}}$, where the critical value $q_{\alpha}$ (2.498) is obtained from the table found in \cite{Demsar:2006}. 
With the $CD$ value calculated (1.16), one observes that the differences between the \textit{rank} averages of the algorithms \textit{Algorithm X} and \textit{HPKM} (2.14), \textit{Algorithm X} and \textit{Kernel $k$-means} (5.68), \textit{Algorithm X} and \textit{DBSCAN} (4.42) and \textit{Algorithm X} e \textit{SSDBSCAN} (1.25) were higher than $CD$. 
Therefore, it is possible to conclude that the effectiveness of the \textit{Algorithm X} algorithm is higher than that of the algorithms selected as the baseline for the tested datasets.

In addition to the effectiveness, the efficiency of the algorithms was also analyzed. 
Table \ref{tab4} presents the times (in milliseconds) spent by each algorithm for obtaining the results presented in Table \ref{tab3}.
The time required by the \textit{HPKM} and the \textit{Algorithm X} algorithms for calculating the \textit{hubness score} of the datasets is also shown. 
The time for calculating the \textit{hubness score} was computed for the different neighborhoods under consideration, i.e. (5), (10), (15) and (20). 
This time was considered separately, since it is a pre-processing stage of the \textit{HPKM} and \textit{Algorithm X} algorithms.    

\begin{table}[htbp]
    \caption{Execution time (milliseconds) of each algorithm. Column \textit{Hubness} presents time to compute the \textit{hubness} score of the datasets considering the neighborhood (K) equals to (5), (10), (15) and (20).
		The numbers in bold highlight the smallest times.
		Column D shows the ID of the datasets.}
\scalefont{0.70}
    \centering
    \setlength{\tabcolsep}{1.8pt}
    \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}
\cline{2-13}    \multicolumn{1}{r|}{} & \multicolumn{4}{c|}{\textit{\textbf{\textit{Hubness}}}} & \multicolumn{4}{c|}{\textit{\textbf{\textit{Algorithm X}}}} & \multicolumn{4}{c|}{\textit{\textbf{\textit{HPKM}}}} & \multicolumn{1}{r}{} & \multicolumn{1}{r}{} & \multicolumn{1}{r}{} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{D} & \multicolumn{1}{c|}{$K=5$} & \multicolumn{1}{c|}{$K=10$} & \multicolumn{1}{c|}{$K=15$} & \multicolumn{1}{c|}{$K=20$} & \multicolumn{1}{c|}{$K=5$} & \multicolumn{1}{c|}{$K=10$} & \multicolumn{1}{c|}{$K=15$} & \multicolumn{1}{c|}{$K=20$} & \multicolumn{1}{c|}{$K=5$} & \multicolumn{1}{c|}{$K=10$} & \multicolumn{1}{c|}{$K=15$} & \multicolumn{1}{c|}{$K=20$} & \multicolumn{1}{c|}{\textit{\textbf{KerKM}}} & \multicolumn{1}{c|}{\textit{\textbf{\textit{DBSCAN}}}} & \multicolumn{1}{c|}{\textit{\textbf{SSDBS}}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{1} & \multicolumn{1}{l|}{1,327} & \multicolumn{1}{l|}{1,327} & \multicolumn{1}{l|}{1,343} & \multicolumn{1}{l|}{1,358} & \multicolumn{1}{l|}{540} & \multicolumn{1}{l|}{630} & \multicolumn{1}{l|}{586} & \multicolumn{1}{l|}{586} & \multicolumn{1}{l|}{39} & \multicolumn{1}{l|}{\textbf{28}} & \multicolumn{1}{l|}{40} & \multicolumn{1}{l|}{34} & \multicolumn{1}{l|}{3,866} & \multicolumn{1}{l|}{1,386} & \multicolumn{1}{l|}{1,670} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{2} & \multicolumn{1}{l|}{297} & \multicolumn{1}{l|}{296} & \multicolumn{1}{l|}{296} & \multicolumn{1}{l|}{296} & \multicolumn{1}{l|}{162} & \multicolumn{1}{l|}{165} & \multicolumn{1}{l|}{150} & \multicolumn{1}{l|}{150} & \multicolumn{1}{l|}{143} & \multicolumn{1}{l|}{\textbf{107}} & \multicolumn{1}{l|}{116} & \multicolumn{1}{l|}{113} & \multicolumn{1}{l|}{334} & \multicolumn{1}{l|}{316} & \multicolumn{1}{l|}{588} \bigstrut\\

    \hline
    \multicolumn{1}{|c|}{3} & \multicolumn{1}{l|}{47} & \multicolumn{1}{l|}{47} & \multicolumn{1}{l|}{31} & \multicolumn{1}{l|}{63} & \multicolumn{1}{l|}{23} & \multicolumn{1}{l|}{22} & \multicolumn{1}{l|}{24} & \multicolumn{1}{l|}{21} & \multicolumn{1}{l|}{10} & \multicolumn{1}{l|}{10} & \multicolumn{1}{l|}{28} & \multicolumn{1}{l|}{\textbf{4}} & \multicolumn{1}{l|}{107} & \multicolumn{1}{l|}{57} & \multicolumn{1}{l|}{351} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{4} & \multicolumn{1}{l|}{2,325} & \multicolumn{1}{l|}{2,341} & \multicolumn{1}{l|}{2,356} & \multicolumn{1}{l|}{2,326} & \multicolumn{1}{l|}{1,229} & \multicolumn{1}{l|}{1,307} & \multicolumn{1}{l|}{1,351} & \multicolumn{1}{l|}{1,351} & \multicolumn{1}{l|}{78} & \multicolumn{1}{l|}{\textbf{63}} & \multicolumn{1}{l|}{66} & \multicolumn{1}{l|}{96} & \multicolumn{1}{l|}{2,236} & \multicolumn{1}{l|}{2,360} & \multicolumn{1}{l|}{5,460} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{5} & \multicolumn{1}{l|}{81,011} & \multicolumn{1}{l|}{81,198} & \multicolumn{1}{l|}{81,432} & \multicolumn{1}{l|}{81,588} & \multicolumn{1}{l|}{\textbf{540}} & \multicolumn{1}{l|}{755} & \multicolumn{1}{l|}{555} & \multicolumn{1}{l|}{555} & \multicolumn{1}{l|}{1,073} & \multicolumn{1}{l|}{1,177} & \multicolumn{1}{l|}{1,199} & \multicolumn{1}{l|}{1,131} & \multicolumn{1}{l|}{98,989} & \multicolumn{1}{l|}{80,988} & \multicolumn{1}{l|}{2,760} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{6} & \multicolumn{1}{l|}{1,202} & \multicolumn{1}{l|}{1,157} & \multicolumn{1}{l|}{1,204} & \multicolumn{1}{l|}{1,214} & \multicolumn{1}{l|}{1,200} & \multicolumn{1}{l|}{1,064} & \multicolumn{1}{l|}{1,120} & \multicolumn{1}{l|}{1,049} & \multicolumn{1}{l|}{184} & \multicolumn{1}{l|}{100} & \multicolumn{1}{l|}{\textbf{64}} & \multicolumn{1}{l|}{86} & \multicolumn{1}{l|}{3,259} & \multicolumn{1}{l|}{1,195} & \multicolumn{1}{l|}{8,935} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{7} & \multicolumn{1}{l|}{15} & \multicolumn{1}{l|}{13} & \multicolumn{1}{l|}{15} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{19} & \multicolumn{1}{l|}{25} & \multicolumn{1}{l|}{19} & \multicolumn{1}{l|}{19} & \multicolumn{1}{l|}{26} & \multicolumn{1}{l|}{28} & \multicolumn{1}{l|}{7} & \multicolumn{1}{l|}{9} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{19} & \multicolumn{1}{l|}{140} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{8} & \multicolumn{1}{l|}{321,890} & \multicolumn{1}{l|}{361,937} & \multicolumn{1}{l|}{305,449} & \multicolumn{1}{l|}{413,557} & \multicolumn{1}{l|}{891,045} & \multicolumn{1}{l|}{752,290} & \multicolumn{1}{l|}{691,510} & \multicolumn{1}{l|}{910,188} & \multicolumn{1}{l|}{\textbf{82,345}} & \multicolumn{1}{l|}{102,945} & \multicolumn{1}{l|}{86,362} & \multicolumn{1}{l|}{89,370} & \multicolumn{1}{l|}{1,529,628} & \multicolumn{1}{l|}{404,494} & \multicolumn{1}{l|}{5,069,043} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{9} & \multicolumn{1}{l|}{75,801} & \multicolumn{1}{l|}{75,472} & \multicolumn{1}{l|}{75,972} & \multicolumn{1}{l|}{75,863} & \multicolumn{1}{l|}{17,170} & \multicolumn{1}{l|}{26,458} & \multicolumn{1}{l|}{16,546} & \multicolumn{1}{l|}{16,546} & \multicolumn{1}{l|}{15,156} & \multicolumn{1}{l|}{15,106} & \multicolumn{1}{l|}{\textbf{14,980}} & \multicolumn{1}{l|}{15,969} & \multicolumn{1}{l|}{67,495} & \multicolumn{1}{l|}{75,953} & \multicolumn{1}{l|}{229,852} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{10} & \multicolumn{1}{l|}{24,399} & \multicolumn{1}{l|}{24,586} & \multicolumn{1}{l|}{24,710} & \multicolumn{1}{l|}{24,632} & \multicolumn{1}{l|}{3,975} & \multicolumn{1}{l|}{3,834} & \multicolumn{1}{l|}{3,847} & \multicolumn{1}{l|}{3,847} & \multicolumn{1}{l|}{383} & \multicolumn{1}{l|}{310} & \multicolumn{1}{l|}{\textbf{307}} & \multicolumn{1}{l|}{466} & \multicolumn{1}{l|}{24,181} & \multicolumn{1}{l|}{24,627} & \multicolumn{1}{l|}{35,010} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{11} & \multicolumn{1}{l|}{49,842} & \multicolumn{1}{l|}{49,873} & \multicolumn{1}{l|}{50,388} & \multicolumn{1}{l|}{50,622} & \multicolumn{1}{l|}{35,016} & \multicolumn{1}{l|}{34,167} & \multicolumn{1}{l|}{32,526} & \multicolumn{1}{l|}{32,526} & \multicolumn{1}{l|}{477} & \multicolumn{1}{l|}{\textbf{432}} & \multicolumn{1}{l|}{469} & \multicolumn{1}{l|}{650} & \multicolumn{1}{l|}{98,211} & \multicolumn{1}{l|}{50,084} & \multicolumn{1}{l|}{70,193} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{12} & \multicolumn{1}{l|}{2,451} & \multicolumn{1}{l|}{2,435} & \multicolumn{1}{l|}{2,465} & \multicolumn{1}{l|}{2,481} & \multicolumn{1}{l|}{1,451} & \multicolumn{1}{l|}{1,707} & \multicolumn{1}{l|}{1,810} & \multicolumn{1}{l|}{1,810} & \multicolumn{1}{l|}{58} & \multicolumn{1}{l|}{\textbf{34}} & \multicolumn{1}{l|}{66} & \multicolumn{1}{l|}{50} & \multicolumn{1}{l|}{5,761} & \multicolumn{1}{l|}{2,472} & \multicolumn{1}{l|}{3,543} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{13} & \multicolumn{1}{l|}{14,103} & \multicolumn{1}{l|}{16,866} & \multicolumn{1}{l|}{16,611} & \multicolumn{1}{l|}{14,461} & \multicolumn{1}{l|}{21,463} & \multicolumn{1}{l|}{23,159} & \multicolumn{1}{l|}{24,320} & \multicolumn{1}{l|}{23,,312} & \multicolumn{1}{l|}{\textbf{642}} & \multicolumn{1}{l|}{870} & \multicolumn{1}{l|}{918} & \multicolumn{1}{l|}{1,311} & \multicolumn{1}{l|}{37,468} & \multicolumn{1}{l|}{13,964} & \multicolumn{1}{l|}{41,862} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{14} & \multicolumn{1}{l|}{578} & \multicolumn{1}{l|}{577} & \multicolumn{1}{l|}{594} & \multicolumn{1}{l|}{608} & \multicolumn{1}{l|}{253} & \multicolumn{1}{l|}{269} & \multicolumn{1}{l|}{259} & \multicolumn{1}{l|}{259} & \multicolumn{1}{l|}{81} & \multicolumn{1}{l|}{79} & \multicolumn{1}{l|}{68} & \multicolumn{1}{l|}{\textbf{57}} & \multicolumn{1}{l|}{1,071} & \multicolumn{1}{l|}{606} & \multicolumn{1}{l|}{8,329} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{15} & \multicolumn{1}{l|}{15} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{15} & \multicolumn{1}{l|}{15} & \multicolumn{1}{l|}{\textbf{6}} & \multicolumn{1}{l|}{\textbf{6}} & \multicolumn{1}{l|}{9} & \multicolumn{1}{l|}{9} & \multicolumn{1}{l|}{26} & \multicolumn{1}{l|}{12} & \multicolumn{1}{l|}{23} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{22} & \multicolumn{1}{l|}{25} & \multicolumn{1}{l|}{117} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{16} & \multicolumn{1}{l|}{4,727} & \multicolumn{1}{l|}{4,774} & \multicolumn{1}{l|}{4,805} & \multicolumn{1}{l|}{4,789} & \multicolumn{1}{l|}{1,501} & \multicolumn{1}{l|}{1,497} & \multicolumn{1}{l|}{1,863} & \multicolumn{1}{l|}{1,863} & \multicolumn{1}{l|}{144} & \multicolumn{1}{l|}{103} & \multicolumn{1}{l|}{\textbf{54}} & \multicolumn{1}{l|}{101} & \multicolumn{1}{l|}{6,331} & \multicolumn{1}{l|}{4,943} & \multicolumn{1}{l|}{7,024} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{17} & \multicolumn{1}{l|}{218} & \multicolumn{1}{l|}{266} & \multicolumn{1}{l|}{234} & \multicolumn{1}{l|}{234} & \multicolumn{1}{l|}{244} & \multicolumn{1}{l|}{237} & \multicolumn{1}{l|}{294} & \multicolumn{1}{l|}{294} & \multicolumn{1}{l|}{132} & \multicolumn{1}{l|}{\textbf{90}} & \multicolumn{1}{l|}{106} & \multicolumn{1}{l|}{122} & \multicolumn{1}{l|}{219} & \multicolumn{1}{l|}{247} & \multicolumn{1}{l|}{885} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{18} & \multicolumn{1}{l|}{79} & \multicolumn{1}{l|}{79} & \multicolumn{1}{l|}{79} & \multicolumn{1}{l|}{79} & \multicolumn{1}{l|}{31} & \multicolumn{1}{l|}{47} & \multicolumn{1}{l|}{38} & \multicolumn{1}{l|}{38} & \multicolumn{1}{l|}{27} & \multicolumn{1}{l|}{21} & \multicolumn{1}{l|}{\textbf{18}} & \multicolumn{1}{l|}{21} & \multicolumn{1}{l|}{65} & \multicolumn{1}{l|}{90} & \multicolumn{1}{l|}{695} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{19} & \multicolumn{1}{l|}{94} & \multicolumn{1}{l|}{93} & \multicolumn{1}{l|}{94} & \multicolumn{1}{l|}{109} & \multicolumn{1}{l|}{65} & \multicolumn{1}{l|}{56} & \multicolumn{1}{l|}{78} & \multicolumn{1}{l|}{78} & \multicolumn{1}{l|}{46} & \multicolumn{1}{l|}{44} & \multicolumn{1}{l|}{46} & \multicolumn{1}{l|}{\textbf{35}} & \multicolumn{1}{l|}{147} & \multicolumn{1}{l|}{103} & \multicolumn{1}{l|}{574} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{20} & \multicolumn{1}{l|}{14} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{15} & \multicolumn{1}{l|}{15} & \multicolumn{1}{l|}{\textbf{3}} & \multicolumn{1}{l|}{\textbf{3}} & \multicolumn{1}{l|}{\textbf{3}} & \multicolumn{1}{l|}{\textbf{3}} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{14} & \multicolumn{1}{l|}{12} & \multicolumn{1}{l|}{13} & \multicolumn{1}{l|}{13} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{374} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{21} & \multicolumn{1}{l|}{47} & \multicolumn{1}{l|}{47} & \multicolumn{1}{l|}{46} & \multicolumn{1}{l|}{47} & \multicolumn{1}{l|}{22} & \multicolumn{1}{l|}{34} & \multicolumn{1}{l|}{34} & \multicolumn{1}{l|}{34} & \multicolumn{1}{l|}{25} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{13} & \multicolumn{1}{l|}{\textbf{13}} & \multicolumn{1}{l|}{56} & \multicolumn{1}{l|}{63} & \multicolumn{1}{l|}{347} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{22} & \multicolumn{1}{l|}{156} & \multicolumn{1}{l|}{156} & \multicolumn{1}{l|}{172} & \multicolumn{1}{l|}{156} & \multicolumn{1}{l|}{69} & \multicolumn{1}{l|}{65} & \multicolumn{1}{l|}{66} & \multicolumn{1}{l|}{66} & \multicolumn{1}{l|}{60} & \multicolumn{1}{l|}{59} & \multicolumn{1}{l|}{\textbf{47}} & \multicolumn{1}{l|}{63} & \multicolumn{1}{l|}{156} & \multicolumn{1}{l|}{178} & \multicolumn{1}{l|}{207} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{23} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{1} & \multicolumn{1}{l|}{3} & \multicolumn{1}{l|}{6} & \multicolumn{1}{l|}{\textbf{3}} & \multicolumn{1}{l|}{\textbf{3}} & \multicolumn{1}{l|}{12} & \multicolumn{1}{l|}{13} & \multicolumn{1}{l|}{13} & \multicolumn{1}{l|}{12} & \multicolumn{1}{l|}{16} & \multicolumn{1}{l|}{9} & \multicolumn{1}{l|}{40} \bigstrut\\
    \hline
    \end{tabular}%
   
  \label{tab4}%
\end{table}%

It is possible to note that the \textit{HPKM} algorithm presents the lowest run times in 19 of the 23 tested datasets. 
It was expected that through the comparison of the \textit{HPKM} and the \textit{Algorithm X} algorithms, the \textit{HPKM} would present a lower run time, since it does not possess the overhead of the semi-supervised approach. 
However, it is important to highlight that in spite of this fact, \textit{Algorithm X} demanded less time than the \textit{HPKM} in 4 of the evaluated datasets (sets 5, 15, 20 and 23).    

Analyzing the performance of the \textit{Algorithm X} algorithm regarding the others (that is, not considering the \textit{HPKM} algorithm), it is possible to verify that it presents the lowest run times in 18 of the 23 evaluated datasets. 
Moreover, when only the semi-supervised clustering approaches \textit{Algorithm X} and \textit{SSDBSCAN} are considered, the \textit{Algorithm X} algorithm presents the lowest run times for all datasets. 
Noteworthy here is that, even when considering the total sum of the time spent with the \textit{hubness score} calculation to the processing time of the \textit{Algorithm X} algorithm, it demanded less time than the \textit{SSDBSCAN} algorithm in 19 of the 23 datasets. 
For example, for the dataset 8, the \textit{Algorithm X} algorithm demanded 74\% less time than the \textit{SSDBSCAN} and obtained a better effectiveness (see Table \ref{tab3}).    

\subsection{Varying the parameters} \label{exp2}

The experimental results presented in Section \ref{exp1} show that the \textit{Algorithm X} algorithm has a higher effectiveness than all other algorithms considered in the evaluation and an efficiency higher than three of these algorithms.
It loses only to the \textit{HPKM} that employs an unsupervised clustering approach. 
In addition, these results also show a variation in the effectiveness of the \textit{Algorithm X} algorithm when the neighborhood defined by the \textit{hubness score} calculation varies. 
With the aim of investigating the individual contribution of each strategy employed by the \textit{Algorithm X}algorithm in the final result of the clustering experiments described herein, two variations of the parameters were considered: the non-updating of the main representatives (Section \ref{exp2_1}) and the different percentages of borderline elements (Section \ref{exp2_2}). 

To perform these experiments, 10 of the 23 datasets were selected, which were used in the experiments described in Section \ref{exp1} (see Table \ref{tab3}): Churn (4), Covertype (5), Digits389 (6), Hepmass (8), Isolet (9), Musk2 (10), NBA (11), Pendigits (13), Segment (14) and Urbanlandcover (17). 
These sets were selected while taking into consideration that, in general, they present the highest quantity of instances and greater variability of classes and dimensions.  

\subsubsection{Non-updating of the main representatives }\label{exp2_1}

The original version of the \textit{Algorithm X} presented in Algorithm \ref{alg1} (lines 13 to 18) considers the updating of the main representatives at each iteration. 
However, as this phase is unsupervised, it is possible for the main representative to be replaced by a data instance which does not have the same label as the main representative of the previous iteration.  

Therefore, for these experiments, we wanted to verify if the updating of the main representatives could have a negative impact, in terms of the effectiveness of the algorithm, as it may diverge from the information obtained through the selection of the initial representatives during the interaction phase with the user. 
For this investigation, a new version of the algorithm was implemented that does not update the main representatives at each iteration. 
This version only maintained the update for the auxiliary representatives that are derived from the \textit{must-link} constraints.  

Table \ref{tab5} presents the results of this evaluation. 
Column (1) represents the original version of the \textit{Algorithm X} algorithm, and column (2) the modified version that does not consider the updating of the main representatives.

Observing Table \ref{tab5} it is noted that for values lower than $K=5$, the new version without the updating of the main representatives surpasses the original version in 7 out of the 10 evaluated datasets. 
Considering $K=20$, the new version presents an effectiveness that is superior for every one of the 10 evaluated datasets. 
As the value of $K$ increases, the number of datasets for which the new version presents superior results increases and the difference in the effectiveness also increases.    

\begin{table}[htbp]
    \caption{Comparison of \textit{Algorithm X} algorithm with (1) and without (2) updating the main representatives.}
\scalefont{0.86}
    \centering
    \setlength{\tabcolsep}{3pt}
    \begin{tabular}{|r|c|c|c|c|c|c|c|c|}
\cline{2-9}    \multicolumn{1}{r|}{} & \multicolumn{4}{c|}{\textbf{\textit{Algorithm X} (1)}} & \multicolumn{4}{c|}{\textbf{\textit{Algorithm X} (2)}} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{Dataset} & $K=5$   & $K=10$  & $K=15$  & $K=20$  & $K=5$   & $K=10$  & $K=15$  & $K=20$ \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{4} & -0.02 & \textbf{0.15} & 0.03  & 0.02  & 0.03  & \textbf{0.15} & 0.11  & 0.10 \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{5} & 0.20  & 0.23  & 0.24  & 0.19  & 0.22  & 0.24  & \textbf{0.25} & 0.24 \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{6} & 0.10  & 0.74  & 0.79  & 0.47  & 0.50  & 0.95  & 0.89  & \textbf{0.97} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{8} & \textbf{0.32} & 0.22  & 0.30  & 0.19  & 0.23  & 0.22  & 0.17  & 0.25 \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{9} & 0.52  & 0.49  & 0.49  & 0.50  & 0.28  & 0.55  & \textbf{0.56} & 0.54 \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{10} & 0.07  & -0.01 & -0.01 & -0.02 & 0.09  & 0.20  & 0.12  & \textbf{0.25} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{11} & -0.01 & 0.74  & -0.03 & 0.63  & 0.14  & 0.60  & 0.61  & \textbf{0.75} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{13} & 0.67  & 0.49  & 0.56  & 0.54  & 0.55  & \textbf{0.79} & 0.73  & 0.76 \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{14} & 0.37  & 0.50  & 0.46  & 0.50  & 0.52  & 0.59  & 0.59  & \textbf{0.61} \bigstrut\\
    \hline
    \multicolumn{1}{|c|}{17} & 0.08  & 0.42  & 0.42  & 0.42  & 0.43  & 0.48  & 0.47  & \textbf{0.49} \bigstrut\\
    \hline
    \end{tabular}%
  \label{tab5}%
\end{table}%

This behavior can be explained by the fact that when the algorithm considers a smaller neighborhood (for example, $K=5$) for the identification of \textit{hubs}, these may not initially be so representative. 
Therefore, in this case, the final clustering result can be improved through the approach that allows for the updating of main representatives at each iteration. 
On the other hand, when the algorithm considers a larger neighborhood (for example, $K=20$), the \textit{hubs} become more representative and the selection of the initial representatives at the interaction phase with the user becomes sufficient for obtaining good results.  

\subsubsection{Percentage variation of borderline instances}\label{exp2_2} 

The clustering approach employed by the \textit{Algorithm X} algorithm (see Section \ref{prop}) allows for semi-supervision in two moments: during the selection of the initial representatives and during the analysis of the borderline elements. 
The experiments described in this section aim to allow the evaluation of the contribution made in this phase of the analysis of borderline elements to the final clustering result. 
Hence, Table \ref{tab6} exhibits the results of the experiments by considering the parameter $f$ as varying from $0$ to $10\%$ of the dataset size. 
Noteworthy here is that when $f=0\%$ none of the borderline instances are analyzed, i.e., semi-supervision is only considered in the definition of the initial representatives at the first iteration of the algorithm. 
For the experiments shown herein, $K=10$ was adopted for the calculation of the \textit{hubness score}.

\begin{table}[htbp]
    \caption{Comparison of \textit{Algorithm X} algorithm with different percentages for borderline instances.}
\scalefont{0.86}
    \centering
    \setlength{\tabcolsep}{3pt}
\begin{tabular}{|c|c|c|c|c|}
\cline{2-5}    \multicolumn{1}{c|}{} & \multicolumn{4}{c|}{\textbf{\textit{Algorithm X}}} \bigstrut\\
    \hline
    Dataset & 0\%   & 1\%   & 5\%   & 10\% \bigstrut\\
    \hline
    4     & 0.04  & 0.15  & 0.20  & \textbf{0.33} \bigstrut\\
    \hline
    5     & 0.15  & 0.23  & 0.20  & \textbf{0.27} \bigstrut\\
    \hline
    6     & 0.59  & 0.74  & 0.92  & \textbf{0.95} \bigstrut\\
    \hline
    8     & 0.14  & 0.22  & 0.20  & \textbf{0.27} \bigstrut\\
    \hline
    9     & 0.46  & 0.49  & 0.54  & \textbf{0.55} \bigstrut\\
    \hline
    10    & -0.01 & -0.01 & -0.06 & \textbf{0.04} \bigstrut\\
    \hline
    11    & 0.04  & 0.74  & 0.75  & \textbf{0.79} \bigstrut\\
    \hline
    13    & 0.50  & 0.49  & 0.53  & \textbf{0.62} \bigstrut\\
    \hline
    14    & 0.45  & 0.50  & 0.50  & \textbf{0.66} \bigstrut\\
    \hline
    17    & 0.46  & 0.42  & 0.45  & \textbf{0.49} \bigstrut\\
    \hline
    \end{tabular}%
  \label{tab6}%
\end{table}%

Through the analysis of the results presented in Table \ref{tab6}, one notes that, in a general sense, the rate at which the value of the parameter $f$ increases, the effectiveness of the algorithm also increases. 
For example, for dataset 4, the increase in effectiveness varied from $3.75$ to $8.25$ times when compared to the result obtained through running the \textit{Algorithm X} algorithm with $f=0$ and for dataset 11, the increase in effectiveness varied from $18.50$ to $19.75$ times when compared to the results obtained with $f=0$.    

\section{CONCLUSIONS} \label{conc}

The combination of \textit{hubness} with semi-supervision strategies to allow clustering results, which match best with the desired partitioning for high-dimensional data, had still not been explored in the related works.
The proposed \textit{Algorithm X} algorithm employs a semi-supervised clustering approach based on partitioning, in which each partition is represented by multiple prototypes with its definition based on \textit{hubness score} information of the data instances. 
This information is used by the \textit{Algorithm X} semi-supervision strategies at two moments: during the selection of the initial representatives and during the analysis of borderline elements.    

The experimental results demonstrate that the method developed herein statistically surpasses four approaches proposed in the literature that present good results in the treatment of high-dimensional data; those being \textit{HPKM}, \textit{Kernel $k$-means}, \textit{DBSCAN} and \textit{SSDBSCAN}. 
Moreover, it was shown that the proposed algorithm possesses great potential for dealing with different quantities of instances, clusters and dimensions. 
Among the planned future work, the exploration of other strategies for the selection of borderline elements in the semi-supervision phase is prioritized, as well as work toward improving the computational efficiency of the method for calculating the \textit{hubness scores}, taking as a base the work described in Section \ref{background}.


\bibliographystyle{jidm}
\bibliography{jidmb}


\begin{received}
\end{received}

\end{document}
