A Spatial Missing Value Imputation Method for Multi-view Urban Statistical Data

1 Introduction

Urban statistic data connect social sciences, urban computing, administrative management, transportation, and regional planning that are significant for city development [Murgante and Danese, 2011; Zheng et al., 2014; Gong et al., 2020]. These statistical data usually include multi-fold views (e.g., views of Population and Economy) to reveal the growth gaps among different administrative regions from various perspectives. For example, the economy view records the key economic indicators for fine-grained regions, such as the number of industries and employee statistics; and the population view consists of detailed population information of all age groups in each region.

The statistic data provide key statistics to governments, business and the community on social science, for the benefit of all aspects of human life.

However, in some places, statistical data are hard to be entirely acquired due to document defacement, error recordings, and statistician misplay. Such missing data hide useful information which may cause distorted results for further analysis. To the best of our knowledge, it is still a blank field concerning this specific problem, but the real demand appears. Hence, the missing value imputation for urban statistical data is a vital task for reliable urban computing and government services.

∗Corresponding Author

In this paper, we study the problem of missing-data imputation for the Australian Bureau of Statistics (ABS), which has some unique challenges:

• Missing temporal information. In the real-world data from ABS, almost all the missing values in the current year were also missing in the past years, which may be caused by the region restriction and complicated human-made errors. This violates the basic assumption of matrix completion [Cand`es and Recht, 2009] that the unobserved entries are sampled uniformly at random. Thus matrix completion-based approaches may not work in this case.
• Multi-view problem. The complicated underlying interactions suggest that simply recovering the missing information without considering the correlations among attributes and multi-modes will end up with a poor performance. For example, the economy view has strong correlations with the income and population views, so that a high-quality economy in a region usually goes along with a better income and a larger population; and a low-level economy in a region has a high probability of being connected with a lower income and a smaller population.
• Spatial correlation mining problem. As illustrated in Fig-

ure 1, the statistical data focusing on fine-grained regions may change over locations significantly and non-linearly. Therefore, to properly recover the missing information of statistical data, we need to consider the regional similarities.

To date, a number of missing data imputation approaches are applied in urban statistical data, e.g., mean-filling (MF), k-nearest-neighbor (KNN) filling [Pan and Li, 2010], and collaborative filtering based methods [Ranjbar et al., 2015]. Most of them, however, have been proposed to focus on the single view problem. Besides, although several spatiotemporal methods can infer the missing information based on the knowledge from both spatial and temporal domains [Yi et al., 2016; Cheng and Lu, 2017; Zhou and Huang, 2018], they do not perform well when the missing temporal information challenge appears. To address all challenges, our proposed method is designed as a spatially related method which can only use spatial information to achieve a strong performance. In detail, the method integrates a spatial multi-kernel clustering method and an adaptive-weight non-negative matrix factorization (NMF) for solving the multi-view spatially related tasks. We summarize the main contributions and innovations of this paper as follows:

• To handle the multi-view problem with spatial characteristic, we propose a Spatially related Multi-Kernel KMeans (S-MKKM) method to identify the underlying relationships among multiple views and capture the regional similarities.
• We propose an adaptive-weight non-negative matrix factorization approach to leverage the information learned above to tackle the multi-view missing data imputation problem. Besides, the proposed method also takes the guidance from the single-view and the real geographic information with KNN strategy into consideration.
• A spatial multi-view missing data imputation method for urban statistical data based on non-negative matrix factorization is proposed, called SMV-NMF. SMV-NMF does not rely on the temporal information but achieves a great performance only using spatial information.
• Our experiments on six real-world datasets verify the effectiveness of our method. All the empirical results show that the proposed method SMV-NMF outperforms all the other state-of-the-art approaches. Furthermore, SMV-NMF shows strong generalizability and can transfer the constructed model from one urban dataset to another well.

2 RelatedWork

2.1 Spatial Missing Data Imputation

Missing data imputation is a significant task for data analysis [Van Buuren, 2018]. In the spatially related problem, neighborhood and collaborative filtering [Su and Khoshgoftaar, 2009; Yi et al., 2016] based methods are two kinds of dominant approaches in missing data filling. Although some classical methods (e.g., zero-filling, mean value filling, regression models) can be applied to the spatial missing data imputation, they have disadvantages in nature, i.e, they are not designed for this spatial problem. [Chen and Liu, 2012]

used the inverse distance weighting (IDW) method to interpolate the spatial rainfall distribution. [Wu and Li, 2013] utilized the spatial information as inputs in a residual kriging method to estimate the average monthly temperature. Unlike the spatial model, some successful spatio-temporal models were proposed for use with time stream data [Yi et al., 2016; Cheng and Lu, 2017; Zhou and Huang, 2018; Atluri et al., 2018]. However, they focused on filling missing entries by considering both spatial and temporal properties, and would not perform well on the static spatial data without the temporal information. Furthermore, these discussed methods leveraged the spatial guidance but did not consider the problem on multi-view datasets.

2.2 Multi-view Learning

Multi-view learning methods involved the diversity of different views that can jointly optimize functions based on various feature subsets [Singh and Gordon, 2008; Li et al., 2018]. [Xu et al., 2015] proposed a matrix co-factorization based method (MVL-IV) to embed different views into a shared subspace, such that the incomplete views can be estimated by the information on observed views. To connect multiple views, MVL-IV assumes that different views have distinct 'feature' matrices (i.e., {Hi}di=1 ), but correspond to the same coefficient matrix (i.e., W). However, it does not exploit the spatial correlations and may suffer from the imbalance problem, i.e., if there is a substantial missing ratio gap between views, the coefficient matrix W is mostly learned from the dense view. In our method, we have addressed this weakness by introducing guidance matrices. Another widely used strategy for solving the multi-view problem is tensor factorization [Rendle et al., 2009; Xiong et al., 2010], but this restricts a regular tensor that requires the number of dimensions per view to be the same. Moreover, multiple kernel learning with incomplete views [Trivedi et al., 2010; Liu et al., 2017] only focuses on completing missing kernels instead of filling missing values. To the best of our knowledge, none of the above studies considered both spatial and multi-view problems. Hence, in this paper, we proposed an effective missing value imputation model for multi-view urban statistical data.

3 The ProposedMethod

3.1 ProblemDescription and Preliminary

As illustrate in Figure 2, this research focuses on completing the missing values in the urban statistical data, where one urban dataset contains multiple views, e.g., Income, Population, Economy views, etc. For a dataset with n regions (r1,...,rn) and d views, the dimension of attributes in the p-th view is mp (1 ≤ p ≤ d). Our method aims to impute the missing values with a high accuracy.

Multi-view NMF

The multi-view NMF aims to learn a latent subspace W ∈ Rn×k + by multiple views {X1...Xd} through the multi-view generation matrices Hp ∈ Rk×mp + . The basic missing data imputation model can be described as the following optimization objective:

where Yp are indicator matrices whose entry Yp(i, j) is one if Xp(i, j) has been recorded (for observed values) and zero otherwise (for missing values); and ⊙ is the Hadamard product operator.

Multiple Kernel K-means (MKKM)

Let {xi}ni=1 be a collection of n samples (region), xi represents the statistical features of the i-th region, and φp(·) be the p-th view mapping that maps x onto the p-th reproducing kernel Hilbert space. In this case, each sample has multiple feature representations defined by a group of feature mappings φβ(xi) = [β1φ1(xi)⊤, · · · , βdφd(xi)⊤]⊤, where β consists of the coefficients of the d base kernels. A kernel function can be expressed as κβ(xi, xj) = φβ(xi)⊤φβ(xj) = ∑dp=1 β2 p κp(xi, xj). And a kernel matrix Kβ is then calculated by applying the kernel function κβ(·, ·) to {xi}ni=1 . Based on the kernel matrix Kβ, the objective of MKKM can be written as:

where V is the clustering matrix; 1d ∈ Rd is a column vector with all 1 elements; In and Il are identity matrices with size n and l; l is the number of clusters.

3.2 Multi-view Spatial Similarity Guidance

As discussed in Section 2.2, multi-view matrix factorization based methods suffer from the imbalance problem. In this paper, we build the similarity guidance Xmv p for the p-th view Xp to address this problem. Accordingly, we propose an approach to obtain regional similarities via the spatially related MKKM model, called S-MKKM. The basic idea is that the development of a city gradually fosters different functional groups, such as educational and business districts, where the regions belonging to the same group would have strong connections with each other [Zheng et al., 2014]. S-MKKM utilizes the MKKM clustering algorithm combined with a graph Laplacian dynamics strategy (an effective smoothing approach for finding spatial structure similarity [Deng et al., 2016; Gong et al., 2018]) to cluster regions into the functional groups. Specifically, we construct a graph Laplacian matrix L, defined as L = D -M, where M is a graph proximity matrix that is constructed from the regional physical topology (i.e., M(i,j) = 1 if and only if the region xi is contiguous to xj), and D is a diagonal matrix D(i,i) = ∑j (M(i,j)). With this constraint, the S-MKKMmodel is expressed as follows:

where α is the regularization parameter; V is the consensus clustering matrix.

To get the complete kernels, we initially impute the missing data for each view by a simple method, such as KNN or MF. After that, Eq. (3) can be solved by alternately updating V and β: i) With the kernel coefficients β fixed, V can be obtained by choosing the l smallest eigenvectors of (-Kβ +αL). ii) With V fixed, β can be optimized via solving the quadratic programming with linear constraints [Liu et al., 2017].

The objective of the S-MKKM is to discover the regions with similar properties and build the guidance matrices Xmv p . After having gotten V , Xmv p can be built. Figure 3 shows an example of this process. The construction process of Xmv p is that i) for the unknown entry xij, and the region xi ∈ c-th cluster, we use its corresponding value xc(i),j from the centroid region to impute xij; ii) if the corresponding value of centroid region is also missed, a greedy strategy will be used to find the nearest observed value for imputation.

3.3 Adaptive-Weight NMF

To learn the knowledge fromXmv p more reliably, we propose an adaptive weighting strategy in the NMF imputation process. The adaptive-weight matrix of the p-th view is denoted as Zp ∈ Rn×mp + , which is built by an exponential function as shown in Eq. (4) and (5).

where Dist(·, ·) is the Euclidean distance calculating from the geo-location (vi) and its corresponding centroid region (vc(i)), here we use the latent embedding vi to represent the geo-location of region i, and vc(i) represents the centroid of the c-th cluster which contains region vi; zp ∈ Rn+ is a column vector and 1mp is all-ones vector with size mp. It is not a straight way for imputation, but the adaptive-weight matrix Zp controls how much information can be extracted. Zp adjusts the penalty of each estimated entry. As emphasised in the First Law of Geography [Tobler, 1970], the near things have more spatial correlations than distant things. If the distance between xi and xc(i) is small, we want a high penalty to guide the imputation process.

Combining the above strategy, our model can be described as the following optimization function:

where ¯ Yp = 1 - Yp, 1 is an all one matrix that has the same size as Yp; Xmv p is a homomorphic matrix of Xp; and λ1 is the regularization parameter to control the learning rate of Xmv p .

3.4 Improved by Single-view and KNNGuidances

S-MKKM aims to find the regional groups by considering multiple views simultaneously. However, it is obvious that each view has its characteristics, and the relationships between regions in one specific view are also critical for imputing missing entries. To consider the above knowledge, we apply the spatially related kernel k-means (S-KKM) to capture the similarities among regions of each view. It is essentially analogous to the learning process of S-MKKM as discussed in section 3.2, but considering each view, respectively. For one viewXp, the S-KKMmodel is expressed as follows:

where Kp is one separate kernel and Vp represents the p-th clustering matrix based on Xp.

In fact, to reduce the complexity of our model, we assume that the physical location affects the clustering performance with the same degree and the number of clusters is the same as that in S-MKKM, i.e., l and α are the same as used in Eq. (3). The reason behind this assumption is that most cities have the same functional regions, such as the residential region and business region. Thus, it is reasonable that we choose the same α and l in this practical task. Besides, α and l are very stable due to the intrinsic property of the urban statistical data, and we fixed them in the experiments. The single view guidance matrix Xsv p and adaptive-weight matrix Z′p can be constructed by the same strategy of building Xmv p and Zp.

Furthermore, for each region, its k-nearest spatial neighbors imply rich information that should be considered in our model. Even though the regional physical topology is already involved in multi-view and single-view learning processes, the KNN is a more flexible method. After structuring Xknn p which is an imputed matrix with the average value of k-nearest neighbors, our final optimization function is shown as follows:

where λ2 and λ3 are the regularization parameters to control the learning rate of Xsv p andXknn p , respectively.

Given the estimated factor matrices W and Hp based on the above update equations, the filled data are given by:

3.5 Learning Algorithm

As Eq. (8) is a non-convex problem, we use the multiplicative update strategy [Lee and Seung, 2001] to ensure the convergence under the following update rules. We first initialize latent space matrices (W and Hp) by decomposing data matrices {X1...Xd}. The update rules for W and Hp are presented in Eq. (10) - (11).

The above two multiplicative update rules guarantee to be non-negative if the initialization is positive. Without this constraint, the matrices W and Hp could be negative, thus the imputation results could be negative too, which is a contradiction to the facts. The process of SMV-NMF is summarized in Algorithm 1.

Time complexity and convergence. We discuss the time complexity and convergence of SMV-NMF here. The time complexity of guidance matrices Xmv p and Xsv p is mainly affected by MKKM. Even though MKKM has a high computational complexity (O(n3 )), it is not involved in update loop of variables (W andHp). Eq. (10) and Eq. (11) present that the time complexity of our final function is governed by matrix multiplication operations in each iteration. Therefore, the

Algorithm 1: SMV-NMF

Input: original data {Xp }; graph Laplacian matrix L.

Output: complete data { ˆ Xp}.

• 1 Impute Xp by KNN for an initialization.
• 2 InitializeW andHp by decomposingXp.
• 3 Construct Xmv p , Xsv p andXknn p by S-MKKM, S-KKM, and KNN respectively.

4 for t = 1 to T do

10 Return ˆ Xp By Eq. (9).

time complexity per iteration is dominated by O(nk2 ). Due to the pursuing of pinpoint accuracy, we sacrifice efficiency to some degree in this real-world problem. In terms of convergence, Algorithm 1 is guaranteed to converge when W or Hp is fixed, because the second-order derivatives regarding W or Hp are positive semi-definite. Thus, the objective function can achieve its optimal value by optimizing W and Hp alternately.

4 Experiments

In this paper, we have conducted complete experiments to demonstrate the effectiveness of our method 1 .

4.1 Datasets

There are six real-world urban statistical datasets (Sydney, Melbourne, Brisbane, Perth, SYD-large, and MEL-large), where -large datasets contain much more fine-grained regions from Australian Bureau of Statistics (2017). Each dataset contains four views, i.e., Economy, Family, Income, and Population. The size of the six datasets are 174, 284, 220, 130, 2230, 1985 respectively. The designation of regions is based on the Australian Statistical Geography Standard for the best practical value. The scales of different views are normalized into the same range [0,10] so that we can evaluate the results together. The numbers of the dimension of the four views are 43, 44, 50, 97, respectively. We choose Australian cities mostly because the Australian Bureau of Statistics provides enough data for our study, while such data from other countries is inaccessible to us. However, our method is general enough and can be applied to other cities with administrative areas and statistical census data. To guarantee the diversity of testing, for each missing ratio, we randomly select the test columns and repeat the experiment 20 times and report average results.

1 The strict proof, resource code, and parameters used to achieve the best performance on different datasets are shown in the https://github.com/SMV-NMF/SMV-NMF.

4.2 Baselines &Measures

Baselines

We compare the proposed method SMV-NMF with the following 12 baselines. All parameters of the proposed method and baselines are optimized by the grid search method.

sKNN: A classical method that uses the average values of its k nearest spatial neighbors as an estimate (k=6).

MKKMIKa ; MKKMIKb: A MKKM based method to handle the incomplete views [Liu et al., 2017]. We modified it to adapt to the spatially related data, then interpolated a missing value by its k nearest spatial neighbors (k=6); Utilize the mean value of each cluster to fill the missing data.

NMF: Fill the missing data by NMF.

IDW: A global spatial learning method compared in many works [Chen and Liu, 2012; Cheng and Lu, 2017].

• UCF: The Local spatial learning method based on collaborative filtering [Su and Khoshgoftaar, 2009; Yi et al., 2016].

IDW+UCF: The average result of IDW and UCF.

• MVL-IV: A state-of-the-art multi-view learning method based on matrix co-factorization, which learns a same coefficient matrix to connect multiple views [Xu et al., 2015].
• ST-MVL: A state-of-the-art method to impute spatiotemporal missing data [Yi et al., 2016]. We only use its spatial part due to the problem of missing temporal information.
• SMV-MF; MV-NMFa ; MV-NMFb: Remove the nonnegativity constraint in SMV-NMF; Remove the graph Laplacian dynamics strategy in SMV-NMF when building the Xmv p andXsv p ; Remove the KNN guidance in SMV-NMF.

Measures. We utilized the most widely used evaluation metrics in our paper, namely Mean Relative Error (MRE) and Root Mean Square Error (RMSE).

where ˆui is a prediction for missing value, and ui is the ground truth; Q is the number of prediction values.

4.3 Results on Urban Statistical Datasets

The first set of experiments is designed to assess performance on each dataset. We pick up half of statistical fields (properties) in each urban dataset randomly as the validation set, and the other half as the test set. In the test set, we randomly select missing ratios from 10% to 70% to evaluate the imputation accuracy.

Table 1 presents the average errors of all missing ratios across different test methods. It is clear show that our approaches (SMV-MF, MV-NMFa , MV-NMFb , SMV-NMF) perform much better than other baselines across different missing ratios on six real-world datasets, where SMV-NMF achieves the best results. Without the non-negativity constraint, SMV-MF performs worse than SMV-NMF, which demonstrates the effectiveness of this constraint. MVL-IV yields better results than ST-MVL, MKKMIKa , IDW+UCF, and NMF becuase it considers the multi-view problem.

To represent our results more clearly, we pick the top eight methods varying different missing ratios on the Sydney dataset, which is shown in Figure 4. It is apparent that NMF

is sensitive to the missing ratio, which could get good results under the lower level missing ratios, but performs worse when the missing ratio increases. Our methods, (SMV-MF, MVNMFa , MV-NMFb , SMV-NMF) have significant improvements compared with current baselines.

Overall, SMV-NMF outperforms the other baselines because it integrates both multi-view and spatial problems to address the specified missing data imputation task. MV-NMFa and MV-NMFb remove a part of the spatial guidance which results in slightly worse performances than SMV-NMF.

4.4 Generalizability Test

We conduct experiments on testing the generalizability in this section. In detail, we choose the dataset Sydney as the validation set and two urban datasets (Melbourne and Brisbane) as the test sets. We report the experimental results on eight available algorithms. SMV-NMF is the most outstanding approach, as shown in Figure 5.

Our method represents strong generalizability which can transfer the constructed model from one urban dataset to another. This is because there are high correlations among cities. For example, the number of functional regions of each city is mostly the same, resulting in the same amount of clusters. The gap between SMV-NMF and MVL-IV narrows as the missing ratio increases, but the former is more robust than the latter because SMV-NMF achieves the best results across all missing ratios. Table 2 reveals the average errors using two evaluation metrics. The generality test demonstrates that our model SMV-NMF is a universal model that performs well crossing different urban statistical datasets.

5 Conclusion

In this paper, we propose a spatial missing data imputation method for multi-view urban statistical data, called SMVNMF. To address the multi-view problem, an improved spatial multi-kernel method is designed to guide the imputation process based on the NMF strategy. Moreover, the spatial correlations among different regions are involved in our method from two perspectives. Firstly, the latent similarities are discovered by S-MKKN and S-KKM based on the idea of finding functional regions, and secondly, KNN is used for capturing the information of real geographical positions. We conduct intensive experiments on six real-world datasets to compare the performance of our model and other state-of-the-art approaches. The results not only show that our approach outperforms all other methods, but also represent strong generalizabilities crossing different urban datasets.