如何在Scikit-learn中实现概念聚类？维基百科文章层级构建

Great question—dealing with hierarchical clustering on large datasets is tricky because of that O(n²) memory bottleneck from full distance matrices. Let’s break down practical, memory-efficient solutions tailored to your Wikipedia article use case (where you want top-level clusters to map to broad categories like Programming Languages → Functional Languages → Haskell):

1. Use Scikit-Learn's AgglomerativeClustering (Optimized for Large Data) #

Scikit-learn's AgglomerativeClustering avoids storing a full pairwise distance matrix when using the ward linkage method (perfect for your L2-normalized data, since it relies on Euclidean distance). It uses an optimized algorithm based on minimum spanning trees, cutting memory usage down to O(n) instead of O(n²).

You can build your hierarchy recursively: start with top-level broad clusters, then cluster each sub-cluster to create deeper levels. Here's how:

from sklearn.cluster import AgglomerativeClustering
import numpy as np

# Assume your preprocessed data (TF-IDF → Truncated SVD → L2 norm) is stored in X (shape: [n_samples, n_components])
# Step 1: Create top-level broad clusters (adjust n_clusters to match your desired number of root categories)
top_clustering = AgglomerativeClustering(
    n_clusters=20,  # Example: 20 broad top-level categories
    linkage='ward',
    compute_full_tree=True  # Preserve the full clustering tree for later hierarchy building
)
top_labels = top_clustering.fit_predict(X)

# Step 2: Recursively cluster each top-level sub-cluster to build deeper hierarchy
cluster_hierarchy = {}
for cluster_id in np.unique(top_labels):
    # Extract data points in the current top-level cluster
    sub_cluster_data = X[top_labels == cluster_id]
    # Cluster this sub-group into smaller, more specific categories
    sub_clustering = AgglomerativeClustering(
        n_clusters=5,  # Example: 5 sub-categories per top-level cluster
        linkage='ward'
    )
    sub_labels = sub_clustering.fit_predict(sub_cluster_data)
    cluster_hierarchy[cluster_id] = sub_labels

If you want to visualize the full hierarchy, you can use scipy.cluster.hierarchy.dendrogram with the children_ attribute of the clustering object.

2. Incremental Hierarchical Clustering with KD-Tree #

Since you already experimented with KD-Tree, you can use it to build an incremental hierarchical clusterer that avoids computing all pairwise distances. The idea is to start with each sample as its own cluster, then repeatedly merge the closest pair of clusters (found via KD-Tree) until you reach your desired hierarchy level.

Here's a simplified implementation:

from sklearn.neighbors import KDTree
import numpy as np

# Initialize: each sample is a cluster, with its own center (the sample itself)
cluster_centers = X.copy()
cluster_members = [[i] for i in range(len(X))]
kdtree = KDTree(cluster_centers, leaf_size=30)

# Merge clusters until we reach the desired number of top-level categories
target_top_clusters = 20
while len(cluster_centers) > target_top_clusters:
    # Find the nearest neighbor for each cluster center (exclude self)
    distances, nearest_indices = kdtree.query(cluster_centers, k=2)
    # Find the pair of clusters with the smallest distance
    min_distance = np.min(distances[:, 1])
    pair_idx = np.where(distances[:, 1] == min_distance)[0][0]
    cluster_a_idx = pair_idx
    cluster_b_idx = nearest_indices[pair_idx, 1]

    # Merge the two clusters: combine members and compute new center
    merged_members = cluster_members[cluster_a_idx] + cluster_members[cluster_b_idx]
    merged_center = np.mean(X[merged_members], axis=0)

    # Clean up old clusters and add the new one
    # Delete higher index first to avoid shifting issues
    del cluster_members[max(cluster_a_idx, cluster_b_idx)]
    del cluster_members[min(cluster_a_idx, cluster_b_idx)]
    cluster_members.append(merged_members)

    # Update cluster centers and rebuild KD-Tree
    cluster_centers = np.delete(cluster_centers, [cluster_a_idx, cluster_b_idx], axis=0)
    cluster_centers = np.vstack([cluster_centers, merged_center])
    kdtree = KDTree(cluster_centers, leaf_size=30)

This approach uses O(n) memory (storing only cluster centers and member lists) and is much faster than full distance matrix methods for large datasets. Note that it's an approximate method (since it merges locally closest pairs instead of globally optimal ones), but it's a practical tradeoff for scale.

3. Optimized Linkage with fastcluster #

If you prefer a more traditional hierarchical clustering approach but need better memory efficiency than scipy's hierarchy.linkage, use the fastcluster library. It's a drop-in replacement for scipy's linkage functions but uses optimized algorithms that reduce memory usage and speed up computation—especially for the ward linkage method (which uses O(n) memory instead of O(n²)).

Example usage:

import fastcluster
from scipy.cluster.hierarchy import dendrogram

# Generate the linkage matrix with fastcluster (memory-efficient for large n)
linkage_matrix = fastcluster.linkage(X, method='ward', metric='euclidean')

# Visualize the dendrogram (optional, for small enough subsets)
dendrogram(linkage_matrix)

For datasets with 10,000+ samples, fastcluster will handle the linkage computation without hitting memory limits, unlike scipy's default implementation.

4. Post-Processing: Map Clusters to Semantic Labels #

Once you have your hierarchy, you'll want to label each cluster with meaningful, human-readable names (like Programming Languages). A simple way to do this is:

• For each cluster, extract the top TF-IDF weighted terms from all articles in the cluster.
• Use these top terms to assign a descriptive label (e.g., if the top terms are "programming", "language", "code", the cluster label could be Programming Languages).
• If you have access to Wikipedia's category metadata for the articles, you can also use that to align clusters with existing Wikipedia categories for more accurate labels.

内容的提问来源于stack exchange，提问作者michaelsnowden