\documentclass[11pt,twoside]{article}
\usepackage{informat}
\usepackage{epsfig}

\usepackage{amsmath}

%% old imports?
\usepackage{dcolumn}
\usepackage{endnotes}

\usepackage{multicol}
\usepackage{mathptmx}

\usepackage{url}

\usepackage{amssymb}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{todonotes}
\usepackage{comment}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{float}

\usepackage{biblatex}
\addbibresource{references.bib}

\begin{document}
  \title{Parametrized MTree Clusterer for Weka}
  \author{Marian Cristian Mih\u{a}escu, Marius Andrei Ciurez \\
      Department of Computer Science and Information Technologies\\
      Faculty of Automatics, Computers and Electronics\\
      University of Craiova, Craiova, Romania\\
      E-mail: cristian.mihaescu@edu.ucv.ro \\
      E-mail: mariusandrei.ciurez@gmail.com
      }
  \titleodd{Parametrized MTree Clusterer for Weka}
  \authoreven{M.C.  Mihaescu et al.}
  \keywords{Clustering, MTrees, Metric spaces}
  \received{June 24, 2021}

  \abstract{In the area of clustering, proposing or improving new algorithms represents a challenging task due to an already existing well-established list of algorithms and various implementations that allow rapid evaluation against tasks on publicly available datasets. In this work, we present an improved version of the MTree clustering algorithm that has been implemented within Weka workbench. The algorithmic approach starts from classical metric spaces and integrates parametrized business logic for finding the optimal number of clusters, choosing the division policy and other characteristics. The result is a versatile data structure that may be used in the context of clustering for finding the optimal number of clusters, but mainly for loading datasets, which already have a known structure. Experimental results show the MTree manages to find the right structure in two clustering tasks, although other algorithms fail in various ways. A discussion of topics related to further improvements and experiments on real datasets and tasks is included.}
  \abstractSi{}

  \maketitle

\section{Introduction}
Clustering, as an unsupervised learning technique is continuously getting attention within the machine learning area due to a large number of available algorithms and wide range of application domains for which practical solutions are continually being designed and implemented.

The general problem of building clusters of objects is narrowed down in \cite{von2012clustering} by clearly stating that the first thing that needs to be taken into consideration is the context of the problem. Therefore, building a general purpose clustering algorithm that may work with any objects and solve any task is not a realistic option. Therefore, the objects that we need to work as well as the precise task description accompanied by particular distance and evaluation metrics or various algorithmic approaches need to carefully take care in the process of building a clustering data analysis workflow.  

Recently, in \cite{adolfsson2019cluster}, authors raised the problem of clusterability of a dataset. Having an available dataset does not necessarily imply that we may meaningfully run a clustering process to solve a particular task. Thus, defining clusterability becomes a critical issue and checking if a dataset is clusterable becomes an inherently tricky problem, especially when dealing with real data and trying to solve a particular practical task.

%   [p1] 
The wide range of approaches used in available implemented clustering algorithms have found various application domains where they provide efficient solutions to many practical tackled problems. From the many application domains we mention medical image processing (i.e., pattern recognition and image segmentation) \cite{silva2016hybrid} \cite{goswami2013brain}, general and natural language processing knowledge discovery \cite{gan2007data} \cite{minarro2015knowledge} \cite{rebedeanews}, navigation of robots \cite{di2012fully} \cite{gauci2014clustering} and in many other contexts.

%   [p2] 
In the area of unsupervised learning there are several general classes of clustering algorithms (i.e., flat, hierarchical and density based) that all share two common problems: finding the optimal number of clusters and quickly and efficiently finding the correct clusters taking into consideration specific distance measures appropriate for the objects (i.e., pixels, points, persons, books, etc.) that are being grouped. Further, once the clusters are being correctly determined, there may be later used to query for the nearest neighbours or run specific range queries. Depending upon the inner data structures used for managing the clusters when tree data structures are being used efficiently than searching or traversing may be in general accomplished. 

%   research issue
%   [p3] 
The objective of this work is to present an improved version of the metric trees (MTree) algorithm that has been firstly proposed by \cite{ciaccia1997indexing} and later by \cite{uhlmann1991satisfying} and \cite{zezula2006similarity}. The first proposal of using MTrees in the context of clustering has been made in \cite{mihaescu2012using} and later implemented as Weka \cite{eibe2016weka} package in \cite{MTree_Clusterer_weka_package}. The last improved version has been tested in a comparative benchmark with k-MS morphological reconstruction clustering algorithm \cite{rodrigues2017k} along with classical algorithms (i.e., simple k-means, Cobweb, Farther First and Canopy) in \cite{ciurez2018improved}.

In this paper, we present a further improved parametrized version of the MTree algorithm in terms of managed items, used distance, the method for finding and setting K (i.e., the number of clusters), division policy and validation metrics. The critical improvement of the new parametrized version of the MTree clusterer is that it is now suitable to address a broader range of problems. The parametrized version is not suitable for solving any clustering problem by dynamically choosing at runtime the adequate parameters. Instead, a wide range of clustering problems may be addressed to newly proposed MTree cluster by properly setting its parameters depending on the available data objects and the tackled task. 

In general, there are two types of clustering problems. One regards finding patterns in a dataset which we do not know if it has a particular structure or if a certain number of clusters exists. The second type of task regards correctly building a data clustering model that may later be queried many times for getting specific information about managed data. In this scenario, the cluster model is built only once such that it may be regarded as a preprocessing step. Later, at runtime, few insertions and updates may occur while the majority of calls are range queries or kNN queries which need to be solved correctly and efficiently. The current proposed approach is suited for both types of tasks, but the second one is more appropriate.        

%   [p5] 
The paper is organized as follows. In Section 2, we perform a literature review with regards to similar libraries, other application domain usages of metric trees for clustering such as time series analysis of cytometry data, recommender systems, spatial clustering data, automatic computing the number of clusters for colour or grey scale image segmentation and clustering quality metrics. Section 3 describes the proposed approach with a detailed presentation of how each parameter may be set and how it influences the business logic of the MTree. Section 4 presents the experimental results on two publicly available datasets with runs on several parameter settings. Finally, section 5 contains the conclusions of this work, summarizes the main contributions and discusses potential improvements and applications.

