اندازه‌ گيري تشابه خطوط سير با استفاده از تئوري فازي

Measuring the Similarity of Trajectories Using Fuzzy Theory

با پيشرفت انواع سامانه‌هاي تعيين موقعيت، امكان دسترسي به حجم وسيعي از داده‌هاي حركتي فراهم‌شده است. ازجمله روش‌هاي كشف دانش از اين نوع داده‌ها، اندازه‌گيري تشابه خطوط سير حاصل از حركت اشيا است. همچنين اندازه‌گيري تشابه، بطور مستقيم و غيرمستقيم در ساير روش‌هاي داده‌كاوي مثل خوشه‌بندي و طبقه‌بندي كاربرد دارد و در حال حاضر به‌عنوان يك موضوع چالش‌برانگيز مورد توجه بسياري از محققان در حوضه سيستم‌هاي اطلاعات مكاني قرارگرفته است. باوجوداينكه عدم قطعيت يك مسئله اجتناب‌ناپذير است، تاكنون توجه كمي به اين موضوع در زمينه اندازه‌گيري تشابه خطوط سير شده است. يك راه مقابله با عدم قطعيت در مشاهدات و تعاريف مسئله، استفاده از تئوري فازي است. در اين تحقيق، دو روش sim1 و sim2 به ترتيب بر پايه روش‌هاي LCSS و EDR ارائه‌شده كه براي مقابله با عدم قطعيت در اندازه‌گيري تشابه خطوط سير و بهبود كارايي آن‌ها از تئوري فازي استفاده‌شده است. روش‌هاي پيشنهادي با استفاده از يك تابع عضويت فازي و بر اساس فاصله ميان نقاط دو خط سير، درجه انطباق هر دو نقطه از دو خط سير را تعيين مي‌كنند كه بر اساس آن تشابه دو خط سير تعيين مي‌شود. به‌منظور ارزيابي اين دو روش، دو سري آزمايش بر روي خطوط سير واقعي و مصنوعي خودروهاي شخصي انجام شده است. نتايج آزمايش‌ها نشان مي‌دهند كه روش‌هاي sim1 و sim2 ازلحاظ حساسيت نسبت به نويز، كاهش و افزايش نرخ نمونه‌برداري عملكردي مشابه روش‌هاي LCSS و EDR و از لحاظ حساسيت نسبت به جابجايي، عملكرد بهتري نسبت به آن‌ها دارند. به‌طوري‌كه براي مثال ميانگين درصد تغييرات تشابه نسبت به تغييرات فاصله براي چهار حد آستانه 5، 10، 25 و 50 متر براي روش LCSS برابر 0.02، 0.97، 0.66 و 0.23 است و براي روش‌هاي sim1 و sim2 برابر 0.41 درصد است.

In recent years, with the advancement of positioning systems, access to a large amount of movement data is provided. Among the methods of discovering knowledge from this type of data is to measure the similarity of trajectories resulting from the movement of objects. Similarity measurement has also been used in other data mining methods such as classification and clustering and is currently, an important and challenging topic for many researchers in the field of geospatial information systems. Although uncertainty is an inevitable issue in the field of geospatial information systems, so far little attention has been paid to this issue especially in the field of measuring the similarity of trajectories. One way to cope with the uncertainty in the observations and definitions of the problem, is to use fuzzy theory. In this study, two methods of sim1 and sim2 based on Longest Common Subsequence (LCSS) and Edit Distance on Real Sequence (EDR) methods, respectively, have been introduced to deal with uncertainty in measuring similarity of trajectories and improving their performance using fuzzy theory. The proposed methods use a fuzzy membership function based on the distance between the points of two trajectories to determine the degree of matching of every pair of points on two trajectories based on which the similarity of the two trajectories is calculated. In order to evaluate these two methods, two experiments have been performed on the real and synthetic trajectories of personal cars. Experimental results show that sim1 and sim2 are similar to LCSS and EDR in terms of sensitivity to noise, increasing and decreasing sampling rate and have better performance in terms of sensitivity to displacement. For example, the mean percentage change of similarity to distance variations for the four thresholds of 5, 10, 25, and 50 meters for LCSS is 0.02, 0.97, 0.66, and 0.23 but for sim1 and sim2 is 0.41 which is proportional to rate of changes in reference trajectory.