خوشه‌بندی سلسله مراتبی

خوشه‌بندی سلسله مراتبی تکنیکی است که در گروه بندی یا دسته بندی داده ها به کارمی رود. نقاط داده ها در این روش در دسته ها و زیر دسته هایی بر اساس معیار شباهت قرار می گیرند. در روش خوشه بندی سلسله مراتبی، به خوشه های نهايی بر اساس ميزان عموميت آنها ساختاری سلسله مراتبی، معمولا به صورت درختی نسبت داده می شود. به اين درخت سلسله مراتبی دندوگرام (dendogram) می گويند.

روش کار تکنيکهاي خوشه بندی سلسله مراتبی معمولا بر اساس الگوريتم هاي حريصانه (Greedy Algorithms) و بهينگی مرحله های (stepwise-optimal) است. روشهای خوشه بندی بر اساس ساختار سلسله مراتبی توليدی توسط آنها معمولا به دو دسته زير تقسيم می شوند:

 بالا به پايين (Top-Down) يا تقسيم کننده(Pisive)

در اين روش ابتدا تمام دادهها به عنوان يک خوشه در نظر گرفته مي شوند و سپس در طي يک فرايند تکراري در هر مرحله دادههايي شباهت کمتري به هم دارند به خوشههاي مجزايي شکسته ميشوند و اين روال تا رسيدن به خوشه هايي که داراي يک عضو هستند ادامه پيدا ميکند.

حتما بخوانید: محاسبه مدل لجیت

پايين به بالا (Bottom-Up) يا متراکم شونده (Agglomerative)

در اين روش ابتدا هر دادهها به عنوان خوشهاي مجزا در نظر گرفته ميشود و در طي فرايندي تکراري در هر مرحله خوشههايي که شباهت بيشتري با يکديگر با يکديگر ترکيب ميشوند تا در نهايت يک خوشه و يا تعداد مشخصي خوشه حاصل شود. از انواع الگوريتمهاي خوشه بندي سلسله مراتبی متراکم شونده رايج ميتوان از الگوريتم های Single-Linkage، Average-Linkage وComplete-Linkage نام برد. تفاوت اصلي در بين تمام اين روشها به نحوه محاسبه شباهت بين خوشهها مربوط مي شود. که در بخشهای بعد به تشريح هر يک پرداخته خواهد شد.

خوشه‌بندی سلسله مراتبی در R

با بسته های قدرتمند R می توان خوشه بندی ها را به خوبی انجام داد. دستور کلی خوشه بندی سلسله مراتبی در R به صورت زیر است:

hclust(d, method = “complete”, members=NULL)

تقریبا تمام روش های خوشه بندی بر مبنای “فاصله” استوارند. ماتریس فاصله که با جایگذاری فاصله ی میان هر دو جفت از داده ها در یک ماتریس به دست می آید در جای دادن نقاط داده ها نقشی اساسی ایفا می کند. نقاطی که به هم نزدیکترند در یک گروه یا خوشه جای می گیرند. بنا براین ورودی روش خوشه بندی سلسله مراتبی یک ماتریس فاصله خواهد بود. در نتیجه باید یکی از آن ها را محاسبه کنیم.
در گام بعد باید این ماتریس فاصله را در تابع hclust اجرا کنیم

hclust(as.dist(d))

المان های تابع hclust به شرح زیر است:

• d ساختاری بر اساس تفاوت موجود در نمونه ها، که از تابع dist به دست می آید.
• method روش خوشه بندی سلسله مراتبی را شرح می دهد. که باید یکی از روش های “single”، “ward”، “complete”، “average”، “mcquitty”، “median” یا “centroid” در دستور فوق نوشته شود.

در حالت کلی این روش های خوشه بندی به قرار زیرند:

1. Ward’s minimum variance or error sum of squares method.
2. single linkage or nearest neighbor method.
3. complete linkage or diameter.
4. average linkage, group average, or UPGMA method.
5. McQuitty’s or WPGMA method.
6. median, Gower’s or WPGMC method.
7. centroid or UPGMC method.

که روش ward کمترین واریانس را در یافتن خوشه ها دخیل می کند و روش “complete linkage” خوشه های شبیه به هم را پیدا می کند. روش “single linkage” که بسیار مرتبط به درخت پوشای مینیمم است، از استراژدی خوشه بندی “friends of friends” استفاده می کند. سایر روش های فوق راه میان بری میان خوشه بندی “complete”و خوشه بندی “single” هستند.

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

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

فرض کید معدل دانشجویان کارشناسی ارشدآمار ده دانشگاه به صورت زیر باشد و بخواهیم این 10 دانشگاه را بر اساس معدل به صورت سلسله مراتبی خوشه بندی کنیم؛

h<-C(12,13,17,4,13,8,19,14,7,16,12)
data<-data.frame(h)

( نوشتن داده ها به صورت دیتا فریم در مواقعی که تعداد داده ها زیاد باشند و نیز داده هایمان چند بعدی باشند کار را ساده تر خواهد کرد)

dh<-dist(data)ساختن ماتریس فاصله

dh

1 2 3 4 5 6 7 8 9 10

2 1

3 5 4

4 8 9 13

5 1 0 4 9

6 4 5 9 4 5

7 7 6 2 15 6 11

8 2 1 3 10 1 6 5

9 5 6 10 3 6 1 12 7

10 4 3 1 12 3 8 3 2 9

11 0 1 5 8 1 4 7 2 5 4

sh<-hclust(dh,”single”)خوشه بندی از روش تنها

ch<-hclust(dh,”complete”)خوشه بندی با روش کامل

ah<-hclust(dh,”average”)خوشه بندی با روش میانگین

oh<-hclust(dh,”centroid”)خوشه بندی با روش مرکزگرایی

par(mfrow=c(2,2)) قرار دادن نمودارها در دو سطر و دو ستون در یک صفحه
plot(sh,hang=-1)
plot(ch,hang=-1)
plot(ah,hang=-1)
plot(oh,hang=-1

چنانچه بخواهید خوشه بندی را از مرحله ای به بعد متوقف کنید و یا خواهان تعداد خوشه های مورد نظر خود باشید از دستور (cutree(d,n=k استفاده کنید به طوری که n تعداد خوشه های مورد نظر تان است.

با مثالی دیگر این توابع و کاربردهای دیگر خوشه بندی را در R بهتر ببینید:

require(graphics)
hc <- hclust(dist(USArrests), “ave”)
plot(hc)
plot(hc, hang = -1)

## Do the same with centroid clustering and squared Euclidean distance,
## cut the tree into ten clusters and reconstruct the upper part of the
## tree from the cluster centers.

همین کار را با روش خوشه بندی مرکزی با مجذور فاصله اقلیدسی انجام می دهیم:

kc <- hclust(dist(USArrests)^2, “cen”)
plot(kc,hang=-1)

حال چنانچه بخواهیم فقط از وضیعت 10 خوشه از قسمت فوقانی دندوگرام (نمودار درختی) اطلاع داشته باشیم باید درخت را برش و بازسازی کنیم:

memb <- cutree(kc, k = 10)
memb
cent <- NULL
for(k in 1:10){
cent <- rbind(cent, colMeans(USArrests[memb == k, , drop = FALSE]))
}
hc1 <- hclust(dist(cent)^2, method = “cen”, members = table(memb))
opar <- par(mfrow = c(2, 2))
plot(hc, labels = FALSE, hang = -1, main = “Original Tree”)
plot(hc1, labels = FALSE, hang = -1, main = “Re-start from 10 clusters”)
par(opar)

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