—d1143

فصل سوم
جدول3-1. نگاشت لغات لاتین در خوشه‌بندی ترکیبی به نظریه خرد جمعی .......................................................... 93
جدول3-2. یک نمونه از جدول نگاشت استاندارد کد .............................................................................................. 98
فصل چهارم
جدول4-1. مجموعه داده ........................................................................................................................................ 117
جدول4-2. لیست مجموعه الگوریتم‌های پایه ........................................................................................................ 119
جدول4-3. جدول نگاشت استاندارد کد ................................................................................................................ 120
جدول4-4. دقت نتایج این الگوریتم‌های خوشه‌بندی را نسبت به کلاس‌های واقعی داده ...................................... 130
جدول4-5. جدول مقایسه معیار اطلاعات متقابل نرمال‌ شده (NMI) نتایج آزمایش .............................................. 132

فهرست تصاویر و نمودار
فصل دوم
شکل 2-1. یک خوشه‌بندی سلسله مراتبی و درخت متناظر ..................................................................................... 10
شکل 2-2. ماتریس مجاورت .................................................................................................................................... 11
شکل 2-3. رابطه دودویی و گراف آستانه ................................................................................................................. 12
شکل 2-4. گراف‌های آستانه برای ماتریس ........................................................................................................ 12
شکل 2-5. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی منفرد ..................................................................... 13
شکل 2-6. دندوگرام پیوندی منفرد برای ماتریس............................................................................................... 13
شکل 2-7. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی کامل ...................................................................... 14
شکل 2-8. دندوگرام پیوندی کامل برای ماتریس ............................................................................................... 14
شکل 2-9. الگوریتم خوشه‌بندی افرازبندی...................................................................................... 16
شکل 2-10. الگوریتم فازی خوشه‌بندی ...................................................................................................... 18
شکل 2-11. خوشه‌بندی کاهشی .............................................................................................................................. 23
شکل 2-12. شبه‌کد الگوریتم MKF ........................................................................................................................ 26
شکل2-13. (الف) مجموعه داده با تعداد 10 خوشه واقعی. (ب) منحنی ........................................................ 29
شکل2-1۴. (الف) مجموعه داده (ب) منحنی مربوطه ..................................................................................... 29
شکل2-15. دو افراز اولیه با تعداد سه خوشه ........................................................................................................... 31
شکل2-16. نمونه‌های اولیه در نتایج الگوریتم ................................................................................ 36
شکل 2-17. زیر شبه کد الگوریتم خوشه‌بندی ترکیبی توسط مدل مخلوط .............................................................. 43
شکل 2-18. خوشه‌بندی ترکیبی ............................................................................................................................... 44
شکل 2-19. نمونه ماتریس، جهت تبدیل خوشه‌بندی به ابر گراف ................................................................. 45
شکل 2-20. ماتریس شباهت بر اساس خوشه برای مثال شکل (3-5) .................................................................... 46
شکل 2-21. الگوریتم افرازبندی ابر گراف ............................................................................................................... 47
شکل 2-22. الگوریتم فرا خوشه‌بندی ..................................................................................................................... 49
شکل2-23. الگوریتم خوشه‌بندی ترکیبی مبتنی بر ماتریس همبستگی ...................................................................... 50
شکل2-24. الگوریتم افرازبندی با تکرار ................................................................................................................... 53
شکل2-25. نمایش گراف مجاورت در مراحل کاهش درجه ماتریس و شمارش آن ................................................ 54
شکل2-26. مثال روند تغییر توزیع تعداد خوشه ....................................................................................................... 55
شکل2-27. جریان کار عمومی برای پیاده‌سازی الگوریتم افرازبندی گراف .............................................................. 55
شکل 2-28. گراف تابع در بازه بین صفر و یک ............................................................................................. 62
شکل 2-29. الگوریتم خوشه‌بندی ترکیبی طیفی مبتنی بر انتخاب بر اساس شباهت ................................................ 63
شکل 2-30. مثالی از ماتریس اتصال ........................................................................................................................ 66
شکل 2-31. شبه کد خوشه‌بندی ترکیبی انتخابی لی‌مین .......................................................................................... 68
شکل 2-32. روش ارزیابی خوشهی یک افراز در روش MAX ............................................................................... 69
شکل 2-33. چهارچوب خوشهبندی ترکیبی مبتنی بر انتخاب با استفاده از مجموعه‌ای از خوشه‌های یک افراز ...... 71
شکل 2-34. چهارچوب روش بهترین افراز توافقی اعتبارسنجی شده ...................................................................... 72
فصل سوم
شکل3-1. چهارچوب الگوریتم خوشه‌بندی خردمند با استفاده از آستانه‌گیری ......................................................... 82
شکل3-۲. محاسبه درجه استقلال دو خوشه‌بندی ..................................................................................................... 86
شکل3-3. تأثیر عدم تمرکز بر روی پیچیدگی داده ................................................................................................... 89
شکل3-3. تأثیر انتخاب افرازها در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر مقدار NMI ارزیابی‌شده ........................ 91
شکل3-4. شبه کد خوشه‌بندی خردمند با استفاده از آستانه‌گیری .............................................................................. 92
شکل3-5. دسته‌بندی الگوریتم‌های خوشه‌بندی ........................................................................................................ 94
شکل3-6. کد الگوریتم K-means به زبان استقلال الگوریتم‌ خوشه‌بندی ................................................................. 98
شکل3-7. تبدیل کد‌های شروع و پایان به گراف .................................................................................................... 100
شکل3-8. تبدیل عملگر شرط ساده به گراف ......................................................................................................... 100
شکل3-9. تبدیل عملگر شرط کامل به گراف ......................................................................................................... 101
شکل3-10. تبدیل عملگر شرط تو در تو به گراف ................................................................................................. 101
شکل3-11. تبدیل عملگر حلقه ساده به گراف ....................................................................................................... 102
شکل3-12. تبدیل عملگر حلقه با پرش به گراف ................................................................................................... 102
شکل3-13. پیاده‌سازی شرط ساده بدون هیچ کد اضافی ........................................................................................ 103
شکل3-14. پیاده‌سازی شرط ساده با کدهای قبل و بعد آن .................................................................................... 103
شکل3-15. پیاده‌سازی شرط کامل ......................................................................................................................... 104
شکل3-16. پیاده‌سازی شرط‌ تو در تو .................................................................................................................... 104
شکل3-17. پیاده‌سازی یک شرط کامل در یک شرط ساده .................................................................................... 105
شکل3-18. پیاده‌سازی یک شرط کامل در یک شرط کامل دیگر ........................................................................... 105
شکل3-19. پیاده‌سازی حلقه ساده .......................................................................................................................... 106
شکل3-20. پیاده‌سازی یک حلقه ساده داخل حلقه‌ای دیگر ................................................................................... 106
شکل3-21. پیاده‌سازی یک حلقه داخل یک شرط کامل ........................................................................................ 106
شکل3-22. پیاده‌سازی یک شرط کامل داخل یک حلقه ساده ................................................................................ 107
شکل3-23. ماتریس درجه وابستگی‌ کد ................................................................................................................. 108
شکل3-24. شبه کد مقایسه محتوای دو خانه از آرایه‌های استقلال الگوریتم .......................................................... 108
شکل3-25. چهارچوب خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم ...................................................... 110
شکل3-26. شبه کد خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم ............................................................ 113
فصل چهارم
شکل۴-۱. مجموعه داده Halfring .......................................................................................................................... 118
شکل4-2. الگوریتم K-means ................................................................................................................................ 121
شکل4-3. الگوریتم FCM ...................................................................................................................................... 121
شکل4-4. الگوریتم Median K-Flats .................................................................................................................... 122
شکل4-5. الگوریتم Gaussian Mixture ................................................................................................................ 122
شکل4-6. الگوریتم خوشه‌بندی Subtractive ......................................................................................................... 122
شکل4-7. الگوریتم پیوندی منفرد با استفاده از معیار فاصله اقلیدسی ..................................................................... 123
شکل4-8. الگوریتم پیوندی منفرد با استفاده از معیار فاصله Hamming ................................................................ 123
شکل4-9. الگوریتم پیوندی منفرد با استفاده از معیار فاصله Cosine ..................................................................... 123
شکل4-10. الگوریتم پیوندی کامل با استفاده از معیار فاصله اقلیدسی ................................................................... 124
شکل4-1۱. الگوریتم پیوندی کامل با استفاده از معیار فاصله Hamming .............................................................. 124
شکل4-1۲. الگوریتم پیوندی کامل با استفاده از معیار فاصله Cosine .................................................................... 124
شکل4-1۳. الگوریتم پیوندی میانگین با استفاده از معیار فاصله اقلیدسی ............................................................... 124
شکل4-14. الگوریتم پیوندی میانگین با استفاده از معیار فاصله Hamming .......................................................... 125
شکل4-15. الگوریتم پیوندی میانگین با استفاده از معیار فاصله Cosine ............................................................... 125
شکل4-16. الگوریتم پیوندی بخشی با استفاده از معیار فاصله اقلیدسی ................................................................ 125
شکل4-17. الگوریتم پیوندی بخشی با استفاده از معیار فاصله Hamming ............................................................ 125


شکل4-18. الگوریتم پیوندی بخشی با استفاده از معیار فاصله Cosine ................................................................. 126
شکل4-19. طیفـی با استفاده از ماتریس شباهت نامتراکم ...................................................................................... 126
شکل4-20. طیفـی با استفاده از روش نیستروم با متعادل ساز .............................................................................. 127
شکل4-21. طیفـی با استفاده از روش نیستروم بدون متعادل ساز ......................................................................... 127
شکل4-22. نرم‌افزار تحلیل‌گر کد استقلال الگوریتم ............................................................................................... 128
شکل4-23. ماتریس AIDM ................................................................................................................................... 129
شکل4-24. میانگین دقت الگوریتم‌های خوشه‌بندی ............................................................................................... 131
شکل4-25. رابطه میان آستانه استقلال و زمان اجرای الگوریتم در روش پیشنهادی اول ........................................ 133
شکل4-26. رابطه میان آستانه پراکندگی و زمان اجرای الگوریتم در روش پیشنهادی اول ..................................... 133
شکل4-27. رابطه میان آستانه استقلال و دقت نتیجه نهایی در روش پیشنهادی اول .............................................. 134
شکل4-28. رابطه میان آستانه پراکندگی و دقت نتیجه نهایی در روش پیشنهادی اول ............................................ 134
شکل4-29. رابطه میان آستانه عدم تمرکز و دقت نتیجه نهایی در روش پیشنهادی اول ......................................... 135
شکل4-30. رابطه میان آستانه پراکندگی و زمان اجرای الگوریتم در روش پیشنهادی دوم ..................................... 135
شکل4-31. رابطه میان آستانه پراکندگی و دقت نتایج نهایی در روش پیشنهادی دوم ............................................ 136
شکل4-32. رابطه میان آستانه عدم تمرکز و دقت نتایج نهایی در روش پیشنهادی دوم ......................................... 137
شکل4-33. مقایسه زمان اجرای الگوریتم‌ ............................................................................................................... 138
فصل اول
مقدمه
center3187700
1. مقدمه1-1. خوشه‌بندیبه عنوان یکی از شاخه‌های وسیع و پرکاربرد هوش مصنوعی، یادگیری ماشین به تنظیم و اکتشاف شیوه‌ها و الگوریتم‌هایی می‌پردازد که بر اساس آن‌ها رایانه‌ها و سامانه‌های اطلاعاتی توانایی تعلم و یادگیری پیدا می‌کنند. طیف پژوهش‌هایی که در مورد یادگیری ماشینی صورت می‌گیرد گسترده ‌است. در سوی نظر‌ی آن پژوهش‌گران بر آن‌اند که روش‌های یادگیری تازه‌ای به وجود بیاورند و امکان‌پذیری و کیفیت یادگیری را برای روش‌هایشان مطالعه کنند و در سوی دیگر عده‌ای از پژوهش‌گران سعی می‌کنند روش‌های یادگیری ماشینی را بر مسائل تازه‌ای اعمال کنند. البته این طیف گسسته نیست و پژوهش‌های انجام‌شده دارای مؤلفه‌هایی از هر دو رو‌یکرد هستند. امروزه، داده‌کاوی به عنوان یک ابزار قوی برای تولید اطلاعات و دانش از داده‌های خام، در یادگیری ماشین شناخته‌شده و همچنان با سرعت در حال رشد و تکامل است. به طور کلی می‌توان تکنیک‌های داده‌کاوی را به دو دسته بانظارت و بدون نظارت تقسیم کرد [29, 46].
در روش بانظارت ما ورودی (داده یادگیری) و خروجی (کلاس داده) یک مجموعه داده را به الگوریتم هوشمند می‌دهیم تا آن الگوی بین ورودی و خروجی را تشخیص دهد در این روش خروجی کار ما مدلی است که می‌تواند برای ورودی‌های جدید خروجی درست را پیش‌بینی کند. روش‌های طبقه‌بندی و قوانین انجمنی از این جمله تکنیک‌ها می‌باشد. روش‌های با نظارت کاربرد فراوانی دارند اما مشکل عمده این روش‌ها این است که همواره باید داده‌ای برای یادگیری وجود داشته باشد که در آن به ازای ورودی مشخص خروجی درست آن مشخص شده باشد. حال آنکه اگر در زمینه‌ای خاص داده‌ای با این فرمت وجود نداشته باشد این روش‌ها قادر به حل این‌گونه مسائل نخواهند بود [29, 68]. در روش بدون نظارت برخلاف یادگیری بانظارت هدف ارتباط ورودی و خروجی نیست، بلکه تنها دسته‌بندی ورودی‌ها است. این نوع یادگیری بسیار مهم است چون خیلی از مسائل (همانند دنیای ربات‌ها) پر از ورودی‌هایی است که هیچ برچسبی (کلاس) به آن‌ها اختصاص داده نشده است اما به وضوح جزئی از یک دسته هستند [46, 68]. خوشه‌بندی شاخص‌ترین روش در داده‌کاوی جهت حل مسائل به صورت بدون ناظر است. ایده اصلی خوشه‌بندی اطلاعات، جدا کردن نمونه‌ها از یکدیگر و قرار دادن آن‌ها در گروه‌های شبیه به هم می‌باشد. به این معنی که نمونه‌های شبیه به هم باید در یک گروه قرار بگیرند و با نمونه‌های گروه‌های دیگر حداکثر متفاوت را دارا باشند [20, 26]. دلایل اصلی برای اهمیت خوشه‌بندی عبارت‌اند از:
اول، جمع‌آوری و برچسب‌گذاری یک مجموعه بزرگ از الگوهای نمونه می‌تواند بسیار پرکاربرد و باارزش باشد.
دوم، می‌توانیم از روش‌های خوشه‌بندی برای پیدا کردن و استخراج ویژگی‌ها و الگوهای جدید استفاده کنیم. این کار می‌تواند کمک به سزایی در کشف دانش ضمنی داده‌ها انجام دهد.
سوم، با خوشه‌بندی می‌توانیم یک دید و بینشی از طبیعت و ساختار داده به دست آوریم که این می‌تواند برای ما باارزش باشد.
چهارم، خوشه‌بندی می‌تواند منجر به کشف زیر رده‌های مجزا یا شباهت‌های بین الگوها ممکن شود که به طور چشمگیری در روش طراحی طبقه‌بندی قابل استفاده باشد.
1-2. خوشه‌بندی ترکیبیهر یک از الگوریتم‌های خوشه‌بندی، با توجه به اینکه بر روی جنبه‌های متفاوتی از داده‌ها تاکید می‌کند، داده‌ها را به صورت‌های متفاوتی خوشه‌بندی می‌نماید. به همین دلیل، نیازمند روش‌هایی هستیم که بتواند با استفاده از ترکیب این الگوریتم‌ها و گرفتن نقاط قوت هر یک، نتایج بهینه‌تری را تولید کند. در واقع هدف اصلی خوشه‌بندی ترکیبی جستجوی بهترین خوشه‌ها با استفاده از ترکیب نتایج الگوریتم‌های دیگر است [1, 8, 9, 54, 56]. به روشی از خوشه‌بندی ترکیبی که زیرمجموعه‌ی منتخب از نتایج اولیه برای ترکیب و ساخت نتایج نهایی استفاده می‌شود خوشه‌بندی ترکیبی مبتنی بر انتخاب زیرمجموعه نتایج اولیه می‌گویند. در این روش‌ها بر اساس معیاری توافقی مجموعه‌ای از مطلوب‌ترین نتایج اولیه را انتخاب کرده و فقط توسط آن‌ها نتیجه نهایی را ایجاد می‌کنیم [21]. معیارهای مختلفی جهت انتخاب مطلوب‌ترین روش پیشنهاد شده است که معیار اطلاعات متقابل نرمال شده، روش ماکزیموم و APMM برخی از آن‌ها می‌باشند [8, 9, 21, 67]. دو مرحله مهم در خوشه‌بندی ترکیبی عبارت‌اند از:
اول، الگوریتم‌های ابتدایی خوشه‌بندی که خوشه‌بندی اولیه را انجام می‌دهد.
دوم، جمع‌بندی نتایج این الگوریتم‌های اولیه (پایه) برای به دست آوردن نتیجه نهایی.
1-3. خرد جمعینظریه خرد جمعی که اولین بار توسط سورویکی در سال 2004 در کتابی با همان عنوان منتشر شد، استنباطی از مسائل مطرح‌شده توسط گالتون و کندورست می‌باشد، و نشان می‌دهد که قضاوت‌های جمعی و دموکراتیک از اعتبار بیشتری نسبت به آنچه که ما انتظار داشتیم برخوردار است، ما تأثیرات این ایده را در حل مسائل سیاسی، اجتماعی در طی سال‌های اخیر شاهد هستیم. در ادبیات خرد جمعی هر جامعه‌ای را خردمند نمی‌گویند. از دیدگاه سورویکی خردمند بودن جامعه در شرایط چهارگانه پراکندگی، استقلال، عدم تمرکز و روش ترکیب مناسب است [55].
1-4. خوشه‌بندی مبتنی بر انتخاب بر اساس نظریه خرد جمعیهدف از این تحقیق استفاده از نظریه خرد جمعی برای انتخاب زیرمجموعه‌ی مناسب در خوشه‌بندی ترکیبی می‌باشد. تعاریف سورویکی از خرد جمعی مطابق با مسائل اجتماعی است و در تعاریف آن عناصر سازنده تصمیمات رأی افراد می‌باشد. در این تحقیق ابتدا مبتنی بر تعاریف پایه سورویکی از خرد جمعی و ادبیات مطرح در خوشه‌بندی ترکیبی، تعریف پایه‌ای از ادبیات خرد جمعی در خوشه‌بندی ترکیبی ارائه می‌دهیم و بر اساس آن الگوریتم پیشنهادی خود را در جهت پیاده‌سازی خوشه‌بندی ترکیبی ارائه می‌دهیم [55]. شرایط چهارگانه خوشه‌بندی خردمند که متناسب با تعاریف سورویکی باز تعریف شده است به شرح زیر می‌باشد:
پراکندگی نتایج اولیه، هر الگوریتم خوشه‌بندی پایه باید به طور جداگانه و بدون واسطه به داده‌های مسئله دسترسی داشته و آن را تحلیل و خوشه‌بندی کند حتی اگر نتایج آن غلط باشد.
استقلال الگوریتم، روش تحلیل هر یک از خوشه‌بندی‌های پایه نباید تحت تأثیر روش‌های سایر خوشه‌بندی‌های پایه تعیین شود، این تأثیر می‌تواند در سطح نوع الگوریتم (گروه) یا پارامترهای اساسی یک الگوریتم خاص (افراد) باشد.
عدم تمرکز، ارتباط بین بخش‌های مختلف خوشه‌بندی خرد جمعی باید به گونه‌ای باشد تا بر روی عملکرد خوشه‌بندی پایه تأثیری ایجاد نکند تا از این طریق هر خوشه‌بندی پایه شانس این را داشته باشد تا با شخصی سازی و بر اساس دانش محلی خود بهترین نتیجه ممکن را آشکار سازد.
مکانیزم ترکیب مناسب، باید مکانیزمی وجود داشته باشد که بتوان توسط آن نتایج اولیه الگوریتم‌های پایه را با یکدیگر ترکیب کرده و به یک نتیجه نهایی (نظر جمعی) رسید.
در این تحقیق دو روش برای ترکیب خوشه‌بندی ترکیبی و خرد جمعی پیشنهاد شده است. با استفاده از تعاریف بالا الگوریتم روش اول مطرح خواهد شد که در آن، جهت رسیدن به نتیجه نهایی از آستانه‌گیری استفاده می‌شود. در این روش الگوریتم‌های خوشه‌بندی اولیه غیر هم نام کاملاً مستقل فرض خواهند شد و برای ارزیابی استقلال الگوریتم‌های هم نام نیاز به آستانه‌گیری می‌باشد. در روش دوم، سعی شده است تا دو بخش از روش اول بهبود یابد. از این روی جهت مدل‌سازی الگوریتم‌ها و ارزیابی استقلال آن‌ها نسبت به هم یک روش مبتنی بر گراف شبه کد ارائه می‌شود و میزان استقلال به دست آمده در این روش به عنوان وزنی برای ارزیابی پراکندگی در تشکیل جواب نهایی مورد استفاده قرار می‌گیرد. جهت ارزیابی، روش‌های پیشنهادی با روش‌های پایه، روش‌ ترکیب کامل و چند روش معروف ترکیب مبتنی بر انتخاب مقایسه خواهد شد. از این روی از چهارده داده استاندارد و یا مصنوعی که عموماً از سایت UCI [76] جمع‌آوری شده‌اند استفاده شده است. در انتخاب این داده‌ها سعی شده، داده‌هایی با مقیاس‌ کوچک، متوسط و بزرگ انتخاب شوند تا کارایی روش بدون در نظر گرفتن مقیاس داده ارزیابی شود. همچنین جهت اطمینان از صحت نتایج تمامی آزمایش‌های تجربی گزارش‌شده حداقل ده بار تکرار شده است.
1-4-1- فرضیات تحقیقاین تحقیق بر اساس فرضیات زیر اقدام به ارائه روشی جدید در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر اساس نظریه خرد جمعی می‌کند.
۱ ) در این تحقیق تمامی آستانه‌گیری‌ها بر اساس میزان صحت نتایج نهایی و مدت زمان اجرای الگوریتم به صورت تجربی انتخاب می‌شوند.
۲ ) در این تحقیق جهت ارزیابی عملکرد یک الگوریتم، نتایج اجرای آن را بر روی‌داده‌های استاندارد UCI در محیطی با شرایط و پارامترهای مشابه نسبت به سایر الگوریتم‌ها ارزیابی می‌کنیم که این داده‌ها الزاماً حجیم یا خیلی کوچک نیستند.
۳ ) جهت اطمینان از صحت نتایج آزمایش‌ها ارائه‌شده در این تحقیق، حداقل اجرای هر الگوریتم بر روی هر داده ده بار تکرار شده و نتیجه‌ی نهایی میانگین نتایج به دست آمده می‌باشد.
4 ) از آنجایی که روش مطرح‌شده در این تحقیق یک روش مکاشفه‌ای است سعی خواهد شد بیشتر با روش‌های مکاشفه‌ای مطرح در خوشه‌بندی ترکیبی مقایسه و نتایج آن مورد بررسی قرار گیرد.
در این فصل اهداف، مفاهیم و چالش‌های این تحقیق به صورت خلاصه ارائه شد. در ادامه این تحقیق، در فصل دوم، الگوریتم‌های خوشه‌بندی پایه و روش‌های خوشه‌بندی‌ ترکیبی مورد بررسی قرار می‌گیرد. همچنین به مرور روش‌های انتخاب خوشه و یا افراز در خوشه‌بندی ترکیبی مبتنی بر انتخاب خواهیم پرداخت. در فصل سوم، نظریه خرد جمعی و دو روش پیشنهادی خوشه‌بندی خردمند ارائه می‌شود. در فصل چهارم، به ارائه نتایج آزمایش‌های تجربی این تحقیق و ارزیابی آن‌ها می‌پردازیم و در فصل پنجم، به ارائه‌ی نتایج و کار‌های آتی خواهیم پرداخت.

فصل دوم
مروری بر ادبیات تحقیق
center2132965
2. مروری بر ادبیات تحقیق2-1. مقدمهدر این بخش، کارهای انجام‌شده در خوشه‌بندی و خوشه‌بندی ترکیبی را مورد مطالعه قرار می‌دهیم. ابتدا چند الگوریتم‌ پایه خوشه‌بندی معروف را معرفی خواهیم کرد. سپس چند روش کاربردی جهت ارزیابی خوشه، خوشه‌بندی و افرازبندی را مورد مطالعه قرار می‌دهیم. در ادامه به بررسی ادبیات خوشه‌بندی ترکیبی خواهیم پرداخت و روش‌های ترکیب متداول را بررسی خواهیم کرد. از روش‌های خوشه‌بندی ترکیبی، روش ترکیب کامل و چند روش معروف مبتنی بر انتخاب را به صورت مفصل شرح خواهیم داد.
2-2. خوشه‌بندیدر این بخش ابتدا انواع الگوریتم‌های خوشه‌بندی پایه را معرفی می‌کنیم و سپس برخی از آن‌ها را مورد مطالعه قرار می‌دهیم سپس برای ارزیابی نتایج به دست آمده چند متریک معرفی خواهیم کرد.
2-2-1. الگوریتم‌های خوشه‌بندی پایهبه طور کلی، الگوریتم‌های خوشه‌بندی را می‌توان به دو دسته کلی تقسیم کرد:
1- الگوریتم‌های سلسله مراتبی
2- الگوریتم‌های افرازبندی
الگوریتم‌های سلسله مراتبی، یک روال برای تبدیل یک ماتریس مجاورت به یک دنباله از افرازهای تو در تو، به صورت یک درخت است. در این روش‌ها، مستقیماً با داده‌ها سروکار داریم و از روابط بین آن‌ها برای به دست آوردن خوشه‌ها استفاده می‌کنیم. یکی از ویژگی‌های این روش قابلیت تعیین تعداد خوشه‌ها به صورت بهینه می‌باشد. در نقطه مقابل الگوریتم‌های سلسله مراتبی، الگوریتم‌های افرازبندی قرار دارند. هدف این الگوریتم‌ها، تقسیم داده‌ها در خوشه‌ها، به گونه‌ای است که داده‌های درون یک خوشه بیش‌ترین شباهت را به همدیگر داشته باشند؛ و درعین‌حال، بیش‌ترین فاصله و اختلاف را با داده‌های خوشه‌های دیگر داشته باشند. در این فصل تعدادی از متداول‌ترین الگوریتم‌های خوشه‌بندی، در دو دسته سلسله مراتبی و افرازبندی، مورد بررسی قرار می‌گیرند. از روش سلسله‌ مراتبی چهار الگوریتم‌ از سری الگوریتم‌های پیوندی را مورد بررسی قرار می‌دهیم. و از الگوریتم‌های افرازبندی K-means، FCM و الگوریتم طیفی را مورد بررسی خواهیم داد.
2-2-1-1. الگوریتم‌های سلسله مراتبیهمان‌گونه که در شکل 2-1 مشاهده می‌شود، روال الگوریتم‌های خوشه‌بندی سلسله مراتبی را می‌تواند به صورت یک دندوگرام نمایش داد. این نوع نمایش تصویری از خوشه‌بندی سلسله مراتبی، برای انسان، بیشتر از یک لیست از نمادها قابل‌درک است. در واقع دندوگرام، یک نوع خاص از ساختار درخت است که یک تصویر قابل‌فهم از خوشه‌بندی سلسله مراتبی را ارائه می‌کند. هر دندوگرام شامل چند لایه از گره‌هاست، به طوری که هر لایه یک خوشه را نمایش می‌دهد. خطوط متصل‌کننده گره‌ها، بیانگر خوشه‌هایی هستند که به صورت آشیانه‌ای داخل یکدیگر قرار دارند. برش افقی یک دندوگرام، یک خوشه‌بندی را تولید می‌کند [33]. شکل 2-1 یک مثال ساده از خوشه‌بندی و دندوگرام مربوطه را نشان می‌دهد.

شکل 2-1. یک خوشه‌بندی سلسله مراتبی و درخت متناظر
اگر الگوریتم‌های خوشه‌بندی سلسله مراتبی، دندوگرام را به صورت پایین به بالا بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تراکمی نامیده می‌شوند. همچنین، اگر آن‌ها دندوگرام را به صورت بالا به پایین بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تقسیم‌کننده نامیده می‌شوند [26]. مهم‌ترین روش‌های خوشه‌بندی سلسله مراتبی الگوریتم‌های سری پیوندی می‌باشد که در این بخش تعدادی از کاراترین آن‌ها مورد بررسی قرار خواهند گرفت که عبارت‌اند از:
الگوریتم پیوندی منفرد
الگوریتم پیوندی کامل
الگوریتم پیوندی میانگین
الگوریتم پیوندی بخشی
2-2-1-1-1. تعاریف و نماد‌ها
شکل 2-2. ماتریس مجاورت
قبل از معرفی این الگوریتم‌ها، در ابتدا نمادها و نحوه نمایش مسئله نمایش داده خواهد شد. فرض کنید که یک ماتریس مجاورت متقارن داریم. وارده در هر سمت قطر اصلی قرار دارد که شامل یک جای گشت اعداد صحیح بین 1 تا است. ما مجاورت‌ها را عدم شباهت در نظر می‌گیریم. به این معنی است که اشیاء 1 و 3 بیشتر از اشیاء 1 و 2 به هم شبیه‌اند. یک مثال از ماتریس مجاورت معمول برای است که در شکل 2-2 نشان داده شده است. یک گراف آستانه، یک گراف غیر جهت‌دار و غیر وزن‌دار، روی گره، بدون حلقه بازگشت به خود یا چند لبه است. هر نود یک شیء را نمایش می‌دهد. یک گراف آستانه برای هر سطح عدم شباهت به این صورت تعریف می‌شود: اگر عدم شباهت اشیاء و از حد آستانه کوچک‌تر باشد، با واردکردن یک لبه بین نودهای ویک گراف آستانه تعریف می‌کنیم.
(2-1)if and only if
شکل 2-3 یک رابطه دودویی به دست آمده از ماتریس مربوط به شکل 2-2 را برای مقدار آستانه 5 نشان می‌دهد. نماد "*" در موقعیت ماتریس، نشان می‌دهد که جفت متعلق به رابطه دودویی می‌باشد. شکل 2-4، گراف‌های آستانه برای ماتریس را نمایش می‌دهد.

شکل 2-3. رابطه دودویی و گراف آستانه برای مقدار آستانه 5.

شکل 2-4. گراف‌های آستانه برای ماتریس
2-2-1-1-2. الگوریتم پیوندی منفرداین الگوریتم روش کمینه و روش نزدیک‌ترین همسایه نیز نامیده می‌شود [26]. اگر و خوشه‌ها باشند، در روش پیوندی منفرد، فاصله آن‌ها برابر خواهد بود با:
(2-2)
که نشان‌دهنده فاصله (عدم شباهت) بین نقاط a و b در ماتریس مجاورت است. شکل 2-5 این الگوریتم را نمایش می‌دهد. شکل 2-6 دندوگرام حاصل از روش پیوندی منفرد را برای ماتریس ، را نشان می‌دهد.
Step 1. Begin with the disjoint clustering implied by threshold graph, which contains no edges and which places every object in a unique cluster, as the current clustering. Set.
Step 2. From threshold graph.
If the number of comonents (maximally connected subgraphs) in, is less than the number of clusters in the current clustering, redefiene the current clustering by naming each component of as a cluster.
Step 3. If consists of a single connected graph, stop. Else, setand go to step 2.
شکل 2-5. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی منفرد

شکل 2-6. دندوگرام پیوندی منفرد برای ماتریس
2-2-1-1-3. الگوریتم پیوندی کاملاین الگوریتم روش بیشینه یا روش دورترین همسایه نیز نامیده می‌شود. الگوریتم پیوندی کامل می‌گوید که وقتی دو خوشه و شبیه به هم هستند که بیشینه روی تمام ها در و کوچک باشد. به عبارت دیگر، در این الگوریتم، برای یکی کردن دو خوشه، همه جفت‌ها در دو خوشه باید شبیه به هم باشند [26]. اگر و خوشه‌ها باشند، در روش پیوندی کامل، فاصله آن‌ها برابر خواهد بود با:
(2-3)
که نشان‌دهنده فاصله(عدم شباهت) بین نقاط a و در ماتریس مجاورت است. شکل 2-7 این الگوریتم و شکل 2-8 دندوگرام حاصل از این روش را برای ماتریس ، را نشان می‌دهد.
Step 1. Begin with the disjoint clustering implied by threshold graph, which contains no edges and which places every object in a unique cluster, as the current clustering. Set.
Step 2. From threshold graph.
If two of the current clusters from a clique (maximally complete sub graph) in, redefine the current clustering by merging these two clusters into a single cluster.
Step 3. If, so that is the complete graph on the nodes, stop. Else, set and go to step 2.
شکل 2-7. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی کامل

شکل 2-8. دندوگرام پیوندی کامل برای ماتریس
2-2-1-1-4. الگوریتم پیوندی میانگینالگوریتم پیوندی منفرد اجازه می‌دهد تا خوشه‌ها به صورت دراز و نازک رشد کنند. این در شرایطی است که الگوریتم پیوندی کامل خوشه‌های فشرده‌تری تولید می‌کند. هر دو الگوریتم مستعد خطا با داده‌های خارج از محدوده هستند. الگوریتم خوشه‌بندی پیوندی میانگین، یک تعادلی بین مقادیر حدی الگوریتم‌های پیوندی منفرد و کامل است. الگوریتم پیوندی میانگین همچنین، روش جفت-گروه بدون وزن با استفاده از میانگین حسابی نامیده می‌شود. این الگوریتم، یکی از پرکاربردترین الگوریتم‌های خوشه‌بندی سلسله مراتبی می‌باشد [26]. اگر یک خوشه با تعداد تا عضو، و یک خوشه دیگر با تعداد تا عضو باشند، در روش پیوندی میانگین، فاصله آن‌ها برابر خواهد بود با:
(2-4)
که نشان‌دهنده فاصله(عدم شباهت) بین نقاط a و در ماتریس مجاورت است.
2-2-1-1-5. الگوریتم پیوندی بخشیروش پیوندی بخشی که از مربع مجموع خطا‌های (SSE) خوشه‌های یک افراز برای ارزیابی استفاده می‌کند، یکی دیگر از روش‌های سلسله مراتبی می‌باشد [60]. اگر یک خوشه با تعداد تا عضو، و یک خوشه دیگر با تعداد تا عضو باشند و نماد به معنای فاصله اقلیدسی و و مراکز خوشه‌های و باشد آنگاه در روش پیوندی بخشی، فاصله آن‌ها برابر خواهد بود با:
(2-5)
2-2-1-2. الگوریتم‌های افرازبندییک خاصیت مهم روش‌های خوشه‌بندی سلسله مراتبی، قابلیت نمایش دندوگرام است که تحلیل‌گر را قادر می‌سازد تا ببیند که چگونه اشیاء در سطوح متوالی مجاورت، در خوشه‌ها به هم پیوند می‌خورند یا تفکیک می‌شوند. همان طور که اشاره شد، هدف الگوریتم‌های افرازبندی، تقسیم داده‌ها در خوشه‌ها، به گونه‌ای است که داده‌های درون یک خوشه بیش‌ترین شباهت را به همدیگر داشته باشند؛ و درعین‌حال، بیش‌ترین فاصله و اختلاف را با داده‌های خوشه‌های دیگر داشته باشند. آن‌ها یک افراز منفرد از داده را تولید می‌کنند و سعی می‌کنند تا گروه‌های طبیعی حاضر در داده را کشف کنند. هر دو رویکرد خوشه‌بندی، دامنه‌های مناسب کاربرد خودشان را دارند. معمولاً روش‌های خوشه‌بندی سلسله مراتبی، نیاز به ماتریس مجاورت بین اشیاء دارند؛ درحالی‌که روش‌های افرازبندی، به داده‌ها در قالب ماتریس الگو نیاز دارند. نمایش رسمی مسئله خوشه‌بندی افرازبندی می‌تواند به صورت زیر باشد:
تعیین یک افراز از الگوها در گروه، یا خوشه، با داشتن الگو در یک فضای d-بعدی؛ به طوری که الگوها در یک خوشه بیش‌ترین شباهت را به هم داشته و با الگوهای خوشه‌های دیگر بیش‌ترین، تفاوت را داشته باشند. تعداد خوشه‌ها،، ممکن است که از قبل مشخص‌شده نباشد، اما در بسیاری از الگوریتم‌های خوشه‌بندی افرازبندی، تعداد خوشه‌ها باید از قبل معلوم باشند. در ادامه برخی از معروف‌ترین و پرکاربردترین الگوریتم‌های افرازبندی مورد بررسی قرار خواهند گرفت.
2-2-1-2-1. الگوریتم K-meansدر الگوریتم مراکز خوشه‌ها بلافاصله بعد از اینکه یک نمونه به یک خوشه می‌پیوندد محاسبه می‌شوند. به طور معمول بیشتر روش‌های خوشه‌بندی ترکیبی از الگوریتم جهت خوشه‌بندی اولیه خود استفاده می‌کنند [37, 47, 57]. اما مطالعات اخیر نشان داده‌اند که با توجه به رفتار هر مجموعه داده، گاهی اوقات یک روش خوشه‌بندی خاص پیدا می‌شود که دقت بهتری از برای بعضی از مجموعه داده‌ها می‌دهد [1, 54]. اما الگوریتم به دلیل سادگی و توانایی مناسب در خوشه‌بندی همواره به عنوان انتخاب اول مطالعات خوشه‌بندی ترکیبی مورد مطالعه قرار گرفته است. در شکل 2-10 شبه کد الگوریتم را مشاهده می‌کنید:
1. Place K points into the space represented by the objects that are being clustered.
These points represent initial group centroids.
2. Assign each object to the group that has the closest centroid.
3. When all objects have been assigned, recalculate the positions of the K centroids.
4. Repeat Steps 2 and 3 until the centroids no longer move. This produces a separation
of the objects into groups from which the metric to be minimized can be calculated
شکل 2-9. الگوریتم خوشه‌بندی افرازبندی
مقادیر مراکز اولیه‌ی‌ متفاوت برای الگوریتم می‌تواند منجر به خوشه‌بندی‌های مختلفی شود. به خاطر اینکه این الگوریتم مبتنی بر مربع خطا است، می‌تواند به کمینه محلی همگرا شود، مخصوصاً برای خوشه‌هایی که به طور خیلی خوبی از هم تفکیک نمی‌شوند، این امر صادق است. نشان داده شده است که هیچ تضمینی برای همگرایی یک الگوریتم تکراری به یک بهینه سراسری نیست [33]. به طور خلاصه می‌توان ویژگی‌های الگوریتم را به صورت زیر برشمرد:
1- بر اساس فاصله اقلیدسی تمامی ویژگی‌ها می‌باشد.
2- منجر به تولید خوشه‌هایی به صورت دایره، کره و یا ابر کره می‌شود.
3- نسبت به روش‌های دیگر خوشه‌بندی، ساده و سریع است.
4- همگرایی آن به یک بهینه محلی اثبات شده است، اما تضمینی برای همگرایی به بهینه سراسری وجود ندارد.
5- نسبت به مقداردهی اولیه مراکز خوشه‌ها خیلی حساس است.
2-2-1-2-2. الگوریتم FCMالگوریتم FCM اولین بار توسط دون [13] ارائه شد. سپس توسط بزدک [66] بهبود یافت. این متد دیدگاه جدیدی را در خوشه‌بندی بر اساس منطق فازی [62] ارائه می‌دهد. در این دیدگاه جدید، به جای اینکه داده‌ها در یک خوشه عضو باشند، در تمامی خوشه‌ها با یک ضریب عضویت که بین صفر و یک است، عضو هستند و ما در این نوع خوشه‌بندی، دنبال این ضرایب هستیم. در روش‌های معمول در جایی که ما داده داشته باشیم، جواب نهایی ماتریس خواهد بود که هر خانه شامل برچسب خوشه‌ی داده‌ی نظیر آن می‌باشد. ولی در این روش در صورت داشتن خوشه، جواب نهایی یک ماتریس خواهد بود که در آن هر ردیف شامل ضرایب عضویت داده‌ی نظیر به آن خوشه است. بدیهی است که جمع افقی هر ردیف (ضرایب عضویت یک داده خاص) برابر با یک خواهد بود. یک روش معمول جهت رسیدن به جواب‌هایی غیر فازی بر اساس نتایج نهایی الگوریتم فازی، برچسب‌زنی داده بر اساس آن ضریبی که مقدار حداکثر را در این داده دارد، می‌باشد. رابطه 2-6 معادله پایه در روش فازی است: [66]
(2-6) ,
در رابطه 2-6 متغیرm یک عدد حقیقی بزرگ‌تر از یک و درجه عضویت داده در خوشه j-ام می‌باشد، که خود ، i-امین داده d-بُعدی از داده‌ی مورد مطالعه می‌باشد و مرکز d-بعدی خوشه j-ام‌ است و هر روش معمول جهت اندازه‌گیری شباهت میان داده و مرکز خوشه می‌باشد. در روش خوشه‌بندی فازی مراکز خوشه () و درجه عضویت () با تکرار مکرر به ترتیب بر اساس رابطه‌های 2-7 و 2-8 به‌روزرسانی می‌شوند، تا زمانی که شرط توقف درست در آید. در این شرط مقدار یک مقدار توافقی بسیار کوچک‌تر از یک می‌باشد که مطابق با نوع داده و دقت خوشه‌بندی قابل جایگذاری خواهد بود. بدیهی است که هر چقدر این مقدار به سمت صفر میل کند درجه عضویت دقیق‌تر و مقدار زمان اجرا بیشتر خواهد بود [66].
(2-7)
(2-8)
مراحل اجرای الگوریتم در شبه کد شکل 2-11 شرح داده شده است:
1.Initialize matrix,
2.At k-step: calculate the centers vectors with

3.Update ,

4. If then STOP; otherwice returen to step 2.
شکل 2-10. الگوریتم فازی خوشه‌بندی
2-2-1-2-3. الگوریتم طیفیروش خوشه‌بندی طیفی که بر اساس مفهوم گراف طیفی [11] مطرح شده است، از ماتریس شباهت برای کاهش بعد داده‌ها در خوشه‌بندی استفاده می‌کند. در این روش یک گراف وزن‌دار بدون جهت به نحوی تولید می‌شود که رئوس گراف نشان‌دهنده‌ی مجموعه نقاط و هر یال وزن‌دار نشان‌دهنده‌ی میزان شباهت جفت داده‌های متناظر باشد. بر خلاف روش‌های کلاسیک، این روش، روی‌ داده‌ای پراکنده‌ در فضایی با شکل‌ هندسی غیر محدب، نتایج مطلوبی تولید می‌کند [63]. کاربرد این روش در محاسبات موازی [69, 70]، تنظیم بار [15]، طراحی VLSI [28]، طبقه‌بندی تصاویر [35] و بیوانفورماتیک [31, 59] می‌باشد.
در خوشه‌بندی طیفی از بردارهای ویژگی در ماتریس شباهت برای افراز مجموعه‌ داده استفاده می‌شود. در اغلب این روش‌ها، مقدار ویژه اولویت بردارها را تعیین می‌کند. ولی این نحوه‌ی انتخاب، انتخاب بهترین بردارها را تضمین نمی‌دهد. در اولین تحقیقی که در این زمینه توسط ژیانگ و گنگ [61] انجام شد، مسئله‌ی انتخاب بردارهای ویژگی مناسب جهت بهبود نتایج خوشه‌بندی پیشنهاد گردید. در روش پیشنهادی آن‌ها شایستگی هر یک از بردارهای با استفاده از تابع چگالی احتمال هر بردار تخمین زده می‌شود. وزنی به بردارهایی که امتیاز لازم را به دست آورندگ، اختصاص یافته و برای خوشه‌بندی از آن‌ها استفاده می‌شود. در کاری دیگر که توسط ژائو [64] انجام شده است، هر یک از بردارهای ویژه به ترتیب حذف می‌شوند و مقدار آنتروپی مجموعه بردارهای باقی‌مانده محاسبه می‌شود. برداری که حذف آن منجر به افزایش آنتروپی و ایجاد بی‌نظمی بیشتر در مجموعه داده شود، اهمیت بیشتری داشته و در رتبه بالاتری قرار می‌گیرد. سپس زیرمجموعه‌ای از مناسب‌ترین بردارها برای خوشه‌بندی مورد استفاده قرار می‌گیرند. الگوریتم خوشه‌بندی طیفی دارای متدهای متفاوتی جهت پیاده‌سازی است، که الگوریتم‌های برش نرمال، NJW، SLH وPF از آن جمله می‌باشد. در تمامی این روش‌ها، بخش اول، یعنی تولید گراف، مشترک می‌باشد. ما در ادامه ابتدا به بررسی بخش مشترک این روش‌ها می‌پردازیم. سپس به تشریح دو روش پر کاربرد برش نرمال و NJW می‌پردازیم.
در الگوریتم خوشه‌بندی طیفی، افراز داده‌ها بر اساس تجزیه‌ی ماتریس شباهت و به دست آوردن بردارها و مقادیر ویژه‌ی آن صورت می‌گیرد. مجموعه‌ی با داده‌یبعدی را در نظر بگیرید، می‌توان برای این مجموعه گراف وزن‌دار و بدون جهت را ساخت به صورتی که رئوس گراف نشان‌دهنده داده و یال‌ها که ماتریس شباهت را تشکیل می‌دهند بیانگر میزان شباهت بین هر جفت داده متناظر باشند. ماتریس شباهت به صورت رابطه 2-9 تعریف می‌شود:
(2-9)
تابع میزان شباهت بین دو داده را اندازه می‌گیرد. می‌تواند یک تابع گوسی به صورت باشد. که در آن فاصله‌ی بین دو نمونه را نشان می‌دهد و پارامتر مقیاس سرعت کاهش تابع با افزایش فاصله بین دو نمونه را مشخص می‌کند. در ادامه به بررسی دو الگوریتم خوشه‌بندی طیفی برش نرمال و NJW می‌پردازیم.
2-2-1-2-3-1. الگوریتم برش نرمالالگوریتم برش نرمال توسط شی و ملیک [35] برای قطعه‌بندی تصاویر ارائه شده است. در این روش، میزان تفاوت بین خوشه‌های مختلف و شباهت بین اعضا یک خوشه، بر اساس فاصله‌ی داده‌ها محاسبه می‌کند. رابطه 2-10 اشاره به مفهوم شباهت داده دارد که با استفاده از آن اقدام به ساخت گراف وزن‌دار می‌نماییم:
(2-10)
موقعیت i-امین داده (پیکسل در تصاویر) و بردار ویژگی از صفات داده (مانند روشنایی در تصاویر) می‌باشد. با کمک حد آستانه می‌توان میزان تنکی ماتریس شباهت را با توجه به تعداد اثرگذار داده‌های همسایه تعیین کرد. گام‌های این الگوریتم به صورت زیر می‌باشد:
محاسبه ماتریس درجه.
محاسبه ماتریس لاپلاسین.
محاسبه دومین بردار ویژگی متناظر با دومین کوچک‌ترین مقدار ویژه.
استفاده از برای خوشه‌بندی (قطعه‌بندی در تصاویر) گراف.
روش برش نرمال بیشتر در قطعه‌بندی تصاویر کاربرد دارد و معمولاً در خوشه‌بندی داده از سایر الگوریتم‌های خوشه‌بندی طیفی استفاده می‌کنند.
2-2-1-2-3-2. الگوریتم NJWایده الگوریتم استفاده از اولین بردار ویژه متناظر با بزرگ‌ترین مقدار ویژه ماتریس لاپلاسین است. مراحل این الگوریتم به صورت زیر می‌باشد: [51]
ساخت ماتریس شباهت با استفاده از رابطه 2-9.
محاسبه ماتریس درجه، و ماتریس لاپلاسین.
به دست آوردن اولین بردار ویژه متناظر با اولین بزرگ‌ترین مقدار ماتریسو تشکیل ماتریس ستونی.
نرمال سازی مجدد و تشکیل به طوری که همه سطرهای آن طول واحد داشته باشد.
خوشه‌بندی مجموعه داده بازنمایی شده با استفاده از.

