Full Parameter Time Complexity (FPTC): A Method to Evaluate the Running Time of Machine Learning Classifiers for Land Use/Land Cover Classification

Abstract

In emergency responses to natural disasters, actionable information provided by remote sensing images is crucial to help emergency managers become aware of the situation and assess the magnitude of the damage. Without the accurate prediction of time consumption, choosing an algorithm for land use/land cover (LULC) classification under these emergency circumstances could be blind and subjective. Here, we proposed a full parameter time complexity (FPTC) analysis and the corresponding coefficient ω to estimate the actual running time of the LULC classification without actually running the code. The FPTC of five general algorithms is derived in this article. After derivation, the FPTC of k-nearest neighbors (kNN) is F(nv + nlog2 u), the FPTC of logistic regression (LR) is F(Qm2vn), the FPTC of classification and regression tree (CART) is F((m + 1)nvlog2n), the FPTC of random forest (RF) is F(s(m + 1)nvlog2n), and the FPTC of support vector machine (SVM) is F(m2Qv (n + k)). The results show a strong linear relationship between the actual running time and FPTC [R-squared: kNN (0.991), LR (0.997), CART (0.999), RF (1.000), and SVM (0.999)], with different data size. The average root-mean-squared error between the real running time and the estimated running time is 3.34 s, which demonstrates the effectiveness of FPTC. Combining FPTC with the corresponding coefficient ω, the running time of the classification can be precisely predicted, which will help emergency managers quickly choose algorithms in response to natural disasters with available remote sensing data and limited time.

Keywords

• Algorithm running time
• full parameter time complexity (FPTC)
• land use/land cover (LULC) classification
• Sentinel-2a
• traditional time complexity (TTC)