تعداد صفحات: ۱۲۱ | قابل ویرایش

فهرست مطالب

۱-        مقدمه   ۲

۱-۱-       تعریف مسأله و انگیزه انجام آن. ۵

۱-۲-       روش پیشنهادی برای حل مسأله. ۶

۱-۳-       ساختار پایان نامه. ۸

۲-        سریهای زمانی و مفاهیم مربوطه. ۱۱

۲-۱-       سریهای زمانی     ۱۱

۲-۲-       معیارهای اندازه گیری فاصله. ۱۴

۲-۳-       پیش پردازشهای روی سری زمانی.. ۱۴

۲-۴-       تکنیکهای کاهش ابعاد داده ۱۶

۳-        خوشه بندی  ۳۲

۳-۱-       تعریف خوشه بندی.. ۳۲

۳-۲-       معیارهای ارزیابی خوشه بندی.. ۳۴

۳-۳-       الگوریتم های خوشه بندی.. ۳۷

۳-۴-       الگوریتم خوشه بندی k-means و Fuzzy k-means. 39

۴-        خوشه بندی سریهای زمانی. ۴۲

۴-۱-       بررسی تحقیقات انجام شده در زمینه خوشه بندی سریهای زمانی و مقایسه تطبیقی آنها ۴۴

۴-۲-       نکاتی مهم در داده کاوی سریهای زمانی.. ۴۹

۵-        خوشه بندی با استفاده از الگوریتم های ژنتیک.. ۵۳

۵-۱-       الگوریتم ژنتیک    ۵۳

۵-۲-       تنظیم قسمتهای مختلف الگوریتم ژنتیک برای خوشه بندی.. ۵۸

۵-۳-       مقایسه تطبیقی فعالیتهای مرتبط با خوشه بندی بوسیله الگوریتم ژنتیک… ۶۳

۶-        بررسی تأثیر روشهای کاهش ابعاد داده در خوشه بندی. ۶۸

۶-۱-       بسترهای داده   ۶۹

۶-۲-       متدولوژی انجام آزمایشها ۷۲

۶-۳-       نتایج آزمایشها  ۷۴

۶-۴-       کدام روش و چه میزان کاهش… ۷۹

۷-        ارائه روشی جدید برای خوشه بندی سریهای زمانی. ۸۳

۷-۱-       الگوریتم AKU-kMeans  ۸۵

۷-۲-       الگوریتم I-kMeans  ۸۷

۷-۳-       بسترهای داده   ۸۸

۷-۴-       نتایج آزمایشات   ۹۰

۷-۵-       مقایسه تطبیقی الگوریتم AKU-kMeans با روشهای دیگر خوشه بندی سریهای زمانی.. ۹۳

۸-        خوشه بندی سریهای زمانی با استفاده از الگوریتم ژنتیک.. ۹۶

۸-۱-       الگوریتم IGA-Clustering  ۹۷

۸-۲-       نتایج آزمایشات   ۱۰۱

۸-۳-       مقایسه تطبیقی الگوریتم IGA-Clustering با روشهای دیگر. ۱۰۳

۹-        آزمایشات تکمیلی. ۱۰۷

۱۰-      جمع بندی، نتیجه گیری و کارهای آتی. ۱۱۶

منابع و مراجع    ۱۱۹

واژه نامه انگلیسی به فارسی. ۱۲۲

واژه نامه فارسی به انگلیسی. ۱۲۴

چکیده

در سالهای اخیر داده­کاوی برروی سریهای زمانی توجه بسیاری را به خود جلب کرده است. شاید بتوان گفت از میان تمام تکنیکهای به کار برده شده برروی سریهای زمانی، خوشه­بندی پر استفاده­ترین تکنیک می­باشد. خوشه­بندی سریهای زمانی می­تواند به دلائل مختلفی مانند یافتن الگوهای پنهان در داده­ها و جستجوی شباهتها انجام شود.

سریهای زمانی معمولاً دارای ابعاد طولانی هستند که این امر کار پردازش آنها را چه از نظر حافظه و چه از نظر زمان با مشکل روبرو می­سازد. اما خوشبختانه به دلیل وابستگی زیاد بین مقادیر متوالی یک سری زمانی، تکنیکهای کاهش ابعاد داده راهکار مناسبی برای حل مشکل ابعاد آنها می­باشد.

با توجه به اینکه موضوع مورد بررسی ما خوشه­بندی است، ما به بررسی تأثیر پنج روش مختلف کاهش ابعاد داده در خوشه­بندی به وسیله الگوریتم k-means پرداخته و با انجام آزمایشات وسیع به این نتیجه رسیدیم که خوشه­بندی برروی درصد بسیار کمی از مهمترین مؤلفه­های استخراج شده از داده­ها می­تواند به نتایجی بسیار نزدیک به خوشه­بندی برروی داده­های اصلی منجر شود.

