




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

_lowerCamelCase	:      List[str]   =							"""K-MEANS-CLUST/ """

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase=None						):




	"""simple docstring"""






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

	# Pick K indices from range [0, N).
	A_	:					Union[str, Any]						 =		np.random.randint(0	,   _UpperCAmelCase	,   _UpperCAmelCase						)

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

	return centroids

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






	return pairwise_distances(_UpperCAmelCase	,   _UpperCAmelCase	,   metric='''euclidean'''						)

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






	A_	:					str						 =		centroid_pairwise_dist(_UpperCAmelCase	,   _UpperCAmelCase						)

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

	return cluster_assignment

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






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

	return new_centroids

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






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

	return heterogeneity

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






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




	"""simple docstring"""






	A_	:					List[str]						 =		initial_centroids[:]
	A_	:					List[str]						 =		None

	for itr in range(_UpperCAmelCase						):
		if verbose:
			print(_UpperCAmelCase	,   end=''''''						)

		# 1. Make cluster assignments using nearest centroids
		A_	:					Union[str, Any]						 =		assign_clusters(_UpperCAmelCase	,   _UpperCAmelCase						)

		# 2. Compute a new centroid for each of the k clusters, averaging all data
		#    points assigned to that cluster.
		A_	:					Union[str, Any]						 =		revise_centroids(_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase						)

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

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

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase	,   _UpperCAmelCase=None						):




	"""simple docstring"""






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


if __name__ == "__main__":
		import doctest

		doctest.testmod()






'''simple docstring'''





from itertools import count
from math import asin, pi, sqrt






def SCREAMING_SNAKE_CASE__  (				snake_case       :				float  )   ->				float:







     """simple docstring"""
     return (
         (1 - 2 * point) * sqrt(point - point**2  ) + 2 * point + asin(sqrt(1 - point  )  )
     ) / 4






def SCREAMING_SNAKE_CASE__  (				snake_case       :				int  )   ->				float:







     """simple docstring"""
     a					:							List[str]							= (circles_number + 1 - sqrt(2 * circles_number  )) / (
         2 * (circles_number**2 + 1)
     )
     a					:							int							= circles_number * intersection_y

     a					:							List[Any]							= intersection_x * intersection_y / 2
     a					:							List[str]							= circle_bottom_arc_integral(
         1 / 2  ) - circle_bottom_arc_integral(snake_case  )

     return triangle_area + concave_region_area






def SCREAMING_SNAKE_CASE__  (				snake_case       :				float = 1 / 1_000  )   ->				int:







     """simple docstring"""
     a					:							str							= (1 - pi / 4) / 4

     for n in count(1  ):
          if concave_triangle_area(snake_case  ) / l_section_area < fraction:
               return n

     return -1


if __name__ == "__main__":
      print(f'''{solution() = }''')

