Journal of Geomatics Science and Technology

fa ارائه ی یک روش خوشه بندی توافقی سری های زمانی بر اساس روش Fuzzy C-Means و الگوریتم انبوه ذرات A Hybrid Time Series Clustering Method Based on Fuzzy C-Means Algorithm: An Agreement Based Clustering Approach سامانه های اطلاعات مکانی GIS پژوهشي Research <div style="text-align: justify;">در سالهای اخیر با پیشرفت فناوریهای جمع آوری اطلاعات و فراهم شدن حجم عظیمی از دادههای پیچیده همچون سریهای زمانی نیاز به روشهایی مناسب به منظور تجزیه و تحلیل این نوع داده بیش از پیش احساس میشود. از میان روشهای مختلف دادهکاوی موجود تکنیک خوشهبندی دادهها با هدف ساده سازی مجموعه دادههای بزرگ و استخراج اطلاعات مفید توجه بسیاری از محققین علوم کامپیوتر را به خود جلب کرده است. مسئلهی انتخاب تابع فاصله یکی از مهمترین چالشهایی است که پیش از آغاز فرآیند خوشهبندی سریهای زمانی مورد توجه قرار میگیرد. انتخاب تابع فاصلهی مناسب یک مجموعه داده به شناخت ماهیت داده پیش از انجام عملیات خوشهبندی وابسته میباشد و از این رو امری پیچیده و زمانبر میباشد. از سویی دیگر تاکنون توابع فاصلهی مختلفی با ویژگیها و نقاط قوت متفاوت به منظور اندازهگیری میزان تفاوت/شباهت میان سریهای زمانی پیشنهاد داده شده است. چگونگی ارائهی یک روش خوشهبندی با قابلیت بهره جستن از ویژگیهای توابع فاصلهی مختلف به طور همزمان و بدون نیاز به شناخت ماهیت دادهها پیش از آغاز فرآیند خوشهبندی، چالش اصلی این تحقیق میباشد. به منظور حل این مسئله در این تحقیق یک روش خوشهبندی با ترکیب روش خوشهبندی <span dir="LTR">Fuzzy C-Means</span> (<span dir="LTR">FCM</span>) و الگوریتم شناخته شدهی مبتنی بر هوش جمعی انبوه ذرات (<span dir="LTR">PSO</span>) با هدف استفاده از توابع فاصلهی مختلف با وزنهای متفاوت در حین فرآیند خوشهبندی پیشنهاد داده شد. انتخاب تابع هدف در این مطالعه به گونهای بوده است که نتیجهی حاصل از خوشهبندی بیشترین اشتراک را با نتایج خوشهبندی حاصل از توابع فاصلهی مختلف داشته باشد. به عبارت دیگر روش خوشهبندی ارائه شده در این تحقیق یک روش خوشهبندی توافقی میباشد که نتیجه حاصل توافق میان توابع فاصلهی مختلف میباشد. روش پیشنهادی ارائه شده در این تحقیق با در نظر گرفتن سه تابع فاصلهی مختلف بر روی هفت سری مجموعه دادهی شناخته شده از سریهای زمانی پیادهسازی شد و با پنج روش دیگر مقایسه گردید نتایج حاصل از این مقایسه نشان داد روش ارائه شده در این تحقیق در بیشتر از 85 درصد موارد بهتر از سایر روشها عمل کرده است.<span dir="LTR"></span></div> <div style="text-align: justify;">In recent years, the advancement of information gathering technologies such as GPS and GSM networks have led to huge complex datasets such as time series and trajectories. As a result it is essential to use appropriate methods to analyze the produced large raw datasets. Extracting useful information from large data sets has always been one of the most important challenges in different sciences, and data mining techniques provide useful solutions to solve this problem. Nowadays, clustering technique as the most widely used function of data mining, has attracted the attention of many researchers in various sciences. Due to different applications, the problem of clustering time series data has become highly popular and many approaches have been presented in this field. An efficient clustering method groups data in such a way that the objects in the same cluster are more similar to each other than to objects in <em>different clusters</em>. In order to compute the difference/similarity between time series data in clustering process, a similarity measure or distance function is used. Therefore, choosing an appropriate distance function is one of the most important challenges that should be considered before starting the clustering process. So far, various distance functions have been proposed to measure the difference/similarity between time series and each of them have its own strengths and weaknesses. Since choosing a suitable distance function to cluster a specific data set is a complicated process, in this study, we proposed a clustering method based on combination of the well-known Fuzzy C-Means (FCM) method and the Particle Swarm Optimization with the ability of using different distance functions in time series clustering process. In this way, the step of choosing the best distance function before starting time series clustering procedure has been deleted and different similarity measures can participate in the clustering process with different impacts. The objective function in this study is defined based on Fuzzy C-Means clustering objective function and the particle Swarm Optimization algorithm is used to find the optimal value for the considered objective function. Finally, by considering three distance functions including Euclidean distance, dynamic time warping and Pearson correlation coefficients the proposed method was implemented on seven well-known UCR time series datasets. Also, by considering the average normalized mutual information as a criterion for evaluating the performance of methods in this research, the proposed method was compared with five other methods. The results of this comparison indicated that the method presented in this study performed better in more than 85% of cases rather than other methods. In order to have a better evaluation, Tukey’s multiple comparison tests with a threshold of p < 0.05 is used with the ability of comparing the methods in pairs. The results obtained by Tukey test showed that, in about 83% of cases, the difference between achieved results by the proposed method in this study and results obtained by the other five techniques are statistically significant. Overall, the results of this study clearly showed the superiority of the proposed clustering method in the production of high quality clusters in comparison to some other methods.</div> داده کاوی, خوشه بندی, تابع فاصله, سری زمانی, Fuzzy C-Means, الگوریتم انبوه ذرات Clustering, Time Series, Particle Swarm Optimization, Fuzzy C-Means 23 37 http://jgst.issgeac.ir/browse.php?a_code=A-10-334-2&slc_lang=fa&sid=1 Z. Izakian زاهده ایزکیان zizakian@mail.kntu.ac.ir 10031947532846007037 10031947532846007037 Yes K.N. Toosi University of Technology دانشگاه خواجه نصیر طوسی M. S. Mesgari محمد سعدی مسگری mesgari@kntu.ac.ir 10031947532846007038 10031947532846007038 No K.N. Toosi University of Technology دانشگاه خواجه نصیر طوسی