بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
کاهش ابعاد داده های بیو انفورماتیکی با استفاده از الگوریتم جفت گیری زنبور عسل
چکیده - یکی از مشکلات مطرح در فرآیند تحلیل داده های بیوانفورماتیکی، ابعاد بالای این داده ها است. تعداد غالبا بسیار ناچیز نمونههای آموزشی در این دادهها، مشکل ابعاد زیاد را تشدید مینماید. اهمیت کاربردی تحلیل این دادهها، لزوم افزایش سرعت پردازش و درعین حال ضرورت تحلیل دقیق این دادهها، محققین را به سمت توسعهی راهکارهای کاهش موثر ابعاد این داده ها سوق داده است. تاکنون روشهای متعددی برای این امر پیشنهاد شده است. در این مقاله، شیوه نوینی برگرفته از روشهای خوشه بندی بهینه سازی شده با استفاده از الگوریتم جفتگیری زنبور عسل ارائه میشود. نتایج حاصل شده از شبیه سازیها حاکی از آن است که این شیوه، در کاهش ابعاد دادههای بیو انفورماتیکی بسیار کارامد می باشد.
کلید واژه- کاهش ابعاد داده های بیو انفورماتیکی، خوشه بندی، روشهای خوشه بندی بهینه سازی شده، الگوریتم جفت گیری زنبور عسل.
-1 مقدمه
امروزه با توجه به پیشرفت تکنولوژی و گسترش تجهیزات و ابزارهای استخراج مدلهای ریاضی و عددی از جهان خارج با حجم بسیار وسیعی از دادههای عددی روبرو هستیم که تنها مقدار کمی از این حجم وسیع داده برای تحلیل مسائل و محاسبات مدنظر، مورد استفاده قرار می گیرد. یک نمونه بارز از این موضوع، داده های بیو انفورماتیکی است که ابعاد بالای این داده ها باعث ایجاد مشکلات پردازشی و تحلیلی برای بررسی این نوع از دادهها می شود که برای حل این مشکل، اعمال عملیاتهای پیش پردازشی کاهش ابعاد، ضرورت دارد. تعداد کم نمونههای آموزشی، این مشکل را مضاعف مینماید.[1] تاکنون شیوه های متعددی به منظور کاهش ابعاد دادههایی با ابعاد بالا ارائه شده است که از آن جمله می توان استفاده از شیوههای استخراج ویژگی مانند آنالیز مولفههای اساسی (PCA)، آنالیز جداکننده خطی (LDA) ، ماشین بردار پشتیبان (SVM) و شیوههای انتخاب ویژگی مانند اعمال الگوریتم ژنتیک را نام برد که بعضی از آنها به نتایج مطلوبی نیز منجر می شود4]،3،.[2 البته چنانچه اشاره شد، درخصوص دادههای بیوانقورماتیکی، تعداد دادههای آموزشی اغلب بسیار ناچیز است که این خود موجب ایجاد محدودیتهائی در انتخاب روش مورد نظر میشود. در این مقاله، با استفاده از تکنیکهای خوشه بندی بهینهسازی شده، روشی
جدید برای کاهش هوشمند ابعاد دادههای بیو انفورماتیکی ارائه میشود که موجب کاهش موثر و کارآمد ابعاد این دادهها می-گردد و با توجه به آزمایشات انجام شده در ادامه اثبات می شود با الگوریتم پیشنهادی بیش از 50 درصد، معیار کیفیت خوشه بندی ما بهبود پیدا می کند. لذا در این مقاله، ابتدا ضمن بیان اصول کلی مطرح در فرآیند خوشهبندی دادهها، شیوه خوشه بندی k میانگین مرور میشود. سپس جزئیات الگوریتم جفت گیری زنبور عسل بیان شده و روش پیشنهادی برای خوشه بندی بهینه سازی شده که مبتنی بر این الگوریتم میباشد، ارائه می-شود. پس از آن، ضمن بررسی نتایج حاصل از اعمال الگوریتم پیشنهادی، به سه مجموعه داده شناخته شده غیربیوانفورماتیکی، کیفیت عملکرد روش را مورد ارزیابی اولیه قرار داده و نهایتا چگونگی عملکرد الگوریتم برای کاهش ابعاد دادههای بیوانفورماتیکی را بررسی میکنیم.
-2 خوشهبندی
خوشهبندی یکی از شیوههای آموزش بدون مربی است که در آن داده ها با توجه به شباهتی که به هم دارند در گروهها یا اصطلاحا خوشههای مربوطه دسته بندی می شوند. خوشه بندی با دو شیوهی سلسه مراتبی (درختی) یا بخشبندی انجام می شود.[5] در روش درختی، با بررسی شباهت بین دادهها، واحد-های کوچکتر(یا بزرگتر) دادهها بصورت سلسله مراتبی با یکدیگر
ادغام (یا بطور مناسب تجزیه) میشوند تا نهایتا خوشههای معناداری ایجاد شود. در روش بخشبندی، با در نظر گرفتن معیاری، بهعنوان معیار شباهت، دادهها مستقیما به تعدادی خوشه بخشبندی میشود. از مهمترین شیوههای بخشبندی، به الگوریتمهای تکراری میتوان اشاره کرد که در آنها، دادهها ابتدا بطور تصادفی یا شبهتصادفی بخشبندی میشوند و سپس در تکرارهای متعدد، این دسته بندیها اصلاح میشود تا نهایتا به یک خوشه بندی دقیق منجر شود.
-1-2 خوشهبندی با شیوه k میانگین
الگوریتم k میانگین یکی از مرسوم ترین شیوه های خوشه بندی به حساب می آید که سادگی آن و حجم پایین محاسبات و سرعت بالای اجرای آن، دلایل استفاده گسترده از آن می-باشد.[6] در این الگوریتم، ابتدا بصورت تصادفی/ شبه تصادفی تعدادی مراکز خوشه در نظر گرفته میشود. سپس میزان شباهت (فاصله) داده ها با مراکز خوشهها که در تکرارهای بعدی برابر با میانگین تمام دادههای قرار گرفته در آن خوشه در نظر گرفته میشود، بدست میآید و هر داده به خوشه ای که شباهت بیشتری با آن داشته باشد تعلق میگیرد. پس از تشکیل خوشه های جدید، میانگین جدید برای تکرار بعد محاسبه میشود و این کار تا زمانی که دیگر از یک مرحله به مرحله بعد، مرکز خوشهها تغییر چندانی نکند، ادامه مییابد. برای سنجش فاصله دادهها تا مرکز خوشهها عموما از معیار فاصله Minkowski (رابطه (1 با r=2 و یا همان معیار فاصله اقلیدسی (رابطه (2 استفاده میشود:
برای ارزیابی کیفیت خوشهبندی نیز عموما از رابطه 3 استفاده میشود.
که در رابطه بالا، K تعداد خوشهها و cl مرکز خوشه مربوط به داده i ام در انتهای عمل خوشه بندی است.[7]
برای این شیوه خوشهبندی علاوه بر محاسنی که وجود دارد دو عیب عمده مطرح است: وابستگی نتیجه به پاسخ تصادفی اولیه و امکان همگرا شدن الگوریتم به اپتیمم های محلی.
برای حل این مشکلات شیوههای متفاوتی تحت عنوان الگوریتمهای بهینهسازی ارائه شده است. یکی از کارآمدترین الگوریتمها، الگوریتمهایی است که بر پایه رفتار حشرات از جمله مورچه یا زنبور شکل گرفته اند.
-3 الگوریتم بهینه سازی جفت گیری زنبور عسل
در این پژوهش از الگوریتم بهینه سازی جفتگیری زنبور عسل برای بهبود خوشه بندی و جلوگیری از همگرایی به اپتیمم های محلی استفاده شده است. این الگوریتم با الهام از آنچه که در طبیعت و زندگی زنبورهای عسل وجود دارد به حل مسائل بهینهسازی می پردازد. مراحل اجرای این الگوریتم بهینه سازی، به اختصار به شرح ذیل می باشد9]،:[8
برای شروع الگوریتم یک سری پاسخ های اولیه در نظر گرفته و آن را به عنوان جواب برتر قبول میکنیم که این جواب برتر در واقع زنبور ملکه ماست که در هر بار اجرای الگوریتم بهترین جواب تولید شده جایگزین آن میشود. الگوریتم با جفت گیری ملکه و زنبورهای نر، که با احتمال مطرح شده در رابطه 4 صورت می گیرد آغاز می شود.
توجه داشته باشید که در رابطه بالا که بیانگر احتمال جفت گیری موفقیت آمیز است ( ( f تفاوت بین تابع تناسب زنبور نر((D و ملکه (Q) می باشد و S (t) سرعت ملکه در زمان t می باشد. این بدان معناست که در ابتدای پرواز ملکه، که سرعت آن بالاست و یا زمانی که اختلاف تابع تناسب ملکه و زنبور نر کم باشد احتمال جفت گیری بیشتر می شود. همچنین لازم به ذکر است پس از هربار جفت گیری سرعت و انرژی ملکه به ترتیب با رابطه 5 و 6 کاهش می یابد.
که در آن (t) یک عدد در محدوده صفر و یک و
میزان کاهش انرژی ملکه پس از هر بار جفت گیری است و هرچه سرعت ملکه و انرژی آن بیشتر باشد نیز احتمال جفت گیری و پرشدن محفظه اسپرم ملکه توسط زنبور نر افزایش می یابد. البته این جفت گیری باید تا زمانی انجام شود که انرژی ملکه برای بازگشت به کندو در سطح قابل قبولی قرار داشته باشد. لذا این دو پارامتر نقش کنترلی برای تولید تعداد مشخصی از جوابهای تمرینی را ایفا می کنند.
بچه زنبورهای جدید از لقاح بین ملکه و زنبور نر که در واقع با جابجایی بین ژنهای آنها صورت می گیرد بوجود می آیند و جوابهای تمرینی ما را بوجود می آورند.
از زنبورهای کارگر برای بهبود جوابهای تمرینی یا رشد و بزرگ کردن بچه زنبورها استفاده می شود. تابع تناسب کارگرها بر اساس میزان بهبود در نسل بچه زنبورها جوابهای تمرینی را مرتب می کند. در صورت بهتر بودن یکی از جواب های آزمایشی از جواب برتر یا ملکه، آن دو جابجا می شوند تا از جواب آزمایشی بهتر برای تولید جوابهای ازمایشی استفاده شود.
شکل 1 روال کلی این الگوریتم را نمایش می دهد.
شکل :1 الگوریتم بهینه سازی جفت گیری زنبور عسل[9]
به عبارت دقیق تر الگوریتم جفت گیری زنبور عسل را می توان در نه مرحله بیان کرد.[9]
درمرحله اول یک کروموزوم برای ارائه یک جواب پیشنهادی مورد استفاده قرار میگیرد. هر ژن در کروموزوم معرف یک پارامتر از جواب می باشد. در اینجا یک کروموزوم به مجموعه ای از K مرکز کلاستر اولیه اشاره دارد هر کروموزوم می تواند به شکل C=[C1 …&n…&j] بیان شود که Cn، n امین ژن و j مجموع تعداد ژنهاست. شکل زیر یک مثال انتخاب کروموزوم را
نشان می دهد. برای مثال در شکل زیر هر ژن شامل سه مرکز خوشه می باشد.
شکل :2 یک نمونه از کروموزمی که در الگوریتم تزویج زنبور عسل به عنوان جواب در نظر گرفته می شود
در مرحله دوم پارامترهای ورودی مدل تعیین میشود و الگوریتم با سه پارامتر تعیین شده توسط کاربر و یک پارامتر از پیش تعیین شده شروع می شود. پارامتر پیش تعیین شده ، تعداد کارگر ها((W است که بیانگر تعداد اکتشاف های کد شده در برنامه می باشد. پارامتر بعدی تعیین شده توسط کاربر، حجم محفظه اسپرم ملکه می باشد که بیانگر حداکثر تعداد نوزادی است که قابل به دنیا آمدن بوسیله ملکه هستند و پارامتر دیگر سرعت ملکه می باشد که در شروع هر پرواز جفت گیری به صورت تصادفی به آن مقدار اولیه داده می شود و نهایتا پارامتر آخر تعداد ملکهها یا جواب های برتری است که در هر مرحله می تواند برای ایجاد جوابهای آزمایشی تعیین گردند.
در مرحله سوم مجموعهای از مرکز کلاسترهای اولیه به صورت تصادفی با استفاده از نقاط مجموعه داده، تولید می شود. هر پاسخ بیانگر K مرکز کلاستر مطابق آنچه در شکل 2 نمایش داده شده می باشد.
در مرحله چهارم بعد از تولید مجموعهای از پاسخهای ابتدایی در مرحله گذشته، برپایه تابع عملکرد جوابها رتبه بندی و بهترین آنها به عنوان ملکه تعیین می شود.
مرحله پنجم، پرواز جفتگیری و استفاده از شبیهسازی پایدار برای انتخاب مجموعه ای از پاسخ ها در فضای جستجو، به منظور ایجاد مخزن جفتگیری است و برای امکان جابجایی اطلاعات بین بهترین پاسخ پیشنهادی ارائه شده (ملکه) و پاسخ آزمایشی انتخاب شده می باشد.
مرحله ششم، فرایند تولید مثل و ایجاد مجموعه جدیدی از پاسخ ها با استفاده از اپراتور تزویج از پیش تعیین شده و تابع اکتشاف بین پاسخ پیشنهادی و پاسخ آزمایشی براساس مقادیر تناسب آنها میباشد. لازم به ذکر است که نوزاد ها با اتخاذ یک میانگین وزن دار از والدین تولید می شوند. وزنها را می توان با یک پارامتر مجزا مشخص کرد. نرخ نیز میتواند یک عدد یا یک بردار خام از طول اعداد متغیر باشد. پیشفرض ما این است که
وزنها ، برداری که تمام اعضای آن برابر با یک است، می باشد. در این مرحله فرزندان از والد1 و والد 2 طبق رابطه زیر تولید می شوند.
که در رابطه بالا ratio در بازه صفر و یک و ran یک عدد تصادفی می باشد.
مرحله هفتم تغذیه نوزادهای انتخاب شده و ملکه با ژل رویایی بوسیله کارگرها و ارتقاء مجموعه پاسخ اخیرا تولید شده با بکارگیری توابع اکتشاف و اپراتور برازش مطابق مقادیر مناسب آنها میباشد. لازم به ذکر است که مقدار دلتا در محدوده صفر و یک توسط یک تابع توزیع یکنواخت تولید می شود. اگر موقعیت ژن مدنظر ما v باشد، بعد از برازش خواهد شد:
