



'''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__						:	Optional[Any]      ,				lowerCAmelCase__						:	Optional[int]      ,				lowerCAmelCase__						:	Union[str, Any]=None			):

			"""simple docstring"""





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

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

			return centroids


def 	lowercase_						( lowerCAmelCase__						:	int      ,				lowerCAmelCase__						:	List[Any]			):

			"""simple docstring"""





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


def 	lowercase_						( lowerCAmelCase__						:	Optional[int]      ,				lowerCAmelCase__						:	Dict			):

			"""simple docstring"""





			__UpperCAmelCase :   Dict    					=  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 	lowercase_						( lowerCAmelCase__						:	Dict      ,				lowerCAmelCase__						:	int      ,				lowerCAmelCase__						:	Dict			):

			"""simple docstring"""





			__UpperCAmelCase :   Optional[Any]    					=  []
			for i in range(lowerCAmelCase__			):
						# Select all data points that belong to cluster i. Fill in the blank (RHS only)
						__UpperCAmelCase :   str    					=  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 :   List[Any]    					=  np.array(lowerCAmelCase__			)

			return new_centroids


def 	lowercase_						( lowerCAmelCase__						:	List[str]      ,				lowerCAmelCase__						:	int      ,				lowerCAmelCase__						:	List[Any]      ,				lowerCAmelCase__						:	Union[str, Any]			):

			"""simple docstring"""





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

			return heterogeneity


def 	lowercase_						( lowerCAmelCase__						:	Optional[Any]      ,				lowerCAmelCase__						:	Tuple			):

			"""simple docstring"""





			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 	lowercase_						( lowerCAmelCase__						:	List[Any]      ,				lowerCAmelCase__						:	List[str]      ,				lowerCAmelCase__						:	str      ,				lowerCAmelCase__						:	str=500      ,				lowerCAmelCase__						:	List[str]=None      ,				lowerCAmelCase__						:	List[Any]=False			):

			"""simple docstring"""





			__UpperCAmelCase :   Tuple    					=  initial_centroids[:]
			__UpperCAmelCase :   str    					=  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 :   List[str]    					=  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 :   Any    					=  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[Any]    					=  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

					_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__						:	str=None			):

			"""simple docstring"""





			if fill_missing_report:
						__UpperCAmelCase :   int    					=  df.fillna(value=lowerCAmelCase__			)
			__UpperCAmelCase :   List[Any]    					=  1
			__UpperCAmelCase :   Union[str, Any]    					=  df.select_dtypes(np.number			).columns
			__UpperCAmelCase :   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__			) * 25 / 100			) : round(len(lowerCAmelCase__			) * 75 / 100			)
			                        ]			)			),
			            ),
			            ("""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)
			__UpperCAmelCase :   Union[str, Any]    					=  report[
			    (report["""Features"""] == """dummy""") & (report["""Type"""] == """count""")
			].copy()  # avoid SettingWithCopyWarning
			__UpperCAmelCase :   str    					=  (
			    """ClusterSize"""  # rename created cluster df to match report column names
			)
			__UpperCAmelCase :   Dict    					=  """# of Customers"""
			__UpperCAmelCase :   Optional[int]    					=  pd.DataFrame(
			    clustersize.iloc[:, 2:].values
			    / clustersize.iloc[:, 2:].values.sum()			)
			__UpperCAmelCase :   List[str]    					=  """% of Customers"""  # rename created cluster df to match report column names
			__UpperCAmelCase :   Tuple    					=  """ClusterProportion"""
			__UpperCAmelCase :   Union[str, Any]    					=  clusterproportion.columns.tolist()
			__UpperCAmelCase :   Any    					=  cols[-2:] + cols[:-2]
			__UpperCAmelCase :   Any    					=  clusterproportion[cols]  # rearrange columns to match report
			__UpperCAmelCase :   str    					=  report.columns
			__UpperCAmelCase :   Dict    					=  pd.DataFrame(
			    abs(
			        report[report["""Type"""] == """count"""].iloc[:, 2:].values
			        - clustersize.iloc[:, 2:].values			)			)  # generating df with count of nan values
			__UpperCAmelCase :   Optional[int]    					=  0
			__UpperCAmelCase :   int    					=  """# of nan"""
			__UpperCAmelCase :   List[Any]    					=  report[
			    report["""Type"""] == """count"""
			].Features.tolist()  # filling values in order to match report
			__UpperCAmelCase :   str    					=  a.columns.tolist()
			__UpperCAmelCase :   List[Any]    					=  cols[-2:] + cols[:-2]
			__UpperCAmelCase :   Optional[int]    					=  a[cols]  # rearrange columns to match report
			__UpperCAmelCase :   Any    					=  report.columns  # rename columns to match report
			__UpperCAmelCase :   Union[str, Any]    					=  report.drop(
			    report[report.Type == """count"""].index			)  # drop count values except cluster size
			__UpperCAmelCase :   Any    					=  pd.concat(
			    [report, a, clustersize, clusterproportion]      ,				axis=0			)  # concat report with clustert size and nan values
			__UpperCAmelCase :   Tuple    					=  report["""Features"""].isin(lowerCAmelCase__			)
			__UpperCAmelCase :   Optional[int]    					=  report.columns.tolist()
			__UpperCAmelCase :   List[Any]    					=  cols[0:2] + cols[-1:] + cols[2:-1]
			__UpperCAmelCase :   Tuple    					=  report[cols]
			__UpperCAmelCase :   List[str]    					=  {
			    """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 :   int    					=  (
			    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 :   str    					=  """"""
			__UpperCAmelCase :   int    					=  report.reset_index()
			__UpperCAmelCase :   Any    					=  report.drop(columns=["""index"""]			)
			return report


if __name__ == "__main__":
					import doctest

					doctest.testmod()









'''simple docstring'''
from .hash_table import HashTable



class _A	(     __SCREAMING_SNAKE_CASE     ):





		def __init__(  self			,							*__UpperCAmelCase			,							**__UpperCAmelCase					)							->  List[Any]:

					'''simple docstring'''
					super().__init__(*__UpperCAmelCase			,							**__UpperCAmelCase					)





		def 				__A							(  self			,							__UpperCAmelCase			,							__UpperCAmelCase=None					)							->  str:

					'''simple docstring'''
					__UpperCAmelCase :   List[str]    					=  1
					__UpperCAmelCase :   Optional[Any]    					=  self.hash_function(key + i * i					)

					while self.values[new_key] is not None and self.values[new_key] != key:
								i += 1
								__UpperCAmelCase :   str    					=  (
								    self.hash_function(key + i * i					)
								    if not self.balanced_factor() >= self.lim_charge
								    else None
								)

								if new_key is None:
											break

					return new_key




