AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Tsinghua University (Science and Technology) Article
PDF (5.3 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Publishing Language: Chinese

Distribution consistency-based missing value imputation algorithm for large-scale data sets

Jiayin YU1, Yulin HE1,2( ), Laizhong CUI1,2, Zhexue HUANG1,2
Big Data Institute, College of Computer Science & Software Engineering, Shenzhen University, Shenzhen 518060, China
Guangdong Laboratory of Artificial Intelligence and Digital Economy(SZ), Shenzhen 518107, China
Show Author Information

Abstract

Objective

As a significant research branch in the field of data mining, missing value imputation (MVI) aims to provide high-quality data support for the training of machine learning algorithms.However, MVI results for large-scale data sets are not ideal in terms of restoring data distribution and improving data prognosis accuracy.To improve the performance of the existing MVI algorithms, we propose a distribution consistency-based MVI (DC-MVI) algorithm that attempts to restore the original data structure by imputing the missing values for large-scale data sets.

Methods

First, the DC-MVI algorithm developed an objective function to determine the optimal imputation values based on the principle of probability distribution consistency.Second, the data set is preprocessed by random initialization of missing values and normalization, and a feasible missing value update rule is derived to obtain the imputation values with the closest variance and the greatest consistency with the complete original values.Next, in a distributed environment, the large-scale data set is divided into multiple groups of random sample partition (RSP) data blocks with the same distribution as the entire data set by taking into account the statistical properties of the large-scale data set.Finally, the DC-MVI algorithm is trained in parallel to obtain the imputation value corresponding to the missing value of the large-scale data set and preserve distribution consistency with the non-missing values.The rationality experiments verify the convergence of the objective function and the contribution of DC-MVI to distribution consistency.In addition, the effectiveness experiments assess the performance of DC-MVI and eight other MVI algorithms (mean, KNN, MICE, RF, EM, SOFT, GAIN, and MIDA) through the following three indicators: distribution consistency, time complexity, and classification accuracy.

Results

The experimental results on seven selected large-scale data sets showed that: 1) The objective function of the DC-MVI method was effective, and the missing value update rule was feasible, allowing the imputation values to remain stable throughout the adjustment process; 2) the DC-MVI algorithm obtained the smallest maximum mean discrepancy and Jensen-Shannon divergence on all data sets, showing that the proposed method had a more consistent probability distribution with the complete original values under the given significance level; 3) the running time of the DC-MVI algorithm tended to be stable in the time comparison experiment, whereas the running time of other state-of-the-art MVI methods increased linearly with data volume; 4) the DC-MVI approach could produce imputation values that were more consistent with the original data set compared to existing methods, which was beneficial for subsequent data mining analysis.

Conclusions

Considering the peculiarities and limitations of missing large-scale data, this paper incorporates RSP into the imputation algorithm and derives the update rules of imputation values to restore the data distribution and further confirm the effectiveness and practical performance of DC-MVI in the large-scale data set imputation, such as preserving distribution consistency and increasing imputation quality.The method proposes in this paper achieves the desired result and represents a viable solution to the problem of large-scale data imputation.

Keywords

large-scale datadistributed computingword information processingmissing value imputationdistribution consistencymaximum mean discrepancyrandom sample partition
CLC number: TP391.1 Document code: A Article ID: 1000-0054(2023)05-0740-14

References

[1]

SCHEET P, STEPHENS M. A fast and flexible statistical model for large-scale population genotype data: Applications to inferring missing genotypes and haplotypic phase[J]. The American Journal of Human Genetics, 2006, 78(4): 629-644.
Crossref Google Scholar
[2]

JEREZ J M, MOLINA I, GARCÍA-LAENCINA P J, et al. Missing data imputation using statistical and machine learning methods in a real breast cancer problem[J]. Artificial Intelligence in Medicine, 2010, 50(2): 105-115.
Crossref Google Scholar
[3]
YUAN H W, XU G M, YAO Z J, et al. Imputation of missing data in time series for air pollutants using long short-term memory recurrent neural networks[C]// Proceedings of the 2018 ACM International Joint Conference and 2018 International Symposium on Pervasive and Ubiquitous Computing and Wearable Computers. Singapore: ACM, 2018: 1293-1300.
Crossref
[4]

