带容量约束的k-means聚类

### Capacity Constrained K-Means Clustering Algorithm Implementation and Explanation Capacity-constrained k-means clustering is a variant of the traditional k-means algorithm where each cluster has an upper limit on the number of points it can contain. This constraint ensures that clusters do not become too large, which may be desirable in certain applications such as load balancing or resource allocation. The standard k-means objective function minimizes within-cluster variance but does not consider capacity constraints. To incorporate these constraints into the model: - A penalty term must be added to penalize violations of the capacity limits. - The assignment step needs modification so that no more than \( C_i \) points are assigned to any given cluster \( i \). An effective approach involves using Lagrange multipliers to handle inequality constraints during optimization[^1]. Here's how one might implement this method in Python: ```python import numpy as np from sklearn.cluster import MiniBatchKMeans def capacity_constrained_kmeans(X, n_clusters=8, max_iter=300, capacities=None): """ Perform capacity-constrained k-means clustering Parameters: X (array-like): Input data matrix with shape (n_samples, n_features). n_clusters (int): Number of clusters. max_iter (int): Maximum iterations allowed. capacities (list[int]): List containing maximum size per cluster. Returns: labels (ndarray): Array of integer labels indicating cluster membership. centers (ndarray): Centroid coordinates for each cluster. """ if capacities is None: raise ValueError("Capacities list cannot be empty") # Initialize centroids randomly from input samples rng = np.random.RandomState(42) indices = rng.choice(len(X), size=n_clusters, replace=False) centers = X[indices] prev_labels = None for iteration in range(max_iter): distances = ((X[:, :, None] - centers.T)**2).sum(axis=1) # Assign points while respecting capacity restrictions available_slots = capacities.copy() labels = [-1] * len(X) sorted_indices = np.argsort(distances.sum(axis=1)) for idx in sorted_indices: valid_options = [ c for c in range(n_clusters) if available_slots[c] > 0 and distances[idx][c] != float('inf') ] if not valid_options: break chosen_cluster = min(valid_options, key=lambda x: distances[idx][x]) labels[idx] = chosen_cluster available_slots[chosen_cluster] -= 1 # Update center positions based on new assignments updated_centers = [] for clust_id in set(labels): members = [idx for idx, lbl in enumerate(labels) if lbl == clust_id] if members: centroid = X[members].mean(axis=0) updated_centers.append(centroid) centers = np.array(updated_centers) # Check convergence condition if prev_labels is not None and all(prev_labels == labels): break prev_labels = labels[:] return labels, centers ``` This code snippet demonstrates implementing capacity-constrained k-means by ensuring no cluster exceeds its specified capacity when assigning points. It iteratively updates both point-to-cluster assignments and cluster centroids until either reaching `max_iter` iterations or achieving stable results between consecutive passes over the dataset. --related questions-- 1. How would varying initial conditions affect performance? 2. What alternative strategies exist beyond simple distance-based selection? 3. Can parallel processing techniques improve execution speed significantly here? 4. Are there specific use cases better suited for capacity-constrained versus regular k-means?