طبقه بندی های مبتنی بر تئوری بیز

طبقه بندی های مبتنی بر تئوری بیز

اسلاید 1: طبقه‌بندهای مبتنی‌بر تئوری بیزClassifiers based on Bayes Decision Theoryحسین منتظری کردیدانشکده مهندسی برق و کامپیوتر دانشگاه صنعتی نوشیروانی بابلپاييز 91

اسلاید 2: رئوس مطالب1- تئوری تصمیم بیز2- توابع تمایز و سطوح تصمیم3- طبقه‌بندی بیزین برای توزیع‌های نرمال4- تخمین توابع چگالی احتمال نامعلوم5- قاعده نزدیکترین همسایه6- شبکه‌های بیزین

اسلاید 3: 1- تئوری تصمیم بیزهدف طراحی طبقه‌بندی جهت قراردادن یک الگوی ناشناس در محتمل‌ترین کلاسفرض M کلاس از ω1، ω2، ...، ωM موجود بوده و یک بردار ویژگی ناشناس x داریم. M احتمال شرطی بصورت P(ωi|x), i =1, 2, …, M را تشکیل می‌دهیم، این توابع احتمال شرطی را احتمالات پسین نیز می‌نامندهر احتمال‌پسین بیانگر میزان تعلق بردار x به کلاس ωi می‌باشدمحتمل‌ترین کلاس می‌تواند برابر اندیس احتمال شرطی بیشینه باشد و x به آن تعلق داردکار طراحی با تخمین توابع چگالی احتمال (pdf) از روی بردارهای ویژگی مجموعه داده آموزش شروع می‌شودبرای سادگی، مسئله دو کلاسه را در نظر بگیرید (ω1، ω2) و احتمال‌ پیشین اتفاق هر کلاس نیز معلوم فرض می‌شودحتی اگر اینگونه نبود، به آسانی قابل تخمین‌زدن می‌باشند (غیر دقیق)

اسلاید 4: توابع چگالی احتمال شرطی کلاس، P(x|ωi), i =1, 2، بیانگر توزیع هر بردار ویژگی در کلاس مربوطه، قابل تخمین توسط داده آموزش؛ این تابع بعنوان تابع همانندی (likelihood function) نیز شناخته می‌شودطبق قاعده بیزقاعده طبقه‌بندی بیزبا جایگزینی قاعده بیز در رابطه طبقه‌بندی، داریمهمانطور که می‌بینیم، به P(x) در رابطه نهایی احتیاجی نیست و اگر احتمال پیشین وقوع کلاسها را برابر در نظر بگیریم داریم:

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

اسلاید 6: باتوجه بشکل، خطای تصمیم برابر است باهدف در طراحی طبقه‌بند بیز، حداقل کردن خطای تصمیم‌گیری می‌باشدحداقل کردن احتمال خطای طبقه‌بندیاز لحاظ کمینه احتمال خطا، طبقه‌بند بیز بهینه می‌باشدP(.,.) احتمال توام دو رویداد، طبق قانون بیزخطا کمینه است اگر R1 و R2 بصورت زیر تعریف شوند

اسلاید 7: از سویی دیگر، R1 و R2 کل فضای ویژگی را پوشش می‌دهند و داریمبدیهی است، تنها در صورتی خطا کمینه خواهد بود که در ناحیه R1 در حالت M کلاسه، بردار ویژگی x متعلق به کلاس ωi می‌باشد هرگاهحداقل کردن متوسط خطرپذیری (Average risk) احتمال خطای طبقه‌بندی همواره بهترین معیار نیست

