
import warnings

import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from sklearn.metrics import pairwise_distances

warnings.filterwarnings('ignore')

_UpperCamelCase:					Union[str, Any]     ='K-MEANS-CLUST/ '



def 	_a  (					__SCREAMING_SNAKE_CASE					:  List[str]		,				__SCREAMING_SNAKE_CASE					:  Union[str, Any]		,				__SCREAMING_SNAKE_CASE					:  str=None    ):






  """simple docstring"""




  if seed is not None:  # useful for obtaining consistent results
    np.random.seed(__SCREAMING_SNAKE_CASE    )
  _lowerCAmelCase						=		data.shape[0]  # number of data points

  # Pick K indices from range [0, N).
  _lowerCAmelCase						=		np.random.randint(0		,				__SCREAMING_SNAKE_CASE		,				__SCREAMING_SNAKE_CASE    )

  # Keep centroids as dense format, as many entries will be nonzero due to averaging.
  # As long as at least one document in a cluster contains a word,
  # it will carry a nonzero weight in the TF-IDF vector of the centroid.
  _lowerCAmelCase						=		data[rand_indices, :]

  return centroids



def 	_a  (					__SCREAMING_SNAKE_CASE					:  Union[str, Any]		,				__SCREAMING_SNAKE_CASE					:  str    ):






  """simple docstring"""




  return pairwise_distances(__SCREAMING_SNAKE_CASE		,				__SCREAMING_SNAKE_CASE		,				metric='euclidean'    )



def 	_a  (					__SCREAMING_SNAKE_CASE					:  Any		,				__SCREAMING_SNAKE_CASE					:  List[str]    ):






  """simple docstring"""




  _lowerCAmelCase						=		centroid_pairwise_dist(__SCREAMING_SNAKE_CASE		,				__SCREAMING_SNAKE_CASE    )

  # Compute cluster assignments for each data point:
  # Fill in the blank (RHS only)
  _lowerCAmelCase						=		np.argmin(__SCREAMING_SNAKE_CASE		,				axis=1    )

  return cluster_assignment



def 	_a  (					__SCREAMING_SNAKE_CASE					:  Dict		,				__SCREAMING_SNAKE_CASE					:  Tuple		,				__SCREAMING_SNAKE_CASE					:  List[str]    ):






  """simple docstring"""




  _lowerCAmelCase						=		[]
  for i in range(__SCREAMING_SNAKE_CASE    ):
    # Select all data points that belong to cluster i. Fill in the blank (RHS only)
    _lowerCAmelCase						=		data[cluster_assignment == i]
    # Compute the mean of the data points. Fill in the blank (RHS only)
    _lowerCAmelCase						=		member_data_points.mean(axis=0    )
    new_centroids.append(__SCREAMING_SNAKE_CASE    )
  _lowerCAmelCase						=		np.array(__SCREAMING_SNAKE_CASE    )

  return new_centroids



def 	_a  (					__SCREAMING_SNAKE_CASE					:  Optional[Any]		,				__SCREAMING_SNAKE_CASE					:  Tuple		,				__SCREAMING_SNAKE_CASE					:  str		,				__SCREAMING_SNAKE_CASE					:  Union[str, Any]    ):






  """simple docstring"""




  _lowerCAmelCase						=		0.0
  for i in range(__SCREAMING_SNAKE_CASE    ):
    # Select all data points that belong to cluster i. Fill in the blank (RHS only)
    _lowerCAmelCase						=		data[cluster_assignment == i, :]

    if member_data_points.shape[0] > 0:  # check if i-th cluster is non-empty
      # Compute distances from centroid to data points (RHS only)
      _lowerCAmelCase						=		pairwise_distances(
          __SCREAMING_SNAKE_CASE		,				[centroids[i]]		,				metric='euclidean'    )
      _lowerCAmelCase						=		distances**2
      heterogeneity += np.sum(__SCREAMING_SNAKE_CASE    )

  return heterogeneity



