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

درجه استقلال نهايي هر الگوريتم را‌ در حين اجرا نشان مي‌دهد:
(3-10)
در اين رابطه Algi نشان‌دهنده الگوريتمي است که قرار است درجه استقلال نهايي آن محاسبه شود و WisedCrowd جامعه خردمند و يا همان نتايج اوليه انتخاب‌شده مي‌باشد و n تعداد الگوريتم‌هاي غير هم ‌نام و m تعداد الگوريتم‌هاي هم ‌نام با اين الگوريتم در جامعه خردمند مي‌باشد. در اين رابطه به ازاي هر الگوريتم غير هم نام درجه استقلال آن نسبت به الگوريتم از ماتريس AIDM خواند مي‌شود و به ازاي هر الگوريتم هم نام درجه استقلال آن نسبت به الگوريتم بر اساس پارامتر‌هاي اساسي الگوريتم که حين اجرا توليد مي‌شوند با استفاده از تابع BPI محاسبه مي‌شود. بديهي است که AI همواره مقداري بين صفر و يک خواهد داشت چون از ميانگين اعدادي که هميشه بين صفر و يک هستند به دست مي‌آيد. همچنين جهت استفاده از درجه استقلال نهايي به دست آمده به عنوان وزن در ترکيب نتايج اوليه آن‌ها را در ماتريسي با عنوان ماتريس استقلال الگوريتم‌ها180 يا همان AIM نگهداري مي‌کنيم. قابل‌ذکر است که اين ماتريس فقط و فقط استقلال نهايي الگوريتم‌هايي که موفق به ورود به جامعه خردمند شده‌اند را نگهداري مي‌کند و نه تمام الگوريتم‌هايي که در تشکيل نتايج اوليه خوشه‌بندي ترکيبي نقش داشته‌اند.

3-4-3-2. روش انباشت مدارک وزن‌دار
در سال‌هاي اخير بسياري از مقالات جهت ترکيب نتايج خوشه‌بندي از روش انباشت مدارک به خاطر کالايي بالاي آن استفاده کرده‌اند [8, 9, 19, 21, 67]. در اين روش براي ترکيب نتايج از رابطـه 2-56 استفاده مي‌شود. همان طور که پيش‌تر ذکر شد در اين رابطه پارامتر تعداد دفعاتي است که جفت نمونه‌هاي و باهم در يک خوشه گروه‌بندي شده‌اند و همچنين تعداد نمونه‌برداري‌هايي است که هر دوي اين جفت نمونه‌ها به طور همزمان در آن ظاهرشده‌اند. با توجه به نحوه محاسبه پارامتر مي‌توان گفت شمارش تعداد نمونه‌ها يعني هر نتيجه با وزن مساوي و برابر با يک در جواب نهايي شرکت مي‌کند. در اين تحقيق ديدگاه جديدي در مورد رابطه 2-56 مطرح خواهد شد که در آن قرار است درجه نهايي استقلال هر الگوريتم به عنوان وزني براي احتمال درستي هر نتيجه در نظر گرفته شود. از اين روي از رابطه 3-11 که ما آن را با عنوان روش انباشت مدارک وزن‌دار181 يا همان نام‌گذاري کرده‌ايم براي ترکيب نتايج استفاده خواهيم کرد.
(3-11)
در رابطه 3-11 متغير نشان‌دهنده ماتريس درجه استقلال الگوريتم مي‌باشد و تعداد دفعاتي است که جفت نمونه‌هاي و باهم در يک خوشه گروه‌بندي شده‌اند و تابع res مقدار مربوط به نمونه -ام (که اين مقدار برابر با مقدار نمونه -ام نيز است) را از نتايج اوليه خوشه‌بندي بر مي‌گرداند و شماره‌ي الگوريتمي که دو نمونه و را توليد کرده است بر مي‌گرداند که متناسب با آن درجه استقلال نهايي آن الگوريتم از ماتريس AIM خوانده خواهد شد. همچنين در اين رابطه تعداد نمونه‌برداري‌هايي است که هر دوي اين جفت نمونه‌ها به طور همزمان در آن ظاهرشده‌اند.
3-4-3-3. شبه کد خوشه‌بندي خردمند مبتني بر گراف استقلال الگوريتم
همان طور که پيش‌تر اشاره شد شکل 3-25 چهارچوب روش پيشنهادي دوم اين تحقيق را ارائه مي‌دهد. اين فرآيند با توليد نتايج اوليه شروع مي‌شود و در ادامه با ارزيابي پراکندگي و وزن‌هاي به دست آمده از ماتريس استقلال الگوريتم اقدام به توليد جامعه خردمند مي‌کنيم. در نهايت با استفاده از روش انباشت مدارک وزن‌دار افرازهاي جمع‌آوري شده در جامعه خردمند با يکديگر ادغام‌شده و نتيجه نهايي را توليد مي‌کند. شکل 3-26 نشان‌دهنده شبه کد روش پيشنهادي دوم است.
Function WCboAIG (Dataset, Kb, dT, cT) Return [Result, nCrowd]
Initialized nCrowd to zero
While we have base cluster
[IDX, Basic-Parameter] = Generate-Basic-Algorithm (Dataset, Kb*cT)
If (Diversity (IDX) > dT) then
Find the Algoritms AID from AIDM
Insert idx, AID, and Basic-Parameter to Crowd-Partitions
Crowd = Crowd + 1
End if
End while
Generate AIM matrix
W-Co-Acc = WEAC (Crowd-Partition, AIM)
Z = Average-Linkage (W-Co-Acc)
Result = Cluster (Z, Kb)
شکل3-26. شبه کد خوشه‌بندي خردمند مبتني بر گراف استقلال الگوريتم

