# A Novel Approach for Cognitive Clustering of Parkinsonisms through Affinity Propagation
## 2 Materials and Methods
### Affinity Propagation  
Affinity propagation (AP) is a non-hierarchical clustering method based on graph theory proposed by [PERSON] (2008), in which each data point is treated as a node of the network, and the nodes exchange iteratively \"messages\" through the edges of the network itself. An important feature introduced by the AP approach is the concept of exemplars, representative points, which identify centers of clusters. Exemplars are different than centroids of K-Means--barycenter of the points in a cluster--since they have to be one of the actual samples or participants as in the present work. The AP algorithm simultaneously considers all the participants as probable candidates to become centers of the clusters and propagate exchanges of messages between the other participants until the emergence of the best exemplars that maximize the intra-cluster similarity ([PERSON] et al., 2018; [PERSON] et al., 2018). At each iteration of the AP algorithm, the message between two nodes represents the current \"affinity\" that a sample has for selecting another sample as its exemplar. For this reason, the AP method does not require the initial specification of the number of clusters, as for example in \(k\)-centers and \(k\)-means approaches. The AP algorithm requires as input an \(n\times n\) similarity matrix, \(\mathbf{S}\) = [\(s_{ij}\)], where \(n\) is the number of participants to be clustered and \(i\) and \(j\) are the participant's indices. A commonly used measure of distance or dissimilarity is the squared Euclidean distance. If there are two points in an \(m\) dimensional space where \(m\) is the number of measured variables (the eleven MMSE subscales), then the squared Euclidean distance is defined as:  
\[s_{ij}=\sum_{z=1}^{m}\left(e_{iz}-e_{jz}\right)^{2} \tag{3}\]  
where \(e_{iz}\) is the value of the \(z\)-th variable for the \(i\)-th residual and \(e_{ik}\) is the value of the \(z\)-th variable for the \(j\)-th residual in \(\mathbf{E}(n\times m)\), the matrix of regression residuals, calculated as described in Section 2.3.1. Larger values of \(s_{ij}\) indicate a greater degree of similarity between \(i\) and \(j\) than smaller values of \(s_{ij}\). It is assumed that \(s_{ii}\) = 0 (for all \(1\leq i\leq n\)) in the formulation. In the present work, the negative squared Euclidean distance was used, as suggested by [PERSON] (2008). The definition of the suitability of each participant for serving as an exemplar is contained in the second input of the AP algorithm: the preferences (\(p_{i}\), for \(1\leq i\leq n\), which may also be specified as the \(n\times 1\) vector \(\mathbf{p}\)). In other words, the preferences represent an a priori knowledge of how good a participant could be eligible as an exemplar ([PERSON] et al., 2018). Usually, all samples are equally eligible to be an exemplar, thus their value \(p\) is the same constant ([PERSON] et al., 2018; [PERSON] et al., 2018). Anyhow, the preferences vector is none other than a control parameter and increasing the value of one sample results in an increase in the likelihood that the sample will be chosen as exemplar ([PERSON] et al., 2018; [PERSON] et al., 2018). The default specification for the preferences is the median of the similarity values (\(\mathbf{S^{M}}\)) ([PERSON] et al., 2018; [PERSON] et al., 2018), although it has been shown that by using the median, the number of clusters could be dramatically overestimated ([PERSON] et al., 2018; [PERSON] et al., 2018). A reliable alternative is to specify the preference as the minimum of the similarity measures: \(p_{i}\) = \(\mathbf{S^{min}}\), for \(1\leq i\leq n\), resulting in a smaller number of clusters ([PERSON] et al., 2018). For assessing which between the median and the minimum of the similarity matrix is to prefer in the case of the clustering of the MMSE scores, we used both preference values and then we compared their findings with a Silhouette analysis [47] as described in Section 2.5.