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

مقدمه

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

طبقه‌­بندی

در واقع سيستم­‌هايي که بر­اساس طبقه­‌بندي داده کاوي مي‌­کنند، دو مجموعه ورودي دارند: يک مجموعه آموزشي که در آن داده‌هايي که به طور پيش فرض در دسته­‌هاي مختلفي قرار دارند، همراه با ساختار دسته­‌بندي خود وارد سيستم مي­‌شوند و سيستم براساس آن­ها به خود آموزش مي­‌دهد يا به عبارتي پارامترهاي دسته­‌بندي را براي خود مهيا مي­‌کند. دسته ديگر از ورودي‌­هايي هستند که پس از مرحله آموزش و براي تعيين دسته وارد سيستم مي‌­شوند . تکنيک­‌هاي داده کاوي که براي دسته‌­بندي به کار مي‌­آيند عموماً شامل تکنيک­‌هاي شبکه عصبي و درخت تصميم‌­گيري هستند. هدف طبقه­‌بندي داده‌­ها، سازماندهي و تخصيص داده­‌ها به کلاس­‌هاي مجزا مي‌باشد. در اين فرايند بر­اساس داده‌­هاي توزيع شده، مدل اوليه‌­اي ايجاد مي­‌گردد. سپس اين مدل براي طبقه­‌بندي داده­‌هاي جديد مورد استفاده قرار مي‌گيرد، به اين ترتيب با بکارگيري مدل بدست امده، تعلق داده‌­هاي جديد به کلاس قابل پيشگويي مي­‌باشد. طبقه‌بندي در مورد مقادير گسسته و پيشگويي آن­ها به کار مي‌­رود.هدف پيشگويي، پيش بيني و دريافت مقدار يک خصيصه بر­اساس خصيصه‌­هاي ديگر مي‌­باشد. بر­اساس داده­‌هاي توزيعي، در ابتدا يک مدل ايجاد مي‌­گردد، سپس از اين مدل در پيشگويي مقادير ناشناخته استفاده مي­‌شود. در داده کاوي، طبقه­‌بندي، به پيشگويي مقادير گسسته و پيشگويي به تخمين مقادير پيوسته اتلاق مي‌­شود. در فرايند طبقه­‌بندي، اشيا موجود به کلاس­‌هاي مجزا با مشخصه‌­هاي تفکيک شده (ظروف جداگانه) طبقه‌­بندي و به صورت يک مدل معرفي مي­‌گردند. سپس با در نظر گرفتن ويژگي­‌هاي هر طبقه، شي جديد به آنها تخصيص يافته، برچسب و نوع آن پيشگويي مي‌­گردد.در طبقه‌­بندي، مدل ايجاد شده بر پايه‌­ي يک­سري داده‌­هاي آموزشي، (اشيا داده­‌هايي که بر چسب کلاس آن­ها مشخص و شناخته شده‌­است) حاصل مي­‌آيد. مدل بدست آمده در اشکال گوناگون مانند قوانين طبقه بندي (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 از هم جدا شده‌­اند. رنگ تيره در اطراف اين خط، ماکزيمم حاشيه‌ان خط را نشان مي­‌دهد.