Similarity-Based Clustering: Recent Developments and Biomedical Applications (Lecture Notes in Computer Science, 5400)

This book is the outcome of the Dagstuhl Seminar on "Similarity-Based Clustering" held at Dagstuhl Castle, Germany, in Spring 2007. In three chapters, the three fundamental aspects of a theoretical background, the representation of data and their connection to algorithms, and particular challenging applications are considered. Topics discussed concern a theoretical investigation and foundation of prototype based learning algorithms, the development and extension of models to directions such as general data structures and the application for the domain of medicine and biology. Similarity based methods find widespread applications in diverse application domains, including biomedical problems, but also in remote sensing, geoscience or other technical domains. The presentations give a good overview about important research results in similarity-based learning, whereby the character of overview articles with references to correlated research articles makes the contributions particularly suited for a first reading concerning these topics. Front matter 1 Chapter 1 9 Statistical Mechanics of On-line Learning 9 Introduction 9 On-line Learning in Classifiers: Linearly Separable Case 11 On-line Learning in Two-Layered Networks 16 Dynamics of Prototype Based Learning 21 Summary and Outlook 28 References 28 Chapter 2 31 Some Theoretical Aspects of the Neural Gas Vector Quantizer 31 Introduction 31 The Neural Gas Vector Quantizer 32 Statistical Physics Interpretation of (Unsupervised) Vector Quantization and Neural Gas 34 Vector Quantizer by Deterministic Annealing (VQDA) 34 Neural Gas Interpretations 35 Concluding Remarks 38 References 38 Appendix 1 39 Appendix 2 40 Chapter 3 43 Immediate Reward Reinforcement Learning for Clustering and Topology Preserving Mappings 43 Introduction 43 Immediate Reward Reinforcement Learning 44 Topology Preserving Maps 46 The Gaussian Learner 46 Visualisation 47 Alternative Reward Functions 48 New Algorithm RL1 49 Second Algorithm RL2 50 Third Algorithm, RL3 51 Topology Preserving Mapping 53 Discussion 55 Stochastic Weights 56 Simulation 57 Conclusion 58 References 58 Chapter 4 60 Advances in Feature Selection with Mutual Information 60 Introduction 60 The Two Ingredients of Feature Selection 62 Feature Selection with Mutual Information 64 Mutual Information Definition 64 Mutual Information Estimation 65 Greedy Selection Procedure 66 The Problems to Solve 68 Improving the Feature Selection by MI 68 Parameter Setting in the MI Estimation 68 Stopping Criterion 71 Clustering by Rank Correlation 73 Conclusion 76 References 77 Chapter 5 78 Unleashing Pearson Correlation for Faithful Analysis of Biomedical Data 78 Introduction 78 Correlation Measures 80 Kendall's Tau [$\tau$] 80 Spearman Rank Correlation [$\rho$] 81 Extended Pearson Correlation [\mathsf{r_{\lambda}}] 81 Attribute Rating and Adaptive Correlation 84 Unsupervised Attribute Rating – Variance Analogon 84 Supervised Attribute Rating (SARDUX) 85 Vector Quantization – Neural Gas with Correlation Measure (NG-C) 86 Visualization – High-Throughput Multidimensional Scaling (HiT-MDS) 88 Analysis of Biological Data 89 Experiment Clustering 90 Principal Component Plots of Experiments and Genes 91 Unsupervised Attribute Rating 91 Supervised Attribute Rating 92 Correlation-Based Browser of Expression Patterns 92 Neural Gas Clustering 95 Discussion 96 Conclusions 97 References 97 Chapter 6 100 Median Topographic Maps for Biomedical Data Sets 100 Introduction 100 Prototype Based Clustering 102 Median Clustering 105 Fast Implementations 110 Block Summing 111 Heuristic Search 112 Median Neural Gas 114 Approximate Patch Clustering for Large Data Sets 118 Discussion 121 References 122 Chapter 7 126 Visualization of Structured Data via Generative Probabilistic Modeling 126 Introduction 126 The Generative Topographic Mapping Algorithm 128 Overview of Hidden Markov Tree Models 129 Extending the GTM to Sequences and Tree-Structured Data 131 Hidden Markov Trees as Noise Models for the GTM 131 Hidden Markov Models as a Noise Model for GTM 133 Magnification Factors 133 Experimental Results 136 Artificially Generated Sequences 136 Melodic Lines of Chorals by J.S.Bach 136 Artificially Generated Trees 138 Traffic Policeman Benchmark Tree Structured Data 140 Discussion 142 Conclusions 143 References 144 Chapter 8 146 Learning Highly Structured Manifolds: Harnessing the Power of SOMs 146 The Challenges of Learning Highly Structured Manifolds 146 Learning Manifolds with Self-Organizing Maps 148 Learning the Clusters in Highly Structured Manifolds 150 Measuring the Correctness of SOM Learning for Complicated High-Dimensional Manifolds 152 Cluster Extraction 158 Case Studies with Higly Structured Real Data Sets 163 Real Data Sets 163 Clustering of the Ocean City Multispectral Image 165 Clusterings of the RIT Synthetic Hyperspectral Image 168 Conclusions and Outlook 172 References 173 Chapter 9 177 Estimation of Boar Sperm Status Using Intracellular Density Distribution in Grey Level Images 177 Introduction 177 Obtaining Sperm Head Images 178 Image Acquisition 178 Preprocessing and Segmentation 178 Rotation and Illumination Normalization 180 Intracellular Distribution Model 182 Feature Extraction 182 Estimation of the Deviation from the Model Distribution 183 Classification and Results 185 Minimization of False Acceptance and False Rejection Errors 185 Equalization of False Rejection and False Acceptance Errors 186 Least Squares Estimation of the Fraction of Alive Cells 189 Summary 191 References 191 Chapter 10 193 HIV-1 Drug Resistance Prediction and Therapy Optimization: A Case Study for the Application of Classification and Clustering Methods 193 Introduction 194 Machine Learning Interpretation Systems 194 The EuResist Project 196 A Detour - Semi-supervised Learning 197 Preliminaries and Background 198 Problem Formulation 199 Experimental Results 200 Discussion and Conclusion 203 A Generative-Discriminative Approach 204 Summary 206 References 206 Back matter 210 Similarity-based Learning Methods Have A Great Potential As An Intuitive And ?exible Toolbox For Mining, Visualization,and Inspection Of Largedata Sets. They Combine Simple And Human-understandable Principles, Such As Distance-based Classi?cation, Prototypes, Or Hebbian Learning, With A Large Variety Of Di?erent, Problem-adapted Design Choices, Such As A Data-optimum Topology, Similarity Measure, Or Learning Mode. In Medicine, Biology, And Medical Bioinformatics, More And More Data Arise From Clinical Measurements Such As Eeg Or Fmri Studies For Monitoring Brain Activity, Mass Spectrometry Data For The Detection Of Proteins, Peptides And Composites, Or Microarray Pro?les For The Analysis Of Gene Expressions. Typically, Data Are High-dimensional, Noisy, And Very Hard To Inspect Using Classic (e. G. , Symbolic Or Linear) Methods. At The Same Time, New Technologies Ranging From The Possibility Of A Very High Resolution Of Spectra To High-throughput Screening For Microarray Data Are Rapidly Developing And Carry Thepromiseofane?cient,cheap,andautomaticgatheringoftonsofhigh-quality Data With Large Information Potential. Thus, There Is A Need For Appropriate - Chine Learning Methods Which Help To Automatically Extract And Interpret The Relevant Parts Of This Information And Which, Eventually, Help To Enable Und- Standingofbiologicalsystems,reliablediagnosisoffaults,andtherapyofdiseases Such As Cancer Based On This Information. Moreover, These Application Scenarios Pose Fundamental And Qualitatively New Challenges To The Learning Systems - Cause Of The Speci?cs Of The Data And Learning Tasks. Since These Characteristics Are Particularly Pronounced Within The Medical Domain, But Not Limited To It And Of Principled Interest, This Research Topic Opens The Way Toward Important New Directions Of Algorithmic Design And Accompanying Theory. Front Matter....Pages - Statistical Mechanics of On-line Learning....Pages 1-22 Some Theoretical Aspects of the Neural Gas Vector Quantizer....Pages 23-34 Immediate Reward Reinforcement Learning for Clustering and Topology Preserving Mappings....Pages 35-51 Advances in Feature Selection with Mutual Information....Pages 52-69 Unleashing Pearson Correlation for Faithful Analysis of Biomedical Data....Pages 70-91 Median Topographic Maps for Biomedical Data Sets....Pages 92-117 Visualization of Structured Data via Generative Probabilistic Modeling....Pages 118-137 Learning Highly Structured Manifolds: Harnessing the Power of SOMs....Pages 138-168 Estimation of Boar Sperm Status Using Intracellular Density Distribution in Grey Level Images....Pages 169-184 HIV-1 Drug Resistance Prediction and Therapy Optimization: A Case Study for the Application of Classification and Clustering Methods....Pages 185-201 Back Matter....Pages -