Luis C S Afonso

Clayton R Pereira
email: clayton.pereira@unesp.br

Silke A T Weber

Christian Hook
email: christian.hook@hs-regensburg.de

Alexandre X Falcão
email: afalcao@ic.unicamp.br

João P Papa
email: joao.papa@unesp.br

Hierarchical Learning Using Deep Optimum-Path Forest

Keywords: Parkinson's disease, Optimum-Path Forest, Handwriting Dynamics, Hierarchical Representation

Bag-of-Visual Words (BoVW) and deep learning techniques have been widely used in several domains, which include computer-assisted medical diagnoses. In this work, we are interested in developing tools for the automatic identification of Parkinson's disease using machine learning and the concept of BoVW. The proposed approach concerns a hierarchical-based learning technique to design visual dictionaries through the Deep Optimum-Path Forest classifier. The proposed method was evaluated in six datasets derived from data collected from individuals when performing handwriting exams. Experimental results showed the potential of the technique, with robust achievements.

Introduction

Image and signal classification problems have been widely studied in the past decades by machine learning and computer vision research communities. More recently, a considerable effort is done towards deep learning (DL) techniques recently. Despite the fact that DL-driven approaches are known to be quite useful in generalizing over a number of problems, they still can not deal with some simple problems as well [START_REF] Nye | Are efficient deep representations learnable?[END_REF]. Also, specific neural architectures need to be designed to cope with signal classification problems since most of the models available in the literature are developed to handle image-based applications only.

The well-known Bag-of-Visual-Words (BoVW) [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF] paradigm has been consistently employed and enhanced over the years to address both image-and signal-based classification problems. In a nutshell, the idea consists in extracting information (e.g., visual words/key points/descriptors) from the data for further using them to compose a dictionary (i.e., bag) that can be employed to compute new representations for a given data. Applications in medical data vary from X-ray categorization to histopathology image classification [START_REF] Avni | X-ray categorization and retrieval on the organ and pathology level, using patch-based visual words[END_REF][START_REF] Caicedo | Histopathology image classification using bag of features and kernel functions[END_REF][START_REF] Souza | Barrett's esophagus identification using optimum-path forest[END_REF], among others.

Computer-assisted Parkinson's disease (PD) identification is another research area that can benefit from automated diagnosis and the BoVW paradigm. Such illness is known to be neurodegenerative, it has no cure, and its main symptoms include the freezing of gate, tremors, and speech alterations, to name a few. In this context, a considerable number of works that deal with automated PD diagnosis can be referred in the literature. Spadotto et al. [START_REF] Spadotto | Parkinson's disease identification through optimum-path forest[END_REF], for instance, introduced the Optimum-Path Forest (OPF) [START_REF] Papa | Supervised pattern classification based on optimum-path forest[END_REF][START_REF] Papa | Efficient supervised optimum-path forest classification for large datasets[END_REF][START_REF] Papa | Optimum-path forest based on k-connectivity: Theory and applications[END_REF] for PD identification from speech signals. Later on, they employed evolutionary optimization techniques to select the most relevant features to deal with the same problem [START_REF] Spadotto | Improving parkinson's disease identification through evolutionary-based feature selection[END_REF]. Sama et al. [START_REF] Samà | Determining the optimal features in freezing of gait detection through a single waist accelerometer in home environments[END_REF] and Bächlin et al. [START_REF] Bächlin | Wearable assistant for parkinson's disease patients with the freezing of gait symptom[END_REF] explored wearable accelerometers to detect the freezing of gate and to provide assistance as soon as the condition is detected.

Rigas et al. [START_REF] Rigas | Assessment of tremor activity in the parkinson's disease using a set of wearable sensors[END_REF] investigated an automated method that estimates the type and severity of tremors based on data acquired from accelerometers attached to specific positions at a patient's body. The estimations are used to assess both resting and action tremors.

Other works used images to cope with PD recognition automatically. Pereira et al. [START_REF] Pereira | A new computer vision-based approach to aid the diagnosis of parkinson's disease[END_REF] proposed to extract features from handwriting exams that were further digitized to fulfill the aims of the work. They used the HandPD dataset1 , which comprises exams performed by healthy individuals and PD patients to detect subtle tremors when drawing spirals and meanders on a piece of paper.

Since the exams were conducted using a pen equipped with sensors2 , the same group of authors further proposed to use the signals obtained from the pen as a means to perform automatic PD recognition [START_REF] Pereira | Deep learning-aided parkinson's disease diagnosis from handwritten dynamics[END_REF]. Very recently, Afonso et al. [START_REF] Afonso | Parkinson's disease identification using deep recurrence plots[END_REF] introduced the concept of "deep recurrence plots" for the identification of Parkinson's disease, where the idea is to employ recurrence plots [START_REF] Eckmann | Recurrence plots of dynamical systems[END_REF] to model the time dependency of the signals acquired during the exam. Afonso et al. [START_REF] Afonso | Parkinson's disease identification through deep optimum-path forest clustering[END_REF] also proposed a BoVW-based model to learn representations from signals (i.e., the same ones used in the works mentioned earlier) to be further used to cope with the problem of Parkinson's disease identification. The proposed approach first extracts key points (descriptors) from the signal, which are then clustered using the unsupervised OPF technique [START_REF] Rocha | Data clustering as an optimum-path forest problem with applications in image analysis[END_REF]. The idea behind the clustering is to select only the most informative ones that will compose the final dictionary. The results showed that OPF could build more informative dictionaries than other clustering algorithms. The OPF is a framework to the design of classifiers based on graph partition, where each node stands for a dataset sample, and an adjacency relation connects them for the further application of a reward-competition approach that ends up partitioning the dataset into optimum-path trees (OPTs). Such OPTs can be either unlabeled clusters (unsupervised problems) or labeled trees (supervised and semi-supervised [START_REF] Amorim | Improving semisupervised learning through optimum connectivity[END_REF] problems), and their roots stand for the so-called "prototypes".

