بخشی از مقاله
چکیده
خوشه بندی و طبقه بندی از جمله روش های پرکاربرد در تجزیه و تحلیل داده ها است. خوشه یابی در واقع یافتن ساختار و الگو در مجوعهای از داده هایی است که طبقه بندی نشده اند. به بیان دیگر می توان گفت که خوشه بندی، قراردادن داده ها در گروه هایی است که اعضای هر گروه از زاویه خاصی شباهت دارند. در این مقاله یک روش پویا برای خوشه بندی تصاویر رنگی مبتنی بر الگوریتم فراابتکاری جستجوی هارمونی که از فرایند طبیعی اجرای موسیقی برگرفته شده، معرفی گردیده است.
در روش پیشنهادی علاوه بر اینکه امکان تنظیم دستی تعداد خوشه ها در تصویر رنگی وجود دارد، قابلیت الگوریتم جستجوی هارمونی به نحوی اصلاح شده است تا با استفاده از یک کنترل کننده فازی و بر اساس فواصل درون خوشه ای و برون خوشه ای و به طور اتوماتیک علاوه بر تعیین بهترین مکان - رنگ - مراکز خوشه ها، بهترین تعداد خوشه ها نیز استخراج گردند. نتایج آزمایش، راندمان و کارایی قابل توجه این روش را در مقایسه با روش مرسوم K میانگین نشان می دهد.
کلمات کلیدی خوشه بندی خودکار، جستجوی هارمونی، فاصله درون خوشه ای و برون خوشه ای، تصویر رنگی، کنترل کننده فازی، ناحیه بندی
مقدمه
خوشه بندی تصویر کاربرد گسترده ای در زمینه بینایی کامپیوتر و مسائل کرد. در روش خوشه بندی سلسله مراتبی، به خوشههای نهایی بر اساس تحلیل تصویر دارد که نیازمند مرحله ناحیه بندی2 جهت آشکارسازی اشیا و یا میزان عمومیت آنها ساختاری سلسله مراتبی نسبت داده میشود و خروجی، خوشه بندی تصویر به نواحی همگن با توجه به معیارهای معلوم نظیر رنگ، درختی است که دنباله ای از خوشه بندی را نشان می دهد و هر خوشه جزئی بافت، جنبش و... هستند.
از این رو، خوشه بندی موضوع عمده بسیاری از مجموعه داده هاست. از سوی دیگر الگوریتم های خوشه بندی مبتنی بر تحقیقات علمی محققان علم پردازش تصویر است. بخش بندی درصددند تا ضمن آنکه معیار معینی را بهینه می کنند مجموعه خوشه بندی یکی از شاخه های یادگیری بدون نظارت می باشد که در داده را مستقیما به خوشه های منفصل تجزیه کنند . با توجه به اینکه
دسته بندی گروه های داده از طریق سنجش شباهت آن ها به کار می رود.
روشهای خوشهبندی سلسله مراتبی پیچیدگی محاسباتی بالایی دارند، برای مطلوب این سنجش ها آن است که شباهت درون خوشه ای ، بیشینه و مجموعه دادههای بزرگ و در کاربرد های بازشناسی الگو روشهای شباهت برون خوشه ای، کمینه شود الگوریتم های خوشه بندی در زمینه خوشهبندی بر اساس بخش بندی کاربرد بیشتری دارند. یکی از الگوریتم های های بسیاری از جمله بازشناسی الگو، تحلیل تصویر، داده کاوی و یادگیری خوشه بندی مرسوم بر اساس بخش بندی، الگوریتم خوشه بندی K میانگین 6ماشین کاربرد دارند.
در این روش ابتدا K مرکز خوشه به صورت تصادفی از میان نقاط روش های خوشه بندی را می توان به دو گروه شامل روش های خوشه داده انتخاب می شود، سپس عمل تشکیل خوشه ها با تعلق دادن نقاط داده به بندی سلسله مراتبی4 و روش های خوشه بندی مبتنی بر بخش بندی5 تقسیم نزدیکترین مرکز خوشه صورت می گیرد. در مرحله بعد مراکز جدید خوشه ها با میانگین گیری روی اعضای هر خوشه به دست می آید و مجددا عمل تعلق داده به خوشه ها در فضای ویژگی تکرار می شود.
این فرایند آنقدر تکرار می شود تا مرکز خوشه ها ثابت باقی بمانند. روش K میانگین به دلیل کاربرد آسان آن با اقبال بیشتری نسبت به سایر روش ها روبروست ولی با توجه به آنکه زمان اجرای الگوریتم وابسته به تعداد داده هاست، در مواجهه با دنیای واقعی و حجم زیاد اطلاعات دچار چالش می شود و تخمین دقیق بهترین تعداد خوشه ها - K - در آن کار آسانی نیست. لذا امروزه محققان با ترکیب روش های کلاسیک و الگوریتم های فرا ابتکاری به روش های موثرتری جهت خوشه یابی در فضاهای با ابعاد زیاد دست یافته اند. از جمله این الگوریتم ها می توان به خوشه یابی وراثتی ، خوشه یابی گروه ذرات و یا خوشه بندی توسط الگوریتم کلونی مورچگان اشاره نمود.
ناحیه بندی و بخش بندی تصویر دیجیتال، به قطعات مناسب یک مسئله اساسی و مهم و از مراحل بدوی در علم تحلیل تصویر است. روش های ناحیه بندی دقیق اشیا مورد نظر در تصویر، عموما شامل موارد زیر است: - 1ناحیه بندی لبه و خطوط - 2روش های رشد ناحیه - 3خوشه بندی - 4روش های شکافت ناحیه. روش پیشنهادی ما به ناحیه بندی تصویر براساس روش خوشه بندی متمرکز است.
روش خوشه بندی دینامیک تصاویر رنگی که در این تحقیق ارائه شده، قادر است بطور اتوماتیک با استفاده از قابلیت های الگوریتم جستجوی هارمونی ضمن یافتن مناسب ترین محل مراکز خوشه ها، تعداد مناسب خوشه ها را - بدون دانش قبلی - نیز در مجموعه داده های تصویر بیابد. نتایج آزمایش ، کارایی قابل توجه روش پیشنهادی را در مقایسه با الگوریتم K میانگین در خوشه بندی دینامیک تصاویر رنگی استاندارد نشان می دهد.
پیکربندی مقاله به این ترتیب است که در بخش به مفاهیم اساسی در مورد الگوریتم بهینه سازی جستجوی هارمونی اشاره خواهد شد. در بخش روش پیشنهادی خوشه یابی خودکار تصویر رنگی مبتنی بر الگوریتم جستجوی هارمونی معرفی و در بخش الگوریتم و روال انجام آن تبیین می شود. نهایتا در بخش 5 به ارزیابی عملکرد آن در مواجهه با انواع استاندارد تصویر و مقایسه عملکرد آن با روش مرسوم K میانگین و بحث و نتیجه گیری پرداخته خواهد شد.
الگوریتم جستجوی هارمونی
الگوریتم های فراابتکاری بهینه یابی از پدیده های طبیعی تقلید می کنند. الگوریتم فراابتکاری جستجوی هارمونی7 در سال 2001 توسط گیم8 و همکارانش ارائه شده است . این الگوریتم، از فرایند طبیعی اجرای موسیقی برگرفته شده است. همانطور که آهنگساز به دنبال یافتن زیباترین آهنگ است در فرآیند بهینه یابی نیز به دنبال یافتن بهترین جواب برای مسئله هستیم. مناسب بودن جواب در فرآیند بهینه یابی با بررسی تابع هدف تعیین می شود.
در ساخت آهنگ، زیبایی آهنگ را گام هریک از دستگاه های موسیقی تعیین می کند و در بهینه یابی نیز مقدار تابع هدف را مقادیر متغیرهای مسئله تعیین می کند. جزئیات مربوط به شباهت بین بداهه نوازی در موسیقی و بهینه سازی نشان داده شده است. در فرایند بداهه نوازی، هر نوازنده نتی از بین محدوده ممکن را به صدا در می آورد و این اصوات در کنار هم یک بردار هارمونی را تشکیل می دهند. اگر تمام نت ها در کنار هم یک هارمونی خوب تولید کنند، این بردار هارمونی در ذهن نوازنده ها ذخیره می شود و امکان تولید هارمونی خوب در مرحله بعد نیز افزایش پیدا می کند.
مشابه همین فرایند، در بهینه سازی مهندسی، هر متغیر تصمیم گیری در ابتدا یک مقدار از بین مقادیر ممکن را انتخاب می کند. این مقادیر در کنار هم یک بردار راه حل را تشکیل می دهند. اگر تمام مقادیر متغیرهای تصمیم گیری، راه حل خوبی را ایجاد کنند، این پاسخ در حافظه هر متغیر ذخیره شده و در این حالت نیز احتمال تولید یک پاسخ خوب درمرحله بعد افزایش پیدا می کند.
ارتباط بین تکنیک آهنگسازی و بهینه یابی را می توان به صورت زیر بیان نمود.هر آهنگساز با هر متغیر مسئله مرتبط است.عرض نوار تنظیم کوک دستگاه های موسیقی با دامنه تغییر متغیرهای مسئله مرتبط است.هارمونی موسیقی در یک زمان مشخص با بردار متغیرهای مسئله در در یک تکرار مشخص، مرتبط است.زیبایی موسیقی از نظر شنوندگان با تابع هدف مرتبط است. و با اصلاح شدن هارمونی موسیقی در هر لحظه، بردار متغیرهای مسئله در هر تکرار اصلاح خواهند شد.
تشابه بین بداهه نوازی در موسیقی و فرآیند بهینه سازید فرمول بندی مسئله بهینه سازی و تعریف پارامترهای الگوریتم: مسئله بهینه سازی به صورت زیر تعریف می شود: که f - x - تابع هدف بوده، x بردار متغیرهای مسئله - که اعضای آن xi ها هستند - ، Xi مجموعه مقادیر ممکن برای متغیر xi است و برای متغیرهای پیوسته داریم Lxi [i Uxi و N نیز تعداد متغیرهای مسئله است. پارامترهای الگوریتم جستجوی هارمونی نیز که در این مرحله تعیین می شوند عبارتند از : اندازه حافظه هارمونی9 - یا تعداد بردارهای متغیرهای مسئله - ، نرخ انتخاب از حافظه هارمونی10، نرخ تنظیم کوک11، عرض نوار تنظیم کوک و معیار توقف یا حداکثر تعداد جستجوها. نرخ انتخاب از حافظه هارمونی و نرخ تنظیم کوک مقداری بین صفر و یک است.
به هنگام سازی حافظه هارمونی: در این گام اگر بردار پاسخ جدید که در گام قبلی به دست آمد، با توجه به مقدار تابع هدف به ازای این بردار از بدترین بردار موجود در حافظه هارمونی بهتر باشد، بردار پاسخ جدید در حافظه هارمونی جایگزین بدترین بردار موجود در حافظه شده و بردارهای حافظهی هارمونی مجددا براساس مقادیر تابع هدف مرتب می شوند. تکرار گام های های سوم و چهارم تا برآورده شدن معیار توقف جستجو: در گام پنجم، گام های سوم و چهارم تا زمان برآورده شدن معیار توقف جستجو که معمولا بر حسب حداکثر تعداد جستجوها تعریف می شود، تکرار می شوند.
