باشگاه دانشجویی کارشناسی ارشد دانشگاه امیرکبیر

۹۲/۰۷/۱۳
تدریس یار خوشه بندی

تمرین تا ۲۴ مهر فرصت داده شده

الگوریتم K-means

تعداد خوشه ها به صورت پیش فرض به ما داده می شود
اما خیلی مواقع این تعداد در دسترس نیست

یک سری بردار ویژگی داده می شود که باید تقسیم بندی کنیم که چند دسته نقسیم می شوند.

هدف خوشه بندی :خوشه بندی تا حد امکان فشرده باشند و خوشه های مختلف تا حد امکان فاصه آنها از هم بیشتر باشد.

تعداد پارامتر های مدل را باید بیشتر کرد

باید یک پارامتر جریمه باید گذاشت که تعداد خوشه ها خیلی زیاد نشوند

به عنوان تمرین هفته آینده گفته می شود : هر کسی حداقل ۵ معیار را پیدا کند که تعداد خوشه های بهینه در یک الگوریتم خوشه بندی بهینه باشد
این برچسب ها در ابتدا مشخص نیستند.

این برچسب ها می گویند هر داده مربوط به چه خوشه ای است
در K meas
n اندیس نمونه k هست
k بین ۱ تا ۳ تغییر پیدا می کند

برای هر نمونه X(n)
نمونه یکم در مرحله اول به چه خوشه ای تعلق دارد
توسط تابع j مجموع مجذورات بردار نمونه را حساب میکنیم

قرار است تابع را مینی مایز کنیم ، فاصله هر نمونه تا مرکز خوشه حداقل شود

هدف k-means حداقل سازی
به روش تکرار شونده انجام می دهد .
اول از همه شروع الگوریتم ۳ تا مرکز اولیه را بدهد

چند تا نقطه local min می تواند داشته باشد

اهمیت دارد که Global min داشته باشد

در یک فرایند دو فازی این
یک تابع دو پارامتری هست

فرض می کنیم میو k ثابت هست
نسبت به rnk حداقل کنیم

تعلق داده ها به خوشه ها

برچسب نمونه
ولی j را در فاز دوم نسبت که میو k حداقل کنیم

در هر فاز تابع j را پیدا میکنیم

فاز دوم اینکه چجوری میو k را انتخاب کنیم
مشتق میگیریم

در جایی که الگوریتم را تکرار کنیم و برچسب های خوشه عوض نشد ، نقطه پایانی هست ( یکی از معیار ها )

روش K-means

EM : Expectation Maximization روش بیشینه سازی امید در K-means

محدودیت اصلی روش K-means مبنایی

روشهای دیگر : فازی C-means و gmm و کاهش بعد را در این درس بررسی میکنیم