2-2-1-2-4. الگوریتم خوشه‌بندی کاهشیالگوریتم خوشه‌بندی کاهشی یکی از سریع‌ترین الگوریتم‌های تک گذر، برای تخمین تعداد خوشه و مراکز آن‌ها در مجموعه‌ی داده می‌باشد. این مفهوم یعنی به جای تحت تأثیر قرار گرفتن محاسبات از ابعاد مسئله، متناسب با اندازه مسئله آن را انجام دهیم. با این وجود، مراکز واقعی خوشه الزاماً یکی از نقاط داده موجود در مجموعه داده نیست ولی در بیشتر موارد این انتخاب تخمین خوبی است که به صورت ویژه از این رویکرد در محاسبات کاهشی استفاده می‌شود. اگر هر نقطه از مجموعه داده به عنوان گزینه‌ای برای مرکز خوشه در نظر گرفته شود، معیار تراکم هر نقطه به صورت زیر تعریف می‌شود [79].
(2-11)
در رابطه بالا یک ثابت مثبت است، که نشان‌دهنده‌ی شعاع همسایگی (سایر نقاط داده که نزدیک‌ترین نقاط به این داده خاص هستند) می‌باشد، و نشان‌دهنده‌ی سایر داده‌های مجموعه، و نشان‌دهنده‌ی تعداد این داده‌ها است. از این روی، داده‌ای دارای بیش‌ترین مقدار تراکم می‌باشد که بیش‌ترین نقاط داده در همسایگی آن است. اولین مرکز خوشه بر اساس بزرگ‌ترین مقدار تراکم انتخاب می‌شود. بعد از این انتخاب میزان تراکم هر یک از نقاط داده به صورت زیر به‌روز می‌شود [79].
(2-12)
در رابطه بالا ثابت مثبت همسایگی را تعریف می‌کند که میزان کاهش تراکم قابل اندازه‌گیری را نشان می‌دهد. از آنجایی که نقاط داده در نزدیکی مرکز خوشه اول به طور قابل‌توجهی مقادیر چگالی را کاهش می‌دهند بعد از به‌روز کردن مقادیر تابع چگالی توسط رابطه بالا مرکز خوشه بعدی بر اساس داده‌ای که بزرگ‌ترین مقدار چگالی را دارد انتخاب می‌شود. این فرآیند آن قدر تکرار می‌شود تا به تعداد کافی مرکز خوشه ایجاد شود. پس از اتمام این فرآیند می‌توان توسط الگوریتم که مراکز داده در آن توسط فرآیند بالا به صورت دستی داده شده است (نه به صورت تصادفی)، داده‌ها را خوشه‌بندی کرد. شبه کد شکل زیر روند فرآیند بالا را نشان می‌دهد که در آن ابتدا مقادیر ثابت‌ها () و مجموعه داده به عنوان ورودی گرفته می‌شود و پس از ساخت مراکز داده مطابق با تعاریف بالا، این مراکز برای خوشه‌بندی در الگوریتم استفاده می‌شود [79].
Inputs Dataset, Constants
Output Clusters
Steps
1. Initialize constants and density values
2. Make a new cluster center.
3. Update density values
4. If the sufficient number of clusters are not obtained, go to 2.
3. Clustering the dataset by k-means, using fix centers.
شکل 2-11. خوشه‌بندی کاهشی
2-2-1-2-5. الگوریتم خوشه‌بندی Median K-Flatالگوریتم Median K-Flat یا به اختصار MKF مجموعه داده‌یرا به K خوشه‌ی افراز می‌کند که هر خوشه یک شبه فضای d-بُعدی تقریباً خطی می‌باشد. پارامتر‌ با فرض ماتریسی با ابعاد می‌باشد، که هر یک از خانه‌های آن تخمین شبه فضای خطی متعامد می‌باشد. قابل به ذکر است که می‌باشد. در این جا تخمین شبه فضای خوشه‌های را نام‌گذاری می‌کنیم. مطابق تعاریف بالا تابع انرژی برای افرازهای ‌ بر اساس شبه فضای به شکل زیر تعریف می‌شود [77].
(2-13)
این الگوریتم سعی می‌کند تا مجموعه داده را به خوشه‌های ‌تبدیل کند به نحوی که تابع انرژی کمینه باشد. تا وقتی که سطوح تخت اساسی به شکل شبه فضای خطی هستند ما می‌توانیم به صورت فرضی المان‌های X را در یک حوضه واحد نرمال کنیم به طوری که برای و تابع انرژی را به شکل زیر بیان کنیم: [77]
(2-14)
این الگوریتم برای کمینه‌سازی تابع انرژی الگوریتمMKF از روش کاهش گرادیان تصادفی استفاده می‌کند. مشتق تابع انرژی بر اساس ماتریس به شرح زیر است:
(2-15)
این الگوریتم نیاز به تطبیق بر اساس مؤلفه‌ی متعامد مشتق دارد. بخشی از مشتق که با شبه فضای موازی است به شرح زیر می‌باشد.
(2-16)
از این روی مؤلفه متعامد برابر است با رابطه 2-17 می‌باشد.
(2-17)
در رابطه بالا برابر با رابطه 2-18 است.
(2-18)
با در نظر گرفتن محاسبات بالا، الگوریتم MKF تصمیم می‌گیرد که داده تصادفی از مجموعه داده، عضو کدام باشد، و از این طریق شروع به چیدن داده‌ها می‌کند. آن گاه، الگوریتم تابع را به‌روز کند که در آن (مرحله زمانی) پارامتری است که توسط کاربر تعیین می‌شود. این فرآیند آن قدر تکرار می‌شود تا ضابطه همگرایی دیده شود. آنگاه هر نقطه از مجموعه داده به نزدیک‌ترین شبه فضای که تعیین‌کننده خوشه‌هاست اختصاص داده می‌شود. شبه کد زیر فرآیند الگوریتم MKF را نشان می‌دهد [77].
Input:
: Data, normalized onto the unit sphere, d: dimension of subspaces K: number of subspaces, the initialized subspaces. : step parameter.
Output: A partition of X into K disjoint clusters
Steps:
1. Pick a random point in X
2. Find its closest subspace , where
3. Compute by
4. Update
5. Orthogonalize
6. Repeat steps 1-5 until convergence
7. Assign each xi to the nearest subspace
شکل 2-12. شبه‌کد الگوریتم MKF [77]
2-2-1-2-6. الگوریتم خوشه‌بندی مخلوط گوسییک مخلوط گوسی یا همان را می‌توان ترکیب محدبی از چگالی‌های گوسی دانست. یک چگالی گوسی در فضای d-بُعدی به ازای میانگین، توسط ماتریس هم‌وردایی با ابعاد به صورت زیر تعریف می‌شود: [83]
(2-19)
در رابطه بالا پارامتر‌های و را تعریف می‌کند. از این روی مؤلفه به صورت زیر تعریف می‌شود:
(2-20)
در رابطه (2-20) پارامتر وزن مخلوط کردن و مؤلفه مخلوط می‌باشد. از آنجا که در مقایسه با تخمین چگالی غیر پارامتری، تعداد کمتری از توابع چگالی در تخمین چگالی مخلوط باید ارزیابی شود، از این روی ارزیابی چگالی کارآمدتر خواهد بود. علاوه بر آن، استفاده از اجرای محدودیت هموار کردن بر روی برخی از مؤلفه‌های مخلوط در نتیجه‌ی چگالی به ما اجازه می‌دهد تا چگالی مستحکم‌تری را تخمین بزنیم. الگوریتم حداکثر-انتظار یا همان به ما اجازه به‌روز کردن پارامتر‌های مؤلفه‌ی مخلوط را مطابق با مجموعه داده به ازای هر می‌دهد، به طوری که احتمال هرگز کوچک‌تر از مخلوط جدید نشود. به‌روز کردن الگوریتم می‌تواند در یک فرآیند تکراری برای تمامی مؤلفه‌های مطابق با رابطه‌های زیر انجام شود: [83]
(2-21)
(2-22)
(2-23)
(2-24)
در این تحقیق از روش پیشنهادی بومن و همکاران برای پیاده‌سازی الگوریتم مخلوط گوسی استفاده شده است. از آنجایی که روش پیاده‌سازی و توضیحات مربوط به الگوریتم مخلوط گوسی در روش ترکیب مبتنی بر مخلوط استفاده می‌شود از این روی در بخش روش‌های ترکیب نتایج با تابع توافقی آن را بررسی خواهیم کرد.
2-2-2. معیارهای ارزیابیدر یادگیری با ناظر ارزیابی راحت تر از یادگیری بدون ناظر است. برای مثال آن چیز که ما در رده‌بندی باید ارزیابی کنیم مدلی است که ما توسط داده‌های یادگیری به الگوریتم هوش مصنوعی آموزش داده‌ایم. در روش‌های با ناظر ورودی و خروجی داده معلوم است و ما بخشی از کل داده را برای آزمون جدا کرده و بخش دیگر را به عنوان داده یادگیری استفاده می‌کنیم و پس از تولید مدل مطلوب ورودی داده آزمون را در مدل وارد کرده و خروجی مدل را با خروجی واقعی می‌سنجیم. از این روی معیارهای بسیاری برای ارزیابی روش‌های با ناظر ارائه‌شده‌اند.
در یادگیری بدون ناظر روش متفاوت است. در این روش هیچ شاخص معینی در داده جهت ارزیابی وجود ندارد و ما به دنبال دسته‌بندی کردن داده‌ها بر اساس شباهت‌ها و تفاوت‌ها هستیم. از این روی برخلاف تلاش‌های خیلی از محققان، ارزیابی خوشه‌بندی خیلی توسعه داده نشده است و به عنوان بخشی از تحلیل خوشه‌بندی رایج نشده است. در واقع، ارزیابی خوشه‌بندی یکی از سخت‌ترین بخش‌های تحلیل خوشه‌بندی است [33]. معیارهای عددی، یا شاخص‌هایی که برای قضاوت جنبه‌های مختلف اعتبار یک خوشه به کار می روند، به سه دسته کلی تقسیم می‌شوند:
1- شاخص خارجی که مشخص می‌کند که کدام خوشه‌های پیداشده به وسیله الگوریتم خوشه‌بندی با ساختارهای خارجی تطبیق دارند. در این روش نیاز به اطلاعات اضافی مثل برچسب نقاط داده، داریم. آنتروپی یک مثالی از شاخص خارجی است.
2- شاخص داخلی که برای اندازه‌گیری میزان خوبی یک ساختار خوشه‌بندی بدون توجه به اطلاعات خارجی به کار می‌‌رود. یک نمونه از شاخص داخلی است.
3- شاخص نسبی که برای مقایسه دو خوشه‌بندی مختلف یا دو خوشه مختلف به کار می‌رود. اغلب یک شاخص خارجی یا داخلی برای این تابع استفاده می‌شود. برای مثال، دو خوشه‌بندی می‌توانند با مقایسه یا آنتروپی‌شان مقایسه شوند.
این فصل تعدادی از مهم‌ترین و رایج‌ترین روش‌های به‌کاررفته برای ارزیابی خوشه‌بندی را مرور خواهد کرد.
2-2-2-1. معیار SSEیک معیار داخلی ارزیابی خوشه‌بندی، مثل، می‌تواند برای ارزیابی یک خوشه‌بندی نسبت به خوشه‌بندی دیگر به کار رود. به علاوه، یک معیار داخلی اغلب می‌تواند برای ارزیابی یک خوشه‌بندی کامل یا یک خوشه تنها به استفاده شود. این اغلب به خاطر این است که این روش، سعی می‌کند تا میزان خوبی کلی خوشه‌بندی را به عنوان یک جمع وزن‌دار از خوبی‌های هر خوشه در نظر می‌گیرد. با استفاده از رابطه 2-25 محاسبه می‌شود [68].
(2-25)
کهیک نقطه داده در خوشه است و، j-امین ویژگی از داده X است. ، j-امین ویژگی از مرکز خوشه می‌باشد. برای مقایسه دو خوشه‌بندی مختلف روی یک داده با یک تعداد مشابه، تنها مقایسه مقدارهای متناظر آن‌ها کافی است. هر چه مقدار کمتر باشد، آن خوشه‌بندی بهتر خواهد بود. البته، وقتی تعداد نقاط داده در دو خوشه متفاوت باشند، مقایسه مستقیم از روی مقدار خوب نخواهد بود. بنابراین، یک خوشه معیار مناسب تری برای مقایسه است. رابطه 2-26 این معیار را نشان می‌دهد که در آن مقدار تعداد کل نمونه‌هاست [68].
(2-26)
تعداد درست خوشه‌ها در الگوریتم ، اغلب می‌تواند با استفاده از نگاه کردن به منحنی مشخص شود. این منحنی با رسم مقادیر به ازایهای مختلف به دست می‌آید. تعداد خوشه‌های بهینه با توجه به منحنی، ای است که به ازای آن نرخ کاهش مقدار، قابل چشم‌پوشی شود. شکل 2-13-ب منحنی را برای داده‌های شکل 2-13-الف، نشان می‌دهد.

(الف)
(ب)
شکل2-13. (الف) مجموعه داده با تعداد 10 خوشه واقعی. (ب) منحنی مربوطه [68]
همان طور که از شکل 2-13-ب برمی‌آید، برای مقادیرهای از صفر تا 10 شیب منحنی نسبت به بقیه مقادیر، تندتر می‌باشد. این امر نشان‌دهنده آن است که مقدار یک مقدار بهینه برای تعداد خوشه‌ها می‌باشد.

(الف)
(ب)
شکل2-14. (الف) مجموعه داده (ب) منحنی مربوطه [2]
شکل 2-14-ب نیز منحنی را برای داده‌های شکل 2-14-الف، نشان می‌دهد. مشاهده می‌شود که در این داده‌ها، چون تعداد خوشه‌ها نسبت به شکل 2-14-الف کاملاً گویا نیست، بنابراین، منحنی آن نیز نرم تر خواهد بود . اما با توجه به شکل 2-14-ب، می‌توان گفت که تعداد نسبتاً خوب باشد. چون منحنی برای های بعد از 8، دارای شیب کندتری خواهد شد. با توجه به نتایج فوق می‌توان گفت که اگرچه منحنی برای همه مسایل نمی‌تواند جواب بهینه برای تعداد بدهد، اما می‌تواند به عنوان یک معیار خوب برای این امر مطرح باشد.
2-2-2-2. معیار اطلاعات متقابل نرمال شدهمعیار اطلاعات متقابل () توسط کاور و توماس [71] معرفی شد که یک روش جهت اندازه‌گیری کیفیت اطلاعات آماری مشترک بین دو توزیع است. از آنجایی که این معیار وابسته به اندازه خوشه‌ها است در [54] روشی جهت نرمال سازی آن ارائه شده است. فرد و جین [19] روش نرمال سازی اطلاعات متقابل را اصلاح کردند و آن را تحت عنوان اطلاعات متقابل نرمال () ارائه داده‌اند. رابطه 2-27 اطلاعات متقابل نرمال شده را نشان می‌دهد[1, 2, 19] .
(2-27)
در رابطه 2-27 پارامتر کل نمونه‌ها است و یعنی افرازهایی که اندیس آن‌ها شامل i با تمام مقادیر j می‌باشد و یعنی افرازهایی که تمام مقادیر i با و اندیس j را شامل شود. از رابطه 2-28 محاسبه می‌شود [1, 2, 19].
(2-28)
, ,
در صورتی که دو افراز به صورت و که در آن کل داده و خوشه اول و خوشه دوم هر یک از افرازها باشد آنگاه نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد، نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد، نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد و نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد. در واقع و به ترتیب بیانگر کل نمونه‌های موجود در و می‌باشد [1].
شکل 2-15 دو افراز اولیه را نشان می‌دهد که میزان پایداری برای هر کدام از خوشه‌های به دست آمده هم محاسبه شده است. در این مثال الگوریتم به عنوان الگوریتم خوشه‌بندی اولیه انتخاب شده است و تعداد خوشه‌های اولیه برابر با سه نیز به عنوان پارامتر آن از قبل مشخص شده است. همچنین، در این مثال تعداد افرازهای موجود در مجموعه مرجع برابر با ۴۰ می‌باشد. در ۳۶ افراز نتایجی مشابه با شکل 2-15 (a) و در 4 حالت باقیمانده نیز نتایجی مشابه با شکل 2-15 (a) حاصل شده است [1].

شکل2-15. دو افراز اولیه با تعداد سه خوشه. (a) خوشه‌بندی درست (b) خوشه‌بندی نادرست [1]
از آن جایی که در مجموعه مرجع در ۹۰ % مواقع، داده‌های متراکم گوشه بالا‐چپ از شکل 2-15 در یک خوشه مجزا گروه‌بندی شده‌اند، بنابراین این خوشه باید مقدار پایداری بالایی را به خود اختصاص دهد. اگرچه این مقدار نباید دقیقاً برابر با یک باشد (چون در همه موارد این خوشه درست تشخیص داده نشده است)، مقدار پایداری با روش متداول اطلاعات متقابل نرمال شده مقدار یک را بر می‌گرداند. از آن جایی که ادغام دو خوشه سمت راست تنها در ۱۰ % موارد مانند شکل 2-15 (b) اتفاق افتاده است، خوشه حاصل باید مقدار پایداری کمی به دست آورد. اگر چه خوشه حاصل از ادغام دو خوشه سمت راستی، به ندرت ( ۱۰ % موارد) در مجموعه مرجع دیده شده است، مقدار پایداری برای این خوشه نیز برابر با یک به دست می‌آید. در اینجا مشکل روش متداول محاسبه پایداری با استفاده از اطلاعات متقابل نرمال شده ظاهر می‌شود. از آنجایی که معیار اطلاعات متقابل نرمال شده یک معیار متقارن است، مقدار پایداری خوشه بزرگ ادغامی سمت راست (با ۱۰ % تکرار) دقیقاً برابر با میزان پایداری خوشه متراکم گوشه بالا‐چپ (با ۹۰ % تکرار) به دست می‌آید. به عبارت دیگر در مواردی که داده‌های دو خوشه مکمل یکدیگر باشند، یعنی اجتماع داده‌های آن‌ها شامل کل مجموعه داده شود و اشتراک داده‌های آن‌ها نیز تهی باشد، مقدار پایداری برای هر دو به یک اندازه برابر به دست می‌آید. از دیدگاه دیگر، این اتفاق زمانی رخ می‌دهد که تعداد خوشه‌های تشکیل‌دهنده مجموعه در خوشه‌بندی مرجع عددی بیشتر از یک باشد. هر زمان که با ادغام دو یا بیشتر از خوشه‌ها به دست آید، منجر به نتایج نادرست در مقدار پایداری می‌شود. ما این مشکل را تحت عنوان مشکل تقارن در اطلاعات متقابل نرمال شده می‌شناسیم. در سال‌های اخیر روش‌هایی جهت حل این مشکل ارائه‌شده‌اند که یکی از آن‌ها را علیزاده و همکاران در [1, 9]ارائه داده‌اند که در‌ آن بزرگ‌ترین خوشه از بین مجموعه مرجع (که بیش از نصف نمونه‌هایش در خوشه مورد مقایسه وجود دارد) جایگزین اجتماع همه خوشه‌ها می‌شود که ما آن را با عنوان روش Max می‌شناسیم. روش دیگر جهت رفع این مشکل معیار APMM می‌باشد. در ادامه به بررسی این معیار می‌پردازیم [1, 8, 67].
2-2-2-3. معیار APMMبر خلاف معیارکه برای اندازه‌گیری شباهت دو افراز طراحی شده است معیار روشی برای اندازه‌گیری میزان شباهت یک خوشه در یک افراز است که توسط عـلیزاده و همکاران [8, 67] معرفی شده است رابطه 2-29 این معیار را معرفی می‌کند.
(2-29)
در رابطه 2-29 پارامتر خوشه i-ام در افراز می‌باشد و افراز متناظر با خوشه در خوشه‌بندی است. پارامتر تعداد کل نمونه‌های مجموعه داده و تعداد نمونه‌های مشترک بین خوشه‌های و می‌باشد. همچنین، تعداد خوشه‌های موجود در افراز می‌باشد. در این روش برای محاسبه پایداری خوشه از رابطه 2-30 استفاده می‌کنیم [8, 67].
(2-30)
در رابطه 2-30 پارامتر نشان‌دهنده j-امین افراز از مجموعه مرجع است و تعداد کل افرازها است [8, 67]. از آنجایی که این معیار برای ارزیابی شباهت یک خوشه است می‌توان هم برای ارزیابی خوشه و هم برای ارزیابی افراز استفاده کرد. جهت استفاده از این معیار برای ارزیابی یک افراز کافی است آن را برای تک‌تک خوشه‌های آن افراز استفاده کنیم و در نهایت از کل مقادیر میانگین بگیریم.
2-۳. خوشه‌بندی ترکیبیکلمه’Ensemble‘ ریشه فرانسوی دارد و به معنی باهم بودن یا در یک زمان می‌باشد و معمولاً اشاره به واحدها و یا گروه‌های مکملی دارد که باهم در اجرای یک کار واحد همکاری می‌کنند. ترکیب تاریخ طولانی در دنیای واقعی دارد، نظریه هیئت‌منصفه ی کندورست که در سال 1785 میلادی مطرح شده است و این ایده را مطرح می‌کند که، احتمال نسبی درستی نظر گروهی از افراد (رأی اکثریت) بیشتر از نظر هر یک از افراد به تنهایی می‌باشد را می‌توان دلیلی برای ترکیب نتایج در دنیای واقعی دانست [10, 27]. خوشه‌بندی ترکیبی روشی جدید در خوشه‌بندی می‌باشد که از ترکیب نتایج روش‌های خوشه‌بندی متفاوت به دست می‌آید از آنجایی که اکثر روش‌های خوشه‌بندی پایه روی جنبه‌های خاصی از داده‌ها تاکید می‌کنند، در نتیجه روی مجموعه داده‌های خاصی کارآمد می‌باشند. به همین دلیل، نیازمند روش‌هایی هستیم که بتواند با استفاده از ترکیب این الگوریتم‌ها و گرفتن نقاط قوت هر یک، نتایج بهینه‌تری را تولید کند. هدف اصلی خوشه‌بندی ترکیبی جستجوی نتایج بهتر و مستحکم‌تر، با استفاده از ترکیب اطلاعات و نتایج حاصل از چندین خوشه‌بندی اولیه است [18, 54]. خوشه‌بندی ترکیبی می‌تواند جواب‌های بهتری از نظر استحکام، نو بودن، پایداری و انعطاف‌پذیری نسبت به روش‌های پایه ارائه دهد [3, 21, 54, 57]. به طور خلاصه خوشه‌بندی ترکیبی شامل دو مرحله اصلی زیر می‌باشد : [34, 54]
1- تولید نتایج متفاوت از خوشه‌بندی‌ها، به عنوان نتایج خوشه‌بندی اولیه بر اساس اعمال روش‌های مختلف که این مرحله را، مرحله ایجاد تنوع یا پراکندگی می‌نامند.
2- ترکیب نتایج به دست آمده از خوشه‌بندی‌های متفاوت اولیه برای تولید خوشه نهایی؛ که این کار توسط تابع توافقی (الگوریتم ترکیب‌کننده) انجام می‌شود.
2-۳-1. ایجاد تنوع در خوشه‌بندی ترکیبیدر خوشه‌بندی ترکیبی، هرچه خوشه‌بندی‌های اولیه نتایج متفاوت تری ارائه دهند نتیجه نهایی بهتری حاصل می‌شود. در واقع هرچه داده‌ها از جنبه‌های متفاوت‌تری مطالعه و بررسی شوند (تشخیص الگوهای پنهان داده) نتیجه نهایی که از ترکیب این نتایج حاصل می‌شود متعاقباً دارای دقت بالاتری خواهد بود که این امر منجر به کشف دانش ضمنی پنهان در داده نیز خواهد شد. تنوع در این بخش به این معنا می‌باشد که با استفاده از روش‌های متفاوت مجموعه داده را از دیدگاه‌های گوناگونی مورد بررسی قرار دهیم. در این فصل برای ایجاد پراکندگی در بین نتایج حاصل چند راه‌کار مختلف پیشنهاد می‌کنیم و به بررسی مطالعات انجام‌شده در هر یک از آن‌ها می‌پردازیم. راه‌های مختلفی برای ایجاد پراکندگی در خوشه‌بندی ترکیبی وجود دارد که عبارت‌اند از:
استفاده از الگوریتم‌های متفاوت خوشه‌بندی.
تغییر مقادیر اولیه و یا سایر پارامترهای الگوریتم خوشه‌بندی انتخاب‌شده.
انتخاب بعضی از ویژگی داده‌ها یا ایجاد ویژگی‌های جدید.
تقسیم‌بندی داده‌های اصلی به زیرمجموعه‌هایی متفاوت و مجزا.
در حقیقت به خاطر ماهیت بدون ناظر بودن مسئله خوشه‌بندی این اصل که آیا پراکندگی به وجود آمده مفید می‌باشد یا مفید نیست را نمی‌تواند مورد مطالعه قرارداد اما نتایج تجربی نشان داده است که ایجاد پراکندگی در خوشه‌بندی‌های اولیه به طور معمول موجب بهبود خوشه‌بندی در اکثر مواقع می‌شود لذا در روش‌های ارائه‌شده هدف تنها بررسی مجموعه داده از زوایای مختلف است [42] .

user8286

