# Sound Source Localization Indoors Based on Two-Level Reference Points Matching
## 3 Two-Level Matching Method for Adjacent RPs Searching
### Adjacent Subset Searching Based on Clustering Method  
The clustering method can classify datasets according to the similarity between samples and classify new sampling points. For fingerprint-based SSL, the clustering method can be used to separate the positioning database into several sub-databases and classify the pending target into a corresponding category. Then, the RPs matching range will be reduced compared to the global linear matching method. The process of fingerprint-based SSL using the clustering method is shown in Figure 4 in brief.  
Figure 3: The RPs matching process based on a greedy algorithm.  
In many cases, it is difficult to classify the targets reasonably by the hard clustering method such as the K-means algorithm, which was adopted in our previous work [41], because the relationship between RPs in practice is vague and uncertain. In this case, the soft clustering method can more scientifically and reasonably divide the database. As a typical clustering method, the Fuzzy c-means algorithm can use fuzzy mathematics to analyze the uncertainty of the sample properties, and the clustering partition will be completed according to the membership degree of samples. For the RPs matching process in the fingerprint-based SSL, the first-level searching (i.e., adjacent sub-database searching) process based on the Fuzzy c-means method can be shown as follows:  
Step 1: determine the number of sub-databases \(k\), which means the positioning database will be divided into \(k\) clusters.  
Step 2: assign a membership degree to each cluster for each RP, which meets the following conditions:  
\[\sum_{c=1}^{k}u_{cj}=1,\quad 0\leq u_{cj}\leq 1,\quad c=1,2,\ldots,k.\quad j =1,2,\ldots,N. \tag{9}\]  
where \(u_{cj}\) represents the membership degree of the RP\({}_{j}\) to cluster \(c\), and the value is defined between 0 and 1 (when the value is 1, the RP is exclusive to the cluster, \(c\)), and \(N\) is the total number of RPs.  
Step 3: calculate the clustering center and update the membership matrix of RPs. Specifically, the objective function of the Fuzzy c-means algorithm is:  
\[J=\sum_{c=1}^{k}\sum_{j=1}^{N}{(u_{cj})^{\gamma}D_{j}^{c}} \tag{10}\]  
where \(D_{j}^{c}=\left\|F_{center}^{c}-F_{j}\right\|\) represents the distance between the  
where \(U=[u_{cj}]\), \(\Phi=[F_{center}^{c}]\), \(c=1,2,\ldots,k\). \(j=1,2,\ldots,N\)., \(\lambda_{j}\), is the lagrange multiplier, and the constraint condition is (9). By differentiating the input parameters, the minimization condition of the objective function can be translated into:  
\[F_{c}=\frac{\sum\limits_{j=1}^{N}{(u_{cj})^{\gamma}F_{j}}}{\sum\limits_{j=1}^{ N}{(u_{cj})^{\gamma}}} \tag{12}\]  
\[u_{cj}=\frac{1}{\sum\limits_{r=1}^{k}{\left(\frac{D_{ij}}{D_{rl}}\right)^{2/( \gamma-1)}}} \tag{13}\]  
Through Formula (12), the new clustering center \(U=[u_{cj}]\), \(c=1,2,\ldots,k\). \(j=1,2,\ldots,N\). can be generated, and then the new membership matrix can be obtained through Formula (13).  
Step 4: after the clustering center is generated, we decide whether the result is convergent by the objective function (10): when the condition is not met, return to step 3, and complete the whole updating process through the cyclic iteration of Formulae (12) and (13). When the convergence condition is satisfied, run the next step for clustering results output.  
Step 5: output the final clustering center and membership matrix (i.e., the cluster information of the RPs).