In this paper, we extend the work of Afonso et al. [START_REF] Afonso | Parkinson's disease identification through deep optimum-path forest clustering[END_REF] by proposing a hierarchical-based learning methodology to design visual dictionaries. The proposed approach makes use of the Deep OPF classifier [START_REF] Afonso | Learning to classify seismic images with deep optimum-path forest[END_REF], which aims at performing different levels of clustering to learn and encode distinct information at each phase. We showed results that outperformed the ones obtained by Afonso et al. [START_REF] Afonso | Parkinson's disease identification through deep optimum-path forest clustering[END_REF] in the context of computer-assisted Parkinson's disease identification using signals derived from handwriting exams.

The remainder of this paper is organized as follows. Section 2 presents a theoretical background about the OPF and Deep OPF. Sections 3 and 4 describe how deep representations are learned through Deep OPF and the proposed approach, respectively. Section 5 presents the experimental results, and Section 6 states conclusions and future work.

Optimum-Path Forest Clustering

The fundamental problem in unsupervised learning is to identify clusters in an unlabeled dataset Z, such that samples from the same cluster should share some level of similarity. Many methods were proposed where the learning problem is addressed with different perspectives, such as data clustering and density estimation, just to mention a few [START_REF] Schwenker | Pattern classification and clustering: A review of partially supervised learning approaches[END_REF]. The Optimum-Path Forest handles unsupervised learning under a data clustering perspective through graph partitioning [START_REF] Rocha | Data clustering as an optimum-path forest problem with applications in image analysis[END_REF]. Briefly, the partition task is performed as a competitive-based process ruled by a set of key samples s ∈ Z called prototypes that conquer the remaining samples offering them optimum-cost paths. As a result, it is obtained a collection of trees (forest) rooted at each prototype, in which each tree represents a different cluster.

Suppose that a graph (Z, A k ) can be derived from Z through a k-nearest neighbors adjacency relation A k . Each n-dimensional sample x ∈ Z is represented as a graph node, and the connection (edge) between two nodes s and t is weighted by some distance or similarity metric d(s, t) based on their feature vectors. Also, each node s is weighted by a probability density function (pdf) defined as follows:

ρ(s) = 1 √ 2πσ 2 |A(s)| ∀t∈A(s) exp -d 2 (s, t) 2σ 2 , (1)
in which σ =

d f 3 ,
f ( t ) =    ρ(t) if t ∈ S ρ(t) -δ otherwise f ( π s • s, t ) = min{f (π s ), ρ(t)}, (2)
for δ = min ∀(s,t)∈A k |ρ(t) =ρ(s) |ρ(t)-ρ(s)|.
Notice that high values of delta reduce the number of maxima. In summary, the OPF algorithm maximizes f (π t ) such that the optimum paths form an optimum-path forest, i.e., a predecessor map P with no cycles that assigns to each sample t / ∈ S its predecessor P (t) in the optimum path from S or a marker nil when t ∈ S.

Deep Optimum-Path Forest

The OPF has the very interesting characteristic to identify clusters on-thefly, which is very useful for applications where the number of groups is unknown.

However, the absence of an OPF-based approach capable of computing a specific number of clusters becomes also a bottleneck. One solution is to play with the parameter k max by setting different values until the desired number of clusters is reached. Besides costly, this operation does not guarantee such condition is satisfied.

Based on hierarchical clustering, Afonso et al. [START_REF] Afonso | Learning to classify seismic images with deep optimum-path forest[END_REF] proposed a multi-layered OPF-based clustering algorithm. The main idea is to build a model comprised of a user-defined number of layers to obtain the desired number of clusters in the last layer. In their method, each layer is responsible for computing an optimumpath forest. The first layer takes as input the original dataset and clusters it following the OPF algorithm. The roots (prototypes) from the resulting forest are used as input by the following layer. The process is repeated until the last layer is reached. The usage of prototypes as the most representatives samples is supported by the studies of Castelo and Calderón-Ruiz [START_REF] Castelo-Fernández | Automatic video summarization using the optimum-path forest unsupervised classifier[END_REF] and Afonso et al. [START_REF] Afonso | Automatic visual dictionary generation through optimum-path forest clustering[END_REF]. Prototypes are located in the regions of highest density and, therefore, are suitable to represent the samples of its cluster [START_REF] Rosa | On the training of artificial neural networks with radial basis function using optimum-path forest clustering[END_REF].