شکل2-13. (الف) مجموعه داده با تعداد 10 خوشه واقعی. (ب) منحنی ........................................................ 29
شکل2-1۴. (الف) مجموعه داده (ب) منحنی مربوطه ..................................................................................... 29
شکل2-15. دو افراز اولیه با تعداد سه خوشه ........................................................................................................... 31
شکل2-16. نمونه‌های اولیه در نتایج الگوریتم ................................................................................ 36
شکل 2-17. زیر شبه کد الگوریتم خوشه‌بندی ترکیبی توسط مدل مخلوط .............................................................. 43
شکل 2-18. خوشه‌بندی ترکیبی ............................................................................................................................... 44
شکل 2-19. نمونه ماتریس، جهت تبدیل خوشه‌بندی به ابر گراف ................................................................. 45
شکل 2-20. ماتریس شباهت بر اساس خوشه برای مثال شکل (3-5) .................................................................... 46
شکل 2-21. الگوریتم افرازبندی ابر گراف ............................................................................................................... 47
شکل 2-22. الگوریتم فرا خوشه‌بندی ..................................................................................................................... 49
شکل2-23. الگوریتم خوشه‌بندی ترکیبی مبتنی بر ماتریس همبستگی ...................................................................... 50
شکل2-24. الگوریتم افرازبندی با تکرار ................................................................................................................... 53
شکل2-25. نمایش گراف مجاورت در مراحل کاهش درجه ماتریس و شمارش آن ................................................ 54
شکل2-26. مثال روند تغییر توزیع تعداد خوشه ....................................................................................................... 55
شکل2-27. جریان کار عمومی برای پیاده‌سازی الگوریتم افرازبندی گراف .............................................................. 55
شکل 2-28. گراف تابع در بازه بین صفر و یک ............................................................................................. 62
شکل 2-29. الگوریتم خوشه‌بندی ترکیبی طیفی مبتنی بر انتخاب بر اساس شباهت ................................................ 63
شکل 2-30. مثالی از ماتریس اتصال ........................................................................................................................ 66
شکل 2-31. شبه کد خوشه‌بندی ترکیبی انتخابی لی‌مین .......................................................................................... 68
شکل 2-32. روش ارزیابی خوشهی یک افراز در روش MAX ............................................................................... 69
شکل 2-33. چهارچوب خوشهبندی ترکیبی مبتنی بر انتخاب با استفاده از مجموعه‌ای از خوشه‌های یک افراز ...... 71
شکل 2-34. چهارچوب روش بهترین افراز توافقی اعتبارسنجی شده ...................................................................... 72
فصل سوم
شکل3-1. چهارچوب الگوریتم خوشه‌بندی خردمند با استفاده از آستانه‌گیری ......................................................... 82
شکل3-۲. محاسبه درجه استقلال دو خوشه‌بندی ..................................................................................................... 86
شکل3-3. تأثیر عدم تمرکز بر روی پیچیدگی داده ................................................................................................... 89
شکل3-3. تأثیر انتخاب افرازها در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر مقدار NMI ارزیابی‌شده ........................ 91
شکل3-4. شبه کد خوشه‌بندی خردمند با استفاده از آستانه‌گیری .............................................................................. 92
شکل3-5. دسته‌بندی الگوریتم‌های خوشه‌بندی ........................................................................................................ 94
شکل3-6. کد الگوریتم K-means به زبان استقلال الگوریتم‌ خوشه‌بندی ................................................................. 98
شکل3-7. تبدیل کد‌های شروع و پایان به گراف .................................................................................................... 100
شکل3-8. تبدیل عملگر شرط ساده به گراف ......................................................................................................... 100
شکل3-9. تبدیل عملگر شرط کامل به گراف ......................................................................................................... 101
شکل3-10. تبدیل عملگر شرط تو در تو به گراف ................................................................................................. 101
شکل3-11. تبدیل عملگر حلقه ساده به گراف ....................................................................................................... 102
شکل3-12. تبدیل عملگر حلقه با پرش به گراف ................................................................................................... 102
شکل3-13. پیاده‌سازی شرط ساده بدون هیچ کد اضافی ........................................................................................ 103
شکل3-14. پیاده‌سازی شرط ساده با کدهای قبل و بعد آن .................................................................................... 103
شکل3-15. پیاده‌سازی شرط کامل ......................................................................................................................... 104
شکل3-16. پیاده‌سازی شرط‌ تو در تو .................................................................................................................... 104
شکل3-17. پیاده‌سازی یک شرط کامل در یک شرط ساده .................................................................................... 105
شکل3-18. پیاده‌سازی یک شرط کامل در یک شرط کامل دیگر ........................................................................... 105
شکل3-19. پیاده‌سازی حلقه ساده .......................................................................................................................... 106
شکل3-20. پیاده‌سازی یک حلقه ساده داخل حلقه‌ای دیگر ................................................................................... 106
شکل3-21. پیاده‌سازی یک حلقه داخل یک شرط کامل ........................................................................................ 106
شکل3-22. پیاده‌سازی یک شرط کامل داخل یک حلقه ساده ................................................................................ 107
شکل3-23. ماتریس درجه وابستگی‌ کد ................................................................................................................. 108
شکل3-24. شبه کد مقایسه محتوای دو خانه از آرایه‌های استقلال الگوریتم .......................................................... 108
شکل3-25. چهارچوب خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم ...................................................... 110
شکل3-26. شبه کد خوشه‌بندی خردمند مبتنی بر گراف استقلال الگوریتم ............................................................ 113
فصل چهارم
شکل۴-۱. مجموعه داده Halfring .......................................................................................................................... 118
شکل4-2. الگوریتم K-means ................................................................................................................................ 121
شکل4-3. الگوریتم FCM ...................................................................................................................................... 121
شکل4-4. الگوریتم Median K-Flats .................................................................................................................... 122
شکل4-5. الگوریتم Gaussian Mixture ................................................................................................................ 122
شکل4-6. الگوریتم خوشه‌بندی Subtractive ......................................................................................................... 122
شکل4-7. الگوریتم پیوندی منفرد با استفاده از معیار فاصله اقلیدسی ..................................................................... 123
شکل4-8. الگوریتم پیوندی منفرد با استفاده از معیار فاصله Hamming ................................................................ 123
شکل4-9. الگوریتم پیوندی منفرد با استفاده از معیار فاصله Cosine ..................................................................... 123
شکل4-10. الگوریتم پیوندی کامل با استفاده از معیار فاصله اقلیدسی ................................................................... 124
شکل4-1۱. الگوریتم پیوندی کامل با استفاده از معیار فاصله Hamming .............................................................. 124
شکل4-1۲. الگوریتم پیوندی کامل با استفاده از معیار فاصله Cosine .................................................................... 124
شکل4-1۳. الگوریتم پیوندی میانگین با استفاده از معیار فاصله اقلیدسی ............................................................... 124
شکل4-14. الگوریتم پیوندی میانگین با استفاده از معیار فاصله Hamming .......................................................... 125
شکل4-15. الگوریتم پیوندی میانگین با استفاده از معیار فاصله Cosine ............................................................... 125
شکل4-16. الگوریتم پیوندی بخشی با استفاده از معیار فاصله اقلیدسی ................................................................ 125
شکل4-17. الگوریتم پیوندی بخشی با استفاده از معیار فاصله Hamming ............................................................ 125
شکل4-18. الگوریتم پیوندی بخشی با استفاده از معیار فاصله Cosine ................................................................. 126
شکل4-19. طیفـی با استفاده از ماتریس شباهت نامتراکم ...................................................................................... 126
شکل4-20. طیفـی با استفاده از روش نیستروم با متعادل ساز .............................................................................. 127
شکل4-21. طیفـی با استفاده از روش نیستروم بدون متعادل ساز ......................................................................... 127
شکل4-22. نرم‌افزار تحلیل‌گر کد استقلال الگوریتم ............................................................................................... 128
شکل4-23. ماتریس AIDM ................................................................................................................................... 129
شکل4-24. میانگین دقت الگوریتم‌های خوشه‌بندی ............................................................................................... 131
شکل4-25. رابطه میان آستانه استقلال و زمان اجرای الگوریتم در روش پیشنهادی اول ........................................ 133
شکل4-26. رابطه میان آستانه پراکندگی و زمان اجرای الگوریتم در روش پیشنهادی اول ..................................... 133
شکل4-27. رابطه میان آستانه استقلال و دقت نتیجه نهایی در روش پیشنهادی اول .............................................. 134
شکل4-28. رابطه میان آستانه پراکندگی و دقت نتیجه نهایی در روش پیشنهادی اول ............................................ 134
شکل4-29. رابطه میان آستانه عدم تمرکز و دقت نتیجه نهایی در روش پیشنهادی اول ......................................... 135
شکل4-30. رابطه میان آستانه پراکندگی و زمان اجرای الگوریتم در روش پیشنهادی دوم ..................................... 135
شکل4-31. رابطه میان آستانه پراکندگی و دقت نتایج نهایی در روش پیشنهادی دوم ............................................ 136
شکل4-32. رابطه میان آستانه عدم تمرکز و دقت نتایج نهایی در روش پیشنهادی دوم ......................................... 137
شکل4-33. مقایسه زمان اجرای الگوریتم‌ ............................................................................................................... 138
فصل اول
مقدمه
center3187700
1. مقدمه1-1. خوشه‌بندیبه عنوان یکی از شاخه‌های وسیع و پرکاربرد هوش مصنوعی، یادگیری ماشین به تنظیم و اکتشاف شیوه‌ها و الگوریتم‌هایی می‌پردازد که بر اساس آن‌ها رایانه‌ها و سامانه‌های اطلاعاتی توانایی تعلم و یادگیری پیدا می‌کنند. طیف پژوهش‌هایی که در مورد یادگیری ماشینی صورت می‌گیرد گسترده ‌است. در سوی نظر‌ی آن پژوهش‌گران بر آن‌اند که روش‌های یادگیری تازه‌ای به وجود بیاورند و امکان‌پذیری و کیفیت یادگیری را برای روش‌هایشان مطالعه کنند و در سوی دیگر عده‌ای از پژوهش‌گران سعی می‌کنند روش‌های یادگیری ماشینی را بر مسائل تازه‌ای اعمال کنند. البته این طیف گسسته نیست و پژوهش‌های انجام‌شده دارای مؤلفه‌هایی از هر دو رو‌یکرد هستند. امروزه، داده‌کاوی به عنوان یک ابزار قوی برای تولید اطلاعات و دانش از داده‌های خام، در یادگیری ماشین شناخته‌شده و همچنان با سرعت در حال رشد و تکامل است. به طور کلی می‌توان تکنیک‌های داده‌کاوی را به دو دسته بانظارت و بدون نظارت تقسیم کرد [29, 46].
در روش بانظارت ما ورودی (داده یادگیری) و خروجی (کلاس داده) یک مجموعه داده را به الگوریتم هوشمند می‌دهیم تا آن الگوی بین ورودی و خروجی را تشخیص دهد در این روش خروجی کار ما مدلی است که می‌تواند برای ورودی‌های جدید خروجی درست را پیش‌بینی کند. روش‌های طبقه‌بندی و قوانین انجمنی از این جمله تکنیک‌ها می‌باشد. روش‌های با نظارت کاربرد فراوانی دارند اما مشکل عمده این روش‌ها این است که همواره باید داده‌ای برای یادگیری وجود داشته باشد که در آن به ازای ورودی مشخص خروجی درست آن مشخص شده باشد. حال آنکه اگر در زمینه‌ای خاص داده‌ای با این فرمت وجود نداشته باشد این روش‌ها قادر به حل این‌گونه مسائل نخواهند بود [29, 68]. در روش بدون نظارت برخلاف یادگیری بانظارت هدف ارتباط ورودی و خروجی نیست، بلکه تنها دسته‌بندی ورودی‌ها است. این نوع یادگیری بسیار مهم است چون خیلی از مسائل (همانند دنیای ربات‌ها) پر از ورودی‌هایی است که هیچ برچسبی (کلاس) به آن‌ها اختصاص داده نشده است اما به وضوح جزئی از یک دسته هستند [46, 68]. خوشه‌بندی شاخص‌ترین روش در داده‌کاوی جهت حل مسائل به صورت بدون ناظر است. ایده اصلی خوشه‌بندی اطلاعات، جدا کردن نمونه‌ها از یکدیگر و قرار دادن آن‌ها در گروه‌های شبیه به هم می‌باشد. به این معنی که نمونه‌های شبیه به هم باید در یک گروه قرار بگیرند و با نمونه‌های گروه‌های دیگر حداکثر متفاوت را دارا باشند [20, 26]. دلایل اصلی برای اهمیت خوشه‌بندی عبارت‌اند از:
اول، جمع‌آوری و برچسب‌گذاری یک مجموعه بزرگ از الگوهای نمونه می‌تواند بسیار پرکاربرد و باارزش باشد.
دوم، می‌توانیم از روش‌های خوشه‌بندی برای پیدا کردن و استخراج ویژگی‌ها و الگوهای جدید استفاده کنیم. این کار می‌تواند کمک به سزایی در کشف دانش ضمنی داده‌ها انجام دهد.
سوم، با خوشه‌بندی می‌توانیم یک دید و بینشی از طبیعت و ساختار داده به دست آوریم که این می‌تواند برای ما باارزش باشد.
چهارم، خوشه‌بندی می‌تواند منجر به کشف زیر رده‌های مجزا یا شباهت‌های بین الگوها ممکن شود که به طور چشمگیری در روش طراحی طبقه‌بندی قابل استفاده باشد.
1-2. خوشه‌بندی ترکیبیهر یک از الگوریتم‌های خوشه‌بندی، با توجه به اینکه بر روی جنبه‌های متفاوتی از داده‌ها تاکید می‌کند، داده‌ها را به صورت‌های متفاوتی خوشه‌بندی می‌نماید. به همین دلیل، نیازمند روش‌هایی هستیم که بتواند با استفاده از ترکیب این الگوریتم‌ها و گرفتن نقاط قوت هر یک، نتایج بهینه‌تری را تولید کند. در واقع هدف اصلی خوشه‌بندی ترکیبی جستجوی بهترین خوشه‌ها با استفاده از ترکیب نتایج الگوریتم‌های دیگر است [1, 8, 9, 54, 56]. به روشی از خوشه‌بندی ترکیبی که زیرمجموعه‌ی منتخب از نتایج اولیه برای ترکیب و ساخت نتایج نهایی استفاده می‌شود خوشه‌بندی ترکیبی مبتنی بر انتخاب زیرمجموعه نتایج اولیه می‌گویند. در این روش‌ها بر اساس معیاری توافقی مجموعه‌ای از مطلوب‌ترین نتایج اولیه را انتخاب کرده و فقط توسط آن‌ها نتیجه نهایی را ایجاد می‌کنیم [21]. معیارهای مختلفی جهت انتخاب مطلوب‌ترین روش پیشنهاد شده است که معیار اطلاعات متقابل نرمال شده، روش ماکزیموم و APMM برخی از آن‌ها می‌باشند [8, 9, 21, 67]. دو مرحله مهم در خوشه‌بندی ترکیبی عبارت‌اند از:
اول، الگوریتم‌های ابتدایی خوشه‌بندی که خوشه‌بندی اولیه را انجام می‌دهد.
دوم، جمع‌بندی نتایج این الگوریتم‌های اولیه (پایه) برای به دست آوردن نتیجه نهایی.
1-3. خرد جمعینظریه خرد جمعی که اولین بار توسط سورویکی در سال 2004 در کتابی با همان عنوان منتشر شد، استنباطی از مسائل مطرح‌شده توسط گالتون و کندورست می‌باشد، و نشان می‌دهد که قضاوت‌های جمعی و دموکراتیک از اعتبار بیشتری نسبت به آنچه که ما انتظار داشتیم برخوردار است، ما تأثیرات این ایده را در حل مسائل سیاسی، اجتماعی در طی سال‌های اخیر شاهد هستیم. در ادبیات خرد جمعی هر جامعه‌ای را خردمند نمی‌گویند. از دیدگاه سورویکی خردمند بودن جامعه در شرایط چهارگانه پراکندگی، استقلال، عدم تمرکز و روش ترکیب مناسب است [55].
1-4. خوشه‌بندی مبتنی بر انتخاب بر اساس نظریه خرد جمعیهدف از این تحقیق استفاده از نظریه خرد جمعی برای انتخاب زیرمجموعه‌ی مناسب در خوشه‌بندی ترکیبی می‌باشد. تعاریف سورویکی از خرد جمعی مطابق با مسائل اجتماعی است و در تعاریف آن عناصر سازنده تصمیمات رأی افراد می‌باشد. در این تحقیق ابتدا مبتنی بر تعاریف پایه سورویکی از خرد جمعی و ادبیات مطرح در خوشه‌بندی ترکیبی، تعریف پایه‌ای از ادبیات خرد جمعی در خوشه‌بندی ترکیبی ارائه می‌دهیم و بر اساس آن الگوریتم پیشنهادی خود را در جهت پیاده‌سازی خوشه‌بندی ترکیبی ارائه می‌دهیم [55]. شرایط چهارگانه خوشه‌بندی خردمند که متناسب با تعاریف سورویکی باز تعریف شده است به شرح زیر می‌باشد:
پراکندگی نتایج اولیه، هر الگوریتم خوشه‌بندی پایه باید به طور جداگانه و بدون واسطه به داده‌های مسئله دسترسی داشته و آن را تحلیل و خوشه‌بندی کند حتی اگر نتایج آن غلط باشد.
استقلال الگوریتم، روش تحلیل هر یک از خوشه‌بندی‌های پایه نباید تحت تأثیر روش‌های سایر خوشه‌بندی‌های پایه تعیین شود، این تأثیر می‌تواند در سطح نوع الگوریتم (گروه) یا پارامترهای اساسی یک الگوریتم خاص (افراد) باشد.
عدم تمرکز، ارتباط بین بخش‌های مختلف خوشه‌بندی خرد جمعی باید به گونه‌ای باشد تا بر روی عملکرد خوشه‌بندی پایه تأثیری ایجاد نکند تا از این طریق هر خوشه‌بندی پایه شانس این را داشته باشد تا با شخصی سازی و بر اساس دانش محلی خود بهترین نتیجه ممکن را آشکار سازد.
مکانیزم ترکیب مناسب، باید مکانیزمی وجود داشته باشد که بتوان توسط آن نتایج اولیه الگوریتم‌های پایه را با یکدیگر ترکیب کرده و به یک نتیجه نهایی (نظر جمعی) رسید.
در این تحقیق دو روش برای ترکیب خوشه‌بندی ترکیبی و خرد جمعی پیشنهاد شده است. با استفاده از تعاریف بالا الگوریتم روش اول مطرح خواهد شد که در آن، جهت رسیدن به نتیجه نهایی از آستانه‌گیری استفاده می‌شود. در این روش الگوریتم‌های خوشه‌بندی اولیه غیر هم نام کاملاً مستقل فرض خواهند شد و برای ارزیابی استقلال الگوریتم‌های هم نام نیاز به آستانه‌گیری می‌باشد. در روش دوم، سعی شده است تا دو بخش از روش اول بهبود یابد. از این روی جهت مدل‌سازی الگوریتم‌ها و ارزیابی استقلال آن‌ها نسبت به هم یک روش مبتنی بر گراف شبه کد ارائه می‌شود و میزان استقلال به دست آمده در این روش به عنوان وزنی برای ارزیابی پراکندگی در تشکیل جواب نهایی مورد استفاده قرار می‌گیرد. جهت ارزیابی، روش‌های پیشنهادی با روش‌های پایه، روش‌ ترکیب کامل و چند روش معروف ترکیب مبتنی بر انتخاب مقایسه خواهد شد. از این روی از چهارده داده استاندارد و یا مصنوعی که عموماً از سایت UCI [76] جمع‌آوری شده‌اند استفاده شده است. در انتخاب این داده‌ها سعی شده، داده‌هایی با مقیاس‌ کوچک، متوسط و بزرگ انتخاب شوند تا کارایی روش بدون در نظر گرفتن مقیاس داده ارزیابی شود. همچنین جهت اطمینان از صحت نتایج تمامی آزمایش‌های تجربی گزارش‌شده حداقل ده بار تکرار شده است.
1-4-1- فرضیات تحقیقاین تحقیق بر اساس فرضیات زیر اقدام به ارائه روشی جدید در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر اساس نظریه خرد جمعی می‌کند.
۱ ) در این تحقیق تمامی آستانه‌گیری‌ها بر اساس میزان صحت نتایج نهایی و مدت زمان اجرای الگوریتم به صورت تجربی انتخاب می‌شوند.
۲ ) در این تحقیق جهت ارزیابی عملکرد یک الگوریتم، نتایج اجرای آن را بر روی‌داده‌های استاندارد UCI در محیطی با شرایط و پارامترهای مشابه نسبت به سایر الگوریتم‌ها ارزیابی می‌کنیم که این داده‌ها الزاماً حجیم یا خیلی کوچک نیستند.
۳ ) جهت اطمینان از صحت نتایج آزمایش‌ها ارائه‌شده در این تحقیق، حداقل اجرای هر الگوریتم بر روی هر داده ده بار تکرار شده و نتیجه‌ی نهایی میانگین نتایج به دست آمده می‌باشد.
4 ) از آنجایی که روش مطرح‌شده در این تحقیق یک روش مکاشفه‌ای است سعی خواهد شد بیشتر با روش‌های مکاشفه‌ای مطرح در خوشه‌بندی ترکیبی مقایسه و نتایج آن مورد بررسی قرار گیرد.
در این فصل اهداف، مفاهیم و چالش‌های این تحقیق به صورت خلاصه ارائه شد. در ادامه این تحقیق، در فصل دوم، الگوریتم‌های خوشه‌بندی پایه و روش‌های خوشه‌بندی‌ ترکیبی مورد بررسی قرار می‌گیرد. همچنین به مرور روش‌های انتخاب خوشه و یا افراز در خوشه‌بندی ترکیبی مبتنی بر انتخاب خواهیم پرداخت. در فصل سوم، نظریه خرد جمعی و دو روش پیشنهادی خوشه‌بندی خردمند ارائه می‌شود. در فصل چهارم، به ارائه نتایج آزمایش‌های تجربی این تحقیق و ارزیابی آن‌ها می‌پردازیم و در فصل پنجم، به ارائه‌ی نتایج و کار‌های آتی خواهیم پرداخت.

فصل دوم
مروری بر ادبیات تحقیق
center2132965
2. مروری بر ادبیات تحقیق2-1. مقدمهدر این بخش، کارهای انجام‌شده در خوشه‌بندی و خوشه‌بندی ترکیبی را مورد مطالعه قرار می‌دهیم. ابتدا چند الگوریتم‌ پایه خوشه‌بندی معروف را معرفی خواهیم کرد. سپس چند روش کاربردی جهت ارزیابی خوشه، خوشه‌بندی و افرازبندی را مورد مطالعه قرار می‌دهیم. در ادامه به بررسی ادبیات خوشه‌بندی ترکیبی خواهیم پرداخت و روش‌های ترکیب متداول را بررسی خواهیم کرد. از روش‌های خوشه‌بندی ترکیبی، روش ترکیب کامل و چند روش معروف مبتنی بر انتخاب را به صورت مفصل شرح خواهیم داد.
2-2. خوشه‌بندیدر این بخش ابتدا انواع الگوریتم‌های خوشه‌بندی پایه را معرفی می‌کنیم و سپس برخی از آن‌ها را مورد مطالعه قرار می‌دهیم سپس برای ارزیابی نتایج به دست آمده چند متریک معرفی خواهیم کرد.
2-2-1. الگوریتم‌های خوشه‌بندی پایهبه طور کلی، الگوریتم‌های خوشه‌بندی را می‌توان به دو دسته کلی تقسیم کرد:
1- الگوریتم‌های سلسله مراتبی
2- الگوریتم‌های افرازبندی
الگوریتم‌های سلسله مراتبی، یک روال برای تبدیل یک ماتریس مجاورت به یک دنباله از افرازهای تو در تو، به صورت یک درخت است. در این روش‌ها، مستقیماً با داده‌ها سروکار داریم و از روابط بین آن‌ها برای به دست آوردن خوشه‌ها استفاده می‌کنیم. یکی از ویژگی‌های این روش قابلیت تعیین تعداد خوشه‌ها به صورت بهینه می‌باشد. در نقطه مقابل الگوریتم‌های سلسله مراتبی، الگوریتم‌های افرازبندی قرار دارند. هدف این الگوریتم‌ها، تقسیم داده‌ها در خوشه‌ها، به گونه‌ای است که داده‌های درون یک خوشه بیش‌ترین شباهت را به همدیگر داشته باشند؛ و درعین‌حال، بیش‌ترین فاصله و اختلاف را با داده‌های خوشه‌های دیگر داشته باشند. در این فصل تعدادی از متداول‌ترین الگوریتم‌های خوشه‌بندی، در دو دسته سلسله مراتبی و افرازبندی، مورد بررسی قرار می‌گیرند. از روش سلسله‌ مراتبی چهار الگوریتم‌ از سری الگوریتم‌های پیوندی را مورد بررسی قرار می‌دهیم. و از الگوریتم‌های افرازبندی K-means، FCM و الگوریتم طیفی را مورد بررسی خواهیم داد.
2-2-1-1. الگوریتم‌های سلسله مراتبیهمان‌گونه که در شکل 2-1 مشاهده می‌شود، روال الگوریتم‌های خوشه‌بندی سلسله مراتبی را می‌تواند به صورت یک دندوگرام نمایش داد. این نوع نمایش تصویری از خوشه‌بندی سلسله مراتبی، برای انسان، بیشتر از یک لیست از نمادها قابل‌درک است. در واقع دندوگرام، یک نوع خاص از ساختار درخت است که یک تصویر قابل‌فهم از خوشه‌بندی سلسله مراتبی را ارائه می‌کند. هر دندوگرام شامل چند لایه از گره‌هاست، به طوری که هر لایه یک خوشه را نمایش می‌دهد. خطوط متصل‌کننده گره‌ها، بیانگر خوشه‌هایی هستند که به صورت آشیانه‌ای داخل یکدیگر قرار دارند. برش افقی یک دندوگرام، یک خوشه‌بندی را تولید می‌کند [33]. شکل 2-1 یک مثال ساده از خوشه‌بندی و دندوگرام مربوطه را نشان می‌دهد.

شکل 2-1. یک خوشه‌بندی سلسله مراتبی و درخت متناظر
اگر الگوریتم‌های خوشه‌بندی سلسله مراتبی، دندوگرام را به صورت پایین به بالا بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تراکمی نامیده می‌شوند. همچنین، اگر آن‌ها دندوگرام را به صورت بالا به پایین بسازند، الگوریتم‌های خوشه‌بندی سلسله مراتبی تقسیم‌کننده نامیده می‌شوند [26]. مهم‌ترین روش‌های خوشه‌بندی سلسله مراتبی الگوریتم‌های سری پیوندی می‌باشد که در این بخش تعدادی از کاراترین آن‌ها مورد بررسی قرار خواهند گرفت که عبارت‌اند از:
الگوریتم پیوندی منفرد
الگوریتم پیوندی کامل
الگوریتم پیوندی میانگین
الگوریتم پیوندی بخشی
2-2-1-1-1. تعاریف و نماد‌ها
شکل 2-2. ماتریس مجاورت
قبل از معرفی این الگوریتم‌ها، در ابتدا نمادها و نحوه نمایش مسئله نمایش داده خواهد شد. فرض کنید که یک ماتریس مجاورت متقارن داریم. وارده در هر سمت قطر اصلی قرار دارد که شامل یک جای گشت اعداد صحیح بین 1 تا است. ما مجاورت‌ها را عدم شباهت در نظر می‌گیریم. به این معنی است که اشیاء 1 و 3 بیشتر از اشیاء 1 و 2 به هم شبیه‌اند. یک مثال از ماتریس مجاورت معمول برای است که در شکل 2-2 نشان داده شده است. یک گراف آستانه، یک گراف غیر جهت‌دار و غیر وزن‌دار، روی گره، بدون حلقه بازگشت به خود یا چند لبه است. هر نود یک شیء را نمایش می‌دهد. یک گراف آستانه برای هر سطح عدم شباهت به این صورت تعریف می‌شود: اگر عدم شباهت اشیاء و از حد آستانه کوچک‌تر باشد، با واردکردن یک لبه بین نودهای ویک گراف آستانه تعریف می‌کنیم.
(2-1)if and only if
شکل 2-3 یک رابطه دودویی به دست آمده از ماتریس مربوط به شکل 2-2 را برای مقدار آستانه 5 نشان می‌دهد. نماد "*" در موقعیت ماتریس، نشان می‌دهد که جفت متعلق به رابطه دودویی می‌باشد. شکل 2-4، گراف‌های آستانه برای ماتریس را نمایش می‌دهد.

شکل 2-3. رابطه دودویی و گراف آستانه برای مقدار آستانه 5.

شکل 2-4. گراف‌های آستانه برای ماتریس
2-2-1-1-2. الگوریتم پیوندی منفرداین الگوریتم روش کمینه و روش نزدیک‌ترین همسایه نیز نامیده می‌شود [26]. اگر و خوشه‌ها باشند، در روش پیوندی منفرد، فاصله آن‌ها برابر خواهد بود با:
(2-2)
که نشان‌دهنده فاصله (عدم شباهت) بین نقاط a و b در ماتریس مجاورت است. شکل 2-5 این الگوریتم را نمایش می‌دهد. شکل 2-6 دندوگرام حاصل از روش پیوندی منفرد را برای ماتریس ، را نشان می‌دهد.
Step 1. Begin with the disjoint clustering implied by threshold graph, which contains no edges and which places every object in a unique cluster, as the current clustering. Set.
Step 2. From threshold graph.
If the number of comonents (maximally connected subgraphs) in, is less than the number of clusters in the current clustering, redefiene the current clustering by naming each component of as a cluster.
Step 3. If consists of a single connected graph, stop. Else, setand go to step 2.
شکل 2-5. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی منفرد

شکل 2-6. دندوگرام پیوندی منفرد برای ماتریس
2-2-1-1-3. الگوریتم پیوندی کاملاین الگوریتم روش بیشینه یا روش دورترین همسایه نیز نامیده می‌شود. الگوریتم پیوندی کامل می‌گوید که وقتی دو خوشه و شبیه به هم هستند که بیشینه روی تمام ها در و کوچک باشد. به عبارت دیگر، در این الگوریتم، برای یکی کردن دو خوشه، همه جفت‌ها در دو خوشه باید شبیه به هم باشند [26]. اگر و خوشه‌ها باشند، در روش پیوندی کامل، فاصله آن‌ها برابر خواهد بود با:
(2-3)
که نشان‌دهنده فاصله(عدم شباهت) بین نقاط a و در ماتریس مجاورت است. شکل 2-7 این الگوریتم و شکل 2-8 دندوگرام حاصل از این روش را برای ماتریس ، را نشان می‌دهد.
Step 1. Begin with the disjoint clustering implied by threshold graph, which contains no edges and which places every object in a unique cluster, as the current clustering. Set.
Step 2. From threshold graph.
If two of the current clusters from a clique (maximally complete sub graph) in, redefine the current clustering by merging these two clusters into a single cluster.
Step 3. If, so that is the complete graph on the nodes, stop. Else, set and go to step 2.
شکل 2-7. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی کامل

