Journal of Information Technology Management University of Tehran
ISSN: 2008-5893 Faculty of Management
EISSN: 2423-5059
Vol. 9, No. 1; PP. 123 – 142
Spring 2017

Attribute Reduction in Incomplete Information
System based on Rough Set Theory Using Fuzzy Imperialist Competitive Algorithm
Mohammad Ghanei Ostad 1, Hosein Khosravi Mahmoee 2, Majid Abdolrazzagh Nezhad 3
Abstract: In recent years, rough set theory has been considered as a strong solution to solve artificial intelligence problem such as data mining. But, the classic rough set theory is not effective in the case of attribute reduction in incomplete information systems. Since there are null values for some of attributes in a data set, an incomplete information system is created. In this paper, a novel method proposed to solve attribute reduction in incomplete information system based on rough set theory by combining and modifying imperialist competitive algorithm with fuzzy logic. Utilizing the fuzzy logic to control the parameters of the algorithm was useful and generated better solutions compared to its classic draft. In this research, no changes imposed on incomplete data, and it was just considered as a complete systems. The fuzzy imperialist competitive algorithm acted intelligently to reduce the number of attribute in incomplete information system, providing appropriate results that is worthy of attention.

Key words: Attribute reduction, Fuzzy logic, Imperialist competitive algorithm, Incomplete information system, Rough set theory.

MSc. Student in IT Engineering, University of Birjand, Iran
MSc. Student in IT Engineering, University of Birjand, Iran
Assistant Prof., Faculty of Engineering, Dep. of Computer, Bozorgmehr University of Qaenat, Qaen, Iran

Submitted: 13/ February / 2016
Accepted: 24 / January / 2017
Corresponding Author: Mohammad Ghanei Ostad
Email: m.ghanei1992@gmail.com

Journal of Information Technology Management د ناوری اطلاعات
دانشكدة مديريت دانشگاه تهران دورة 9، شمارة 1 بهار 1396
صص. 142- 123

كاهش ويژگي سيستمهاي اطلاعاتي ناقص بر مبناي تئوري مجموعة راف
با استفاده از الگوريتم رقابت استعماري فازي
محمد قانعي استاد1، حسين خسروي مهموئي2، مجيد عبدالرزاق نژاد3
چكيده: در سالهاي اخير، تئوري مجموعة راف به يكي از راهحلهاي قدرتمند در حل مسـائلهوش مصنوعي همچون دادهكاوي تبديل شده است. اما نسخة كلاسيك تئوري مجموعـة رافبراي بحث كاهش ويژگي در سيستمهاي اطلاعاتي ناقص، چندان مناسب نيست. يـك سيسـتماطلاعاتي ناقص به جدول هايي از دادهها اطلاق ميشود كه برخي درايههاي صفات آن مقداري ندارند. در اين مقاله، راهحل نويني كه تركيبي از الگوريتم رقابت استعماري و منطق فازي است، براي حل مسئلة كاهش ويژگي سيستمهاي اطلاعاتي ناقص مبتنـي بـر تئـوري مجموعـة رافارائه شده است. نتايج نشان داد استفاده از منطق فازي در كنتـرل پارامترهـاي الگـوريتم رقابـتاستعماري مفيد است و در مقايسه با نسخة كلاسيك الگوريتم، جوابهاي بهينهتـري بـه دسـتمي آورد. در روند اجراي اين پروژه، تغييري روي دادههاي ناقص اعمال نشـد و بـه آن همچـون سيستم اطلاعاتي كامل نگاه شد. الگوريتم رقابت استعماري فازي به صورت هوشمند عمل كرده و براي كاهش ويژگي در سيستمهاي اطلاعاتي ناقص، نتايج مناسبي ارائه داد كه درخـور تأمـلاست.

واژه هاي كليدي: الگوريتم رقابت استعماري، تئوري مجموعـة راف، سيسـتم اطلاعـاتي نـاقص،كاهش ويژگي، منطق فازي.

دانشجوي كارشناسي ارشد مهندسي فناوري اطلاعات، دانشكدة برق و كامپيوتر، دانشگاه بيرجند، بيرجند، ايران
دانشجوي كارشناسي ارشد مهندسي فناوري اطلاعات، دانشكدة برق و كامپيوتر، دانشگاه بيرجند، بيرجند، ايران
استاديار دانشكدة فني مهندسي، گروه مهندسي كامپيوتر، دانشگاه بزرگمهر قائنات، قائن، ايران

