خوشه بندی

خوشه‌بندی یکی از مهم‌ترین مسایل در حوزه‌ی یادگیری بدون ناظر است. مانند هر مساله‌ی دیگر از این نوع، با یافتن یک ساختار در یک مجموعه داده‌ی بدون برچسب سروکار دارد. به طور غیر رسمی، فرآیند سازمان‌دهی اشیا در چند دسته به طوری که اعضای هر دسته از جنبه‌هایی به هم شبیه باشند را خوشه‌بندی گویند. با این تعریف، یک خوشه مجموعه‌ای از اشیا است که به هم شبیه‌اند و با اشیای مربوط به دیگر خوشه‌ها متفاوتند. هدف خوشه‌بندی، شناسایی دسته‌های طبیعی در یک مجموعه از اشیای برچسب نخورده است. تاکنون الگوریتم‌های فراوانی برای خوشه‌بندی داده‌ها معرفی شده است که از آن میان می‌توان به [Han et al, 2001]، [Jain et al.,1999]، [Duda et al. 2001]، [Kaufman et al., 1990]، [Everitt, 1993]، [Theodoridis and Koutroumbas, 1999] اشاره کرد. با وجود گوناگونی روش‌های خوشه‌بندی، هنوز روشی یکتایی وجود ندارد که بتواند تمام انواع خوشه‌ها را به خوبی شناسایی کند؛ از این رو، این کاربر است که باید با توجه به نیاز‌هایش روش مناسب را بر‌گزیند.‌
تقسیم‌بندی‌های گوناگونی برای روش‌های خوشه‌بندی وجود دارد: سلسله مراتبی و افراز‌بندی ، انحصاری و غیر‌انحصاری، فازی و غیر‌فازی و جزیی و کامل. از این میان، تقسیم‌بندی روش‌های خوشه‌بندی به دو نوع سلسله‌مراتبی و افراز‌بندی یا تو‌در‌تو و غیر‌تودرتو بیش از موارد دیگر مورد توجه است. در خوشه‌بندی افراز‌بندی، با مجموعه‌ای از خوشه‌ها سروکار داریم که روی هم افتادگی ندارند و هر شی تنها به یک خوشه‌تعلق دارد. از سوی دیگر، در خوشه‌بندی سلسله‌مراتبی، خوشه‌ها به صورت تودرتو سازمان می‌یابند و تشکیل یک ساختار درختی می‌دهند.‌ در ادامه، هر یک از این دو دسته به طور دقیق‌تر مورد بررسی قرار خواهند گرفت.‌

1- خوشه‌بندی سلسله‌مراتبی

خوشه‌بندی سلسله‌مراتبی نوعی از خوشه‌بندی است که در آن خوشه‌ها به صورت تودرتو سازمان می‌یابند. نتیجه‌ی خوشه‌بندی سلسله‌مراتبی روی یک مجموعه داده را می‌توان با یک ساختار درختی به نمایش در آورد. این بازنمایی درختی دندوگرام نامیده می‌شود.‌
یکی از ویژگی‌های مهم روش‌های سلسله مراتبی آن است که برای خوشه‌بندی داده‌هایی که طبیعت سلسله‌مراتبی دارند (مانند دسته‌بندی جانوران)، مناسب است.‌ ویژگی دیگر آنها، این است که هیچ فرضی در مورد تعداد خوشه‌ها نمی‌گیرد. پس از اجرای یک خوشه‌بندی سلسله‌مراتبی، برای بدست آوردن تعداد مشخصی خوشه باید دندوگرام حاصل را از محلی مناسب برش دهیم. نتیجه این کار تعدادی دندوگرام گسسته است که هر کدام متناظر با یک خوشه است.‌ افزون بر این دو ویژگی، گاهی خوشه‌بندی سلسله‌مراتبی خوشه‌های با کیفیت‌تری نسبت به دیگر روش‌های خوشه‌بندی بدست می‌دهد.
خوشه‌بندی سلسله‌مراتبی به دو دسته تقسیم می‌شود: جمع‌شونده و تقسیم‌شونده. در خوشه‌بندی سلسله‌مراتبی جمع‌شونده، ابتدا هر شی به عنوان یک خوشه در نظر گرفته می‌شود و سپس به صورت گام به گام خوشه‌ها با هم ادغام تا در پایان یک خوشه بدست آید. به عکس، در خوشه‌بندی سلسله‌مراتبی تقسیم‌شونده ابتدا تمام اشیا یک خوشه‌ را تشکیل می‌دهند و سپس به صورت گام به گام خوشه‌ها تقسیم می‌شوند تا جایی که هر خوشه تنها شامل یک شی باشد. در این پایان‌نامه، خوشه‌بندی جمع‌شونده مورد نظر است و هر جا سخن از خوشه‌بندی سلسله مراتبی می‌شود، نوع جمع‌شونده‌ی آن مورد نظر است.‌
فرآیند کلی یک الگوریتم خوشه‌بندی سلسله‌مراتبی جمع‌شونده به صورت زیر است.:
1. نخست، هر شی به صورت یک خوشه در نظر گرفته می‌شود.
2. شبیه‌ترین دو خوشه‌ی موجود مشخص شده و در هم آمیخته می‌شوند تا یک خوشه را تشکیل دهند. به این ترتیب، تعداد خوشه‌ها یکی کاهش می‌یابد.
3. فاصله یا شباهت بین خوشه‌ی تازه شکل یافته و خوشه‌های قدیمی محاسبه می‌شود.
4. گام‌های 2 و 3 آنقدر تکرار می‌شوند تا تنها یک خوشه باقی بماند.‌
تعیین شباهت (فاصله) بین خوشه‌ها از راه‌های گوناگونی انجام‌پذیر است. بر حسب اینکه چه معیاری برای تعیین شباهت بین خوشه‌ها بکار گرفته شود، می‌توان چندین نوع خوشه‌بندی سلسله‌مراتبی تعریف نمود.‌ سه نوع عمده و پر‌کاربرد خوشه‌بندی سلسله‌مراتبی عبارتند از: اتصال منفرد، اتصال میانگین و اتصال کامل. در بخش‌های بعدی، این سه الگوریتم با جزییات بیشتری مورد بررسی قرار خواهند گرفت. لازم به یادآوری است که پیچیدگی محاسباتی الگوریتم‌های خوشه‌بندی سلسله‌مراتبی جمع‌شونده در بهترین حالت O(n2 log n) است.