اسلاید 8: بدلیل نسبت‌دادن اهمیت یکسان به تمام خطاها، مثال خطر تشخیص اشتباه یک بیمار با تومور بدخیم بعنوان خوشخیم (منجر به مرگ بیمار و بالعکس خیر)راه حل، اختصاص یک جریمه (پنالتی) بعنوان وزن برای هر خطا؛ فرض ω1 کلاس بیماران سرطانی و ω2 افراد سالم، همچنین نواحی مربوطه بترتیب R1 و R2هدف کمینه کردن تابع خطرپذیری زیرانتخاب منطقی بصورت λ12> λ21 خواهدبوددر مسئله M کلاسه با نواحی تصمیم Rj, j = 1, 2, …, M فرض می‌کنیم بردار x از کلاس ωk در Ri, i≠k قرار گیرد. مقدار جریمه λki بنام تلفات به این تصمیم اشتباه اختصاص می‌یابد، ماتریس تلفات L با درایه‌های (k,i) مبین مقدار جریمه تشکیل‌می‌شود، و مقدار خطرپذیری یا تلف کلاس k

اسلاید 9: در رابطه قبلی، احتمال قرارگیری بردار ویژگی x از کلاس k در کلاس i محاسبه می‌شودهدف انتخاب یک یک ناحیه تصمیم Rj جهت کمینه کردن متوسط rk می‌باشدرابطه بالا کمینه است اگر هریک از انتگرالها کمینه باشداگر λki= 1- δki باشد، آنگاه حداقل‌متوسط‌خطرپذیری معادل با حداقل احتمال طبقه‌بندی خواهدبود. در حالت دو کلاسه داریمآنگاه x به ω1 اختصاص دارد، اگر l1 < l2 باشد

اسلاید 10: طبیعی است که λij>λii باشد، قاعده تصمیم بنام نسبت همانندی برای دو کلاسبطور معمول، عناصر قطری ماتریس تلفات را صفر در نظر می‌گیرند، حال اگر بخواهیم طبقه‌بندی اشتباه الگوهای کلاس 2 در کلاس 1 عواقب وخیم بهمراه داشته باشد، آنگاه بایستی λ21>λ12 در رابطه بالا، احتمال وقوع کلاس‌ها برابر فرض شده‌اند. مثال: برای یک مسئله دوکلاسه، با فرض احتمال گوسی برای بردار ویژگی x با σ2 = ½ و میانگین صفر و یک بترتیب برای هر کلاس، مقدار آستانه را برای کمینه احتمال خطا و خطرپذیری با ماتریس تلف زیر حساب نمایید.

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

اسلاید 12: اگر نواحی Ri و Rj مجاور هم در فضای ویژگی باشند، آنگاه یک سطح تصمیم ایندو را از هم جدا می‌نماید. این سطح جهت حداقل خطای احتمال بصورت زیر توصیف می‌شودبجای کار با توابع چگالی احتمال، از توابع جایگزین استفاده می‌کنیمدر رابطه بالا، f (.) یک تابع صعودی یکنواخت، و gi(.) نیز تابع تمایز (Discriminant function) نام داردمسئله طبقه‌بندی بصورت تصمیم‌گیری زیر خلاصه می‌شودسطوح تصمیم جداکننده نواحی مجاور نیز بصورت

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

اسلاید 14: میانگین و واریانس از روابط زیر محاسبه می‌شوند

اسلاید 15: توزیع گوسی برای حالت چند متغیره در فضای l بعدی بصورت در رابطه بالا، μ بردار میانگین و ∑ ماتریس کوواریانس l × lبرای حالت دو متغیره یا فضای ویژگی دو بعدیدر رابطه بالا، σ12 کوواریانس بین دو متغیر بوده و بیانگر همبستگی آماری متقابل دو متغیر می‌باشد، یعنی اگر دو متغیر مستقل باشند آنگاه σ12 صفر خواهدبوددر حالت دو متغیره برای تعبیر هندسی توابع توزیع داریم

اسلاید 16: معادله یک بیضی برحسب ثابت C

