الگوریتم های کلاسترینگ

در این قسمت انواع الگوریتم های کلاسترینگ را بررسی می کنیم. الگوریتم های کلاسترینگ را می توان به دسته های اصلی زیر تقسیم بندی کرد:

• الگوریتم های کلاسترینگ ترتیبی

• الگوریتم های کلاسترینگ سلسله مراتبی 

• الگوریتم های کلا سترینگ مبتنی بر بهینه سازی تابع هزینه

 الگوریتم های کلاسترینگ ترتیبی

این الگوریتم ها در ابتدا یک کلاستر تک تولید می کنند و روش های سریع و واضحی می باشند. در اکثر آنها بردارهای خصوصیات به تعداد دفعات کمی و یا تنها یک بار به الگوریتم داده می شوند. در اینجا بطور خلاصه الگوریتم ترتیبی پایه را توضیح می دهیم. در این نمونه تمام بردارها یک بار به الگوریتم ارائه می شوند. تعداد دسته ها در این مورد از قبل مشخص نیستند. در واقع کلاسترهای جدید در حین اجرای برنامه ایجاد می شوند. اگر به معنای فاصله (عدم شباهت) بین بردار خصوصیت و کلاستر باشد، هر بردار بسته به فاصله از کلاستر، به کلاسترهای موجود و یا به کلاستر جدید نسبت داده می شود. در زیر الگوریتم کلاسترینگ ترتیبی پایه آورده شده است.

در الگوریتم های کلاسترینگ ترتیبی نتیجه نهایی به ترتیبی که بردارها به الگوریتم ارائه می شوند بستگی دارد.

کلاسترینگ سلسله مراتبی (Hierarchical Clustering)

با در دست داشتن N نمونه داده برای کلاستر شدن و یک ماتریس فاصله یا شباهت به ابعاد N*N ، پروسه اصلی کلاستریگ سلسله مراتبی به صورت زیر میباشد :

1. با تخصیص هر نمونه به یک کلاستر شروع کنید . یعنی اگر N نمونه داشته باشیم ، N کلاستر داریم که هر یک دارای یک نمونه می باشند . فاصله بین کلاستر ها همان فاصله بین کلاستر های آنهاست .

2. دو کلاستری را که نزدیک تر هستند پیدا کنید و آنها را ادغام کنید . حالا یک کلاستر کمتر داریم .

3. فاصله کلاستر جدید را با هر یک از کلاسترهای قدیمی محاسبه کنید .

4. مراحل 2 و3 را آنقدر تکرار کنید که همه نمونه ها در یک کلاستر به اندازه N قرار بگیرند

مرحله 3 می تواند به روش های مختلفی انجام گیرد که کلاستریگ single-linkage ، complete-linkage و Average-linkage را مشخص می کند .

