خوشه بندی به روش K-Means در R

یکی از روش های معتبر خوشه بندی، خوشه بندی K-mean است که بر اساس کمترین فاصله های هر داده از مرکز یک خوشه (میانگین) خوشه بندی را انجام می دهد. در نرم افزار R ، با استفاده از تابع kmeans() همان طور از اسم آن مشخص است داده های خود را به روش k-means خوشه بندی کرده تا آن ها را در k گروه بگنجانیم به قسمی که مجموع مربعات فاصله ی داده ها از مراکز خوشه ی خود حداقل گردد. در واقع این روش خوشه بندی از نقاط داده ها مجموعه هایی مجزا می سازد به طوری که در هر مجموعه نقاط داده ها به مرکز خوشه نزدیک اند.

الگوریتم K-means : الگوریتم K-means دارای یک پارامتر K است که نماینده ی تعداد خوشه‌های مد نظرمان است.‌ الگوریتم K-means پایه به صورت زیر است: 1- مقدار دهی اولیه: k نقطه را به عنوان مراکز اولیه در نظر می گیرد. 2- تکرار 3- K خوشه را با تخصیص تمام نقاط به نزدیک ترین مرکز تشکیل می دهد. 4- مراکز هر خوشه دوباره محاسبه می شوند. 5- تا زمانی که مراکز تغییر نکنند.

معمولا مرکز خوشه‌های اولیه به صورت تصادفی از میان نمونه‌های اولیه انتخاب می شوند. بنابراین خوشه های به دست آمده در خوشه بندی ها منحصر به فرد نیستند چرا که مرکز خوشه‌های اولیه در دو خوشه‌بندی مستقل K-means می‌توانند متفاوت باشند.‌ در الگوریتم K-means می‌توان از معیار‌های فاصله‌ی گوناگون بهره گرفت و خوبی یا بدی بکارگیری آن معیار بستگی دارد به نوع داده‌هایی که قرار است خوشه بندی گردند. دستور کلی خوشه بندی K-میانگین در R به صورت زیر است:

kmeans(x, centers, iter.max=10, nstart=1, algorithm=c(“Hartigan-Wong”, “Lloyd” , “Forgy”, “MacQuenn”)) المان ها: X ماتریس عددی از داده ها؛ یا چیزی که می تواند جای یک ماتریس قرار گیرد ( مثل: یک بردار عددی از داده ها یا یک دیتا فریم با ستون های عددی)

Centers تعداد خوشه ها یعنی k یا مجموعه ای از خوشه های (مجزای) اولیه را مشخص می کند. چنانچه یک عدد داشته باشیم یک مجموعه ی تصادفی از سطرهای (مجزا) در X را به عنوان مراکز اولیه در نظر می گیرد.

iter.max حداکثر تعداد تکرار مجاز nstart چنانچه centers یک عدد باشد، تعداد مجموعه های تصادفی که باید انتخاب شوند را نشان می دهد.

algorithm خوشه بندی k-میانگین خود برای اجرا از الگوریتم های متفاوتی استفاده می کند این المان برای تابع ()kmean الگوریتم خاصی را مشخص می کند.

این تابع به طور پیش فرض الگوریتم هارتیگان و ونگ را در خوشه بندی پیش می گیرد اما ممکن است بسیاری از نویسندگان روش های دیگر K-means را ترجیح دهند. مثل الگوریتم مک کویین که اغلب به سایر الگوریتم ها ترجیح داده می شود. اما به طور کلی الگوریتم هارتیگان و ونگ نسبت به بقیه بهتر عمل می کند، با این حال استفاده از یک شروع nstart>1 تصادفی معمولا توصیه می شود. برای سهولت در برنامه ریزی معمولا K=1 مجاز است.

با یک مثال دو بعدی چگونگی استفاده از این تابع را نمایش می دهیم:

# دو ماتریس تصادفی تولید شده را با 50 سطر و دوستون از سطر با هم ترکیب می کنیم که اولین ماتریس حاوی 100 عدد تصادفی تولید شده ی نرمال با میانگین 0 و انحراف معیار 0.3 و ماترسی دوم حاوی 100 عدد تصادفی تولید شده با میانگین 1 و انحراف معیار 0.3 است.

# دو ماتریس تصادفی تولید شده را با 100 سطر و دو ستون از سطر با هم ترکیب می کنیم که اولین ماتریس حاوی 200 عدد تصادفی تولید شده ی توزیع نمایی با پارامتر 4 و ماتریس دوم حاوی 200 عدد تصادفی تولید شده از توزیع نمایی با پارامتر 2 است.

> z1<-matrix(rexp(200,4),100) > z2<-matrix(rexp(200,2),100) > z<-rbind(z1,z2) # نامگذاری ستون های z : > (colnames(z)<-c("x","y")) [1] "x" "y" # خوشه بندی ماتریس z با 6 خوشه در k. > (k<-kmeans(z,6)) K-means clustering with 6 clusters of sizes 9, 34, 97, 18, 5, 37 Cluster means: x y 1 0.3259749 1.7754646 2 0.1865689 0.8059417 3 0.1338772 0.1799131 4 1.2720724 0.1668356 5 1.5632726 1.2220303 6 0.6040383 0.2922071 Clustering vector: [1] 3 3 3 6 3 2 3 3 3 3 2 3 3 3 3 3 3 6 3 6 3 3 6 3 6 3 2 2 2 3 6 3 3 2 6 3 3 [38] 6 3 3 2 2 6 3 3 3 6 3 3 3 3 3 3 2 2 3 6 2 6 3 3 4 3 2 6 3 3 3 3 3 3 3 3 6 [75] 6 3 3 6 3 6 3 3 3 3 2 3 3 6 3 2 2 3 3 3 3 2 6 3 3 3 6 4 3 4 4 2 6 3 1 3 2 [112] 6 5 1 5 3 3 6 1 2 2 3 6 2 5 4 3 3 4 2 3 4 5 6 2 3 3 4 6 2 3 4 2 3 1 6 3 1 [149] 2 3 2 3 4 2 1 2 3 1 5 6 4 1 6 3 6 3 3 4 2 3 2 3 2 4 3 3 1 4 3 3 6 3 2 4 4 [186] 3 3 3 4 6 3 2 6 4 6 6 6 6 3 3 Within cluster sum of squares by cluster: [1] 1.204575 2.440911 2.874572 1.732132 1.176951 2.316250 (between_SS / total_SS = 84.2 %) Available components: [1] "cluster" "centers" "totss" "withinss" "tot.withinss" [6] "betweenss" "size" #ترسیم ماتریس x و اختصاص رنگ به دو خوشه ی cl: > plot(z,col=k$cluster) > points(k$centers,col=1, pch=3,cex=2) # مشخص کردن مراکز دو خوشه ی cl با رنگ آبی(col) و فرم ستاره(pch) و اندازه ی بزرگتر(cex)