اسلاید 17: 3-2- طبقه‌بند بیزین برای کلاس‌های با توزیع نرمالبرای یک طبقه‌بند بیزین بهینه، با توصیف توزیع داده هر کلاس بصورت توزیع‌های نرمال چند متغیره و استفاده از تابع تمایز لگاریتمی داریمکه ci یک ثابت بصورت می‌باشد، با بسط تابع بالا داریمرابطه بالا، یک رابطه تربیعی غیرخطی می‌باشد. در حالت دو کلاسه با ماتریس کوواریانس قطری سطوح تصمیم و طبقه‌بند بیزین یک سطح و طبقه‌بند درجه دو می‌باشد

اسلاید 18: مثال: مسئله دو کلاسه با مقادیر زیر

اسلاید 19:

اسلاید 20: ابرصفحه‌های تصمیماگر ماتریس کوواریانس کلاسها را یکسان فرض کنیم؛ ∑i=∑؛ تابع تصمیم بصورتتابع تصمیم بالا، یک تابع خطی می‌باشد، و بنابراین سطوح تصمیم ابرصفحه است■ ماتریس کوواریانس قطری با عناصر مساویفرض ویژگیهای منفرد بردار ویژگی متقابلا ناهمبسته با واریانس برابر باشنددر این حالت، ∑= σ2I که I ماتریس یکانی l بعدی است

اسلاید 21: سطح تصمیم یک ابرصفحه گذرنده از نقطه x0 می‌باشد، اگر احتمال وقوع کلاسها را برابر در نظر بگیریم آنگاه تابع تصمیم بالا، یک تابع خطی می‌باشد، و بنابراین سطوح تصمیم ابرصفحه است. این ابرصفحه بر خط μi-μj در همه حالات عمود است. برای هر x روی ابرصفحهاگر واریانس کلاسها کوچک باشد، آنگاه تفاوت کم در احتمال وقوع کلاسها تاثیر چندانی در تصمیم‌گیری ندارد (تعبیر هندسی واریانس، دایره بشعاع σ حول مرکز μ)ولی اگر مقدار واریانس کلاسها بزرگ باشد، آنگاه جابجایی ابرصفحه با اختلاف بین احتمال کلاسها در تصمیم‌گیری تاثیرگذار می‌باشد■ ماتریس کوواریانس غیرقطری مشابه قبل برای سطح تصمیم داریم

اسلاید 22:

اسلاید 23: در رابطه بالا، نُرم ∑-1 از x نام داردهمانند ماتریس کوواریانس قطری، تمام مطالب صحیح بوده، باستثنای اینکه ابرصفحه تصمیم بر بردار μi-μj عمود نمی‌باشد و بر تبدیل خطی آن ∑-1(μi-μj) عمود استطبقه‌بند حداقل فاصلهحالت کلاسهای هم احتمال با ماتریس کوواریانس یکسان را درنظر بگیرید، داریمدر رابطه بالا، مقدار ثابت صرفنظر شده‌است. باتوجه به ماتریس کوواریانس داریم■ ماتریس کوواریانس قطری (∑= σ2I)در این حالت، بیشینه gi منجر به فاصله اقلیدسی می‌گردد

اسلاید 24: بردار ویژگی به کلاسی با کمترین فاصله اقلیدسی نسبت داده می‌شود■ ماتریس کوواریانس غیرقطری در این حالت، بیشینه gi منجر به نرم ∑-1 می‌گردد و معروف به فاصله ماهالانوبیسدر حالت اقلیدسی، dε= c دوایری بمرکز میانگین کلاسها بوده و برای دومی، dm= c بیضی شکل بمرکز میانگین است. در حالت اقلیدسی خط تصمیم بر خط فاصل دو میانگین عمود بوده و در حالت دوم، این خط باتوجه به بیضی‌ها چرخش دارد.ملاحظاتدر عمل اغلب داده‌ها با توزیع گوسی فرض می‌شوند، لذا طبقه‌بند بیزین برحسب قطری یا غیرقطری بودن ماتریس کوواریانس ماهیت خطی یا تربیعی دارد. در آمار به این نوع از طبقه‌بندها بترتیب تحلیل تمایز خطی (LDA: Linear discriminant analysis) یا تحلیل تمایز تربیعی (QDA: Quadratic discriminant analysis) گویند