در کلاستریگ single-linkage (که روش connectedness یا minimum هم نامیده می شود( ، فاصله یک کلاستر از کلاستر دیگر را کوتاهترین فاصله هر عضو از کلاستر اول تا هر عضو از کلاستر دوم در نظر می گیرند .

اگر داده ها شامل شباهت باشند ، شباهت یک کلاستر تا کلاستر دیگر را برابر بیشترین شباهت هر عضو از کلاستر اول تا هر عضو از کلاستر دوم در نظر می گیرند .

در کلاستریگ complete-linkage (که روش diameter یا maximum هم نامیده می شود(، فاصله یک کلاستر از کلاستر دیگر را بزرگترین فاصله هر عضو از کلاستر اول تا هر عضو از کلاستر دوم در نظر می گیرند .

در کلاستریگ average-linkage ، فاصله یک کلاستر از کلاستر دیگر را میانگین فاصله هر عضو از کلاستر اول تا هر عضو از کلاستر دوم در نظر می گیرند .

کلاستریگ سلسله مراتبی ، agglomerative یا متراکم شونده نیز نامیده می شود ، زیرا کلاستر ها را به تدریج ادغام می کند .کلاسترینگ تقسیم کننده یا divisive هم وجود دارد که به صورت عکس عمل می کند ، به این صورت که ابتدا همه اشیاء را در یک کلاستر قرار می دهد و به تدریج آن را به قطعه های کوچکتر تقسیم می کند.

البته این نوع کلاستریگ به ندرت مورد استفاده قرار می گیرد . شکل زیر نحوه عملکرد این دو الگوریتم را نشان می دهد.

الگوریم کلاسترینگ single-linkage :

این الگوریم agglomerative است و زمانیکه کلاستر ها برای تشکیل کلاستر های جدید ، ادغام می شوند ، سطرها و ستون های مربوط به آنها را در ماتریس مجاورت پاک می کند .

ماتریس مجاورت به ابعاد N*N ، D = [d(i,j)] را در نظر بگیرید . به کلاستر ها اعداد 0 و 1 و ... و n-1 ، تخصطص داده می شود و L(k) ، سطح k امین کلاسترینگ است . کلاستری با شماره m به صورت (m) نمایش داده می شود و مجاورت بین کلاسترهای (r) و (s) به صورت d[(r) , (s)] نمایش داده می شود .

الگوریتم شامل مراحل زیر است :

1. با کلاسترینگ با سطح L(0)=0 و m=0 شروع کنید .

2. بی شباهت ترین جفت از کلاستر ها را پیدا کنید . ((r),(s)) :

D[(r),(s)] = min d[(i),(j)]

مینیمم بین همه جفت کلاسترها در نظر گرفته می شود .

3.m=m+1 قرار دهید . کلاستر های (r) و (s) را ادغام کنید تا تا کلاستریگ بعدی را تشکیل دهد . سطح کلاستریگ را به این صورت تنظیم کنید :

L(m) = d[(r),(s)]

4. ماتریس مجاورت (D) را update کنید . به این ترتیب که سطرها و ستون های مربوط به کلاسترهای(r) و (s) را حذف کنید و یک سطر و ستون جدید برای کلاستری که تازه تشکیل شده ایجاد کنید . 

مجاورت بین کلاستر جدید (r,s) و کلاستر های قدیمی k به این ترتیب محاسبه می شود: 

d [(k), (r,s)] = min d[(k),(r)], d[(k),(s)]

5. اگر تمام اشیاء در یک کلاستر قرار گرفتند متوقف می شویم ، در غیر این صورت به مرحله 2 باز می گردیم . 

یک مثال : 

به عنوان مثال یک کلاسترینگ از فواصل بین یک سری از شهر های ایتالیایی که بر حسب کیلومتر بیان شده اند را بررسی می کنیم . روش استفاده شده ، single-linkage می باشد .

ماتریس فاصله که ورودی می باشد به صورت زیر است : (برای همه کلاستر ها L=0 می باشد .)

نزدیکترین شهرها MI و TO هستند ، که به فاصله 138 کیلومتر می باشند . آنها در یک کلاستر به نام MI/TO ادغام می شوند . سطح کلاستر جدید L(MI/TO) = 138 و m=1 می باشد .

می توانیم فاصله این شیء ترکیبی را از همه اشیاء دیگر محاسبه کنیم . در کلاسترینگ single-linkage ، قانون این است که فاصله شیء ترکیبی تا سایر اشیاء ، برابر کوتاهترین فاصله از هر عضو از کلاستر تا شیء خارجی می باشد . بنابراین فاصله MI/TO تا RM ، 564 انتخاب می شود که فاصله از MI تا RM می باشد.بعد از ادغام MI و TO ، خواهیم داشت :

min d(i,j) = d(NA,RM) = 219 => 

NA وRM در کلاستر جدیدی به نام NA/RM ادغام می شوند .

L(NA/RM) = 219

m = 2

min d(i,j) = d(BA,NA/RM) = 255 =>

BA و NA/RM در کلاستر جدیدی به نام BA/ NA/RM ادغام می شوند .

L(BA/NA/RM) = 255

m = 3

min d(i,j) = d(BA/NA/RM,FI) = 268 =>

BA/NA/RM و FI در کلاستر جدیدی به نام BA/FI/NA/RM ادغام می شوند .

L(BA/FI/NA/RM) = 268

m = 4

نهایتاً دو کلاستر باقیمانده را در سطح 295 ادغام می کنیم .

پروسه انجام شده به صورت خلاصه در ساختار سلسله مراتبی درخت زیر نمایش داده شده است 

مشکلات :

نقاط ضعف اصلی روش های کلاسترینگ agglomerative عبارتند از :1 - پیچیدگی زمانی ، حداقل ( O(n است که n ، تعداد کل اشیاء می باشد .2 - مراحلی که قبلاً انجام شده ، قابل بازگشت نیستند و نمی توان تأثیر قدم های قبلی را undo کرد.