DM4 - Hierarchical clustering Flashcards

Question 1

Hierarchical Clustering

Accepted Answer

Partitions the space in progressively smaller clusters, forming a hierarchy. Can be agglomerative (bottom-up) or divisive (top-down).

Question 2

Agglomerative Hierarchical Clustering

Accepted Answer

A bottom-up approach where individual points start as clusters and are progressively merged to form larger clusters based on a chosen distance function.

Question 3

Divisive Hierarchical Clustering

Accepted Answer

A top-down approach where all points start in one cluster and are progressively split into smaller clusters.

Question 4

Dendrogram

Accepted Answer

A tree-like visualization tool for hierarchical clustering. The root contains all points, and leaves are single-point clusters. Branch height indicates distance, and a cut-off identifies a partition.

Question 5

Single-link Distance

Accepted Answer

The distance between two clusters $C_i, C_j$ is the minimum distance between any two points from different clusters: $	ext{dist}_{	ext{sl}}(C_i, C_j) = \min_{x \in C_i, y \in C_j} 	ext{dist}(x, y)$.

Question 6

Complete-link Distance

Accepted Answer

The distance between two clusters $C_i, C_j$ is the maximum distance between any two points from different clusters: $	ext{dist}_{	ext{cl}}(C_i, C_j) = \max_{x \in C_i, y \in C_j} 	ext{dist}(x, y)$.

Question 7

Average-link Distance

Accepted Answer

The distance between two clusters $C_i, C_j$ is the average distance between all pairs of points from different clusters: $	ext{dist}_{	ext{al}}(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{x \in C_i, y \in C_j} 	ext{dist}(x, y)$.

Question 8

OPTICS (Ordering Points To Identify the Clustering Structure)

Accepted Answer

An extension of DBSCAN designed to find density-based clusters in data with varying densities, by ordering points based on reachability distance.

Question 9

Core-distance ($cdist$)

Accepted Answer

The smallest distance $\epsilon$ such that a point $x$ is a core point, i.e., its $\epsilon$-neighborhood contains at least $MinPts$ points.
Formula: $	ext{cdist}(x) = \begin{cases} 	ext{MinPts-th smallest distance } 	ext{dist}(x, y) & 	ext{if } |N_\epsilon(x)| \ge MinPts \ 	ext{undefined} & 	ext{otherwise} \end{cases}$

Question 10

Reachability-distance ($rdist$)

Accepted Answer

The distance of a point $x$ from another point $y$, defined as the maximum of $y$'s core-distance and the Euclidean distance between $x$ and $y$, for $y$ in $x$'s $\epsilon$-neighborhood.
Formula: $	ext{rdist}(x, y) = \max(	ext{cdist}(y), 	ext{dist}(x, y))$ for $y \in N_\epsilon(x)$.

Question 11

Reachability Plot

Accepted Answer

A visualization output by OPTICS that shows the reachability and core distances of all points, ordered by reachability. Low reachability indicates high-density areas, and jumps indicate cluster boundaries.

Question 12

OPTICS Advantages

Accepted Answer

*   Does not require the number of clusters in advance.
*   Robust to varying densities.
*   Computes a complete hierarchy.
*   Good visualizations (reachability plot).

Question 13

OPTICS Disadvantages

Accepted Answer

*   No backtracking, greedy splits and merges.
*   May not scale well; runtime $O(n^2)$ without indexing.

Question 14

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)

Accepted Answer

An algorithm for clustering large datasets that summarizes data into Clustering Features (CFs) and organizes them in a CF-tree before applying a standard clustering algorithm.

Question 15

Clustering Feature (CF)

Accepted Answer

A summary of a micro-cluster $C \subseteq D$, consisting of:
*   $N = |C|$: Number of points.
*   $LS = \sum_{x \in C} x$: Linear sum of points.
*   $SS = \sum_{x \in C} x^2$: Square sum of points.

Question 16

CF Additivity Theorem

Accepted Answer

An important property of CFs stating that if two clusters are merged, the CF of the new cluster is the element-wise sum of their respective CFs.

Question 17

CF-tree

Accepted Answer

A balanced tree structure (similar to a B+-tree) that stores Clustering Features (CFs) of micro-clusters hierarchically. Parameters: $B$ (max internal node entries), $L$ (max leaf node entries), $T$ (max diameter/radius of leaf node entries).

Question 18

BIRCH Phase 1

Accepted Answer

Scans the dataset to build an in-memory CF-tree, compressing individual data points into micro-clusters.

Question 19

BIRCH Phase 2 (Optional)

Accepted Answer

Condenses the CF-tree into a smaller one if desired, further reducing data size.

Question 20

BIRCH Phase 3

Accepted Answer

Applies an arbitrary clustering algorithm (e.g., k-means) to the leaf nodes (CF feature vectors) of the CF-tree.

Question 21

BIRCH Phase 4 (Optional)

Accepted Answer

Refines the clustering with more passes over the data to improve quality.

Question 22

BIRCH Advantages

Accepted Answer

*   Compression factor tunable to memory.
*   Efficient microclustering construction $O(n)$.
*   Good clustering results for large datasets.
*   Handles incremental data.

Question 23

BIRCH Disadvantages

Accepted Answer

*   Only for Euclidean vector spaces (numeric data).
*   Sensitive to data record order.
*   Multiple parameters to tune.

Question 24

Curse of Dimensionality

Accepted Answer

A phenomenon in high-dimensional data where:
*   **Sparsification**: Data points grow further apart.
*   **Incomparability**: Distances between points become less meaningful (all distances tend to be similar).

Question 25

Subspace Clustering

Accepted Answer

A technique that finds clusters in different subsets of the dimensions where the data lies, addressing the curse of dimensionality by ignoring irrelevant dimensions for specific clusters.

DM4 - Hierarchical clustering

Card Preview

Related Flashcard Sets

Classical Mechanics - Newtonian Laws & Energy Conservation

General Pharmacology - Pharmacodynamics & Pharmacokinetics

Neuroscience Fundamentals - Brain Anatomy & Neurotransmitters

Cell Biology - Cellular Structure & Function