خوشه بندی قابل تفسیر: یک رویکرد بهینه سازی

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

روی یک دست نوشته کار می کنید؟

از رایج ترین اشتباهات اجتناب کنید و دستنوشته خود را برای سردبیران مجلات آماده کنید.

مقدمه

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

برخلاف طبقه‌بندی تحت نظارت، هیچ برچسب کلاسی وجود ندارد و بنابراین هیچ معیار طبیعی برای دقت وجود ندارد. در عوض، هدف این است که اشیاء را به خوشه‌ها فقط بر اساس ویژگی‌های قابل مشاهده آنها گروه بندی کنیم، به طوری که هر خوشه شامل اشیایی با ویژگی‌های مشابه باشد و خوشه‌های مختلف دارای ویژگی‌های متمایز باشند. رویکردهای متعددی برای تولید این خوشه ها وجود داشته است. روش های پارتیشنی مانند K-means (MacQueen 1967) یک پارتیشن واحد از داده ها را به تعداد ثابتی از خوشه ها ارائه می دهند. این روش ها با روش های اولیه سازی جدید در دهه های اخیر بهبود یافته اند (Arthur and Vassilvitskii 2007). روش های سلسله مراتبی یک سری پارتیشن تو در تو را بر اساس متریک فاصله تولید می کنند (Sneath et al. 1973). سایر روش‌های پیچیده‌تر شامل خوشه‌بندی مبتنی بر مدل (هستی و همکاران 2009) و خوشه‌بندی مبتنی بر چگالی (Ester et al. 1996) هستند که بهتر می‌توانند خوشه‌هایی با شکل نامنظم یا چگالی متفاوت را ثبت کنند.

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

در حالی که اهمیت تفسیرپذیری خوشه به خوبی درک شده است، موفقیت محدودی در پرداختن به این موضوع حاصل شده است (دوشی-ولز و کیم 2017). هیچ یک از الگوریتم‌های خوشه‌بندی که در بالا توضیح داده شد با هدف تفسیرپذیری در فضای ویژگی اصلی ساخته نشدند. بنابراین آنها به یک مرحله پس پردازش برای ترکیب معانی خوشه نیاز دارند. مفهوم بازنمایی خوشه ای توسط دوران و اودل (1974) معرفی شد و متعاقباً توسط دیدی و سیمون (1976) و استپ و میچالسکی (1986) مورد مطالعه قرار گرفت. نمایش یک خوشه از نقاط توسط مرکز آن در برنامه های مختلف محبوب بوده است (Radev et al. 2004). هنگامی که خوشه ها فشرده یا همسانگرد هستند، این کار به خوبی کار می کند، اما زمانی که خوشه ها دراز یا غیر همسانگرد هستند شکست می خورد (Jain et al. 1999). این خوشه ها را می توان با محاسبه معیارهای اضافی، مانند واریانس در هر بعد، بهتر مشخص کرد. با این حال، این تعداد آمار خلاصه مورد استفاده برای هر خوشه را افزایش می دهد و بار زیادی در تفسیر ایجاد می کند، به خصوص زمانی که تعداد ویژگی ها زیاد شود. یکی دیگر از رویکردهای رایج، تجسم خوشه ها بر روی یک نمودار دو بعدی با استفاده از پیش بینی های تحلیل مؤلفه اصلی (PCA) است (Jolliffe 2011؛ Rao 1964). با این حال، در کاهش ابعاد فضای ویژگی، PCA رابطه بین خوشه ها و متغیرهای اصلی را پنهان می کند.

روش‌های یادگیری تحت نظارت مبتنی بر درخت، مانند CART (Breiman et al. 1984)، برای مسائلی که تفسیرپذیری را در اولویت قرار می‌دهند، مناسب هستند، زیرا تقسیم‌بندی ویژگی‌ها و مسیرهای تصمیم‌گیری آنها بینشی نسبت به ویژگی‌های متمایز بین اعضا در هر برگ ارائه می‌دهد. اکثر الگوریتم‌های پارتیشن‌بندی بازگشتی درخت‌ها را به روشی از بالا به پایین و حریصانه تولید می‌کنند، به این معنی که هر تقسیم به‌صورت مجزا و بدون در نظر گرفتن تأثیر آن بر شکاف‌های بعدی در درخت انتخاب می‌شود. برتسیماس و دان (2017، 2019) الگوریتم جدیدی را پیشنهاد کرده‌اند که از تکنیک‌های مدرن بهینه‌سازی اعداد صحیح مختلط (MIO) برای تشکیل کل درخت تصمیم در یک مرحله استفاده می‌کند و اجازه می‌دهد هر تقسیم با دانش کامل از همه تقسیم‌های دیگر تعیین شود. الگوریتم درخت‌های طبقه‌بندی بهینه (OCT) ساخت درخت‌های تصمیم‌گیری را برای طبقه‌بندی و رگرسیون امکان‌پذیر می‌سازد که عملکرد قابل مقایسه با روش‌های پیشرفته مانند جنگل‌های تصادفی و درخت‌های تقویت‌شده گرادیان را بدون به خطر انداختن تفسیرپذیری ارائه شده توسط یک درخت واحد دارند.

