دانلود با لینک مستقیم و پر سرعت .
نوع فایل: word 2010
حجم فایل:685 کیلوبایت
تعداد صفحه:69
چکیده
انتخاب خوشهبندی ترکیبی[1] با در نظر گرفتن کیفیت[2] و تنوع[3]به وسیله:
این موضوع بسیار محتمل است که افرازی موجود باشد که آن افراز از طریق یک معیار پایداری[4] به عنوان یک معیار بد، داوری[5] شود در حالیکه آن افراز یک خوشه بسیار با ارزش[6] یا بیشتر را، شامل شود؛ و بعد آن خوشه کاملا نادیده گرفته میشود. بنابراین، با الهام گرفتن از ارزیابی افرازها[7]، محققان به تعریف معیارهایی برای ارزیابی خوشهها پرداختند. معیارهای پایداری بسیاری مانند اطلاعات متقابل نرمال شده[8] برای اعتبارسنجی یک افراز[9]، پیشنهاد شدهاند. این معیارهای پیشنهاد شده، بر اطلاعات متقابل نرمال شده، بنا میشوند. اشکال تکنیکی که بطور رایج استفاده میشود در این مقاله بحث خواهد شد و یک معیار برای ارزیابی وابستگی[10] بین یک خوشه و یک افراز پیشنهاد میشود که آن معیار، معیار اطلاعات متقابل نرمال و تصحیح شده، ENMI[11]، گفته میشود. معیار ENMI اشکال معیار اطلاعات متقابل نرمال شده معمولی، NMI[12]، را تصحیح میکند. همچنین، یک روش خوشهبندی ترکیبی، که مبتنی بر تجمیع[13] زیرمجموعهای از خوشههای اولیه[14] است، نیز پیشنهاد میشود. روش پیشنهادی از میانگین ENMI[15] به عنوان معیار برازندگی[16] برای انتخاب تعدادی از خوشهها استفاده میکند. خوشههایی که یک آستانه از پیش تعریف شده[17] مربوط به معیار ذکر شده را ارضا کنند، برای شرکت در ترکیب نهایی انتخاب میشوند. برای ترکیب خوشههای انتخاب شده مجموعهای از شیوههای تابع توافق[18] بکار گرفته میشود. یک کلاس از توابع توافق استفاده شده، توابع توافق مبتنی بر همبستگی[19] میباشد. بخاطر اینکه روش خوشهبندی انباشت مدرک، EAC[20]، نمیتواند ماتریس همبستگی[21] را از مجموعهای از خوشهها بیرون بکشد، EAC توسعه یافته، EEAC[22]، برای ایجاد ماتریس همبستگی از مجموعه خوشههای انتخاب شده بکار گرفته میشود. دومین کلاس توابع توافق استفاده شده، بر الگوریتمهای افرازبندی ابر گراف[23] بنا میشود. کلاس دیگری از توابع توافق استفاده شده، خوشههای انتخاب شده را به عنوان یک فضای ویژگی[24] جدید در نظر میگیرد و از یک الگوریتم خوشهبندی ساده برای استخراج افرازبندی توافقی[25] استفاده میکند. مطالعات تجربی نشان میدهد که روش پیشنهادی از ترکیبهایی که تاکنون شناخته شدهاند بهتر عمل میکند و ترکیب مناسبتری از خوشهبندها را انتخاب میکند.
واژههای کلیدی: خوشهبندی ترکیبی، معیار پایداری، پایداری بهبود یافته[26]، انباشت مدرک[27]، EAC بهبود یافته، ماتریس همبستگی، ارزیابی خوشه[28].
مقدمه
تشخیص الگو[1] تقریبا در تمام زمینههای علمی استفاده شده است (N. Pattanasri, 2012). با این حال در دهه اخیر شیوههای ترکیبی به عنوان یک شیوه قدرتمند، تقریبا در تمام زیر رشتههای تشخیص الگو در بین جوامع هوش مصنوعی[2] پدیدار شدهاند و آن اخیرا در ردهبندی نیز مورد توجه قرار گرفته است (R.R. Derakhshani, 2011؛ C.H. Wu, 2011؛ J. Wagner, 2011).
خوشهبندی داده[3] یا یادگیری بدون نظارت[4] یک مساله پر چالش و مهم میباشد. هدف خوشهبندی افراز مجموعهای از اشیا بدون برچسب، به گروهها یا خوشههای همگن[5] است (R.O. Duda, et al. 2001). کاربردهای زیادی وجود دارد که از تکنیکهای خوشهبندی[6] برای کشف ساختارهای موجود در دادهها استفاده میکنند مانند دادهکاوی[7] (R.O. Duda, et al. 2001)، بازیابی اطلاعات[8]، قطعهبندی تصویر[9]، و یادگیری ماشین[10] (A. Fred and A.K. Jain, 2005). در مسائل واقعی[11]، خوشهها میتوانند با شکلها، اندازهها، درجات پراکندگی داده[12]، و درجات جدایی[13] متفاوت ظاهر شوند. تکنیکهای خوشهبندی به تعریف یک معیار تشابه[14] بین هر جفت الگو نیاز دارد. به علت فقدان هیچ دانش قبلی درباره شکلها و ساختارهای خوشه، انتخاب یک روش خوشهبندی تخصصی[15] آسان نیست (V. Roth, et al. 2002).
مانند همه زیر رشتهها در تشخیص الگو و ردهبندی[16]مطالعات ترکیب خوشه[17] نیز در سالهای اخیر گرایش به شیوههای ترکیبی[18] داشتهاند (K. Faceli, et al. 2006). شیوههای ترکیب خوشه میکوشند تا یک راه حل خوشهبندی مستحکمتر[19] و بهتر -از طریق آمیختن اطلاعات[20] از چندین افرازبندی دادهای اولیه[21]- پیدا کنند (.G. Ayad, and M.S. Kamel, 2008). خوشهبندی ensembles، (C. Domeniconi, and M. Al-Razgan, 2009؛ J. Ghosh, and A. Acharya, 2011؛ R. Ghaemi, et al. 2011)، ****[22]. افراز توافقی باید بهترین افراز نماینده[23]، برای همه خوشهبندیهای اولیه[24] موجود در ترکیب باشد. افراز توافقی آن افرازی است که یک تابع هدف معین[25] را بهینه میکند.
به طور عمومی، دو گام اصلی در خوشهبندی ترکیبی وجود دارد: الف) ایجاد تعدادی افرازبندی ضعیف[26]، ب) تجمیع[27] افرازبندی اولیه بدست آمده. گام نخست ایجاد تعدادی افراز ضعیف میباشد. بخاطر آنکه هر افرازبندی اولیهای یک جنبه پنهان داده[28] را آشکار میکند، ترکیبشان میتواند اشکالهای انفرادیشان[29] را پوشش دهد. بنابراین، نتایج اولیه برای تا حد ممکن متنوع بودن نیاز میشوند تا اطلاعات بیشتری درباره الگوهای پنهان موجود در داده[30] را ارائه دهد. روشهای بسیاری برای ایجاد تنوع لازم در نتایج اولیه پیشنهاد شده است. برای انجام این کار، سادهترین راه استفاده از الگوریتمهای خوشهبندی مختلف میباشد. بعضی روشهای دیگر از این راهها چنین کاری را انجام میدهد: مقداردهی اولیه[31] متفاوت، پارامترهای الگوریتمی متفاوت، زیرمجموعهای از ویژگیها، نگاشت[32] داده به فضاهای ویژگی دیگر (.G. Ayad, and M.S. Kamel, 2008)، نمونهبرداری مجدد داده[33] (B. Minaei-Bidgoli, et al. 2004). در این مقاله نمونهبرداری مجدد، الگوریتمهای پایه متفاوت، مقداردهی اولیه متفاوت و پارامترهای متفاوت برای فراهم کردن تنوع لازم در نتایج اولیه، استفاده میشوند. دومین گام اصلی در خوشهبندی ترکیبی، ترکیب[34] افرازبندیهای اولیه حاصل از گام نخست است. جمع کننده مبتنی بر ماتریس همبستگی[35]، یکی از رایجترین شیوههای ترکیب افراز اولیه است که در این مقاله نیز بکار برده میشود. خوشهبندی انباشت مدرک (EAC) [36] که نخست توسط فرد و جین[37] پیشنهاد میشود، افرازهای دادهای انفرادی[38] موجود در یک خوشهبندی ترکیبی را، به یک معیار تشابه بین-الگویی جدید[39]، با خلاصهسازی ساختارهای درون-الگویی[40] مشاهده شده از این خوشهبندیها، نگاشت میکند. افراز داده نهایی با اعمال روش تک-پیوند[41] با این ماتریس تشابه جدید بدست آورده میشود(A. Fred and A.K. Jain, 2002).
برای ارزیابی یک خوشه، معیار NMI[42] (اطلاعات متقابل نرمال شده) (A. Fred and A.K. Jain, 2005) ضعف[43]های زیادی دارد که در (H. Alizadeh, et al. 2011) تشریح شده است. علیزاده و همکاران نسخه دیگری از NMI که روش M
AX نامیده شده را پیشنهاد میکنند. آنها همچنین نشان دادند که روش MAX نیز اشکالهایی دارد، بنابراین آنها معیار دیگری که APMM نامیده شده را پیشنهاد میکنند، که این اسم ابتدای اسامی نویسندگان آن است (H. Alizadeh, et al. 2011). کارهای پیشین از یک اثر نامناسب که در آن خوشه مکمل[44] از روی معیار خوشه ساخنه میشود، رنج میبرند. بنابراین این مقاله یک معیار جدیدی برای ارزیابی یک خوشه معرفی میکند که در آن ارزیابی تشابه میانگین مربوط به خوشه، از طریق حذف اثر خوشه مکملش، با خوشههای دیگر خواسته میشود.
در این مقاله یک روش خوشهبندی ترکیبی نیز پیشنهاد میشود که زیرمجموعهای از خوشههای اولیه را استفاده میکند. یک معیار اعتبار[45] جدید که stab نامیده میشود برای ارزیابی خوبی خوشه[46] پیشنهاد میشود. هر خوشه که یک آستانه[47] از stab را ارضا کند میتواند برای شرکت در پیدا کردن افراز توافقی در نظر گرفته شود. برای ترکیب خوشههای انتخابی، مجموعهای از روشهای تابع توافق بکار برده میشوند. یک کلاس از توابع توافق استفاده شده، توابع توافق مبتنی بر همبستگی[48] میباشد. از آنجا که روش EAC نمیتواند ماتریس همبستگی را از زیرمجموعهای از خوشهها بیرون بکشد خوشهبندی انباشت مدرک توسعهیافته (EEAC) [49] برای تولید ماتریس همبستگی از زیرمجموعه انتخابی خوشهها بکار برده میشود. دومین کلاس توابع توافق مورد استفاده، بر الگوریتمهای افرازبندی ابرگراف[50] بنا میشود. کلاس دیگر توابع توافق مورد استفاده، خوشههای انتخابی را به عنوان یک فضای ویژگی جدید در نظر میگیرد و الگوریتم خوشهبندی سادهای را برای استخراج افراز توافقی بکار میبرد.
پیش زمینه
هنگامی که هر یک از خوشهبندیهای پایه روی زیرداده خاصی[51] خوب کار میکند، خوشهبندی ترکیبی تلاش میکند تا به یک افراز توافقی مستحکم، و بطور همزمان بهینه برسد (.G. Ayad, and M.S. Kamel, 2008؛ A. Fred and A. Lourenco, 2008؛ A. Strehl and J. Ghosh, 2002؛ A.P. Topchy, et al. 2003). بطور کلی خوشهبندی ترکیبی composes of two main parts: الف) استخراج افراز متفاوت زیادی خارج از داده که این قسمت ایجاد تنوع[52] نامیده میشود و ب) تجمیع آنها در یک افراز توافقی از طریق روشی که تابع توافق نامیده میشود (این دو قسمت با جزئیات بیشتر در ذیل توصیف میشود).
استفاده از یک خوشهبندی پایه با مقداردهیهای اولیه متفاوت منبعی از تولید تنوع مورد نیاز برای یک ترکیب بوده است. در این مسیر الگوریتم k-میانگین[53] بیشترین سهم را برای ایجاد تنوع مورد نیاز در یک ترکیب را دارد (B. Minaei-Bidgoli, et al. 2004؛ B. Minaei-Bidgoli, et al. 2011). بعد از ایجاد ترکیب متنوعی از افرازهای پایه نیاز به بکار گیری یک الگوریتم به منظور تجمیع آنها در یک افراز توافقی میباشد. این الگوریتم همچنین معمولا بعنوان تابع توافق نیز خوانده میشود. استفاده از یک ماتریس همبستگی که افرازهای پایه را نمایش می دهد و سپس استخراج یک افراز از آن ماتریس از طریق بکارگیری یک الگوریتم خوشه بندی سلسله مراتبی[54] مانند تک پیوند[55] یکی از رایجترین روشها میباشد. روش EAC که بر ماتریس همبستگی بنا میشود نخست توسط فرد و جین[56] معرفی شد (A. Fred and A.K. Jain, 2002) و خیلی زود یک روش محبوب شد.
توابع توافق دیگر بر الگوریتمهای افرازبندی ابرگراف[57] بنا میشوند (A. Strehl and J. Ghosh, 2002). استرل و گوش[58] مفهوم افراز توافقی را معرفی کردهاند. آنها سه تابع توافقی مبتنی بر مفهوم ابرگراف پیشنهاد کردهاند. آنها ترکیب خوشه بندیهای پایه درون یک ابرگراف را طرح ریزی کردهاند. رئوس[59] موجود در ابرگراف، نمونهها[60] هستند. لبه[61]های ابرگراف خوشهها هستند یعنی لبهها ممکن است به بیش از دو راس متصل باشند، بنابراین یک لبه در ابرگراف ابرلبه[62] نامیده میشود. با روشهای پیشنهاد شده توسط ریاضیدانان برای افراز ابرگره با کمترین برش[63] آنها رئوس یا نمونهها را خوشهبندی کردهاند. برای کاهش k-برش[64] از ابرگراف به k خوشه تاکنون تعدادی ابتکارات بطور خوب سازمان یافته[65]، برای حل k-روش مساله افرازبندی کمترین-برش[66] معرفی شدهاند. سه الگوریتم ابرگراف، CSPA، HGPA، و MCLA، توصیف خواهد شد.
در CSPA، فضای ویژگی اصلی درآغاز در یک فضای دادهای همبسته طرحریزی میشود. سپس با درنظر گرفتن این ماتریس بعنوان یک گراف یک الگوریتم مانند METIS بر داده طرحریزی شده برای خوشه کردن آنها اعمال میشود. لازم است گفته شود که METIS الگوریتمی است که یک ابرگراف را به تعدادی جزء[67] افراز میکند که کمترین برش را دارد. CSPA سادهترین روش ابتکاری میان سه روش میباشد. این روش زمانبرترین[68] آنها نیز میباشد. الگوریتم HGPA فرض میکند که رئوس، *************.
الگوریتم METIS بر گراف تعریف شده برای خوشه کردن رئوس یا نمونه های دیتا اعمال می شود. MCLA تلاش می کند تا خوشههای بدست آمده در افرازهای پایه ترکیب را خوشهبندی کند. سپس یک مکانیزم مبتنی بر رایگیری[69] را برای ایجاد افراز توافقی استفاده میکند. نام دیگر این روش خوشه بندی خوشه[70] میباشد. خوشه بندی خوشه با استفاده از METIS انجام میشود. برای جزئیات بیشتر در مورد توابع توافقی مبتنی بر ابرگراف به (A. Strehl and J. Ghosh, 2002)رجوع کنید.
یک طبقهبندی خوب از توابع توافقی مختلف در شکل (3-1) نشان داده شده است.
فهرست مطالب
فصل 1: مقدمه 1
1-1- مقدمه. 2
فصل 2: پیش زمینه 6
فصل 3: کار مرتبط 10
فصل 4: خوشه بندی ترکیبی پیشنهادی 18
4-1- گام اول: تولید خوشه های اولیه. 20
4-2- گام دوم: محاسبه پایداری... 21
4-3- گام سوم: انتخاب مبتنی بر پایداری... 26
4-4- گام چهارم: تابع توافقی و بدست آوردن افراز نهایی... 27
فصل 5: نتایج تجربی 32
5-1- متریک ارزیابی... 33
5-2- محکها 35
5-3- تنظیمات آزمایش.... 36
5-4- نتایج تجربی... 37
فصل 6: نتایج 46
مراجع 48
فهرست اشکال
شکل (3-1) توابع توافقی مختلف.... 12
شکل (3-2) طرح خوشهبندی ترکیبی پیشنهادی... 17
شکل (4-1) محاسبه پایداری خوشه 1 افراز در شکل (4-1-الف). ملاحظه افراز در شکل (4-1-ب) از مجموعه مرجع استفاده کننده از روش NMI. 21
شکل (4-2) محاسبه پایداری خوشه 1 افراز در شکل (4-2-الف). ملاحظه افراز در شکل (4-2-ب) از مجموعه مرجع استفاده کننده از روش Max. 24
شکل (4-3) محاسبه پایداری خوشه 1 افراز در شکل (4-3-الف). ملاحظه افراز در شکل (4-3-ب) از مجموعه مرجع استفاده کننده از روش APMM. 24
شکل (4-4) محاسبه پایداری خوشه 1 افراز در شکل (4-4-الف). ملاحظه افراز در شکل (4-4-ب) از مجموعه مرجع استفاده کننده از روش ENMI. 25
شکل (4-5) محاسبه پایداری خوشه Ci 27
شکل (4-6) چهار افراز π1 تا π4 از یک مجموعه داده ساده با 12 نقطه دادهای و دو خوشه واقعی از طریق خوشهبندی k-میانگین استخراج میشوند.k پارامتر در k-میانگین به ترتیب 3، 4، 2، و 2 گذاشته میشود. 27
شکل (4-7) خوشههای استخراج شده از افرازهای شکل (4-6). 28
شکل (4-8) روشهای مختلف برای انجام گام 4. 30
شکل (4-9) روشهای مختلف برای خوشبندی ترکیبی... 31
شکل (5-1) مجموعه داده halfring. 36
شکل (5-2) محور افقی نشانگر نرخ خوشههای پایداری است که با استفاده از روش ENMI انتخاب میشوند. محور عمودی نشانگر مقدار NMI برای مجموعه داده Wine میباشد. 37
شکل (5-3) محور افقی نشانگر نرخ خوشههای پایداری است که با استفاده از روش ENMI انتخاب میشوند. محور عمودی نشانگر مقدار NMI میانگینگیری شده روی هر ده مجموعه داده جدول (5-1) میباشد. 38
شکل (5-4) محور افقی نشانگر نرخ خوشههای پایداری است که با استفاده از روش ENMI انتخاب میشوند. محور عمودی نشانگر مقدار دقت میانگین گیری شده روی هر ده مجموعه داده جدول (5-1) میباشد. 38
شکل (5-5) محور افقی نشانگر نرخ خوشه های پایداری است که با استفاده از روش ENMI انتخاب میشوند. محور عمودی نشانگر معیار-F میانگین گیری شده روی هر ده مجموعه داده جدول (5-1) میباشد. 39
شکل (5-6) محور افقی نشانگر نرخ خوشه های پایداری است که با استفاده از روش ENMI انتخاب میشوند. محور عمودی نشانگر میانگین محورهای عمودی در شکل (5-3)، شکل (5-4) و شکل (5-5) میباشد. 40
شکل (5-7) محور افقی نشانگر نرخ خوشه های پایداری است که انتخاب میشوند. محور عمودی مشابه شکل (5-6) میباشد با این تفاوت که معیار MAX به عنوان معیار پایداری یک خوشه به کار میرود. 41
شکل (5-8) محور افقی نشانگر نرخ خوشههای پایداری است که انتخاب میشوند. محور عمودی مشابه شکل (5-6) میباشد با این تفاوت که معیار APMM به عنوان معیار پایداری یک خوشه به کار میرود. 42
شکل (5-9) محور افقی نشانگر نرخ خوشههای پایداری است که انتخاب میشوند. محور عمودی مشابه شکل (5-6) میباشد با این تفاوت که معیار NMI اصلی به عنوان معیار پایداری خوشه به کار میرود. 42
فهرست جداول
جدول (5-1) اطلاعات مختصر درباره مجموعه دادههای استفاده شده. 35
جدول (5-2) دقت افراز توافقی تولید شده با انتخاب خوشه معیارهای NMI و MAX و APMM. 41
جدول (5-3) نتایج تجربی... 44
