17870

17870

توسعه ي يك الگوريتم جديد مبتني بر بهينه سازي اجتماع ذرات براي ارتقاء يادگيري درخت تصميم از داده هاي نويزي

كارشناسي ارشد

هوش مصنوعي و رباتيك

شهريور 1396

دكتر محمدرضا كنگاوري

كامپيوتر

گرچه درخت تصميم يك مدل ساده است ولي هنوز يكي از متداول‌ترين رده¬بندها براي حل مسائل دنياي واقعي مي¬باشد. يكي از مهم¬ترين ويژگي¬هاي درخت تصميم توليد قواعدي است كه به سادگي مي¬توان آن¬ها را تفسير كرد. با اين حال يكي از بزرگترين مشكلاتي كه درخت تصميم با آن مواجه است اين است كه بيش¬تر روش¬هاي ساخت درخت تصميم روش¬هاي حريصانه هستند كه درخت را از بالا به پائين و به¬صورت تقسيم و غلبه مي¬سازند، و در اين الگوريتم¬ها امكان بررسي تمام حالات ممكن وجود ندارد و در نتيجه درخت ساخته شده، لزوماً بهترين درخت ممكن نمي‌باشد. همچنين يكي ديگر از چالش‌هايي كه روش‌هاي يادگيري درخت تصميم با آن مواجه هستند اين است كه وجود نويز در مجموعه‌ داده‌ها باعث كاهش دقت درخت مي‌شود. با ظهور داده‌هاي جرياني در دنياي اطلاعات روش‌هايي براي يادگيري درخت تصميم از داده‌هاي جرياني كه داراي قابليت يادگيري برخط مي‌باشند ارائه شد، يكي از اين مدل‌هاي درخت هافدين مي‌باشد كه اين مدل هم مانند روش‌هاي يادگيري درخت تصميم از داده‌هاي ايستا يك روش حريصانه است و همچنين در اين مدل هم وجود نويز باعث كاهش دقت درخت هافدين مي‌شود. در اين تحقيق سعي شده است كه با ارائه‌ي يك مدل يادگيري درخت تصميم از داده‌هاي جرياني كه به صورت متناوب از الگوريتم بهينه‌سازي اجتماع ذرات كمك مي‌گيرد اقدام به بهبود دقت درخت هافدين نماييم. روش ارائه شده باعث افزايش اندازه‌ي درخت هافدين مي‌شود به همين دليل در اين تحقيق از يك الگوريتم انتخاب خصيصه كه از الگوريتم بهينه‌سازي اجتماع ذرات دودويي كمك مي‌گيرد نيز براي كاهش اندازه‌ي درخت توليد شده استفاده كرده‌ايم. نتايج آزمايش‌ها نشان مي‌دهد كه الگوريتم يادگيري درخت تصميم كه به صورت متناوب از الگوريتم بهينه‌سازي اجتماع ذرات كمك مي‌گيرد موجب بهبود دقت يادگيري از داده‌‌هاي نويزي و بدون نويز مي‌شود. همچنين نتايج آزمايش‌ها نشان مي‌دهد با اضافه كردن الگوريتم انتخاب ويژگي به مدل پيشنهادي اندازه‌ي درخت توليد شده بهبود مي‌يابد و دقت آن نيز قابل مقايسه با درخت هافدين مي‌باشد. واژه‌هاي كليدي: داده‌هاي جرياني، درخت تصميم، بهينه‌سازي اجتماع ذرات.

1396/07/15

1/1/1900 12:00:00 AM

Although the decision tree is a simple model, it is still one of the most popular classifiers to solve real world problems. One of the most important features of the decision tree is to generate rules that can be easily interpreted. However, one of the biggest problems in the way of the decision tree is that most of the methods of making decision tree are greedy approach that make the tree in a top-down divide and conquer approach. In these algorithms, it is not possible to examine all the possible scenarios, and as a result, the constructed tree would not necessarily be the best possible tree. Another challenge that the decision tree learning methods are faced with is the presence of noise in the data set, leading to reduced tree accuracy. With the advent of streaming data in the information world, some learning methods were represented for learning the decision tree from streaming data that are capable of online learning. One of these models is the Hoeffding tree, a model, which is also a greedy method such as the learning methods of the decision tree of static data. In this model, the presence of noise reduces the accuracy of the Hoeffding tree as well. In this research, providing a decision tree learning model of the streaming data that utilizes the particle swarm optimization algorithm intermittently, we tried to improve the accuracy of the Hoeffding tree. The proposed method increases the size of the Hoeffding tree. Thus, we used a feature selection algorithm in this research to reduce the size of the produced that applies a binary particle swarm optimization algorithm. The test results showed that the decision tree learning algorithm, which alternatively uses the particle swarm optimization algorithm, improves the learning accuracy of noisy and non-noisy data. In addition, the experiments' results indicated that the size of the generated tree will improve by adding the feature selection algorithm to the proposed model, and its precision is also comparable to the Hoeffding tree. Keywords: stream data, decision tree, particle swarm optimization