Let S i be the set of prototypes at layer L i , i = 1, 2, . . . , l, in which l stands for the number of layers. Since each root will be the maximum of a pdf (Equation 1),

we have a set of samples that fall in the same optimum-path tree and are represented by the very same prototype (root of that tree) in the next layer.

In summary, the higher the number of layers, the less prototypes (clusters) one

shall have, i.e., |S 1 | < |S 2 | < . . . < |S l | < . . . ≤ 1.
Therefore, at layer l, one shall find only one cluster when l → ∞. Figure 1 displays the OPF-based architecture for deep-driven feature space representation, hereinafter called dOPF.

In the example, the layer L 1 computed four clusters, i.e., optimum-path trees, rooted at the black-filled nodes (prototypes). The resulting set of prototypes S 1 is used as input by the following layer L 2 . As one can observe at layer L 2 , a few samples become prototypes once more, resulting in the set S 2 . The In the context of Bag-of-Visual Words using dOPF, the final bag could be a coarser model if only the outcome of the last layer was used to compose it (i.e., only the prototypes of the last layer comprise the bag), as proposed by Afonso et al. [START_REF] Afonso | Learning to classify seismic images with deep optimum-path forest[END_REF]. However, an enriched model could be accomplished by adding information computed by the intermediate layers as well. As a comparison, the idea of using intermediate representations would be similar to using the features learned by the many hidden layers of a deep-learning model. Each layer can learn more complex features and, therefore, more robust representations.

As mentioned earlier, we propose to extend the work of Afonso et al. [START_REF] Afonso | Parkinson's disease identification through deep optimum-path forest clustering[END_REF] by employing hierarchical learning in the context of BoVW, hereinafter called hOPF (hierarchical OPF). The proposed approach will provide a more complex and more robust dictionary, being such representation the collection of selected visual words computed by all layers. Figure 2 illustrates both dictionary learning methods, i.e., dOPF and hOPF. Although dOPF provides a simpler and coarser representation by using only the features learned in the last layer, hOPF outputs a more complex and robust representation that stands for the concatenation of features learned by all layers.

In the context of BoVW, the resulting dictionary generated by hOPF will be of

size |S 1 | + |S 2 | + . . . + |S l |.

Proposed Approach

This section describes the steps employed in the assessment of dOPF and hOPF as visual dictionary learning methods for BoVW in the context of automatic Parkinson's disease identification, as illustrated in Figure 3

Data acquisition

The experimental data were collected from a series of tasks performed by individuals using a smart pen. The tasks exercise different hand movements that enable to capture the handwriting dynamics for further analysis. Furthermore, the exercises were elaborated in such way that are supposed not to be trivial to PD patients. All hand motion is captured by the smart pen that contains sensors that provide information on finger grip, the axial pressure of ink refill, tilt and acceleration in the x, y, and z directions.

Figure 4 illustrates the set of six tasks employed to evaluate the hand movements and to support the detection of anomalies. The set of six tasks stands for a sample, and an individual may have more than one sample assigned to it (i.e., the individual had more than on appointment). In the first task (exam (a) in Figure 4), the individual is asked to draw a circle 12 times continuously.

In the second task, the individual performs the circle-drawing movement (i.e., on the air) 12 times continuously (exam (b) in Figure 4). The third and fourth tasks also concern drawing activities. In the exam (c) in Figure 4, four spirals are drawn over a guideline from the inner to the outer part. The exam (d) in windows (i.e., one sliding window applied to each signal), as depicted in Figure 5.

Notice that all sliding windows comprise the same portion of time (i.e., the same initial and final times) as they go through the signals and the DWT is computed independently to each window. Moreover, the window length and shifting are user-defined. The experiments used windows of 150 ms of length and a stride of 100 ms, which showed the best results when compared with a window of size 100 ms and stride of 50 ms, and a window of size 200 ms and stride of 150 ms. Moreover, each segment is represented by a descriptor, and the longer is the signal, the higher will be the number of descriptors representing the input signal.

Dictionary formulation

The dictionary is formulated in a straightforward way by selecting the most representative "words" (descriptors) among the set computed in the previous step, and it is further used to compute a new sample representation. The most representative words are usually selected by a clustering algorithm where each centroid becomes a "word" of the dictionary. Therefore, the dictionary size is defined by the number of clusters. Since it has some impact on the accuracy rate, it is common the use of different sizes for the dictionary to balance the computational cost and accuracy rate. As mentioned in Section 2.1, the prototypes are very suitable to represent the samples of their trees (i.e., prototypes are equivalent to centroids of a cluster), thus being good representations to compose the dictionaries. This work employs the Optimum-Path Forest clustering algorithm to select the most representative words, i.e., the prototypes.

The new representation

