Classification Analysis of DNA Microarrays

LEIF E. PETERSON, PHD, is Associate Professor of Public Health, Weill Cornell Medical College, Cornell University, and is with the Center for Biostatistics, The Methodist Hospital Research Institute (Houston). He is a member of the IEEE Computational Intelligence Society, and Editor-in-Chief of the BioMed Central Source Code for Biology and Medicine.

• Preface xixAbbreviations xxiii1 Introduction 11.1 Class Discovery 21.2 Dimensional Reduction 41.3 Class Prediction 41.4 Classification Rules of Thumb 51.5 DNA Microarray Datasets Used 9References 11Part I Class Discovery 132 Crisp K-Means Cluster Analysis 152.1 Introduction 152.2 Algorithm 162.3 Implementation 182.4 Distance Metrics 202.5 Cluster Validity 242.5.1 Davies–Bouldin Index 252.5.2 Dunn’s Index 252.5.3 Intracluster Distance 262.5.4 Intercluster Distance 272.5.5 Silhouette Index 302.5.6 Hubert’s Statistic 312.5.7 Randomization Tests for Optimal Value of K 312.6 V-Fold Cross-Validation 352.7 Cluster Initialization 372.7.1 K Randomly Selected Microarrays 372.7.2 K Random Partitions 402.7.3 Prototype Splitting 412.8 Cluster Outliers 442.9 Summary 44References 453 Fuzzy K-Means Cluster Analysis 473.1 Introduction 473.2 Fuzzy K-Means Algorithm 473.3 Implementation 493.4 Summary 54References 544 Self-Organizing Maps 574.1 Introduction 574.2 Algorithm 574.2.1 Feature Transformation and Reference Vector Initialization 594.2.2 Learning 604.2.3 Conscience 614.3 Implementation 634.3.1 Feature Transformation and Reference Vector Initialization 634.3.2 Reference Vector Weight Learning 664.4 Cluster Visualization 674.4.1 Crisp K-Means Cluster Analysis 674.4.2 Adjacency Matrix Method 684.4.3 Cluster Connectivity Method 694.4.4 Hue–Saturation–Value (HSV) Color Normalization 694.5 Unified Distance Matrix (U Matrix) 714.6 Component Map 714.7 Map Quality 734.8 Nonlinear Dimension Reduction 75References 795 Unsupervised Neural Gas 815.1 Introduction 815.2 Algorithm 825.3 Implementation 825.3.1 Feature Transformation and Prototype Initialization 825.3.2 Prototype Learning 835.4 Nonlinear Dimension Reduction 855.5 Summary 87References 886 Hierarchical Cluster Analysis 916.1 Introduction 916.2 Methods 916.2.1 General Programming Methods 916.2.2 Step 1: Cluster-Analyzing Arrays as Objects with Genes as Attributes 926.2.3 Step 2: Cluster-Analyzing Genes as Objects with Arrays as Attributes 946.3 Algorithm 966.4 Implementation 966.4.1 Heatmap Color Control 966.4.2 User Choices for Clustering Arrays and Genes 976.4.3 Distance Matrices and Agglomeration Sequences 986.4.4 Drawing Dendograms and Heatmaps 104References 1057 Model-Based Clustering 1077.1 Introduction 1077.2 Algorithm 1107.3 Implementation 1117.4 Summary 116References 1178 Text Mining: Document Clustering 1198.1 Introduction 1198.2 Duo-Mining 1198.3 Streams and Documents 1208.4 Lexical Analysis 1208.4.1 Automatic Indexing 1208.4.2 Removing Stopwords 1218.5 Stemming 1218.6 Term Weighting 1218.7 Concept Vectors 1248.8 Main Terms Representing Concept Vectors 1248.9 Algorithm 1258.10 Preprocessing 1278.11 Summary 137References 1379 Text Mining: N-Gram Analysis 1399.1 Introduction 1399.2 Algorithm 1409.3 Implementation 1419.4 Summary 154References 156Part II Dimension Reduction 15910 Principal Components Analysis 16110.1 Introduction 16110.2 Multivariate Statistical Theory 16110.2.1 Matrix Definitions 16210.2.2 Principal Component Solution of R 16310.2.3 Extraction of Principal Components 16410.2.4 Varimax Orthogonal Rotation of Components 16610.2.5 Principal Component Score Coefficients 16810.2.6 Principal Component Scores 16910.3 Algorithm 17010.4 When to Use Loadings and PC Scores 17010.5 Implementation 17110.5.1 Correlation Matrix R 17110.5.2 Eigenanalysis of Correlation Matrix R 17210.5.3 Determination of Loadings and Varimax Rotation 17410.5.4 Calculating Principal Component (PC) Scores 17610.6 Rules of Thumb For PCA 18210.7 Summary 186References 18711 Nonlinear Manifold Learning 18911.1 Introduction 18911.2 Correlation-Based PCA 19011.3 Kernel PCA 19111.4 Diffusion Maps 19211.5 Laplacian Eigenmaps 19211.6 Local Linear Embedding 19311.7 Locality Preserving Projections 19411.8 Sammon Mapping 19511.9 NLML Prior to Classification Analysis 19511.10 Classification Results 19711.11 Summary 200References 203Part III Class Prediction 20512 Feature Selection 20712.1 Introduction 20712.2 Filtering versus Wrapping 20812.3 Data 20912.3.1 Numbers 20912.3.2 Responses 20912.3.3 Measurement Scales 21012.3.4 Variables 21112.4 Data Arrangement 21112.5 Filtering 21312.5.1 Continuous Features 21312.5.2 Best Rank Filters 21912.5.3 Randomization Tests 23612.5.4 Multitesting Problem 23712.5.5 Filtering Qualitative Features 24212.5.6 Multiclass Gini Diversity Index 24612.5.7 Class Comparison Techniques 24712.5.8 Generation of Nonredundant Gene List 25012.6 Selection Methods 25412.6.1 Greedy Plus Takeaway (Greedy PTA) 25412.6.2 Best Ranked Genes 25812.7 Multicollinearity 25912.8 Summary 270References 27013 Classifier Performance 27313.1 Introduction 27313.2 Input–Output, Speed, and Efficiency 27313.3 Training, Testing, and Validation 27713.4 Ensemble Classifier Fusion 28013.5 Sensitivity and Specificity 28313.6 Bias 28413.7 Variance 28513.8 Receiver–Operator Characteristic (ROC) Curves 286References 29514 Linear Regression 29714.1 Introduction 29714.2 Algorithm 29914.3 Implementation 29914.4 Cross-Validation Results 30014.5 Bootstrap Bias 30314.6 Multiclass ROC Curves 30614.7 Decision Boundaries 30814.8 Summary 310References 31015 Decision Tree Classification 31115.1 Introduction 31115.2 Features Used 31415.3 Terminal Nodes and Stopping Criteria 31515.4 Algorithm 31515.5 Implementation 31515.6 Cross-Validation Results 31815.7 Decision Boundaries 32615.8 Summary 327References 32916 Random Forests 33116.1 Introduction 33116.2 Algorithm 33316.3 Importance Scores 33416.4 Strength and Correlation 33816.5 Proximity and Supervised Clustering 34216.6 Unsupervised Clustering 34516.7 Class Outlier Detection 34816.8 Implementation 35016.9 Parameter Effects 35016.10 Summary 357References 35817 K Nearest Neighbor 36117.1 Introduction 36117.2 Algorithm 36217.3 Implementation 36317.4 Cross-Validation Results 36417.5 Bootstrap Bias 36917.6 Multiclass ROC Curves 37317.7 Decision Boundaries 37417.8 Summary 377References 37818 Naїve Bayes Classifier 37918.1 Introduction 37918.2 Algorithm 38018.3 Cross-Validation Results 38018.4 Bootstrap Bias 38418.5 Multiclass ROC Curves 38618.6 Decision Boundaries 38618.7 Summary 389References 39119 Linear Discriminant Analysis 39319.1 Introduction 39319.2 Multivariate Matrix Definitions 39419.3 Linear Discriminant Analysis 39619.3.1 Algorithm 39719.3.2 Cross-Validation Results 39719.3.3 Bootstrap Bias 40119.3.4 Multiclass ROC Curves 40219.3.5 Decision Boundaries 40319.4 Quadratic Discriminant Analysis 40319.5 Fisher’s Discriminant Analysis 40619.6 Summary 411References 41220 Learning Vector Quantization 41520.1 Introduction 41520.2 Cross-Validation Results 41720.3 Bootstrap Bias 41720.4 Multiclass ROC Curves 42620.5 Decision Boundaries 42820.6 Summary 428References 43021 Logistic Regression 43321.1 Introduction 43321.2 Binary Logistic Regression 43421.3 Polytomous Logistic Regression 43921.4 Cross-Validation Results 44321.5 Decision Boundaries 44421.6 Summary 444References 44722 Support Vector Machines 44922.1 Introduction 44922.2 Hard-Margin SVM for Linearly Separable Classes 44922.3 Kernel Mapping into Nonlinear Feature Space 45222.4 Soft-Margin SVM for Nonlinearly Separable Classes 45222.5 Gradient Ascent Soft-Margin SVM 45422.5.1 Cross-Validation Results 45522.5.2 Bootstrap Bias 45722.5.3 Multiclass ROC Curves 46522.5.4 Decision Boundaries 46522.6 Least-Squares Soft-Margin SVM 46522.6.1 Cross-Validation Results 47022.6.2 Bootstrap Bias 47722.6.3 Multiclass ROC Curves 47722.6.4 Decision Boundaries 47722.7 Summary 481References 48323 Artificial Neural Networks 48723.1 Introduction 48723.2 ANN Architecture 48823.3 Basics of ANN Training 48823.3.1 Backpropagation Learning 49323.3.2 Resilient Backpropagation (RPROP) Learning 49623.3.3 Cycles and Epochs 49623.4 ANN Training Methods 49723.4.1 Method 1: Gene Dimensional Reduction and Recursive Feature Elimination for Large Gene Lists 49723.4.2 Method 2: Gene Filtering and Selection 50223.5 Algorithm 50223.6 Batch versus Online Training 50423.7 ANN Testing 50423.8 Cross-Validation Results 50423.9 Bootstrap Bias 50623.10 Multiclass ROC Curves 50623.11 Decision Boundaries 51323.12 RPROP versus Backpropagation 51323.13 Summary 522References 52224 Kernel Regression 52524.1 Introduction 52524.2 Algorithm 52724.3 Cross-Validation Results 52724.4 Bootstrap Bias 52824.5 Multiclass ROC Curves 53624.6 Decision Boundaries 53724.7 Summary 540References 54225 Neural Adaptive Learning with Metaheuristics 54325.1 Multilayer Perceptrons 54425.2 Genetic Algorithms 54425.3 Covariance Matrix Self-Adaptation–Evolution Strategies 54925.4 Particle Swarm Optimization 55625.5 ANT Colony Optimization 56025.5.1 Classification 56025.5.2 Continuous-Function Approximation 56225.6 Summary 567References 56726 Supervised Neural Gas 57326.1 Introduction 57326.2 Algorithm 57426.3 Cross-Validation Results 57426.4 Bootstrap Bias 58226.5 Multiclass ROC Curves 58226.6 Class Decision Boundaries 58426.7 Summary 586References 58827 Mixture of Experts 59127.1 Introduction 59127.2 Algorithm 59527.3 Cross-Validation Results 59627.4 Decision Boundaries 59727.5 Summary 597References 59928 Covariance Matrix Filtering 60128.1 Introduction 60128.2 Covariance and Correlation Matrices 60128.3 Random Matrices 60228.4 Component Subtraction 60828.5 Covariance Matrix Shrinkage 61028.6 Covariance Matrix Filtering 61328.7 Summary 621References 622Appendixes 625A Probability Primer 627A.1 Choices 627A.2 Permutations 628A.3 Combinations 630A.4 Probability 632A.4.1 Addition Rule 633A.4.2 Multiplication Rule and Conditional Probabilities 634A.4.3 Multiplication Rule for Independent Events 635A.4.4 Elimination Rule (Disease Prevalence) 636A.4.5 Bayes’ Rule (Pathway Probabilities) 637B Matrix Algebra 639B.1 Vectors 639B.2 Matrices 642B.3 Sample Mean, Covariance, and Correlation 647B.4 Diagonal Matrices 648B.5 Identity Matrices 649B.6 Trace of a Matrix 650B.7 Eigenanalysis 650B.8 Symmetric Eigenvalue Problem 650B.9 Generalized Eigenvalue Problem 651B.10 Matrix Properties 652C Mathematical Functions 655C.1 Inequalities 655C.2 Laws of Exponents 655C.3 Laws of Radicals 656C.4 Absolute Value 656C.5 Logarithms 656C.6 Product and Summation Operators 657C.7 Partial Derivatives 657C.8 Likelihood Functions 658D Statistical Primitives 665D.1 Rules of Thumb 665D.2 Primitives 668References 678E Probability Distributions 679E.1 Basics of Hypothesis Testing 679E.2 Probability Functions: Source of p Values 682E.3 Normal Distribution 682E.4 Gamma Function 686E.5 Beta Function 689E.6 Pseudo-Random-Number Generation 692E.6.1 Standard Uniform Distribution 692E.6.2 Normal Distribution 693E.6.3 Lognormal Distribution 694E.6.4 Binomial Distribution 695E.6.5 Poisson Distribution 696E.6.6 Triangle Distribution 697E.6.7 Log-Triangle Distribution 698References 698F Symbols and Notation 699Index 703