## 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
2. Compute centroids of clusters
3. Iterate over collection: Assign document to nearest cluster
4. Recompute cluster centroids
5. 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