شکل 2-8. دندوگرام پیوندی کامل برای ماتریس
2-2-1-1-4. الگوریتم پیوندی میانگینالگوریتم پیوندی منفرد اجازه می‌دهد تا خوشه‌ها به صورت دراز و نازک رشد کنند. این در شرایطی است که الگوریتم پیوندی کامل خوشه‌های فشرده‌تری تولید می‌کند. هر دو الگوریتم مستعد خطا با داده‌های خارج از محدوده هستند. الگوریتم خوشه‌بندی پیوندی میانگین، یک تعادلی بین مقادیر حدی الگوریتم‌های پیوندی منفرد و کامل است. الگوریتم پیوندی میانگین همچنین، روش جفت-گروه بدون وزن با استفاده از میانگین حسابی نامیده می‌شود. این الگوریتم، یکی از پرکاربردترین الگوریتم‌های خوشه‌بندی سلسله مراتبی می‌باشد [26]. اگر یک خوشه با تعداد تا عضو، و یک خوشه دیگر با تعداد تا عضو باشند، در روش پیوندی میانگین، فاصله آن‌ها برابر خواهد بود با:
(2-4)
که نشان‌دهنده فاصله(عدم شباهت) بین نقاط a و در ماتریس مجاورت است.
2-2-1-1-5. الگوریتم پیوندی بخشیروش پیوندی بخشی که از مربع مجموع خطا‌های (SSE) خوشه‌های یک افراز برای ارزیابی استفاده می‌کند، یکی دیگر از روش‌های سلسله مراتبی می‌باشد [60]. اگر یک خوشه با تعداد تا عضو، و یک خوشه دیگر با تعداد تا عضو باشند و نماد به معنای فاصله اقلیدسی و و مراکز خوشه‌های و باشد آنگاه در روش پیوندی بخشی، فاصله آن‌ها برابر خواهد بود با:
(2-5)
2-2-1-2. الگوریتم‌های افرازبندییک خاصیت مهم روش‌های خوشه‌بندی سلسله مراتبی، قابلیت نمایش دندوگرام است که تحلیل‌گر را قادر می‌سازد تا ببیند که چگونه اشیاء در سطوح متوالی مجاورت، در خوشه‌ها به هم پیوند می‌خورند یا تفکیک می‌شوند. همان طور که اشاره شد، هدف الگوریتم‌های افرازبندی، تقسیم داده‌ها در خوشه‌ها، به گونه‌ای است که داده‌های درون یک خوشه بیش‌ترین شباهت را به همدیگر داشته باشند؛ و درعین‌حال، بیش‌ترین فاصله و اختلاف را با داده‌های خوشه‌های دیگر داشته باشند. آن‌ها یک افراز منفرد از داده را تولید می‌کنند و سعی می‌کنند تا گروه‌های طبیعی حاضر در داده را کشف کنند. هر دو رویکرد خوشه‌بندی، دامنه‌های مناسب کاربرد خودشان را دارند. معمولاً روش‌های خوشه‌بندی سلسله مراتبی، نیاز به ماتریس مجاورت بین اشیاء دارند؛ درحالی‌که روش‌های افرازبندی، به داده‌ها در قالب ماتریس الگو نیاز دارند. نمایش رسمی مسئله خوشه‌بندی افرازبندی می‌تواند به صورت زیر باشد:
تعیین یک افراز از الگوها در گروه، یا خوشه، با داشتن الگو در یک فضای d-بعدی؛ به طوری که الگوها در یک خوشه بیش‌ترین شباهت را به هم داشته و با الگوهای خوشه‌های دیگر بیش‌ترین، تفاوت را داشته باشند. تعداد خوشه‌ها،، ممکن است که از قبل مشخص‌شده نباشد، اما در بسیاری از الگوریتم‌های خوشه‌بندی افرازبندی، تعداد خوشه‌ها باید از قبل معلوم باشند. در ادامه برخی از معروف‌ترین و پرکاربردترین الگوریتم‌های افرازبندی مورد بررسی قرار خواهند گرفت.
2-2-1-2-1. الگوریتم K-meansدر الگوریتم مراکز خوشه‌ها بلافاصله بعد از اینکه یک نمونه به یک خوشه می‌پیوندد محاسبه می‌شوند. به طور معمول بیشتر روش‌های خوشه‌بندی ترکیبی از الگوریتم جهت خوشه‌بندی اولیه خود استفاده می‌کنند [37, 47, 57]. اما مطالعات اخیر نشان داده‌اند که با توجه به رفتار هر مجموعه داده، گاهی اوقات یک روش خوشه‌بندی خاص پیدا می‌شود که دقت بهتری از برای بعضی از مجموعه داده‌ها می‌دهد [1, 54]. اما الگوریتم به دلیل سادگی و توانایی مناسب در خوشه‌بندی همواره به عنوان انتخاب اول مطالعات خوشه‌بندی ترکیبی مورد مطالعه قرار گرفته است. در شکل 2-10 شبه کد الگوریتم را مشاهده می‌کنید:
1. Place K points into the space represented by the objects that are being clustered.
These points represent initial group centroids.
2. Assign each object to the group that has the closest centroid.
3. When all objects have been assigned, recalculate the positions of the K centroids.
4. Repeat Steps 2 and 3 until the centroids no longer move. This produces a separation
of the objects into groups from which the metric to be minimized can be calculated
شکل 2-9. الگوریتم خوشه‌بندی افرازبندی
مقادیر مراکز اولیه‌ی‌ متفاوت برای الگوریتم می‌تواند منجر به خوشه‌بندی‌های مختلفی شود. به خاطر اینکه این الگوریتم مبتنی بر مربع خطا است، می‌تواند به کمینه محلی همگرا شود، مخصوصاً برای خوشه‌هایی که به طور خیلی خوبی از هم تفکیک نمی‌شوند، این امر صادق است. نشان داده شده است که هیچ تضمینی برای همگرایی یک الگوریتم تکراری به یک بهینه سراسری نیست [33]. به طور خلاصه می‌توان ویژگی‌های الگوریتم را به صورت زیر برشمرد:
1- بر اساس فاصله اقلیدسی تمامی ویژگی‌ها می‌باشد.
2- منجر به تولید خوشه‌هایی به صورت دایره، کره و یا ابر کره می‌شود.
3- نسبت به روش‌های دیگر خوشه‌بندی، ساده و سریع است.
4- همگرایی آن به یک بهینه محلی اثبات شده است، اما تضمینی برای همگرایی به بهینه سراسری وجود ندارد.
5- نسبت به مقداردهی اولیه مراکز خوشه‌ها خیلی حساس است.
2-2-1-2-2. الگوریتم FCMالگوریتم FCM اولین بار توسط دون [13] ارائه شد. سپس توسط بزدک [66] بهبود یافت. این متد دیدگاه جدیدی را در خوشه‌بندی بر اساس منطق فازی [62] ارائه می‌دهد. در این دیدگاه جدید، به جای اینکه داده‌ها در یک خوشه عضو باشند، در تمامی خوشه‌ها با یک ضریب عضویت که بین صفر و یک است، عضو هستند و ما در این نوع خوشه‌بندی، دنبال این ضرایب هستیم. در روش‌های معمول در جایی که ما داده داشته باشیم، جواب نهایی ماتریس خواهد بود که هر خانه شامل برچسب خوشه‌ی داده‌ی نظیر آن می‌باشد. ولی در این روش در صورت داشتن خوشه، جواب نهایی یک ماتریس خواهد بود که در آن هر ردیف شامل ضرایب عضویت داده‌ی نظیر به آن خوشه است. بدیهی است که جمع افقی هر ردیف (ضرایب عضویت یک داده خاص) برابر با یک خواهد بود. یک روش معمول جهت رسیدن به جواب‌هایی غیر فازی بر اساس نتایج نهایی الگوریتم فازی، برچسب‌زنی داده بر اساس آن ضریبی که مقدار حداکثر را در این داده دارد، می‌باشد. رابطه 2-6 معادله پایه در روش فازی است: [66]
(2-6) ,
در رابطه 2-6 متغیرm یک عدد حقیقی بزرگ‌تر از یک و درجه عضویت داده در خوشه j-ام می‌باشد، که خود ، i-امین داده d-بُعدی از داده‌ی مورد مطالعه می‌باشد و مرکز d-بعدی خوشه j-ام‌ است و هر روش معمول جهت اندازه‌گیری شباهت میان داده و مرکز خوشه می‌باشد. در روش خوشه‌بندی فازی مراکز خوشه () و درجه عضویت () با تکرار مکرر به ترتیب بر اساس رابطه‌های 2-7 و 2-8 به‌روزرسانی می‌شوند، تا زمانی که شرط توقف درست در آید. در این شرط مقدار یک مقدار توافقی بسیار کوچک‌تر از یک می‌باشد که مطابق با نوع داده و دقت خوشه‌بندی قابل جایگذاری خواهد بود. بدیهی است که هر چقدر این مقدار به سمت صفر میل کند درجه عضویت دقیق‌تر و مقدار زمان اجرا بیشتر خواهد بود [66].
(2-7)
(2-8)
مراحل اجرای الگوریتم در شبه کد شکل 2-11 شرح داده شده است:
1.Initialize matrix,
2.At k-step: calculate the centers vectors with

3.Update ,

4. If then STOP; otherwice returen to step 2.
شکل 2-10. الگوریتم فازی خوشه‌بندی
2-2-1-2-3. الگوریتم طیفیروش خوشه‌بندی طیفی که بر اساس مفهوم گراف طیفی [11] مطرح شده است، از ماتریس شباهت برای کاهش بعد داده‌ها در خوشه‌بندی استفاده می‌کند. در این روش یک گراف وزن‌دار بدون جهت به نحوی تولید می‌شود که رئوس گراف نشان‌دهنده‌ی مجموعه نقاط و هر یال وزن‌دار نشان‌دهنده‌ی میزان شباهت جفت داده‌های متناظر باشد. بر خلاف روش‌های کلاسیک، این روش، روی‌ داده‌ای پراکنده‌ در فضایی با شکل‌ هندسی غیر محدب، نتایج مطلوبی تولید می‌کند [63]. کاربرد این روش در محاسبات موازی [69, 70]، تنظیم بار [15]، طراحی VLSI [28]، طبقه‌بندی تصاویر [35] و بیوانفورماتیک [31, 59] می‌باشد.
در خوشه‌بندی طیفی از بردارهای ویژگی در ماتریس شباهت برای افراز مجموعه‌ داده استفاده می‌شود. در اغلب این روش‌ها، مقدار ویژه اولویت بردارها را تعیین می‌کند. ولی این نحوه‌ی انتخاب، انتخاب بهترین بردارها را تضمین نمی‌دهد. در اولین تحقیقی که در این زمینه توسط ژیانگ و گنگ [61] انجام شد، مسئله‌ی انتخاب بردارهای ویژگی مناسب جهت بهبود نتایج خوشه‌بندی پیشنهاد گردید. در روش پیشنهادی آن‌ها شایستگی هر یک از بردارهای با استفاده از تابع چگالی احتمال هر بردار تخمین زده می‌شود. وزنی به بردارهایی که امتیاز لازم را به دست آورندگ، اختصاص یافته و برای خوشه‌بندی از آن‌ها استفاده می‌شود. در کاری دیگر که توسط ژائو [64] انجام شده است، هر یک از بردارهای ویژه به ترتیب حذف می‌شوند و مقدار آنتروپی مجموعه بردارهای باقی‌مانده محاسبه می‌شود. برداری که حذف آن منجر به افزایش آنتروپی و ایجاد بی‌نظمی بیشتر در مجموعه داده شود، اهمیت بیشتری داشته و در رتبه بالاتری قرار می‌گیرد. سپس زیرمجموعه‌ای از مناسب‌ترین بردارها برای خوشه‌بندی مورد استفاده قرار می‌گیرند. الگوریتم خوشه‌بندی طیفی دارای متدهای متفاوتی جهت پیاده‌سازی است، که الگوریتم‌های برش نرمال، NJW، SLH وPF از آن جمله می‌باشد. در تمامی این روش‌ها، بخش اول، یعنی تولید گراف، مشترک می‌باشد. ما در ادامه ابتدا به بررسی بخش مشترک این روش‌ها می‌پردازیم. سپس به تشریح دو روش پر کاربرد برش نرمال و NJW می‌پردازیم.
در الگوریتم خوشه‌بندی طیفی، افراز داده‌ها بر اساس تجزیه‌ی ماتریس شباهت و به دست آوردن بردارها و مقادیر ویژه‌ی آن صورت می‌گیرد. مجموعه‌ی با داده‌یبعدی را در نظر بگیرید، می‌توان برای این مجموعه گراف وزن‌دار و بدون جهت را ساخت به صورتی که رئوس گراف نشان‌دهنده داده و یال‌ها که ماتریس شباهت را تشکیل می‌دهند بیانگر میزان شباهت بین هر جفت داده متناظر باشند. ماتریس شباهت به صورت رابطه 2-9 تعریف می‌شود:
(2-9)
تابع میزان شباهت بین دو داده را اندازه می‌گیرد. می‌تواند یک تابع گوسی به صورت باشد. که در آن فاصله‌ی بین دو نمونه را نشان می‌دهد و پارامتر مقیاس سرعت کاهش تابع با افزایش فاصله بین دو نمونه را مشخص می‌کند. در ادامه به بررسی دو الگوریتم خوشه‌بندی طیفی برش نرمال و NJW می‌پردازیم.
2-2-1-2-3-1. الگوریتم برش نرمالالگوریتم برش نرمال توسط شی و ملیک [35] برای قطعه‌بندی تصاویر ارائه شده است. در این روش، میزان تفاوت بین خوشه‌های مختلف و شباهت بین اعضا یک خوشه، بر اساس فاصله‌ی داده‌ها محاسبه می‌کند. رابطه 2-10 اشاره به مفهوم شباهت داده دارد که با استفاده از آن اقدام به ساخت گراف وزن‌دار می‌نماییم:
(2-10)
موقعیت i-امین داده (پیکسل در تصاویر) و بردار ویژگی از صفات داده (مانند روشنایی در تصاویر) می‌باشد. با کمک حد آستانه می‌توان میزان تنکی ماتریس شباهت را با توجه به تعداد اثرگذار داده‌های همسایه تعیین کرد. گام‌های این الگوریتم به صورت زیر می‌باشد:
محاسبه ماتریس درجه.
محاسبه ماتریس لاپلاسین.
محاسبه دومین بردار ویژگی متناظر با دومین کوچک‌ترین مقدار ویژه.
استفاده از برای خوشه‌بندی (قطعه‌بندی در تصاویر) گراف.
روش برش نرمال بیشتر در قطعه‌بندی تصاویر کاربرد دارد و معمولاً در خوشه‌بندی داده از سایر الگوریتم‌های خوشه‌بندی طیفی استفاده می‌کنند.
2-2-1-2-3-2. الگوریتم NJWایده الگوریتم استفاده از اولین بردار ویژه متناظر با بزرگ‌ترین مقدار ویژه ماتریس لاپلاسین است. مراحل این الگوریتم به صورت زیر می‌باشد: [51]
ساخت ماتریس شباهت با استفاده از رابطه 2-9.
محاسبه ماتریس درجه، و ماتریس لاپلاسین.
به دست آوردن اولین بردار ویژه متناظر با اولین بزرگ‌ترین مقدار ماتریسو تشکیل ماتریس ستونی.
نرمال سازی مجدد و تشکیل به طوری که همه سطرهای آن طول واحد داشته باشد.
خوشه‌بندی مجموعه داده بازنمایی شده با استفاده از.

2-2-1-2-4. الگوریتم خوشه‌بندی کاهشیالگوریتم خوشه‌بندی کاهشی یکی از سریع‌ترین الگوریتم‌های تک گذر، برای تخمین تعداد خوشه و مراکز آن‌ها در مجموعه‌ی داده می‌باشد. این مفهوم یعنی به جای تحت تأثیر قرار گرفتن محاسبات از ابعاد مسئله، متناسب با اندازه مسئله آن را انجام دهیم. با این وجود، مراکز واقعی خوشه الزاماً یکی از نقاط داده موجود در مجموعه داده نیست ولی در بیشتر موارد این انتخاب تخمین خوبی است که به صورت ویژه از این رویکرد در محاسبات کاهشی استفاده می‌شود. اگر هر نقطه از مجموعه داده به عنوان گزینه‌ای برای مرکز خوشه در نظر گرفته شود، معیار تراکم هر نقطه به صورت زیر تعریف می‌شود [79].
(2-11)
در رابطه بالا یک ثابت مثبت است، که نشان‌دهنده‌ی شعاع همسایگی (سایر نقاط داده که نزدیک‌ترین نقاط به این داده خاص هستند) می‌باشد، و نشان‌دهنده‌ی سایر داده‌های مجموعه، و نشان‌دهنده‌ی تعداد این داده‌ها است. از این روی، داده‌ای دارای بیش‌ترین مقدار تراکم می‌باشد که بیش‌ترین نقاط داده در همسایگی آن است. اولین مرکز خوشه بر اساس بزرگ‌ترین مقدار تراکم انتخاب می‌شود. بعد از این انتخاب میزان تراکم هر یک از نقاط داده به صورت زیر به‌روز می‌شود [79].
(2-12)
در رابطه بالا ثابت مثبت همسایگی را تعریف می‌کند که میزان کاهش تراکم قابل اندازه‌گیری را نشان می‌دهد. از آنجایی که نقاط داده در نزدیکی مرکز خوشه اول به طور قابل‌توجهی مقادیر چگالی را کاهش می‌دهند بعد از به‌روز کردن مقادیر تابع چگالی توسط رابطه بالا مرکز خوشه بعدی بر اساس داده‌ای که بزرگ‌ترین مقدار چگالی را دارد انتخاب می‌شود. این فرآیند آن قدر تکرار می‌شود تا به تعداد کافی مرکز خوشه ایجاد شود. پس از اتمام این فرآیند می‌توان توسط الگوریتم که مراکز داده در آن توسط فرآیند بالا به صورت دستی داده شده است (نه به صورت تصادفی)، داده‌ها را خوشه‌بندی کرد. شبه کد شکل زیر روند فرآیند بالا را نشان می‌دهد که در آن ابتدا مقادیر ثابت‌ها () و مجموعه داده به عنوان ورودی گرفته می‌شود و پس از ساخت مراکز داده مطابق با تعاریف بالا، این مراکز برای خوشه‌بندی در الگوریتم استفاده می‌شود [79].
Inputs Dataset, Constants
Output Clusters
Steps
1. Initialize constants and density values
2. Make a new cluster center.
3. Update density values
4. If the sufficient number of clusters are not obtained, go to 2.
3. Clustering the dataset by k-means, using fix centers.
شکل 2-11. خوشه‌بندی کاهشی
2-2-1-2-5. الگوریتم خوشه‌بندی Median K-Flatالگوریتم Median K-Flat یا به اختصار MKF مجموعه داده‌یرا به K خوشه‌ی افراز می‌کند که هر خوشه یک شبه فضای d-بُعدی تقریباً خطی می‌باشد. پارامتر‌ با فرض ماتریسی با ابعاد می‌باشد، که هر یک از خانه‌های آن تخمین شبه فضای خطی متعامد می‌باشد. قابل به ذکر است که می‌باشد. در این جا تخمین شبه فضای خوشه‌های را نام‌گذاری می‌کنیم. مطابق تعاریف بالا تابع انرژی برای افرازهای ‌ بر اساس شبه فضای به شکل زیر تعریف می‌شود [77].
(2-13)
این الگوریتم سعی می‌کند تا مجموعه داده را به خوشه‌های ‌تبدیل کند به نحوی که تابع انرژی کمینه باشد. تا وقتی که سطوح تخت اساسی به شکل شبه فضای خطی هستند ما می‌توانیم به صورت فرضی المان‌های X را در یک حوضه واحد نرمال کنیم به طوری که برای و تابع انرژی را به شکل زیر بیان کنیم: [77]
(2-14)
این الگوریتم برای کمینه‌سازی تابع انرژی الگوریتمMKF از روش کاهش گرادیان تصادفی استفاده می‌کند. مشتق تابع انرژی بر اساس ماتریس به شرح زیر است:
(2-15)
این الگوریتم نیاز به تطبیق بر اساس مؤلفه‌ی متعامد مشتق دارد. بخشی از مشتق که با شبه فضای موازی است به شرح زیر می‌باشد.
(2-16)
از این روی مؤلفه متعامد برابر است با رابطه 2-17 می‌باشد.
(2-17)
در رابطه بالا برابر با رابطه 2-18 است.
(2-18)
با در نظر گرفتن محاسبات بالا، الگوریتم MKF تصمیم می‌گیرد که داده تصادفی از مجموعه داده، عضو کدام باشد، و از این طریق شروع به چیدن داده‌ها می‌کند. آن گاه، الگوریتم تابع را به‌روز کند که در آن (مرحله زمانی) پارامتری است که توسط کاربر تعیین می‌شود. این فرآیند آن قدر تکرار می‌شود تا ضابطه همگرایی دیده شود. آنگاه هر نقطه از مجموعه داده به نزدیک‌ترین شبه فضای که تعیین‌کننده خوشه‌هاست اختصاص داده می‌شود. شبه کد زیر فرآیند الگوریتم MKF را نشان می‌دهد [77].
Input:
: Data, normalized onto the unit sphere, d: dimension of subspaces K: number of subspaces, the initialized subspaces. : step parameter.
Output: A partition of X into K disjoint clusters
Steps:
1. Pick a random point in X
2. Find its closest subspace , where
3. Compute by
4. Update
5. Orthogonalize
6. Repeat steps 1-5 until convergence
7. Assign each xi to the nearest subspace
شکل 2-12. شبه‌کد الگوریتم MKF [77]
2-2-1-2-6. الگوریتم خوشه‌بندی مخلوط گوسییک مخلوط گوسی یا همان را می‌توان ترکیب محدبی از چگالی‌های گوسی دانست. یک چگالی گوسی در فضای d-بُعدی به ازای میانگین، توسط ماتریس هم‌وردایی با ابعاد به صورت زیر تعریف می‌شود: [83]
(2-19)
در رابطه بالا پارامتر‌های و را تعریف می‌کند. از این روی مؤلفه به صورت زیر تعریف می‌شود:
(2-20)
در رابطه (2-20) پارامتر وزن مخلوط کردن و مؤلفه مخلوط می‌باشد. از آنجا که در مقایسه با تخمین چگالی غیر پارامتری، تعداد کمتری از توابع چگالی در تخمین چگالی مخلوط باید ارزیابی شود، از این روی ارزیابی چگالی کارآمدتر خواهد بود. علاوه بر آن، استفاده از اجرای محدودیت هموار کردن بر روی برخی از مؤلفه‌های مخلوط در نتیجه‌ی چگالی به ما اجازه می‌دهد تا چگالی مستحکم‌تری را تخمین بزنیم. الگوریتم حداکثر-انتظار یا همان به ما اجازه به‌روز کردن پارامتر‌های مؤلفه‌ی مخلوط را مطابق با مجموعه داده به ازای هر می‌دهد، به طوری که احتمال هرگز کوچک‌تر از مخلوط جدید نشود. به‌روز کردن الگوریتم می‌تواند در یک فرآیند تکراری برای تمامی مؤلفه‌های مطابق با رابطه‌های زیر انجام شود: [83]
(2-21)
(2-22)
(2-23)
(2-24)
در این تحقیق از روش پیشنهادی بومن و همکاران برای پیاده‌سازی الگوریتم مخلوط گوسی استفاده شده است. از آنجایی که روش پیاده‌سازی و توضیحات مربوط به الگوریتم مخلوط گوسی در روش ترکیب مبتنی بر مخلوط استفاده می‌شود از این روی در بخش روش‌های ترکیب نتایج با تابع توافقی آن را بررسی خواهیم کرد.
2-2-2. معیارهای ارزیابیدر یادگیری با ناظر ارزیابی راحت تر از یادگیری بدون ناظر است. برای مثال آن چیز که ما در رده‌بندی باید ارزیابی کنیم مدلی است که ما توسط داده‌های یادگیری به الگوریتم هوش مصنوعی آموزش داده‌ایم. در روش‌های با ناظر ورودی و خروجی داده معلوم است و ما بخشی از کل داده را برای آزمون جدا کرده و بخش دیگر را به عنوان داده یادگیری استفاده می‌کنیم و پس از تولید مدل مطلوب ورودی داده آزمون را در مدل وارد کرده و خروجی مدل را با خروجی واقعی می‌سنجیم. از این روی معیارهای بسیاری برای ارزیابی روش‌های با ناظر ارائه‌شده‌اند.
در یادگیری بدون ناظر روش متفاوت است. در این روش هیچ شاخص معینی در داده جهت ارزیابی وجود ندارد و ما به دنبال دسته‌بندی کردن داده‌ها بر اساس شباهت‌ها و تفاوت‌ها هستیم. از این روی برخلاف تلاش‌های خیلی از محققان، ارزیابی خوشه‌بندی خیلی توسعه داده نشده است و به عنوان بخشی از تحلیل خوشه‌بندی رایج نشده است. در واقع، ارزیابی خوشه‌بندی یکی از سخت‌ترین بخش‌های تحلیل خوشه‌بندی است [33]. معیارهای عددی، یا شاخص‌هایی که برای قضاوت جنبه‌های مختلف اعتبار یک خوشه به کار می روند، به سه دسته کلی تقسیم می‌شوند:
1- شاخص خارجی که مشخص می‌کند که کدام خوشه‌های پیداشده به وسیله الگوریتم خوشه‌بندی با ساختارهای خارجی تطبیق دارند. در این روش نیاز به اطلاعات اضافی مثل برچسب نقاط داده، داریم. آنتروپی یک مثالی از شاخص خارجی است.
2- شاخص داخلی که برای اندازه‌گیری میزان خوبی یک ساختار خوشه‌بندی بدون توجه به اطلاعات خارجی به کار می‌‌رود. یک نمونه از شاخص داخلی است.
3- شاخص نسبی که برای مقایسه دو خوشه‌بندی مختلف یا دو خوشه مختلف به کار می‌رود. اغلب یک شاخص خارجی یا داخلی برای این تابع استفاده می‌شود. برای مثال، دو خوشه‌بندی می‌توانند با مقایسه یا آنتروپی‌شان مقایسه شوند.


این فصل تعدادی از مهم‌ترین و رایج‌ترین روش‌های به‌کاررفته برای ارزیابی خوشه‌بندی را مرور خواهد کرد.
2-2-2-1. معیار SSEیک معیار داخلی ارزیابی خوشه‌بندی، مثل، می‌تواند برای ارزیابی یک خوشه‌بندی نسبت به خوشه‌بندی دیگر به کار رود. به علاوه، یک معیار داخلی اغلب می‌تواند برای ارزیابی یک خوشه‌بندی کامل یا یک خوشه تنها به استفاده شود. این اغلب به خاطر این است که این روش، سعی می‌کند تا میزان خوبی کلی خوشه‌بندی را به عنوان یک جمع وزن‌دار از خوبی‌های هر خوشه در نظر می‌گیرد. با استفاده از رابطه 2-25 محاسبه می‌شود [68].
(2-25)
کهیک نقطه داده در خوشه است و، j-امین ویژگی از داده X است. ، j-امین ویژگی از مرکز خوشه می‌باشد. برای مقایسه دو خوشه‌بندی مختلف روی یک داده با یک تعداد مشابه، تنها مقایسه مقدارهای متناظر آن‌ها کافی است. هر چه مقدار کمتر باشد، آن خوشه‌بندی بهتر خواهد بود. البته، وقتی تعداد نقاط داده در دو خوشه متفاوت باشند، مقایسه مستقیم از روی مقدار خوب نخواهد بود. بنابراین، یک خوشه معیار مناسب تری برای مقایسه است. رابطه 2-26 این معیار را نشان می‌دهد که در آن مقدار تعداد کل نمونه‌هاست [68].
(2-26)
تعداد درست خوشه‌ها در الگوریتم ، اغلب می‌تواند با استفاده از نگاه کردن به منحنی مشخص شود. این منحنی با رسم مقادیر به ازایهای مختلف به دست می‌آید. تعداد خوشه‌های بهینه با توجه به منحنی، ای است که به ازای آن نرخ کاهش مقدار، قابل چشم‌پوشی شود. شکل 2-13-ب منحنی را برای داده‌های شکل 2-13-الف، نشان می‌دهد.

