[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:
> So I think it might be worth considering supporting categorical data in a k-means like kinda clustering algorithm.

I feel that I don't understand something here: k-means minimizes a criterion based on Euclidean. So how you are going to represent your categories, and more importantly how you are going to scale the corresponding columns compared to the other columns is going to make a huge difference in the clusters.

Let me try to expand a bit my thoughts here: suppose I have three columns: "age", "sex", and "city", and that there are 30 different cities, and 2 different sex categories, both evenly distributed.

If I don't scale age, the Euclidean distance is going to be completely dominated by the age, as the other columns are going to contribute 1 or 0 to the Euclidean distance.

If I standard-scale the columns, each sex category gets a weight of 1/sqrt(2) ~ .7, but each city gets a weight of 1/sqrt(30) ~ .18. So what we are saying here is that it is approximately 4 times less important to have the same city than the same sex to be in the same cluster.

The point that I am trying to make is that there is no good solution. It's a modeling problem. It boils down to: what makes two samples closer or more distant?

I don't think that this is something that we, or any algorithm, should be deciding for users (unless there is excellent literature on this that I don't know, but I've worked a fair bit on unsupervised learning, so I feel that I have a good understanding of the challenges). We can how provide helpful guidelines and way of approaching the problem.

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