آیا مساله خوشه بندی یک مساله خوش تعریف است؟

وقتی برای اولین بار در یکی از بانک های ایران مجموعه ای داده به من دادند و ازم خواستند که مشتری ها را خوشه بندی(clustering) کنم هیجان زده بودم چون که برای اولین بار می توانستم یادگیری ماشین را در عمل استفاده کنم. اما به سرعت متوجه مشکلات زیادی شدم. اول آنکه برخلاف داده هایی که شما معمولا در پروژه های دانشگاهی یا پژوهشی از آن استفاده می کنید داده های واقعی تمیز و شیک نیستند. بسیاری از مقادیر وجود ندارد(مثلا سن یا محل تولد بعضی افراد را نداریم) علاوه بر آن باید با داده ها با احتیاط برخورد کرد چون ممکن است غلط هم باشند. حجم داده ها به طرز وحشتناکی بزرگ هستند و گاهی هم از کمبود داده رنج می بردیم. اما علاوه بر آن مشکلات تکنیکی هم وجود داشتند. اولین سوال این بود که چند خوشه؟ چند گروه از مشتریان قابل تفکیک هستند؟ سریعا به ذهنم رسید که الگوریتم های خوشه بندی ای وجود دارند که خودشان تعداد خوشه ها را تشخیص می دهند. اما دستکاری کردن داده ها مثلا اسکیل کردن آنها (تقسیم داده ها بر بزرگترین مقدار برای قرار دادنشان در بازه صفر و یک. کاری که در یادگیری ماشین برای مثلا استخراج جهت های داده بسیار معمول است) باعث می شد تعداد خوشه ها تغییر کند! الگوریتم های مختلف خوشه بندی نتایج متفاوت و بعضا متضادی به من می دادند. کاملا کلافه و سر درگم شده بودم. چه اتفاقی دارد می افتد؟ احساس می کردم هر آنچه در دانشگاه یاد گرفته ام به من کمکی نکرده است و مستاصل مانده ام با داده هایی که هیچ کس دیگری قبل از من آنها را ندیده است بنابراین جستجو در اینترنت هم به من کمکی نمیکرد. بالاخره روزی از خودم پرسیدم که اصلا آیا خوشه بندی یک مساله خوش تعریف است؟ خوش تعریف از لحاظ ریاضی به این معناست که بتوان جوابهایی قطعی و نهایی با استفاده از مجموعه ای ورودی و پیش فرض های مشخص تعریف کرد. در چنین مواقعی ممکن است با خود بگویید: ولش کن! خودت را بیشتر خسته نکن سعی کن یک روش را که حدودی کار می کند ارایه بدهی حقوقت را بگیری و حتی براحتی ترفیع بگیری. اما از طرفی دوست داری بدانی واقعا مشکل قضیه کجاست. اینجاست که باید انتخاب کنی قرص آبی را انتخاب کنی بر گردی سر کارت و بقیه کدهایت را بنویسی یا قرص قرمز را انتخاب کنی و بدانی داستان پشت صحنه چیست. این جا جایی بود که من قرص قرمز را انتخاب کردم تا وارد دنیای عجیبی شوم که فلسفه ی پنهان پیش فرض های ریاضی روش های هوش مصنوعی بود! ورود به سرزمین عجایب!قرص قرمز یا آبی؟ غیر ممکن بودن خوشه بندیمقاله ای از یک ریاضیدان به نام کلاینبرگ یافتم که ادعا می کرد به لحاظ ریاضی ثابت کرده است که خوشه بندی یک مساله غیر قابل حل است. در این جا سعی میکنم نسخه ساده ای از آن اثبات را بیاورم(متن زیر ترجمه ای با دخل و تصرف از این وبلاگ است). کلاینبرگ می گوید که یک الگوریتم خوشه بندی ایده آل باید سه ویژگی داشته باشد. این ویژگی ها با شهود ما درمورد خوشه بندی مطابقت دارند.1- غیر حساس به مقیاس(scale-invariance): یک الگوریتم خوشه بندی ایده آل اگر داده ها را در همه جهت ها به یک اندازه کوچک یا بزرگ کنیم(با ضرب کردن ساده در کل داده ها)، باید نتایج یکسانی بدهد.اگر همه داده ها را در یک عدد ضرب کنیم باز هم باید به همان خوشه ها برسیم2- سازگاری(Consistency): اگر ما داده ها بکشیم طوری که فاصله بین خوشه ها بیشتر و درون خوشه ها کمتر شود باز هم نتیجه الگوریتم خوشه بندی نباید تغییر کند.اگر فاصله بین نقاط در یک خوشه را با یک فاکتور کاهش و بین خوشه ها را با افزایش دهیم باز هم باید به یک خوشه بندی برسیم3- غنی بودن(Richness): این ویژگی به ما می گوید الگوریتم خوشه بندی باید قادر باشد که خود، تعداد خوشه ها را استخراج کند. به عبارتی اگر N داده داشته باشیم و از قبل چیزی در مورد فاصله های بین آن ها به ما نگفته باشند باید الگوریتم قادر باشد به صورت اتوماتیک تعداد خوشه ها را تشخیص دهد.الگوریتم خوشه بندی باید قادر باشد خود تعداد خوشه ها را استخراج کند کلاینبرگ نشان داد همه الگوریتم های خوشه بندی حداکثر می توانند دو ویژگی را داشته باشند و داشتن سومی آن ها را دچار تناقض می کند. جزییات اثبات پیچیده و طولانی است اما می توان را به صورت زیر ساده تر کرد. برای این هدف کلاینبرگ می گوید که الگوریتم خوشه بندی تک اتصاله (single linkage clustering) را در نظر بگیرید. این الگوریتم اینگونه آغاز می شود که هر نقطه ای را یک خوشه در نظر میگیرد. سپس شروع می کند به یافتن نزدیک ترین نقاط به هم (بر اساس معیار فاصله ای که تعریف شده است که معمولا فاصله اقلیدسی است) و سپس آن ها را با هم ادغام می کند. این چیزی بسیار شبیه به خوشه بندی سلسله مراتبی است که در شکل زیر می بینید.خوشه بندی سلسله مراتبی و تصمیم برای توقف خوشه بندی در هر مرحله اما کجا باید متوقف شد؟ اینجاست که روش های مختلف ظاهر می شوند و هر کدام تنها می توانند دو شرط را ارضا کنند1- توقف بر اساس تعداد خوشه: اگر قرار را بر این بگذاریم که به k خوشه که از قبل مشخص کرده ایم، برسیم می توانیم همانجا متوقف شویم. این شرط توقف ویژگی سوم را به وضوح نقض می کند چون چیزی به اسم "تعداد خوشه های طبیعی" را نمی تواند تشخیص دهد. اینجا دقیقا مثل حالت خوشه بندی مشتریان بانک بود که مثلا می توانستیم آن ها را 10 دسته در نظر بگیریم. اما مدیر سریع می گفت چرا 10 و چرا 11 نه؟؟ اما دو ویژگی دیگر برقرار هستند. می توانید از روی شکل های ویژگی یک و دو این موضوع را بررسی کنید. مشکل برای یک و دو زمانی پیش می آید که شروع به ادغام یا از هم جدا کردن کنیم(حالت های بعدی).اگر k=2 بگیریم نمی توانیم سه خوشه را تشخیص دهیم حتی اگر "واقعا" سه خوشه وجود داشته باشد.2- توقف بر اساس فاصله: خوشه بندی را متوقف کن زمانی که فاصله دو نزدیکترین خوشه بزرگتر از یک مقدار از پیش تعریف شده (مثلا r) باشد.این روش شرط غنی بودن را ارضا می کند. ما همیشه می توانیم r را طوری دستکاری کنیم که تعداد خوشه های متفاوتی بدست آوریم. اگر r را برابر با کوچکترین فاصله بین هر دو نقطه در نظر بگیریم تعداد خوشه ها برابر با تعداد نقطه هاست و اگر r را بی نهایت بگیریم همه داده ها یک خوشه می شوند و مقادیر r بین این دو سر طیف می توانند هر تعداد خوشه ای را ایجاد کنند. پس اگر r را بدانیم الگوریتم به صورت خودکار تعداد خوشه ها را تشخیص می دهد.این الگوریتم همچنین شرط سازگاری را حفظ می کند. اگر ما داده ها را بکشیم طوری که فاصله بین خوشه ها بیشتر شود حداقل فاصله را بزرگتر از r نگه می دارد. همچنین اگر داده ها را بکشیم طوری که فاصله بین نقاط هر خوشه کوچکتر شود بیشترین فاصله را همچنان کمتر از r نگه می دارد.اما شرط اول نقض می شود. اگر ما داده ها را با یک عدد به اندازه کافی بزرگ ضرب کنیم آنگاه هر نقطه ای به یک خوشه جداگانه تعلق پیدا می کند.(تعداد خوشه ها و نقاط یکی می شوند) از طرفی اگر داده ها را در یک عدد بسیار نزدیک به صفر ضرب کنیم فاصله ها همه از r کوچکتر شده و همه در یک خوشه قرار می گیرند!مقایس بندی با ضرب داده ها در یک عدد کوچک همه را در یک خوشه جمه می کند(سمت چپ) و ضرب در یک عدد بزرگ آن ها در خوشه های متفاوت قرار می دهد(سمت راست) 3- توقف بر اساس مقایس e: زمانی خوشه بندی را متوقف کن که فاصله دو نزدیکترین خوشه بزرگتر از کسری از بیشترین فاصله بین هر دو نقطه در مجموعه داده هاست. این دقیقا شبیه به روش قبل است با این تفاوت که r=e * delta است که delta بیشترین فاصله بین هر دو نقطه است. این طبیعی ترین راهکار برای حل مشکل ما با سومین ویژگی است. زمانی که داده ها را در یک عدد کوچک یا بزرگ ضرب میکردیم. اما این راهکار مشکل را حل می کند؟ خیر.با داشتن این معیار ویژگی های غیر حساس بودن به مقیاس و غنی بودن برطرف می شود. اما ویژگی دوم از دست می رود. برای این که متوجه این موضوع بشوید شکل زیر را در نظر بگیرید. اگر ما تبدیل زیر را انجام دهیم که بر اساس آن خوشه سبز رنگ از دو خوشه دیگر فاصله بگیرید(بر اساس ویژگی دوم می توانیم این کار را بکنیم). این باعث می شود بیشترین فاصله بیین نقاط یعنی delta بزرگتر شود. همین باعث می شود دو خوشه قرمز و آبی در هم ادغام شوند!خوشه هایی که فاصله کمتر از r دارند در هم ادغام می شوند. با افزایش فاصله خوشه سبز دلتا بزرگ شده و دو خوشه قرمز و آبی باید در هم ادغام شوند. چه کنیم؟نتیجه گیری کلاینبرگ روشن است: ما باید بطور کلی انتظارات خود را از خوشه بندی پایین بیاوریم و قبول کنیم که این مساله تعریف درستی ندارد! مصالحه در مورد این که کدام شرط را نقض کنیم بستگی به کاربرد دارد. مثلا مورد آخر بیشتر قابل سوال کردن است.آیا ویژگی دوم همیشه منطقی است؟ بسیاری از روش ها مانند kmeans شرط غنی بود را به کلی کنار می گذارند و از قبل تعداد خوشه ها را مشخص می کنند. این قضیه حتی می تواند سوالات عمیق تری در مورد ذهن و اینکه ما چگونه جهان را دسته بندی می کنیم هم ادامه پیدا کند که در این مجال نمی گنجد.