• صفحه اصلی
  • دسته‌بندی داده‌های دو رده‌ای با ابرمستطیل موازی محورهای مختصات

اشتراک گذاری

آدرس مقاله


کد مقاله : 202007118331 بازدید : 12535 صفحه: 1 - 14

20.1001.1.27170411.1394.7.26.1.8

نوع مقاله: پژوهشی

دسته‌بندی داده‌های دو رده‌ای با ابرمستطیل موازی محورهای مختصات

محورهای موضوعی : عمومى

زهرا مصلحی 1 * , مازیار پالهنگ 2

1 - دانشجو
2 - -

تاریخ دریافت : 1392/01/16 تاریخ پذیرش : 1392/01/16 تاریخ انتشار : 1395/02/13

کلید واژه: یادگیری ماشین, دسته‌بندی, درخت تصمیم, هندسه محاسباتی, تفکیک‌پذیری, مستطیل,

چکیده مقاله :

یکی از روشهای یادگیری در یادگیری ماشین و شناسایی الگو، یادگیری با ناظر است. در یادگیری با ناظر و در مسایل دو رده‌ای، برچسب دادههای آموزشی موجود و شامل دو رده مثبت و منفی میباشند. هدف الگوریتم یادگیری با ناظر، محاسبه فرضیه‌ای است که بتواند با کمترین مقدار خطا، داده‌های مثبت و منفی را از یکدیگر جدا کند. در این مقاله، از بین کلیه الگوریتمهای یادگیری با ناظر، بر عملکرد درخت‌های تصمیم متمرکز می‌شویم. دیدگاه هندسی درخت تصمیم ما را به مفهوم تفکیک‌پذیری در هندسه محاسباتی نزدیک می‌کند. از بین کلیه الگوریتم‌های تفکیک‌پذیری موجود و مرتبط با درخت تصمیم، مساله محاسبه مستطیل با حداکثر اختلاف دو رنگ را مطرح می‌کنیم و الگوریتم را در یک، دو، سه و m بعد پیادهسازی می‌کنیم که m تعداد ویژگیهای دادهها را نشان میدهد. نتیجه پیاده‌سازی نشان‌دهنده آن است که این الگوریتم، الگوریتمی قابل رقابت با الگوریتم شناخته شده C4.5 است.

چکیده انگلیسی:

One of the learning methods in machine learning and pattern recognition is supervised learning. In supervised learning and in two-category problems, the available educational data labels include positive and negative categories. The goal of the supervised learning algorithm is to calculate a hypothesis that can separate positive and negative data with the least amount of error. In this article, among all supervised learning algorithms, we focus on the performance of decision trees. The geometric view of the decision tree brings us closer to the concept of separability in computational geometry. Among all the available resolution algorithms related to the decision tree, we raise the problem of calculating the rectangle with the maximum difference of two colors and implement the algorithm in one, two, three and m dimensions, where m represents the number of data features. The implementation result shows that this algorithm is competitive with the well-known C4.5 algorithm.

منابع و مأخذ:

T. M. Mitchell, Machine learning, McGraw-Hill, 1997.
2.P.L. Hammer, A. Kogan, B. Simeone, and S. Szedmak, “Pareto-optimal patterns in logical analysis of data,” Discrete Applied Mathematics, vol.144, pp.79-102, 2004.
3.M. Kreveld, T. Lankveld, and R. Veltkamp, “Identifying well-covered minimal bounding rectangles in 2D point data,” in 25th European Workshop on Computational Geometry, EWCG, 2009, pp.277-280.
4.J. Eckstein, P. Hammer, Y. Liu, M. Nediak, and B. Simeone, “The maximum box problem and its application to data analysis,” Journal of Computational Optimization and Application, vol.23, pp. 85-98, 2002.
5.D. P. Dobkin, D. Gunopulos, and W. Maass, “Computing the maximum bichromatic discrepancy with applications to computer graphics and machine learning,” Journal of Computer and System Science, vol.52, pp. 453–470, 1996.
6.Y. Liu, and M. Nediak, “Planar case of the maximum box and related problems,” in Proceedings 15th Canadian Conferance of Computational Geometry, CCCG, 2003, pp.14-18.
7.C. Cortés, J. Díaz-Báòez, P. Pérez-Lantero, C. Seara, J. Urrutia, and I. Ventura, “Bichromatic separability with two boxes: A general approach,” Journal of Algorithms, vol.64, pp.79-88. 2009.
8.C. Cortés, J. Díaz-Báòez, and J. Urrutia, “Finding enclosing boxes with empty intersection,” in Proceedings 23rd European Workshop on Computational Geometry, EWCG, 2006, pp.185-188.
9.ز. مصلحی، " تفکیک‌پذیری نقاط با اشیای هندسی در فضای دوبعدی،" پایان نامه کارشناسی ارشد دانشکده مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه صنعتی امیرکبیر، 1391.
10.ز. مصلحی، ع. باقری، " تفکیک پذیري سري نقاط دو رنگ با دو مستطیل مجزا و موازي محورهاي مختصات،" مجله علمی پژوهشی رایانش نرم و فناوري اطلاعات، جلد 1، شماره 2، صفحه 35-42، 1391.
11.S. Cabello, J. M. Díaz-Báñez, C. Seara, J. A. Sellarès, J. Urrutia, and I. Ventura, “Covering point sets with two convex objects,” in 21st European Workshop on Computational Geometry, EWCG, 2005, pp. 195-206.
12.S. Cabello, J. M. Díaz-Báñez, C. Seara, J. Urrutia, and I. Ventura, “Covering point sets with two disjoint disks or squares,” Computational Geometry: Theory and Application, vol.40, pp. 195-206, 2008.
13.D.P. Dobkin, and D. Gunopulos, “Geometric problems in machine learning, in Lecture Notes in Computer Science, LNCS, 1996, vol.1148, pp.121-132.
14.M. D. Berg, O. Cheong, M. V. Kreveld, and M. Overmars, Computational geometry: algorithms and applications, 3rd Edition, TELOS, Santa Clara, CA, USA, 2008.
15.K. Bache and M. Lichman. (2013). UCI Machine Learning Repository [Online]. Available: http://archive.ics.uci.edu/ml
16.I. H. Witten, E. Frank, and M. A. Hall, Data Mining: Practical machine learning tools and techniques, 3rd Edition, Morgan Kaufmann, San Francisco, 2011.
متن کامل:


 

فصلنامه علمي- پژوهشي  

فناوري اطلاعات و ارتباطات ایران

سال هفتم، شماره‌هاي 25 و 26، پاییز و زمستان 1394

صص: 1-  14

E:\E Drive\logo\iicta Logo0.JPG 

 

دسته‌بندی داده‌های دو رده‌ای با ابرمستطیل موازی محورهای مختصات

 

*زهرا مصلحی ** مازیار پالهنگ

* دانشجوی دکتری، دانشکده مهندسی برق و کامپیوتر، دانشگاه صنعتی اصفهان، اصفهان

** دانشیار، دانشکده مهندسی برق و کامپیوتر، دانشگاه صنعتی اصفهان، اصفهان

تاریخ دریافت: 16/11/92                     تاریخ پذیرش:20/11/94

 

چکیده

