Application of support vector machine modeling and graph theory metrics for disease classification

Abstract

Disease classification is a crucial element of biomedical research. Recent studies have demonstrated that machine learning techniques, such as Support Vector Machine (SVM) modeling, produce similar or improved predictive capabilities in comparison to the traditional method of Logistic Regression. In addition, it has been found that social network metrics can provide useful predictive information for disease modeling. In this study, we combine simulated social network metrics with SVM to predict diabetes in a sample of data from the Behavioral Risk Factor Surveillance System (BRFSS). In this dataset, Logistic Regression outperformed SVM with validation data ROC index of 81.8 and 81.7 for models with and without graph metrics, respectively. SVM with a polynomial kernel had validation ROC index of 72.9 and 75.6 for models with and without graph metrics, respectively. Although this did not perform as well as Logistic Regression, the results are consistent with previous studies utilizing SVM to classify diabetes.

Keywords

Support vector machine logistic regression graph theory disease classification

1. Introduction

Disease classification is a crucial element of biomedical research. Improved disease classification models aim to provide accurate and timely prediction to allow for earlier diagnosis and implementation of preventative measures. For example, in the US, approximately 29.1 million people (9.3%) are affected by diabetes, with 1/3 unaware of their disease status, and 57 million with pre-diabetes (American Diabetes Association, 2012). Diabetes and pre-diabetes are known to increase the risk of heart disease and stroke (American Diabetes Association, 2012) but these long-term effects can be prevented with lifestyle changes and/or medical intervention (Pi-Sunyar, 2007). Early screening and predictive risk models built with simple clinical measurements (no lab tests required) are important for deployment of prevention strategies, especially in undiagnosed population (Heikes et al., 2008).

Traditionally, biomedical data is modeled using Logistic Regression, a method that relies on fitting data to a pre-determined model. Alternatively, the Support Vector Machine (SVM) algorithm is a supervised machine learning method that is a “model-free”, meaning it is a non-probabilistic classifier that, given a labeled dataset, will assign new examples to one class or another without requiring a probability distribution. In SVM each data point is represented as a n-dimensional vector and the algorithm constructs an n-1-dimensional separating hyperplane to discriminate 2 classes, with minimized penalty function for points to the maximal margin (defined by the support vectors). Non-linear functions, kernels, can also be used to transform data into multidimensional space. Previous research demonstrates that SVM has similar or improved predictive capabilities for disease classification in comparison to Logistic Regression (Yu et al., 2010).

In addition, it has been found that graph theory metrics provide useful information for the disease classification problem. Studies classifying diseases such as Alzheimer’s (Khazaee et al., 2014) and Multiple Sclerosis (Kocevar et al., 2016) combined graph theory with machine learning methods, such as SVM, for improved prediction. I have not found previous research on the application of graph theory metrics to demographic and behavioral data for the prediction of disease.

This project aims to assess the application of SVM for classification of diabetes in a sample of people in Georgia, and apply graph theory metrics as potential predictors of disease in the model. This paper includes: Section 2 description of the dataset, Section 3.1 overview of SVM application to disease classification, Section 3.2 overview of graph theory application to disease classification, Section 3.3 overview of nonlinear SVM with kernels, Section 4.1 social network simulation, Section 4.2 SVM algorithm, Section 4.3 logistic regression algorithm, Section 5 results, and Section 6 discussion.

2. Dataset details

Data from 2015 were obtained from Georgia’s Behavioral Risk Factor Surveillance System (BRFSS) (Centers for Disease Control and Prevention, 2014), landline and cellphone based survey conducted by the Centers for Disease Control and Prevention (CDC). BRFSS includes over 300 variables of various health behaviors and chronic conditions. A binary predictor variable was defined based on survey respondents reporting they had been informed by their physician they had diabetes or pre-diabetes. Variables related to survey design and unrelated to disease outcome were dropped, in addition to variables with greater than 30% missing, refused, or unknown response rate. Variables known to be redundant were also dropped to avoid unnecessary collinearity. Categorical variables with response of 9 (missing/refused) in less than 30% of observations were kept for consideration as predictors of interest with 9 as a valid response category. Once imputing missing data on continuous variables by the median, the analysis dataset included 3,465 observations with 100 potential predictors of interest. This analysis dataset has 616 observations (17.8%) classified as having diabetes or pre-diabetes. For this study, I selected potential predictor variables based on literature review and the known conceptual model (Okwechime & Roberson, 2015).

