CLUSTERING
CLICK
2. Hierarchical Clustering
CLICK
3. K-Means Clustering
CLICK
4. Fuzzy C-Means Clustering
CLICK
1. Introduction
5. Clustering Codes in MATLAB
CLICK
6. References
CLICK
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
خوشه بندی بر گروه بندی رکوردها ، مشاهدات یا نمونه ها به طبقه هایی از اشیاءِ مشابه دلالت می کند. یک خوشه ، مجموعه ای از رکوردهاست که شبیه یکدیگرند و شبیه رکوردهای دیگر در سایر خوشه ها نیستند.
تفاوت خوشه بندی با طبقه بندی این است که هیچ متغیر هدفی برای خوشه بندی وجود ندارد. خوشه بندی برای طبقه بندی ، تخمین یا پیش بینی مقدار متغیر هدف تلاش نمی کند.
هدف همه ی روش های خوشه بندی، شناسایی گروه هایی از رکوردهاست که شباهتشان داخل گروه خیلی زیاد است ، در حالی که شباهتشان با رکوردهای سایر گروه ها خیلی کم است. به عبارت دیگر ، الگوریتم های خوشه بندی سعی می کنند تا خوشه هایی از رکوردها بسازند که اختلاف بین خوشه ای (BCV) در مقایسه با اختلاف درون خوشه ای (WCV) بزرگ باشد.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
2
فهرست
1. Introduction
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
3
فهرست
1. Introduction
در خوشه بندی با سوالات زیر مواجه می شویم:
چه طور مشابهت رکوردها را بسنجیم؟
چه طور متغیرهای قیاسی را کد گذاری کنیم؟
چه طور متغیرهای عددی را استاندارد یا نرمالیزه کنیم؟
انتظار داریم چند خوشه کشف گردد؟ (مجموعه داده به چند خوشه بایستی تقسیم شود؟)
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
4
فهرست
1. Introduction
سوال اول: چه طور مشابهت رکوردها را بسنجیم؟
تحلیل گران تابع فاصله را برای سنجش مشابهت رکوردها به کار می برند.
جایی که X = x1 , x2 , … , xm و Y = y1 , y2 , … , ym ، مقدارهای m ویژگی از دو رکورد را نشان می دهند.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
5
فهرست
1. Introduction
سوال دوم: چه طور متغیرهای قیاسی را کد گذاری کنیم؟
برای متغیرهای قیاسی ، تابع “different from” را برای مقایسه ی مقدارهای ویژگی i ام یک جفت از رکوردها به صورت زیر تعریف می کنیم:
جایی که xi و yi ، متغیرهای قیاسی هستند. سپس different(xi,yi) را در جمله ی i ام تابع فاصله جایگذین می کنیم.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
6
فهرست
1. Introduction
سوال سوم: چه طور متغیرهای عددی را استاندارد یا نرمالیزه کنیم؟
به منظور کارایی بهینه ی الگوریتم های خوشه بندی ، دقیقا مانند الگوریتم های طبقه بندی ، نیاز است که مجموعه داده نرمالیزه شود تا هیچ متغیر خاصی یا هیچ زیر مجموعه ای از متغیرها بر تحلیل تسلط پیدا نکند. به این منظور ، تحلیل گران از نرمالیزاسیون Min-max یا استانداردسازی Z-score استفاده می کنند:
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
7
فهرست
1. Introduction
الگوریتم های خوشه بندی ، سلسله مراتبی یا غیر سلسله مراتبی هستند.
در خوشه بندی سلسله مراتبی ، یک ساختار خوشه ای درخت مانند از طریق تفکیک کردن بازگشتی (روش های تقسیم کننده) یا ترکیب خوشه های موجود (روش های جمع کننده) ، ایجاد می شود.
در روش های خوشه بندی تقسیم کننده ، در ابتدا همه ی رکوردها در یک خوشه ی بزرگ قرار دارند که غیر مشابه ترین رکوردها به طور بازگشتی شروع به جدا شدن در خوشه های جداگانه می کنند تا زمانی که هر رکورد ، خودش یک خوشه را نشان می دهد.
در روش های خوشه بندی جمع کننده ، در ابتدا هر مشاهده به یک خوشه خیلی کوچک از خودش تخصیص می یابد. سپس در مراحل بعدی ، دو مشابه ترین خوشه در یک خوشه ی جدید ترکیب می شوند. در این روش ، تعداد خوشه ها در مجموعه داده به ازاء هر مرحله کاهش می یابد. سرانجام ، همه ی رکوردها در یک خوشه ی بزرگ ترکیب می شوند. چون بیشتر برنامه های کامپیوتری که خوشه بندی سلسله مراتبی را به کار می برند از روش های جمع کننده استفاده می کنند، روی این روش ها تمرکز می کنیم.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
8
فهرست
2. Hierarchical Clustering
پس از کدگذاری متغیرهای قیاسی و نرمالیزه کردن متغیرهای عددی ، فاصله ی بین رکوردها قابل محاسبه است. اما چه طور باید فاصله ی بین خوشه ها را تعیین کنیم؟
چند معیار برای شناسایی فاصله ی بین خوشه های دلخواه A وB عبارتند از:
پیوند واحد (Single Linkage) که روش نزدیکترین همسایه نامیده می شود و بر اساس مینیمم فاصله ی بین هر رکورد در خوشه ی A و هر رکورد در خوشه ی B است.
پیوند کامل (Complete Linkage) که روش دورترین همسایه نامیده می شود و بر اساس ماکزیمم فاصله ی بین هر رکورد در خوشه ی A و هر رکورد در خوشه ی B است.
معیار پیوند میانگین (Average Linkage) که بر اساس میانگین فاصله ی همه ی رکوردهای خوشه ی A از همه ی رکوردهای خوشه ی B است.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
9
فهرست
2. Hierarchical Clustering
10
فهرست
2. Hierarchical Clustering
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
مثال: (خوشه بندی سلسله مراتبی جمع کننده با معیار Single Linkage)
مجموعه داده ی کوچک یک بعدی زیر را در نظر بگیرید:
5 9 15 16 18 25 33 33 45
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
هدف Single Linkage مینیمم کردن فاصله ی بین نزدیکترین رکوردهای دو خوشه است.
[0]
[1]
[3]
[2]
[4]
[6]
[7]
[8]
[12]
مثال: (خوشه بندی سلسله مراتبی جمع کننده با معیار Complete Linkage)
مجموعه داده ی کوچک یک بعدی زیر را در نظر بگیرید:
2 5 9 15 16 18 25 33 33 45
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
11
فهرست
2. Hierarchical Clustering
هدف Complete Linkage مینیمم کردن فاصله ی بین دورترین رکوردهای دو خوشه است.
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
[0]
[1]
[3]
[3]
[7]
[8]
[16]
[20]
[43]
الگوریتم خوشه بندیK-Means به صورت زیر عمل می کند: MacQueen(1967)
مرحله ی1: از کاربر بپرسید که مجموعه داده باید به چند خوشه ، K ، تفکیک شود.
مرحله ی2: به طور تصادفی ، K رکورد را به مراکز خوشه های اولیه تخصیص دهید.
مرحله ی3: برای هر رکورد ، نزدیکترین مرکز خوشه را بیابید. در نتیجه هر مرکز خوشه یک تفکیک از مجموعه داده را نشان می دهد. بنابراین ما K خوشه، (C1 , C2 , … , Ck) ، داریم.
مرحله ی4: برای هر K خوشه، مرکز ثقل خوشه را بیابید و محل مرکز هر خوشه را با مقدار جدید مرکز ثقل ، به روز رسانی کنید.
مرحله ی5: مراحل 3 تا 5 را تا زمان هم گرایی یا توقف الگوریتم تکرار کنید.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
12
فهرست
3. K-Means Clustering
معیار نزدیکترین در مرحله ی 3 معمولا به وسیله ی فاصله ی اقلیدسی تعیین می شود، اگر چه سایر معیارها نیز می توانند به کار گرفته شوند.
مرکز ثقل خوشه در مرحله ی 4 به صورت زیر تعیین می شود:
فرض کنید که n نقطه داده به صورت (a1,b1,c1),(a2,b2,c2),…,(an,bn,cn) داریم.
مرکز ثقل این نقاط ، نقطه ی است.
برای مثال ، مرکز ثقل نقاط (2,1,1) و (1,3,1) و (1,2,1) و (1,1,1) به صورت زیر محاسبه می شود:
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
13
فهرست
3. K-Means Clustering
چه هنگام الگوریتم متوقف می شود؟
هنگامی که دیگر مراکز ثقل تغییر نکنند، الگوریتم متوقف می شود. به عبارت دیگر ، هنگامی که همه ی رکوردهای هر خوشه در همان خوشه باقی بمانند.
همچنین ، الگوریتم می تواند زمانی که در دو عبور متوالی از الگوریتم ، مقدار کاهش در SSE از مقدار از پیش تعیین شده ی ε کمتر باشد، متوقف شود.
جایی که pєCi ، هر نقطه داده در خوشه ی i و mi ، مرکز ثقل خوشه ی i را نشان می دهد.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
14
فهرست
3. K-Means Clustering
مثال: فرض کنید که 8 نقطه داده در فضای دو بعدی داریم که در جدول و شکل زیر نشان داده شده اند و می خواهیم تا مجموعه داده را توسط الگوریتم K-Means به K=2 خوشه تفکیک کنیم.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
15
فهرست
3. K-Means Clustering
مرحله ی1: از کاربر بپرسید که مجموعه داده باید به چند خوشه تفکیک شود. (K=2)
مرحله ی2: به طور تصادفی ، K رکورد را به مراکز خوشه های اولیه تخصیص دهید. m1=(1,1) و m2=(2,1)
مرحله ی3 (اولین عبور): برای هر رکورد ، نزدیکترین مرکز خوشه را بیابید.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
16
فهرست
3. K-Means Clustering
بنابراین خوشه ی 1 شامل نقاط {a,e,g} و خوشه ی 2 شامل نقاط {b,c,d,f,h} است.
مرحله ی4 (اولین عبور): برای هر K خوشه ، مرکز ثقل خوشه را بیابید و محل مرکز هر خوشه را با مقدار جدید مرکز ثقل ، به روز رسانی کنید. مرکز ثقل خوشه ی 1 ، [(1+1+1)/3,(3+2+1)/3] = (1,2) است و مرکز ثقل خوشه ی 2 ، [(3+4+5+4+2)/5,(3+3+3+2+1)/5] = (3.6,2.4) است. خوشه ها و مراکز ثقل (مثلث ها) در پایان اولین عبور در شکل زیر نشان داده شده اند.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
17
فهرست
3. K-Means Clustering
مرحله ی 5: مراحل 3 تا 5 را تا زمان هم گرایی یا توقف الگوریتم تکرار کنید. مراکز ثقل جا به جا شده اند، بنابراین ما برای دومین عبور از الگوریتم به مرحله ی 3 بر می گردیم.
مرحله ی 3 (دومین عبور) : برای هر رکورد ، نزدیکترین مرکز خوشه را بیابید. جدول زیر، فاصله ی اقلیدسی بین هر نقطه و هر یک از مراکز خوشه ی به روز شده ی m2=(3.6,2.4) و m1=(1,2) را همراه با نتایج عضویت نشان می دهد.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
18
فهرست
3. K-Means Clustering
در اینجا رکورد h از خوشه ی 2 به خوشه ی 1 تغییر مکان می دهد و سایر رکوردها در همان خوشه های قبلی باقی می مانند. بنابراین خوشه ی 1 شامل نقاط {a,e,g,h} و خوشه ی 2 شامل نقاط {b,c,d,f} است.
مرحله ی 4 (دومین عبور): برای هر K خوشه ، مرکز ثقل خوشه را بیابید و محل مرکز هر خوشه را با مقدار جدید مرکز ثقل ، به روز رسانی کنید.
مرکز ثقل جدید برای خوشه ی 1 ، [(1+1+1+2)/4,(3+2+1+1)/4] = (1.25,1.75) است و مرکز ثقل جدید برای خوشه ی 2 ، [(3+4+5+4)/4,(3+3+3+2)/4] = (4,2.75) است.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
19
فهرست
3. K-Means Clustering
مرحله ی 5: مراحل 3 تا 5 را تا زمان هم گرایی یا توقف الگوریتم تکرار کنید. مراکز ثقل جا به جا شده اند، بنابراین ما برای سومین عبور از الگوریتم به مرحله ی 3 بر می گردیم.
مرحله ی 3 (سومین عبور): برای هر رکورد ، نزدیکترین مرکز خوشه را بیابید. جدول زیر، فاصله ی اقلیدسی بین هر نقطه و هر یک از مراکز خوشه ی به روز شده ی m2=(4,2.75) و m1=(1.25,1.75) را همراه با نتایج عضویت نشان می دهد.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
20
فهرست
3. K-Means Clustering
توجه کنید که هیچ رکوردی تغییر مکان نمی دهد و همه ی رکوردها در همان خوشه های قبلی باقی می مانند.
مرحله ی 4 (سومین عبور) : برای هر K خوشه ، مرکز ثقل خوشه را بیابید و محل مرکز هر خوشه را با مقدار جدید مرکز ثقل ، به روز رسانی کنید. چون هیچ رکوردی تغییر مکان نداشته است ، بنابراین مراکز ثقل خوشه ها بدون تغییر باقی می مانند.
مرحله ی 5: مراحل 3 تا 5 را تا زمان هم گرایی یا توقف الگوریتم تکرار کنید. چون مراکز ثقل خوشه ها بدون تغییر باقی مانده اند، الگوریتم متوقف می شود.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
21
فهرست
3. K-Means Clustering
توجه کنید که الگوریتم K-Means نمی تواند یافتن مینیمم جهانی برای SSE را تضمین کند ولی اغلب به یک مینیمم محلی دست می یابد. برای بهبود احتمال دستیابی به مینیمم جهانی ، تحلیل گر باید با استفاده از مراکز خوشه ی اولیه ی مختلف ، الگوریتم را دوباره اجرا کند.
Moore(2001) پیشنهاد می کند: (1) قرار دادن اولین مرکز خوشه روی یک نقطه ی تصادفی و (2) قرار دادن مراکز خوشه های بعدی روی نقاطی که از مراکز قبلی تا حد امکان دور هستند.
یک مشکل بالقوه برای به کار بردن الگوریتمK-Means این است که: چه کسی تصمیم می گیرد که چند خوشه باید جستجو شود؟ یعنی چه کسی K را تعیین می کند؟ مگر نه اینکه تحلیل گر یک دانش استقرایی برای تعیین تعداد خوشه دارد ، بنابراین یک حلقه ی بیرونی باید به الگوریتم اضافه شود که در چرخه های مختلف ، مقدارهای مختلفِ K را به کار گیرد. سپس راه حل های خوشه بندی به ازاء هر مقدار K ، مقایسه می شوند و آن K که منجر به کوچکترین SSE می شود ، انتخاب می گردد.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
22
فهرست
3. K-Means Clustering
اگر برخی از ویژگی های پیش بینی کننده نسبت به سایر ویژگی ها مهم تر باشند ، چه باید کرد؟
چون تحلیل گران تابع فاصله را برای سنجش مشابهت رکوردها به کار می برند ، می توان بر اساس نظر کارشناسان خبره برای هر ویژگی یک ضریب اهمیت تعریف نمود و سپس با توجه به این ضرایب اهمیت تابع فاصله را محاسبه کرد.
برای مثال اگر در مثال قبلی ضریب اهمیت ویژگی اول برابر با 3 و ضریب اهمیت ویژگی دوم برابر با 1 باشد ، آنگاه در مرحله ی3 از اولین عبور از الگوریتم فاصله ی نقطه داده ی a از m2 به صورت زیر محاسبه می شود:
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
23
فهرست
3. K-Means Clustering
الگوریتم خوشه بندیFuzzy C-Means توسط Bezdek(1981) مطرح شد.
در تفکیک مجموعه داده به C خوشه توسط الگوریتمFuzzy C-Means تابع هدفی به شکل زیر تعریف می شود که در عبورهای متوالی از الگوریتم این تابع هدف کاهش می یابد.
جایی که درجه عضویت داده ی k ام در خوشه ی i ام و فاصله ی اقلیدسی داده ی k ام ( ) از مرکز خوشه ی i ام ( ) را نشان می دهد و هر نقطه داده شامل m ویژگی است. پارامتر ، توان ماتریس تفکیک U و درجه ی فازی بودن را نشان می دهد. r نیز شمارشگر تعداد عبور از الگوریتم است.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
24
فهرست
4. Fuzzy C-Means Clustering
الگوریتم خوشه بندی Fuzzy C-Means به صورت زیر عمل می کند:
مرحله ی1: از کاربر بپرسید که مجموعه داده باید به چند خوشه ، C ، تفکیک شود. پارامتر یعنی توان ماتریس تفکیک U و ماتریس تفکیک اولیه ی را مقدار دهی کنید.
مرحله ی2: مراکز خوشه ها ( ها) را محاسبه کنید.
مرحله ی3: ماتریس تفکیک U را به روز رسانی کنید.
مرحله ی4: مراحل 2 تا 3 را تا زمان هم گرایی یا توقف الگوریتم تکرار کنید.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
25
فهرست
4. Fuzzy C-Means Clustering
چه هنگام الگوریتم متوقف می شود؟
هنگامی که دیگر مراکز خوشه ها تغییر نکنند، الگوریتم متوقف می شود. به عبارت دیگر ، هنگامی که همه ی رکوردهای هر خوشه در همان خوشه باقی بمانند.
همچنین ، الگوریتم می تواند زمانی که در دو عبور متوالی از الگوریتم ، مقدار کاهش در تابع هدف از مقدار از پیش تعیین شده ی ε کمتر باشد، ، متوقف شود.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
26
فهرست
4. Fuzzy C-Means Clustering
مثال: فرض کنید که 4 نقطه داده در فضای دو بعدی داریم که در جدول زیر نشان داده شده اند و می خواهیم تا مجموعه داده را توسط الگوریتم Fuzzy C-Means به C=2 خوشه تفکیک کنیم.
مرحله ی1: از کاربر بپرسید که مجموعه داده باید به چند خوشه ، C ، تفکیک شود. پارامتر یعنی توان ماتریس تفکیک U و ماتریس تفکیک اولیه ی را مقدار دهی کنید.
مرحله ی2 (اولین عبور): مراکز خوشه ها ( ها) را محاسبه کنید.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
27
فهرست
4. Fuzzy C-Means Clustering
مرحله ی3 (اولین عبور): ماتریس تفکیک U را به روز رسانی کنید.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
28
فهرست
4. Fuzzy C-Means Clustering
مرحله ی4: مراحل 2 تا 3 را تا زمان هم گرایی یا توقف الگوریتم تکرار کنید.
مرحله ی2 (دومین عبور): مراکز خوشه ها ( ها) را محاسبه کنید.
مرحله ی3 (دومین عبور): ماتریس تفکیک U را به روز رسانی کنید. همانطوریکه ملاحظه می کنید مراکز خوشه ها تغییر نکردند ، درنتیجه ماتریس تفکیک U تغییری نمی کند و الگوریتم متوقف می شود.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
29
فهرست
4. Fuzzy C-Means Clustering
CLICK
2. Hierarchical Clustering Using Complete Linkage
CLICK
3. Hierarchical Clustering Using Average Linkage
CLICK
4. K-Means Clustering
CLICK
1. Hierarchical Clustering Using Single Linkage
5. Fuzzy C-Means Clustering
CLICK
30
فهرست
5. Clustering Codes in MATLAB
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
Daniel T. Larose. Discovering knowledge in data: An introduction to data mining: John Wiley & Sons, Inc; 2005.
J. MacQueen. Some methods for classification and analysis of multivariate observations, Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, pp. 281–297, University of California Press, Berkeley, CA, 1967.
Andrew Moore, k-Means and Hierarchical Clustering, Course Notes, http://www-2.cs.cmu.edu/∼awm/tutorials/, 2001.
Timothy J. Ross. Fuzzy logic with engineering applications: John Wiley & Sons Ltd; 2004.
Bezdek, J. Pattern recognition with fuzzy objective function algorithms, Plenum, New York; 1981.
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389
31
فهرست
5. References
thanks a lot for your attentions
University of Tafresh, Industrial Engineering Department, Clustering by Hamid Moakedi, Azar1389