\section{Related work, limitations and approaches}
%   Clustering and Image clustering
Data clustering (also known as unsupervised learning) represents a subarea of machine learning along supervised learning, reinforcement learning or deep learning. A particular sub-domain is represented by image clustering and segmentation \cite{dhanachandra2015image} which presents the use of subtractive clustering along with classical K-means algorithm to preprocess the data for optimal centroid initialization. The experimental results were obtained on medical images representing infected blood cells with malaria and on classical images used for segmentation brings better results than k-means taking into account RMSE and PSNR metrics.


%   Clustering and Image clustering 

Another approach for image clustering was proposed by Chang et al. in \cite{chang2017deep}. They propose a Deep Adaptive Clustering (DAC) approach that reduces to a classification problem in which similarity is determined by cosine distance and learned labelled features tend to be one-hot vectors obtaining good results on popular and accessible datasets like MNIST, CIFAR-10 and STL-10.


%   #10 Image segmentation
%   \cite{wang2009adaptive} 
One of the critical practical usages of clustering algorithms is for image segmentation. Including spatial information along with taking outlier points at a later stage in the clustering algorithm has been proposed in \cite{wang2009adaptive}. From this perspective, outliers are data points with almost equal distance to their adjacent clusters and therefore should be taken into consideration later. This approach raises two issues. One regards the fact that the order in which data points are given to the algorithm has significant importance. Thus, if a clustering algorithm is highly sensitive to the order in which data points are provided with a custom preprocessing may be necessary. The second issue regards the very nature of the data set from the clusterability perspective. The critical verification that is also highly recommended is to always check for clusterability before starting to the clustering analysis.  

%   #8
%   \cite{zhou2019automatic}
Another application of clustering is grey scale image segmentation \cite{zhou2019automatic}. As compared with the clustering of colour images or with images that incorporate spatial information, the task is to highly decrease the time complexity of the algorithm by using affinity propagation (AP) clustering algorithm. As always, when real life grey scale images are being clustered the problem of correctly determining the number of clusters or segments is a critical one.

%   #6 works with spatial data & EM
%   \cite{tianming2005clustering}
%
%       IF NEEDED!!!!
%
%   - another data type, i.e. spatial data
%   - uses EM and newly proposed NEM

%   CBIR: Content based image retrieval
%   one phrase is needed for jain1996image

More elaborate applications regard indexing and retrieval of similar images from an image database (CBIR - Content-Based Image Retrieval) which represent a challenging task that has been addressed in \cite{maheshwari2009image} and \cite{jain1996image}. The first approach uses features, colour and texture. It employs K-means and hierarchical clustering for finding the most similar images. The second approach uses colour, texture and shape as features and K-means as business logic for determining four classes of images: dinosaurs, flowers, buses and elephants. The obtained experimental results are promising in terms of excellent precision and recall values.


%   new clustering algs. for recommendations in collaborative filtering 
%   \cite{deng2019anovel}
Clustering has also been used successfully in recommender systems that were based on collaborative filtering in \cite{deng2019anovel}. A novel K-medoids clustering recommendation algorithm has been proposed, which introduced an improved Kullback-Leibler divergence for computing item similarity. The final task was to improve the effectiveness of the developed recommendation system.


%   #5 clustering in cytometry data
%   \cite{putri2019chronoclust}
Lately, in the application domain of immunology has been used clustering algorithms - \textit{ChronoClust}, a new density-based clustering algorithm - on time series cytometry data \cite{putri2019chronoclust}. The task was to characterize the immune response to disease by tracking temporal evolution.

%   #9
%   \cite{adolfsson2019cluster} 

Very recent works \cite{adolfsson2019cluster} put a high emphasis on defining clusterability and checking if a dataset is clusterable as a preprocessing step before any other data analysis is further performed. Therefore, before applying the algorithm for solving a task that requires clustering a \textit{sanity check} may be required, in the way that we should verify the clusterability of the dataset. In other words, clustering may not work on datasets which do not exhibit any internal structure, irrespective of any particular algorithm that may be employed. In our case, clusterability becomes a prerequisite that the dataset needs to meet before being loaded into the MTree structure.  The new proposed clustering algorithm should have as main scenario working with data that is known to be clusterable, for which we know it has a clear structure and with a known number of clusters. If the number of clusters is not known than the results highly depend on the particular practical context of the clustering problem. The context is defined by the problem (clustered objects and clustering task) and parameters of the MTree: object type, distance function, splitting policy and validation metrics. If the dataset is not clusterable, we argue that the MTree algorithm - as well as any other clustering algorithms - will exhibit undefined behaviour. 


%   Finding optimal K
A more complex context occurs when the image source is unknown or when the ground truth for the training dataset is also unknown \cite{caldelli2011fast} \cite{dash2016image}. In this particular situation, finding the optimal K represents am an inherently difficult task.  From an experimental algorithmic perspective, using proper distance metrics and loss function in this optimization problem represents one of the key ingredients towards successful results. Such approaches propose fancy solutions such as hierarchical clustering or clustering ensembles based graph partitioning methods,  cluster-based Similarity Partitioning Algorithm (CSPA), HyperGraph Partitioning Algorithm (HGPA), and Meta Clustering Algorithm (MCLA).  


Among the most well-known issues in unsupervised learning consists in determining the actual number of clusters from a dataset. Unfortunately, scenarios in which the value of K is known to occur only in a few practical systems. In general, an application that performs an image processing task does not have any information regarding the actual number of clusters from the target image. This situation may occur when dealing with data streams \cite{guha2016clustering} or with very high-dimensional datasets \cite{esmin2015areview}. In general, one of the most suitable approaches tries to reduce to automatic determination of K that may be based on dynamic clustering \cite{esmin2015areview} or joint tracking segmentation \cite{milan2015joint}.

