AIPrimer.AI
  • 🚦AI Primer In Transportation
  • CHAPTER 1 - INTRODUCTION TO MACHINE LEARNING
    • Machine Learning in Transportation
    • What is Machine Learning?
    • Types of Machine Learning
      • Supervised Learning
      • Unsupervised Learning
      • Semi-supervised Learning
      • Reinforced Learning
    • Fundamental concepts of machine learning
      • Model Training and Testing
      • Evaluating the Model’s Prediction Accuracy
      • The Underfitting and Overfitting Problems
      • Bias-Variance Tradeoff in Overfitting
      • Model Validation Techniques
      • Hyperparameter Tuning
      • Model Regularization
      • The Curse of Ddimensionality
    • Machine Learning versus Statistics
  • CHAPTER 2 - SUPERVISED METHODS
    • Supervised Learning_Complete Draft
    • K-Nearest Neighbor (KNN) Algorithm
    • Tree-Based Methods
    • Boosting
    • Support Vector Machines (SVMs)
  • CHAPTER 3 - UNSUPERVISED LEARNING
    • Principal Component Analysis
      • How Does It Work?
      • Interpretation of PCA result
      • Applications in Transportation
    • CLUSTERING
      • K-MEANS
      • SPECTRAL CLUSTERING
      • Hierarchical Clustering
    • REFERENCE
  • CHAPTER 4 - NEURAL NETWORK
    • The Basic Paradigm: Multilayer Perceptron
    • Regression and Classification Problems with Neural Networks
    • Advanced Topologies
      • Modular Network
      • Coactive Neuro–Fuzzy Inference System
      • Recurrent Neural Networks
      • Jordan-Elman Network
      • Time-Lagged Feed-Forward Network
      • Deep Neural Networks
  • CHAPTER 5 - DEEP LEARNING
    • Convolutional Neural Networks
      • Introduction
      • Convolution Operation
      • Typical Layer Structure
      • Parameters and Hyperparameters
      • Summary of Key Features
      • Training of CNN
      • Transfer Learning
    • Recurrent Neural Networks
      • Introduction
      • Long Short-Term Memory Neural Network
      • Application in transportation
    • Recent Development
      • AlexNet, ZFNet, VggNet, and GoogLeNet
      • ResNet
      • U-Net: Full Convolutional Network
      • R-CNN, Fast R-CNN, and Faster R-CNN
      • Mask R-CNN
      • SSD and YOLO
      • RetinaNet
      • MobileNets
      • Deformable Convolution Networks
      • CenterNet
      • Exemplar Applications in Transportation
    • Reference
  • CHAPTER 6 - REINFORCEMENT LEARNING
    • Introduction
    • Reinforcement Learning Algorithms
    • Model-free v.s. Model-based Reinforcement Learning
    • Applications of Reinforcement Learning to Transportation and Traffic Engineering
    • REFERENCE
  • CHAPTER 7 - IMPLEMENTING ML AND COMPUTATIONAL REQUIREMENTS
    • Data Pipeline for Machine Learning
      • Introduction
      • Problem Definition
      • Data Ingestion
      • Data Preparation
      • Data Segregation
      • Model Training
      • Model Deployment
      • Performance Monitoring
    • Implementation Tools: The Machine Learning Ecosystem
      • Machine Learning Framework
      • Data Ingestion tools
      • Databases
      • Programming Languages
      • Visualization Tools
    • Cloud Computing
      • Types and Services
    • High-Performance Computing
      • Deployment on-premise vs on-cloud
      • Case Study: Data-driven approach for the implementation of Variable Speed Limit
      • Conclusion
  • CHAPTER 8 - RESOURCES
    • Mathematics and Statistics
    • Programming, languages, and software
    • Machine learning environments
    • Tools of the Trade
    • Online Learning Sites
    • Key Math Concepts
  • REFERENCES
  • IMPROVEMENT BACKLOG
Powered by GitBook
On this page
  1. CHAPTER 3 - UNSUPERVISED LEARNING
  2. CLUSTERING

K-MEANS

PreviousCLUSTERINGNextSPECTRAL CLUSTERING

Last updated 1 year ago

The objective of k-means clustering is to partition a dataset of n points into k groups, where each cluster i is defined by a prototype point ci which is also its centroid and every point xin belongs to the cluster with the closest prototype. In 2-D space, the result of a k-means clustering can be represented by a centroidal Voronoi tessellation, an example of which is shown in Figure 1 below.

Figure 1: Example of Centroidal Voronoi Tessellation

The k-means clustering problem is NP-hard in Euclidean space, but many heuristic algorithms are available [,]. The advantages of k-means are that the heuristic methods are easy to implement and typically converge quickly.

The disadvantages of k-means are that it is sensitive to the initial condition, requires the user to choose k, and assumes that clusters are “blob-like” and of similar size.

The standard method for k-means clustering, Lloyd’s algorithm [1], tends to converge to local minima which makes the solution dependent on the initial locations of the k prototypes. To address this problem, the k-means++ algorithm uses a weighted random sampling to choose the starting prototypes and was shown to improve the speed and accuracy of k-means.

Choosing an appropriate value of k is difficult, as a value that is either too small or too large produces some clusters that are not meaningful. Several papers have proposed methods for automatically determining k,,.

K-means is best at identifying clusters that are “blob-like” (i.e. roughly spherical) and of similar size. A well-known example where k-means performs poorly is the mouse dataset, reproduced below in Figure 2. This example contains three clusters: two small ones (the ears), and one large one (the head). Because the head is much larger than the ears and there is little separation between them, k-means will incorrectly associate many points to the ears which actually belong to the head.

Figure 2: Mouse Dataset