بخش‌بندی تصویر بر مبنای طبقه‌بندی

مقدمه

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

طبقه‌­بندی

در واقع سیستم­‌هایی که بر­اساس طبقه­‌بندی داده کاوی می‌­کنند، دو مجموعه ورودی دارند: یک مجموعه آموزشی که در آن داده‌هایی که به طور پیش فرض در دسته­‌های مختلفی قرار دارند، همراه با ساختار دسته­‌بندی خود وارد سیستم می­‌شوند و سیستم براساس آن­ها به خود آموزش می­‌دهد یا به عبارتی پارامترهای دسته­‌بندی را برای خود مهیا می­‌کند. دسته دیگر از ورودی‌­هایی هستند که پس از مرحله آموزش و برای تعیین دسته وارد سیستم می‌­شوند . تکنیک­‌های داده کاوی که برای دسته‌­بندی به کار می‌­آیند عموماً شامل تکنیک­‌های شبکه عصبی و درخت تصمیم‌­گیری هستند. هدف طبقه­‌بندی داده‌­ها، سازماندهی و تخصیص داده­‌ها به کلاس­‌های مجزا می‌باشد. در این فرایند بر­اساس داده‌­های توزیع شده، مدل اولیه‌­ای ایجاد می­‌گردد. سپس این مدل برای طبقه­‌بندی داده­‌های جدید مورد استفاده قرار می‌گیرد، به این ترتیب با بکارگیری مدل بدست امده، تعلق داده‌­های جدید به کلاس قابل پیشگویی می­‌باشد. طبقه‌بندی در مورد مقادیر گسسته و پیشگویی آن­ها به کار می‌­رود.هدف پیشگویی، پیش بینی و دریافت مقدار یک خصیصه بر­اساس خصیصه‌­های دیگر می‌­باشد. بر­اساس داده­‌های توزیعی، در ابتدا یک مدل ایجاد می‌­گردد، سپس از این مدل در پیشگویی مقادیر ناشناخته استفاده می­‌شود. در داده کاوی، طبقه­‌بندی، به پیشگویی مقادیر گسسته و پیشگویی به تخمین مقادیر پیوسته اتلاق می‌­شود. در فرایند طبقه­‌بندی، اشیا موجود به کلاس­‌های مجزا با مشخصه‌­های تفکیک شده (ظروف جداگانه) طبقه‌­بندی و به صورت یک مدل معرفی می­‌گردند. سپس با در نظر گرفتن ویژگی­‌های هر طبقه، شی جدید به آنها تخصیص یافته، برچسب و نوع آن پیشگویی می‌­گردد.در طبقه‌­بندی، مدل ایجاد شده بر پایه‌­ی یک­سری داده‌­های آموزشی، (اشیا داده­‌هایی که بر چسب کلاس آن­ها مشخص و شناخته شده‌­است) حاصل می­‌آید. مدل بدست آمده در اشکال گوناگون مانند قوانین طبقه بندی (If-Then)، درخت­‌های تصمیم، فرمول­‌های ریاضی و شبکه‌­های عصبی قابل نمایش می‌­باشد. از طبقه­‌بندی می­توان برای پیشگویی کلاس اشیا داده‌­ها استفاده کرد. در برخی موارد نیز افراد ترجیح می­‌دهند مقدار یک خصیصه و نه کلاس آن را پیشگویی نمایند که به یافتن مقدار یک خصیصه، پیشگویی اتلاق می­‌گردد. در هر حال پیشگویی، تخمین مقدار و بر چسب کلاس را با هم در بر می­‌گیرد. طبقه‌­بندی و پیشگویی با استفاده از تحلیل ارتباط، خصیصه‌­هایی را که فرایند مورد نظر، بی تاثیر و قابل حذف می‌باشند، شناسایی می­‌کنند.

طبقه­‌بندی داده‌ها یک فرآیند دو مرحله ای است: 1-یادگیری  2–طبقه‌­بندی

1-در مرحله اول یک مدل ساخته می­‌شود که مجموعه‌­ای از کلاس­‌های داده­‌ای یا مفاهیم را مشخص می‌­کند. این مرحله را مرحله یادگیری گوییم که در ان یک الگوریتم طبقه­‌بندی یک مدل را با تحلیل یک مجموعه­‌ی آموزشی که مجموعه‌­ای از تاپل­‌های پایگاه داده­است می­‌سازد و بر چسب کلاس‌­های مربوط به این تاپل­‌ها را مشخص می‌­کند. یک تاپل X با یک بردار صفت (x1،x2،…،xn)-X نمایش داده می­‌شود. فرض می‌­شود که هر تاپل به یک کلاس از پیش تعریف شده متعلق است و کلاس با یک صفت که به آن صفت بر چسب کلاس می­‌گوییم مشخص می­‌شود. مجموعه آموزشی به صورت تصادفی از پایگاه انتخاب می­‌شود. از آنجایی که برچسب هر تاپل آموزشی در این مرحله مشخص است، این مرحله یادگیری نظارت شده نامیده می­‌شود. 2- در مرحله دوم، از مدل ساخته‌­شده برای طبقه­‌بندی استفاده می­‌شود. یادگیری از طریق یک تابع (X)fy انجام می­‌شود که می‌­تواند برچسب کلاس هر تاپل X از پایگاه را پیش­‌بینی کند. این تابع به صورت قواعد طبقه‌­بندی، درخت‌­های تصمیم­‌گیری یا فرمول­‌های ریاضی است. شکل زیر نشان می‌­دهد که چگونه یک تابع طبقه‌­بندی ساخته شده و سپس داده‌های جدید بوسیله آن طبقه‌­بندی می­‌شوند.

در ابتدا میزان دقت مدل یا کلاسه‌­بند تخمین زده می‌­شود. این تاپل­ها تصادفی انتخاب شده و مستقل از تاپل­‌های مجموعه آموزشی هستند. میزان دقت در پیشگویی یک مدل روی مجموعه تست داده­‌شده برابر است با درصد تاپل‌­هایی از تاپل‌­های مجموعه تست که توسط مدل، درست طبقه­‌بندی شده‌­اند. برچسب کلاس هر تاپل مجموعه تست، با برچسب کلاس پیش­گویی شده برای آن تاپل توسط مدل یادگیری مقایسه می‌­شود اگر میزان دقت مدل قابل قبول واقع شود، انگاه این مدل می­تواند برای طبقه‌­بندی تاپل­‌های جدید با بر چسب کلاس نامعلوم استفاده شود. (در اصطلاحات یادگیری ماشین به این نوع تاپل‌­ها یا داده‌­ها unknown or previously unseen data گفته می‌­شود).

انواع روش­‌های طبقه­‌بندی

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

ارزیابی روش‌های طبقه­‌بندی

ارزیابی روش‌های طبقه­‌بندی با معیارهای زیر انجام می‌­پذیرد:

میزان دقت

Classifer accuracy: میزان قابلیت و توانایی یک مدل در پیشگویی صحیح بر چسب یک کلاس.

Predictor accuracy: میزان قابلیت و توانایی یک مدل در حدس مقدار صفت­‌های پیش­گویی شده.

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

بررسی انواع روش­‌های طبقه‌­بندی

درخت تصمیم

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

بیزین

الگوریتم‌­های یادگیری بیزی به طور صریح بر روی احتمالات فرض­‌های مختلف کار می­‌کنند. کلاسه‌بندهای بیزی کلاسه‌بندهای آماری هستند. آنها اعضای کلاس را به صورت احتمالی پیشگویی می­‌کنند. مثلاً میزان احتمال این­که یک نمونه داده شده متعلق به یک کلاس خاص باشد. طبقه­‌بندی بیزی بر مبنای تئوری بیز می‌­باشد. مقایسه الگوریتم­‌های طبقه‌­بندی نشان داده‌ ­است که یک کلاسه‌­بند بیزی ساده از نظر کارایی با کلاسه بندهای درخت تصمیم و شبکه‌های عصبی قابل رقابت است و در برخی موارد بهتر از انها عمل می­‌کند. همچنین کلاسه‌بندهای بیزی میزان دقت و سرعت بالایی را هنگامی که در دیتابیس‌های بزرگ به کار برده می‌­شوند، ارائه می­‌دهند. Naïve Bayesian classifier فرض می­کند که تاثیر یک مقدار صفت روی یک کلاس داده­‌شده، مستقل از مقادیر دیگر صفت­‌ها می‌­باشد. به این فرض استقلال شرطی کلاس گفته­‌می‌­شود. این فرض محاسبات را ساده‌تر می‌کند و به همین دلیل است که به این روش naïve گفته می‎‌­شود. Bayesian belief network ها نیز که برای طبقه‌بندی استفاده می‌­شوند، مدل‌­های گرافیکی هستند که بر خلاف naïve Baysian classifier ها وابستگی میان زیر مجموعه­‌ای از صفت­‌ها را نمایش می­‌دهند.

روش طبقه‌­بندی نزدیکترین K- همسایه

هنگام تلاش برای حل مسائل جدید، افراد معمولاً به راه­‌حل‌­های مسائل مشابه که قبلاً حل شده‌­اند مراجعه می­‌کنند. k- نزدیکترین همسایه (k-NN) یک تکنیک طبقه‌­بندی است که از نسخه‌­ای از این متد استفاده می‌­کند. در این روش تصمیم‌­گیری اینکه یک نمونه جدید در کدام کلاس قرار گیرد با بررسی تعدادی (k) از شبیه­‌ترین نمونه­‌ها یا همسایه­‌ها انجام می­‌شود. در بین این k نمونه، تعداد نمونه ­ها برای هر کلاس شمرده می­‌شوند، و نمونه جدید به کلاسی که تعداد بیشتری از همسایه‌­ها به آن تعلق دارند نسبت داده می­‌شود. شکل زیر محدوده همسایگی نمونه N را نشان می‌­دهد. در این محدوده، بیش‌تر همسایه­‌ها در کلاس X قرار گرفته‌­اند.

اولین کار برای استفاده از k-NN یافتن معیاری برای شباهت یا فاصله بین صفات در داده‌­ها و محاسبه آن است. در حالی که این عمل برای داده­‌های عددی آسان است، متغیرهای دست‌ه­ای نیاز به برخورد خاصی دارند. هنگامی که فاصله بین نمونه­‌های مختلف را توانستیم اندازه گیریم، می‌­توانیم مجموعه نمونه‌­هایی که قبلاً طبقه­‌بندی شده‌­اند را به عنوان پایه دسته­‌بندی نمونه­‌های جدید استفاده کنیم. فهم مدل­های K-NN هنگامی که تعداد متغیرهای پیش­بینی کننده کم است بسیار ساده است. آن­ها هم­چنین برای ساخت مدل­‌هایی مانند متن که شامل انواع داده غیر استاندارد هستند، بسیار مفیدند. تنها نیاز برای انواع داده جدید وجود یک معیار مناسب شباهت است.

روش طبقه­‌بندی شبکه­‌های عصبی

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

روش طبقه‌بندی ماشین بردار پشتیبان

ماشین بردار پشتیبان (SVM) یکی از روش‌های یادگیری ماشین است که از تئوری یادگیری آماری سرچشمه می­‌گیرد و از آن برای طبقه­‌بندی و رگرسیون استفاده می‌کنند. این روش از جمله روش‌های نسبتاً جدیدی است که در سال‌های اخیر کارایی خوبی برای طبقه­‌بندی نسبت به روش‌های قدیمی‌تر از جمله شبکه‌های عصبی پرسپترون نشان داده است. مبنای کاری طبقه بندی SVM، طبقه بندی خطی داده‌ها است. در تقسیم خطی داده‌ها سعی می‌شود خطی انتخاب شود که حاشیه اطمینان بیشتری داشته ­باشد. برای یک مسئله طبقه بندی دو کلاسه، هدف جداسازی دو کلاس بوسیله یک تابع است که از نمونه­‌های آموزشی بدست می­‌آید. شکل زیر یک مثال از یک مجموعه داده‌­ی دو بعدی (دو کلاسه) را نشان می‌دهد که کلاس‌­های سیاه رنگ و سفید رنگ توسط خط x 2=6.5 – 2x 1 از هم جدا شده‌­اند. رنگ تیره در اطراف این خط، ماکزیمم حاشیه‌ان خط را نشان می­‌دهد.