ساخت درخت ‌تصميم مقياس‌پذير مبتني بر تقسيم سريع داده‌ها و پيش‌هرس

Construction of Scalable Decision Tree Based on Fast Data Partitioning and Pre-Pruning

دسته‌بندي، يكي از وظايف مهم داده‌كاوي و يادگيري ماشين است و درخت تصميم به ‌عنوان يكي از الگوريتم‌هاي پركاربرد دسته‌بندي، داراي سادگي و قابليت تفسير نتايج است. اما در مواجهه با داده‌هاي حجيم، درخت تصميم بسيار پيچيده خواهد شد و با محدوديت‌هاي حافظه و زمان اجرا مواجه‌ است. الگوريتم‌هاي ساخت درخت بايد همه مجموعه داده آموزش و يا بخش زيادي از آن را درون حافظه نگه دارند. الگوريتم‌هايي كه به علت انتخاب زيرمجموعه‌اي از داده با محدوديت حافظه مواجه نيستند، زمان اضافي جهت انتخاب داده صرف‌ مي‌كنند. جهت انتخاب بهترين ويژگي براي ايجاد انشعاب در درخت هم بايد محاسبات زيادي بر روي اين مجموعه داده انجام شود. در اين مقاله، يك رويكرد مقياس‌پذير افزايشي بر مبناي تقسيم سريع و هرس، جهت ساخت درخت تصميم بر روي‌ مجموعه داده‌هاي حجيم ارائه شده است. الگوريتم ارائه‌شده درخت تصميم را با استفاده از كل مجموعه داده‌ آموزش اما بدون نياز به ذخيره‌سازي داده در حافظه اصلي مي‌سازد. همچنين جهت كاهش پيچيدگي درخت از روش پيش‌هرس استفاده شده است. نتايج حاصل از اجراي الگوريتم بر روي مجموعه داده‌هاي 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.