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

یکی از روش های معتبر خوشه بندی، خوشه بندی 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)

با دریافت « مشاوره برنامه‌نویسی، وب و سئو » از کارشناسان جوان حرفه‌ای و باتجربه ساکوراد؛ موفقیت کسب و کار، رونق فروش و افزایش درآمد خود را تضمین کنید!