Abstract Recently data mining techniques have emerged as an important technique to detect land change by detecting the sudden change and/or gradual change in time series of vegetation index dataset. In this technique, the algorithms takes the vegetation index time series data set as input and provides a list of change scores as output and each change score corresponding to a particular location. If the change score of a location is greater than some threshold value, then that location is considered as change. In this paper, we proposed a two step process for threshold determination: first step determine the upper and lower boundary for threshold and second step find the optimal point between upper and lower boundary, for change detection algorithm. Further, by engaging this process, we determine the threshold value for both Recursive Merging Algorithm and Recursive Search Algorithm and presented a comparative study of these algorithms for detecting changes in time series data. These techniques are evaluated quantitatively using synthetic dataset, which is analogous to vegetation index time series data set. The quantitative evaluation of the algorithms shows that the Recursive Merging (RM) method performs reasonably well, but the Recursive Search Algorithm (RSA) significantly outperforms in the presence of cyclic data.

References

[1] Aach T. and Kaup A., “Bayesian Algorithms for Adaptive Change Detection in Image Sequences using Markov Random Fields,” Signal Processing: Image Communication, vol. 7, no. 2, pp. 147-160, 1995.

[2] Alcock R. and Manolopoulos Y., “Time-Series Similarity Queries Employing a Feature-Based Approach,” in Proceedings of 7th Hellenic Conference on Informatics, Ioannina, pp. 27-29, 1999.

[3] Boriah S., Kumar V., Potter C., Steinbach M., and Klooster S., “Land Cover Change Detection using Data Mining Techniques,” Technical Report, 2008.

[4] Boriah S., Kumar V., Steinbach M., Potter C., and Klooster S., “Land Cover Change Detection: A Case Study,” in Proceedings of 14th International Conference on Knowledge Discovery and Data Mining, Las Vegas, pp. 857- 865, 2008.

[5] Boriah S., Kumar V., Steinbach M., Tan P., Potter C., and Klooster S., Detecting Ecosystem Disturbances and Land Cover Change Using Data Mining, CRC Press, 2009.

[6] Boriah S., Mithal V., Garg A., Kumar V., Steinbach M., Potter C., and Klooster S., “A Comparative Study of Algorithms for Land Cover Change,” in Proceeding of the Conference on Intelligent Data Understanding, CA, pp. 175- 188, 2010.

[7] Boriah S., Time Series Change Detection: Algorithms for Land Cover Change, PhD Thesis, University of Minnesota, 2010.

[8] Chamber Y., Garg A., Mithal V., Brugere I., Lau M., Krishna V., Boriah S., Potter C., and Klooster S., “A Novel Time Series based Approach to Detect Gradual Vegetation Changes in Forests,” in Proceedings of Conference on Intelligent Data Understanding, California, pp. 248-262, 2011.

[9] Coppin P., Jonckheere I., Nackaerts K., Muys B., and Lambin E., “Digital Change Detection Methods in Ecosystem Monitoring: a Review,” International Journal of Remote Sensing, vol. 25, no. 9, pp. 1565-1596, 2004.

[10] Chen X., Karpatne A., Chamber Y., Mithal V., Lau M., Steinhaeuser K., Boriah S., Steinbach M., Kumar V., Potter C., Klooster S., Abraham T., Stanley J., and Castilla-Rubio J., “A New Data Mining Framework for Forest Fire Mapping,” in Proceedings of Conference on Intelligent Data Understanding, Boulder, pp. 104-111, 2012.

[11] Garg A., Manikonda L., Kumar S., Krishna V., Boriah S., Steinbach M., Toshnival D., Kumar V., Potter C., and Klooster S., “A Model-Free Time Series Segmentation Approach for Land Cover Change Detection,” in Proceedings of the Conference on Intelligent Data Understanding, California, pp. 144-158, 2011.

[12] Huete A. and Justice C., MODIS Vegetation Index (MOD13) Algorithm Theoretical Basis Document, the University of Arizona, 1999.

[13] Han J., Kamber M., and Pei J., Data Mining: Concepts and Techniques, Morgan Kaufmann, 2011.

[14] Jain A. and Dubes R., Algorithm for Clustering Data, Prentice Hall, 1988.

[15] Justice C., Giglio O., and Roy L., “MODIS- Derived Global Fire Products,” in Proceedings of Land Remote Sensing and Global Environmental Change, New York, pp. 661-679, 2011.

[16] Kucera J., Barbosa P., and Strobl P., “Cumulative Sum Charts-a Novel Technique for Processing Daily Time Series of Modis Data for Burnt Area Mapping in Portugal,” International Workshop on the Analysis of Multi-Temporal Remote Sensing Images, Leuven, pp. 1-6, 2007.

[17] Keogh E., Chu S., Hart D., and Pazzani M., “Segmenting Time Series: A survey and Novel Approach,” in Proceedings of Data Mining in Time Series Databases, pp. 1-21, 2003.

[18] Kumar V., Steinbach M., Tan P., Klooster S., Potter C., and Torregrosa A., “Mining Scientific Data: Discovery of Patterns in the Global Climate System,” in Proceedings of the Joint Statistical Meetings, Athens, 2001.

[19] Kasetkasem T. and Varshney P., “An Image Change Detection Algorithm based on Markov Random Field Models,” IEEE Transactions on Geoscience and Remote Sensing, vol. 40, no. 8, pp. 1815-1823, 2002.

[20] Karim S., Riadh F., Solaiman B., and Mohamed B., “Towards a Multi-Temporal Approach for Satellite Image Interpretation,” The International Arab Journal of Information Technology, vol. 5, no. 3, pp. 281-287, 2008.

[21] Lunetta R., Knight J., Ediriwickrema J., Lyon J., and Worthy L., “Land-Cover Change Detection using Multi-Temporal MODIS NDVI Data,” Remote Sensing of Environment, vol. 105, no. 2, pp. 142-154, 2006.

[22] Lucas J. and Saccucci M., “Exponentially Weighted Moving Average Control Schemes: Properties and Enhancements,” Technometrics, vol. 32, no. 1, pp. 1-12, 1990.

[23] Mithal V., Garg A., Boriah S., Steinbach M., Kumar V., Potter C., Klooster S., and Castilla- Rubio J., “Monitoring Global Forest Cover using Data Mining,” ACM Transactions on Intelligent Systems and Technology, vol. 2, no. 4, 2011.

[24] Mithal V., Garg A., Brugere I., Boriah S., Kumar V., Steinbach M., Potter C., and Klooster S., “Incorporating Natural Variation into Time Series based Land Cover Change Detection,” in 274 The International Arab Journal of Information Technology, Vol. 16, No. 2, March 2019 Proceedings of Conference on Intelligent Data Understanding, CA, pp. 45-59, 2011.

[25] Nemmour H. and Chibani Y., “Support Vector Machines for Automatic Multi-class Change Detection in Algerian Capital Using Landsat TM Imagery,” Journal of the Indian Society of Remote Sensing, vol. 38, no. 4, pp. 585-591, 2010.

[26] Page E., “Continuous Inspection Schemes,” Biometrika, vol. 41, no. 1-2, pp. 100-115, 1954.

[27] Pham D. and Chan A., “Control Chart Pattern Recognition using a New Type of Self Organizing Neural Network,” in Proceedings of the Institution of Mechanical Engineers, vol. 212, no. 1, pp. 115-127, 1998.

[28] Potter C., Genovese V., Gross P., Boriah S., Steinbach M., and Kumar V., “Revealing Land Cover Change in California With Satellite Data,” EOS, Transactions, American Geophysical Union, vol. 88, no. 26, pp. 269-276, 2007.

[29] Potter C., Tan P., Kumar V., Kucharik C., Klooster S., Genovese V., Cohen W., and Healey S., “Recent History of Large-Scale Ecosystem Disturbances in North America Derived from the AVHRR Satellite Record,” Ecosystems, vol. 8, no. 7, pp. 808-824, 2005.

[30] Panigrahi S., Verma K., and Tripathi P., “Data Mining Algorithms for Land Change Detection: A Review,” Sādhanā Journal, vol. 42, no. 12, pp. 2081-2097, 2017.

[31] Panigrahi S., Verma K., and Tripathi P., “An Efficient Approach to Detect Sudden Changes in Vegetation Index Time Series for Land Change Detection,” IETE Technical Review, vol. 33, no. 5, pp. 539-556, 2016.

[32] Roy D., Lewis P., and Justice C., “Burned Area Mapping using Multi Temporal Moderate Spatial Resolution Data–a Bi-directional Reflectance Model based Expectation Approach,” Remote Sensing of Environment, vol. 83, no. 1-2, pp. 263- 286, 2002.

[33] Synthetic Control Chart Time Series, Available: http://kdd.ics.uci.edu/databases/synthetic_control/ synthetic_control.html, Last Visited, 2018.

[34] Taylor W., “Change-point Analysis: a Powerful New Tool for Detecting Changes,” http://www.variation.com/cpa/tech/changepoint.ht ml, Last Visited, 2000.

[35] Tan P., Steinbach M., and Kumar V., Introduction to Data Mining, Addison-Wesley, 2006.

[36] US Geological Survey and NASA. Land Processes Distributed Active Archive Center (LP DAAC). Available: https://lpdaac.usgs.gov/products/modis_products_ table, Last Visited, 2018.

[37] Verbesselt J., Hyndman R., Newnham G., and Culvenor D., “Detecting Trend and Seasonal Changes in Satellite Image Time Series,” Remote Sensing of Environment, vol. 114, no. 1, pp. 106- 115, 2010. Sangram Panigrahi is currently pursuing Ph.D.program in Dept. of Computer Applications, NIT Raipur, India. His areas of research interests include data mining, NN and WSN. He has authored number of research papers in the above mentioned areas in international journals and conferences. Kesari Verma Post graduated in 1998 and got doctorate in 2007. She is currently Assistant professor in National Institute of Technology, Raipur. She has 12 year R & D and Teaching experience. She has more than 30 publications in journals and conferences. Priyanka Tripathy has received Ph.D. degree from MANIT, India, in 2009. She is currently working as Associate professor in the Dept. of Comp. Engg. and App., NITTTR, Bhopal, India. She has around 15 years of teaching and research experience. Her research interest includes web engg.,, ERP, NN & fuzzy logic, data mining and S/W engineering.