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

در مطالب قبلی از سری مباحث خوشه‌بندی در انتشارات شرکت علم داده ارزیاب به تئوری الگوریتم های خوشه‌بندی K-means پرداختیم. در قسمت اول پیاده سازی الگوریتم های لوید و فورجی نیز یک مثال آموزشی بر روی مجموعه داده‌ی Iris که یکی از ساده‌ترین و معروف‌ترین دیتاست های خوشه بندی هست رو مشاهده کردیم. در این مطلب قصد داریم دو الگوریتم لوید و فورجی را بر روی مجموعه داده الماس پیاده سازی و مقایسه کنیم. قبل ازین که مطلب رو شروع کنم باید بگم مراحل خوشه‌بندی در این جا هم تقریبا مثل مجموعه داده Iris هست با این تفاوت که یک چالشی در خوشه‌بندی مجموعه داده الماس یا همون diamond وجود داره که باعث میشه تا یک قدم در خوشه‌بندی داده های تجاری و بیزنسی حرفه‌ای تر بشیم. پس قراره در این مطلب بیشتر به این چالش بپردازیم.قسمت دوم پیاده سازی الگوریتم های لوید و فورجی - مجموعه داده Diamondسری مباحث خوشه بندیدر ابتدا لازم می‌دونم بگم این مطلب جزء مطالب تخصصی‌تر هست و اگه دوست دارید پایه‌ای‌تر این مبحث رو دنبال کنید بهتون پیشنهاد می‌کنم سلسه زیر رو به ترتیب بخونید و البته اگه هم با مطلبی آشنایی دارید می‌تونید برید مطلب بعدی که براتون تازه‌تر هست:1- یادگیری ماشین و مدل سازی آماری(شباهت ها و تفاوت ها)2- یادگیری تحت نظارت و بدون نظارت در یادگیری ماشین در سه دقیقه3- خوشه بندی چیست و چگونه عمل می‌کند؟4- معرفی روش خوشه بندی K-means5- الگوریتم های خوشه بندی لوید و فورجی(K-means)6- الگوریتم های خوشه بندی هارتیگان-ونگ و مک‌کوئین (K-means)7- پیاده سازی الگوریتم های لوید و فورجی - قسمت اول (مجموعه داده Iris)معرفی مجموعه داده الماس یا Diamondدومین مجموعه داده‌ای که به منظور پیاده سازی الگوریتم های لوید و فورجی در مبحث الگوریتم های خوشه‌بندی K-means مورد استفاده قرار گرفته؛ مجموعه داده الماس هاست. این مجموعه داده از 9 متغیر که ویژگی الماس ها را ثبت کرده؛ تشکیل شده است. قابل ذکر است که این مجموعه داده شامل 53940 مشاهده است و جدول زیر خلاصه از اطلاعات این متغیر ها را شرح می‌دهد:تصویر1: جدول معرفی دیتاست الماس ها(توی پرانتز اگه نمی‌دونید مجموعه داده یا دیتاست چیه یه سر به «مطلب داده کاوی چیست؟» بزنید?)که نام متغیر ها به انگلیسی به ترتیب جدول از چپ به راست عبارتند از:Carat, Cut, Color, Clarity, Price, x, y, z, Depthبرای درک بهتر این دیتاست هم 6 مشاهده اول رو می‌تونید توی جدول زیر ببینید:تصویر 2: 6 مشاهده اول مجموعه داده الماس هامصور سازی دیتاست الماستوی این بخش برای درک بهتر دیتاست، برخی از متغیر ها رو با چند تا نمودار ساده به تصویر کشیدم. این نکته رو باید اینجا اضافه کنم که قبل از این که بخوایم وارد مدل سازی بشیم خیلی خوبه که با دیتا ها کلنجار بریم و بشناسیمشون. شناخت روی داده ها به ما دید بهتر می‌ده که چه مدلی مناسبه و چطور می‌تونیم حداکثر اطلاعات رو ازش بکشیم بیرون. به نظر من هر دیتاست یه داستان برای گفتن داره. با مصور سازی مجموعه داده می‌تونیم یکم بیشتر باهاش دوست بشیم و درک بهتری از داستانی که می‌خواد برامون تعریف کنه، داشته باشیم. پس بریم چند تا نموداری که ممکنه توی درک دیتاست الماس به ما دید بهتری بده رو ببینیم:تصویر3: هیستوگرام متغیر قیمتبا یک نگاه به نمودار هیستوگرام قیمت می‌توان دریافت که بیشتر الماس ها در این دیتاست قیمت گذاری پایینی به نسبت دیگر الماس ها دارند. و هرچی قیمت بالاتر می‌ره فراوانی الماس ها کاهش پیدا می‌کنه. این یعنی الماس های کمی هستند که قیمتی اند. با دیدن این نمودار این سوال بوجود میاد که الماس های گران‌تر چه ویژگی هایی دارند که فراوانی آن ها کمتر شده است؟ ?برای کسایی که نمی‌دونند هیستوگرام چیه؟فرض کنید شما در یک مطالعه، نمونه‌ای n تایی از یک جامعه می‌گیرید و متغیر پیوسته‌ای مثل سن دارید. در این صورت اگر شما بخواید مطلع بشید که فراوانی های متغیر سن در دیتاست نمونه شما به چه صورت است؛ ابتدا این متغیر را بازه بندی می‌کنید. مثلا از 15 تا 20، 20 تا 25، 25 تا 30 و 30 تا 45. بعد از این مرحله فراوانی مشاهدات را در دسته بندی ها بدست می‌آورید. مثلا در بازه 15 تا 20 در نمونه شما 5 نفر مشاهده شده‌اند و به همین ترتیب برای بقیه بازه ها.هیستوگرام نموداریه که محور عمودی اون نشان دهنده فراوانی متغیر و محور افقی نشان دهنده بازه هایی از اون متغیر هست. با رسم هیستوگرام می‌توان نگاهی کلی به این داشت که مشاهدات چگونه توزیع شده‌اند. البته که این نمودار بیشتر برای متغیر های پیوسته رسم می‌شه ولی به مواردی هم برخوردم که رسم اون برای متغیر های گسسته هم مفید بوده.?بافت نگار معادل فارسی هیستوگرام است.همانطور که در تصویر 1 نیز مشاهده کردید متغیر عمق تابعی از متغیر های x، y و z است که یعنی این متغیر تابعی از طول، عرض و عمق الماس است. پس شاید رسم هیستوگرام این متغیر دید خوبی به ما بده. در ادامه هیستوگرام متغیر عمق رسم شده:تصویر4: هیستوگرام متغیر عمقبا نگاه کلی به این هیستوگرام می‌توان فهمید که بیشترین فراوانی الماس ها در متغیر عمق حدودا 50 الی 57 میلی‌متر است. همچنین پراکندگی هایی نیز به چشم می‌خورد که گویای کم بودن فراوانی در عمق خیلی زیاد و یا خیلی کم است. نمی‌توان به طور قطعی گفت اما این هیستوگرام کمی متقارن است؛ در علم آمار می‌دانیم توزیع نرمال یکی از توزیع هایی است که خروجی هیستوگرامی داده های آن متقارن است. نرمال بودن داده ها از حوصله این بحث خارجه و فعلا توی این مطلب نمی‌خوام بهش بپردازم. شاید قسمت بشه و مطالب دیگه این مبحث رو بیشتر باز کنم.در ادامه نمودار های جعبه ای 4 متغیر x، y، z و عیار در کنار یکدیگر رسم شده است:تصویر5: نمودار جعبه‌ای متغیر های طول، عرض، عمق و عیار الماسنمودار جعبه‌ای این 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خروجیش هم به صورت یک جدول مرتب شده در تصویر زیر اوردم:تصویر 6: جدول میانگین های خوشه‌ای یا cluster means برای الگوریتم لویدچیزی که از جدول میشه برداشت کرد اینه که باتوجه به واریانس بین خوشه ها در هر متغیر، متغیر عمق یا 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)با توجه به کد های بالا داده ها به پنج خوشه تقسیم بندی شده‌اند که میانگین مشخصه های هر خوشه در جدول زیر آورده شده است:تصویر 7: جدول میانگین های خوشه‌ای برای الگوریتم فورجیهمچنین دستور های 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 خوشه در این الگوریتم ها خروجی نزدیک به هم داده‌اند. تعداد تکرار در هر دو الگوریتم نیز با یک دیگر برابر است. در جدول زیر سعی شده خروجی این دو الگوریتم با یکدیگر مقایسه شود: ?قابل ذکر است که خوشه هایی که رنگ هایلایت یکسان دارند بیانگر نزدیک بودن این خوشه ها از نظر خوشه‌بندی در دو الگوریتم است.تصویر8: مقایسه جدول میانگین های خوشه‌ای حاصل از اجرای دو الگوریتم لوید و فورجی?یک نکته‌ای که باید اینجا بگم اینه که ما در ابتدا فرض کردیم هیچ دانشی نسبت به دیتاست نداریم و بعد شروع کردیم به دوست شدن باهاش و فهمیدنش. توی این مطلب من فرض کردم هیچی درباره کاهش بعد هم نمیدونیم و صد البته مساله ما در اینجا صرفا پیاده سازی الگوریتم های 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 یا طول الماس:تصویر9: مقایسه متغیر قیمت در برابر متغیر X یا طول الماس2- نمودار قیمت در برابر y:تصویر 10: مقایسه متغیر قیمت در برابر متغیر y یا عرض الماسدر هر دو نمودار آورده شده مشاهده می‌شود که متغیر قیمت تاثیری اساسی در خوشه‌بندی گذاشته است. نمودار های نقطه‌ای الگوریتم فورجیدر این نمودار ها می‌توان دسته بندی هایی که الگوریتم فورجی بر روی داده ها انجام داده را مشاهده کرد. البته که در ادامه مشاهده خواهید کرد نمودار ها تفاوت زیادی با یکدیگر ندارند.1- نمودار قیمت در برابر x:تصویر 11: مقایسه متغیر قیمت در برابر متغیر x یا طول الماس1- نمودار قیمت در برابر y:تصویر 12: مقایسه متغیر قیمت در برابر متغیر y یا عرض الماس در آخر با توجه به جداول میانگین های خوشه‌ای در هر الگوریتم و همچنین نمودار های نقطه‌ای رسم شده می‌توان دریافت که در عمل اجرای این الگوریتم ها بر روی این مجموعه داده نتایج چندان متفاوتی با یکدیگر ندارند و در هر دو الگوریتم متغیر قیمت بیشترین تاثیر را در خوشه بندی دارد و باز هم اینجا تاکید می‌کنم بررسی این دیتاست صرفا یک مثال هست که به شما ایده بده تا روی دیتاست هاتون الگوریتم های k-means رو پیاده سازی و مقایسه کنید.این مطلب آخرین مطلب از سری خوشه‌بندی k-means نیست و قطعا مطالب دیگه‌ای هم به اشتراک خواهم گذاشت. اما تا به اینجا می‌شه گفت به خوبی تونستیم این مبحث رو پوشش بدیم. احتمالا در مطالب آینده از سری مباحث دیگه گریزی به این مطالب خواهم زد و خواهم گفت که اگر چه مبحثی رو می‌دونستیم کار کردن با این الگوریتم های خوشه‌بندی بر روی دیتاست ها برامون راحت‌تر می‌شد.??‍?حسن ختام این مطلب یه تجربه هم بگم بهتون. الگوریتم های k-means برای مجموعه داده ها با حجم بالا غالبا ریسورس بالایی می‌خواد و اگه شما یه دیتاست بزرگ دارید و می‌خواید خوشه بندیش کنید؛ بهتره اول به فکر کاهش بعد یا پیاده‌سازی الگوریتم های بهینه‌تر باشید.?اگر نظر یا کامنتی دارید خوشحال می‌شم مطرح کنید?