X
تبلیغات
کالج کارآفرینی تیوان

TDC : Text Document Clustring

مقایسه عملکرد الگوریتم 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 به cj (مرکز خوشة 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 مرکز

 

نظرات (1)
نام :
ایمیل : [پنهان میماند]
وب/وبلاگ :
برای نمایش آواتار خود در این وبلاگ در سایت Gravatar.com ثبت نام کنید. (راهنما)
با سلام
تشکر بابت وبلاگ پر محتوا و کاربردیتون .بسار مفید بود
ما هم وبلاگی در زمینه سئو و طراحی سایت داریم
لطفا در صورت تمایل برای تبادل لینک دوطرفه با ما در ارتباط باشید
http://kianartco.bigsite.ir/
چهارشنبه 6 دی 1396 ساعت 12:29
امتیاز: 0 0