الگوریتم خوشه‌بندی کامیلیون (CHAMELEON): آموزش کامل خوشه‌بندی مبتنی بر گراف

1.اهداف یادگیری

پس از مطالعه این فصل، خواننده باید بتواند:

1. جایگاه الگوریتم کامیلیون را در میان روش‌های خوشه‌بندی مبتنی بر گراف و سلسله‌مراتبی توضیح دهد.
2. مسئله‌ای را که کامیلیون برای حل آن طراحی شده است، به‌صورت دقیق صورت‌بندی کند.
3. ایده مدل‌سازی پویا (Dynamic Modeling) را از رویکردهای ایستا (Static Modeling) متمایز سازد.
4. معیارهای پیوستگی نسبی (Interconnectivity  Relative) و نزدیکی نسبی  (Relative Closeness) را تعریف، محاسبه و تفسیر کند.
5. دو فاز اصلی الگوریتم، یعنی افراز اولیه گراف و ادغام سلسله‌مراتبی پویا را تشریح نماید.
6. رفتار الگوریتم را در حضور نویز، داده‌های نامتوازن، شکل‌های پیچیده و ابعاد بالا تحلیل کند.
7. پیچیدگی زمانی و حافظه‌ای روش را بررسی و درباره مقیاس‌پذیری آن قضاوت کند.
8. ابرپارامترهای کلیدی مانند k، تعداد افرازهای اولیه و پارامتر α را تنظیم و آثار آن‌ها را تحلیل نماید.
9. کامیلیون را با روش‌هایی مانند K-means، DBSCAN، طیفی (Spectral) و CURE مقایسه کند.
10. برای یک مسئله واقعی، مناسب‌بودن یا نبودن این الگوریتم را از منظر علمی و عملی ارزیابی نماید.

2.پیش‌نیازها

برای فهم دقیق این فصل، آشنایی با موارد زیر ضروری است:

• ریاضیات گسسته: مفاهیم پایه نظریه گراف، شامل رأس، یال، وزن، مؤلفه همبند و برش گراف
• جبر خطی مقدماتی: بردار، فاصله، شباهت و نمایش داده‌ها در فضای ویژگی
• آمار و داده‌کاوی مقدماتی: مفهوم خوشه، انسجام درون‌خوشه‌ای و جدایی بین‌خوشه‌ای
• الگوریتم‌ها: آشنایی مقدماتی با خوشه‌بندی سلسله‌مراتبی، k-nearest neighbors و مفاهیم پایه پیچیدگی زمانی
• برنامه‌نویسی علمی: توانایی خواندن و پیاده‌سازی شبه‌کد، ترجیحاً در محیط‌هایی مانند Python
• درک شهودی از یادگیری بدون ناظر: تفاوت خوشه‌بندی با طبقه‌بندی و نبود برچسب در داده‌های آموزشی

.

۳. چکیده

الگوریتم کامیلیون یکی از مهم‌ترین روش‌های خوشه‌بندی مبتنی بر گراف است که برای کشف خوشه‌هایی با شکل، اندازه و چگالی متفاوت طراحی شده است. مسئله اصلی که این الگوریتم به آن پاسخ می‌دهد، ناتوانی بسیاری از روش‌های کلاسیک در شناسایی ساختارهای پیچیده داده است؛ به‌ویژه هنگامی که خوشه‌ها کروی نیستند، مرزهای نامنظم دارند، یا تراکم آن‌ها در بخش‌های مختلف فضا یکسان نیست. ایده محوری کامیلیون، استفاده از مدل‌سازی پویا برای تصمیم‌گیری درباره ادغام خوشه‌ها است.

در این رویکرد، شباهت دو خوشه نه بر اساس یک معیار ثابت و سراسری، بلکه با توجه به ساختار درونی خود آن خوشه‌ها سنجیده می‌شود. الگوریتم در دو مرحله عمل می‌کند: نخست، گراف k-نزدیک‌ترین همسایه ساخته و به زیرخوشه‌های کوچک افراز می‌شود؛ سپس این زیرخوشه‌ها بر پایه دو معیار پیوستگی نسبی و نزدیکی نسبی به‌صورت سلسله‌مراتبی ادغام می‌شوند. در این فصل، زمینه شکل‌گیری الگوریتم، مفاهیم پایه، مبانی نظری و ریاضی، روند اجرا، شبه‌کد، مثال‌های آموزشی، تحلیل رفتاری، پیچیدگی محاسباتی، تنظیم پارامترها، محدودیت‌ها، کاربردها و توسعه‌های جدید کامیلیون به‌صورت نظام‌مند و دانشگاهی بررسی می‌شود.