%   general method for finding optimal K
%   \cite{malika2014nbclust} 
A general-purpose algorithm for finding the optimal number of clusters has been proposed by \cite{malika2014nbclust} and implemented in an R package in NbClust. The main idea of this approach is that it may use up to 30 indices for voting the number of clusters. The package has implemented a function to run a clustering algorithm (i.e., k-means or hierarchical clustering) using various distance measures and aggregation methods. The main limitation of the approach is that it is general and practical usage for particular datasets needs to be parametrized by the appropriate clustering algorithm, subset of indices, distance measure and aggregation method.

%   #7 finding K in colour images
%   \cite{garciakamont2018automatic}
One particular usage of clustering regards automatic computing of the number of clusters for colour image segmentation \cite{garciakamont2018automatic}. This approach uses fuzzy c-means algorithms for extracting chromaticity features of colours and trains a Neural-Networks with obtained chromatic data of colours. The trained model may be further used on new colour images to predict the number of clusters in colour images.


%   \cite{hermes2019leac} 
%   open source library in git for clustering
Among many clustering libraries, we mention LEAC \cite{hermes2019leac}. It is an open-source library with source code publicly available in the GitHub repository. Thus, once the experiments are also performed on publicly available datasets, the results may be reproducible and also used in other setups for further improvements. Inclusion of 23 state-of-the-art Evolutionary Algorithms for partial clustering within a library that allows easy and fast development and integration of new clustering algorithm represents the solution that we also target when improving MTree clustering algorithm within Weka package. 

%   #3 closest usage of metric trees => should have a larger paragraph
%   \cite{deves2018scalable} 
Another usage of metric trees has been reported recently in \cite{deves2018scalable}. The task is to quickly and efficiently scale-up the problem of shadow rendering for 70 million objects (i.e., triangles) in real-time. The proposed metric tree uses as splitting policy binary space partitioning (BSP) and ternary object partitioning (TOP) for grouping triangles into clusters as precomputed bounding capsules (line-swept spheres).

%   Clustering quality metrics
%   review!
Finally, the whole clustering process needs validation, and many quality metrics may accomplish this for a wide range of algorithms \cite{fahad2014asurvey}.  Depending on the structure of the dataset, various clustering quality frameworks \cite{gonzales2017formal}, \cite{santos2015categorical} have been proposed. The key issue that always arises regards choosing the proper similarity and quality metrics \cite{santos2015categorical}.

%
%       PROPOSED APPROACH
%

\section{Proposed approach}
The proposed MTree parametrized clusterer has been firstly proposed in \cite{mihaescu2012using} in an attempt to define a new clustering algorithm that has as main business logic the metric trees initially presented in \cite{ciaccia1997indexing} and later in \cite{uhlmann1991satisfying} and \cite{zezula2006similarity}. The initial C++ implementation approach was designed to cluster students who were defined by three of their obtained grades during one semester. The main shortcoming of the proposed structure was that it as designed only for managing student objects and had several hard-coded parameters needed for building the tree. The most important one is \textit{nrKeys}, which represents the maximum number of students contained in a node (i.e., a cluster). This approach has a critical limitation in the fact that the \textit{splitNote} method was called based only when a note was full. Other limitations regard the lack of parametrized division policy, distance metrics or other features needed for flexibly running a clustering process.

Later, the initially proposed MTree clustering algorithm has been contributed as an official Weka package \cite{MTree_Clusterer_weka_package}. This newly Java-based approach had the goal to be functionally available under Weka workbench as any other clusterer, such that it may be further used in various practical situations. The MTree clusterer from Weka has been used in \cite{rodrigues2017k} in a comparative analysis on publicly available images. The results of MTree were inferior such that the limitations were addressed in \cite{ciurez2018improved}. As critical improvements, the MTree version from \cite{ciurez2018improved} uses off-line dataset preprocessing for finding the optimal number of clusters and adjusts the business logic of the clusterer in terms of division policy and distance metric between instances.   

The current proposed version of the MTree cluster represents a flexible parametrized version of the former one in terms of division policy, used distance, the method for finding and setting the number of clusters.

\subsection{Definitions and context}
The metric space \( M = (D, d) \) on a data domain \( D \) with the distance function \( d:D \times D \rightarrow \mathbb{R} \) postulates:

\begin{subequations}
    \begin{align}
        & Non \hspace{1ex} negativity: \forall x,y \in D, d(x,y) \geq 0\\
        & Symmetry: \forall x,y \in D, d(x,y) = d(y,x)    \\
        & Identity: \forall x,y \in D, x=y \Leftrightarrow d(y,x)=0 \\
        & Triangle \hspace{1ex} inequality: \forall x, y, z \in D, d(x,z) \leq d(x,y) + d (y,z)
    \end{align}
\end{subequations}

The conditions specified above are satisfied by most discrete or continuous distance (or similarity) metrics (or measures): Euclidean, Minkowski, Manhattan, quadratic form distance (i.e., colour histograms, weighted Euclidean distance), edit distance, Jaccard's coefficient or Hausdorff distance.
Building clusters of objects in metric spaces relies on the partitioning method and shape of the decision boundary that lays between two adjacent clusters. The partitioning method regards how a set of objects is split into two or more clusters taking into account specific optimization criteria such as the sum of squared errors (SSE) in case of simple k-means algorithm. Regarding the decision boundary, the two most common options are ball partitioning as in metric spaces and hyperplane partitioning.

As current implementation of the MTree algorithm represents a two-level ball decomposition generalization of the approach from \cite{uhlmann1991satisfying}. The limitations from \cite{uhlmann1991satisfying} regard choosing an arbitrary object as the pivot, using only binary splits around the median object, which implies previously sorting the objects and multilayered approach due to recursive construction. From the practical perspective of running a clustering process, these are substantial limitations because ordering may not always be possible, binary splitting may not be useful when dataset consists of many clusters and the notion of the cluster become unclear in a multilayered approach.

\textbf{Definition 1.} The designed MTree data structure is a two-level balanced tree able to index a set of objects into its leaves. After building the tree, the root contains a set of centroids and their corresponding covered radius. On the second level, the leaves represent the clusters containing objects whose distance is smaller or equal to the radius assigned to the corresponding centroid in the root.