(الف)
(ب)
شکل2-13. (الف) مجموعه داده با تعداد 10 خوشه واقعی. (ب) منحنی مربوطه [68]
همان طور که از شکل 2-13-ب برمی‌آید، برای مقادیرهای از صفر تا 10 شیب منحنی نسبت به بقیه مقادیر، تندتر می‌باشد. این امر نشان‌دهنده آن است که مقدار یک مقدار بهینه برای تعداد خوشه‌ها می‌باشد.

(الف)
(ب)
شکل2-14. (الف) مجموعه داده (ب) منحنی مربوطه [2]
شکل 2-14-ب نیز منحنی را برای داده‌های شکل 2-14-الف، نشان می‌دهد. مشاهده می‌شود که در این داده‌ها، چون تعداد خوشه‌ها نسبت به شکل 2-14-الف کاملاً گویا نیست، بنابراین، منحنی آن نیز نرم تر خواهد بود . اما با توجه به شکل 2-14-ب، می‌توان گفت که تعداد نسبتاً خوب باشد. چون منحنی برای های بعد از 8، دارای شیب کندتری خواهد شد. با توجه به نتایج فوق می‌توان گفت که اگرچه منحنی برای همه مسایل نمی‌تواند جواب بهینه برای تعداد بدهد، اما می‌تواند به عنوان یک معیار خوب برای این امر مطرح باشد.
2-2-2-2. معیار اطلاعات متقابل نرمال شدهمعیار اطلاعات متقابل () توسط کاور و توماس [71] معرفی شد که یک روش جهت اندازه‌گیری کیفیت اطلاعات آماری مشترک بین دو توزیع است. از آنجایی که این معیار وابسته به اندازه خوشه‌ها است در [54] روشی جهت نرمال سازی آن ارائه شده است. فرد و جین [19] روش نرمال سازی اطلاعات متقابل را اصلاح کردند و آن را تحت عنوان اطلاعات متقابل نرمال () ارائه داده‌اند. رابطه 2-27 اطلاعات متقابل نرمال شده را نشان می‌دهد[1, 2, 19] .
(2-27)
در رابطه 2-27 پارامتر کل نمونه‌ها است و یعنی افرازهایی که اندیس آن‌ها شامل i با تمام مقادیر j می‌باشد و یعنی افرازهایی که تمام مقادیر i با و اندیس j را شامل شود. از رابطه 2-28 محاسبه می‌شود [1, 2, 19].
(2-28)
, ,
در صورتی که دو افراز به صورت و که در آن کل داده و خوشه اول و خوشه دوم هر یک از افرازها باشد آنگاه نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد، نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد، نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد و نشان‌دهنده تعداد نمونه‌های مشترک موجود در و می‌باشد. در واقع و به ترتیب بیانگر کل نمونه‌های موجود در و می‌باشد [1].
شکل 2-15 دو افراز اولیه را نشان می‌دهد که میزان پایداری برای هر کدام از خوشه‌های به دست آمده هم محاسبه شده است. در این مثال الگوریتم به عنوان الگوریتم خوشه‌بندی اولیه انتخاب شده است و تعداد خوشه‌های اولیه برابر با سه نیز به عنوان پارامتر آن از قبل مشخص شده است. همچنین، در این مثال تعداد افرازهای موجود در مجموعه مرجع برابر با ۴۰ می‌باشد. در ۳۶ افراز نتایجی مشابه با شکل 2-15 (a) و در 4 حالت باقیمانده نیز نتایجی مشابه با شکل 2-15 (a) حاصل شده است [1].

شکل2-15. دو افراز اولیه با تعداد سه خوشه. (a) خوشه‌بندی درست (b) خوشه‌بندی نادرست [1]
از آن جایی که در مجموعه مرجع در ۹۰ % مواقع، داده‌های متراکم گوشه بالا‐چپ از شکل 2-15 در یک خوشه مجزا گروه‌بندی شده‌اند، بنابراین این خوشه باید مقدار پایداری بالایی را به خود اختصاص دهد. اگرچه این مقدار نباید دقیقاً برابر با یک باشد (چون در همه موارد این خوشه درست تشخیص داده نشده است)، مقدار پایداری با روش متداول اطلاعات متقابل نرمال شده مقدار یک را بر می‌گرداند. از آن جایی که ادغام دو خوشه سمت راست تنها در ۱۰ % موارد مانند شکل 2-15 (b) اتفاق افتاده است، خوشه حاصل باید مقدار پایداری کمی به دست آورد. اگر چه خوشه حاصل از ادغام دو خوشه سمت راستی، به ندرت ( ۱۰ % موارد) در مجموعه مرجع دیده شده است، مقدار پایداری برای این خوشه نیز برابر با یک به دست می‌آید. در اینجا مشکل روش متداول محاسبه پایداری با استفاده از اطلاعات متقابل نرمال شده ظاهر می‌شود. از آنجایی که معیار اطلاعات متقابل نرمال شده یک معیار متقارن است، مقدار پایداری خوشه بزرگ ادغامی سمت راست (با ۱۰ % تکرار) دقیقاً برابر با میزان پایداری خوشه متراکم گوشه بالا‐چپ (با ۹۰ % تکرار) به دست می‌آید. به عبارت دیگر در مواردی که داده‌های دو خوشه مکمل یکدیگر باشند، یعنی اجتماع داده‌های آن‌ها شامل کل مجموعه داده شود و اشتراک داده‌های آن‌ها نیز تهی باشد، مقدار پایداری برای هر دو به یک اندازه برابر به دست می‌آید. از دیدگاه دیگر، این اتفاق زمانی رخ می‌دهد که تعداد خوشه‌های تشکیل‌دهنده مجموعه در خوشه‌بندی مرجع عددی بیشتر از یک باشد. هر زمان که با ادغام دو یا بیشتر از خوشه‌ها به دست آید، منجر به نتایج نادرست در مقدار پایداری می‌شود. ما این مشکل را تحت عنوان مشکل تقارن در اطلاعات متقابل نرمال شده می‌شناسیم. در سال‌های اخیر روش‌هایی جهت حل این مشکل ارائه‌شده‌اند که یکی از آن‌ها را علیزاده و همکاران در [1, 9]ارائه داده‌اند که در‌ آن بزرگ‌ترین خوشه از بین مجموعه مرجع (که بیش از نصف نمونه‌هایش در خوشه مورد مقایسه وجود دارد) جایگزین اجتماع همه خوشه‌ها می‌شود که ما آن را با عنوان روش Max می‌شناسیم. روش دیگر جهت رفع این مشکل معیار APMM می‌باشد. در ادامه به بررسی این معیار می‌پردازیم [1, 8, 67].
2-2-2-3. معیار APMMبر خلاف معیارکه برای اندازه‌گیری شباهت دو افراز طراحی شده است معیار روشی برای اندازه‌گیری میزان شباهت یک خوشه در یک افراز است که توسط عـلیزاده و همکاران [8, 67] معرفی شده است رابطه 2-29 این معیار را معرفی می‌کند.
(2-29)
در رابطه 2-29 پارامتر خوشه i-ام در افراز می‌باشد و افراز متناظر با خوشه در خوشه‌بندی است. پارامتر تعداد کل نمونه‌های مجموعه داده و تعداد نمونه‌های مشترک بین خوشه‌های و می‌باشد. همچنین، تعداد خوشه‌های موجود در افراز می‌باشد. در این روش برای محاسبه پایداری خوشه از رابطه 2-30 استفاده می‌کنیم [8, 67].

pro12

2-12-3- استگانوگرافی در صدا36
2-12-3-1- محیط های صدا37
-12-3-2- ذخیره صدا37
2-12-3-3- وسایل پخش37
2-12-3-4- روش های مخفی کردن اطلاعات در صدا38
2-12-3-5- مخفی کردن اطلاعات در Echo39
2-11- ابزارهای پنهان نگاری و بازیابی40
2-12- استفاده از خط فرمان و ادغام فایل زیپ با گیف41
2-15-کاربردهای استگانوگرافی42
2-13- تبدیل فوریه44
2-14- تبدیل موجک45
2-15- تبدیل موجک گسسته (DWT)45
2-16- تجزیه مقدار منفرد48
2-17- مقدار منفرد چیست؟49
2-18- تعریف تجزیه مقدار منفرد49
2-18- مثالی از SVD51
2-19- خواص SVD در پردازش تصاویر دیجیتال51
2-20- پنهان نگاری دیجیتالی با استفاده از تجزیه مقدار منفرد53
2-20-1- الگوریتمهای مبتنی بر SVD خالص53
2-20-1-1- الگوریتم های مبتنی بر غیر بلوک54
2-20-1-2- الگوریتم های مبتنی بر بلوک55
2-20-2- SVD و الگوریتم های مبتنی بر دامنه تبدیل55
2-20-2-1- الگوریتم مبتنی بر SVD و DCT56
2-20-2-2- الگوریتم مبتنی بر SVD و DWT56
2-20-2-3- الگوریتم مبتنی بر SVD و FHT57
2-20-2-4- الگوریتم مبتنی بر SVD و Zernike57
فصل سوم: روش تحقیق
3-1- پنهان نگاری دیجیتالی59
3-2- پیشینه تحقیق61
3-3- روش های پنهان نگاری مبتنی بر SVD63
3-4- نهان نگاری مبتنی بر SVDچندگانه در حوزه موجک... (زارعی، 2014)63
3-4-1- الگوریتم جاسازی تصویر نهان نگاری63
3-4-2- الگوریتم استخراج تصویر نهان نگاری65
3-5- روش پیشنهادی پنهان نگاری مبتنی بر DWT-SVD67
3-5-1- الگوریتم جاسازی پنهان نگاری68
3-5-2- الگوریتم استخراج پنهان نگاری70

فصل چهارم: محاسبات و یافته های تحقیق
4-1- پیاده سازی الگوریتم72
4-1-1- ابزار مورد استفاده برای آزمایش و پارامترهای اندازه گیری72
4-2- نتایج پیاده سازی74
4-3- مقایسه با سایر روش های پنهان نگاری78
فصل پنجم: نتیجه گیری و پیشنهادات
نتیجه گیری و پیشنهادات74
منابع و مآخذ84
پیوست (الف) کدهای پیاده سازی شده به زبان متلب89
Abstract92
فهرست جداول
جدول 2-1 مقایسه پنهان نگاری، نهان نگاری و رمزنگاری22
جدول 2-2 ارزش های منفرد از دو تصویر52
جدول 4-1 MSE و PSNR با استفاده از روش پنهان نگاری پیشنهاد شده DWT-SVD78
جدول 4-1 MSE و PSNR با استفاده از روش نهان نگاری زارعی (2014)78
فهرست اشکال
شکل 2-1 Johannes Trithemius و نمونه ای از کتابهایش12
شکل 2-2 طبقه بندی انواع واترمارکینگ براساس مدل دی ولیچساور15
شکل 2-3 شکل های پنهان سازی اطلاعات توسط پتیتکولاس26
شکل 2-4 تصویر لنا – تصویر اصلی و تصویر فیلتر شده52
شکل3-1 چارچوب استگانوگرافی سرپرست فعال60
شکل 3-2 استگانوگرافی مدرن61
شکل 3-3 الگوریتم جاسازی نهان نگاری زارعی 64
شکل 3-4 الگوریتم استخراج نهان نگاری زارعی65
شکل 3-5 فلوچارت الگوریتم پرندگان در الگوریتم پیشنهادی66
-21863051652905تصویر رنگی پوشش
00تصویر رنگی پوشش
شکل 3-6 الگوریتم جاسازی به روش DWT-SVD69
-21863051652905تصویر رنگی پوشش
00تصویر رنگی پوشش
شکل 3-7 الگوریتم استخراج به روش DWT-SVD70
شکل 4-1 تصویر پوششی72
شکل 4-2 تصویر مخفی72
شکل 4-3 تصویر پنهان نگاری شده73
شکل 4-4 تصویر مخفی استخراج شده73
شکل 4-5 تصویر پنهان نگاری شده توسط الگوریتم DWT-SVD پیشنهاد شده74
شکل 4-6 تصویر پنهان نگاری شده توسط الگوریتم زارعی74
شکل 4-7 حمله Salt & paper بر روی الگوریتم DWT-SVD پیشنهاد شده75
شکل 4-8 حمله Salt & paper بر روی الگوریتم زارعی75
شکل 4-9 حمله Rotation بر روی الگوریتم DWT-SVD پیشنهاد شده76
شکل 4-10 حمله Rotation بر روی الگوریتم زارعی 76
شکل 4-11 حمله gaussian بر روی الگوریتم DWT-SVD پیشنهاد شده76
شکل 4-12 حمله gaussian بر روی الگوریتم زارعی77
شکل 4-13 حمله Cropping بر روی الگوریتم DWT-SVD پیشنهاد شده77
شکل 4-14 حمله Cropping بر روی الگوریتم زارعی77
فصل اول
2505075465899500مقدمه و کلیات تحقیق
232854567043300023285456179185002505075432943000
1-1- مقدمه
پیشرفت سریع اینترنت و انقلاب اطلاعات دیجیتالی باعث تغییرات مهمی در کل جامعه شده است. داده های مولتی مدیا که در فرمت های دیجیتالی موجودند (تصویر، ویدئو، صدا) زمینه های چالش برانگیزی از نوآوری را باز کرده اند. نرم افزارهای ساده کاربردی و کاهش قیمت وسایل دیجیتالی این امکان را برای همه ی مردم در سراسر جهان فراهم کرده که داده های مولتی مدیا را براحتی ایجاد و ویرایش کنند.
پهنای باند ارتباطات اینترنتی و انتقال تقریباً بدون خطای اطلاعات ایجاد کپی های یکسان از داده ها را آسان کرده است، به عکس فایل های آنالوگ (نوارهای کاست، نوارهایVHS )، فایل های دیجیتالی بر اثر کپی های زیاد کیفیتشان کم نمی شود، در نگاه اول این مزیت فایل های دیجیتالی به نوع آنالوگ آن است ولی اشکال در حفظ حقوق کپی رایت می باشد.[6]
روش های قدیم حقوق کپی رایت برای محافظت از داده های مولتی مدیا دیگر کافی نیست یک مکانیسم ساده ی حفاظت که براساس تعبیه اطلاعات در بیت های سرآمد یک فایل دیجیتالی بود، ناکارآمد شده زیرا این اطلاعات می تواند به آسانی با تغییر در فرمت داده بی اثر شود بدون آنکه هیچ اثری روی کیفیت فایل بگذارد.
رمزگذاری یک فایل مولتی مدیای دیجیتالی از دسترسی داشتن به آن فایل تا زمانی که کلید آشکار سازی مناسب را در اختیار نداشته باشند جلوگیری می کند، بنابراین مؤلف می تواند برای تحویل مولتی مدیا بصورت قابل مشاهده پول دریافت کند و هر مشتری که حق تایپ را پرداخت کرده قادر خواهد بود فایل دریافت شده را بطور مناسب رمزگشایی کرده و استفاده نماید، اما اشکال در این است که وقتی یکبار فایل مولتی مدیا رمز گشایی شد آن فایل می تواند بدون مانع مکرراً کپی شده و توزیع گردد.[6]
پنهان نگاری دیجیتالی یک راه حل دیگر را برای حل این مشکل فراهم می کند. پنهان نگاری معادل فارسی واژه ی استگانوگرافی می باشد که در اصل کلمه ای یونانی بوده و از دو کلمهSteganos به معنای پنهان کردن و Graphy به معنای نوشتن تشکیل شده است.[7,8] اساس پنهان نگاری بر این فرض استوار است که پیام پنهان شده در اسناد یا تصویر توسط شخص سوم قابل تشخیص و یا بازیابی نباشد. پوشش می تواند یک فایل صوتی، صدا، متن و یا ویدئو و ... باشد.
با توجه به اینکه پنهان نگاری در طیف گسترده ای از رسانه های دیجیتالی و با اهداف خاصی طراحی می شوند، لذا با توجه به موارد کاربردی در دسته های مختلفی طبقه بندی می شوند. با وجود تفاوت در اعمال روش های پنهان نگاری دیجیتال، همه روش ها در داشتن امنیت بالا دارای نقطه اشتراک هستند با توجه به دامنه وسیع کاربرد تکنیک های پنهان نگاری آنها را می توان به صورت زیر طبقه بندی نمود:
طبقه بندی با توجه به حوزه کاری (حوزه فرکانس یا حوزه مکان) با توجه به نوع اسناد (متن، صدا و تصویر) و با توجه به ادارک و آگاهی انسانی (سیستم بینایی و یا شنوایی)؛ با توجه به برنامه های کاربردی (مبتنی بر منبع یا مبتنی بر مقصد).[9]
استگانوگرافی دارای روش های گسترده ای برای مخفی کردن اطلاعات در رسانه های مختلف است. در میان این روش ها می توان به جوهرهای نامرئی، امضای دیجیتالی، کانالهای پیچیده و ارتباطات طیف گسترده اشاره کرد. امروزه به خاطر وجود تکنولوژی پیشرفته از استگانوگرافی در متن، تصویر، صدا، سیگنالها و خیلی رسانه های دیگر استفاده می کنند. با این حال استگانوگرافی دارای عیوبی نیز می باشد. به طور مثال، برای فرستادن چند بیت اطلاعات، احتیاج به فرستادن تعداد بسیار زیادی بیت بدون اطلاعات هستیم و تلفات آن زیاد است. یا اینکه به محض لو رفتن الگوریتم یک روش، دیگر از آن روش نمی توان در مخفی کردن اطلاعات استفاده کرد.[2] به صورت کلی در سیستم های اختفاء اطلاعات سه عنصر مقاومت، امنیت، و ظرفیت دخیل هستند. در روش های پنهان نگاری عناصر ظرفیت و امنیت اهمیت اصلی را دارند. تصاویر مهمترین رسانه مورد استفاده به خصوص در اینترنت هستند و درک تصویری انسان از تغییرات در تصاویر محدود است. تصاویر نوعی رسانه پوششی مناسب در پنهان نگاری محسوب می شوند و الگوریتم های پنهان نگاری متعددی برای ساختارهای مختلف تصاویر ارائه شده است.[2] به طور کلی روش های پنهان نگاری در تصویر از الگوریتم جاسازی بیت ها و الگوریتم استخراج تشکیل شده اند. برخی روش های روش های رایج در استگانوگرافی فایلهای تصویری عبارتند از [10] :
جایگزینی بیت کمترین ارزش (LSB)
همبستگی بر پایه آستانه
همبستگی بر پایه مقایسه
روش طیف گسترده
مقایسه ضریب باند متوسط DCT
مقایسه – همبستگی مستقر در باند متوسط DCT
طیف گسترده در دامنه موجک
با توجه به کارهای گذشته ای که در این زمینه انجام شده است، در این تحقیق قصد داریم تا الگوریتم های پنهان نگاری در تصاویر دیجیتالی با استفاده از تجزیه مقدار منفرد را توسعه دهیم. برای این منظور از روش های پنهان نگاری ترکیبی که شامل تجزیه مقدار منفرد و تبدیل موجک گسسته می باشد استفاده خواهیم کرد.
1-2- بیان مساله
متن، تصویر، صوت و ویدئو را می توان به صورت داده های دیجیتال بیان کرد. فراگیری فزاینده و رشد سریع استفاده از اینترنت انسان ها را به سوی جهان دیجیتال و ارتباط از طریق داده های دیجیتال سوق داده است. هر جا سخن از ارتباط به میان آید، مساله امنیت کانال ارتباطی نیز مطرح می گردد. در واقع، در یک کانال ارتباطی، استگانوگرافی یا همان پنهان نگاری روشی از ارسال اطلاعات محرمانه است به نحوی که وجود خود کانال در این ارتباط مخفی بماند. روش استگانوگرافی کامپیوتری، روشی از استگانوگرافی است که امنیت اطلاعات را در رسانه دیجیتال فراهم می سازد و هدف آن درج و ارسال پیام محرمانه از طریق رسانه دیجیتال است بگونه ای که هیچ ظنّی مبنی بر ارسال اطلاعات برانگیخته نشود. پیام محرمانه می تواند به صورت یک تصویر یا متن و یا سیگنال کنترل و خلاصه هر چیزی که بتوان بصورت یک رشته بیتی از صفر و یک بیان شود، باشد. قابل توجه است، امکان دارد، پیام محرمانه قبل از استگانوگرافی تحت مراحل فشرده سازی و یا رمزنگاری نیز قرار گیرد. استگانوگرافی دارای سه پارامتر ظرفیت اطلاعات وارد شونده، کیفیت ادراکی و مقاومت است. بدون شک پیشینه سازی تؤام همه ی این پارامترها امکان پذیر نیست و تنها بسته به کاربرد می باید مصالحه ای بین این پارامترها ایجاد کرد. روش های استگانوگرافی کامپیوتری، اساساً باید به گونه ای باشد که به هیچ وجه تصویر استگانوگرافی قابل کشف از تصویر اصلی نباشد. این چنین روش هایی از استگانوگرافی می توانند برای اهداف مختلفی مورد استفاده قرار گیرند. برای مثال، کاربرد دیگر استگانوگرافی علاوه بر ارتباطات امنیتی، کمک در ایجاد بانک اطلاعاتی است. در این کاربری، وظیفه استگانوگرافی همراه کردن اطلاعات اضافی و مربوطه به تصویر با آن به منظور یکپارچه سازی اطلاعات و تسهیل در ذخیره سازی است. چنین کاربردهایی از استگانوگرافی، وجود اطلاعات در تصویر عموماً معلوم بوده و سیستم بسته فرض می شود و هیچگونه نگرانی از حمله به تصویر از خارج به منظور کشف اطلاعات وجود ندارد. در این موارد، روش های غیر مقاوم مناسب به نظر می رسند. از طرف دیگر در کاربردهای اطلاعاتی، تصویر دیجیتال به عنوان سیگنال حامل بوده و پیام محرمانه می تواند به صورت نامه های بسیار محرمانه نقشه های نظامی و تصاویر مخصوصی باشد در این کاربردها تاکید اصلی بر این است که ناظر سوم به هیچ وجه متوجه وجود اطلاعات در تصویر نشده و نتواند تداخلی در کانال ارتباطی ایجاد کند یا موفق به کشف پیام شود. در این کاربردها، می توان از شکل های مقاوم یا از روش های غیر مقاوم استفاده کرد.
1-3- ضرورت و اهمیت تحقیق
به دلیل رشد وسیع ارتباطات دیجیتال و سهولت در رد و بدل نمودن اطلاعات پرونده ها از طریق شبکه های کامپیوتری نظیر اینترنت و همچنین حجم بسیار زیاد اطلاعات رد و بدل شده، پنهان نگاری کاربرد مناسبی پیدا کرده است و استفاده از آن روز به روز بیشتر می شود. از طرفی برای جلوگیری اطلاع از ارتباطات باندهای تروریستی یا افراد بزهکار و یا خروج اطلاعات محرمانه از شرکت ها یا سازمان ها به منظور ارزیابی امنیتی سیستم های پنهان نگاری که توسط نیروهای نظامی یا امنیتی استفاده می شوند، به تحلیل پنهان نگاری نیاز است. هر چقدر پهنای باند اینترنت برای انتقال پرونده های بزرگ نظیر پرونده های ویدئویی، بیشتر می شود، انتقال اطلاعات غیر عادی و مشکوک نیز ساده تر شده و غیر قابل آشکارتر می شود. در طی سالهای اخیر تلاش هایی برای طراحی الگوریتم های تحلیل انجام شده است. اکثر پژوهشگران با توجه به راه حل های پیشنهادی خود بر این باورند که سایر الگوریتم های پنهان نگاری دارای ضعف هستند و اختلاف آرا در این زمینه وجود دارد. لذا مقایسه و بررسی الگوریتم های پیشنهادی با سایر روش ها برای تحقیق در نظر گرفته شده است.

1-4- اهداف تحقیق
به طور کلی اهداف تحلیل پنهان نگاری و یا حالت هایی که تحلیل انجام می گیرد شامل اثبات وجود یا عدم وجود پیغام پنهانی، تخریب پیغام، استخراج پیغام، تغییر پیغام، استخراج کلید عمومی و کلید رمز، یافتن الگوریتم پنهان نگاری می باشد. در میان روش های ابتکاری توسعه یافته برای حل این مشکل، تکنیک پنهان نگاری تصاویر دیجیتال مبتنی بر تجزیه مقدار منفرد یکی از پرکاربردترین روش ها است. روش های مشابه دارای معایبی از جمله برگشت پذیر بودن و تشخیص مثبت- کاذب و ناتوان بودن در برابر برخی حملات از جمله اعوجاج هندسی و ... است. یکی از راه های مقابله با دستکاری غیر مجاز در تصاویر دیجیتالی استفاده از تکنیک پنهان نگاری مبتنی بر تجزیه مقدار منفرد می باشد. هدف اصلی این تحقیق، بهبود الگوریتم پنهان نگاری در تصاویر دیجیتال با استفاده از تجزیه مقدار منفرد می باشد. روش پیشنهادی از ترکیب تجزیه مقدار منفرد بهمراه تبدیل موجک گسسته بهره می برد و هدف آن امنیت تصاویر دیجیتالی است که در مقایسه با دیگر روش ها کارایی بیشتری داشته باشد. همچنین بدلیل ایجاد تخریب هایی که توسط کاربران غیر مجاز بر روی تصاویر پنهان نگاری شده انجام می گیرد و گاهاً باعث لو رفتن اطلاعات پنهان نگاری با تخریب داده های اصلی می شوند. لذا از اهداف دیگر الگوریتم پیشنهادی افزایش توانمندی الگوریتم در برابر حملات تخریب کننده و برطرف کردن مشکل نرخ هشدار – کاذب است.
1-5- سوالات تحقیق
استفاده از الگوریتم های پنهان نگاری در تصاویر دیجیتالی باعث می شود تا از اطلاعات محرمانه حفاظت شود و آن را در برابر استفاده غیر مجاز کاربران مصون بدارد. با توجه به عملکرد این نوع الگوریتم های پنهان نگاری سوالات در این زمینه مطرح می کنیم و در این طرح به آن ها می پردازیم:
چگونه می توان الگوریتم های پنهان نگاری در تصاویر دیجیتال را با استفاده از روش تجزیه مقدار منفرد بهبود بخشید؟
چطور می توان الگوریتم پنهان نگاری مبتنی بر تجزیه مقدار منفرد و تبدیل موجک گسسته در تصاویر دیجیتال را در برابر حملات تخریب کننده معمول از قبیل چرخش، تغییر اندازه، برداشت و ایجاد نویز توانمند و مقاوم کرد؟