A signal can be represented by its set of descriptors, which can range from dozens to thousands (i.e., a descriptor can be computed for each segment of the original signal, and the number of segments varies according to its length and stride). However, a few of these descriptors might be variations of another one or only represent noisy information. Moreover, machine learning techniques cannot be directly applied to the sets of descriptors since their dimension is not the same to all signals. Therefore, quantization is performed so that signals can be mapped into the same feature space. The outcome of the process is a histogram of length equals to the size of the previously formulated dictionary, where each bin stores the frequency of its closest word (descriptor) in the input signal. Finally, any machine learning technique can be applied for classification purposes using the histograms as input.

Experiments and results

In this section, we provide details concerning the experiments carried out on the assessment of deep-based dictionaries in the context of automatic Parkinson's disease identification. The experiments were divided into two parts: (i) the first one evaluated and compared dOPF-based dictionaries against the traditional OPF-based bags and the traditional BoVW method that computes the bags using the well-known k-means (Section 5.1); and (ii) the second part provides a comparison of the proposed approach (i.e., hOPF) with the method presented in the work of Afonso et al. [START_REF] Afonso | Learning to classify seismic images with deep optimum-path forest[END_REF] (Section 5.2). Additionally, the second section of experiments includes the hOPF performance evaluation using compressed versions of the representations learned. For that purpose, we applied the Restricted Boltzmann Machine (RBM) [START_REF] Hinton | Training products of experts by minimizing contrastive divergence[END_REF] to provide different compression levels. Notice that both experiments used data collected from 66 exams (35 healthy individuals and 31 PD patients), and the output of the protocol discussed in the previous section results in six different datasets, one for each task. The following sections describe the particularities of each experiment and the results using the proposed methodology.

Single-scale deep-based representations

This experiment aimed at evaluating the clustering quality of dOPF, k- to allow a fair comparison. Regarding the OPF algorithm, the values for k max were empirically set as 2, 500 for the Spiral and Meander datasets, and as 1, 500

for the remaining datasets. The clustering quality was assessed under a hold-out procedure with 15 runs, being the training and testing sets randomly partitioned in each new run and always with 50% of the dataset each. The classification step employs three classifiers for comparison purposes: Bayesian Classifier (BC) 6 , supervised OPF (sOPF) 7 and SVM using a Radial Basis Function (RBF) kernel with fine-tunned parameters (SVM-RBF) [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF].

Tables 2a-2f present the mean recognition rates concerning all six exams, being the accuracy computed according to Papa et al. [START_REF] Papa | Supervised pattern classification based on optimum-path forest[END_REF], which considers unbalanced datasets. The best results (i.e., bold values) are defined according to the Wilcoxon signed-rank [START_REF] Wilcoxon | Individual comparisons by ranking methods[END_REF] with a significance of 0.05, which pointed out the best ones for each exam. Further, we also considered the best among all exams as the underlined ones.

The statistical evaluation pointed out [OPF, SVM-RBF] and [k-means, BC] as the best pairs of [dictionary learner, classifier] with accuracies near to 81% and 83%, respectively. Comparing that recognition rates against some previous works [START_REF] Pereira | A new computer vision-based approach to aid the diagnosis of parkinson's disease[END_REF], dOPF showed significant gains, ranging from 10% to 30%. Concerning the best accuracies regarding each exam, dOPF obtained very much suitable results, being more accurate than naïve OPF in most cases. Supervised OPF obtained good results as well, but SVM-RBF achieved the best recognition rates in a few more situations. Additionally, we also evaluated the accuracy per class for all situations, as presented in Tables 345678, whose best results are also highlighted considering the Wilcoxon signed-rank. The best results for each class are in bold, and the best among all datasets is underlined.

Actually, the main improvement concerns the accuracy for the identification of healthy individuals, since Pereira et al. [START_REF] Pereira | Deep learning-aided parkinson's disease diagnosis from handwritten dynamics[END_REF] obtained recognition rates nearly to 50% over the Meander and Spirals datasets for the control class. The dOPF increased not only the global accuracy with respect to the work by Pereira et al. [START_REF] Pereira | Deep learning-aided parkinson's disease diagnosis from handwritten dynamics[END_REF], but also the specificity and sensitivity for most of the cases. Also, Circ-A dataset provided two out of the five best results, thus showing as a good alternative for the Parkinson's Disease identification. Table 9 presents the mean computational load required by each technique 320 for dictionary learning. Notice the computational burden for dOPF considers the four layers. In this context, k-means figured as the fastest one due to its simplicity. If one considers dOPF and OPF only, we can observe the former is about 78 times faster in Circ-B dataset, which is quite effective. The lowest gains can be observed in both Meander and Spiral datasets. The small differences 325 come from the fact the value used for k max in both situations is small, thus justifying the fact the dictionaries computed in these datasets have very high dimension when compared to others.

Multi-scale deep-based representations

As aforementioned, this round of experiments aimed at providing a performance comparison between dOPF and hOPF. To fulfill that purpose, the quality of the dictionaries provided by both techniques was compared using the protocol described in Section 5.1. As more visual words were added, hOPF dictionaries provide higher-dimensional representations. Hence, an additional experiment evaluated the quality of compressed representations computed by RBM. There were used representation sizes of 25% (hOPF-25), 50% (hOPF-50), and 75% (hOPF-75) of the original one (hOPF). Figure 6 illustrates the workflow of representation compression. Tables 10-15 provide the overall accuracy rates concerning each dataset.

