پیاده سازی الگوریتم های لوید و فورجی - قسمت دوم(مجموعه داده Diamond)

در مطالب قبلی از سری مباحث خوشه‌بندی در انتشارات شرکت علم داده ارزیاب به تئوری الگوریتم های خوشه‌بندی K-means پرداختیم. در قسمت اول پیاده سازی الگوریتم های لوید و فورجی نیز یک مثال آموزشی بر روی مجموعه داده‌ی Iris که یکی از ساده‌ترین و معروف‌ترین دیتاست های خوشه بندی هست رو مشاهده کردیم. در این مطلب قصد داریم دو الگوریتم لوید و فورجی را بر روی مجموعه داده الماس پیاده سازی و مقایسه کنیم.

قبل ازین که مطلب رو شروع کنم باید بگم مراحل خوشه‌بندی در این جا هم تقریبا مثل مجموعه داده Iris هست با این تفاوت که یک چالشی در خوشه‌بندی مجموعه داده الماس یا همون diamond وجود داره که باعث میشه تا یک قدم در خوشه‌بندی داده های تجاری و بیزنسی حرفه‌ای تر بشیم. پس قراره در این مطلب بیشتر به این چالش بپردازیم.

سری مباحث خوشه بندی

در ابتدا لازم می‌دونم بگم این مطلب جزء مطالب تخصصی‌تر هست و اگه دوست دارید پایه‌ای‌تر این مبحث رو دنبال کنید بهتون پیشنهاد می‌کنم سلسه زیر رو به ترتیب بخونید و البته اگه هم با مطلبی آشنایی دارید می‌تونید برید مطلب بعدی که براتون تازه‌تر هست:

1- یادگیری ماشین و مدل سازی آماری(شباهت ها و تفاوت ها)

2- یادگیری تحت نظارت و بدون نظارت در یادگیری ماشین در سه دقیقه

3- خوشه بندی چیست و چگونه عمل می‌کند؟

4- معرفی روش خوشه بندی K-means

5- الگوریتم های خوشه بندی لوید و فورجی(K-means)

6- الگوریتم های خوشه بندی هارتیگان-ونگ و مک‌کوئین (K-means)

7- پیاده سازی الگوریتم های لوید و فورجی - قسمت اول (مجموعه داده Iris)

معرفی مجموعه داده الماس یا Diamond

دومین مجموعه داده‌ای که به منظور پیاده سازی الگوریتم های لوید و فورجی در مبحث الگوریتم های خوشه‌بندی K-means مورد استفاده قرار گرفته؛ مجموعه داده الماس هاست. این مجموعه داده از 9 متغیر که ویژگی الماس ها را ثبت کرده؛ تشکیل شده است. قابل ذکر است که این مجموعه داده شامل 53940 مشاهده است و جدول زیر خلاصه از اطلاعات این متغیر ها را شرح می‌دهد:

(توی پرانتز اگه نمی‌دونید مجموعه داده یا دیتاست چیه یه سر به «مطلب داده کاوی چیست؟» بزنید?)

که نام متغیر ها به انگلیسی به ترتیب جدول از چپ به راست عبارتند از:

Carat, Cut, Color, Clarity, Price, x, y, z, Depth

برای درک بهتر این دیتاست هم 6 مشاهده اول رو می‌تونید توی جدول زیر ببینید:

مصور سازی دیتاست الماس

توی این بخش برای درک بهتر دیتاست، برخی از متغیر ها رو با چند تا نمودار ساده به تصویر کشیدم. این نکته رو باید اینجا اضافه کنم که قبل از این که بخوایم وارد مدل سازی بشیم خیلی خوبه که با دیتا ها کلنجار بریم و بشناسیمشون. شناخت روی داده ها به ما دید بهتر می‌ده که چه مدلی مناسبه و چطور می‌تونیم حداکثر اطلاعات رو ازش بکشیم بیرون. به نظر من هر دیتاست یه داستان برای گفتن داره. با مصور سازی مجموعه داده می‌تونیم یکم بیشتر باهاش دوست بشیم و درک بهتری از داستانی که می‌خواد برامون تعریف کنه، داشته باشیم. پس بریم چند تا نموداری که ممکنه توی درک دیتاست الماس به ما دید بهتری بده رو ببینیم:

با یک نگاه به نمودار هیستوگرام قیمت می‌توان دریافت که بیشتر الماس ها در این دیتاست قیمت گذاری پایینی به نسبت دیگر الماس ها دارند. و هرچی قیمت بالاتر می‌ره فراوانی الماس ها کاهش پیدا می‌کنه. این یعنی الماس های کمی هستند که قیمتی اند. با دیدن این نمودار این سوال بوجود میاد که الماس های گران‌تر چه ویژگی هایی دارند که فراوانی آن ها کمتر شده است؟

?برای کسایی که نمی‌دونند هیستوگرام چیه؟
فرض کنید شما در یک مطالعه، نمونه‌ای n تایی از یک جامعه می‌گیرید و متغیر پیوسته‌ای مثل سن دارید. در این صورت اگر شما بخواید مطلع بشید که فراوانی های متغیر سن در دیتاست نمونه شما به چه صورت است؛ ابتدا این متغیر را بازه بندی می‌کنید. مثلا از 15 تا 20، 20 تا 25، 25 تا 30 و 30 تا 45. بعد از این مرحله فراوانی مشاهدات را در دسته بندی ها بدست می‌آورید. مثلا در بازه 15 تا 20 در نمونه شما 5 نفر مشاهده شده‌اند و به همین ترتیب برای بقیه بازه ها.
هیستوگرام نموداریه که محور عمودی اون نشان دهنده فراوانی متغیر و محور افقی نشان دهنده بازه هایی از اون متغیر هست.
با رسم هیستوگرام می‌توان نگاهی کلی به این داشت که مشاهدات چگونه توزیع شده‌اند. البته که این نمودار بیشتر برای متغیر های پیوسته رسم می‌شه ولی به مواردی هم برخوردم که رسم اون برای متغیر های گسسته هم مفید بوده.
?بافت نگار معادل فارسی هیستوگرام است.

همانطور که در تصویر 1 نیز مشاهده کردید متغیر عمق تابعی از متغیر های x، y و z است که یعنی این متغیر تابعی از طول، عرض و عمق الماس است. پس شاید رسم هیستوگرام این متغیر دید خوبی به ما بده. در ادامه هیستوگرام متغیر عمق رسم شده:

با نگاه کلی به این هیستوگرام می‌توان فهمید که بیشترین فراوانی الماس ها در متغیر عمق حدودا 50 الی 57 میلی‌متر است. همچنین پراکندگی هایی نیز به چشم می‌خورد که گویای کم بودن فراوانی در عمق خیلی زیاد و یا خیلی کم است. نمی‌توان به طور قطعی گفت اما این هیستوگرام کمی متقارن است؛ در علم آمار می‌دانیم توزیع نرمال یکی از توزیع هایی است که خروجی هیستوگرامی داده های آن متقارن است. نرمال بودن داده ها از حوصله این بحث خارجه و فعلا توی این مطلب نمی‌خوام بهش بپردازم. شاید قسمت بشه و مطالب دیگه این مبحث رو بیشتر باز کنم.

در ادامه نمودار های جعبه ای 4 متغیر x، y، z و عیار در کنار یکدیگر رسم شده است:

نمودار جعبه‌ای این 4 متغیر به ما نشان می‌ده که هر کدوم ازین متغیر ها به چه میزان پراکندگی دارند و کدومشون داده های دورافتاده داره. مثلا اگه توی باکس پلات متغیر عیار دقت کنید می‌تونید متوجه بشید که داده های دور افتاده توی این متغیر بیشتره و اگه بیشتر به این نمودار دقت کنید می‌‎تونید متوجه بشید بین همه مشاهدات این دیتا ست یک مشاهده وجود داره که متغیر عیارش مقدار 5 رو اختیار کرده. اینجا برام جالب میشه که بدونم بقیه متغیر های این مشاهده مثل متغیر قیمت چه مقداری رو اختیار کردند. می‌تونند ربطی داشته باشند به هم؟ شاید شهودی و تجربی اکثرا معتقد باشند که خب هرچی عیار الماس بالاتر باشه قیمتش بیشتره ولی خب اگه نظر یک متخصص رو بخوان باید علمی تر از بقیه صحبت کنه و فقط از شهود و تجربه استنتاج نکنه. هم‌خطی و ارتباط بین متغیر ها شاید یه بحث جذاب باشه اینجا اما نمی‌خوام از بحث اصلی که خوشه‌بندی این دیتاست به روش K-means هست دور بشم. البته در ادامه شاید گریزی به این بحث هم زدیم. ?

چالش دیتاست الماس

همونطور که در ابتدای مطلب هم گفتم؛ پیاده‌سازی الگوریتم های خوشه‌بندی K-means بر روی دیتاست الماس کمی پیچیده‌تر از دیتاست Iris هست. اما چالش کار کجاست؟ یادتونه توی مطلب «معرفی روش خوشه‌بندی K-means» به معایب و مزایای این روش پرداختم؟ اونجا گفتم از معایب این روش اینه که باید تعداد k رو برای خوشه‌بندی به الگوریتم بدیم وگرنه الگوریتم نمی‌دونه در نهایت باید به چند خوشه برسه.

خب توی دیتاست Iris ما می‌دونستیم که ماهیت این دیتاست چیه. یعنی می‌دونستیم که 3 نوع گل از نژاد Iris هست. پس بعد ازین که برچسب های دیتاست رو حذف کردیم به الگوریتم های K-means مقدار 3 رو برای خوشه‌بندی کردن داده ها دادیم. چالش دیتاست الماس اینه که ما نمی‌دونیم ماهیتا چند نوع الماس داریم و باید k رو چند قرار بدیم. این مساله رایجی در دیتاست های تجاری هست که حل کردن اون باعث می‌شه یه لول در مسائل خوشه‌بندی k-means حرفه‌ای تر بشیم. ?✌

پیاده سازی الگوریتم لوید بر روی دیتاست الماس

خب برای پیاده سازی الگوریتم روی دیتاست الماس نیاز به دو مورد حیاتی داریم:

1- همه متغیر ها عددی باشند؛ چون الگوریتم های k-means مقادیر عددی رو قبول میکنن و ورودی شون باید دیتاستی باشه که همه متغیراش عددی باشند.

2- مقدار k رو بدونیم؛ چون یکی از ورودی های الگوریتم های k-means مقدار k هست و بدون دونستن اون الگوریتم نمی‌تونه خوشه‌بندی کنه. (برای این که چرا الگوریتم ها نمی‌تونن بدون دانستن k کار کنن پیشنهاد می‌کنم تئوری چگونگی کارکرد این الگوریتم ها رو در مطلب معرفی خوشه‌بندی k-means بخونید.)

1️⃣ خب مورد اول که چالش اساسی‌ای به حساب نمیاد و با چند خط کد میشه مقادیر اختیار شده در متغیر های کیفی رو عددی کرد. کد های برنامه R برای این که کامپیوتر بفهمه باید عددی کنه متغیر ها رو به صورت زیر هست:

# the data has been numeric to use algorithms
# so we have this codes:
> x = as.numeric(diamond_data$x)
> y = as.numeric(diamond_data$y)
> z = as.numeric(diamond_data$z)
> carat = as.numeric(diamond_data$carat)
> price = as.numeric(diamond_data$price)
> depth = as.numeric(diamond_data$depth)
> cut = as.numeric(diamond_data$numeric_cut)
> color = as.numeric(diamond_data$numeric_color)
> clarity = as.numeric(diamond_data$numeric_clarity)
> dia_data = data.frame(x,y,z,carat,price,depth,cut,color,clarity)
> View(dia_data)

البته برای همه متغیر ها نیاز نبود دستور as.numeric رو بزنیم ولی اینجا احتیاط شده و برای همه متغیر ها ازین دستور استفاده شده. کد بهینه‌تر شده به این صورته که فقط برای سه متغیر cut، color و clarity ازین دستور استفاده می‌شد؛ چون بقیه متغیر ها عددی هستند و فقط این متغیر ها کیفی اسمی اند(تصویر 2).

2️⃣ خب حالا به چالش دوم بپردازیم که یه چالش اساسی‌تر هست؛ مقدار k رو چند بگیریم؟ توی مجموعه داده هایی که ما شناخت کمی داریم بهترین کار اینه که چند تا k رو در نظر بگیریم. یعنی مثلا یه بار k رو 5 بذاریم، یه بار 10، یه بار 20 و بعد نتایج رو باهم مقایسه کنیم تا جایی که مطمئن شیم kای که برای خوشه‌بندی انتخاب کردیم تقریبا استنتاج خوبی رو به ما می‌ده و می‌تونیم ازش خروجی های مفیدی رو بدست بیاریم. باید بگم اگه هیچ ایده ای نسبت به تعداد خوشه های داده هاتون ندارید و حتی هیچ تحقیق پیشینی هم در دستتون نیست که بتونید به کمک اون حدسایی بزنید؛ این قسمت تجربیه و با اجرا و مقایسه می‌شه به نتایج قابل قبولی رسید.

توی این مثال یعنی دیتاست الماس من باتوجه به تعداد k های متفاوتی که الگوریتم ها رو اجرا کردم متوجه شدم که تعداد 5 خوشه بهینه هست و اگه کمتر بشه اطلاعات از دست میدیم و اگه بیشتر بشه یک خوشه به چندین خوشه تجزیه میشه.

?پس من در ادامه کار مقدار k رو برابر با 5 در نظر می‌گیرم و الگوریتم لوید رو پیاده‌سازی می‌کنم. کد های R برای پیاده‌سازی الگوریتم لوید بر روی دیتاست الماس به صورت زیر هست:

#Lloyd Algorithm
> Lloyd_D1 = kmeans(dia_data, 5, algorithm =&quotLloyd&quot)

قبل‌تر در مطلب الگوریتم های خوشه‌بندی لوید و فورجی به معرفی تمامی ورودی ها و همچنین نوع خروجی های کد بالا که چی هستند و چی رو نشون میدن پرداختم. پس اینجا فقط خروجی اجرای الگوریتم رو می‌بینیم و تفسیر می‌کنیم.

خب چیزی که مهمه جدول میانگین های خوشه‌ای هست که کد اون به صورت زیر هست:

> Lloyd_D1$centers

خروجیش هم به صورت یک جدول مرتب شده در تصویر زیر اوردم:

چیزی که از جدول میشه برداشت کرد اینه که باتوجه به واریانس بین خوشه ها در هر متغیر، متغیر عمق یا depth در خوشه بندی نسبت به دیگر متغیر ها تاثیر کمتری داشته است.

برای این که بدونیم فراوانی هر کدوم از مشاهدات در خوشه ها چطور بوده کد زیر رو به همراه نتایجش داریم:

> table(Lloyd_D1$cluster)
1                 2              3            4             5
11490    10424    18068     8933     5025

از خروجی ای که به ما نشون میده می‌تونیم بفهمیم که 11490 مشاهده به خوشه اول، 10424 مشاهده به خوشه دوم، 18068 مشاهده به خوشه سوم، 8933 مشاهده به خوشه چهارم و 5025 مشاهده به خوشه پنجم تعلق گرفته است.

برای اطلاع از تعداد تکرار الگوریتم هم کد زیر رو داریم:

> Lloyd_D1$iter
[1] 11

که خروجی نشان دهنده این است که برای رسیدن به این خوشه‌بندی الگوریتم لوید 11 بار تکرار شده است.

در ادامه مطلب همین روند را برای الگوریتم فورجی پیاده سازی می‌کنیم و نتایج این دو را با یکدیگر مقایسه خواهیم کرد.

پیاده سازی الگوریتم فورجی بر روی دیتاست الماس

خب همانند مراحل بالا با در نظر گرفتن k=5 مراحل پیاده سازی را با الگوریتم فورجی اجرا می‌کنیم. کد های پیاده سازی الگوریتم فورجی به صورت زیر است:

>#Forgy Algorithm
> Forgy_D = kmeans(dia_data, 5, algorithm =&quotForgy&quot)

با توجه به کد های بالا داده ها به پنج خوشه تقسیم بندی شده‌اند که میانگین مشخصه های هر خوشه در جدول زیر آورده شده است:

همچنین دستور های table و iter را نیز برای دانستن فراوانی خوشه ها و تعداد تکرار الگوریتم فورجی بر روی دیتاست الماس، به کار می‌بریم:

 > table(Forgy_D$cluster)
1                     2               3                4                 5
20848         3802       11068       6160      12062
> Forgy_D$iter
[1] 11

باتوجه به خروجی این کد ها، تعداد تکرار در اجرای الگوریتم فورجی نیز برابر با 11 شده است و درحالت کلی از 53940 داده، 20848 مشاهده به خوشه 1، 3802 مشاهده به خوشه 2، 11068 مشاهده به خوشه 3، 6160 مشاهده به خوشه 4 و 12062 مشاهده به خوشه 5 ام تعلق گرفته است.

مقایسه پیاده سازی الگوریتم های لوید و فورجی بر روی دیتاست الماس

با مقایسه نتایج جدول میانگین مشخصه های هر خوشه در اجرای الگوریتم لوید و فورجی بر روی مجموعه داده الماس ها می‌توان دریافت که 2 خوشه در این الگوریتم ها خروجی نزدیک به هم داده‌اند. تعداد تکرار در هر دو الگوریتم نیز با یک دیگر برابر است. در جدول زیر سعی شده خروجی این دو الگوریتم با یکدیگر مقایسه شود:

?قابل ذکر است که خوشه هایی که رنگ هایلایت یکسان دارند بیانگر نزدیک بودن این خوشه ها از نظر خوشه‌بندی در دو الگوریتم است.

?یک نکته‌ای که باید اینجا بگم اینه که ما در ابتدا فرض کردیم هیچ دانشی نسبت به دیتاست نداریم و بعد شروع کردیم به دوست شدن باهاش و فهمیدنش. توی این مطلب من فرض کردم هیچی درباره کاهش بعد هم نمیدونیم و صد البته مساله ما در اینجا صرفا پیاده سازی الگوریتم های k-means هست و هیچ وقت درباره این که این دیتاست چطوری به دست ما رسیده و قبلش چه شناخت هایی باید حاصل می‌شده و چه فرایندی باید طی می‌شده بحث نکردیم. البته من سعی کردم یک دید کلی در مطلب «داده کاوی چیست؟» رو ارائه بدم.
? بهرحال این مهمه که بدونیم در این مطلب ما هیچ پیش زمینه‌ای از کاهش بعد، هم‌بستگی بین مغیر ها، رگرسیون و این دست مسائل که روابط بین متغیر های یک دیتاست رو به ما نشان می‌دهند نداریم.

✅با فرض بر دانستن نکته بالا مطلب رو ادامه می‌دیم.

با مقایسه واریانس های میانگین خوشه ها در 9 متغیر عمق، قیمت، عیار، x، y، z، برش، رنگ و شفافیت در 2 الگوریتم، می‌توان دریافت متغیر های قیمت و x و y بیشترین تاثیر و متغیر عمق کمترین تاثیر را در این خوشه‌بندی گذاشته‌ اند. کد های برنامه R برای مقایسه واریانس های خوشه‌ای این 9 متغیر در 2 الگوریتم ذکر شده به صورت زیر است:

> # comparing varibles with variance
> algorithm_D = list(Lloyd_D1$centers,Forgy_D$centers)
> x = c()
> y = c()
> z = c()
> carat = c()
> price = c()
> depth = c()
> cut1= c()
> color = c()
> clarity = c()

