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

خوشه‌بندی سلسله مراتبی تکنیکی است که در گروه بندی یا دسته بندی داده ها به کارمی رود. نقاط داده ها در این روش در دسته ها و زیر دسته هایی بر اساس معیار شباهت قرار می گیرند. در روش خوشه بندی سلسله مراتبی، به خوشه های نهایی بر اساس میزان عمومیت آنها ساختاری سلسله مراتبی، معمولا به صورت درختی نسبت داده می شود. به این درخت سلسله مراتبی دندوگرام (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” در دستور فوق نوشته شود.

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

۱. 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” هستند.

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

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

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

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

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

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

dh

۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰

۲ ۱

۳ ۵ ۴

۴ ۸ ۹ ۱۳

۵ ۱ ۰ ۴ ۹

۶ ۴ ۵ ۹ ۴ ۵

۷ ۷ ۶ ۲ ۱۵ ۶ ۱۱

۸ ۲ ۱ ۳ ۱۰ ۱ ۶ ۵

۹ ۵ ۶ ۱۰ ۳ ۶ ۱ ۱۲ ۷

۱۰ ۴ ۳ ۱ ۱۲ ۳ ۸ ۳ ۲ ۹

۱۱ ۰ ۱ ۵ ۸ ۱ ۴ ۷ ۲ ۵ ۴

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)

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

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)

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