# Affinity Propagation Clustering Using Path Based Similarity
## 3 Results
### Results on UCI Datasets
#### 3.2.1 Clustering results on UCI datasets  
In this section, we take APC, \(k\)-means [28], EM [29; 30], SSC [31], pAPC [21] and APCGD [22] as the comparing methods and comparatively study the performance of APC-PS on four UCI datasets. To avoid random effect, we repeat the experiments 20 times for each comparing method on each dataset, and report the average results and standard deviations in Tables 2 and 3. Since pAPC can not \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Dataset** & \(n\) & \(d\) & \(k\) \\ \hline Balance & 625 & 4 & 3 \\ Glass & 214 & 9 & 6 \\ Synthetic & 600 & 60 & 6 \\ Mushrooms & 8124 & 112 & 2 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Four UCI datasets used for experimental study. finish on Mushroom in 12 days, its results on Mushroom are not reported in these two tables. In these table, the numbers in **boldface** denote the statistical significant best (or comparable best) results at 95% confident level. From Tables 2 and 3, we have clear observation that none of these comparing algorithms are always performing better than others. This is because different algorithms have different bias and these adopted four datasets are also distributed with different structures. EM is outperformed by \(k\)-means, APC and APC-PS in majority cases. The reason is that EM assumes samples are normally distributed. But samples in these four datasets are not subject to normal distribution. \(k\)-means outperforms SSC on Synthetic control and Glass identification, but it loses to SSC on other two datasets. The reason is that \(k\)-means can work well on spherical datasets, but it does not perform well on other datasets, whose samples are distributed with complex structures. Although SSC assumes the sparsity of features and mixture of subspace clusters, it is still often loses to APC and always loses to APC-PS. The possible cause is that the assumption used by SSC does not hold for these four datasets. APC-PS significantly performs better than APC in most cases under different evaluation metrics and it often performs as well as the best of the other five methods in terms of F-measure and FMI. APC only utilizes Euclidean distance between samples to explore the underlying structures between samples. In contrast, APC-PS not only exploits the Euclidean distance, but also a path-based similarity to explore the underlying structures of samples and to assign samples to their respective clusters via this similarity. Therefore, APC-PS produces better results than APC. From these results, we can draw a conclusion that the path-based similarity can faithfully explore underlying structures of samples and thus to boost the accuracy of APC. APCGD and pAPC adopts different techniques to measure the similarity between samples, instead of the original negative Euclidean distance. They are still outperformed by APC-PS in most cases. APC-PS and pAPC employ similar path-based similarity to assign a non-exemplar sample to the cluster, whose exemplar has largest similarity with the sample. APC-PS achieves better results than pAPC. This occurs principally because APC-PS and pAPC take different samples as exemplars. In practice, pAPC computes the path-based similarity between any pairwise samples at first. Then, it performs