The Use of Spatio-Temporal Data Mining for Detection and Interpretation of Trajectory Outliers in Health Care Services

Abstract

In the last decade, useful information extraction from moving objects has become widespread in the spatial-temporal data mining field with the increasing use of devices such as RFID and GPS. For this purpose, the outlier detection method, which is a subfield of data mining, was applied to the trajectory of patients and diseases in the dental health service. In this article, TRAOD and TOD-SS algorithms combining distance and density-based methods were preferred. These algorithms do not handle the moving object trajectory as a whole unlike other outlier detection techniques. They investigate whether each piece exhibits different behavior according to its neighbors by separating trajectories into pieces. So, they detect outlying trajectory pieces that other algorithms cannot locate. Algorithms preferred in this study were used in a COMB-O model we developed and their performances were compared. In addition, according to the region and clinic, the classification of patients was made. Also, clustering, which is another branch of spatial-temporal data mining, was performed for trajectory. When the COMB-O model was executed, results showed sub-trajectories that deviated from the trajectory data were successfully detected with the help of the trajectory outlier detection algorithms. Inconsistent trajectories perceived provided significant data. In addition to this, successful classification was performed by making use of non-linear classification features of DVM. Moreover, stops and moves in the Faculty of Dentistry were detected by using CB-SMoT and DB-SMoT which are clustering algorithms.

Keywords

• Spatio-temporal veri madenciliği,hareketli cisimler,yörünge verileri,yörünge sapması algılama,destek vektör makinesi

Sağlık Hizmetlerinde Aykırı Dataların Kestirimi İçin Mekansal Zamansal Veri Madenciliğinin Kullanımı

Abstract

Son on yılda, hareketli nesnelerden yararlı bilgi çıkarma, mekansal-zamansal veri madenciliği alanında RFID ve GPS gibi cihazların kullanımının yaygınlaşması ile yaygınlaşmıştır. Bu amaçla, veri madenciliğinin bir alt alanı olan belirsizlik tespit yöntemi, diş hekimliği servisindeki hastaların ve hastalıkların gidişatına uygulanmıştır. Bu makalede, mesafe ve yoğunluk tabanlı yöntemleri birleştiren TRAOD ve TOD-SS algoritmaları tercih edilmiştir. Bu algoritmalar, diğer aykırı algılama tekniklerinden farklı olarak, hareketli nesne yörüngesini bir bütün olarak ele almaz. Her bir parçanın yörüngeleri parçalara ayırarak komşularına göre farklı davranış sergileyip sergilemediklerini araştırıyorlar. Dolayısıyla, diğer algoritmaların bulamayan yörünge parçalarını algılarlar. Bu çalışmada tercih edilen algoritmalar geliştirdiğimiz COMB-O modelinde kullanılmış ve performansları karşılaştırılmıştır. Buna ek olarak, bölgeye ve klinikte, hastaların sınıflandırması yapılmıştır. Ayrıca, mekansal-zamansal veri madenciliğinin bir başka dalı olan kümeleme, yörünge için gerçekleştirildi. COMB-O modeli yürütüldüğünde, sonuçlar yörünge verilerinden sapmış olan alt yörüngeleri yörünge aykırı değer algılama algoritmaları yardımıyla başarıyla tespit edildiğini gösterdi. Algılanan tutarsız yörüngeler önemli veriler sağlamıştır. Buna ek olarak, DVM'nin doğrusal olmayan sınıflandırma özelliklerinden faydalanarak başarılı bir sınıflandırma gerçekleştirildi. Ayrıca, kümeleme algoritmaları olan CB-SMoT ve DB-SMoT kullanılarak Diş Hekimliği Fakültesindeki durmalar ve hareketler tespit edildi.

Keywords

• Spatio-temporal data mining,moving objects,trajectory data,trajectory outlier detection,support vector machine

References

1. [1] Rao, K.V., Govardhan, A., Rao, K.V.C., “Spatiotemporal Data Mining: Issues, Tasks and Applications”, International Journal of Computer Science and Engineering Survey ( IJCSES), vol.3, issue 1, 2012, pp. 39-52.
2. [2] Geetha, R., Sumathi, N., Sathiabama, D. S., “A Survey of Spatial, Temporal and Spatio-Temporal Data Mining”, Journal of Computer Applications, vol.1 issue 4, 2008, pp. 31- 33.
3. [3] Alvares, L.O., Palma, A.T., Oliveira, G., Bogorny, V., “WEKA-STPM: From Trajectory Samples to Semantic Trajectories”, in: Proceedings of the Workshop on Open Source Code, Porto Alegre, Brazil 2010, pp. 1–6.
4. [4] Rocha, J.A., Times, V.C., Oliveira, G., Alvares, L.O., Bogorny, V., “DB-SMoT: A direction-based spatio-temporal clustering method”, IEEE Conf. of Intelligent Systems, 2010, pp. 114-119.
5. [5] Sharma, L.K., Vyas, O.P., Scheider, S., Akasapu, A., “Nearest Neighbor Classification for Trajectory Data ITC”, Springer LNCS CCIS 101, 2010, pp. 180–185.
6. [6] Almeida, V.T., and Güting, R.H., “Indexing the Trajectories of Moving Objects in Networks”, Geoinformatica, vol. 9, issue 1, 2005, pp. 33-60.
7. [7] Gogoi, P., Bhattacharyya, D., Borah, B., and Kalita, J.K., “A survey of outlier detection methods in network anomaly identification”, The Computer Journal, vol.54, issue 4, 2011, pp. 570–588.
8. [8] Kriegel, H.-P., Kroger, P., and Zimek, A., “Outlier Detection Techniques”, in: Tutorial at the 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2009.