The accuracy rate was computed using the same formulation as in Section 5.1, and the best results (i.e., bolded ones) were determined by the Wilcoxon signedrank with significance as 0.05.

In general, hOPF-based dictionaries achieved competitive results in all six datasets and always figured among the best ones. Also, slight improvements compared to dOPF can be observed in most scenarios, being the most significant ones achieved in the Dia-B dataset (Table 15). The average gain in that dataset varies from 5.79% (BC) to 8.83% (SVM-RBF). We also investigated the accuracy rates in each class, as shown in Tables 161718192021. The representations learned by the hierarchical approach also figured among the best results in many situations. Once again, the more significant improve- Since the difference between dOPF and hOPF relies on whether the visual words selected in the intermediate layers are used or not in the final dictionary, it must be concluded that the computational load for dictionary learning is the same.

Conclusion and Future Work

This work introduced a hierarchical-learning approach using the Deep Optimum-Path Forest to design visual dictionaries. The proposed approach was assessed and compared against a previous approach proposed by Afonso et al. [START_REF] Afonso | Parkinson's disease identification through deep optimum-path forest clustering[END_REF]

Figure 1 : 3 .

 13 Figure1: Architecture of an l th -layered dOPF. Adapted from Afonso et al.[START_REF] Afonso | Parkinson's disease identification through deep optimum-path forest clustering[END_REF]

Figure 2 :

 2 Figure 2: The main difference between (a) dOPF and (b) hOPF concerns the usage (or not) of features learned in the intermediate layers.

  . The workflow indicated by the light blue arrow concerns the training phase. The first step computes the local descriptors from the training signals to further clustering. The most representative samples from each cluster compose the dictionary, which is used for quantization (i.e., flow indicated by the purple arrow) of both training and testing signals. The outcome of such process is the new representation of each sample. Similarly, testing signals have their local descriptors extracted and quantized (i.e., flow indicated by the yellow arrows). The final step is to perform training and classification using the new computed representations.

Figure 3 :

 3 Figure 3: Proposed approach based on BoW and dOPF for computer-aided PD diagnosis.

Figure 4

 4 Figure 4 comprises the drawing of meander also four times and from the inner to the outer part. Last but not least, the fifth and sixth tasks are known as the diadochokinesis test and are used to evaluate the wrist movement of the right and left hands.

Figure 4 :

 4 Figure 4: Tasks perfomed to the assessment of hand movements

Figure 5 :

 5 Figure 5: Local feature extraction.

means 3

 3 and OPF4 through the accuracy rate obtained in the classification phase.The dOPF used in the work comprises an architecture with four layers, being the values of k max set as follows: 100 for the first layer, 1% of the number of clusters computed in the previous layer are used as an input for the second layer, and 10% of the number of clusters computed in their respective antecessor layers for the third and fourth layers 5 . The parameter k for k-means was always set as the number of clusters found by the fourth (last) layer of dOPF approach 3 Our implementation. 4 https://github.com/jppbsi/LibOPF 5 Those values were empirically set.

Figure 6 :

 6 Figure 6: The Deep OPF block represents the workflow depicted in Figure 3. The outcome of such process is used as input of RBM that outputs a compressed representation used by classifiers.

  achieved the best performance among the compressed versions with best results in 11 out of 18 scenarios against 6 out 18 of hOPF-25. Concerning the classifiers employed in the work, it can be observed a similar situation like the one illustrated in Section 5.1. The classifiers obtained good results with SVM-RBF being the best statistically technique in most cases. The highest accuracy among all datasets was achieved by the pair [hOPF, SVM-RBF] with 85.29%.

  in the context of Parkinson's disease identification. The experiments used six datasets derived from signal data collected when individuals were submitted to a handwriting exam. The exam is comprised of tasks supposed not to be trivial to Parkinson's disease patients, and the usage of signals allows to detect subtle variations.The main contributions of this work rely on the introduction of the proposed approach itself, its application in the context of automatic PD detection, and the usage of Restricted Boltzmann Machine for data compression. Experimental results showed the potential of hierarchical-learning approaches where interesting results were achieved. A general analysis pointed improvements in most scenarios and the proposed approach always figured the best results. An in-depth investigation showed a more considerable improvement in accuracy in the healthy individuals class in most scenarios.With respect to the compressed representations, RBM provided good models and achieved very interesting results (it either outperformed or was statistically similar to the original-sized representation and dOPF) in 12 out of 18 configurations (i.e., pair [dictionary learner, classifier] ) for the HC class, and 10 out of 18 configurations for the PD class. Regarding future work, we aim to study different ways to create hierarchical representations instead of the concatenation.

  and d f is the length of the longest edge in the graph (Z, A k ).

	The choice of this parameter considers all nodes for density computation since
	a Gaussian function covers most samples within d(s, t) ∈ [0, 3σ].
	The most common method for probability density function is the Parzen-
	window provided by Equation 1, which is based on the isotropic Gaussian kernel
	when the arcs are defined by (s, t) ∈ A k if d(s, t) ≤ d f . However, issues re-
	lated to differences in scale and sample concentration arise on the application of
	such approach. To overcome the mentioned problems, Comaniciu [23] proposed
	adopting adaptive choices for d f according to the region in the feature space.
	The method consists in selecting the best number of k-nearest neighbors within
	[1, k max ], such that 1 ≤ k max ≤ |Z|. In a similar way, Rocha et al. [19] proposed
	to select the value k ∈ [1, k max ] that minimizes the graph cut measurement of
	Shi and Malik [24] computed to each (Z, A k ).
	As aforementioned, the graph partitioning task is performed in a competitive
	fashion where the prototype nodes try to conquer the non-prototype ones by
	offering them optimum-path costs. A path π t in (Z, A k ) can be defined as a
	sequence of adjacent nodes starting in a root-node S(t) and ending at a sample
	t, where S stands for the set of root nodes. Also, let π t = t a trivial path, and
	π s • s, t the concatenation of π s and the arc (s, t). The Optimum-Path Forest
	makes use of a smooth function that assigns a value f (π t ) to each path π t . A
	path is said optimum if f (π t ) ≥ f (τ t ), being τ t any other path with terminus
	at t. The smooth function formulation employed by OPF is defined as follows:

