بخشی از مقاله
چکیده
امروزه خوشهبندی سریهای زمانی، در زمینههای متعددی مانند پزشکی و اقتصاد به دلیل کشف الگوهای پنهان و پیشبینی مقادیر آینده، بسیار حائز اهمیت است. اما سریهای زمانی دارای ویژگیهایی مانند: حجم زیاد، ابعاد بالا و وابستگی زمانی بین دادهها میباشند که خوشهبندی آنها را با چالشهایی چون: انتخاب مدل مناسب، حل مسئله مقداردهی اولیه مدل، تعیین خودکار تعداد خوشهها و هزینه بالای محاسباتی مواجه میکند. از سوی دیگر، خوشهبندی یک مسئله بهینهسازی نیز میباشد؛ اما روشهای سنتی خوشهبندی برای دادهها با ابعاد بالا، به دلیل پدیدار شدن زیاد بهینه محلی، با مشکل همگرا شدن به این بهینهها مواجه هستند.
در این مقاله برای رفع معایب ذکر شده، الگوریتم خوشهبندی به نام k » مدل مبتنی بر مدل مخفی مارکوف « را با الگوریتم بهینهسازی گرگ خاکستری ترکیب نمودیم. کارایی روش پیشنهادی را با اجرا بر روی چندین مجموعه داده سریهای زمانی استاندارد، ارزیابی و با روشهای دیگر مانند روش ترکیب شده با الگوریتم ازدحام ذرات مقایسه نمودیم. نتایج نشان میدهد که روش پیشنهادی به دلیل وابسته نبودن به مقادیر اولیه و اجتناب از بهینه محلی از صحت و استحکام بیشتری برخوردار میباشد و با استفاده از مدل ریاضی ساده در براورد دوباره مراکز خوشهها هزینه محاسباتی را نیز کاهش داده است.
کلید واژه- الگوریتم بهینهسازی، خوشهبندی، سریهای زمانی، گرگ خاکستری
.1 مقدمه
یک سری زمانی، دنبالهای از اعداد حقیقی میباشد که مقدار مشاهده شده از یک رویداد را در فواصل زمانی برابر نشان می-دهد.[1] مانند قیمت سهام در روزهای متوالی. خوشهبندی سریهای زمانی به معنی افرازبندی یک مجموعه از سریهای زمانی بدون برچسب به چندین گروه میباشد به طوریکه دنبالههای شبیه به هم در یک خوشه قرار گیرند.[2] امروزه خوشهبندی سریهای زمانی در زمینههای متعددی مانند: پزشکی، اقتصاد، علوم زیستی حائز اهمیت می-باشد[3]،[4]،.[5] از خوشهبندی سریهای زمانی میتوان برای یافتن الگوهای پنهان در دادهها و پیشینی مقادیر ناشناخته آینده استفاده نمود[6]،.[7]
اما سریهای زمانی دارای ویژگیهای متمایزی نسبت به داده-های ایستا میباشند؛ مانند حجم زیاد، ابعاد بالا و همبستگی زمانی پیچیده در بین دادهها.[8] این ویژگیها خوشهبندی سریهای زمانی را با چالشهایی مواجه میکند. به عنوان نمونه، ابعاد بالای سریهای زمانی خوشهبندی آنها را مدام در بهینه محلی قرار میدهد. از این رو انتخاب رویکردی مناسب جهت جستجوی فضای جواب و خروج از بهینه محلی اهمیت ویژهای دارد. امروزه برای حل مسائل پیچیده مانند خوشهبندی دادهها که تا حدودی بیقاعده، نویزدار و متغییر با زمان هستند از الگوریتمهای بهینهسازی مانند الگوریتم ژنتیک[9]، الگوریتم کلونی مورچگان[10] و الگوریتم ازدحام ذرات[11] استفاده میشود.
در این میان با توجه به قدرت و سرعت بالایی که الگوریتم بهینهسازی گرگ خاکستری[23] در جستجوی فضای جواب و خروج از بهینه محلی نسبت به الگوریتمهای یاد شده دارد، در این تحقیق این الگوریتم را برای ترکیب با الگوریتم خوشهبندی انتخاب کردیم.ادامهی مقاله به صورت زیر تنظیم شده است. در بخش دوم، تحقیقات انجام شده در مورد خوشهبندی سریهای زمانی را بیان کرده و در بخش سوم، الگوریتم k » مدل مبتنی بر مدل مخفی مارکوف « و الگوریتم بهینهسازی گرگ خاکستری بررسی میگردند. سپس در بخش چهارم، روش پیشنهادی که ترکیبی از این دو الگوریتم فوق میباشد، معرفی میگردد. در بخش پنجم، نحوه ارزیابی و نتایج آن و در بخش آخر نتیجه-گیری و کارهای آینده بیان میشود.
.2 کارهای مرتبط
[12] Han and Kamber، روشهای خوشهبندی بر روی دادههای ایستا را به پنج دسته عمده طبقهبندی کردند. روش-های پارتیشنبندی 1، روشهای سلسلهمراتبی2، روشهای مبتنی بر چگالی3، روشهای مبتنی بر شبکه4 و روشهای مبتنی بر مدل.5 از الگوریتمهای موجود در روشهای فوق به طور مستقیم و یا اصلاح شده جهت خوشهبندی سریهای زمانی استفاده شده است. از طرفی [13] Liao، الگوریتمهای ارائه شده جهت خوشهبندی سریهای زمانی را از نظر نحوه برخورد با دادهها به سه دسته زیر نیز تقسیم نموده است:
دسته اول، الگوریتمهایی هستند که به طور مستقیم بر داده-های خام6 اعمال میشوند؛ مانند الگوریتمهای k میانه، c میانه فازی و الگوریتم ادغامی[14] ، [15]، .[16] از مزایای این دسته میتوان به از دست ندادن دادهها و انعطافپذیری در برابر تغییرات طول دادههای زمانی و از معایب آن نیز به نویز فراوان، حساس به مقادیر اولیه و پیچیدگی بالای محاسباتی اشاره کرد. دسته دوم، الگوریتمهایی هستند که بر ویژگیهای استخراج شده از دادههای خام7 اعمال میشوند. مانند الگوریتمهای k میانه، c میانه فازی و الگوریتم ادغامی به همراه الگوریتمهایانتخاب ویژگی مانند آنالیز مولفههای اصلی[17] - PCA - 1، [18]، .[19] این دسته از دادهها نویز کمتری دارند.
در دسته آخر، الگوریتمهای معمول خوشهبندی بر مدلهای ساخته شده از دادههای خام 2 اعمال میشوند. از مدلهای تولیدی در این دسته میتوان به مدل مخفی مارکوف - HMM - 3، مدل ARMA4، زنجیره مارکوف مرتبه اول - MC - 5 و شبکهی بیزین داینامیک اشاره کرد[20]، [21]،.[22]در این میان، روشهای مبتنی بر مدل مخصوصا مبتنی بر مدل مخفی مارکوف به دلیل اینکه با توانایی بیشتری بر وابستگی زمانی بین دادهها مقابله میکند به طور وسیعتر مورد استفاده قرار گرفته است. ما نیز الگوریتم k » مدل مبتنی بر مدل مخفی مارکوف « را به دلیل سادگی و کارایی جهت خوشهبندی سری-های زمانی در این تحقیق انتخاب نمودیم، که در ادامه آن را شرح میدهیم.
.3 الگوریتم ترکیبی پیشنهادی
الگوریتم پیشنهادی، از ترکیب دو الگوریتم k » مدل مبتنی بر مدل مخفی مارکوف [22]« و الگوریتم بهینهسازی گرگ خاکستری[23]، حاصل شده است. در این بخش ابتدا به طور مختصر هر یک از این الگوریتمها را شرح داده و سپس در بخش چهارم، روش پیشنهادی و مزایای آن را توضیح میدهیم.
.1-3 الگوریتم خوشهبندی k » مدل مبتنی بر مدل مخفی مارکوف« 6
این الگوریتم در مقاله [22] بیان شده است و همان الگوریتم k میانه[24] 7 میباشد، با این تفاوت که مراکز خوشهها مدل-های مخفی مارکوف میباشند و عمل انتساب نمونهها به هر خوشه با توجه به بالا بودن احتمال مشاهده8 هر نمونه از مرکزهر خوشه به عنوان معیار فاصله، انجام میشود.[25] این الگوریتم به شرح زیر میباشد:
1.انتخاب تصادفی k تا نمونه از مجموعه داده سری-های زمانی بدون جایگذاری به عنوان مراکز اولیه k تا خوشه
2.مقداردهی اولیه k مدل مخفی مارکوف با تعداد از پیش تعریف شده حالات و تخمین پارامترهای مدل به وسیله الگوریتم EM
3.محاسبه لگاریتم درستنمایی هر نمونه از مدل مخفی مارکوف
4.اختصاص هر نمونه به مدلی که دارای بیشترین احتمال مشاهده از مدل را میباشد.
5.براورد دوباره پارامترهای مدلهای مخفی مارکوف مربوط به خوشهها
6.تکرار گامهای 3 تا 5 تا زمانی که عضویت خوشهها تغییر نکند.
مهمترین مزیت این الگوریتم، در نظر گرفتن وابستگی زمانی بین دادهها در سریها زمانی به کمک مدل مخفی مارکوف میباشد. از طرفی چون معیار فاصله در این الگوریتم، میزان احتمال مشاهده از مدل میباشد، این الگوریتم بر روی مجموعه دادهها با طول - ابعاد - نامساوی و دارای مقادیر گمشده9 نیز قابل اعمال میباشد که این امر با معیار فاصله اقلیدوسی[26] امکانپذیر نیست.
اما این الگوریتم نیز مانند الگوریتم K میانه، از وابسته بودن به تعیین تعداد خوشهها، مقادیر اولیه مراکز و همچنین افتادن در بهینه محلی رنج میبرد. در این تحقیق معایب ذکر شده به کمک ترکیب این الگوریتم با الگوریتم بهینهسازی گرگ