اسلاید 25: مشکل LDA و QDA تخمین پارامترهای زیاد می‌باشد، در فضای l بعدی‌ویژگی بترتیب l و l 2/2 برای بردار میانگین و ماتریس کوواریانس متقارن

اسلاید 26: LDA و QDA در بسیاری از کاربردها دارای عملکرد خوب می‌باشند. علت این امر بیشتر در سطوح تصمیم خطی و تربیعی نهفته است تا فرض گوسی بودن توزیع داده4- تخمین توابع چگالی احتمال نامعلومدر بیشتر موارد، توابع چگالی احتمال کلاسها ناشناخته بوده و مجبور به تخمین‌زدن آن از روی داده موجود می‌باشیمگاهی اوقات شکل توزیع (گوسی یا رایلی) معین و پارامترها (میانگین، واریانس) نامعین؛ و در برخی موارد توزیع نامعین و پارامترها (میانگین، واریانس) معین4-1- تخمین پارامتر با روش حداکثر شباهت (همانندی)در یک مسئله M کلاسه بردارهای ویژگی بصورت توابع شباهت p (x |ωi) در شکل پارامتری به بردارهای ناشناخته θi وابسته استهدف تخمین پارامترهای تابع بصورت p (x |ωi;θi) از روی یک مجموعه بردار ویژگی معین (مجموعه داده آموزش) برای هر کلاسفرض داده هر کلاس مستقل از کلاسهای دیگر می‌باشد (جهت تخمین پارامترها)

اسلاید 27: نمونه‌های تصادفی از تابع p (x ; θ) می‌باشند و تابع چگالی احتمال توام p (X ; θ) از روی مجموعه را تشکیل می‌دهیمبا فرض استقلال آماری بین نمونه‌ها، داریمتابع بالا را تابع شباهت θ برحسب X نامیده، و روش حداکثر شباهت (ML) مقدار θ را برای بیشینه کردن این تابع تخمین می‌زندشرط لازم برای بیشینه شدن تابع بالا، صفرشدن مشتق آن برحسب θ می‌باشدبا تعریف تابع لگاریتمی بصورت

اسلاید 28: با جایگزینی تابع لگاریتمی بجای تابع چگالی، داریمخواص تخمین‌گر ML - این تخمین‌گر بدون بایاس می‌باشد، یعنی میانگین تخمین با خودش برابر است - تخمین‌گر سازگار می‌باشد، یعنی برای مقادیر بزرگ از N واریانس تخمین به صفر میل می‌کند - تخمین‌گر ML باند پایین کرامر-رائو (کوچکترین واریانس ممکن) را برآورده می‌کند - برای مقادیر بزرگ N این تخمین‌گر دارای توزیع نرمال می‌باشدمثال: تخمین ML از یک داده N نقطه‌ای با میانگین معلوم و واریانس نامشخص را بیابید. این نقاط توسط یک تابع pdf گوسی یک بعدی تولید شده‌اند.

اسلاید 29: تخمین بالا دارای بایاس میباشد، اگر N بسمت بینهایت میل کند4-2- تخمین بیشینه احتمال پسین (Maximum a posteriori probability) در این تخمین θ را بردار تصادفی فرض می‌کنیم و مقدارش را بشرط مشاهده نمونه‌های داده تخمین می‌زنیم. با قانون بیز داریم

اسلاید 30: تخمین MAP با بیشینه کردن احتمال p (θ|X ) تعریف می‌شوداختلاف تخمین‌های ML و MAP در وجود p (θ) می‌باشد4-3- استنتاج بیزینفرض‌می‌شود N بردار آموزشی X موجود باشد و اطلاعات پیشین درباره تابع‌چگالی‌احتمال p (θ) نیز مفروض باشد، هدف محاسبه تابع‌چگالی‌احتمال‌شرطی p (x |θ) و می‌دانیممشکل روابط بالا، عدم وجود راه‌حل تحلیلی برای تخمین‌گر می‌باشد، استفاده از روش‌های عددی نظیر روش زنجیره مارکوف-مونت کارلو (MCMC) جهت حل مسئله

اسلاید 31: ملاحظاتسه‌تخمین‌گر ML، MAP، و BI بازای مقادیر بزرگ N یکسان بوده، و در مقادیر کوچک متفاوت هستندبرای داده‌های با طول محدود، تخمین‌گرهای ML و MAP ساده‌تر می‌باشند4-4- تخمین بیشینه آنتروپیآنتروپی ریشه در تئوری اطلاعات شانون دارد، اندازه‌ای برای سنجش تصادفی‌بودن اطلاعات (بردار ویژگی) خروجی یک سامانه، برای یک متغیر تصادفی فرض می‌شود تابع p (x) نامعین بوده ولی به تعدادی قیود معلوم (میانگین، واریانس) وابسته است؛ بیشینه آنتروپی تابع pdf نامعلوم را برای بیشینه نمودن انتگرال بالا با قیود داده شده تخمین می‌زندمثال: متغیر تصادفی x بین x1 ≤ x ≤ x2 غیرصفر و بقیه جاها صفر است. تخمین بیشینه

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

اسلاید 33: 4-5- مدلهای ترکیبی (Mixture models)یکی‌از راه‌های مدل‌کردن یک تابع p (x) استفاده از ترکیب خطی توابع چگالی بصورت زیر می‌باشداولین گام، انتخاب مجموعه‌ای از مولفه‌های چگالی پارامتری بشکل p (x|j;θ) و محاسبه پارامترهای θ و pj, j= 1, 2, …, J برحسب مجموعه داده آموزشالگوریتم بیشینه امید ریاضی (The expectation maximization algorithm)اطلاعات اشتباه برچسب موجب می‌شود تا مسئله دارای مجموعه‌داده غیرکامل شود، روش EM برای این نوع داده بسیار مناسب می‌باشدهدف این روش، تخمین pdf داده غیرکامل از روی نمونه‌های یک مجموعه‌کامل می‌باشد

اسلاید 34: از آنجاییکه yها در دسترس نمی‌باشند، الگوریتم EM امید ریاضی تابع لگاریتم همانندی را مشروط به نمونه‌های مشاهده (xها) در هر مرحله بیشینه می‌کندگام E در مرحله (تکرار) t + 1 و موجود بودن θ(t )، امید زیر را حساب می‌کنیمگام M تخمین t + 1 از θ را با بیشینه کردن رابطه زیر حساب می‌کنیمبرای اجرا، از یک حدس اولیه θ(0) شروع کرده و تکرار مراحل تا ||θ(t +1)-θ(t )||≤ε ادامه می‌یابدکاربرد EM برای مسئله مدلسازی ترکیبیدر مدل‌ترکیبی، مجموعه‌داده کامل بصورت (xk, jk), k= 1, 2, …, N وجود داشته و jk نیز یک عدد صحیح بین [1, J] است؛ این اندیس نشان می‌دهد ترکیب از کدام xk تولید شده‌است

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

اسلاید 36: برای ترکیب گوسی با ماتریس کوواریانس قطری، ∑= σ2I، داریمعلاوه‌بر احتمال‌پیشین، Pj، مقادیر μj و σj برحسب j= 1, 2, …, J نامعلوم بوده و θ یک بردار J(l +1) بعدی می‌باشد. با ادغام معادلات داریم: مرحله E:مرحله M:

اسلاید 37: برای تکمیل مراحل الگوریتم EM نیاز به محاسبه احتمالات زیر داریم: مشکل روش بالا در تخمین پارامترها، نامعین‌بودن مقدار دقیق J می‌باشد. یک راهکار برای حل مشکل، استفاده از تکنیک تخمین خطا است. 4-6- تخمین غیرپارامترییک تکنیک مبتنی‌بر تخمین هیستوگرامی از تابع چگالی احتمالمراحل تخمین pdf بصورت - ابتدا محور فضای ویژگی را به h قسمت تقسیم می‌کنیم - احتمال یک نمونه x متعلق به یک قسمت برای هر بخش تخمین‌زده می‌شود - اگر N تعداد کل نمونه‌ها باشد و kN تای آن در یک قسمت قرار گیرد

اسلاید 38: آنگاه با نسبت فرکانسی، احتمال آن قسمت برابر است با - اگر N بسمت بینهایت میل کند، آنگاه تخمین بالا به مقدار واقعی p می‌رسد. مقدار pdf بصورت زیر تخمین‌زده می‌شود؛ نقطه میانی قسمت مربوطه است

اسلاید 39: - برای مقادیر کوچک h مقدار p در قسمت مربوطه ثابت است؛ در عمل برای تخمین مناسب بایستی N باندازه کافی بزرگ، h بقدر کافی کوچک، و kN نیز بمقدار کافی زیادپنجره‌های پارزن (Parzen windows)درحالت چند بعدی، بجای قسمتهای جعبه‌ای باندازه h، فضای l بعدی‌ویژگی به مکعب‌های با طول h و حجم hl تقسیم می‌شود. بیایید بردارهای ویژگی باشند، تابع زیر را تعریف می‌کنیم:جاییکه مولفه‌های بردار هستند. بعبارتی، این تابع تمام مقادیری از که در داخل‌مکعبی به طول 1 و مرکزیت مبداء قرارگیرند، مقدار 1 داده و مابقی صفر می‌شونددر اینحالت، برای تخمین احتمال داریم:

اسلاید 40: رابطه قبلی، تابع pdf را با استفاده از بسط به توابع پله گسسته تخمین می‌زند.تابع هموارساز φ به توابع کرنل، توابع پتانسیل، و یا پنجره‌های‌پارزن معروف هستند. یکی‌از این توابع کرنل می‌تواند تابع گوسی بصورت N(0,I) باشد، در اینحالت داریم:

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

اسلاید 42:

اسلاید 43:

اسلاید 44: با افزایش ابعاد بردار ویژگی، مسئله کم بودن N بیشتر نمایان می‌شود و برخی از نواحی فضای ویژگی دارای نقاط پراکنده می‌شوند. لذا، برای حل این مشکل بهتر است از h متغیر استفاده شود (در نقاط پراکنده از h بزرگ)تخمین چگالی با k نزدیکترین همسایه (k nearest neighbor)در تخمین پارزن، حجم اطراف نقطه x ثابت برابر hl درنظر گرفته‌شد و لذا، تعداد kN از یک نقطه به نقطه دیگر بطور تصادفی دارای تغییر زیاد می‌باشددر تخمین k نزدیکترین‌همسایه، نقش h و kN عوض می‌شود. مقدار kN =k ثابت و فاصله حجم اطراف x هر لحظه تنظیم می‌شودبنابراین، در سطوح کم چگال مقدار حجم بزرگ و در سطوح پر چگال مقدار حجم کوچکتخمین‌گر در روش k نزدیکترین همسایه بصورتاز نقطه نظر عملی، با ورود یک بردار ویژگی ناشناخته x فاصله آن تا تمامی بردارهای آموزش از همه کلاس‌ها محاسبه می‌شود

اسلاید 45: طبقه‌بندی kNN دو کلاسهفرض r1 شعاع ابرکره بمرکز x شامل k نقطه از ω1 و r2 شعاع ابرکره شامل k نقطه از ω2 باشند (لزوما نقاط k برای کلاسها برابرنیستند)؛ اگر V1 و V2 بترتیب حجم کره‌ها باشند، با آزمودن نسبت شباهتبکارگیری فاصله اقلیدسی منجر به ایجاد ابرکره، و فاصله ماهالانوبیس ایجاد ابربیضیحجم ابربیضی برای فاصله ماهالانوبیس به اندازه r برحسب حجم کره با شعاع واحدملاحظاتهرچند کارآیی تخمین‌گرهای غیرپارامتری با افزایش ابعاد فضای ویژگی کاهش

