DM3 - Density-based clustering Flashcards

Question 1

$k$-distance ($kdist(x)$)

Accepted Answer

The distance from point $x$ to its $k$-nearest neighbor. Used in heuristics for tuning DBSCAN parameters.

Question 2

$k$-distance Plot

Accepted Answer

A chart of the $k$-distances of all points, sorted in decreasing order of distance. Used to visually determine a suitable $\epsilon$ value for DBSCAN.

Question 3

DBSCAN Advantages

Accepted Answer

*   Does not require specifying the number of clusters.
*   Performs well with clusters of arbitrary shape.
*   Robust to outliers and can handle them by classifying them as noise.

Question 4

DBSCAN Disadvantages

Accepted Answer

*   Requires domain knowledge for MinPts and $\epsilon$ is difficult to determine.
*   Not well-suited for datasets with clusters of very different in-cluster densities.

Question 5

Density Estimation (DE)

Accepted Answer

A set of non-parametric models used to estimate an unknown probability density function in a dataset. It does not assume a fixed probability model and estimates density at each point.

Question 6

Kernel Density Estimation (KDE)

Accepted Answer

A more robust density estimation method using kernel functions to assign weights to individual points based on their neighborhood. The estimate is $\hat{f}(x) = \frac{1}{nh} \sum_{i=1}^n K\left(\frac{x - x_i}{h}\right)$.

Question 7

Kernel Function ($K(z)$)

Accepted Answer

A localized probability density function used in KDE, characterized by:
*   Non-negativity: $K(x) \ge 0$
*   Symmetry: $K(-x) = K(x)$
*   Integrates to 1: $\int K(x) dx = 1$

Question 8

Density-based Clustering

Accepted Answer

A clustering approach that defines clusters as high-density regions separated by low-density regions, departing from rigid geometrical structures. It can handle arbitrary cluster shapes.

Question 9

DBSCAN

Accepted Answer

A density-based clustering algorithm where a cluster is defined by two parameters ($\epsilon$, MinPts) that regulate the size and minimum number of points in the cluster. It identifies clusters as density-reachable points.

Question 10

DENCLUE

Accepted Answer

A density-based clustering algorithm that uses kernel functions for more flexible notions of density, detecting dense regions without explicitly specifying neighborhood size. It relies on density attractors.

Question 11

Neighborhood ($N_\epsilon(x)$)

Accepted Answer

For a point $x$, the set of points that are at a distance of at most $\epsilon$ from $x$. Formally: $N_\epsilon(x) = \{y \in D | \	ext{dist}(x, y) \le \epsilon\}$.

Question 12

Dense Neighborhood

Accepted Answer

A neighborhood that contains at least MinPts points, i.e., $|N_\epsilon(x)| \ge \	ext{MinPts}$.

Question 13

Core Object (DBSCAN)

Accepted Answer

A point $x$ whose $\epsilon$-neighborhood contains at least MinPts points. It is a central point in a dense region.

Question 14

Directly Density-Reachable

Accepted Answer

Point $y$ is directly density-reachable from $x$ (within $\epsilon$, MinPts) if $y \in N_\epsilon(x)$ and $x$ is a core object.

Question 15

Density-Reachable

Accepted Answer

Point $p$ is density-reachable from $x$ if $p$ is directly density-reachable from a point $y$ in $N_\epsilon(x)$. It is the transitive closure of directly density-reachability and is not symmetric.

Question 16

Density-Connected

Accepted Answer

Points $x$ and $y$ are density-connected if there is a point $p$ such that both $x$ and $y$ are density-reachable from $p$.

Question 17

Density-based Cluster (DBSCAN)

Accepted Answer

A non-empty subset $S \subseteq D$ of data points satisfying:
*   **Maximality:** If $x \in S$ and $y$ is density-reachable from $x$, then $y \in S$.
*   **Connectivity:** Each object in $S$ is density-connected to all other objects in $S$.

Question 18

Noise Cluster (DBSCAN)

Accepted Answer

The set of objects $N = D \setminus \{C_1, \dots, C_k\}$ that do not belong to any density-based cluster $C_i$.

Question 19

DBSCAN Algorithm Idea

Accepted Answer

Each object in a density-based cluster is density-reachable from any of its core objects, and nothing else is reachable from the core objects. This ensures maximality and connectivity.

Question 20

DBSCAN Time Complexity (Worst Case)

Accepted Answer

Without specialized spatial indexes, DBSCAN runs in $O(n^2)$ time, where $n$ is the number of data points. With tree-based support (e.g., R*-trees), it can be $O(n \log n)$.

Question 21

DBSCAN Parameter Tuning

Accepted Answer

DBSCAN requires setting $\epsilon$ and MinPts. A low $\epsilon$ or high MinPts yields many small clusters; a high $\epsilon$ might result in a single large cluster. Heuristics like the $k$-distance plot are used.

Question 22

Discrete Kernel

Accepted Answer

A simple kernel corresponding to a degenerate uniform probability density function: $K(z) = \begin{cases} 1 & 	ext{if } |z| \le \frac{1}{2} \ 0 & 	ext{otherwise} \end{cases}$. It results in a histogram-like density estimate.

Question 23

Gaussian Kernel

Accepted Answer

A popular kernel representing a Gaussian (normal) distribution centered around a point: $K(z) = \frac{1}{\sqrt{2\pi}} \exp\left(-\frac{z^2}{2}\right)$. In KDE, $h$ acts as the standard deviation.

Question 24

Multivariate Density Estimation

Accepted Answer

Extends univariate DE to $d$-dimensional data. The window $h$ becomes a hypercube with volume $h^d$. The estimate is $\hat{f}(x) = \frac{1}{nh^d} \sum_{i=1}^n K\left(\frac{x - x_i}{h}\right)$.

Question 25

Nearest Neighbor Density Estimation

Accepted Answer

Estimates density by fixing the number of points $k$ in a neighborhood and finding the volume of that region. Density at $x$ is $\hat{f}(x) = \frac{k}{n \cdot 	ext{vol}(S_d(h_x))}$, where $h_x$ is the distance to the $k$-nearest neighbor.

DM3 - Density-based 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