یکی از روشهای یادگیری در یادگیری ماشین و شناسایی الگو، یادگیری با ناظر است. در یادگیری با ناظر و در مسایل دو رده‌ای، برچسب دادههای آموزشی موجود و شامل دو رده مثبت و منفی میباشند. هدف الگوریتم یادگیری با ناظر، محاسبه فرضیه‌ای است که بتواند با کمترین مقدار خطا، داده‌های مثبت و منفی را از یکدیگر جدا کند. در این مقاله، از بین کلیه الگوریتمهای یادگیری با ناظر، بر عملکرد درخت‌های تصمیم متمرکز می‌شویم. دیدگاه هندسی درخت تصمیم ما را به مفهوم تفکیک‌پذیری در هندسه محاسباتی نزدیک می‌کند. از بین کلیه الگوریتم‌های تفکیک‌پذیری موجود و مرتبط با درخت تصمیم، مساله محاسبه مستطیل با حداکثر اختلاف دو رنگ را مطرح می‌کنیم و الگوریتم را در یک، دو، سه و m بعد پیادهسازی می‌کنیم که m تعداد ویژگیهای دادهها را نشان میدهد. نتیجه پیاده‌سازی نشان‌دهنده آن است که این الگوریتم، الگوریتمی قابل رقابت با الگوریتم شناخته شده C4.5 است.

­واژه­های کلیدی : یادگیری ماشین، دسته‌بندی، درخت تصمیم، هندسه محاسباتی، تفکیک‌پذیری، مستطیل

 

1- مقدمه

 

یکی از زمینه‌های فعالیت در یادگیری ماشین و شناسایی الگو یادگیری با ناظر می‌باشد. مهمترین ویژگی الگوریتمهای یادگیری با ناظر آن است که در آن برچسب دادههای آموزشی موجود است. تاکنون انواع روش‌های یادگیری با ناظر پیشنهاد شده است. به عنوان مثال می‌توان به درخت‌های تصمیم، یادگیر SVM و روش‌های نزدیکترین همسایه اشاره کرد. در این مقاله بر عملکرد درخت‌های تصمیم متمرکز می‌شویم. عملکرد هندسی درختهای تصمیم با مفهوم تفکیک‌پذیری در هندسه محاسباتی ارتباط نزدیکی دارد. در ابتدا در مورد عملکرد درخت تصمیم صحبت میکنیم و پس از آن در مورد مساله تفکیک‌پذیری در هندسه محاسباتی صحبت خواهیم کرد و ارتباط بین درخت‌های تصمیم و مساله تفکیک‌پذیری را مطرح می‌کنیم.

نویسنده عهده­دار مکاتبات: زهرا مصلحی z.moslehi@ec.iut.ac.ir

درخت‌های تصمیم یکی از روش‌های یادگیری با ناظر برای ردهبندی داده‌های پیوسته و یا داده‌های گسسته است. نحوه‌ی ساخت فرضیه متناظر با درخت‌های تصمیم به این صورت است که ابتدا بر اساس یک معیار مشخص یکی از ویژگی‌های متناظر با داده‌های ورودی انتخاب می‌شود و این ویژگی به عنوان ریشه در نظر گرفته می‌شود. تعداد زیرشاخه‌های متناظر با ریشه برابر با مقادیر مختلف ویژگی انتخاب شده خواهد بود. اگر داده‌های آموزشی پیوسته- مقدار باشند، زیر شاخههای متناظر با ریشه با انتخاب یک خصیصه و تقسیم محدوده مربوط به آن به دو و یا چند قسمت بدست میآید. حال می‌توان خصیصه دوم را انتخاب کرد و همین روند را مجددا تکرار کرد. در نهایت برگ‌های درخت، برچسب‌ متناظر با رده داده‌ها را مشخص می‌کند. یکی از مهمترین ملاکهای کارایی این درخت‌ها آن است که آنها قابلیت تعمیم بالایی داشته باشند. به همین منظور لازم است در هر مرحله از ساخت، خصیصه‌ای به عنوان ریشه انتخاب شود که به ازای هریک از مقادیر آن بیشترین خلوص ایجاد گردد. ارزیابی میزان خلوص با معیار آنتروپی قابل اندازه‌گیری است [1]. حال برای انتساب یک برچسب مشخص به داده ورودی لازم است بر اساس مقادیر متناظر با ویژگی‌های آن داده یک مسیر از ریشه تا یکی از برگهای درخت پیموده شود و برچسب متناظر با داده آزمون محاسبه گردد.

حال به تعریف مساله تفکیکپذیری میپردازیم. در مساله تفکیک‌پذیری در هندسه محاسباتی، دو مجموعه نقطه قرمز و آبی داده می‌شود. هدف مساله تفکیک‌پذیری پایه، به دست آوردن شکل هندسی C به گونه‌ای است که بتواند مجموعه نقاط قرمز و آبی را از یکدیگر جدا کند. به عبارتی قصد داریم شکل هندسی C را به گونه‌ای در فضا قرار دهیم بطوریکه کلیه نقاط آبی (قرمز) داخل آن و کلیه نقاط قرمز (آبی) خارج از آن قرار گیرند. تنوعات زیادی برای مساله تفکیک‌پذیری مطرح شده است. تفاوت الگوریتم‌های ارائه شده در انتخاب شکل هندسی C و تابع هدف تعریف شده است.

تاکنون کارهای زیادی در زمینه تفکیک با مستطیل، دایره، مثلث، خط و گوه ارائه شده است. هدف مساله بهینه‌سازی، گاهی کم کردن حجم، محیط و مساحت شکل هندسی تفکیککننده است. همچنین گاهی هدف، حداکثر کردن تعداد نقاط همرنگ داخل C است. این مساله زمانی مطرح می‌شود که مجموعه نقاط قرمز و آبی به طور کامل تفکیک‌پذیر نباشند.ارتباط روشنی بین مساله درخت تصمیم در یادگیری ماشین و مساله تفکیک‌پذیری نقاط در هندسه محاسباتی وجود دارد. تعبیر هندسی عملکرد درخت تصمیم به صورت زیر است: اگر تعداد ویژگی‌های داده‌ها برابر m باشد، کلیه داده‌ها، نقاطی در فضای m بعدی هستند که هر بعد بیانگر یک ویژگی از داده‌ها است. عملکرد درخت تصمیم مشابه پیدا کردن ابرصفحه‌های تقسیم‌کننده در فضای m بعدی است، بطوریکه داده‌های موجود را به درستی رده‌بندی کند و تا حد ممکن رده‌بندی صحیح داده‌های آینده را نیز بدست آورد. برای آنکه بتوانیم این مساله را به مساله تفکیک‌پذیری ارتباط دهیم کافی است به داده‌های با برچسب مثبت رنگ آبی و به داده‌های با برچسب منفی رنگ قرمز انتساب دهیم. عملکرد درخت تصمیم مشابه آن است که در فضای m بعدی بهترین تفکیک‌کننده ممکن را بیابیم بطوریکه فضا به چندین بخش افراز گردد و هر بخش دارای بیشترین تعداد نقاط همرنگ باشد. 

1-1 کارهای مرتبط

در مسایل تفکیکپذیری، مطالعه وسیعی برای انتخاب مفیدترین الگو برای تفکیک مجموعه نقاط قرمز و آبی در [2] انجام شده است. در همین مرجع نشان داده شده است که یکی از الگوهای مفید مستطیل است. تاکنون، مقالات زیادی در زمینه تفکیک‌پذیری برای مستطیل ارائه شده است.تفکیک کامل با یک مستطیل در [3] مورد بررسی قرار گرفته است. در این مساله، مستطیل فقط دارای نقاط از یک رنگ است و نقاط از رنگ دیگر، خارج از مستطیل واقع می‌شوند. ممکن است تفکیک با یک مستطیل بطور کامل امکان‌پذیر نباشد. تفکیک با یک مستطیل با هدف حداکثر تعداد نقاط از یک رنگ داخل مستطیل، به نحوی که نقطه‌ای از رنگ دیگر، داخل مستطیل واقع نباشد در [4] مورد بررسی قرار گرفته است. تفکیک با یک مستطیل با هدف حداکثر اختلاف دو رنگ، بین نقاط از یک رنگ و رنگ دیگر داخل مستطیل نیز در [5,6] بررسی گردیده است (در این حالت مستطیل دارای نقاط از هر دو رنگ است).

