



'''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						:		Any						      = '''K-MEANS-CLUST/ '''



def 	__lowerCAmelCase       (				lowerCamelCase :    Any					,		lowerCamelCase :    Dict					,		lowerCamelCase :    int=None       ):






	'''simple docstring'''




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

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

	return centroids



def 	__lowerCAmelCase       (				lowerCamelCase :    Union[str, Any]					,		lowerCamelCase :    str       ):






	'''simple docstring'''




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



def 	__lowerCAmelCase       (				lowerCamelCase :    List[str]					,		lowerCamelCase :    Union[str, Any]       ):






	'''simple docstring'''




	__lowerCAmelCase       				=	centroid_pairwise_dist(lowerCamelCase					,		lowerCamelCase       )

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

	return cluster_assignment



def 	__lowerCAmelCase       (				lowerCamelCase :    Union[str, Any]					,		lowerCamelCase :    str					,		lowerCamelCase :    str       ):






	'''simple docstring'''




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

	return new_centroids



def 	__lowerCAmelCase       (				lowerCamelCase :    List[Any]					,		lowerCamelCase :    List[str]					,		lowerCamelCase :    List[str]					,		lowerCamelCase :    Optional[Any]       ):






	'''simple docstring'''




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

	return heterogeneity



def 	__lowerCAmelCase       (				lowerCamelCase :    Any					,		lowerCamelCase :    List[str]       ):






	'''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 	__lowerCAmelCase       (				lowerCamelCase :    Union[str, Any]					,		lowerCamelCase :    Dict					,		lowerCamelCase :    Union[str, Any]					,		lowerCamelCase :    Optional[int]=5_00					,		lowerCamelCase :    List[str]=None					,		lowerCamelCase :    Dict=False       ):






	'''simple docstring'''




	__lowerCAmelCase       				=	initial_centroids[:]
	__lowerCAmelCase       				=	None

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

		# 1. Make cluster assignments using nearest centroids
		__lowerCAmelCase       				=	assign_clusters(lowerCamelCase					,		lowerCamelCase       )

		# 2. Compute a new centroid for each of the k clusters, averaging all data
		#    points assigned to that cluster.
		__lowerCAmelCase       				=	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       				=	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       				=	compute_heterogeneity(lowerCamelCase					,		lowerCamelCase					,		lowerCamelCase					,		lowerCamelCase       )
			record_heterogeneity.append(lowerCamelCase       )

		__lowerCAmelCase       				=	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						:		Union[str, Any]						      = ds.load_iris()
	lowerCAmelCase						:		int						      = 3
	lowerCAmelCase						:		Dict						      = []
	lowerCAmelCase						:		Tuple						      = get_initial_centroids(dataset['''data'''], k, seed=0)
	lowerCAmelCase      ,   lowerCAmelCase						:		Union[str, Any]						      = kmeans(
	    dataset['''data'''],
	    k,
	    initial_centroids,
	    maxiter=4_0_0,
	    record_heterogeneity=heterogeneity,
	    verbose=True,
	)
	plot_heterogeneity(heterogeneity, k)



def 	__lowerCAmelCase       (				lowerCamelCase :    pd.DataFrame					,		lowerCamelCase :    np.ndarray					,		lowerCamelCase :    Any=None       ):






	'''simple docstring'''




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


if __name__ == "__main__":
	import doctest

	doctest.testmod()




'''simple docstring'''



def 	__lowerCAmelCase       (				lowerCamelCase :    float					,		lowerCamelCase :    float       ):






	'''simple docstring'''




	__lowerCAmelCase       				=	float()
	try:
		__lowerCAmelCase       				=	mass * acceleration
	except Exception:
		return -0.0
	return force


if __name__ == "__main__":
	import doctest

	# run doctest
	doctest.testmod()

	# demo
	lowerCAmelCase						:		List[Any]						      = 12.5
	lowerCAmelCase						:		Optional[Any]						      = 1_0
	lowerCAmelCase						:		str						      = newtons_second_law_of_motion(mass, acceleration)
	print('''The force is ''', force, '''N''')