1-6- فرضیه های تحقیق
الگوریتم پنهان نگاری پیشنهاد شده، روش پنهان نگاری مبتنی بر تجزیه مقادیر منفرد را توسعه داده است. این روش یک الگوریتم ترکیبی است که از تجزیه مقدار منفرد و تبدیل موجک گسسته بهره می برد.
بمنظور حفاظت از افشای اطلاعات محرمانه، الگوریتمی ارائه شده که در برابر رایج ترین حملات و به طور خاص، در برابر حملات اعوجاج هندسی توانمند و ایمن می باشد.
این الگوریتم از روش اعداد تصادفی در تصویر پنهان نگاری، از یک تصویر با متن معنی دار استفاده می کند. بنابراین کیفیت تصویر پنهان نگاری استخراج شده عملکرد الگوریتم را تضمین می کند.
در روش پیشنهادی در استخراج تصویر پنهان نگاری کور می باشد به این صورت که حمله کننده از نوع الگوریتم به کاررفته در فرایند استگانوگرافی اطلاعی ندارد.
1-7- کلمات کلیدی
1-7-1- استگانوگرافی
استگانوگرافی یا پنهان نگاری دانشی است برای پنهان کردن داده یا فایلی در فایل دیگر، بطوری که فقط افراد آگاه با ابزار لازم بتوانند به آن دست یابند. استفاده از این روش در مواردی بسیار عالی و کاربردی است. برخلاف رمزگذاری که فایل حفاظت شده را کاملاً حساس جلوه می‌دهد و جلب توجه می کند، این روش از ناآگاهی افراد، برای جلوگیری از دستیابی آن‌ها به اطلاعات خاص بهره می برد. پنهان نگاری خود شاخه ای از دانشی به نام ارتباطات پوشیده است. دانش ارتباطات پوشیده خود شامل چندین شاخه از جمله رمز نگاری، ته نقش نگاری و ... می باشد.
1-7-2- حوزه تبدیل
تکنیک های پنهان نگاری می توانند به دو دسته تقسیم بندی شدند: تکنیک های دامنه فضایی (مکان) و تکنیک های دامنه تبدیل (فرکانس). در شکل های دامنه فضایی برای گنجاندن شی دیجیتال مورد نظر مقادیر پیکسل ها بطور مستقیم دستکاری می شود. این روش پیچیدگی کمتری دارند، شکننده ترند و قوی نیستند، اما در شکل های حوزه تبدیل (فرکانس) ابتدا تصاویر به یکی از حوزه های فرکانسی انتقال یافته و سپس پنهان نگاری با دستکاری مقادیر در حوزه فرکانس انجام می گیرد و در نهایت تصویر به حوزه مکان بازگردانده می شود. در مقایسه با تکنیک های دامنه فضایی ثابت شده است که تکنیک های حوزه تبدیلی در دست یافتن به الگوریتم پنهان نگاری دیجیتال از لحاظ غیر قابل مشاهده بودن و نیازمندی های استحکام بهتر می باشد. انتقال های حوزه تبدیل که عموماً در الگوریتم های پنهان نگاری تصاویر دیجیتال مورد استفاده قرار می گیرد شامل انتقال های زیر است: دامنه تبدیل کسینوسی گسسته (DCT)، دامنه تبدیل فوریه گسسته (DFT)، دامنه تبدیل موجک (DWT)، دامنه تبدیل سریع هادامارد (FHT) و تجزیه مقدارمنفرد (SVD) و ... می باشد.
1-7-3- تجزیه مقدار منفرد
روش های متعدد پنهان نگاری در حوزه تبدیل وجود دارند. تجزیه مقدار منفرد یا تجزیه مقدارهای تکین (SVD) یکی ازاین موارد است. این روش توسط بلترامی در سال 1873 و جردن در سال 1874 مستقلاً ابداًع شد و بعدها در سال 1930 یانگ آن را برای ماتریس های مستطیل شکل گسترش داد. تا سال 1960 به دلیل نیاز به تکنیک های پیچیده عددی، از SVD به عنوان یک ابزار محاسباتی استفاده نمی شد. ژنه کلوب آن را به عنوان یک ابزار سودمند در موارد گوناگون معرفی کرد.[11] SVD یکی از مفیدترین ابزارهای جبر خطی برای کاربردهای مختلف مانند فشرده سازی تصویر و سایر زمینه های پردازش تصویر و سیگنال می باشد. بطور کلی طرح های پنهان نگاری مبتنی بر تجزیه مقدار منفرد با توجه به سادگی در پیاده سازی و برخی ویژگی های جذاب ریاضی، محبوبیت زیادی را به دست آورده اند.
1-7-4- تبدیل موجک گسسته
تبدیل موجک گسسته (DWT) یک ابزار ریاضی مناسب برای نمایش و پردازش تصویر دیجیتالی است. این تبدیل در حوزه فرکانس صورت می گیرد اصولاً تبدیلاتی که در حوزه فرکانس انجام می شوند پیچیدگی بیشتری دارند و در برابر تخریب ها و حملات مقاوم تر عمل می کنند.

1-8- نوآوری تحقیق
با توجه به تلاش هایی که در زمینه پنهان نگاری تصاویر دیجیتالی صورت گرفته، نوآوری تحقیق پیشرو ارائه روش پیشنهادی پنهان نگاری تصاویر دیجیتال با استفاده از روش ترکیبی تجزیه مقدار منفرد و تبدیل موجک گسسته 1- سطحی می باشد که همانطور که در نتایج این تحقیق نشان داده شده است در امنیت و حفظ تصویر مخفی موثر واقع شده است.
1-9- ساختار پژوهشدر این پایان نامه در فصل اول مقدمه و کلیات تحقیق ارائه شده است، در ادامه بحث فصل دوم ادبیات و پیشینه تحقیق، مفاهیم کلی پنهان نگاری دیجیتالی، تجزیه مقدار منفرد و تبدیل موجک گسسته ارائه می شود و در فصل سوم روش تحقیق شرح داده شده می شود، در فصل چهارم محاسبات و یافته های تحقیق روش پیشنهادی ارائه می گردد و سرانجام فصل پنجم نتیجه گیری و پیشنهادات بیان شده است.

فصل دوم
ادبیات و پیشینه تحقیق
226568040170100023679156535420002480945585343000255714562236350022656804645025002-1- تاریخچه
پنهان کردن اطلاعات تاریخچه ی کهنی دارد. جوهرهای نامرئی، کدهای رمزی، پیغام های مخفی و به طور کلی استگانوگرافی همواره مورد توجه بشر بوده است. [12]اولین استفاده از تکنیک های پنهان نگاری توسط هرودوت که یک مورخ یونانی است در کتابش «تاریخها» شرح داده شده است. [13]داستان آن به حوالی سالهای 440 قبل از میلاد برمی گردد، وقتی که حاکم یونان به دست داریوش در شوش زندانی شده بود ولی بایست پیامی را بصورت محرمانه برای برادر خوانده اش در میلتیوس ارسال کند. به همین منظور موی سر غلامش را تراشید و پیام خود را روی سرش خال کوبی نمود و وقتی موهای غلام به اندازه کافی رشد نمود او را عازم مقصد نمود و جالب است که در اوایل قرن بیستم نیز از همین روش جاسوسان آلمانی استفاده نمودند. داستان دیگر نیز مربوط به زمانه همین پادشاه است. دمراتوس، یک یونانی در دربار ایران بود و یک پیام مخفی را برای اسپارتا ارسال کرد تا او را از حمله کوروش آگاه سازد. او ابتدا موم روی لوح را برداشت و پیام را روی چوب زیر موم نوشت سپس پیام را با موم دوباره مخفی کرد. به گونه ای که لوح دوباره بصورت یک لوح مفید که هنوز هیچ پیامی روی آن نوشته نشده بود درآمد. به همین ترتیب روش های دیگری توسط آلفیس استفاده شد. روش های مخفی سازی پیام در پاشنه کفش پیکهای خبررسان، گوشواره های زنان و نوشتن متن داخل لوح های چوبی که توسط گچ سفید پوشانده می شدند از این جمله بودند. همچنین او در روش دیگری پیشنهاد کرد که می توان جهت مخفی سازی یک پیام سوراخهایی در بالا و پایین حروف ایجاد و یا ارتفاع حروف مورد نظر را در یک متن که ما آن را متن پوششی می نامیم تغییر داد. سوراخ های ایجاد شده روی حروف و یا زیر آن به علت تضاد رنگ سیاه حروف و سفید کاغذ اصولاً محو می شدند و قابل دیدن نمی باشند. این روش تا قرن 17 میلادی نیز استفاده می شد. اما در سالهای بعدی توسط وایلکنس توسعه یافت. او از نقاط بسیار کوچک که با جوهرهای قابل رؤیت ایجاد می کرد بجای سوراخ کردن کاغذ استفاده می نمود. جوهرهای نامریی نیز یکی از عمومی ترین ابزارها برای پنهان نگاری هستند و در روم باستان حتی در جنگ جهانی دوم مورد استفاده قرار می گرفتند. یکی از پیشگامان پنهان نگاری تریتمیوس روحانی آلمانی بود و کتابی پیرامون پنهان نگاری با عنوان «Steganographia» نوشت که در زمان وی منتشر نشد.[8] اولین کتاب واقعی در این زمینه را اسکات در سال 1665 در 400 صفحه با نام Schola Steganographica نوشت. [14] او در این کتاب به چگونگی مخفی کردن پیام در لابلای نتهای موسیقی اشاره کرده است.

شکل 2-1 Johannes Trithemius و نمونه ای از کتابهایش [14]
در قرن 15 و 16، پنهان نگاری توسعه زیادی پیدا نمود. در سال 1875 بروستر پیشنهاد کرد که می توان پیام های محرمانه را در فواصل خالی در حدود یک نقطه پنهان نمود.
در اوایل قرن بیستم و در طی جنگ بور در آفریقای جنوبی یک پیشاهنگ انگلیسی نقشه هایش را روی نقاشیهایی از بالهای پروانه مخفی می کرد و برای فرمانده اش می فرستاد. در جنگ بین روسیه و ژاپن در سال 1905، تصاویر میکروسکوپی در گوش، سوراخ های بینی و یا زیر ناخن انگشتان جاسازی می شد. در جنگ جهانی اول پیامهایی که بین جاسوسان رد و بدل می گشت محدود به یک سری نقاط بسیار ریز بود که در چندین مرحله کوچک شده بودند و در بالای نقطه ها و یا علامت های کاما که در یک جمله استفاده می گشتند قرار می گرفتند و بگونه ای که هیچ توجهی را جلب کنند.
در جنگ جهانی دوم نیز توجه زیادی به پنهان نگاری شد و تجربیات زیادی در این زمینه کسب شد. در ابتدای جنگ از جوهرهای نامریی استفاده می شد ولی بعداً از حروف و پیام های معمولی برای مخفی کردن پیام اصلی استفاده کردند.
اولین روش های پنهان نگاری دیجیتال در دهه ی 80 مطرح شدند و روش های جدیدتر همه مربوط به یک دهه ی اخیر هستند. با ارائه هر الگوریتم، روشی نیز بر ضد آن طراحی می شود و روش های قدیمی جای خود را به روش های جدیدتر می دهند. البته دولت آمریکا تا سال 1999 از ترس استفاده ی تروریستی و جاسوسی کشورهای دیگر، استفاده تجاری از پنهان نگاری را ممنوع کرده بود ولی با فشار شرکتها و محققان آمریکایی و طی یک دادخواهی چهار ساله اجازه ی استفاده مشروط از این فناوری در کاربردهای عمومی را صادر کرد. [12,15,16]
2-2- معرفی
همزمان با پیشرفت تکنولوژی و رشد روز افزون اینترنت ، امکان استفاده غیر مجاز از اطلاعات افزایش یافته است، لذا نیاز مبرم به روش های جدید به منظور حفظ حریم اشخاص و شرکت ها در این حوزه احساس می شود. رمزنگاری و استگانوگرافی علومی هستند که به بشر در زمینه امنیت اطلاعات کمک می نمایند. در حوزه رمز نگاری، ابتدا داده به صورتی که برای مهاجم نامفهوم باشد، تغییر شکل می یابد و سپس ارسال می شود. تغییر شکل به گونه ای است که امکان دستیابی مهاجم به اطلاعات بدون داشتن کلید رمز غیرممکن خواهد بود. اما در حوزه نهان نگاری، ابتدا داده درون یک سیگنال پوشاننده برای ایجاد «سیگنال نهان نگاری شده» مخفی می شود سپس این سیگنال، ذخیره یا مخابره خواهد شد. بنابراین وجود داده و حتی انتقال آن مخفی خواهد ماند.
مبنای انواع کریپتوگرافی و استگانوگرافی به این دلیل است که ارتباطات الکترونیکی در رسانه های ناامنی نظیر ایمیل و صفحات وب انجام می شود. در واقع، بیشتر دولتها مقرراتی دارند که به آنها اجازه می دهد هر نوع ارتباطات در اینترنت و شبکه های تلفنی سوییچ عمومی را کنترل نمایند. این موضوع شامل کنترل ایمیل ها، صفحات وب، تلفن های عمومی و سایر شکل های ارتباط الکترونیکی می باشد.[17] آژانس های امنیتی دولتها از سخت افزارها و نرم افزارهای ویژه برای دریافت سیگنالهای الکترونیکی در مخابرات ماهواره های بین المللی استفاده می کنند. سپس کامپیوترها اطلاعات مشکوک در ارتباط تلفنی را براساس کلید واژه هایی نظیر «بمب» با تطبیق یک الگوی ویژه صوتی فیلتر می کنند.[18]
برنامه های استگانوگرافی گسترده ای بصورت آماده در اینترنت قابل دسترسی هستند که به تروریستها یا افراد سودجو کمک می کند تا اطلاعات با ارزش خود را از طریق اینترنت پخش کنند بدون اینکه آژانس های امنیتی دولت ها متوجه شوند. در حال حاضر برخی از گروههای امنیتی مشغول توسعه روش هایی برای تشخیص اطلاعات استگانوگرافی شده هستند. با توجه به وجود هزاران روش و برنامه قابل دسترس استگانوگرافی، تقریباً غیر ممکن است که هر تجزیه و تحلیل روی ارتباطات نتیجه دهد و اطلاعات استگانوگرافی شناسایی شوند.[19]
در ادامه به طور کامل به معرفی کامل شکل های مختلف حفاظت از محتوای رسانه دیجیتالی خواهیم پرداخت.
2-2-1- پنهان نگاری
بسیاری از شما نوشتن با آبلیمو و آب پیاز را در کودکی تجربه کرده‌اید و شاید هم برای دوستان تان این تردستی را اجرا کرده باشید که با گرم کردن کاغذ نوشته‌ها نمایان می شدند. از قلم‌های بی‌رنگ که استفاده کرده اید؟ قلم‌هایی که جوهر نامرئی دارند. نوشته‌های این قلم‌ها تنها با استفاده از نورهای مخصوص نمایش داده می‌شوند. برای نوشتن عبارات مخفی و سرّی بر روی کاغذ می‌توان از این روش استفاده کرد. تنها کسانی می‌توانند نوشته‌ی روی آن را بخوانند که از شیوه کار آگاه بوده و چراغ مخصوص اش را داشته باشند.
پنهان نگاری معادل فارسی واژه ی استگانوگرافی می باشد که در اصل کلمه ای یونانی بوده و از دو کلمه Steganos به معنای پنهان کردن و Graphy به معنای نوشتن تشکیل شده است. ترجمه کلمه به کلمه این لغت «نوشتار پوششی» می باشد که البته برداشت این معنی از استگانوگرافی چندان متداول نیست و بیشتر به مفهوم پنهان سازی اطلاعات در یک رسانه به عنوان پوشش بکار می رود به گونه ای که توسط اشخاص غیر مجاز قابل تشخیص نباشد.
مفاهیم مخفی سازی اطلاعات، جاسازی داده ها و واترمارکینگ دیجیتال اغلب در یک واژه کلی تحت عنوان واترمارکینگ مورد استفاده قرار می گیرند که البته این موضوع در کاربردهای تجاری بیشتر صدق می کند و لیکن در مقالات و کتب تخصصی پیرامون این موضوع، نویسندگان از عناوین مختلف استفاده می نمایند. به عنوان نمونه دی ولیسچاور بنا به استفاده تخصصی در هر موضوع، استگانوگرافی را در دسته های مختلف مطابق شکل (2-2) تقسیم نمود [20] و یا نیکولیدیس معیار دیگری برای تقسیم بندی این موضوع مطرح کرد.[21]

شکل 2-2 طبقه بندی انواع واترمارکینگ براساس مدل دی ولیچساور [20]
یک اصل اساسی در انواع روش های پنهان نگاری این است که پیام پنهان شده در اسناد یا تصویر توسط شخص سوم قابل تشخیص و یا بازیابی نباشد. به عنوان مثال، پیام پنهان شده می تواند شامل یک شماره سریال یا یک دنباله ارقام تصادفی یا داده های کپی رایت و یا مشخصات پدیدآورنده اثر باشد. بنابراین در جهان امروز استگانوگرافی را به صورت نوعی رمزنگاری الکترونیک می توان تعریف کرد که در آن اطلاعات در یک فایل که آن را پوشش می نامند، به گونه ای مخفی شود که تنها توسط گیرنده ی مجاز (فردی که الگوریتم و رمز به کار گرفته شده را می داند) قابل بازیابی باشد. پوشش می تواند یک فایل تصویری، صدا، متن و یا ویدئو و ... باشد. به فایل نهایی اصطلاحاً «استگانوگرام » می گویند.
با نگاهی به تاریخ در می یابیم که روش های مختلف پنهان سازی اطلاعات از یک سابقه هزار ساله برخوردار است. [7,8,22] اما تنها در سالهای اخیر روش های جدید پنهان نگاری پیشرفت چشمگیری داشته است. هر روز میلیون ها فایل در اینترنت بین افراد جابه جا می شود وگستردگی و ارزان قیمت بودن این شبکه، این امکان را فراهم آورده است که به صورت کانالی ارزان و سهل الوصول برای مبادله ی پیغام های سری مورد استفاده قرار گیرد، که در این زمینه جالب است بدانیم اعضای القاعده برای تبادل پیام های خود قبل از 11 سپتامبر از تصاویر و متن های استگانوگرام استفاده کرده بودند. روش های متعددی برای پنهان نگاری مطرح شده است که اکثر آنها مربوط به همین چند سال اخیر می باشند. هر روش مزایا، معایب و کاربردهای خاص خود را دارد.
به دلیل احتمال استفاده ی غیر قانونی از این تکنولوژی، روش های تشخیص و بیرون کشیدن اطلاعات پنهان شده نیز اهمیت فوق العاده ای دارند. جنگ دیرینه ی بین روش های مختلف پنهان کردن و تشخیص اطلاعات همچنان ادامه دارد و هر دو در ابتدای راه پیشرفت خود هستند.
2-2-2- واترمارکینگ یا نقشاب داده ها
واتر + مارکینگ به معنی نشانه گذاری یا نقش بر آب می باشد که از ترکیب دو واژه به معنی نشانه گذاشتن و آب می باشد. اگر توجه کرده باشید اگر یک چوبی را در دست خود بگیرید و بر روی آب نقشی حک کنید می بینید بعد از مدتی محو می شود ولی این نوشته وجود داشته است. بیشترین کاربرد واترمارکینگ در حک کردن اسم ها و امضاها بر روی عکس ها می باشد به طوری که مشخص نخواهد بود. این امر باعث می شود تا دیگر عکسی تقلب در آن صورت نگیرد و می توانید ادعا کنید که این عکس برای شماست. کسی این نوشته را نمی بیند ولی شما می توانید با یک الگوریتمی آن را استخراج کنید این نرم افزار همین کار را بر روی عکس انجام می دهد و نوشته هایی را به صورت هاید بر روی عکس می نویسد. پنهان‌نگاری هنر و علم جاسازی اطلاعات در یک رسانه حامل است که با توجه به پیشرفت قابل توجه ارتباطات دیجیتال استفاده از آن رو به افزایش می‌باشد. در پنهان‌نگاری هدف اصلی، امنیت به معنای عدم توانایی در اثبات وجود پیغام است در حالیکه در واترمارکینگ با توجه به کاربردهای مختلف، بیشتر مقاومت در مورد تغییرات اهمیت دارد. هر یک از حوزه‌های پنهان‌نگاری و واترمارکینگ کاربردهای متنوع و خاص خود را دارند. امروزه واترمارکینگ قابل مشاهده و پنهان در شاخه‌های مختلف کاربردی شده و یک نیاز جدی به حساب می‌آید. نرم‌افزار نهان‌ساز با هدف واترمارکینگ و پنهان‌نگاری در تصویر، طراحی و پیاده‌سازی شده است و از الگوریتم‌های متنوع با هدف دستیابی به امنیت، مقاومت و ظرفیت‌های مورد نظر بهره گرفته شده تا کاربردهای مختلفی از واترمارکینگ و پنهان‌نگاری پوشش داده شود. واترمارکینگ (فیزیکی) که در زبان فارسی به چاپ سفید ترجمه شده‌است، طرحی است که علاوه بر طرح زمینه، به صورتی غیر محسوس بر روی اسناد کاغذی چاپ می‌شود و با کمک رنگ روشن‌تر و یا از راه در معرض نور قرار گرفتن قابل رؤیت می‌باشد. واترمارکینگ دیجیتال رابطه نزدیکی با پنهان نگاری و پنهان‌سازی داده دارد. ولی با این حال، بسته به کاربردهایی که دارد، تفاوت‌هایی نیز مشاهده می‌شود. لذا در عین حال که می‌توان از مفاهیم مشابه در پنهان نگاری برای ارزیابی الگوریتم‌های واترمارکینگ بهره گرفت، نباید از تفاوت‌هایی که در عمل بین آن‌ها وجود دارد، غافل بود.
2-2-3-پوشیده نگاری
متشکل از دو آلمه یونانی stego به معنی مخفی و graphos به معنای نوشته که روی هم معنی نوشته مخفی را تداعی می کنند. در رمز نگاری دسترسی به محتوای پیام برای فرد غیر مجاز ناممکن می گردد لیکن در پوشیده نگاری موجودیت پیام انکار می شود. هدف رمزنگاری حفظ محرمانگی و تمامیت پیام است که با رمز کردن آن حاصل می شود. پوشیده نگاری هم همین اهداف را با پنهان نمودن پیام دنبال می کند بعلاوه در پوشیده نگاری انتخاب جا و ترتیب پنهان نمودن پیام نیز با بهره گیری از نوعی رمز در چینش بیت های پیام لابه لای بیت های میزبان صورت می پذیرد .همچنین می توان پیام را قبل از جا سازی داخل میزبان با استفاده از الگوریتم های رمز نگاری به صورت رمز در آورد و سپس عمل پنهان سازی را انجام داد.
بطوریکه می توان گفت با استفاده از پوشیده نگاری در حقیقت سه لایه حفاظتی بسیار محکم در دسترسی به پیام ایجاد خواهد شد: اول اینکه وجود ارتباط نامحسوس است و این هدف اصلی در پوشیده نگاری است و بنابراین گذشتن از اولین مانع کار چندان ساده ای نخواهد بود در صورتیکه وجود اطلاعات در یک میزبان مورد سوءظن واقع شود مرحله دوم پیدا کردن الگوریتم پنهان سازی است طوریکه باید جا و ترتیب پنهان شدن اطلاعات معلوم شود لیکن در این مرحله نیز چون از یک کلید بنام کلید استگ برای جاسازی پیام استفاده شده دانستن این کلید ضروری است و بنابراین گذشتن از این مرحله نیز با دشواری همراه خواهد بود و چنانچه دو مرحله قبلی با موفقیت پشت سر گذاشته شوند اکنون به متن رمزی دسترسی پیدا شده است که تازه در این مرحله مسائل مربوط به رمزنگاری مطرح می گردند .
در دنیای واقعی کنونی نیز استفاده از رمزنگاری قوی در ارتباطات شخصی توسط دولت ها محدود شده است. علت این محدودیت سوء استفاده از این علم برای انجام فعالیت های جنایی و تروریستی و سایر امور مرتبط با این موضوعات می باشد و به شدت توسط ارگانهای مربوطه کنترل می گردد و در صورت انجام تخلّف از فرستنده و گیرنده پیام رمزی توضیح خواسته می شود.
2-2-4- پنهان شکنی
در حالی که هدف استگانوگرافی مخفی کردن اطلاعات و جلوگیری از پیدا شدن و جلب توجه آنهاست، پنهان شکنی علمی است که برای پیدا کردن چنین مطالب مخفی شده ای به کار می رود. پنهان شکنی سعی می کند تا اطلاعات پنهان شده را پیدا کند اما اغلب متون مخفی که با استفاده از نرم افزارهای استگانوگرافی مخفی شده اند علامت خاصی از خود نشان نمی دهند یعنی مثلا اگر به شما چندین عکس داده شود تا یک متن مخفی را از درون آنها پیدا کنید بایستی ابتدا تشخیص دهید که کدام عکس شامل این متن مخفی است چرا که هیچ علامت خاصی وجود ندارد تا شما آن را تشخیص دهید حتی اگر عکس اولیه و اصلی نیز وجود داشته باشد براحتی قابل تشخیص نیست چرا که نه از لحاظ ظاهری و نه از لحاظ حجم این دو عکس تفاوت چندانی با یکدیگر ندارند. نسل های مختلفی از نرم افزار های استگانوگرافی وجود دارد که پنهان شکنی یکی از انواع آن است. به طور کلی شکل های پنهان نگاری در صورتی امن هستند که تصویر پوششی یا گنجانه دارای نشانه‌های قابل کشف نباشد. به بیان دیگر، خواص آماری تصویر پوششی یا گنجانه باید همانند خواص آماری پوشانده باشد. توانایی کشف پیام در تصویر به طول پیام پنهان بستگی دارد. واضح است که هرچه مقدار اطلاعاتی که در یک تصویر قرار می‌دهیم کمتر باشد امکان کمتری هست که نشانه‌های قابل کشف به وجود آید. انتخاب فرمت تصویر نیز تأثیر زیادی بر سیستم پنهان نگاری دارد. فرمت‌های فشرده نشده‌ای مثل BMP، فضای زیادی برای پنهان نگاری فراهم می‌کنند ولی استفاده از آنها به دلیل حجم اطلاعات زائد بالای آنها شک برانگیز است.
پیدا کردن پیغام ها که بسیار مفید تر از نابودی آن است می تواند به دو دسته کلی تقسیم شود، عکس ها و متن ها. البته دسته های دیگری مانند بررسی های بلا درنگ بر روی ISDN و TCP/IP می تواند باشد که برای آنها به علت حجم بسیار بالای اطلاعات منتقل شده باید از الگوریتم های پیچیده استفاده کرد. همچنین در مورد پیدا کردن پیغام در متن، یک text باید از جنبه هایی مثل: گرامر، تعداد لغات تکرار شده، تعداد حرف های تکرار شده، محتوای متن و معنای آن. با وجود روش های بسیار زیاد انتقال متن مانند فکس، پست الکترونیکی، چاپ های با کیفیت بالا حتی با چاپگر های خانگی، تلگراف، پیدا کردن یک پیغام مخفی شده در حجم عظیمی از متن ها که جابجا می شوند کار بسیار دشوار و تقریباً غیر ممکن است.
2-2-5- تشخیص استگانوگرافی
هنر تشخیص استگانوگرافی، به عنوان آنالیزاستگ یاد می شود، که برای تشخیص استگانوگرافی موجود در یک فایل استفاده می شود .
روش های زیادی برای تشخیص استگانوگرافی وجود دارند:
1- مشاهده آن فایل و مقایسه آن با دیگر کپی آن فایل از طریق پیداکردن آن در اینترنت: معمولاً کپی های چندگانه ای از تصاویر در اینترنت وجود دارند، به طوری که شما می توانید چند تا از آنها را جهت مقایسه با فایل مشکوک به کار گیرید .
به عنوان مثال اگر شما یک فایل JPEG را دانلود کردید و فایل مشکوک هم JPEG بود و دو فایل، از واقعیت فاصله داشتند ، یکی از دیگری بزرگتر است. احتمال اینکه فایل مشکوک شما اطلاعات مخفی در درون خود داشته باشد زیاد است.
2- گوش کردن به یک فایل: این روش مانند روش بالا است و سعی در تشخیص استگانوگرافی در فایل تصویر دارد. اگر شما سعی در تشخیص استگانوگرافی در یک فایل صوتی دارید ، شما نیازمند این هستید که فایل یکسانی را برای مقایسه پیدا کنید که از همان فرمت صوتی استفاده می کند.
2-2-6- علامت حق تکثیر
در حقیقت علامت های حق تکثیر جنبه تجاری استفاده از پنهان سازی اطلاعات هستند که برای جلوگیری از استفاده های غیرمجاز تولیدات الکترونیکی اطلاعات به صورت نامحسوس و غیرقابل تفکیک از محصول داخل آن جاسازی می شود که در مواقع لزوم برای پیگیری استفاده غیر مجاز و اثبات حق مالکیت از طریق قانون می تواند به مالک واقعی محصول کمک کند . علامت حق تکثیر را می توان به دو دسته تقسیم کرد:
الف) واترمارکینگ: علامت واترمارکینگ اطلاعاتی هستند که داخل محصول الکترونیکی جاسازی می شوند و یا به بیان بهتر ترکیب می شوند طوری که از مقاومت بسیار بالایی برخوردار می باشند و معمولاً این اطلاعات شامل آرم یا علامت مخصوص شرکت یا مالک است که به آن لوگو گفته می شود. فرقی که پوشیده نگاری با واترمارکینگ دارد این است که در پوشیده نگاری آنچه مهم است پیامی است که داخل میزبان پنهان شده است و میزبان در حقیقت سدی است برای محافظت از پیام، لیکن در واترمارکینگ آنچه که مهم است میزبان است و پیام برای محافظت از میزبان داخل آن جاسازی شده است. یکی از خصوصیات ضروری واترمارکینگ داشتن مقاومت بسیار بالا است به طوری که به هیچ وجه قابل تفکیک از میزبان نباشد و از بین بردن آن منجر به از بین رفتن میزبان شود.
ب) فینگرپرینتینگ: فینگرپرینتینگ اطلاعاتی است که برای محافظت در مقابل استفاده غیر مجاز از محصولات نرم افزاری داخل آن پنهان می شود طوری که استفاده کننده مجاز با وارد کردن آنها به صورت عدد شناسایی قادر به استفاده از آن خواهد بود. همچنین این عدد شناسایی برای پیگیری کپی های غیر مجاز از نرم افزار نیز می تواند مورد استفاده قرار گیرد.
2-3- معایب استگانوگرافی
استگانوگرافی به اعتقاد بسیاری از نویسندگان و متخصصان علوم کامپیوتر، استگانوگرافی کاربردهای بد و غیرقانونی نیز وجود دارد. براساس آمار وب سایت www.techsec.com بیش از 300 نوع برنامه استگانوگرافی در اینترنت وجود دارند که به صورت رایگان و بی نام قابل دانلود شدن هستند. بدین ترتیب هر کس که تنها اطلاعات کمی در مورد کامپیوتر داشته باشد می تواند یکی از این برنامه ها را دانلود کرده و از آنها برای فرستادن پیام های مخفی استفاده کند. حال این فرد می تواند یک فرد عضو یک گروه جنایتکار و تبهکار باشد. و یا یکی دیگر ازاستفاده های بد استگانوگرافی را می توان هرزه نگاری برخی افراد و پنهان کردن آنها در داخل عکس های معمولی و قرار دادن آن عکس ها در داخل وب سایت ها برشمرد که در این صورت حتی ما از وجود آنها در بین فایل هایمان نیز بی اطلاع خواهیم بود.
2-4- تفاوت بین واترمارکینگ و فینگرپرینتینگ
واترمارکینگ و فینگرپرینتینگ کمی با یکدیگر تفاوت دارند، وقتی نشانه تجاری یا مشخصه ای در یک اثر مانند عکس، ویدئو یا صدا به شکل مخفیانه ذخیره می شود به آن واترمارکینگ می گویند؛ اما مخفی کردن شماره سریال یا یک مشخصه از یک چیز در چیز مشابه دیگر را فینگرپرینتینگ می نامند. هر دوی این روش ها برای جلوگیری از دزدی آثار بکار می روند، از دومی برای پیدا کردن ناقضین کپی رایت و از اولی برای اثبات آن استفاده می شود. اما این دو روش بخشی از مطلب کلی تری به نام استگانوگرافی هستند.
2-5- تفاوت پنهان نگاری و رمزنگاریتفاوت اصلی رمزنگاری و پنهان نگاری آن است که در رمز نگاری هدف اختفاء محتویات پیام است و نه به طور کلی وجود پیام، اما در پنهان نگاری هدف مخفی کردن هر گونه نشانه‌ای از وجود پیام است. در مواردی که تبادل اطلاعات رمز شده مشکل آفرین است باید وجود ارتباط پنهان گردد. به عنوان مثال اگر شخصی به متن رمزنگاری شده‌ای دسترسی پیدا کند، به هر حال متوجه می‌شود که این متن حاوی پیام رمزی می‌باشد. اما در پنهان نگاری شخص سوم ابداً از وجود پیام مخفی در متن اطلاعی حاصل نمی‌کند.
بنابراین استگانوگرافی به نوعی امنیت بیشتری نسبت به رمزنگاری دارد. البته همانطور که گفته شد می توان از ترکیب هر دو با هم نیز استفاده کرد، بدین ترتیب که پیام ابتدا رمز و سپس مخفی می شود که در این صورت یک لایه ی امنیتی دیگر به روش های متداول رمزنگاری اضافه می شود.

