الگوریتم ISODATA چیست؟ راهنمای خوشه‌بندی ایزودیتا

الگوریتم ISODATA یا Iterative Self-Organizing Data Analysis Technique یکی از روش‌های خوشه‌بندی بدون ناظر است که برای گروه‌بندی داده‌ها بر اساس شباهت آن‌ها استفاده می‌شود. این الگوریتم از نظر ایده به K-means شباهت دارد، اما برخلاف K-means کلاسیک می‌تواند در طول اجرای الگوریتم تعداد خوشه‌ها را با استفاده از عملیات Split و Merge تغییر دهد.

این ویژگی باعث شده است ISODATA در مسائلی مانند پردازش تصویر، طبقه‌بندی تصاویر ماهواره‌ای، سنجش از دور، Image Segmentation و تشخیص الگو مورد استفاده قرار گیرد؛ به‌خصوص زمانی که ساختار واقعی داده‌ها از ابتدا به‌طور دقیق مشخص نیست.

الگوریتم ISODATA چیست؟

ISODATA داده‌ها را در فضای ویژگی به چند گروه تقسیم می‌کند. در ابتدای اجرای الگوریتم، تعدادی مرکز خوشه در نظر گرفته می‌شود و هر نمونه به نزدیک‌ترین مرکز اختصاص داده می‌شود. سپس مراکز خوشه و ویژگی‌های آماری آن‌ها محاسبه می‌شوند.

تفاوت اصلی ISODATA با یک روش ساده مانند K-means در این است که الگوریتم فقط به جابه‌جایی مراکز و تخصیص دوباره داده‌ها محدود نمی‌شود. اگر یک خوشه بیش از حد پراکنده باشد، ممکن است Split شود و اگر دو خوشه بیش از حد به یکدیگر نزدیک باشند، ممکن است Merge شوند.

بنابراین تعداد خوشه‌ها در ISODATA می‌تواند در طول اجرای الگوریتم تغییر کند.

ISODATA چه نوع الگوریتم خوشه‌بندی است؟

ISODATA یک روش خوشه‌بندی بدون ناظر (Unsupervised Clustering) و از خانواده روش‌های پارتیشن‌بندی مبتنی بر مرکز (Centroid-Based Partitioning) محسوب می‌شود.

ISODATA پارتیشن‌بندی است، نه خوشه‌بندی سلسله مراتبی

یک نکته مهم درباره ISODATA وجود دارد که گاهی در منابع فارسی به‌اشتباه بیان می‌شود: ISODATA یک الگوریتم خوشه‌بندی سلسله مراتبی نیست.

در خوشه‌بندی سلسله مراتبی، ساختار سلسله‌مراتبی گروه‌ها به‌صورت یک درخت یا Dendrogram ایجاد می‌شود. اما ISODATA چنین ساختار درختی ایجاد نمی‌کند.

در ISODATA، عملیات Split و Merge صرفاً برای تطبیق تعداد و ساختار خوشه‌ها با داده‌ها انجام می‌شوند. بنابراین وجود عملیات تقسیم و ادغام به‌تنهایی به معنی Hierarchical بودن الگوریتم نیست.

به بیان ساده:

• K-means: تعداد خوشه‌ها ثابت است.
• ISODATA: تعداد خوشه‌ها می‌تواند در طول اجرا تغییر کند.
• Hierarchical Clustering: ساختار سلسله‌مراتبی از روابط میان خوشه‌ها ایجاد می‌شود.

برای آشنایی بیشتر با روش سوم می‌توانید مقاله خوشه‌بندی سلسله مراتبی را مطالعه کنید.

الگوریتم ISODATA چگونه کار می‌کند؟

ISODATA به‌صورت تکرارشونده عمل می‌کند. در هر مرحله، داده‌ها به خوشه‌ها اختصاص داده می‌شوند و سپس الگوریتم بررسی می‌کند که آیا ساختار فعلی خوشه‌ها نیاز به اصلاح دارد یا خیر.

1. تعیین مراکز اولیه

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

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

2. تخصیص داده‌ها به نزدیک‌ترین مرکز

هر نمونه داده بر اساس معیار فاصله، معمولاً فاصله اقلیدسی، به نزدیک‌ترین مرکز خوشه اختصاص داده می‌شود.

در نتیجه، یک پارتیشن اولیه از داده‌ها شکل می‌گیرد.

3. محاسبه مراکز و ویژگی‌های آماری

پس از تخصیص نمونه‌ها، مرکز هر خوشه مجدداً محاسبه می‌شود. همچنین معیارهایی مانند تعداد نمونه‌های موجود در خوشه و انحراف معیار آن بررسی می‌شود.

انحراف معیار اطلاعات مهمی درباره میزان پراکندگی داده‌ها در هر خوشه ارائه می‌دهد.

4. Split کردن خوشه‌ها

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

در چنین شرایطی ISODATA می‌تواند خوشه را به دو یا چند بخش تقسیم کند. این عملیات را Split می‌نامیم.

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

5. Merge کردن خوشه‌ها

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

اگر فاصله میان مراکز دو خوشه از یک آستانه مشخص کمتر باشد، ISODATA می‌تواند آن‌ها را با یکدیگر ادغام کند. این عملیات Merge نام دارد.

6. حذف خوشه‌های بسیار کوچک

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

7. تکرار فرایند

پس از Split، Merge یا حذف خوشه‌ها، الگوریتم دوباره داده‌ها را به مراکز جدید اختصاص می‌دهد و محاسبات را تکرار می‌کند.

این فرایند تا زمانی ادامه پیدا می‌کند که معیار توقف موردنظر برقرار شود یا حداکثر تعداد تکرارها به پایان برسد.

پارامترهای مهم الگوریتم ISODATA

یکی از ویژگی‌های مهم ISODATA این است که رفتار الگوریتم به مجموعه‌ای از پارامترها وابسته است. بنابراین نمی‌توان گفت ISODATA کاملاً بدون تنظیمات کار می‌کند.

انتخاب این پارامترها می‌تواند تأثیر قابل‌توجهی بر تعداد و ساختار خوشه‌های نهایی داشته باشد.

تفاوت ISODATA و K-means

ISODATA از نظر پایه محاسباتی شباهت زیادی به K-means دارد. هر دو الگوریتم داده‌ها را بر اساس فاصله از مراکز خوشه گروه‌بندی می‌کنند و به‌صورت تکرارشونده مراکز را به‌روزرسانی می‌کنند.

اما تفاوت مهم این است که K-means تعداد خوشه‌ها را از ابتدا ثابت در نظر می‌گیرد، در حالی که ISODATA می‌تواند بر اساس شرایط داده‌ها خوشه‌ها را Split یا Merge کند.

بنابراین می‌توان ISODATA را به‌صورت ساده یک روش تطبیقی‌تر نسبت به K-means در نظر گرفت که اجازه می‌دهد تعداد خوشه‌ها در جریان اجرای الگوریتم تغییر کند.

چرا ISODATA با Hierarchical Clustering متفاوت است؟

شباهت ظاهری میان عملیات Split و Merge در ISODATA و برخی عملیات مورد استفاده در خوشه‌بندی سلسله مراتبی ممکن است باعث این اشتباه شود که ISODATA یک روش Hierarchical است؛ اما این دو الگوریتم از نظر ساختار متفاوت هستند.

در Hierarchical Clustering هدف اصلی ساخت یک hierarchy از روابط میان نمونه‌ها یا خوشه‌هاست؛ اما در ISODATA هدف پیدا کردن یک پارتیشن مناسب و تطبیقی از داده‌ها است.

برای آشنایی بیشتر با Hierarchical Clustering می‌توانید مقاله خوشه‌بندی سلسله مراتبی را مطالعه کنید.

یک مثال ساده از Split و Merge در ISODATA

فرض کنید داده‌های یک تصویر در فضای ویژگی به چند گروه تقسیم شده‌اند. در ابتدا الگوریتم چهار مرکز برای چهار خوشه در نظر می‌گیرد.

پس از چند مرحله، مشخص می‌شود یکی از خوشه‌ها پراکندگی بسیار زیادی دارد. این موضوع می‌تواند نشانه آن باشد که دو گروه متفاوت در یک خوشه قرار گرفته‌اند. اگر انحراف معیار از آستانه مشخص بیشتر باشد، الگوریتم می‌تواند آن خوشه را Split کند.

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

در نتیجه، اگر الگوریتم با چهار خوشه شروع شده باشد، ممکن است بعد از این عملیات مثلاً به پنج خوشه برسد یا به سه خوشه کاهش پیدا کند.

این دقیقاً یکی از تفاوت‌های مهم ISODATA با K-means است: تعداد خوشه‌ها در ISODATA می‌تواند در طول فرایند تغییر کند.

کاربردهای الگوریتم ISODATA

پردازش تصویر

یکی از کاربردهای شناخته‌شده ISODATA، گروه‌بندی پیکسل‌های تصویر بر اساس ویژگی‌های آن‌هاست. ویژگی‌هایی مانند مقدار شدت، رنگ یا ویژگی‌های استخراج‌شده از تصویر می‌توانند برای ایجاد خوشه‌های مختلف استفاده شوند.

تصاویر ماهواره‌ای و سنجش از دور

در Remote Sensing، معمولاً داده‌هایی با تعداد زیادی ویژگی طیفی وجود دارد. ISODATA می‌تواند برای خوشه‌بندی و طبقه‌بندی بدون ناظر تصاویر ماهواره‌ای استفاده شود.

برای مثال، پیکسل‌های یک تصویر ماهواره‌ای ممکن است بر اساس ویژگی‌های طیفی در گروه‌هایی قرار گیرند که بعدها توسط متخصص به کلاس‌هایی مانند آب، پوشش گیاهی، خاک یا مناطق شهری نسبت داده شوند.

Image Segmentation

در برخی مسائل segmentation می‌توان از خوشه‌بندی برای گروه‌بندی پیکسل‌هایی با ویژگی‌های مشابه استفاده کرد. ISODATA به دلیل قابلیت تطبیق تعداد خوشه‌ها می‌تواند در چنین مسئله‌هایی مفید باشد.

تشخیص الگو

ISODATA می‌تواند در مسائل Pattern Recognition نیز برای کشف گروه‌های طبیعی در داده‌های بدون برچسب مورد استفاده قرار گیرد.

داده‌های چندبعدی

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

مزایا و محدودیت‌های ISODATA

مزایای ISODATA

• یک روش بدون ناظر است و به برچسب داده‌ها نیاز ندارد.
• تعداد خوشه‌ها می‌تواند در طول اجرای الگوریتم تغییر کند.
• امکان Split کردن خوشه‌های بیش از حد پراکنده وجود دارد.
• امکان Merge کردن خوشه‌های بسیار نزدیک وجود دارد.
• برای داده‌هایی که ساختار دقیق آن‌ها از ابتدا مشخص نیست می‌تواند مفید باشد.
• در برخی کاربردهای پردازش تصویر و سنجش از دور عملکرد مناسبی دارد.

محدودیت‌های ISODATA

• تنظیم پارامترها: نتیجه الگوریتم به انتخاب آستانه‌ها و سایر پارامترهای کنترلی وابسته است.
• وابستگی به مقداردهی اولیه: مراکز اولیه و تنظیمات شروع می‌توانند بر نتیجه نهایی تأثیر بگذارند.
• هزینه محاسباتی: Split و Merge و تکرارهای متعدد می‌توانند نسبت به K-means ساده‌تر، اجرای پیچیده‌تری ایجاد کنند.
• حساسیت به مقیاس ویژگی‌ها: در صورت تفاوت شدید مقیاس متغیرها، معیار فاصله ممکن است تحت تأثیر ویژگی‌های بزرگ‌تر قرار گیرد.
• فرض ضمنی درباره ساختار خوشه‌ها: مانند بسیاری از روش‌های مبتنی بر مرکز، نوع فاصله و شکل خوشه‌ها بر کیفیت نتیجه تأثیر دارند.
• تفسیر خوشه‌ها: خوشه‌های به‌دست‌آمده الزاماً معادل کلاس‌های واقعی یا معنایی داده نیستند.

آیا ISODATA هنوز کاربرد دارد؟

بله. اگرچه الگوریتم‌های جدیدتر و روش‌های متنوع‌تری برای Clustering توسعه یافته‌اند، ISODATA همچنان به‌عنوان یک روش کلاسیک و قابل‌توجه برای خوشه‌بندی تطبیقی بدون ناظر شناخته می‌شود.

اهمیت آن به‌خصوص در مسائلی بیشتر است که تعداد مناسب گروه‌ها از ابتدا مشخص نیست و می‌توان با استفاده از معیارهایی مانند پراکندگی و فاصله میان خوشه‌ها ساختار اولیه را اصلاح کرد.

در پروژه‌های مدرن Machine Learning، انتخاب ISODATA باید بر اساس ویژگی داده و هدف مسئله انجام شود و بهتر است نتیجه آن با روش‌هایی مانند K-means، DBSCAN یا Hierarchical Clustering نیز مقایسه شود.

مسیر یادگیری الگوریتم‌های خوشه‌بندی از کجا شروع می‌شود؟

برای یادگیری Clustering بهتر است الگوریتم‌ها را فقط به‌صورت جداگانه مطالعه نکنید، بلکه ابتدا مفهوم کلی خوشه‌بندی را یاد بگیرید و سپس روش‌ها را بر اساس نوع مسئله مقایسه کنید.

1. مبانی یادگیری بدون ناظر
2. مفهوم فاصله و شباهت
3. K-means
4. Hierarchical Clustering
5. ISODATA
6. DBSCAN
7. Gaussian Mixture Models
8. معیارهای ارزیابی Clustering
9. مقایسه الگوریتم‌ها روی داده واقعی

برای شروع می‌توانید مقاله خوشه‌بندی را مطالعه کنید و سپس سراغ الگوریتم‌های تخصصی‌تر بروید.

سؤالات متداول درباره الگوریتم ISODATA

الگوریتم ISODATA چیست؟

ISODATA یک الگوریتم خوشه‌بندی بدون ناظر و تکرارشونده است که با بررسی ویژگی‌هایی مانند پراکندگی داخل خوشه و فاصله میان مراکز، می‌تواند خوشه‌ها را Split یا Merge کند.

آیا ISODATA یک الگوریتم خوشه‌بندی سلسله مراتبی است؟

خیر. ISODATA معمولاً یک روش پارتیشن‌بندی تطبیقی و مبتنی بر مرکز در نظر گرفته می‌شود. عملیات Split و Merge آن به معنی ایجاد یک ساختار سلسله‌مراتبی یا Dendrogram نیست.

تفاوت ISODATA و K-means چیست؟

هر دو الگوریتم از تخصیص داده‌ها به مراکز خوشه و به‌روزرسانی مراکز استفاده می‌کنند، اما K-means تعداد خوشه‌ها را ثابت در نظر می‌گیرد، در حالی که ISODATA می‌تواند با استفاده از Split و Merge تعداد خوشه‌ها را تغییر دهد.

Split در ISODATA چیست؟

اگر یک خوشه بیش از حد پراکنده باشد و معیار پراکندگی آن از آستانه مشخصی عبور کند، ISODATA می‌تواند آن را به چند خوشه کوچک‌تر تقسیم کند. این عملیات Split نام دارد.

Merge در ISODATA چیست؟

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

آیا ISODATA به تعیین تعداد خوشه‌ها نیاز دارد؟

ISODATA برای شروع معمولاً به تعداد اولیه‌ای از خوشه‌ها یا مراکز نیاز دارد، اما تعداد نهایی خوشه‌ها می‌تواند در طول اجرای الگوریتم تغییر کند. بنابراین برخلاف K-means، تعداد اولیه الزاماً تعداد نهایی خوشه‌ها نیست.

مهم‌ترین کاربرد ISODATA چیست؟

ISODATA در کاربردهایی مانند پردازش تصویر، طبقه‌بندی بدون ناظر تصاویر ماهواره‌ای، سنجش از دور، Image Segmentation و تشخیص الگو استفاده شده است.

آیا ISODATA یک روش یادگیری بدون ناظر است؟

بله. ISODATA برای خوشه‌بندی داده‌ها به برچسب کلاس از پیش تعیین‌شده نیاز ندارد و به همین دلیل در دسته روش‌های یادگیری بدون ناظر قرار می‌گیرد.

جمع‌بندی

الگوریتم ISODATA یکی از روش‌های کلاسیک خوشه‌بندی بدون ناظر است که از نظر پایه به K-means شباهت دارد، اما با قابلیت مهم Split و Merge می‌تواند ساختار و تعداد خوشه‌ها را در طول اجرای الگوریتم تطبیق دهد.

نکته مهم این است که ISODATA را نباید صرفاً به دلیل داشتن عملیات Split و Merge، یک الگوریتم Hierarchical Clustering در نظر گرفت. ISODATA ساختار درختی یا Dendrogram ایجاد نمی‌کند و بیشتر به‌عنوان یک روش پارتیشن‌بندی تطبیقی مبتنی بر مرکز شناخته می‌شود.

قدرت اصلی ISODATA زمانی مشخص می‌شود که تعداد مناسب خوشه‌ها از ابتدا کاملاً مشخص نباشد و بخواهیم بر اساس ویژگی‌هایی مانند پراکندگی داخل خوشه و فاصله میان مراکز، ساختار خوشه‌ها را اصلاح کنیم.

با این حال، نتیجه ISODATA به انتخاب پارامترها، مقداردهی اولیه و ویژگی‌های داده وابسته است. بنابراین در یک پروژه واقعی بهتر است نتیجه آن با الگوریتم‌هایی مانند K-means، DBSCAN و Hierarchical Clustering مقایسه شود.