


"""simple docstring"""





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    				=      "K-MEANS-CLUST/ "





def     lowercase__	(  lowerCamelCase     :  Tuple				,	lowerCamelCase     :  Optional[Any]				,	lowerCamelCase     :  str=None				)					->     List[str]:
  if seed is not None:  # useful for obtaining consistent results
    np.random.seed(lowerCamelCase				)
  lowerCAmelCase__    :    str								=					data.shape[0]  # number of data points

  # Pick K indices from range [0, N).
  lowerCAmelCase__    :    int								=					np.random.randint(0				,	lowerCamelCase				,	lowerCamelCase				)

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

  return centroids





def     lowercase__	(  lowerCamelCase     :  Union[str, Any]				,	lowerCamelCase     :  List[Any]				)					->     Any:
  return pairwise_distances(lowerCamelCase				,	lowerCamelCase				,	metric="euclidean"				)





def     lowercase__	(  lowerCamelCase     :  Union[str, Any]				,	lowerCamelCase     :  List[Any]				)					->     List[str]:
  # Compute distances between each data point and the set of centroids:
  # Fill in the blank (RHS only)
  lowerCAmelCase__    :    int								=					centroid_pairwise_dist(lowerCamelCase				,	lowerCamelCase				)

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

  return cluster_assignment





def     lowercase__	(  lowerCamelCase     :  List[str]				,	lowerCamelCase     :  Any				,	lowerCamelCase     :  Optional[Any]				)					->     str:
  lowerCAmelCase__    :    List[str]								=					[]
  for i in range(lowerCamelCase				):
    # Select all data points that belong to cluster i. Fill in the blank (RHS only)
    lowerCAmelCase__    :    str								=					data[cluster_assignment == i]
    # Compute the mean of the data points. Fill in the blank (RHS only)
    lowerCAmelCase__    :    Tuple								=					member_data_points.mean(axis=0				)
    new_centroids.append(lowerCamelCase				)
  lowerCAmelCase__    :    Dict								=					np.array(lowerCamelCase				)

  return new_centroids





def     lowercase__	(  lowerCamelCase     :  Union[str, Any]				,	lowerCamelCase     :  Dict				,	lowerCamelCase     :  int				,	lowerCamelCase     :  Union[str, Any]				)					->     Optional[Any]:
  lowerCAmelCase__    :    Dict								=					0.0
  for i in range(lowerCamelCase				):
    # Select all data points that belong to cluster i. Fill in the blank (RHS only)
    lowerCAmelCase__    :    List[Any]								=					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__    :    Tuple								=					pairwise_distances(
          lowerCamelCase				,	[centroids[i]]				,	metric="euclidean"				)
      lowerCAmelCase__    :    int								=					distances**2
      heterogeneity += np.sum(lowerCamelCase				)

  return heterogeneity





def     lowercase__	(  lowerCamelCase     :  List[Any]				,	lowerCamelCase     :  Optional[int]				)					->     str:
  plt.figure(figsize=(7, 4)				)
  plt.plot(lowerCamelCase				,	linewidth=4				)
  plt.xlabel("# Iterations"				)
  plt.ylabel("Heterogeneity"				)
  plt.title(F"Heterogeneity of clustering over time, K={k:d}"				)
  plt.rcParams.update({"font.size": 1_6}				)
  plt.show()





def     lowercase__	(  lowerCamelCase     :  int				,	lowerCamelCase     :  Dict				,	lowerCamelCase     :  int				,	lowerCamelCase     :  Union[str, Any]=5_0_0				,	lowerCamelCase     :  List[str]=None				,	lowerCamelCase     :  List[Any]=False				)					->     Tuple:
  lowerCAmelCase__    :    str								=					initial_centroids[:]
  lowerCAmelCase__    :    Optional[Any]								=					None

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

    # 1. Make cluster assignments using nearest centroids
    lowerCAmelCase__    :    Optional[int]								=					assign_clusters(lowerCamelCase				,	lowerCamelCase				)

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

    # 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__    :    str								=					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__    :    List[str]								=					compute_heterogeneity(lowerCamelCase				,	lowerCamelCase				,	lowerCamelCase				,	lowerCamelCase				)
      record_heterogeneity.append(lowerCamelCase				)

    lowerCAmelCase__    :    Tuple								=					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    				=      ds.load_iris()
   __UpperCAmelCase    				=      3
   __UpperCAmelCase    				=      []
   __UpperCAmelCase    				=      get_initial_centroids(dataset["data"], k, seed=0)
   __UpperCAmelCase				,     __UpperCAmelCase    				=      kmeans(
       dataset["data"],
       k,
       initial_centroids,
       maxiter=400,
       record_heterogeneity=heterogeneity,
       verbose=True,
   )
   plot_heterogeneity(heterogeneity, k)





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


if __name__ == "__main__":
   import doctest

   doctest.testmod()




"""simple docstring"""