تفکیک با دو مستطیل بطوریکه دو مستطیل به گونهای در صفحه قرار گیرند که اضلاع آنها موازی یکدیگر بوده و نقاطی که در یک مستطیل قرار می‌گیرند (که در مستطیل دیگر قرار ندارند) تک رنگ باشند، مساله دیگری است که در [7,8] بررسی شده است. به عبارتی اگر R را مستطیل دربرگیرنده نقاط قرمز و B را مستطیل در برگیرنده نقاط آبی تعریف کنیم، نقاط داخل img0 باید فقط از رنگ آبی و نقاط داخل img0 فقط از رنگ قرمز باشند. در این مساله هدف بیشینه کردن تعداد نقاط داخل img0 است. یعنی نقاطی که در فصل مشترک دو مستطیل و خارج از دو مستطیل واقع می‌شوند از مجموعه نقاط حذف خواهند شد. همچنین، الگوریتم محاسبه دو مستطیل مجزا و موازی محورهای مختصات بطوریکه کلیه نقاط آبی داخل آن دو مستطیل و کلیه نقاط قرمز خارج از آن‌ها واقع شوند در [9,10] ارائه شده است. تفکیک با دو مربع واحد مجزا و تک رنگ موازی با محورهای مختصات، با هدف حفظ بزرگترین زیرمجموعه از نقاط در [11,12] بررسی گردیده است. در کل تفاوت الگوریتم‌های گوناگون برای تفکیک‌پذیری نقاط با مستطیل بر اساس تعداد مستطیل‌های استفاده شده، زاویه این مستطیل‌ها نسبت به یکدیگر و نسبت به محورهای مختصات و همچنین گاهی تابع بهینه‌سازی مطرح شده می‌باشد. توابع مختلف بر اساس مقدار خطای موجود بر اساس تعداد نقاطی که به اشتباه ردهبندی می‌شوند، مساحت و یا محیط مستطیل‌ها تعریف می‌گردند.

تاکنون کارهای بسیار کمی از لحاظ کاربردی و در حوزه یادگیری ماشین و دستهبندی برای مسایل تفکیکپذیری در هندسه محاسباتی ارائه شده است. از بین کارهای موجود تنها میتوان به کارهای انجام شده توسط دابکین1 و همکارانش اشاره کرد [5,13]. در [13] تنها وابستگی برخی از این مسایل به مساله درخت تصمیم شرح داده میشود. به عنوان مثال دابکین عملکرد یک درخت تصمیم img0 را به این صورت تعریف میکند که کلیه مثال‌های آموزشی را در یک بعد k قسمت کنیم، بطوریکه در هر قسمت بیشترین تعداد نقاط همرنگ وجود داشته باشند. به عنوان مثالی دیگر، ابرمستطیل با حداکثر اختلاف دو رنگ به گونه‌ای متفاوت درخت تصمیم مربوطه را ایجاد میکند [5,13]. در اینجا هر بعد دقیقا به سه قسمت تقسیم می‌شود و در نهایت ابرمستطیل ایجاد شده بیشترین تعداد نقاط همرنگ را دارا خواهد بود.

1-2- نتایج بدست آمده

مهم­ترین ویژگی این مقاله، توجه به مسایل هندسه محاسباتی در حوزه کاربردی میباشد. تاکنون در هیچیک از کارهای انجام شده در زمینه تفکیکپذیری نقاط در هندسه محاسباتی، به پیادهسازی الگوریتمهای موجود بر روی دادههای واقعی و کاربرد عینی این مسایل در یادگیری ماشین پرداخته نشده است. نزدیکترین کارهای موجود به این مقاله، کارهای ارائه شده توسط دابکین و همکارانش میباشد که در آن چندین مساله تفکیکپذیری ارائه و تنها به کاربرد آنها در زمینه درختهای تصمیم اشاره میگردد [5,13]. در هیچیک از کارهای موجود در زمینه تفکیکپذیری به تحلیل الگوریتم از نظر دقت و سرعت و مقایسه با الگوریتمهایی که در دنیای واقعی اجرا میشوند پرداخته نمیشود. بنابراین، یکی از نقاط ضعف کارهای موجود عدم اجرای این الگوریتمها بر روی دادههای واقعی میباشد که در این مقاله به شدت مورد توجه میباشد. در این مقاله محاسبه ابرمستطیل با حداکثر اختلاف دو رنگ مورد توجه قرار می‌گیرد. این مساله را در یک، دو، سه و m بعد پیاده‌سازی می‌کنیم. هنگام پیاده‌سازی الگوریتم در بیش از یک بعد به گونه‌ای متفاوت از الگوریتم اصلی رفتار می‌کنیم تا بتوانیم یک ابرمستطیل جداکننده تقریبی که زمان ساخت آن پیچیدگی محاسباتی کمتری داشته باشد ایجاد کنیم. از بین کلیه آزمایش‌های انجام ‌شده، بهترین نتیجه با پیاده‌سازی این مساله در یک بعد حاصل شد. نتایج پیاده‌سازی این مساله در یک بعد و تحلیل سرعت اجرای الگوریتم، در مقایسه با الگوریتم C4.5 بیانگر آن است که الگوریتم ارائه شده، الگوریتمی قابل رقابت با الگوریتم C4.5 است.

در ادامه، ابتدا در بخش 2 الگوریتم C4.5 را معرفی میکنیم. پس از آن در بخش 3 به معرفی ابرمستطیل با حداکثر اختلاف دو رنگ، ارتباط آن با درخت تصمیم و الگوریتمهای مربوط به آن میپردازیم. پیادهسازی آزمایش‌های مختلف و نتایج آن‌ها در بخش 4 آورده می‌شود. این نتایج با نتایج بدست آمده توسط الگوریتم C4.5 مقایسه می‌گردد. در آخر در بخش 5 نیز نتیجه‌گیری و مسایل باز آورده می‌شود.

2- الگوریتم C4.5

در این بخش به معرفی الگوریتم یادگیری درخت تصمیم C4.5 میپردازیم. محاسبه فرضیه متناظر با الگوریتم C4.5 مشابه چیزی است که در قسمت مقدمه به آن اشاره شد. به عبارتی برای ساخت درخت C4.5 مشابه درختهای تصمیم پایه، به ترتیب یک ویژگی انتخاب میکنیم و انشعابهای متناظر با آن را ایجاد میکنیم و اینکار را تا زمانی ادامه میدهیم که کلیه دادههای متناظر با هر برگ به خلوص کافی دست یابند. منتها الگوریتمهای درخت تصمیم پایه، فاقد برخی از ویژگیها از قبیل قابلیت برخورد با ویژگیهای پیوسته- مقدار، قابلیت برخورد با مشکل بیش پوشش2، انتخاب یک ویژگی مناسب در هر سطح از درخت، قابلیت برخورد با دادههای آموزشی با برخی مقادیر ویژگیهای نامعلوم3 و قابلیت توسعه کارایی محاسباتی الگوریتم میباشند. اغلب این موارد در الگوریتم C4.5 لحاظ شده است [1]. از این الگوریتم در انجام آزمایشها، به عنوان یک معیار مقایسه استفاده میگردد.

 

