# Fingerprinting Acoustic Localization Indoor Based on Cluster Analysis and Iterative Interpolation
## 3 The Proposed Fingerprinting Acoustic Localization Approach
### Database Partition by Clustering Method  
Clustering is an elements grouping process according to some specific features, which is called the cluster key, such as the TDOA value we choose in this paper. The prototype-based clustering method has the advantages of simple, fast and efficient process for big datasets classification. As one of the prototype-based clustering algorithms, K-Means clustering algorithm is a classical and efficient algorithm for cluster analysis [37].  
Figure 2: Fingerprinting acoustic localization process based on cluster analysis and iterative interpolation.  
The database partition process by K-Means clustering algorithm includes three steps. Suppose there is a database \(\mathbf{D}\) with \(N\) samples that needs to be partitioned to \(K\) (\(K\) < \(N\)) groups. The clustering algorithm for the sound-position fingerprint database can be described as Algorithm 1.  
```
Input: database \(\mathbf{D}\)\(=\left[\mathbf{S}_{1},\mathbf{S}_{2},\cdots,\mathbf{S}_{N}\right]^{T}\); cluster class number \(K\). Output:\(\mathbf{D}=\left\{\mathbf{C}_{1},\mathbf{C}_{2},\cdots,\mathbf{C}_{K}\right\}\)
1 Randomly selected \(K\) samples from \(\mathbf{D}\) as the initial cluster centers :\(\left\{\mathbf{\mu}_{1},\mathbf{\mu}_{2},\cdots,\mathbf{\mu}_{K}\right\}\);
2 while\(flag>0\)do
3 cluster centers update flag: \(flag=0\);
4\(\mathbf{C}_{i}\)=\(\mathcal{O}(i=1,2,\ldots,K)\);
5 for\(j\) = 1,2,...,\(N\)do
6 calculate the distance between \(\mathbf{S}_{j}\) and each cluster center \(\mathbf{\mu}_{i}\): \(d_{ji}=\left\|\mathbf{S}_{j}-\mathbf{\mu}_{i}\right\|_{2}\);
7 definite the cluster mark of \(\mathbf{S}_{j}\) by the nearest cluster center: \(\lambda_{j}=\operatorname*{arg\,min}_{i\in\left\{1,2,\cdots,K\right\}}d_{ji}\);
8 classify the sample \(\mathbf{S}_{j}\) into the corresponding cluster: \(\mathbf{C}_{\lambda_{j}}=\mathbf{C}_{\lambda_{j}}\cup\mathbf{S}_{j}\);
9 for\(i\) = 1,2,...,\(K\)do
10 calculate the new cluster center \(\mathbf{\mu}^{\prime}_{i}=\frac{1}{\left|\mathbf{C}_{i}\right|}\sum_{\mathbf{S}\in\mathbf{C}_ {i}}\mathbf{S}\);
11 if\(\mathbf{\mu}^{\prime}_{i}\
eq\mathbf{\mu}_{i}\)then
12 update the current value of \(\mathbf{\mu}_{i}\) to \(\mathbf{\mu}^{\prime}_{i}\);
13\(flag=flag+1\);
14
15 else
16 the current value \(\mathbf{\mu}_{i}\) remain the same;
17
```  
**Algorithm 1**The K-Means clustering algorithm for positioning database partition.  
Firstly, \(K\) samples are randomly selected from the positioning database \(\mathbf{D}\) as the initial cluster center \([\mathbf{\mu}_{1},\mathbf{\mu}_{2}\cdots\mathbf{\mu}_{K}]\). Then, the remaining samples are assigned to the most similar clusters according to the similarity with each cluster center in feature space. Then, the cluster center is updated by \(\mathbf{\mu}_{i}=\frac{1}{\left|\mathbf{C}_{i}\right|}\sum_{\mathbf{S}\in\mathbf{C}_{i}}\mathbf{S}\), where \(\mathbf{S}\) means the samples clustered to \(\mathbf{C}_{i}\). The clustering process is repeated until the cluster centers stop updating, and finally \(\mathbf{D}=\left\{\mathbf{C}_{1},\mathbf{C}_{2}\cdots\mathbf{C}_{K}\right\}\).