
ميشوند. در اين روش مقدار پايداري خوشه بر اساس رابطه 2-30 ارزيابيشده و با استفاده از روش انباشت مدارك اصلاح توسعهيافته (رابطه 2-70) نتيجهي نهايي را ميسازيم [8, 9, 67].
شكل 2-33. چهارچوب خوشهبندي تركيبي مبتني بر انتخاب با استفاده از مجموعهاي از خوشههاي يک افراز[8, 9]
شكل 2-33 چهارچوب خوشهبندي تركيبي مبتني بر انتخاب با استفاده از مجموعهاي از خوشههاي يك افراز را نشان ميدهد. در اين روش ابتدا الـگوريتمهاي خوشهبندي پـايه نتايج اوليه را تـوليد ميكنند و سپس از ارزيابي پايداري (با استفاده از معيار MAX و يا APMM) خوشههاي افرازهاي توليدشده تعدادي از آنها را انتخاب ميكنيم. قابلذکر است كه اين تعداد در ابتدا توسط كاربر براي الگوريتم تعريف ميشود. عليزاده و همكاران عمل انتخاب خوشههاي ارزيابيشده براي شركت در تركيب نهايي را آستانهگيري مينامند. مطابق شكل 2-33 پس از تشكيل مجموعه نهايي تركيب با استفاده از روش انباشت مدارك توسعهيافته اقدام به توليد نتيجه نهايي ميكنيم. اين تحقيق به توسعه يك معيار ارزيابي افراز مبتني بر معيار AMPP ميپردازد چون اولاً اين معيار مشكل تقارن NMI را ندارد و در ثاني كارايي بالاي آن اثبات شده است [1, 8, 67].
2-5. روش بهترين افراز توافقي اعتبارسنجي شده
روش بهترين افراز توافقي اعتبارسنجي شده138 يا همان BVCP که اخيراً توسط نالدي و همکاران ارائه شده است به اين موضوع اشاره ميکند که معيارهاي ارائهشده (شاخصهاي نسبي اعتبارسنجي خوشهبندي139) جهت ارزيابي و انتخاب افراز و يا خوشه در روشهاي خوشهبندي ترکيبي مبتني بر انتخاب هر کدام بر روي يک سري مجموعه داده بهتر عمل ميکنند. از اين روي مطابق شکل زير در اين روش پيشنهاد ميشود تا از نتايج ترکيب کامل به همراه چندين ترکيب مبتني بر انتخاب (CES) براي ساخت نتيجهي نهايي استفاده شود [87].
شکل 2-34. چهارچوب روش بهترين افراز توافقي اعتبارسنجي شده [87]
در اين روش مطابق شکل بالا ابتدا توسط الگوريتمهاي خوشهبندي پايه نتايج اوليه را ايجاد ميکنيم. افرازهاي به دست آمده در اين بخش توسط الگوريتم خوشهبندي ترکيب کامل و چند الگوريتم خوشهبندي ترکيبي مورد استفاده قرار ميگيرند. در اين روش پس از ساخت ماتريسهاي همبستگي با استفاده از روشهاي ترکيبي آنها را در مجموعهاي جهت ارزيابي و انتخاب جمعآوري ميکنيم. پس از ارزيابي نتايج ماتريسهاي همبستگي بهترين افراز به عنوان جواب نهايي انتخاب ميشود. در اين روش شاخصهاي SS140، ASS141، VRC142، PBM، DB143 و Dunn جهت ارزيابي ماتريسهاي همبستگي معرفيشدهاند. قابلذکر است که مسائلي همچون پيچيدگي زماني، روش انتخاب شاخصها و الگوريتمهاي خوشهبندي ترکيبي و تأثيرات توابع توافقي مختلف بر روي نتيجه نهايي در اين روش با ابهامات زيادي رو به رو است. از آن جايي که تمرکز اين تحقيق بر روي ارائهي روشهاي خوشهبندي ترکيبي مبتني بر انتخاب ميباشد و نه ارزيابي و ترکيب نتايج آنها بنابراين تشريح روش کار اين الگوريتم خارج از محدودهي کاري اين تحقيق ميباشد.
2-6. استفاده از نظريه خرد جمعي در علوم رايانه
استفاده از نظريههاي مطرح شده در ساير علوم از نظير رياضيات، اقتصاد، مديريت و غيره در علوم رايانه امري بعيد و دور از انتظار نيست. کارايي نظريه خرد جمعي که اولين بار توسط سورويکي در سال 2004 در کتابي با همين عنوان مطرح شده است، توسط مثالهاي فراواني از قضاياي اجتماعي، اقتصادي و غيره اثبات شده است. از اين روي در سالهاي اخير از نظريه خرد جمعي در چند تحقيق در حوزهي علوم رايانه استفاده شده است که ما به برخي از آنها به صورت مختصر اشاره ميکنيم. استيورز144 و همکاران از خرد جمعي براي باز جمعآوري اطلاعات مرتب شده استفاده کردهاند [92] و ميلر145 و همکاران يک رويکرد جديد براي رتبهبندي مسائل مرتبشده ارائه دادهاند [91]. ولي ندر146 و همکاران از اين نظريه براي تخمين مقادير اساسي (نظير کلاس147 در طبقهبندي148) براي هر تصوير در محيط نويزي استفاده کردهاند که آن را خرد جمعي چندبُعدي149 ناميدهاند [89]. ويليام و همکاران راهکاري با عنوان طبقهبندي معدن زير آب150 با استفاده از برچسبهاي بدون کيفيت بر اساس نظريه خرد جمعي ارائه دادهاند [90]. يي و همکاران بر اساس اين نظريه روشي براي مسئله درخت پوشاي حداقل151 ارائه دادهاند [88]. بيکر و همکاران با استفاده از نظريه خرد جمعي در محيطهاي مدلسازي يک روش براي طبقهبندي ترکيبي ارائه دادهاند [10]. لازم به ذکر است که اين تحقيق در نگاشت شرايط چهارگانه خرد جمعي به خوشهبندي ترکيبي مبتني بر انتخاب از مفاهيم و ايدههاي مطرحشده در [10] استفاده کرده است که در بخش سوم به بررسي آنها ميپردازيم.
فصل سوم
روش تحقيق
3. روش تحقيق
3-1. مقدمه
در اين فصل ابتدا به بررسي نظريه خرد جمعي بر اساس تعاريف کتاب سورويکي ميپردازيم. در اين راستاي ابتدا شرايط چهارگانه جامعه خردمند را بررسي ميکنيم و سپس به بررسي استثناها در اين نظريه خواهيم پرداخت. پس از تشريح نظريه خرد جمعي، روش پيشنهادي اول اين تحقيق را شرح ميدهيم. اين روش را ما با عنوان “خوشهبندي خردمند با استفاده از آستانهگيري” ميشناسيم که در آن مطابق با ادبيات مطرحشده در خوشهبندي ترکيبي، ابتدا به بيان چهارچوب کلي آن پرداخته و سپس براي شرايط چهارگانه خرد جمعي تعريفي متناسب و جديد ارائه ميدهيم. آنگاه بر اساس اين تعاريف الگوريتم پيشنهادي روش اول را بيان ميکنيم. در اين روش پس از توليد نتايج اوليه با استفاده از چهارچوب پيشنهادي غيرمتمرکز به آستانهگيري از نتايج به دست آمده از ارزيابي درجه استقلال الگوريتمها و پراکندگي نتايج اوليه ميپردازيم و در پايان بر اساس نتايج انتخابشده (افرازهاي خردمند) نتيجه نهايي را توليد ميکنيم. در اين روش دو الگوريتم پايه غير هم نام کاملاً مستقل و درجه استقلال الگوريتمهاي هم نام بر اساس پارامترهاي اساسي آنها محاسبه ميشود.
در ادامه، روش پيشنهادي دوم اين تحقيق بيان ميشود. اين روش که ما آن را با عنوان ” خوشهبندي خردمند مبتني بر گراف استقلال الگوريتم “ميشناسيم به بهبود دو بخش از روش اول ميپردازد. اين روش در ابتدا اين ايده را بررسي ميکند که الگوريتمهاي غير هم نام کاملاً مستقل نيستند. در اين راستاي براي محاسبه درجه استقلال دو الگوريتم با استفاده از ايده تبديل کد به گراف در تست نرمافزار به ارائه روشي با عنوان مدلسازي گراف استقلال الگوريتم ميپردازيم. با مقايسه گرافهاي به دست آمده (درجه استقلال) در اين روش ميتوان يک وزن براي احتمال صحت جوابهاي به دست آمده پيشنهاد داد. از اين روي در اين روش به جاي ارزيابي و آستانهگيري از استقلال الگوريتمها، آنها را به عنوان وزني براي ترکيب نتايج در نظر ميگيريم که اين کار نياز به تعيين آستانه براي استقلال را از بين ميبرد. در روش دوم پيشنهادي اين تحقيق رابطهاي جديد بر اساس رابطه 2-56 براي ترکيب نتايج اوليه به صورت وزندار با عنوان روش انباشت مدارک وزندار يا 152WEAC معرفي ميشود.
3-2. نظريه خرد جمعي
“فرانسيس گالتون” فيلسوف و دانشمند علم آمار از انگلستان بود که مفاهيم اصلي انحراف استاندارد و همبستگي را معرفي کرد. يک روز که او از نمايشگاه دام بازديد ميکرد، به جايي رسيد که در آن مسابقهاي ترتيب داده شده بود. يک گاو نر فربه انتخابشده و در معرض ديد عموم قرار گرفته بود. هر کس که تمايل شرکت در مسابقه را داشت بايد شش پنس ميپرداخت و ورقهاي مهرشده را تحويل ميگرفت. در آن ورقه بايد تخمين خود را از وزن گاو نر مينوشت. نزديکترين تخمين به واقعيت برنده مسابقه بود و جوايزي به صاحب آن تعلق ميگرفت. مجموعاً ٧٨٧ نفر در مسابقه شرکت کردند تا شانس خود را بيازمايند. افراد از همه تيپ و طبقهاي آمده بودند. از قصاب گرفته که قاعدتاً بايد بهترين و نزديکترين نظر را به واقعيت ميداد تا کشاورز و مردم عامي بي تخصص. گالتون ميخواست دريابد عقل جمعي مردم پليموت چگونه قضاوت کرده است. بدون شک تصور او اين بود که عدد مزبور فرسنگها از عدد واقعي فاصله خواهد داشت چرا که از ديد وي افراد کمهوش و عقبمانده در آن جمع اکثريت قاطع را تشکيل ميدادند. برخلاف نظر گالتون، متوسط نظرات جمعيت اين بود که گاو نر ١١٩٧ پوند وزندارد و وزن واقعي گاو که در روز مسابقه وزنکشي شد ١١٩٨ پوند بود. گالتون اشتباه ميکرد. نظر جمع تقريباً به طور کامل با واقعيت تطابق داشت گالتون در مقالهاي که در مجله علمي “طبيعت” منتشر نمود نوشت نتايج نشان ميدهد که قضاوتهاي جمعي و دموکراتيک از اعتبار بيشتري نسبت به آنچه که من انتظار داشتم برخوردارند [44]. نظريه هيئتمنصفه كه اولين بار توسط کندورست بيان شد نيز اين نتيجه گالتون را تأييد ميکند. اين نظريه در علوم سياسي، احتمال نسبي درستي نظر گروهي از افراد (رأي اکثريت) را بررسي ميکند. نظريه خرد جمعي که اولين بار توسط سورويکي در کتابي با همان عنوان انتشار يافته است، تأييد ميکند که يک جمع ميتواند مسئله را بهتر از اکثر اعضاي گروه حل کند. مطابق تعريف اين کتاب، يک جمعيت به هر گروهي از افراد اطلاق ميشود که ميتوانند به طور جمعي تصميمي بگيرند يا مسئلهاي را حل کنند [55].
3-2-1. شرايط جامعه خردمند
خرد جمعي روشي نوين براي تصميمگيريهاي اجتماعي ميباشد. كارايي اين روش نه تنها در نظريه بلكه در عمل نيز در مسايل مختلف اثبات شده است كه پيشتر به آن اشاره شده است. اين روش تأييد ميکند که يک جمع ميتواند مسئله را بهتر از اکثر اعضاي گروه حل کند مطابق تعريف اين خرد جمعي، يک جمعيت به هر گروهي از افراد اطلاق ميشود که ميتوانند به طور جمعي تصميمي بگيرند يا مسئلهاي را حل کنند. مطابق تحقيقات مککي، همه جمعيتها (گروهها) خردمند نيستند. يک مثال روشن از اين قضيه بازار سهام است که جمعيت به سمت حباب بازار هدايت ميشود. بنابراين ابتدا بايد فهميد که تحت چه شرايطي خرد جمعي ميتواند اثرگذار باشد [44]. از اين روي در اين روش چهارچوبي جهت تعريف جامعه خردمند ارائه شده است. سورويکي چهار شرط اساسي زير را براي تمايز جمعيت خردمند از يک جمعيت غير عاقل پيشنهاد ميدهد: [55]
1- تنوع (پراكندگي153) آراء
2- استقلال154 آراء
3- عدم تمركز155 آراء
4- روش تركيب156 مناسب
3-2-1-1. تعريف معيار پراكندگي
در خرد جمعي معيار تنوع يا پراكندگي به صورت زير تعريف ميشود:
“هر فرد بايد به طور جداگانه اطلاعي از موضوع مورد نظر داشته باشد حتي اگر اطلاعات مزبور غلط و مخدوش باشد.” [55]
يکي از دلايلي که سورويکي در خصوص چرايي کارکرد نظريه خرد جمعي مطرح ميکند اين است که نظر هر فرد دو عنصر را در درون خود دارد اطلاعات صحيح و غلط. اطلاعات صحيح (از آن رو که صحيحاند) هم جهتاند و بر روي يکديگر انباشته ميشوند اما خطاها در جهات مختلف و غير همسو عمل ميکنند لذا تمايل به حذف يکديگر دارند. نتيجه اين ميشود که پس از جمع نظرات آنچه که ميماند اطلاعات صحيح است. از اين روي معيار پراكندگي يكي از مهمترين اصلها در خرد جمعي است زيرا به طور مستقيم بر روي ميزان هم جهت سازي آراي تأثير دارد [55].
3-2-1-2. تعريف معيار استقلال
استقلال يكي ديگر از اصلهاي خرد جمعي است. در صورت وابستگي افراد به گروه يا فرد خاصي اصل هم جهتي در آراي از بين مي رود. به عبارت ديگر در صورت نبود استقلال مقدار انحراف معيار آراي جامعه آماري ما واقعي نخواهد بود و نظريه خرد جمعي در اينگونه جوامع كه ما آن را در با عنوان جامعههاي ديكتاتوري ميشناسيم درست عمل نميکند. در خرد جمعي معيار استقلال به صورت زير تعريف ميشود:
“نظر افراد بايد به طور مستقل و بدون تأثير گرفتن از يک فرد يا گروه مشخص شکل گيرد.” [55]
3-2-1-3. تعريف معيار عدم تمركز
در خرد جمعي معيار عدم تمركز به صورت زير تعريف ميشود:
” افراد بايد توانايي شخصي سازي و نتيجهگيري مبتني بر دانش محلي خود را