تاريخ دريافت مقاله: 24/11/1394
تاريخ پذيرش نهايي مقاله: 05/11/1395 نويسندة مسئول مقاله: محمد قانعي استاد
E-mail: m.ghanei1992@gmail.com
مقدمه
امروزه در بيشتر سازمانها، دادهها به سرعت جمعآوري و ذخيره مي شوند، اماميتـوان ادعـا كـرد عليرغم اين حجم انبوه داده، سازمانها با فقر دانش در تصـميم گيـري روبـه رو هسـتن د ( هـان و كمبر، 2006). همچنين با توجه به ذخيرة دهها، صـدها يـا حتـي هـزاران ويژگـي در پايگـاه دادةبرنامههاي كاربردي، بحث كاهش ويژگي در جهت تحليل اين دادهها، امر ضروري و انكارناپـذيراست (گايون و اليزف، 2003؛ يو، 2005). در بررسـي پايگـاههـاي داده، گـاهي بـا سيسـتمهـاياطلاعاتي ناقص1 مواجه ايم. سيستم اطلاعاتي ناقص به جدول هايي از دادهها اطلاق ميشود كـهبرخي درايههاي صفات آن بي مقدارند (اورلاسكا و پاولاك، 1984). يكي از رويكردهـا ي تحليـلاين سيستمها، اين است كه سطر مربوط به مقادير ناقص را حذف كنـيم (كميلسـكي، گ ريزمـالا،پترسن و تان، 1993)؛ اما اين رويكرد مناسب نيست، زيرا اندازة دادهها را كاهش مي دهد و امكان حذف اطلاعات مفيد وجود دارد. روش ديگر براي تحليل اين نوع سيسـتم هـاي اطلاعـاتي ايـناست كه دادههاي ناموجود را به صورتهاي مختلف مقداردهي كنيم. براي مثـال از تحليـلهـايآماري استفاده كرده و داده هاي ناموجود را حدس بزنيم (گونلان، 1986؛ كميلسـكي و همكـاران ، 1993). هر دو رويكرد براي كامل شدن سيستمهاي اطلاعاتي كاربرد دارند، اما به كـارگيري روشمناسب براي كامل كردن سيستمهاي اطلاعاتي ناقص، خود يك موضوع تحقيـق پيچيـده اسـت(منگ و ژي، 2009).
در سالهاي اخير تئوري مجموعة راف2 به يكي از راهحلهاي قدرتمند در حل مسائل هـوشمصنوعي همچون دادهكاوي تبديل شده است (پاولاك و اسكورن، 2007). يكـي از راهكارهـاياساسي براي استخراج دانش و كشف الگوهاي پنهان از سيستمهاي اطلاعاتي3 بزرگ، استفاده از دادهكاوي4 است (هان و كمبر، 2006). كاهش ويژگي5 كه همان انتخاب ويژگي6 ناميده ميشود، يكي از موضوعات مهم در تئوري مجموعة راف است، اما نسخة كلاسيك تئوري مجموعـة رافبراي بحث كاهش ويژگي در سيستمهاي اطلاعاتي ناقص چندان مناسب نيست (كيـان، ليانـگ،پدريك و دانگ، 2011). براي كاهش ويژگي، دو استراتژي كلي به نام بستهبنـدي 7 (كوهـاوي وجان، 1997) و فيلتر8 مطرح شده است. در گذشته، يك الگوريتم يادگيري براي ارزيابي مجموعـة
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Incomplete Information System
Rough Set Theory
Information System
45. Data Mining . Attribute Reduction
Feature Selection
Wrapper
Filter
ويژگيهاي انتخاب شده به كار ميرفت، اما به مرور زمان مجموعة ويژگيها به وسيلة معيارهاي بـا معني اي همچون افزايش اطلاعات1 (لي و لي، 2006؛ كـونلان، 1986)، سـازگاري (داش و ليـو،2003؛ كوين، ليانگ و دانگ، 2008)، مسافت (كـايرا و رنـدل، 1992)، وابسـتگي (مورزجسـكي،
1992) و غيره بررسي ميشوند. اين معيارها به دو دسـتة كلـي مبتنـي بـر مسـافت و مبتنـي بـرسازگاري، طبقه بندي شدهاند (هو، ژيو و يو، 2007).
اغلب روشهاي بهينهسازي مبتني بر هوش مصنوعي همانند الگوريتم ژنتيـك، شـبيهسـازيفرايندهاي طبيعي هستند. يكي از دلايل اين امر ملمـوس بـودن، سـادگي فرمولـهكـردن و دركتكامل اين الگوريتمهاست. الگوريتم رقابت استعماري2، با الهامگيري از نوعي فراينـد اجتمـاعي ـ سياسي نسبت به ساير روشهاي مطرح شده در اين زمينه توانايي زيادي دارد و از سرعت مناسبي نيز برخوردار است (آتش پز و لوكاس، 2007؛ صفوي، پورجعفريان و صفوي، 1393: 104).
راهحل نوين ارائهشده در اين مقاله، تركيبي از الگوريتم رقابت استعماري و منطق فازي اسـتكه در حل مسئلة كاهش ويژگي سيستمهاي اطلاعاتي ناقص مبتنـي بـر تئـوري مجموعـة رافكاربرد دارد. استفاده از منطق فازي در كنترل پارامترهاي الگوريتم رقابت استعماري بسـيار مفيـداست و در مقايسه با نسخة بدون فازي الگوريتم، جوابهاي بهينهاي مـي دهـد . منطـق فـازي ازاجزاي محاسبات نرم3 است كه روش محاسباتي جديدي محسوب ميشود و تواناييهاي شاخص ذهن انسان را براي استدلال و يادگيري در محيط نامعين و نادقيق گرد هم مـي آورد (لطفـي زاده، 1992). الگوريتم رقابت استعماري فازي هوشمندانه عمل مي كند و روي سيستمهـاي اطلاعـاتيناقص نتايج مناسبي ارائه مي دهد.
بخشهاي مختلـف ايـن مقالـه بـدين شـرح اسـت؛ ابتـدا پيشـينة پـژوهش بررسـي شـده و پژوهش هاي موفق در زمينة كاهش ويژگي مبتني بر تئوري مجموعة راف مرور ميشوند. بخـشروششناسي پژوهش، به توضيح روند اجراي پروژه اختصاص دارد. در قسمت يافتههاي پژوهش، نتايج به دست آمده از اجراي روش، ب هصورت مقايسهاي مطرح مي شود و در نهايت نتيجهگيـري وپيشنهادها ارائه خواهد شد.
پيشينة پژوهش
در دو دهة گذشته، تعداد زيادي از روشهاي كاهش ويژگي مبتني بر تئوري مجموعـة راف ارائـهشده است (لي، ژانگ و ليونگ، 2004؛ مي، وا و ژانـگ، 2003؛ وا، ژانـگ، و لـي، 2005؛ شـاو و
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Information gain
Imperialist Competitive Algorithm (ICA)
Soft Computing
ژانگ، 2005؛ كيان، ليانگ و دانگ، 2008). يكي از مشكلات اساسي اين روشها، زمان زيـادياست كه صرف پردازش مجموعة دادههاي بـزرگ مـيشـود . در ادامـه تعـدادي از تحقيـقهـايانجام شده در اين حوزة پژوهشي بررسي مي شود.
پيشينة نظري
در بررسي پيشينة نظري كاهش ويژگي بر مبناي تئوري مجموعة راف، دو رويكـرد اساسـي را درمقابل داريم. ابتدا رويكردهايي كه كلاسيك هستند و از همان نسخة اصلي تئوري مجموعة راف استفاده ميكنند. رويكرد دوم، توسعه يافتة رويكرد قبلي است كه الگوريتم هاي اكتشـافي كـاهشويژگي را ارائه ميكند. نكتة مهم در رويكردهاي مختلف كاهش ويژگي بر مبناي تئوري مجموعة راف، نوع سيستمهاي اطلاعاتي است. در اغلب پژوهش هاي اجراشده بر سيستمهـاي اطلاعـاتيكامل تمركز شده است؛ اما در دنياي واقعي، مجموعة دادههـاي جمـعآوري شـده هميشـه كامـلنيستند. پس چالش اساسي كاهش ويژگي مبتني بر تئوري مجموعة راف، كار روي سيسـتم هـاياطلاعاتي ناقص است.
پيشينة تجربي
در بررسي پيشينة تجربي، تعدادي از پروژههاي موفق در زمينة كاهش ويژگي مبتنـي بـر تئـوريمجموعة راف مرور ميشوند. اين پژوهشها در همان قالب توضيح داده شده در بخش قبـل ار ائـهشدهاند.
يكي از تحقيقات ابتدايي انجام شده، روي چند روش مبتني بر تئـوري مجموعـة راف تمركـزدارد كه براي استخراج قوانين از جدول هاي تصميم به كار ميروند. معمولاً اين روشها با استفاده از ماتريسهاي عيني عمل مـي كننـد (اسـكورن، 1995). در ايـن پـژوهش، كـارايي روشهـايمطرح شده و دقت استخراج قوانين پايين بود.
براي افزايش كارايي عملكـرد كـاهش ويژگـي در تئـوري مجموعـة راف، چنـدين الگـوريتماكتشافي توسعه داده شده است (ها و همكاران، 2007؛ ها، يو و ژيو، 2006؛ ها و سركون، 1995؛ ليانگ، چين، دانگ و ريچد، 2002؛ كيان و ليانگ، 2008؛ اسـلزاك، 2002؛ وانـگ، ژو و يانـگ،2002؛ وانگ، ژائو و آن، 2005؛ وا، لي، هانگ و ليو، 2004). هر يك از اين الگوريتمها در حفـظويژگيهاي خاص سيستم اطلاعاتي داده شده كمك ميكنند.
براي كاهش ويژگي در سيستمهاي اطلاعاتي ناقص، مشابه تحقيقات ابتدايي، يك مـاتريسعيني به صورت كلي مطرح شده كه بحث كاهش ويژگي را روي جدول هاي تصميم ناقص انجـامميدهد (كريزكيوسز، 1998). براي افزايش كارايي در بحث كاهش ويژگي روي دادههاي ناقص، چندين الگوريتم اكتشافي ارائه شده كه در ادامه تعدادي از آنها بررسي ميشود.
ايدة كاهش نواحي مثبت بدين صورت مطرح شد كه يك الگوريتم كاهش ويژگي اكتشـافي، روي جدول هاي تصميم ناقص اعمال ميشود. روش آن به اين شكل است كه ناحية مثبت هدف تصميم را بدون تغيير نگه مـي دارد (يانـگ و شـو، 2006). همچنـين تعريـف جديـد از درگاشـتاطلاعات1، براي اندازهگيري اجمالي از سيستمهاي اطلاعاتي ناقص عنوان شد (ليانگ، شي، لي و وايرمن، 2006). علاوه بر اين، اعمال متنـاظر درگاشـت شـرطي2 در كـاهش ويژگـيهـاي دارايافزونه، شامل اين تعريف بود (ليانـگ و ژو، 2002). دو دانشـمند ديگـر تركيـب درگاشـت بـراياندازه گيري اجمالي از يك سيستم اطلاعاتي ناقص و همچنين استفاده از درگاشت شـرطي بـرايدستيابي به زيرمجموعهاي از ويژگيها را پيشنهاد دادند (كيـان، ليانـگ و وانـگ، 2009). بعـد ازدرگاشت اطلاعات كه براي كاهش ويژگي در تئوري مجموعة راف به صـورت كلاسـيك مطـرحشد، نمونة توسعه يافته اي از آن براي تكميل روش قبلي ارائه گرديد (اسلزاك، 2002).
در يكي از پژوهشهاي انجام شده به بحث بهينهسازي و اثربخشي3 الگوريتمهـاي اكتشـافيكاهش ويژگي در سيستمهاي اطلاعاتي ناقص پرداخته شده است. چارچوب جديدي كـه در ايـنپژوهش براي تئوري مجموعة راف ارائه شد، »تقريب مثبت«4 در سيستمهاي اطلاعـاتي نـاقصناميده ميشود. يكي از نتايج اين چارچوب، اين است كه ميتواند ساختار ناقص تئوري مجموعـةراف را شناسايي كند (كيان، ليانگ، پدريك و دانگ، 2011).
اما يكي از چالشهاي اساسي پژوهشهاي انجام شده در اين حوزه، صرف زمـان زيـاد بـرايپردازش دادههاي ناقص با حجم بالاست. نكتة ديگري كه در تحقيقات پيشين همواره بـه عنـوانيك چالش مطرح است، كارايي كم روشهاي ارائه شده است.
روششناسي پژوهش
در اين بخش، پس از تعريف مفاهيم اساسي همچـون سيسـتمهـاي اطلاعـاتي نـاقص، تئـوريمجموعة راف، الگوريتم رقابت استعماري و قواعد فـازي ، مجموعـة دادة ايـن پـژوهش، تشـريحمي شود.
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Information Entropy
Conditional Entropy
Efficiency
Positive Approximation
سيستمهاي اطلاعاتي ناقص
يك سيستم اطلاعاتي معمولاً به فرم زير ارائه ميشود.
رابطة 1) ⋴(,{} ,,) =
كه در آن، U تعداد متناهي از اشياي داراي مقدار و A تعداد محدودي از ويژگيهاي داراي مقدار است. مجموعة مقادير ويژگيها و ، يك تابع اطلاعاتي از سيستم اطلاعات است كـه را به U نگاشت ميكند. اگر در سيستم اطلاعاتي يك شيء x و يك ويژگي به نام a وجـود داشـتهباشد كه در تابع (x) مقداري نداشته باشد، به آن سيستم اطلاعـاتي نـاقص گفتـه مـي شـود.
معمولاً مقادير ناموجود را با * و به فرم ذيل نمايش مي دهند:
= (U, A,

(2 رابطة
مثال: جدول شمارة 1 نمونهاي از سيستم اطلاعاتي ناقص را نشـان مـيدهـد . ايـن سيسـتمشامل اطلاعات مربوط به چند فرد با ويژگيهاي قد، وزن و سن است. هر يك از مقادير مربـوطبه اين ويژگيها با مقادير كيفي مشخص شده اند.
جدول 1. نمونهاي از سيستم اطلاعاتي ناقص
سن وزن قد افراد
خيلي بالا زياد بلند شمارة 1
بالا زياد كوتاه شمارة 2
پايين كم * شمارة 3
خيلي بالا زياد بلند شمارة 4
خيلي بالا * خيلي بلند شمارة 5
* متوسط بلند شمارة 6

تئوري مجموعة راف
تئوري مجموعة راف در سال 1980 ارائه شد. اين ابزار رياضي براي بيان و بررسي مسائلي اسـتكه در آنها عدم قطعيت و ابهام وجود دارد و معمـولاً بـراي پيـدا كـردن نـاهمگوني در مجموعـةداده ها به كار ميرود. همان طور كه در جدول 1 مشخص است، فرد 1 و 4 مقادير ويژگي مشابهي دارند و با اين مقادير از هم تفكيك نمي شوند (پاولاك، 1998؛ كيانا، ژانگـب، سـانگب و ليانـگ،2014).
رابطة زير را رابطة تفكيكناپذير ميگويند:
رابطة 3) {( )= ( ),∈∀|×∈ (, )}=
اگر x و y دو شيء باشند و براي هر ويژگي در مجموعـ ة B، مقـدار آن ويژگـي در دو شـيء يكسان باشـد ، Iرا رابطـ ة تفكيـك ناپـذير B مـي نامنـد . همچنـين برچسـب كـلاس، ويژگـيتصميم گيري تعريف مي شود و هر به سيستم اطلاعاتي كـه حـاوي ايـن ويژگـي باشـد، سيسـتمتصميم گيري ميگويند.
جدول 2. نمونهاي از سيستم اطلاعاتي كامل
درآمد سن وزن قد افراد
كم خيلي بالا زياد بلند شمارة 1
متوسط بالا متوسط كوتاه شمارة 2
زياد خيلي بالا زياد بلند شمارة 3
زياد خيلي بالا خيلي كم خيلي بلند شمارة 4
كم پايين زياد بلند شمارة 5
خيلي كم بالا كم متوسط شمارة 6

در جدول 2 ستون درآمد، ويژگي تصميمگيري است. در اين جدول افراد 1 و 3 ويژگـي هـاييكساني دارند، اما از نظر درآمد وضعيت مشابهي ندارند. به بيان ديگر، ويژگي تصميمگيـري آنهـا متفاوت است. مجموعة تواني ويژگي ها عبارت اند از{(قد)، (وزن)، (سن)، (قد و وزن)، (قد و سن)، (وزن و سـن)، (قـد، وزن، سـن)}. حـال اگـر مجموعـة (قـد و وزن) را در نظـر بگيـريم، رابطـة تفكيك ناپذيري آن به صورت رابطة 4 است.
رابطة 4) {{6} ,{4} ,{2} ,{5 ,3 ,1}}={وزنوقد}|
با توجه به رابطة 4، مجموعة {1، 3، 5} در رابطة 4، توسط قد و وزن تفكيك ناپذيرنـد و بـهيك كلاس هم ارزي تعلق دارند. در يك رابطة همارزي به نام x، كلاس همارزي مربوط به عضو a شامل اعضايي است كه باa ارتباط دارند. نمايش كلاس هم ارزي به صورت [ ] است.
فرض كنيد يك سيستم اطلاعاتي S= (U, A) داشته باشيم كه در آن U مجموعة اشيا و A ويژگيهاست. همچنين X⊆U و B⊆A را داريم و دو مجموعه به شرح زير تعريف ميشوند:
رابطة 5) { []| }=

