Journal of Geomatics Science and Technology

fa ارزیابی عملکرد الگوریتم های خوشه بندی در استخراج خطوط سیر مکانی متشابه Assessment of the Performance of Clustering Algorithms in the Extraction of Similar Trajectories سامانه های اطلاعات مکانی GIS پژوهشي Research <div style="text-align: justify;">در سالهای اخیر، رشد بالا و روزافزون داده‌های خطوطسیر مکانی و لزوم پردازش و استخراج اطلاعات مفید و الگوهای معنیدار از آن‌ها منجر به جلب توجه محققان بسیاری در زمینه خوشهبندی خطوطسیر مکانی-زمانی شدهاست. تاکنون توابع شباهت و الگوریتم‌های خوشهبندی مختلفی برای طبقهبندی خطوطسیر ارائه شده‌اند. گستردگی الگوریتم‌های خوشهبندی و نتایج منحصربهفرد هر یک بر لزوم توجه و بررسی نقاط ضعف و قوت آن‌ها تاکید می‌کند. در این تحقیق، الگوریتم‌های خوشهبندی در خطوطسیر مکانی که تعمیم یافته از الگوریتمهای خوشهبندی داده‌های نقطهای هستند به چهار دستهی کلی روشهای افرازی، سلسلهمراتبی، چگالی مبنا و مبتنی بر بهینهسازی تقسیم شدند و پرکاربردترین الگوریتم‌ها در هر دسته پیادهسازی و مورد ارزیابی قرار گرفتند. فرایند ارزیابی بر روی دو مجموعه داده با پیچیدگی متفاوت و در سه حالت بدون خطا، خطا با توزیع گوسین و وجود داده پرت انجام گرفته تا توانایی روش‌ها در شرایط مختلف بررسی گردد. از شاخص سیلووت و زمان محاسباتی به عنوان دو پارامتر برای مقایسه و ارزیابی استفاده شده است. با توجه به نتایج به‌دست‌آمده توجه به داده و ویژگیهای آن در انتخاب روش مناسب خوشهبندی حائز اهمیت است. با این حال در مجموع بهترین نتایج از لحاظ کیفیت خوشهبندی به ترتیب از دستههای مبتنی بر بهینهسازی، افرازی،  سلسله مراتبی و چگالی مبنا و از لحاظ سرعت محاسبات  به ترتیب دستههای چگالیمبنا، سلسلهمراتبی، افرازی و مبتنی بر بهینهسازی حاصل شده است. دسته افرازی (صرفا زیر دسته طیفی) بالاترین مقاومت در برابر داده پرت و روشهای چگالی مبنا و مبتنی بر بهینهسازی بالاترین مقاوت در برابر نویز را از خود نشان دادهاند.  </div> <div style="text-align: justify;">In recent years, the tremendous and increasing growth of spatial trajectory data and the necessity of processing and extraction of useful information and meaningful patterns have led to the fact that many researchers have been attracted to the field of spatio-temporal trajectory clustering. The process and analysis of these trajectories have resulted in the extraction of useful information which is able to respond to different challenges in real-world applications such as traffic management and control, smart transportation, surveillance, security and biological studies. Clustering is one of the most important methods for trajectory pattern extraction, their volume reduction, discovering outliers in trajectories, indexing and their simple visualization. So far, different similarity functions and clustering algorithms have been proposed for trajectory clustering. The diversity of clustering algorithms and their unique results highlights the need for paying attention to their weaknesses and strengths. Some clustering algorithms are only effective on low volume datasets. There are also some algorithms which are only able to extract clusters with convex shape, whereas some of them extract clusters of any shapes. On the other hand, several clustering functions require the determination of the initial value, such as the number of clusters by the users while some others do not need initial inputs. In addition, outlier detection is not possible in all clustering algorithms. In this study, spatial trajectories clustering algorithms that are extended from point clustering algorithms is divided into four general categories: partitioning-based clustering, hierarchical clustering, optimization-based clustering and density-based clustering. Then, the most commonly used algorithms in each category are implemented and evaluated. The evaluation process is performed on two sets of data (cross and i5) with dissimilar complexity. The effect of noise and outliers is one of the most critical parameters engaged in the performance quality of clustering functions which is considered in this study. The Silhouette index and computational time are used as two parameters for comparison and evaluation. According to obtained results, it is crucial to consider the data, its features, and also the utilized distance function in order to decide on the proper clustering method.  However, generally, the best results regarding the clustering quality are obtained from optimization-based clustering. With the integration of genetic algorithm into the K-means, all results in two cases of using both two datasets and using two different distance functions are improved. Using the genetic algorithm in K-means leads to finding the optimum location of cluster centers and dealing with the local minimum problem. It is important to note that high computational time is one of the weaknesses of optimization-based clustering. After the optimization-based clustering, regarding the clustering quality, partitioning-based, hierarchical and density-based clustering have achieved the second, third and fourth ranks respectively. With regard to the computational time, the best results are obtained from the density-based, hierarchical, partitioning-based and optimization-based clustering consecutively. Some methods such as K-means (a sub-category of partitioning-based clustering) are severely sensitive to outliers while spectral sub-category of partitioning-based clustering has a high resistance against them. Moreover, the density-based and optimization-based clustering methods have the highest tolerance against noise.  </div> خطوط سیر مکانی, خوشه‌بندی, شاخص سیلووت, زمان محاسباتی Spatio-Temporal Trajectories, Clustering, Silhouette Index, Computational Time 135 149 http://jgst.issgeac.ir/browse.php?a_code=A-10-739-1&slc_lang=fa&sid=1 A. Moayedi علی مویدی alimoayedi2013@ut.ac.ir 10031947532846007626 10031947532846007626 No بدون سازمان R. Ali Abbaspour رحیم علی عباسپور abaspour@ut.ac.ir 10031947532846007627 10031947532846007627 Yes بدون سازمان A. R. Chehreghan علیرضا چهرقان achehreghan@ut.ac.ir 10031947532846007628 10031947532846007628 No بدون سازمان