The key features for the parametrized MTree implementation are:
\begin{enumerate}
    \item The possibility to process various object data types provided that actual input (i.e., image, document, etc.) is transformed into a multidimensional vector.  
    \item The possibility to set up a particular distance function between objects by direct usage of distance functions that are already available in Weka or by using a newly defined custom function.  
    \item The possibility to set up a particular division policy that will be used internally used as needed. Practically, the logic of the division policy is managed by a clustering algorithm. This feature needs to be accompanied by a parameter that controls the number of clusters in which a full leaf is divided. Available options are binary object partitioning (BOP), ternary object partitioning (TOP) or multi-object partitioning (POS).
    \item The possibility to set up a specific number of clusters in which the entire dataset will be partitioned. If the number of clusters is not known, the MTree will find an optimal number of clusters taking into account the other parameters that have been set.
    \item The possibility to compute at request various clustering quality metrics that would give a general idea on the quality of the clustering process. This feature is critical in benchmarking the MTree clustering results against results produced by other clustering algorithms.  
\end{enumerate}

\begin{table*}[h]
  \centering
  \caption{The structure of MTree node}
  \label{tab:structure_of_mtree}
  \begin{tabular}{||l|l||} 
    \hline
        \textbf{Field name} & \textbf{Description} \\ 
    \hline
        nrKeys & the number of objects actually stored in the node   \\ 
        isLeaf & flag representing the node type: root or leaf \\ 
        radix & the vector of distances covered by a centroid  \\ 
        route & the vector of node addresses to leaf nodes  \\ 
        instances & the objects from the leaf \\ 
        parent & the address of the parent node \\ 
    \hline
  \end{tabular}
\end{table*}

The MTree uses only one node data structure for \textit{root} node and for the leaves. In the \textit{root} node, the instances are represented by centroids and each element from \textit{radix} vector represents the covered radius for the corresponding centroid. In the same way, each element from \textit{route} vector is an address of the corresponding leaf node. The correspondence between centroids from \textit{root} node and covered radius and leaves is accomplished through their position in the vector. For example, the first element of \textit{instances} vector of the \textit{root} represents the first centroid with radius defined in the first element of the \textit{radix} vector. The first element of the \textit{route} vector represents the address of the leaf node that contains objects whose distance to the first centroid is smaller or equal with the covered radius.
In the case of leaf nodes, the \textit{instances} represent the data objects themselves. The \textit{isLeaf} flag is set by the business logic to value \textit{TRUE} such that \textit{radix} and \textit{route} vectors are set to \textit{null}. 

Before starting any computation needed for inserting a new object in the MTree, the algorithm checks if we are in a leaf and if the leaf has objects in it. If any of these conditions do not hold than insertion may not take place because insertion may be performed only in a leaf and further splitting may be taken into consideration only if the leaf has objects in it. Further, the leaf is evaluated for splitting parametrized by \textit{evaluatorOfK}, which is a function that determines the optimal number of clusters. This helper function takes as parameter the objects from \textit{treeNode} and outputs \textit{splitEval} as an evaluation of the splitting. If this also is valid, then the leaf node is split into the optimal number of clusters by using a parametrized \textit{divisionPolicy}. The \textit{insertNonFull} function is called to append a new object in the leaf when no splitting is necessary.

The two main ingredients of \textit{mTreeInsert} function are the evaluation of the optimal number of clusters from a leaf and the division policy used for splitting. The current implementation uses a function called \textit{voteK} that computes the optimal number of clusters in a similar way as \textit{NbClust} \cite{malika2014nbclust} package in R. The main difference is that \textit{NbClust} uses 30 indices while \textit{voteK} currently integrates only 8 indices: Davies-Bouldin, Dunn, Xi-Beni, Banfeld-Raftery, McClain-Rao, Ray-Turi, Calinski-Harabasz and PBM indices. The architectural design of the package allows the easy call of any method that given an input dataset can compute the optimal number of clusters.  

The second key ingredient of the \textit{mTreeInsert} function is the division policy. The default option for this parameter is the simple k-means algorithm, but any other strategy may be called as needed. Other options, besides calling particular clustering algorithms as a multi-object partitioning (MOP) strategy, is using binary space partitioning (BSP) or ternary object partitioning (TOP) by simply setting proper parametrized values.

If there is no need for node splitting than insertion reduces to appending the new object into that leaf and this is accomplished by calling \textit{insertNonFull} function. Intuitively, when a leaf is not full, we insert a new object; otherwise, we split the leaf. The critical difference from older versions or other approaches is that splitting is not called when the number of stored objects reaches a specific value, but is called when current objects exhibit the property that they are clustered and this is a motivation for splitting. 

Algorithm~\ref{alg:mtree_insert} summarizes the business logic for inserting a new object into an existing MTree leaf node.

\setlength{\intextsep}{10 pt}
\begin{algorithm*} 
\caption{mTreeInsert (MTree treeNode, Instance newObject)}
\label{alg:mtree_insert}
\begin{algorithmic} [1]
    \IF{\textit{treeNode} is leaf and has objects}
        \STATE \textbf{Set} clusteringEvaluator = getOptimalNrOfClusters (treeNode, \textit{evaluatorOfK}); 
    \ENDIF
    
    \IF{\textit{splitEval} is valid}
        \STATE nrOfClusters = clusterEval.getNumberOfClusters ();
        
        \IF{$nrOfClusters >$ 1}
            \STATE splitNode(treeNode, clusteringEvaluator);
        \ELSE
            \STATE  insertNonFull(treeNode, newObject);
        \ENDIF
    \ENDIF
\end{algorithmic}
\end{algorithm*}

The second key procedure is the one that performs the split of a leaf node as specified in the insertion algorithm. The main ingredient is represented by the \textit{clusteringEvaluator} setup, which allows breaking the leaf into clusters according to with specific division policy and a predetermined optimal number of clusters. The newly obtained clusters are added into a \textit{splitedClusters} vector and returned as output. The main improvement in the split procedure regards avoiding to split a leaf into a hard-coded number of clusters by using a determined optimal number of clusters and parametrizing for the division policy for running the effective split. Algorithm~\ref{alg:mTree_splitNode} summarizes the business logic for splitting.

\setlength{\intextsep}{10 pt}
\begin{algorithm*} 
\caption{mTreeSplitNode (MTree treeNode, ClusterEvaluation
clusteringEvaluator)}
\label{alg:mTree_splitNode}
\begin{algorithmic} [1]
    \STATE clusters = getClusters (treeNode, clusteringEvaluator);  
    \IF{size of clusters $>$ 0}
        \FOR{\textbf{each} cluster \textbf{in} clusters}    
            \STATE centroidInstance = chooseCenter(cluster);
            \STATE splitedCluster.addCentroid(centroidInstance.getCentroid());
            \STATE splitedCluster.setRadix(centroidInstance.getRadix());
            \STATE splitedClusters.add(splitedCluster);
        \ENDFOR
    \ENDIF    
    \STATE Return splitedClusters;
\end{algorithmic}
\end{algorithm*}

The bounding volumes of the MTree leaves are circles if objects are 2-dimensional or spheres if objects are 3-dimensional and Euclidean distance is being used. For n-dimensional spaces, the bounding volumes are hyperspheres, a generalization for a set of points equally distanced to a given point. This generalization is valid only for Euclidean distance, as for other distances, the bounding volume is the representative of a sphere for that particular vector space.

\subsection{MTree practical usage}
The MTree implementation is aimed for usage by client code in practical scenarios. Although the main usage scenario addresses the situation for which we know the true number of clusters, the clusterer may also be used in the situation when the data analyst specifies a particular number of clusters depending on the tackled task or in the situation when the number of clusters is not known or does not exist. 

In any of the situation mentioned above, the parameters that need to be set are the input dataset, the number of clusters, the distance metric, the evaluator of the number of clusters and the division policy algorithm. The main practical goal of the current version of the MTree clusterer is to verify that it correctly loads the data given specific parameters and creates a data model that validates the ground-truth model given in two publicly available datasets. Finally, the clustering validation metrics are verified against other clustering algorithms implemented in Weka workbench. 

One key aspect for correctly building the MTree from data regards the order in which the data objects are provided as input. As a general rule, any clustering algorithm is highly sensitive to the order in which data objects are taken into consideration in the clustering process. The seed mechanism is the general solution to clustering algorithms and is also used as a standard option in the MTree. For our case, the seed mechanism represents a random shuffle of the order in which the instances are added to the MTree.

A particular situation occurs when we do not know the right number of clusters. In this case, the adequate solution is to perform a preprocessing of the dataset to check clusterability and determine the correct number of clusters, if such a number exists. Besides the situation in which a certain number of clusters exist, we may be the situation in which the dataset has not a clear structure. This situation may mean two things: either, the dataset has several possible options as the actual number of clusters, or, we do not know the correct number of clusters. In the first situation, a domain knowledge person should take into consideration the particular data analysis task and decide for the correct number of clusters that fits the practical problem. In the latter situation, more extensive work needs to be done as a preprocessing step. 

As a general rule, when the dataset has no structure, then the first preprocessing steps should define the number of clusters as a task-dependent value. Then, the centroids should also be defined as representatives for each cluster considered by the domain knowledge person. Finally, the objects from the dataset are added to pertaining cluster only if a maximal threshold distance from the centroid is not exceeded. The objects that have almost equal distance from centroids are considered outliers and are not added to any cluster. In this way, the data analyst may obtain a clusterable dataset with a specific number of clusters. Having a clusterable dataset is a prerequisite for the MTree clustering algorithm as well as for any other algorithm. Therefore, if the dataset does not meet clusterability that building an MTree clusterer or any other clusterer will exhibit undefined behaviour.   

Finding the correct number of clusters by using MTree may be performed by running with various parameter settings in terms of the number of clusters and division policy in an attempt to obtain a clusterer whose validation parameters show that the right patterns have been discovered. In this use-case, the MTree data structure is built for finding whatever clusters are to be found.

\subsection{Complexity analysis}
The complexity analysis of building the MTree from data depends on the number of objects, number of clusters, method of finding the optimal number of clusters and number distance computations. The number of clusters from the data-set represents the number of splits that need to be performed while building the tree. The most critical operation is finding the optimal number of clusters, which is called after each object insertion. The number of distance computations is related to the number of clusters since distances from the newly inserted object to all the centroids from the root need to be computed for determining the appropriate leaf where the insertion should take place. The most time consuming function is  \textit{getOptimalNrOfClusters} function that is called whenever a new object is to be inserted. We have observed that for a reasonably small number of clusters and a large number of object that method \textit{getOptimalNrOfClusters} is used in triggering a split fewer times than the number of clusters. For example, once the number of leaves from MTree has been reached the true number of clusters than looking for the optimal number of clusters becomes useless, and further insertions will be performed in constant time just by determining the proper leaf where the new object needs to be inserted. 

As stated in \cite{edelsbrunner2012algorithms} the performance of building an MTree with \textit{n} objects is analogous to that of k-d trees, that is $O(n\log{}n)$ for worst-case scenario. Depending on the split method the time may increase to $O(n\log{}^2n)$ or $O(kn\log{}n)$ for \textit{k} dimensions. Still, the currently proposed method is highly sensitive to the order in which objects are being inserted, the seed selection and the particular parameters setup as well as all other clustering algorithms. 

The critical property of the MTree is that after correctly building the clusters, the operations of inserting, removing and querying may be performed in $O(\log{}n)$ time. These aspects are not tested by the current works and need to be further experimentally investigated in practical clustering tasks.

%
%       EXPERIMENTAL RESULTS
%
\section{Experimental results}

\subsection{Datasets description} 
Experimental results have been performed on two synthetic publicly available datasets from the clustering basic benchmark \cite{ClusteringDatasets}: \textit{Unbalance} \cite{rezaei2016set} and \textit{Dim2} \cite{karkkainen2007gradual}. \textit{Unbalance} is a synthetic 2-d dataset with 6500 points and 8 Gaussian clusters for which ground truth centroids and partitions are known. \textit{Dim2} is also a synthetic 2-d dataset with 1351 points and 9 Gaussian clusters. Figures \ref{Fig:unbalance_data} and \ref{Fig:dim2_data} present a plot of the raw input data. 


% \begin{comment}
%         \begin{figure} [!htb]
%         	\centering
%         	\begin{subfigure}{0.45\textwidth} % width of left subfigure
%         		\includegraphics[width=\textwidth]{figures/unbalance.png}
%         		\caption{Unbalance} % subcaption
%         	\end{subfigure}
%         	\vspace{1em} % here you can insert horizontal or vertical space
%         	\begin{subfigure}{0.45\textwidth} % width of right subfigure
%         		\includegraphics[width=\textwidth]{figures/dim2.png}
%         		\caption{Dim2} % subcaption
%         	\end{subfigure}
%         	\caption{\textit{Unbalance} and \textit{Dim2} datasets} 
%         \end{figure}
% \end{comment}

\begin{figure}[!htb]\centering
   \begin{minipage}{0.4\textwidth} \color{white} 
     \frame{\includegraphics[width=\linewidth]{figures/unbalance.png}} \centering  
     \caption{Unbalance dataset}\label{Fig:unbalance_data}
   \end{minipage}
   \begin{minipage} {0.4\textwidth} \color{white} 
     \frame{\includegraphics[width=.8\linewidth]{figures/dim2.png}} \centering
     \caption{Dim2 dataset}\label{Fig:dim2_data}
   \end{minipage}
\end{figure}

We have chosen two synthetic datasets for which the ground truth centroids and partitions are known because they are suitable for comparing clustering results obtained by MTree algorithm against other ones implemented in Weka workbench.

Finally, we have tested the MTree on \textit{Wine} and \textit{Iris} classical datasets from UCI Machine Learning Repository \cite{blake1998uci}. These real-world datasets were chosen because they may be successfully used in clustering tasks as they are labelled, and classical unsupervised training may correctly determine the classes. 

\subsection{MTree package description} 
MTree is implemented in Java and is aimed to be executed within Weka 3.8 workbench by using the \textit{Package manager} tool. The MTree package is based on three classes \textit{Node}, \textit{MTreeBean} and \textit{MTree}  along with other three helper classes. Figure \ref{fig:uml_class_diagram_mtree} shows the software architecture the MTree package as an UML class diagram .

\begin{figure*}
    \centering
    \includegraphics[width=\textwidth]{figures/MtreeUMLv4.png}  
    \caption{UML class diagram for MTree package}
    \label{fig:uml_class_diagram_mtree}
\end{figure*}

The class \textit{Node} represents a blueprint for a cluster of instances and the \textit{MTreeBean} class contains the root of the MTree. The most important class is \textit{MTree}, which extends \textit{RandomizableClusterer}, which is an abstract class whose direct subclasses are Canopy, Cobweb, FarthestFirst and SimpleKMeans. Further, by implementing the \textit{NumberOfClustersRequestable} and other interfaces, the MTree gets the possibility to be parametrized similarly as other clustering algorithms are in Weka. 

The main goal was to obtain a clusterer that may be parametrizable in the same way as already existing clusterers based on interfaces that are already defined in Weka but also offering the possibility of defining new interfaces specific for parameters needed by MTree algorithm. In this way, the newly obtained MTree can be easily parametrized in the usage of the command line interface or Weka GUI interface.  

\subsection{Sample MTree usage} 
The MTree can be used in three ways. The current implementation provides flexibility for running full experimental runs and benchmarking the performance of an MTree parameter configuration against new proposals or already existing Weka clustering algorithms.   
\begin{itemize}
    \item \textit{Basic mode, through command line}. This mode allows executing the MTree on any machine that has JVM 1.8 and \textit{weka.jar} version 3.8.3. Figure \ref{fig:command_line_execution_MTree} presents a sample command line execution of the MTree algorithm. This approach is commonly used when batch execution is needed just one time for building the clusters and serializing the obtained model (i.e., the distribution of objects into clusters) to persistent storage (i.e., csv, xml, etc.) for later usage is rather difficult. 
    
    \begin{figure*}
    	\centering
    	\caption{Command line execution of MTree}
      	\label{fig:command_line_execution_MTree}
      	\includegraphics[width=\textwidth]{figures/weka_cli_execution_MTree.png} 
    \end{figure*}
    
    The available options when running MTree in command line interface are further presented. \textbf{\textit{N}} represents the number of clusters. If we want MTree to decide for itself the number of clusters this option must be set to value -1. \textbf{\textit{init}} option may be used for setting the initialization method. \textbf{\textit{I}} option is for setting the maximum number of iterations, \textbf{\textit{O}} for preserving the order of instances, \textbf{\textit{S}} for setting the number of seeds, \textbf{\textit{d}} for setting the distance metric, \textbf{\textit{findN}} for setting the method for finding the optimal number of clusters and \textbf{\textit{splitPolicy}} for setting the method used as splitting policy. Current implementation may use as splitting policy Canopy, Simple k-means, CobWeb, FarthestFirst or HierarchicalClusterer clusterers from Weka.\\

    \item \textit{Using the Weka GUI}. This mode is the most user-friendly as the MTree may be used from Weka GUI as any other clustering algorithm. As the MTree package is in the list of official packages, it needs to be installed before usage. Installing the MTree package in Weka is a straightforward procedure as the \textit{MTree.zip} archive is publicly available in SourceForge \cite{MTree_Clusterer_weka_package} and the link to the package is available in the list of official packages within the Weka package manager tool.
    
    \begin{figure*}
    	\centering
    	\caption{Execution of MTree in Weka GUI}
      	\label{fig:weka_gui_execution_MTree}
      	\includegraphics[width=.8\textwidth]{figures/weka_gui_execution_MTree.png}  
    \end{figure*}

    \item \textit{Programmatic way}. The most versatile usage of the MTree is programmatically. This approach allows setting up the parameters at runtime as well as having a ready-to-use in memory MTree object that is ready for querying. This approach allows the usage of the cluster as business logic on a server side in complex applications where client code is performing various queries. Sample code for building the MTree from data is publicly available in \cite{ciurez2019mtreeclientcode}.      
