# Variable Selection Using Adaptive Band Clustering and Physarum Network
## 2 Theory  
### AP Algorithm  
AP [20; 21; 22; 23; 24; 25; 26; 27] is an unsupervised clustering algorithm. It clusters data points by identifying a set of centers (exemplars). Unlike other clustering algorithms that need an initial set of input exemplars, AP considers all data points as potential exemplars. Each data point is regarded as a node in a network, real-valued messages are transmitted along the edge of the network until a set of exemplars and clusters are found. Because of the unsupervised characteristics and good performance of AP, it has been used in many areas since its initial publishing [20], such as band selection [21] and data compression [24] in hyperspectral imaging, spatial clustering in geospatial data [22], statistical information extraction from high-dimensional data spaces [23], and identification of protein complexes from protein interaction graphs [26]. The input required by the AP is the real valued similarities \(S(i,k)\) between data point \(i\) and point \(k\), which indicates how suitable the data point \(k\) is for being the exemplar of data point \(i\). The input \(S(k,k)\) for each data point \(k\) is called preference and is denoted as \(p_{k}\). The data point with a large preference has a higher chance of being selected as an exemplar. The values of the input preferences can influence the number of exemplars or clusters, i.e., the larger the \(p_{k}\) is, the more exemplars the AP will give [20]. The messages passing through the edges are responsibility and availability. The responsibility \(r(i,k)\) reflects how well the point \(k\) acts as an exemplar to the point \(i\). The availability \(a(i,k)\) reflects how well the point \(i\) belongs to a class centered on point \(k\)[20]. An illustration of message exchange in an AP network is given in Figure 1.  
The \(r(i,k)\) and \(a(i,k)\) are calculated by using the formulas below  
\[r(i,k)=S(i,k)-\max\bigl{\{}a(i,k^{\prime})+S(i,k^{\prime})\bigr{\}} \tag{1}\]  
\[a(i,k)=\min\bigl{\{}0,r(k,k)+\sum_{i^{\prime}\
otin\{i,k\}}\max\bigl{\{}0,r(i^ {\prime},k)\bigr{\}}\bigr{\}} \tag{2}\]  
The \(r(k,k)\) and \(a(k,k)\) are calculated using different rules below  
\[r(k,k)=S(k,k)-\max\bigl{\{}S(k,k^{\prime})\bigr{\}} \tag{3}\]  
\[a(k,k)=\sum_{i^{\prime}\
eq k}\max\bigl{\{}0,r(i^{\prime},k)\bigr{\}} \tag{4}\]  
The responsibility and availability are updated constantly by using the rules below  
\[r(i,k)_{new} =\lambda\cdot r(i,k)_{old}+(1-\lambda)\cdot r(i,k)_{new} \tag{5}\] \[a(i,k)_{new} =\lambda\cdot a(i,k)_{old}+(1-\lambda)\cdot a(i,k)_{new} \tag{6}\]  
where \(\lambda\) is the damping factor between 0 and 1 to avoid numerical oscillations, \(r(i,k)_{new}\) and \(r(i,k)_{old}\) are current and previous responsibility, respectively, and \(a(i,k)_{new}\) and \(a(i,k)_{old}\) are current and previous availability, respectively. The damping factor \(\lambda\) was set to a value between 0.5 and 0.9 following the suggestion in [21]. Different values of \(\lambda\) in the suggested range were tested. It was found that \(\lambda\) in this range has no effect on the final number of groups (see Sections 3.1.2, 3.2.1 and 3.3.2 for details), so the \(\lambda\) is set as 0.9, which is the default value suggested in AP Algorithm software [20]. Figure 1: Two messages, responsibility (\(r(i,k)\), \(r(i^{\prime},k)\), and \(r(i,k^{\prime})\) ), and availability (\(a(i,k)\), \(a(i^{\prime},k)\), and \(a(i,k^{\prime})\) ), are passing in an affinity propagation network. The responsibility \(r(i,k)\) and \(r(i^{\prime},k)\) reflect how well the point \(k\) acts as an exemplar to the point \(i\) and \(i^{\prime}\), respectively. The availability \(a(i,k)\) and \(a(i^{\prime},k)\) reflect how well the point \(i\) and \(i^{\prime}\) belong to a class centered on point \(k\). The responsibility \(r(i,k^{\prime})\) reflects how well the point \(k^{\prime}\) acts as an exemplar to the point \(i^{\prime}\). The availability \(a(i,k^{\prime})\) reflects how well the point \(i\) belongs to a class centered on point \(k^{\prime}\).