Focal-Test-Based Spatial Decision Tree Task

A Focal-Test-Based Spatial Decision Tree Task is a Classification Tree Learning Task that uses both local and focal data.

• AKA: FTSDT Task, Spatial Decision Tree Learning Task, SDTL Task, Raster Classification Task.
• Context:
  • Task Input:
    • A spatial framework [math]\displaystyle{ S }[/math] that is a 2-D regular grid.
    • A spatial neighborhood definition N, and its maximum size [math]\displaystyle{ S_{max} }[/math]
    • Training and test samples (with features and class labels) drawn from [math]\displaystyle{ S }[/math]. Training samples must form contiguous patches of locations in [math]\displaystyle{ S }[/math].
  • output :
    • A decision tree model based on training samples.
  • Task Requirements :
    • It requires to minimize classification errors and salt-and-pepper noise.
  • Constraint(s) :
    • Spatial autocorrelation must exists in class labels.
  • It can be solved by a Focal-Test-Based Spatial Decision Tree System (that implements a Focal-Test-Based Spatial Decision Tree Algorithm).
  • It is based on k-Nearest Neighbor Task.
  • ...
• Example(s):
  • Illustrative problem example (Jiang et al., 2015)

     FTSDT.png.

• Counter-Example(s):
  • a Regression Tree Learning Task.
  • Logistic Model Learning Task.
  • SVM Learning Task.
• See: Salt-and-Pepper Noise, k-Nearest Neighbor (kNN) Algorithm, Supervised Learning Task, Classification Task, Decision Tree, Classification Rule, Spatial Data Mining, Indicator Formula, Neighborhood Relationship, Spatial Autocorrelation Statistic, Focal Function Test.

References

2017a

• (Jiang, 2017) ⇒ Zhe Jiang. (2017). "Focal-Test-Based Spatial Decision Tree". In: Encyclopedia of GIS pp 622-627
  • QUOTE: Given a raster spatial framework, as well as training and test sets, the spatial decision tree learning problem aims to find a decision tree model that minimizes classification errors as well as salt-and-pepper noise. Figure 1 shows a real-world wetland mapping problem example (from city of Chanhassen, MN). Some input features of aerial photo bands are in Fig. 1a as well as Fig. 1b and ground truth class labels (red for dryland, green for wetland) are in Fig. 1c. A decision tree model is learned from the dataset by C4.5 algorithm (Quinlan 1993), and its final classification result is shown in Fig. 1d. As can be seen, the generated decision tree has very poor classification performance with lots of salt-and-pepper noise. In contrast, the prediction of a focal-test-based spatial decision tree (Jiang et al. 2013) is shown in Fig. 1e, which has less errors and salt-and-pepper noise.

2017b

• (Jiang & Shekhar, 2017) ⇒ Jiang, Z., & Shekhar, S. (2017). Focal-Test-Based Spatial Decision Tree. In Spatial Big Data Science (pp. 77-104). Springer, Cham. DOI:10.1007/978-3-319-60195-3_5
  • ABSTRACT: This chapter introduces another spatial classification technique called focal-test-based spatial decision tree (FTSDT), in which the tree traversal direction of a sample is based on both local information and focal (neighborhood) information. We also provide comparisons of FTSDT with existing decision trees and spatial decision trees on real-world wetland mapping data.

2015

• (Jiang et al., 2015) ⇒ Jiang, Z., Shekhar, S., Zhou, X., Knight, J., & Corcoran, J. (2015). "Focal-test-based spatial decision tree learning". IEEE Transactions on Knowledge and Data Engineering, 27(6), 1547-1559. DOI: 10.1109/TKDE.2014.2373383
  • ABSTRACT: Given learning samples from a raster data set, spatial decision tree learning aims to find a decision tree classifier that minimizes classification errors as well as salt-and-pepper noise. The problem has important societal applications such as land cover classification for natural resource management. However, the problem is challenging due to the fact that learning samples show spatial autocorrelation in class labels, instead of being independently identically distributed. Related work relies on local tests (i.e., testing feature information of a location) and cannot adequately model the spatial autocorrelation effect, resulting in salt-and-pepper noise. In contrast, we recently proposed a focal-test-based spatial decision tree (FTSDT), in which the tree traversal direction of a sample is based on both local and focal (neighborhood) information. Preliminary results showed that FTSDT reduces classification errors and salt-and-pepper noise. This paper extends our recent work by introducing a new focal test approach with adaptive neighborhoods that avoids over-smoothing in wedge-shaped areas. We also conduct computational refinement on the FTSDT training algorithm by reusing focal values across candidate thresholds. Theoretical analysis shows that the refined training algorithm is correct and more scalable. Experiment results on real world data sets show that new FTSDT with adaptive neighborhoods improves classification accuracy, and that our computational refinement significantly reduces training time.

2013

• (Jiang et al., 2015) ⇒ Jiang, Z., Shekhar, S., Zhou, X., Knight, J., & Corcoran, J. (2013, December). Focal-test-based spatial decision tree learning: A summary of results. In Data Mining (ICDM), 2013 IEEE 13th International Conference on (pp. 320-329). IEEE. DOI: 10.1109/ICDM.2013.96
  • ABSTRACT: Given a raster spatial framework, as well as training and test sets, the spatial decision tree learning (SDTL) problem aims to minimize classification errors as well as salt-and-pepper noise. The SDTL problem is important due to many societal applications such as land cover classification in remote sensing. However, the SDTL problem is challenging due to the spatial autocorrelation of class labels, and the potentially exponential number of candidate trees. Related work is limited due to the use of local-test-based decision nodes, which can not adequately model spatial autocorrelation during test phase, leading to high salt-and-pepper noise. In contrast, we propose a focal-test-based spatial decision tree (FTSDT) model, where the tree traversal direction for a location is based on not only local but also focal (i.e., neighborhood) properties of the location. Experimental results on real world remote sensing datasets show that the proposed approach reduces salt-and-pepper noise and improves classification accuracy.

• Concept
• Machine Learning