






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






def     lowerCamelCase__				(   __lowerCamelCase      :					Dict  ,		__lowerCamelCase      :					int  ,		__lowerCamelCase      :					Optional[int]=None		):
		if seed is not None:  # useful for obtaining consistent results
				np.random.seed(__lowerCamelCase		)
		__UpperCAmelCase							:     str									=  data.shape[0]  # number of data points

		# Pick K indices from range [0, N).
		__UpperCAmelCase							:     List[str]									=  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.
		__UpperCAmelCase							:     Optional[int]									=  data[rand_indices, :]

		return centroids






def     lowerCamelCase__				(   __lowerCamelCase      :					List[Any]  ,		__lowerCamelCase      :					Any		):
		return pairwise_distances(__lowerCamelCase  ,		__lowerCamelCase  ,		metric="""euclidean"""		)






def     lowerCamelCase__				(   __lowerCamelCase      :					List[Any]  ,		__lowerCamelCase      :					List[Any]		):
		# Compute distances between each data point and the set of centroids:
		# Fill in the blank (RHS only)
		__UpperCAmelCase							:     str									=  centroid_pairwise_dist(__lowerCamelCase  ,		__lowerCamelCase		)

		# Compute cluster assignments for each data point:
		# Fill in the blank (RHS only)
		__UpperCAmelCase							:     Union[str, Any]									=  np.argmin(__lowerCamelCase  ,		axis=1		)

		return cluster_assignment






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

		return new_centroids






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

		return heterogeneity






def     lowerCamelCase__				(   __lowerCamelCase      :					str  ,		__lowerCamelCase      :					Optional[Any]		):
		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""": 16}		)
		plt.show()






def     lowerCamelCase__				(   __lowerCamelCase      :					Union[str, Any]  ,		__lowerCamelCase      :					Any  ,		__lowerCamelCase      :					int  ,		__lowerCamelCase      :					int=500  ,		__lowerCamelCase      :					List[str]=None  ,		__lowerCamelCase      :					str=False		):
		__UpperCAmelCase							:     int									=  initial_centroids[:]
		__UpperCAmelCase							:     Tuple									=  None

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

				# 1. Make cluster assignments using nearest centroids
				__UpperCAmelCase							:     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.
				__UpperCAmelCase							:     Union[str, Any]									=  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:
						__UpperCAmelCase							:     int									=  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							:     List[str]									=  compute_heterogeneity(__lowerCamelCase  ,		__lowerCamelCase  ,		__lowerCamelCase  ,		__lowerCamelCase		)
						record_heterogeneity.append(__lowerCamelCase		)

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






def     lowerCamelCase__				(   __lowerCamelCase      :					pd.DataFrame  ,		__lowerCamelCase      :					np.ndarray  ,		__lowerCamelCase      :					List[str]=None		):
		# Fill missing values with given rules
		if fill_missing_report:
				__UpperCAmelCase							:     Optional[int]									=  df.fillna(value=__lowerCamelCase		)
		__UpperCAmelCase							:     Optional[int]									=  1
		__UpperCAmelCase							:     Dict									=  df.select_dtypes(np.number		).columns
		__UpperCAmelCase							:     Tuple									=  (
		    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		) * 25 / 100		) : round(len(__lowerCamelCase		) * 75 / 100		)
		                        ]		)		),
		            ),
		            ("""mean_with_na""", np.mean),
		            ("""min""", lambda __lowerCamelCase		: x.min()),
		            ("""5%""", lambda __lowerCamelCase		: x.quantile(0.0_5		)),
		            ("""25%""", lambda __lowerCamelCase		: x.quantile(0.2_5		)),
		            ("""50%""", lambda __lowerCamelCase		: x.quantile(0.5_0		)),
		            ("""75%""", lambda __lowerCamelCase		: x.quantile(0.7_5		)),
		            ("""95%""", lambda __lowerCamelCase		: x.quantile(0.9_5		)),
		            ("""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)
		__UpperCAmelCase							:     Optional[Any]									=  report[
		    (report["""Features"""] == """dummy""") & (report["""Type"""] == """count""")
		].copy()  # avoid SettingWithCopyWarning
		__UpperCAmelCase							:     int									=  (
		    """ClusterSize"""  # rename created cluster df to match report column names
		)
		__UpperCAmelCase							:     List[str]									=  """# of Customers"""
		__UpperCAmelCase							:     Optional[Any]									=  pd.DataFrame(
		    clustersize.iloc[:, 2:].values
		    / clustersize.iloc[:, 2:].values.sum()		)
		__UpperCAmelCase							:     Any									=  """% of Customers"""  # rename created cluster df to match report column names
		__UpperCAmelCase							:     Any									=  """ClusterProportion"""
		__UpperCAmelCase							:     Optional[Any]									=  clusterproportion.columns.tolist()
		__UpperCAmelCase							:     List[str]									=  cols[-2:] + cols[:-2]
		__UpperCAmelCase							:     Optional[Any]									=  clusterproportion[cols]  # rearrange columns to match report
		__UpperCAmelCase							:     int									=  report.columns
		__UpperCAmelCase							:     List[str]									=  pd.DataFrame(
		    abs(
		        report[report["""Type"""] == """count"""].iloc[:, 2:].values
		        - clustersize.iloc[:, 2:].values		)		)  # generating df with count of nan values
		__UpperCAmelCase							:     Union[str, Any]									=  0
		__UpperCAmelCase							:     Optional[Any]									=  """# of nan"""
		__UpperCAmelCase							:     Any									=  report[
		    report["""Type"""] == """count"""
		].Features.tolist()  # filling values in order to match report
		__UpperCAmelCase							:     Union[str, Any]									=  a.columns.tolist()
		__UpperCAmelCase							:     Optional[Any]									=  cols[-2:] + cols[:-2]
		__UpperCAmelCase							:     Union[str, Any]									=  a[cols]  # rearrange columns to match report
		__UpperCAmelCase							:     int									=  report.columns  # rename columns to match report
		__UpperCAmelCase							:     Optional[Any]									=  report.drop(
		    report[report.Type == """count"""].index		)  # drop count values except cluster size
		__UpperCAmelCase							:     List[Any]									=  pd.concat(
		    [report, a, clustersize, clusterproportion]  ,		axis=0		)  # concat report with clustert size and nan values
		__UpperCAmelCase							:     Tuple									=  report["""Features"""].isin(__lowerCamelCase		)
		__UpperCAmelCase							:     Any									=  report.columns.tolist()
		__UpperCAmelCase							:     int									=  cols[0:2] + cols[-1:] + cols[2:-1]
		__UpperCAmelCase							:     Tuple									=  report[cols]
		__UpperCAmelCase							:     Tuple									=  {
		    """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							:     Optional[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		)
		)
		__UpperCAmelCase							:     List[str]									=  """"""
		__UpperCAmelCase							:     Dict									=  report.reset_index()
		__UpperCAmelCase							:     Any									=  report.drop(columns=["""index"""]		)
		return report


if __name__ == "__main__":
							import doctest

							doctest.testmod()










def     lowerCamelCase__				(   __lowerCamelCase      :					list		):
  if len(__lowerCamelCase		) <= 1:
    return data
  else:
    return [
        *quick_sort([e for e in data[1:] if e <= data[0]]		),
        data[0],
        *quick_sort([e for e in data[1:] if e > data[0]]		),
    ]


if __name__ == "__main__":
       import doctest

       doctest.testmod()


