پروژه آموزشی پیاده سازی الگوریتم خوشه بندی k-means بصورت iterative با متلب

 

نحوه ی کار الگوریتم
نسل اول :
الگوریتم k-means اعمال میشه ولی در این نسل دو تا عملیات Threshold داریم :
1 – برای تعداد خوشه ها در نسل اول در k-means معمولی.
2-  یه حد آستانه دیگه تعیین می کنیم و می گوییم اگر در 30 Epoch متوالی مراکز خیلی جا به جا نشدند، یعنی
به اندازه ی یک ԑ(Epsilon) سر جای خودشان جابه جا می شوند، پس دیگر کافی است و ادامه ندهید.
نسل دوم :
1 – یکی از کارهایی که در این نسل باید انجام بدهیم هرس کردن می باشد، هرس کردن به صورت ترکیبی برش
جزئی و کلی می باشد. ابتدا هرس کلی اتفاق می افتد یعنی مثلا شما در نظر بگیرید که ما در نسل اول k=5
می باشد یعنی 5 تا خوشه ی پدر داریم . اولین کاری که در نسل دوم میکنیم این است که این 5 تا خوشه ی
پدر را با تصویر کوئری داده ی تست  می سنجیم و سپس یکی را که از همه دور تر می باشد حذف میکنیم
پس یعنی 5 / 1 یعنی 20 درصد از تعداد خوشه های پدر را هرس کلی یا برش کلی میزنیم. حالا 4 تا خوشه ی
پدر داریم.
2) ادامه الگوریتم در نسل 2 می آییم هر خوشه ی نسل اول را به تعدادی خوشه ی جدید تقسیم می کنیم، یعنی
یک حد آستانه دیگر هم اینجا داریم که با استفاده از آن، هر خوشه از نسل قبلی را به تعدادی خوشه تقسیم
می کنیم ، پس k را باید مشخص کنیم که یعنی هر خوشه ی پدر به چند تا خوشه ی فرزند تقسیم بشود مثلا
k=8 قرار می دهیم پس ما الان 32 تا فرزند)پنج پدر داشتیم در نسل اول که با ورود به نسل دوم 20 درصدش
هرس کلی کردیم حالا چهار پدر باقی مونده هر کدوم تبدیل به هشت تا خوشه فرزند می شوند که مجموعا 32
تا خوشه فرزند) در نسل دوم داریم .
الف) عملیات merge کردن خوشه ای از خوشه های نسل دو، که تعداد سمپل های کم هست ) یک سلول یا
ماتریس درمتلب تعریف می کنیم که کلا میانگین یا mean همه ی خوشه ها را داخلش قرار بدهیم ( برای
اینکه ببینیم که دو تا کلاستر بهم نزدیک هستن یا نه برای merge کردن شون میاییم میانگین عناصر اون
خوشه ای که تعداد سمپل هاش کم هست رو حساب میکنیم و می بینیم که به میانگین کدوم یکی از خوشه
های نزدیک و اونا باهم merge میکنیم و قاعدتا مرکز کلاستر مجددا بررسی می شود.
ب) اگر خوشه ای هیچ سمپلی داخلش نباشه و تهی باشه اون به صورت اتوماتیک حذف بشود.

حالا برش جزئی را انجام میدهیم به این صورت که یک ماتریس مانند شکل زیر رسم میکنیم. در این ماتریس
به تعداد پدر ها که 4 تا هست سطر داریم و به تعداد فرزندانی که به وجود اومدن برای هر پدر که 8 تا می باشد
ستون داریم. سطر اول تا 4 ماتریس رو از دور به نزدیک نسبت به تصویر کوئری)یا داده تست( پدر ها رو قرار
میدهیم.)یعنی سطر اول ماتریس دورترین پدر نسبت به تصویر کوئری)یا داده تست( از این 4 تا پدر هست و
سطر آخر یا چهارم نزدیک ترین پدر به داده ی تست ما می باشد و هم چنین فرزندان هر پدر را هم با داده ی
تست مقایسه کنید و از سمت چپ ماتریس نزدیک ترین فرزندان به داده ی تست را به صورت سورت یا مرتب
داخل ماتریس قرار بدهید به گونه ای که فرزند سمت چپ یا اولین فرزند، داخل ماتریس ،نزدیک ترین خوشه
یا فرزند به داده ی تست و فرزند سمت راست یا اخرین فرزند دورترین خوشه به داده ی تست باشد. ( حالا از
بالا به پایین روشی که معمول هست در هوش مصنوعی مثل الگوریتم ذوب فلزات که هرچی دما کم می شود
فشار هرس هم کم می شود. از سطر اول که نسبت به داده ی تست ما دور هست 80 درصد، سطر بعدی 60 ،
سطر بعدی 40 و سطر اخر 20 درصد هرس میشود. انجام پروژه متلب
توجه : این درصد هرس باید متناسب با تعداد سطر های ماتریس باشد یعنی الان که 4 سطر هست به این شکل
هرس می شود وقتی سطرها بیشتر می شود باید هرس هم کمتر شود.

پروژه آموزشی پیاده سازی الگوریتم خوشه بندی k-means بصورت iterative با متلب توسط کارشناسان گروه ۱.۲.۳ پروژه پیاده سازی گردیده است .