ساخت درخت تصمیم مقیاس‌پذیر مبتنی بر تقسیم سریع داده‌ها و پیش‌هرس
محورهای موضوعی : electrical and computer engineering
سميه لطفي
1
,
محمد قاسم زاده
2
,
مهران محسن زاده
3
,
ميترا ميرزارضايي
4
1 - دانشگاه آزاد اسلامی واحد علوم و تحقیقات
2 - دانشگاه یزد
3 - دانشگاه آزاد اسلامی واحد علوم و تحقيقات
4 - دانشگاه آزاد اسلامی واحد علوم و تحقيقات
کلید واژه: پیش‌هرس, داده‌کاوی, درخت تصمیم, مقیاس‌پذیر,
چکیده مقاله :
دسته‌بندی، یکی از وظایف مهم داده‌کاوی و یادگیری ماشین است و درخت تصمیم به عنوان یکی از الگوریتم‌های پرکاربرد دسته‌بندی، دارای سادگی و قابلیت تفسیر نتایج است. اما در مواجهه با داده‌های حجیم، درخت تصمیم بسیار پیچیده خواهد شد و با محدودیت‌های حافظه و زمان اجرا مواجه است. الگوريتم‌هاي ساخت درخت باید همه مجموعه داده آموزش و یا بخش زیادی از آن را درون حافظه نگه دارند. الگوریتم‌هایی که به علت انتخاب زیرمجموعه‌ای از داده با محدودیت حافظه مواجه نیستند، زمان اضافی جهت انتخاب داده صرف می‌کنند. جهت انتخاب بهترین ویژگی برای ایجاد انشعاب در درخت هم باید محاسبات زیادی بر روی این مجموعه داده انجام شود. در این مقاله، یک رویکرد مقیاس‌پذیر افزایشی بر مبنای تقسیم سریع و هرس، جهت ساخت درخت تصمیم بر روی مجموعه داده‌های حجیم ارائه شده است. الگوریتم ارائه‌شده درخت تصمیم را با استفاده از کل مجموعه داده آموزش اما بدون نیاز به ذخیره‌سازی داده در حافظه اصلی می‌سازد. همچنین جهت کاهش پیچیدگی درخت از روش پیش‌هرس استفاده شده است. نتایج حاصل از اجرای الگوریتم بر روی مجموعه داده‌های UCI نشان می‌دهد الگوریتم ارائه‌شده با وجود دقت و زمان ساخت قابل رقابت با سایر الگوریتم‌ها، بر مشکلات حاصل از پیچیدگی درخت غلبه کرده است.
Classification is one of the most important tasks in data mining and machine learning; and the decision tree, as one of the most widely used classification algorithms, has the advantage of simplicity and the ability to interpret results more easily. But when dealing with huge amounts of data, the obtained decision tree would grow in size and complexity, and therefore require excessive running time. Almost all of the tree-construction algorithms need to store all or part of the training data set; but those algorithms which do not face memory shortages because of selecting a subset of data, can save the extra time for data selection. In order to select the best feature to create a branch in the tree, a lot of calculations are required. In this paper we presents an incremental scalable approach based on fast partitioning and pruning; The proposed algorithm builds the decision tree via using the entire training data set but it doesn't require to store the whole data in the main memory. The pre-pruning method has also been used to reduce the complexity of the tree. The experimental results on the UCI data set show that the proposed algorithm, in addition to preserving the competitive accuracy and construction time, could conquer the mentioned disadvantages of former methods.