در اين شکلتعداد خوشه‌ها در الگوريتم پايه مي‌باشد. همانند روش اول پارامترهاي dT و cT به ترتيب مقادير آستانه براي ارزيابي پراکندگي و عدم تمرکز هستند. تابع Generate-Basic-Algorithm نتايج اوليه (افرازهاي) را با استفاده از الگوريتم‌هاي خوشه‌بندي‌هاي پايه توليد مي‌کند. تابع Diversity براي ارزيابي پراکندگي به کار مي‌رود و تابع WEAC ماتريس همبستگي را براي توليد نتيجه نهايي با استفاده از نتايج اوليه به صورت روش انباشت مدارک وزن‌دار بر اساس رابطه 3-11 توليد مي‌کند. براي توليد دندوگرام از ماتريس همبستگي ما از الگوريتم پيوندي ميانگين استفاده کرده‌ايم چون نتايج تجربي اين تحقيق نشان داده است که اين روش بهترين دقت را داراست. در اينجا تابع Average-Linkage نشان‌دهنده الگوريتم پيوندي ميانگين است. در نهايت تابع Cluster بر اساس تعداد خوشه تعيين‌شده نتيجه نهايي را از روي دندوگرام تشکيل مي‌دهد.
به عنوان نکته پاياني مي‌توان به اين موضوع اشاره کرد که در شبه کد شکل 3-26 با استفاده از روش ارزيابي استقلال مبتني بر گراف و به‌کارگيري آن به عنوان وزن در روش انباشت مدارک وزن‌دار ما ميزان تأثير رأي هر الگوريتم را با تغيير اندازه در سطح‌هاي دندوگرام بر روي نتيجه نهايي اعمال مي‌کنيم. به عنوان مثال مي‌توان گفت اگر دو الگوريتم با درجه استقلال پايين در توليد نتيجه‌ي شبه کد شکل 3-26 شرکت کنند و نتايج مشابه داشته باشند آنگاه روش پيشنهادي دوم فقط و فقط به اندازه ميزان استقلال آن دو الگوريتم شکل دندوگرام را تغيير مي‌دهد که بسيار کمتر از وقتي است که دو الگوريتم کاملاً مستقل (يعني درجه استقلال آن‌ها برابر با يک باشد) با نتايج برابر در تشکيل نتيجه نهايي شرکت مي‌کنند.

فصل چهارم
پياده‌سازي و
تحليل نتايج

