خوشه‌بندی کی-میانگین

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

تاریخچه الگوریتم 
اصطلاح کی-میانگین  برای اولین بار توسط جیمز مک‌کوین در سال ۱۹۶۷ مورد استفاده قرار گرفت، هرچند این ایده به هوگو استینگز در سال ۱۹۵۷ باز می‌گردد. این الگوریتم ابتدا توسط استوارت لویید در سال ۱۹۵۷ به عنوان یک تکنیک برای مدولاسیون کد پالس پیشنهاد شد و تا سال ۱۹۸۲ خارج از آزمایشگاه‌های بل به انتشار نرسید. فورجی در سال ۱۹۶۵ الگوریتمی مشابه را منتشر کرد، به همین دلیل است که بعضی اوقات این الگوریتم، لویید فورجی هم نامیده می‌شود.

توضیحات 
با توجه به مجموعه‌ای از مشاهدات  که در آن هر یک از مشاهدات یک بردار حقیقی -بعدی است. خوشه‌بندی کی-میانگین با هدف پارتیشن‌بندی  مشاهدات به  مجموعه  است به طوری که مجموع مربع اختلاف از میانگین (یعنی واریانس) برای هر خوشه حداقل شود. تعریف دقیق ریاضی آن به این شکل است:

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

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

الگوریتم

الگوریتم استاندارد 
رایج‌ترین الگوریتم کی-میانگین با استفاده از یک تکرار شونده پالایش کار می‌کند. اغلب به نام الگوریتم کی-میانگین شناخته می‌شود. آن را با عنوان الگوریتم لوید نیز می‌شناسند مخصوصاً در میان جامعه علوم کامپیوتر.

الگوریتم به این شکل عمل می‌کند:

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

 حال میانگین‌ها را بر اساس این خوشه های جدید به این شکل بروز می‌کنیم:

 در نهایت میانگین‌های مرحله آخر (در زمان ) یعنی  خوشه‌ها را نمایندگی خواهند کرد.

الگوریتم کی-میانگین را می‌توان با پویانمایی پایین برای  به تصویر کشید.

کاربردها 
خوشه‌بندی کی‌میانگین خوشه‌بندی حتی برای مجموعه داده‌های بزرگ به‌ویژه هنگام استفاده از روش‌های اکتشافی مانند Lloyd's algorithm بسیار آسان است. این با موفقیت در بخش‌بندی بازار، بینایی رایانه‌ای و نجوم در میان بسیاری از حوزه‌های دیگر مورد استفاده قرار گرفته است. اغلب به عنوان یک مرحله پیش پردازش برای الگوریتم های دیگر استفاده می شود، به عنوان مثال برای پیدا کردن یک پیکربندی شروع.

کمیت‌سازی برداری 

خوشه‌بندی کی‌میانگین از پردازش سیگنال سرچشمه می گیرد و هنوز در این حوزه کاربرد دارد. به عنوان مثال، در گرافیک کامپیوتری، کمیت‌سازی رنگ وظیفه کاهش  پالت رنگ یک تصویر به تعداد ثابتی k از رنگ‌ها است. الگوریتم کی‌میانگین به راحتی می تواند برای این کار استفاده شود و نتایج قابل رقابتی ایجاد کند. یک مورد استفاده برای این رویکرد تقسیم بندی تصویر است. کاربردهای دیگر کمیت‌سازی برداری عبارتند از نمونه‌گیری غیرتصادفی، زیرا کی‌میانگین به راحتی می‌تواند برای انتخاب k دنمونه متفاوت اما مقدماتی از یک مجموعه داده بزرگ برای آنالیزهای بیشتر استفاده شود.

تحلیل خوشه‌ای 

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

یادگیری ویژگی 
خوشه‌بندی کی‌میانگین به عنوان یک مرحله یادگیری ویژگی (یا یادگیری دیکشنری) در (یادگیری نیمه نظارتی یا یادگیری خودران (خودسازمانده) استفاده شده است.

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

روش دیگر، تبدیل فاصله نمونه-خوشه از طریق یک  RBF گاوسی می‌باشد که لایه پنهان یک شبکه تابع پایه شعاعی
را به دست می‌آورد.

این استفاده از کی‌میانگین به طور موفقیت آمیزی با طبقه‌بندی خطی های ساده برای یادگیری نیمه نظارتی در NLP (به ویژه برای شناسایی موجودیت نامدار  ) ترکیب شده است.

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

نگارخانه

منابع 

الگوریتم‌های آماری
روش‌های خوشه‌بندی