\end{itemize}

\subsection{Sample runs on Unbalance and Dim2 synthetic datasets} 
The newly released parametrized MTree implementation has been tested against two publicly available synthetic datasets: \textit{Unbalance} and \textit{Dim2}. The client code that calls the MTree package is publicly available at \cite{ciurez2019mtreeclientcode}, as further presented experimental results were obtained by programmatically running the MTree implementation.

\begin{figure*} 
	\centering
	\begin{subfigure}{0.45\textwidth} % width of left subfigure
		\includegraphics[width=\textwidth]{figures/1_MT_U.png}
		\caption{MTree results} % subcaption
	\end{subfigure}
	\vspace{1em} % here you can insert horizontal or vertical space
	\begin{subfigure}{0.45\textwidth} % width of right subfigure
		\includegraphics[width=\textwidth]{figures/2_canopy_U.png}
		\caption{Canopy results} % subcaption
	\end{subfigure}
	
	\begin{subfigure}{0.45\textwidth} 
		\includegraphics[width=\textwidth]{figures/3_EM_U.png}
		\caption{EM results} 
	\end{subfigure}
	\vspace{1em} 
	\begin{subfigure}{0.45\textwidth} 
		\includegraphics[width=\textwidth]{figures/4_FF_U.png}
		\caption{FF results} 
	\end{subfigure}
	
	\begin{subfigure}{0.45\textwidth} 
		\includegraphics[width=\textwidth]{figures/5_HC_U.png}
		\caption{HC results} 
	\end{subfigure}
	\vspace{1em} 
	\begin{subfigure}{0.45\textwidth} 
		\includegraphics[width=\textwidth]{figures/6_SKM_U.png}
		\caption{SKM results} 
	\end{subfigure}
	
	\caption{Clustering results on \textit{Unbalance} dataset} % caption for whole figure
	\label{unbalance_dataset_results}
\end{figure*}

\begin{figure*} 
	\centering
	\begin{subfigure}{0.45\textwidth} 
		\includegraphics[width=\textwidth]{figures/1_MT_D2.png}
		\caption{MTree results} 
	\end{subfigure}
	\vspace{1em} 
	\begin{subfigure}{0.45\textwidth} 
		\includegraphics[width=\textwidth]{figures/2_canopy_D2.png}
		\caption{Canopy results} 
	\end{subfigure}
	
	\begin{subfigure}{0.45\textwidth} 
		\includegraphics[width=\textwidth]{figures/3_EM_D2.png}
		\caption{EM results} 
	\end{subfigure}
	\vspace{1em} 
	\begin{subfigure}{0.45\textwidth} 
		\includegraphics[width=\textwidth]{figures/4_FF_D2.png}
		\caption{FF results} 
	\end{subfigure}
	
	\begin{subfigure}{0.45\textwidth} 
		\includegraphics[width=\textwidth]{figures/5_HC_D2.png}
		\caption{HC results} 
	\end{subfigure}
	\vspace{1em} 
	\begin{subfigure}{0.45\textwidth} 
		\includegraphics[width=\textwidth]{figures/6_SKM_D2.png}
		\caption{SKM results} 
	\end{subfigure}
	
	\caption{Clustering results on \textit{Dim2} dataset} 
	\label{dim2_dataset_results}
\end{figure*}

\begin{table*}
    \centering
    \caption{Running times statistics (measured in seconds)}
    \label{tab:running_time_statistics}
    \begin{tabular}{||l|l|l||} 
        \hline
            \textbf{Algorithm} &  \textbf{Unbalance dataset} & \textbf{Dim2 dataset}\\  
        \hline 
            MTree   & 0.3 [per seed]    & 0.06 [per seed]\\ 
            Canopy  & 0.01  & 0.1    \\ 
            EM   & 8.21 [per tuned seed]    & 0.55 [per tuned seed]   \\ 
            FF   & 0.01 [per seed]  & 0.01 [per seed]  \\ 
            HC   & 605.42   & 4.11  \\ 
            SKM   & 0.06 [per seed] & 0.01 [per seed]  \\ 
        \hline
    \end{tabular}
\end{table*}

\begin{table*}
    \centering
    \caption{Performance results on real world datasets}
    \label{tab:performance_results_real_world_datasets}
    \begin{tabular}{||l|l|l||} 
        \hline
            \textbf{Algorithm} &  \textbf{Accuracy Wine} & \textbf{Accuracy Iris}\\  
        \hline 
            MTree+Canopy & 0.94382 & 0.89261 \\
            MTree+cKMs   & 0.92134 & 0.89261 \\
            MTree+FF     & 0.93258 & 0.88590 \\
            MTree+HC     & 0.89887 & 0.89261 \\
            KMeans       & 0.93258 & 0.88590 \\
        \hline
    \end{tabular}
\end{table*}

Figures \ref{unbalance_dataset_results} and \ref{dim2_dataset_results} present the experimental results of running the MTree clusters along other five clusterers implemented in Weka workbench: Canopy, EM (expectation-maximization), FF (Farthest First), HC (Hierarchical Clustering) and SKM (Simple KMeans).

As figure \ref{unbalance_dataset_results} clearly shows, the MTree correctly determines the clusters by using 100 seeds and Canopy for split policy. As a general rule, the clustering result exhibits undefined behaviour regarding the number of seeds, such that correct results may be obtained sometimes for only 10 seeds and sometimes for 1000 seeds. Here is a summary of the experimental results of the other five algorithms:

\begin{itemize}
    \item \textit{Canopy} algorithm fails to determine the correct number of clusters and the found distribution into clusters is wrong.
    \item \textit{EM} algorithm fails to determine the correct number of clusters although in many situations it is used for this task as it does not require the value of K. The obtained clusters are reasonable fine with two exceptions: cluster 0 puts together three real clusters and cluster 1 puts together two real clusters.
    \item \textit{FF} algorithm correctly determines the number of clusters but misses to determine two of them correctly: cluster 0 puts together two real clusters and cluster 2 is composed of objects belonging to two distinct clusters. 
    \item \textit{HC} algorithm correctly solves the task. 
    \item \textit{SKM} algorithm correctly solves the task after finetuning the parameters: 100 seeds, usage of kmeans++ \cite{arthur2007k} for seed optimization and maximum 10,000 iterations. 
\end{itemize}

As figure \ref{dim2_dataset_results} clearly shows, the MTree correctly determines the clusters on a more difficult task by using only 10 seeds. The other investigated algorithms provide the following results:
\begin{itemize}
    \item \textit{Canopy} algorithm fails to determine the correct number of clusters and the found distribution into clusters is wrong, as it puts together in a cluster objects from two clusters. 
    \item \textit{EM} algorithm correctly determines the clusters.
    \item \textit{FF} algorithm fails to determine the correct number of clusters and misses to determine one of them correctly. The result shows that objects from one real cluster are split between two real clusters.   
    \item \textit{HC} fails to determine the correct number of clusters and reports one found cluster as a join between two real clusters. 
    \item \textit{SKM} algorithm correctly solves the task after fine tuning the parameters: 10 seeds, usage of kmeans++ \cite{arthur2007k} for seed optimization and maximum 10,000 iterations.
\end{itemize}

Experimental results show that the first K instances have the most significant impact over the final result, where K is the number of clusters. Thus, the current implementation uses kmeans++ \cite{arthur2007k} seed optimization, so the first K instances that are added to the MTree are a rather sparse one from another.



Table \ref{tab:running_time_statistics} summarizes the running time statistics for all six algorithms on both datasets. In the case of EM algorithm, each tuned seed has been obtained by more iterations, and more k-means runs, a fact that explains the more significant running time. HC and Canopy do not have seeds and Canopy's poor results on both datasets were obtained regardless of the configuration parameters. The number of seeds for the algorithms that correctly solved the \textit{dim2} dataset has been set to 10.

Finally, the SSE (sum of squared error), as well as the assignment of objects, are correctly computed for MTree as they compute to the same values as SKM of 4.2471 and 0.3367 for \textit{unbalance} and \textit{dim2} datasets, respectively. Therefore, the clusters produced by the MTree are valid and represent the real ones from the datasets and SSE represents a good optimization metric for these datasets. 


\subsection{Sample runs on Iris and Wine real-world datasets} 
Wine data was normalized and then MTree was used on all 13 features. The algorithm was run on 100 seeds and the best result was targeting to be with the best (smallest) SSE. As can be seen from the table, smaller SSE does not always provide the best accuracy, with a SSE value of 66 against 68 but an accuracy of 89 against 94.This suggests that a different cluster quality metrics may be able to improve the performance of the proposed algorithm. KMeans run on 100 seeds obtains 93\% accuracy or 12 wrong predictions.

Iris data was normalized and MTree used on all 4 features. As on the previous dataset, the algorithm was run on 100 seeds and best SSE was targeted. It is interesting to notice that different SSE provide the same accuracy, it seems that the algorithm converged with 16 wrong predictions being its best. 
MTree+cobweb is not able to cluster the data. On the same data, KMeans run on 100 seeds obtains 88\% accuracy or 17 wrong predictions.

Table \ref{tab:performance_results_real_world_datasets} presents accuracy results of MTree parametrized by various splitting algorithms (i.e., Canopy, KMeans, Farthest First and Hierarchical clustering) against baseline KMeans algorithm. Experimental results show the MTree clustering algorithm correctly finds groups at least as good as simple KMeans algorithm. 



%
%       CONCLUSIONS AND FUTURE WORK
%
\section{Conclusions and future work}
This paper presents an improved parametrized MTree clusters for Weka workbench. The experimental results show that MTree correctly solves two synthetic datasets for which the correct structure (i.e., number of clusters, centroids and distribution) is known. More, five other clustering algorithms implemented in Weka are outperformed in various situations due to that fact that they do not solve the clustering task correctly or need intensive tuning for solving it.
    
Still, the current approach is used only for \textit{sanity check} of the clustering capabilities of the MTree implementation, rather than solving a particular clustering task on a real dataset. The implementation is Java-based and is available as open source Weka package. The experimental results are correct and promising such that further development under Weka offers the possibility of proper benchmarking of further clustering tasks that may be taken into consideration.  

The main contributions are summarized as follows:

\begin{enumerate}
    \item An updated parametrized version of the MTree package is presented. The parametrization mainly regards used distance metric, the method for finding and setting the number of clusters and the division policy. The data structure can load various object types after being properly processed as well as providing validation insights.   
    \item The proposed software architecture of the MTree enables parameterization through easy integration of other internal algorithmic strategies that perform key tasks within the business logic.
    \item The implementation of the MTreeis available as an open source package in Weka workbench. This approach gives the opportunity for further usage and benchmarking against other clustering algorithms.
    \item The experiments demonstrate that the proposed approach outperforms current clustering algorithms on two datasets.
\end{enumerate}

Future works may take into consideration extending the \textit{voteK} algorithm as a Java implementation of the already existing R package NbClust. Extending \textit{voteK} should take into consideration the available clustering quality indices and parametrization capabilities. In terms of internal business logic, MTree may try different approaches regarding the order in which objects are processed when building the tree. One option is to cluster the outlier objects later in the process.   

As the most expensive operations are finding the optimal number of clusters and splitting, one option is trying to predict how the insertion of an object will impact the tree in terms of triggering a split. Checking for the optimal number of clusters should be performed only when an insert is highly to determine a split, as most inserts do not require a split, especially when the dataset has a clear structure.

MTree currently implements range query and kNN query. These implementations should be further tested in practical real data scenarios. Other tasks in which MTree may be also used are outlier detection and finding the correct number of clusters in a dataset. Finally, MTree algorithm may be further tested for finding patterns in data in the situation when internal structure is not known. 

\printbibliography
\end{document}