VAN BUUREN S, GROOTHUIS-OUDSHOORN K. MICE: Multivariate imputation by chained equations in R[J]. Journal of Statistical Software, 2011, 45(3): 1-67.
Crossref Google Scholar
[5]

NGUYEN C D, CARLIN J B, LEE K J. Model checking in multiple imputation: An overview and case study[J]. Emerging Themes in Epidemiology, 2017, 14(1): 1-12.
Crossref Google Scholar
[6]

ZHANG Z H. Missing data imputation: Focusing on single imputation[J]. Annals of Translational Medicine, 2016, 4(1): 9.
Google Scholar
[7]
KHOSRAVI P, LIANG Y T, CHOI Y J, et al. What to expect of classifiers? Reasoning about logistic regression with missing features[C]// Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19). Macao, China: IJCAI, 2019: 2716-2724.
Crossref
[8]

SEFIDIAN A M, DANESHPOUR N. Missing value imputation using a novel grey based fuzzy c-means, mutual information based feature selection, and regression model[J]. Expert Systems with Applications, 2019, 115: 68-94.
Crossref Google Scholar
[9]

ZHU X F, ZHANG S C, JIN Z, et al. Missing value estimation for mixed-attribute data sets[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(1): 110-121.
Crossref Google Scholar
[10]

LIU X W, ZHU X Z, LI M M, et al. Multiple kernel k-means with incomplete kernels[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020, 42(5): 1191-1204.
Google Scholar
[11]

CHEN X Y, YANG J M, SUN L J. A nonconvex low-rank tensor completion model for spatiotemporal traffic data imputation[J]. Transportation Research Part C: Emerging Technologies, 2020, 117: 102673.
Crossref Google Scholar
[12]

ZHU Y M, LI Z, ZHU H Z, et al. A compressive sensing approach to urban traffic estimation with probe vehicles[J]. IEEE Transactions on Mobile Computing, 2013, 12(11): 2289-2302.
Crossref Google Scholar
[13]

YU J R, STETTLER M E J, ANGELOUDIS P, et al. Urban network-wide traffic speed estimation with massive ride-sourcing GPS traces[J]. Transportation Research Part C: Emerging Technologies, 2020, 112: 136-152.
Crossref Google Scholar
[14]

HUANG J L, KEUNG J W, SARRO F, et al. Cross-validation based K nearest neighbor imputation for software quality datasets: An empirical study[J]. Journal of Systems and Software, 2017, 132: 226-252.
Crossref Google Scholar
[15]
AL-HELALI B, CHEN Q, XUE B, et al. A hybrid GP-KNN imputation for symbolic regression with missing values[C]// Australasian Joint Conference on Artificial Intelligence. Cham: Springer, 2018: 345-357.
Crossref
[16]

CHOUDHURY S J, PAL N R. Imputation of missing data with neural networks for classification[J]. Knowledge-Based Systems, 2019, 182: 104838.
Crossref Google Scholar
[17]
YOON J, JORDON J, VAN DER SCHAAR M. GAIN: Missing data imputation using generative adversarial nets[C]// Proceeding of the 35th International Conference on Machine Learning. Stockholm, Sweden: PMLR, 2018: 5689-5698.
[18]

MA Q, LEE W C, FU T Y, et al. MIDIA: Exploring denoising autoencoders for missing data imputation[J]. Data Mining and Knowledge Discovery, 2020, 34(6): 1859-1897.
Crossref Google Scholar
[19]

LIN W C, TSAI C F, ZHONG J R. Deep learning for missing value imputation of continuous data and the effect of data discretization[J]. Knowledge-Based Systems, 2022, 239: 108079.
Crossref Google Scholar
[20]
HE K M, CHEN X L, XIE S N, et al. Masked autoencoders are scalable vision learners[C]// 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition. New Orleans, USA: IEEE, 2022: 16000-16009.
Crossref
[21]

BADSHA M B, LI R, LIU B X, et al. Imputation of single-cell gene expression with an autoencoder neural network[J]. Quantitative Biology, 2020, 8(1): 78-94.
Crossref Google Scholar
[22]

BANSAL P, DESHPANDE P, SARAWAGI S. Missing value imputation on multidimensional time series[J]. Proceedings of the VLDB Endowment, 2021, 14(11): 2533-2545.
Crossref Google Scholar
[23]

MENG X F, CI X. Big data management: Concept, techniques and challenge[J]. Journal of Computer Research and Development, 2013, 50(1): 146-169. (in Chinese)
Google Scholar
[24]

CHEN M, MAO S, ZHANG Y, et al. Big data storage[M]. Cham: Springer, 2014: 33-49.
Crossref
[25]
SHVACHKO K, KUANG H R, RADIA S, et al. The hadoop distributed file system[C]// 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST). Incline Village, USA: IEEE, 2010: 1-10.
Crossref
[26]
DEAN J, GHEMAWAT S. MapReduce: Simplified data processing on large clusters[C]// Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation. San Francisco, USA: ACM, 2004: 137-150.
[27]

HUANG Z X, HE Y L, WEI C H, et al. Random sample partition data model and related technologies for big data analysis[J]. Journal of Data Acquisition and Processing, 2019, 34(3): 373-385. (in Chinese)
Crossref Google Scholar
[28]

STRIKE K, EL-EMAM K, MADHAVJI N. Software cost estimation with incomplete data[J]. IEEE Transactions on Software Engineering, 2001, 27(10): 890-908.
Crossref Google Scholar
[29]

ZHANG S C, QIN Z, LING C X, et al. "Missing is useful": Missing values in cost-sensitive decision trees[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(12): 1689-1693.
Crossref Google Scholar
[30]

LITTLE R J A, RUBIN D B. Statistical analysis with missing data[M]. Hoboken: John Wiley & Sons, 2019.
Crossref
[31]

MORRIS T P, WHITE I R, ROYSTON P. Tuning multiple imputation by predictive mean matching and local residual draws[J]. BMC Medical Research Methodology, 2014, 14(1): 75.
Crossref Google Scholar
[32]

LI D W, ZHANG H Q, LI T R, et al. Hybrid missing value imputation algorithms using fuzzy C-means and vaguely quantified rough set[J]. IEEE Transactions on Fuzzy Systems, 2022, 30(5): 1396-1408.
Crossref Google Scholar
[33]

REZVAN P H, LEE K J, SIMPSON J A. The rise of multiple imputation: A review of the reporting and implementation of the method in medical research[J]. BMC Medical Research Methodology, 2015, 15(1): 30.
Crossref Google Scholar
[34]

HUGHES R A, HERON J, STERNE J A C, et al. Accounting for missing data in statistical analyses: Multiple imputation is not always the answer[J]. International Journal of Epidemiology, 2019, 48(4): 1294-1304.
Crossref Google Scholar
[35]

ZHANG S C. Nearest neighbor selection for iteratively KNN imputation[J]. Journal of Systems and Software, 2012, 85(11): 2541-2552.
Crossref Google Scholar
[36]
KEERIN P, KURUTACH W, BOONGOEN T. Cluster-based KNN missing value imputation for DNA microarray data[C]// 2012 IEEE International Conference on Systems, Man, and Cybernetics (SMC). Korea: IEEE, 2012: 445-450.
Crossref
[37]
VINCENT P, LAROCHELLE H, BENGIO Y, et al. Extracting and composing robust features with denoising autoencoders[C]// Proceedings of the 25th International Conference on Machine Learning. Helsinki, Finland: ACM, 2008: 1096-1103.
Crossref
[38]
GONDARA L, WANG K. MIDA: Multiple imputation using denoising autoencoders[C]// Proceeding of the 22nd Pacific-Asia Conference on Knowledge Discovery and Data Mining. Melbourne, Australia: Springer, 2018: 260-272.
Crossref
[39]

SOVILJ D, EIROLA E, MICHE Y, et al. Extreme learning machine for missing data using multiple imputations[J]. Neurocomputing, 2016, 174: 220-231.
Crossref Google Scholar
[40]

LU C B, MEI Y. An imputation method for missing data based on an extreme learning machine auto-encoder[J]. IEEE Access, 2018, 6: 52930-52935.
Crossref Google Scholar
[41]

GARCÍA J C F, KALENATIC D, BELLO C A L. Missing data imputation in multivariate data by evolutionary algorithms[J]. Computers in Human Behavior, 2011, 27(5): 1468-1474.
Crossref Google Scholar
[42]

ZHANG Y, ZHOU B H, CAI X R, et al. Missing value imputation in multivariate time series with end-to-end generative adversarial networks[J]. Information Sciences, 2021, 551: 67-82.
Crossref Google Scholar
[43]

DEMPSTER A P, LAIRD N M, RUBIN D B. Maximum likelihood from incomplete data via the EM algorithm[J]. Journal of the Royal Statistical Society: Series B (Methodological), 1977, 39(1): 1-22.
Crossref Google Scholar
[44]

RAHMAN M G, ISLAM M Z. Missing value imputation using a fuzzy clustering-based EM approach[J]. Knowledge and Information Systems, 2016, 46(2): 389-422.
Crossref Google Scholar
[45]

GOLD M S, BENTLER P M. Treatments of missing data: A Monte Carlo comparison of RBHDI, iterative stochastic regression imputation, and expectation-maximization[J]. Structural Equation Modeling: A Multidisciplinary Journal, 2000, 7(3): 319-355.
Crossref Google Scholar
[46]
KURUCZ M, BENCZU'R A A, CSALOGÁNY K. Methods for large scale SVD with missing values[C]// Proceedings of KDD Cup and Workshop. San Jose, USA: ACM, 2007, 12: 31-38.
[47]

MAZUMDER R, HASTIE T, TIBSHIRANI R. Spectral regularization algorithms for learning large incomplete matrices[J]. The Journal of Machine Learning Research, 2010, 11: 2287-2322.
Google Scholar
[48]

ZHU X S, WANG J Y, SUN B, et al. An efficient ensemble method for missing value imputation in microarray gene expression data[J]. BMC Bioinformatics, 2021, 22(1): 188.
Crossref Google Scholar
[49]
PETROZZIELLO A, JORDANOV I, SOMMEREGGER C. Distributed neural networks for missing big data imputation[C]// 2018 International Joint Conference on Neural Networks (IJCNN). Rio de Janeiro, Brazil: IEEE, 2018: 1-8.
Crossref
[50]

HE Y L, HUANG D F, DAI D X, et al. General bounds for maximum mean discrepancy statistics[J]. Mathematica Applicata, 2021, 34(2): 284-288. (in Chinese)
Google Scholar
[51]

GRETTON A, BORGWARDT K M, RASCH M J, et al. A kernel two-sample test[J]. The Journal of Machine Learning Research, 2012, 13(1): 723-773.
Google Scholar
[52]

TANG F, ISHWARAN H. Random forest missing data algorithms[J]. Statistical Analysis and Data Mining: The ASA Data Science Journal, 2017, 10(6): 363-377.
Crossref Google Scholar
[53]
OpenIDEA-Yunan University, Ycimpute[EB/OL]. (2020-08-23)[2022-09-25]. https://github.com/OpenIDEA-YunanUniversity/ycimpute.
[54]
RUBINSTEYN A, FELDMAN S. Fancyimpute: An imputation library for python[EB/OL]. (2021-10-22)[2022-09-25]. https://github.com/iskandr/fancyimpute.
[55]
UC Irvine Machine Leaning Repository. UCI machine learning repository[EB/OL]. (2021-05-02)[2022-09-25]. http://archive.ics.uci.edu/ml.
[56]

TRIGUERO I, GONZÁLEZ S, MOYANO J M, et al. KEEL 3.0: An open source software for multi-stage analysis in data mining[J]. International Journal of Computational Intelligence Systems, 2017, 10(1): 1238-1249.
Crossref Google Scholar
[57]

WHITE I R, ROYSTON P, WOOD A M. Multiple imputation using chained equations: Issues and guidance for practice[J]. Statistics in Medicine, 2011, 30(4): 377-399.
Crossref Google Scholar
Journal of Tsinghua University (Science and Technology)
Volume 63 Issue 5,
May 2023
Pages 740-753
DOI: 10.16511/j.cnki.qhdxxb.2023.25.003
Cite this article:
YU J, HE Y, CUI L, et al. Distribution consistency-based missing value imputation algorithm for large-scale data sets. Journal of Tsinghua University (Science and Technology), 2023, 63(5): 740-753. https://doi.org/10.16511/j.cnki.qhdxxb.2023.25.003

119

Views

3

Downloads

0

Crossref

0

Scopus

2

CSCD

Altmetrics
Received: 25 September 2022
Published: 15 May 2023
© Journal of Tsinghua University (Science and Technology). All rights reserved.
Return