دسامبر 2019

الگوریتم های فراابتکاری (هیوریستیک)

الگوریتم های فرا ابتکاری یا فرا تکاملی یا فرا اکتشافی نوعی از الگوریتم‌ های تصادفی هستند که برای یافتن پاسخ بهینه به کار می‌روند.

روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتمهای دقیق (exact) و الگوریتم‌های تقریبی (approximate algorithms) تقسیم‌بندی می‌شوند. الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه‌سازی سخت کارایی کافی ندارند و زمان اجرای آن‌ها متناسب با ابعاد مسائل به صورت نمایی افزایش می‌یابد. الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند.

الگوریتم‌های تقریبی نیز به سه دسته الگوریتم‌های ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش‌بندی می‌شوند. دو مشکل اصلی الگوریتم‌های ابتکاری، گیر افتادن آنها در نقاط بهینه محلی، همگرایی زودرس به این نقاط است. الگوریتم های فراابتکاری برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از نقاط بهینه محلی هستند و قابلیت کاربرد در طیف گسترده‌ای از مسائل را دارند. رده‌های گوناگونی از این نوع الگوریتم در دهه‌های اخیر توسعه یافته‌است که همه این ها زیر مجموعه الگوریتم فراابتکاری می باشند.

دسته‌بندی الگوریتم های فرا ابتکاری

معیارهای مختلفی می‌توانند برای طبقه‌بندی الگوریتم های فراابتکاری استفاده شوند:

مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتم‌های مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند.
الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم های فراابتکاری از طبیعت الهام گرفته شده‌اند، در این میان برخی از الگوریتم های فراابتکاری نیز از طبیعت الهام گرفته نشده‌اند.
با حافظه و بدون حافظه: برخی از الگوریتم های فراابتکاری فاقد حافظه می‌باشند، به این معنا که، این نوع الگوریتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به طور مثالتبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.
قطعی و احتمالی: یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم های فراابتکاری احتمالی نظیر تبرید شبیه‌سازیشده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.

الگوریتم های فراابتکاری بر پایه جمعیت

از الگوریتم‌های شناخته شده فراابتکاری بر پایه جمعیت می‌توان الگوریتم‌های تکاملی (الگوریتم ژنتیک، برنامه‌ریزی ژنتیک، …)، بهینه‌سازی کلونی مورچگان، کلونی زنبورها، روش بهینه‌سازی ازدحام ذرات، الگوریتم قهرمانی در لیگهای ورزشی، بهینه‌سازی ملهم از فیزیک نور، الگوریتم ریشه-پاجوش و الگوریتم چکه آبهای هوشمند را نام برد.

در سالهای اخیر الگوریتم های فراابتکاری جدیدی با توجه به موجودات زنده موجود در طبیعت توسعه داده شده اند که از معروف ترین آنها میتوان به الگوریتم بهینه سازی گرگ خاکستری ، الگوریتم بهینه سازی سنجاقک ، الگوریتم بهینه سازی گرده افشانی گل ها، الگوریتم بهینه سازی نهنگ یا وال ، الگوریتم بهینه سازی ملخ نام برد.

الگوریتم‌های متداول فراابتکاری مبتنی بر یک جواب

از الگوریتم‌های متداول فراابتکاری مبتنی بر یک جواب می‌توان الگوریتم جستجوی ممنوعه و الگوریتم تبرید شبیه‌سازی شده را نام برد.

پیاده‌سازی الگوریتم های فراابتکاری

فرایند طراحی و پیاده‌سازی الگوریتم های فراابتکاری دارای سه مرحلهٔ متوالی است که هر کدام از آن‌ها دارای گام‌های مختلفی هستند. در هر گام فعالیت‌هایی باید انجام شود تا آن گام کامل شود. مرحلهٔ ۱ آماده‌سازی است که در آن باید شناخت دقیقی از مسئله‌ای که می‌خواهیم حل کنیم بدست آوریم، و اهداف طراحی الگوریتم فراابتکاری برای آن باید با توجه به روش‌های حل موجود برای این مسئله به طور واضح و شفاف مشخص شود. مرحلهٔ بعدی، ساخت نام دارد.

مهمترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازه‌گیری عملکرد، و طراحی الگوریتم برای استراتژی حل انتخابی می‌باشد. آخرین مرحله پیاده‌سازی است که در آن پیاده‌سازی الگوریتم طراحی شده در مرحلهٔ قبل، شامل تنظیم پارامترها، تحلیل عملکرد، و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.

منبع

خلاصه ای در مورد الگوریتم های متاهیوریستیک

اکنون تعداد زیادی از مسائل بهینه سازی در پیرامون ما وجود دارد که به روش دقیق یا اصلاً قابل حل نیستند و یااین که در زمان معقول انجام این امر امکان پذیر نیست. بعضی از این چنین مسائلی را که عمدتاً جزء مسائل بهینه سازی هستند، مسائل NP-Hard می نامند. این خانواده بزرگ از مسائل، خواص بسیار جالبی دارند که سبب شده است تا کنون روش های تقریبی متعددی برای حل هر کدام از آنها در طول زمان ارائه شود. الگوریتم های فراابتکاری (متاهیوریستیک) جزء این دسته از روش ها هستند.

البته در مواقعی که در یک مسئله بهینه سازی، پارامتر یا محدودیت تصادفی، چند تابع هدف متضاد و امثالهم هم وجود داشته باشد، استفاده از الگوریتم های فراابتکاری بسیار موفقیت آمیزتر از سایر روش ها گزارش شده است. از طرف دیگر تنها تعداد معدودی از این الگوریتم ها اثبات شده اند که در حل بعضی از مسائل خاص حتماً به ازای هر مقدار از پارامترهای ورودی به جواب بهینه همگرا می شوند. عیب عمده این روش ها هم در همین مورد است. اما قابلیت مانور فراوان، طراحی ساده و بسیار سریع بودن آنها در کفه دیگر ترازو قرار دارد.

تعداد الگوریتم های فراابتکاری بسیار زیاد است اما ساختار منطق حاکم بر آنها معمولا جزء چند دسته از ساختارهای شناخته شده قرار می گیرد. از این رو با شناخت این منطق ها می توان الگوریتم های هیبریدی جدیدی را برای حل مسائلی را که با آنها سر و کار داریم، به وجود آورد. این روند همچنان ادامه دارد و هر روز الگوریتم های جالبی متولد می شوند و عده ای از الگوریتم ها نیز به تدریج منسوخ می شوند و تنها ارزش گزارش شدن در تاریخچه الگوریتم ها را به خود می گیرند. به عبارت دیگر، یکی از اهداف این دوره، آشنایی با دنیای زنده و پر تکاپوی موجودات الگوریتمی برای مهندسین صنایع است تا در مطالعات علمی خود از آنها استفاده کنند.

منبع

در چند دهه اخیر، دسته‌ای از الگوریتم‌های تقریبی توسعه داده شده‌اند که سعی دارند با ترکیب اصول اولیه روش‌های ابتکاری (هیوریستیک) روشی را برای جستجوی مؤثر و کارای فضای جواب پیدا کنند. امروزه این روش‌ها به روش‌های فرا ابتکاری (متاهیوریستیک) مشهورند. اصطلاح متاهیوریستیک اولین بار توسط Glover در سال 1993 و به هنگام معرفی روش جستجوی ممنوع به عنوان یک روش ابتکاری جدید به کار برده شد.
پیش از این، روش‌های فرا ابتکاری، روش‌های ابتکاری نوین نامیده می‌شدند. الگوریتم‌های تکاملی نظیر الگوریتم ژنتیک، الگوریتم بهینه‌سازی مورچگان، روش شبیه‌سازی تبرید، جستجوی ممنوع و شبکه‌های عصبی مصنوعی نمونه‌هایی از این روش‌ها می‌باشند.
تا به امروز تعریف مشخص و جامعی از اصطلاح متاهیوریستیک یا فرا ابتکاری صورت نگرفته است و تعاریف مختلفی برای این اصطلاح ارائه شده است. اما به طور خلاصه می‌توان مشخصات اصلی روش‌های فرا ابتکاری را به صورت زیر بیان نمود.

برخلاف روش‌های ابتکاری، هدف اصلی این روش‌ها، جستجوی مؤثر و کارای فضای جواب به جای یافتن صرف جواب‌های بهینه یا نزدیک بهینه می‌باشد؛
روش‌های فرا ابتکاری سیاست‌ها و راهکارهایی هستند که فرآیند جستجو را هدایت می‌کنند؛
روش‌های فرا ابتکاری تقریبی بوده و اغلب غیر قطعی(تصادفی) می‌باشند؛
این روش‌ها ممکن است با استفاده از مکانیزم‌هایی از به دام افتادن فرآیند جستجو در بهینه‌های موضعی جلوگیری کنند؛
الگوریتم های فراابتکاری، برخلاف روش‌های ابتکاری وابسته به نوع مساله نیستند، به عبارت دیگر می‌توان آنها را برای حل طیف گسترده‌ای از مسائل بهینه‌سازی مورد استفاده قرار داد؛
روش‌های فرا ابتکاری پیشرفته‌تر، از تجربیات و اطلاعات به دست آمده در طول فرآیند جستجو به شکل حافظه برای هدایت جستجو به نواحی پرامیدتر فضای جواب استفاده می‌کنند؛

به طور خلاصه می‌توان گفت که الگوریتم های فراابتکاری، راهکارهای پیشرفته و کلی جستجو می‌باشند و گام‌ها و معیارهایی را پیشنهاد می‌کنند که در فرار از دام بهینه‌های موضعی بسیار مؤثر هستند. عامل مهم در این روش‌ها، تعادل پویا بین استراتژی‌های تنوع بخشی و پرقدرت سازی است. تنوع بخشی به جستجوی گسترده در فضای جواب اشاره دارد و پرقدرت سازی به معنی بهره‌برداری از تجربیات به دست آمده در فرآیند جستجو و تمرکز بر نواحی پرامیدتر فضای جواب می‌باشد.
بنابراین با ایجاد تعادل پویا بین این دو استراتژی از یک طرف، جستجو به سمت محدوده‌هایی از فضای جواب سوق داده می‌شود که جواب‌های بهتری در آنها یافت شده است و از طرف دیگر موجب عدم اتلاف زمان بیشتر در بخشی از فضای جواب می‌شود که پیش از این بررسی شده و یا شامل جواب‌های نامرغوب‌تری است.
یکی از شاخص‌های تقسیم‌بندی الگوریتم های فراابتکاری، تعداد جواب‌هایی است که آنها در هر تکرار، تولید و مورد بررسی قرار می‌دهند. بر این اساس روش‌های فر ا ابتکاری به دو گروه روش‌های تک نقطه‌ای و روش‌های جمعیتی تقسیم‌بندی می‌شوند که در اینجا شرح مختصری از هر کدام از این روش‌ها آورده می‌شود.

منبع

الگوریتم های فراابتکاری

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

دسته‌بندی الگوریتم های فراابتکاری

معیارهای مختلفی می‌تواند برای طبقه‌بندی الگوریتم های فراابتکاری استفاده شود.
-1مبتنی بر یک جواب و مبتنی بر جمعیت: الگوریتم‌های مبتنی بر یک جواب در حین فرآیند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند .
-2الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم های فراابتکاری از طبیعت الهام گرفته شده‌اند، در این میان برخی از الگوریتم های فراابتکاری نیز از طبیعت الهام گرفته نشده اند .
3-با حافظه و بدون حافظه: برخی از الگوریتم های فراابتکاری فاقد حافظه می‌باشند، به این معنا که، این نوع الگوریتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به طور مثال تبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.
-4قطعی و احتمالی: یک الگوریتم فراابتکاری قطعی نظیر جستجوی ممنوعه، مسئله را با استفاده از تصمیمات قطعی حل می‌کند. اما در الگوریتم های فراابتکاری احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.

الگوریتم های مبتنی بر یک جواب

-الگوریتم تبرید شبیه سازی شده simulated annealing
-جست وجوی ممنوعه tabu search
-جست و جوی حریصانهGRASP search
-جست و جوی همسایگی متغیرvariable neighborhood search
-جست و جوی محلی هدایت شدهguided local search
-جست و جوی محلی تکرار شوندهinterated local search

الگوریتم های مبتنی بر جمعیت

–الگوریتم ژنتیک Genetic Algorithm
-الگوریتم رقابت استعماری Imperialist Competitive Algorithm
–الگوریتم بهینه سازی کلونی مورچگان Ant Colony Optimization Algorithm
–الگوریتم کلونی زنبور عسل Bee Colony Algorithm
-الگوریتم کرم شب تاب Firefly Algorithm
-الگوریتم سیتم ایمنی مصنوعی Artificial Immune System Algorithm
-الگوریتم جستجوی هارمونی Harmony Search Algorithm
–الگوریتم بهینه سازی تجمعی ذرات Particle Swarm Optimization Algorithm

منابع

1.https://fa.wikipedia.org

2.http://eyvazian.ir

3.http://www.papyrus.ir

4.http://www.ariamodir.com

دسامبر 13, 2019/0 دیدگاه /توسط daliri

مسئله کوله پشتی قسمت 2

آموزش های عمومی هوش مصنوعی

روابط پوشانندگی در مسئلهٔ کوله پشتی بیکران

در حل مسئلهٔ کوله پشتی بیکران، با کنار گذاشتن اشیایی که هیچوقت مورد استفاده قرار نمی‌گیرند، می‌توان مسئله را ساده‌تر کرد. برای مثال، فرض کنید برای شی ای مانند i، می‌توان زیر مجموعه از اشیا به نام J یافت طوری‌که ارزش مجموع آن‌ها بزرگتر از ارزش i و وزن مجموع آن‌ها کمتر از وزن i باشد؛ بنابراین، i نمی‌تواند در جواب بهینه بیاید. در این هنگام مجموعهٔ J را پوشاننده ی iمی‌گوییم. (توجه کنید این استدلال برای مسئلهٔ کوله پشتی کراندار نمی‌تواند مورد استفاده قرار گیرد. زیرا ممکن است قبلاً از اشیا سازندهٔ مجموعهٔ J استفاده کرده باشیم و تمام شده باشند)

پیدا کردن روابط پوشانندگی، به ما کمک می‌کند تا تا حجم فضای جستجو را در حد قابل توجهی کاهش دهیم. انواع مختلفی از روابط پوشانندگی وجود دارند، که همگی در نامساوی زیر صدق می‌کنند:

$\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ , and $\qquad \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ for some $x\in Z_{+}^{n}$

که: $\alpha \in Z_{+}\,,J\subseteq N$ و $i\not \in J$ . و $x_{j}$ تعداد انتخاب‌های شی نوع j را نشان می‌دهد. (دقت کنید این j‌ها، اعضای مجموعهٔ J هستند)

پوشانندگی انتخابی

شی $i$ ام، به‌طور انتخابی توسط $J$ پوشانده شده، اگر جمع وزن تعدادی از اعضای مجموعهٔ $J$ ، کمتر از $w_{i}$ باشد و جمع ارزش آن‌ها بیشتر از $v_{i}$ . به بیان ریاضی:

$\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}$ و $\qquad \sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}$ درصورتی که $x\in Z_{+}^{n}$ که $\alpha =1$ .

بررسی این نوع پوشانندگی، از لحاظ پیچیدگی محاسباتی چندان ساده نیست، بنابراین از بهترین روش‌ها، راه حل پویاست. در واقع این مسئله، یک مسئله کوله پشتی، اما با پارامترهای کوچکتر، مطابق زیر است:

$V=v_{i}$ ، $W=w_{i}$ و اشیا محدود به مجموعهٔ $J$ هستند.

نماد ریاضی پوشانندگی انتخابی به صورت $i\ll J$ است.

پوشانندگی حدی

شی $i$ ام، به‌طور حدی توسط $J$ پوشانده شده، اگر تعدادی از اشیا نوع $i$ توسط $J$ پوشانده شوند. به بیان ریاضی:

$\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ و $\qquad \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ در صورتی که $x\in Z_{+}^{n}$ و $\alpha \geq 1$ .

این نوع پوشانندگی، نمایش کلی تری از پوشانندگی انتخابی نیست که برای اولین بار در معرفی شد و در الگوریتم EDUK مورد استفاده قرار گرفت. کوچکترین $\alpha$ ممکن، حد $i$ نامیده می‌شود. به بیان ریاضی: $t_{i}=(\alpha -1)w_{i}$ . در این هنگام، پاسخ بهینه حد اکثر می‌تواند به تعداد $\alpha -1$ شی، از نوع $i$ را شامل شود.

پوشانندگی چندگانه

شی $i$ ، به‌طور چندگانه توسط شی $j$ پوشانده شده، اگر $i$ توسط تعدادی از شی نوع $j$ پوشانده شود. (یعنی شی $i$ ، فقط توسط تعدادی شی از نوع $j$ پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد). به بیان ریاضی:

$\qquad w_{j}\,x_{j}\ \leq w_{i}$ و $\qquad v_{j}\,x_{j}\ \geq v_{i}$ برای $x_{j}\in Z_{+}$

که $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ .

این پوشانندگی می‌تواند برای بهینه کردن پروسهٔ حل مورد استفاده قرار گیرد، زیرا تشخیص روابط پوشانندگی از این نوع، به محاسبات زیادی نیاز ندارد و نسبتاً ساده است.

نماد ریاضی پوشانندگی انتخابی به صورت $i\ll _{m}j$ است.

پوشانندگی ماژولار

فرض کنیم $b$ بهترین شی باشد، یعنی برای تمام $i$ ها، ${\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,$ . $b$ شی ای با بیشترین چگالی است.

شی $i$ ام، به‌طور ماژولار توسط شی $j$ پوشانده شده، اگر توسط $j$ و تعدادی شی از نوع $b$ پوشانده شود. (یعنی شی $i$ ، فقط توسط $j$ و تعدادی شی از نوع $b$ پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد) به بیان ریاضی:

$w_{j}+tw_{b}\leq w_{i}$ و $v_{j}+tv_{b}\geq v_{i}$

که $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ .

نماد ریاضی پوشانندگی ماژولار به صورت $i\ll _{\equiv }j$ است.

الگوریتم کوله پشتی با استفاده از روش حریصانه

void Greedy Knapsack(w,n)
{
//W is the knapsack and the n objects
sort (p,w)//Pi/Wi  &gt;  =  Pi+1/Wi+1
for(i=0;i  &lt;  n;i++)
    x[i]=۰
    U=W
    for(i=0;i  &lt; n;i++) if(W[i] &gt;  u);
break ;
[
x[i]=1;
u=u-[wi] 
}
if(i  &lt;  n)
    x[i]=u/w 
}

شبه کد عقبگرد برای مسئله کوله پشتی ۰و۱

از انجاییکه این مسئله بهینه‌سازی است، ما رد بهترین مجموعه کنونی کالاها و مجموع ارزش آن‌ها را نگه می‌داریم که اینکار توسط ارائه bestset و و یک متغیر maxprofit انجام می‌شود. این مسئله را برای یافتن اولین جواب بهینه مطرح می‌کنیم

مسئله:n کالا داریم که هر کدام از آن‌ها دارای ارزشی و وزنی دارند. ارزش‌ها و وزن ها، اعدادی صحیح و مثبت هستند. مجموعه‌ای از کالاها با حداکثر مجموع ارزش را طوری تعیین کنید که مجموع اوزان آن‌ها بیش از عدد صحیح مثبت w نشود

ورودی:اعداد صحیح مثبت nوw,ارایه‌های wوpکه از ۱ تاn شاخص دهی شده و هر یک شامل اعداد صحیح و مثبتی هستند که بترتیب غیر نزولی بر اساس مقادیر [p[i]/w[i مرتب شده‌اند

خروجی:مقدار صحیح maxprofit که ماکزیمم ارزش است، ارائه bestset که از ۱ تا n شاخص دهی شده و در مقادیر bestsetو “yes”است اگر کالای iام در مجموعه بهینه قرار داشته باشد در غیر اینصورت مقدار ان “no” می‌باشد

void knapsack (index I ,
             int profit , int weight)
 {
    if (weight  &lt; = W &amp;&amp; profit &gt;  maxprofit){
      maxprofit=profit;
      numbest=i;
      bestset=include;
    }
   if(promising(i)){
   include[i+1]=”yes”;
 knapsack(i+1,profit+p[i+1],weight+w[i+1]);
 include[i+1]=”no”
 knapsack(i+1,profit,weight);
 }
 }
 bool promising(index i)
 {
 index j,k;
 int totweight;
 float bound;
 if(weight  &gt; =  W)
 return false;
 else {
 j=i+1;
 bound=profit;
 totweight=weight;
 while(j  &lt; = n &amp;&amp; totweight + w[j]  &lt; = W){
 totweight=totweight+w[j];
 bound=bound+p[j];
 j++;
 }
 k=j;
 if(k  &lt; = n) bound=bound+(W-totweight)*p[k]/w[k]; return bound &gt;  maxprofit;
 }
 }

طبق قرار دادn,w,p,W ,numbest , bestset , include , maxprofit ورودیهای روتین نیستند. اگر این متغیرهای را به صورت سراسری تعریف می‌کردیم، شبه کد زیر ماکزیمم ارزش و مجموعه دارای این ارزش را تولید می‌کرد:

 numbest=0;
maxprofit = 0 ;
knapsack(0,0,0);
cout  &lt;&lt; maxprofit;      // نوشتن ماکزیمم ارزش
for (j=i ; j &lt; = numbest ; j++)     //نمایش مجموعه بهینه کالاها
cout &lt;&lt; bestset[i];

کاربردها

مسئلهٔ کوله پشتی می‌تواند در تصمیم‌گیری‌هایی که در دنیای واقعی با آن‌ها روبرو هستیم، مورد استفاده قرار گیرد. مانند بریدن کالا به‌طوری‌که کمترین مقدار به هدر رود، انتخاب سرمایه‌گذاری‌هاو سبد سهام، انتخاب دارایی‌ها برای مسئلهٔ امنیت دارایی‌های قبلی و ساختن کلیدها برای سیستم رمزنگاری کوله پشتیِ مرکل-هلمن.

== یکی از کاربردهای اولیهٔ مسئلهٔ کوله پشتی، طراحی و بارم بندی آزمون است به نحوی که آزمون دهنده در پاسخگویی به سؤالات حق انتخاب داشته باشد. چنانچه بارم بندی سؤالات همگن باشد، مسئله بسیار ساده خواهد شد. برای مثال، اگر آزمون دارای 12 سؤال، هر سؤال به ارزش 10 نمره باشد، آزمون دهنده باید فقط 10 سؤال را پاسخ دهد تا به بیشینه نمره ممکنِ 100 برسد. اما برای آزمون‌هایی با بارم بندی نایکسان، مسئله کمی سخت‌تر می‌شود. Feuerman و Weiss سیستمی ارائه دادند که در آن دانش آموزان با آزمونی با بارم بندی ناهمگن، با جمع بارم 125 روبرو هستند. از دانش آموزان خواسته می‌شود با توجه به توانایی‌های خود به سؤالات پاسخ دهند. در اینجا با مسئلهٔ کوله پشتی روبرو هستیم. چه زیر مجموعه‌هایی، جمع نمره‌ای برابر با 100 خواهند داشت؟ برای هر دانش آموز، پاسخ گویی به کدام زیر مجموعه از سؤالات، نمرهٔ بیشتری را به ارمغان می‌آورد؟

یک مثال از مسئله کوله پشتی

صورت مسئله: دزدی قصد سرقت از مغازه‌ای را دارد و حداکثر وزن w از اجناس را که می‌تواند بدزد در این مغازه n نوع جنس وجود دارد. اگر وزن جنس iام wi و قیمت آن vi باشد بیشینه سودی که بدست می‌آورد چقدر است؟

این مسئله به دو صورت تعریف می‌شود: 1- صفر و یک در حالت صفر و یک مسئله به این صورت تعریف می‌شود که دزد یا یک جنس را برمی‌دارد یا برنمی‌دارد و حق برداشتن تکه‌ای از یک جنس را ندارد. برای این مسئله راه حل حریصانه‌ای وجود ندارد و به ارائه یک راه حل پویا خواهیم پرداخت.

ایده حل این مسئله در حالت پویا یه ابن صورت هست که دزد یا جنس iام را برمی‌دارد یا برنمی‌دارد و براساس این دو حالت سود زیرمسئله ایجاد شده محاسبه می‌شود و از مسیری که جواب بیشینه را داده پیش خواهیم رفت. به عبارتی:

کد c[i,w] = c[i-1, w]

 if wi  ≥  0
 max [vi + c[i-1, w-wi], c[i-1, w]}
 if i &gt; 0 and w  ≥  wi

شبه کد Dynamic-0-1-knapsack (v, w, n, W)

 for w = 0 to W
 do c[0, w] = 0
 for i = 1 to n
 do c[i, 0] = 0
 for w = 1 to W
 do if wi  ≤  w
 then if vi + c[i-1, w-wi]
 then c[i, w] = vi + c[i-1, w-wi]
 else c[i, w] = c[i-1, w]
 else
 c[i, w] = c[i-1, w]

۲-کسری در این حالت از مسئه دزد می‌تواند قسمتی از یک جنس را بردارد و مثل حالت قبل ۰ و ۱ی نمی‌باشد. برای این مسئله راه حال حریصانه وجود داره و به این شکل هست که دزد تا می‌تواند جنس پرارزش تر را برداشته و درصورتی که نتوانست بیشترین کسر ممکن آن را برمی‌دارد.

تاریخچه

مسئلهٔ کوله پشتی بیش از یک قرن مورد مطالعه قرار گرفته و اولین بررسی در سال ۱۸۹۷ انجام گرفته‌است. هر چند اولین داده‌های ثبت شده در این مورد، به کارهای ریاضیدانی به نام (1884–1956) Tobias Dantzig برمی گردد، چیزی با عنوان مسئلهٔ کوله پشتی قبلاً در میان عامهٔ مردم وجود داشته‌است.

مسئلهٔ کوله پشتی درجه دوم، اولین بار توسط Hammer، Gallo و Simeone در سال ۱۹۶۰ مطرح شد.

در سال ۱۹۸۸، تحقیقی از دانشگاه استونی بروک بر روی مجموعه‌ای از الگوریتم‌ها، نشان داد که از میان ۷۵ مسئلهٔ الگوریتمی، مسئلهٔ کوله پشتی، ۱۸ امین مسئلهٔ معروف و ۴ امین مسئلهٔ پرکاربرد بعد از درخت کی دی، درخت پیشوندی و bin packing problem است.

منبع

تعریف سوال

شما یک کوله پشتی دارید که حجم ثابتی دارد. همچنین تعدادی وسیله نیز دارید که حجم هر کدام را به شما داده اند. می‌خواهید تعدادی از این وسیله‌ها را در کوله پشتی بریزید به طوری که بیشترین حجم ممکن از کوله پشتی اشغال شود. (فرض کنید شکل وسایل طوری است که فضای بی‌استفاده بین آن‌ها باقی نمی‌ماند.)

الگوریتم

این مسئله یکی از پایه‌ای‌ترین مسائل برنامه‌ریزی پویا است و صورت‌های مختلفی دارد که در انتها به آن‌ها و ایده‌ی اثبات‌شان اشاره می‌شود.
برای حل مدل ساده‌ی سوال، یک آرایه دوبعدی به نام d به ابعاد(n+1)×(W+1) را در نظر بگیرید که در آن n تعداد وسایل مختلفی که می‌توانیم در کوله‌پشتی بگذاریم وW حجم کوله‌پشتی است.
مقدارdi,j برابر یک است اگر و تنها اگر بتوان فقط با استفاده از i وسیله‌ی اول، دقیقا حجم j از کوله‌پشتی را پر کرد. یعنی یک زیرمجموعه‌ از i عضو اول وجود دارد که مجموع وزن‌شان j است. در غیر اینصورت، مقدارش برابر صفر است.
جواب مسئله بزرگترین اندیس jاست که dn,j برابر یک باشد.
مقداردهی اولیه: با استفاده از ۰ وسیله‌ی اول (استفاده نکردن از وسایل) فقط می‌توان حجم ۰ را تولید کرد (کوله‌پشتی خالی) پس تمام خانه‌های به صورت d0,j برابر صفر اند به جز d0,0 که برابر ۱ است.
به روز رسانی: برای به دست آوردن di,j دو حالت وجود دارد این که خود وسیله‌ی i ام در کوله‌پشتی نباشد که در این صورت باید برای این که مقدار یک شود، مقدار di−1,j برابر ۱ باشد. حالت دیگر این است که خود وسیله در کوله پشتی باشد. پس در این حالت مقدار در صورتی یک می‌شود که (مقدار حجم وسیله‌ی i ام را ai بگیریم) di−۱,j−ai با فرض j≥ai برابر یک باشد.

شبه کد:

d = {0} 
d[0][0] = 1 

for i from 1 to n 
	for j from 0 to W 
		d[i][j] = d[i-1][j] 
		if j   &gt;  = a[i]  and  d[i-1][j-a[i]] == 1
			d[i][j] = 1

اگر دقت کنید می‌بینید احتیاج خاصی به نگه داشتن یک آرایه‌ی دوبعدی نداریم چون برای محاسبه‌ی هر ستون، فقط به ستون قبلی احتیاج داریم و فقط باید ۲ ستون را نگه‌داریم. اما حتی می‌توانیم از این هم جلوتر برویم و فقط یک ستون داشته باشیم. اما در اینجا باید حواس‌مان باشد که اشتباه زیر را انجام ندهیم.
شبه کد با آرایه‌ی یک بعدی (اشتباه):

d = {0} 
d[0] = 1 

for i from 1 to n 
	for j from 0 to W 
		if j   &gt; =  a[i] and d[j-a[i]] == 1
			d[j] = 1

کد بالا یک مشکل دارد. به نظرتان مشکلش چیست؟
فرض کنید در فقط یک وسیله داریم مثلا با حجم ۲ واحد و حجم کوله‌پشتی برابر ۴ است. پس فقط می‌توان ۲ واحد از کوله‌پشتی را پر کرد. اما اگر شبه کد بالا را برای آن اجرا کنید، می‌بینید که مقدار d4 برابر یک است. چون با استفاده از وسیله‌ی اول که حجم دو واحد داشت، مقدار d2 را یک کردیم، اما بعد از این متوقف نشدیم بلکه چون مقدار d2 برابر یک بود، مقدار d4 را نیز برابر یک قرار دادیم. پس انگار بیش از یک وسیله با حجم دو داشتیم. در واقع این کد جواب مسئله‌ی دیگری به نام خرد کردن پولاست که در آن به تعداد نامتناهی از هر کدام از وسایل داریم.
حال بیایید سعی کنیم مشکل کد بالا را حل کنیم. مشکل این بود که اول با استفاده از وسیله‌ی اول (یا بقیه‌ی وسایل) مقدار خانه‌های پایین جدول را به روز رسانی کردیم و سپس دوباره با استفاده از همان وسیله، مقادیر خانه‌های بالاتر را نیز به روز رسانی کردیم. چطور می‌شود اگر خانه‌ها را به ترتیب دیگری پیمایش کنیم تا این مشکل پیش نیاید؟ حجم وسایل که نمی‌تواند منفی باشد. پس اگر بالا به پایین آرایه را به روز رسانی کنیم، این مشکل پیش نمی‌آید. خودتان هم کمی فکر کنید که چرا این روش درست است.
بر همین اساس کد را تغییر می‌دهیم. شبه کد با آرایه‌ی یک بعدی (درست):

d = {0} 
d[0] = 1 

for i from 1 to n 
	for j from W to 0 
		if j   &gt; =  a[i] and d[j-a[i]] 
			d[j] = 1

پیچیدگی‌ الگوریتم

پیچیدگی زمانی که در تمام حالت‌ها از O(n×W) است. مقدار حافظه‌ی مورد نیاز نیز O(W) است.

صورت‌های مختلف سوال

مثال: فرض کنید وسایلی که می‌خواهید در کوله‌پشتی بگذارید، علاوه‌بر حجم، ارزش نیز داشته باشند و هدف شما فقط بردن وسایلی باشد که در مجموع ارزش‌شان بیشترین مقدار ممکن باشد. الگوریتمی از O(n×W) برای حل این سوال بدهید.

پاسخ

تعریف آرایه‌ی d را به این صورت تغییر دهید که di,j یعنی با استفاده از i وسیله‌ی اول و حجم j حداکثر مجموع ارزش وسایل در کوله‌پشتی چقدر است. شیوه‌ی به روز رسانی شبیه سوال اصلی است و به خواننده محول می‌شود.

پیاده‌سازی اولیه

#include   &lt; iostream &gt; 
using namespace std; 
 
const int MAXN = 10*1000; 
const int MAXW = 100*1000; 
 
bool d[MAXW+10]; 
int p[MAXW+10]; 
int a[MAXN+10]; 
 
int main() 
{ 
	ios::sync_with_stdio(false); 
	int n, w; 
	cin   &gt;&gt;   n   &gt;&gt;   w; 
	for(int i=0; i  &lt; n; i++) cin &gt;&gt;   a[i]; 
 
	d[0] = 1; 
	for(int i=0; i  &lt; n; i++) for(int j=w; j &gt;  =a[i]; j--) 
			if( d[j] == 0 &amp;&amp; d[j-a[i]] == 1 ) 
			{ 
				d[j] = 1; 
				p[j] = a[i]; 
			} 
 
	int out = w; 
	for(; out  &gt; =  0; out--) 
		if( d[out] ) 
			break; 
 
	cout   &lt;&lt;   out   &lt;&lt;   endl; 
	while( out != 0 ) 
	{ 
		cout   &lt;&lt;   p[out]   &lt;&lt;   " "; 
		out -= p[out]; 
	} 
	cout   &lt;&lt;   endl; 
	return 0; 
}

منبع

مسئله کوله پشتی قسمت 1
مسئله کوله پشتی قسمت 2

دسامبر 12, 2019/0 دیدگاه /توسط hgadmin

مسئله کوله پشتی قسمت 1

آموزش های عمومی هوش مصنوعی

مسئله کوله پشتی که با عنوان‌های Knapsack یا Rucksack مطرح می‌شود، مسئله‌ای در بهینه‌سازی ترکیبیاتی است. فرض کنید مجموعه‌ای از اشیا، که هر کدام داری وزن و ارزش خاصی هستند در اختیار دارید. به هر شی تعدادی را تخصیص دهید به‌طوری‌که وزن اشیا انتخاب شده کوچکتر یا مساوی حدی از پیش تعیین شده، و ارزش آن‌ها بیشینه شود. علت نامگذاری این مسئله، جهانگردی است که کوله پشتی ای با اندازهٔ محدود دارد و باید آن را با مفیدترین صورت ممکن از اشیا پر کند.

معمولاً در تخصیص منابع با محدودیت‌های مالی، با این مسئله روبرو هستیم. همچنین مسائلی از این قبیل در ترکیبیات، نظریه پیچیدگی محاسباتی،رمزنگاری و ریاضیات کاربردی به چشم می‌خورد.

نسخهٔ مسئله تصمیم برای مسئلهٔ کوله پشتی، این سؤال است: “آیا ارزش V با انتخاب اشیایی با مجموع وزن کمتر یا مساوی W، قابل دستیابی است؟”

نمونه‌ای از مسئلهٔ کوله پشتی یک بعدی: چه جعبه‌هایی باید انتخاب شوند تا مقدار پول بیشینه شود اما وزن جعبه‌های مذکور بیشتر از ۱۵ کیلوگرم نشود؟ یک مسئله چند محدودیتی، می‌تواند هم وزن و هم حجم جعبه‌ها را در نظر بگیرد. مدل‌سازی اندازه و شکل جعبه‌ها، یک مسئله بسته‌بندی است.
(راه حل: اگر هر تعداد دلخواهی از جعبه‌ها در دسترس باشد، ۳ جعبهٔ زرد و ۳ جعبهٔ خاکستری پاسخ‌اند. اما اگر مطابق شکل باشد، یعنی از هر جعبه فقط یکی داشته باشیم، تمامی جعبه‌ها به جز جعبهٔ سبز را انتخاب می‌کنیم)

تعریف

مسئله کوله پشتی چیست؟ فرض کنید که جهانگردی می‌خواهدکوله پشتی خود را با انتخاب حالتهای ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می‌سازند پر کند. این مسئله می‌تواند با شماره‌گذاری این وسائل از ۱ تا n و تعریف برداری از متغیرهای دودویی(Binary) (j = ۱٬۲,۳…n) به صورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می‌آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است، که محدودیت را برآورده کند. بطوری‌که تابع هدف ماکزیمم مقدار خود را بگیرد به عنوان نمونه‌ای از مسائلی که می‌توانند به صورت مسئله کوله پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه‌گذاری همه یا قسمتی ازسرمایه‌تان باشید. اگر مبلغی که برای سرمایه‌گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه‌گذاری ممکن باشد، اجازه دهیدکه سود حاصل از سرمایه‌گذاری j ام و مقدار دلارهایی باشد که آن سرمایه‌گذاری لازم دارد. بدین ترتیب جواب بهینه مسئله کوله پشتی که تعریف کردیم به ما این امکان را می دهدکه بهترین حالت ممکن را از بین حالتهای مختلف سرمایه‌گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد. یک روش ابتدایی که در نگاه اول توجه ما را به خود جلب می‌کند، عبارت از برنامه‌نویسی برای کامپیوتر به منظور امتحان کردن تمامی بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می‌کنند بهترین را انتخاب کند. متأسفانه تعداد چنین بردارهایی است. بطوری‌که یک کامپیوتر فرضی که می‌تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛ برای n = ۶۰ بیش از ۳۰ سال وقت لازم دارد و بیش از ۶۰ سال برای n = ۶۱ و ده‌ها قرن برای n = ۶۵ والی آخر. با این وجود، با استفاده از الگوریتمهایی خاص می‌توان در بسیاری موارد مسئله‌ای با n = ۱۰۰ ۰۰۰ را در عرض چند ثانیه روی یک کامپیوتر کوچک حل کرد __________________

فرض کنید $n$ جسم داریم که از $1$ تا $n$ شماره‌گذاری شده‌اند. جسم $i$ ام ارزشی معادل $v_{i}$ و وزنی برابر با $w_i$ دارد. معمولاً فرض می‌شود که وزن‌ها و ارزش‌ها نامنفی‌اند. برای ساده‌تر شدن نمایش، بدون کم شدن از کلیت مسئله می‌توان فرض کرد اشیا به ترتیب صعودی بر حسب وزنشان مرتب شده‌اند. بیشترین وزنی که می‌توان در کوله پشتی حمل کرد، $W$ است.

معروف‌ترین نوع از این مسئله، مسئلهٔ کوله پشتی ۰ و ۱ است. یعنی تعداد از هر شی، یا ۰ است (آن شی را انتخاب نمی‌کنیم) یا ۱ (آن شی انتخاب می‌شود). مسئلهٔ کوله پشتی ۰ و ۱ را می‌توان به این صورت، به زبان ریاضی بیان کرد:

مقدار $\qquad \sum _{i=1}^{n}v_{i}x_{i}$ را بیشینه کنید.
به‌طوری‌که $\qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad x_{i}\in \{0,1\}$

مسئلهٔ کوله پشتی کران دار، نسخهٔ دیگری از این سؤال است که در آن تعداد اشیا ( $x_i$ ) عددی صحیح و نامنفی و حد اکثر برابر با $c_{i}$ است. به بیان ریاضی:

مقدار $\qquad \sum _{i=1}^{n}v_{i}x_{i}$ را بیشینه کنید.
به‌طوری که $\qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad x_{i}\in \{0,1,\ldots ,c_{i}\}$

مسئلهٔ کوله پشتی بیکران (UKP)، هیچ محدودیتی روی تعداد اشیا قائل نمی‌شود. یعنی از هر شی، به هر تعداد دلخواهی می‌توان انتخاب کرد. نسخه‌ای ازین سؤال که بیش از همه مورد توجه قرار می‌گیرد، دارای ویژگی‌های زیر است:

یک مسئله تصمیم است.
مسئله ۰ و ۱ است.
برای هر شی، وزن و ارزش آن برابرند. یعنی $w_{i}=v_{i}$ .

دقت کنید که در این مورد خاص، این مسئله هم ارز است با: ” مجموعه‌ای از اعداد صحیح نا منفی داده شده‌است. آیا زیر مجموعه‌ای از آن وجود دارد که جمع اعضایش دقیقاً $W$ شود؟” و چنانچه وزن‌های منفی هم قابل قبول باشند، و $W$ برابر با $0$ در نظر گرفته شود، مسئله عبارت است از: ” مجموعه‌ای از اعداد صحیح داده شده‌است. آیا زیر مجموعه‌ای غیر تهی از آن هست که جمع اعضایش $0$ شود؟” این مسئله خاص، مسئله جمع زیرمجموعه‌ها نامیده می‌شود. در رمزنگاری، هر گاه از مسئله کوله پشتی نام برده می‌شود، منظور مسئله جمع زیرمجموعه‌ها است.

چنانچه چند کوله پشتی داشته باشیم، مسئله تبدیل به سؤال bin packing می‌شود.

پیچیدگی محاسباتی

از دید علوم کامپیوتر، مسئلهٔ کوله پشتی شایان توجه است زیرا:

الگوریتمی با زمان اجرای شبه چندجمله‌ای با استفاده از برنامه‌نویسی پویا دارد.
الگوریتمی تقریبی با زمان چندجمله‌ای دارد که از الگوریتم‌های با زمان شبه چندجمله‌ای به عنوان یک زیر-برنامه استفاده می‌کند.
حل دقیق این سؤال، مسئله‌ای از نوع NP-complete است؛ بنابراین پیش‌بینی شده که راه حلی که هم درست و هم سریع باشد (با زمان اجرای چندجمله‌ای) برای هر ورودی دلخواه، ندارد.

مسئله جمع زیر مجموعه‌ها که نسخه‌ای از مسئلهٔ کلی کوله پشتی است، به عنوان یکی از 21 مسئلهٔ NP-کاملِ Karp مطرح است.

تلاش‌هایی برای استفاده از مسئلهٔ جمع زیر مجموعه‌ها به عنوان اصل در سیستم‌های رمزنگاری کلید عمومی، مانند سیستم رمزنگاری کوله پشتی مرکل-هلمن انجام شد. در این روش‌ها، معمولاً ازگروه‌هایی به جز اعداد صحیح استفاده می‌شد. Merkle-Hellman و الگوریتم‌های مشابه دیگر بعداً با شکست روبرو شدند، زیرا مسائل خاصی که تولید می‌کردند در زمان چندجمله‌ای قابل حل بودند.

در خیلی از تحقیقات سعی می‌شود به این سؤال پاسخ داده شود که نمونه‌های سخت مسئلهٔ کوله پشتی چه هستند؟ یا از دید دیگر، چه ویژگی‌هایی از مثال‌های مسئلهٔ کوله پشتی، باعث می‌شود در زمانی معقولتر نسبت به آنچه در صورت کلی NP-completeِ سؤال مطرح است، حل شوند. . الگوریتم‌های زیادی بر پایه ی: برنامه‌نویسی پویا، روش تقسیم و حد، یا ترکیبی از هر دو روش برای این مسئله وجود دارند.

راه حل برنامه‌نویسی پویا

مسئلهٔ کوله پشتی بیکران

اگر تمام وزن‌ها ( $w_{1},\ldots ,w_{n},W$ ) اعداد صحیح نامنفی باشند، مسئلهٔ کوله پشتی در زمانی شبه چندجمله‌ای با استفاده از برنامه‌نویسی پویا قابل حل است.

برای سادگی فرض کنید تمام وزن‌ها اکیداً مثبت اند ( $w_{i}>0$ ). می‌خواهیم جمع ارزش کالاهای انتخاب شده را بیشینه کنیم با این فرض که مجموع وزن آن‌ها حداکثر $W$ شود. حال برای هر $w<W$ ، مقدار $m[w]$ را بیشترین ارزش قابل دستیابی تعریف کنید به‌طوری‌که جمع وزن اشیا انتخاب شده حد اکثر $w$ شود. بدیهی است که $m[W]$ پاسخ مورد نظر است.

دقت کنید که $m[w]$ ویژگی‌های زیر را دارد:

$m[0]=0\,\!$ (جمع اعضای مجموعهٔ تهی ۰ است)
$m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])$ که $v_{i}$ ارزش شی i ام است.

بیشترین ارزش قابل دستیابی از مجموعهٔ تهی، ۰ است. برای محاسبهٔ هر کدام از $m[w]$ ‌ها، باید $n$ شی را بررسی کرد. همچنین آرایهٔ $W$ ، $m$ عنصر دارد. بنابراین زمان اجرای این الگوریتم $O(nW)$ است. بدیهی است با تقسیم کردن $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ بر بزرگترین مقسوم علیه مشترک شان، می‌توان زمان اجرای الگوریتم را بهینه کرد.

پیچیدگی زمانی $O(nW)$ تناقضی با NP-complete بودن مسئلهٔ کوله پشتی ندارد. زیرا $W$ برخلاف $n$ ، برحسب ورودی چندجمله‌ای نیست. طول $W$ ِ ورودی، متناسب با تعداد بیت‌های لازم برای نمایش $W$ ، یعنی $\log W$ است، نه خود $W$ .

مسئلهٔ کوله پشتی ۰ و ۱

روش مشابهی با استفاده از برنامه‌سازی پویا برای حل مسئله کوله پشتی ۰ و ۱ با پیچیدگی زمانی شبه چندجمله‌ای وجود دارد. مانند بالا، فرض کنید $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ ‌ها اعداد صحیح اکیداً مثبتی هستند. $m[i,w]$ را بیشترین ارزش قابل دستیابی، با استفاده از اشیای ۱ تا $i$ با حد اکثر وزن $w$ تعریف کنید.

$m[i,w]$ را می‌توان به‌طور بازگشتی، مطابق زیر تعریف کرد:

$m[0,\,w]=0$
$m[i,\,0]=0$
$m[i,\,w]=m[i-1,\,w]$ اگر $w_{i}>w\,\!$
$m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ اگر $w_{i}\leqslant w$ .

پاسخ با محاسبهٔ $m[n,W]$ بدست می‌آید. برای کارآمد شدن راه حل، می‌توان از جدولی برای نگهداری نتایج محاسبات قبلی استفاده کرد؛ بنابراین پیچیدگی زمانی آن $O(nW)$ و حافظه $O(nW)$ خواهد شد. همچنین می‌توان حجم حافظه را به $O(W)$ کاهش داد. به این ترتیب که آرایهٔ یک بعدی $m[w]$ ، ارزش بهینه تا کنون را نشان می‌دهد. از $i=1$ شروع کرده، آرایه را پر می‌کنیم. سپس با حرکت بر روی $i$ ، مقدار $m[w]$ را با افزدون یک شی جدید به انتخاب‌ها، به روز آوری می‌کنیم.

الگوریتم دیگری برای مسئله کوله پشتی ۰ و ۱، در سال ۱۹۷۴ ارائه شد که گاهی «رویارویی در میانه» نیز نامیده می‌شود. این الگوریتم نسبت به تعداد اشیا نمایی است. (این اسم، از الگوریتمی مشابه در رمزنگاری نشات گرفته‌است). هنگامی که $W$ نسبت به $n$ بسیار بزرگتر باشد (یعنی $W$ از $2^n$ هم بزرگتر باشد)، این الگوریتم نسبت به روش پویا از نظر زمانی بهینه تر است. برای مثال فرض کنید $w_i$ ‌ها نامنفی باشند، اما صحیح نباشند. در اینجا نیز می‌توان از روش پویا استفاده کرد: اگر عددها $d$ رقم بعد از اعشار داشته باشند، کافی است آن‌ها را در $10^{d}$ ضرب و سپس رند کرد (با استفاده از محاسبات ممیز ثابت). روش پویا با این تغییرات، از مرتبهٔ زمانی $O(nW*10^{d})$ و حافظهٔ $O(W*10^{d})$ خواهد بود.

الگوریتم «رویارویی در میانه» به صورت زیر است:

مجموعهٔ ${1,2,\ldots ,n}$ را به دو مجموعهٔ $A$ و $B$ با اندازهٔ نسبتاً برابر تقسیم کنید.
ارزش‌ها و وزن‌های هر زیر مجموعه از هریک از $A$ و $B$ را بدست آورید.
برای هر زیرمجموعه از $A$ ، بهترین مکمل $B$ را از زیر مجموعه‌هایش انتخاب کنید: به عبارتی زیر مجموعه‌ای از $B$ با بیشترین جمع ارزش کالاها، به نحوی که جمع وزن‌های دو زیر مجموعه، از $W$ بیشتر نشود. بیشترین ارزش بدست آمده را ذخیره کنید.

این الگوریتم از مرتبهٔ حافظهٔ $O(2^{n/2})$ است و با پیاده‌سازی بهینه گام ۳، از مرتبهٔ زمانی $O(n*2^{n/2})$ می‌شود. (برای مثال با مرتب کردن زیرمجموعه‌های $B$ بر حسب وزن، چشم پوشی از زیر مجموعه‌هایی از $B$ که وزنی بیشتر از سایر زیر مجموعه‌ها با ارزش بزرگتر/مساوی دارند و استفاده از جستجوی دودویی برای یافتن بهترین تطابق). مانند روش رویارویی در میانه در رمز نگاری، استفاده از این الگوریتم با هزینه کردن حافظه (مرتبهٔ نمایی به جای مقدار ثابت) باعث بهینه شدن زمان اجرا می‌شود. می‌دانیم چنانچه بخواهیم تمام زیر مجموعه‌های {1…n} را به روش brute force بررسی کنیم، مرتبهٔ زمانی $O(n*2^{n})$ خواهد شد اما با این الگوریتم آن را بهینه کردیم.

الگوریتم تقریبی حریصانه

George Dantzig الگوریتمی تقریبی از نوع حریصانه برای حل مسئله کوله پشتی بیکران ارائه داد.

به این ترتیب که اشیا را به ترتیب نزولی بر حسب ارزش به واحد وزن مرتب می‌کند ( $v_{i}/w_{i}$ ) سپس از شی شماره ۱ شروع می‌کند. بیشترین تعداد ممکن از آن را در کوله پشتی قرار می‌دهد، تا زمانی که دیگر جای خالی ای برای آن نوع باقی نماند. آنگاه سراغ شی بعدی می‌رود. (دقت کنید که در این نسخه از سؤال، محدودیتی برای تعداد اشیا نداریم) اگر $m$ بیشینه ارزش اشیایی باشد که در کوله پشتی جا می‌شوند، این الگوریتم حداقل به مقدار $m/2$ دست می‌یابد. اما اگر تعداد مجاز از هر شی محدود باشد، ممکن است خروجی این الگوریتم از پاسخ بهینه بسیار دور باشد.

مسئله کوله پشتی قسمت 1
مسئله کوله پشتی قسمت 2

دسامبر 11, 2019/توسط daliri

خوشه بندی (Clustering) قسمت 4

آموزش عمومی پردازش تصویر و بینایی ماشین

خوشه‌بندی سلسله مراتبی (Hierarchical Clustering)

برعکس خوشه‌بندی تفکیکی که اشیاء را در گروه‌های مجزا تقسیم می‌کند، «خوشه‌بندی سلسله مراتبی» (Hierarchical Clustering)، در هر سطح از فاصله، نتیجه خوشه‌بندی را نشان می‌دهد. این سطوح به صورت سلسله مراتبی (Hierarchy) هستند.

برای نمایش نتایج خوشه‌بندی به صورت سلسله مراتبی از «درختواره» (Dendrogram) استفاده می‌شود. این شیوه، روشی موثر برای نمایش نتایج خوشه‌بندی سلسله مراتبی است. در تصویر ۲ نتایج خوشه‌بندی سلسله مراتبی روی داده‌های $s = 1, 3, 6, 2, 8, 10$ با استفاده از درختواره را می‌بینید.

تصویر ۲- نمودار دختواره برای داده‌های مربوط s=1,3,6,2,8,10

همانطور که در تصویر ۲ قابل رویت است،‌ ابتدا هر مقدار یک خوشه محسوب می‌شود. در طی مراحل خوشه‌بندی، نزدیکترین مقدارها (براساس تابع فاصله تعریف شده) با یکدیگر ادغام شده و خوشه جدیدی می‌سازند.

در نتیجه براساس تصویر ۲ ابتدا در مرحله اول مقدار اول و چهارم تشکیل اولین خوشه را می‌دهند، زیرا کمترین فاصله را دارند. سپس در مرحله دو، مقدار دوم با خوشه تشکیل شده در مرحله اول ترکیب می‌شود. در مرحله سوم مقدارهای سوم و ششم با هم تشکیل یک خوشه می‌دهند که در مرحله چهارم با مقدار پنجم ترکیب شده و خوشه جدیدی می‌سازند.

در انتها نیز خوشه تشکیل شده در مرحله دوم با خوشه تشکیل شده در مرحله چهارم ادغام شده و خوشه نهایی را ایجاد می‌کنند. همانطور که دیده می‌شود با داشتن شش مقدار خوشه‌بندی سلسله مراتبی، پنچ مرحله خواهد داشت زیرا در هر مرحله فقط یک عمل ادغام انجام می‌شود.

نکته: توجه داشته باشید که مقدارهایی که روی محور افقی دیده می‌شوند، بیانگر موقعیت مقدارها در لیست داده‌ها است و نه خود مقادیر. همچنین محور عمودی نیز فاصله یا ارتفاع بین خوشه‌ها را نشان می‌دهد.

در الگوریتم خوشه‌بندی سلسله مراتبی معمولا با کوچکترین خوشه‌ها شروع می‌کنیم. به این معنی که در ابتدا هر مقدار بیانگر یک خوشه است. سپس دو مقداری که بیشترین شباهت (کمترین فاصله) را دارند با یکدیگر ادغام شده و یک خوشه جدید می‌سازند. بعد از این مرحله، ممکن است دو مقدار یا یک مقدار با یک خوشه یا حتی دو خوشه با یکدیگر ادغام شده و خوشه جدیدی ایجاد کنند.

این عملیات با رسیدن به بزرگترین خوشه که از همه مقدارها تشکیل یافته پایان می‌یابد. به این ترتیب اگر n مقدار داشته باشیم در مرحله اول تعداد خوشه‌ها برابر با n‌ است و در آخرین مرحله یک خوشه باقی خواهد ماند.

برای اندازه‌گیری فاصله بین دو خوشه یا یک مقدار با یک خوشه از روش‌های «پیوند» (Linkage) استفاده می‌شود. از انواع روش‌های پیوند می‌توان به «نزدیکترین همسایه» (Nearest Neighbor) یا «پیوند تکی» (Single Linkage)، «دورترین همسایه» (Furthest Neighbor) یا «پیوند کامل» (Complete Linkage) و همچنین «پیوند میانگین» (Average Linkage) اشاره کرد.

معمولا به این شیوه خوشه‌بندی سلسله مراتبی، روش «تجمیعی» (Agglomerative) می‌گویند.

برعکس اگر عمل خوشه‌بندی سلسله مراتبی به شکلی باشد که با بزرگترین خوشه، عملیات خوشه‌بندی شروع شده و با تقسیم هر خوشه به خوشه‌های کوچکتر ادامه پیدا کند، به آن «خوشه‌بندی سلسله مراتبی تقسیمی» (Divisive Hierarchical Clustering) می‌گویند. در آخرین مرحله این روش، هر مقدار تشکیل یک خوشه را می‌دهد پس n خوشه خواهیم داشت.

هر چند شیوه نمایش خوشه‌بندی سلسله مراتبی تقسیمی نیز توسط درختواره انجام می‌شود ولی از آنجایی که محدودیت‌هایی برای تقسیم یک خوشه به زیر خوشه‌های دیگر وجود دارد، روش تقسیمی کمتر به کار می‌رود.

نکته: در شیوه خوشه‌بندی سلسله مراتبی، عمل برچسب گذاری در طی مراحل خوشه‌بندی اصلاح پذیر نیست. به این معنی که وقتی عضوی درون یک خوشه قرار گرفت هرگز از آن خوشه خارج نمی‌شود.

از الگوریتم‌های معروف برای خوشه‌بندی سلسله مراتبی تجمیعی می‌توان به AGNES و برای تقسیمی به DIANA اشاره کرد.

خوشه‌بندی برمبنای چگالی (Density-Bases Clustering)

روش‌های خوشه‌بندی تفکیکی قادر به تشخیص خوشه‌هایی کروی شکل هستند. به این معنی که برای تشخیص خوشه‌ها از مجموعه داده‌هایی به شکل‌های «کوژ» (Convex) یا محدب خوب عمل می‌کنند. در عوض برای تشخیص خوشه‌ها برای مجموعه داده‌های «کاو» (Concave) یا مقعر دچار خطا می‌شوند. به تصویر ۳ توجه کنید که بیانگر شکل‌های کاو است.

تصویر ۳- مقایسه نتایج خوشه‌بندی تفکیکی با روش چگالی

همانطور که دیده می‌شود میانگین هر دو خوشه در روش k-means در محلی قرار گرفته است که مربوط به خوشه‌ دیگر است. در حالی که خوشه‌بندی برمبنای چگالی به خوبی نقاط را در خوشه‌های درست قرار داده است.

در الگوریتم‌ها خوشه‌بندی برمبنای چگالی، نقاط با تراکم زیاد شناسایی شده و در یک خوشه قرار می‌گیرند. از الگوریتم‌های معروف در این زمینه می‌توان به DBSCAN اشاره کرد که در سال ۱۹۹۶ توسط «استر» (Ester) معرفی شد.

این الگوریتم توانایی شناسایی نقاط دورافتاده را داشته و می‌تواند تاثیر آن‌ها را در نتایج خوشه‌بندی از بین ببرد. شیوه کارکرد این الگوریتم‌ بنا به تعریف‌های زیر قابل درک است:

همسایگی به شعاع : اگر فضای با شعاع $ϵ$ را حول نقطه‌ای x در نظر بگیریم، یک همسایگی ایجاد کرده‌ایم که به شکل $N_{ϵ} (x)$ نشان داده می‌شود. شکل ریاضی این همسایگی به صورت زیر است.

$N_{ϵ} (x) = {y \in D; d (x, y) \leq ϵ}$

بطوری که D مجموعه داده و d تابع فاصله است. تصویر 4 مفهوم همسایگی را نشان می‌دهد.

تصویر ۴- همسایگی و شعاع همسایگی

قابل دسترسی مستقیم (Directly density-reachable): نقطه x را قابل دسترسی مستقیم از y می‌نامند اگر براساس دو پارامتر $N_{m i n}$ و $ϵ$ داشته باشیم:

$x \in N_{ϵ} (y)$

$| N_{ϵ} (y) | \geq N_{m i n}$

در اینجا $| N_{ϵ} (y)$ نشانگر تعداد اعضای همسایگی به شعاع $ϵ$ از نقطه y است.

پس شرط اول به معنی این است که x در همسایگی از y قرار دارد و شرط دوم نیز بیان می‌کند که باید تعداد اعضای همسایگی y از حداقل تعداد اعضای همسایگی بیشتر باشد.

نقطه قابل دسترسی (Density-Reachable): نقطه x را از طرق y‌ نامیده می‌شود، اگر دنباله‌ای از نقاط مثل $x_{1}, x_{2}, \dots, x_{i}$ موجود باشند که نقطه x را به y برسانند. یعنی:

$x = x_{1}, x_{2}, \dots, x_{i} = y$

در این حالت برای مثال $x_{1}$ «قابل دسترسی مستقیم» (Direct Reachable) به $x_{2}$ ‌ نامیده می‌شود.

نقاط متصل (Density-Connected): دو نقطه x و y را متصل گویند اگر براساس پارامترهای $ϵ$ و $N_{m i n}$ نقطه‌ای مانند z وجود داشته باشد که هر دو نقطه x و y از طریق آن قابل دسترسی باشند.
خوشه (Cluster): فرض کنید مجموعه داده D موجود باشد. همچنین C یک زیر مجموعه غیر تهی از D‌ باشد. C را یک خوشه می‌نامند اگر براساس پارمترهای $ϵ$ و $N_{m i n}$ در شرایط زیر صدق کند:

۱- اگر x درون C باشد و y نیز قابل دسترسی به x با پارامترهای $ϵ$ و $N_{m i n}$ باشد، آنگاه y نیز در C‌ است.

۲- اگر دو نقطه x و y در C باشند آنگاه این نقاط براساس پارامترهای $ϵ$ و $N_{m i n}$ نقاط متصل محسوب شوند.

به این ترتیب خوشه‌ها شکل گرفته و براساس میزان تراکمشان تشکیل می‌شوند. نویز یا نوفه (Noise) نیز نقاطی خواهند بود که در هیچ خوشه‌ای جای نگیرند. برای روشن شدن این تعریف‌ها به تصویر 5 توجه کنید.

تصویر ۵- نقاط مرکزی، مرزی، نوفه (نویز)

نکته: با توجه به تعریف خوشه، مشخص است که اندازه هر خوشه از $N_{m i n}$ بیشتر است.

مراحل خوشه‌بندی برمبنای چگالی به این ترتیب است که ابتدا یک نقطه را به صورت اختیاری انتخاب کرده و نقاط قابل دسترس برای آن پیدا می‌شود. اگر x یک نقطه مرکزی باشد (نقطه‌ای که درون خوشه قرار داشته باشد)، خوشه را تشکیل می‌دهد ولی اگر x نقطه‌ای مرزی باشد (نقطه‌ای که در لبه‌های خوشه قرار داشته باشد) آنگاه هیچ نقطه‌ قابل دسترسی برای x وجود نخواهد داشت و الگوریتم از نقطه‌ای دیگری ادامه پیدا می‌کند.

در مراحل خوشه‌بندی ممکن است دو خوشه که به یکدیگر نزدیک باشند، ادغام شوند. فاصله بین دو خوشه برحسب حداقل فاصله بین اعضای دو خوشه (پیوند تکی) سنجیده می‌شود.

نکته: انتخاب مقدار برای پارامترهای $ϵ$ و $N_{m i n}$ مسئله مهمی است که براساس نظر محقق باید به الگوریتم داده شوند. ترسیم نمودار داده‌ها در انتخاب این پارامترها می‌تواند موثر باشد. هرچه داده‌ها در دسته‌های متراکم‌تر دیده شوند بهتر است مقدار $ϵ$ را کوچک در نظر گرفت و اگر لازم است که تعداد خوشه‌ها کم باشند بهتر است مقدار $N_{m i n}$ را بزرگ انتخاب کرد.

خوشه‌بندی برمبنای مدل (Model-Based Clustering)

در روش‌های پیشین، فرضیاتی مبنی بر وجود یک توزیع آماری برای داده‌ها وجود نداشت. در روش «خوشه‌بندی برمبنای مدل» (Model-Based Clustering) یک توزیع آماری برای داده‌ها فرض می‌شود. هدف در اجرای خوشه‌بندی برمبنای مدل، برآورد پارامترهای توزیع آماری به همراه متغیر پنهانی است که به عنوان برچسب خوشه‌ها در مدل معرفی شده.

با توجه به تعداد خوشه‌هایی که در نظر گرفته شده است، مثلا k، تابع درستنمایی را برای پیدا کردن خوشه‌ها به صورت زیر می‌نویسند:

$L_{M} (Θ_{1}, Θ_{2}, Θ_{3}, \dots, Θ_{k}; t_{1}, t_{2}, \dots, t_{k}) = n \prod i = 1 k \sum j = 1 t_{j} f_{j} (x_{i}, Θ_{j})$

در رابطه بالا $t_{j}$ بیانگر احتمال تعلق نقطه به خوشه jام و $f_{j}$ نیز توزیع آمیخته با پارامترهای $Θ_{j}$ است.

در اکثر مواقع برای داده‌ها توزیع نرمال آمیخته در نظر گرفته می‌شود. در چنین حالتی توزیع آمیخته را به فرمی می‌نویسند که درصد آمیختگی (درصدی از داده‌ها که متعلق به هر توزیع هستند) نیز به عنوان پارامتر در مدل حضور دارد.

$f (x) = k \sum j = 1 p_{j} Φ (X; μ_{j}, Σ_{i})$

در رابطه بالا $Φ$ توزیع نرمال با پارامترهای $μ_{j}$ و $Σ_{j}$ برای توزیع jام هستند و $p_{j}$ ‌ نیز درصد آمیختگی برای توزیع jام محسوب می‌شود. در تصویر 6 یک نمونه از توزیع آمیخته نرمال دو متغیره نمایش داده شده است.

تصویر ۶- توزیع آمیخته نرمال دو متغیره

انتخاب‌های مختلفی برای ماتریس واریانس-کوواریانس یا $Σ$ وجود دارد. یکی از این حالت‌ها در نظر گرفتن استقلال و یکسان بودن واریانس برای همه توزیع‌ها است. همچنین می‌توان واریانس هر توزیع را متفاوت از توزیع‌های دیگر در نظر گرفت و بدون شرط استقلال عمل کرد. در حالت اول پیچیدگی مدل و تعداد پارامترهای برآورد شده کم و در حالت دوم پیچیدگی مدل و تعداد پارامترهای برآورده شده زیاد خواهد بود.

برای برآورد پارامترهای چنین مدلی باید از تابع درستنمایی استفاده کرد و به کمک مشتق مقدار حداکثر را برای این تابع بدست آورد. با این کار پارامترهای مدل نیز برآورد می‌شوند. ولی با توجه به پیچیدگی تابع درستنمایی می‌توان از روش‌هایی ساده‌ و سریع‌تری نیز کمک گرفت. یکی از این روش‌ها استفاده از الگوریتم EM‌ (مخفف Expectation Maximization) است. در الگوریتم EM که براساس متغیر پنهان عمل می‌کند، می‌توان به حداکثر مقدار تابع درستنمایی همراه با برآورد پارامترها دست یافت.

در چنین حالتی می‌توان برچسب تعلق هر مقدار به خوشه را به عنوان متغیر پنهان در نظر گرفت. اگر متغیر پنهان را $z_{i j}$ ‌ در نظر بگیریم مقداری برابر با ۱ دارد اگر مشاهده iام در خوشه jام باشد و در غیر اینصورت مقدار آن 0 خواهد بود.

منبع

منابع

1.https://fa.wikipedia.org

2.https://tik4.com

3.https://blog.faradars.org

خوشه بندی (Clustering) قسمت 1
خوشه بندی (Clustering) قسمت 2
خوشه بندی (Clustering) قسمت 3
خوشه بندی (Clustering) قسمت 4

دسامبر 10, 2019/0 دیدگاه /توسط hgadmin

خوشه بندی (Clustering) قسمت 3

آموزش عمومی پردازش تصویر و بینایی ماشین

هدف از خوشه بندی چیست؟

همانطور که می‌دانید از داده‌ کاوی برای کاوش در اطلاعات و کشف دانش استفاده می‌شود. برای اینکار الگوریتم‌های متعددی وجود دارد که هر یک برای هدف خاصی کاربرد دارند

خوشه بندی چیست؟

خوشه بندی

کلاسترینگ(Clustering) یا خوشه‌ بندی از جمله الگوریتم‌های قطعه بندی به حساب می‌آید. الگوریتم خوشه‌بندی اطلاعاتی را که ویژگی‌های نزدیک به هم و مشابه دارند را در دسته‌های جداگانه که به آن خوشه گفته می‌شود قرار می‌دهد. به بیان دیگر خوشه‌بندی همان دسته‌بندی‌های ساده‌ای است که در کارهای روزانه انجام می‌دهیم. وقتی با یک مجموعه کوچک از صفات روبرو باشیم دسته بندی به سادگی قابل اجرا است، برای مثال در یک مجموعه ‌از خودکارهای آبی، مشکی، قرمز و سبز به راحتی می‌توانیم آن‌ها را در ۴ دسته قرار دهیم اما اگر در همین مجموعه ویژگی‌های دیگری مثل سایز، شرکت سازنده، وزن، قیمت و… مطرح باشد کار کمی پیچیده می‌شود. حال فرض کنید در یک مجموعه متشکل از هزاران رکورد و صدها ویژگی قصد دسته بندی دارید، چگونه باید این کار را انجام دهید؟!

بخش بندی داده‌ها به گروه‌ها یا خوشه‌های معنادار به طوری که محتویات هر خوشه ویژگی‌های مشابه و در عین حال نسبت به اشیاء دیگر در سایر خوشه‌ها غیر مشابه باشند را خوشه‌بندی می‌گویند. از این الگوریتم در مجموعه داده‌های بزرگ و در مواردی که تعداد ویژگی‌های داده زیاد باشد استفاده می‌شود.

هدف خوشه بندی (Clustering) یافتن خوشه های مشابه از اشیاء در بین نمونه های ورودی می باشد اما چگونه می توان گفت که یک خوشه بندی مناسب است و دیگری مناسب نیست؟ در حقیقت سوال اصلی این است که کدام روش خوشه بندی برای هر مجموعه داده ای مناسب خواهد بود؟ می توان نشان داد که هیچ معیار مطلقی برای بهترین خوشه بندی وجود ندارد بلکه این بستگی به مساله و نظر کاربر دارد که باید تصمیم بگیرد که آیا نمونه ها بدرستی خوشه بندی شده اند یا خیر؟ با این حال معیار های مختلفی برای خوب بودن یک خوشه بندی ارائه شده است که می تواند کاربر را برای رسیدن به یک خوشه بندی مناسب راهنمایی کند که در بخشهای بعدی چند نمونه از این معیارها آورده شده است. یکی از مسایل مهم در خوشه بندی انتخاب تعداد خوشه ها می باشد. در بعضی از الگوریتم ها تعداد خوشه ها از قبل مشخص شده است و در بعضی دیگر خود الگوریتم تصمیم می گیرد که داده ها به چند خوشه تقسیم شوند.

خوشه بندی داده ها

خوشه بندی یا Clustering یکی از شاخه های یادگیری بدون نظارت (Unsupervised) می باشد و فرآیند خود کاری است که در طی آن، نمونه ها به دسته هایی که اعضای آن مشابه یکدیگر می باشند تقسیم می شوند که به این دسته ها خوشه (Cluster) گفته می شود. بنابراین خوشه مجموعه ای از اشیاء می باشد که در آن اشیاء با یکدیگر مشابه بوده و با اشیاء موجود در خوشه های دیگر غیر مشابه می باشند. برای مشابه بودن می توان معیارهای مختلفی را در نظر گرفت مثلا می توان معیار فاصله را برای خوشه بندی مورد استفاده قرار داد و اشیائی را که به یکدیگر نزدیکتر هستند را بعنوان یک خوشه در نظر گرفت که به این نوع خوشه بندی، خوشه بندی مبتنی بر فاصله نیز گفته می شود. بعنوان مثال در شکل ۱ نمونه های ورودی در سمت چپ به چهار خوشه مشابه شکل سمت راست تقسیم می شوند. در این مثال هر یک از نمونه های ورودی به یکی از خوشه ها تعلق دارد و نمونه ای وجود ندارد که متعلق به بیش از یک خوشه باشد.

خوشه بندی

بعنوان یک مثال دیگر شکل ۲ را در نظر بگیرید در این شکل هر یک از دایره های کوچک یک وسیله نقلیه (شیء) را نشان می دهد که با ویژگی های وزن و حداکثر سرعت مشخص شده اند. هر یک از بیضی ها یک خوشه می باشد و عبارت کنار هر بیضی برچسب آن خوشه را نشان می دهد. کل دستگاه مختصات که نمونه ها در آن نشان داده شده اند را فضای ویژگی می گویند.

خوشه بندی

همانطور که در شکل می بینید وسایل نقلیه به سه خوشه تقسیم شده اند. برای هر یک از این خوشه ها می توان یک نماینده در نظر گرفت مثلا می توان میانگین وسایل نقلیه باری را محاسبه کرد و بعنوان نماینده خوشه وسایل نقلیه باری معرفی نمود. در واقع الگوریتمهای خوشه بندی اغلب بدین گونه اند که یک سری نماینده اولیه برای نمونه های ورودی در نظر گرفته می شود و سپس از روی میزان تشابه نمونه ها با این نماینده های مشخص می شود که نمونه به کدام خوشه تعلق دارد و بعد از این مرحله نماینده های جدید برای هر خوشه محاسبه می شود و دوباره نمونه ها با این نماینده ها مقایسه می شوند تا مشخص شود که به کدام خوشه تعلق دارند و این کار آنقدر تکرار می شود تا زمانیکه نماینده های خوشه ها تغییری نکنند.

خوشه بندی با طبقه بندی (Classification) متفاوت است. در طبقه بندی نمونه های ورودی برچسب گذاری شده اند ولی در خوشه بندی نمونه های ورودی دارای بر چسب اولیه نمی باشند و در واقع با استفاده از روشهای خوشه بندی است که داده های مشابه مشخص و بطور ضمنی برچسب گذاری می شوند. در واقع می توان قبل از عملیات طبقه بندی داده ها یک خوشه بندی روی نمونه ها انجام داد و سپس مراکز خوشه های حاصل را محاسبه کرد و یک بر چسب به مراکز خوشه ها نسبت داد و سپس عملیات طبقه بندی را برای نمونه های ورودی جدید انجام داد.

منبع

آشنایی با خوشه‌بندی (Clustering) و شیوه‌های مختلف آن

الگوریتم‌های متنوع و زیادی برای انجام عملیات خوشه‌بندی در داده‌کاوی به کار می‌رود. آگاهی از الگوریتم‌های خوشه‌بندی و آشنایی با نحوه اجرای آن‌ها کمک می‌کند تا مناسب‌ترین روش را برای خوشه‌بندی داده‌های خود به کار ببرید.

«تحلیل خوشه‌بندی» (Cluster Analysis) نیز مانند «تحلیل طبقه‌بندی» (Classification Analysis) در «یادگیری ماشین» (Machine Learning) به کار می‌رود. هر چند که تحلیل طبقه‌بندی یک روش «با ناظر» (Supervised) محسوب شده ولی خوشه‌بندی روشی «بدون ناظر» (Unsupervised) است.

در این متن، ابتدا خوشه‌بندی را تعریف می‌کنیم و سپس به معرفی گونه‌های مختلف الگوریتم‌های خوشه‌بندی می‌پردازیم.

خوشه‌بندی (Clustering)

«تحلیل خوشه‌بندی» (Cluster Analysis) یا بطور خلاصه خوشه‌بندی، فرآیندی است که به کمک آن می‌توان مجموعه‌ای از اشیاء را به گروه‌های مجزا افراز کرد. هر افراز یک خوشه نامیده می‌شود. اعضاء هر خوشه با توجه به ویژگی‌هایی که دارند به یکدیگر بسیار شبیه هستند و در عوض میزان شباهت بین خوشه‌ها کمترین مقدار است. در چنین حالتی هدف از خوشه‌بندی، نسبت دادن برچسب‌هایی به اشیاء است که نشان دهنده عضویت هر شیء به خوشه است.

به این ترتیب تفاوت اصلی که بین تحلیل خوشه‌بندی و «تحلیل طبقه‌بندی» (Classification Analysis) وجود دارد، نداشتن برچسب‌های اولیه برای مشاهدات است. در نتیجه براساس ویژگی‌های مشترک و روش‌های اندازه‌گیری فاصله یا شباهت بین اشیاء، باید برچسب‌هایی بطور خودکار نسبت داده شوند. در حالیکه در طبقه‌بندی برچسب‌های اولیه موجود است و باید با استفاده از الگوی‌های پیش‌بینی قادر به برچسب گذاری برای مشاهدات جدید باشیم.

با توجه به روش‌های مختلف اندازه‌گیری شباهت یا الگوریتم‌های تشکیل خوشه‌،‌ ممکن است نتایج خوشه‌بندی برای مجموعه داده ثابت متفاوت باشند. شایان ذکر است که تکنیک‌های خوشه‌بندی در علوم مختلف مانند، گیاه‌شناسی، هوش مصنوعی، تشخیص الگوهای مالی و … کاربرد دارند.

روش‌های خوشه‌بندی

اگر چه بیشتر الگوریتم‌ها یا روش‌های خوشه‌بندی مبنای یکسانی دارند ولی تفاوت‌هایی در شیوه اندازه‌گیری شباهت یا فاصله و همچنین انتخاب برچسب برای اشیاء هر خوشه در این روش‌ها وجود دارد.

هر چند ممکن است امکان دسته‌بندی روش‌ها و الگوریتم‌ها خوشه‌بندی به راحتی میسر نباشد،‌ ولی طبقه‌بندی کردن آن‌ها درک صحیحی از روش خوشه‌بندی بکار گرفته شده در الگوریتم‌ها به ما می‌دهد. معمولا ۴ گروه اصلی برای الگوریتم‌های خوشه‌بندی وجود دارد. الگوریتم‌های خوشه‌بندی تفکیکی، الگوریتم‌های خوشه‌بندی سلسله مراتبی، الگوریتم‌های خوشه‌بندی برمبنای چگالی و الگوریتم‌های خوشه‌بندی برمبنای مدل. در ادامه به معرفی هر یک از این گروه‌ها می‌پردازیم.

خوشه‌بندی تفکیکی (Partitioning Clustering)

در این روش، براساس n‌ مشاهده و k گروه، عملیات خوشه‌بندی انجام می‌شود. به این ترتیب تعداد خوشه‌ها یا گروه‌ها از قبل در این الگوریتم مشخص است. با طی مراحل خوشه‌بندی تفکیکی، هر شیء فقط و فقط به یک خوشه تعلق خواهد داشت و هیچ خوشه‌ای بدون عضو باقی نمی‌ماند. اگر نشانگر وضعیت تعلق $x_{i}$ به خوشه $c_{j}$ باشد تنها مقدارهای ۰ یا ۱ را می‌پذیرد. در این حالت می‌نویسند:

$l_{i j} = 1, x_{i} \in c_{j} o r l_{i j} = 0, x_{i} \notin c_{j}$

هر چند این قانون‌ها زمانی که از روش «خوشه‌بندی فازی» (Fuzzy Clustering) استفاده می‌شود، تغییر کرده و برای نشان دادن تعلق هر شئی به هر خوشه از درجه عضویت استفاده می‌شود. به این ترتیب میزان عضویت $x_{i}$ به خوشه $c_{j}$ مقداری بین ۰ و ۱ است. در این حالت می‌نویسند:

$l_{i j} \in [0, 1]$

معمولا الگوریتم‌های تفکیکی بر مبنای بهینه‌سازی یک تابع هدف عمل می‌کنند. این کار براساس تکرار مراحلی از الگوریتم‌های بهینه‌سازی انجام می‌شود. در نتیجه الگوریتم‌های مختلفی بر این مبنا ایجاد شده‌اند. برای مثال الگوریتم «k-میانگین» (K-means) با تعیین تابع هدف براساس میانگین فاصله اعضای هر خوشه نسبت به میانگینشان، عمل می‌کند و به شکلی اشیاء را در خوشه‌ها قرار می‌دهد تا میانگین مجموع مربعات فاصله‌ها در خوشه‌ها، کمترین مقدار را داشته باشد. اگر مشاهدات را با x نشان دهیم، تابع هدف الگوریتم «k-میانگین» را می‌توان به صورت زیر نوشت:

$E = k \sum j = 1 \sum x \in c_{j} d i s t (x, μ_{c})$

که در آن $μ_{c j}$ میانگین خوشه‌ $c_{j}$ و dist نیز مربع فاصله اقلیدسی است.

به این ترتیب با استفاده از روش‌های مختلف بهینه‌سازی می‌توان به جواب مناسب برای خوشه‌بندی تفکیکی رسید. ولی از آنجایی که تعداد خوشه‌ها یا مراکز اولیه باید به الگوریتم داده شود، ممکن است با تغییر نقاط اولیه نتایج متفاوتی در خوشه‌بندی بدست آید. در میان الگوریتم‌های خوشه‌بندی تفکیکی، الگوریتم k-میانگین که توسط «مک‌کوئین» (McQueen) جامعه شناس و ریاضیدان در سال ۱۹۶۵ ابداع شد از محبوبیت خاصی برخوردار است.

نکته: در شیوه خوشه‌بندی تفکیکی با طی مراحل خوشه‌بندی، برچسب عضویت اشیاء به هر خوشه براساس خوشه‌های جدیدی که ایجاد می‌شوند قابل تغییر است. به این ترتیب می‌توان گفت که الگوریتم‌های خوشه‌بندی تفکیکی جزء الگوریتم‌های «یادگیری ماشین بدون ناظر» (Unsupervised Machine Learning) محسوب می‌شوند.

در تصویر ۱ نتایج ایجاد ۴ خوشه‌ روی داده‌های دو بعدی به کمک الگوریتم k-میانگین نمایش داده شده است. داشتن حالت کروی برای داده‌ها به ایجاد خوشه‌های مناسب در الگوریتم k-میانگین کمک می‌کند.

تصویر ۱- خوشه‌بندی k-میانگین برای داده‌های دو بعدی

دسامبر 9, 2019/0 دیدگاه /توسط hgadmin

خوشه بندی (Clustering) قسمت 2

آموزش عمومی پردازش تصویر و بینایی ماشین

چلامارزیابی مدل خوشه‌بندی

ارزیابی (یا «اعتبار سنجی») نتایج خوشه بندی به همان اندازه خوشه بندی سخت است. رویکردهای محبوب شامل ارزیابی “درونی” است که در آن خوشه بندی به یک عدد کیفیت واحد خلاصه می‌شود، ارزیابی “خارجی”، که در آن خوشه بندی با طبقه بندی “ground truth” موجود، ارزیابی “دستی” توسط متخصص و ارزیابی “غیر مستقیم ” با استفاده از خوشه بندی در برنامه مورد نظر مقایسه می‌شود.

مشکلی که ارزیابی خارجی دارد این است که اگر ما برچسبهای “ground truth” داشته باشیم، دیگر نیازی به خوشه نخواهیم داشت و در برنامه‌های کاربردی معمولا چنین برچسب‌هایی را نداریم. از سوی دیگر، برچسب‌ها فقط یک پراکندگی از مجموعه داده نشان می‌دهد، که به این معنی نیست که خوشه ای متفاوت و شاید حتی بهتر از آن وجود نداشته باشد.

بنابراین هیچکدام از این روشها نهایتا نمیتوانند کیفیت واقعی خوشه بندی را قضاوت کنند، اما اینکار نیاز به ارزیابی انسانی دارد که بسیار ذهنی است.

ارزیابی داخلی

هنگامی که یک نتیجه خوشه بندی ای که بر اساس داده‌های خودش خوشه بندی شده‌است، ارزیابی شود، ارزیابی داخلی نامیده می‌شود.اگر از استاندارد gold استفاده شود، اندازه گیری خارجی نامیده می‌شوند و در بخش بعدی مورد بحث قرار می‌گیرد .(اگر متقارن باشد، می‌تواند اندازه گیری بین خوشه ایی برای ارزیابی داخلی استفاده شود.) روش‌ها معمولا بهترین عدد را برای الگوریتمی که درون خوشه شباهت زیاد و بین خوشه‌ها ، شباهت کم باشد،تولید می‌کند.این ارزیابی به سمت الگوریتم‌هایی است که از یک مدل خوشه ای استفاده می‌کنند. به عنوان مثال، خوشه بندي k-means به‌طور طبيعي به فضاهاي شئي بهينه مي كند و معيار داخلي مبتني بر فاصله، احتمالا از خوشه بندي به دست مي آيد.

بنابراین، اقدامات ارزیابی داخلی برای درک وضعیتی که یک الگوریتم بهتر از دیگری عمل می‌کند، مناسب است، اما این به این معنی نیست که یک الگوریتم نتیجه‌های معتبرتری را نسبت به دیگری تولید کند.

بیش از دوازده اندازه گیری ارزیابی داخلی وجود دارد. به عنوان مثال، برای ارزیابی کیفیت خوشه بندی می‌توان از روش‌های زیر استفاده کرد.

شاخص Davies–Bouldin

شاخصDavies–Bouldin را می‌توان با فرمول زیر محاسبه کرد:

$D={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,,$

که n تعداد خوشه و $c_{x}$ مرکز خوشه x و σx فاصله متوسط همه عناصر در خوشه x و $d(c_{i},c_{j})$ فاصله بین مرکزهای $c_{i}$ و $c_{j}$ است.از آنجا که الگوریتم‌هایی که خوشه‌ها را با فاصله‌های درونی خوشه ای کم (شباهت بین خوشه ای بالا) و فاصله‌های بین خوشه ای بالا (شباهت بین خوشه ای پایین) تولید می‌کنند، یک شاخص Davies–Bouldin پایین خواهیم داشت، الگوریتم خوشه بندی که مجموعه ای از خوشه‌های با کوچکترین شاخصDavies–Bouldin ، بهترین الگوریتم بر اساس این معیار است.

شاخصDunn

هدف شاخص Dunn شناسایی خوشه‌های متراکم و جداسازی آنهاست و به عنوان نسبت بین کمترین فاصله بین خوشه ای تا حداکثر فاصله بین خوشه ای تعریف شده‌است. برای هر قسمت خوشه، شاخص دان را می‌توان با فرمول زیر محاسبه کرد:

$D={\frac {\min _{1\leq i<j\leq n}d(i,j)}{\max _{1\leq k\leq n}d^{\prime }(k)}}\,$

که d (i، j) فاصله بین خوشه‌های i و j را نشان می‌دهد و d ‘(k) فاصله بین خوشه ایی خوشه k را اندازه گیری می‌کند. فاصله بین خوشه ای d (i، j) بین دو خوشه ممکن است هر تعداد از اندازه گیری‌های فاصله، مانند فاصله بین centroids از خوشه‌ها باشد. به‌طور مشابه، فاصله بین خوشه ای d ‘(k) ممکن است از روش‌های مختلف اندازه گیری شود، مانند فاصله حداکثر بین هر جفت المان در خوشه k.

از آنجایی که معیار داخلی به دنبال خوشه‌هایی با شباهت بین خوشه ای بالا و شباهت بین خوشه ای کم است، الگوریتم‌هایی که خوشه‌ها را با شاخص Dunn بالایی تولید می‌کنند بیشتر مطلوب است.

ضریب Silhouette

ضریب Silhouette در مقایسه با فاصله میانگین تا عناصر در خوشه‌های مشابه با میانگین فاصله تا عناصر در خوشه‌های دیگر، مقایسه می‌شود. اشیاء با Silhouette بالا به خوبی خوشه بندی می‌شوند، اشیاء باSilhouette کم ممکن است ناپایدار باشند. این شاخص با خوشه بندی k-means کار می‌کند و همچنین برای تعیین تعداد مطلوب خوشه‌ها استفاده می‌شود.

ارزیابی خارجی

در ارزیابی خارجی، نتایج خوشه بندی بر اساس داده‌هایی که برای خوشه بندی استفاده نشدند، مانند برچسب‌های کلاس شناخته شده و معیارهای خارجی ارزیابی می‌شود. چنین معیارهایی قبل از طبقه بندی اغلب توسط متخصص تعیین می‌شود. بنابراین مجموعه معیارها می‌تواند به عنوان یک استاندارد gold برای ارزیابی استفاده شود. این نوع روش‌های ارزیابی اینکه چقدر خوشه بندی به کلاس‌های معیاری پیش تعیین شده نزدیک است، را تعیین می‌کند. با این حال، اینکه آیا این برای داده‌های واقعی مناسب است یا فقط بر روی مجموعه داده‌های مصنوعی با ground truth است، مورد بحث قرار گرفته‌است ، از آنجا که کلاس‌ها می توانند ساختار داخلی داشته باشند، ویژگی‌های موجود ممکن است اجازه جدا شدن خوشه‌ها یا کلاس‌ها را ندهند.

همانند ارزیابی داخلی، چند اندازه گیری برای ارزیابی خارجی وجود دارد که در ادامه چند روش بیان شده‌است.

Purity: خلوص برای خوشه‌هایی که دارای یک کلاس واحد هستند،اندازه گیری می‌شود.برای محاسبهٔ آن ، برای هر خوشه، تعداد نقاط داده از کلاس معمول در خوشهٔ مورد نظر شمرده می‌شود ،سپس تمام خوشه‌ها را جمع شده و بر تعداد نقاط داده تقسیم می‌شود. با توجه به مجموعه ای از خوشه‌های M و برخی از مجموعه ای از کلاس‌های D، هر دو پارامتر با N نقطه داده، خلوص را می‌توان به صورت زیر تعریف کرد:

${\frac {1}{N}}\sum _{m\in M}\max _{d\in D}{|m\cap d|}$

اندازه گیری رند (ویلیام رند، 1971)

شاخص رند اینکه خوشه‌ها (که توسط الگوریتم خوشه بندی بازمی گردند) به معیار طبقه بندی‌ها چقدر شبیه‌اند را محاسبه می‌کند. همچنین می توانید شاخص رند را به عنوان اندازه گیری درصد تصمیمات درست که توسط الگوریتم ساخته شده‌است را استفاده کرد. که می‌توان با استفاده از فرمول زیر محاسبه کرد:

$RI={\frac {TP+TN}{TP+FP+FN+TN}}$

TP تعداد مثبت صحیح و TN تعداد منفی صحیح وFP تعداد مثبت کاذب وFN تعداد منفی‌های کاذب می‌باشد .

اندازه گیری F

اندازه گیری F را می‌توان برای تعادل مشارکت منفی‌های کاذب با استفاده از وزن دادن از طریق پارامتر β≥0 استفاده کرد.

$P={\frac {TP}{TP+FP}}$

$R={\frac {TP}{TP+FN}}$

که pنرخ دقت و R نرخ فراخوان است. F را با استفاده از فرمول زیر محاسبه شده‌است:

$F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}$

شاخص Jaccard

شاخص Jaccard برای اندازه گیری شباهت بین دو مجموعه داده استفاده می‌شود. شاخص Jaccard مقداري بين 0 و 1 دارد. شاخص 1 بدين معني است که دو مجموعه داده يکسان هستند و شاخص 0 نشان مي دهد که مجموعه داده‌ها هيچ عنصر مشترکي ندارند. شاخص Jaccard توسط فرمول زیر تعریف می‌شود:

$J(A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {TP}{TP+FP+FN}}$

شاخص Dice

اندازه گیری متقارنDice دو برابر وزن TP است در حالی کهTN نادیده گرفته می‌شود و برابر با F1 است – اندازه گیری F با β = 1 :

$J(A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {2TP}{2TP+FP+FN}}$

شاخص Fowlkes-Mallows (E. B. Fowlkes & C. L. Mallows 1983)

شاخص Fowlkes-Mallows شباهت میان خوشه‌های بازگشتی توسط الگوریتم خوشه بندی و معیارهای طبقه بندی را محاسبه می‌کند. هر چه مقدار شاخص Fowlkes-Mallows بیشتر باشد خوشه‌ها و معیارهای طبقه بندی مشابه هستند.این شاخص را می‌توان با استفاده از فرمول زیر محاسبه کرد:

$FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}$

کهTP تعداد مثبت واقعی وFP تعداد مثبت کاذب وFN تعداد منفی‌های کاذب است. FM شاخص میانگین هندسی دقت و فراخوانی P, R است و همچنین به عنوان اندازه گیری G شناخته شده‌است، در حالی که اندازه گیری F میانگین هارمونیک آن‌ها است. علاوه بر این، دقت و یادآوری نیز به عنوان شاخص والاس $B^{I}$ و $B^{II}$ شناخته شده‌است.

اطلاعات متقابل، اندازه گیری نظری اطلاعاتی است که چقدر اطلاعات بین خوشه بندی و طبقه بندی ground-truth است که می‌تواند تشابه غیر خطی بین دو خوشه بندی را تشخیص دهد.

ماتریسconfusion

یک ماتریس confusion می‌تواند برای به سرعت نتایج یک طبقه بندی (یا خوشه بندی) الگوریتم را نمایش دهد و نشان می‌دهد که چگونه یک خوشه از خوشه استاندارد gold متفاوت است.

تمایل خوشه

هدف از اندازه گیری تمایل خوشه،این است که چه درجه ای خوشه‌ها در داده‌های خوشه بندی شده وجود داردو ممکن است قبل از تلاش برای خوشه سازی به عنوان یک آزمون اولیه انجام شود. یکی از راه‌های انجام این کار این است که داده‌ها با دادههای تصادفی مقایسه شود. در اصل ،داده‌های تصادفی نباید خوشه ای داشته باشند.

آمار Hopkins

فرمول‌های متعدد از آمار هاپکینز وجود دارد. یک نمونه به این صورت می‌باشد که : X مجموعه ای از n نقاط داده درd بعد است. یک نمونه تصادفی (بدون جایگزینی)

m≪n با اعضای xi را در نظر بگیرید .همچنین یک مجموعه Y از m نقطه داده با توزیع یکنواخت رندوم یکنواخت تولید کنید.دو فاصله اندازه گیری، ui فاصله از yi∈Y از نزدیک‌ترین همسایه اش در X و $w_i$ فاصله ازxi∈X از نزدیک‌ترین همسایه اش در X است. آمار Hopkins به صورت زیر تعریف می‌شود:

$H={\frac {\sum _{i=1}^{m}{u_{i}^{d}}}{\sum _{i=1}^{m}{u_{i}^{d}}+\sum _{i=1}^{m}{w_{i}^{d}}}}\,$

کاربرد

زیست شناسی، زیست‌شناسی محاسباتی و بیوانفورماتیک

بوم‌شناسی گیاه و حیوانات

تجزیه و تحلیل خوشه ای برای توصیف و مقایسه مقادیر مکانی و زمانی جوامع ارگانیسم‌ها در محیط‌های ناهمگن استفاده می‌شود؛ از آن نیز در سیستماتیک گیاه برای تولید phylogenies مصنوعی یا خوشه‌های ارگانیسم (افراد) در گونه، جنس و یا سطح بالاتر که دارای تعدادی از ویژگی‌های مشترک است، استفاده می‌شود.

Transcriptomics

خوشه بندی برای ساخت گروهی از ژن‌ها با الگوی بیان مربوطه به عنوان الگوریتم خوشه بندی HCS استفاده می‌شود. اغلب این گروه‌ها حاوی عملکرد پروتئین‌های مرتبط هستند، مانند آنزیم‌ها برای یک مسیر خاص، یا ژن‌هایی که هم تنظیم می‌شوند. آزمایشات با توان بالا با استفاده از نشانگرهای ترتیبی بیان شده (ESTs) یا میکروآرایه‌های DNA می‌تواند یک ابزار قدرتمند برای حاشیه‌نویسی ژنوم، یک جنبه عمومی ژنومیک باشد.

تجزیه و تحلیل متوالی

خوشه بندی برای دسته بندی توالی‌های همولوگ به خانواده‌های ژن ،مورد استفاده قرار می‌گیرد.به‌طور کلی این مفهوم بسیار مهمی در بیوانفورماتیک و زیست‌شناسی تکاملی است.

سیستم عامل‌های ژنوتایپ با بازده بالا

الگوریتم خوشه بندی به‌طور خودکار برای تعیین ژنوتیپ‌ها استفاده می‌شود.

خوشه بندی ژنتیک انسانی

شباهت داده‌های ژنتیکی در خوشه بندی برای به دست آوردن ساختار جمعیت استفاده می‌شود.

پزشکی

تصویربرداری پزشکی

در PET، تجزیه خوشه ای می‌تواند برای تمایز بین انواع مختلف بافت در یک تصویر سه بعدی برای بسیاری از اهداف مختلف مورد استفاده قرار گیرد.

تجزیه و تحلیل فعالیت ضد میکروبی

تجزیه خوشه ای می‌تواند برای تجزیه و تحلیل الگوهای مقاومتی آنتی بیوتیکی، طبقه بندی ترکیبات ضد میکروبی مطابق با مکانیسم عمل آن ها، طبقه بندی آنتی بیوتیک‌ها بر اساس فعالیت ضد باکتری آن‌ها استفاده شود.

بخش بندی IMRT

خوشه بندی می‌تواند برای تقسیم یک نقشه فلوئنسی به مناطق مجزا برای تبدیل به زمینه‌های قابل ارائه در پرتودرمانی براساس MLC استفاده شود.

کسب و کار و بازاریابی

تحقیقات بازار

تجزیه و تحلیل خوشه ای در تحقیقات بازار به‌طور گسترده در کار با داده‌های چندمتغیره از نظرسنجی‌ها و پانل‌های آزمایش استفاده می‌شود. محققان بازار از تحلیل خوشه ای استفاده می‌کنند تا جمعیت عمومی مصرف کنندگان را به بخش‌های بازار تقسیم کنند و به درک بهتر روابط بین گروه‌های مختلف مصرف کنندگان / مشتریان بالقوه و برای استفاده در تقسیم بندی بازار، موقعیت محصول، توسعه محصول جدید و انتخاب تست بازار کمک می‌کند.

گروه بندی اقلام خرید

خوشه بندی را می‌توان برای دسته بندی تمام اقلام خرید موجود در وب به مجموعه ای از محصولات منحصر به فرد استفاده کرد. به عنوان مثال، تمام اقلام در eBay را می‌توان به محصولات منحصر به فرد گروه بندی کرد.

وب جهان گستر

تجزیه و تحلیل شبکه اجتماعی

در مطالعه شبکه‌های اجتماعی، خوشه بندی ممکن است برای تشخیص ارتباط جوامع در گروه‌های بزرگ مردم استفاده شود.

گروه بندی نتایج جستجو

در فرایند گروه بندی هوشمند از فایل‌ها و وب سایت ها، خوشه بندی ممکن است برای ایجاد یک مجموعه مناسب تر از نتایج جستجو در مقایسه با موتورهای جستجوی معمول مانند Google استفاده شود. در حال حاضر تعدادی از ابزارهای خوشه سازی مبتنی بر وب مانند Clusty وجود دارد.

بهینه سازی نقشه Slippy

در نقشه Flickr از عکس‌ها و سایر krai سایت‌ها از خوشه بندی برای کاهش تعداد نشانگرها در یک نقشه استفاده شده‌است. این باعث می‌شود که هر دو سریعتر و میزان خطای بصری را کاهش دهد.

علوم کامپیوتر

تکامل نرم افزار

خوشه بندی در تکامل نرم افزار مفید است، زیرا آن را با اصلاح قابلیت‌هایی که پراکنده شده‌است، کمک می‌کند تا خواص میراث را در کد کاهش دهد. این یک نوع بازسازی است و از این رو، راه مستقیم نگهداری پیشگیرانه است.

بخش بندی تصویر

خوشه بندی می‌تواند برای تقسیم یک تصویر دیجیتال به مناطق مشخص برای تشخیص مرز یا تشخیص شی مورد استفاده قرار گیرد.

الگوریتم‌های تکاملی

خوشه بندی ممکن است برای شناسایی nichهای مختلف در جمعیت یک الگوریتم تکاملی استفاده شود تا فرصت تولید مجد را به‌طور یکنواخت تر بین گونه‌ها یا گونه‌های در حال رشد توزیع کرد.

سیستم توصیه گر

سیستم‌های توصیه شده به منظور توصیف ایتم جدید بر اساس سلیقه کاربر طراحی شده‌اند. گاهی اوقات از الگوریتم خوشه بندی برای پیش‌بینی ترجیحات کاربر بر اساس ترجیحات دیگر کاربران در خوشه کاربر استفاده می‌کنند.

روش مارکوف مونت کارلو زنجیره ای

خوشه بندی اغلب برای تعیین مکان و تشخیص اکسترمم در توزیع هدف، مورد استفاده قرار می‌گیرد.

تشخیص ناهنجاری

ناهنجاری‌ها معمولا – به صراحت یا به‌طور ضمنی – با توجه به ساختار خوشه ای در داده‌ها تعریف می‌شود.

علوم اجتماعی

تجزیه و تحلیل جرم

از تجزیه و تحلیل خوشه ای می‌توان برای شناسایی مناطق که در آن موارد بیشتر از انواع خاصی از جرم وجود دارد استفاده شود. با شناسایی این مناطق متمایز یا “hot spot” که جرم مشابهی در طی یک دوره زمانی اتفاق افتاده است، می‌توان منابع اجرای قانون را به‌طور مؤثرتر مدیریت کرد.

داده کاوی آموزشی

به عنوان مثال، تجزیه و تحلیل خوشه ای برای شناسایی گروه‌های مدارس یا دانشجویانی با ویژگی مشابه استفاده می‌شود.

تایپولوژی ها

در داده‌های نظرسنجی، پروژه‌هایی نظیر آنچه که توسط مرکز تحقیقاتی Pew انجام شده، از تجزیه و تحلیل خوشه ای استفاده می‌کنند تا نوع‌شناسی عقاید، عادت‌ها و جمعیت شناسایی را که ممکن است در سیاست و بازاریابی سودمند باشد، شناسایی کند.

و کاربردهای دیگر

در زمینه رباتیک

الگوریتم خوشه بندی برای آگاهی موقعیت رباتیک برای ردیابی اشیاء و تشخیص خروجی‌ها در داده‌های سنسور استفاده می‌شود.

شیمی محاسباتی

به عنوان مثال، برای پیدا کردن شباهت ساختاری و غیره، به عنوان نمونه، 3000 ترکیب شیمیایی در فضای 90 شاخص توپولوژیکی ،خوشه بندی شدند.

اقلیم شناسی

برای پیدا کردن آب و هوایی و یا الگوهای فشار جو در سطح دریا مورد نظر است.

زمین‌شناسی نفت

تجزیه و تحلیل خوشه ای برای بازسازی داده‌های اصلی ازدست رفته سوراخ پایین یا منحنی‌های لگاریتمی از دست رفته به منظور بررسی خواص مخزن استفاده می‌شود.

جغرافیای فیزیکی

خوشه بندی خواص شیمیایی در مکان‌های مختلف نمونه.

منبع

خوشه بندی (Clustering) قسمت 1
خوشه بندی (Clustering) قسمت 2
خوشه بندی (Clustering) قسمت 3

دسامبر 8, 2019/0 دیدگاه /توسط hgadmin

خوشه بندی (Clustering) قسمت 1

آموزش عمومی پردازش تصویر و بینایی ماشین

در خوشه بندی، هدف تقسیم داده به گروه‌های مختلف است که با رنگ‌های مختلف در اینجا نشان داده شده‌اند.

در تجزیه و تحلیل خوشه یا خوشه بندی، گروه بندی مجموعه ای از اشیاء انجام می‌شود اینکار به این صورت است که اشیاء در یک گروه (به نام خوشه) در مقایسه با دیگر دسته‌ها (خوشه ها) مشابه تر هستند. این وظیفه اصلی داده کاوی اکتشافی است و یک روش معمول برای تجزیه و تحلیل داده‌های آماری است که در بسیاری از زمینه‌ها از جمله یادگیری ماشین، تشخیص الگو،تجزیه و تحلیل تصویر، بازیابی اطلاعات، بیوانفورماتیک، فشرده سازی داده‌ها و گرافیک کامپیوتری استفاده می‌شود.

هدف خوشه بندی

تجزیه و تحلیل خوشه ای خود یک الگوریتم خاص نیست، بلکه روند کلی است و می‌تواند توسط الگوریتم‌های مختلفی به دست آید که در درک آنچه که یک خوشه را تشکیل می دهند و نحوه کارآمدی آن‌ها را پیدا می‌کند.

اصطلاحات خوشه‌ها شامل گروه‌هایی با فاصله‌های کم بین اعضای خوشه، مناطق متراکم فضای داده، فواصل و یا توزیع‌های آماری خاص است. بنابراین خوشه بندی می‌تواند به عنوان یک مسئله بهینه سازی چند هدفه صورت گیرد. الگوریتم خوشه بندی مناسب و تنظیمات پارامتر (از جمله پارامترهایی مانند تابع فاصله مورد استفاده، آستانه تراکم یا تعداد خوشه مورد انتظار) بستگی به تنظیم مجموعه داده‌ها توسط فرد و استفاده خاص فرد از نتایج دارد. تجزیه و تحلیل خوشه ای یک روش اتوماتیک نیست، بلکه یک فرآیند تکراری از کشف دانش یا بهینه سازی چند هدفه تعاملی است که شامل آزمایش و شکست است. اغلب لازم است که داده‌های پیش پردازش شده و پارامترهای مدل اصلاح شوند تا نتیجه حاصل ، همان نتیجهٔ دلخواه باشد.

علاوه بر اصطلاحات خوشه بندی، تعدادی از اصطلاح با معانی مشابه وجود دارد، از جمله طبقه بندی خودکار، طبقه بندی عددی، روش‌شناسی و تجزیه و تحلیل توپولوژیکی. تفاوت‌های کم اغلب در نتایج استفاده می‌شود: در داده کاوی، نتیجه گروه‌ها مورد توجه هست و در طبقه بندی خودکار، قدرت تشخیصی مورد توجه است.

تجزیه و تحلیل خوشه ای در انسان‌شناسی توسط Driver و Kroeber در سال 1932 آغاز شد و در روان‌شناسی توسط زوبین در سال 1938 و رابرت تیرون در سال 1939 معرفی شد و در سال 1943 برای طبقه بندی نظریه رفتاری در روانشناسی شخصیت توسط Cattell استفاده شده‌است.

تعریف

مفهوم “خوشه” را دقیقا نمیتوان تعریف کرد،یکی از دلایلش این است که الگوریتم‌های خوشه بندی زیادی وجود دارد. همهٔ آن‌ها یک قسمت مشترک دارند و آن یک گروه از اشیاء داده است. با این حال، محققان از مدل‌های مختلف خوشه استفاده می‌کنند و برای هر یک از این مدل‌های خوشه، الگوریتم‌های مختلفی را می‌توان ارائه داد. مفهوم یک خوشه، همانطور که توسط الگوریتم‌های مختلف یافت می‌شود، به‌طور خاصی در خواص تفاوت دارند. درک این مدلهای خوشه ، کلید فهمیدن تفاوت بین الگوریتم‌های مختلف است. مدل‌های خوشه ای معمول عبارتند از:

مدل‌های متصل: به عنوان مثال، خوشه بندی سلسله مراتبی، مدل‌هایی براساس فاصله متصل را ایجاد می‌کند.
مدل‌های مرکزی: به عنوان مثال، الگوریتم k-means ، هر خوشه را با یک بردار متوسط نشان می‌دهد.
مدل‌های توزیع: خوشه‌ها با استفاده از توزیع‌های آماری، مانند توزیع نرمال چند متغیره که در الگوریتم حداکثر انتظار ، استفاده شده‌است.
مدلهای تراکم: به عنوان مثال، DBSCAN و OPTICS خوشه را به عنوان مناطق متراکم متصل در فضای داده تعریف می‌کنند.
مدل‌های زیر فضایی: در biclustering (که به عنوان خوشه مشترک یا خوشه ای دو حالت شناخته می‌شود)، خوشه‌ها با هر دو اعضای خوشه و ویژگی‌های مرتبط مدل سازی می‌شوند.
مدل‌های گروهی: برخی از الگوریتم‌ها یک مدل تصحیح شده برای نتایج خود را ارائه نمی دهند و فقط اطلاعات گروه بندی را ارائه می دهند.
مدل‌های مبتنی بر گراف: یک کلاس، یعنی یک زیر مجموعه از گره‌ها در یک گراف به طوری که هر دو گره در زیر مجموعه با یک لبه متصل می‌شود که می‌تواند به عنوان یک شکل اولیه از خوشه مورد توجه قرار گیرد.
مدل‌های عصبی: شبکه عصبی غیرقابل نظارت ، شناخته شده‌ترین نقشه خود سازمانی است و معمولا این مدل‌ها می توانند به عنوان مشابه با یک یا چند مدل فوق شامل مدل‌های زیر فضایی، زمانی که شبکه‌های عصبی یک فرم تجزیه و تحلیل مؤلفه اصلی یا مستقل تجزیه و تحلیل المان می‌باشد .

“خوشه بندی” اساسا مجموعه ای از خوشه‌ها است که معمولا شامل تمام اشیاء در مجموعه داده‌ها می‌شود. علاوه بر این، می‌توان رابطه خوشه‌ها را به یکدیگر تعریف کند، به عنوان مثال، سلسله مراتب خوشه‌های تعبیه شده در یکدیگر.

خوشه بندی را می‌توان براساس سختی تمایز به صورت زیر مشخص کرد:

خوشه بندی سخت: هر شیء متعلق به خوشه است یا نه.
خوشه بندی نرم (همچنین: خوشه فازی): هر شیء به درجه خاصی از هر خوشه متعلق است (به عنوان مثال، احتمال وابستگی به خوشه)

همچنین امکان تمایز دقیق تر وجود دارد، مثلا:

خوشه بندی جداسازی دقیق ( پارتیشن بندی): هر شیء دقیقا به یک خوشه متعلق است.
خوشه بندی جداسازی دقیق با ناپیوستگی: اشیاء می توانند به هیچ خوشه ای تعلق نداشته باشند.
خوشه بندی همپوشانی (همچنین: خوشه بندی جایگزین، خوشه بندی چندگانه): اشیاء ممکن است متعلق به بیش از یک خوشه باشد؛ معمولا خوشه‌های سخت را شامل می‌شود
خوشه بندی سلسله مراتبی: اشیایی که متعلق به خوشه فرزند هستند، متعلق به خوشه پدر و مادر هم هستند.
خوشه بندی زیر فضا: در حالی که خوشه بندی همپوشانی، که در یک زیر فضای منحصر به فرد تعریف شده ، انتظار نمی رود که خوشه‌ها با همپوشانی داشته باشند.

الگوریتم

همانطور که در بالا ذکر شد، الگوریتم‌های خوشه بندی را می‌توان بر اساس مدل خوشه ای طبقه بندی کرد. در ادامه نمونه‌های برجسته ای از الگوریتم‌های خوشه بندی بیان شده‌است، زیرا احتمالا بیش از 100 الگوریتم خوشه بندی منتشر شده وجود دارد. همه مدلها برای خوشه هایشان بیان نشده اند، بنابراین نمی توان به راحتی دسته بندی کرد.

الگوریتم خوشه بندی عینی “صحیح” وجود ندارد، اما همانطور که اشاره شد، “خوشه بندی در چشم بیننده است.” بهترین الگوریتم خوشه بندی برای یک مسئله خاص، اغلب باید به صورت تجربی انتخاب شود، مگر اینکه یک دلیل ریاضی برای ترجیح دادن یک مدل خوشه بر دیگری وجود داشته باشد. لازم به ذکر است که یک الگوریتم که برای یک نوع مدل طراحی شده‌است و در یک مجموعه داده ای که شامل تفاوت اساسی مدل است، شکست می خورد. به عنوان مثال، k-means نمیتواند خوشه‌های غیرمحدب را پیدا کند.

خوشه بندی براساس اتصال (خوشه بندی سلسله مراتبی)

خوشه بندی براساس اتصال، که همچنین به عنوان خوشه بندی سلسله مراتبی شناخته می‌شود، بر مبنای ایده اصلی اشیائی است که بیشتر مربوط به اشیای نزدیک، نسبت به اشیاء دورتر است. این الگوریتم‌ها “اشیا” را برای ایجاد “خوشه ها” بر اساس فاصله آن‌ها متصل می‌کنند. خوشه را می‌توان به طورکلی با حداکثر فاصله مورد نیاز برای اتصال قطعات خوشه توصیف کرد. در فاصله‌های مختلف، خوشه‌های متفاوتی شکل می‌گیرند که می‌تواند با استفاده از یک دندروگرام نشان داده شود، که توضیح می‌دهد که نام معمول “خوشه بندی سلسله مراتبی” از آن می آید: این الگوریتم‌ها یک پارتیشن بندی مچموعه داده را ارائه نمی دهند، بلکه یک سلسله مراتب گسترده ای از خوشه‌هایی که در فاصله‌های معینی با یکدیگر ادغام می‌شوند، ارائه میدهد. در یک دندروگرام، محور y نشان دهنده فاصله ای است که خوشه‌ها ادغام می‌کنند، در حالی که اشیا در امتداد محور x قرار می‌گیرند به طوری که خوشه‌ها با هم مخلوط نمی‌شوند.

خوشه بندی سلسله مراتبی شامل دو نوع خوشه بندی می‌باشد:

single linkage -1 این روش که به روش Bottom-Up و Agglomerative نیز معروف است روشی است که در آن ابتدا هر داده به عنوان یک خوشه در نظر گرفته می‌شود. در ادامه با به کارگیری یک الگوریتم هر بار خوشه‌های دارای ویژگی‌های نزدیک به هم با یکدیگر ادغام شده و این کار ادامه می‌یابد تا به چند خوشهٔ مجزا برسیم. مشکل این روش حساس بودن به نویز و مصرف زیاد حافظه می‌باشد.

complete linkage -2 در این روش که به روش Top-Down و Divisive نیز معروف است ابتدا تمام داده‌ها به عنوان یک خوشه در نظر گرفته شده و با به کارگیری یک الگوریتم تکرار شونده هربار داده‌ای که کمترین شباهت را با داده‌های دیگر دارد به خوشه‌های مجزا تقسیم می‌شود. این کار ادامه می‌یابد تا یک یا چند خوشه یک عضوی ایجاد شود. مشکل نویز در این روش برطرف شده‌است.

مثال هایی از خوشه linkage

خوشه بندی براساس centroid

در خوشه بندی براساس centroid، خوشه‌ها با یک بردار مرکزی نشان داده می‌شوند، که ممکن است لزوما جزء مجموعه داده نباشد. هنگامی که تعدادی از خوشه‌ها به k متصل می‌شوند، خوشه بندی k-means یک تعریف رسمی را به عنوان یک مسئله بهینه سازی ارائه می‌دهد.

روش میانگین k در عین سادگی یک روش بسیار کاربردی و پایه چند روش دیگر مثل خوشه بندی فازی و Segment-wise distributional clustering Algorithm می‌باشد.روش کار به این صورت است که ابتدا به تعداد دلخواه نقاطی به عنوان مرکز خوشه در نظر گرفته می‌شود. سپس با بررسی هر داده، آن را به نزدیک‌ترین مرکز خوشه نسبت می‌دهیم. پس از اتمام این کار با گرفتن میانگین در هر خوشه می‌توانیم مراکز خوشه و به دنبال آن خوشه‌های جدید ایجاد کنیم. (با تکرار مراحل قبل)از جمله مشکلات این روش این است که بهینگی آن وابسته به انتخاب اولیه مراکز بوده و بنابراین بهینه نیست. مشکلات دیگر آن تعیین تعداد خوشه‌ها و صفر شدن خوشه‌ها می‌باشد.

K-means دارای تعدادی خواص نظری است. اول، فضای داده را به یک ساختار معروف به یک نمودار Voronoi تقسیم می‌کند. دوم، به لحاظ مفهومی نزدیک به طبقه بندی نزدیکترین همسایه است و به همین علت در یادگیری ماشین محبوب است. سوم، می‌توان آن را به عنوان تنوع خوشه بندی براساس مدل مشاهده کرد.

مثال هایی از خوشه بندی k-means

خوشه بندی براساس توزیع

این مدل خوشه بندی که دقیقا مربوط به آمار می‌باشد، بر اساس مدل‌های توزیع است.خوشه‌ها به راحتی می توانند به عنوان اشیایی تعریف می‌شوند که به احتمال زیاد ب توزیع یکسانی دارند. یک ویژگی خوب این رویکرد این است که با نمونه برداری از اشیاء تصادفی از یک توزیع، دقیقا شبیه نحوه تولید مجموعه داده‌های مصنوعی است. مبنای نظری این روش‌ها عالی است، ولی مشکل اصلی overfitting دارند، مگر اینکه محدودیت‌ها بر پیچیدگی مدل قرار بگیرد.

یک روش شناخته شده ،مدل مخلوط گاوس (با استفاده از الگوریتم حداکثر سازی انتظار) است. مجموعه داده‌ها معمولا با یک ثابت (برای جلوگیری از overfitting) تعداد توزیع‌های گاوسی که به صورت تصادفی استفاده شده و به منظور مناسب تر کردن مجموعه داده مدل ، پارامترهای آن به‌طور تکراری بهینه شده‌است که به یک بهینه محلی همگرا می‌شود، بنابراین در طول چند اجرا ممکن است نتایج متفاوتی تولید کند. به منظور به دست آوردن خوشه بندی سخت، اشیاء اغلب به توزیع گاوسی که به احتمال زیاد متعلق به آنهاست، اختصاص داده است که برای خوشه بندی نرم، اینکار لازم نیست.خوشه بندی مبتنی بر توزیع، مدل‌های پیچیده ای را برای خوشه‌ها ایجاد می‌کند که می‌تواند همبستگی و وابستگی ویژگی را نشان دهد.

مثال های Expectation-maximization (EM)

خوشه بندی براساس Density

در این تکنیک این اصل مطرح می‌شود که خوشه‌ها مناطقی با چگالی بیشتر هستند که توسط مناطق با چگالی کمتر از هم جدا شده‌اند. یکی از مهم‌ترین الگوریتم‌ها در این زمینه الگوریتم DBSCAN است.

روش این الگوریتم به این صورت است که هر داده متعلق به یک خوشه در دسترس چگالی سایر داده‌های همان خوشه است، ولی در دسترسی چگالی سایر داده‌های خوشه‌های دیگر نیست.(چگالی داده همسایگی به مرکز داده و شعاع همسایگی دلخواه ε است)مزیت این روش این است که تعداد خوشه‌ها به صورت خودکار مشخص می‌شود. در تشخیص نویز نیز بسیار کاراست.

مثال هایی برای خوشه بندی براساس Density

پیشرفت های اخیر

در سال‌های اخیر تلاش‌های قابل توجهی در بهبود عملکرد الگوریتم‌های موجود انجام شده‌است.با توجه به نیازهای جدید به پردازش داده‌های خیلی بزرگ، تمایل به کاربرد خوشه‌های تولید شده برای عملکرد تجاری افزایش یافته‌است. این امر منجر به توسعه روش‌های پیش خوشه سازی مانند خوشه بندیcanopy می‌شود که می‌تواند داده‌های حجیم را به‌طور مؤثر پردازش کند.

برای داده‌های با ابعاد بزرگ، بسیاری از روش‌های موجود به علت ابعاد شکست خورده است، که باعث می‌شود که توابع خاص فاصله در فضاهای بزرگ بعدی مشکل ساز باشند. این باعث شد که الگوریتم‌های خوشه بندی جدید برای داده‌های با ابعاد بزرگ ، بر خوشه بندی زیر فضایی تمرکز کنند و استفاده شود.

چندین سیستم خوشه بندی مختلف مبتنی بر اطلاعات متقابل پیشنهاد شده‌است. یکی از آن ها، تغییرات اطلاعات مارینا مالگا است که یکی دیگر از خوشه بندی سلسله مراتبی را فراهم می‌کند. با استفاده از الگوریتم‌های ژنتیکی، طیف گسترده ای از تناسب توابع مختلف، از جمله اطلاعات متقابل، می‌تواند بهینه سازی شود،پیشرفت اخیر در علوم کامپیوتری و فیزیک آماری، منجر به ایجاد انواع جدیدی از الگوریتم‌های خوشه بندی شده‌است.

خوشه بندی (Clustering) قسمت 1
خوشه بندی (Clustering) قسمت 2
خوشه بندی (Clustering) قسمت 3

دسامبر 7, 2019/0 دیدگاه /توسط daliri

ایجاد پانوراما با چندین عکس قسمت 2

آموزش عمومی پردازش تصویر و بینایی ماشین

مرحله 1: استخراج ویژگی:

ما می بایست از توصیف کننده opencv_contrib’s SIFT استفاده کنیم. SIFT، هم چنین در مقیاس ثابت تغییر ویژگی، یک الگوریتم بسیار قدرتمند CV است. برای خواندن بیشتر در مورد ویژگی ها، لطفا بسته کلمات ویژوال من برای پست طبقه بندی عکس را بخوانید. هم چنین OpenCV’s docs on SIFT را بررسی کنید. آنها یک منبع بسیار خوب هستند!

    sift_obj = cv2.xfeatures2d.SIFT_create()
    descriptors, keypoints = sift_obj.detectAndCompute(image_gray, None)

اگر شما ویژگی ها را طرح ریزی کنید، این است که چگونه آن را خواهید دید. (تصویر سمت چپ تصویر واقعی را نشان می دهد. تصویر سمت راست با ویژگی های شناسایی شده توسط SIFT یادداشت نویسی شده است.)

مثال 1: استفاده از تصویر Lunchroom

گام دوم: تطبیق دادن مطابقت های بین تصاویر:

هنگامی که شما توصیف گرها و نقاط کلیدی دو تصویر را دارید، به این معنی که یک جفت تصویر، ما مطابقت های بین آنها را پیدا خواهیم کرد. چرا این کار را می کنیم؟ خوب، برای پیوستن هر دو تصویر به یک تصویر بزرگتر، ما باید درباره نقاط دارای اشتراک که چه هستند به دست بیاوریم. این نقاط دارای اشتراک به ما یک ایده از جهت گیری تصویر دوم w.r.t به دیگری می دهد. و بر اساس این نقاط رایج، ما یک ایده می گیریم که آیا تصویر دوم به تصویر بزرگتر اسلاید شده است یا چرخش داده شده و سپس همپوشانی شده است یا شاید مقیاس پایین/بالا شده و سپس نصب شده است. همه این اطلاعات از طریق ایجاد مطابقت ها به دست آمده است. این فرآیند ثبت(registration) نامیده می شود.

برای تطبیق، می توان از FLANN یا BFMatcher استفاده کرد که توسط opencv ارائه شده است.

  # FLANN parameters
    FLANN_INDEX_KDTREE = 0
    index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
    search_params = dict(checks=50)   # or pass empty dictionary

    flann = cv2.FlannBasedMatcher(index_params,search_params)

    matches = flann.knnMatch(des1,des2,k=2)

    img3 = cv2.drawMatchesKnn(img1c,kp1,img2c,kp2,matches,None,**draw_params)

    cv2.imshow("correspondences", img3)
    cv2.waitKey()

پس از محاسبه تطابق ها، شما یک خروجی مشابه دریافت می کنید:

با مجموعه داده Lunchroom

تطبیق ویژگی در تصاویر Lunchroom

با مثال تپه:

تطبیق ویژگی در تصویر نمونه تپه

مرحله 3: محاسبه هموگرافی

بله، هنگامی که ما مطابقت ها را بین تصاویر به دست آورده ایم، گام بعدی ما محاسبه ماتریس هموگرافی است. همانطور که در بالا توضیح داده شد، ماتریس هموگرافی از این نقاط تطبیق برای برآورد تبدیل جهت نسبی در دو تصویر استفاده می کند به این معنی که این معادله را حل خواهد کرد.

از این رو، این برای ماتریس H حل می شود.

خب، برای ارزیابی هموگرافی یک کار ساده است. اگر از opencv استفاده می کنید، این کد دو خط است. با این حال، من توصیه می کنم که خود آن را پیاده سازی کنید.

 H, __ = cv2.findHomography(srcPoints, dstPoints, cv2.RANSAC, 4)

هورا! ماتریس هموگرافی ما چیزی شبیه به این به نظر می رسد …

به هر حال، گرافیک بسیار زیبا را کنار بگذارید، آنچه که ماتریس هموگرافی است را بفهمید. هموگرافی خطوط مستقیم را در یک تصویر حفظ می کند. از این رو تنها تغییرات احتمالی ممکن است برگردان ها، وابسته انتقال های خطی و غیره باشند.

به عنوان مثال، برای انتقال خطی

همچنین میتوانید با h13 و h23 برای برگردان بازی کنید.

گام چهارم: خم کردن و دوختن:

برای درک دوختن، من می خواهم پیشنهاد بدم Adrian Rosebrock’s blog post on OpenCV Panorama stitching. وبلاگ او توضیح فوق العاده ای در مورد چگونگی اقدام به دوخت تصویر و ساخت پانوراما با استفاده از 2 تصویر ارائه می دهد.

بنابراین، هنگامی که ما یک هموگرافی را ایجاد کرده ایم، یعنی ما می دانیم که چگونه تصویر دوم (اجازه دهید بگوییم تصویر سمت راست) را از منظر تصویر فعلی نگاه کنیم، ما نیاز داریم آن را در یک فضای جدید تبدیل کنیم. این تحول، پدیده ای که ما متحمل شدیم را تقلید می کند. این است تصویر کمی تحریف شده و تغییر یافته ای که ما از پیرامونمان می بینیم. این فرایند خم شدن نامیده می شود. ما یک تصویر را بر اساس یک تبدیل جدید، تبدیل می کنیم. در این مورد، من از انحراف مسطح استفاده میکنم. آنچه که من انجام می دهم اساساً صفحه ی زمینه ی دید من را تغییر می دهد. در حالی که، “برنامه های پانوراما” از چیزی که به عنوان یک پیچ و تاب های استوانه ای و کروی نامیده می شود، استفاده می کنند!

انواع خم کردن:

*سطحی: در جایی که هر تصویر یک عنصر از یک سطح مسطح است، با توجه به برگردان و چرخش …

* استوانه ای: در جایی که هر تصویر به گونه ای نشان شده است که سیستم مختصات استوانه ای باشد. و تصویر بر روی سطح منحنی استوانه ترسیم شد.

* کروی: در بالا به جای استوانه، مدل مرجع یک کره است.

هر مدل دارای برنامه کاربردی خود است. برای اهداف این آموزش، من هموگرافی مسطح و انحراف را می چسبانم. بنابراین، برای خم کردن، که اساسا میدان دید را تغییر می دهد، ما ماتریس هموگرافی را به تصویر اعمال می کنیم.

warped_image = cv2.warpPerspective(image, homography_matrix, dimension_of_warped_image)

در اینجا کمی تجسم … است. در زیر تصاویر خم شده به راست و خم شده به چپ هستند.به جهت گیری و تصویربرداری هر تصویر توجه داشته باشید.

تصاویر خم شده Lunchroom

سابقاً، ما یک تصویر خم شده را به دست آورده ایم، ما به سادگی تصویر خم شده را همراه با تصویر دوم اضافه می کنیم. این را زیاد از طریق دوختن در سمت راست و دوختن در سمت چپ تکرار کنید، و هورا! ما خروجی را داریم.

من می خواهم کمی عمیق تر به بخش نحوه انجام تصویر پیوستن بپردازم. می گوییم ما یک ماتریس هموگرافی H داریم. اگر مختصات شروع هر تصویر (0،0) و نقطه انتهایی باشد،ما می توانیم ابعاد تصویر خم شده جدید را با تا دریافت کنیم. توجه: اگر start_pt که بیرون می آید منفی باشد، برای یک تغییر برگردانی حساب می شود. یعنی “اقدام برای تغییر برگردان به تصویر توسط “. همچنین اطمینان حاصل کنید که ماتریس هموگرافی عادی شده است به طوری که آخرین ردیف به یک بردار واحد مربوط می شود.

شما می توانید توضیحات ذکر شده بالا را در زیر بررسی کنید این قطعه پیاده سازی از کد واقعی است. لطفا کد کامل را ببینید که بفهمید مطابق با پست باشد.

    def leftstitch(self):
        # self.left_list = reversed(self.left_list)
        a = self.left_list[0]
        for b in self.left_list[1:]:
            H = self.matcher_obj.match(a, b, 'left')
            print "Homography is : ", H
            xh = np.linalg.inv(H)
            print "Inverse Homography :", xh
            # start_p is denoted by f1
            f1 = np.dot(xh, np.array([0,0,1]))
            f1 = f1/f1[-1]
            # transforming the matrix 
            xh[0][-1] += abs(f1[0])
            xh[1][-1] += abs(f1[1])
            ds = np.dot(xh, np.array([a.shape[1], a.shape[0], 1]))
            offsety = abs(int(f1[1]))
            offsetx = abs(int(f1[0]))
            # dimension of warped image
            dsize = (int(ds[0])+offsetx, int(ds[1]) + offsety)
            print "image dsize   =  &amp;gt;  ", dsize
            tmp = cv2.warpPerspective(a, xh, dsize)
            # cv2.imshow("warped", tmp)
            # cv2.waitKey()
            tmp[offsety:b.shape[0]+offsety, offsetx:b.shape[1]+offsetx] = b
            a = tmp

روش دیگر: یک روش دیگر وجود دارد، یعنی استفاده از ساختارهای حلقه پایه for و دو تصویر را روی هم قرار دهیم. منطق ساده است. ورودی به متد تصویر ثابت و تصویر خم شده خواهد بود. تکرار از طریق هر دو تصویر، و اگر پیکسل ها برابر هستند، پیکسل را به عنوان آن مقدار قرار می دهد. جز این به یک پیکسل غیر سیاه ترجیح می دهم.

 def mix_match(self, leftImage, warpedImage)
        i1y, i1x = leftImage.shape[:2]
        i2y, i2x = warpedImage.shape[:2]

        for i in range(0, i1x):
            for j in range(0, i1y):
                try:
                    if(np.array_equal(leftImage[j,i],np.array([0,0,0])) and  \
                        np.array_equal(warpedImage[j,i],np.array([0,0,0]))):
                        # print "BLACK"
                        # instead of just putting it with black, 
                        # take average of all nearby values and avg it.
                        warpedImage[j,i] = [0, 0, 0]
                    else:
                        if(np.array_equal(warpedImage[j,i],[0,0,0])):
                            # print "PIXEL"
                            warpedImage[j,i] = leftImage[j,i]
                        else:
                            if not np.array_equal(leftImage[j,i], [0,0,0]):
                                bl,gl,rl = leftImage[j,i]                               
                                warpedImage[j, i] = [bl,gl,rl]
                except:
                    pass
        # cv2.imshow("waRPED mix", warpedImage)
        # cv2.waitKey()
        return warpedImage def mix_match(self, leftImage, warpedImage)
        i1y, i1x = leftImage.shape[:2]
        i2y, i2x = warpedImage.shape[:2]

        for i in range(0, i1x):
            for j in range(0, i1y):
                try:
                    if(np.array_equal(leftImage[j,i],np.array([0,0,0])) and  \
                        np.array_equal(warpedImage[j,i],np.array([0,0,0]))):
                        # print "BLACK"
                        # instead of just putting it with black, 
                        # take average of all nearby values and avg it.
                        warpedImage[j,i] = [0, 0, 0]
                    else:
                        if(np.array_equal(warpedImage[j,i],[0,0,0])):
                            # print "PIXEL"
                            warpedImage[j,i] = leftImage[j,i]
                        else:
                            if not np.array_equal(leftImage[j,i], [0,0,0]):
                                bl,gl,rl = leftImage[j,i]                               
                                warpedImage[j, i] = [bl,gl,rl]
                except:
                    pass
        # cv2.imshow("waRPED mix", warpedImage)
        # cv2.waitKey()
        return warpedImage

اما این روش بیش از حد پیکسل تکرار خواهد کرد. این خیلی آهسته است، به دو دلیل. اولاً، این با تکرار سنگین پیچیده می شود. و، خوب، من شخصاً چنین حلقه های سنگینی را در ++C اجرا می کنم و نه در پایتون.

بنابراین، اساساً، این همان نحوه ی عمل اصلی من به نظر می رسد… قلب و هسته تمام پیاده سازی ها

 if __name__ == '__main__':
        try:
            args = sys.argv[1]
        except:
            args = "txtlists/files1.txt"
        finally:
            print "Parameters : ", args
        s = Stitch(args)
        s.leftshift()
        # s.showImage('left')
        s.rightshift()
        print "done"
        cv2.imwrite("test.jpg", s.leftImage)
        print "image written"
        cv2.destroyAllWindows()

جزئیات پیاده سازی: بررسی کد

نتایج!!!

خوب، من کد را روی تصاویر زیر اجرا کردم. شما می توانید بر روی منابع دیگر که با پانوراما و دوخت تصویر سروکار دارند کلیک و همچنین تست کنید.

دوختن با استفاده از مثال اتاق

دوخت با میز ناهار خوری خونه من 🙂

دوخت با مجموعه داده های ترکیبی

در زیر تصاویر دیگر گرفته شده از github و منابع مختلف آنلاین هستند. مراجع را برای بیشتر ببینید.

دوختن با مثال ساختمان

دوختن با استفاده از مثال تپه

دوختن با استفاده از مثال اتاق

برای بررسی کد در Github اینجا کلیک کنید

من خم شدن استوانه ای و چگونه opencv واقعاً دوختن را اجرا می کند را در یک پست متفاوت پوشش خواهم داد.

منابع:

مقاله پایه برای پانوراما با استفاده از ویژگی های ثابت مقیاس:

[1] ” دوخت تصویر پانورامیک خودکار با استفاده از ویژگی های ثابت”, Download.springer.com , 2016. [Online]. Available: matthewalunbrown.com/papers/ijcv2007.pdf

تصاویر تست گرفته شده از

[2]”PASSTA Datasets”, Cvl.isy.liu.se, 2016. [Online]. Available: http://www.cvl.isy.liu.se/en/research/datasets/passta/.

[3] “OpenCV Stitching example (Stitcher class, Panorama)”, Study.marearts.com, 2013. [Online]. Available: http://study.marearts.com/2013/11/opencv-stitching-example-stitcher-class.html.

[4] “Github daeyun Image-Stitching Test Images”, 2016. [Online]. Available: https://github.com/daeyun/Image-Stitching/tree/master/img/hill.

[5] “Github tsherlock Test Images”, 2016. [Online]. Available: . https://github.com/tsherlock/panorama/

ترجمه شده از پیج https://kushalvyas.github.io/stitching.html

ایجاد پانوراما با چندین عکس قسمت 1
ایجاد پانوراما با چندین عکس قسمت 2

دسامبر 4, 2019/0 دیدگاه /توسط hgadmin

ایجاد پانوراما با چندین عکس قسمت 1

آموزش عمومی پردازش تصویر و بینایی ماشین

ایجاد یک پانوراما با استفاده از چندین عکس:

چسباندن(دوختن) چند تصویر

باید بگویم، حتی از گسترش آموزش پانوراما لذت بردم. چیزی درباره چشم انداز تصویر و تصاویر بزرگ شده به سادگی برای دانش آموز کامپیوتر فریبنده است. من فکر می کنم، دوختن تصویر یک مقدمه عالی برای فضاهای هماهنگ و دید چشم اندازها است. در اینجا من می خواهم چگونگی گرفتن مجموعه ای منظم از بسیاری از تصاویر را نشان دهم(فرض کنید آنها از سمت چپ به راست گرفته شده اند).

بنابراین دوخت تصویر چگونه است؟ به عبارت ساده، برای یک گروه ورودی از تصاویر، خروجی تصویر مرکبی است به طوری که آن، نقطه اوج صحنه است. ضمناً، جریان منطقی بین تصاویر بایستی حفظ شود.

به عنوان مثال، مجموعه ی تصاویر زیر را در نظر بگیرید(گرفته شده از نمونه های MATLAB). از یک گروه از یک سری عکس های بهم پیوسته ورودی، ما اساسا یک تصویر چسبانده شده منفرد ایجاد می‌کنیم. یکی که صحنه کامل را در جزئیات توضیح می دهد. این یک الگوریتم واقعاً جالب است!

مباحث تحت پوشش پیاده سازی پانوراما در زبان برنامه نویسی پایتون انجام خواهد شد.

خواندن چندین عکس (به ترتیب)

پیدا کردن سازگاری های منطقی در تصاویر (این کار با استفاده از هموگرافی انجام میشود).

دوختن تصاویر

شروع کنیم …

اجازه دهید ابتدا مفهوم mosaicking (تکه تکه بهم پیوستن) یا دوختن تصویر را درک کنیم. اساسا اگر بخواهید یک صحنه بزرگ را بگیرید. حالا دوربین شما تنها می تواند یک تصویر از یک وضوح خاص ارائه دهد و آن وضوح، می گویند 640 به 480، قطعا برای گرفتن دید بزرگ پانورامیک کافی نیست. بله، به نظر می رسد خوب است. درست است! چنین عکسهایی که به عنوان یک مجموعه منظم از صحنه مطرح می شوند، به عنوان موزاییک یا پانورامای نامیده می شوند. کل فرایند به دست آوردن تصویر چندگانه و تبدیل آنها به چنین پانوراما به عنوان موزاییک کردن(mosaicking) تصویر نامیده می شود. و در نهایت، ما یک عکس زیبا، بزرگ و سیع از نمایش منظره داریم.

روش دیگر برای دستیابی به این هدف، استفاده از لنز زاویه وسیع در دوربین شما است. آنچه که یک لنز زاویه وسیع انجام می دهد، به طور چشمگیری زاویه دید شما را افزایش می دهد. خروجی، متفاوت خواهد بود (بدیهی است). اما برای اهداف این آموزش، اجازه دهید به نحوه ایجاد پانوراما با استفاده از رایانه و نه لنز بپردازیم.

راه اندازی محیط

لطفا توجه داشته باشید که سیستم شما با پایتون 2.7 راه اندازی شده است (پیاده سازی کد در python2.7 است اگر شما نسخه های دیگر را دارید، بنابراین لطفا کد را تغییر دهید) و OpenCV 3.0. ما از خدمات OpenCV Helper برای خواندن تصاویر، نوشتن تصاویر و تبدیل فضاهای رنگ استفاده خواهیم کرد. هنگامی که تصاویر به دست می آید، کل محاسبات پانوراما با استفاده از یک تابع اختلاط خانه انجام می شود. این مقاله به سه قسمت عمده تقسیم شده است.

ورود، خواندن و پردازش تصاویر: مسیرهای تصویری از فایل های متنی. هر متن فایل حاوی لیست مسیرهای هر تصویر است. اطمینان حاصل کنید که مسیرها به ترتیب جهت چپ به راست هستند.
محاسبه جهت نسبی تصاویر w.r.t با یکدیگر: جفت
ماژول دوختن/ترکیب و مطابقت: که اساسا دو تصویر را در یک زمان پیوند می دهد.

الگوریتم

الگوریتم برای انجام دوخت تصویر بسیار ساده است.

  images []  &lt; -- Input images Assuming, that the center image is no_of_images/2 let centerIdx = length(images)/2 for each images[] at positions 0 - &gt;   centerIdx :
        perform leftward stitching

    for each images[] at positions centerIdx   -  &gt;   length(images):
        perform rightward stitching

خروجی یک موزاییک کامل از تصاویر ورودی خواهد بود.

بعضی محدودیت ها الگوریتم وقت گیر است به دلیل تعداد تکرارهای درگیر، بهتر است که تعداد تصاویر ورودی hte چندان زیاد نباشد یا نه از وضوح بسیار بالا (به عنوان مثال 4000×3000). پیاده سازی من بر روی رایانه 2 گیگابایتی دارای پردازنده Intel i3 (بر روی دستگاه من آزمایش نشده است) مبتنی است. به راحتی می توانید این مدل را با استفاده از مشخصات بالاتر یا شاید GPU ارتقا دهید/مقیاس کنید. هیچ وقت برای سعی کردن خیلی دیر نیست.

معماری پروژه:

|_ code -|
    |        |-- pano.py
    |        |-- txtlists-|
    |                     |--files1.txt .... 
    |   
    |_ images - |
    |           |- img1.jpg
    |           |- abc.jpg 
    |           .... and so on ...

معماری پروژه به شرح زیر است. دایرکتوری کد شامل فایل اصلی pano.py است. همچنین شامل یک فهرست / دایرکتوری است که حاوی فایل هایی است که دارای مسیر هایی به تصاویر در پانوراما هستند. این تصاویر بصورت جداگانه داخل تصاویر / فهرست ذخیره می شوند.

در این آموزش، من از تصاویر مجموعه داده های PASSTA استفاده خواهم کرد. این شامل 2 مجموعه داده، رستوران غذاهای مختصر و ترکیبی است. همچنین برای تست، من از تصاویری از وبلاگ بینایی رایانه Mare استفاده خواهم کرد. من از تست تصاویر تپه دیون نیز استفاده خواهم کرد. و هم چنین تی شرلوک !! (برای کاربرد و استنادات مربوطه، نگاهی به منابع بیندازید.)

اکنون قسمت واقعی

برای درک هر دو ماژول دوخت چپ یا راست، اول اجازه دهید برخی مفاهیم بینایی را مستقیماً دریافت کنیم. آنها بودند:

هم نگاشتی: اوه، من عاشق این هستم.
انحراف: علت، بدون انحراف، هم نگاشتی کمی احساس تنهایی می کند.
مخلوط کردن: به علت تفاوت های شدت کمی بیش از حد جریان اصلی وجود دارند.

هم نگاشتی

خوب، چنین فرض کنید که شما به یک منظره نگاه می کنید. شما یک میدان دید دارید و این میدان دید از آن چیزی است که شما می خواهید پانوراما ایجاد کنید. شما می‌توانید سر خود را بچرخانید و یک منطقه بزرگ را پوشش دهید. اما در حالی که شما مستقیماً نگاه میکنید، مستقیماً دیدن به طور قائم در زیر صحنه، بخش باقی مانده از منظره را کمی مایل یا کمی تنگ شده ظاهر میکند. این به واسطه فیزیک ساده است. از آنجایی که شما در یک جهت مواجه هستید، چیزهایی که به پیرامون بی نهایت شما ظاهر می شوند، نامفهوم هستند، کاهش در ابعاد و نه لزوماً مستقیم/طبیعی (کمی متمایل). این دقیقا همان چیزی است که ما از آن بهره برداری خواهیم کرد.

تصاویری که در شکل بالا نشان داده شده است را در نظر بگیرید. هر تصویر حاوی بعضی قسمت معمولی با تصاویر دیگر است. با توجه به این عادت ما می توانیم بگوییم که تصویر x یا به سمت سمت راست یا چپ تصویر y در می آید.

به هر حال، اکنون که من آن را روشن کرده ام، ادامه دهید تا چگونگی محاسبۀ هموگرافی را انجام دهیم. بگویید شما یک جفت از تصاویر I1، I2 را دارید. شما تصویر اول را ضبط میکنید. سپس شما تصمیم به چرخش دوربین خود می‌گیرید، و یا شاید کمی از برگردان را انجام دهید و یا شاید ترکیبی از حرکت چرخش/برگردان. سپس با به روز رسانی موقعیت دوربین جدید خود، تصویر دوم را ضبط کنید. مشکلی که اکنون وجود دارد این است که چگونه شما برای سیستمی که در آن به ایجاد یک تغییر نیاز خواهید داشت که به طور موثر یک نقطه را که در هر دو تصویر پیش بینی می شود حل کنید. یا به عبارت ساده، چگونه شما یک تصویر w.r.t دیگر از منظره را تجسم می کنید، با توجه به اطلاعات موجود که در مورد هر دو نقطه منظره شما وجود دارد.

انواع تغییرات

هر یک از تغییرات فوق، برخی از انواع تغییرات تصویر را انجام می دهد. برای مثال یک تبدیل تصویری(خوب در مورد شما، هم نگاشتی) خطوط مستقیم و غیره را حفظ خواهد کرد. در حال حرکت، یک ماتریس هم نگاشتی چنین است که اگر به هر تصویری اعمال شود، صفحه تصویر P1 را به صفحه تصویر دیگر P2 تبدیل می کند.

تصویر زیر را که ببینید، درک میکنید که من در مورد چه چیزی صحبت میکنم.

آنچه که در بالا می بینید، می تواند یک خروجی از اعمال هم نگاشتی از I1 = H × I2 باشد. چگونه از هم نگاشتی(Homography) برای تبدیل تصاویر در OpenCV استفاده کنیم؟(این پاسخ را نیز بررسی کنید. این عکس ها از پست مزبور گرفته شده است.)

شما می توانید از روش ()openCV findhomography برای حل مسئله برای هم نگاشتی استفاده کنید. برای پیدا کردن I1 = H × I2 شما نیاز خواهید داشت که مختصات نقاط را در صفحه اصلی تصویر 1 و مختصات نقاط هدف در تصویر 2 را به روش عبور دهید. پس از گذشت زمان، متد، ماتریس هموگرافی را از بین خواهد برد.

نحوه شناسایی نقاط برای محاسبه هموگرافی!

یکی از روش های مستقیم به شرح زیر است:

  Compute similar features in both images

    Out of them , filter out good features (you'll find plenty of tutorials on these )

    Make an array sorts of ; featuresofI1   = =  &gt;   [srcPoints], featuresofI2   = =  &gt;  [dstPoints] (using opencv nomenclature)

    Compute Homography matrix using RANSAC algorithm

دسامبر 3, 2019/0 دیدگاه /توسط daliri

حذف نویز تصاویر با شبکه های عصبی و فیلتر میانی قسمت 3

آموزش عمومی پردازش تصویر و بینایی ماشین

شبکه های عصبی پرسپترون چند لایه

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

به طور کلی شبکه های عصبی مصنوعی از لحاظ یاد گیری بر دو دسته اند: شبکه های وزن ثابت و شبکه های با وزن متغییر. خود شبکه های یاد گیر نیز به دودسته با سرپرست و بدون سرپرست تقسیم می شوند. در شبکه های با سرپرست، در فاز آموزش از نمونه هایی استفاده می گردد که خروجی ایده آل متناظر با آن ها از پیش دانسته است. به عبارت دیگر در این گونه شبکه ها، نمونه های داده ورودی برچسب دارند. در شبکه های بی سرپرست، بر اساس یک معیار(مثلا فاصله) و بر اساس موعی رقابت، خروجی مورد نظر در کلاس جداگانه قرار می گیرد.

با توجه به این که شبکه عصبی، مدل ساده شده اعصاب بدن است، درست به مانند آن ها قابلیت یادگیری دارند. به عبارت دیگر شبکه با استفاده از اطلاعاتی که از ورودی و توسط سرپرست خود دریافت می کند قادر به فراگیری روند موجود در الگو ها است. لذا به طور مشابه با انسان، روند یاد گیری در شبکه عصبی نیز از مدل های انسانی الهام گرفته است. بدین صورت که مثال های بسیاری را به دفعات بایستی به شبکه ارائه نمود تا بتواند با تغییر وزن های شبکه، خروجی مورد نظر را دنبال کند.

ارائه نمونه داده های ورودی به شبکه عصبی به دو روش امکان پذیر است:

– روش ارائه یک جا: در این روش، تمام نمونه ها به شبکه ارائه می گردند و در آخر، خطای شبکه نسبت به کل نمونه ها محاسبه گشته و وزن ها بر اساس آن خطا تغییر می کنند. در مرحله بعد مجددا تمام داده ها یک بار دیگر به شبکه ارائه شده و روند فوق نظیر به نظیر انجام می پذیرد تا نهایتا خطا به حد اقل قبولی برسد. مسلما این روش پیچیده و زمان بر بوده و نیاز به حافظه زیادی دارد. همچنین امکان به تله افتادن الگوریتم در مینیمم های محلی وجود دارد.

– روش ارائه الگو: در این روش در هر بار نمونه ها به صورت تک تک به شبکه داده شده و خطای متناظر با همان داده بلافاصله محاسبه شده و بر اساس آن، وزن های شبکه به روز رسانی می شوند. سپس نمونه بعدی به شبکه ارائه شده و روند بالا مشابها انجان می پذیرد. چون در این روش در هر گام اصلاح وزن ها بر اساس هر نمونه انجام می پذیرد، الگوریتم هم گرایی خوبی داشته و با توجه به ماهیت تصادفی موجود در ارائه تکی داده ها، احتمال خطر تله مینیمم های محلی بسیار کم خواهد بود.

به منظور آموزش شبکه و اصلاح وزن ها تا رسیدن به یک خطای معنا دار، روش های بسیار زیادی وجود دارد. یکی از مشهورترین این روش ها الگوریتم پس انتشار خطاست که در ادامه توضیح داده می شود.

الگوریتم پس انتشار خطا

این الگوریتم در سال 1986 روملهارت و مک گلیلاند پیشنهاد گردید، در شبکه های عصبی پیش رو مورد استفاده قرار می گیرد. پیش سو بودن به این معنا است که نورون های مصنوعی در لایه های متوالی قرار گرفته اند و خروجی خود را به جلو می فرستند. واژه پس انتشار نیز به معنای این است که خطا به سمت عقب در شبکه تغذیه می شوند تا وزن ها را اصلاح کنند و پس از آن مجددا ورودی مسیر پیش سوی خود را تا خروجی تکرار کنند. روش پس انتشار خطا از روش های با ناظر است به این مفهوم که نمونه های ورودی برچسب خورده اند و خروجی مورد انتظار هر یک از آن ها از پیش دانسته است. لذا خروجی شبکه با این خروجی های ایده آل مقایسه شده و خطای شبکه محاسبه می گردد. در این الگوریتم ابتدا فرض بر این است که وزن های شبکه به طور تصادفی انتخاب شده اند. در هر گام خروجی شبکه محاسبه شده و بر حسب میزان اختلاف آن با خروجی مطلوب، وزن ها تصحیح می گردند تا در نهایت این خطا مینیمم شود. در الگوریتم پس انتشار خطا، تابع تحریک هر عصب به صورت جمع وزن دار ورودی های مربوط به آن عصب در نظر گرفته می شود.

حال بایستی به بررسی ارتباط خطا با ورودی ها، وزن ها و خروجی ها بپردازیم. برای این کار روش های متفاوتی وجود دارد که برخی از مهمترین آن ها عبارتند از:

1- روش گرادیان شیب

2- روش نیوتن

3- روش اندازه حرکت

4- روش آنتروپی متقابل

5- روش Marquarlt-levenberg

الگوریتم پیشنهادی

در چند دهه اخیر متد های متفاوتی برای حذف نویز از تصاویر دیجیتال ارائه شده اند. مروری بر نتایج تحقیقات انجام شده نشان می دهد الگوریتم های مبتنی بر فاز تشخیص و فاز ترمیم از کارایی بالاتری نسبت به سایر الگوریتم ها برخوردارند. الگوریتم های تک مرحله ای بدون توجه به نویزی بودن یا نبودن یک پیکسل عمیات فیلترینگ را انجام می دهند و این امر موجب می شود جزئیات تصویر در طی عملیات فیلتر کردن تخریب شده و در نتیجه تصویر خروجی از کیفیت لازم برخوردار نباشد. در مقابل الگوریتم های مبتنی بر فاز تشخیص و ترمیم ابتدا از یک آشکار گر نویز استفاده کرده و در مرحله بعد تنها پیکسلهای نویزی وارد فیلتر می شوند و لذا پیکسل های سالم از هر گونه تغییر محفوظ نگه داشته می شوند. الگوریتم های متنوعی با معیار های مختلف جهت تشخیص نویزی بودن یک پیکسل ارائه شده اند. که در اکثریت آن ها مرز تصمیم گیری پیکسل سالم یا نویزی توسط آستانه های تعیین شده توسط کاربر مشخص می شود.

الگوریتم پیشنهادی از یک شبکه عصبی پیشرو برای فاز تشخیص پیکسل های نویزی استفاده می کند. هدف از این کار طبقه بندی پیکسل ها بر مبنای نویزی یا سالم بودن توسط شبکه عصبی است. این سیستم از دو جزء آشکارگر نویز ضربه و عملیات فیلتر گذاری تشکیل شده است. زمانی که آشکار گر، پیکسلی را نویزی برچسب گذاری کند، آن پیکسل توسط بخش بعدی فیلتر گذاری می شود و مقدار شدت روشنایی تصویر در آن پیکسل توسط همسایگی آن تخمین زده می شود.

ساختار هر شبکه مصنوعی با تعداد سلول ورودی، تعداد لایه های پنهان و تعداد سلول ها در هر لایه پنهان و تعداد سلول خروجی مشخص می شود. شبکه عصبی ارائه شده دارای 7 سلول ورودی، یک لایه پنهان با ده سلول و یک سلول خروجی است. در ادامه جزئیات شبکه پیشنهادی شرح داده خواهد شد.

با توجه به این که هر چه میزان قدر مطلق تفاضل پیکسل مرکزی و میانه پنجره فیلتر کم تر باشد احتمال نویزی بودن پیکسل مرکزی کمتر است، این ویژگی می تواند به عنوان یک ویژگی متمایز کننده پسکسل نویزی از پیکسل سالم به کار رود. ورودی دوم شبکه عصبی حاصل مینیمم گیری روی کانولوشن پنجره فیلتر در چهار فیلتر لاپلاسین می باشد. هر کدام از فیلتر ها نسبت به یکی از لبه های افقی، عمودی، لبه با شیب مثبت و لبه با شیب منفی حساس است. کمینه مقادیر حاصل از کانولوشن این 4 فیلتر را می توان به عنوان معیاری برای تشخیص نویز در نظر گرفت. از مقدار ROAD به عنوان دورودی سوم شبکه عصبی استفاده می شود. مقدار ROAD برای پیکسل های نویزی مقدار بالا و برای پیکسل های سالم مقدار پائین دارد. مقدار چهارم تا هفتم شبکه عصبی، 4 مقدار محاسبه شده توسط فیلتر SD-ROM است. و هر یک از این چهار مقدار اطلاعاتی را در رابطه با وجود نویز در پیکسل مرکزی بیان می کند.

برای آموزش هر ماشین یادگیر، نیاز به یک مجموعه از داده های آموزشی است. مجموعه داده های آموزشی جفت های ورودی – خروجی هستند که شبکه سعی در یاد گیری آن ها دارد. برای یادگیری شبکه عصبی پیشنهادی نیاز به تصویری نویزی به عنوان ورودی و تصویر باینری نویز به عنوان خروجی داریم.

رویکرد معمولی که در مقالات مختلف برای حل این مشکل ارائه شده است، تولید یک تصویر تصادفی است و هدف این کار آن است که آموزش شبکه به تصویر خاصی وابسته نباشد. برای آموزش شبکه عصبی پیشنهادی از تصویر 128*128 از بلوک های 4*4 که تمام پیکسل های هر بلوک شدت روشنایی ثابتی دارند که به صورت تصادفی انتخاب می شوند استفاده می شود.

با توجه به اینکه گلوگاه سرعت اجرای الگوریتم ارائه شده، محاسبه خروجی شبکه عصبی برای تعیین نوع پیکسل ورودی است، از یک فاز تشخیص اولیه استفاده شده است تا تنها پیکسل هایی که احتمال نویزی بودن آن ها وجود دارد برای تصمیم گیری نهایی به شبکه عصبی داده شوند.

برای آموزش شبکه پیشنهادی از الگوریتم شناخته شده ی انتشار خطای عقب گرد و حد اکثر تعداد 100 و همچنین خطای مطلوب صفر استفاده می شود. پس از آموزش شبکه، مقدار خروجی برای پیکسل های نویزی نزدیک به یک و برای پیکسل های سالم نزدیک به صفر است.

در صورتی که آشکار گر مبتنی بر شبکه عصبی، یک پیکسل را نویزی تشخیص دهد، مقدار پیکسل نویزی باید فیلتر شود و تخمینی بر مبنای مقادیر پیکسل های همسایه بدست آید. برای فیلتر کردن پیکسل های نویزی از فیلتر میانه استاندارد بر روی عناصر سالم پنجره بهره گرفته شده است. همچنین در صورتیکه تمامی پیکسل ها در همسایگی پیکسل مرکزی نویزی باشند مقدار خروجی صفر قرار داده می شود و الگوریتم برای بار دیگر به صورت بازگشتی بر روی تصویر بدست آمده اجرا می شود. برای افزایش سرعت اجرای الگوریتم از یک پیش قضاوت اولیه استفاده شده است. با توجه که تنها نویز فلفل نمکی مورد بررسی است، تمام پیکسل هایی که مقداری به جز 0 یا 255 دارند به عنوان سالم در نظر گرفته می شود. و برای طبقه بندی دقیق تر پیکسل ها از شبکه عصبی پیشنهادی استفاده می شود. پس از طبقه بندی نهایی، در صورت نویزی بودن یک پیکسل، از فیلتر میانه استاندارد برای تخمین پیکسل نویزی از پیکسل های همسایه استفاده شده است.

معیار های ارزیابی

برای ارزیابی توانایی متد های مختلف در حذف نویز از تصاویر سطح خاکستری معمولا از دو معیار استاندارد نسبت پیک سیگنال به نویز (PSNR) و میانگین مربعات خطا (MSE) استفاده می شود.

نتایج شبیه سازی

جدول 1 مقدار PSNR حاصل از اجرای الگوریتم پیشنهادی بر روی تصاویر موجود در شکل به ازای چگالی های مختلف نویز فلفل نمکی را نشان می دهد.

مقادیر PSNR حاصل از اجرای متد پیشنهادی بر روی تصاویر مختلف با درصد نویز متفاوت:

جدول 1- مقادیر PSNR حاصل از متد پیشنهادی بر روی تصاویر مختلف با درصد نویز متفاوت

Peppers	House	Barbara	Boat	Cameraman	%noisy
26.05	45.01	36.66	42.01	38.26	5
25.94	41.35	33.53	38.45	35.26	10
25.77	39.12	31.77	36.43	32.94	15
25.68	37.02	30.09	34.60	31.50	20
25.27	34.38	28.67	32.13	28.70	30
24.77	31.98	26.33	29.84	26.63	40
23.96	29.90	24.79	27.86	24.62	50
22.80	26.90	23.16	25.60	22.83	60

همچنین مقدار MSE بین تصویر اصلی و خروجی حاصل از الگوریتم پیشنهادی برای تصاویر مختلف در جدول 2 لیست شده است:

جدول 2- مقدار MSE بین تصویر اصلی و خروجی الگوریتم پیشنهادی

Peppers	House	Barbara	Boat	Cameraman	%noisy
161.10	2.04	14.02	4.08	9.69	5
165.36	4.76	28.81	9.27	19.32	10
171.82	7.97	43.22	14.78	32.97	15
175.49	12.94	63.67	22.49	45.93	20
193.14	23.67	101.47	39.79	78.56	30
216.50	41.13	151.38	67.42	141.04	40
261.06	66.49	215.35	106.35	224.29	50
340.81	132.57	314.02	178.87	338.37	60

هر چه میزان شباهت تصویر اصلی و بازیابی شده بیشتر باشد، مقدار MSE بین دوتصویر کمتر و لذا طبق رابطه میزان PSNR بین آن ها بیشتر خواهد بود.

جدول 3 نتایج مقایسه الگوریتم پیشنهادی و سایر متد های شناخته شده و موفق برای حذف نویز فلفل نمکی با چگالی 25% را برای جند تصویر نشان می دهد:

جدول 3- نتایج مقایسه الگوریتم پیشنهادی با سایر متدها

Barbara	House	Peppers	Cameraman	Boat	Method
42.62	28.12	22.89	22.24	22.19	MF
52.12	29.86	25.92	55.35	24.32	Sdrom
26.08	31.15	27.67	27.91	28.05	TONF
27.55	34.49	28.00	28.11	28.22	Yuksel
29.73	36.03	28.59	30.21	32.15	Proposed

نتایج

نتایج عددی و بصری به دست آمده از اجرای روش پیشنهادی حاکی از آن است که روش ارائه شده در حذف نویز و حفظ جزئیات لبه های تصویر موفق بوده است. همچنین با تکرار اجرای الگوریتم بر روی تصاویر با چگالی نویز بالا، نتایج قابل قبولی بدست آمد.

پیشنهاد ها

البته به منظور بهبود عملکرد شبکه عصبی در دسته بندی پیکسل ها در درصد های مختلف نویز، اگر از معیار هایی با متمایز کنندگی بالاتر و مقاوم نسبت به چگالی نویز آغشته کننده و یا استفاده از شبکه های عصبی چند لایه متناظر با چگالی های نویز مختلف استفاده کرد. همچنین در فاز دوم الگوریتم، می توان برای فیلتر کردن پیکسل های آلوده از الگوریتم های دیگری مانند میانه وزن دار یا وزن دار مرکزی استفاده کرد.

منبع

حذف نویز تصاویر با شبکه های عصبی و فیلتر میانی قسمت 1
حذف نویز تصاویر با شبکه های عصبی و فیلتر میانی قسمت 2
حذف نویز تصاویر با شبکه های عصبی و فیلتر میانی قسمت 3

دسامبر 2, 2019/0 دیدگاه /توسط hgadmin