شکل ۳-۶، یک پیاده سازی مناسب از الگوریتم خوشه‏بندی سلسله مراتبی پایین به بالا را نمایش می‏دهد. این الگوریتم با مقدار‏دهی اولیه خوشه‏بندی C آغاز می‏شود؛ به این ترتیب که خوشه‏بندی C، شامل تمامی نمونه‏ها در قالب خوشه‏های یگانه خواهد بود. از آنجائیکه، خوشه‏بندی اولیه، شامل تعداد زیادی خوشه می‏باشد، مکررآً، جفت خوشه‏ای که دارای امتیاز بالاتری نسبت به سایرین هستند انتخاب می‏شوند و درصورتی که امتیاز آنها از حد آستانه مورد نظر بیشتر باشد، خوشه‏های با یکدیگر ادغام و تشکیل یک خوشه‏ی جدید می‏دهند، و این فرایند با جفت خوشه دیگری که دارای امتیاز بالاتری نسبت به سایرین هستند ادامه پیدا می‏کند. تابع امتیازدهی یک ترکیب وزن‏دار خطی از ویژگی‏های می‏باشد که از جفت خوشه‏ها استخراج شده، و توسط بردار وزن W پارامتردهی می‏شود. از سویی دیگر، تابع نیز، خوشه‏بندی^[۲۰۸] C را به عنوان ورودی گرفته و طبق رابطه ۳-۱۴، مجموعه‏ای از جفت خوشه‏ها را برمی‏گرداند.
رابطه (۳-۱۴) } } |
همانطور که در رابطه‏ی ۳-۱۴، مشاهده می‏شود، شامل جفت نیز می‏باشد، که برای آن، تعریف خواهد شد تا شامل ویژگی دودویی منحصر بفردی برای جفت‏های خالی نیز باشد. وزن متناظرِ آن، به همراه تمام وزن‏های دیگر، مورد یادگیری قرار می‏گیرد تا به طور موثر به عنوان آستانه‏ی خوشه‏بندی عمل نماید.

( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

۳-۲-۱-۲. آموزش الگوریتم خوشه‏بندی سلسله مراتبی
الگوریتم‏هایی که در شکل‏های ۳-۷ و ۳-۸ آمده‏اند، بیانگر یک مدل یادگیری افزایشی می‏باشند. در الگوریتم ۳-۷، بردار وزنی W، با تکراری به اندازه‏ی تعداد دوره‏های آموزشیT و یک مجموعه خوشه‏بندی شده^[۲۰۹]، بروزرسانی می‏شود؛ بدین ترتیب که این الگوریتم مکرراً، از خوشه‏بندی‏های مشخص شده برای نیل به این منظور استفاده می‏کند. این اقدام و استفاده از میانگین در بردارِ وزنی مانع از بروز بیش‏برازش^[۲۱۰] خواهد شد. همان طور که مشاهده می‏شود، هسته اصلی مدل یادگیری، رویه بروزرسانی است و بطوریکه الگوریتم یادگیری، برای بروزرسانی آخرین بردار وزنی، این رویه را فراخوانی می‏کند.

الگوریتم خوشه‏بندی سلسله مراتبی پایین به بالا با ورودی‏های (X,F):

1. 1. و

1. 1. به ازای انجام بده

1. 1. پایان حلقه اول

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

1. 1. تا زمانی که و ادامه بده

1. 1. در C، را با جایگزین کن

1. 1. حالا از میان جفت‏های باقیمانده، جفت بعدی که دارای بیشترین امتیاز است را انتخاب کن

1. 1. پایان حلقه دوم

1. 1. بازگرداندن C در خروجی

شکل ۳-۶: الگوریتم خوشه‏بندی سلسله مراتبی پایین به بالا

الگوریتم بروزرسانی، نخست مانند الگوریتم خوشه‏بندی حریصانه عمل می‏کند، تا تمام داده‏های ورودی را در قالب خوشه‏های تک عنصری در مجموعه خوشه‏بندی قرار دهد. در هر تکرار ازحلقه(خطوط ۶ تا ۱۷)، یک جفت خوشه که دارای بیشترین امتیاز نسبت به سایرین هستند ادغام می‏شوند، حلقه آنقدر ادامه پیدا می‏کند تا تمام خوشه‏ها با هم یکی شده و تشکیل یک خوشه را بدهند و یا جفت خوشه خالی نیز به حداکثر امتیاز برسد. منطق بروزرسانی وزن در خطوط۸-۱۱ تعبیه شده‏است. به این ترتیب که اگر بتوان جفت دقیق تری پیدا کرد، آن‏را به عنوان جفتی که دارای بالاترین امتیاز است به ورودی پرسپترون در خط ۱۱ داده‏می‏شود.

الگوریتم یادگیری با ورودی‏های (C,T)
ورودی این الگوریتم: دریافت مجموعه خوشه‏بندی‏های به عنوان مجموعه‏ی آموزشی و تعداد دوره‏های آموزش T
خروجی: مقدار میانگین شده

1. 1. مقدار ۰ را به W اختصاص بده

1. 1. به ازای انجام بده

1. 1. برای تمام انجام بده

1. 1. UPDATE(C,W)

1. 1. پایان حلقه اول

1. 1. پایان حلقه دوم

1. 1. بازگرداندن

شکل ۳-۷: الگوریتم آموزش خوشه‏بندی حریصانه

اگر چندین جفت خوشه در خطوط ۷و۱۰ کاندیدا شوند، به طور تصادفی یکی از آنها انتخاب می‏شود. این عمل به خصوص در هنگام شروع فرایند و هنگامی که بردار وزن برابر با صفر است، می‏تواند موثر واقع شود. از طرفی دیگر در خط ۸، تابع خوبی^[۲۱۱] یا تناسب استفاده شده‏است، این تابع برای جفت خوشه به صورت تعریف شده است. این مقدار با توجه به خوشه‏بندی برچسب‏دار آموزشیِ به عنوان صحتِ^[۲۱۲] جفت‏های هم‏مرجع درنظر گرفته می‏شود، که در صورت ادغام ایجاد گردیده است.
رابطه (۳-۱۵)
رابطه‏ی۳-۴ نشان می‏دهد، تابع تناسب، در خطوط ۸تا ۱۰، جفت خوشه‏ای را انتخاب می‏کند که در هنگام ادغامشان، نتایج در خوشه‏بندی به دقت بهتری منتج شوند. به طورکلی این الگوریتم سعی دارد به گونه‏ای با جستجو در داده‏های آموزشی، پارامترهایی را پیدا کند که هم بیش‏برازش را تحت کنترل داشته باشد(با بهره گرفتن از پارامترهای میانگین) و هم دقت خوشه‏بندی، بیشینه گردد.