یک رویکرد ترکیبی کلی می تواند با اجرای یک روش خوشه بندی جزئی یا سلسله مراتبی و استفاده از تکالیف حاصل به عنوان برچسب های کلاس ، چنین روش هایی را به دست آورد. سپس داده ها می توانند با استفاده از یک درخت طبقه بندی مناسب باشند ، که در آن به هر برگ بر اساس رایج ترین تکلیف مشاهدات در آن برگ ، برچسب خوشه ای داده می شود و مسیرهای تصمیم گیری منتهی به برگهای هر خوشه ای بینش در مورد ویژگی های تمایز دهنده (Jain etآل. 1999). هنکوک و همکاران.(2003) از درختان تصمیم گیری برای تفسیر و تصحیح نتایج خوشه بندی سلسله مراتبی برای دمای سطح جهانی دریا استفاده کنید. در حالی که این درختان مشخصات صریح از ویژگی های خوشه ای را ارائه می دهند ، این روش ها شامل یک فرآیند دو مرحله ای برای ساخت خوشه ها و متعاقباً مشخص کردن ویژگی های تمایز آنها است. بنابراین ، مکانیسم اصلی خوشه بندی از یک معماری متفاوت در مقایسه با درخت تصمیم گیری استفاده می کند که ممکن است با شکاف های ویژگی یک متغیره ضبط شود.< SPAN> یک رویکرد کلی ترکیبی می تواند با اجرای یک روش خوشه بندی جزئی یا سلسله مراتبی و استفاده از تکالیف حاصل به عنوان برچسب های کلاس ، چنین روش هایی را به دست آورد. سپس داده ها می توانند با استفاده از یک درخت طبقه بندی مناسب باشند ، که در آن به هر برگ بر اساس رایج ترین تکلیف مشاهدات در آن برگ ، برچسب خوشه ای داده می شود و مسیرهای تصمیم گیری منتهی به برگهای هر خوشه ای بینش در مورد ویژگی های تمایز دهنده (Jain etآل. 1999). هنکوک و همکاران.(2003) از درختان تصمیم گیری برای تفسیر و تصحیح نتایج خوشه بندی سلسله مراتبی برای دمای سطح جهانی دریا استفاده کنید. در حالی که این درختان مشخصات صریح از ویژگی های خوشه ای را ارائه می دهند ، این روش ها شامل یک فرآیند دو مرحله ای برای ساخت خوشه ها و متعاقباً مشخص کردن ویژگی های تمایز آنها است. بنابراین ، مکانیسم اصلی خوشه بندی از یک معماری متفاوت در مقایسه با درخت تصمیم گیری استفاده می کند که ممکن است با شکاف ویژگی های یک متغیره ضبط شود. یک رویکرد ترکیبی عمومی می تواند با اجرای یک روش خوشه بندی جزئی یا سلسله مراتبی و استفاده از تکالیف حاصل به عنوان کلاس ، چنین روش هایی را به کار گیرد. برچسب ها. سپس داده ها می توانند با استفاده از یک درخت طبقه بندی مناسب باشند ، که در آن به هر برگ بر اساس رایج ترین تکلیف مشاهدات در آن برگ ، برچسب خوشه ای داده می شود و مسیرهای تصمیم گیری منتهی به برگهای هر خوشه ای بینش در مورد ویژگی های تمایز دهنده (Jain etآل. 1999). هنکوک و همکاران.(2003) از درختان تصمیم گیری برای تفسیر و تصحیح نتایج خوشه بندی سلسله مراتبی برای دمای سطح جهانی دریا استفاده کنید. در حالی که این درختان مشخصات صریح از ویژگی های خوشه ای را ارائه می دهند ، این روش ها شامل یک فرآیند دو مرحله ای برای ساخت خوشه ها و متعاقباً مشخص کردن ویژگی های تمایز آنها است. بنابراین ، مکانیسم اصلی خوشه بندی از یک معماری متفاوت در مقایسه با درخت تصمیم گیری استفاده می کند که ممکن است با شکاف های ویژگی یک متغیره ضبط شود.

