ساخت درخت تصمیم مقیاس‌پذیر مبتنی بر تقسیم سریع داده‌ها و پیش‌هرس
الموضوعات :
سميه لطفي
1
,
محمد قاسم زاده
2
,
مهران محسن زاده
3
,
ميترا ميرزارضايي
4
1 - دانشگاه آزاد اسلامی واحد علوم و تحقیقات
2 - دانشگاه یزد
3 - دانشگاه آزاد اسلامی واحد علوم و تحقيقات
4 - دانشگاه آزاد اسلامی واحد علوم و تحقيقات
الکلمات المفتاحية: پیش‌هرس, داده‌کاوی, درخت تصمیم, مقیاس‌پذیر,
ملخص المقالة :
دسته‌بندی، یکی از وظایف مهم داده‌کاوی و یادگیری ماشین است و درخت تصمیم به عنوان یکی از الگوریتم‌های پرکاربرد دسته‌بندی، دارای سادگی و قابلیت تفسیر نتایج است. اما در مواجهه با داده‌های حجیم، درخت تصمیم بسیار پیچیده خواهد شد و با محدودیت‌های حافظه و زمان اجرا مواجه است. الگوريتم‌هاي ساخت درخت باید همه مجموعه داده آموزش و یا بخش زیادی از آن را درون حافظه نگه دارند. الگوریتم‌هایی که به علت انتخاب زیرمجموعه‌ای از داده با محدودیت حافظه مواجه نیستند، زمان اضافی جهت انتخاب داده صرف می‌کنند. جهت انتخاب بهترین ویژگی برای ایجاد انشعاب در درخت هم باید محاسبات زیادی بر روی این مجموعه داده انجام شود. در این مقاله، یک رویکرد مقیاس‌پذیر افزایشی بر مبنای تقسیم سریع و هرس، جهت ساخت درخت تصمیم بر روی مجموعه داده‌های حجیم ارائه شده است. الگوریتم ارائه‌شده درخت تصمیم را با استفاده از کل مجموعه داده آموزش اما بدون نیاز به ذخیره‌سازی داده در حافظه اصلی می‌سازد. همچنین جهت کاهش پیچیدگی درخت از روش پیش‌هرس استفاده شده است. نتایج حاصل از اجرای الگوریتم بر روی مجموعه داده‌های UCI نشان می‌دهد الگوریتم ارائه‌شده با وجود دقت و زمان ساخت قابل رقابت با سایر الگوریتم‌ها، بر مشکلات حاصل از پیچیدگی درخت غلبه کرده است.
[1] S. Agarwal, "Data mining: data mining concepts and techniques," in Proc. IEEE Int. Conf. on Machine Intelligence and Research Advancement, . pp. 203-207, Katra, India, 21-23 Dec. 2013.
[2] S. B. Kotsiantis, "Decision trees: a recent overview," Artificial Intelligence Review, vol. 39, no. 4, pp. 261-283, 2013.
[3] Z. Ruiz, J. Salvador, and J. Garcia-Rodriguez, "A survey of machine learning methods for big data," in International Work-Conf. on the Interplay Between Natural and Artificial Computation, pp. 259-267, Springer, Cham, Jun. 2017.
[4] S. Lomax and S. Vadera, "A survey of cost-sensitive decision tree induction algorithms," ACM Computing Surveys (CSUR), vol. 45, no. 2, pp. 1-35, Feb. 2013.
[5] Y. L. Chen, C. C. Wu, and K. Tang, "Time-constrained cost-sensitive decision tree induction," Information Sciences, vol. 354, pp. 140-152, Mar. 2016.
[6] F. Stahl and M. Bramer, "Jmax-pruning: a facility for the information theoretic pruning of modular classification rules," Knowledge-Based Systems, vol. 29, pp. 12-19, 2012.
[7] S. Hwang, H. G. Yeo, and J. S. Hong, "A new splitting criterion for better interpretable trees," IEEE Access, vol. 8, pp. 62762-62774, 2020.
[8] J. Gehrke, V. Ganti, R. Ramakrishnan, and W. Y. Loh, "BOAT-optimistic decision tree construction," ACM SIGMOD Record, vol. 28, no. 2, pp. 169-180, Jun. 1999.
[9] M. Mehta, R. Agrawal, and J. Rissanen, "SLIQ: a fast scalable classifier for data mining," Advances in Database Technology-EDBT'96, pp. 18-32, 1996.
[10] J. Shafer, R. Agrawal, and M. Mehta, "SPRINT: a scalable parallel classifier for data mining," in Proc. Int. Conf. Very Large Data Bases, vol. 96, pp. 544-555, 3-6 Sept. 1996.
[11] J. Gehrke, R. Ramakrishnan, and V. Ganti, "Rainforest-a framework for fast decision tree construction of large datasets," Data Mining and Knowledge Discovery, vol. 4, pp. 127-162, 2000.
[12] G. Hulten and P. Domingos, "Mining decision trees from streams," in Garofalakis M., Gehrke J., Rastogi R. (eds.) Data Stream Management. Data-Centric Systems and Applications. pp. 189-208, Springer Berlin Heidelberg, 2016.
[13] C. C. Wu, Y. L. Chen, Y. H. Liu, and X. Y. Yang, "Decision tree induction with a constrained number of leaf nodes," Applied Intelligence, vol. 45, no. 3, pp. 673-685, Oct. 2016.
[14] A. Franco-Arcega, J. A. Carrasco-Ochoa, G. Sanchez-Diaz, and J. F. Martinez-Trinidad, "Decision tree induction using a fast splitting attribute selection for large datasets," Expert Systems with Applications, vol. 38, no. 11, pp. 14290-14300, Oct. 2011.
[15] B. Chandra, R. Kothari, and P. Paul, "A new node splitting measure for decision tree construction," Pattern Recognition, vol. 43, no. 8, pp. 2725-2731, Aug. 2010.
[16] P. S. Akash, M. E. Kadir, A. A. Ali, and M. Shoyaib, "Inter-node hellinger distance based decision tree," in Proc. 28th Int. Joint Conf. on Artificial Intelligence, IJCAI’19, pp. 1967-1973, Aug. 2019.
[17] M. Bramer, "Using J-pruning to reduce overfitting in classification trees," Knowledge-Based Systems, vol. 15, no. 5, pp. 301-308, Jul. 2002.