3. Literature review

3.1 SVM application to disease classification

Yu et al. (2014) used the National Health and Nutrition Examination Survey (NHANES), an ongoing, cross-sectional, probability sample of US population, to build SVM and Logistic Regression classification models for 2 classification schemes: persons with diabetes (diagnosed or undiagnosed) vs. persons without diabetes, and persons with undiagnosed diabetes or pre-diabetes vs. persons without diabetes. They used 14 potential predictors commonly associated with diabetes: family history, age, gender, race and ethnicity, weight, height, waist circumference, BMI, hypertension, physical activity, smoking, alcohol use, education, household income (Yu, 2014). They found that the Radial Basis Function (RBF) kernel, and Linear kernel worked best for classification schemes I and II respectively, and there was no significant difference between Logistic Regression and SVM performance (validation AUC 0.83 & 0.73 for classification I and II, respectively, with both models) (Yu et al., 2014).

Additionally, Kumari and Chitra (2013) also found success with the SVM model for classification of diabetes in the Pima India Diabetic Dataset from the UCI Machine Learning Laboratory. In this case, an 8 predictor SVM model, including lab data (plasma glucose concentration, 2-hr serum insulin) was validated with 78% accuracy using the RBF kernel.

SVM has been used across diverse biomedical classification problems. This includes a patient financial risk model using health claims and clinical encounter data, and a patient response to flu awareness campaign model, both using weighted SVM (Razzaghi et al., 2016). A project comparing various machine learning techniques with Logistic Regression for prediction of heart disease also shows no significant difference between Logistic Regression and SVM, with the Linear kernel performing best (Khanna et al., 2015).

3.2 Graph theory application to disease classification

In Kocevar et al. (2016) they combined graph metrics with SVM to classify various Multiple Sclerosis (MS) clinical profiles. Cortical and sub-cortical gray matter (GM) segmentation was performed on the advanced MRI imaging of 77 MS patients and 26 healthy controls (HC). The MRI scans are segmented to create nodes, and anatomically constrained probabilistic streamline tractography is used to create edges between the segments. Edge weights are determined by a function of the number of fibers connecting the segments. The weakest connections are removed by applying a threshold 0 $\leqslant\tau\leqslant$ 1 on the weighted graph, generating an unweighted graph maintaining the $\tau$ % strongest connections in the network. Global network metrics calculated for the study on the unweighted graph included: graph density (D), assortativity (r), transitivity (T), global efficiency (Eg), modularity (Q), and characteristic path length (CPL).

The study found that global graph metrics were not significantly dependent on patients’s age or gender. Overall, significant difference in graph metrics were found when comparing MS patients with HC groups, as well as between different clinical classifications of MS. SVM classification with RBF kernel was then used to predict varying binary classifications of HC groups and clinical courses, with highest classification achieved using all graph metrics as a feature vector in the model at 91.8%. Using only one graph metric, the best in this case being modularity, the study could achieve validation accuracy of 88.9%.

In Khazaee et al. (2014), they found that using changes in brain connections from functional magnetic resonance imaging (MRI) provided strong predictive measures for classifying Alzheimer’s Disease (AD) patients from healthy controls (HC). Twenty patients with AD and 20 age-matched HC from Alzheimer’s disease neuroimaging initiative (ADNI) database were selected for study. MRI images were parcellated into 90 regions and edges were defined as connectivity of all pairs of regions using Pearson’s correlation coefficient. As in the previous study, thresholding was used to maintain the strongest connections in the network. Preserving a high proportion of the network results in a dense graph with noisy and less significant edges maintained. However, removing too many edges can result in a disconnected graph where global graph metrics cannot be calculated. From their previous research, this study found that a threshold of 12% was optimal (Khazaee et al., 2014). The study maintained the bridge edges between any disconnected sections that resulted from thresholding, regardless of the edge weight.

Graph metrics calculated for this project included: functional segregation via clustering coefficient, local efficiency, and normalized local efficiency to measure specialized processing within densely interconnected groups of regions; functional integration via characteristic path length and global efficiency to assess ability of the brain to rapidly combine specialized information from distributed regions; and 3 local measures including degree, participation coefficient, and betweenness centrality to measure properties of the 90 regions. An iterative feature selection algorithm using 7 different methods was then used to filter the most effective graph features for the classification problem. Linear SVM with a tuned C parameter using leave-one-out cross validation was used to perform the final feature classification.

End results found that Fisher Score provided the best feature selection method for the discriminative algorithm. The best algorithm found could classify AD patients from HC group with a highest validation accuracy of 97.5%.

3.3 Nonlinear SVM with kernels

It was found in (Zhang, 2007) that, in addition to the widely used SVM kernel functions for mapping the feature space (linear, rbf, polynomial), a tuned kernel function using combinations of the common functions, or a kernel designed for feature selection can provide improved model results. For feature selection, recursion methods can be used to repeatedly eliminate predictors that rank last in model performance until optimization is achieved.

For this study, feature selection was completed using SAS ${}^{\@setsize{\scriptsize}{8pt}{\viipt}{\@viipt}\textregistered}$ PROC VARCLUS, a procedure closely related to Principal Component Analysis that will find groups of variables that are as correlated as possible within groups, but as uncorrelated as possible across groups (Nelson, 2001). This has the added benefit of reducing redundancy and collinearity.

To build the custom kernel based on feature selection, a dot product matrix was created to select the top 5 features based on conceptual knowledge, variable clustering, and performance in a stepwise selection logistic model. Features selected included: age, cholesterol, race, education, and sex.

4. Methods

Python Scikit-learn package was used to build the SVM models. Grid search and 5-fold cross validation was used to determine best kernel and parameters based on smallest mean square error. The data were split into 80% training, 20% validation datasets. Grid search compared the common kernels: Linear, Polynomial, and RBF, with the custom kernel based on feature selection with 5-fold cross validation for each kernel to determine the best parameters, C, gamma, and degree. The grid search assessed penalty parameter C values 0.001, 0.01, 0.1, 1, 10 for all kernels, gamma values 0.001, 0.01, 0.1, 1 for RBF kernel, and degrees 2 and 3 for the polynomial kernel. This controls for overfitting of the model by specifying allowable misclassification. SAS ${}^{\@setsize{\scriptsize}{8pt}{\viipt}{\@viipt}\textregistered}$ PROC LOGISTIC was used to build the Logistic Regression model for comparison. The models were compared based on sensitivity, specificity, and area under the receiver operating characteristic (ROC) curve.

4.1 Social network simulation

To test the application of graph theory metrics as potential predictors in a classification model, it was necessary to simulate a social network within the BRFSS dataset. The Watts-Strogatz small world network model was selected to represent the sample social network for this application due to its ability to simulate the interconnected groups (clusters) that exist in real-world networks, as well as the existence of random irregular connectivity patterns (Prettejohn et al., 2011). This model was first introduced by Duncan Watts and Steven Strogratz in Nature in 1998 (Liu et al., 2015).

Watts-Strogatz is a variation of the lattice network where nodes are connected to their nearest neighbors only. Watts-Strogatz randomly rewires some of the lattice edges, resulting in high clustering and short paths. This network is undirected. Ideally, the data studied would include some network characteristics, but I did not have access to a public use dataset that includes both demographic and network characteristics. For the purposes of testing the application of graph metrics to a predictive model, a simulated network will suffice. To incorporate an element of the demographic data into the social network simulation, I weighted each edge by the average standardized number of adults in the respondents household, assuming that a respondent with more household members would have more social network connections.

The algorithm for creating a Watts-Strogatz network starts with a lattice network where each node is adjacent to a defined $L$ neighbors. If each node has degree $k_{L}$ , and $k_{L}$ is even, then the global clustering coefficient, $C$ , of the network is

$\displaystyle C=0.75(k_{L}-2)/(k_{L}-1)$ (1)

To randomly rewire the lattice network, each edge has a defined probability, $p_{w}$ , of being re-wired. Each edge can only have one end re-wired and the edges are replaced so that total number of edges and mean degree is the same as the original lattice (Prettejohn et al., 2011). The reason why the Watts-Strogatz model maintains high clustering coefficient, but low average path length, as compared with a random network, is that the global clustering coefficient is based on the average of the local measure; rewiring a small number of connections will only affect the local clustering coefficient of a small number of nodes. However, average path length is a global measure of the average of shortest path length between every combination of nodes. Changing even one edge can create shortcuts between many pairs of nodes, greatly affecting the average path length (Prettejohn et al., 2011). In addition, even if we select a rewiring probability of 1, a Watt-Strogatz network will not be the same as a random network with same size and average degree because the Watts-Strogatz algorithm does not allow nodes to have degree less than n/2, where the random network does allow this (Prettejohn et al., 2011). Figure 1 shows the simulated BRFSS network for 10% of the data.

Figure 1.

Watts-Strogatz simulated network

The R igraph package was used to create the Watts-Strogatz network using 1284 nodes, $k_{L}=$ 4 (degree of every node in the initial lattice), and rewiring probability $p_{w}$ 0.5. The resulting edge-list was imported into SAS ${}^{\@setsize{\scriptsize}{8pt}{\viipt}{\@viipt}\textregistered}$ and merged with the household variable in the analysis dataset to create the edge weights as described above. SAS ${}^{\@setsize{\scriptsize}{8pt}{\viipt}{\@viipt}\textregistered}$ PROC OPTGRAPH was used to calculate various graph characteristics to be used in the SVM and Logistic Regression model application, including: local clustering coefficient, degree centrality, closeness centrality, betweenness centrality, and eigenvector centrality.

4.2 Support vector machine

SVM is a supervised learning algorithm that represents instances of data as points in space and then builds a model to assign new instances to one category or another. Each data point is represented as a $n$ -dimensional vector, then SVM constructs an $n-1$ -dimensional separating hyperplane to discriminate 2 classes, with maximized distance between the hyperplane and data points on each side. SVM aims to find the best hyperplane for separation of both classes (Khanna et al., 2015).

Data are represented as

$\displaystyle(\vec{x}_{1},y_{1}),\ldots(\vec{x}_{n},y_{n})$ (2)

where $y_{i}$ is either 1 or $-$ 1, indicating to which class $x_{i}$ belongs. Each $x_{i}$ is $p$ -dimensional vector representing all of the characteristic values (variables) of $x_{i}$ . The hyperplane that best separates the group of $x_{i}$ vectors where $y_{i}=1$ from the group of vectors where $yi=-1$ is

$\displaystyle\vec{w}\bm{\cdot}\vec{x}-b=0$ (3)

Where $\vec{w}$ is the normal vector to the hyperplane and $b$ is the offset of the hyperplane from the origin. If the data points are linearly separable, the hard margin can be represented as

$\displaystyle\vec{w}\bm{\cdot}\vec{x}-b=1$ (4)

and

$\displaystyle\vec{w}\bm{\cdot}\vec{x}-b=-1$ (5)

Figure 2 shows a maximum margin separation for linearly separable data. The samples that fall on the margin are known as the support vectors.

Figure 2.

Maximum margin hyperplane (Kumari et al., 2013).

For data that is not linearly separable we can include a hinge loss function, ‘C’ to determine the trade-off between increasing the margin and whether an instance of $x i$ lies on the correct side of the margin. In addition, we can implement kernel functions to adjust the inner dot product of the maximum margin hyperplane optimization algorithm. This transforms the data into a higher dimensional space. Figure 3 shows the transformation of features into higher dimension space.

Figure 3.

Kernel transformation of feature space (Khanna et al., 2015).

The most common kernel functions include:

•

Linear Kernel

$\displaystyle K(x,z)=[x,z]$ (6)

•

Polynomial Kernel

$\displaystyle K(x,z)=([x,z]+c)^{d}$ (7)

•

RBF (Gaussian) Kernel

$\displaystyle K(x,z)=exp(-\sigma||x-z||)^{2})$ (8)

For example, polynomial kernel with degree 2 and offset $c=$ 1 in a 2-dimensional space would be:

$\displaystyle K(x,z)=[(x_{1}z_{1}+x_{2}z_{2})+1]^{2}$ (9)

And would map to:

$\displaystyle\phi(x)=(x_{1}^{2},\sqrt{2x_{1}}x_{2},x_{2}^{2},\sqrt{2x_{1}},% \sqrt{2x_{2}},1)$ (10)

Thus, mapping the features from $R^{2}$ to $R^{6}$ (Zhang, 2007). When fitting the SVM models it is required to tune several parameters including: C in all models, “gamma” as $\sigma$ in the RBF kernel, and “degree” and “coef” as d and c in the polynomial kernel. New observations are scored based on the signed distance to the decision boundary in the trained model: a positive score belongs in one class while a negative score belongs in the other class. In SAS ${}^{\@setsize{\scriptsize}{8pt}{\viipt}{\@viipt}\textregistered}$ , a score card is created for each class of the target variable. A new observation is then scored on each model and assigned a probability for each class. An observation will likely have probability less than 0.5 if it falls on the negative side of the dividing hyperplane, and a probability greater than 0.5 if it falls on the positive side. The observation is assigned to the target class with the highest probability.

4.3 Logistic regression

Logistic Regression examines the non-linear relationship between a binary outcome and categorical or continuous predictor variables. The logistic model outputs a probability of an event between 0 and 1 as the log of the odds ratio:

$\displaystyle Ln\left(\frac{P}{1-P}\right)=\beta_{0}+\beta_{1}X_{1}+\beta_{2}X% _{2}+\ldots+\beta_{n}X_{n}$ (11)

where $\beta$ is the parameter coefficient and X is the value of the independent variable.

SAS ${}^{\@setsize{\scriptsize}{8pt}{\viipt}{\@viipt}\textregistered}$ PROC LOGISTIC was used to build the model and stepwise elimination with $\alpha=$ 0.05, based on t-statistics of each parameter at each step of the model, was used to eliminate redundancy and keep the strongest predictors in the model. Holdout validation dataset was used to score new observations and assess accuracy. New observations are scored based on fitting them to the determined model and calculating the probability of the event, in this case, the probability of a new observation having diabetes. An advantage of probabilities associated with each observation is that you can apply performance metrics, such as specificity and sensitivity, to get a probability cutoff value for event classification that is tailored to the specific application. For example, if the research goal is to capture as many diabetes cases as possible, we may choose a cutoff value that results in the highest sensitivity (true positive rate), although this will come at the expense of specificity (true negative rate).

5. Results

Table 1 illustrates the significant effects remaining in the logistic regression models, for models with and without network characteristic metrics included. Age, BMI, hypertension, and cholesterol all have increased odds of diabetes outcome, while education has decreased odds. This is consistent with outcomes of previous research and known risk factors for diabetes. In the model with graph metrics included, only closeness centrality remains as significant, in addition to the same demographic variables from the previous model. If this were a real network in the dataset (not simulated), this would indicate that people with shorter total paths to other people in the network would have increased risk of diabetes.

Table 1
Odds ratio estimates and wald confidence intervals

Effect	No network characteristics		Including network characteristics
	Estimate	95% CI	Estimate	95% CI
Age	1.62	(1.26,2.09)	1.55	(1.20,1.99)
Education	0.58	(0.47,0.71)	0.57	(0.46,0.68)
BMI	3.77	(1.96,7.22)	3.74	(1.95,7.19)
Hypertension	3.32	(2.08,5.30)	3.40	(2.12,5.44)
Cholesterol	3.48	(2.24,5.40)	3.37	(2.16,5.24)
Closeness centrality	–	–	1.39	(1.11,1.73)

Table 2

Comparison of logistic regression and SVM results for data with and without simulated graph metrics

Model	Graph metrics	Kernel	Best C	Sensitivity	Specificity	Roc index (test)
Logistic	NO	NA	NA	34.2	97.7	81.7
Logistic	YES	NA	NA	36.8	97.2	81.8
SVM	NO	LINEAR	0.2	0	100	80.4
SVM	YES	LINEAR	0.5	0	100	78.9
SVM	NO	POLY	0.2	26.3	96.4	75.6
SVM	YES	POLY	0.2	23.7	97.3	72.9
SVM	NO	RBF	1	0	100	70.9
SVM	YES	RBF	0.2	0	100	71.1

