<commit_before>""" K-means clustering
"""

# Authors: <NAME> <<EMAIL>>
#          <NAME> <<EMAIL>>
#          <NAME> <<EMAIL>>
# License: BSD

import warnings

import numpy as np

from ..base import BaseEstimator
from ..metrics.pairwise import euclidian_distances


###############################################################################
# Initialisation heuristic

def k_init(X, k, n_samples_max=500, rng=None):
    """Init k seeds according to kmeans++

    Parameters
    -----------
    X: array, shape (n_samples, n_features)
        The data

    k: integer
        The number of seeds to choose

    n_samples_max: integer, optional
        The maximum number of samples to use: the complexity of the
        algorithm is n_samples**2, if n_samples > n_samples_max,
        we use the Niquist strategy, and choose our centers in the
        n_samples_max samples randomly choosen.

    Notes
    ------
    Selects initial cluster centers for k-mean clustering in a smart way
    to speed up convergence. see: <NAME>. and <NAME>.
    "k-means++: the advantages of careful seeding". ACM-SIAM symposium
    on Discrete algorithms. 2007

    Implementation from Yong Sun's website
    http://blogs.sun.com/yongsun/entry/k_means_and_k_means

    kinit originaly from pybrain:
    http://github.com/pybrain/pybrain/raw/master/pybrain/auxiliary/kmeans.py
    """
    n_samples = X.shape[0]
    if rng is None:
        rng = np.random

    if n_samples >= n_samples_max:
        X = X[rng.randint(n_samples, size=n_samples_max)]
        n_samples = n_samples_max

    distances = euclidian_distances(X, X, squared=True)

    # choose the 1st seed randomly, and store D(x)^2 in D[]
    first_idx = rng.randint(n_samples)
    centers = [X[first_idx]]
    D = distances[first_idx]

    for _ in range(k - 1):
        bestDsum = bestIdx = -1

        for i in range(n_samples):
            'Dsum = sum_{x in X} min(D(x)^2,||x-xi||^2)'
            Dsum = np.minimum(D, distances[i]).sum()

            if bestDsum < 0 or Dsum < bestDsum:
                bestDsum, bestIdx = Dsum, i

        centers.append(X[bestIdx])
        D = np.minimum(D, distances[bestIdx])

    return np.array(centers)


###############################################################################
# K-means estimation by EM (expectation maximisation)

def k_means(X, k, init='k-means++', n_init=10, max_iter=300, verbose=0,
                    delta=1e-4, rng=None, copy_x=True):
    """ K-means clustering algorithm.

    Parameters
    ----------
    X: ndarray
        A M by N array of M observations in N dimensions or a length
        M array of M one-dimensional observations.

    k: int or ndarray
        The number of clusters to form as well as the number of
        centroids to generate. If minit initialization string is
        'matrix', or if a ndarray is given instead, it is
        interpreted as initial cluster to use instead.

    max_iter: int, optional, default 300
        Maximum number of iterations of the k-means algorithm to run.

    n_init: int, optional, default: 10
        Number of time the k-means algorithm will be run with different<commit_msg>style conventions for variable names<commit_after>""" K-means clustering
"""

# Authors: <NAME> <<EMAIL>>
#          <NAME> <<EMAIL>>
#          <NAME> <<EMAIL>>
# License: BSD

import warnings

import numpy as np

from ..base import BaseEstimator
from ..metrics.pairwise import euclidian_distances


###############################################################################
# Initialisation heuristic

def k_init(X, k, n_samples_max=500, rng=None):
    """Init k seeds according to kmeans++

    Parameters
    -----------
    X: array, shape (n_samples, n_features)
        The data

    k: integer
        The number of seeds to choose

    n_samples_max: integer, optional
        The maximum number of samples to use: the complexity of the
        algorithm is n_samples**2, if n_samples > n_samples_max,
        we use the Niquist strategy, and choose our centers in the
        n_samples_max samples randomly choosen.

    Notes
    ------
    Selects initial cluster centers for k-mean clustering in a smart way
    to speed up convergence. see: <NAME>. and <NAME>.
    "k-means++: the advantages of careful seeding". ACM-SIAM symposium
    on Discrete algorithms. 2007

    Implementation from Yong Sun's website
    http://blogs.sun.com/yongsun/entry/k_means_and_k_means

    kinit originaly from pybrain:
    http://github.com/pybrain/pybrain/raw/master/pybrain/auxiliary/kmeans.py
    """
    n_samples = X.shape[0]
    if rng is None:
        rng = np.random

    if n_samples >= n_samples_max:
        X = X[rng.randint(n_samples, size=n_samples_max)]
        n_samples = n_samples_max

    distances = euclidian_distances(X, X, squared=True)

    # choose the 1st seed randomly, and store D(x)^2 in D[]
    first_idx = rng.randint(n_samples)
    centers = [X[first_idx]]
    D = distances[first_idx]

    for _ in range(k - 1):
        best_d_sum = best_idx = -1

        for i in range(n_samples):
            # d_sum = sum_{x in X} min(D(x)^2, ||x - xi||^2)
            d_sum = np.minimum(D, distances[i]).sum()

            if best_d_sum < 0 or d_sum < best_d_sum:
                best_d_sum, best_idx = d_sum, i

        centers.append(X[best_idx])
        D = np.minimum(D, distances[best_idx])

    return np.array(centers)


###############################################################################
# K-means estimation by EM (expectation maximisation)

def k_means(X, k, init='k-means++', n_init=10, max_iter=300, verbose=0,
                    delta=1e-4, rng=None, copy_x=True):
    """ K-means clustering algorithm.

    Parameters
    ----------
    X: ndarray
        A M by N array of M observations in N dimensions or a length
        M array of M one-dimensional observations.

    k: int or ndarray
        The number of clusters to form as well as the number of
        centroids to generate. If minit initialization string is
        'matrix', or if a ndarray is given instead, it is
        interpreted as initial cluster to use instead.

    max_iter: int, optional, default 300
        Maximum number of iterations of the k-means algorithm to run.

    n_init: int, optional, default: 10
        Number of time the k-means algorithm will be run with different
{'fraction_non_alphanumeric': 0.14166928145591465, 'fraction_numerical': 0.009099466582993411, 'mean_word_length': 2.6956521739130435, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6254489', 'n_tokens_mistral': 2027, 'n_tokens_neox': 1877, 'n_words': 641}