= {x|[ ] X} (6 رابطة
با توجه به تعريف B، مجموعههاي X

و X احتمالاً داراي اشيايي متعلق بـهX هسـتند .
محدودة مرزي روي X به صورت زير تعريف ميشود و حاوي اشيايي است كه قطعاً در X نيستند.
(X) =

X- X (7 رابطة
يك مجموعه در صورتي راف است كه با توجه به B، مجموعة مرزي آن تهي نباشـد . بـرايمثال، X برابر است با افرادي كه درآمد زيادي دارنـد ، يعنـي {4 , 3} = X و مجموعـةB برابـر{قد، وزن و سن} فرض شود، آنگاه داريم:

X ={4}, X ={1, 3, 4}, BN (X) = {1, 3}, U-BN (X) = {2, 5, }6
همان طور كه مشخص است، مجموعة مـرزي تهـي نيسـت. افـراد 1 و 3 داراي درآمـد بـالاهستند، افراد 4، 3 و 1 احتمالاً درآمد بالايي دارند. افراد 3 و 1 را نمي توان بـاB تعيـين تكليـف كرد. همچنين افراد 2، 5 و 6 قطعاٌ درآمد بالايي ندارند. ميزان دقت مجموعة راف را مـي تـوان از رابطة 8 تعيين كرد.
X
534162-95734

رابطة 8) = (X)
X
درجة تعلق x به X را مي توان با تابع تعلق راف بيان كرد. اين تابع تعلق، درجة هـم پوشـانيمجموعه X و كلاس همارزي [] را تعيين ميكند. در مثال بالا كلاسهاي همارزي به شـرحزير هستند:
{6}= [6] ,{5}= [5] ,{4}= [4] ,{2}= [2] ,{3 ,1}= [3]= [1]رابطة زير تابع تعلق را مشخص ميكند:
|[ ]∩|
: U → [0, 1]and(x) =

|[ ] | (9 رابطة
در بررسي دادهها، يافتن رابطة بين ويژگيهاي شرطي و تصميم اهميـت دارد . بـا اسـتفاده ازهمين وابستگي بين ويژگيها ميتوان آنهايي كه اهميت ندارند را حذف كرد. اگـرTd مجموعـة ويژگيهاي تصميمگيري و Tc مجموعة ويژگيهاي شرطي باشد، وابسـتگي بـين آنهـا بـه ايـنشكل بيان ميشود Tc≤Td؛ به اين معنا كه تمام مقادير تصميمگيري از مقادير شرطي ب هدسـتميآيند و البته حالت جزئي هم ميتواند داشته باشد.
تعريف رسمي براي اين خاصيت بدين صورت است كـه اگـرC و D زيـر مجموعـههـايA باشند، به طوري كه اشتراك C و D تهي و اجتماع آنها A باشد، ميگوييم D وابسته به C اسـت .
و به شكل C⇒D نمايش داده ميشود، اگر رابطة 10 برقرار باشد.
X
رابطة 10) ||

اگر k برابر 1 باشد، يعني D كاملاً به C وابسته است. در مثال قبلـي ويژگـي تصـميمگيـري درآمد با درجة

به مجموعة ويژگيهاي {قد، وزن و سن} وابسته است.
با توجه به تشريح تئوري مجموعة راف، كاربردهاي مختلف آن قابـل درك خواهـد بـود كـهبحث كاهش ويژگي يكي از كاربردهاي مهم آن است.
الگوريتم رقابت استعماري
الگوريتم رقابت استعماري در سال 2007، به عنوان روش جست وجوي فرامكاشفهاي مطـرح شـدكه از پديدة اجتماعي ـ انساني الهام ميگيرد (آتشپز و لوكاس، 2007). اين الگـوريتم بـا تعـداديجمعيت اوليه آغاز ميشود كه هر عنصر جمعيـت يـك كشـور نـام دارد و كشـورها بـه دو گـروهاستعمارگر و مستعمره دسته بندي مـي شـوند . هـر اسـتعمارگر بسـته بـه قـدرت خـود تعـدادي ازكشورهاي مستعمره را به سلطه درمـي آورد و آنهـا را كنتـرل مـيكنـد . سياسـت جـذب، رقابـتاستعماري و انقلاب، هستة اصلي اين الگوريتم را تشكيل ميدهند (صنيعي آباده و جبـل، 1392).
روية اجراي اين الگوريتم به صورت زير است (حاجي حسني، ارمغاني و مارتو، 2015):
شكلدهي امپراتوريهاي اوليه: تعـدادي از بهتـرين عناصـر جمعيـت بـه عنـوا ن اسـتعمارگرانتخاب مي شوند و باقي ماندة جمعيت نيز مستعمره در نظر گرفتـه مـي شـوند . اسـتعمارگرانبسته به قدرتشان، اين مستعمرات را با روند خاصي به سمت خود مي كشند. در بهينه سـازي،هدف، يافتن يك جواب بهينه بر حسب متغيرهاي مسـئله اسـت . مـا آرايـه اي از متغيرهـا ي مسئله را كه بايد بهينه شوند، ايجـاد مـي كنـيم و آن را يـك كشـور مـي نـاميم . در مسـئل ة بهينه سازي Nvarبعدي، يك كشور، آرايهاي به طـول 1 * Nvarاسـت . ايـن آرايـه بـه ايـنصورت تعريف مـي شـود : [p1, p2, …, pNvar] = كشـور . مقـادير متغيرهـا در يـك كشـور،به صورت اعداد اعشـاري نمـايش داده مـي شـوند. از ديـدگاه تـاريخي و فرهنگـي، اجـزايتشكيل دهندة يك كشور را ميتوان ويژگي هـاي اجتمـاعي ـ سياسـي آن كشـور، همچـونفرهنگ، زبان، ساختار اقتصادي و ساير ويژگي ها در نظر گرفت.
ناوریدورةبهار
سياست جذب (همگون سازي): اين سياست با هـدف تحليـل فرهنـگ و سـاختار اجتمـاعيمستعمرات در فرهنگ حكومت مركزي اجرا مي شد. كشورهاي استعمارگر براي افزايش نفوذ خود، شروع به ايجاد زيرساخت هاي حمل و نقل، تأسيس دانشگاه و غيره مي كردند. در واقع، حكومت مركزي با اعمال سياست جذب تلاش مي كرد كشور مستعمره را در راسـتاي ابعـادمختلف اجتماعي ـ سياسي به خود نزديك كند.
انقلاب: روند انقلاب تغييرات ناگهاني را در ويژگيهاي اجتماعي ـ سياسي يك كشور ايجـادميكند. در الگوريتم رقابت استعماري، انقلاب با جابه جايي تصادفي يك كشور مستعمره بـهموقعيت تصادفي جديد، مدلسازي ميشود.
جابه جايي موقعيت مستعمره و اسـتعمارگر: در حـين حركـت مسـتعمرات بـه سـمت كشـوراستعمارگر، ممكن است بعضي از اين مستعمرات به موقعيتي بهتـر از اسـتعمارگر برسـند . در اين حالت، كشور استعمارگر و كشور مستعمره، جاي خود را با يكديگر عوض ميكنند.
رقابت استعماري: قدرت امپراتوري، به صورت قدرت كشور استعمارگر به اضـاف ة درصـدي ازقدرت كل مستعمرات آن تعريف ميشود. هر امپراتوري كه نتواند بـر قـدرت خـود بيفزايـد وقدرت رقابت خود را از دست بدهد، در جريان رقابت هاي استعماري، به تدريج سقوط مي كنـد و مستعمراتش به دست امپراتوري هاي قوي تر ميافتد.
در شكل 1 نمودار الگوريتم رقابت استعماري مشاهده ميشود.

شكل 1. فلوچارت الگوريتم رقابت استعماري
در ادامه به معرفي پارامترهاي الگوريتم رقابت استعماري پرداخته مي شود.
جدول 3. معرفي پارامترهاي الگوريتم رقابت استعماري
نام متغيرها توضيح
Nvar تعداد متغيرها
Npop تعداد اعضاي جمعيت
Nimp تعداد استعمارگران
Maxdecades تعداد تكرار
Beta ضريب جابه جايي
Prevolve ضريب انقلاب (شبيه جهش در ژنتيك)
Zeta ضريب ميانگين قدرت كلونيهاي يك استعمارگر

در هر بار تكرار الگوريتم، مقادير اولية مختلفي را براي پارامترهاي آن انتخاب كـرديم كـه درنهايت، بهترين مقادير آنها به صورت تجربي به اين ترتيب مشخص شد: تعداد تكرار برابر بـا 100 تا 200، تعداد اعضاي جمعيت 50 تا 100، تعداد استعمارگران بسته به تعداد اعضاي جمعيت بـين5 تا 10، با توجه به پيشنهاد ارائه دهندگان الگوريتم ضريب جابه جايي مقدار 2/0، ضريب انقـلاب
1/0 و ضريب ميانگين قدرت كلونيها بين 05/0 تا 005/0.
قوانين فازي تعريفشده
استفاده از قواعد فازي در اجراي الگوريتم باعث شد بتوانيم پارامترهاي كليـدي الگـوريتم رقابـتاستعماري را بهتر كنترل كنيم. مجموعة قواعد فازي براي اين برنامه به صورت زير تعريف شد:

.1 If (UN is not L) and (I is not L) then (Prevolve is M) (zeta is L) (Beta is H)
.2 If (nimp is M) and (I is M) then (Prevolve is L) (zeta is M) (Beta is M)
.3 If (I is H) then (Prevolve is M) (Beta is L)
.4 If (I is L) then (Prevolve is L) (Beta is H)
.5 If (I is M) then (Prevolve is M) (Beta is M)
.6 If (nimp is not H) and (I is H) then (Prevolve is L) (zeta is M) (Beta is L) .وروديها و خروجيهاي مجموعة قواعد در جدول 4 مشخص شدهاند
ناوریدورةبهارجدول 4. توضيح وروديها و خروجيهاي قوانين فازي تعري فشده
توضيح خروجيها خروجيها توضيح وروديها وروديها
ضريب انقلاب (جهش) Prevolve تعداد تكرارها I
ضريب ميانگين قدرت كلونيهاي يك استعمارگر zeta تعداد اجراهايي كه جواب تغيير نميكند UN
ضريب جابه جايي Beta تعداد استعمارگران Nimp

همچنين در مشخص كردن مقدار وروديها و خروجيها، L بـه معنـاي كـم 1، M بـه معنـاي متوسط2 و H به معناي زياد3 است. در شكل 2، نمودارهاي مربـوط بـه قـوانين نشـان داده شـده است.

شكل 2. نمودار وروديها و خروجيهاي قوانين فازي
با توجه به بررسي شكل 2، هنگامي كه وروديهاي قواعد فازي را متوسط (M) فرض كنيم،
خروجيهاي آن به صورتPrevolve برابر 242/0، zeta برابـر 04776/0 و Beta برابـر 613/0 است.

ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Low
Medium
High
ويژگياطلاعاتيبرتئوري…
مجموعه دادة در دست بررسي
همان طور كه در قسمت مقدمة مقاله اشاره كرديم، كـار روي داده هـاي نـاقص انجـام مـي شـود .
داده هاي ناقص به جدول هايي از دادهها گفته مي شود كه برخي درايـه هـاي صـفات آن مقـداريندارند. در روند انجام اين پروژه، هيچ تغييري روي دادههاي ناقص اعمال نكرديم و آن را سيستم اطلاعاتي كامل فرض كرديم. مجموعة دادة در دست بررسـي در جـدول 5 معرفـي شـده اسـت .
(كيان، ليانگ، پدريك و دانگ، 2011؛ يو. سي. آي، 2016).
جدول 5. معرفي مجموع دادة مورد بررسي
شمارة ستون تصميم تعداد ستونها تعداد سطرها نام مجموعه دادهها رديف
57 57 32 Lungcancer 1
35 35 366 Dermatology 2
11 11 699 Wisconsin_Breast_Cancer 3
20 20 155 Hepatitis 4
3 30 194 Flag 5

در مجموعة دادة معرفي شده، دادة شمارة 1 مربوط به سرطان ريه، دادة شـمارة 2 مربـوط بـهمشخصات پوست، دادة شمارة 3 مربوط به سرطان سينه، دادة شمارة 4 مربوط به هپاتيـت و دادةشمارة 5 مربوط به مشخصات پرچمهاست.
يافتههاي پژوهش
شكل 3 چارچوب سادهاي از اجراي اين پژوهش را نشان ميدهد كه نقش قواعد فازي در تعيـينپارامترهاي الگوريتم و نحوة ارتباط آن با تئوري مجموعة راف را تعيين ميكند. همچنين در ايـنچارچوب، ورودي و خروجي مشخص شده است.

شكل 3. چارچوب پژوهش
ناوریدورةبهار
دو نسخة الگوريتم رقابت استعماري و رقابت استعماري فازي طراحيشـده، بـه دفعـات زيـادروي مجموعة دادهها اجرا شد. بهترين جوابهاي به دست آمده از اجراي دو نسخة الگوريتم رقابت استعماري با بهترين جوابهاي به دست آمده تاكنون در جدول 6 آمده است (كيان، ليانگ، پدريك و دانگ، 2011؛ كي، ژو و گيانگ، 2008). همان طور كه در جـدول مشـاهده مـيشـود، بهتـرينجوابهاي به دست آمده از هر دو نسخة الگوريتم براي مجمو عـة دادة 2 تـا 5، بهتـر يـا برابـر بـابهترين جوابهاي به دست آمده تاكنون است. از سويي، نسخة فازي الگوريتم نتايج بهينـه تـري راارائه كرده اسـت . نتيجـة اجـراي نسـخة فـازي الگـوريتم روي مجموعـه دادة 1 بهتـر از نسـخةكلاسيك آن است، اما بهينهتر از بهترين جواب به دست آمده تاكنون نبود.

جدول 6. بهترين جوابهاي به دست آمده از دو نسخة الگوريتم با بهترين جوابهاي به دست آمده تاكنون
بهترين جواب به دست آمده تاكنون الگوريتم رقابت استعماري الگوريتم رقابت استعماري فازي مجموعة دادهها
شمارة ستونها بهترين جواب شمارة ستونها بهترين جواب 4 ،35 ،28 ،11 ،7 ،3 39 6 ،36 ،28 ،11 ،3 41 5 1
10 ،16 ،9 ،8 ،5 ،4 ،3 ،2 28 ،22 ،18 10 ،16 ،9 ،4 ،3 ،2 28 ،19 ،17 8 2
4 6 ،3 1، 3 6 ،1 2 3
5 16 ،8 2، 3 17 ،6 ،2 3 4
2 11 ،9 4، 3 4 1 5

با مقايسة دو نسخة الگوريتم رقابت استعماري روي مجموعة دادة مشخص شده، درمـي يـابيمكه نسخة فازي، راهحلهاي بهينهتري را ارائه كرده است. بهترين جـواب هـاي بـه دسـت آمـده ازالگوريتم رقابت استعماري فازي براي پنج دادة تعيين شده، بهترتيـب {5، 8، 2، 3، 1} و بـدترينپاسخ هاي به دست آمده شامل {10، 11، 4، 5، 6} است، اما بهترين پاسخهـاي بـه دسـت آمـده ازاجراي الگوريتم رقابت استعماري براي مجموعة دادههـا بـهترتيـب {6، 10، 3، 3، 3} و بـدترينجوابها به صورت {9، 14، 4، 5، 5} هستند. در جدول 7 مقايسة ريز نتايج دو نسـخة الگـوريتم درج شده است.
ويژگياطلاعاتيبرتئوري…
جدول 7. مقايسة بهترين و بدترين جواب هاي به دست آمده از دو نسخة الگوريتم
Fuzzy-ICA
واريانس بهترين جواب ها ميانگين بهترين جواب ها بدترين
جواب بهترين جواب شمارة ستونها مجموعة
داده
2/6667 7 10 5 41 ،36 ،28 ،11 ،3 1
0/7667 9/9 11 8 28 ،19 ،17 ،16 ،9 ،4 ،3 ،2 2
0/4889 2/6 4 2 6 ،1 3
4/4889 3/6 5 3 17 ،8 ،2 4
2/8444 2/7 6 1 4 5
ICA
0/9889 6/9 9 6 39 ،35 ،28 ،11 ،7 ،3 1
1/9556 11/2 14 10 28 ،22 ،18 ،16 ،9 ،8 ،5 ،4 ،3 ،2 2
0/2333 3/2 4 3 6 ،3 ،1 3
0/5444 3/9 5 3 16 ،8 ،2 4
0/4444 4 5 3 11 ،9 ،4 5

در بررسي نتايج اين مقاله، دو نسخة الگوريتم رقابـت اسـتعماري طراحـي شـده بـا الگـوريتمژنتيك مقايسه شدند. با توجه به بهترين نتايج به دست آمده، مشاهده مي شـود كـه نسـخة فـازيالگوريتم رقابت استعماري از الگوريتم ژنتيك جوابهاي بهينهتري را ارائه ميكند. در شكل هـاي4 تا 8 نمودارهاي همگرايي اين نتايج مشاهده ميشود.

شكل 4. نمودار همگرايي براي دادة 1شكل 5. نمودار همگرايي براي دادة 2
ناوریدورةبهار



قیمت: تومان


پاسخ دهید