Journal of Geomatics Science and Technology

fa ارائه ی یک روش خوشه بندی سری های زمانی بر مبنای الگوریتم تکاملی دیفرانسیلی و تبدیل کسینوسی گسسته Time Series Data Clustering Based on Differential Evolution Algorithm and Discrete Cosine Transform سامانه های اطلاعات مکانی GIS پژوهشي Research <div style="text-align: right"> با پیشرفت روز افزون تکنولوژیهای جمع آوری اطلاعات و امکان دسترسی به حجم عظیمی از داده همواره نیازمند روشهایی برای تجزیه و تحلیل این حجم داده خام و استخراج اطلاعات مفید از آن میباشیم.  امروزه خوشهبندی داده به عنوان یکی از روشهای آنالیز و ساده سازی مجموعه دادههای بزرگ، مورد توجه بسیاری از محققین قرار گرفته است. در این میان خوشهبندی سریهای زمانی با دقت مورد قبول، حائز اهمیت بسیاری میباشد. در روش پیشنهادی از ترکیب الگوریتم تکاملی دیفرانسیلی و روش خوشه Fuzzy-Cmeans به عنوان یکی از الگوریتمهای خوشهبندی مطرح و شناخته شده، برای خوشهبندی سریهای زمانی استفاده گردید. در این روش برای کاهش مجهولات مسئله و در نتیجه افزایش کارایی الگوریتم، تکنیکهای مختلف نمایش دادههای مکانی-زمانی را مورد بررسی قرار دادیم و از این میان روش ضرایب DCT را برای کاهش مجهولات مراکز خوشهها انتخاب کردیم. بدین مفهوم که الگوریتم تکاملی دیفرانسیلی انتخابی برای خوشهبندی، به جای یافتن تمامی المانهای مراکز خوشههای موجود در مجموعه داده، تنها تعداد محدودی از ضرایب DCT این مراکز را یافته و سپس با استفاده از همین ضرایب محدود مراکز خوشهها بازسازی میشوند. با در نظر گرفتن تابع فاصلهی Dynamic Time Warping و انتخاب تابع بهینهسازی مربوط به روش خوشهبندی Fuzzy-Cmeans، روش پیشنهادی بر روی دو مجموعه داده پیادهسازی شد و با روش خوشهبندی FCM و روش خوشهبندی مبتنی بر الگوریتم تکاملی دیفرانسیلی بدون استفاده از ضرایب DCT مقایسه گردید. روش پیشنهادی کندتر از الگوریتم خوشهبندی Fuzzy-Cmeans بوده اما به دلیل استفاده از روش تبدیل کسینوسی گسسته برای کاهش مجهولات، سریعتر از روش خوشهبندی معمول مبتنی بر الگوریتم تکاملی دیفرانسیلی عمل میکند. همچنین نتایج حاصل از مقایسهی این سه روش نشاندهندهی عملکرد بهتر روش پیشنهادی نسبت به دو روش دیگر میباشد. </div> Time series is a type of data with complex structure. Analysis of time series is used in sciences such as meteorology, economics, geology, marine science, medicine and engineering widely. So, Because of time series applications in various sciences, the interest to analyze these data has been increased.On the other hand by developing information gathering technologies such as mobile, GPS and sensors, and Access to large volumes of time series data, we always require methods to extract useful information from large datasets. Thus, data mining is an important method for solving this problem. Clustering analysis as the most commonly used function of data mining, has attracted many researchers in computer science. Clustering is a strong instrument for knowledge discovery and it provides useful information about existing patterns in datasets. In general, the purpose of clustering is representing large datasets by a fewer number of cluster centers. It simplifies large datasets and thus is an important step in the process of knowledge discovery and data mining. Fuzzy C-means (FCM) clustering is one of the most important classic clustering methods that have been used in many researches. The main disadvantage of this method is the high probability of getting trapped in local optima especially in facing high-dimensional data such as time series. Furthermore Euclidean distance is the most commonly used similarity measure in Fuzzy C-means but sometimes, its necessary to use another similarity/dissimilarity measures instead of Euclidean distance. In this paper in order to compensate the shortcomings of Fuzzy C-means algorithm, we used one of the existing evolutionary algorithms. Evolutionary algorithms has gained huge popularity in the field of pattern recognition and clustering recently. Among the existing evolutionary algorithms, the differential evolution algorithm as a strong, fast and efficient global search method has been attracted the attention of researchers. In this paper, we proposed a technique for clustering time series data using a combination of Fuzzy C-means and differential evolution (DE) approach and we considered dynamic time warping (DTW) as distance measures between time series. Also, in this method we used Discrete Cosine Transform (DCT) to time series dimension reduction. Finding all elements of cluster centers using differential evolution is time consuming and the large number of unknown parameters related to the cluster centers will reduce the efficiency and the speed of differential evolution algorithm.So, for reducing the search space,the most important Discrete Cosine Transform coefficients of the cluster centers were recognized as the main unknown clustering problem in the proposed method and differential evolution algorithm tries to determine the near optimal Discrete Cosine Transform  coefficients of cluster centers by minimizing the Fuzzy C-means objective function. Experimental results over two popular data sets indicate the superiority of the proposed technique compared to fuzzy C-means and a clustering algorithm based on differential evolution without using dimension reduction techniques.Comparing the run time of the methods, the proposed method is slower than the Fuzzy C-means clustering algorithm, but due to the use of discrete cosine transform method to reduce unknowns, it operates faster than differential evolution without using dimension reduction techniques. سری زمانی, خوشه بندی, الگوریتم تکاملی دیفرانسیلی, روش خوشه بندی Fuzzy-Cmeans, تبدیل کسینوسی گسسته. Time Series, Clustering, Fuzzy C-Means, Differential Evolution, Discrete Cosine Transform 199 209 http://jgst.issgeac.ir/browse.php?a_code=A-10-334-1&slc_lang=fa&sid=1 Z. Izakian زاهده ایزکیان zahedeh_izakian@yahoo.com 10031947532846003333 10031947532846003333 Yes بدون سازمان Y. Amerian یزدان عامریان amerian@kntu.ac.ir 10031947532846003334 10031947532846003334 No بدون سازمان M. Mesgari Saadi محمد سعدی مسگری mesgari@kntu.ac.ir 10031947532846003335 10031947532846003335 No بدون سازمان