تصحیح خودکار داده‌ها مبتنی بر وابستگی تابعی و سیستم یادگیری مرکب

نویسندگان

تهران - دانشگاه تربیت دبیر شهید رجایی - دانشکده مهندسی کامپیوتر

چکیده

صحت داده‌ها یکی از مهم‌ترین ابعاد کیفیت داده‌ها به‌شمارمی‌رود. با توجه به حجم بالای منابع داده‌ای نیاز به روش‌هایی خودکار وجود دارد. در این مقاله راهکاری خودکار برای تصحیح داده‌هایی با انواع داده‌ای متفاوت ارائه ‌شده ‌است. در این راهکار در ابتدا رکوردهایی که احتمالاً حاوی ویژگی خطا است با استفاده از وابستگی تابعی شناسایی‌می‌گردد، بدین‌صورت که رکوردی که به ازای یک وابستگی تابعی با بیش از  از رکوردها در تناقض باشد، مشکوک به خطا است. سپس به ازای هر ویژگی از منبع داده مورد بررسی، سیستم یادگیری مرکب ساخته‌می‌شود. سیستم یادگیری مرکب از سه طبقه‌بند بیز، درخت تصمیم و شبکه عصبی MLP تشکیل‌شده است و دارای استراتژی ترکیب رأی اکثریت است. سیستم یادگیری مرکب به‌وسیله رکوردهای صحیح شناسایی‌شده مورد آموزش قرارداده ‌می‌شود. پس از آموزش طبقه‌بندها، هر ویژگی غلط به‌عنوان کلاس هدف سیستم یادگیری‌مرکب قرارمی‌گیرد و مقداری برای آن پیش‌بینی‌می‌گردد. روش پیشنهادی قادراست چندین خطا در یک رکورد را شناسایی نماید. آزمایش‌ها نشان‌می‌دهد که true negative rate الگوریتم پیشنهادی در بخش تشخیص خطا به‌طور متوسط 93.7% و در بخش تصحیح خطا به‌طور متوسط 90.6% است. هم‌چنین آزمایش‌ها نشان‌می‌دهد که میزان پارامترهای ارزیابی در الگوریتم پیشنهادی در مقایسه با دو الگوریتم مشابه مبتنی بر وابستگی تابعی بهبود داشته است.

کلیدواژه‌ها

عنوان مقاله [English]

Automatic Data Cleaning using Functional Dependency and Ensemble Learning

نویسندگان [English]

  • M. Ataeyan
  • N. Daneshpour
Faculty of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran
چکیده [English]

Data accuracy is one of the important aspects of data quality. According to high volume of data sources an automatic method is required. In this article an automatic method is proposed for cleaning of data with various data types. Initially, records that may contain incorrect attributes are detected using functional dependency, so that each record that inconsistent more than  records for one functional dependency, probably is error. Thereafter ensemble learning is done for each attribute of data source. Ensemble learning contains 3 classifiar naïve bayes, decision tree and MLP, and voting is combination strategy. It is trained using correct records that identified in the initial steps. After training, each incorrect attribute is placed as target and predict values for it. Proposed method is able to clean data in data sources with different data types. Experiments show the true negative rate in detecting error part of the proposed algorithm is averagely 93.7% and in cleaning error part is averagely 90.6%. Also experiments show that evaluation parametrs are improved in proposed method compared with 2 similar methods.

کلیدواژه‌ها [English]

  • Data cleaning
  • error detection
  • functional dependency
  • ensemble learning

مراجع

