This paper presents a study on area change detection applications based on remote sensing data. The crucial parts of the process are in selecting the optimal combination of bands and in the image clustering process, so that we could obtain the object regions correctly. The proposed methodology consists of the following steps: (i) image band selection using Optimum Index Factor; (ii) K-Means clustering where their cluster centres are determined by K-D tree; and (iii) detecting area changes. For experiment purposes, temporal images that are registered to each other are required. The image registration is done by matching several ground control points between two or more temporal images. The experiments have used the images of Kalimantan, with the size of 512512 pixels, and are recorded in the years of 2002 and 2009. The experiments have used both random approach and K-D tree based approach for determining the initial cluster centres in the clustering process. The experimental results show that the K-D-tree based approach gave better results than the random approach in terms of the similarity measure of the clusters' members.