


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')

a__  : List[str]				=	'K-MEANS-CLUST/ '







def _UpperCamelCase	(					__A				,      __A				,      __A=None   )							->		Optional[int]:


      '''simple docstring'''



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

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

      # 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.
      UpperCamelCase__  =    data[rand_indices, :]

      return centroids







def _UpperCamelCase	(					__A				,      __A   )							->		List[str]:


      '''simple docstring'''



      return pairwise_distances(__A				,      __A				,      metric="euclidean"   )







def _UpperCamelCase	(					__A				,      __A   )							->		Optional[Any]:


      '''simple docstring'''



      UpperCamelCase__  =    centroid_pairwise_dist(__A				,      __A   )

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

      return cluster_assignment







def _UpperCamelCase	(					__A				,      __A				,      __A   )							->		Dict:


      '''simple docstring'''



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

      return new_centroids







def _UpperCamelCase	(					__A				,      __A				,      __A				,      __A   )							->		int:


      '''simple docstring'''



      UpperCamelCase__  =    0.0
      for i in range(__A   ):
            # Select all data points that belong to cluster i. Fill in the blank (RHS only)
            UpperCamelCase__  =    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)
                  UpperCamelCase__  =    pairwise_distances(
                      __A				,      [centroids[i]]				,      metric="euclidean"   )
                  UpperCamelCase__  =    distances**2
                  heterogeneity += np.sum(__A   )

      return heterogeneity







def _UpperCamelCase	(					__A				,      __A   )							->		str:


      '''simple docstring'''



      plt.figure(figsize=(7, 4)   )
      plt.plot(__A				,      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 _UpperCamelCase	(					__A				,      __A				,      __A				,      __A=500				,      __A=None				,      __A=False   )							->		Any:


      '''simple docstring'''



      UpperCamelCase__  =    initial_centroids[:]
      UpperCamelCase__  =    None

      for itr in range(__A   ):
            if verbose:
                  print(__A				,      end=""   )

            # 1. Make cluster assignments using nearest centroids
            UpperCamelCase__  =    assign_clusters(__A				,      __A   )

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

            # 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:
                  UpperCamelCase__  =    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
                  UpperCamelCase__  =    compute_heterogeneity(__A				,      __A				,      __A				,      __A   )
                  record_heterogeneity.append(__A   )

            UpperCamelCase__  =    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

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







def _UpperCamelCase	(					__A				,      __A				,      __A=None   )							->		pd.DataFrame:


      '''simple docstring'''



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


if __name__ == "__main__":
  import doctest

  doctest.testmod()









'''simple docstring'''







from itertools import permutations







def _UpperCamelCase	(					)							->		Optional[int]:


      '''simple docstring'''



      UpperCamelCase__  =    list(map("".join				,      permutations("0123456789"   )   )   )
      return result[999999]


if __name__ == "__main__":
  print(solution())