اسلاید 46: می‌یابد، ولی بعنوان طبقه‌بند از عملکرد مطلوبی برخوردار هستندمثال: دو کلاس هم احتمال با توزیع نقاط بصورت: مشکی (ω1)، و آبی (ω2) را درنظر بگیرید. هدف طبقه‌بندی نقطه ستاره به مشخصه (0.7, 0.6) با روش 5NN می‌باشد

اسلاید 47: - با استفاده از فاصله اقلیدسی، 5 همسایه نزدیکتر در کلاسهای ω1 و ω2 تعیین شدند - برای محاسبه حجم، شعاع متناظر با دورترین همسایه از مرکز ستاره محاسبه می‌شود؛ به ترتیب مقادیر و برای کلاسهای 1 و 2 - تعداد نقاط کلاس یک برابر N1= 59 و کلاس دو نیز N2= 61، با توجه به دایروی بودن سطح تصمیم مقادیر سطوح دو کلاس بترتیب برابر - با صرفنظر کردن از ضرایب خطرپذیری، نقطه ستاره به کلاس دو اختصاص می‌یابد4-7- طبقه‌بند Naive بیزبرای تخمین pdf در یک فضای ویژگی l بعدی به N l نقطه آموزش نیاز داریم. برای حل مشکل، می‌توانیم هر ویژگی در بردار ویژگی را مستقل فرض نماییمبا این فرض می‌توان نوشت

اسلاید 48: مسئله اکنون به تخمین l تابع‌چگالی‌احتمال تبدیل می‌شود و برای هر کلاس تعداد l × N نقطه داده کفایت می‌کند. این تخمین به Naive بیز معروف استطبقه‌بند Naive بیز نمونه نامعین را به کلاس m بصورت زیر اختصاص می‌دهدمثال: بردارویژگی را با مقادیر باینری ویژگی، ، درنظر بگیرید. همچنین، احتمال‌های شرطی کلاس‌ها بترتیب و می‌باشند. برای یک x با مقدار معلوم طبق قاعده بیز و نسبت شباهت با حداقل خطای احتمال داریمبا اعمال فرض استقلال آماری (جهت سادگی تخمین احتمال) خواهیم داشت

اسلاید 49: با گرفتن لگاریتم از نسبت شباهت (رسیدن به یک تابع تمایز خطی) باتوجه به توابع احتمال شرطی داریمبسادگی می‌توان نوشتتعداد تخمین‌های لازم در اینحالت برابر 2l جهت محاسبه pi و qi می‌باشدویژگی‌های‌باینری در تشخیص‌پزشکی با اختصاص مقدار 1 به حالت نرمال و 0 به مورد غیر نرمال کاربرد دارد

اسلاید 50: 5- قاعده نزدیکترین همسایهدر ابتدا قاعده نزدیکترین همسایه برای یک بردار ویژگی x و یک اندازه فاصله بشرح زیر بیان می‌شود - برای N بردار آموزش، k همسایه نزدیکتر باتوجه به برچسب کلاسها تعیین می‌شوند. مقدار k برای مسئله دو کلاسه فرد و برای M کلاسه نبایستی مضرب صحیح از تعداد کلاس باشد. - در بین این k نمونه، تعداد بردارهای ki متعلق به ωi را تعیین می‌کنیم. بوضوح - بردار x به کلاس ωi با بیشترین ki اختصاص می‌یابداندازه‌های فاصله نظیر اقلیدسی، ماهالانوبیس، قدرمطلق فاصله یا نرم یک (L1)، و ...برای k = 1 ساده‌ترین نوع الگوریتم بنام قاعده نزدیکترین همسایه (NN)، بعبارتی دیگر یک بردار ورودی ناشناس به برچسب کلاس نزدیکترین همسایه اختصاص می‌یابدبرای تعداد داده آموزشی کافی، این روش ساده دارای عملکرد مناسب می‌باشد و برای میل N به مقدار بینهایت، میزان خطای طبقه‌بندی برای NN به مقادیر زیر محدود می‌شود

