

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

lowerCamelCase_    =					'''K-MEANS-CLUST/ '''



def    UpperCamelCase(					lowercase_			,					lowercase_			,					lowercase_=None							)	->				Dict:





  '''simple docstring'''





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

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

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

  return centroids



def    UpperCamelCase(					lowercase_			,					lowercase_							)	->				Optional[int]:





  '''simple docstring'''





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



def    UpperCamelCase(					lowercase_			,					lowercase_							)	->				Optional[int]:





  '''simple docstring'''





  snake_case_       						=      centroid_pairwise_dist(lowercase_			,					lowercase_							)

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

  return cluster_assignment



def    UpperCamelCase(					lowercase_			,					lowercase_			,					lowercase_							)	->				Any:





  '''simple docstring'''





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

  return new_centroids



def    UpperCamelCase(					lowercase_			,					lowercase_			,					lowercase_			,					lowercase_							)	->				Tuple:





  '''simple docstring'''





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

  return heterogeneity



def    UpperCamelCase(					lowercase_			,					lowercase_							)	->				Any:





  '''simple docstring'''





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





  '''simple docstring'''





  snake_case_       						=      initial_centroids[:]
  snake_case_       						=      None

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

    # 1. Make cluster assignments using nearest centroids
    snake_case_       						=      assign_clusters(lowercase_			,					lowercase_							)

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

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

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

    lowerCamelCase_    =					ds.load_iris()
    lowerCamelCase_    =					3
    lowerCamelCase_    =					[]
    lowerCamelCase_    =					get_initial_centroids(dataset['''data'''], k, seed=0)
    lowerCamelCase_   ,  lowerCamelCase_    =					kmeans(
        dataset['''data'''],
        k,
        initial_centroids,
        maxiter=400,
        record_heterogeneity=heterogeneity,
        verbose=True,
    )
    plot_heterogeneity(heterogeneity, k)



def    UpperCamelCase(					lowercase_			,					lowercase_			,					lowercase_=None							)	->				pd.DataFrame:





  '''simple docstring'''





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


if __name__ == "__main__":
    import doctest

    doctest.testmod()
'''simple docstring'''


from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize






class      __SCREAMING_SNAKE_CASE						(       lowerCamelCase_       ):







  '''simple docstring'''






  lowerCamelCase_		:Union[str, Any]						    =		1
  lowerCamelCase_		:List[Any]						    =		2
  lowerCamelCase_		:Optional[Any]						    =		3


  def __repr__( self						):




       '''simple docstring'''

       return F'''{self.__class__.__name__}.{self.name}'''







def 					_lowerCamelCase    (      lowerCamelCase_					:							tuple[int, int]	,     lowerCamelCase_					:							int	,     lowerCamelCase_					:							int   ):



     """simple docstring"""





     UpperCAmelCase_   ,			UpperCAmelCase_							:   Any   =      point
     return degrees(atana(y - miny	,     x - minx   )   )


def 					_lowerCamelCase    (      lowerCamelCase_					:							tuple[int, int]	,     lowerCamelCase_					:							tuple[int, int]	,     lowerCamelCase_					:							tuple[int, int]   ):



     """simple docstring"""





     UpperCAmelCase_   ,			UpperCAmelCase_							:   str   =      starting
     UpperCAmelCase_   ,			UpperCAmelCase_							:   Optional[int]   =      via
     UpperCAmelCase_   ,			UpperCAmelCase_							:   Dict   =      target
     UpperCAmelCase_							:   Optional[Any]   =      degrees(atana(ya - ya	,     xa - xa   )   )
     via_angle %= 360
     UpperCAmelCase_							:   Optional[Any]   =      degrees(atana(ya - ya	,     xa - xa   )   )
     target_angle %= 360
     # t-
     #  \ \
     #   \ v
     #    \|
     #     s
     # via_angle is always lower than target_angle, if direction is left.
     # If they are same, it means they are on a same line of convex hull.
     if target_angle > via_angle:
          return Direction.left
     elif target_angle == via_angle:
          return Direction.straight
     else:
          return Direction.right





def 					_lowerCamelCase    (      lowerCamelCase_					:							list[tuple[int, int]]   ):



     """simple docstring"""





     if len(lowerCamelCase_   ) <= 2:
          # There is no convex hull
          raise ValueError('graham_scan: argument must contain more than 3 points.'   )
     if len(lowerCamelCase_   ) == 3:
          return points
     # find the lowest and the most left point
     UpperCAmelCase_							:   Dict   =      0
     UpperCAmelCase_   ,			UpperCAmelCase_							:   Union[str, Any]   =      maxsize, maxsize
     for i, point in enumerate(lowerCamelCase_   ):
          UpperCAmelCase_							:   Union[str, Any]   =      point[0]
          UpperCAmelCase_							:   List[Any]   =      point[1]
          if y < miny:
               UpperCAmelCase_							:   Dict   =      y
               UpperCAmelCase_							:   Optional[int]   =      x
               UpperCAmelCase_							:   Optional[Any]   =      i
          if y == miny and x < minx:
               UpperCAmelCase_							:   Union[str, Any]   =      x
               UpperCAmelCase_							:   Dict   =      i

    # remove the lowest and the most left point from points for preparing for sort
     points.pop(lowerCamelCase_   )

     UpperCAmelCase_							:   List[str]   =      sorted(lowerCamelCase_	,     key=lambda lowerCamelCase_   : angle_comparer(lowerCamelCase_	,     lowerCamelCase_	,     lowerCamelCase_   )   )
     # This insert actually costs complexity,
     # and you should instead add (minx, miny) into stack later.
     # I'm using insert just for easy understanding.
     sorted_points.insert(0	,     (minx, miny)   )

     UpperCAmelCase_							:   deque[tuple[int, int]]   =      deque()
     stack.append(sorted_points[0]   )
     stack.append(sorted_points[1]   )
     stack.append(sorted_points[2]   )
     # In any ways, the first 3 points line are towards left.
     # Because we sort them the angle from minx, miny.
     UpperCAmelCase_							:   List[Any]   =      Direction.left

     for i in range(3	,     len(lowerCamelCase_   )   ):
          while True:
               UpperCAmelCase_							:   Optional[Any]   =      stack[-2]
               UpperCAmelCase_							:   Optional[int]   =      stack[-1]
               UpperCAmelCase_							:   str   =      sorted_points[i]
               UpperCAmelCase_							:   Union[str, Any]   =      check_direction(lowerCamelCase_	,     lowerCamelCase_	,     lowerCamelCase_   )

               if next_direction == Direction.left:
                    UpperCAmelCase_							:   Union[str, Any]   =      Direction.left
                    break
               if next_direction == Direction.straight:
                    if current_direction == Direction.left:
                         # We keep current_direction as left.
                         # Because if the straight line keeps as straight,
                         # we want to know if this straight line is towards left.
                         break
                    elif current_direction == Direction.right:
                         # If the straight line is towards right,
                         # every previous points on those straigh line is not convex hull.
                         stack.pop()
               if next_direction == Direction.right:
                    stack.pop()
          stack.append(sorted_points[i]   )
     return list(lowerCamelCase_   )