چندین الگوریتم برای ساخت خوشه‌های قابل تفسیر پیشنهاد شده‌اند، که در آن تفسیرپذیری به جای اینکه به عنوان مرحله تحلیل بعدی در نظر گرفته شود، در طول ایجاد خوشه مورد توجه قرار می‌گیرد. چاونت و همکاران(1999) روشی را ارائه کرد که درختان خوشه‌بندی دوتایی را که با تغییر شکل جدیدی از فضای ویژگی مشخص می‌شوند، می‌سازد. تلاش‌های بیشتر بر معیارهای جایگزین برای انتخاب ویژگی در تابع تبدیل و همچنین طرح‌های اجرای الگوریتمی جدید متمرکز شد (باساک و کریشناپورام 2005). در هر دوی این موارد، تبدیل فضای ویژگی که در این روش‌ها دخیل است، تأثیری بر قابلیت تفسیر دارد. محققان دیگر روش هایی را برای ساخت درخت های تصمیم در فضای ویژگی اصلی پیشنهاد کرده اند که بیشتر با هدف ما مطابقت دارد. لیو و همکاران(2000) ایده ترجمه یک مسئله خوشه بندی را به یک مسئله نظارت شده معرفی کرد که برای ساخت درخت تصمیم قابل قبول است. یک معیار خلوص اصلاح شده برای ارزیابی شکاف ها به گونه ای استفاده می شود که مناطق متراکم و همچنین مناطق پراکنده را شناسایی کند. با این حال، این روش نیاز به پیش پردازش اضافی از طریق معرفی داده های مصنوعی به منظور ایجاد یک تنظیم طبقه بندی باینری دارد. بلوکیل و همکاران(2000) همچنین یک چارچوب کلی القای درخت از بالا به پایین با قابلیت کاربرد در خوشه بندی ("درختان خوشه بندی پیش بینی") و همچنین سایر وظایف یادگیری تحت نظارت را پیشنهاد کرد. فرایمن و همکاران(2013) الگوریتم خوشه‌بندی دیگری به نام «خوشه‌بندی با استفاده از درختان باینری بدون نظارت» (CUBT) ایجاد کرد که تقسیم‌های حریصانه را برای بهینه‌سازی اندازه‌گیری ناهمگنی خوشه‌ای ایجاد می‌کند. اگرچه این الگوریتم‌ها به سمت هدف ساخت خوشه‌ها با استفاده مستقیم از درختان پیشرفت می‌کنند، هر دو از رویکرد تقسیم حریصانه استفاده می‌کنند و در انتخاب معیار اعتبارسنجی خوشه انعطاف‌پذیری ارائه نمی‌دهند.

نیاز به روش‌های یادگیری ماشینی دقیق و قابل تفسیر بدون شک وجود دارد و حتی از سوی سازمان‌های نظارتی مانند اتحادیه اروپا نیز ابراز می‌شود (گودمن و فلکسمن 2016). حتی اگر روش‌های مبتنی بر درخت معرفی شده‌اند، هیچ الگوریتم یادگیری بدون نظارت قابل تفسیر موجود نمی‌تواند فضای ویژگی را هم برای داده‌های عددی و هم برای داده‌های طبقه‌بندی به طور دقیق تقسیم کند.

مشارکت ها

با انگیزه محدودیت‌های راه‌حل‌های موجود برای خوشه‌بندی قابل تفسیر، ما یک روش یادگیری بدون نظارت مبتنی بر درخت را توسعه می‌دهیم که از تکنیک‌های بهینه‌سازی سنتی و یادگیری ماشین برای به دست آوردن خوشه‌های قابل تفسیر با عملکرد قابل مقایسه یا برتر در مقایسه با الگوریتم‌های موجود استفاده می‌کند. کمک های ما به شرح زیر است:

ما یک فرمول MIO از مسئله یادگیری بدون نظارت را ارائه می‌کنیم که منجر به ایجاد درخت‌های خوشه‌بندی بهینه در سطح جهانی می‌شود و الگوریتم جدید ما را برای خوشه‌بندی تفسیرپذیر از طریق درختان بهینه (ICOT) تحریک می‌کند. روش ما بر اساس الگوریتم OCT است و آن را به تنظیمات بدون نظارت گسترش می دهد. در ICOT، تفسیرپذیری در طول ایجاد خوشه به جای اینکه به عنوان یک مرحله تجزیه و تحلیل بعدی در نظر گرفته شود، مورد توجه قرار می گیرد.

ما پیاده‌سازی روش خود را با یک رویکرد مختصات-نزولی تکراری ارائه می‌کنیم که به مشکلات بزرگ‌تر مقیاس می‌دهد و راه‌حل بهینه جهانی را به خوبی تقریب می‌کند. ما به طور گسترده از دو معیار اعتبار سنجی تثبیت شده، متریک Silhouette (Rousseeuw 1987) و Dunn Index (Dunn 1974)، به عنوان تابع هدف الگوریتم استفاده می کنیم. ما تکنیک‌های دیگری را پیشنهاد می‌کنیم که از اصول هندسی ایجاد خوشه برای بهبود کارایی الگوریتم استفاده می‌کند. علاوه بر این، ما اکتشافی‌های نمونه‌گیری را معرفی می‌کنیم که راه‌حل‌های سریع و با کیفیت بالا را در آزمایش‌های تجربی خود بازیابی می‌کنند و تجزیه و تحلیل پیچیدگی روش جستجوی محلی را برای یک تکرار از الگوریتم ارائه می‌دهند.

ما الگوریتم خود را به گونه ای توسعه می دهیم که تنظیم پیچیدگی درخت اضافی باشد. این با این واقعیت فعال می شود که توابع ضرر ما هم چگالی درون خوشه ای و هم جدایی بین خوشه ای را در نظر می گیرد. کاربر می تواند به صورت اختیاری الگوریتم را با انتخاب حداکثر عمق درخت و حداقل تعداد مشاهدات در هر خوشه تنظیم کند.

ما راه حلی را برای ادغام داده های عددی و مقوله ای مختلط پیشنهاد می کنیم. اندازه گیری فاصله وزن مجدد ما از تسلط یک نوع متغیر منفرد بر محاسبه فاصله جلوگیری می کند و به کاربران امکان می دهد به صورت اختیاری تعادل بین دو نوع متغیر کمکی را تنظیم کنند.

ما عملکرد روش خود را در برابر رویکردهای مختلف خوشه بندی در سراسر مجموعه داده های مصنوعی از مجموعه مشکلات خوشه بندی اساسی (FCPS) (Ultsch 2005) ارزیابی می کنیم که سطح متفاوتی از واریانس و فشرده سازی را ارائه می دهند. ما عملکرد برتر ICOT را در برابر یک روش یادگیری تحت نظارت دو مرحله ای در هر دو متریک شبح و شاخص Dunn نشان می دهیم و به ترتیب 27. 8 ٪ و 352. 7 ٪ نمره را ارائه می دهیم. ما همچنین ICOT را در برابر چندین روش پیشرفته مقایسه می کنیم که نشان دهنده رویکردهای مختلف خوشه بندی ، یعنی خوشه بندی جزئی ، سلسله مراتبی ، مبتنی بر مدل و چگالی است. ما می دانیم که ICOT در برابر این روش ها در معیارهای مختلف اعتبار سنجی داخلی رقابتی است.

ما نمونه هایی از نحوه استفاده از الگوریتم در تنظیمات دنیای واقعی را ارائه می دهیم. ما در مورد بیماران در معرض خطر بیماری قلبی عروقی از مجموعه داده های مطالعه قلب فرامینگهام (FHS) (Daniel Levy 2006 ؛ Feinleib و همکاران 1975) برای شناسایی پروفایل های مشابه بیمار و پروفایل های اقتصادی کشورهای اروپایی در طول جنگ سرد انجام می دهیم (کریم و حمزا)2015). از طریق این آزمایشات ، ما تأثیر پارامترهای کلیدی مختلف در الگوریتم ICOT را نشان می دهیم. ما همچنین ICOT را با سایر الگوریتم های پیشرفته در آزمایش FHS و با CUBT در آزمایش مشخصات اقتصادی مقایسه می کنیم. ما در مورد تفسیر روشها و همچنین عملکرد آنها در معیارهای اعتبار سنجی داخلی بحث می کنیم.

