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

Hierarchical Clustering

PreviousSPECTRAL CLUSTERINGNextREFERENCE

Last updated 1 year ago

Hierarchical clustering is a class of clustering methods which are applicable to most types of data. These methods can be subdivided into agglomerative (or bottom-up) and divisive (or top-down) approaches. Both approaches generate a dendrogram which shows the nested grouping of patterns and similarity levels at which groupings change. An example is shown in Figure 3.

Figure 3: Example of a Dendrogram

Agglomerative hierarchical clustering starts with each data point in its own cluster. In each step, the most similar clusters are merged. This process continues until there is only one cluster remaining. A common algorithm for agglomerative hierarchical clustering is complete-link. In this algorithm, the similarity value for two clusters is the maximum of all pairwise distances between their component points. In every step, clusters with a similarity score higher than a threshold value are merged. The threshold value is increased in each step until there is only one cluster remaining.

Divisive approaches start with all data points in a single cluster and perform splitting until a stopping criterion is met [13]. One algorithm, described in , selects the cluster with the highest squared error and splits it using bisecting k-means with an objective of maximizing the Ward’s distance, between the two parts. Another type of divisive algorithm starts by constructing a weighted graph from the data and finding a minimum spanning tree. Then, the highest weighted edge remaining in the minimum spanning tree is removed in each step to split clusters.

The advantages of hierarchical clustering is that these methods have been shown to produce clusters of higher quality and do not need predefined parameters like k in the methods described above. The outputted dendrogram is a useful representation of the structure of the data and allows the user to determine k at the end of the process by selecting the cut that is most meaningful.

The disadvantages of hierarchical clustering is that the computational cost is typically higher than other clustering methods such as k-means. The complexity is quadratic, O(N2logN) for agglomerative and O(2N) for divisive [14], which makes hierarchical clustering impractical for large datasets unless heuristics or hybrid approaches are used.