Scalable Analytics: Chapter 4

Fundamentals of Clustering in High-Dimensional Space

The Definition and Problem of Clustering

• Clustering involves taking a set of points and a notion of distance between them to group the points into a specific number of clusters.

• While clustering is straightforward in two dimensions or for small datasets, it becomes difficult in high-dimensional spaces (e.g., 10 to 10,000 dimensions).

• High-dimensional spaces exhibit unique characteristics: almost all pairs of points are located at approximately the same distance from one another.

Practical Applications of Clustering

• Wind Farm Management: Clustering is used for the optimal control of wind farms by grouping similar turbines based on operational parameters like rotor speed and power production.

• Galactic Catalogs: In astronomy, a catalog of 2 billion "sky objects" represents items by their radiation across 7 dimensions. The goal is to cluster these into distinct objects such as galaxies, quasars, or nearby stars.

Distance Measures

Similarity is defined by the type of data being analyzed:

• Vectors: Similarity is measured by the cosine distance.

• Sets: Similarity is measured by the Jaccard distance.

• Points: Similarity is measured by Euclidean distance.

K-Means Clustering

Core Principles and Euclidean Space

• k-means assumes the data exists in Euclidean space and utilizes Euclidean distance.

• Input: A dataset $D = \{x_1, \dots, x_n\}$, where each $x_i \in \mathbb{R}^d$.

• Objective: Find a set of clusters $C = \{c_1, \dots, c_k\}$ where $c_i \subseteq D$, with the intersections of clusters being empty ($\bigcap_{i=1}^k c_i = \emptyset$) and the union of clusters representing the entire dataset ($\bigcup_{i=1}^k c_i = D$).

Distance Function and Metric Properties

The distance function $d(x_i, x_j) \rightarrow \mathbb{R}^+$ must satisfy the following metric properties:

1. $d(x_i, x_j) = 0 \iff x_i = x_j$

2. Symmetry: $d(x_i, x_j) = d(x_j, x_i)$

3. Triangle Inequality: $d(x_i, x_j) \leq d(x_i, x_k) + d(x_k, x_j)$

• Common metrics used include Euclidean distance and Manhattan distance.

Optimization and Heuristics

• The k-means problem is defined as:     $\text{arg min}_{C} \sum_{i=1}^k \sum_{x_j \in C_i} \|x_j - \mu_i\|^2$

• This problem is NP-hard. It is typically solved using Lloyd's algorithm, a heuristic approach.

Determining the Value of k

• To find the optimal number of clusters, one can try different values of $k$ and observe the change in the average distance to the centroid.

• Elbow Method: The average distance falls rapidly until the "right" $k$ is reached, after which it changes little. The ideal $k$ is located at this "elbow" in the plot.

The BFR (Bradley-Fayyad-Reina) Algorithm

Extension for Big Data

• BFR is a variant of k-means designed to handle massive, disk-resident datasets.

• It assumes clusters are normally distributed around a centroid in Euclidean space.

• The algorithm operates by keeping summary statistics of groups of points rather than keeping the points themselves in memory.

Point Classification in BFR

BFR tracks three distinct sets of points:

• Discard Set (DS): Points close enough to a centroid to be summarized.

• Compression Set (CS): Groups of points that are close to each other but not close to any existing centroid.

• Retained Set (RS): Isolated points waiting to be assigned to a compression set or discarded.

Summarizing Sets of Points

For each cluster, the Discard Set is summarized by three values ($2d + 1$ values represent a cluster of any size in $d$ dimensions):

1. N: The total number of points.

2. SUM: A vector where the $i$-th component is the sum of the coordinates in the $i$-th dimension.

3. SUMSQ: A vector where the $i$-th component is the sum of the squares of the coordinates in the $i$-th dimension.

From these summary statistics, the following can be calculated:

• Centroid (Average in dimension i): $\frac{\text{SUM}_i}{N}$

• Variance in dimension i: $\frac{\text{SUMSQ}_i}{N} - \left(\frac{\text{SUM}_i}{N}\right)^2$

Algorithm Workflow

1. Initialize $K$ clusters/centroids (e.g., via random points or optimal clustering of a small sample).

2. Load a bag of points from disk.

3. Assign new points to one of the $K$ clusters if they are "sufficiently close."

4. Cluster the remaining points into new compression sets ($CS$) or add to the retained set ($RS$).

5. Attempt to merge new compression sets with existing ones if the combined variance is below a threshold.

6. Adjust cluster statistics for the new points.

7. Repeat until all points are examined; in the final round, merge all $CS$ and $RS$ points into their nearest cluster.

Mahalanobis Distance

To decide if a point is "close enough" to a cluster, BFR uses the Mahalanobis distance, which is a normalized Euclidean distance:

1. Normalize the point in each dimension: $y_i = \frac{x_i - c_i}{\sigma_i}$

2. Take the sum of the squares of the $y_i$.

3. Take the square root: $d(x, c) = \sqrt{\sum_{i=1}^d \left(\frac{x_i - c_i}{\sigma_i}\right)^2}$

• If clusters are normally distributed in $d$ dimensions, one standard deviation equals $\sqrt{d}$.

• A point is typically accepted if its Mahalanobis distance is below a threshold, such as 2 standard deviations.

The CURE (Clustering Using REpresentatives) Algorithm

Handling Arbitrary Shapes

• K-means and BFR assume clusters are normally distributed in each dimension and aligned with fixed axes. They cannot handle clusters of arbitrary shapes (e.g., concentric rings).

• CURE assumes Euclidean distance but allows for any cluster shape.

• Instead of one centroid, CURE uses a collection of representative points to represent each cluster.

CURE Two-Pass Approach

Pass 1: Initialization

1. Pick a random sample of points that fit in main memory.

2. Cluster these points hierarchically to find initial clusters.

3. Pick representative points for each cluster: select a sample of dispersed points and move them slightly toward the cluster centroid.

Pass 2: Completion

1. Rescan the entire dataset.

2. Visit each point $p$ and place it in the cluster of the closest representative point.

Dimensionality Reduction

Concepts and Goals

• Dimensionality reduction assumes data lies on or near a low d-dimensional subspace.

• Goals:

  • Discover hidden correlations or topics.

  • Remove redundant and noisy features.

  • Improve interpretation and visualization.

  • Facilitate easier storage and processing.

• Rank: The number of linearly independent rows in a matrix. Low-rank matrices allow data to be rewritten using basis vectors and new coordinates.

Singular Value Decomposition (SVD)

Definition

SVD decomposes an input data matrix $A[m \times n]$ into: $A[m \times n] = U[m \times r] \Sigma[r \times r] (V[n \times r])^T$

• U: Left singular vectors (User-to-concept similarity matrix).

• $\Sigma$: Diagonal matrix of singular values representing the "strength" of each concept. Values are positive and sorted ($\sigma_1 \geq \sigma_2 \geq \dots \geq 0$).

• V: Right singular vectors (Movie-to-concept similarity matrix).

Properties

• $U$ and $V$ are column orthonormal: $U^T U = I$ and $V^T V = I$.

• SVD always exists for any real matrix.

Practical Case Study: Movie Recommendations

• In a users-to-movies matrix, concepts (latent dimensions/factors) might represent genres like 'SciFi' or 'Romance.'

• Querying: To find users that like a movie (e.g., 'Matrix'), the query $q$ is mapped into concept space: $q_{\text{concept}} = q V$.

• This allows finding similarities between users even if they have zero common ratings, provided they share similar concept preferences.

Drawbacks and Complexity

• Drawbacks: Interpretability is difficult; concepts can be hard to define. Singular vectors are usually dense (lack of sparsity).

• Complexity: Generally $O(nm^2)$ or $O(n^2 m)$. It is implemented in packages like LINPACK, Matlab, and Mathematica.

Scalable SVD for Large Sparse Matrices

The Challenge of Tall and Skinny Matrices

• In scenarios like Twitter (user similarity) or Netflix (users vs movies), the matrix $A$ is often $m \gg n$ (e.g., $10^{13}$ rows vs $10^4$ columns).

• These matrices are sparse, with each row having at most $L$ non-zeros (e.g., $L=20$).

Naive MapReduce Approach

• One can approximate SVD by computing $A^T A = V \Sigma \Sigma^T V^T$.

• Naive computation involves all dot products:

  • Shuffle size: $O(m L^2)$.

  • Reduce-key complexity: $m$.

DIMSUM Importance Sampling

• To scale higher, importance sampling is used. A random matrix $B$ is generated such that its entries approximate the cosine similarities between columns of $A$.

• DIMSUM Mapper: For all pairs of non-zero entries $(a_{ij}, a_{ik})$ in row $r_i$, emit the product with probability:     $P = \min\left(1, \frac{\gamma}{\|c_j\| \|c_k\|}\right)$

• $\gamma$ is a parameter to modulate behavior:

  • Low $\gamma$: Preserves similar entries of $A^T A$.

  • High $\gamma$: Preserves singular values.

• DIMSUM Reducer: Approximates the expectation to output the entry $b_{jk}$.

Complexity and Guarantees

• Shuffle size: $O(n \cdot L \cdot \gamma)$.

• Reduce-key complexity: $O(n \cdot \gamma)$.

• Using Probably Approximately Correct (PAC) guarantees, $\gamma$ is chosen based on whether the goal is preserving similarities or singular values.