> for(name in 1:2){
AL_D = algorithm_D[name]
 x[name] = var(AL_D[[1]][1:5])
 y[name] = var(AL_D[[1]][6:10])
z[name] = var(AL_D[[1]][11:15])
carat[name] = var(AL_D[[1]][16:20])
price[name] = var(AL_D[[1]][21:25])
depth[name] = var(AL_D[[1]][26:30])
cut1[name] = var(AL_D[[1]][31:35])
 color[name] = var(AL_D[[1]][36:40])
clarity[name] = var(AL_D[[1]][41:45]) }

> x
[1] 1.442573        1.536787 

> y
[1] 1.431015       1.529341

> z
[1] 0.5393813      0.5768793 

> carat
[1] 0.3189001      0.3208689 

> price
[1] 33073205       30712068 

> depth
[1] 0.007042929      0.004078505

> cut1
[1] 0.02113756     0.02125287 

> color
[1] 0.1483196     0.1569140 

> clarity
[1] 0.2097639      0.2744841

بنابر این نتیجه در ادامه با تمرکز بر سه متغیر x و y و قیمت، نمودار های نقطه‌ای دسته‌بندی ها را در این 2 الگوریتم رسم کرده و مقایسه می‌کنیم. برای رسم نمودار ها همانند گذشته از کتابخانه ggplot استفاده شده است.

نمودار نقطه‌ای الگوریتم لوید

در این نمودار ها می‌توان دسته بندی هایی که الگوریتم لوید بر روی داده ها انجام داده را مشاهده کرد:

1- نمودار قیمت در برابر x یا طول الماس:

2- نمودار قیمت در برابر y:

در هر دو نمودار آورده شده مشاهده می‌شود که متغیر قیمت تاثیری اساسی در خوشه‌بندی گذاشته است.

نمودار های نقطه‌ای الگوریتم فورجی

در این نمودار ها می‌توان دسته بندی هایی که الگوریتم فورجی بر روی داده ها انجام داده را مشاهده کرد. البته که در ادامه مشاهده خواهید کرد نمودار ها تفاوت زیادی با یکدیگر ندارند.

1- نمودار قیمت در برابر x:

1- نمودار قیمت در برابر y:

در آخر با توجه به جداول میانگین های خوشه‌ای در هر الگوریتم و همچنین نمودار های نقطه‌ای رسم شده می‌توان دریافت که در عمل اجرای این الگوریتم ها بر روی این مجموعه داده نتایج چندان متفاوتی با یکدیگر ندارند و در هر دو الگوریتم متغیر قیمت بیشترین تاثیر را در خوشه بندی دارد و باز هم اینجا تاکید می‌کنم بررسی این دیتاست صرفا یک مثال هست که به شما ایده بده تا روی دیتاست هاتون الگوریتم های k-means رو پیاده سازی و مقایسه کنید.

این مطلب آخرین مطلب از سری خوشه‌بندی k-means نیست و قطعا مطالب دیگه‌ای هم به اشتراک خواهم گذاشت. اما تا به اینجا می‌شه گفت به خوبی تونستیم این مبحث رو پوشش بدیم. احتمالا در مطالب آینده از سری مباحث دیگه گریزی به این مطالب خواهم زد و خواهم گفت که اگر چه مبحثی رو می‌دونستیم کار کردن با این الگوریتم های خوشه‌بندی بر روی دیتاست ها برامون راحت‌تر می‌شد.

??‍?حسن ختام این مطلب یه تجربه هم بگم بهتون. الگوریتم های k-means برای مجموعه داده ها با حجم بالا غالبا ریسورس بالایی می‌خواد و اگه شما یه دیتاست بزرگ دارید و می‌خواید خوشه بندیش کنید؛ بهتره اول به فکر کاهش بعد یا پیاده‌سازی الگوریتم های بهینه‌تر باشید.

?اگر نظر یا کامنتی دارید خوشحال می‌شم مطرح کنید?