def 	_a  (					__SCREAMING_SNAKE_CASE					:  Optional[Any]		,				__SCREAMING_SNAKE_CASE					:  int    ):






  """simple docstring"""




  plt.figure(figsize=(7, 4)    )
  plt.plot(__SCREAMING_SNAKE_CASE		,				linewidth=4    )
  plt.xlabel('# Iterations'    )
  plt.ylabel('Heterogeneity'    )
  plt.title(f'''Heterogeneity of clustering over time, K={k:d}'''    )
  plt.rcParams.update({'font.size': 16}    )
  plt.show()



def 	_a  (					__SCREAMING_SNAKE_CASE					:  Tuple		,				__SCREAMING_SNAKE_CASE					:  Tuple		,				__SCREAMING_SNAKE_CASE					:  Optional[Any]		,				__SCREAMING_SNAKE_CASE					:  Union[str, Any]=500		,				__SCREAMING_SNAKE_CASE					:  Any=None		,				__SCREAMING_SNAKE_CASE					:  List[Any]=False    ):






  """simple docstring"""




  _lowerCAmelCase						=		initial_centroids[:]
  _lowerCAmelCase						=		None

  for itr in range(__SCREAMING_SNAKE_CASE    ):
    if verbose:
      print(__SCREAMING_SNAKE_CASE		,				end=''    )

    # 1. Make cluster assignments using nearest centroids
    _lowerCAmelCase						=		assign_clusters(__SCREAMING_SNAKE_CASE		,				__SCREAMING_SNAKE_CASE    )

    # 2. Compute a new centroid for each of the k clusters, averaging all data
    #    points assigned to that cluster.
    _lowerCAmelCase						=		revise_centroids(__SCREAMING_SNAKE_CASE		,				__SCREAMING_SNAKE_CASE		,				__SCREAMING_SNAKE_CASE    )

    # Check for convergence: if none of the assignments changed, stop
    if (
        prev_cluster_assignment is not None
        and (prev_cluster_assignment == cluster_assignment).all()
    ):
      break

    # Print number of new assignments
    if prev_cluster_assignment is not None:
      _lowerCAmelCase						=		np.sum(prev_cluster_assignment != cluster_assignment    )
      if verbose:
        print(
            f'''    {num_changed:5d} elements changed their cluster assignment.'''    )

        # Record heterogeneity convergence metric
    if record_heterogeneity is not None:
      # YOUR CODE HERE
      _lowerCAmelCase						=		compute_heterogeneity(__SCREAMING_SNAKE_CASE		,				__SCREAMING_SNAKE_CASE		,				__SCREAMING_SNAKE_CASE		,				__SCREAMING_SNAKE_CASE    )
      record_heterogeneity.append(__SCREAMING_SNAKE_CASE    )

    _lowerCAmelCase						=		cluster_assignment[:]

  return centroids, cluster_assignment


# Mock test below
if False:  # change to true to run this test case.
       from sklearn import datasets as ds

       _UpperCamelCase:					int     =ds.load_iris()
       _UpperCamelCase:					Any     =3
       _UpperCamelCase:					Optional[Any]     =[]
       _UpperCamelCase:					List[Any]     =get_initial_centroids(dataset['data'], k, seed=0)
       _UpperCamelCase     ,    _UpperCamelCase:					Any     =kmeans(
           dataset['data'],
           k,
           initial_centroids,
           maxiter=400,
           record_heterogeneity=heterogeneity,
           verbose=True,
       )
       plot_heterogeneity(heterogeneity, k)



def 	_a  (					__SCREAMING_SNAKE_CASE					:  pd.DataFrame		,				__SCREAMING_SNAKE_CASE					:  np.ndarray		,				__SCREAMING_SNAKE_CASE					:  Dict=None    ):






  """simple docstring"""




  if fill_missing_report:
    _lowerCAmelCase						=		df.fillna(value=__SCREAMING_SNAKE_CASE    )
  _lowerCAmelCase						=		1
  _lowerCAmelCase						=		df.select_dtypes(np.number    ).columns
  _lowerCAmelCase						=		(
      df.groupby(['Cluster']    )[  # construct report dataframe
          numeric_cols
      ]  # group by cluster number
      .agg(
          [
              ('sum', np.sum),
              ('mean_with_zeros', lambda __SCREAMING_SNAKE_CASE    : np.mean(np.nan_to_num(__SCREAMING_SNAKE_CASE    )    )),
              ('mean_without_zeros', lambda __SCREAMING_SNAKE_CASE    : x.replace(0		,				np.NaN    ).mean()),
              (
                  'mean_25-75',
                  lambda __SCREAMING_SNAKE_CASE    : np.mean(
                      np.nan_to_num(
                          sorted(__SCREAMING_SNAKE_CASE    )[
                              round(len(__SCREAMING_SNAKE_CASE    ) * 25 / 100    ) : round(len(__SCREAMING_SNAKE_CASE    ) * 75 / 100    )
                          ]    )    ),
              ),
              ('mean_with_na', np.mean),
              ('min', lambda __SCREAMING_SNAKE_CASE    : x.min()),
              ('5%', lambda __SCREAMING_SNAKE_CASE    : x.quantile(0.0_5    )),
              ('25%', lambda __SCREAMING_SNAKE_CASE    : x.quantile(0.2_5    )),
              ('50%', lambda __SCREAMING_SNAKE_CASE    : x.quantile(0.5_0    )),
              ('75%', lambda __SCREAMING_SNAKE_CASE    : x.quantile(0.7_5    )),
              ('95%', lambda __SCREAMING_SNAKE_CASE    : x.quantile(0.9_5    )),
              ('max', lambda __SCREAMING_SNAKE_CASE    : x.max()),
              ('count', lambda __SCREAMING_SNAKE_CASE    : x.count()),
              ('stdev', lambda __SCREAMING_SNAKE_CASE    : x.std()),
              ('mode', lambda __SCREAMING_SNAKE_CASE    : x.mode()[0]),
              ('median', lambda __SCREAMING_SNAKE_CASE    : x.median()),
              ('# > 0', lambda __SCREAMING_SNAKE_CASE    : (x > 0).sum()),
          ]    )
      .T.reset_index()
      .rename(index=__SCREAMING_SNAKE_CASE		,				columns={'level_0': 'Features', 'level_1': 'Type'}    )
  )  # rename columns
  # calculate the size of cluster(count of clientID's)
  _lowerCAmelCase						=		report[
      (report['Features'] == 'dummy') & (report['Type'] == 'count')
  ].copy()  # avoid SettingWithCopyWarning
  _lowerCAmelCase						=		(
      'ClusterSize'  # rename created cluster df to match report column names
  )
  _lowerCAmelCase						=		'# of Customers'
  _lowerCAmelCase						=		pd.DataFrame(
      clustersize.iloc[:, 2:].values
      / clustersize.iloc[:, 2:].values.sum()    )
  _lowerCAmelCase						=		'% of Customers'  # rename created cluster df to match report column names
  _lowerCAmelCase						=		'ClusterProportion'
  _lowerCAmelCase						=		clusterproportion.columns.tolist()
  _lowerCAmelCase						=		cols[-2:] + cols[:-2]
  _lowerCAmelCase						=		clusterproportion[cols]  # rearrange columns to match report
  _lowerCAmelCase						=		report.columns
  _lowerCAmelCase						=		pd.DataFrame(
      abs(
          report[report['Type'] == 'count'].iloc[:, 2:].values
          - clustersize.iloc[:, 2:].values    )    )  # generating df with count of nan values
  _lowerCAmelCase						=		0
  _lowerCAmelCase						=		'# of nan'
  _lowerCAmelCase						=		report[
      report['Type'] == 'count'
  ].Features.tolist()  # filling values in order to match report
  _lowerCAmelCase						=		a.columns.tolist()
  _lowerCAmelCase						=		cols[-2:] + cols[:-2]
  _lowerCAmelCase						=		a[cols]  # rearrange columns to match report
  _lowerCAmelCase						=		report.columns  # rename columns to match report
  _lowerCAmelCase						=		report.drop(
      report[report.Type == 'count'].index    )  # drop count values except cluster size
  _lowerCAmelCase						=		pd.concat(
      [report, a, clustersize, clusterproportion]		,				axis=0    )  # concat report with clustert size and nan values
  _lowerCAmelCase						=		report['Features'].isin(__SCREAMING_SNAKE_CASE    )
  _lowerCAmelCase						=		report.columns.tolist()
  _lowerCAmelCase						=		cols[0:2] + cols[-1:] + cols[2:-1]
  _lowerCAmelCase						=		report[cols]
  _lowerCAmelCase						=		{
      'ClusterSize': 9,
      'ClusterProportion': 8,
      'mean_with_zeros': 7,
      'mean_with_na': 6,
      'max': 5,
      '50%': 4,
      'min': 3,
      '25%': 2,
      '75%': 1,
      '# of nan': 0,
      '# > 0': -1,
      'sum_with_na': -2,
  }
  _lowerCAmelCase						=		(
      report.assign(
          Sortera=lambda __SCREAMING_SNAKE_CASE    : x.Type.map(__SCREAMING_SNAKE_CASE    )		,				Sortera=lambda __SCREAMING_SNAKE_CASE    : list(reversed(range(len(__SCREAMING_SNAKE_CASE    )    )    )    )		,				)
      .sort_values(['Sorter1', 'Mark', 'Sorter2']		,				ascending=__SCREAMING_SNAKE_CASE    )
      .drop(['Sorter1', 'Sorter2']		,				axis=1    )
  )
  _lowerCAmelCase						=		''
  _lowerCAmelCase						=		report.reset_index()
  _lowerCAmelCase						=		report.drop(columns=['index']    )
  return report


