بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
روشي براي خوشه بندي تکاملي با استفاده از الگوريتم کرم شب تاب
چکيده
به موازات گسترش وب و افزايش حجم اطلاعات موجود در پايگاه هاي داده ، همواره روش هاي استخراج اطلاعات و روندهاي سودمند از اين پايگاه ها رو به افزايش بوده است . از اين رو در پژوهش حاضر سعي شده است تا الگوريتمي جديد براي بهبود الگوريتم بسيار کاربردي و ساده ي K-Means ارائه شود. يکي از بزرگ ترين ايراداتي که به الگوريتم K-Means وارد است ، انتخاب مراکز اوليه ي خوشه ها به صورت تصادفي است ، که همواره پاسخ نهايي اين الگوريتم را تحت تأثير قرار ميدهد، در نتيجه در الگوريتم حاضر سعي شده است تا با بهره گيري از الگوريتم کرم شب تاب اين نقص را بهبود داد. هر دو الگوريتم پيشنهادي و K-Means بر روي پايگاه داده ي عمومي و معتبر MovieLens پياده سازي شدند. نتايج حاصل از شاخص اعتبارسنجي ديويس بولدين نيز نشان دهنده ي بهبود چشمگير اين الگوريتم ميباشد.
کلمات کليدي
خوشه بندي، K-Means، الگوريتم کرم شب تاب
١- مقدمه
در دنياي امروز حجم وسيعي از داده ها بر روي هم انباشته شده اند و جست وجوي دانش از ميان اين حجم عظيم داده ها يکي از اساسي ترين ويژگي هاي علم داده کاوي ١ است .[١] داده کاوي تنها به جمع آوري و مديريت داده ها محدود نمي شود، بلکه تجزيه و تحليل و پيش بيني را نيز در بر مي گيرد. به طور کلي روش هاي مختلف داده کاوي در دو دسته روش هاي يادگيري با نظارت (نظارتي ) و روش هاي يادگيري بدون نظارت قرار مي گيرند. [٢]
در روش هاي يادگيري با نظارت هدف از داده کاوي مشخص است و ميدانيم که به دنبال چه نوع دانشي هستيم ،همانند انواع روش هاي طبقه بندي، اما در روش هاي يادگيري بدون نظارت ، هدف کاملا تعريف شده نيست ، که از اين ميان مي توان به روش هاي مختلف خوشه بندي اشاره کرد.[٢] خوشه بندي به دنبال سازمان دهي مجموعه اي از اقلام داده به خوشه ها، به طريقي است که اقلام موجود در يک خوشه بسيار"
مشابه " هم باشند و اين شباهت با اقلام موجود در خوشه هاي ديگر بسيار کاهش يابد.[٣]
خوشه بندي معمولا زماني مورد استفاده قرار مي گيرد که هيچ اطلاعاتي در رابطه با عضويت اقلام داده در کلاس هايي (طبقه هايي ) از پيش تعريف شده ، وجود نداشته باشد. به همين دليل ، خوشه بندي به طور سنتي، به عنوان جزئي از يادگيري بدون نظارت در نظر گرفته ميشود.[٤] در اين ميان الگوريتم خوشه بندي K-Means رويه ي خوشه بندي است که به طور گسترده مورد استفاده قرار مي گيرد. اين روش به دنبال يک جدا سازي نزديک به بهينه با تعداد ثابتي از خوشه ها مي باشد. اين روش از يک الگوريتم تپه - نوردي ٢ تکرار شونده استفاده مي کند.[٥]
الگوريتم K-Means به دليل عملکرد آسان و ساده بسيار محبوب است .[٦] با اين وجود اين الگوريتم داراي اشکالاتي نيز مي باشد. اول آن که اين الگوريتم با هم پوشاني خوشه ها به خوبي مقابله نمي کند و خوشه ها مي توانند از طريق دور افتاده ها به خارج از مراکز کشيده شوند. همچنين حاصل خوشه بندي ممکن است به فرزندان اوليه بستگي داشته باشد، با اين وجود سازوکاري به منظور بهينه سازي فرزندان اوليه وجود ندارد.[٧] علاوه بر موارد فوق ، اين الگوريتم ممکن است به يک بهينه ي محلي تحت شرايط خاصي همگرا شود، چرا که اين الگوريتم همچون يک استراتژي تپه -نوردي عمل مي کند.[٨] در نتيجه در سال هاي اخير به منظور بهبود اين الگوريتم در تعدادي از پژوهش ها از الگوريتم هاي تکاملي بهره گرفته شده است .
کيم و اهن در سال ٢٠٠٨، يک الگوريتم خوشه بندي جديد مبتني بر الگوريتم هاي ژنتيک ٣ (GAs)، به منظور بخش بندي کارآمد و موثر بازار خريد آنلاين ارائه کردند. اين پژوهشگران روش خوشه بندي -K Meansرا که پاسخ هاي اوليه آن توسط GA بهينه سازي شده است و آن را GA K-Means نام نهاده اند، به يک مورد بخش بندي بازار خريد آنلاين دنياي واقعي، اعمال کردند.[٨]
يوکريت ، نيپن و سنسنيي در سال ٢٠١٤ يک الگوريتم خوشه بندي جديد بر اساس الگوريتمهاي ممتيک ٤ و K-Means ارائه کردند.[٩] شمس فرد، مويدي کيا و فرصتي در سال ٢٠١٥ يک الگوريتم خوشه بندي جديد مبتني بر الگوريتم هاي جستجوي هارموني و الگوريتم K-Means تحت عنوان الگوريتم خوشه بندي جست وجوي هارموني (HSC) ارائه کردند.[١٠]
از آن جا که در پژوهش هاي اخير استفاده از الگوريتم هاي تکاملي به دليل عملکرد مناسب در اغلب حوزه ها، گسترش يافته است و از طرفي مطالعات اوليه ، برتري الگوريتم کرم شب تاب (FA)٥ را نسبت به الگوريتم هاي ژنتيک و ازدحام ذرات ٦ نشان ميدهد[١١]، در پژوهش حاضر، از اين الگوريتم به منظور بهبود الگوريتم K-Means در انتخاب مراکز اوليه ي خوشه ها، استفاده شده است . در الگوريتم پيشنهادي از ادغام ويژگيهاي ميزان سازي دقيق الگوريتم K-Means و ديد قدرتمند سراسري الگوريتم کرم شب تاب به منظور يافتن خوشه هايي نزديک به بهينه استفاده شده است . به اين صورت که ابتدا الگوريتم کرم شب تاب به تعداد مطلوب انجام شده و سپس خروجي اين الگوريتم به عنوان خوشه هاي اوليه ي الگوريتم K-Means مورد استفاده قرار ميگيرند.
در ادامه اين پژوهش ، نخست به تشريح مباني پژوهش پرداخته و الگوريتم هاي K-Means و کرم شب تاب معرفي ميشوند. پس از آن الگوريتم پيشنهادي FA-K-Means به تفصيل بيان ميشود. به دنبال آن ، شاخص ارزيابي ديويس بولدين (DB)٧ توضيح داده شده و در پايان ، به بررسي نتايج آزمايش ها، تحليل هاي مربوطه و جمع بندي دستاوردهاي پژوهش پرداخته ميشود.
٢- مباني پژوهش
در اين بخش ، الگوريتم هاي مورد استفاده در مدل پيشنهادي يعني الگوريتم هاي K-Means و کرم شب تاب معرفي ميشوند.
١-٢- الگوريتم خوشه بندي K-Means
فرايند خوشه بندي K-Means به شرح زير ميباشد.
• فرزندان اوليه با تعداد منتخب خوشه ها، K، انتخاب ميشوند و يک جداسازي اوليه با استفاده از فرزندان به عنوان مراکز ثقل خوشه هاي اوليه صورت ميگيرد.
• هر رکورد به مرکز ثقلي که نزديک ترين است ، تخصيص داده ميشود. در نتيجه يک خوشه شکل ميگيرد.
• به منظور نگه داشتن همان تعداد مشخص شده از خوشه ها، مرکز ثقل جديد هر يک از خوشه ها محاسبه مي شود.
• گام هاي دوم و سوم تا زماني که که خوشه ها ديگر تغيير نکنند يا شرايط توقف برآورده شود، تکرار ميشوند.[٨]
٢-٢- الگوريتم کرم شب تاب
8 الگوريتم کرم شب تاب به ابزار به طور فزاينده مهم هوش جمعي که قابل اعمال در اغلب حوزه هاي بهينه سازي و همچنين کاربردهاي مهخنتدلف س،يبه اسطت و،ر تمبودفيقل يت شآمديه زياس ات ز.طبرسييق اربيه اکزارگميسرائيل الاگزورحيتوم زه هکاري شب تاب و انواع مختلف آن حل شده اند. به منظور استفاده از اين الگوريتم براي حل مسائل گوناگون ، الگوريتم کرم شب تاب اصلي نياز به تغيير و يا اصلاح و ترکيب دارد.[١٢]
بر اساس پژوهش صورت گرفته توسط فيستر و همکاران اش در سال ٢٠١٣ بر روي اصول زندگي و تکامل اين هوش جمعي، نشان داده شد که الگوريتم کرم شب تاب قابل اعمال به تمامي مسائل دنياي واقعي ميباشد. اين الگوريتم اغلب تضمين ميکند که نتايج حاصل انتظارات را برآورده خواهند کرد.[١٣]
نسخه اصلي الگوريتم کرم شب تاب به اين ترتيب قابل توصيف است : شدت نور I حاصل از تابيدن کرم شب تاب همان طور که فاصله از منبع r افزايش مييابد، بر حسب ࢘.1 ן I کاهش پيدا ميکند.
علاوه بر اين ، قابليت جذب هوا٩ سبب ميشود که همان طور که فاصله از منبع افزايش پيدا ميکند، نور ضعيف تر و ضعيف تر شود. اين تابش نور، عامل الهام بخش براي توسعه ي الگوريتم کرم شب تاب (FA)، توسط يانگ در سال ٢٠٠٨ شده است .[١٤]
در اين جا، شدت نور متناسب است با تابع هدف مسأله اي که ميبايست بهينه سازي شود. (به عبارت ديگر، (F)s ן (I)s است ، که در آن (S)x =s نشان دهنده ي يک پاسخ نامزد است .)[١٣]
به منظور مدل سازي الگوريتم FA، برخي از ويژگيهاي تابش کرم هاي شب تاب ايده آل در نظر گرفته شدند، که عبارتند از:
• تمامي کرم هاي شب تاب تک جنسيتي ميباشند.
• جذابيت آن ها با شدت نورشان متناسب است .
• درخشندگي يک کرم شب تاب متأثر و يا تعيين شده با مقدار تابع هدف ميباشد.
دقت شود که ، شدت نور I و جذابيت به طريقي مترادف هستند.
در حالي که شدت نور به عنوان معيار سنجشي مطلق از نور ساطع شده توسط کرم شب تاب ، در نظر گرفته ميشود، جذابيت به عنوان معيار سنجشي نسبي از نوري است ، که ميبايست در چشم بيننده ديده شود و توسط ديگر کرم هاي شب تاب مورد قضاوت قرار گيرد.[١٤]
شدت نور I با فاصله ي r تغيير ميکند، که از طريق معادله ي (١) بيان ميشود.
که در آن ٠ܫ به شدت نور در منبع اشاره دارد و ߛ ضريب ثابت جذب نور است . به طور مشابه ، جذابيت β که به فاصله r بستگي دارد، بر اساس معادله ي تعميم يافته ي (٢) محاسبه ميشود.
فاصله ي بين کرم هاي شب تاب i و j از طريق فاصله ي اقليدسي (٣) نمايش داده ميشود.
که در آن امين عنصر i امين موقعيت کرم شب تاب در فضاي جست وجو، ميباشد و D به ابعاد مسأله اشاره دارد. هر کرم شب تاب i به سمت کرم شب تاب j جذاب تر به صورت رابطه ي (٤)، حرکت ميکند.
معادله ي فوق از سه اصل تشکيل شده است ، که عبارتند از:
• اصل اول تعيين کننده ي موقعيت i امين کرم شب تاب است .
• اصل دوم به جذابيت اشاره دارد.
• اصل سوم مربوط به حرکت تصادفي i امين کرم شب تاب در فضاي جست وجو ميباشد. اين اصل دربرگيرنده ي پارامترهاي تصادفي سازي ן و اعداد تصادفي (٠,١) برگرفته از يک توزيع گاوسي ١٠ ميباشد.
الگوريتم FA، روي جمعيت کرم هاي شب تاب (P)t به صورت بردارهاي حقيقي نمايش داده ميشود، که در آن ميباشد و NP به تعداد کرم هاي شب تاب در جمعيت (P)t در نسل t اشاره دارد. توجه شود که t) هر کرم شب تاب Si مربوط به بعد D است . جمعيت کرم هاي شب تاب در ابتدا (تابع InitFFA) به صورت تصادفي بر اساس معادله ي (٥)، مقداردهي ميشود.
حلقه ي اصلي فرايند جست وجوي کرم شب تاب که توسط بيشينه ي تعداد نسل ها MAX_GEN کنترل ميشود، شامل توابع زير است .
• آلفاي جديد١١: براي پارامتر تصادفيسازي α مقادير جديد محاسبه ميشود. اين پارامتر بر اساس معادلات (٦) و (٧)، اصلاح ميشود.
که در آن اندازه گام تغيير را تعيين ميکند. توجه شود که اين پارامتر با افزايش شمارنده ي t کاهشي يکنواخت دارد.
• ارزيابي FA: ارزيابي پاسخ جديد (Si)t، بر اساس تابع برازش (F)St که در آن ((S)xi)t =Si)t( ميباشد، صورت ميگيرد.
• ترتيب 12FA: ترتيب پاسخ هاي (Si)t براي NP,...,1 = I با توجه به تابع برازش (F)St به صورت صعودي ميباشد، که در آن ((S)xi)t =Si)t( ميباشد.
• يافتن بهترين FA: بهترين پاسخ در جمعيت (P)t را تعيين ميکند. به طور معمول ، بهترين پاسخ (t)S0 = כS ميشود.
• حرکت FA: کرم هاي شب تاب در فضاي جست وجو با توجه به جذابيت پاسخ هاي همسايگان خود به سمت آن ها حرکت ميکنند.
٣-٢- شاخص ارزيابي ديويس بولدين (DB)
اين معيار تابعي از نسبت مجموع پراکندگي درون خوشه به پراکندگي بين خوشه ها مي باشد.[١٥] در ابتدا، پراکندگي درون iامين خوشه و فاصله ي iامين و jامين خوشه به ترتيب به بر اساس روابط (٨)
و (٩) تعريف ميشوند:
که در آن مرکز خوشه ي iام ، q مقداري صحيح ميباشند، به گونه اي که q و t هر يک ميتوانند به صورت مستقل انتخاب گردند. ࡺ تعداد عناصر موجود در خوشه ي iام ميباشد.
[١٥] سپسࡾ࢚ به صورت رابطه ي (١٠) تعريف ميشود:
در نهايت شاخص DB به صورت رابطه ي (١١) تعريف ميشود:
٣- الگوريتم پيشنهادي FA-K-Means
الگوريتم پيشنهادي FA-K-Means از ترکيب دو الگوريتم کرم شب تاب و K-Means به منظور رفع نواقص الگوريتم K-Means ارائه شده است . الگوريتم کرم شب تاب کاوشي سراسري را براي يافتن پاسخ ها اجرا ميکند، در حالي که رويه ي خوشه بندي K-Means، جست وجويي محلي را اجرا ميکند. در جست وجوي محلي پاسخ حاصل معمولا در مجاورت پاسخ حاصل در گام قبلي ميباشد. الگوريتم خوشه بندي K-Means از فرزنداني که به صورت تصادفي ايجاد شده اند به عنوان مراکز ثقل خوشه هاي اوليه استفاده ميکند و موقعيت مراکز را در هر تکرار اصلاح ميکند. فرايند اصلاح الگوريتم K-Means نشان دهنده ي اين است که اين الگوريتم تنها به کاوش در مجاورت بسيار محدود، اطراف مراکز ثقل اوليه اي که به صورت تصادفي توليده شده اند، ميپردازد و پاسخ هاي نهايي آن به اين مراکز ثقل اوليه بستگي دارد.
در نتيجه ، الگوريتم هاي کرم شب تاب و K-Means داراي نقاط قوت و ضعف مکملي ميباشند. الگوريتم کرم شب تاب در يافتن مناطق مستعد و اميدبخش از فضاي جست وجو بسيار عالي عمل ميکند، اما به خوبي K-Means در ميزان سازي دقيق ١٣ در اين مناطق نميباشد.
از طرف ديگر، الگوريتم K-Means در ميزان سازي دقيق خوب است ، اما فاقد يک ديد سراسري است . به نظر ميرسد که يک الگوريتم ترکيبي که الگوريتم هاي کرم شب تاب و K-Means را با هم ترکيب کند، به نتيجه ي بهتري نسبت به عملکرد هر کدام به تنهايي، ميرسد.
به همين دليل ، در اين پژوهش يک رويکرد خوشه بندي ترکيبي که از الگوريتم K-Means براي مرحله ي اصلاح در الگوريتم کرم شب تاب استفاده ميکند، ارائه شده است . به طور کلي، الگوريتم کرم شب تاب منطقه ي بهينه را مييابد و سپس K-Means وظيفه ي يافتن مراکز ثقل بهينه را به عهده ميگيرد. لازم است که تراز درست ميان (قابليت ) انتفاع ١٤ محلي و (قابليت ) پويش ١٥ سراسري برقرار گردد.
الگوريتم FA-K-Means در هشت گام به صورت زير اجرا ميشود:
گام ١. مقدار دهي اوليه پارامترهاي استفاده شده در الگوريتم شامل :
گام ٢. مقداردهي شمارنده ي تکرارها ٠=maxit
گام ٣. مقدار دهي اوليه جمعيت (در ابتدا الگوريتم FA حدود بالا و پايين پايگاه داده ي مورد نظر را ميگيرد و بر اين اساس جمعيت اوليه تصادفي را در اين حدود توليد و در قالب تابع برازش آن را بهبود مي دهد.)
گام ٤. اعمال الگوريتم کرم شب تاب که در گام پيشين به تفصيل بيان
شد و شامل دو گام زير است :
گام ١-٤. اجراي الگوريتم کرم شب تاب براي به روز رساني جمعيت
