از اونجایی که دیگه بدجور فرو رفتم تو نقش معلمی و اینا، میخوام یکی از الگوریتمهای جالب آمار و احتمالی رو بهتون معرفی کنم. این الگوریتم خیلی جاها به درد میخوره و واقعا چیز جالبیه و نتایج جالبی هم میده.
فرض کنید یه تعداد نقطه داریم که میخوایم دستهبندیشون کنیم.مثل نقاط این عکس:
همینجوری که به این تصویر نگاه کنید، میبینید که این نقطهها احتمالا تو دو تا دسته قرار میگیرن. اما خب، ما اصولا وقتی با دادهها سر و کار داریم، باید فرض «چشم داشتن» و «نگاه کردن» رو بذاریم کنار و با روابط ریاضی به نتیجه برسیم.
حالا چی کار کنیم؟ فعلا بیاید فرض کنیم از غیب به ما الهام شده که تعداد این دستهها دو تاست.(چون همون طور که گفتم، چشم نداریم و نمیدونیم دستهها چند تاست!)
یه معیار خوب برای این که دستهبندی رو انجام بدیم، یعنی بگیم هر نقطه به گدوم دسته تعلق داره، اینه که مرکز هر دسته رو در نظر بگیریم، بعد فاصلهی هر نقطه رو با مرکز هر دسته به دست بیاریم، بعد با هر مرکزی که فاصلهش کمتر بود، بگیم نقطهمون به اون دسته تعلق داره. اما ما الان نمیدونیم مرکز دستههامون کجاست! به شکل عجیبی این یکی از غیب بهمون الهام نشده:))
پس بریم سراغ الگوریتممون!
اساس این الگوریتم اینه که فرض کنیم یه چیزایی رو داریم، بعد برای باقی چیزاها تصمیم بگیریم. بعد برگردیم ببینیم تصمیمهایی که گرفتیم، میتونه فرض اولیهمون رو بهبود بده یا نه و اگه بهبود میداد، فرض اولیه رو عوض کنیم و دوباره تصمیم بگیریم و اون قدر این کار رو (یعنی فرض کردن و تصمیم گرفتن رو) تکرار کنیم که دیگه به یه فرض و تصمیم ثابتی برسیم. الان مثال رو که توضیح بدم، متوجه میشید:))
توی این مثال، ما همونطور که گفتم، مرکز دستهها رو نداریم. پس همین جری الکی یه فرضی راجع به مرکز دستهها میکنیم و میریم جلو تا بعدش ببینیم چی میشه!
بیاید دو تا نقطهی کاملا تصادفی A و B رو در نظر بگیریم و فرض کنیم مراکز این دو تا دسته هستن. این میشه فرض اولیهمون و با احتمال ۱۰۰ درصد اصلا فرض خوبی نیست؛ دو تا نقطه رو از صفحه انتخاب کردیم و اسمشون رو گذاشتیم مرکز، در حالی که ممکنه اصلا یه جاهای پرتی باشن! مثل این عکس:
حالا میخوایم بر مبنای این فرض اولیه، تصمیم بگیریم که هر کدوم از نقاطی که داشتیم تو کدوم دسته هستن. دستهی a یا دستهی b . پس میایم فاصلهی تکتک نقاط رو از این دو تا نقطهی A و B حساب میکنیم و بر اساس این فاصله، هر کدوم رو به یه دستهای نسبت میدیم. خب! ما اینجا با کمال اعتماد به نفس یه دستهبندی غلط رو انجام دادیم!
حالا که تصمیممون رو گرفتیم و یه بار دستهبندی رو انجام دادیم، بیاید برگردیم سراغ تعریف مرکز. وقتی میگیم A مرکز دستهی a هست، منظورمون چیه؟ منظورمون اینه که A یه جورایی میانگین همهی نقاطی هست که تو دستهی a قرار دارن. حالا ما چی داریم؟ توی هر دسته،یه سری نقطه و یه مرکز به اسم A که فقط اسمش مرکزه و ممکنه حتی اون سر دنیا باشه! پس وقتشه که فرض اولیهمون (یعنی مرکز بودن A) رو اصلاح کنیم!
برای اصلاحش چی کار کنیم خوبه؟ کافیه مرکز قبلی رو بذاریم کنار و حالا که دستهی a رو به دست آوردیم، از نقاطی که تو دستهی A داریم، میانگین بگیریم تا حالا که دستههامون به وضوح غلط هستن، حداقل مرکزاشون درست باشن! اینجوری:
توی این عکس جدید، ما به دستهبندیمون دست نزدیم. فقط اومدیم مرکز همون دستههایی که خودمون پیدا کردهبودیم رو حساب کردیم. این دو تا نقطهی A و B حال دیگه واقعا مرکز اون دو تا دستهی غلطمون هستن. همونطور که گفتم، درسته که دستهبندیمون غلطه، ولی حالا دیگه حداقل مرکز دستههامون درسته و نقطههایی که به عنوان مرکز انتخاب کردیم، خیلی هم پرت نیستن.
حالا یه فرض جدید یا به عبارتی، «به روز شده» داریم.و بر اساس این فرض باید دوباره تصمیم بگیریم. در واقع دو تا مرکز جدید داریم و حالا باید دستهی b وa ای که تو دور قبلی به دست آوردهبودیم رو بذاریم کنار و یه دور دیگه نقاطمون رو دستهبندی کنیم. یعنی برگشتیم سر خونهی اول! یه سری نقطه داریم، با دو تا نقطهای که حدس میزنیم مرکز باشن. اینجوری:
حالا دوباره همون کار قبلی رو تکرار میکنیم و فاصلهی هر نقطهی نامشخص رو تا A و B حساب میکنیم و میبینیم به کدوم نزدیکتره. نتیجه میشه این:
بعد از این مرحله دوباره یه دستهبندی جدید داریم! حالا باز باید بریم مرکز این دستههای جدید رو پیدا کنیم.
دیدید چی شد؟ با همین چند تا مرحله رسیدیم به اون چیزی که میخواستیم! با یه دونه حدس غلط شروع کردیم و حالا رسیدیم به جای درست! هم دستهبندیمون درست انجام شده، هم مرکز هر دسته به دست اومده!
اما حالا باز ی سوالی هست. ما چشم داریم و میبینیم که به جای درست رسیدیم، اما به زبون ریاضی چطور به این الگوریتم بگیم که دیگه باید متوقف بشه و هی دوباره فاصله حساب نکنه؟
سادهس. بهش میگیم هر بار که مرکز دستهها رو مشخص کردی، مختصات اونا رو یادت نگهدار. و اون قدر این مراحل دستهبندی و تعیین مرکز رو ادامه بده، تا تو دوتا مرحلهی پشت سر هم، مختصات مرکز عوض نشه. اگه بخوام سادهتر بگم... میشه این جوری: وقتی به جای درست رسیدی و الگوریتمت جواب داد، چون فقط یه جواب درست وجود داره، دیگه نتیجه قرار نیست عوض بشه. پس اون قدر ادامه بده، تا به جایی برسی که دیگه مرکزها جابهجا نشن. به همین سادگی، به همین خوشمزگی!
***
این یکی از سادهترین مثالهای الگوریتم EM بود که به راحتی و با کشیدن چند تا نقطه رو کاغذ و استفاده از خطکش میتونید امتحانش کنید! اما خب خیلی جاهای دیگه هم مورد استفاده قرار میگیره و ابزار قویای محسوب میشه و بعضی مسائل به شدت پیچیده که روش مستقیمی برای حل کردنشون نیست رو میشه با همین الگوریتم حل کرد.
یا مثلا تو همین مسئله تعریف دستهها میتونه عوض بشه (مثلا یه توزیع آماری باشه) یا فاصله یه معنی دیگه داشتهباشه که خب اینجا گفتنش ضرورتی نداره.
اگه واقعا چند تا دسته توی نقاطتون داشتهباشید و تعداد دستهها رو درست در نظر گرفتهباشید، بالاخره بعد از چند بار اجرای الگوریتم، دستهها و مرکزهاشون رو پیدا میکنید.
اما اگه دستهبندیای وجود نداشتهباشه چی؟ مثلا فرض کنید نقطهای وجود داره که فاصلهش از مراکزی که تعیین کردیم به یه اندازه باشه و هر بار که الگوریتم رو اجرا میکنیم، شانسی توی یه دسته قرار بگیره. این نقطه نمیذاره الگوریتم ما هیچ وقت متوقف بشه. چون هر بار میره توی یه دسته و باعث میشه مرکزی که انتخاب کردیم تو مرحلهی بعد جابهجا بشه.
برای حل این مشکل میشه که بررسی کنیم و اگه دیدیم فقط یکی دو تا از این نقطهها داریم، اونا رو نادیده بگیریم و در واقع فرض کنیم با خطای اندازهگیری ایجاد شدن. اما اگه تعداد اینا خیلی زیاد بود، به این معنیه که امکان دستهبندی وجود نداره یا تعداد مرکزها رو درست انتخاب نکردیم. یعنی مثلا ما سه تا دسته داشتیم در اصل، ولی فرض کردیم دو تا دسته داریم، حالا نقاط دستهی سوم آواره شدن و هر بار خودشون رو میچسبونن به یه دسته و نمیذارن ما هم به دستهبندیمون برسیم!
راه حل چیه؟
یادتونه گفتم فرض کنیم از غیب بهمون الهام شده که ۲ تا دسته داریم؟ واقعیت اینه که هیچ وقت از غیب بهمون الهام نمیشه که چند تا دستهداریم:)) معمولا از روی دادهها میشه یه حدسایی زد. مثلا اگه این نقطهها یه سری آدم سالم یا بیمار باشن که با مدلسازی ما تبدیل به این نمودار شدهباشن، به وضوح دو تا دسته داریم: سالم و بیمار!
اما اگه دادههامون هیچ اطلاعاتی به ما ندن چی؟
باز هم راههایی هست. راههای ساده و پیچیده! سادهترین راه میدونید چیه؟ این که چندین بار الگوریتم رو اجرا کنیم. یعنی اول فرض کنیم دو تا دسته داریم، بعد فرض کنیم ۳ تا دسته داریم، بعد فرض کنیم ۴ تا دسته داریم و اون قدر ادامه بدیم تا به یه نتیجهی خوب برسیم که این «نتیجهی خوب»، خودش تعریف داره و قابل سنجیدن هست. مثلا اگه ما هی تعداد دستهها رو زیاد کنیم، ممکنه به یه جایی برسیم که بگیم به تعداد نقاطمون دسته داریم و هر نقطه خودش مرکز یه دستهس! به نظر ممکنه درست بیاد، ولی به چه دردی میخوره خب؟
***
خب! امیدوارم تونسته باشم خوب توضیح بدم. اگه کنجکاوتر بودین، میتونید سوال هم بپرسید:))
+ آقاااا... من این پست رو ۲۷ تیر نوشتهبودم! یعنی ببینید تنبلی چه میکنه با آدم:))
+ و البته یه نیم ساعتی هم با صندوق بیان درگیر بودم الان و آخرم عکسا رو یه جا دیگه آپلود کردم.
- سه شنبه ۱۵ مهر ۹۹
- ادامه مطلب