1-1- اتصال منفرد

در اتصال منفرد [Sneath and Sokal, 1973]، فاصله‌ی بین دو خوشه برابر با کمترین فاصله بین جفت اشیایی است که هر کدام متعلق به یکی از دو خوشه است (شکل 2-1، قسمت الف). به بیان دیگر

که Ci و Cj دو خوشه هستند و d(a,b) فاصله‌ی بین دوشی a و b است. بکارگیری الگوریتم اتصال منفرد هنگامی مفید است که خوشه‌های طبیعی دراز، نازک و دارای اشیای نزدیک به هم باشند (خوشه پیوسته باشد).

1-2- اتصال میانگین

در الگوریتم خوشه‌بندی اتصال میانگین [Jain and Dubes, 1988]، فاصله‌ی بین دو خوشه به صورت میانگین فاصله‌ی بین همه‌ی جفت‌هایی است که یکی از آنها در خوشه‌ی نخست و دیگری در خوشه‌ی دوم باشد (شکل 2-1، قسمت ب). به بیان دیگر

که Ci و Cj دو خوشه هستند، ni و nj تعداد اشیای متعلق به دو خوشه‌ی Ci و Cj هستند و d(a,b) فاصله‌ی بین دوشی a و b است. خوشه‌هایی که اتصال میانگین تولید می‌کند فشرده‌تر از خوشه‌هایی است که در اتصال منفرد تولید می‌شوند.

1-3- اتصال کامل

در الگوریتم خوشه‌بندی اتصال کامل [King, 1967]، فاصله‌ی بین دو خوشه به صورت بیشینه فاصله‌ی بین همه‌ی جفت‌هایی است که یکی از آنها در خوشه‌ی نخست و دیگری در خوشه‌ی دوم باشد (شکل 2-1، قسمت ج). به بیان دیگر

که Ci و Cj دو خوشه هستند و d(a,b) فاصله‌ی بین دوشی a و b است.

2- خوشه‌بندی افراز‌بندی

همان‌طور که گفته شد، در خوشه‌بندی افراز‌بندی با مجموعه‌ای از خوشه‌ها سروکار داریم که روی هم افتادگی ندارند و هر شی تنها به یک خوشه‌تعلق دارد. هدف از خوشه‌بندی افراز‌بندی، تقسیم داده‌ها به گونه‌ای است که داده‌های درون یک خوشه بیشترین شباهت را به هم داشته باشند و از سوی دیگر، بیشترین فاصله را با داده‌های موجود در خوشه‌های دیگر داشته باشند. الگوریتم‌های Forgy، Isodata و K-means چند نمونه از روش‌های خوشه‌بندی افراز‌بندی هستند.‌ بخش بعد، به بررسی روش K-mean اختصاص دارد.

1-2- الگوریتم K-means

الگوریتم K-means یکی روش‌های خوشه‌بندی ساده و سریع است. این الگوریتم دارای یک پارامتر به نام K است که تعداد خوشه‌هایی که باید بدست آید را مشخص می‌کند.‌ الگوریتم K-means پایه به صورت زیر است:

به طور معمول، مرکز خوشه‌های اولیه به صورت تصادفی از میان نمونه‌های اولیه گزینش می‌شوند. به همین دلیل، مرکز خوشه‌های اولیه در دو خوشه‌بندی مستقل K-means می‌توانند متفاوت باشند. این موضوع موجب می‌شود که خوشه‌های بجا مانده از دو اجرای مختلف K-means با هم متفاوت باشند.‌ در الگوریتم K-means می‌توان از معیار‌های فاصله‌ی گوناگون بهره گرفت و خوبی یا بدی بکارگیری آن معیار بستگی به نوع داده‌هایی دارد که باید خوشه‌بندی شوند.‌ الگوریتم K-means از مرتبه‌ی زمانی (O(I*K*n است که I تعداد تکرارها، K تعداد خوشه‌ها و n تعداد نمونه‌ها است.

خوشه بندی

مطالب مشابه :

خوشه بندی

فروش پروژه خوشه بندی FCM یا فازی Cmeans جهت قطعه بندی تصویر با نرم افزار MATLAB

فازی میانگین مرکز (Fuzzy C-mean)

روشی کارا برای خوشه‌بندی در شبکه‌های حسگر بی‌سیم

فروش پروژه خوشه بندی آفلاین فازی با سری زمانی مکی گلس با نرم افزار MATLAB

خوشه بندی یا کلاسترینگ چیست؟

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