مقایسه عملکرد الگوریتم K-Means و K-Means ++

الگوریتم K-Means

خوشه­بندی که به آن یادگیری بدون ناظر نیز گفته می­شود تعداد خوشه­ها در آن مشخص نیست. خوشه­بندی در واقع یک عملیات غیرنظارتی می­باشد. این عملیات هنگامی استفاده می­شود که ما به دنبال یافتن گروه­هایی از داده­های مشابه می­باشیم بدون اینکه از قبل یک پیش­بینی در مورد شباهت­های موجود داشته باشیم. هر خوشه شامل مجموعه­ای از اشیاء داده­ای است که به هم شبیه هستند اما با اشیاء خارج از آن متفاوت می­باشند. یکی از روش‌های معروف در زمینه خوشه­بندی، الگوریتم K-Means می‌باشد [5]. الگوریتم K-Means علی‌رغم آنکه ساده است یک روش پایه برای بسیاری از روش‌های خوشه‌بندی محسوب می‌شود. برای این الگوریتم شکل­های مختلفی بیان شده است. ولی همه آنها دارای روالی تکراری هستند که برای تعدادی ثابت از خوشه‌ها سعی در تخمین موارد زیر دارند [5]:

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

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

الگوریتم K-Means ابتدا K عضو(که K تعداد خوشه­ها است) را به صورت تصادفی از میان N عضو انتخاب می­نماید و آنها را به عنوان مراکز خوشه­ها در نظر می­گیرد. سپس N-K عضو باقیمانده به نزدیکترین خوشه تخصیص می­یابند. بعد از تخصیص همه اعضا مجدداً مراکز خوشه­ها محاسبه شده و اعضا با توجه به میزان نزدیکی (شباهت) به یکی از خوشه‌ها تخصیص می­یابند و این کار تا زمانی که مراکز خوشه­ها ثابت بمانند، ادامه می­یابد. با تکرار همین روال می‌توان در هر تکرار با میانگین‌گیری از داده‌ها مراکز جدیدی برای آنها محاسبه کرد و مجدداً داده‌ها را به خوشه‌های جدید نسبت داد.

الگوریتم  K-Meansیکی از روش­های رایج خوشه­بندی می­باشد که علیرغم مزایای بسیار از جمله سرعت بالا و سهولت پیاده­سازی، در دام بهینه محلی قرار نمی­گیرد و می­تواند جواب بهینه برای مسئه مورد نظر را تولید ذنماید. تابع هدف در الگوریتم K-Means طبق معادله(2-3) تعریف شده است.

 

  

برای اینکه بتوانیم داده­ها را خوشه­بندی کنیم باید بتوانیم میزان شباهت آنها را بدست آوریم. اینکار معمولاً به صورت غیرمستقیم انجام می­شود، یعنی با استفاده از معیارهای اندازه­گیری فاصله، میزان تفاوت بین دو شیء بدست می­آید بطوریکه اشیاء شبیه به هم دارای فاصله کمتری خواهند بود. در معادله(2-3)، پارامتر k تعداد نقاط مراکز خوشه­ها است. هر نمونه داده به خوشه‌ای که مرکز آن خوشه کمترین فاصله تا آن داده را داراست، نسبت داده‌ می‌شود. و || || معیار فاصله نقطه x به c_j (مرکز خوشة jام) است. برای مثال خوشه­بندی برمبنای K-Means قصد داریم که داده­های جدول(2-4) را خوشه­بندی کنیم. جدول(2-4)، شامل 8 نمونه است که شامل مقادیری مختلفی هستند.

جدول(2-4): نمایش نمونه­ها برای خوشه­بندی

خوشه­بندی	Y	X	ردیف
1	72	185	1
2	56	170	2
2	60	168	3
1	68	179	4
1	72	182	5
1	77	188	6
1	73	186	7
2	60	168	8

در ابتدا تعداد خوشه­ها را برابر دو درنظر می­گیریم. یعنی خوشه k1(185,72) و k2(170,56) از جدول(2-5) را به عنوان مراکز داده­ها انتخاب می­کنیم.

جدول(2-5): انتخاب مراکز خوشه­ها به منظور خوشه­بندی

Y	X	Cluster
72	185	k1
56	170	k2

سپس برای پیدا کردن فاصله اقلیدسی بین نمونه­ها از معادله(2-4) استفاده می­کنیم.

(2-4)

سپس فاصله بین خوشه­ها با یکدیگر محاسبه می­شود.

(2-5)
(2-6)

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

جدول(2-6): انتساب نمونه­ها به خوشه­ها

خوشه­بندی	Y	X	Cluster
1	21.93	0	k1
2	0	21.93	k2

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

(168,60)
[(170+168)/2=169] [(60+56)/2=58]→Update Cluster2
(179,68)
[(185+179)/2=182] [(72+68)/2=70]→ Update Cluster1
(182,72)
[(182+182)/2=182] [(70+72)/2=71]→ Update Cluster1
(188,77)
[(182+188)/2=185] [(71+77)/2=74]→ Update Cluster1
(186,73)
[(185+186)/2=185] [(74+73)/2=73]→ Update Cluster1
(165,60)
[(168+165)/2=166] [(56+60)/2=58]→ Update Cluster1

در جدول(2-7)، بروزرسانی مرکز خوشه­ها نشان داده شده است. با محاسبه هر نمونه یک مقدار جدید برای مرکز خوشه­ها پیدا می­شوند  و مرکز خوشه بروزرسانی می­شود. مرکز خوشه­ها بهینه­ترین نقطه را به منظور همبستگی بین نمونه­ها کشف می­کند.

جدول(2-7): بروزرسانی مراکز خوشه­ها

Update		Y	X	Cluster
Y	X
70	182	72	185	k1
71	182
74	185
73	185
58	168	56	170	k2
58	166

در شکل(2-12)، نحوه خوشه­بندی نمونه­ها با مرکزیت خوشه نشان داده شده است. در هر مرحله مرکز خوشه بروزرسانی می­شود و برای نمونه­ها یک مقدار جدید به عنوان مرکز و فاصله بین دو خوشه در نظر گرفته می­شود.

شکل(2-12): نمایش خوشه­بندی نمونه­ها با مرکزیت خوشه

در شکل(2-12)، داده­های موجود در یک خوشه بیشترین نزدیکی را به هم دارند و داده­های موجود در دو خوشه متفاوت، بیشترین فاصله را با هم دارند.

الگویتم K-Means++

الگوریتم k-means++ [37] روشی برای انتخاب تصادفی مقادیر اولیه مراکز خوشه­ها در الگوریتم خوشه­بندی k-means است. این الگوریتم در سال 2007 توسط دیوید آرتور و سرگئی واسیلویتسکی پیشنهاد شد. لذا الگوریتم K-means++ مراکز اولیه خوشه­ها را به صورت تصادفی انتخاب می­کند.

جدول(2-8): مقایسه الگوریتم k-means و k-means++

k-means	k-means++
1) یک مجموعه از نقاط داده X={x1,x2,…,xn} 2) تعداد خوشه­ها برابر k 3) محاسبه مراکز خوشه­ها C={c1,c2,…,ck} 4) فاصله از x به نزدیکترین مرکز در C برابر= d(x,C) 5) هدف تابع برازندگی مینیمم مقدار  است.	1) انتخاب اولین مرکز(c1) به صورت تصادفی در میان داده­ها (x) 2) انتخاب مرکز جدید(ci)، انتخاب کردن  برمبنای پارامتر D(x) کوتاه­ترین فاصله از نقاط داده به نزدیکترین مرکز است. 3) تکرار مراحل به منظور یافتن k مرکز