from __future__ import annotations

__UpperCAmelCase    				=      [2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]

class  lowercase_  :







      def __init__(      self :							int		,  _lowercase :							int    ):
        lowerCAmelCase__    :    int								=					-1
        lowerCAmelCase__    :    int								=					-1
        lowerCAmelCase__    :    list[int]								=					[-1] * length
        lowerCAmelCase__    :    Node | None								=					None
        lowerCAmelCase__    :    Node | None								=					None







      def __repr__(      self :							List[Any]    ):
        return f"Node(min_value={self.minn} max_value={self.maxx})"





def     lowercase__	(  lowerCamelCase     :  list[int]				)					->     Node | None:
  lowerCAmelCase__    :    Any								=					Node(len(lowerCamelCase				)				)
  lowerCAmelCase__				,		lowerCAmelCase__    :    Any								=					min(lowerCamelCase				), max(lowerCamelCase				)
  # Leaf node case where the node contains only one unique value
  if root.minn == root.maxx:
    return root
  lowerCAmelCase__    :    str								=					(root.minn + root.maxx) // 2

  lowerCAmelCase__    :    list[int]								=					[]
  lowerCAmelCase__    :    list[int]								=					[]

  for index, num in enumerate(lowerCamelCase				):
    if num <= pivot:
      left_arr.append(lowerCamelCase				)
    else:
      right_arr.append(lowerCamelCase				)
    lowerCAmelCase__    :    Optional[Any]								=					len(lowerCamelCase				)
  lowerCAmelCase__    :    List[str]								=					build_tree(lowerCamelCase				)
  lowerCAmelCase__    :    List[Any]								=					build_tree(lowerCamelCase				)
  return root





def     lowercase__	(  lowerCamelCase     :  Node | None				,	lowerCamelCase     :  int				,	lowerCamelCase     :  int				)					->     int:
  if index < 0 or node is None:
    return 0
  # Leaf node cases
  if node.minn == node.maxx:
    return index + 1 if node.minn == num else 0
  lowerCAmelCase__    :    int								=					(node.minn + node.maxx) // 2
  if num <= pivot:
    # go the left subtree and map index to the left subtree
    return rank_till_index(node.left				,	lowerCamelCase				,	node.map_left[index] - 1				)
  else:
    # go to the right subtree and map index to the right subtree
    return rank_till_index(node.right				,	lowerCamelCase				,	index - node.map_left[index]				)





def     lowercase__	(  lowerCamelCase     :  Node | None				,	lowerCamelCase     :  int				,	lowerCamelCase     :  int				,	lowerCamelCase     :  int				)					->     int:
  if start > end:
    return 0
  lowerCAmelCase__    :    int								=					rank_till_index(lowerCamelCase				,	lowerCamelCase				,	lowerCamelCase				)
  lowerCAmelCase__    :    Optional[Any]								=					rank_till_index(lowerCamelCase				,	lowerCamelCase				,	start - 1				)
  return rank_till_end - rank_before_start





def     lowercase__	(  lowerCamelCase     :  Node | None				,	lowerCamelCase     :  int				,	lowerCamelCase     :  int				,	lowerCamelCase     :  int				)					->     int:
  if index > (end - start) or start > end or node is None:
    return -1
  # Leaf node case
  if node.minn == node.maxx:
    return node.minn
  # Number of elements in the left subtree in interval [start, end]
  lowerCAmelCase__    :    List[str]								=					node.map_left[end] - (
      node.map_left[start - 1] if start else 0
  )
  if num_elements_in_left_tree > index:
    return quantile(
        node.left				,	lowerCamelCase				,	(node.map_left[start - 1] if start else 0)				,	node.map_left[end] - 1				,	)
  else:
    return quantile(
        node.right				,	index - num_elements_in_left_tree				,	start - (node.map_left[start - 1] if start else 0)				,	end - node.map_left[end]				,	)





def     lowercase__	(  lowerCamelCase     :  Node | None				,	lowerCamelCase     :  int				,	lowerCamelCase     :  int				,	lowerCamelCase     :  int				,	lowerCamelCase     :  int				)					->     int:
  if (
      start > end
      or node is None
      or start_num > end_num
      or node.minn > end_num
      or node.maxx < start_num
  ):
    return 0
  if start_num <= node.minn and node.maxx <= end_num:
    return end - start + 1
  lowerCAmelCase__    :    List[str]								=					range_counting(
      node.left				,	(node.map_left[start - 1] if start else 0)				,	node.map_left[end] - 1				,	lowerCamelCase				,	lowerCamelCase				,	)
  lowerCAmelCase__    :    List[str]								=					range_counting(
      node.right				,	start - (node.map_left[start - 1] if start else 0)				,	end - node.map_left[end]				,	lowerCamelCase				,	lowerCamelCase				,	)
  return left + right


if __name__ == "__main__":
   import doctest

   doctest.testmod()
