[ENH] Adding KModes and KPrototypes clustering algorithms

### Describe the workflow you want to enable

Currently, scikit-learn users working with datasets that contain categorical features (e.g., `country`, `profession`, `product_type`) face a significant hurdle. The standard practice is to use one-hot encoding before applying algorithms like K-Means.

This workflow is problematic because:
1.  **High-Dimensionality:** It drastically increases the dimensionality of the dataset (the "curse of dimensionality").
2.  **Sparsity:** It creates a sparse matrix that is computationally inefficient and poorly suited for distance-based algorithms like K-Means, which are designed for dense, numerical data.
3.  **Interpretability:** The resulting clusters are based on a transformed version of the data, making the centroids and the cluster logic difficult to interpret in terms of the original categorical features.

The workflow I want to enable is a seamless and native experience for clustering categorical and mixed data:
*   **For fully categorical data:** A user should be able to call `KModes(n_clusters=5).fit(X_categorical)` directly, without any pre-processing.
*   **For mixed data types:** A user should be able to call `KPrototypes(n_clusters=5, categorical=[0, 2]).fit(X_mixed)`, where they simply specify which columns are categorical. The algorithm would then automatically use an appropriate dissimilarity measure for each data type.

This integrates categorical clustering directly into the robust and familiar scikit-learn API, eliminating the need for external dependencies and inefficient pre-processing.

### Describe your proposed solution

I propose implementing the well-established K-Modes and K-Prototypes algorithms as new classes within the `sklearn.cluster` module. These algorithms are the canonical equivalents of K-Means for categorical and mixed data, respectively.

**Proposed API Design (following scikit-learn conventions):**

```python
class KModes(BaseEstimator, ClusterMixin):
    """
    K-Modes clustering for categorical data.

    Parameters
    ----------
    n_clusters : int, default=8
        The number of clusters to form as well as the number of centroids to generate.
    init : {'Huang', 'Cao', 'random' or an ndarray}, default='Huang'
        Method for initialization.
    n_init : int, default=10
        Number of times the algorithm will be run with different centroid seeds.
    max_iter : int, default=300
        Maximum number of iterations of the algorithm for a single run.
    verbose : int, default=0
        Verbosity mode.
    random_state : int, RandomState instance, default=None
        Determines random number generation for centroid initialization.
    """
    # Will have attributes: cluster_centroids_, labels_, cost_, n_iter_

class KPrototypes(BaseEstimator, ClusterMixin):
    """
    K-Prototypes clustering for mixed numeric and categorical data.

    Parameters
    ----------
    n_clusters : int, default=8
        The number of clusters to form.
    categorical : list of int, default=[]
        Indices of columns in the input data that are categorical.
    init : {'Huang', 'Cao', 'random' or an ndarray}, default='Huang'
        Method for initialization.
    n_init : int, default=10
        Number of times the algorithm will be run with different centroid seeds.
    max_iter : int, default=300
        Maximum number of iterations of the algorithm for a single run.
    gamma : float, default=None
        Weighting factor for categorical dissimilarity. If None, it will be calculated automatically.
    verbose : int, default=0
        Verbosity mode.
    random_state : int, RandomState instance, default=None
        Determines random number generation for centroid initialization.
    """
    # Will have attributes: cluster_centroids_, labels_, cost_, n_iter_
```

**Implementation Plan:**
1.  **API Consistency:** The classes will inherit from `BaseEstimator` and `ClusterMixin`, ensuring full compatibility with the scikit-learn ecosystem (e.g., `fit`, `predict`, `fit_predict`, `get_params`, `set_params`).
2.  **Performance:** The initial implementation will be in Python with NumPy, with a clear path for future optimization using Cython if needed, following the same pattern as the `KMeans` codebase.
3.  **Validation:** Input validation will use scikit-learn's existing utilities (`check_array`, `check_random_state`). The `categorical` parameter will be rigorously validated against the input data's shape.
4.  **Comprehensive Testing:** I will write a full suite of tests in `test_kmodes.py` and `test_kprototypes.py`, covering functionality, convergence, input validation, and consistency against known results.
5.  **Documentation:** I will provide detailed docstrings with mathematical formulations (modes, cost function) and create examples demonstrating the use cases in the `examples/` gallery.

### Describe alternatives you've considered, if relevant

The main alternative for users today is to use the third-party `kmodes` package. While it is a good implementation, relying on it has several drawbacks:

1.  **Ecosystem Fragmentation:** It forces users to leave the integrated scikit-learn environment for a specific task. This breaks workflow consistency and requires managing an external dependency.
2.  **Inconsistency:** The `kmodes` API, while similar, is not identical to scikit-learn's. This creates a learning curve and potential for errors.
3.  **Limited Compatibility:** It does not integrate as smoothly with scikit-learn's powerful ecosystem tools like `Pipeline`, `GridSearchCV`, or `SKLearnEstimator` in libraries like Spark MLlib. Users cannot build a simple pipeline like `Pipeline([('impute', SimpleImputer()), ('cluster', KPrototypes())])`.
4.  **Maintenance and Visibility:** As an external library, it has less visibility and a smaller pool of potential contributors compared to a feature within scikit-learn itself. Users may not even be aware it exists.

Another alternative, one-hot encoding + K-Means, is fundamentally flawed for the reasons described in the first section (high dimensionality, sparsity, poor interpretability).

Therefore, the best alternative is a native implementation that provides a unified, consistent, and efficient experience for the scikit-learn community.

### Additional context

*   **Mathematical Foundation:** The algorithms are well-established with strong academic foundations. The key references are:
    *   **K-Modes:** Huang, Z. (1998). Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values. *Data Mining and Knowledge Discovery*.
    *   **K-Prototypes:** Huang, Z. (1997). Clustering large data sets with mixed numeric and categorical values. *Proceedings of the First Pacific-Asia Conference on Knowledge Discovery and Data Mining*.
    *   The cost function for K-Modes minimizes the sum of dissimilarities using a simple matching function (0 for same category, 1 for different). K-Prototypes combines this with the Euclidean distance for numerical features.

*   **Personal Commitment:** I am a mathematician from SPbU and ML engineer at Sber with a deep understanding of these algorithms and the scikit-learn codebase. I am fully committed to implementing this feature to the project's highest standards, including comprehensive tests, documentation, and examples. I am prepared to iterate on the code based on feedback from the maintainers.

*   **Scope:** This enhancement fits perfectly within the scope of scikit-learn's `cluster` module, filling a clear and important gap for a common data type (categorical data) that is currently underserved.

COMMENT:
Well, it's about how you define the distance. We've had requests on allowing a custom distance metric for `kmean` in the past, and we've also had efforts to implement Gower distance (https://github.com/scikit-learn/scikit-learn/pull/16834). Of course you can also extend the similarity measure in Gower distance if you know more about your categories, and putting some assumptions on what the individual categorical distance measure returns, makes a sane distance metric overall.

The way I understand it, `KPrototypes` implements something very similar, if not the same as Gower distance, so it's not that there's no literature around the topic.

You're right that it might be hard to set something which is absolutely bulletproof as a distance metric here, but user requests and literature suggests these existing options are much better than nothing.

Labels: New Feature, module:cluster, Needs Decision - Include Feature