بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
خوشه بندی با استفاده از روش ترکیبی الگوریتم جستجوی گرانشی و میانگین هارمونیک K
چکیده
یکی از مرسومترین روشهای داده کاوی خوشهبندی است که به تفکیک مجموعهای از اشیا به خوشههای مختلف اطلاق میگردد، به طوریکه اشیا قرار گرفته در یک خوشه، بیشترین تشابه را با یکدیگر داشته باشند و از اشیا قرار گرفته در سایر کلاسها متفاوت باشند. روشهای متعددی برای خوشهبندی پیشنهاد و استفاده شده است. نشان داده شده است که روش GSA-KM که از ترکیب روش جستجوی گرانشی و میانگین K استفاده شده، نسبت به سایر روشها عملکرد بهتری نشان داده است اما این روش همچنان مشکل وابستگی به مقداردهی اولیه را دارد. در این مقاله روشی موسوم به GSA-KHM پیشنهاد شده که در آن، از طریق استفاده از الگوریتم میانگین هارمونیک K بهجای میانگین K، مشکل وابستگی به مقداردهی اولیه را نیز پوششداده میشود. نتایج آزمایشات نشان میدهد که این روش بهتر از روش GSA-KM در خوشهبندی عمل خواهد کرد.
.1 مقدمه
یکی از کاربردیترین روشهای مدیریت اطلاعات، عمل خوشهبندی است که در زمینههای بسیاری همچون یادگیری ماشین، دادهکاوی، بازیابی اطلاعات، شناسایی الگو، انفورماتیک زیستی کاربرد دارد. روشهای زیادی در این زمینه پیشنهاد شده است. مرسومترین این روشها روش میانگین [1 ] 2(KM ) K است که مشکل وابستگی به مقدار دهی اولیه و قرار گرفتن در بهینه محلی را دارد. روش دیگر روش میانگین هارمونیک [2] 3(KHM) K است که هدف آن این است که میانگین هارمونیک تمامی دادهها را تا مراکز خوشهها کمینه کند. این روش مشکل مقداردهی اولیه در روش KM را برطرف کرده است اما همچنان احتمال قرار گیری در بهینهی محلی در این روش وجود دارد. بنابراین باید به نوعی مشکل افتادن در دام بهینه محلی نیز برطرف گردد. روشهای حریصانه بسیاری برای حل این مشکل پیشنهاد شدهاند.
در [3] از الگوریتم وراثتی4 برای خوشهبندی استفاده شده و عملکرد آن روی مجموعه دادههای مختلف بررسی شده است. در [4] الگوریتم خوشهبندی ترکیبی KM و الگوریتم وراثتی پیشنهاد شده است. همچنین در [6 ] و [7] به ترتیب روشی مبتنی بر الگوریتم مورچگان5 و الگوریتم جفتگیری زنبور عسل6 برای خوشهبندی پیشنهاد گردیده است. خوشهبندی با استفاده از الگوریتم انبوه ذرات (پرندگان)7 در [7])، ([8] پیشنهاد شده است. در [9] روشی بر اساس الگوریتم ذوب فلزات ارائه شده است. در [10])، ([11]روش جستجوی گرانشی تشریح و عمل خوشه بندی با استفاده از آن پیشنهاد و با سایر روشها مقایسه شده است. در[12] روشی ترکیبی از جستجوی تابو و الگوریتم KHM به کار برده شده است. در [13] با استفاده از ترکیب KM و الگوریتم جستجوی گرانشی روشی موسوم به GSA-KM پیشنهاد گردیده که نتایج مقایسه این روش با همه روشهای ذکر شده نشان میدهد که این روش نسبت به همهی آنها عملکرد بهتری داشته است. در روش GSA-KM ابتدا الگوریتم KM اجرا و جوابهای آن به عنوان بخشی از جمعیت اولیه وارد الگوریتم GSA میشود. این راهکار باعث میشود که الگوریتم، فضای جستجوی مناسبتری داشته باشد و از قرار گرفتن در بهینه محلی جلوگیری شود و از طرفی، الگوریتم سریعتر به جواب بهینه همگرا گردد. اما عیبی که این روش دارد این است که الگوریتم KM همچنان به مقادیر اولیه حساس است. در تحقیق پیش رو، به جای استفاده از KM در مقداردهی جمعیت اولیه، از KHM استفاده شده است. در واقع در روش پیشنهادی GSA-KHM جستجوی گرانشی و میانگین هارمونیک K، از مزایای هر دو روش در خوشه بندی استفاده میکند. نتایج آزمایشات نشان میدهد که با این نوع جایگذاری، الگوریتم به مقداردهی اولیه حساس نبوده و همچنین عمل خوشه بندی با نتایج بهتری انجام خواهد شد. آزمایشات روی پنج مجموعه داده از مجموعه دادههای متداول [14] UCI انجام شده است.
ادامه این مقاله به طریق زیر سازماندهی شده است. ابتدا در بخش 2، روش خوشهبندی KM و KHM تشریح و مقایسه شدهاند. در بخش 3، الگوریتم جستجوی گرانشی و مراحل آن توضیح داده شده است. در بخش 4 روش پیشنهادی GSA-KHM که حاصل ترکیب الگوریتم GSA و KHM است معرفی گردیده است. در بخش پنجم آزمایشات و نتایج شبیه سازی نشان داده شده و با روش [13] GSA-KM مقایسه گردیده استو نهایتاً در بخش 6 خلاصهای از کارهای انجام شده در این تحقیق، توضیح داده شده است.
.2 روش خوشه بندی KM و KHM
روش خوشه بندی KM یک روش ساده و پایهای است که در سال 1967 توسط مک کویین [15] پیشنهاد شد که علیرغم سادگی آن می-تواند در سایر مدلهای خوشه بندی استفاده شود. این روش بر اساس کمترین فاصلهی هر داده تا مرکز (میانگین) خوشهها، عمل خوشه بندی را انجام میدهد. در واقع این روش از دادههای موجود خوشههایی را سازماندهی میکند که فاصله دادههای موجود در هر خوشه تا مرکز آن خوشه حداقل باشد.
در این روش برای دستهبندی دادههای مسئله در K خوشه، مراحل زیر دنبال میگردد([1]، :([15] K -1 نقطه به صورت تصادفی و به عنوان مراکز خوشهها برگزیده میشوند.
-2 بر اساس رابطهی (1)، فاصله هر دادهی i تا همهی مراکز خوشهها محاسبه و به خوشهای که کمترین فاصله را با مرکز آن داشته باشد، ملحق میشود.
-3 مرکز هر خوشه با محاسبه میانگین دادههای موجود در هر خوشه به روز رسانی میشود. -4 مراحل 2 و 3 تا زمانی که تغییری در مرکز خوشهها ایجاد نشود تکرار میگردند.
همانگونه که در این الگوریتم ملاحظه میشود، نتیجهی خوشهبندی شدیدا به مراکز انتخاب شدهی اولیه وابسته است و ارتباط زیادی بین داده-ها با نزدیکترین مرکز وجود دارد و باعث میشود که مراکز خوشهها از محدودهی تراکم محلی خارج گردند. در روش KM هر داده فقط به یک مرکز اختصاص داده میشود. در نواحی با تراکم زیاد داده و مراکز، ممکن است یک مرکز نتواند از یک داده دور شود، علی رغم اینکه مرکز دیگری در آن حوالی وجود دارد. انتخاب مرکز دوم ممکن است باعث شود که جواب محلی کمی بدتر شود اما اثر کلی آن در خوشه بندی بسیار مفید خواهد بود. این جابجایی مراکز خوشهها نمیتواند توسط روش KM انجام شود درحالیکه روش KHM با استفاده از درجهی عضویت بر این مشکل فایق آمده است. الگوریتم خوشهبندی KHM اولین بار توسط ژانگ در سال 1999 پیشنهاد شد .[2] در این روش برای هر داده، تابع هدف از فواصل همهی مراکز استفاده میکند. میانگین هارمونیک بر این وقعیت استوار است که در نزدیکی هر داده بیش از یک مرکز خوشه وجود دارد. الگوریتم یک یا تعدادی از این مراکز را به سمت دادههایی که در نزدیکیشان مرکز خوشه وجود ندارد جابهجا میکند.
اگر = { 1, 2, … , } مجموعهی دادهها و = { 1, 2, … , } مجموعهی مراکز خوشهها باشد، این الگوریتم طبق مراحل زیر عمل میکند:
-1 مراکز خوشهها به صورت تصادفی تولید میشود. -2 مقدار تابع هدف طبق رابطهی (2) بدست میآید.
-3 به ازای هر مرکز j فاصلهی آن از تمامی دادهها iی طبق رابطهی (3) بدست میآید.
در این رابطه، وزن ( i) بیانگر مقدار تاثیر هر دادهی i در محاسبهی مجدد پارامترهای مرکز در تکرار بعدی است که براساس رابطهی (4) بدست میآید و ( | ) تابع عضویتی است که سهم تعلق دادهی i به مرکز j را تعیین میکند.، به ازای هر داده و طبق رابطهی (5) بدست میآید.
-4 گام 3 تا زمانی تکرار میشود که مقدار ( , ) به اندازه قابل توجهی تغییر نکند. داده i را به خوشهی که بیشترین مقدار عضویت ( | ) را دارد تخصیص میدهد.
در این مقاله، از روش KHM در مرحلهی تولید جوابهای اولیه الگوریتم جستجوی گرانشی استفاده خواهد شد به این منظور که همگرایی آن سریعتر شود و جوابهای بهینهتری حاصل گردد [2])، ([12]
.3 الگوریتم جستجوی گرانشی (GSA)
ایدهی اصلی الگوریتم جستجوی گرانشی از قانون گرانش نیوتن بین اجرام برگرفته شده است. طبق این قانون، گرانش بین دو جسم به مقدار جرم آنها و میزان فاصلهشان از یکدیگر بستگی دارد. نیروی گرانشی بین دو جسم با جرمهای 1 و 2 که در فاصلهی از یکدیگر قرار دارند، طبق رابطهی (6) بدست میآید که در آن مقدار ثابت برابر با 6,67259×10-11 است.
توجه به این رابطه، نیروی گرانشی بین اجرام سنگینتر با فاصلهی نزدیکتر بیشتر است. براساس قانون دوم نیوتن، وقتی که نیروی گرانشی روی یک جسم به جرم اعمال میشود، آن جسم به سمت جسم دیگر با مقدار شتاب a حرکت میکند، مقدار این شتاب براساس رابطه-(7) محاسبه میگردد.
در الگوریتم جستجوی گرانشی فرض میشود که داده به عنوان جسم در فضای بعدی قرار دارد. موقعیت جسم i ام به صورت رابطه ی زیر تعریف شده است که . id موقعیت جسم در بعد ام فضای n بعدی است.
موقعیت بهینهی جسمها معادل جواب بهینهی مسئله است. جرم هر جسم طبق رابطهی (9) حاصل میشود.
که در این رابطه، ( ) جرم هر جسم و ( ) مقدار تناسب آن در تکرار ام الگوریتم است و مقدار ( ) از رابطهی (10) بدست میآید. جرم بیشتر به منزلهی جواب بهتر است. به این معنا که هر قدر که جرم بیشتر و جواب مطلوبتر باشد با سرعت کمتری در فضا جا به جا میشود.
با توجه به رابطههای (7) و (8) برای محاسبه شتاب یک جسم، باید مجموع نیروهایی که از سوی اجرام دیگر بر آن اعمال میشود همانند رابطهی (11) محاسبه و با جایگذاری در رابطهی((7 شتاب آن به صورت رابطهی (12) محاسبه گردد.
در روابط فوق، یک مقدار کوچک برای جلوگیری از تقسیم بر صفر بوده و j یک عدد تصادفی با توزیع یکنواخت بین 0 و 1 است. مجموعهی مجموعهای از جواب با بهترین مقدار تناسب و بیشترین وزن است که با تکرار الگوریتم تغییر میکند. اندازهی مجموعه-ی در ابتدا به اندازهی (تعداد اجسام) و در پایان اندازه آن 1 خواهد بود. در واقع در آغاز از سوی همهی اجرام نیرو وارد میشود و در پایان فقط از سوی یک جسم نیرو وارد میگردد. ( ) تابعی کاهشی نسبت به زمان است که در ابتدای الگوریتم مقدار آن 1 و در پایان صفر میشود و Rij فاصلهی اقلدیسی بین جسم و است که خود از رابطهی زیر محاسبه میشود:
