# High-Dimensional Data Analysis Using Parameter Free Algorithm Data Point Positioning Analysis
## 3 Overview of Clustering Algorithms
### Affinity Propagation  
The affinity propagation (AP) technique, mentioned in [28; 39], is a distance-dependent approach that can identify exemplars in a dataset. AP can cluster facial images, locate genes, and cluster spatial datasets on a map, among other tasks [40; 41; 42]. Unlike K-means, AP selects existing points as exemplars and does not generate new points. It does not need a predetermined number of clusters or initial candidate exemplars. Instead, AP considers every point in the dataset and chooses exemplars through competitive iterations. AP employs two types of \"messages\" to compute responsibility and availability, based on the distance between any two distinct points, \(x_{i}\) and \(x_{k}\), in the dataset. Responsibility, represented by \(r(i,k)\), is a \"message\" sent from \(x_{i}\) to its candidate exemplar point \(x_{k}\) and indicates how well \(x_{k}\) can represent \(x_{i}\) as an exemplar. Availability, represented by \(a(k,i)\), is the \"message\" sent from \(x_{k}\) to \(x_{i}\) and represents the accumulated evidence for how suitable \(x_{k}\) is for being selected as an exemplar by \(x_{i}\). AP initializes the values of these \"messages\" between any two distinct points, and then iteratively updates the values of responsibility and availability. Finally, AP selects the point \(x_{k^{\prime}}\) with the highest sum of responsibility \(r(i,k^{\prime})\) and availability \(a(k^{\prime},i)\) as the exemplar for each point \(x_{i}\). Thus, AP clusters \(x_{i}\) and \(x_{k^{\prime}}\) into the same cluster and assigns \(x_{i}\) a label based on the sequence index number of \(x_{k^{\prime}}\) in the dataset. As a result, AP can identify exemplars and assign class labels to each point based on its exemplar's sequence index number. Here is a detailed description of the affinity propagation algorithm:  
1. Initialization: The algorithm begins by initializing two matrices: the \"similarity matrix\" and the \"responsibility matrix\". The similarity matrix contains the pairwise similarity scores between all data points. The responsibility matrix is a matrix of the same size as the similarity matrix and is initialized to 0. 2. Calculate responsibility matrix: In this step, the algorithm iteratively updates the responsibility matrix. The responsibility matrix represents how well-suited each data point is to be an \"exemplar\" or representative of a cluster. The update rule is as follows: \[r(i,k)=s(i,k)-\max_{k^{\prime}\
eq k}a(i,k^{\prime})+s(i,k^{\prime})\] (1) where \(r(i,k)\) is the responsibility of point \(i\) to exemplar \(k\), \(s(i,k)\) is the similarity score between point i and exemplar \(k\), and \(a(i,k)\) is the \"availability\" of point \(i\) to exemplar \(k\), which is updated in step 3. 3. Calculate availability matrix: In this step, the algorithm updates the availability matrix. The availability matrix represents how much \"support\" a data point receives from other data points for being an exemplar. The update rule is as follows: \[a(i,k)=\min 0,r(k,k)+\sum_{i^{\prime}\
eq i,i^{\prime}\
eq k}\max 0,r(i^{\prime},k)\] (2) where \(a(i,k)\) is the availability of point \(i\) to exemplar \(k\), \(r(k,k)\) is the self-responsibility of exemplar \(k\), and the summation term represents the total responsibility that other points have assigned to exemplar \(k\). 4. Calculate cluster exemplars: The algorithm uses the responsibility and availability matrices to calculate which data points are the best exemplars for each cluster. The exemplars are chosen as the data points with the highest sum of their responsibility and availability scores: \[e(k)=\operatorname*{argmax}_{i}(r(i,k)+a(i,k))\] (3)
5. Assign data points to clusters: Finally, the Algorithm 2 assigns each data point to its nearest exemplar, which forms the final clusters. Affinity propagation algorithm has advantages: Automatic cluster number determination and handling of non-spherical clusters. However, it can be computationally expensive and sensitive to the initial exemplar choice.