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

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

• بالا به پايين (Top-Down) يا تقسيم کننده(Pisive)
در اين روش ابتدا تمام دادهها به عنوان يک خوشه در نظر گرفته ميشوند و سپس در طي يک فرايند تکراري در هر مرحله دادههايي شباهت کمتري به هم دارند به خوشههاي مجزايي شکسته ميشوند و اين روال تا رسيدن به خوشه هايي که داراي يک عضو هستند ادامه پيدا ميکند.

اعضای شبکه مشاوران در حوزه «تحقیقات بازار، بازاریابی و فروش»

All Locations آلمان— بایرن— برلین— راینلاند فالتسآمریکا— تگزاسامارات— ابوظبی— دبیایران— آذربایجان شرقی— آذربایجان غربی— اصفهان— البرز— تهران— خراسان رضوی— خراسان شمالی— سمنان— فارس— قزوین— کردستان— کرمانشاه— گیلان— لرستان— مازندران— همدانترکیه— آنکارا— استانبول

•  پايين به بالا (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)