Document clustering

Use case

  • Standing queries (monitor collection of documents)
  • Search result clustering
    • e.g., Wikipedia disambiguation
    • Cluster search results
    • Advantage: Effective presentation to the user
  • Scatter-gather
    • Cluster complete collection
    • Search without typing
    • User selects set of clusters which are merged and clustered again
  • Collection clustering
    • Cluster complete collection
    • Static hierarchical clustering
    • Advantage: Exploratory browsing
  • Language modeling
    • Cluster collection
    • Goal: Extend result lists by adding similar documents
    • Advantage: Increased effectiveness
  • Cluster-based retrieval
    • Pruning
    • Advantage: Increase efficiency (speed-up)
    • Cluster complete collection
    • Retrieve clusters by comparing the query to cluster centroids
    • Merge clusters and compute similarity for each documents

Cluster Hypothesis

  • Closely associated/similar documents are relevant to the same requests
  • Observation:
    • Real-world collections have clear cluster structure
  • Experimental validation
    • Hypothesis is highly collection-specific
  • Dependencies
    • Document representation
    • Similarity measure
    • Queries

Problem statement

  • Documents \( D=\{d_1,...,d_n\} \)
  • Cardinality \( k \)
  • Objective function \( f \)
  • Goal: Find \( \gamma : D\rightarrow \{1,...,k\} \) while maximizing/minimizing \( f \)

Criteria

  • Internal structural criteria
    • Primary goals:
      • Low inter-cluster similarity
      • High intra-cluster similarity
    • Secondary goals:
      • No very small clusters
      • No very large clusters
  • External criteria
    • Compare to hand-crafted reference clustering
    • Metric: Rand index
      • Percentage of correct classified pairs
      • \( RI = \frac{TP+TN}{TP+FP+TN+FN} \)

Issues

  • Cardinality \( k \)
    • Often good guess
  • Flat or hierarchical
    • Flat: No relation between clusters
    • Hierarchical: Clusters are split up into more clusters
  • Hard or soft
    • Hard: Object assigned to exactly one cluster
    • Soft: Object assigned to multiple clusters (i.e., distribution of clusters, e.g., LSI)
  • Clustering quality
    • Usual quality measure: Distance/cosine similarity
  • Computation of clusters
    • Naive: Try all clusters (impossible)
    • Number of possible flat hard clusters: Stirling number of the second kind

Flat clustering (K-means)

  • Most important flat hard clustering algorithm: K-means
  • Use defined \( k \)
    • e.g., \( k = \arg \min_{k} RSS_{min}(A_1,...,A_k)+\lambda k \)
  • Documents: Unit vectors
  • Objective:
    • Minimize average squared distance to cluster centers
    • Minimize variance of clusters from centroid
    • $J=\sum_{i=1}^k \sum_{j=1}^{|A_i|} ||d_j - \mu(A_i)||^2
  • Member of the class of partitional clustering algorithms

Metrics

  • Centroid of a cluster \( A \)
    • \( \mu(A) = \frac{1}{|A|} \sum_{i=1}^{|A|} d_i \)
  • Residual sum of squares
    • \( RSS(A) = \sum_{i=1}^{|A|} ||d_i - \mu(A) ||^2 \)
  • Clustering quality
    • \( RSS(A_1,...,A_k) = \sum_{i=1}^k RSS(A_i) \)

Lloyd’s algorithm

  1. Select \( k \) documents randomly as seeds
  2. Create \( k \) empty clusters with seeds
  3. Compute centroids of clusters
  4. Iterate over collection: Assign document to nearest cluster
  5. Recompute cluster centroids
  6. Check cluster quality (stop if good enough)
    • Small change in cluster centroids
    • Maximum number of iterations
    • Threshold for RSS

Extensions

  • K-medoids (use nearest document as centroid)
  • Fuzzy c-means (soft k-means)
  • Model-based clustering (find maximum likelihood for generated source points)

Hierarchical clustering

  • Approaches
    • Hierarchical agglomerative (HAC)
    • Hierarchical divisive

Agglomerative clustering

  • Bottom-up
  • Start with documents as clusters and merge
  • Assumption of monotony:
    • \( s_1,...,s_{k-1} \) cluster similarities of the merges
    • \( s_1\geq ... \geq s_{k-1} \)

Dendrogram

  • Visualization of cluster merges
  • y-coordinate: Cluster similarity (from 1.0 to 0.0)
  • Cut dendrogram at specific point to get \( k \) clusters

Algorithm

  1. Create cluster for each document
  2. Compute similarity for each document pair (\( m\times m \) similarity matrix)
  3. Merge clusters with highest similarity
  4. GOTO (2) if more than one cluster exists

Cluster similarity

  • Single-link clustering
    • Similarity of most similar members
    • Problem: Long chains, only local structure
  • Complete-link clustering
    • Similarity of most dissimilar members
    • Merged cluster has smallest diameter
    • Problem: Outliers
  • Centroid clustering
    • Similarity is similarity of centroids
    • Problem:
      • Not monotonic (overlap in dendrogram)
      • Contradicts assumption that small clusters are more coherent than larger ones
  • Group-average clustering
    • Similarity is average similarity of all documents of the union of both clusters
    • Including documents from the same cluster but not self-similarity
    • Goal: Resulting cluster should be coherent
    • Problem: Expensive

Divisive clustering

  • Top-down
  • Start with one cluster and split
  • Use flat clustering (e.g., iteratively apply 2-means)
  • Possible constraints
    • Avoid very small clusters
    • Avoid high deviation in cluster cardinalities