if __name__ == "__main__":
       import doctest

       doctest.testmod()


from __future__ import annotations



def 	_a  (					__SCREAMING_SNAKE_CASE					:  list		,				__SCREAMING_SNAKE_CASE					:  list    ):






  """simple docstring"""




  _lowerCAmelCase						=		[None] * (len(__SCREAMING_SNAKE_CASE    ) + len(__SCREAMING_SNAKE_CASE    ))

  _lowerCAmelCase						=		0  # pointer to current index for left Half
  _lowerCAmelCase						=		0  # pointer to current index for the right Half
  _lowerCAmelCase						=		0  # pointer to current index for the sorted array Half

  while pointera < len(__SCREAMING_SNAKE_CASE    ) and pointera < len(__SCREAMING_SNAKE_CASE    ):
    if left_half[pointera] < right_half[pointera]:
      _lowerCAmelCase						=		left_half[pointera]
      pointera += 1
      index += 1
    else:
      _lowerCAmelCase						=		right_half[pointera]
      pointera += 1
      index += 1
  while pointera < len(__SCREAMING_SNAKE_CASE    ):
    _lowerCAmelCase						=		left_half[pointera]
    pointera += 1
    index += 1

  while pointera < len(__SCREAMING_SNAKE_CASE    ):
    _lowerCAmelCase						=		right_half[pointera]
    pointera += 1
    index += 1

  return sorted_array



def 	_a  (					__SCREAMING_SNAKE_CASE					:  list    ):






  """simple docstring"""




  if len(__SCREAMING_SNAKE_CASE    ) <= 1:
    return array
  # the actual formula to calculate the middle element = left + (right - left) // 2
  # this avoids integer overflow in case of large N
  _lowerCAmelCase						=		0 + (len(__SCREAMING_SNAKE_CASE    ) - 0) // 2

  # Split the array into halves till the array length becomes equal to One
  # merge the arrays of single length returned by mergeSort function and
  # pass them into the merge arrays function which merges the array
  _lowerCAmelCase						=		array[:middle]
  _lowerCAmelCase						=		array[middle:]

  return merge(merge_sort(__SCREAMING_SNAKE_CASE    )		,				merge_sort(__SCREAMING_SNAKE_CASE    )    )


if __name__ == "__main__":
       import doctest

       doctest.testmod()