Table 1

 1 presents the number of local descriptors obtained from each dataset, as well as the number of visual words selected by each clustering technique. Notice the values concerning the dOPF column stand for the number of visual words selected by each layer. As aforementioned, dOPF dictionaries are comprised of the visual words computed by the last layer only (i.e., bolded values).

Table 1 :

 1 Number of descriptors extracted from the training set and number of words computed by each technique.

	dataset (task)	# descriptors	dOPF	k-means OPF
	Circ-A exam (a)	18,000	5,682 -2,584 -228 -68	68	693
	Circ-B exam (b)	11,898	538 -376 -43 -17	17	33
	Spiral exam (c)	46,637	12,118 -3,951 -370 -92	92	1,424
	Meander exam (d)	41,094	10,865 -3,937 -429 -99	99	1,591
	Dia-A exam (e)	14,608	666 -480 -95 -47	47	80
	Dia-B exam (f)	13,947	657 -394 -78 -27	27	70

Table 2 :

 2 Overall accuracies.

		(a) Circ-A dataset.			(b) Circ-B dataset.
		BC	sOPF	SVM-RBF		BC	sOPF	SVM-RBF
	dOPF	82.96±2.88	81.71±5.12	73.87±4.58	dOPF	68.75±7.96	69.14±6.95	77.31±4.45
	k-means	83.38±4.22	82.01±5.11	65.80±12.39	k-means	67.80±7.44	65.58±6.79	74.54±6.39
	OPF	81.06±4.36	81.90±4.89	76.17±6.92	OPF	70.81±4.62	73.08±8.96	76.69±5.38
		(c) Spiral dataset.			(d) Meander dataset.
		BC	sOPF	SVM-RBF		BC	sOPF	SVM-RBF
	dOPF	78.30±5.80	76.73±6.83	77.25±3.46	dOPF	73.33±4.97	74.07±2.90	80.45±2.42
	k-means	73.37±5.37	73.11±5.31	78.83±2.20	k-means	76.07±3.31	76.09±2.77	78.26±3.91
	OPF	75.40±3.09	75.57±3.13	81.03±2.40	OPF	78.53±3.15	77.21±3.52	81.07±2.60
		(e) Dia-A dataset.			(f) Dia-B dataset.
		BC	sOPF	SVM-RBF		BC	sOPF	SVM-RBF
	dOPF	69.86±7.21	70.93±7.29	68.69±7.26	dOPF	67.96±8.10	64.86±7.93	61.89±8.49
	k-means	72.18±7.46	72.43±5.81	73.93±8.66	k-means	72.92±8.51	69.84±9.03	67.24±9.31
	OPF	70.72±6.60	67.01±7.45	68.69±7.26	OPF	63.77±8.85	67.25±6.80	66.30±7.38

Table 3 :

 3 Circ-A dataset.

		BC		sOPF	SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	82.59±8.09 83.33±5.62	85.93±6.59	77.5±10.24	67.41±11.67 61.67±15.10
	k-means 82.59±8.09 84.17±7.79	84.44±12.09 79.58±10.15	67.04±7.99 70.42±12.60
	OPF	82.96±8.52 79.17±12.19	82.96±6.79	80.83±8.34	71.48±9.82	75.42±6.87

Table 4 :

 4 Circ-B dataset.

		BC		sOPF		SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	76.67±49.12 60.83±18.32 71.85±13.98 63.75±13.35 77.04±10.51 64.58±13.24
	k-means 77.04±12.48 61.25±11.68 67.41±12.32 63.75±13.35	77.41±6.24 68.75±14.43
	OPF	59.99±9.56 74.58±13.39 57.04±17.15 54.17±13.04	45.93±7.98	57.92±10.07

