# High-Dimensional Data Analysis Using Parameter Free Algorithm Data Point Positioning Analysis
## 3 Overview of Clustering Algorithms
### Affinity Propagation
```
Inputs: - Similarity matrix s - Damping factor damping - Maximum number of iterations max_iter - Tolerance tol Outputs: - Cluster assignments Initialize: - Responsibility matrix r = zeros(n_samples, n_samples) - Availability matrix a = zeros(n_samples, n_samples) foriter=1 to max_iterdo ifinrange(n_samples)do  max_val = inf  max_idx = -1 fork in range(n_samples)do  val = a[i], k + si[k] ifval > max_valthen  max_val = val max_idx = k  end if  end fork inrange(n_samples)do ifk!= max_idx



density estimation, which estimates the density over \(X\) and identifies modes that correspond to the densest regions [45]. These modes can serve as estimates of cluster centers. To identify the modes in kernel density estimation, the mean shift, a basic gradient approach, is used. In the following section, we will delve into the mean shift procedure. #### 3.3.1 Mean Shift Procedures

Mean shift techniques are utilized to identify the modes of the kernel density estimation. The kernel, denoted as \(H:X\to R\), is defined by \(H(x)=h(\left|x-x_{j}\right|^{2})\). The estimation of the kernel density is derived using the following equation [46]:

\[\hat{\int}H(x)=\sum_{j=1}^{n}h(\left|x-x_{j}\right|^{2})w(x_{j}) \tag{4}\]

In this equation, \(w(x_{j})\) is a weight function. [PERSON] and [PERSON] [47] first introduced the statistical properties of the gradient of the density estimation using a uniform weight, which includes asymptotic unbiasedness, consistency, and uniform consistency. \[\triangledown\hat{\int}_{H}(x)=2\sum_{j=1}^{n}(x-x_{j})h^{\prime}(\left\|x-x_{ j}\right\|^{2})w(x_{j}) \tag{5}\]

Assume the existence of a kernel \(K:X\to R\), such that \(h^{\prime}(r)=ck(r)\), where \(c\) is a constant. If kernel \(H\) is considered a shadow of kernel \(K\), as defined in Ref. [48], then the following equation holds:

\[\triangledown\hat{\int}_{H}(x)=\sum_{j=1}^{n}k(\left\|x-x_{j} \right\|^{2})(x_{j}-x)w(x_{j}) \tag{6}\] \[=\left[\sum_{j=1}^{n}k(\left\|x-x_{j}\right\|^{2})w(x_{j})\right] \times\left[\frac{\sum_{j=1}^{n}k(\left\|x-x_{j}\right\|^{2})w(x_{j})x_{j}}{ \sum_{j=1}^{n}k(\left\|x-x_{j}\right\|^{2})w(x_{j})}\right]\] \[=\int^{\prime}K(x)[m_{K}(x)-x]\]

The generalized mean shift is expressed by the formula \(m_{K}(x)-x=\triangledown\hat{f_{H}}(x)/\hat{f_{K}}(x)\), which measures the estimated density gradient. This equation was first introduced in Reference [49] under the assumption of uniform weights. When the gradient estimator \(\triangledown f_{H}(x)\) is zero, the mode estimation can be determined by:

\[x=m_{K}(x)=\frac{\sum_{j=1}^{n}k(\left\|x-x_{j}\right\|^{2})w(x_{j})x_{j}}{ \sum_{j=1}^{n}k(\left\|x-x_{j}\right\|^{2})w(x_{j})} \tag{7}\]

Here, \(K\) is the kernel, and \(H\) is its shadow. Equation (6) is known as the sample weighted mean using kernel \(K^{\prime\prime}\). The mean shift can be implemented in three ways. The first method involves assigning initial values to each data point and updating each data point's \(x_{j}\) with \(m_{K}(x_{j})\), called blurring mean shift, where each data point and the density estimate \(\hat{f_{H}}(x)\) are modified with each iteration. The second method, called non-blurring mean shift, updates only the data point \(x\) with \(m_{K}(x_{j})\), while keeping most data points and the density estimate unchanged. The third method, called general mean shift, involves selecting \(c\) starting values, which can be more or less than \(n\), and updating the data point \(x\) with \(m_{K}(x_{j})\). [PERSON] [48] discussed the convergence properties of blurring mean shift using Equation (6), while [PERSON] and [PERSON] [49] presented various mean shift properties for discrete data and their relationship with the Nadaraya-Watson estimator through kernel regression and the robust \(M\)-estimator. If a kernel \(K\) has a shadow \(H\), the mean shift method can identify the modes of a known density estimate \(\hat{f_{H}}(x)\), allowing for direct identification of the estimated density shape modes.