ساخت گراف برای خوشه بندی

linkage measures

بر اساس معیارهای زیر می توانیم گرافهای متفاوتی برای خوشه بندی نقاط بسازیم. اولین چیزی که به ذهن آدم می رسد یک گراف کامل است که فاصله ی هر دو نقطه را وزن یال قرار بدهیم، اما این کار هزینه ی زیادی دارد.

1- کمترین فاصله: فاصله ی هر نقطه از یک خوشه را تا یک نقطه از خوشه ی دیگر مینیمم کند.

به این روش ها نزدیک ترین همسایه می گویند. کلا هر روشی که بر مبنای نزدیک ترین خوشه به یک نقطه عمل کند single linkage است.

در ساخت گراف آن، به این معنی است که بین نزدیک ترین دو نقطه ی دو خوشه (نزدیک ترین خوشه ها) متفاوت یک یال رسم کنیم. (راسهای گراف نقاط هستند). چون همیشه یالها بین خوشه های متفاوت رسم می شوند، گراف ساخته شده یک درخت است. به همین دلیل به این روشها minimal spanning tree هم می گویند.

(هر نقطه به نزدیک ترین مرکز خود وصل است)

(نزدیک بودن محلی)

2- بیشترین فاصله: فاصله ی بین نقاط دو خوشه متمایز را ماکسیمم می کند. (بین هر دو خوشه نه، بین هر خوشه تا نزدیک ترین خوشه ها به آن)

به این روشها دورترین همسایه می گویند. اگر تا جایی ادامه دهیم که فاصله ی دو خوشه از یک حد آستانه مشخص شده توسط کاربر بیشتر شود، به آن اتصال کامل می گویند.

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

هدف این الگوریتم ها مینیمم کردن قطر خوشه ها است و وقتی بهترین جواب را می دهند که خوشه ها فشرده باشند و اندازه ی تقریبا مساوی داشته باشند.

(نزدیک بودن سراسری)

** هر دوی روشهای بالا به داده های پرت (که با داده های دیگر فاصله زیاد دارند) و نویز (خطای تصادفی) حساس هستند. به همین دلیل روش های دیگری ارائه شد که بین این دو روش افراطی بودند:

3- فاصله میانگینها: بین میانگین دو خوشه فاصله را مینیمم کنیم.

** این روش مشکل قبل را حل می کند و محاسبه ی آن ساده است، اما برای داده های غیر عددی جواب نمی دهد، در نتیجه ملاک دیگری ارائه شد:

4- میانگین فاصله ی نقاط دو خوشه

1/(n1*n2) * sum (pi, qj)

pi in C1, q in C2

بر خلاف تعریف فاصله ی مرکزها، میانگین را می توانیم برای داده های غیرعددی هم تعریف کنیم. (مثلا مد یا میانه)

**** این روشها برای خوشه بندی سلسله مراتبی هستند.