An Extended ID3 Decision Tree Algorithm for Spatial Data

Abstract

Ulilizing data mining tasks such as classification on spatial data is more complex than those on non-spatial data. It is because spatial data mining algorithms have to consider not only objects or interest Itself but also neighbours of the objects in order to extract useful and Interesting patterns. One or classilication algorithms namely the 103 algorithm which originally designed for a non-spatial dataset bas been Improved by other researchers in the previous work to construe! a spatial decision tree from a spatial dataset containing polygon features only. The objective of this paper is to propose a new spatial decision tree algorithm based on the ID3 algorithm for djscrete features represented in points, lines nod polygons. As in the ID3 algorithm that use information gain in the attribute seleclion, the proposed algorithm uses the spatial information gain to choose the best splitting layer from a set of explanatory layers. The new formula for spatial information gain is propost.'Cl using spatial measures for point, line and polygon features. Empirical result demonslratcs that the proposed algorithm can be used to join hvo spatial objects in constructing spatial decision trees on small spatiaJ dataset. The proposed aJgorithm has been applied to the real spatial dataset consisting of point and polygon features. The result is a spatial decision tree with 138 leaves and the accuracy is 74.72%.