۲۱۷۳۱پ
per
ارائه‌ی الگوریتمی مؤثر برای یادگیری قوانین و بهبود روش‌های ساخت قانون مبتنی بر پایه‌ی محاسبات گرانولار با استفاده از توزیع بتا نرمال
An Effective Algorithm for Rule Learning and Improving Rule Generation Methods Based on Granular Computing Using the Beta-Normal Distribution
/سید علی داودزاده
: علوم ریاضی
، ۱۳۹۸
، میرزائی
۹۹ص
چاپی - الکترونیکی
کارشناسی ارشد
مهندسی کامپیوتر گرایش هوش مصنوعی
۱۳۹۸/۰۶/۲۰
تبریز
یادگیری قانون یکی از محبوب‌ترین زمینه‌های تحقیق در یادگیری ماشین است، زیرا نتیجه‌ی این یادگیری، مجموعه‌ای از قوانین را تهیه و تولید می‌کند که نه تنها دسته‌بندی و پیش‌بینی نسبتا دقیقی ارائه می‌دهد، بلکه یک فرآیند شفاف از ورودی‌ها به خروجی‌ها نشان می‌دهد .یادگیری قانون به‌طور معمول دو استراتژی اصلی را دنبال می‌کند" :تقسیم و غلبه "و" جداسازی و غلبه ."استراتژی اول، یعنی تقسیم و غلبه با هدف ساخت قوانین و نمایش آن در قالب یک درخت تصمیم است، این در حالی است که هدف استراتژی دوم، یعنی جداسازی و غلبه، ساخت و یادگیری مستقیم قوانین است .از آن‌صجا که برای استراتژی تقسیم و غلبه باید تشکیل درخت تصمیم داده شود، این استراتژی می‌تواند منجر به مشکل تکرار زیرصدرخت‌صها شود که نه تنها منجر به ایجاد مشکل بیش‌صبرازش می-شود، بلکه پیچیدگی محاسباتی را برای دسته‌بندی نمونه‌های جدید افزایش می‌دهد .از این رو محققان انگیزه‌ای برای ایجاد رویکردهای مبتنی بر یادگیری قوانین یافتند تا این قوانین را از طریق استراتژی جداسازی و غلبه توسعه دهند .در این پژوهش، ما بر بررسی الگوریتم Prism متمرکز هستیم، زیرا این الگوریتم یک نماینده بسیار مناسب از دسته الگوریتم‌هایی است که از استراتژی جداسازی و غلبه پیروی می‌صکنند و هدف آن یادگیری مجموعه‌ای از قوانین، برای دسته‌بندی در محیط محاسبات گرانولی یا دانه‌صای است، که در آن هر کلاس، به عنوان گرانول در نظر گرفته می‌شود .دلیل انتخاب این الگوریتم این است که، الگوریتم Prism عملکرد بسیار قابل مقایسه‌ای با الگوریتم‌های محبوب موجود، مانند الگوریتم‌صهای ID۳ و C۴.۵ است که به دنبال استراتژی تقسیم و غلبه هستند .با این حال، به دلیل نیاز به یادگیری یک قانون برای هر کلاس، Prism معمولا دسته‌بندصهای مبتنی بر قانون بسیار پیچیده‌صای را تولید می‌کند .یکی از مباحث مهم در آمار، تعمیم توزیع‌ها می‌باشد .در این راستا تعمیم توزیع‌های پیوسته به دلیل انعطاف بیشترشان، بیش از گذشته نسبت به توزیع‌های گسسته، مورد توجه بوده است .یکی از این توزیع‌های پیوسته، توزیع بتا است که با تعمیم این توزیع می‌توان بسیاری از توزیع‌های مهم مانند بتا نرمال را به دست آورد که این توزیع دارای ویژگی‌های خاص و در عمل دارای برتری نسبت به توزیع‌های دیگر است، بنابراین این موضوع سبب می‌شود که توزیع بتا به طور ویژه‌ای مورد توجه قرار گیرد .توزیع بتا حالت کلی‌تر توزیع یکنواخت پیوسته است که در فاصله۰] - [۱تعریف می‌گردد .در یادگیری ماشین سنتی مبتنی بر یادگیری قانون، دسته‌بندی به طور معمول توسط بخش آموزش یک دسته‌بند انجام می‌شود که یک کلاس را از کلاس‌های دیگر جدا می‌کند تا هر نمونه را به طور منحصر به فرد دسته‌بندی کند، زیرا این دسته‌بندی بر اساس این فرض است که کلاس‌های متفاوت متقابلا منحصر به فرد هستند و هر نمونه نمی‌تواند به بیش از یک کلاس تعلق داشته باشد .این در حالی است که فرضیه‌ی بالا همیشه در دسته‌بندی داده‌های واقعی وجود ندارد .در کاربردهای واقعی، مسائل زیادی وجود دارند که فقط یک کلاس هدف را شامل نمی‌شوند، بنابراین لازم است که یک قانون را برای هر کلاس تعریف کنیم، یعنی سیستم باید همه‌صی مجموعه قوانین را برای کلاس-های هدف یاد بگیرد .برای رسیدگی به مسائل فوق، ما یک الگوریتم جدید را به نام BNBRG ارائه دادیم که BNBRG مخففNormal Based Rule Generation - Betaو به معنای" ساخت قوانین مبتنی بر روش بتا نرمال "است .در آخر روش پیشنهادی خود را از لحاظ عملکرد آن در دقت و پیچیدگی با الگوریتم‌های Prism و C۴.۵ مقایسه می‌کنیم .نتایج بدست آمده نشان می‌دهد که BNBRG منجر به تولید دسته‌بندی بر اساس قوانین ساده‌تر و تعداد قوانین و نمونه‌های کمتر، با دقت بالاتر در مقایسه با Prism شود .همچنین الگوریتم ما در مقایسه با الگوریتم C۴.۵ با بهبود عملکرد همراه است .در کل الگوریتم پیشنهادی ما یعنی BNBRG از نظر دقت در دسته‌بندی از مجموع میانگین ۲۰ مجموعه داده، در مجموع و در کل با افزایش ۱۱ درصدی نسبت به دو الگوریتم عمل کرده‌است و همچنین از نظر پیچیدگی در تولید قوانین با کاهش ۳۹ درصدی نسبت به C۴.۵ و کاهش ۴۸ درصدی نسبت به الگوریتم Prism همراه بوده‌است .از طرفی نیز از نظر پیچیدگی تعداد اصطلاحات و نمونه های موجود در قوانین نسبت به C۴.۵ با کاهش ۷۲ درصدی و همچنین نسبت به Prism با کاهش ۵۸ درصدی همراه بوده‌است
Rule learning is a popular branch of machine learning, which can provide accurate and interpretable classification results. In general, two main strategies of rule learning are referred to as divide and con-quer and separate and conquer. The first strategy, namely divide and conquer, aims at making rules and displaying them in the form of a decision tree, while the second strategy, namely separate and conquer, generates and learns the rules directly. Because the divide and conquer strategy must be decided, this strategy can lead to the problem of duplicating sub-trees, which not only leads to over-fitting problems but also computational complexity for classification increases new ones. Decision tree generation that fol-lows the former strategy has a serious drawback, which is known as the replicated subtree problem, re-sulting from the constraint that all branches of a decision tree must have one or more common attributes. The above problem is likely to result in high computational complexity and the risk of overfitting, which leads to the necessity to develop rule learning algorithms (e.g., Prism) that follow the separate and con-quer strategy. Therefore, the researchers were motivated to develop rules-based approaches to learning to develop these rules through a strategy of separate and conquer. In this research, we are focusing on the Prism algorithm, because it is a very good representative of a set of algorithms that follow the separate and conquer strategy, which aims to learn a set of rules for classification in granular computing environ-ments. Is, in which each class is regarded as a granule. The reason for choosing this algorithm is that the Prism algorithm performs very comparable to existing popular algorithms, such as ID3 and C4.5 algo-rithms, which seek to divide and conquer. However, because of the need to learn one rule for each class, Prism usually produces very complex rule-based classifications. The replicated sub-tree problem can be effectively solved using the Prism algorithm, but the trained models are still complex due to the need of training an independent rule set for each selected target class. One of the most important topics in statis-tics is the generalization of distributions. In this regard, the generalization of continuous distributions, due to their greater flexibility, has been more favored than discrete distributions. One of these continuous distributions is the beta distribution, which can be obtained by generalizing this distribution to many im-portant distributions, such as normal beta, which have specific characteristics and in fact have superiority over other distributions, thus giving rise to the distribution. Beta should be particularly noted. The beta distribution is the general state of continuous uniform distribution defined at [0-1]. In order to reduce the risk of overfitting and the model complexity, we propose in this thesis a variant of the Prism algorithm using beta-normal distribution referred to as BNBRG, where the acronym of BNBRG stands for Beta Normal Based Rule Generation. The experimental results show that the BNBRG algorithm leads to ad-vances in classification performance and reduction of model complexity, in comparison with the C4.5 and Prism algorithms. Overall, our proposed algorithm, BNBRG, performed an accuracy of classificating the average of 20 datasets, with an overall increase of 11 over the two algorithms, and also of the com-plexity of generating rules with a 39 decrease over C4.5 and 48 decrease compared to Prism algo-rithm. On the other hand, in terms of complexity, the number of terms and instances in the rules was down 72 compared to C4.5 and 58 down on Prism
An Effective Algorithm for Rule Learning and Improving Rule Generation Methods Based on Granular Computing Using the Beta-Normal Distribution
داودزاده، سید علی
Davoodzadeh, Seyed Ali
سیاه و سفید
نمایه‌سازی قبلی