Table 2 shows the model performance results for models with and without the social network graph characteristics. The models were evaluated based on the sensitivity, specificity, and ROC index for the validation data set. The logistic model performs best for models with and without graph metrics included, and the SVM model with polynomial kernel is comparable but the ROC index is affected by lower sensitivity. Figure 4 provides a visual comparison of the area under the ROC curves for models including graph metrics. The ROC curves for models without the graph metrics are the same and are not included to avoid redundancy.

Figure 4.

Comparison of ROC curves: Models including graph metrics.

6. Discussion

Support Vector Machines are important tools to be considered for disease classification problems. While SVM did not perform as well as Logistic Regression in this study, its results were comparable to previous research. SVM is known to be less sensitive to high dimensionality, and sparse datasets, so would likely perform better than Logistic Regression in studies with biomedical data of that nature, particularly much larger datasets. This is a comparatively small dataset for use in machine learning algorithms. Including graph metrics in the model did improve predictive performance slightly using a simulated network. Ideally, future research will include a dataset with both demographic and network characteristics included. Program codes are available upon request.

Future improvements to this study will include:

•

Parameter selection using machine learning such as Random Forest.

•

Multiple imputation of missing values for features of interest.

•

Creating a custom kernel for SVM using deep learning techniques, neural network.

Footnotes

Acknowledgments

I would like to thank Dr. Erik Westlund for his encouragement to pursue applied graph theory methods for this project.

References

American Diabetes Association. 2012 [http://www.diabetes.org/].

Centers for Disease Control and Prevention. (2014). Behavioral risk factor surveillance system survey data. Atlanta, GA: US Department of Health and Human Services, Centers for Disease Control and Prevention.

Heikes,

K. E.

Eddy,

D. M.

Arondekar,

, & Schlessinger,

(2008). Diabetes Risk Calculator: a simple tool for detecting undiagnosed diabetes and pre-diabetes. Diabetes Care, 31(5), 1040-1045.

Khanna,

Sahu,

Baths,

, & Deshpande,

(2015). Comparative Study of Classification Techniques (SVM, Logistic Regression and Neural Networks) to Predict the Prevalence of Heart Disease. International Journal of Machine Learning and Computing, 5(5), 414.

Khazaee,

Ebrahimzadeh,

, & Babajani-Feremi,

(2014, November). Automatic classification of Alzheimer’s disease with resting-state fMRI and graph theory. In Biomedical Engineering (ICBME), 2014 21th Iranian Conference on (pp. 252-257). IEEE. Chicago

Kocevar,

Stamile,

Hannoun,

Cotton,

Vukusic,

Durand-Dubief,

, & Sappey-Marinier,

(2016). Graph theory-based brain connectivity for automatic classification of multiple sclerosis clinical courses. Frontiers in Neuroscience, 10, 478.

Kumari,

V. A.

, & Chitra,

(2013). Classification of diabetes disease using support vector machine. International Journal of Engineering Research and Applications, 3(2), 1797-1801.

Nelson,

“Variable Reduction for Modeling using PROC VARCLUS”, Statistics, Data Analysis, and Data Mining (SUGI 26), paper 261-26.

Liu,

Beus,

Madler,

, & Bush,

(2015). “Analysis of Watts-Strogatz Networks”, Arizona State University.

10.

Okwechime,

I. O.

, & Roberson,

(2015). Prevalence and predictors of pre-diabetes and diabetes among adults 18 years or older in Florida: A multinomial logistic modeling approach. PloS One, 10(12), e0145781.

11.

Pi-Sunyer,

F. X.

(2007). How effective are lifestyle changes in the prevention of type 2 diabetes mellitus? Nutrition Reviews, 65(3), 101-110.

12.

Prettejohn,

B. J.

Berryman,

M. J.

, & McDonnell,

M. D.

(2011). Methods for generating complex networks with selected structural properties for simulations: a review and tutorial for neuroscientists. Frontiers in Computational Neuroscience, 5, 11.

13.

Razzaghi,

Roderick,

Safro,

, & Marko,

(2016). Multilevel weighted support vector machine for classification on healthcare data with missing values. PloS One, 11(5), e0155119.

14.

Yu,