الگوریتم DIANA چیست؟ آموزش کامل خوشه‌بندی سلسله‌مراتبی تقسیمی در یادگیری ماشین

دکتر محمدرضا عاطفی
جولای 11, 2026

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

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

مفهوم خوشه‌بندی سلسله‌مراتبی و تفاوت دو رویکرد تجمیعی (Agglomerative) و تقسیمی (Divisive) را به‌صورت دقیق توضیح دهد.
جایگاه الگوریتم DIANA را در خانواده روش‌های یادگیری بدون ناظر (Unsupervised Learning) تبیین کند.
منطق تشکیل گروه جداشونده (Splinter Group) در DIANA را از منظر شهودی و ریاضی تحلیل کند.
مراحل اجرای الگوریتم DIANA را گام‌به‌گام روی یک مجموعه‌داده ساده اجرا و تفسیر کند.
نقش معیار فاصله (Distance Metric) را در کیفیت خوشه‌بندی DIANA تشریح کند.
فرمول‌های اصلی مورد استفاده در انتخاب عنصر اولیه جداسازی و انتقال تدریجی اعضا را بنویسد و تفسیر نماید.
خروجی درختی الگوریتم، یعنی دندروگرام (Dendrogram)، را بخواند و از آن برای استخراج تعداد خوشه‌ها استفاده کند.
مزایا، محدودیت‌ها، پیچیدگی محاسباتی، و موارد کاربرد DIANA را با رویکردی انتقادی ارزیابی کند.
الگوریتم DIANA را با روش‌هایی مانند AGNES و k–means مقایسه کند.
تشخیص دهد که DIANA در چه نوع مسائل و چه مقیاس داده‌ای انتخاب مناسبی است و در چه شرایطی باید از روش‌های جایگزین استفاده کرد.

2. چکیده

الگوریتم DIANA که مخفف Divisive Analysis است، یکی از مهم‌ترین روش‌های کلاسیک در خوشه‌بندی سلسله‌مراتبی تقسیمی به‌شمار می‌آید. برخلاف روش‌های تجمیعی که از نقاط منفرد آغاز می‌کنند و به‌تدریج خوشه‌ها را ادغام می‌نمایند، DIANA با یک خوشه واحد شامل همه نمونه‌ها شروع می‌شود و در هر مرحله، ناهمگن‌ترین خوشه را به دو زیرخوشه تقسیم می‌کند. هسته تصمیم‌گیری این روش بر پایه شناسایی یک گروه جداشونده (Splinter Group) است؛ یعنی مجموعه‌ای از نقاط که نسبت به سایر اعضای خوشه از عدم‌شباهت بیشتری برخوردارند و بنابراین جداسازی آن‌ها ساختار درونی داده را آشکارتر می‌کند.

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

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

3. مقدمه

خوشه‌بندی (Clustering) یکی از بنیادی‌ترین مسائل در یادگیری بدون ناظر است. در این مسئله، هدف آن است که مجموعه‌ای از داده‌های بدون برچسب به گروه‌هایی تقسیم شوند که اعضای هر گروه از دید یک معیار شباهت، به یکدیگر نزدیک‌تر و از اعضای سایر گروه‌ها دورتر باشند. برخلاف طبقه‌بندی (Classification) که در آن برچسب‌های از پیش تعیین‌شده در دسترس‌اند، در خوشه‌بندی ساختار پنهان داده باید مستقیماً از خود داده‌ها کشف شود.

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

خوشه‌بندی سلسله‌مراتبی معمولاً به دو خانواده اصلی تقسیم می‌شود:

رویکرد تجمیعی (Agglomerative):

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

رویکرد تقسیمی (Divisive):

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

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

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

4. جایگاه الگوریتم در یادگیری ماشین

الگوریتم DIANA در ساختار کلی یادگیری ماشین در مسیر زیر قرار می‌گیرد:

Machine Learning→Unsupervised Learning→Clustering→Hierarchical Clustering→Divisive Clustering→DIANA

این جایگاه نشان می‌دهد که DIANA در دسته روش‌هایی قرار دارد که:

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

در داده‌کاوی (Data Mining)، DIANA از این جهت مهم است که امکان تحلیل ساختار داده در چند سطح را فراهم می‌کند. در بسیاری از مسائل، تحلیلگر نمی‌خواهد فقط بداند «چند خوشه» وجود دارد، بلکه می‌خواهد بداند این خوشه‌ها چگونه از یک کل بزرگ‌تر منشعب شده‌اند. این نوع بینش در تحلیل مشتریان، داده‌های زیستی، اسناد، و حتی ساختارهای اجتماعی بسیار ارزشمند است.

مقایسه کوتاه این دو دیدگاه به فهم جایگاه DIANA کمک می‌کند:

ویژگی	AGNES	DIANA
جهت حرکت	پایین به بالا	بالا به پایین
نقطه آغاز	هر داده یک خوشه	همه داده‌ها یک خوشه
عملیات اصلی	ادغام خوشه‌ها	تقسیم خوشه‌ها
تمرکز اولیه	شباهت‌های محلی	تفاوت‌های کلان
خروجی	دندروگرام	دندروگرام

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

از سوی دیگر، DIANA در مقایسه با روش‌هایی مانند k-means یا DBSCAN، کمتر برای تولید سریع خوشه‌ها در داده‌های بزرگ به‌کار می‌رود و بیشتر برای:

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

مناسب است.

5. تعاریف و مفاهیم پایه

5.1 مجموعه داده

فرض کنید مجموعه داده شامل n مشاهده باشد:

که هر مشاهده x_i می‌تواند یک بردار در فضای p-بعدی باشد:

2.5 معیار فاصله

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

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

فاصله گاور (Gower Distance):

برای داده‌های ترکیبی شامل متغیرهای عددی، رتبه‌ای، دودویی و اسمی مناسب است (Gower, 1971).

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

5.3 ماتریس فاصله

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

در بسیاری از پیاده‌سازی‌های DIANA، ابتدا ماتریس فاصله محاسبه می‌شود. این ماتریس را با D نشان می‌دهیم:

اگرماتریس فاصله هسته محاسباتی DIANA است. هرچند ذخیره آن باعث سرعت دسترسی به فاصله‌ها می‌شود، اما حافظه‌ای در مرتبه O(n^2)نیاز دارد..

5.4 خوشه

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

5.5 قطر خوشه

قطر خوشه (Cluster Diameter) بیشترین فاصله میان دو عضو آن خوشه است:

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

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

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

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

5.7 دندروگرام

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

دندروگرام نمودار درختی خروجی خوشه‌بندی سلسله‌مراتبی است. در DIANA، دندروگرام از بالا به پایین قابل تفسیر است:

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

5.8 گروه جداشونده

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

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

6. مسئله‌ای که الگوریتم حل می‌کند

DIANA مسئله زیر را هدف قرار می‌دهد:

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

در این مسئله، چند نکته مهم وجود دارد:

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

بنابراین DIANA صرفاً یک الگوریتم برای تفکیک داده‌ها نیست؛ بلکه ابزاری برای تحلیل ساختار چندسطحی داده است.

7. اهمیت و ضرورت

اهمیت DIANA را باید هم از منظر نظری و هم از منظر عملی بررسی کرد.

7.1 اهمیت نظری

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

7.2 اهمیت آموزشی

از آنجا که DIANA منطق تصمیم‌گیری خود را به‌صورت نسبتاً شفاف بیان می‌کند، برای آموزش مفاهیمی مانند:

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

بسیار مناسب است.

7.3 اهمیت تفسیری

در برخی مسائل، نخستین تقسیم داده بسیار مهم است. برای مثال، در تحلیل ریسک، ممکن است ابتدا بخواهیم مشتریان بسیار پرریسک را از سایر مشتریان جدا کنیم. در تحلیل زیستی، ممکن است هدف، تفکیک اولیه گروه‌های ژنی بسیار متفاوت باشد. DIANA به‌دلیل حرکت از کل به جزء، برای چنین تحلیل‌هایی مناسب است.

7.4 اهمیت عملی

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

8. مبانی نظری

الگوریتم DIANA بر سه ایده نظری اصلی استوار است:

ناهمگنی درون‌خوشه‌ای
جداسازی تدریجی اعضای متفاوت
تصمیم‌گیری حریصانه

8.1 ناهمگنی درون‌خوشه‌ای

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

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

8.2 جداسازی اعضای متفاوت

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

این نقطه به‌عنوان آغازگر Splinter Group انتخاب می‌شود.

8.3 تصمیم‌گیری حریصانه

DIANA یک الگوریتم حریصانه (Greedy Algorithm) است. یعنی در هر مرحله، بر اساس بهترین تصمیم محلی عمل می‌کند؛ بدون آنکه همه تقسیم‌های ممکن را به‌صورت کامل جست‌وجو کند.

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

8.4 ارتباط با مفهوم درخت تصمیم

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

9. مبانی ریاضی

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

9.1 میانگین فاصله یک نقطه از یک خوشه

اگر C یک خوشه باشد و xi ∈C، میانگین فاصله xi از سایر اعضای خوشه چنین تعریف می‌شود:

که در آن:

این مقدار نشان می‌دهد xi تا چه اندازه از بقیه اعضای خوشه دور است.

9.2 انتخاب نقطه آغازگر Splinter Group

نقطه آغازگر گروه جداشونده به‌صورت زیر انتخاب می‌شود:

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

تفسیر علمی این رابطه آن است که الگوریتم ابتدا «دورافتاده‌ترین» یا «ناسازگارترین» عضو خوشه را شناسایی می‌کند. البته این نقطه لزوماً داده پرت نیست؛ ممکن است نماینده یک زیرساختار واقعی در داده باشد.

این نقطه، بذر اولیه (seed) یا هسته اولیه گروه جداشونده خواهد بود.

9.3 تشکیل دو مجموعه اولیه

پس از انتخاب xs، دو مجموعه ساخته می‌شود:

که در آن:

A گروه جداشونده
B: باقی‌مانده خوشه اصلی

در ابتدا، A فقط یک عضو دارد و B شامل سایر اعضای خوشه است.

9.4 معیار انتقال عضو از B به A

برای هر نقطه xi∈ R^p ، الگوریتم بررسی می‌کند که آیا این نقطه باید از B به A منتقل شود یا خیر. معیار تصمیم‌گیری معمولاً به شکل زیر بیان می‌شود:

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

9.5 انتخاب خوشه برای تقسیم بعدی

پس از پایان یک تقسیم، الگوریتم باید مشخص کند کدام خوشه در گام بعدی تقسیم شود. یکی از معیارهای رایج، انتخاب خوشه‌ای با بیشترین قطر (Diameter) یا بیشترین ناهمگنی درونی است:

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

10. فرمول‌ها و تعریف تمام نمادها

در این بخش، فرمول‌های اصلی الگوریتم به‌صورت منظم ارائه می‌شوند.

10.1 مجموعه داده

نماد	تعریف
X	مجموعه کل داده‌ها
x-i	مشاهده یا نمونه iام
n	تعداد مشاهدات
p	تعداد ویژگی‌ها

10.2 تابع فاصله

نماد	تعریف
d	تابع فاصله یا عدم شباهت
x_i ,x_j	دو مشاهده از مجموعه داده

10.3 ماتریس فاصله

نماد	تعریف
D	ماتریس فاصله
D(i,j)	فاصله بین مشاهده i و مشاهده j

10.4 میانگین فاصله از خوشه

نماد	تعریف
C	خوشه جاری
(	C
d (x_i,C)	میانگین فاصله x-i از سایر اعضای C

10.5 قطر خوشه

10.6 انتخاب نقطه آغازگر

نماد	تعریف
x-s	نقطه آغازگر گروه جداشونده
Arg max	مقداری از ورودی که تابع را بیشینه می‌کند

10.7 گروه جداشونده و گروه باقی‌مانده

نماد	تعریف
A	گروه جداشونده
B	اعضای باقی‌مانده خوشه
C∖A	اعضای C که در A نیستند

10.8 معیار انتقال

11. مثال شهودی

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

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

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

این مثال نشان می‌دهد که DIANA فقط یک فرمول ریاضی نیست؛ بلکه الگوریتمی است که نوعی منطق تحلیلی انسانی را شبیه‌سازی می‌کند:

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

12. منطق ریاضی

منطق ریاضی DIANA بر پایه مقایسه دو نوع فاصله بنا شده است:

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

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

12.1 چرا میانگین فاصله مهم است؟

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

برای مثال، ممکن است نقطه x-i به یک عضو از A نزدیک باشد، اما از سایر اعضای A بسیار دور باشد. در این حالت، تصمیم‌گیری بر اساس نزدیک‌ترین همسایه می‌تواند گمراه‌کننده باشد. میانگین فاصله این مشکل را تا حدی کاهش می‌دهد.

12.2 چرا معیار Δ معنادار است؟

معیار انتقال چنین است:

12.3 ماهیت حریصانه تصمیم

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

به همین دلیل، DIANA را باید یک روش اکتشافی و ساختاری دانست، نه الگوریتمی که تضمین بهینگی مطلق ارائه می‌دهد.

12.4 ارتباط با مفهوم ناهمگنی

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

13. مراحل اجرای الگوریتم با توضیحات لازم برای پیاده‌سازی

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

13.1 ورودی الگوریتم

الگوریتم DIANA به یک نمایش از داده‌ها و یک معیار عدم‌شباهت نیاز دارد. ورودی را می‌توان در یکی از دو فرم زیر دریافت کرد:

حالت اول: ماتریس داده

اگر داده‌ها به‌صورت ماتریس ویژگی‌ها داده شوند، داریم:

که در آن:

n: تعداد نمونه‌ها
p: تعداد ویژگی‌ها
x-i: بردار ویژگی نمونه iام

در این حالت، پیش از اجرای اصلی DIANA باید ماتریس فاصله ساخته شود.

حالت دوم: ماتریس عدم‌شباهت یا فاصله

در بسیاری از پیاده‌سازی‌ها، الگوریتم مستقیماً با ماتریس فاصله کار می‌کند:

که باید ویژگی‌های زیر را داشته باشد:

این حالت در عمل بسیار متداول است؛ زیرا DIANA تقریباً تمام تصمیم‌های خود را بر اساس فاصله‌ها می‌گیرد.

13.2 خروجی الگوریتم

خروجی DIANA یک ساختار سلسله‌مراتبی تقسیمی است که معمولاً به‌صورت یکی از قالب‌های زیر نمایش داده می‌شود:

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

13.3 ایده اجرایی در یک نگاه

الگوریتم DIANA از یک خوشه شامل همه نقاط شروع می‌کند. سپس در هر مرحله:

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

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

13.4 آماده‌سازی اولیه

پیش از شروع حلقه اصلی الگوریتم، چند گام مقدماتی لازم است.

گام 1: انتخاب معیار فاصله

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

فاصله اقلیدسی (Euclidean)
فاصله منهتن (Manhattan)
فاصله گاور (Gower) برای داده‌های ترکیبی
سایر معیارهای متناسب با دامنه مسئله

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

گام 2: محاسبه یا دریافت ماتریس فاصله

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

گام 3: ایجاد خوشه اولیه

در ابتدای اجرا، فقط یک خوشه داریم:

یعنی همه نمونه‌ها در یک خوشه قرار می‌گیرند.

گام 4: ایجاد ساختار ثبت تاریخچه تقسیم‌ها

برای تولید دندروگرام یا بازسازی مسیر تقسیم‌ها، باید در هر مرحله اطلاعات زیر ثبت شود:

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

این اطلاعات برای خروجی تفسیری و رسم درخت ضروری است.

13.5 انتخاب خوشه‌ای که باید تقسیم شود

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

منطق انتخاب

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

سپس خوشه‌ای انتخاب می‌شود که بیشترین قطر را داشته باشد:

تفسیر اجرایی

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

نکته پیاده‌سازی

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

13.6 آغاز تقسیم درون خوشه انتخاب‌شده

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

گام 1: محاسبه میانگین فاصله هر عضو از بقیه اعضا

برای هر x-i، مقدار زیر محاسبه می‌شود:

گام 2: انتخاب عضو آغازگر

عضوی که بیشترین میانگین فاصله را دارد، به‌عنوان شروع گروه جداشونده انتخاب می‌شود:

تفسیر

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

13.7 تشکیل دو مجموعه موقت

پس از انتخاب x-s، خوشه ∗ ^C به‌صورت موقت به دو بخش تقسیم می‌شود:

که در آن:

A: گروه جداشونده (Splinter Group)
B: گروه باقی‌مانده

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

13.8 ارزیابی انتقال اعضا از B به A

اکنون الگوریتم هر عضو موجود در B را از نظر تعلق خوشه‌ای بازبینی می‌کند.

برای هر برای هر xi∈B، دو کمیت محاسبه می‌شود:

سپس معیار انتقال تعریف می‌شود:

قاعده تصمیم

اگر:

آنگاه xi به A منتقل می‌شود.

معنای این قاعده

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

13.9 راهبرد انتقال در هر تکرار

در این مرحله دو روش کلی برای پیاده‌سازی وجود دارد، اما برای سازگاری با منطق کلاسیک DIANA، روش زیر مناسب‌تر است:

روش حریصانه مرحله‌ای

برای همه اعضای B، مقدار (Δ(xi محاسبه شود.
عضوی انتخاب شود که بیشترین مقدار Δ را دارد.
اگر این مقدار مثبت باشد، آن عضو از B به A منتقل شود.
پس از انتقال، چون ترکیب A و B عوض شده است، مقادیر Δ دوباره محاسبه شوند.
این روند تکرار شود تا دیگر هیچ عضو با Δ بزرگتر از صفر باقی نماند.

دلیل بازمحاسبه

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

مزیت این راهبرد

این رویکرد باعث می‌شود گروه جداشونده به‌صورت تدریجی و سازگار رشد کند.

13.10 پایان تقسیم یک خوشه

فرایند تقسیم خوشه *C زمانی پایان می‌یابد که دیگر هیچ عضو باقی‌مانده‌ای در B شرایط انتقال به A را نداشته باشد. یعنی:

در این حالت، تقسیم خوشه *Cبه دو زیرخوشه نهایی می‌شود:

13.11 به‌روزرسانی ساختار سلسله‌مراتبی

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

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

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

13.12 تکرار فرایند روی خوشه‌های جدید

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

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

این چرخه تا زمان برآورده شدن معیار توقف ادامه می‌یابد.

13.13 معیار توقف

الگوریتم DIANA می‌تواند با معیارهای توقف مختلفی متوقف شود. انتخاب معیار توقف به هدف مسئله وابسته است.

معیار 1: تک‌عضوی شدن همه خوشه‌ها

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

معیار 2: رسیدن به تعداد مشخصی خوشه

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

معیار 3: حداقل اندازه خوشه

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

معیار 4: آستانه ناهمگنی

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

معیار 5: نبود تقسیم معنادار

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

13.14 تابع هدف یا منطق تصمیم‌گیری

الگوریتم DIANA در فرم کلاسیک خود معمولاً مانند k -means دارای یک تابع هدف صریح و واحد نیست که در هر مرحله مستقیماً کمینه یا بیشینه شود. در عوض، بر اساس یک منطق تصمیم‌گیری ساختاری و حریصانه عمل می‌کند.

این منطق شامل دو اصل است:

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

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

13.15 فرم بازگشتی یا تکراری پیاده‌سازی

پیاده‌سازی DIANA را می‌توان به دو صورت طراحی کرد:

پیاده‌سازی تکراری

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

پیاده‌سازی بازگشتی

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

توصیه پیاده‌سازی

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

13.16 ملاحظات پیاده‌سازی برای برنامه‌نویس

در پیاده‌سازی واقعی، چند نکته باید مورد توجه قرار گیرد:

1. هزینه محاسبه فاصله‌ها

اگر ماتریس فاصله از ابتدا محاسبه و ذخیره شود، دسترسی سریع می‌شود، اما حافظه O(n^2) نیاز دارد.

2. بازمحاسبه میانگین فاصله‌ها

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

3. مدیریت خوشه‌ها

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

4. ثبت تاریخچه تقسیم

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

5. داده‌های با فاصله‌های مساوی

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

13.17 تفسیر نهایی فرایند اجرا

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

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

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

14. سه مثال عددی با سطوح سختی متفاوت

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

14.1 مثال اول: مثال بسیار ساده با داده‌های یک‌بعدی

صورت مسئله

پنج نقطه یک‌بعدی زیر را در نظر بگیرید:

هدف آن است که اولین تقسیم DIANA را به‌صورت دستی به‌دست آوریم.

داده ورودی

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

گام اول: تشکیل خوشه اولیه

در ابتدا:

گام دوم: محاسبه میانگین فاصله هر نقطه از سایر نقاط

گام سوم: انتخاب عضو آغازگر گروه جداشونده

بیشترین مقدار مربوط به 11 است. بنابراین:

گام چهارم: بررسی انتقال اعضای B به A

برای 10:

هیچ عضو دیگری منتقل نمی‌شود.

پاسخ نهایی

اولین تقسیم DIANA چنین است:

تفسیر نتیجه

الگوریتم به‌درستی شکاف بزرگ بین {1,2,3} و {10,11} را شناسایی کرده است. این مثال نشان می‌دهد که DIANA ابتدا تفاوت کلان را استخراج می‌کند.

14.2 مثال دوم: مثال دوبعدی با فاصله اقلیدسی

صورت مسئله

شش نقطه دوبعدی زیر را در نظر بگیرید:

هدف، اجرای اولین تقسیم DIANA است.

داده ورودی

فاصله اقلیدسی:

تحلیل شهودی پیش از محاسبه

سه نقطه اول نزدیک هم هستند، دو نقطه x5 ,x4 نیز نزدیک هم‌اند، و x6 بسیار دورافتاده است. انتظار داریم DIANA ابتدا x6 را جدا کند.

گام اول: خوشه اولیه

گام دوم: شناسایی آغازگر

به دلیل دوری زیاد x6 از همه نقاط دیگر، میانگین فاصله آن از سایر نقاط از همه بیشتر است. پس:

گام سوم: بررسی انتقال سایر اعضا

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

برای مثال، برای (x5=(8,9

فاصله آن تا (x6=(25,25 تقریباً برابر است با:

در حالی که میانگین فاصله x5 تا نقاط x1 , x2, x3 ,x4 به‌مراتب کمتر از این مقدار است. پس:

بنابراین x5 به A منتقل نمی‌شود.

همین منطق برای x1 , x2, x3 ,x4 نیز برقرار است. هیچ‌یک به گروه x6 نزدیک‌تر از گروه باقی‌مانده نیستند.

پاسخ نهایی

در اولین تقسیم:

تفسیر نتیجه

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

14.3 مثال سوم: مثال با سختی بیشتر و دو مرحله تقسیم

صورت مسئله

داده‌های زیر را در نظر بگیرید:

هدف آن است که دو مرحله نخست DIANA را اجرا کنیم.

داده ورودی

فاصله یک‌بعدی:

مرحله اول: تقسیم اول

گام 1: خوشه اولیه

گام 2: انتخاب آغازگر

نقطه 21 یا 20 بیشترین میانگین فاصله را از بقیه دارد. با محاسبه دقیق، معمولاً 21 آغازگر می‌شود. بنابراین:

گام 3: بررسی انتقال

برای 20:

بنابراین 20 به A منتقل می‌شود.

اکنون:

برای 9، فاصله متوسط آن تا B بسیار کمتر از فاصله متوسط آن تا {20و21} است؛ بنابراین منتقل نمی‌شود. همین وضعیت برای 8 ,3,2,1 نیز برقرار است.

نتیجه مرحله اول

مرحله دوم: انتخاب خوشه بعدی برای تقسیم

اکنون دو خوشه داریم:

مرحله سوم: تقسیم خوشه {1,2,3,8,9}

گام 1: انتخاب آغازگر

در این خوشه، نقطه 9 بیشترین میانگین فاصله را از سایرین دارد، پس:

پس 8 به A منتقل می‌شود.

اکنون:

پاسخ نهایی

پس از دو مرحله، ساختار خوشه‌بندی چنین است:

تفسیر نتیجه

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

15. شبه‌کد الگوریتم DIANA

در این بخش، شبه‌کد الگوریتم به‌صورت آموزشی و پیاده‌سازانه ارائه می‌شود. این شبه‌کد عمداً روشن و قابل ترجمه به Python، MATLAB، R یا Java نوشته شده است.

Algorithm DIANA(X or D)

Input:
    X : data matrix, or
    D : dissimilarity matrix
Output:
    Hierarchical divisive clustering tree

1. If input is X, compute dissimilarity matrix D
2. Initialize cluster list:
       C = {all objects in one cluster}
3. Initialize tree/history structure

4. While stopping criterion is not met:

5.     Select cluster C* from current clusters
       such that C* is the most heterogeneous
       (for example, has the largest diameter)

6.     For each object x in C*:
           compute average dissimilarity from x to all other objects in C*

7.     Choose splinter seed xs:
           xs = object with largest average dissimilarity

8.     Initialize:
           A = {xs}              // splinter group
           B = C* \ {xs}         // remainder group

9.     Repeat:

10.        For each object x in B:
               compute:
               avg_to_B = average dissimilarity from x to other objects in B
               avg_to_A = average dissimilarity from x to objects in A
               Delta(x) = avg_to_B - avg_to_A

11.        Let x_best = argmax Delta(x) over x in B

12.        If Delta(x_best) > 0:
               move x_best from B to A
           Else:
               stop the repeat loop

13.     End Repeat

14.     Replace cluster C* in cluster list with A and B
15.     Record split (C* -> A, B) in tree/history

16. End While

17. Return clustering tree/history

15.1 توضیح خط‌به‌خط شبه‌کد

خط 1: اگر داده خام وارد شده باشد، ابتدا ماتریس فاصله ساخته می‌شود.
خط 2: همه داده‌ها در یک خوشه قرار می‌گیرند.
خط 5: خوشه‌ای انتخاب می‌شود که بیشترین ناهمگنی را دارد.
خط 6 و 7: دورافتاده‌ترین عضو خوشه به‌عنوان بذر گروه جداشونده انتخاب می‌شود.
خط 8: تقسیم موقت به دو گروه A و B انجام می‌شود.
خط 10 تا 12: اعضای B از نظر تعلق به A بازبینی می‌شوند.
خط 14 و 15: تقسیم نهایی در ساختار اصلی ثبت می‌شود.
خط 16: این فرایند تا تحقق معیار توقف ادامه می‌یابد.

15.2 نکته مهم برای پیاده‌سازی

در پیاده‌سازی واقعی، باید مشخص شود که:

معیار ناهمگنی دقیقاً چیست،
معیار توقف چگونه تعریف می‌شود،
قواعد حل تساوی چگونه اعمال می‌شوند،
و ساختار درختی خروجی چگونه ذخیره می‌شود.

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

16. تحلیل پیچیدگی زمانی و حافظه (Complexity Analysis)

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

16.1 پیچیدگی زمانی (Time Complexity)

به‌طور کلی، الگوریتم DIANA از نظر محاسباتی بسیار سنگین‌تر از الگوریتم‌های تجمیعی (Agglomerative) مانند AGNES است. دلیل اصلی این امر، فرایند مکرر یافتن گروه جداشونده (Splinter Group) از طریق محاسبه میانگین فاصله‌ها درون خوشه‌هاست.

1. محاسبه ماتریس فاصله اولیه

اگر داده‌های ورودی به‌صورت ماتریس ویژگی‌های خام xi∈ R^(n×p) باشند، در گام نخست باید ماتریس فاصله D∈ R^(n×n) محاسبه شود. پیچیدگی این گام برابر است با:

که در آن n تعداد نمونه‌ها و p تعداد ویژگی‌ها (بعد داده) است.

2. یافتن آغازگر و انتقال تدریجی اعضا

در هر سطح از تقسیم سلسله‌مراتب، فرض کنید می‌خواهیم خوشه‌ای با اندازه m را تقسیم کنیم:

یافتن عضو آغازگر (xs): برای محاسبه میانگین فاصله هر یک از m عضو نسبت به سایر اعضا، به محاسباتی از مرتبه O(m^2) نیاز داریم.
انتقال تدریجی اعضا: در هر مرحله از حلقه تکرار داخلی، فرض کنید گروه جداشونده دارای ∣A∣ عضو و گروه باقی‌مانده دارای ∣B∣ عضو است (A∣+∣B∣=(m∣. برای هر عضو x∈Bباید میانگین فاصله آن تا اعضای A (هزینه محاسباتی O(|A|)و اعضای B (هزینه محاسباتی (O(|B|)را محاسبه کنیم. انجام این کار برای تمام اعضای موجود در B هزینه محاسباتی معادل با موارد زیر دارد:

از آنجا که این بررسی با هر بار انتقال یک عضو تکرار می‌شود (که در بدترین حالت ممکن است تا O(m) بار تکرار شود)، مجموع پیچیدگی زمانی برای تقسیم کامل یک خوشه به اندازه m در بدترین حالت به صورت زیر خواهد بود:

3. مجموع پیچیدگی زمانی کل الگوریتم

اگر الگوریتم را تا رسیدن به خوشه‌های تک‌عضوی (درخت کامل با n برگ) ادامه دهیم:

در بدترین حالت (Worst Case): زمانی رخ می‌دهد که در هر مرحله، تقسیم‌ها بسیار نامتوازن باشند (مثلاً در هر گام فقط یک نقطه از خوشه جدا شود). در این صورت، طول زنجیره تقسیم برابر با n خواهد بود و پیچیدگی کل به صورت زیر محاسبه می‌شود:

• در بهترین حالت (Best Case): زمانی رخ می‌دهد که تقسیم‌ها کاملاً متوازن (Balanced) باشند؛ یعنی در هر گام، هر خوشه دقیقاً به دو زیرخوشه با اندازه مساوی تقسیم شود. در این سناریو، عمق درخت برابر با log2(n) خواهد بود و پیچیدگی زمانی کل به صورت زیر کاهش می‌یابد:

بنابراین، پیچیدگی زمانی کلی DIANA در حالت عمومی بین بنابراین، پیچیدگی زمانی کلی DIANA در حالت عمومی بین O(n^3)تا O(n^4)متغیر است که استفاده از آن را برای داده‌های بسیار بزرگ (Big Data) بدون روش‌های تقریب یا نمونه‌گیری غیرممکن می‌سازد.

16.2 پیچیدگی حافظه (Space Complexity)

پیچیدگی حافظه الگوریتم DIANA عمدتاً تحت تأثیر ماتریس عدم‌شباهت (Dissimilarity Matrix) قرار دارد:

ذخیره‌سازی ماتریس فاصله: برای محاسبه و تصمیم‌گیری سریع، الگوریتم به ماتریس فاصله نیاز دارد که فضایی از مرتبه O(n^2) اشغال می‌کند.
ذخیره ساختار درخت و متغیرهای موقت: ساختارهای داده‌ای که برای نگهداری اطلاعات دندروگرام، فهرست خوشه‌های فعلی و خوشه‌های موقت A و B استفاده می‌شوند، به حافظه‌ای از مرتبهO(n^2) نیاز دارند.

در نتیجه، پیچیدگی حافظه نهایی الگوریتم برابر باO(n^2) است. در ابعاد بسیار بزرگ، محدودیت حافظه (به دلیل ذخیره‌سازی ماتریس n×n) معمولاً پیش از محدودیت زمان پردازش به گلوگاه (Bottleneck) سیستم تبدیل می‌شود.

17. ابرپارامترها و روش تنظیم آن‌ها (Hyperparameters and Tuning)

الگوریتم DIANA به دلیل ماهیت ناپارامتری (Non-parametric) خود، در مقایسه با روش‌هایی مانند مخلوط‌های گوسی (GMM) یا شبکه‌های عصبی، ابرپارامترهای کمتری دارد. با این حال، تصمیم‌گیری‌های کلیدی وجود دارند که مستقیماً بر ساختار درخت نهایی و افرازهای حاصل از آن اثر می‌گذارند.

17.1 معرفی ابرپارامترها و تنظیمات ساختاری

1. معیار محاسبه فاصله/عدم‌شباهت (Distance Metric)

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

اقلیدسی (Euclidean): مناسب برای داده‌های پیوسته و هم‌مقیاس با فرضیات فضایی کروی.
منهتن (Manhattan): مناسب برای داده‌های با ابعاد بالا یا زمانی که تأثیر داده‌های پرت (Outliers) باید تعدیل شود.
گاور (Gower): زمانی استفاده می‌شود که مجموعه‌داده شامل متغیرهای ترکیبی (عددی، طبقه‌بندی‌شده و باینری) باشد.

روش تنظیم: تنظیم این پارامتر معمولاً بر اساس دانش دامنه (Domain Knowledge) انجام می‌شود. همچنین می‌توان عملکرد مدل را با استفاده از معیارهای ارزیابی درونی مانند «ضریب نیمرخ» (Silhouette Coefficient) به ازای معیارهای مختلف فاصله سنجید.

2. تعداد خوشه‌های هدف (k )

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

روش تنظیم:

روش آرنج (Elbow Method): محاسبه و ترسیم مجموع مربعات درون‌خوشه‌ای (WSS) به ازای مقادیر مختلف k و یافتن نقطه خمیدگی یا آرنج در نمودار.
شاخص نیمرخ (Silhouette Index): محاسبه میانگین ضریب نیمرخ برای افرازهای حاصل از برش‌های مختلف دندروگرام؛ مقداری که این شاخص را بیشینه کند به عنوان k بهینه انتخاب می‌شود.
ارتفاع برش دندروگرام (Height Threshold): مشخص کردن یک آستانه فاصله (عدم‌شباهت) برای برش دادن شاخه‌های دندروگرام.

3. استانداردسازی داده‌ها (Standardization)

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

روش تنظیم: توصیه می‌شود که متغیرها پیش از اجرای الگوریتم با استفاده از روش‌هایی مانند استانداردسازی Z-score یا مقیاس‌دهی Min-Max پیش‌پردازش شوند، مگر آنکه مقیاس واقعی متغیرها اهمیت ذاتی داشته باشد.

18. کاربردهای واقعی

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

تحلیل بیوانفورماتیک و ژنومیک (Bioinformatics & Genomics):تقسیم‌بندی توالی‌های ژنتیکی یا داده‌های بیان ژن (Gene Expression Profiling) به گروه‌های بزرگ کارکردی، به طوری که ابتدا شاخه‌های اصلی زیستی (مانند راسته‌ها یا خانواده‌های بزرگ پروتئینی) و سپس زیرگروه‌های دقیق‌تر شناسایی شوند.
تقسیم‌بندی بازار و مشتریان (Market Segmentation):تقسیم پایگاه مشتریان شرکت‌ها به بخش‌های کلان رفتاری (مثلاً مشتریان وفادار، مشتریان گذری، مشتریان کم‌مصرف) و سپس خرد کردن هر دسته به بخش‌های کوچک‌تر جهت شخصی‌سازی کمپین‌های بازاریابی.
پزشکی و تشخیص بیماری‌ها (Medical Diagnosis):دسته‌بندی بیماران بر اساس ویژگی‌های بالینی و پاسخ‌های فیزیولوژیک برای شناسایی الگوهای اپیدمیولوژیک کلان و کشف زیرگونه‌های ناشناخته از یک بیماری خاص.
تحلیل ساختار وب و شبکه‌های اجتماعی (Web & Social Network Analysis):تقسیم‌بندی جوامع آنلاین یا ساختار وب‌سایت‌ها به خوشه‌های محتوایی بزرگ برای بهبود سیستم‌های توصیه‌گر (Recommender Systems) و ناوبری وب.
رده‌بندی اسناد و متون (Document Hierarchical Classification):سازماندهی مجموعه‌ای از مقالات یا اسناد متنی در ساختار درختی از موضوعات کلی (مانند علم، هنر، ورزش) به سمت موضوعات تخصصی‌تر درون هر شاخه.

19. مزایا

الگوریتم DIANA به عنوان یک رویکرد تقسیمی (Divisive)، از ویژگی‌های مثبتی برخوردار است که آن را از روش‌های تجمیعی متمایز می‌کند:

قدرت بالا در شناسایی ساختارهای کلان (Global Structure):به دلیل رویکرد بالا به پایین (Top-Down)، تصمیم‌گیری‌های اولیه الگوریتم بر اساس کل داده‌ها انجام می‌شود. این ویژگی باعث می‌شود که ساختارهای اصلی و خوشه‌های کلان بسیار دقیق‌تر از روش‌های پایین به بالا (که در ابتدا بر اساس تصمیم‌های محلی نقاط منفرد شکل می‌گیرند) شناسایی شوند.
عدم نیاز به تعریف تعداد خوشه‌ها از ابتدا:برخلاف الگوریتم‌های افرازی نظیر k -means، نیازی به حدس زدن تعداد بهینه خوشه‌ها پیش از اجرا نیست؛ کاربر می‌تواند پس از رسم دندروگرام، در مورد افراز مناسب تصمیم‌گیری کند.
انعطاف‌پذیری در توقف زودهنگام:اگر کاربر تنها به تعداد کمی خوشه (مثلاً K=3) نیاز داشته باشد، الگوریتم DIANA می‌تواند پس از رسیدن به تعداد خوشه‌های مورد نظر متوقف شود. این کار از انجام محاسبات سنگین در سطوح پایین‌تر جلوگیری می‌کند؛ مزیتی که در روش‌های تجمیعی وجود ندارد زیرا آن‌ها باید مسیر را تا انتهای ادغام ادامه دهند.
مستندسازی مسیر با دندروگرام واضح:نمایش بصری سلسله‌مراتب تقسیمی به صورت درختی، تحلیل‌های مدیریتی و علمی را به دلیل قابلیت تفسیر بالا تسهیل می‌کند.

20. محدودیت‌ها

با وجود مزایای ذکر شده، DIANA چالش‌های جدی دارد که پیاده‌سازان باید از آن‌ها آگاه باشند:

پیچیدگی محاسباتی بسیار سنگین:پیچیدگی زمانیO(n^3) در حالت متوسط و O(n^4)در بدترین حالت، این الگوریتم را برای مجموعه‌داده‌هایی با بیش از چند هزار نمونه کاملاً غیرعملی می‌سازد.
عدم امکان جبران اشتباهات در مراحل بعدی (Greedy Nature):مانند سایر روش‌های سلسله‌مراتبی، تصمیم‌هایی که برای تقسیم یک خوشه در مراحل اولیه گرفته می‌شوند، غیرقابل بازگشت (Irreversible) هستند. اگر نقطه‌ای در اولین تقسیم به اشتباه به خوشه A فرستاده شود، الگوریتم در گام‌های بعدی راهی برای اصلاح این خطا و انتقال آن به خوشه B ندارد.
حساسیت شدید به نویز و داده‌های پرت:نقاط پرت (Outliers) به دلیل داشتن فاصله زیاد از سایر نقاط، به سرعت به عنوان آغازگر گروه جداشونده (Splinter Seed) انتخاب می‌شوند. این امر می‌تواند منجر به شکل‌گیری خوشه‌های تک‌عضوی کاذب و انحراف ساختار دندروگرام شود.
نیاز به حافظه بالا:نیاز به ذخیره ماتریس فاصله با مرتبهO(n^2) کارایی الگوریتم را روی سیستم‌هایی با حافظه رم محدود به شدت کاهش می‌دهد.

21. مقایسه با الگوریتم‌های مشابه

برای درک بهتر جایگاه DIANA، مقایسه‌ای ساختاریافته بین این الگوریتم، الگوریتم تجمیعی AGNES و الگوریتم افرازی k –means ارائه می‌شود:

ویژگی / الگوریتم	الگوریتم DIANA	الگوریتم AGNES	الگوریتم k -means
رویکرد خوشه‌بندی	سلسله‌مراتبی تقسیمی (Top-Down)	سلسله‌مراتبی تجمیعی (Bottom-Up)	افرازی (Partitioning)
پیچیدگی زمانی متوسط	O(n^3)	O(n^2)	O(I.k.n.p) (سریع و خطی)
نیاز به تعیین اولیه k	خیر (تعیین پس از رسم دندروگرام)	خیر (تعیین پس از رسم دندروگرام)	بله (باید از ابتدا مشخص باشد)
دقت در ساختار کلان	بسیار بالا (شروع از کل به جزء)	متوسط تا ضعیف (تا تمرکز روی جزئیات)	وابسته به مقداردهی اولیه مراکز
دقت در ساختار خرد	متوسط	بسیار بالا	خوب
قابلیت برگشت‌پذیری	خیر (تصمیمات تقسیمی نهایی هستند)	خیر (تصمیمات ادغامی نهایی هستند)	بله (نقاط در هر تکرار جابجا می‌شوند)
حجم داده قابل پشتیبانی	کوچک (کمتر از چند هزار نمونه)	متوسط (کمتر از ده هزار نمونه)	بسیار بزرگ (میلیونی)

22. جمع‌بندی

الگوریتم DIANA (Divisive Analysis) به عنوان نماینده کلاسیک روش‌های خوشه‌بندی سلسله‌مراتبی تقسیمی (Top-Down)، دیدگاهی متفاوت نسبت به سازماندهی داده‌ها ارائه می‌دهد. این الگوریتم با شروع از یک کل واحد (خوشه شامل تمام نقاط) و شکستن تدریجی و حریصانه ناهمگن‌ترین بخش‌ها بر اساس ایده گروه جداشونده (Splinter Group)، ساختار درختی کاملی از عدم‌شباهت‌های داده ایجاد می‌کند.

اگرچه پیچیدگی محاسباتی بالا O(n^3) کاربرد آن را به مجموعه‌داده‌های کوچک تا متوسط محدود می‌کند، اما توانایی استثنایی آن در کشف ساختارهای کلان و عدم نیاز به فرضیات اولیه درباره تعداد خوشه‌ها، DIANA را به ابزاری ارزشمند در تحلیل‌های اکتشافی داده، بیوانفورماتیک و تقسیم‌بندی‌های استراتژیک بازار تبدیل کرده است. در مواجهه با داده‌های واقعی، ترکیب خروجی سلسله‌مراتب این الگوریتم با معیارهای اعتبارسنجی مانند شاخص نیمرخ، راهکاری دقیق برای دستیابی به افرازهای بهینه و تفسیرپذیر فراهم می‌سازد.

23. نکات کلیدی فصل

الگوریتم DIANA (Divisive Analysis) یکی از شناخته‌شده‌ترین روش‌های خوشه‌بندی سلسله‌مراتبی تقسیمی است که از یک خوشه شامل تمام داده‌ها آغاز می‌کند و به‌تدریج آن را به زیرخوشه‌های کوچک‌تر تقسیم می‌نماید.
برخلاف روش‌های تجمیعی مانند AGNES که از داده‌های منفرد شروع کرده و خوشه‌ها را ادغام می‌کنند، DIANA رویکردی بالا به پایین (Top-Down) دارد.
هسته تصمیم‌گیری در DIANA بر اساس مفهوم گروه جداشونده (Splinter Group) است؛ یعنی ابتدا ناسازگارترین عضو خوشه انتخاب شده و سپس سایر اعضایی که شباهت بیشتری به آن دارند، به گروه جداشونده منتقل می‌شوند.
الگوریتم DIANA به ماتریس فاصله یا عدم‌شباهت وابسته است؛ بنابراین انتخاب معیار فاصله مانند اقلیدسی، منهتن، کسینوسی یا گاور اثر مستقیم بر نتیجه خوشه‌بندی دارد.
DIANA به تعیین اولیه تعداد خوشه‌ها نیاز ندارد، اما برای استفاده عملی از خروجی آن معمولاً باید دندروگرام در سطحی مشخص برش داده شود.
پیچیدگی زمانی الگوریتم در حالت عمومی بالا است و معمولاً بینO(n^3) تاO(n^4)گزارش می‌شود؛ ازاین‌رو برای داده‌های بسیار بزرگ مناسب نیست مگر با روش‌های تقریب، نمونه‌گیری یا بهینه‌سازی.
پیچیدگی حافظه الگوریتم عمدتاً به ذخیره ماتریس فاصله مربوط است و برابر با O(n^2)ست.
DIANA برای تحلیل‌های اکتشافی، داده‌های زیستی، بخش‌بندی مشتریان، تحلیل اسناد، تشخیص الگوهای پزشکی و مطالعه ساختارهای شبکه‌ای کاربرد دارد.
مهم‌ترین مزیت DIANA توانایی آن در شناسایی ساختارهای کلان داده در مراحل اولیه خوشه‌بندی است.
مهم‌ترین محدودیت DIANA حساسیت به داده‌های پرت، هزینه محاسباتی بالا و غیرقابل بازگشت بودن تصمیم‌های تقسیمی است.
دندروگرام خروجی DIANA ابزار مهمی برای تفسیر سلسله‌مراتب داده‌ها و تصمیم‌گیری درباره تعداد خوشه‌هاست.
برای داده‌های واقعی، پیش‌پردازش، مقیاس‌بندی ویژگی‌ها، حذف یا کنترل داده‌های پرت و انتخاب معیار فاصله مناسب نقش بسیار مهمی در کیفیت خروجی دارند.

24. پرسش‌های مفهومی

الگوریتم DIANA از نظر جهت حرکت خوشه‌بندی چه تفاوتی با AGNES دارد؟
منظور از خوشه‌بندی سلسله‌مراتبی تقسیمی چیست؟
چرا DIANA را یک الگوریتم حریصانه (Greedy) می‌دانند؟
مفهوم Splinter Group در الگوریتم DIANA چیست و چگونه تشکیل می‌شود؟
چرا انتخاب معیار فاصله در DIANA اهمیت اساسی دارد؟
اگر داده‌ها دارای ویژگی‌هایی با مقیاس‌های بسیار متفاوت باشند، چه مشکلی در اجرای DIANA ایجاد می‌شود؟
چرا DIANA برای داده‌های بسیار بزرگ مناسب نیست؟
تفاوت دندروگرام حاصل از روش‌های تقسیمی و تجمیعی در چیست؟
در چه شرایطی DIANA نسبت به AGNES می‌تواند انتخاب مناسب‌تری باشد؟
چرا نقاط پرت می‌توانند ساختار خوشه‌بندی DIANA را تحت تأثیر قرار دهند؟
معیار قطر خوشه (Cluster Diameter) در DIANA چه نقشی دارد؟
چگونه می‌توان از شاخص نیمرخ برای انتخاب تعداد خوشه‌ها در خروجی DIANA استفاده کرد؟
چرا تصمیم‌های اولیه در DIANA اهمیت زیادی دارند؟
آیا DIANA برای داده‌های غیرعددی قابل استفاده است؟ در صورت مثبت بودن، چه نوع معیار فاصله‌ای مناسب است؟
تفاوت اصلی DIANA با k -means از نظر نیاز به تعیین تعداد خوشه‌ها چیست؟

25. تمرین‌های پایان فصل

تمرین 1: تحلیل مفهومی

داده‌های زیر را در نظر بگیرید:

X={2,3,4,20,21,22}

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

تمرین 2: محاسبه گروه جداشونده

فرض کنید خوشه‌ای شامل چهار نقطه زیر باشد:

A(1,1) , B(1,2) , C(8,8) , D(9,8)

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

تمرین 3: مقایسه الگوریتم‌ها

یک جدول مقایسه‌ای بین DIANA، AGNES، DBSCAN و k -means تهیه کنید. معیارهای مقایسه شامل موارد زیر باشد:

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

تمرین 4: تحلیل دندروگرام

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

تمرین 5: اثر مقیاس داده

داده‌های زیر مربوط به سه مشتری است:

مشتری	درآمد سالانه	تعداد خرید ماهانه
A	500000000	2
B	520000000	3
C	100000000	20

توضیح دهید چرا اجرای مستقیم DIANA روی این داده‌ها ممکن است گمراه‌کننده باشد. سپس یک روش پیش‌پردازش مناسب پیشنهاد دهید.

تمرین 6: تحلیل پیچیدگی

اگر الگوریتم DIANA روی مجموعه‌داده‌ای با n=5000نمونه اجرا شود، چه چالش‌هایی از نظر زمان و حافظه ایجاد می‌شود؟ پاسخ خود را با توجه به پیچیدگی‌هایO(n^2)وO(n^3) تحلیل کنید.

تمرین 7: داده‌های پرت

فرض کنید مجموعه‌داده‌ای شامل 100 نقطه فشرده در اطراف مرکز (0,0) و یک نقطه دورافتاده در (100,100) باشد. توضیح دهید DIANA در اولین تقسیم چگونه رفتار خواهد کرد و چرا.

تمرین 8: انتخاب معیار فاصله

برای هر یک از داده‌های زیر، معیار فاصله مناسب پیشنهاد دهید:

داده‌های عددی پیوسته استانداردشده
داده‌های متنی مبتنی بر بردار TF-IDF
داده‌های شامل متغیرهای عددی و طبقه‌ای
داده‌های باینری حضور/عدم حضور ویژگی‌ها

26. پروژه پیشنهادی

عنوان پروژه

پیاده‌سازی، ارزیابی و مقایسه الگوریتم DIANA با روش‌های خوشه‌بندی رایج روی داده‌های واقعی

هدف پروژه

هدف این پروژه آن است که دانشجو یا پژوهشگر بتواند الگوریتم DIANA را از پایه پیاده‌سازی کرده، خروجی آن را با روش‌هایی مانند AGNES، k -means و DBSCAN مقایسه کند و اثر معیارهای فاصله، استانداردسازی داده و انتخاب سطح برش دندروگرام را تحلیل نماید.

داده‌های پیشنهادی

برای اجرای پروژه می‌توان از یکی از مجموعه‌داده‌های زیر استفاده کرد:

مجموعه‌داده Iris
مجموعه‌داده Wine
داده‌های مشتریان فروشگاه شامل سن، درآمد، تعداد خرید و ارزش خرید
داده‌های بیان ژن در مقیاس کوچک
داده‌های متنی کوتاه تبدیل‌شده به بردارهای TF-IDF

مراحل انجام پروژه

گردآوری یا انتخاب مجموعه‌داده مناسب
پاک‌سازی داده‌ها و حذف مقادیر گمشده
استانداردسازی یا نرمال‌سازی ویژگی‌ها
محاسبه ماتریس فاصله
پیاده‌سازی الگوریتم DIANA از پایه
رسم دندروگرام حاصل
انتخاب تعداد خوشه‌ها با استفاده از شاخص نیمرخ یا تحلیل دندروگرام
اجرای الگوریتم‌های مقایسه‌ای مانند AGNES، k -means و DBSCAN
مقایسه خروجی‌ها بر اساس معیارهای درونی خوشه‌بندی
تحلیل مزایا، محدودیت‌ها و رفتار الگوریتم روی داده مورد مطالعه

خروجی‌های مورد انتظار

کد کامل Python
نمودار دندروگرام
نمودار پراکندگی خوشه‌ها در فضای دوبعدی
جدول مقایسه شاخص‌های ارزیابی
گزارش تحلیلی 10 تا 15 صفحه‌ای
بحث درباره مناسب بودن یا نبودن DIANA برای داده انتخاب‌شده

معیارهای ارزیابی پروژه

معیار	امتیاز
درستی پیاده‌سازی الگوریتم	25
کیفیت پیش‌پردازش داده‌ها	15
تحلیل دندروگرام و انتخاب خوشه‌ها	15
مقایسه با سایر الگوریتم‌ها	20
کیفیت گزارش نهایی	15
خلاقیت در تحلیل یا توسعه روش	10

27. منابع

Aggarwal, C. C. (2015). Data mining: The textbook. Springer.

Anderberg, M. R. (1973). Cluster analysis for applications. Academic Press.

Ankerst, M., Breunig, M. M., Kriegel, H.-P., & Sander, J. (1999). OPTICS: Ordering points to identify the clustering structure. ACM SIGMOD Record, 28(2), 49-60. https://doi.org/10.1145/304181.304187

Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1027-1035). SIAM.

Balcan, M.-F., & Liang, Y. (2016). Clustering under perturbation resilience. SIAM Journal on Computing, 45(1), 102-155. https://doi.org/10.1137/140973338

Bock, H.-H. (1974). Automatische Klassifikation: Theoretische und praktische Methoden zur Gruppierung und Strukturierung von Daten. Vandenhoeck & Ruprecht.

Bouveyron, C., Celeux, G., Murphy, T. B., & Raftery, A. E. (2019). Model-based clustering and classification for data science. Cambridge University Press.

Chavent, M., Kuentz-Simonet, V., Labenne, A., & Saracco, J. (2018). ClustGeo: An R package for hierarchical clustering with spatial constraints. Computational Statistics, 33, 1799-1822. https://doi.org/10.1007/s00180-018-0791-1

Chavent, M., Kuentz-Simonet, V., Liquet, B., & Saracco, J. (2012). ClustOfVar: An R package for the clustering of variables. Journal of Statistical Software, 50(13), 1-16. https://doi.org/10.18637/jss.v050.i13

Everitt, B. S., Landau, S., Leese, M., & Stahl, D. (2011). Cluster analysis (5th ed.). Wiley.

Fionn Murtagh, & Contreras, P. (2012). Algorithms for hierarchical clustering: An overview. WIREs Data Mining and Knowledge Discovery, 2(1), 86-97. https://doi.org/10.1002/widm.53

Gower, J. C. (1971). A general coefficient of similarity and some of its properties. Biometrics, 27(4), 857-871. https://doi.org/10.2307/2528823

Hennig, C., Meila, M., Murtagh, F., & Rocci, R. (Eds.). (2015). Handbook of cluster analysis. CRC Press.

Jain, A. K. (2010). Data clustering: 50 years beyond k-means. Pattern Recognition Letters, 31(8), 651-666. https://doi.org/10.1016/j.patrec.2009.09.011

Kaufman, L., & Rousseeuw, P. J. (1990). Finding groups in data: An introduction to cluster analysis. Wiley.

Kriegel, H.-P., Kröger, P., Sander, J., & Zimek, A. (2011). Density-based clustering. WIREs Data Mining and Knowledge Discovery, 1(3), 231-240. https://doi.org/10.1002/widm.30

Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to information retrieval. Cambridge University Press.

Müllner, D. (2011). Modern hierarchical, agglomerative clustering algorithms. arXiv. https://arxiv.org/abs/1109.2378

Murtagh, F. (1985). Multidimensional clustering algorithms. Physica-Verlag.

Murtagh, F., & Legendre, P. (2014). Ward’s hierarchical agglomerative clustering method: Which algorithms implement Ward’s criterion? Journal of Classification, 31, 274-295. https://doi.org/10.1007/s00357-014-9161-z

Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., & Duchesnay, É. (2011). Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12, 2825-2830.

Rokach, L., & Maimon, O. (2005). Clustering methods. In O. Maimon & L. Rokach (Eds.), Data mining and knowledge discovery handbook (pp. 321-352). Springer.

Rousseeuw, P. J. (1987). Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20, 53-65. https://doi.org/10.1016/0377-0427(87)90125-7

Saxena, A., Prasad, M., Gupta, A., Bharill, N., Patel, O. P., Tiwari, A., Er, M. J., Ding, W., & Lin, C.-T. (2017). A review of clustering techniques and developments. Neurocomputing, 267, 664-681. https://doi.org/10.1016/j.neucom.2017.06.053

Sokal, R. R., & Michener, C. D. (1958). A statistical method for evaluating systematic relationships. University of Kansas Science Bulletin, 38, 1409-1438.

Tan, P.-N., Steinbach, M., Karpatne, A., & Kumar, V. (2019). Introduction to data mining (2nd ed.). Pearson.

Theodoridis, S., & Koutroumbas, K. (2009). Pattern recognition (4th ed.). Academic Press.

Xu, R., & Wunsch, D. C. (2009). Clustering. Wiley-IEEE Press.

Zhang, T., Ramakrishnan, R., & Livny, M. (1996). BIRCH: An efficient data clustering method for very large databases. ACM SIGMOD Record, 25(2), 103-114. https://doi.org/10.1145/235968.233324 Zimek, A., Schubert, E., & Kriegel, H.-P. (2012). A survey on unsupervised outlier detection in high-dimensional numerical data. Statistical Analysis and Data Mining, 5(5), 363-387. https://doi.org/10.1002/sam.11161

هوش مصنوعی

الگوریتم DIANA چیست؟ آموزش کامل خوشه‌بندی سلسله‌مراتبی تقسیمی در یادگیری ماشین

1. اهداف یادگیری انتظار می‌رود خواننده پس از مطالعه این فصل بتواند: . 2. چکیده الگوریتم DIANA که مخفف Divisive Analysis است، یکی از مهم‌ترین روش‌های کلاسیک در خوشه‌بندی سلسله‌مراتبی تقسیمی به‌شمار می‌آید. برخلاف روش‌های تجمیعی که از نقاط منفرد آغاز می‌کنند و به‌تدریج خوشه‌ها را ادغام می‌نمایند، DIANA با

توضیحات بیشتر »

جولای 11, 2026 بدون دیدگاه

هوش مصنوعی

پیاده‌سازی الگوریتم ROCK در پایتون؛ آموزش گام‌به‌گام خوشه‌بندی داده‌های طبقه‌ای

این مقاله بخش عملی آموزش الگوریتم ROCK است. اگر هنوز با مفاهیم شباهت Jaccard، گراف همسایگی، Link و تابع Goodness آشنا نیستید، ابتدا مقاله «الگوریتم ROCK چیست؟ راهنمای کامل خوشه‌بندی داده‌های طبقه‌ای» را مطالعه کنید. در این بخش، مفاهیم نظری بخش اول را به کد پایتون تبدیل می‌کنیم؛ از آماده‌سازی

توضیحات بیشتر »

جولای 11, 2026 بدون دیدگاه

هوش مصنوعی

الگوریتم ROCK چیست؟ راهنمای کامل خوشه‌بندی داده‌های طبقه‌ای

1.چکیده الگوریتم ROCK که مخفف RObust Clustering using linKs است، یکی از روش‌های مهم خوشه‌بندی سلسله‌مراتبی برای داده‌های طبقه‌ای (categorical) و باینری (binary) به‌شمار می‌آید. این الگوریتم برای موقعیت‌هایی طراحی شده است که معیارهای فاصله‌محور کلاسیک، مانند فاصله اقلیدسی، برای توصیف شباهت داده‌ها مناسب نیستند. ROCK به‌جای اتکا به

توضیحات بیشتر »

جولای 8, 2026 بدون دیدگاه