2-6- تفاوت پنهان نگاری، واترمارکینگ و رمزنگاری
جدول 2-1 مقایسه پنهان نگاری، نهان نگاری و رمزنگاری [23]
روش پنهان نگاری نهان نگاری رمزنگاری
حامل انواع رسانه دیجیتالی بیشتر ویدئو و تصویر متن هایی که مبتنی بر بسط فایل تصویری هستند
داده مخفی بار مفید واترمارک متن ساده
کلید اختیاری ضروری
فایل های ورودی حداقل دو تا مگر اینکه در تابع تعبیه سازی باشد یکی
آشکارسازی کور یادگیرنده است(نیاز به پوشش اصلی یا واترمارک برای استخراج دارد) کور
احراز هویت بازیابی کامل داده معمولاً توسط ارتباط متقابل بدست می آید. بازیابی کامل داده
هدف ارتباط مخفی حفظ قانون کپی رایت حفاظت از داده
نتیجه فایل استگ فایل واترمارک رمز گذاری متن
بحران مطلوبیت / ظرفیت استقامت استقامت
انواع حمله پنهان شکنی پردازش تصویر رمزگشایی
قابلیت مشاهده هیچ وقت گاهی اوقات همیشه
زمان شکست شناسایی شود حذف یا جایگزین شود رمزگشایی شود
ارتباط با پوشش لزوما وابسته به پوشش نیست. پیام مهمتر از پوشش است. معمولاً ویژگی از پوشش می آید. پوشش مهمتر از پیام است. کاربرد ندارد.
قابلیت انعطاف برای انتخاب پوشش مناسب آزاد است. انتخاب پوشش محدودیت دارد. کاربرد ندارد
تاریخچه بسیار سنتی بغیر از مدل های دیجیتالی مدرن مدرن
2-7- اهداف و ملزومات پنهان نگاری
به طور کلی اهداف تحلیل پنهان نگاری و یا حالت هایی که تحلیل انجام می گیرد به ترتیب شامل موارد زیر است:
1- اثبات وجود یا عدم وجود پیغام پنهانی: در یک رسانه ی مشکوک این حالت مهمترین هدف تحلیل پنهان نگاری است و اکثر الگوریتم های ارائه شده نیز در این مقوله هستند.
2- تخریب پیغام: این حالت مربوط به بازرسی فعال می شود. در یک کانال ارتباطی مشکوک تمام رسانه های رد و بدل شده را طوری تغییر می دهند که مطمئن باشند هیچ پیغامی رد و بدل نمی شود. البته در این زمینه باید توجه داشت که تغییر رسانه با هدف تخریب، کمترین تاثیر را روی کیفیت رسانه بگذارد.
3- استخراج پیغام: اگر فرستنده و گیرنده از الگوریتم های ساده ی پنهان نگاری استفاده کنند که نیازی به کلید رمز یا عمومی ندارد و یا این که کلید لو رفته باشد و الگوریتم توسط دشمن شناسایی شده باشد، دشمن می تواند پیغام را استخراج نماید. البته این حالت در پنهان نگاری به سختی اتفاق می افتد.


4- تغییر پیغام: پس از استخراج پیغام، ممکن است دشمن به قصد فریب پیغام را تغییر دهد و آن را در تصویر قرار داده و برای گیرنده ارسال کند.
5- استخراج کلید عمومی و کلید رمز: در بسیاری از الگوریتم های پنهان نگاری، کلید عمومی در بخشی از رسانه ی پنهان نگار به صورت ترتیبی قرار می گیرد که می توان الگوریتم های تحلیل خاصی به این منظور طراحی نمود.
6- یافتن الگوریتم پنهان نگاری: یک نوع تحلیل می تواند این باشد که پیغام به نوعی به دست دشمن رسیده است و دشمن می خواهد الگوریتم پنهان نگاری را به دست آورد تا برای رسانه های پنهان نگار بعدی بتواند پیغام پنهانی را استخراج کند.
گرچه هر کاربردی از پنهان نگاری تصویر نیازهای خاص خود را دارد، با این همه تمام روش های پنهان نگاری باید ملزومات مشترکی را رعایت کنند که عبارتند از :
١) شفافیت از نظر درک سیستم، ٢) امنیت و ٣) رعایت ظرفیت سیگنال
واضح است که این ملزومات به یکدیگر مربوطند. الگوریتم های پنهان نگاری، به منظور درج اطلاعات سیگنال پیام در داخل داده میزبان، تغییرات کوچکی را بر اساس سیگنال پیام در داده میزبان، ایجاد می کنند، به نحوی که با چشم انسان قابل مشاهده نباشد.
مواردی که در طراحی یک روش پنهان سازی دارای اهمیت هستند:
شفافیت: شفافیت سیستم بیان می دارد که موضوع میزبان قبل و بعد از جاسازی در پیام نباید تفاوت محسوسی داشته باشد چرا که هدف غیر قابل حس کردن انتقال پیام است و در حقیقت امنیت یک سیستم پنهان سازی در همین مسئله شفافیت نهفته است و هر چقدر که شباهت موضوع میزبان پیام در هر دو حالت عاری و حاوی پیام بیشتر باشد امنیت این سیستم در سطح بالاتری قرار دارد.
مقاومت: مقاومت یک سیستم پنهان سازی به معنای این است که پیام پنهان شده در مقابل اعمال تغییرات ناخواسته و غیر عمدی که وجود نویز در طول مسیر انتقال بوجود می آورد و یا اعمال تغییرات عمدی که توسط حمله کننده فعال به منظور تغییر پیام یا از بین بردن آن انجام می گیرد مقاومت لازم را داشته باشد.
ظرفیت: در یک سیستم پنهان سازی هر چقدر بتوان پیام بیشتری را در یک میزبان مخفی نمود این سیستم مناسب تر خواهد بود حجم داده ای که می توان در یک میزبان ذخیره کرد دقیقا بستگی به ماهیت میزبان دارد و این که تاچه حدی می توان داده در آن پنهان کرد بدون اینکه در شفافیت آن تاثیری جدی بگذارد. سه ویژگی فوق بطور بسیار تنگاتنگی در ارتباط با یکدیگر هستند بدین معنی که با ثابت فرض کردن ویژگی اول و افزایش ویژگی دوم ویژگی سوم حتما کاهش خواهد یافت.
ثابت =مقاومت*ظرفیت
در شکل های پنهان نگاری عناصر ظرفیت و شفافیت اهمیت اصلی را دارند. در دنیای امروز، جوهر نامرئی و کاغذ که در گذشته برای برقراری ارتباط پنهانی به کار برده می‌شد به وسیله رسانه‌های عملی‌تر مثل تصویر، ویدئو و فایل‌های صوتی جایگزین شده‌اند. به دلیل اینکه این رسانه‌های دیجیتال دارای افزونگی اطلاعاتی زیادی هستند می‌توانند به عنوان یک پوشش مناسب برای پنهان کردن پیام استفاده شوند. تصاویر مهم‌ترین رسانه مورد استفاده به خصوص در اینترنت هستند و درک تصویری انسان از تغییرات در تصاویر محدود است. تصاویر نوعی رسانه پوششی مناسب در پنهان نگاری محسوب می‌شوند و الگوریتم‌های پنهان نگاری متعددی برای ساختارهای مختلف تصاویر ارائه شده‌است. هیچ یک از این الگوریتم‌ها تاکنون امنیت را به طور کامل تأمین نکرده‌اند. به طور کلی شکل های پنهان نگاری در تصویر از الگوریتم جاسازی و الگوریتم استخراج بیت‌ها تشکیل شده‌اند. به تصویر مورد استفاده برای پنهان نگاری پوشانه و به تصویری که در اثر قرار دادن پیام به وسیله الگوریتم جاسازی به دست می‌آید تصویر پوششی یا گنجانه می‌گوییم. الگوریتم‌های پنهان نگاری به صورت عمومی از افزونگی در فضای مکانی یا افزونگی در فضای تبدیل استفاده می‌کنند. در هر کدام از این فضاها به شیوه‌های گوناگونی می‌توان داده‌ها را پنهان کرد که یکی از ساده‌ترین روش ها، استفاده از بیت‌های کم ارزش فضای مورد نظر است. در پنهان نگاری نیز همانند رمز نگاری فرض بر آن است که الگوریتم‌های بکار رفته در پنهان نگاری برای همه آشکار است. شفافیت در این روش ها بر پایه پنهان بودن کلید تعریف می‌گردد به طوری که نتوان بدون داشتن کلید هیچ اطلاعی از وجود پیام پنهان کسب کرد.
2-8- انواع بازرسی
در راستای رسیدن به اهداف یاد شده تحلیلگر دو نوع بازرسی می تواند انجام دهد:
1- بازرسی فعال: در این نوع بازرسی، ناظر پیغام را با اندکی دست کاری تغییر می دهد تا امیدوار باشد که هیچ ارتباط پنهانی برقرار نمی شود. چون روش های پنهان نگاری بیشتر روی امنیت و ظرفیت تکیه دارد، معمولاً شکننده و غیر مقاوم هستند. لذا پنهان نگاری در برابر ناظر فعال، کار مشکلی است و در این حالت باید از تکنیک های واترمارکینگ مقاوم بهره گرفت.
2- بازرسی غیر فعال: در بازرسی غیر فعال، تحلیلگر تمام پیغام هایی را که بین فرستنده و گیرنده رد و بدل می شود بررسی می کند. هیچ پیغامی را تغییر نمی دهد. لازم به ذکر است که در ارتباط فرستنده و گیرنده، رسانه پنهان نگاری شده قابل تشخیص نیست و این تحلیلگر است که باید با هنر خود آن را پیدا کند.
2-9- شیوه حملات تحلیل
تحلیل را با دو شیوه حملات مشاهده ای و آماری می توان انجام داد. اگرچه پنهان نگاری سعی می کند اطلاعات را طوری پنهان نماید که قابل مشاهده و ادراک نباشد ولی اعوجاج هایی روی مشخصات آماری سیگنال پوششی ایجاد می کند. هنر روش های تحلیل، شناسایی این ویژگی ها و دسته بندی آن ها، برای جداسازی تصاویر پنهان نگار و غیر پنهان نگار است.
روش های تحلیل آماری خود به دو گروه روش های عمومی و الگوریتم هایی که برای یک روش خاص پنهان نگاری طراحی می شوند، تقسیم می گردند. در روش های عمومی، تحلیل برای همه روش های پنهان نگاری یا برای دسته ای از روش های پنهان نگاری انجام می شود. اگرچه روش های عمومی کاربردی تر و جذاب تر هستند برای یک الگوریتم خاص نسبت به گروه دوم، پاسخ های ضعیف تری تولید می کنند. البته بایستی اشاره کرد که با توجه به ساختارهای تصویر، دسته بندی های مختلفی برای تحلیل پنهان نگاری می توان ارائه نمود. به عنوان مثال می توان به تحلیل پنهان نگاری در حوزه مکانی و در حوزه تبدیل و یا تحلیل پنهان نگاری برای تصاویر غیر فشرده و تصاویر فشرده، تحلیل پنهان نگاری برای تصاویر رنگی، سیاه و سفید و باینری اشاره کرد.
2-10- اصطلاحات استگانوگرافی
فایل حامل: فایلی که اطلاعات مخفی شده را درون خود نگه می دارد .
آنالیزگر استگ: فرایندی که اطلاعات مخفی درون یک فایل را تشخیص می دهد .
وسیله استگ: وسیله ای که در اطلاعات مخفی وجود دارد.
بیت های فراوانی: قسمتهایی از اطلاعات درون یک فایل که می تواند بدون صدمه به فایل در آن عمل اوررایت یا تغییر فایل را انجام دهد.
محل حمل (داده): اطلاعاتی که مخفی می شوند .
2-11- روش های پنهان سازی اطلاعات
همانطور که در شکل (2-3) نشان داده شده است پتیتکولاس (1999) روش های پنهان سازی اطلاعات را به صورت زیر دسته بندی کرد [8]:
-25336513970پنهان سازی اطلاعات
کانالهای مخفی
پنهان نگاری
ناشناس ماندن
علامت گذاری کپی رایت
زبان شناختی
فنی
قوی
شکننده
فینگرپرینتینگ
واترمارکینگ
غیرقابل مشاهده
قابل مشاهده
00پنهان سازی اطلاعات
کانالهای مخفی
پنهان نگاری
ناشناس ماندن
علامت گذاری کپی رایت
زبان شناختی
فنی
قوی
شکننده
فینگرپرینتینگ
واترمارکینگ
غیرقابل مشاهده
قابل مشاهده

شکل 2-3 شکل های پنهان سازی اطلاعات توسط پتیتکولاس[8]
بلوک دیاگرام و تعاریفی که در اولین کارگاه بین المللی پنهان سازی اطلاعات برای انجام این عمل عنوان شد به شرح زیر است [24]:
over-medium : شئ ای که پیام در قالب آن منتقل می شود و می توان شامل تصویر، متن و …باشد در این تحقیق به آن تصویر پوششی گفته می شود.
Embedded-message : داده ای که باید به صورت پنهانی منتقل شود و داخل پیام پوششی جاسازی می گردد در این تحقیق به آن پیام مخفی گفته می شود.
Stego-medium : حاصل ترکیب پیام در میزبان است در این تحقیق به آن تصویر پنهان نگاری شده گفته می شود.
Stego-key : اطلاعات سری است که مشترک بین فرستنده و گیرنده است و به منظور جاسازی و بازیابی اطلاعات از آن استفاده می شود.
Embedder(E ) : تابع جاسازی کننده پیام .
Extractor(E-1 ) : تابع استخراج کننده پیام .
برای انجام هر روش پنهان سازی دو کار زیر باید صورت پذیرد [25]:
الف) در آنچه به عنوان تصویر پوششی بکار می رود این تحقیق باید انجام شود که چه تغییراتی را می توان روی آن اعمال نمود بدون اینکه تفاوت قابل درکی بین نمونه اصلی و نمونه ای که در آن تغییرات ایجاد شده بوجود آید. این تحقیق برای انجام عملیات فشرده سازی نیز جهت حذف اجزاء زائدی که وجود یا عدم وجود آنها در کیفیت تاثیر چندانی ندارد انجام می شود.
ب) از مشخصه تحقیق شده در قسمت (الف) برای پنهان کردن اطلاعات استفاده شود.
اگرخواسته باشیم پنهان سازی اطلاعات را به صورت فرمولی عنوان کنیم می توان گفت برای قطعه ای اصلی از داده d که به عنوان میزبان مطرح است حد آستانه ای وجود دارد t که چنانچه زیر این حد آستانه، تغییراتی در d بوجود آوریم قابل تشخیص برای حسگرهای انسانی نیست. این حد آستانه از راه آزمایش بدست می آید و در افراد مختلف متفاوت است. لیکن کمترین مقدار آن از لحاظ حس انسانی می تواند برای t در نظر گرفته می شود. بنابراین ما همواره می توانیم تغییر c در d را زیر حد آستانه t بوجود آوریم طوری که قابل تشخیص بوسیله احساس نباشد.
d+c<t
اساس کار روش های موجود در پوشیده نگاری را می توان به دو دسته کلی زیر تقسیم کرد [24]:
روش هایی که بر پایه نقص در سیستم بینایی انسان (HVS) استواراست.
روش هایی که بر پایه نقص در سیستم شنوایی انسان(HOS ) استوار است.
سیستم شنیداری انسان آنقدر دقیق نیست که تغییرات جزئی ایجاد شده در قطعات صوت را تشخیص دهد و بنابراین از همین نقطه ضعف می توان استفاده نمود و داده ای را لابه لای قطعات صوت جا سازی کرد همچنین سیستم دیداری انسان دارای خصوصیاتی است که بر مبنای آنها روش های پنهان سازی متفاوتی در قالب تصاویر خصوصاً تصاویر ثابت ابداًع شده اند.
2-12- استگانوگرافی در رسانه های مختلف
در سه بخش بعدی درباره اینکه چگونه از استگانوگرافی در متن، عکس و صدا ایجاد و استفاده می شود بحث می کنیم. اغلب، در حالی که احتیاجی به آن نیست، متن هایی که در متن مخفی می شوند را نیز رمزگذاری می کنند. این برای تبعیت از یکی از قوانین کیرشهف در رمزنگاری است. طبق این قانون باید فرض شود دشمن از علم و تکنولوژی برخوردار است که می تواند تشخیص دهد شما از استگانوگرافی استفاده کرده اید. تنها قسمتی که دشمن از آن بی خبر است کلمه کوتاهی است که برای رمزگشایی مورد استفاده قرار می گیرد. سیستم باید به شکلی باشد که دشمن بدون آن کلمه بختی برای یافتن متن شما نداشته باشد.
 وقتی اطلاعات را جاسازی می کنیم باید نکات زیر را در نظر داشته باشیم:
اطلاعات پوشاننده باید به شکلی باشد که وقتی اطلاعات مورد نظر را درون آن جاسازی می کنیم تغییر نکند، اطلاعاتی که جاسازی می شود نیز باید به شکلی باشد که دیده نشود، البته منظور همیشه مخفی بودن نیست، اطلاعات می تواند دیده بشود ولی نظر کسی را جلب نکند.
اطلاعات جاسازی شده باید مستقیما ً در خود اطلاعات پوشاننده جاسازی شود و در هِدِر آن یا بالای آن قرار نگیرد.
اطلاعات جاسازی شده باید مقاومت کافی در برابر حمله ها و روش های مقابله با آن را داشته باشد.
ممکن است وقتی اطلاعات پوشاننده تغییر می کنند اطلاعات جاسازی شده کمی تغییر بکند، بدین منظور باید قابلیت استفاده از کد های خطایاب را داشته باشد.
اطلاعات جاسازی شده باید قابلیت آن را داشته باشد تا اگر قسمتی از اطلاعات پوشاننده از دست رفت دوباره بازیابی شود. مثلا ً اگر فقط قسمتی از عکس در دست بود بتوان همان قسمت از پیغام اصلی را استخراج کرد.
2-12-1- استگانوگرافی در متن
 یکی از مشکلاتی که برای نویسندگان وجود دارد توزیع غیر قانونی نوشته ها بوسیله ابزارهای پیشرفته مانند پست الکترونیکی است. بدین معنی که بدون پرداخت هزینه به نویسنده، نوشته وی را به دیگران می دهند. برای جلوگیری از این کار روش هایی ابداًع شد، مانند ساختن کلمه ای که از نظر خواننده دیده نمی شود ولی مشخصه آن متن است، یا کد کردن متن یا تغییر آن به روشی که قابل کپی برداری با دستگاه های فتوکپی نباشد، روش دیگر استفاده از کلمات حاشیه ای است که مخفی می باشد ولی mail server ها را می توان نسبت به آن حساس کرد تا از پخش آن جلوگیری کنند. روش هایی که در بعضی متون مورد استفاده قرار می گرفت در زیر آمده است.