اسلاید 51: در رابطه بالا PB خطای بهینه بیز می‌باشد. برای حالت دو کلاسه و طبقه‌بند kNNبرای مقادیر مختلف k و مقدار N بزرگ، قاعده kNN به طبقه‌بند بیزین میل می‌کندملاحظاتوجود پیچیدگی برای جستجوی نزدیکترین همسایه‌ها در تکنیک kNN، میزان محاسبات متناسب با kN برای مجموعه‌داده با N کوچک، کارآیی روش kNN کاهش می‌یابد. استفاده از روش‌های ویرایش، تعریف فاصله سازگار با داده، و شیوه‌های دیگر جهت افزایش کارآییبرای k = 1 در قاعده‌نزدیکترین‌همسایه، بردارهای‌ویژگی‌آموزش فضای‌ویژگی l بعدی را به N ناحیه Ri معروف به سنگ‌فرش‌های‌ورونی (Voronoi tessellation) بصورت زیر تقسیم می‌کنند

اسلاید 52: Ri شامل تمام نقاطی در فضا است که به xi نسبت به نقاط دیگر از مجموعه آموزش برحسب فاصله d نزدیکتر می‌باشند6- شبکه‌های بیزیندر ابتدا با قاعده زنجیره‌ای احتمال برای ویژگیهای شروع می‌کنیممی‌توان رابطه بالا را بصورت زیر نوشتبرای l = 6 داریم

اسلاید 53: بصورت گرافیکی، گره‌ها مبین هر ویژگی بوده و والدین هر ویژگی، xi، اعضای Ai می‌باشند که با خطوط مستقیم به گره ویژگی ارتباط می‌یابندبا قاعده زنجیره‌ای، تخمین pdf با ابعاد کمتری صورت می‌گیرد و پیچیدگی محاسباتی کاهش می‌یابدروابط بالا، مبتنی‌بر فرضیات استقلال ویژگی‌ها نوشته شده‌اند. بدیهی‌است می‌توان گرافهای دیگری نیز برای تخمین توابع چگالی احتمال بالا رسم نمود. طبقه‌بند Naive بیز حالت خاصی از شبکه بیزین با Ai= Ø می‌باشدشبکه بیزین یک گراف مستقیم مارپیچ (DAG) با رئوس مرتبط با هر ویژگی است

اسلاید 54: تعیین کامل شبکه بیزین به دانستهای زیر نیاز دارد - احتمال گره‌های ریشه (گره‌هایی که والدین نداشته باشند) - احتمالهای شرطی گره‌های غیر ریشه - محاسبه احتمال‌های توام با ضرب تمام احتمال‌های‌شرطی در احتمال‌های‌پیشین گره‌های ریشه

اسلاید 55: در ابتدا قاعده نزدیکترین همسایه برای یک بردار ویژگی x و یک اندازه فاصله بشرح زیر بیان می‌شود5- قاعده نزدیکترین همسایهدر ابتدا قاعده نزدیکترین همسایه برای یک بردار ویژگی x و یک اندازه فاصله بشرح زیر بیان می‌شود - برای N بردار آموزش، k همسایه نزدیکتر باتوجه به برچسب کلاسها تعیین می‌شوند. مقدار k برای مسئله دو کلاسه فرد و برای M کلاسه نبایستی مضرب صحیح از تعداد کلاس باشد. - در بین این k نمونه، تعداد بردارهای ki متعلق به ωi را تعیین می‌کنیم. بوضوح - بردار x به کلاس ωi با بیشترین ki اختصاص می‌یابد