سرانجام ، ما توانایی الگوریتم را برای مقیاس به نمونه های مشکل بزرگ با استفاده از FCPS و همچنین داده های دنیای واقعی از یک برنامه به اشتراک گذاری دوچرخه مبتنی بر بوستون آزمایش می کنیم. ما نشان می دهیم که تکنیک های اکتشافی پیشنهادی ما بر کیفیت راه حل های بازیابی تأثیر نمی گذارد. علاوه بر این ، آزمایش های ما نشان می دهد که ICOT می تواند به طور مؤثر مجموعه داده های اندازه را تا صدها هزار مشاهده انجام دهد.

ساختار مقاله به شرح زیر است. در فرقه2 ، ما مشکل ایجاد درخت بهینه را در یک چارچوب MIO شکل می دهیم. فرقه3 توضیحات کاملی از اجرای الگوریتم ارائه می دهد. در فرقه ها4 و 5 ، ما طیف وسیعی از آزمایشات را با استفاده از مجموعه داده های مصنوعی و واقعی انجام می دهیم تا عملکرد و تفسیر روش خود را در مقایسه با سایر الگوریتم های پیشرفته ارزیابی کنیم. در فرقه6 ، ما تأثیر روشهای مقیاس گذاری خود را بر زمان اجرا و کیفیت راه حل بررسی می کنیم. در فرقه7 ، ما در مورد یافته های کلیدی از کار و فرقه بحث می کنیم. 8 ما شامل اظهارات نتیجه گیری خود هستیم.

فرمولاسیون MIO

در این بخش، ما یک رویکرد MIO را ارائه می‌کنیم که به ما امکان می‌دهد مدل‌های درختی بهینه جهانی را در یک محیط یادگیری بدون نظارت بسازیم. در بخش2. 1، ما یک نمای کلی از چارچوب MIO ارائه شده توسط Bertsimas و Dunn (2017، 2019) ارائه می دهیم. بخش 2. 2 معیارهای اعتبار سنجی را معرفی می کند که به عنوان توابع هدف در مسئله بهینه سازی استفاده می شوند. در بخش2. 3، ما فرمول کامل ICOT را برای یکی از توابع از دست دادن در نظر گرفته شده بیان می کنیم.

چارچوب OCT

الگوریتم OCT ساختار درختی را با استفاده از MIO فرموله می‌کند که به ما اجازه می‌دهد یک مسئله واحد را تعریف کنیم، برخلاف روش‌های بازگشتی سنتی، از بالا به پایین که باید هر یک از تصمیمات درختی را به صورت مجزا در نظر بگیرند. این به ما اجازه می دهد تا تأثیر کامل تصمیماتی که در بالای درخت گرفته می شود را در نظر بگیریم، نه صرفاً یک سری تصمیمات بهینه محلی، و از نیاز به هرس و اقدامات ناخالص اجتناب کنیم.

داده های آموزشی به ما داده می شود \((<\mathbf >)\) ، حاوی n مشاهده \((<\mathbf >, y_i)\) , \(i = 1,\dots , n\) ، هر کدام دارای p ویژگی و یک برچسب کلاس \(y_i \in \\) به عنوان نشانگر اینکه کدام یک از برچسب های پتانسیل K به نقطه i اختصاص داده شده است.. ما بدون از دست دادن کلیت فرض می کنیم که مقادیر هر بردار آموزشی به گونه ای نرمال شده است که \(<\mathbf >\در [0, 1]^p\) . درخت تصمیم به صورت بازگشتی فضای ویژگی را برای شناسایی مجموعه ای از مناطق مجزا و سلسله مراتبی که درخت طبقه بندی را تشکیل می دهند، تقسیم بندی می کند. درخت نهایی \(<<\mathcal >>\) از گره هایی تشکیل شده است که می توانند در زیر دسته بندی شوند:

گره برگ: گره \(t \in<<\mathcal >_<\mathcal >>\) به تمام نقاطی که در آنها قرار می گیرند یک کلاس اختصاص دهید. هر گره برگ با یک کلاس مشخص می شود که به طور کلی توسط کلاسی که اغلب در بین مشاهداتی که متعلق به آن هستند تعیین می شود.