3- ابرمستطیل با حداکثر اختلاف دو رنگ

در این بخش با مفهوم ابرمستطیل با حداکثر اختلاف دو رنگ آشنا میشویم. ابتدا در یک زیر بخش به تعریف رسمی ابرمستطیل با حداکثر اختلاف دو رنگ میپردازیم. پس از آن در زیر بخشهای جداگانه به معرفی الگوریتم در ابعاد مختلف خواهیم پرداخت.

3-1- تعریف و ارتباط با درختهای تصمیم

ابتدا مفهوم ابرمستطیل با حداکثر اختلاف دو رنگ را به صورت رسمی مطرح میکنیم و سپس ارتباط آن با درخت تصمیم را با رسم شکل نشان میدهیم.

فرض کنید داده‌های آموزشی به همراه برچسب‌های آن‌ها (برچسب‌های مثبت و منفی) داده شده است. این ‌داده‌ها، مجموعه نقاط S در فضای m بعدی را تشکیل می‌دهند. برچسب هریک از داده‌ها به کمک رنگ آن‌ها نشان داده می‌شود. بنابراین، می‌توان داده‌های آموزشی را با رنگ‌های قرمز و آبی مجزا کرد. در مساله محاسبه مستطیل با حداکثر اختلاف دو رنگ، هدف، حداکثرسازی درجه خلوص داده‌های آموزشی پوشش داده شده با یک فرضیه‌ مستطیل‌شکل و موازی محورهای مختصات است. منظور از حداکثر خلوص، محاسبه مستطیلی است که بیشترین نقاط آبی و کمترین نقاط قرمز را داراست. درنتیجه ابرمستطیل بدست آمده دارای بیشترین اختلاف دو رنگ است. به شکل 1 توجه کنید. در این شکل نقاط قرمز و آبی به ترتیب با علامت img0 و ● مشخص شده‌اند.

چنانچه بخواهیم این مساله را با عبارات ریاضی مدل کنیم به روابط زیر می‌رسیم. ابتدا از تابع نگاشت رابطه (1) برای مشخص کردن هریک از داده‌های مثبت و منفی استفاده می‌کنیم.

img0                                                   (1)

سپس img0 به صورت زیر تعریف می‌شود:

img0                                       (2)