4. پياده‌سازي و تحليل نتايج
4-1. مقدمه
در اين فصل نتايج آزمايش‌‌هاي تجربي اين تحقيق را جهت ارزيابي الگوريتم‌هاي پيشنهادي ارائه خواهيم کرد. از اين روي در ادامه در بخش مجموعه داده، ابتدا به بررسي داده‌هاي استاندارد به‌کاررفته در اين تحقيق خواهيم پرداخت. پس از معرفي داده‌ها و مشخصات آن‌ها، در بخش مدل‌سازي الگوريتم‌ها به زبان استقلال الگوريتم‌ ليستي از الگوريتم‌‌هاي پايه که در ساخت نتايج اوليه خوشه‌بندي از آن‌ها استفاده شده است ارائه مي‌گردد و همچنين پياده‌سازي کدهاي الگوريتم‌هاي ذيل به زبان استاندارد استقلال الگوريتم که پيش‌تر به آن اشاره شد نيز ارائه خواهد شد. در بخش ابزار تحليلگر کد استقلال الگوريتم182 به معرفي نرم‌افزاري که متناسب با استاندارد‌هاي اين تحقيق براي تبديل خودکار کد استقلال الگوريتم به گراف و ارزيابي آن به زبان برنامه‌نويسي C# در مجموعه Microsoft Visual Studio 2012 طراحي و ساخته شده است مي‌پردازيم. سرانجام، در بخش نتايج آزمايش‌ها دقت و ميزان NMI نتايج نهايي الگوريتم‌هاي پيشنهادي اين تحقيق نسبت به کلاس‌هاي واقعي داده را با روش‌هاي پيشين مقايسه مي‌کنيم و همچنين تأثير پارامتر‌هاي معرفي‌شده در اين تحقيق همچون پراکندگي، استقلال و عدم تمرکز بر روي کارايي نتايج و زمان اجراي الگوريتم‌ها را بررسي خواهيم کرد. کليه نتايج ارائه‌شده در اين بخش توسط پياده‌سازي و شبيه‌سازي الگوريتم‌ها در نرم‌افزار Matlab R2013a (8.1.0.604) توليد و ارائه‌شده‌اند.
4-2. مجموعه داده‌
در اين تحقيق نتايج تجربي آزمايش‌ها بر روي چهارده مجموعه داده استاندارد براي ارزيابي روش پيشنهادي گزارش‌شده‌اند. بيشتر مجموعه داده‌‌ها در اين تحقيق از مجموعه داده‌هاي استاندارد UCI [76] مي‌باشند که تقريباً نتايج تمام مطالعات اخير دنيا در زمينه خوشه‌بندي با استفاده از اين مجموعه داده‌ها گزارش مي‌شوند. علاوه بر آن از داده Halfring که در کارهاي تحقيقاتي عظيمي و همکاران [2, 4, 5, 6, 7] و عليزاده و همکاران [1, 8, 9, 67] به عنوان يک داده مصنوعي با شکل غير کروي که تشخيص آن توسط الگوريتم‌هاي خوشه‌بندي پايه سخت مي‌باشد نيز مورد استفاده قرار گرفته است. جدول 4-1 مشخصات مجموعه داده‌ به‌کاررفته در ارزيابي الگوريتم‌هاي اين تحقيق را نشان مي‌دهد.
جدول4-1. مجموعه داده
Sample
Class
Feature
Name
No.
400
2
2
Half Ring
1
150
3
4
Iris
2
625
3
4
Balance Scale
3
683
2
9
Breast Cancer
4
345
2
6
Bupa
5
323
7
4
Galaxy
6
214
6
9
Glass
7
351
2
34
Ionosphere
8
462
2
9
SA Heart
9
178
2
13
Wine
10
1484
10
8
Yeast
11
10992
10
16
Pendigits
12
6435
7
36
Statlog
13
5620
10
62
Optdigits
14

در انتخاب مجموعه داده‌ جدول 4-1 سعي شده است که از هر سه نوع داده کوچک، متوسط و بزرگ چند نمونه داده انتخاب شود تا تأثير اندازه‌ي داده بر روي روش عملکرد الگوريتم و نتايج آن کاهش يابد. ويژگي‌هاي مجموعه داده‌ به‌کاررفته در اين تحقيق جهت حذف تأثير مقياس ابعاد داده بر روي نتايج با ميانگين صفر و وردايي183 يک، N(0,1)، نرمال شده‌اند. از آنجايي که به جز داده Halfring مشخصات و روش تهيه تمامي داده‌هاي جدول 4-1 توسط نيومن و همکاران به خوبي در [76] توضيح داده شده است در ادامه به ارائه شکل Halfring و تشريح مشخصات آن بسنده مي‌کنيم. مطابق با شکل 4-1 داده Halfring در نمودار دو بُعدي اعداد نشان داده شده است.

شکل۴-۱. مجموعه داده Halfring [1]