This paper describes a method of improving the prediction of urbanization. The four datasets used in this study were extracted using Geographical Information Systems (GIS). Each dataset contains seven independent variables related to urban development and a class label which denotes the urban areas versus the rural areas. Two classification methods Support Vector Machines (SVM) and Neural Networks (NN) were used in previous studies to perform the two-class classification task. Previous results achieved high accuracies but low sensitivity, because of the imbalanced feature of the datasets. There are several ways to deal with imbalanced data, but two sampling methods are compared in this study.
The aim of this paper is to show that class imbalance has a powerful impact on the performance of binary classification algorithms. Most machine learning algorithms provide models with better performances when trained using balanced training datasets. However, most of the real-world datasets from various domains like medical diagnosis, document classification, fraud and intrusion detection are highly imbalanced towards the positive or the minority class.
In general, classification algorithms are designed to optimize the overall accuracy performance. However, for imbalanced data, good accuracy does not mean that most examples from the minority class were correctly classified. Therefore, additional performance measures like recall, fmeasure, g-means, AUC should be included when we study imbalanced problems.
One common approach to solve the imbalance problem is
to sample the data to build an equally distributed training
dataset. Several sampling techniques were proposed and
analyzed in the literature (Van Hulse, Khoshgoftaar, and
Napolitano 2007) including random under-sampling,
random over-sampling and more intelligent sampling
techniques. A second class of methods uses meta-costs and
assigns different penalties for the misclassified instances,
depending on their true class. The problem with this type
of methods is that it is hard to come up with a good penalty
cost. The last type of methods is the algorithmic-based
approach. They tweak the classifier to accommodate
imbalanced datasets. The algorithm-based methods use
meta-learning
Real-world imbalanced datasets come from diverse
application areas like medical diagnosis, fraud detection,
intrusion detection, gene profiling, and object detection
from satellite images
SVM and NN were used before in various studies to predict
urbanization and land cover with almost similar results, but
different prediction patterns
One challenge is that in practice an ideal separating hyperplane may not exist due to a large overlap between input data points from the two classes. In order to make the algorithm flexible a noise variable εi ≥ 0 for all i = 1,…,l, is introduced in the objective function as follows: min w∈Rl ×Rl ,b∈R τ (w,ε i ) = w 2 + C ∑li=1ε i random sampling, under-sampling and Wilson’s editing. The last section presents the conclusions.
Previous research
The machine learning algorithms named support vector machines proposed by (Vapnik 1999) consist of two important steps. Firstly, the dot product of the data points in the feature space, called the kernel, is computed. Secondly, a hyperplane learning algorithm is applied to the kernel.
Let (xi, yi), i = 1,…,l, be the training set of examples. The decision yi ∈ {-1, 1} is associated with each input instance xi ∈ RN for a binary classification task. In order to find a linear separating hyperplane with good generalization abilities, for the input data points, the set of hyperplanes 〈w,x〉+b=0 is considered. The optimal hyperplane can be determined by maximizing the distance between the hyperplane and the closest input data points. The hyperplane is the solution of the following problem: (1) (2) (3) (4) when yi ( w, xi + b) ≥ 1 − ε i for all i = 1 ,…, l. By using Lagrange multipliers the previous problem can be formulated as the following convex maximization problem (Liu, An, and Huang 2006): W (α ) = ∑
il=1α i − 1 ∑il, j=1 yi y jα iα j K ( xi , x j ) when the following conditions are true, 0 ≤ α i ≤ C for all i = 1 ,…, l, and
l ∑i=1α i yi = 0 . Here the positive constant C controls the trade-off between the maximization of (3) and the training error minimization, ∑εi.
From the optimal hyperplane equation the decision function for classification can be generated. For any unknown instance x the decision will be made based on: f (x) = sign(∑ l
y α K (xi , x) + b) i=1 i i which geometrically corresponds to the distance of the unknown instance to the hyperplane.
The method described until now works well on linear problems. Function K, the kernel from (4) enables good results for nonlinear decision problems. The dot product of the initial input space is called the new higher-dimensional feature space.
K : R l × R l → R , K ( xi , x j ) = φ ( xi ),φ ( x j ) (5) A polynomial kernel, the radial basis and the sigmoid function are suitable kernels with similar behavior in terms of the resulting accuracy and they can be tuned by changing the values of the parameters. There is no good method to choose the best kernel function. The results reported in this paper were obtained by using the following radial basis function (Schölkopf and Smola 2002) as kernel. K ( xi , x j ) = exp(− xi − x j 2γ 2
The multi-layer perceptron (MLP)
The problem with the MLP methods is that they are susceptible to converge towards local minimums. MLP methods are considered as “black box”, because it is impossible to obtain snap-shots of the process.
Since the datasets considered have over a million instances we decided to investigate under-sampling (US). This sampling technique discards random instances from the majority class until the two classes are equally represented. The other sampling method used in this study is called Wilson’s editing (Barandela el al. 2004) (WE). A k-means nearest neighbor classification procedure is used with k=3 to classify each instance in the training set using all the remaining instances. Afterwards, all the instances from the majority class that were misclassified are removed.
Especially in the case of imbalanced datasets, classification accuracy alone is not the best metric to evaluate a classifier. Several other performance metrics can be used in order to get a more comprehensive picture of the classifier’s capabilities.
Recall or sensitivity is the metric that measures the
accuracy on the positive instances, It can be defined as
TruePositive / (TruePositive + FalseNegative). Specificity
measures the accuracy on the negative instances and can
be defined as TrueNegative / (TrueNegative +
FalsePositive). Both sensitivity and specificity are
incorporated in the g-means measure
Seven broad predictor variables, which aid in describing
the distribution of urbanization within the counties, were
constructed using ESRI’s ArcGIS 9.2 software package.
ArcGIS allows for modeling of a vast array of geospatial
techniques, including the cell-by-cell raster models. These
variables were chosen as they reflect large-scale factors
that influence the patterns of urbanization and general
urban trends for the region, as well as being similar to GIS
variables for urban modeling within the Midwest
Predictor variables for each county were constructed by incorporating data from their bordering Ohio counties, to simulate the influence of nearby spatial factors outside the county borders (for instance, the proximity of a nearby city center in a bordering county could potentially effect the urban development within the target county). The resultant predictor variables created at this multi-county level were then clipped down to the boundaries of the chosen county and used in the analysis.
This type of data was extracted for four counties from the
state of Ohio: Delaware, Holmes, Mahoning and Medina.
All four resulting datasets contain more than a million
instances each. Table 1 shows for each county dataset how
many instances belong to the positive class, how many
instance belong to the negative class and the ratio between
the positive and the negative instances. All datasets are
mildly imbalanced from a 2.4:1 ratio for Mahoning County
to a 12.5:1 ratio for Holmes County.
For the first set of experiments we used two classifiers, the
SVM and the Multi-Layer Perceptron (MLP). We used the
libSVM
Random stratified sampling, which maintains the ratio of positive versus negative instances in the datasets, was used to generate datasets of 10,000 instances for the parameter search and datasets of 50,000 for training sets.
A grid parameter search was performed for the SVM classifier and the values for the two parameters C and gamma are listed below in table 2. Next, both classifiers SVM and MLP were trained on the 50,000 instances datasets and the models obtained were tested using the entire datasets. The results obtained are reported in Table 3. For each dataset and for each classifier (SVM and MLP) three performance metrics are listed: accuracy, recall and g-means. The results show that even if SVM has higher accuracy for three of the datasets MLP has higher recall, so a better classification of the positive instances for three of the datasets. Recall has the largest values for the Mahoning County dataset, which also has the lowest imbalanced ratio. Looking at the low recall values for the other three datasets, we need to investigate ways to better classify the instances from the positive class. Experiments using different sampling techniques are reported in the next section.
We run experiments using RapidMiner (Mierswa et al. 2006) on the four datasets Delaware, Holmes, Mahoning and Medina as follows. For each dataset we performed 5 runs of a five-fold cross validation with the libSVM software. The rbf kernel was used. The two parameters C and gamma where changed to values previously found by running a grid parameter search. Three sampling techniques were used: random stratified sampling (RS), equal under-sampling (US) and Wilson’s editing sampling (WE). Each experiment was iterated through subsample datasets with sizes between 100 and 5000, with a step of 100.
The results are shown on two counties Holmes and Medina, due to space limitation. The Holmes County has the highest imbalanced ratio of approximately 12.5 and Medina has a 4.3 imbalanced ratio.
All four figures show that both under-sampling and Wilson’s editing sampling have a great influence on the classification performance of the SVM learner. As accuracy is not relevant in the case of imbalanced datasets we looked at recall and g-means. The Wilson’e editing worked only slightly better than the equal under-sampling, but required extensive preprocessing. The biggest difference in performance can be seen in Figure 1 with the recall for the Holmes County.
We have presented an experimental analysis performed on large imbalanced GIS extracted datasets. The goal was to find what sampling techniques improve the classification performance especially for the minority class. It is important in the case of imbalanced datasets that additional performance measures like recall and g-means are compared in addition to the usual accuracy. We concluded that both equal under-sampling and Wilson’s editing work better that just simple random stratified sampling, but there is no significant difference between the two.
Further research may investigate how other learners like Neural Networks or Decision Trees perform with undersampling and Wilson’s editing sampling. Over-sampling, cost-sensitive learning, and meta-learners are other alternatives that can be used to improve the performance for our datasets.
Liu, Y.; An A.; and Huang, X. 2006. Boosting Prediction Accuracy on Imbalanced Datasets with SVM Ensembles. Lecture Notes in Artificial Intelligence, vol. 3918: 107-118. T. 2006. YALE: Rapid Prototyping for Complex Data Mining Task. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD06).
Pijanowski, B.; Pithadia, S.; Shellito, B. A.; and Alexandridis, K. 2005. Calibrating a neural network based urban change model for two metropolitan areas of the upper Midwest of the United States. International Journal of Geographical Information Science 19 (2): 197-216.
Pijanowski, B.; Brown, D.; Shellito, B. A.; and Manik, G. 2002. Use of Neural Networks and GIS to Predict Land Use Change. Computers, Environment, and Urban Systems 26(6): 553-575.
Pijanowski, B.; Shellito, B. A.; Bauer, M. and Sawaya, K. 2001. “Using GIS, Artificial Neural Networks and Remote Sensing to Model Urban Change in the Minneapolis-St. Paul and Detroit Metropolitan Areas.” In Proceedings of the ASPRS Annual Conference, St. Louis, MO.
Schölkopf, B.; and Smola, A. 2002. Learning with Kernels. MIT Press, Cambridge Massachusetts.
Shellito, B. A.; and Lazar, A. 2005. Applying Support Vector Machines and GIS to Urban Pattern Recognition. In Papers of the Applied Geography Conferences, volume 28.
Shellito, B. A.; and Pijanowski, B. 2003. “Using Neural Nets to Model the Spatial Distribution of Seasonal Homes.” Cartography and Geographic Information Science 30 (3): 281290.