در واقع img0 به نوعی بیانگر اختلاف تعداد داده‌های مثبت پوشیده شده توسط فرضیه مستطیل- شکل img0 و داده‌های منفی به اشتباه پوشیده شده توسط این فرضیه است. در مساله محاسبه ابرمستطیل با حداکثر تمایز دو رنگ به دنبال برآورده کردن رابطه )3( هستیم.

img0                                                  (3)

ابرمستطیلی را در نظر بگیرید که در رابطه بالا صدق می‌کند. یعنی از بین کلیه ابرمستطیل‌ها، ابرمستطیلی داریم که بیشترین تعداد نقاط آبی و کمترین تعداد نقاط قرمز را پوشش می‌دهد. ابرمستطیلی که دارای بیشترین تمایز دو رنگ است، تعداد نقاط قرمز داخل ابرمستطیل و نقاط آبی خارج از آن‌ را کمینه می‌کند. نقاط قرمز داخل ابرمستطیل به همراه نقاط آبی خارج از آن، معادل img0 است. منظور از img0 خطای نمونه برای کلیه فرضیه‌های مستطیل‌- شکل است. بنابراین، بدست آوردن ابرمستطیل با حداکثر تمایز دو رنگ معادل پیداکردن فرضیه‌ای با حداقل خطای img0 است.

 

 

[1] . Dobkin

[2] . Overfitting

[3] . Missing value

 

شکل 1: محاسبه مستطیل با حداکثر تمایز دو رنگ (در این شکل نقاط قرمز با علامت img0 مشخص شده‌اند )[5]

 

 

شکل 2: مرزهای جداکننده درخت‌ تصمیم img0

 

 

شکل 3: درخت تصمیم متناظر با شکل 2

 

 

 

شکل 4: نگاشت نقاط مابین دو خط افقی روی یک خط

 

 

قضیه 1- از بین کلیه فرضیه‌های مستطیل‌- شکل که داده‌های آموزشی را رده‌بندی می‌کند، مستطیلی که دارای بیشترین تمایز دو رنگ است دارای کمترین مقدار img0 است [5].لازم است اشاره کنیم اگر داده‌های آزمون به خوبی از توزیع جامعه انتخاب شوند، img0 تقریب خوبی از img0 خواهد بود. img0 خطای واقعی فرضیه h را نشان می‌دهد. بنابراین، از بین کلیه فرضیه‌های مستطیل- شکل به دنبال مستطیل با بیشترین تمایز دو رنگ خواهیم بود. برای روشن شدن ارتباط بین درخت تصمیم و ابرمستطیل با حداکثر اختلاف دو رنگ ابتدا به شکل 2 توجه کنید. در این شکل(شماره 2) مرزهای جداکننده درخت تصمیم img0 نشان داده شده است.درخت تصمیم یک‌سطحی معادل آن در شکل 3 آورده شده است.به صورت مشابه، بازه با حداکثر اختلاف دو رنگ را می‌توان معادل یک درخت تصمیم یک‌سطحی دانست بطوریکه ریشه دارای سه انشعاب برای مقادیر کمتر از ابتدای بازه، مقادیر مابین ابتدا و انتهای بازه و مقادیر بیشتر از انتهای بازه است. به همین ترتیب مستطیل، معادل یک درخت تصمیم دوسطحی و ابرمستطیل  mبعدی، معادل یک درخت تصمیم m سطحی با حداکثر سه انشعاب در هر گره است. پیدا کردن ابرمستطیل با حداکثر اختلاف دو رنگ معادل بدست آوردن هریک از انشعاب‌های درخت تصمیم متناظر آن است.

3-2- الگوریتم در حالت یک‌‌ بعدی

در حالت یک‌بعدی فرض می‌شود کلیه داده‌های آموزشی تنها دارای یک خصیصه هستند. در غیر اینصورت می‌توان یکی از خصایص آن‌ها را با استفاده از روش‌های انتخاب خصیصه1 انتخاب کرد. در هر حال شناسایی رده مربوط به هر داده، تنها با استفاده از یکی از خصایص آن‌ها انجام می‌شود. در اینجا ابتدا کلیه مثال‌های آموزشی روی محور متناظر با خصیصه انتخابی تصویر می‌شوند. منظور از ابرمستطیل با حداکثر اختلاف دو رنگ، بازه‌ای است که بیشترین تعداد نقاط آبی و کمترین تعداد نقاط قرمز را داراست. به شکل 4 توجه کنید.

الگوریتم در حالت یک‌بعدی به زمان پیش‌پردازش img0 نیاز دارد که در آن n تعداد کل دادههای آموزشی است [5]. این مرتبه زمانی مربوط به مرتبسازی کلیه داده‌های آموزشی روی محور با خصیصه انتخابی است. فرض کنید پس از تصویر کلیه داده‌های آموزشی روی محور مربوطه، کلیه داده‌ها در بازه بسته img0 قرار گیرند.

حال تعاریف زیر را در نظر بگیرید:

-       img0: زیربازه‌ای از A است که از بین کلیه زیربازه‌های A، دارای بیشترین مقدار img0 است. بنابراین، اگر کلیه نقاط در بازه img0 محدود شده باشند ما به دنبال img0 هستیم.

-       img0: زیربازه‌ای از A است که از میان کلیه زیربازه‌های A که نقطه ابتدای بازه آن‌ها با نقطه ابتدای بازه A برابر است، دارای بیشترین مقدار img0 است.

-       img0: زیربازه‌ای است که از میان کلیه زیربازه‌های A که نقطه انتهای آن‌ها با نقطه انتهای بازه A برابر است دارای بیشترین مقدار img0 است.

مساله محاسبه بازه با بیشترین اختلاف دو رنگ به کمک یک درخت و با استفاده از روش تقسیم و حل پیاده‌سازی می‌شود. ابتدا در مورد راهکار تقسیم و حل بکار گرفته شده صحبت میکنیم و سپس اجرای الگوریتم به کمک درخت ذکر شده در الگوریتم یک آورده میشود.

در ابتدا بازهimg0 را به img0 زیربازه افراز می‌کنیم که در آن n تعداد کل دادههای آموزشی است و در هر زیربازه حداکثر دو داده قرار میگیرد. بنابراین، زیربازههای ایجاد شده همه دادههای آموزشی را پوشش میدهند و اشتراک هر دو زیربازه با یکدیگر تهی است. برای هر زیربازه ایجاد شده، سه زیربازه بیشینه2 گفته شده را محاسبه می‌کنیم. سپس، از چپ به راست L و R را دو زیربازه متوالی غیرهمپوشان تعریف میکنیم. اگر این دو زیربازه را با یکدیگر ترکیب کنیم، بازه LR بدست می‌آید. واضح است که img0 برابر img0 یا img0 و یا img0 خواهد بود. اشاره می‌کنیم منظور از img0 بهترین بازه موجود با بیشترین

[1] . Feature selection

[2] . Maximal

اختلاف دو رنگ پس از ترکیب L و R است. از طرفی img0 برابر img0 و یا img0 است. همچنین، img0 برابر img0 و یا img0 است. حال L و R جدید را دو زیر بازه متوالی بعد از L و R قبلی در نظر میگیریم و روند بالا را برای آنها تکرار میکنیم. این کار را تا زمانی که تمامی img0 زیر بازه ایجاد شده پیمایش شوند تکرار میکنیم. به این ترتیب به تعداد img0 زیر بازه LR به همراه زیربازههای بیشینه آنها محاسبه میگردد. حال img0 زیر بازه جدید را در نظر میگیریم و کل مراحل الگوریتم گفته شده را بر روی آنها تکرار میکنیم. این روند تا زمانی ادامه مییابد که تنها بازه img0 مشاهده شود و سه زیربازه بیشنه متناظر با آن محاسبه گردد.

 

 

 

 

الگوریتم 1- محاسبه بازه با حداکثر اختلاف دو رنگ

ورودی: تصویر کلیه داده‌های آموزشی روی محور متناظر با خصیصه انتخابی و مقیاس شده در بازه img0

خروجی: بازه با حداکثر اختلاف دورنگ img0

1- یک درخت دودویی به ارتفاع img0 ایجاد کن. این درخت شامل img0 برگ میباشد.

2- بازه img0 را به img0 زیر بازه افراز کن. هر زیربازه دارای حداکثر دو نقطه از مجموعه S خواهد بود. از طرفی افراز به نحوی انجام می‌شود که نقاط ابتدا و انتهای بازه روی نقاط متناظر با مجموعه S واقع نشود. زیربازه‌های بدست آمده را در برگ‌های درخت درج کن. برای هر زیربازه A، سه زیربازه بیشینه img0، img0و img0 را محاسبه کن و آن‌ها را در گره متناظر با زیربازه A در درخت ذخیره کن. بنابراین، هر گره از درخت شامل زیر بازه A و زیر بازههای img0، img0و img0 میباشد.

3- هر دو زیربازه متوالی را با یکدیگر ادغام کن. به این ترتیب گره والد مربوط به دو زیر درخت متناظر با آن دو زیربازه مقداردهی می‌شود. پس از عملیات ادغام، سه بیشینه گفته شده را به کمک بیشینه‌های ذخیره شده در فرزندان آن بدست آور و آنها را در گره مربوطه ذخیره کن. واضح است که تعداد گرههای این سطح از درخت نصف تعداد گرههای سطح پایینی است.

4- پس از ادغام زیربازه‌ها اگر بازه img0 بدست آمد img0 را بازگردان. درغیراینصورت به مرحله 3 برو.

 

الگوریتم 1: محاسبه بازه با حداکثر اختلاف دو رنگ. اقتباس شده از [5]

 

حال به بیان شبه کد مربوط به الگوریتم محاسبه img0 می‌پردازیم. در این شبه کد از یک درخت دودویی برای اجرای الگوریتم استفاده میکنیم. به الگوریتم 1 توجه کنید.

قضیه 2- اگر کلیه نقاط در مرحله پیش‌پردازش الگوریتم مرتب شده باشند، بدست آوردن بازه‌ای که دارای بیشترین اختلاف دو رنگ است در زمان خطی امکان‌پذیر است [5].

3-3- الگوریتم در حالت 1 بعدی پویا

الگوریتم به سادگی می‌تواند با کمی تغییرات در حالت پویا نیز استفاده گردد. یعنی به سادگی میتواند درج و حذف را نیز پشتیبانی کند. کافی است یک درخت دودویی روی کلیه بازه‌ها مشابه قبل ساخته شود. برای حذف یک داده از مجموعه داده‌ها لازم است یک مسیر از ریشه به برگ پیموده شده و برگ متناظر با آن داده را بدست آوریم. سپس به ازای کلیه گرههای موجود در مسیر پیموده شده، لازم است سه بیشینه مربوط به آن را بروز کنیم.

قضیه 3- بدست آوردن زیربازه با حداکثر اختلاف دو رنگ، پس از هر عمل درج و یا حذف یک نقطه از مجموعه نقاط در زمان img0 امکان‌پذیر است [5].

پیچیدگی زمانی پایین الگوریتم برای حالت 1بعدی پویا به ما کمک می‌کند که بتوانیم از این الگوریتم در الگوریتم‌های یادگیری برخط1 نیز استفاده کنیم.

3-4- الگوریتم در حالت d بعدی

الگوریتم در حالت یک‌بعدی قابل تعمیم به ابعاد بالاتر نیز خواهد بود. محاسبه مستطیل با حداکثر اختلاف دورنگ در حالت دوبعدی با استفاده از تکنیک خط جاروب [14] و الگوریتم در حالت 1بعدی پویا امکان‌پذیر است.

برای محاسبه مستطیل با حداکثر اختلاف دورنگ، هر بار اضلاع بالایی و پایینی مستطیل را ثابت فرض میکنیم و کلیه نقاط مابین اضلاع بالایی و پایینی را روی محور x نگاشت میکنیم. حال با محاسبه بازه با حداکثر اختلاف دو رنگ میتوان اضلاع چپ و راست این مستطیل را محاسبه کرد. اگر img0 شامل مختصه y همه نقاط باشد، بنابراین، img0 جفت مقدار مختلف برای اضلاع بالایی و پایینی مستطیل وجود دارد. حال با استفاده از تکنیک خط جاروب که از بالا تا پایین، مختصه y نقاط را ملاقات میکند و الگوریتم 1بعدی پویا میتوان الگوریتمی کارا برای محاسبه مستطیل با حداکثر اختلاف دورنگ ارائه کرد.

قضیه 4- فرض کنید مجموعه S دارای n عضو است. همچنین از تابع نگاشت img0 استفاده کرده‌ایم. بدست آوردن مستطیلی موازی محورهای مختصات که دارای بیشترین اختلاف دو رنگ است در زمان img0 و حافظه img0 امکان‌پذیر است [5].الگوریتم مستطیل با حداکثر اختلاف دو رنگ به سادگی می‌تواند برای حالت d بعدی نیز بکار برده شود. مساله پیداکردن ابرمستطیل با حداکثر اختلاف دو رنگ در d بعد به زمان img0 و حافظه img0 نیاز دارد [5].

4- پیاده‌سازی آزمایش‌های گوناگون و نتایج

در این بخش به معرفی آزمایش‌های گوناگون با استفاده از الگوریتمهای معرفی شده در بخشهای قبل و پیاده‌سازی آن‌ها می‌پردازیم.

4-1- معرفی مجموعه داد‌ه‌های فراهم شده برای پیاده‌سازی

ابتدا مجموعه‌داده‌هایی را که برای ارزیابی آزمایش‌ها از آنها استفاده کرده‌ایم را معرفی می‌کنیم. ما برای پیاده‌سازی الگوریتم از 9 مجموعه داده استفاده کردیم. مجموعه داده‌ها از پایگاه داده UCI [15] انتخاب گردید. مشخصات مجموعه داده‌های انتخابی در جدول 1 آورده شده است. در این جدول ستون مقادیر نامشخص2 نشان می‌دهد آیا از بین کلیه مثال‌های یک مجموعه، مثالی با یک مقدار ویژگی نامعلوم وجود دارد یا خیر. منظور از خط مبنا3 در این جدول بیشترین درصد مثال‌ها از یک رده است. به عبارتی اگر یک الگوریتم کاملا تصادفی به هریک از داده‌های آموزشی یک برچسب انتساب دهد به دقتی برابر با خط مبنا خواهد رسید. بنابراین، لازم است الگوریتم یادگیر، به دقتی قابل توجه

 

[1] . Online learning

[2] . Missing value

[3] . Baseline

جدول1: معرفی مجموعه داده‌ها.

نام

سال

نوع خصایص

تعداد داده

تعداد خصایص

مقادیر نامشخص

خط مبنا

BL

2008

حقیقی

748

4

خیر

76.2

HA

1999

صحیح

306

3

خیر

73.52

BCW

1992

صحیح

699

10

بله

65.52

IO

1989

صحیح/حقیقی

351

34

خیر

64.1

MA

2007

حقیقی

19020

10

خیر

64.8

PI

1990

صحیح/حقیقی

768

8

بله

65.1

PA

2008

حقیقی

195

22

خیر

75.38

CO

 

حقیقی

208

60

خیر

53.36

G2

1987

حقیقی

163

9

خیر

53.4

 

نسبت به خط مبنا دست یابد. سایر ستون‌ها نیز سایر خصایص داده‌ها را معین می‌سازد. هنگام انتخاب از میان مجموعه داده‌های حقیقی- مقدار یا صحیح- مقدار تلاش کردیم به تعداد خصایص، تعداد داده‌ها و خط مبنا توجه کنیم بطوریکه تنوع در میان مجموعه‌های انتخابی موجود باشد.

4-2- آزمایش‌های انجام شده

ارزیابی الگوریتم‌های پیاده‌سازی شده بر اساس معیار دقت1 و پیچیدگی زمانی آن‌ها صورت می‌گیرد. رابطه مربوط به محاسبه دقت به صورت زیر است:

img0                             (4)

در این رابطه، منظور از img0 (img0) داده‌های مثبت (منفی) است که توسط فرضیه موجود، مثبت (منفی) رده‌بندی می‌شوند. همچنین img0 تعداد کل داده‌های مثبت و img0 تعداد کل داده‌های منفی است. در واقع، به کمک رابطه بالا نسبت داده‌هایی که به درستی رده‌بندی شده‌اند به کل داده‌ها محاسبه می‌شود.

آزمایش 1- پیاده‌سازی الگوریتم C4.5 

برای ارزیابی عملکرد الگوریتم ابرمستطیل با حداکثر اختلاف دو رنگ لازم است این الگوریتم با یک الگوریتم پایه مقایسه گردد. به همین دلیل الگوریتم C4.5 را به عنوان معیار مقایسه در نظر می‌گیریم. ابتدا به کمک نرم‌افزار وکا2 [16] الگوریتم j.48 (الگوریتم C4.5) را روی تک‌تک مجموعه داده‌ها اجرا می‌کنیم. در اجرای الگوریتم از روش تصدیق- متقاطع3 با 3 بخش4 استفاده کردیم. همچنین، در این پیادهسازی درختهای ایجاد شده درختهایی دودویی است که در آن در هر مسیر از ریشه به برگ ممکن است چندین بار یک خصیصه مشاهده گردد. نتایج این الگوریتم در جدول 2 در سطر دوم آورده شده است.

اشاره می‌کنیم برای پیاده‌سازی کلیه آزمایش‌هایی که در ادامه آورده می‌شوند از زبان برنامه‌سازی C# و پایگاه داده SQL استفاده کردیم. همچنین، از آنجا که در مجموعه داده‌های خود مجموعه ‌داده‌هایی با مقادیر نامعلوم به ازای برخی خصایص وجود دارد در کلیه آزمایش‌ها با این داده‌ها کاملا بدبینانه رفتار می‌کنیم. یعنی اگر خصیصه انتخاب ‌شده دارای برخی مقادیر نامشخص باشد فرض می‌کنیم داده‌ متناظر با آن، توسط فرضیه بدست آمده اشتباه رده‌بندی می‌شود.

آزمایش 2- ابرمستطیل با حداکثر اختلاف دو رنگ (MBD5-*d)

در اینجا الگوریتم محاسبه ابرمستطیل dبعدی با حداکثر اختلاف دو رنگ را به گونه‌ای متفاوت اجرا می‌کنیم. مراحل اجرای این آزمایش در آزمایش 2 آورده شده است.

 

[1] . Accuracy

[2] . Weka

[3] . Cross- validation

[4] . Fold

[5] . Maximum bichromatic discrepancy

جدول 2: نمایش معیار دقت در آزمایش‌های مختلف

 

BCW

BL

G2

HA

IO

MA

PI

PA

CO

C4.5

94.27

76.73

80.36

70.26

90.88

85.01

73.3

84.1

72.11

MBD-1d

92.15

74.14

73.76

72.73

81.27

73.52

73.62

83.13

70.72

MBD-2d

93.37

74.98

70.36

73.33

87.08

75.64

67.85

82.93

69.41

MBD-3d

93.6

76.19

66.7

73.25

86.84

75.32

65.98

78.93

66.74

MBD-4d

94.01

76.23

63.27

-

86.43

74.74

65.47

77.03

63.4

MBD-5d

93.9

-

59.38

-

83.03

74.06

65.52

70.56

60.75

MBD-md

91.96

-

49.49

-

59.26

72

65.26

50.8

47.05

Hi-MBD-1d

91.54

72.92

71.9

70.2

80.69

73.6

72.57

83.03

69.2

 

1- img0 داده‌ها به صورت تصادفی به مجموعه آزمون و img0 داده‌ها به مجموعه آموزشی تخصیص می‌یابد.

2- یک خصیصه انتخاب می‌شود و بازه با حداکثر اختلاف دو رنگ به ازای آن خصیصه روی مثال‌های آموزشی به همراه دقت رده‌بندی آن، محاسبه می‌شود.

3- مرحله 2 را به تعداد خصایص تکرار می‌کنیم. بهترین خصیصه را از نظر دقت رده‌بندی بدست می‌آوریم. کلیه داده‌های خارج از بازه متناظر با بهترین خصیصه را از مجموعه داده‌ها حذف می‌کنیم. همچنین خصیصه انتخابی از مجموعه خصایص حذف می‌شود.

4- اگر img0 باشد به تعداد d بار هریک از مراحل 2 و 3 روی خصایص باقیمانده و همچنین داده‌های باقیمانده تکرار میکنیم. به این ترتیب بازه با حداکثر اختلاف دو رنگ به ازای d خصیصه محاسبه می‌گردد. این d بازه را به عنوان تقریبی از ابرمستطیل با حداکثر اختلاف دو رنگ می‌شناسیم. ابر مستطیل بدست آمده، فرضیه مورد نظر ما است. دقت این فرضیه بر روی داده‌های آزمون مورد ارزیابی قرار می‌گیرد. برای پیشگویی رده داده آزمون با استفاده از فرضیه محاسبه شده، کلیه نقاط خارج از ابرمستطیل، منفی و کلیه نقاط داخل آن مثبت رده‌بندی می‌شوند.

5- هریک از مراحل 1 تا 4 را 100 بار تکرار کرده و نتایج بدست آمده را میانگین‌گیری می‌کنیم.

آزمایش 2: محاسبه ابرمستطیل با حداکثر اختلاف دو رنگ (MBD-*d)

 

چنانچه در آزمایش 2 گفته شد، ما به جای محاسبه دقیق ابرمستطیل با حداکثر اختلاف دو رنگ و با زمان اجرای img0، d بار الگوریتم بازه با حداکثر اختلاف دو رنگ را اجرا میکنیم. در هر بار، برای انتخاب بهترین خصیصه الگوریتم بازه با حداکثر اختلاف دورنگ را به تعداد خصایص تکرار میکنیم. به این ترتیب اجرای آزمایش 2 در زمان img0 امکانپذیر است. با این تقریب به جای الگوریتم ابرمستطیل با حداکثر اختلاف دو رنگ، می‌توان به پیاده‌سازی سرراست و با پیچیدگی محاسباتی کمتری نسبت به پیاده‌سازی الگوریتم اصلی دست یافت.

نتایج بدست آمده با این آزمایش در جدول 2 آورده شده است. در پیادهسازی آزمایش MBD-*d، علامت * محاسبه ابرمستطیل d بعدی را نشان میدهد. به عنوان مثال، MBD-3d ابرمستطیل سه بعدی و MBD-md ابرمستطیل m بعدی را نشان میدهد، که در آن m تعداد خصایص مجموعه داده متناظر میباشد. به عنوان مثال مجموعه داده HA دارای سه خصیصه است. بنابراین، مقادیر MBD-4d و MBD-5d برای آنها بیمعنا است و در جدول به جای آنها خط تیره گذاشته شده است. توجه به مقادیر به دست آمده برای مجموعه دادههای گوناگون، نشان میدهد که در اکثر موارد با افزایش تعداد ابعاد پیادهسازی، دقت فرضیه محاسبه شده کاهش مییابد.

آزمایش 3- بازه با حداکثر اختلاف دو رنگ سلسله مراتبی (Hi-MBD-1d)

با اجرای آزمایش 2 دیدیم که هرقدر تعداد ابعاد افزایش می‌یابد دقت فرضیه محاسبه شده کاهش می‌یابد. بنابراین، نتیجه گرفتیم یک خصیصه تکی نسبت به مجموعه‌ای از خصایص نماینده بهتری از کل داده‌ها برای رده‌بندی است. به همین دلیل تلاش کردیم الگوریتم یک بعدی را مقداری بهبود بخشیم. به همین دلیل از روش بازه با حداکثر اختلاف دو رنگ سلسله مراتبی استفاده کردیم. درواقع پس از محاسبه بازه با بیشترین تعداد نقاط آبی و کمترین نقاط قرمز، کلیۀ

کلیه نقاط خارج از بازه را از مجموعه نقاط حذف می‌کنیم. سپس از مجموعه نقاط باقیمانده، بازه با بیشترین نقاط قرمز و کمترین نقاط آبی را محاسبه می‌کنیم. در واقع محور مورد نظر به 5 قسمت تقسیم می‌شود. این پنج بازه را به عنوان فرضیه دلخواه درنظر می‌گیریم. به ترتیب داده‌های موجود در هریک از بازه‌ها، برچسب قرمز، آبی، قرمز، آبی و قرمز خواهند گرفت. نتایج اجرای این الگوریتم نیز در جدول 2 آورده شده است.

4-3- تحلیل نتایج

با توجه به داده‌های جدول 1، میانگین خط مبنا برای 9 مجموعه داده استفاده شده برابر با 65.7 درصد است. میانگین دقت الگوریتم C4.5 برابر با 80.78 درصد، الگوریتم MBD-1d دارای میانگین دقت 77.22 درصد و MBD-2d میانگین دقت 77.21 درصد است. خواهیم دید با افزایش d، میانگین دقت مرتب کاهش می‌یابد بطوریکه میانگین دقت الگوریتم MBD-md به 65.03 درصد می‌رسد که در آن m تعداد ابعاد داده‌ها را مشخص می‌سازد.

میانگین دقت الگوریتم Hi-MBD-1d نیز برابر 76.18 است. بنابراین، پس از آزمایش یک (الگوریتم C4.5)، بهترین آزمایش انجام شده، آزمایش 2 با img0 است. یعنی از بین پیاده‌سازی‌های موجود برای محاسبه ابرمستطیل با حداکثر اختلاف دو رنگ، بازه با حداکثر اختلاف دو رنگ بیشترین دقت را داراست.

دقت این آزمایش 11.5 درصد از میانگین خط مبنا بالاتر و 3.56 درصد از آزمایش 1 یعنی الگوریتم شناخته‌شده C4.5 کمتر است.

چنانچه به نتایج جدول 2 توجه کنیم، می‌بینیم کارایی الگوریتم مطرح شده به ازای سه مجموعه داده IO، G2 و MA ضعیف است.

 اگر این سه مجموعه داده را از مجموعه داده‌های خود حذف کنیم، می‌بینیم دقت آزمایش 2 به اندازه 0.7 درصد از دقت الگوریتم C4.5 کمتر خواهد شد.

از طرفی میدانیم در پیادهسازی مستطیل با حداکثر اختلاف

دورنگ، ابتدا یک خصیصه انتخاب میکنیم و بهترین بازه متناظر با آن را بدست میآوریم. سپس، کلیه نقاط خارج از بازه را حذف میکنیم.

 به ازای نقاط داخل بازه همینکار را به ازای ابعاد دیگر تکرار میکنیم. این در حالی است که در الگوریتم C4.5 نقاط موجود در هیچ یک از نواحی دور ریخته نمیشود و تقسیمبندی به ازای کلیه نواحی تا رسیدن به بیشترین خلوص ادامه مییابد. بنابراین، تا حدی دقت کمتر الگوریتم مطرح شده نسبت به الگوریتم C4.5 قابل توجیه است. به عبارتی در الگوریتم C4.5، کلیه ندهای درخت تا رسیدن به بیشترین خلوص بسط مییابند.

در صورتی که در الگوریتم بازه با حداکثر اختلاف دورنگ تنها یک مسیر از ریشه به برگ بسط مییابد. واضح است که بسط تنها یک مسیر از درخت از ریشه تا برگ در زمان کمتری انجام میشود.

حال چنانچه img0  انتخاب شود در واقع تنها با یک درخت تصمیم یک سطحی و با سه انشعاب روبرو هستیم که از نظر پیچیدگی محاسباتی بسیار کاراتر از الگوریتم درخت تصمیم C4.5 خواهد بود. این در حالی است که دقت الگوریتم جاری تقریبا مشابه الگوریتم C4.5 است. بنابراین، الگوریتم ارائه شده در این مقاله الگوریتمی قابل رقابت با الگوریتم C4.5 معرفی میشود.

5- نتیجه‌گیری و مسایل باز

در این مقاله الگوریتم محاسبه ابرمستطیل با حداکثر اختلاف دو رنگ که یکی از مسایل شناخته شده در هندسه محاسباتی است را معرفی کردیم. پس از بیان تئوری کافی در این زمینه، آزمایش‌های متعدد با استفاده از این الگوریتم روی 9 مجموعه داده انجام شد.

 

 

 

 

 

سپس، کارایی این الگوریتم‌ها را با الگوریتم شناخته‌شده C4.5 مقایسه کردیم. چنانچه دیدیم کارایی الگوریتم بازه با حداکثر اختلاف دو رنگ به اندازه 3.56 درصد از الگوریتم C4.5 کمتر است. از طرفی محاسبات انجام شده برای بدست آوردن ابرمستطیل با حداکثر اختلاف دو رنگ در مقایسه با الگوریتم C4.5 کمتر خواهد بود. بنابراین، می‌توان این الگوریتم را به عنوان یک الگوریتم قابل رقابت با الگوریتم C4.5 معرفی کرد. تحلیل بیشتر هریک از مجموعه داده‌ها و بررسی عدم کارایی این الگوریتم روی برخی از مجموعه داده‌ها، همچنین بهبود عملکرد این الگوریتم به عنوان یک مساله باز پیشنهاد میگردد.

به عنوان یکی از کارهایی که می‌توان برای بهبود عملکرد این الگوریتم پیشنهاد کرد آن است که ابتدا بر روی داده‌ها PCA اعمال گردد. به این ترتیب می‌توان محورهایی که داده‌ها دارای بیشترین پراش هستند را شناسایی کرد. حال اگر ابتدا دادهها را روی این محور نگاشت کنیم و سپس بازه با حداکثر اختلاف دو رنگ را محاسبه کنیم به کارایی بیشتری نسبت به الگوریتم مطرح شده دست خواهیم یافت. همچنین می‌توان این روش را به عنوان یک روش برای عمل گسسته‌سازی روی محورهای پیوسته‌- مقدار قبل از اعمال الگوریتم درخت‌های تصمیم معرفی کرد. چرا که چنانچه می‌دانیم یکی از مهمترین چالش‌های درخت تصمیم در برخورد با داده‌های پیوسته- مقدار، گسسته‌سازی آن‌ها با تقسیم محورهای مختصات به چندین بازه است. تصور می‌شود اگر این روش اعمال شده و سپس الگوریتم C4.5 را بر روی بازه‌های بدست آمده اجرا کنیم کارایی الگوریتم C4.5 به مقدار قابل توجهی افزایش یابد. پیاده‌سازی هریک از ایده‌های مطرح شده به عنوان کارهای آینده پیشنهاد می‌گردد.

 

 

 

 

 

 

 

 

 

منابع

1.T. M. Mitchell, Machine learning, McGraw-Hill, 1997.

2.P.L. Hammer, A. Kogan, B. Simeone, and S. Szedmak, “Pareto-optimal patterns in logical analysis of data,” Discrete Applied Mathematics, vol.144, pp.79-102, 2004.

3.M. Kreveld, T. Lankveld, and R. Veltkamp, “Identifying well-covered minimal bounding rectangles in 2D point data,” in 25th European Workshop on Computational Geometry, EWCG, 2009, pp.277-280.

4.J. Eckstein, P. Hammer, Y. Liu, M. Nediak, and B. Simeone, “The maximum box problem and its application to data analysis,” Journal of Computational Optimization and Application, vol.23, pp. 85-98, 2002.

5.D. P. Dobkin, D. Gunopulos, and W. Maass, “Computing the maximum bichromatic discrepancy with applications to computer graphics and machine learning,” Journal of Computer and System Science, vol.52, pp. 453–470, 1996.

6.Y. Liu, and M. Nediak, “Planar case of the maximum box and related problems,” in Proceedings 15th Canadian Conferance of Computational Geometry, CCCG, 2003, pp.14-18.

7.C. Cortés, J. Díaz-Báòez, P. Pérez-Lantero, C. Seara, J. Urrutia, and I. Ventura, “Bichromatic separability with two boxes: A general approach,” Journal of Algorithms, vol.64, pp.79-88. 2009.

8.C. Cortés, J. Díaz-Báòez, and J. Urrutia, “Finding enclosing boxes with empty intersection,” in Proceedings 23rd European Workshop on Computational Geometry, EWCG, 2006, pp.185-188.

9.ز. مصلحی، " تفکیک‌پذیری نقاط با اشیای هندسی در فضای دوبعدی،" پایان نامه کارشناسی ارشد دانشکده مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه صنعتی امیرکبیر، 1391.

10.ز. مصلحی، ع. باقری، " تفکیک پذیري سري نقاط دو رنگ با دو مستطیل مجزا و موازي محورهاي مختصات،" مجله علمی پژوهشی رایانش نرم و فناوري اطلاعات، جلد 1، شماره 2، صفحه 35-42، 1391.

11.S. Cabello, J. M. Díaz-Báñez, C. Seara, J. A. Sellarès, J. Urrutia, and I. Ventura, “Covering point sets with two convex objects,” in 21st European Workshop on Computational Geometry, EWCG, 2005, pp. 195-206.

12.S. Cabello, J. M. Díaz-Báñez, C. Seara, J. Urrutia, and I. Ventura, “Covering point sets with two disjoint disks or squares,” Computational Geometry: Theory and Application, vol.40, pp. 195-206, 2008.

13.D.P. Dobkin, and D. Gunopulos, “Geometric problems in machine learning, in Lecture Notes in Computer Science, LNCS, 1996, vol.1148, pp.121-132.

14.M. D. Berg, O. Cheong, M. V. Kreveld, and M. Overmars, Computational geometry: algorithms and applications, 3rd Edition, TELOS, Santa Clara, CA, USA, 2008.

15.K. Bache and M. Lichman. (2013). UCI Machine Learning Repository [Online]. Available: http://archive.ics.uci.edu/ml

16.I. H. Witten, E. Frank, and M. A. Hall, Data Mining: Practical machine learning tools and techniques, 3rd Edition, Morgan Kaufmann, San Francisco, 2011.

ضمیمه الف

در اینجا نام کامل هریک از مجموعه داده‌های بکار گرفته شده آورده شده است. در آخر نیز اشاره می‌کنیم برای دسترسی به هریک از مجموعه داده‌ها کافی است هریک از نام‌های گفته شده را در مرجع [15] جستجو کنید.

BL: Blood transfusion service center

HA: Haberman’s survival

BCW: Breast cancer wisconsin (original)

IO: Ionosphere

MA: Magic gamma telescope

PI: Pima indians diabets

PA: parkinson

CO: Connectionist bench

G2: Glass identification

 

 

 

 

 

 

 


مقالات مرتبط

حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1403-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]