Previous Work
Some previous work has been focused on the particular problem of automatic recognition of Alzheimer’s Disease from MRI data. For example, Klöppel et al. (2008) consider each voxel to be a feature in a feature vector, and then use a support vector machine to classify the resulting feature vectors. Cocosco et al. (2003) consider features of the image which are points in the gray matter, white matter, or CSF, and prune the resulting set of features to develop a minimum spanning tree which can be used for classification based on a clustering approach. Cuingnet et al. (2010) discuss and compare 10 different methods using a large dataset from 509 participants. As such, the study of automatic detection of Alzheimer’s Disease is well-studied. In contrast, our study of classification of Alzheimer’s Disease is used to validate a general-purpose classifier, which is then applied to level of education, and will be applied to other measures as well in the future.
Elsayed et al. (2010) have used graph-based shape representation to classify MR images using the 2D shape of the corpus callosum as it appears in a midsaggital section. Images were classified as either from a musician, or a non-musician, with up to 95% accuracy. Shape analysis was done by recursively subdividing the image into 4 quadrants to form a quad-tree, terminating a branch if the area to be subdivided was sufficiently uniform in color. These trees were then classified by a frequent sub-tree classification method.
This paper extends the idea of graph-based shape recognition into 3 dimensions. Previous 3D graph-based shape classification used particular features of an image to form a graph representing what features are contained in the image. For example, Joshi and Chang (1988) use shape features such as edges, etc. to form a graph-based representation of machined objects. Similar methods have also been used in 2D, for example, by Mauro, Diligenti, Gori, and Maggini (2003). To date, we are unaware of any work representing a 3D structure as contained herein, while recognizing the extension from 2D methods such as in Elsayed et al. (2010).
Work has also taken place regarding classifying MR images by means other than graph-based shape recognition. For example, Mitchell et al. (2004) analyze fMRI data by considering each voxel to be a feature in a feature vector. These feature vectors are classified according to what the study participant was thinking when the scan was made. Although Mitchell et al. (2004) were using fMRI data rather than structural MRI, the task is still one of classifying a shape derived from the brain according to particular criteria.
Graph Classification
This present work is partly derived from our previous graph classification techniques described in Long and Holder (2011). In both, graphs are classified by creating a feature vector using frequent substructures. In the previous work, Gaston was used to find subgraphs, which were then used to form a feature vector which was classified using a support vector machine. In this paper, Subdue (Cook & Holder, 2000) is used to find frequent subgraphs, and also a new frequent branch miner which is optimized for fast performance on trees. Classification is again by support vector machine.
Other authors had previously used the idea of graph classification by frequent subgraphs to form a feature vector. For example, Deshpande et al. (2005) used this approach to classify chemical compounds. This technique allows common machine learning algorithms to be applied to graph classification.
Besides using a feature-vector based approach, graphs can also be classified using direct comparison. For example, in Gaertner, Flach, and Wrobel (2003) a support vector machine kernel which accepts graphs as input rather than feature vectors is used to create a support vector machine which operates on graphs directly. This technique can correctly make classifications which feature vector techniques may miss, as in Long and Holder (2011), but computation of the kernel was found to be infeasible in the present work.