Table 5 :

 5 Spiral dataset.

			BC	sOPF	SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	82.08±8.14 74.51±10.59 75.42±11.92 78.04±12.07 89.43±1.83	67.81±2.17
	k-means 81.25±11.33	65.49±10.63	79.17±10.48	67.06±10.14	84.85±2.25	73.59±3.67
	OPF	77.90±6.95	72.90±6.90	79.52±6.20	71.61±6.27	86.43±1.09	74.58±0.82

Table 6 :

 6 Meander dataset.

			BC	sOPF	SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	73.33±4.97 76.61±4.04 72.76±5.47 75.38±4.62 85.80±0.89 74.81±2.18
	k-means 82.67±4.88	69.46±5.96	78.95±4.99	73.23±4.51	84.43±3.76 71.06±2.62
	OPF	80.29±4.68 76.77±8.44 76.57±5.47 77.85±3.93	87.99±0.72	74.54±1.37

Table 7 :

 7 Dia-A dataset.

		BC		sOPF		SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	72.22±9.51 67.50±16.01	78.52±8.33 65.83±13.28	75.19±7.55 66.25±13.46
	k-means 75.19±5.69 66.67±14.01	74.44±6.97 70.42±12.59 67.78±12.37 66.25±15.61
	OPF	50.74±9.70 51.67±17.15 55.56±12.67 52.08±11.10 50.00±13.46 47.50±12.87

Table 8 :

 8 Dia-B dataset.

			BC	sOPF	SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	72.59±9.62 63.33±12.88	73.33±9.56 72.50±10.89 56.29±15.56 71.25±11.81
	k-means 68.89±9.89	60.83±11.29	72.59±10.63 67.08±13.39	60.74±11.38	73.75±11.23
	OPF	50.37±28.07	60.00±32.18	48.52±12.42	47.92±10.62	53.70±9.44 52.08±15.92

Table 9 :

 9 Dictionary learning computational load [s] required by each technique.

	dataset (task)	dOPF	k-means	OPF
	Circ-A (a)	968.167	37.008	49,087.137
	Circ-B (b)	419.498	13.113	32,777.539
	Spiral (c)	6,063.205	239.859	6,643.906
	Meander (d)	5,003.233	208.443	5,168.819
	Dia-A (e)	613.109	19.878	41,189.133
	Dia-B (f)	569.053	11.025	39,367.844

Table 10 :

 10 Circ-A dataset -Overall accuracies.

		dOPF	hOPF	hOPF-25	hOPF-50	hOPF-75
	BC	82.94±6.00	82.94±5.69	79.80±6.75	81.96±7.53	80.20±6.14
	sOPF	82.16±6.43	82.94±5.69	79.22±6.71	80.39±7.18	79.80±6.14
	SVM-RBF	84.51±5.82	85.29±3.69	83.14±4.19	84.12±8.23	81.76±4.87

Table 11 :

 11 Circ-B dataset -Overall accuracies.

		dOPF	hOPF	hOPF-25	hOPF-50	hOPF-75
	BC	80.98±3.49	79.22±4.65	69.80±5.50	68.63±8.73	68.04±8.67
	sOPF	80.00±3.88	79.02±5.87	69.61±5.63	68.63±8.73	68.04±8.81
	SVM-RBF	79.61±6.33	79.02±4.57	78.24±6.07	78.04±5.76	79.41±7.94

Table 12 :

 12 Spiral dataset -Overall accuracies.

		dOPF	hOPF	hOPF-25	hOPF-50	hOPF-75
	BC	77.22±3.57	78.94±2.58	74.04±3.64	72.88±2.35	72.32±3.36
	sOPF	76.97±3.64	77.88±2.59	73.33±3.64	72.83±2.35	71.77±3.36
	SVM-RBF	79.49±2.33	81.21±2.13	80.35±1.44	80.15±2.73	80.91±2.61

Table 13 :

 13 Meander dataset -Overall accuracies.

		dOPF	hOPF	hOPF-25	hOPF-50	hOPF-75
	BC	77.02±3.39	78.64±3.05	68.89±4.59	68.79±3.92	68.38±4.26
	sOPF	75.15± 3.09	77.42±3.29	68.89±4.37	68.28±4.13	67.68±3.66
	SVM-RBF	82.17±3.82	83.79±2.51	79.04±2.21	79.55±2.18	78.74±3.63

Table 14 :

 14 Dia-A dataset -Overall accuracies.

		dOPF	hOPF	hOPF-25	hOPF-50	hOPF-75
	BC	73.33±7.90	73.33±4.95	66.47±6.53	69.22±7.28	69.99±8.63
	sOPF	73.53±7.86	73.33±5.83	66.47±6.92	68.24±7.31	68.82±7.36
	SVM-RBF	79.22±5.38	77.25±4.51	76.86±4.56	75.69±4.37	79.61±7.49

Table 15 :

 15 Dia-B dataset -Overall accuracies.

		dOPF	hOPF	hOPF-25	hOPF-50	hOPF-75
	BC	68.43±5.71	68.43±5.72	69.80±6.53	75.29±5.54	73.14±7.45
	sOPF	67.45±6.43	67.45±6.43	69.41±6.65	74.71±6.27	73.14±7.02
	SVM-RBF	70.39±6.43	74.51±5.52	74.31±9.06	77.84±8.60	80.59±5.07

Table 16 :

 16 Circ-A -Average accuracy rate for each class.

	360
	ments (i.e., compared to dOPF) can be observed in the HC class in almost
	all scenarios, such as the ones in Circ-B and Dia-B datasets (i.e., the greatest
	ones). Compressed representations also presented competitive results, especially
	the most compressed one (hOPF-25) as one can observe in Circ-A and Circ-B
	datasets for HC class, and Dia-A dataset for PD class.

365

Table 17 :

 17 Circ-B -Average accuracy rate for each class.

			BC	sOPF	SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	78.52±9.12	83.75±9.97	78.15±9.02	82.08±9.99 79.63±11.04 79.58±12.38
	hOPF	78.52±6.92	80.00±7.17	77.41±8.26	80.83±9.59	80.74±9.12	77.08±8.41
	hOPF-25 86.67±5.86 50.83±12.47	86.67±5.86	50.42±12.60 86.30±10.47	69.17±8.34
	hOPF-50 85.56±6.90 49.58±16.61	85.93±7.23	49.17±16.68	81.85±9.26	73.75±14.02
	hOPF-75 78.15±13.36 56.67±14.84 78.15±14.77 56.67±14.26	86.67±8.08 71.25s±16.33

Table 18 :

 18 Spiral -Average accuracy rate for each class.

		BC	sOPF	SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	78.76±6.91	75.48±5.89	78.19±6.71	75.59±6.09 84.95±5.91 73.33±5.91
	hOPF	83.24±3.48 74.09±4.42 82.38±4.17 72.80±4.35 86.38±5.79 75.38±6.72
	hOPF-25 84.95±4.07	61.72±6.75	84.38±3.98	60.86±6.66	87.14±6.01 72.69±6.17
	hOPF-50	81.90±4.06	62.69±5.13	82.10±3.58	62.37±4.79	84.10±4.61 75.70±4.46
	hOPF-75 82.67±4.48	60.65±6.86	82.19±4.58	60.00±6.93	87.52±6.33 73.44±6.06

Table 19 :

 19 Meander -Average accuracy rate for each class.

		BC		sOPF	SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	80.76±5.50 72.80±7.00 77.43±7.56 72.58±7.44	89.43±4.41	73.98±7.41
	hOPF	82.19±5.29 74.62±3.19 80.10±5.83 74.41±3.49 92.48±3.98 73.98±3.33
	hOPF-25	71.14±7.41	66.34±6.87	71.14±7.21	66.34±7.00	90.38±4.09	66.24±3.93
	hOPF-50	72.86±6.39	64.19±6.63	72.10±6.48	63.98±6.81	90.76±4.58	66.88±4.35
	hOPF-75	72.48±5.49	63.76±4.60	71.14±4.52	63.76±4.60	90.29±5.92	65.70±5.08

Table 20 :

 20 Dia-A -Average accuracy rate for each class.

			BC	sOPF	SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	79.26±7.99 66.67±13.08	78.52±6.60 67.92±12.47	72.96±9.59 86.25±10.88
	hOPF	72.96±8.19	73.75±13.04	72.96±8.62	73.75±14.98	72.22±7.86	82.92±13.04
	hOPF-25	64.81±6.79	68.33±15.13	64.81±7.76	68.33±14.46	73.70±9.02 80.42±10.79
	hOPF-50 72.59±10.59 65.42±14.15 70.74±10.60 65.42±14.54	80.37±9.82	70.42±11.68
	hOPF-75 67.41±12.58 72.92±19.00	65.19±12.68	72.92±18.85 76.67±10.33 82.92±14.07

Table 21 :

 21 Dia-B -Average accuracy rate for each class.

			BC	sOPF	SVM-RBF
		HC	PD	HC	PD	HC	PD
	dOPF	67.41±8.36	69.58±11.78	66.67±9.62	68.33±12.60 73.70±13.36	66.67±12.20
	hOPF	67.41±8.36	69.58±11.78	66.67±9.62	68.33±12.60 83.70±11.40	64.17±11.92
	hOPF-25	82.96±7.99	55.00±13.81	83.70±7.99	53.33±13.95	81.85±7.11	65.83±16.68
	hOPF-50 89.99±6.01	58.75±11.52	89.63±5.50 57.92±13.25 79.63±13.72 75.833±20.44
	hOPF-75	81.48±8.31	63.75±14.01	81.11±9.10	64.17±14.07 78.52±11.67 82.92±13.04

http://wwwp.fc.unesp.br/ ~papa/pub/datasets/Handpd

https://www.oth-regensburg.de/index.php?id=5312/biometrics.html

Our implementation.

https://github.com/LibOPF/LibOPF

An interesting aspect to be highlighted, it is the fact that compressed representations computed by RBM also figured among the best results, even the most compressed ones (hOPF-25). The representations hOPF-50 and hOPF-75

Acknowledgments

The authors are grateful to FAPESP grants #2013/07375-0, #2014/12236-1 and #2016/19403-6, Capes, and CNPq grants #306166/2014-3, #307066/2017-7, and #303808/2018-7.