(۱) for i = ۱ to K
(۲) set M-dimensions of [i] to i
(۳) end for
(۴) repeat
(۵) for i = ۱ to K
(۶) C[i] = {y| π^*(y)=i}
(۷) end for
// Compute the representative of each cluster
(۸) for i = ۱ to K
(۹) y_r[i] = <majority{(C_i)₁}, …, majority{(C_i)_M}>
// (C_i)_j is the set of j^th attributes of all data in C_i
(۱۰) end for
(۱۱) for each y in Y
// Re-assign
(۱۲) π^*(y) = Min_i WeightedHDistance (y, y_r[i], W) i[1..K]
(۱۳) end for
(۱۴) until NotChanged(π^*)

ورودی‏های لازم برای الگوریتم COHD مجموعه داده‏ای Y و وزن هر یک از خوشه‏بندی‏های اولیه می‏باشد. این الگوریتم π^* را به عنوان نتیجه‏ی ترکیب خوشه‏بندی‏ها بر می‏گرداند. در الگوریتم COHD ابتدا نماینده‏های اولیه به ازاء هر خوشه طبق آنچه که توضیح داده شده تعیین می‏گردند (خطوط ۱ تا ۳). سپس تا زمانی که هیچ شئ داده‏ای از یک خوشه به خوشه‏ی دیگری منتقل نگردد (خط ۱۴) دو گام اصلی الگوریتم ادامه می‏یابد. در گام اول پس از تخصیص داده‏ها به خوشه‏ها (خطوط ۵ تا ۷) نماینده‏ی هر خوشه دوباره محاسبه می‏گردد (خطوط ۸ تا ۱۰). در گام دوم نیز خوشه‏ای که نماینده‏ی آن کمترین فاصله را با شئ داده مورد نظر دارد به عنوان خوشه‏ی مناسب برای آن داده انتخاب می‏گردد (خطوط ۱۱ تا ۱۳). فاصله‏ی بین نماینده‏ی خوشه و یک شئ داده، با بهره گرفتن از (WeightedHDistance)که شبه کد آن در الگوریتم ۳-۴ آمده است، محاسبه می‏شود (خط ۱۲).

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

الگوریتم ۳- ۴ فاصله همینگ وزنی(WeightedHDistance)

Input: y, y_r as clusteringVector
Weight[1..M] as float

Output: Distance as float

Method:
(۱) set Distance to ۰
(۲) for i = ۱ to M
(۳) if(y[i] != y_r[i])
(۴) Distance = Distance + Weight[i]
(۵) end if
(۶) end for

در الگوریتم ۳-۴ زمانی که رأی خوشه‏بندی شئ داده با بردار نماینده‏ی خوشه متفاوت باشد (خط ۳) وزن آن خوشه‏بندی با فاصله‏ای که تاکنون بدست آمده است جمع می‏گردد (خط ۴) تا در نهایت خوشه‏بندی‏هایی که وزن بالاتری دارند در تعیین این فاصله تأثیرگذارتر باشند و این مقدار را افزایش دهند. این نوع تعیین فاصله، مشابه روش فاصله‏ی همینگ است. در فاصله‏ی همینگ، تعداد تفاوت‏ها شمارش می‏شود اما در اینجا مجموع وزن این تفاوت‏ها محاسبه می‏گردد.
لازم به ذکر است که قبل از اجرای الگوریتم خوشه‏بندی توافقی بر روی داده های توزیع شده ناهمگن، باید خوشه‏های نظیر به نظیر در خوشه‏بندی‏ها اولیه با بهره گرفتن از الگوریتم تشخیص نظیر به نظیر بودن خوشه ها مشخص شوند و برچسب خوشه‏های آنها با توجه به تناسبی که با خوشه‏بندی مرجع دارند، تغییر یابند.
مرتبه‏ی مکانی الگوریتم خوشه‏بندی توافقی بر روی داده های توزیع شده ناهمگن O(NM) که N تعداد داده‏ها و M تعداد خوشه‏بندی‏های اولیه می‏باشد.
از آنجا که الگوریتم پیشنهادی یک الگوریتم EM محسوب می‏گردد، تعداد تکرار‏های آن متغیر است و به مجموعه داده‏ای بستگی دارد. تعداد این تکرار‏ها در آزمایشات ما کمتر از ۶ بوده است. اما از آنجا که ساختار روش پیشنهادی منطبق با الگوریتم خوشه‏بندی K-Means می‏باشد، می توان از روش‏هایی که برای تسریع الگوریتم K-Means توسعه داده شده‏اند [۱۸،۳]، برای بهبود زمان اجرای الگوریتم COHD نیز استفاده نمود.
۳-۳- تولید اجتماع خوشه‏بندی‏ها
در این پایان نامه نتایج الگوریتم پیشنهادی را بر روی خوشه‏بندی‏هایی بررسی می‏نماییم که از تقسیم مجموعه داده‏ای به زیر مجموعه‏ای از ستون‏ها بدست آمده است. به عبارت دیگر در این حالت داده‏ها به صورت ناهمگن توزیع شده‏اند. به طور معمول در حالتی که خوشه‏بندی‏ها بر اساس زیر مجموعه‏هایی از صفات خاصه ایجاد شده باشند، کیفیت خوشه‏بندی‏ها می‏تواند نسبت به یکدیگر بسیار متفاوت باشد. زیرا برخی از صفات خاصه در داده‏ها نمی‏توانند به خوبی نوع و ساختار داده‏ها را نمایان سازند در نتیجه خوشه‏بندی‏هایی که با بهره گرفتن از این صفات خاصه تولید می‏شوند از کیفیت مناسبی برخوردار نمی‏باشند. به طور کلی خوشه‏بندی‏های تولید شده در حالتی که تمام صفات خاصه در دسترس نیستند از دقت کمتری (خطای بیشتری) نسبت به حالتی که خوشه‏بندی با بهره گرفتن از تمام صفات خاصه ایجاد شده است، برخوردارند.
در اغلب روش‏های خوشه‏بندی توافقی، خوشه‏بندی‏های اولیه تأثیر برابری بر روی خوشه‏بندی نهایی دارند. با توجه به این مسئله، وجود تفاوت و تنوع کیفیت در اجتماع اولیه‏ی خوشه‏بندی‏ها، برای این روش‏ها و به خصوص روش‏های رأی محور می‏تواند سبب کاهش کیفیت خوشه‏بندی نهایی گردد. بنابراین استفاده از روشی که در آن هر یک از خوشه‏بندی‏ها به میزان وزنی که به آنها اختصاص داده شده است بتوانند در خوشه‏بندی نهایی تأثیرگذار باشند، مناسب به نظر می‏رسد.
ما در آزمایشات مجموعه داده‏ای را به زیر مجموعه‏هایی از صفات خاصه تقسیم می‏کنیم و هر یک از این زیر مجموعه‏ها را جهت تولید اجتماع خوشه‏بندی‏ها، خوشه‏بندی خواهیم نمود. زیر مجموعه‏های انتخاب شده از صفات خاصه می‏توانند به طور کامل مجزا از یکدیگر بوده و یا همپوشانی نیز داشته باشند. انتخاب زیر مجموعه‏ها به طور تصادفی می‏باشد و معیاری جهت انتخاب آنها در نظر گرفته نشده است.