پیچیدگی مکانی الگوریتمهای IVC و IPVC، O(NM) میباشد که N تعداد دادهها و M تعداد خوشهبندیها است. تعداد تکرارهایی که الگوریتمهای مطرح شده برای رسیدن به کمینههای محلی نیاز دارد وابسته به ساختار دادهها میباشد. اما از آنچه که ساختار الگوریتمهای ارائه شده مشابه الگوریتم K-Means میباشند، تعداد تکرارهای لازم جهت همگرا شدن اغلب کم است. لازم به ذکر است که روشهای مختلفی نظیر [۱۸،۳] جهت بهبود سرعت اجرای الگوریتم K-Means وجود دارند که میتوانند برای این دو الگوریتم نیز مورد استفاده قرار گیرند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
الگوریتم ارائه شده در [۵۷] همانطور که گفته شد از کارایی مطلوبتری نسبت به دیگر روشهای مطرح خوشهبندی توافقی برخوردار میباشند، اما دارای اشکلاتی نیز هستند. اول اینکه در روشهای ارائه شده مسئله نظیر به نظیر بودن خوشهها در خوشهبندیهای مختلف در نظر گرفته نشده است. دوم اینکه تمام خوشهبندیها به طور یکسانی بر روی خوشهبندی نهایی تأثیرگذار میباشند. از آنجا که روشهای مطرح شده رأی محور میباشند این مسئله باعث میشود که در صورت وجود خوشهبندیهایی با کیفیت بسیار پایینتر نسبت به دیگر خوشهبندیها، خوشهبندی نهایی تولید شده به وسیلهی الگوریتمهای مذکور دارای کیفیت مناسبی نباشند. سوم اینکه در روش IVC مانند روش K-Means نیاز به انتخاب تصادفی K مرکز خوشهی اولیه از بین اشیاء داده میباشد. این مسئله میتواند سبب تولید خوشهبندیهایی شود که وابسته به انتخابهای اولیه میباشند و این انتخابها ممکن است کیفیت خوشهبندی نهایی را تحت تأثیر قرار دهند.
در این پایان نامه الگوریتم پیشنهادی مشکلات ذکر شده برای الگوریتم IVC را برطرف مینماید. الگوریتم پیشنهادی مسئلهی ترکیب خوشهبندیها را با استفاده خوشهبندیهای وزن دار شده و به صورت رأی محور انجام میدهد.
۲-۴- روشهای تولید اجتماع خوشهبندیها
بهینگی خوشهبندی نهایی علاوه بر روش انتخاب شده جهت ترکیب اجتماع خوشهبندیها، به روش تولید خوشهبندیهای اولیه نیز بستگی دارد. در ادامه چند روش تولید اجتماع خوشهبندیها که در مقالات اخیر مطرح شده است، ارائه میشود. قسمت عمدهی مطالبی که در این بخش بیان میشود بر اساس رساله دکتری Ayad [6] میباشد. کار تحقیقاتی انجام شده در این پایان نامه بیشتر بر روی الگوریتمی جهت ترکیب خوشهبندی میباشد و به مسئلهی تولید اجتماع خوشهبندیها زیاد پرداخته نخواهد شد.
یکی از روشهای متداول در تولید خوشهبندیها استفاده از الگوریتمهای خوشهبندی مختلف با روشهای اندازهگیری فاصله/شباهت متفاوت بر روی یک مجموعه داده، میباشد. Strehl و Ghosh [61] علاوه بر مطرح نمودن روش قبل، دو روش دیگر را نیز ارائه داده اند. آنها جهت انجام داده کاوی توزیع شده[۱۲۸]، دو روش توزیع شدگی شئ داده[۱۲۹] و توزیع شدگی خصیصه[۱۳۰] را مطرح نمودهاند. توزیع شدگی شئ داده اشاره به این مسئله دارد که یا حجم دادهها بسیار زیاد بوده است و با توزیع افقی آنها سعی در کوچک نمودن آنها داشتهایم و یا اینکه زیر مجموعههایی از دادهها در سایتهای مختلف با محدودیتهای محرمانگی داده[۱۳۱] قرار گرفتهاند و هدف یافتن یک خوشهبندی از ترکیب خوشهبندیهای موجود است. از طرف دیگر، توزیع شدگی خصیصه به مسئلهی خوشهبندی مجموعه داده با ابعاد بسیار زیاد اشاره میکند. زیر مجموعههایی از ابعاد انتخاب شده و هر زیر مجموعه به طور مجزا خوشهبندی میگردد و در نهایت با بهره گرفتن از روشهای خوشهبندی توافقی، خوشههای موجود ترکیب شده و یک خوشهبندی نهایی بدست میآید. به عبارت دیگر از نقطه نظر پایگاه داده، توزیع شدگی شئ داده به معنی تقسیم مجموعه داده به زیر مجموعههایی از سطرها و توزیع شدگی خصیصه به معنی تقسیم مجموعه داده به زیر مجموعههایی از ستونها میباشد.
نیاز به توزیع دادهها میتواند دارای دو دلیل عمده باشد. اول اینکه، ممکن است حجم مجموعه دادهای (از نظر تعداد اشیاء داده و یا تعداد ابعاد داده) بسیار زیاد باشد، به گونهای که خوشهبندی آنها بار پردازشی بسیار سنگینی را به منبع محاسباتی اعمال کند. با توزیع عمودی[۱۳۲] یا افقی[۱۳۳] دادهها میتوان بار پردازشی را بین چند منبع پردازشی (در محیط گرید[۱۳۴] یا در محیط توزیع شده) تقسیم نمود و در نهایت خوشهبندیهایی که در هر یک از منابع بدست میآیند را با بهره گرفتن از روشهای ترکیب خوشهبندی جهت دست یافتن به یک خوشهبندی واحد با یکدیگر ترکیب نمود. دوم اینکه، ممکن است مجموعه دادهای از ابتدا در منابع اطلاعاتی مختلف ذخیره شده باشد، هر منبع نیز میخواهد جزئیات اطلاعاتش محرمانه بماند. در این حالت منابع میتوانند تنها نتایج خوشهبندی را ارائه دهند و الگوریتمهای خوشهبندی توافقی، این نتایج را جهت دست یافتن به یک خوشهبندی واحد با یکدیگر ترکیب نمایند. ما در این پایان نامه نتایج اجرای الگوریتم پیشنهادی را بر روی دادههای توزیع شده (ناهمگن) نشان میدهیم.
Fern و Brodley [73] اجتماع خوشهبندیها را بر اساس تصویرهای تصادفی[۱۳۵] مختلف از دادهها، تولید میکنند. تصویرهای تصادفی متناظر با روش تبدیلی[۱۳۶] است که میتواند کیفیت خوشهبندی را برای دادههایی با ابعاد زیاد بهبود بخشد [۵۹،۴۲،۱،۹]. دادههایی با ابعاد زیاد یک مسئلهی چالش برانگیز در خوشهبندی دادهها میباشد. این مسئله بویژه در حالتی که بردارهای داده بسیار خلوت[۱۳۷] باشند، یافتن ساختار داده را ناممکن میسازد. علاوه بر آن، وجود صفات خاصهی نامربوط و دارای نویز میتواند منجر به خوشهبندی نامناسبی گردد.
نمونه برداری راهانداز از دادههای اصلی یکی دیگر از روشهای اصلی تولید اجتماع خوشهبندیها محسوب میگردد، به طوری که هر یک از نمونههای راهانداز جهت تولید اجتماع متفاوتی از خوشهبندیها، خوشهبندی میشوند. این روش در مطالعات مختلفی مورد استفاده قرار گرفته است نظیر، [۱۷،۱۹،۵۴].
برخی از الگوریتمهای خوشهبندی نظیر K-Means وابسته به هستههای اولیهای است که به طور معمول به صورت تصادفی انتخاب میشوند. این وابستگی به شروعهای مجدد[۱۳۸] تصادفی، نوع دیگری از روشهای تولید اجتماع خوشهبندیها را بوجود میآورد. در این حالت هر خوشهبندی، متناظر با یک شروع مجدد تصادفی میباشد. [۲۱] از این روش تولید اجتماع خوشهبندیها به همراه الگوریتم K-Means جهت بهبود پایداری خوشهبندی نهایی استفاده کردهاند. [۱۵] و [۲۶] از اجراهای مختلف الگوریتمهای خوشهبندی فازی[۱۳۹] نظیر C-Means (FCM[140]) جهت تولید خوشهبندیهای اولیه استفاده میکنند.
Topchy، Jain و Punch [66] دو روش جهت تولید خوشهبندیهای ضعیف[۱۴۱] ارائه داده اند. در روش اول، خوشهبندیها بر مبنای تصویرهای یک بعدی تصادفی از مجموعه داده اصلی تولید میشوند. در روش دوم، خوشهبندیها با بهره گرفتن از تقسیم دادهها به تعدادی ابرصفحه[۱۴۲] تصادفی تولید میشوند. اشیاء دادهای که توسط ابرصفحهها تقسیم شدهاند به خوشههای متفاوتی تخصیص مییابند. هنگامی که تنها از یک ابرصفحه استفاده میشود، دادهها به دو خوشه تقسیم میشوند. ایدهی خوشهبندیهای ضعیف، ترکیب خوشهبندیهای سادهای است که با محاسبات کم هزینهای بدست آمدهاند، به طوری که خوشهبندی نهایی دارای کیفیت بالاتری نسبت به خوشهبندیهای اولیه باشد.
۲-۵- خلاصه فصل
در این فصل علاوه بر بررسی کلی روشهای خوشهبندی، انواع مختلف الگوریتمهای خوشهبندی توافقی نیز در چهار گروه روشهای شباهت محور، روشهای اطلاعات دوجانبه، روشهای مدل ترکیبی و روشهای رأی محور مورد بررسی قرار گرفتند. الگوریتم پیشنهادی در این پایان نامه یک روش رأی محور میباشد. روشهای رأی محور به طور معمول برای هر یک از خوشهبندیهای اولیه یک رأی در نظر میگیرند و این به معنی تأثیر برابر در نتیجهی نهایی میباشد. به دلیل امکان وجود خوشهبندیهایی با کیفیت پایین در اجتماع خوشهبندیها، این تأثیر برابر میتواند باعث کاهش کیفیت نتیجهی نهایی گردد.
الگوریتم پیشنهادی بر اساس وزنی که به هر یک خوشهبندیهای اولیه داده شده است نوعی خوشهبندی رأی محور را بر روی اجتماع خوشهبندیها اعمال میکند. ساختار الگوریتم ارائه شده بر اساس الگوریتم IVC میباشد که در این فصل به بررسی آن پرداخته شد. این الگوریتم دارای معایبی از جمله عدم تشخیص نظیر به نظیر بودن خوشهبندیها، یکسان در نظر گرفتن رأی خوشهبندیهای اولیه و نوع انتخاب مراکز اولیهی خوشهها میباشد که سعی شده است در الگوریتم پیشنهادی این مسائل برطرف گردد. در فصل بعد به تشریح راهکار پیشنهادی خواهیم پرداخت.
فصل سوم
ارائه راهکار پیشنهادی:
خوشهبندی توافقی بر روی دادههای توزیع شده ناهمگن
۳-۱- مقدمه
در این فصل راهکار پیشنهادی جهت انجام خوشهبندی توافقی بر روی دادههای توزیع شده ناهمگن مورد بررسی قرار میگیرد. منظور از دادههای توزیع شده ناهمگن، مجموعه دادهای میباشد که به زیر مجموعههایی از صفات خاصه تقسیم شده است. در فصل قبل به این مسئله اشاره شد که وجود خوشهبندیهایی با کیفیت پایین در اجتماع خوشهبندیها، میتواند سبب کاهش کیفیت خوشهبندی نهایی در انجام خوشهبندی توافقی گردد. این مسئله زمانی نمود بیشتری مییابد که اجتماع اولیهی خوشهبندیها بر روی زیر مجموعهای از صفات خاصه ایجاد شده باشد. زیرا در این حالت به دلیل عدم وجود تمام مشخصات داده در زمان خوشهبندی، برخی از خوشهبندیهای تولید شده ممکن است از خطای بیشتری برخوردار باشند.
راهکار و الگوریتم پیشنهاد شده در این پایان نامه، مسئلهی ترکیب خوشهبندیها را به صورت خوشهبندی توافقی وزن دار انجام میدهد. ساختار کلی کار به این صورت است که به هر یک از خوشهبندیهای اولیه وزنی اختصاص مییابد و سپس با بهره گرفتن از نوعی خوشهبندی توافقی رأی محور و در نظر گرفتن وزن هر خوشهبندی، خوشهبندیهای اولیه جهت ایجاد یک خوشهبندی واحد با هم ترکیب میشوند. لازم به ذکر است که هر یک از خوشهبندیهای اولیه، به میزان وزنی که به آنها اختصاص داده شده است بر روی خوشهبندی نهایی تأثیرگذار خواهند بود. این روش خوشهبندی میتواند علاوه بر حفظ مزایای خوشهبندی توافقی، باعث کاهش تأثیر منفی خوشهبندیهایی با کیفیت پایینتر نیز گردد.
ایدهی بکار رفته در رأی گیری بین خوشهبندیها مشابه الگوریتم IVC میباشد. اما همانطور که در فصل گذشته نیز بیان گردید این الگوریتم دارای معایبی از جمله ۱) عدم تشخیص نظیر به نظیر بودن خوشهها در خوشهبندیهای مختلف، ۲) یکسان در نظر گرفتن رأی
خوشهبندیهای اولیه و ۳) روش انتخاب مراکز اولیهی خوشهها، میباشد. در راهکار پیشنهادی در این پایان نامه سعی گردیده تا هر یک از مسائل مطرح شده برطرف گردد.
در این فصل ابتدا روشی جهت تشخیص خوشههایی که نظیر به نظیر هستند در خوشهبندیهای مختلف ارائه میگردد. سپس روش وزندار نمودن خوشهبندیهای اولیه مورد بررسی قرار خواهد گرفت. پس از آن الگوریتم پیشنهادی جهت انجام خوشهبندی توافقی بر روی داده های توزیع شده ناهمگن ارائه میشود. در نهایت نیز ساختار دادههای توزیع شده ناهمگن مورد بررسی قرار میگیرد.
۳-۲- راهکار پیشنهادی
در این بخش راهکار پیشنهادی جهت انجام خوشهبندی توافقی بر روی داده های توزیع شده ناهمگن مورد بررسی قرار میگیرد. ابتدا الگوریتمی جهت تشخیص خوشههای هم ارز یا نظیر به نظیر ارائه میگردد. سپس روش وزندار نمودن خوشهها بررسی میشود. در پایان نیز الگوریتمی جهت انجام خوشهبندی توافقی بر روی دادههای توزیع شده ناهمگن ارائه خواهد شد.
۳-۲-۱- تشخیص نظیر به نظیر بودن بودن خوشه ها
برخی از روشهای خوشهبندی توافقی مانند روشهای شباهت محور، نیازی به تشخیص تناظر خوشهها بین خوشهبندیها را ندارند. به عبارت دیگر مسئله تشخیص نظیر به نظیر بودن خوشهها را حل نمیکنند. اما برخی دیگر از روشها مانند روشهای خوشهبندی توافقی رأی محور، باید مسئلهی تشخیص تناظر بین خوشهها را به طریقی حل نمایند. جهت وضوح بخشیدن به این مسئله، ادامهی بحث را با بهره گرفتن از یک مثال ساده دنبال مینماییم.
فرض کنید مجموعه دادهای شامل نه شئ داده به صورت X={x1, x2, …, x9} باشد. این دادهها در دو خوشهبندی π۱ و π۲ در سه خوشه قرار گرفتهاند. شکل ۳-۱ وضعیت قرار گرفتن اشیاء داده در این دو خوشهبندی را نشان میدهد. شماره یا برچسب هر یک از خوشهها در پایین آن در شکل آورده شده است. همانطور که مشاهده میشود، خوشههای هم شماره و یا خوشههایی با برچسب مشابه لزوما نظیر به نظیر با یکدیگر نمیباشند.
x1
x3
x2
x4
x5
x8
x9
x77
x6
خوشه ۱
خوشه ۲
خوشه ۳
الف) خوشهبندی ۱π
x2
x8
x6
x9
x1
x5
x7
x3
x4