The performance of image classification usually depends on the quality of labelled datasets to be used as training samples. In the context of remote sensing, the acquisition of ground-truth data can be a difficult and expensive task because it depends on the comprehensive surveys over the area of interest while the labelling task must be performed by experienced professionals. On the other hand, algorithms based on Active Learning can be helpful to overcome the lack of training samples. We present a cohesive algorithm for image classification and change detection based on Active Learning, that tackles the lack of ground-truth data. Afterwards, we compute the Principal Component Analysis over post-classification images to detect deforestation on the eastern side of So Paulo urban area. Our approach provides a way to automatically select data samples, while it also suggests a category. The user provides the category data (labelling task) to the selected pixels which are further used as training data in the final classification step. We applied the algorithm over four 6-channels multispectral images of the Landsat 5/TM device and we classified the pixels in two categories (forest and non-forest) for the years of 1986, 1996, 2003, and 2011. The change detection, is computed through an automatic threshold applied on the post-classification images. We were able to quantify de deforestation suffered by the eastern side of Sao Paulo city along the years. Our results show that the remaining 31% of forest in 1986 reach a minimum of 25% in 2003, but afterwards it recovered to 27% of the area in 2011.