بخشی از مقاله
مروري بر روش هاي خوشه بندي سريهاي زماني
چکيده
خو شه بندي سريهاي زماني، يکي از مهمترين مفاهيم داده کاوي ا ست ، و پارتي شن بندي يک ديتا ست زماني بدون برچســب به چندين خوشــه اســت ، به طوري که دنباله هاي شــبيه به هم درخوشــه هاي يکســان قرارگيرند. هدف از خوشه بندي سريهاي زماني، يافتن الگوهاي پنهان و جستجوي شباهت ها و پيش بيني ارزش آينده داده هاي سريهاي زماني ميبا شد. داده هاي زماني داراي ويژگيهاي متمايزي ن سبت به بقيه داده ها ميبا شند که همين امر، خو شه بندي آنها را به چالش ميکشد. سريهاي زماني، رشته هاي طولاني از اعداد هستند و بين مقادير متوالي آن وابستگي زماني وجود دارد. الگوريتم هاي ارائه شده براي خو شه بندي سريهاي زماني از نظر نحوه برخورد با داده ها به سه د سته مختلف تق سيم مي شوند. الگوريتم هاي مبتني بر داده هاي خام ، الگوريتم هاي مبتني بر ويژگيهاي ا ستخراج شده از داده هاي خام و الگوريتم هاي مبتني بر مدل هاي ساخته شده از داده هايخام . در اين مقاله ، به بررسي کارهاي قبلي که در هر يک از سه حوزه فوق انجام شده است ، ميپردازيم .
کليد واژه - خوشه بندي، سريهاي زماني، داده کاوي
١. مقدمه
خوشه بندي داده ها به دسته هاي متناسب ، يکي از مباحث مهم و پرکاربرد در تشخيص الگو و حوزه هوش مصنوعي ميباشد. در اين امر رسيدن به دسته هايي که داده هاي درون آنها بيشترين شباهت را به يکديگر دارند حائز اهميت است .
سريهاي زماني، ترتيبي از اعداد حقيقي است که مقدار مشاهده شده از يک رويداد را در فواصل زماني برابر نشان ميدهد. مانند قيمت سهام در روزهاي متوالي. از ويژگيهاي سريهاي زماني ميتوان به ابعاد بالا، حجم زياد و وابستگي زماني بين مقادير آن اشاره کرد. وجود اين ويژگيها نشان ميدهد که از روش هاي موجود در خوشه بندي نميتوان به سادگي در دسته بندي سريهاي زماني استفاده کرد.
بقيه مقاله به شکل زير بخش بندي مي شود. در بخش ٢، حوزه هاي خوشه بندي سريهاي زماني را در سه زير بخش به شرح زير بررسي مي کنيم . بخش ٢-١، بررسي روش هاي مبتني بر داده هاي خام ، بخش ٢- ٢، بررسي روش هاي مبتني بر ويژگيهاياستخراج شده از داده هاي خام و بخش ٢-٣، به بررسي روش هاي مبتني بر مدل - هاي استخراج شده از داده هاي خام اختصاص مي يابد. در بخش ٢، کاربرد خوشه بندي سريهاي زماني و بخش ٣ نيز شامل معيارهاي ارزيابي نتايج خوشه بندي و بخش ٤ نيز شامل کاربرد خوشه بندي است . بخش ٥ نيز شامل نتيجه گيري مي باشد.
٢. حوزه هاي خوشه بندي سريهاي زماني
Han and Kamber [١] ، روش هاي خوشه بندي بر روي داده هاي ايستا، داده هاي که مقادير ويژگيهاي آن ها با گذشت زمان تغيير نميکنند، را به پنج دسته عمده طبقه بندي کردند.
روش هاي پارتيشن بندي ١، روش هاي سلسله مراتبي ٢، روش هاي مبتني بر چگالي ٣، روش هاي مبتني بر شبکه ٤ و روش هاي مبتني بر مدل ٥. اين روش هاي پايه به طور مستقيم و يا اصلاح شده جهت خوشه بندي سريهاي زماني استفاده شده اند.
Liao [٢]، الگوريتم هاي ارائه شده جهت خوشه بندي سري - هاي زماني را از نظر نحوه برخورد با داده ها به سه دسته زير تقسيم شده اند:
الگوريتم هاي مبتني بر داده هاي خام ٦ ، الگوريتم هاي مبتني بر ويژگيهاي استخراج شده از داده هاي خام ٧ و الگوريتم هاي مبتني بر مدل هاي ساخته شده از داده هاي خام .
٢-١. . بررسي روش هاي مبتني بر داده هاي خام
روش هاي سابق معمولا به طور مستقيم روي داده هاي خام کار ميکردند. از امتيازات اين روش ميتوان به جلوگيري از، از دست دادن هرگونه اطلاعات ، داشتن راه مستقيم در گرفتن رفتارهاي پويا و انعطاف پذيري در برابر تغييرات طول داده هاي زماني اشاره کرد. معايب اين روش نيز حساس بودن به مقادير اوليه و پيچيدگي بالاي محاسباتي ميباشد.
Kasmelj and Batagelj [٣]، براي خوشه بندي داده هاي زماني چند متغيره و چند زماني از توسعه روش هاي خوشه - بندي داده هاي ايستا استفاده کردند. روش پيشنهادي فقط بر روي سريهاي زماني با طول مساوي عمل ميکرد، و معيار فاصله ، معبار اقليدس بود. Liao و همکارانش [٤]، از الگوريتم k-means ،fuzzy c-means و خوشه بندي ژنتيک براي سريهاي زماني چند متغيره با طول نامساوي استفاده کردند.
معيار فاصله مورد استفاده DTW٩ بوده است . Golay و همکارانش [٥]، از الگوريتم Fuzzy c-means براي سري - هاي تک متغيره با طول مساوي استفاده کردند. سه معيار فاصله يعني اقليدسي و دو معيار cross correlation based يعني CC و D1 را استفاده نمودند. عيب روش آنها عدم تعيين تعداد بهينه خوشه ها بود. به اين منظور آنها تعداد زياد خوشه ها را به عنوان حدس اوليه استفاده ميکردند.
Wijk and Selow[6]، از خوشه بندي سلسله مراتبي Agglomerative بر پايه معيار فاصله ريشه ميانگين مربعات ١ جهت خوشه بندي سريهاي زماني استفاده کردند.
Liao و همکارانش [٧]، يک روش دو مرحله اي را براي خوشه بندي سريهاي زماني چند متغيره با طول برابر يا طول نابرابر استفاده کردند. در گام اول از الگوريتم k-means و يا Fuzzy c-means براي تبديل سريهاي زماني چند متغيره پيوسته به سريهاي زماني تک متغيره گسسته استفاده کردند.
در گام دوم از الگوريتم k-means براي گروه بندي سريهاي زماني تک متغيره استفاده کردند. آنها معيار فاصله اقليدسي را در گام اول و معيار فاصله kullback-liebler را در گام دوم به کار بردند. Niennattrakul and Ratanamahatana[8]، جهت خوشه بندي سريهاي زماني چند رسانه از الگوريتم k-means به همراه معيار فاصله اقليدسي و از الگوريتم k-medoids به همراه معيار فاصله DTW استفاده کردند. آنها ثابت کردند به کارگيري معيار فاصله DTW با الگوريتم k-means نتايج خوبي را به همراه ندارد. Sobhe Bidari و همکارانش [٩]، براي خوشه بندي سري - هاي زماني مربوط به استخراج الگو در ژن از دو فاز خوشه بندي k-means و Fuzzy c-means با معيار شباهت همبستگي پيرسون ٢ استفاده کرد. Keremer و همکارانش [١٠]، براي تشخيص تغييرات آب و هوايي ابتدا سريهاي زماني چند متغيره با طول هاي نابرابر را به سريهاي زماني با با فواصل طولي برابر تقسيم کردند. سپس الگوريتم خوشه بندي زير دنباله مبتني بر چگالي را با معيار فاصله DTW اعمال کردند.
Yinو همکارانش [١١]، روش خوشه بندي سلسله مراتبي کلاسيک را جهت خوشه بندي سريهاي زماني مربوط به داده - هاي جريان ترافيک بهبود دادند. از ارتباط خاکستري ٣ به عنوان معيار شباهت استفاده کردند. Chandrakala and Sekhar [١٢]، يک روش مبتني بر چگالي يراي خوشه بندي سريهاي زماني چند متغيره با طول متغير ارائه دادند. آنها الگوريتم Kernel DBSCAN را با اندازه گيري فاصله اقليدسي استفاده کرده اند. A.Khan و همکارانش [١٣]، از الگوريتم خوشه بندي ترکيبي ٤ جهت استخراج الگوهاي مکرر در داده هاي سهام و عوامل موثر در فروش محصولات استفاده کردند. آنها در فاز اول از الگوريتم k-means براي تقسيم داده ها به سه خوشه مختلف يعني سهام مرده ، سهام با حرکت آهسته و سهام با حرکت سريع بر اساس دسته بندي محصولات استفاده کردند. در فاز دوم از الگوريتم MFP٥ براي پيدا کردن تعداد تکرار مقدار اقلام استفاده کردند و روند فروش را در يک فرم فشرده بدست آوردند. از فاصله اقليدسي به عنوان معيار فاصله استفاده کردند.
٢-٢. بررسي روش هاي مبتني بر ويژگيهاياستخراج شده از داده هاي خام
در اين روش به طور غير مستقيم روي ويژگيهاي استخراج شده از داده هاي خام کار ميشود زيرا داده هاي خام ، نويز زيادي دارند[١٤].. Wilpon and Rabiner [١٥]، براي تشخيص کلمات در يک صحبت از الگوريتم k-means تغيير داده شده ، استفاده کردند. آنها براي اندازه گيري فاصله متقارن بين دو قسمت از الگوي کلمات از فاصله Itakura استفاده کردند. Show and King [١٦]، از دو الگوريتم سلسله مراتبي Agglomerative به نام هاي حداقل واريانس Ward و Single linkage به همراه معيار فاصله اقليدسي استفاده کردند. آنها از روش آناليز مولفه هاي اصلي 1(PCA) جهت انتخاب ويژگي استفاده کردند.
Oseley و همکارانش [١٧]، يک الگوريتم به نام SCRA2 را ارائه کردند. از الگوريتم k-means تغيير داده شده ، به همراه فاصله اقليدسي استفاده کردند. آنها براي اولين بار از تطبيق الگو٣ براي شناسايي سيگنال هاي داده استفاده کردند. از مدل مخفي مارکوف براي نمايش خوشه ها و از ميزان واريانس درون خوشه اي ٤ براي ارزيابي عمليات خوشه بندي استفاده کردند.
Vlachos و همکارانش [١٨]، ابتدا از تبديل موجک ٥ Haar بر روي سريهاي زماني استفاده کردند سپس الگوريتم تغيير يافته k-means را با فاصله اقليدسي اعمال کردند.
Guo و همکارانش [١٩]، ابتدا سريهاي زماني خام را به وسيله 6ICA به بردار ويژگي با ابعاد پايين تبديل کرد. سپس يک الگوريتم اصلاح شده k-means با فاصله اقليدسي را به بردارهاي ويژه استخراج شده در دنياي واقعي سهام اعمال کردند. Jixue و همکارانش [٢٠]، از تبديل موجک به همراه الگوريتم خوشه بندي مبتني بر شبکه ٧ جهت خوشه بندي سريهاي زماني مالي استفاده کردند.
٢-٣. بررسي روش هاي مبتني بر مدل هاي استخراج شده از داده هاي خام
در اين روش بطور غير مستقيم روي مدل هاي ساخته شده از داده هاي خام کار ميکنيم ، يعني هر سري زماني توسط نوعي از مدل يا ترکيبي از توزيع هاي احتمال توليد ميشود. از امتيازات اين روش ميتوان به مقابله با وابستگي بين داده هاي زماني و از معايب آن به مساله انتخاب مدل و بالا بودن پيچيدگي محاسباتي اشاره کرد. روش هاي پيشنهاد شده در اين متد به شرح زير ميباشند.
Piccolo[٢١]، از مدل ARIMA و الگوريتم خوشه بندي سلسله مراتبي Agglomerative به همراه فاصله اقليدسي در محصولات صنعتي استفاده کرد. Maharaj [٢٢]، الگوريتم Agglomerative را بر مبناي يک مقدار p توسعه داد. در آن دو سري زماني در يک گروه با هم قرار ميگرفتند در صورتي که مقدار p آنها بزرگتر از يک مقدار از پيش تعيين شده بود. او از روش هاي فازي جهت خوشه بندي سريهاي زماني نيز استفاده کرده است [٢٣]. Ramoni و همکارانش [٢٤]، يک الگوريتم بيزين براي خوشه بندي پويا ارائه کردند.
در يک مجموعه S از تعداد n تا مقدار سري زماني، هر سري زماني به يک زنجيره مارکوف ٨ (MC) تبديل شده و سپس خوشه ها بر اساس زنجيره هاي مارکوف شبيه با بيشترين احتمال از فرايندهاي توليد شده ، شکل ميگيرند. آنها از روش خوشه بندي Agglomerative استفاده کردند. هدف انتخاب مدلي با ماکزيمم احتمال posterior بود و از آنجا که مدل ها همه با احتمال مساوي فرض شده اند مقايسه بر اساس احتمال marginal likelihood يعني انجام ميشود.
نتيجه خوشه بندي توسط اندازه گيري اطلاعات داده هاي از دست رفته ٩ ناشي از عمليات خوشه بندي ارزيابي شده است .
Tran and Wanger [٢٥]، از روش خوشه بندي Fuzzy c-means استفاده کردند. از مدل گوسين با معيار فاصله بر اساس لگاريتم likelihood استفاده کردند زيرا داده ها از نوع ترتيبي بوده است . معيار ارزيابي ايشان بر اساس ميزان واريانس دروني خوشه ها بوده است که از طريق محاسبه واريانس خوشه - ها و واريانس کل مجموعه داده به دست ميآيد. با توجه به اينکه اين معيار هم از ميزان همگني داده ها و هم از تراکم خوشه ها بهره ميگيرد معيار مناسبي براي ارزيابي خوشه ها محسوب ميشود. نقطه قوت الگوريتم c ميانگين فازي در اين است که هميشه همگرا ميشود. ولي نقاط ضعفي چون زمان محاسبات زياد، حساس بودن به حدسهاي اوليه و به نويز مي - باشد. در ضمن ممکن است در مينيمم هاي محلي نيز متوقف شود.
Oatesو همکارانش [٢٦]، يک الگوريتم خوشه بندي ترکيبي بر روي سريهاي زماني را پيشنهاد کردند که در آن از مقداردهي اوليه حدسي استفاده کردند و از مدل مخفي مارکوف نيز براي حذف دنباله هايي که متعلق به يک خوشه نيستند استفاده کردند. در ابتدا از يک الگوريتم خوشه بندي سلسله مراتبي براي بدست آوردن تخمين اوليه تعداد خوشه استفاده کردند. از DTW1 جهت ارزيابي شباهت استفاده کردند. Biornacki و همکارانش [٢٧]، معيار ICL2 را براي انتخاب يک مدل مخلوط گوسي ٣ و تعداد خوشه ها پيشنهاد کردند. معيار ICL اساسا يک معيار BIC ٤ با تفريق ميانگين آنتروپي تخمين زده شده است . آزمايشات عددي اطلاعات شبيه سازي شده و ديتاهاي واقعي نشان ميدهد که معيار ICL بر تمايل BIC در دست بالا گرفتن تعداد خوشه ها غلبه مي - کند. آنها از الگوريتم 5EM جهت خوشه بندي استفاده کرده اند.
BIC، به عنوان معيار انتخاب تعداد خوشه ها به صورت الگوريتم خودکار است .
Li and Biswas [٢٨]، يک متد خوشه بندي براي داده هاي زماني ٦ با استفاده از مدل مخفي مارکوف (٧ HMM) ارائه دادند. آنها از معيار ارزيابي PMI٨ جهت اندازه گيري تعداد خوشه ها استفاده کردند. خوشه بندي k-means و divisive را بکار برده اند. ساختار هر مدل مخفي مارکوف ، بالاترين احتمال حاشيه اي مبتني بر معيار BIC و تقريب cheeseman-stutz است . آنها مجموعه داده هاي مصنوعي از سه مدل تصادفي توليد شده را ايجاد کردند. يکي با تعداد سه حالت ٩ ، يکي با تعداد چهار حالت و ديگري با تعداد پنج حالت و نشان دادند که روش پيشنهادي ميتواند مدل مخفي مارکوف را با اندازه اي درست و کاملا نزديک به مقدار پارامترهاي مدل بازسازي کند.
