دانلود رايگان آموزش نرم افزار R: خوشه بندي سلسله مراتبي

производство и доставка минеральной воды
как установить на хостинг Joomla 3.0

نگارش یافته توسط مدير محتواي ايران پژوهان مجموعه: دانلود رايگان

تعداد بازدید: 8806

خوشه‌بندي سلسله مراتبي (hierarchical clustering) در R

این مطلب مفید از وبسایت ژورنال آمار آکادمی به امانت گرفته شده است.

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

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

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

• پايين به بالا (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)ساختن ماتریس فاصله

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

Alabama Alaska Arizona Arkansas California

             1              2              3              4              3
      Colorado    Connecticut       Delaware        Florida        Georgia
             4              5              1              6              4
        Hawaii          Idaho       Illinois        Indiana           Iowa
             7              5              1              5              8
        Kansas       Kentucky      Louisiana          Maine       Maryland
             5              5              1              8              3
Massachusetts       Michigan      Minnesota    Mississippi       Missouri
             9              1              8              2              4
       Montana       Nebraska         Nevada New Hampshire     New Jersey
             5              5              1              8              9
    New Mexico       New York North Carolina   North Dakota           Ohio
             3              1             10              8              5
      Oklahoma         Oregon   Pennsylvania   Rhode Island South Carolina
             9              9              5              9              2
South Dakota      Tennessee          Texas           Utah        Vermont
             8              4              4              5              8
      Virginia     Washington West Virginia      Wisconsin        Wyoming
             9              9              8              8              9

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)