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

[sat98]

کلاسترينگ سلسله مراتبي (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 عبارتند از :
? پيچيدگي زماني ، حداقل ( O(n است که n ، تعداد کل اشياء مي باشد .
? مراحلي که قبلاً انجام شده ، قابل بازگشت نيستند و نمي توان تأثير قدم هاي قبلي را undo کرد .