.

۴. بستر علمی و مسئله عملی

خوشه‌بندی یکی از بنیادی‌ترین مسائل در یادگیری بدون ناظر است. هدف آن، کشف ساختارهای پنهان در داده‌ها بدون تکیه بر برچسب‌های از پیش تعیین‌شده است. با وجود قدمت این مسئله، بخش مهمی از دشواری آن از این واقعیت ناشی می‌شود که «خوشه» یک شیء کاملاً بدیهی و یکسان در همه مسائل نیست. در برخی مجموعه‌داده‌ها، خوشه‌ها به‌صورت توده‌های کروی و فشرده ظاهر می‌شوند. در برخی دیگر، ساختار خوشه‌ها کشیده، خمیده، چندشاخه یا دارای چگالی متغیر است. از این‌رو، هیچ الگوریتمی با یک فرض ساده و جهان‌شمول نمی‌تواند برای همه داده‌ها مناسب باشد.

الگوریتم کامیلیون در چنین بستری مطرح شد. در دهه ۱۹۹۰، روش‌های خوشه‌بندی رایج غالباً بر مدل‌های ساده و ایستا متکی بودند. برای مثال، K-means بر این فرض تکیه دارد که هر خوشه حول یک مرکز نماینده شکل می‌گیرد و معیار اصلی تخصیص نقاط، فاصله تا آن مرکز است. این رویکرد برای خوشه‌های تقریباً کروی و هم‌اندازه مناسب است، اما در برابر ساختارهای پیچیده ناتوان می‌شود. روش‌های سلسله‌مراتبی کلاسیک نیز اگرچه انعطاف بیشتری دارند، معمولاً از قواعد ثابتی برای سنجش فاصله بین خوشه‌ها استفاده می‌کنند؛ قواعدی مانند نزدیک‌ترین زوج نقطه، دورترین زوج یا فاصله میانگین. این قواعد در بسیاری از موارد نمی‌توانند تفاوت میان «نزدیکی موضعی» و «هم‌ساختاری واقعی» را تشخیص دهند.

.

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

از نظر جایگاه علمی، کامیلیون در مرز میان سه حوزه قرار می‌گیرد:

• خوشه‌بندی مبتنی بر گراف
• افراز گراف (Graph Partitioning)
• خوشه‌بندی سلسله‌مراتبی تجمیعی

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

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

ورودی مسئله

ورودی معمولاً مجموعه‌ای از نقاط داده است:

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

خروجی مسئله

خروجی، مجموعه‌ای از خوشه‌ها است:

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

فرض‌های کلی

کامیلیون بر چند فرض ضمنی استوار است:

1. روابط محلی میان نقاط، اطلاعات مهمی درباره ساختار خوشه‌ای فراهم می‌کنند.
2. نمایش داده‌ها به‌صورت گراف k-نزدیک‌ترین همسایه، ساختار موضعی را حفظ می‌کند.
3. افراز اولیه می‌تواند داده را به زیرخوشه‌های کوچک اما نسبتاً خالص تقسیم کند.
4. کیفیت ادغام نهایی باید با توجه به ساختار درونی خوشه‌ها سنجیده شود، نه فقط با یک معیار مطلق فاصله یا چگالی.

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

.

۵. مفاهیم پایه و تعاریف ضروری

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

گراف k-نزدیک‌ترین همسایه

گراف k-نزدیک‌ترین همسایه (k-Nearest Neighbor Graph)  گرافی است که در آن هر نقطه داده یک رأس است و با k همسایه نزدیک خود به‌وسیله یال متصل می‌شود. اگر وزن یال‌ها از روی شباهت تعیین شود، گراف می‌تواند ساختار محلی داده را فشرده و مؤثر نمایش دهد.

وزن یال

وزن یال (Edge Weight) عددی است که شدت شباهت یا قدرت ارتباط میان دو رأس را نشان می‌دهد. هرچه دو نقطه مشابه‌تر باشند، معمولاً وزن یال میان آن‌ها بزرگ‌تر است.

افراز گراف

افراز گراف (Graph Partitioning) فرایندی است که در آن یک گراف به چند زیرگراف تقسیم می‌شود، به‌گونه‌ای که ارتباط درون هر زیرگراف زیاد و ارتباط میان زیرگراف‌ها کم باشد.

برش

برش (Cut) مجموع وزن یال‌هایی است که دو بخش از گراف را به هم متصل می‌کنند. اگر گراف به دو قسمت A و B تقسیم شود، برش میان آن‌ها با مجموع وزن یال‌های بین این دو مجموعه تعریف می‌شود.

خوشه

خوشه (Cluster) مجموعه‌ای از نقاط داده است که بر اساس یک معیار شباهت، نسبت به اعضای همان خوشه نزدیک‌تر یا مرتبط‌تر از نقاط خارج از آن هستند.

زیرخوشه

زیرخوشه (Sub−cluster) خوشه‌ای کوچک‌تر است که در فاز نخست الگوریتم از طریق افراز گراف تولید می‌شود و واحد پایه در مرحله ادغام سلسله‌مراتبی را تشکیل می‌دهد.

پیوستگی نسبی

پیوستگی نسبی (Relative Interconnectivity)  معیاری است که قدرت اتصال دو خوشه را نسبت به قدرت اتصال داخلی خود آن‌ها می‌سنجد.

نزدیکی نسبی

نزدیکی نسبی (Relative Closeness) معیاری است که میانگین نزدیکی یا شباهت بین دو خوشه را نسبت به نزدیکی داخلی آن‌ها ارزیابی می‌کند.

مدل‌سازی پویا

مدل‌سازی پویا (Dynamic Modeling) به این معناست که تصمیم ادغام دو خوشه بر اساس ویژگی‌های درونی همان خوشه‌ها انجام شود، نه بر پایه یک آستانه یا معیار ثابت جهانی.

نمادهای اصلی

در ادامه فصل از نمادهای زیر استفاده می‌شود:

• X={x₁,x₂,…,x_n}: مجموعه داده
• G=(V,E): گراف داده
• V: مجموعه رئوس
• E: مجموعه یال‌ها
• w(u,v): وزن یال بین دو رأس u و v
• C_i , C_j: دو خوشه یا زیرخوشه
• ∣C_i∣: تعداد اعضای خوشه Ci
• E(C_i,C_j): مجموعه یا مجموع وزن یال‌های بین دو خوشه
• EC(C_i): برش داخلی مرجع برای خوشه C_i در افراز بهینه آن
• RI(C_i,C_j): پیوستگی نسبی
• RC(C_i,C_j): نزدیکی نسبی
• α: پارامتر تنظیم اهمیت نزدیکی نسبی در تصمیم ادغام

.

۶. ایده محوری و مبانی نظری-ریاضی

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

روش‌های کلاسیک معمولاً یک معیار ثابت برای ادغام دارند. برای نمونه، در پیوند یگانه (Single Linkage)، اگر نزدیک‌ترین دو نقطه از دو خوشه به هم بسیار نزدیک باشند، دو خوشه مستعد ادغام تلقی می‌شوند. این تصمیم، هرچند ساده و سریع است، ممکن است در حضور پل‌های باریک، نویز یا ساختارهای کشیده، خوشه‌های متمایز را به اشتباه یکی کند. کامیلیون برای جلوگیری از این مسئله، ادغام را از یک «قانون مطلق» به یک «قانون نسبی و تطبیقی» تبدیل می‌کند.

۶.۱ شهود علمی الگوریتم

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

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

پس الگوریتم دو پرسش اصلی می‌پرسد:

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

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

۶.۲ نمایش گرافی داده‌ها

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

داده شده‌اند. از روی این داده‌ها گراف

ساخته می‌شود، به‌طوری که هر رأس متناظر با یک نمونه داده باشد. یال میان دو رأس زمانی ایجاد می‌شود که یکی در میان k همسایه نزدیک دیگری قرار گیرد. وزن یال معمولاً از روی شباهت محاسبه می‌شود؛ برای مثال:

یا در برخی کاربردها:

انتخاب فرم دقیق وزن تابع نوع داده و کاربرد است، اما نکته مهم آن است که وزن باید شدت پیوند موضعی را بازتاب دهد.

۶.۳ فاز افراز و نقش آن در منطق نظری

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

• روابط محلی در مقیاس کوچک، قابل اعتمادتر از روابط سراسری‌اند.
• ادغام تدریجی زیرخوشه‌های نسبتاً خالص، از ادغام مستقیم نقاط پراکنده پایدارتر است.

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

۶.۴ تعریف پیوستگی نسبی

برای دو خوشه  C_i,C_j نخست قدرت اتصال میان آن‌ها سنجیده می‌شود. این کمیت را می‌توان با مجموع وزن یال‌هایی تعریف کرد که یک رأس در C_j ​ را به رأسی در C_i​ متصل می‌کنند:

اما این مقدار به‌تنهایی کافی نیست. باید مشخص شود که این اتصال نسبت به ساختار داخلی هر خوشه چه معنایی دارد. برای این منظور، از یک معیار مرجع داخلی استفاده می‌شود. اگر  EC(C_i)بیانگر وزن برشی باشد که خوشهC_i ​ را به دو بخش تقریباً متوازن و با کمترین هزینه تقسیم می‌کند، آن‌گاه این کمیت نوعی شاخص پیوستگی داخلی خوشه است.

پیوستگی نسبی به صورت زیر تعریف می‌شود:

تفسیر

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

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

۶.۵ تعریف نزدیکی نسبی

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

میانگین وزن یال‌های بین دو خوشه را با

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

نمایش می‌دهیم. نزدیکی نسبی به‌صورت زیر تعریف می‌شود:

تفسیر

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

۶.۶ تابع شباهت برای ادغام

کامیلیون از ترکیب این دو معیار برای ساخت یک معیار تصمیم نهایی استفاده می‌کند:

که در آنα >0 پارامتری برای تنظیم اهمیت نزدیکی نسبی است.

نقش α

• اگر α=1، هر دو معیار تقریباً با وزن متوازن وارد تصمیم می‌شوند.
• اگر α>1، نزدیکی نسبی اهمیت بیشتری می‌یابد.
• اگر 0<α<1، نقش پیوستگی نسبی تقویت می‌شود.

۶.۷ فرض‌های ضمنی و دامنه اعتبار

کارایی این چارچوب به چند فرض وابسته است:

1. گراف k-همسایگی باید ساختار محلی واقعی داده را به‌خوبی ثبت کند.
2. افراز اولیه نباید زیرخوشه‌هایی کاملاً ناهمگن تولید کند.
3. وزن یال‌ها باید از نظر معنایی با مفهوم شباهت در مسئله سازگار باشد.
4. روابط خوشه‌ای باید در قالب اتصال و نزدیکی محلی قابل نمایش باشند.

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

۶.۸ جمع‌بندی نظری

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

.

۷. روند اجرا و منطق تصمیم‌گیری

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

۷.۱ ورودی‌ها

الگوریتم معمولاً این ورودی‌ها را دریافت می‌کند:

• مجموعه داده X={x₁,x₂,…,x_n}
• معیار فاصله یا شباهت
• تعداد همسایه‌ها در گراف k
• تعداد زیرخوشه‌های اولیه یا سطح مطلوب خردسازی
• پارامتر α برای ترکیب معیارهای ادغام
• در برخی پیاده‌سازی‌ها، شرط توقف یا تعداد خوشه‌های نهایی

۷.۲ مرحله نخست: ساخت نمایش گرافی

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

منطق این مرحله چنین است: اگر ساختار خوشه‌ای در داده وجود داشته باشد، این ساختار باید در روابط محلی میان نقاط منعکس شود. گراف k-همسایه دقیقاً برای ثبت همین روابط محلی ساخته می‌شود.

۷.۳ مرحله دوم: افراز اولیه گراف

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

• از نظر درونی منسجم باشند
• ارتباط خارجی محدودی داشته باشند
• تا حد امکان از نظر معنایی خالص باشند

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

۷.۴ مرحله سوم: شناسایی زوج‌های کاندید برای ادغام

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

۷.۵ مرحله چهارم: محاسبه معیارهای ادغام

برای هر زوج کاندید  C_i ,C_j ، دو معیار محاسبه می‌شود:

سپس از این دو، یک مقدار شباهت مرکب به دست می‌آید:

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

۷.۶ مرحله پنجم: انتخاب بهترین ادغام

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

منطق این انتخاب حریصانه (Greedy) است. الگوریتم فرض می‌کند بهترین ادغام محلی در هر مرحله، در نهایت به ساختاری مناسب در سطح کلان منجر می‌شود.

۷.۷ مرحله ششم: به‌روزرسانی ساختار

پس از ادغام دو خوشه، باید اطلاعات زیر به‌روزرسانی شود:

• مجموعه خوشه‌های موجود
• روابط مجاورت
• یال‌های بین خوشه‌ها
• مقادیر مرجع لازم برای محاسبه RI و RC در مراحل بعد

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

۷.۸ شرط توقف

الگوریتم می‌تواند با یکی از چند معیار زیر متوقف شود:

• رسیدن به تعداد مشخصی از خوشه‌های نهایی
• پایین آمدن بهترین مقدار شباهت زیر یک آستانه
• نبود زوج مناسب برای ادغام
• تکمیل سلسله‌مراتب مورد نظر

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

۷.۹ خروجی‌ها

خروجی نهایی می‌تواند یکی از این موارد باشد:

• مجموعه خوشه‌های نهایی
• درخت سلسله‌مراتبی ادغام‌ها
• برچسب خوشه‌ای برای هر نمونه
• ساختار مرحله‌به‌مرحله ادغام برای تحلیل بیشتر

۷.۱۰ منطق کلی تصمیم‌گیری

جوهر تصمیم‌گیری در کامیلیون را می‌توان چنین خلاصه کرد:

1. داده را در مقیاس محلی به‌خوبی نمایش بده.
2. ساختار را به واحدهای کوچک و نسبتاً خالص بشکن.
3. هر ادغام را نه با معیار مطلق، بلکه با معیار تطبیقی انجام بده.
4. تنها خوشه‌هایی را ادغام کن که از نظر درونی و بین‌خوشه‌ای، رفتار سازگار نشان می‌دهند.

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

---

۸. شبه‌کد استاندارد (Pseudocode)

Algorithm CHAMELEON(X, k, m, alpha, stop_rule)

Input:
    X         : dataset of n objects
    k         : number of nearest neighbors
    m         : number of initial sub-clusters
    alpha     : weight parameter for relative closeness
    stop_rule : stopping criterion

Output:
    C_final   : final set of clusters

1:  Construct weighted k-nearest neighbor graph G from X
2:  Partition G into m small sub-clusters:
        C = {C1, C2, ..., Cm}
3:  Build adjacency structure among sub-clusters

4:  while stop_rule is not satisfied do
5:      best_score <- -infinity
6:      best_pair  <- null

7:      for each adjacent pair (Ci, Cj) in C do
8:          Compute EC(Ci, Cj)
9:          Compute internal connectivity references EC(Ci), EC(Cj)
10:         Compute RI(Ci, Cj)
11:         Compute RC(Ci, Cj)
12:         score <- RI(Ci, Cj) * (RC(Ci, Cj) ^ alpha)

13:         if score > best_score then
14:             best_score <- score
15:             best_pair  <- (Ci, Cj)
16:         end if
17:      end for

18:      if best_pair is null then
19:          break
20:      end if

21:      Merge the two clusters in best_pair into Cnew
22:      Remove merged clusters from C
23:      Add Cnew to C
24:      Update adjacency relations and required statistics
25:  end while

26:  return C

۹. مثال‌های آموزشی

۹.۱ مثال شهودی: دو رودخانه و یک کانال باریک

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

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

۹.۲ مثال عددی پایه: محاسبه پیوستگی نسبی

دو زیرخوشه   C₁ , C₂را در نظر بگیرید.

فرض کنید:

می‌خواهیم(RI(Ci,Cj را محاسبه کنیم.

فرمول:

جایگذاری:

تفسیر

مقدار RI=1  نشان می‌دهد که قدرت اتصال میان دو خوشه، هم‌تراز با پیوستگی داخلی متوسط آن‌ها است. بنابراین از منظر اتصال ساختاری، این دو خوشه نامزد مناسبی برای ادغام هستند.

---

۹.۳ مثال عددی متوسط: محاسبه نزدیکی نسبی

اکنون فرض کنید برای همین دو خوشه، میانگین وزن یال‌های بین‌خوشه‌ای و درون‌خوشه‌ای به شکل زیر باشد:

ابتدا مخرج را محاسبه می‌کنیم:

حال:

تفسیر

مقدار RC≈0.982 بسیار نزدیک به ۱ است. این یعنی نزدیکی بین دو خوشه تقریباً با مقیاس نزدیکی داخلی آن‌ها برابری می‌کند. پس از منظر هندسی نیز این دو خوشه فاصله غیرعادی از هم ندارند.

---

۹.۴ مثال عددی ترکیبی: تصمیم نهایی ادغام

حال همان داده‌ها را با ∝=2در نظر بگیرید. می‌خواهیم امتیاز نهایی ادغام را محاسبه کنیم.

از دو مثال قبل داریم:

جایگذاری:

تفسیر

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

---

۹.۵ مثال پیشرفته‌تر: مقایسه دو زوج کاندید

فرض کنید دو زوج کاندید برای ادغام داریم:

در این حالت زوج دوم انتخاب می‌شود.

تفسیر

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