در این پست از وبسایت پرووید در رابطه با پیاده سازی الگوریتم خوشه بندی کا میانگین در سی شارپ صحبت خواهیم کرد. الگوریتم خوشه بندی کا میانگین یکی از الگوریتم های Clustering می باشد.
در این قسمت از وبسایت پرووید قصد داریم که یک دوره ی آموزشی رایگان دیگر که به صورت متنی برای شما تنظیم شده است را ارائه بدهیم. در این دوره ی آموزشی در رابطه با پیاده سازی الگوریتم خوشه بندی کا-میانگین (K-Means Clustering) در سی شارپ صحبت خواهیم کرد. امیدواریم که این دوره ی آموزشی نیز برای شما جذاب و کاربردی باشد.
سعی می کنم به زبان خیلی ساده و غیررسمی بنویسم. یه مدت قبل توی پروژه ی کارشناسی ارشدم از این الگوریتم استفاده کردم و داده هامو خوشه بندی کردم. بعد از اتمام کارم به این فکر افتادم که این الگوریتم رو توی سی شارپ پیاده سازی کنم. اینکه انگیزم از این کار چی بود رو بهتره که نگم. به هر حال، شروع کردم به کار و بعد از چند ساعت تونستم کار رو تموم کنم.
بعد از انجام کار، تصمیم گرفتم که نتیجه ی کارم رو در قالب یه مقاله توی سایت کد پراجکت (codeproject.com) منتشر کنم. این لینک مقاله توی سایت کد پراجکت هست. البته از قبل هم چند تا مقاله توی این سایت در مورد شی گرایی و … داشتم. بعد از این، تصمیم گرفتم که توی یه سری پست روی وبسایت پرووید هم کارمو ارائه بدم. البته سعی کردم کدنویسی رو خیلی ساده انجام بدم.
خب، حالا که ماهیت این سری آموزش آشنا شدید، بذارید بحثمو توی پست بعدی ادامه بدم.
قبل از اینکه بریم سراغ برنامه میخوام یه کوچولو در مورد الگوریتم کا-میانگین صحبت کنم. اولین سوالی که شاید به ذهن برسه اینه که کار این الگوریتم چیه؟ همونطور که از اسمش معلومه، این الگوریتم قراره خوشه بندی برای ما انجام بده. یعنی اینکه یه سری داده رو توی خوشه های مختلف برای ما دسته بندی کنه. خوشه رو همون دسته یا گروه در نظر بگیرید.
به عنوان یه مثال از خوشه بندی، فرض کنید ما اطلاعات صد تا دانش آموز رو داریم و میخوایم اونا رو توی n دسته، گروه بندی کنیم. اما اساس گروه بندی چیه؟ خب اساس کار اینه که طوری خوشه بندی رو انجام بدیم تا اعضای یک خوشه ی یکسان حداقل اختلاف رو با هم داشته باشن و اعضای خوشه های مختلف بیشترین اختلاف رو. مثلاً، همون دانش آموزها رو در نظر بگیرید. دانش آموزهایی که معدلشون بالای 16 است، انضباطشون بالای 17 است و حداکثر دو درس رو تا حالا افتادن بذاریم توی یه خوشه، دانش آموزهایی که معدلشون بالای 18 هست، انضباطشون بالای 19 هست و تا حالا هیچ درسی رو نیفتادن بذاریم توی گروه دیگه و همینطور الی آخر.
در واقع نتیجه ی آخر الگوریتم کا-میانگین یه سری خوشه است که هر کدوم حاوی یه سری داده هستند به طوری که داده های درون یه خوشه خیلی به هم شباهت دارند و داده های دو تا خوشه ی متفاوت با هم اختلاف زیادی دارند.
توی این پست می خوام کار رو توی سی شارپ پیش ببرم. هنوز خیلی نکات در مورد الگورتیم کا-میانگین رو نگفتیم ولی خب ترجیح میدم که اونا رو در عمل بهتون بگم. اولین کاری که من انجام دادم، تعریف یک کلاس به عنوان Data Model برنامه است. اسم کلاس رو گذاشتم DataPoint و اینجوری تعریفش کردم:
public class DataPoint
{
public double Height { get; set; }
public double Weight { get; set; }
public int Cluster { get; set; }
public DataPoint(double height, double weight)
{
Height = height;
Weight = weight;
Cluster = 0;
}
public DataPoint()
{
}
public override string ToString()
{
return string.Format("{{{0},{1}}}", Height.ToString("f" + 1), Weight.ToString("f" + 1));
}
}
همونطور که می بینید این کلاس دو تا پروپرتی Height و Weight داره که قراره داده های مربوط به وزن و قد یه سری افراد رو ذخیره کنه. به علاوه، پروپرتی Cluster حاوی ایندکس خوشه ای هست که یک DataPoint توی اون قرار میگیره. مثلاً، اگر مقدار این پروپرتی برای یک شی از این کلاس برابر 3 باشه، یعنی اینکه این DataPoint توی خوشه ی 3 قرار داره. خب من یه کار دیگه هم انجام دادم و اونم Override کردن متد ToString هست. در واقع از این مدت برای نشون دادن DataPoint ها در یک سری TextBox استفاده کردم. همونطور که می بینید، این متد دو تا پروپرتی Height و Weight رو با فرمت {Height,Weight} بر می گردونه.
توی این قسمت کارمون رو روی برنامه ادامه میدیم. برای ذخیره کردن شی های کلاس DataPoint من چند تا کالکشن به برنامه اضافه کردم:
List _rawDataToCluster = new List();
List _normalizedDataToCluster = new List();
List _clusters = new List();
private int _numberOfClusters = 0;
کالکشن ها از نوع لیست جنریک هستند. کالکشن _rawDataToCluster وظیفه ی ذخیره سازی اشیا خام کلاس DataPoint رو داره. چرا میگم خام؟ در ادامه معلوم میشه. یک کالکشن دیگه هم از همین نوع با نام _normalizedDataToCluster تعریف کردم که قراره داده های نرمال شده رو توش قرار بدم. اینکه نرمال سازی چیه رو شاید بدونید شاید ندونید، به هرحال من در ادامه یه کم ازش صحبت می کنم. یه کالکشن دیگه هم با نامه _clusters تعریف کردم که اطلاعات خوشه ها درونش قرار میگیره. اینکه چرا کالکشن آخر که قراره داده های خوشه ها درونش قرار بگیره از نوع DataPoint هست هم بعد معلوم میشه.
نهایتاً یه integer با نام _numberOfClusters تعریف کردم که تعداد خوشه های برنامه رو درونش قرار میدم. این اشیا رو در سطح کلاس (form اصلی برنامه) تعریف کردم تا بتونم توی تمامی متدها ازش استفاده کنم. میدونم که این روش اصول برنامه نویسی شی گرا رو یه جورایی زیر سوال میبره و بهتره که توی متدها اشیا رو پاس بدیم ولی همونطور که اول کار گفتم خواستم برنامه رو به طور خیلی ساده بنویسم و ازش خروجی دریافت کنم.
کاری که الان باید انجام بدیم اینه که به کاربر اجازه بدیم داده های موردنظرشو وارد کنه و همچنین اونا رو ببینه. من برای این کار، دو تا TextBox روی فرم گذاشتم که کاربر دو تا مقدار برای پروپرتی های Height و Weight وارد می کنه و وقتی توی TextBox دوم دکمه ی Enter از کیبورد رو میزنه اون دو تا عدد رو به یه ListBox اضافه می کنم. این کدی هست که برای رویداد Key_Down از TextBox نوشتم:
private void txtWeight_KeyDown(object sender, KeyEventArgs e)
{
if (e.KeyCode==Keys.Enter)
{
if (string.IsNullOrEmpty(txtHeight.Text) || string.IsNullOrEmpty(txtWeight.Text))
{
MessageBox.Show("Please enter the values for both Height and Weight.");
return;
}
DataPoint dp=new DataPoint();
dp.Height = double.Parse(txtHeight.Text);
dp.Weight = double.Parse(txtWeight.Text);
lstRawData.Items.Add(dp.ToString());
}
}
وقتی که کاربر داده هاشو وارد کرد و نهایتاً دستور شروع کار رو داد، باید داده های درون ListBox رو بریزیم توی کالکشن هایی که توی پست قبلی تعریف کردیم. البته اینو بگم که میشه توی همون مرحله ی قبل (وارد کردن داده ها توی ListBox) هم داده ها رو توی کالکشن ها بریزیم ولی خب کاری که من کردم این بوده که با زدن یه دکمه، هر چی داده توی ListBox هست رو میریزم توی کالکشن _rawDataToCluster. این کدی هست که برای این کار اضافه کردم.
private void InitilizeRawData()
{
if (_rawDataToCluster.Count == 0)
{
string lstRawDataItem = string.Empty;
for (int i = 0; i < lstRawData.Items.Count; i++)
{
DataPoint dp = new DataPoint();
lstRawDataItem = lstRawData.Items[i].ToString();
lstRawDataItem = lstRawDataItem.Replace("{", ");
lstRawDataItem = lstRawDataItem.Replace("}", ");
string[] data = lstRawDataItem.Split(',');
dp.Height = double.Parse(data[0]);
dp.Weight = double.Parse(data[1]);
_rawDataToCluster.Add(dp);
}
}
}
همونطور که می بینید، این کد توی تمامی سطرهای ListBox پیمایش انجام میده، داده های درون هر سطر رو با متد Split جدا می کنه، یک شی جدید از نوع DataPoint می سازه، پروپرتی ها رو ست می کنه و نهایتاً اون شی رو به کالکشن اضافه می کنه.
یکی از موضوعاتی که توی الگوریتم خوشه بندی کا-میانگین باید بهش دقت کنیم، نرمال سازی داده هاست. دلیل اینکه نیاز داریم داده ها رو نرمال کنیم اینه که الان داده های ما از نظر ماهیت با هم متفاوت هستند: یکی در مورد وزن و دیگر در مورد قد افراد هست. در واقع چون مقیاس این دو تا پروپرتی فرق می کنن ما باید داده ها رو نرمال کنیم. به عنوان یه مثال دیگه، فرض کنید که داده هایی داریم که مربوط به معدل دانش آموزها، تعداد درسهای انتخابی هر ترمشون، سن شون و غیره هست. دوباره چون ماهیت داده ها فرق داره باید اونا رو نرمال کنیم. روشهای مختلفی برای نرمال سازی داده ها وجود داره که من سعی کردم از ساده ترین اونها استفاده کنیم. اسم این روش گوسیون (روش نرمال) است. در ادامه کد این روش رو براتون گذاشتم:
private void NormalizeData()
{
double heightSum = 0.0;
double weightSum = 0.0;
foreach (DataPoint dataPoint in _rawDataToCluster)
{
heightSum += dataPoint.Height;
weightSum += dataPoint.Weight;
}
double heightMean = heightSum / _rawDataToCluster.Count;
double weightMean = weightSum / _rawDataToCluster.Count;
double sumHeight = 0.0;
double sumWeight = 0.0;
foreach (DataPoint dataPoint in _rawDataToCluster)
{
sumHeight += Math.Pow(dataPoint.Height - heightMean, 2);
sumWeight += Math.Pow(dataPoint.Weight - weightMean, 2);
//sumWeight += (dataPoint.Weight - weightMean) * (dataPoint.Weight - weightMean);
}
double heightSD = sumHeight / _rawDataToCluster.Count;
double weightSD = sumWeight / _rawDataToCluster.Count;
foreach (DataPoint dataPoint in _rawDataToCluster)
{
_normalizedDataToCluster.Add(new DataPoint()
{
Height = (dataPoint.Height - heightMean)/heightSD,
Weight = (dataPoint.Weight - weightMean) / weightSD
}
);
}
}
روش کار این کد خیلی ساده ست. اول این رو بگم که ما داده های خامی که داریم رو نرمال می کنیم و بعد توی کالکشن _normalizedDataToCluster قرار می دیم. اولین کاری که باید انجام بدیم اینه که جمع تمامی مقادیر دو پروپرتی Height و Weight رو توی تمامی DataPoint ها به دست بیاریم. این کاری هست که حلقه ی foreach اول انجام میده. بعد از اون، میانگین این دوتا مقدار رو با تقسیم دوتا مقدار قبلی بر تعداد DataPoint ها به دست میاریم. حلقه ی foreach بعدی مقدار دو تا پروپرتی Height و Weight رو در تمامی DataPoint ها از میانگین مرحله ی قبلی کم می کنه و به توان دو میرسونه (البته نتیجه مرحله های قبلی رو هم نگه میداره و در واقع نتیجه ی هر مرحله از حلقه رو با نتایج قبلی جمع میزنه.). توی قسمت بعدی، مقدار به دست اومده از مرحله قبل رو تقسیم بر تعداد DataPoint ها می کنیم. و نهایتاً توی قسمت آخر، به ازای تمامی DataPoint هایی که داریم، Heigth و Weight شون رو از میانگین کم می کنیم و تقسیم بر انحراف معیاری می کنیم که توی مرحله ی قبلی حساب کردیم. این مقادیر جدید برای Height و Weight رو در قالب یه سری شی جدید به کالکشن _normalizedDataToCluster اضافه می کنیم.
خب از این قسمت به بعد به طور اساسی کار رو روی الگوریتم کا-میانگین شروع می کنیم. البته قبل از این که سراغ کد نویسی بریم بذارید یه کم در مورد نحوه ی کار این الگوریتم صحبت کنم. به عکس زیر که از ویکی پدیا آوردم دقت کنید.
یادتون هست که کار الگوریتم کا-میانگین خوشه بندی یه سری داده ها در گروه های متفاوت بود. به عکس های بالا از چپ به راست دقت کنید. توی عکس اول یه سری مربع های خاکستری رنگ داریم که قراره خوشه بندی بشن و توی دسته های مختلف قرار بگیرن. به علاوه، یه سری نقاط دایره ای رنگی هم داریم. در واقع این نقاط رنگی مشخص کننده یک خوشه هستند و با کمک اونها داده های دیگه رو خوشه بندی می کنیم.
اگر به عکس دوم نگاه کنید می بیند که مربع های خاکستری دیگه رنگ شدند. فضای اصلی هم به سه قسمت رنگی تقسیم شده که خب طبیعتاً محدوده ی هر خوشه رو نشون میده. هر کدوم از مربع ها که توی هر خوشه هستند، با اون دایره ها همرنگ شدند. اسم این دایره ها رو میذاریم Centroid (نقاط مرکزی).
توی عکس سوم یه سری تغییراتی انجام شده. در واقع بعضی از مربع ها توی خوشه ها جابجا شدند. این تغییر اونقدر انجام می پذیره که نهایتاً به عکس آخر برسیم. توی عکس آخر می بینید که خوشه بندی ما تکمیل شده و هر کدام از مربع ها دیگه توی بهترین خوشه ها قرار گرفتند.
در واقع، وظیفه ی الگوریتم خوشه بندی کا-میانگین هم همینه که خوشه بندی رو طوری تغییر بده تا داده ها توی بهترین خوشه ها قرار بگیرند به طوری که تفاوت داده های درون یک خوشه ی یکسان به حداقل و تفاوت داده های دو خوشه ی مختلف به حداکثر برسه.
همونطور که توی قسمت قبلی هم گفتم، Centroid ها به ما کمک میکنند تا داده ها رو خوشه بندی کنیم. در واقع، هر Centroid نشون دهنده ی یک خوشه است. حرف K در نام در الگوریتم (K-Means Clustering) نشون دهنده ی تعداد خوشه هاست. یکی از موضوعات در الگوریتم کا-میانگین اینه که در ابتدای کار باید یه سری Centroid تعریف کنیم. به عبارت دیگر، باید داده های اولیه رو توی یه سری خوشه قرار بدیم و الگوریتم رو شروع کنیم. روش های مختلفی برای ایجاد Centroid ها در ابتدای کار وجود داره. یکی از این روش ها قرار دادن تصادفی اونهاست. یعنی اینکه ما به طور تصادفی داده ها رو توی خوشه های متفاوتی قرار می دیم. باید تعداد خوشه های وارد شده توسط کاربر هم مد نظر قرار بگیره. به کد زیر دقت کنید:
private void InitializeCentroids()
{
Random random = new Random(_numberOfClusters);
for (int i = 0; i < _numberOfClusters; ++i)
{
_normalizedDataToCluster[i].Cluster = _rawDataToCluster[i].Cluster = i;
}
for (int i = _numberOfClusters; i < _normalizedDataToCluster.Count; i++)
{
_normalizedDataToCluster[i].Cluster = _rawDataToCluster[i].Cluster = random.Next(0, _numberOfClusters);
}
}
این کد وظیفش اینه که داده های ورودی رو توی یک سری خوشه ی تصادفی قرار بده. یکی از موضوعات الگوریتم کا-میانگین اینه که همه ی خوشه ها در هر لحظه از زمان باید حداقل یک عضو داشته باشن. حلقه ی اول این کار رو برای ما انجام میده. در واقع، حلقه ی اول به ازای تعداد خوشه ای که کاربر مد نظر داره، پروپرتی Cluster از DataPoint ها رو ست می کنه. حلقه ی دوم هم به طور تصادفی پروپرتی Cluster برای ما بقی DataPoint ها رو با در نظر گرفتن تعداد خوشه های مورد نظر کاربر پر میکنه.
تا حالا، ما تونستیم به طور تصادفی DataPoint ها رو توی خوشه های مختلف قرار بدیم و کنترل هم کردیم که هر خوشه لااقل یک DataPoint داشته باشه.
توی قسمت قبلی ما تونستیم داده ها رو توی خوشه های تصادفی قرار بدیم. کاری که باید الان انجام بدیم اینه که میانگین داده های درون هر خوشه رو محاسبه کنیم. در واقع، همین میانگین هست که نهایتاً تصمیم میگیره که کدوم DataPoint توی کدوم خوشه قرار بگیره. اسم الگوریتم هم از همینجا میاد: کا-میانگین (K-Means). خب چجوری اینو انجام بدیم؟ و کجا ذخیره کنیم؟ یادتونه که یه کالکشن با اسم _culsters تعریف کرده بودم که یک لیست جنریک از نوع DataPoint بود. در واقع ما به ازای هر خوشه یا Centroid یه DataPoint توی این کالکشن قرار میدیم. پروپرتی Cluster توی داده های درون این لیست اندیس هر خوشه رو نگه میدارن و دو تا پروپرتی Height و Weight به ترتیب میانگین مقادیر این دو تا پروپرتی رو برای تمامی DataPoint های درون اون خوشه نگه می دارند.
برای روشن تر شدن بحث یه مثال میزنم. فرض کنید توی کالکشن _rawDataToCluster سه تا DataPoint با مقادیر
داریم. بر اساس پروپرتی Cluster می تونیم بفهمیم که هر سه تای این DataPoint ها توی خوشه ای با اندیس 1 هستند. حالا اگر به کالکشن _clusters نگاه کنیم، می بینیم یه DataPoint با مقدار
DataPoint{21.6,70.6,1}
وجود داره. اندیس این خوشه 1 هست. پروپرتی های Height و Weight به ترتیب حاوی میانگین این دو تا پروپرتی در سه تا DataPoint ی هست که درون این خوشه هستند. برای محاسبه ی میانگین هم کافیه مقادیر هر پروپرتی رو جمع و تقسیم بر تعداد DataPoint درون اون خوشه کنیم. حالا کد زیر رو نگاه کنید:
private bool UpdateDataPointMeans()
{
if (EmptyCluster(_normalizedDataToCluster)) return false;
var groupToComputeMeans = _normalizedDataToCluster.GroupBy(s => s.Cluster).OrderBy(s => s.Key);
int clusterIndex = 0;
double height = 0.0;
double weight = 0.0;
foreach (var item in groupToComputeMeans)
{
foreach (var value in item)
{
height += value.Height;
weight += value.Weight;
}
_clusters[clusterIndex].Height = height / item.Count();
_clusters[clusterIndex].Weight = weight / item.Count();
clusterIndex++;
height = 0.0;
weight = 0.0;
}
return true;
}
توی این متد اول چک کردم که هیچ خوشه ای خالی نباشه. اگر اینجوری بود سریع false رو بر میگردونم. در غیر اینصورت، بر اساس همون دستور LINQ و گروه بندی ای روی کالکشن _clusters بر اساس پروپرتی Cluster کردم میانگین پروپرتی ها رو توی کالکشن _normalizedDataToCluster محاسبه می کنم و توی DataPoint های متناظر درون _clusters قرار میدم. همونطور که گفتم کافیه جمع همه ی مقادیر این دو تا پروپرتی رو به دست بیاریم و بر تعداد تقسیم کنیم.
تا اینجای کار من تونستم کدی را بنویسم که میانگین داده های درون هر خوشه رو حساب کنه و ذخیره کنه.
همونطور که قبلا هم گفتم، یکی از موضوعات مهم در روش کا-میانگین اینه که در هر لحظه، هیچ خوشه ای نباید خالی باشه. به عبارت دیگر، هر خوشه حداقل باید یه عضو داشته باشه وگرنه وجودش بی معنی است. توی قسمت قبلی، قبل از اینکه من میانگین داده های درون یک خوشه را محاسبه کنم چک می کردم که خوشه ها خالی نباشند. کدی که این کار رو برام انجام میده اینه:
private bool EmptyCluster(List data)
{
var emptyCluster =
data.GroupBy(s => s.Cluster).OrderBy(s => s.Key).Select(g => new {Cluster = g.Key, Count = g.Count()});
foreach (var item in emptyCluster)
{
if (item.Count == 0)
{
return true;
}
}
return false;
}
اول کالکشن _clusters رو بر اساس پروپرتی Cluster گروه بندی می کنم و بعد چک می کنم که هر کدوم از گروه ها لااقل یک عضو داشته باشه. (Count که توی دستور LINQ تعریف شده مساوی صفر نباشه.)
یه موضوع دیگه که میخوام توی این پست ازش صحبت کنم محاسبه ی فاصله است. حالا که ما توانستیم میانگین داده های درون یک خوشه رو به دست بیاریم، باید فاصله ی یک DataPoint تا اون میانگین رو محاسبه کنیم و تصمیم بگیریم که آیا اون DataPoint باید به اون خوشه منتقل بشه یا نه. در واقع، ما به دنبال خوشه ای هستیم که میانگین داده هاش (پروپروتی های Height و Weight مربوط به DataPoint های درون کالکشن _clusters) کمترین تفاوت رو همین دو پروپرتی از یک DataPoint داشته باشه. وقتی توانستیم یه همچین خوشه ای رو به دست بیاریم، باید اون DataPoint رو به اون خوشه منتقل کنیم. حالا چجوری فاصله رو محاسبه کنیم؟ روش های مختلفی برای این کار وجود داره. من از روش Euclidean (فاصله ی اقلیدسی) استفاده کردم. فرمولش رو از توی این لینک ببنید. کد زیر بر اساس فرمول این روش نوشته شده:
private double EuclideanDistance(DataPoint dataPoint, DataPoint mean)
{
double _diffs = 0.0;
_diffs = Math.Pow(dataPoint.Height - mean.Height, 2);
_diffs += Math.Pow(dataPoint.Weight - mean.Weight, 2);
return Math.Sqrt(_diffs);
}
همونطور که می بنید، این متد دو تا DataPoint رو دریافت می کنه. پارامتر اول همون DataPoint ی هست که میخوایم احتمالاً به یک خوشه ی دیگه منتقلش کنیم. و پارامتر دوم همون خوشه ی هدف هست که میانگین داده هاش درون دو تا پروپرتی ش ذخیره شده. این متد فاصله ی بین Height و Weight رو محاسبه می کنه و به عنوان یک عدد double بر می گردونه.
خب، بازم به الگوریتم کا-میانگین فکر کنید. این الگوریتم دنبال اینه که اونقدر DataPoint ها رو بین خوشه ها بهینه (که فاصله ی کمتری با یک DataPoint) دارند، جابجا کنه تا به یک خوشه بندی کامل و بهینه برسه. برای جابجا کردن یک DataPoint بین خوشه ها، کافیه که پروپرتی Cluster رو برای هر DataPoint تغییر بدیم. در واقع این پروپرتی نشون دهنده ی اون خوشه ای هست که DataPoint درونش قرار داره. حالا بحث اینه که چجوری اون خوشه رو پیدا کنیم. خیلی راحته. توی هر مرحله از الگوریتم باید فاصله ی DataPoint رو با تمامی خوشه های حاضر محاسبه کنیم و DataPoint رو به اون خوشه ای منتقل کنیم که حداقل فاصله رو با DataPoint داره. البته باید چک کنیم که هیچ خوشه ای هم خالی نباشه. به علاوه، اگر هیچ جابجایی توی عضویت DataPoint ها در خوشه ها اتفاق نیفتاد، دیگه الگوریتم به آخرین مرحله رسیده و تموم میشه. کد زیر رو ببینید:
private bool UpdateClusterMembership()
{
bool changed = false;
double[] distances = new double[_numberOfClusters];
StringBuilder sb = new StringBuilder();
for (int i = 0; i < _normalizedDataToCluster.Count; ++i)
{
for (int k = 0; k < _numberOfClusters; ++k) distances[k] = ElucidanDistance(_normalizedDataToCluster[i], _clusters[k]); int newClusterId = MinIndex(distances); if (newClusterId != _normalizedDataToCluster[i].Cluster) { changed = true; _normalizedDataToCluster[i].Cluster = _rawDataToCluster[i].Cluster = newClusterId; sb.AppendLine("Data Point >> Height: " + _rawDataToCluster[i].Height + ", Weight: " +
_rawDataToCluster[i].Weight + " moved to Cluster # " + newClusterId);
}
else
{
sb.AppendLine("No change.");
}
sb.AppendLine("------------------------------");
txtIterations.Text += sb.ToString();
}
if (changed == false)
return false;
if (EmptyCluster(_normalizedDataToCluster)) return false;
return true;
}
برای پیدا کردن خوشه ای که یک DataPoint کمترین فاصله با اون رو داره از متد MinIndex که در زیر تعریف شده استفاده می کنیم. در واقع این متد یک آرایه رو دریافت می کنه و اندیس کمترین مقدار درون عناصر اون آرایه رو بر میگردونه. این کار توسط یه حلقه ی تکرار انجام میشه. فکر میکنم که کد این متد کاملاً ساده باشه و نیازی به توضیح بیشتری نباشه.
private int MinIndex(double[] distances)
{
int _indexOfMin = 0;
double _smallDist = distances[0];
for (int k = 0; k < distances.Length; ++k)
{
if (distances[k] < _smallDist)
{
_smallDist = distances[k];
_indexOfMin = k;
}
}
return _indexOfMin;
}
حالا که تمامی قسمت های الگوریتم رو ساختیم و کنار هم گذاشتیم وقت اینه که کار خوشه بندی رو انجام بدیم. متدی که خوشه بندی رو انجام میده کارش خیلی ساده ست. در واقع ما از قسمت هایی که قبلاً ساختیم استفاده می کنیم و کار خوشه بندی رو انجام میدیم. به کد زیر دقت کنید:
public void Cluster()
{
bool _changed = true;
bool _success = true;
InitializeCentroids();
int maxIteration = _normalizedDataToCluster.Count * 10;
int _threshold = 0;
while (success == true && _changed == true && _threshold < maxIteration)
{
++_threshold;
_success = UpdateDataPointMeans();
_changed = UpdateClusterMembership();
}
}
اول دوتا متغیر بولین تعریف شده که دوتاشون مقدار true گرفتند. متغیر _success با خروجی متد UpdateDataPointMeans تنظیم شده. بهتون پیشنهاد می کنم که قسمت های قبلی این آموزش رو بخوانید تا متوجه بشید کار این متد چی هست و چه موقع مقدار true یا false بر میگردونه. به علاوه، متغیر _changed با خروجی متد UpdateClusterMembership تنظیم میشه. این متد رو توی قسمت های قبلی این آموزش معرفی کردیم. متغیر maxIteration به عنوان آستانه ی حداکثر تکرار تعریف شده. یعنی اینکه ما حداکثر به این تعداد بار خوشه بندی رو انجام میدیم. و نهایتاً _threshold که با مقدار صفر تنظیم شده و هر دفعه مقدارش با متغیر maxIteration چک میشه میشه.
حالاً به حلقه ی while و شرطش دقت کنید. سه تا شرط برای تکرار این حلقه تعریف شده. اول اینکه _success == true یعنی اینکه خروجی UpdateDataPointMeans باید true باشه. خروجی این متد وقتی true میشه که همه ی خوشه ها لااقل یک عنصر داشته باشن. به عبارت دیگر، اگر در هر مرحله ای از الگوریتم یکی از خوشه ها خالی باشه، الگوریتم متوقف میشه. شرط بعدی اینه که _changed == true باشه. این متغیر در درون حلقه ی تکرار با خروجی متد UpdateClusterMembership تنظیم میشه. خروجی این متد زمانی true هست که لااقل یکی از DataPoint ها بین خوشه ها جابجا بشن. به عبارت دیگر، اگر در هر مرحله ای از خوشه بندی هیچ جابجایی انجام نشه، الگوریتم به کار خودش پایان میده. شرط آخر هم اینه که حلقه ی تکرارمون بیش از حد آستانه اجرا نشه. به عبارت دیگر، تا وقتی _threshold < maxIteration کار رو ادامه میدیم. چون ممکنه درون حلقه ی نامتنهایی گیر بیفتیم. حالا در هر مرحله از حلقه ی تکرار، اول مقدار _threshold رو یک واحد افزایش میدیم. بعد، متدهای UpdateDataPointMeans و UpdateClusterMembership رو اجرا می کنیم. یعنی هم میانگین خوشه ها هم حساب می کنیم و هم جابجایی DataPoint ها در خوشه ها رو انجام میدیم.
توی این قسمت می خوام در مورد آخرین قسمت از کدی که داریم صحبت کنم. کدی که تمامی قسمت های قبلی رو مورد استفاده قرار میده و در واقع درون Event Handler یک Button تعریف شده. این کد بسیار ساده است. لطفاً ببینید:
private void btnCluster_Click(object sender, EventArgs e)
{
InitilizeRawData();
_numberOfClusters = int.Parse(txtNumberOfClusters.Text);
//initialize the clusters (Setting indeces)
for (int i = 0; i < _numberOfClusters; i++) { _clusters.Add(new DataPoint(){Cluster = i}); } Cluster(); StringBuilder sb = new StringBuilder(); var group = _rawDataToCluster.GroupBy(s => s.Cluster).OrderBy(s => s.Key);
foreach (var g in group)
{
sb.AppendLine("Cluster # " + g.Key + ":");
foreach (var value in g)
{
sb.Append(value.ToString());
sb.AppendLine();
}
sb.AppendLine("------------------------------");
}
txtOutput.Text = sb.ToString();
}
}
لطفاً برای اینکه بدونید متدهای InitilizeRawData و Cluster چه کاری انجام میدن به قسمت های قبلی این آموزش رجوع کنید. حلقه ی for اول هم که داره به ازای داده های ورودی DataPoint تعریف می کنه و درون خوشه ها اضافه می کنه. قسمتی که بعد از تعریف sb اومده هم داره کالکشن _rawDataToCluster رو گروه بندی می کنه و نهایتاً خروجی رو با استفاده از حلقه ی foreach چاپ میکنه.
توی این سری آموزش ها از وبسایت پرووید، مرحله به مرحله و قدم به قدم الگوریتم خوشه بندی کا-میانگین رو در سی شارپ پیاده سازی کردیم. همین جا عرض کنم که صد در صد روش های مختلف و چه بسا بهتری برای این کار باید وجود داشته باشه ولی من سعی کردم از ساده ترین روشی که به ذهنم رسید استفاده کنم و بعد هم با شما به اشتراک بذارم. ضمناً می توانید پروژه ی این آموزش رو از مقاله ی انگلیسی این آموزش در سایت کدپراجکت دانلود کنید. موفق و پیروز باشید. یا حق.
بهترین و جامع ترین آموزش های برنامه نویسی و توسعه نرم افزار از سطح ابتدایی تا سطح میانی و سطح پیشرفته
تمامی حقوقی مادی و معنوی متعلق به گروه آموزشی پرووید است.