همچنین با ایجاد دو تغییر اساسی در روش Random Projection، روش جدیدی به نام Sample Based Projection برای کاهش ابعاد داده ارائه کردیم که در آزمایشات انجام شده، عملکرد خوبی از خود به نمایش گذاشت بطوری که وقتی ابعاد داده­های کاهش یافته را کوچک (مثلاً کمتر از ۸) در نظر گرفتیم، از پنج روش دیگر بجز روش Principle Component Analysis بهتر عمل کرد.

در ادامه الگوریتمی به نام AKU-kMeans برای خوشه­بندی سریهای زمانی ارائه کرده­ایم که چه از نظر زمان اجرا و چه از نظر معیار ICV (که از آن برای ارزیابی خوشه­بندی استفاده کرده­ایم) بهتر از الگوریتم k-means عمل می­کند.

مقدمه

بسیاری از داده­هایی که امروزه با آنها سروکار داریم داده­هایی هستند که در طول زمان تغییر می­کنند. دمای هوا، میزان مصرف انرژی در یک کشور، ارتفاع سطح آب در یک رودخانه و قیمت سهام شرکتها، همگی از نوع داده­های وابسته به زمان هستند.

بخش عمده­ای از این داده­ها از نوع سریهای زمانی می­باشد. هرچند یک تعریف واحد برای سریهای زمانی وجود ندارد اما در بیشتر گزارشات تحقیقاتی و کتابها سری زمانی را ترتیبی از اعداد حقیقی در نظر می­گیرند که مقدار مشاهده شده از یک رویداد را در فواصل زمانی برابر نشان می­دهد.

دانشی که در این نوع داده­ها نهفته است می­تواند بسیار ارزشمند باشد. خوشبختانه امروزه با پیشرفتهایی که در علوم کامپیوتر بوجود آمده امکان استخراج این اطلاعات ارزشمند از داده­ها پدید آمده است. استخراج این اطلاعات تحت فرایندی به نام استخراج دانش انجام می­شود. استخراج دانش، طیف وسیعی از انواع داده­ها را شامل می­شود، مانند متن، جداول پایگاه داده، صفحات وب، سریهای زمانی و غیره.

فرایند استخراج دانش را می­توان به سه مرحله تقسیم نمود:

• پیش پردازش داده­ها: در بیشتر مواقع قبل از اجرای الگوریتم­های داده­کاوی، لازم است که بر حسب نیاز، پیش­پردازشهایی برروی داده­ها انجام شود. مانند یکی کردن منابع داده­ها، پاکسازی داده­ها، تبدیل مقادیر پیوسته به گسسته، انتخاب ویژگی­های مناسب، کاهش حجم داده­ها (مثلاً با استفاده از تکنیکهای کاهش ابعاد داده).
• داده کاوی: به معنی استخراج اتوماتیک (یا نیمه اتوماتیک) دانش از داده­ها است. داده­کاوی ترکیبی است از آمار، هوش مصنوعی، پایگاه داده و یادگیری ماشین.

تعریف مسأله و انگیزه انجام آن

از آنجایی که خوشه­بندی در زمره مسائل بغرنج قرار دارد برای حل آن معمولاً از الگوریتم­های مکاشفه­ای استفاده می­شود. سه نمونه از این الگوریتم­ها را در شکل ۱-۱ مشاهده می­کنید. الگوریتم های مکاشفه­ای معمولاً بهترین جواب را پیدا نمی­کنند بلکه جوابی نزدیک به جواب بهینه را پیدا می­کنند.

به همین دلیل همواره پژوهشگران و محققان بدنبال ارائه راه حلهایی هستند که بتواند در آزمایشات مختلف نتایج بهتری را نسبت به راه­حلهای قبلی ارائه دهد. یکی از معروفترین روشهای مکاشفه­ای، الگوریتم ژنتیک است که بدلیل قابلیت زیاد آن در اجرای موازی و نیز پایین بودن احتمال به تله افتادن آن در مینیمم­های محلی نسبت به روشهای مکاشفه­ای دیگر، از محبوبیت بیشتری برخوردار است.

در این پایان نامه ما قصد داریم سریهای زمانی را با استفاده از الگوریتم­های ژنتیک خوشه­بندی نماییم. البته تا کنون چندین گزارش تحقیقاتی برای خوشه­بندی داده­های ایستا با استفاده از الگوریتم های ژنتیک ارائه شده که تعدادی از آنها را در فصل پنجم بررسی خواهیم کرد، اما تا کنون از این روش برای خوشه­بندی سریهای زمانی استفاده نشده است [Liao2005].

بعبارت دیگر اکثر این محققان خوشه­بندی را برای داده­هایی با ابعاد کم (مثلاً کمتر از ۱۰) انجام داده­اند، در حالی که سریهای زمانی معمولاً دارای اندازه­ای طولانی (مثلاً ۱۰۰ یا ۱۰۰۰) می­باشند. در واقع مهمترین چالشی که در این مسأله با آن روبرو هستیم ابعاد زیاد داده­ها است که چه از نظر زمان اجرای الگوریتم و چه از نظر حافظه می­تواند مشکل­ساز باشد.

روش پیشنهادی برای حل مسأله

همانطور  که گفتیم سریهای زمانی معمولاًً دارای اندازه­ای طولانی می­باشند که این امر چه از نظر حافظه و چه از نظر پیچیدگی زمانی، کار پردازش آنها را با مشکل روبرو می­سازد. روشی که ما برای حل این مسأله به کار برده­ایم استفاده از تکنیکهای کاهش ابعاد داده قبل از انجام خوشه­بندی است.

استفاده از تکنیکهای کاهش ابعاد داده قبل از هرگونه پردازشی، یک راه حل متداول است که در تحقیقات مختلف به طرق متفاوتی از آن استفاده شده است. مانند [Lin2004] و [Wang2006] که هر کدام روشی متفاوت را برای کاهش ابعاد داده قبل از خوشه­بندی سریهای زمانی به کار برده­اند.

برای استفاده از ایده فوق، به دو سؤال اصلی باید پاسخ داد:

1. از کدام تکنیک برای کاهش ابعاد داده­ استفاده کنیم؟
2. با توجه به اینکه اکثر تکنیکها به ما امکان کاهش ابعاد داده در دقتهای مختلف را می­دهد، ابعاد داده­ها را تا چه دقتی کاهش دهیم که تأثیری در نتیجه خوشه­بندی نداشته باشد و یا تأثیر آن بسیار ناچیز باشد؟

برای پاسخ­گویی به این دو سؤال، الزاماً باید از مسیر تجربه و انجام آزمایشات و مقایسه تطبیقی نتایج حاصل به پاسخ قابل قبول دست یافت. همانطور که در بالا اشاره شد خوشه­بندی می­تواند به روشهای مختلفی انجام شود. پیاده­سازی و آزمایش تمام حالات مختلف خوشه­بندی کاری طاقت­فرسا خواهد بود.

بنابراین تصمیم گرفتیم فرضیاتی را در مورد مسأله خوشه­بندی سریهای زمانی در نظر بگیریم و آزمایش­هایمان را بر اساس آن فرضیات طراحی کنیم.

منابع و مراجع

1. [Agrawal1993] R. Agrawal, C. Faloutsos, and A. N. Swami, “Efficient Similarity Search In Sequence Databases”, in Proc. of the 4th International Conference of Foundations of Data Organization and Algorithms (FODO), Chicago, Illinois, pp. 69-84, 1993.
2. [Bhuyan1995] J.N. Bhuyan, “A Combination of Genetic Algorithm and Simulated Evolution Techniques for Clustering”, ACM Conference on Computer Science, pp. 127-134, 1995.
3. [Demerdash1999] N. A. O. Demerdash and J. F. Bangura, “Characterization of induction motors in adjustable-speed drives using a time-stepping coupled finite element state-space method including experimental validation”, IEEE Transactions On Industry Applications, vol. 35, pp. 790-802, July/Aug. 1999.
4. [Garai2004] G. Garai, and B.B. Chaudhuri, “A Novel Genetic Algorithm for Automatic Clustering”, Pattern Recognition Letters, ۲۵(۲): ۱۷۳–۱۸۷, ۲۰۰۴
5. [Gesù۲۰۰۵] V.D. Gesù, R. Giancarlo, G.L. Bosco, A. Raimondi, D. Scaturro, “GenClust: A genetic algorithm for clustering gene expression data”. BMC Bioinformatics ۶: ۲۸۹,  ۲۰۰۵.
6. [Hall1999] L.O. Hall, I.B. O. zyurt, J.C. Bezdek, “Clustering with a genetically optimized approach”, IEEE Transactions on Evolutionary Computation, vol. 3, no. 2, pp. 103–۱۱۲, ۱۹۹۹.
7. [Han2001] J. Han, and M. Kamber, Data Mining: Concepts and Techniques, San Francisco: Morgan Kaufmann, 2001.
8. [Hruschka2003] E.R. Hruschka, N.F.F. Ebecken, “A genetic algorithm for cluster analysis”, Intelligent Data Analysis, vol. 7, no. 1, pp. 15–۲۵, ۲۰۰۳.