# An Integrated Fuzzy C-Means Method for Missing Data Imputation Using Taxi GPS Data
## 3 Methodology
### Conventional Fuzzy C-Means Imputation Algorithm  
The fuzzy C-means clustering algorithm is one of the most efficient clustering techniques [13]. Meanwhile, this technique is also capable of estimating missing values in the incomplete datasets. \begin{table}
\begin{tabular}{c c c c c c} \hline  & **Monday** & **Tuesday** & **Wednesday** & **Thursday** & **Friday** \\ \hline
0:00:00–0:05:00 & 158 &? &? & 249 & 341 \\
0:05:00–0:10:00 & 184 & 200 & 254 &? &? \\
0:10:00–0:15:00 & 163 & 200 & 263 & 248 & 341 \\... &... &... &... &... &... \\
7:30:00–7:35:00 &? & 405 & 421 & 417 & 407 \\
7:35:00–7:40:00 & 399 & 444 &? & 455 & 435 \\
7:40:00–7:45:00 & 429 &? &? &? & 468 \\... &... &... &... &... &... \\
23:45:00–23:50:00 & 240 &? & 286 & 395 & 549 \\
23:50:00–23:55:00 & 205 & 281 & 284 & 398 & 542 \\
23:55:00–0:00:00 &? &? & 282 &? & 509 \\ \hline \end{tabular}
\end{table} 
Table 2: Taxi demand volume on weekdays. The “question marks” in Table 2 represent the missing values. Figure 3: Incomplete data on weekdays based on a 5 min aggregation interval. Before utilizing the FCM, several notations definition should be clearly given. Note that there are 288 rows in the matrix of Table 2, and each row has five columns. Let \(\mathbf{X}\) represent the raw data matrix, and \(\mathbf{X}=\{\mathbf{x}_{1};\mathbf{x}_{2};\ldots;\mathbf{x}_{k};\ldots;\mathbf{x}_{n}\}\) is easily derived, where \(n\) is 288 in Table 2. Due to the \(p\) attributes in each row, \(\mathbf{x}_{\mathbf{k}}=\{x_{1k},x_{2k},\ldots x_{jk},\ldots x_{pk}\}\) is also derived, where \(p\) is 5 in Table 2. The matrix-based structure is of the following form:  
\[\mathbf{X}=\left[ \begin{array}{ccc}x_{11}&\ldots&x_{p1}\\ \vdots&x_{jk}&\vdots\\ x_{1n}&\ldots&x_{pn}\end{array} \right] \tag{1}\]  
Moreover, \(c\) denotes the number of clusters. Specifically, with respect to each cluster, \(1\leq i\leq c\), and let \(\mathbf{y}_{i}\) denote each cluster. Different from [PERSON] et al. (2012), in order to increase the estimation accuracy, each cluster \(\mathbf{y}_{i}\) also is comprised of \(p\) attributes, and each attribute denotes the cluster centroid. Thus, it is easily obtained that \(\mathbf{y}_{i}=\left\{y_{1i},y_{2i},\ldots y_{ji},\ldots y_{pi}\right\}\). Different from the K-means clustering algorithm, one of the features of the fuzzy C-means algorithm is the membership degree \(u(\mathbf{x}_{k},y_{ji})\), which represents how close it is between \(\mathbf{x}_{\mathbf{k}}\) and cluster centroid \(y_{ji}\). The indicator used to distinguish the membership degree is the distance \(d(\mathbf{x}_{\mathbf{k}},y_{ji})\). Note that when \(t\) in the Formula (3) is 1, the distance is the Manhattan distance; when \(t\) is 2, the distance is the Euclidean distance. Due to the membership degree and the distance, the objective function of the FCM should be comprised of both simultaneously, which is shown in Formula (2). The distance between any point and the cluster centroid is calculated by Formula (3). The membership degree is calculated by Formula (4). The sum of the membership degree of each \(\mathbf{x}_{\mathbf{k}}\) should be equal to one, which is shown in Formula (5). When the difference between the new membership degree \(u(\mathbf{x}_{\mathbf{k}},y_{ji})^{*}\) and the old membership degree \(u(\mathbf{x}_{\mathbf{k}},y_{ji})\) is larger than the threshold \(\varepsilon\), the new cluster centroid should be updated by Formula (6). When the optimal cluster centroids are finally obtained, the missing values can be obtained by Formula (7).