# An Integrated Fuzzy C-Means Method for Missing Data Imputation Using Taxi GPS Data
## 3 Methodology
### Integrated FCM Imputation Algorithm with GA  
The procedure for determining \(c\) and \(m\) falls into the category of the combinatorial optimization problem. To address this type of problem, the stochastic search algorithm has been proven to be an efficient way [17]. Motivated by the artificial intelligence technique, the genetic algorithm (GA) is effective in solving the combinatorial optimization problem and providing an excellent interface with other algorithms. Thus, in our study, the GA was implemented in the FCM to optimize the membership degree \(m\) and the number of cluster centroids \(c\). In particular, the specific procedure of the integrated imputation algorithm combining the FCM and the GA is put forward as follows:  
Step 1: (Initialization) Set the upper bound and the lower bound of both the parameter of the membership degree and the number of the cluster centroids, respectively. Set the threshold \(\varepsilon\) as 0.1. Initialize the number of the cluster centroids and then calculate the membership degree according to Formulas (3) and (4). Determine the parameters of the GA, including the population size, \(N=20\), the number of generations, \(T=100\), the probability of crossover, \(P_{c}=0.9\), and the probability of mutation \(P_{m}=0.1\).  
Step 2: (FCM) Calculate each membership degree in the FCM. Update the new cluster centroid according to Formula (6), and when the optimal results are obtained, estimate the missing values according to Formula (7).  
Step 3: (Evaluation) Evaluate the root mean squared errors (RMSEs) between the estimated values and the actual values using Formula (8). \(I_{jk}\) is the binary indicator; when it is equal to 1, then this means the value in the \(j^{\text{th}}\) column and the \(k^{\text{th}}\) row of the matrix is missing, and \(x_{jk}^{*}\) is the estimated value, while \(x_{jk}\) is the actual value; otherwise, when it is equal to 0, this means the value in the \(j^{\text{th}}\) column and the \(k^{\text{th}}\) row of the matrix exists.  
\[RMSE=\sqrt{\frac{\sum\limits_{k=1}^{n}\sum\limits_{j=1}^{p}\left[I_{jk}(x_{jk} -x_{jk}^{*})\right]^{2}}{\sum\limits_{k=1}^{n}\sum\limits_{j=1}^{p}I_{jk}}} \tag{8}\]  
Step 4: (Fitness calculation) Define the fitness function used in the GA to achieve the selection procedure. The specified fitness is calculated as follows:  
\[f=1/RMSE \tag{9}\]  
Step 5: (GA procedure) Complete the procedures of selection, crossover, and mutation, and then output the new population including \(c\) and \(m\).  
Step 6: (Termination or not) Judge whether the number of iterations reaches the threshold \(T\) or not; if not, then return to Step 2; otherwise, output the missing values.  
In summary, the detail of the integrated imputation algorithm is illustrated in Figure 4.  
The taxi GPS data in Manhattan, New York City, were utilized to examine the performance of the integrated imputation algorithm. The 24-h taxi GPS data were collected from 14 January to 18 January 2013 (these resources are available in the Supplementary Materials). Moreover, different missing ratios in the datasets were set to evaluate its performance in depth. The detailed results comparisons are put forward in the next section.