[1] G. Rahman and Z. Islam, "Missing value imputation using decision trees and decision forests by splitting and merging records: Two novel techniques," Knowledge-Based Systems, vol. 53, pp. 51 – 65, 2013.
[2] W. Fan, F. Geerts, X. Jia and A. Kementsietsidis, "Conditional functional dependencies for capturing data inconsistencies," ACM Transactions on Database Systems (TODS), vol. 33, no. 2, pp. 1-48, 2008.
[3] P. H. WilliAMS, C. R. Margules, and D. W. Hilbert, "Data requirements and data sources for biodiversity priority area selection," Journal of biosciences, vol. 27, no. 4, pp. 327– 338, 2002.
[4] G. Rahman and Z. Islam, "Decision Tree-based Missing Value Imputation Technique for Data Pre-processing," Proceedings of the 9th Conference on Australasian Data Mining, pp. 41-50, Ballarat, Australia, 2011.
[5] X. Chu and I. F. Ilyas, "Qualitative Data Cleaning," The VLDB Journal, vol. 9, no. 13, pp. 1605 - 1608, 2016.
[6] L. Breiman, "Bagging predictors," Machine Learning, vol. 24, no. 2, pp.123-140, 1996.
[7] M. Yakout, L. Berti-Équill, and A. K. Elmagarmid, "Don’t be SCAREd: Use SCalable Automatic REpairing with Maximal Likelihood and Bounded Changes", Proceedings of the 13th International Conference on Management of Data, pp. 553-564, 2013.
[8] N. Tang, "Big Data Cleaning", Proceedings of the 16th International Conference on Web Technologies and Applications, pp.13-24, 2014.
[9] J. Hipp, U. Gu¨ntzer, and U. Grimmer, "Data quality mining-making a virute of necessity,"Proceedings of the 6th Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD), pp. 52-57, 2001.
[10] S. Bruggemann, "Rule Mining for Automatic Ontology Based Data Cleaning," Proceedings of the 10th International Conference on Asia-Pacific Web Conference Progress, pp. 522-527, 2008.
[11] C. He, Z. Tan, Q. Chen, C. Sha, Z. Wang, and W. Wang, "Repair Diversification for Functional Dependency Violations," Proceedings of the 19thInternational Conference on Database Systems for Advanced Applications, pp. 468-482, 2014.
[12] F. Chiang and R. J. Miller, "A Unified Model for Data and Constraint Repair," Proceedings of the 27th International Conference on Data Engineering, pp. 46-457, 2011.
[13] الناز زعفرانی معطر، محمدرضا فیضی درخشی و آزاده روحانی، »تشخیص هوشمند و خودکار غلط‌های تایپی در پایگاه داده‌های بزرگ بدون استفاده از لغت نامه«، مجله علمی پژوهشی مهندسی برق دانشگاه تبریز،  جلد 47 ، شماره 1، صفحات 81-91، 1396.
[14] مرتضی خرّم کشکولی و مریم دهقانی، »تشخیص، شناسایی و جداسازی عیب توربین گاز پالایشگاه دوم پارس جنوبی با استفاده از روش‌های ترکیبی داده کاوی، k-means، تحلیل مؤلفه‌های اصلی (PCA) و ماشین بردار پشتیبان (SVM) «، مجله علمی پژوهشی مهندسی برق دانشگاه تبریز،  جلد 47 ، شماره 2، صفحات 501-515، 1396.
[15]  یوکابد صدری، علی آقاگلزاده و مهدی ازوجی،»ادغام تصویر چندفوکوسه با استفاده از همدوسی فاز و خوشه‌بند« K-means ، مجله علمی پژوهشی مهندسی برق دانشگاه تبریز،  جلد 45 ، شماره 4، صفحات 115-125، 1394.
[16] M. Fijałkowska and B. Antoszewski, "Classification of congenital nasal deformities: a proposal to amend the existing classification, " European Archives of Oto-Rhino-Laryngology,vol. 274, no. 3, pp. 1231-1235.
[17] C. M. Teng, "Correcting Noisy Data," Proceedings of the 16th International Conference on Machine Learning, pp. 239-248, 1999.
[18] C. M. Teng, "A Comparison of Noise Handling Techniques," Proceedings of the 14th International Conference on Artificial Intelligence Research Society, pp. 269-273, 2001.
[19] C. M. Teng, "Polishing Blemishes: Issues in Data Correction," Intelligent Systems, vol. 19, no. 2, pp. 34-39, 2004.
[20] S. Kolahi and L. Lakshmanan, "On Approximating Optimum Repairs for Functional Dependency Violations," Proceedings of the 12th International Conference on Database Theory, pp. 53-62, 2009.
[21] G. Beskales, I. F. Ilyas, L. Golab and A. Galiullin, "On the Relative Trust between Inconsistent Data and Inaccurate Constraints," Proceedings of the 29th International Conference on Data Engineering, pp. 541-552, 2013.
[22] M. Volkovs, F. Chiang, J. Szlichta and R. J. Miller, "Continuous data cleaning," Proceedings of the 30th  International Conference on Data Engineering, pp. 244-255, 2014.
[23] G. Beskales, I. F. Ilyas, L. Golab and A. Galiullin, "Sampling from Repairs of Conditional Functional Dependency Violations," The VLDB Journal, vol. 23, no. 1, pp. 103 - 128, 2014.
[24] X. Chu, J. Morcos, I. F. Ilyas, M. Ouzzani, P. Papotti, N. Tang and Y. Ye, "KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing,"Proceedings of the 15th International Conference on Management of Data, pp. 1247 - 1261, 2015.
[25] W. Fan, S.  Ma, N. Tang and W. Yu, "Interaction Between Record Matching and Data Repairing," J. Data and Information Quality, vol. 4, no. 4, 2014.
[26] J. Segeren, D. Gairola and F. Chiang, "CONDOR: A System for CONstraint DiscOvery and Repair," in Proceedings of the 23rd International Conference on Information and Knowledge Management, pp. 2078 - 2089, 2014.
[27] S. Song, H. Zhu and J. Wang, "Constraint-Variance Tolerant Data Repairing," Proceedings of the 16th International Conference on Management of Data, pp. 877 - 892, 2016.
[28] F. Chiang and S. Sitaramachandran, "Unifying Data and Constraint Repairs," J. Data and Information Quality, vol. 7, no. 3, pp. 1 - 26, 2016.
[29] J. Han, M. Kamber and J. Pei, Data Mining Concept And Techniques, Morgan Kaufmann Publishers, 3 Edition, 2011.
[30] H. Yao and H. J. Hamilton, "Mining functional dependencies from data," Data Mining and Knowledge Discovery, vol. 16, no. 2, pp. 197-219, 2008.
[31] Y. Huhtala, J. Kärkkäinen, P. Porkka and H. Toivonen, "Tane: An Efficient Algorithm for Discovering Functional and Approximate Dependencies," The Computer Journal, vol. 42, no. 2, pp.100-111, 1999.
[32] P. Kontkanen, J. Lahtinen, P. Myllymaki, T. Silander and H. Tirri, "Pre- and Post-processing in Machine Learning and Data Mining: Theoretical Aspects and Applications," The workshop within Machine Learning and Applications Complex Systems Computation Group (CoSCo), pp. 38-47, 1999
[33] R. Agrawal and R. Ikant and D. Thomas, "Privacy Preserving OLAP," Proceedings of the 5th International Conference on Management of Data, pp. 251-262, 2005.
[34] I. Yoncaci, "Maximum a Posteriori Tree Augmented Naive Bayes Classifiers," Lecture Notes in Artificial Intelligence, 2004.
[35] S. Haykin, Neural Networks: A Comprehensive Foundation, 2nd.
Englewood Cliffs, NJ: Prentice-Hall, 1999.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار