(۲۸) end for

در الگوریتم ۳-۲ فاصله‏هایی که بین هر دو خوشه محاسبه می‏گردد در یک لیست مرتب (به صورت صعودی) قرار داده می‏شوند (خطوط ۶ تا ۱۰) تا مرحله‏ی انتخاب کمترین فاصله‏ها، به آسانی انجام گیرد. هر یک از عناصر این لیست مرتب به ازاء هر دو خوشه، شامل فاصله‏ی همینگ بین دو خوشه از خوشه‏بندی مرجع (با تعداد K_bc خوشه) و خوشه‏بندی m (با تعداد K_m خوشه)، شماره‏ی خوشه در خوشه‏بندی مرجع و شماره‏ی خوشه در خوشه‏بندی m می‏باشد (خط ۸). در مرحله‏ی انتخاب خوشه‏های متناظر به این صورت عمل می‏گردد که ابتدا توسط تابع SelectNext یکی از عناصر لیست مرتب (عنصر بعد از آخرین عنصر انتخاب شده) انتخاب می‏گردد (خط ۱۲)، اگر پیش از این برای آن خوشه از خوشه‏بندی مرجع متناظری در نظر گرفته شده باشد (خط ۱۳) به دنبال انتخاب عنصر بعدی می‏رود. در غیر اینصورت چنانچه در خوشه‏بندی m نیز متناسبی برای آن پیدا نشده باشد، عنصر انتخاب شده به عنوان خوشه‏های متناسب ثبت می‏شوند (خط ۲۳).

اما در شرایطی که تعداد خوشه‏های خوشه‏بندی m کمتر از تعداد خوشه‏های خوشه‏بندی مرجع باشد نظیر به نظیر بودن به صورت یک به یک نخواهد بود و ممکن است یک خوشه در خوشه‏بندی m با چند خوشه در خوشه‏بندی مرجع متناسب گردد. از اینرو در الگوریتم ۳-۲ چنین شرایطی در خطوط ۱۳ تا ۲۰ بررسی می‏گردد. نحوه‏ی بررسی به این شکل است که اگر پیش از آن برای خوشه‏ی مورد نظر در خوشه‏بندی m نظیر به نظیری در خوشه‏بندی مرجع پیدا شده باشد، در صورتی متناسب جدید قابل ثبت خواهد بود که مقدار شمارنده‏ی Count کوچکتر از تفاضل تعداد خوشه‏های خوشه‏بندی مرجع و خوشه‏بندی m گردد. به عنوان مثال اگر خوشه‏بندی مرجع دارای ۱۰ خوشه و خوشه‏بندی m دارای ۴ خوشه باشد، تنها ۶خوشه نظیر به نظیر تکراری در خوشه‏های خوشه‏بندی m می‏تواند رخ دهد. فرایند تشریح شده تا زمانی تکرار می‏گردد که برای هر یک از خوشه‏های خوشه‏بندی مرجع یک خوشه­ی متناسب پیدا شود که با هم نظیر به نظیر باشند (خط ۲۵).
الگوریتم ۳-۲ به ازاء هر خوشه‏بندی فرایند یافتن فاصله‏ها و انتخاب کمترین‏ها را انجام می‏دهد. پیچیدگی زمانی این الگوریتم O(MK³) و پیچیدگی مکانی آن نیز O(MK) می‎باشد که M تعداد خوشه‏بندی‏ها و K حداکثر تعداد خوشه‏ها می‏باشد. با اینکه مرتبه زمانی آن از درجه‏ی ۳ می‏باشد اما از آنجا که به طور معمول تعداد خوشه‏ها عدد بزرگی نمی‏باشد، الگوریتم پیشنهادی می‏تواند زمان اجرای مناسبی را ارائه دهد.
۳-۲-۲- خوشه‏بندی‏های دارای وزن‏
همانطور که تاکنون به آن اشاره گردید، الگوریتم پیشنهادی در این پایان نامه رأی محور است که خوشه‏بندی توافقی را بر اساس وزن هر یک از خوشه‏بندی انجام می‏دهد. در این بخش قصد داریم روشی را جهت وزن‏دار نمودن هر یک از خوشه‏بندی‏های اولیه ارائه دهیم. در روش پیشنهادی یکی از معیار‏های ارزیابی خوشه‏بندی^[۱۴۵]، جهت وزن‏دهی به خوشه‏بندی‏ها استفاده می‏گردد. این معیار شاخص Davies-Bouldin نام دارد که از این پس در پایان نامه به اختصار از DB^[146] به جای این نام استفاده خواهیم نمود. قبل از ارائه‏ راه‏حلی جهت وزن دادن به خوشه‏ها، به طور مختصر و تا آنجا که به بحث ما مربوط می‏گردد در مورد معیار‏های ارزیابی خوشه‏بندی در ادامه مطالبی بیان خواهد شد.
جهت ارزیابی کیفیت خوشه‏بندی و مقایسه‏ی آن با خوشه‏بندی‏هایی دیگر، معیار‏های ارزیابی مختلفی وجود دارد. معیار‏های در [۶۴،۴] معرفی شده و مورد بررسی قرار گرفته‏اند. به طور کلی می‏توان این معیارها را به دو گروه معیار‏های خارجی^[۱۴۷] و معیار‏های داخلی^[۱۴۸] تقسیم‏بندی نمود. در اندازه‏گیری معیار‏های خارجی، درجه‏ی توافق بین دو خوشه‏بندی محاسبه می‏گردد. شاخص Rand، ضریب Jaccard، شاخص Fowlkes-Mallows و NMI از نوع معیار‏های خارجی می‏باشند. معیار‏های داخلی نیز بر اساس اطلاعات موجود در مجموعه داده‏ای بررسی می‏کنند آیا ساختار خوشه‏بندی تولید شده بوسیله‏ی یک الگوریتم خوشه‏بندی، مطابق با داده‏ها می‏باشد یا خیر. اندازه‏گیری دقت^[۱۴۹]، فشردگی^[۱۵۰]، شاخص Davies-Bouldin (DB)، شاخص Dunn نیز از نوع معیارهای داخلی بشمار می‏آیند.
برخی از معیار‏های داخلی در محاسبات خود از برچسب کلاس استفاده می‏کنند. به عبارت دیگر پس از انجام خوشه‏بندی، میزان مطابقت ساختار کشف شده بوسیله الگوریتم خوشه‏بندی با ساختار واقعی داده‏ها با بهره گرفتن از برچسب کلاس هر داده محاسبه می‏شود. لازم به ذکر است که از برچسب‏های کلاس در زمان انجام خوشه‏بندی هیچ استفاده‏ای نمی‏شود و تنها در ارزیابی کیفیت خوشه‏بندی بدست آمده و کارایی الگوریتم استفاده شده، مورد استفاده قرار می‏گیرند. معیار‏هایی که از برچسب‏های کلاس جهت ارزیابی استفاده می‏کنند شامل معیار‏های دقت، دقت معکوس^[۱۵۱] و اندازه‏گیری F می‏باشند. برخی از معیار‏های مطرح شده، جهت ارزیابی نتایج بدست آمده توسط الگوریتم پیشنهادی در این پایان نامه مورد استفاده قرار می‏گیرند که در فصل ۴ با جزئیات بیشتری به آنها اشاره خواهد شد.
همانطور که در ابتدای این بخش اشاره گردید، ما جهت وزن‏دار نمودن هر یک از خوشه‏بندی‏های اولیه از معیاری با نام شاخص DB استفاده می‏نماییم. این معیار یک معیار داخلی محسوب می‏گردد و جهت محاسبه‏ی آن به برچسب کلاس داده‏ها نیازی نمی‏باشد. لازم به ذکر است که معیار‏هایی نظیر معیار دقت می‏توانند به خوبی کیفیت خوشه‏بندی را نشان دهند. اما از آنجا که محاسبه‏ی این معیارها نیاز به برچسب کلاس داده‏ها دارد و در عمل این برچسب‏ها در انجام خوشه‏بندی وجود ندارند، امکان استفاده از چنین معیارهایی برای کاربرد مورد نظر ما (وزن‏دار نمودن خوشه‏ها) وجود ندارد. در ادامه نحوه‏ی محاسبه‏ی شاخص DB را بررسی خواهیم نمود.
فرض کنید s_i میزان پراکندگی خوشه‏ی C_i و d(C_i, C_j)=d_ij عدم تشابه بین دو خوشه‏ی C_i و C_j باشد. شاخص شباهت R_ij بین دو خوشه‏ی C_i و C_j دارای شرایط زیر است [۱۳،۲۹]:
R_ij ≥ ۰
R_ij = R_ji
اگر s_i = ۰ و s_j = ۰ آنگاه R_ij = ۰
اگر s_j > s_k و d_ij = d_ik آنگاه R_ij > R_ik
اگر s_j = s_k و d_ij < d_ik آنگاه R_ij > R_ik
این شرایط نشان می‏دهند که R_ij غیر منفی و متقارن است. یک انتخاب برای R_ij که شرایط فوق را بر آورده سازد در رابطه (۳-۴) آورده شده است:

(۳-۴)

شاخص DB نیز به صورت رابطه (۳-۵) تعریف می‏گردد:

(۳-۵)

که در آن K تعداد خوشه‏ها و می‏باشد.
عدم تشابه بین خوشه‏ی C_i و C_j در یک فضای l بعدی (l صفت خاصه) به صورت رابطه (۳-۶) تعریف می‏گردد:

(۳-۶)

پراکندگی خوشه‏ی C_i نیز به صورت رابطه (۳-۷) تعریف می‏گردد: