[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:
Hi @jeremiedbb!

Thank you for your thoughtful feedback. Indeed, precomputed matrices and KMedoids are existing alternatives. However, a native implementation of KModes and KPrototypes is justified because it solves the core problem of **scalability and user experience** in a way these alternatives cannot.

1.  **The Precomputed Matrix Approach is Computationally Prohibitive:** Calculating a full pairwise distance matrix (e.g., with Gower's distance) for $n$ samples has $O(n^2)$ complexity. This makes it instantly infeasible for the medium-to-large datasets that sklearn is designed for. KModes/KPrototypes, with their $O(nkp)$ complexity per iteration, are the only practical, scalable solution for this common task.

2.  **K-Prototypes and K-Medoids Solve Different Problems Efficiently:** While both handle mixed data, they are fundamentally different.
    *   **K-Medoids** is a robust but expensive algorithm ($O(k(n-k)^2)$ per iteration) that finds *representative data points* (medoids). If I'm not mistaken, it was kept out of sklearn core largely due to its complexity.
    *   **K-Prototypes** is an efficient algorithm - $O(nkp)$ - that creates *interpretable synthetic centroids* (mean for numeric, mode for categorical). It provides the scalability and clean API of K-Means for mixed data.

A native implementation would provide a seamless `fit`/`predict` API, full pipeline compatibility, and a scalable algorithm - addressing a clear gap in the library's offerings that current workarounds cannot efficiently fill.

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