9. [9] Ng, R.T., and Han, J., “Efficient and effective clustering methods for spatial data mining”, Proceeding of 94 VLDB, 1994, pp. 144–155.
10. [10] Ester, M., Kriegel, H-P., and Xu, X., “A database interface for clustering in large spatial databases”, in: Proceedings of 1st International Conference on Knowledge Discovery and Data Mining (KDD-95), 1995.
11. [11] Zhang, T., Ramakrishnan R., and Livny, M., “BIRCH: An efficient data clustering method for very large databases”, Proceedings of the 96 ACM SIGMOD International Conference on Management of Data, New York, NY, USA 1996, pp. 103-114.
12. [12] Guha, S., Rastogi, R., and Shim, K., “CURE: An efficient clustering algorithm for large databases”. SIGMOD Rec., vol. 27 issue 2, 1998, pp. 73–84.
13. [13] Cateni, S., Colla, V., and Vannucci, M., “Outlier Detection Methods for Industrial Application”, in: J. Aramburo, A.R. Trevino (Eds.), Advances in Robotics, Automation and Control, Austria, 2008, pp. 265-281.
14. [14] Ben-Gal. I., “Outlier Detection”, in: O. Maimon, L. Rokach (Eds.), Data Mining and Knowledge Discovery Handbook, Kluwer Academic Publisher, 2005.
15. [15] Mansur, M.O., and Noor Md. Sap, M., “Outlier Detection Technique in Data Mining: A Research Perspective”, in: Proceedings of the Postgraduate Annual Research Seminar, 2005.
16. [16] Knorr, E.M., and Ng, R., “Algorithms for Mining Distance-Based Outliers in Large Datasets”, Proceedings of VLDB, 1988, pp 392-403.
17. [17] Knorr, E.M., Ng, R.T., and Tueakov, V., “Distance-Based Outliers: Algorithms and Applications”, in: Proc. VLDB Journal, vol.8 issue 3, 2000, pp. 237-253.
18. [18] Ramaswamy, S., Rastogi R., and Shim, K., “Efficient algorithms for mining outliers from large data sets”, Proceedings of the International Conference on Management of Data, Dallas, Texas, USA, 2000.
19. [19] Breunig, M. M., Kriegel, H-P., Ng, R.T., and Sander, J., “LOF: Identifying Density-Based Local Outliers”, Proceedings of the 2000 ACMSIGMOD international conference on management of data, Dallas, Texas, United States, ACM Press New York, NY, USA, 2000, pp. 93–104.
20. [20] Papadimitriou, S., Kitawaga, H., Gibbons, P., and Faloutsos, V., “LOCI: Fast Outlier detection using the local correlation integral”, Proceedings of the International Conference on Data Engineering, 2003, pp. 315-326.
21. [21] Birant, D., and Kut, A., “Spatio-temporal Outlier Detection in Large Databases”, in: 28th International Conference on Information Technology Interfaces, 2006, pp. 179–184.
22. [22] Wu, E., Liu, W., and Chawla, S., “Spatio-Temporal Outlier Detection In Precipitation Data”, Proceedings of the Second international conference on Knowledge Discovery from Sensor Data, Las Vegas, NV,2008, pp. 115-133.
23. [23] Bogorny, V., “Spatial and Spatio-Temporal Data Mining”, Trajectory Knowledge Discovery, IEEE ICDM, Universidade Federal de Santa Catarina, 2010.
24. [24] Spaccapietra, S., Parent, C., Damiani, M.L., Macedo, J.A.F., Porto, F., and Vangenot, C., “A conceptual view on trajectories”, Data Knowl. Eng., vol. 65, issue 1, 2008, pp. 126-146.
25. [25] Lee, J., Han, J., and Li, X., “Trajectory Outlier Detection: A Partition-and-Detect Framework”, 24. Int'l Conf. on Data Engineering, 2008, pp. 140-149.
26. [26] Yuan, G., Xia, S., Zhang, L., Zhou, Y., and Ji, C., “Trajectory Outlier Detection Algorithm Based on Structural Features”, Journal of Computational Information Systems, vol.7, issue 11, 2011, pp. 4137–4144.
27. [27] Hsu, C.-W., Chang, C.-C., and Lin, C.-J., “A practical guide to support vector classification”, Tech. rep., Department of Computer Science, National Taiwan University, 2003.
28. [28] Weston, J., “Support Vector Machine”, In: Tutorial, 4 Independence Way, Princeton, USA
29. [29] Spaccapietra, S., Parent, C., Damiani, M.L., Macedo, A.D., Porto, F.,Vangenot, C., “A conceptual view on trajectories”, Data and Knowledge Engineering, vol 65, issue 1, 2008, pp. 126-146.
30. [30] Alvares, L.O., Bogorny, V., Palma, A., Kuijpers, B., Moelans, B., Macedo, J.A.F., “Towards Semantic Trajectory Knowledge Discovery”, Technical Report, Hasselt University, Belgium 2007.
31. [31] Palma A.T., and Bogorny, V., “A Clustering-Based Approach for Discovering Interesting Places in Trajectories, Master of Computer Science Thesis”, Unıversıdade Federal Do Rıo Grande Do Sul Instıtuto De Informátıca Programa De Pós-Graduação Em Computação, Porto Alegre, 2008.
32. [32] Palma, A.T., Bogorny, V., Kuijpers, B., and Alvares, L.O., “A clustering-based approach for discovering interesting places in trajectories”, in: ACMSAC, New York, NY, USA, ACM Press, 2008, pp. 863– 868.
33. [33] Rocha, J.A.M.R., Times, V.C., Oliveria, G., Alvares, L.O., Bogorny, V., “DB-SMoT: A direction-based spatio-temporal clustering method”, IEEE Conf. of Intelligent Systems, 2010, pp. 114-119.