منابع و ماخذ پایان نامه عدم تمرکز

دانلود پایان نامه ارشد

به خاطر اينکه مکانيزم کار آن دو الگوريتم متفاوت است از يکديگر مستقل هستند.
دوم، اگر دو افراز به دست آمده، از دو الگوريتم هم نام باشند درجه استقلال آن با توجه به پارامترهاي اساسي آن دو الگوريتم محاسبه مي‌شود.
در اين تحقيق فرآيند محاسبه استقلال دو الگوريتم توسط تابع “استقلال افرازهاي پايه162” محاسبه مي‌شود که ما آن را به اختصار BPI مي‌ناميم که در شکل 3-2 شبه کد آن نمايش داده شده است.
Function BPI (P1, P2) Return Result
If (Algorithm-Type (P1) == Algorithm-Type (P2) then
Result = 1 – Likeness (Basic-Parameter (P1), Basic-Parameter (P2))
Else
Result = 1
End if
End Function
شکل3-۲. محاسبه درجه استقلال دو خوشه‌بندي
در شکل 3-2 پارامترهاي ورودي P1 و P2 مشخصات کامل افرازهاي دو الگوريتم خوشه‌بندي‌اي هستند که ما قرار است ميزان استقلال آن‌ها را محاسبه کنيم و تابع Algorithm-Type نوع (اسم) الگوريتم‌هاي خوشه‌بندي را بر مي‌گرداند براي مثال و يا و غيره. ماتريس پارامترهاي اساسي يا Basic-Parameter شامل پارامترهاي مهم هر الگوريتم مي‌باشد که تحت تأثير آن الگوريتم‌هاي خوشه‌بندي شروع به حل مسئله مي‌کنند براي مثال نقاط اوليه مراکز، مقادير تصادفي و غيره. اين مقادير مي‌توانند بر اساس دو عامل تعريف شوند: اول طبيعت مسئله و فضاي حل آن و دوم نوع الگوريتم و مکانيزم حل آن. به عنوان يک مثال اضافه مي‌توان به مراکز تصادفي اوليه در الگوريتم اشاره کرد که هرچه اين مقادير در ابتدا داراي فاصله بيشتر باشند و جواب‌هاي نهايي حل شده توسط اين الگوريتم به هم شبيه‌تر باشند مي‌توان احتمال بالاتري براي درستي اين جواب‌ها در نظر گرفت. اين تحقيق براي مقايسه ماتريس‌هاي پارامترهاي اساسي با يکديگر از تابع مکاشفه‌اي Likeness استفاده مي‌کند که در ادامه آن را شرح مي‌دهيم.
در محاسبه تابع Likeness ما فرض مي‌کنيم که MaxDis بيش‌ترين مقدار در ماتريس‌هاي فاصله مي‌باشد (در اين تحقيق ما از معيار فاصله اقليدسي براي محاسبه فاصله استفاده کرديم ولي در روش پيشنهادي اين تحقيق مي‌توان از هر معيار فاصله ديگري نيز استفاده کرد) و ماتريس‌هاي و ماتريس‌هاي پارامترهاي اساسي دو الگوريتم خوشه‌بندي که قرار است درجه استقلال آن‌ها نسبت به هم محاسبه شود مي‌باشد (بخشي از اطلاعات ورودي‌هاي P1 و P2). در اين صورت ماتريس شباهت LMATt براي و فرض خواهد شد که در آن مقدار کمينه اين ماتريس مي‌باشد. با حذف سطر و ستوني که در آن مقدار وجود دارد ماتريس ايجادشده که از طريق مشابه مي‌توان را محاسبه کرد. اين کار آن قدر تکرار خواهد شد تا کل داده‌هاي ماتريس‌هاي حذف شوند. مقدار تابع Likeness بر اساس تعريف بالا از رابطه 3-۴ محاسبه مي‌شود:
(۳-۴)
لازم به ذکر است که در تعاريف بالا يک ماتريس است که تعداد پارامترهاي اساسي در الگوريتم مي‌باشد. استقلال هر افراز در جامعه خردمند با رابطه 3-5 محاسبه مي‌‌شود:
(۳-5)
که در آن تعداد اعضاي جامعه خردمند و تابع BPI با استفاده از شبه کد شکل3-2 مي‌باشد. بنا بر تعاريف بالا شرط ورود يک افراز به جامعه خردمند بزرگي درجه استقلال آن از مقدار آستانه مي‌باشد. رابطه 3-6 اين شرط را نشان مي‌دهد که ما آن را با عنوان شرط استقلال مي‌شناسيم. لازم به ذکر است که مقدار آستانه مي‌باشد.
(۳-6)
به عنوان آخرين نکته بايد اشاره کرد که استقلال يک معيار پراکندگي نيست به خاطر اينکه معيار‌هاي پراکندگي براي ارزيابي نتايج به دست آمده از خوشه‌بندي‌هاي اوليه مورد استفاده قرار مي‌گيرند ولي معيار استقلال فرآيند توليد نتايج را کنترل مي‌کند، اين عمل با مديريت پارامتر‌هاي اساسي در هر الگوريتم محقق مي‌شود. علاوه بر آن، استقلال مي‌تواند احتمال درستي الگو‌هاي مشابه را محاسبه کند ولي از ديدگاه معيارهاي پراکندگي دو الگوي مشابه داراي پراکندگي بسيار پايين مي‌باشند. از طرف ديگر با اين که معيار استقلال مي‌تواند احتمال درستي جواب را بررسي کند ولي نمي‌تواند تضمين کند تا جواب‌ نهايي به دست آمده از پراکندگي لازم برخوردار باشند و فقط مي‌تواند پراکندگي آن را تا حدي بهبود ببخشد از اين روي در اين تحقيق معيار استقلال به عنوان معياري مکمل براي معيار پراکندگي معرفي شده است نه به جاي آن.

3-3-3. عدم تمرکز در بخش‌هاي سازنده خوشه‌بندي ترکيبي
سورويکي موارد لازم براي ايجاد يک مجمع خردمند را اين‌گونه بيان مي‌کند. “شرايط لازم براي جامعه خردمند شامل پراکندگي، استقلال و نوعي خاصي از عدم تمرکز مي‌باشد.” با توجه به توضيحات سورويکي در مورد عدم تمرکز و مثل‌هايي که از سازمان CIA163 يا سيستم‌عامل لينوکس164 و مشکل طراحي شاتل165 در ناسا166 ذکر مي‌کند در مورد عدم تمرکز بايد گفت اين معيار، يک معيار کيفي است. روش کنترل اين متريک بايد در سطح بخش‌هاي سازنده خوشه‌بندي خرد جمعي باشد [55]. عدم تمرکز را بر اساس تعاريف بالا در خوشه‌بندي ترکيبي اين‌گونه تعريف مي‌کنيم:
ارتباط بين بخش‌هاي مختلف خوشه‌بندي خرد جمعي بايد به گونه‌اي باشد تا بر روي عملکرد خوشه‌بندي پايه تأثيري ايجاد نکند تا از اين طريق هر خوشه‌بندي پايه شانس اين را داشته باشد تا با شخصي سازي و بر اساس دانش محلي خود بهترين نتيجه ممکن را آشکار سازد.
در اينجا بهترين نتيجه ممکن يعني نتيجه‌اي که داراي ميزان استقلال و پراکندگي بهينه باشد و در مجمع پذيرفته شود. نتيجه مهمي که از تعاريف بالا مي‌توان دريافت اين است که عدم ‌تمرکز در خرد جمعي با روش ارتباط بخش‌هاي مختلف باهم در خوشه‌بندي خرد جمعي در رابطه مستقيم مي‌باشد از اين رو ما در طراحي سيستم خوشه‌بندي ترکيبي بايد شرايط زير را جهت حفظ عدم تمرکز رعايت کنيم:
1- تعداد الگوريتم‌هاي پايه شرکت‌کننده بايد بيشتر از يک الگوريتم باشد.
2- روش ورود يک الگوريتم پايه به مجمع بايد طوري باشد تا نتايج نهايي تحت تأثير خطاهاي آن قرار نگيرد يا به عبارتي نبايد روش تصميم‌گيري در مورد جواب نهايي متمرکز باشد.
3- مقدار آستانه ضريب عدم تمرکز ناميده مي‌شود که آن به عنوان ضريب براي تعداد خوشه‌هاي الگوريتم پايه استفاده مي‌شود. در اين روش تعداد خوشه‌ها در خوشه‌بندي پايه از تا متغير مي‌باشد.
مطابق تعاريف بالا، ضريب که عضو اعداد طبيعي است، وقتي داده داراي پيچيدگي‌هاي خاصي است و الگوريتم‌ خوشه‌بندي پايه نمي‌تواند الگوهاي آن را شناسايي کند، مي‌تواند دقت در جواب نهايي را بهبود بخشد. اين معيار مي‌تواند با افزايش تعداد خوشه در الگوريتم خوشه‌بندي پايه پيچيدگي آن را کاهش دهد [68] و الگوهاي پيچيده داده را به الگوهاي ساده کوچک‌تر تبديل کند که راحت‌تر توسط الگوريتم قابل‌تشخيص باشد (به ويژه براي الگوريتم‌هاي مبتني بر مرکز خوشه167). اين روش به جاي پيدا کردن يک راه حل مجتمع براي هر مسئله پيچيده سعي مي‌کند تا اين مسئله را به مسائل کوچک‌تر و با الگوهاي ساده‌تر تبديل کند و آن‌ها را حل نمايد. براي مثال حل داده‌هايي با شکل غير کروي توسط الگوريتم‌هاي مبتني بر مرکز خوشه همانند الگوريتم پايه يکي از کاربرد‌هاي اين متريک مي‌باشد. شکل 3-3 نشان‌دهنده تأثير عدم تمرکز بر روي‌داده Halfring مي‌باشد:

شکل3-3. تأثير عدم تمرکز بر روي پيچيدگي داده
بخش (a) شکل 3-3 نشان‌دهنده شکل داده‌ Halfring مي‌باشد که در آن رنگ آبي و قرمز دو کلاس اين داده است. بخش (b) شکل 3-3 نتيجه خوشه‌بندي اين داده را با استفاده از به ازاي (مقدار برابر با تعداد واقعي کلاس داده مي‌باشد) نشان مي‌دهد. همان طور که بخش (b) نشان‌ مي‌دهد الگوريتم قادر به حل اين داده نمي‌باشد. بر اساس روش پيشنهادي اين تحقيق اگر فرض شود آنگاه اين داده پيچيده به بخش‌هاي ساده کوچک‌تر تبديل مي‌شود که به راحتي با استفاده از الگوريتم قابل‌تشخيص خواهد بود. بخش (c) شکل 3-3 نشان‌دهنده خروجي به ازاي تعداد خوشه مي‌باشد.
در انتها بايد به اين نکته اشاره کرد که پياده‌سازي درست عدم تمرکز نياز به رعايت نکاتي در تمامي بخش‌هاي تشکيل‌دهنده خوشه‌بندي ترکيبي دارد که ما در ادامه در بخش ” بررسي تأثير مکانيزم بازخورد168 در کيفيت نتيجه نهايي” آن را کاملاً بررسي مي‌کنيم.
3-3-4. مکانيزم ترکيب مناسب
مطابق با تعاريف خرد جمعي روشي مناسب جهت ادغام نتايج به شکل زير تعريف مي‌کنيم:
بايد مکانيزمي وجود داشته باشد که بتوان توسط آن نتايج اوليه الگوريتم‌هاي پايه را با يکديگر ترکيب کرده و به يک نتيجه نهايي (نظر جمعي) رسيد.
در اين تحقيق ما از روش ماتريس همبستگي که پيش‌تر به آن اشاره شد براي تشکيل نتيجه نهايي با استفاده از نتايج اوليه بهره مي‌بريم. براي اين منظور از رابطه 2-42 استفاده خواهيم کرد. لازم به ذکر است که نتايج تجربي چندين مقاله کارايي اين روش را اثبات مي‌کند [1, 2, 8, 9, 19, 23].
3-3-5. بررسي تأثير مکانيزم بازخورد در کيفيت نتيجه نهايي
در روش‌هاي پيشين خوشه‌بندي ترکيبي ابتدا تمامي نتايج خوشه‌بندي اوليه توليدشده و پس از آن کليه اين نتايج بر اساس يک معيار ارزيابي خوشه همانند NMI ارزيابي مي‌شود و بر اساس اين نتايج ارزيابي افراز‌هاي (در برخي موارد خوشه‌ها) بهتر انتخاب مي‌شود. شکل 3-4 نشان‌دهنده اين فرآيند است. همان‌گونه که در اين شکل مشاهده مي‌شود اگر چه افراز‌هاي به دست آمده در مجموعه کل افرازها داراي بيش‌ترين مقدار متريک مورد ارزيابي مي‌باشد ولي پس از انتخاب مقدار اين ارزيابي‌ها تغيير کرده و در بيشتر موارد کاهش مي‌يابند. اين بدان معني است که در روش‌هاي پيشين اگر چه باکيفيت‌ترين (در بيشتر موارد پراکنده‌ترين) نتايج انتخاب مي‌شوند ولي اين مکانيزم نمي‌تواند دوام اين کيفيت را تضمين کند.

شکل3-3. تأثير انتخاب افرازها در خوشه‌بندي ترکيبي مبتني بر انتخاب بر مقدار NMI ارزيابي‌شده.
از طرف ديگر، روش پيشنهادي اين تحقيق با استفاده از مکانيزم بازخورد تعداد اعضاي جامعه خردمند را به تدريج افزايش مي‌دهد. در اين روش پس از توليد يک نتيجه (افراز) با استفاده از الگوريتم‌هاي خوشه‌بندي پايه آن را با استفاده از متريک استقلال و پراکندگي ارزيابي مي‌کنيم. اگر نتايج اين ارزيابي قابل‌قبول باشد کل افراز به دست آمده به مجموعه جواب‌هاي انتخاب‌شده يا همان جامعه خردمند اضافه مي‌شود در غير اين صورت به طور خودکار حذف مي‌شود. اين فرآيند براي تمامي نتايج تکرار خواهد ‌شد. قابل به ذکر است که اين روند موجب مي‌شود تا کيفيت نتايج اوليه به دست آمده براي توليد نتيجه نهايي حفظ شود زيرا نتايج ارزيابي‌ها پس از تغيير در تعداد اعضاي جامعه خردمند به‌روز شده و بعد از اتمام فرآيند توليد نتايج هيچ گزينش ديگري صورت نمي‌گيرد.
3-3-6. شبه کد خوشه‌بندي خردمند با استفاده از آستانه‌گيري
همان طور که پيش‌تر اشاره شد شکل 3-1 چهارچوب روش پيشنهادي اول اين تحقيق را ارائه مي‌دهد. اين فرآيند با توليد نتايج اوليه شروع‌شده و با ارزيابي پراکندگي و استقلال نتايج اقدام به توليد جامعه خردمند مي‌کند. در نهايت با استفاده از روش انباشت مدارک افرازهاي جمع‌آوري شده در جامعه خردمند با يکديگر ادغام‌شده و نتيجه نهايي را توليد مي‌کند. شکل 3-4 نشان‌دهنده شبه کد روش پيشنهادي اول است. در اين شکلتعداد خوشه‌ها در الگوريتم پايه مي‌باشد و تابع Generate-Basic-Algorithm نتايج اوليه (افرازهاي) را با استفاده از الگوريتم‌هاي خوشه‌بندي‌هاي پايه را توليد مي‌کند. دو تابع Diversity و Independence به ترتيب براي ارزيابي پراکندگي و استقلال به کار مي‌روند. تابع Make-Correlation-Matrix ماتريس همبستگي را براي توليد نتيجه نهايي با استفاده از نتايج اوليه بر اساس رابطه 2-56 توليد مي‌کند. براي توليد دندوگرام از ماتريس همبستگي ما از الگوريتم پيوندي ميانگين استفاده کرده‌ايم چون نتايج تجربي اين

پایان نامه
Previous Entries منابع و ماخذ پایان نامه سلسله مراتب Next Entries منابع و ماخذ پایان نامه الگوريتم، خوشه‌بندي، مدل‌سازي