


from __future__ import annotations




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		int  ,			__lowerCamelCase:		int  ,			__lowerCamelCase:		int  ):







	'''simple docstring'''



	assert (
	    c % greatest_common_divisor(__lowerCamelCase  ,			__lowerCamelCase  ) == 0
	)  # greatest_common_divisor(a,b) function implemented below
	((lowercase_) ,	(lowercase_) ,	(lowercase_))			 = extended_gcd(__lowerCamelCase  ,			__lowerCamelCase  )  # extended_gcd(a,b) function implemented below
	lowercase_			 = c / d
	return (r * x, r * y)




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		int  ,			__lowerCamelCase:		int  ,			__lowerCamelCase:		int  ,			__lowerCamelCase:		int = 2  ):







	'''simple docstring'''



	((lowercase_) ,	(lowercase_))			 = diophantine(__lowerCamelCase  ,			__lowerCamelCase  ,			__lowerCamelCase  )  # Initial value
	lowercase_			 = greatest_common_divisor(__lowerCamelCase  ,			__lowerCamelCase  )
	lowercase_			 = a // d
	lowercase_			 = b // d

	for i in range(__lowerCamelCase  ):
		lowercase_			 = xa + i * q
		lowercase_			 = ya - i * p
		print(__lowerCamelCase  ,			__lowerCamelCase  )




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		int  ,			__lowerCamelCase:		int  ):







	'''simple docstring'''



	if a < b:
		lowercase_ ,	lowercase_			 = b, a

	while a % b != 0:
		lowercase_ ,	lowercase_			 = b, a % b

	return b




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		int  ,			__lowerCamelCase:		int  ):







	'''simple docstring'''



	assert a >= 0 and b >= 0

	if b == 0:
		lowercase_ ,	lowercase_ ,	lowercase_			 = a, 1, 0
	else:
		((lowercase_) ,	(lowercase_) ,	(lowercase_))			 = extended_gcd(__lowerCamelCase  ,			a % b  )
		lowercase_			 = q
		lowercase_			 = p - q * (a // b)

	assert a % d == 0 and b % d == 0
	assert d == a * x + b * y

	return (d, x, y)


if __name__ == "__main__":
							from doctest import testmod

							testmod(name="""diophantine""", verbose=True)
							testmod(name="""diophantine_all_soln""", verbose=True)
							testmod(name="""extended_gcd""", verbose=True)
							testmod(name="""greatest_common_divisor""", verbose=True)





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

SCREAMING_SNAKE_CASE__       			=				"""K-MEANS-CLUST/ """




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		List[str]  ,			__lowerCamelCase:		List[Any]  ,			__lowerCamelCase:		Tuple=None  ):







	'''simple docstring'''



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

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

	return centroids




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		Union[str, Any]  ,			__lowerCamelCase:		Union[str, Any]  ):







	'''simple docstring'''



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




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		List[str]  ,			__lowerCamelCase:		int  ):







	'''simple docstring'''



	lowercase_			 = centroid_pairwise_dist(__lowerCamelCase  ,			__lowerCamelCase  )

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

	return cluster_assignment




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		Dict  ,			__lowerCamelCase:		str  ,			__lowerCamelCase:		str  ):







	'''simple docstring'''



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

	return new_centroids




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		str  ,			__lowerCamelCase:		str  ,			__lowerCamelCase:		List[Any]  ,			__lowerCamelCase:		Optional[Any]  ):







	'''simple docstring'''



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

	return heterogeneity




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		List[Any]  ,			__lowerCamelCase:		Union[str, Any]  ):







	'''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 SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		int  ,			__lowerCamelCase:		Dict  ,			__lowerCamelCase:		Any  ,			__lowerCamelCase:		str=500  ,			__lowerCamelCase:		Union[str, Any]=None  ,			__lowerCamelCase:		Optional[int]=False  ):







	'''simple docstring'''



	lowercase_			 = initial_centroids[:]
	lowercase_			 = None

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

		# 1. Make cluster assignments using nearest centroids
		lowercase_			 = assign_clusters(__lowerCamelCase  ,			__lowerCamelCase  )

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

		lowercase_			 = 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

							SCREAMING_SNAKE_CASE__       			=				ds.load_iris()
							SCREAMING_SNAKE_CASE__       			=				3
							SCREAMING_SNAKE_CASE__       			=				[]
							SCREAMING_SNAKE_CASE__       			=				get_initial_centroids(dataset["""data"""], k, seed=0)
							SCREAMING_SNAKE_CASE__			,      SCREAMING_SNAKE_CASE__       			=				kmeans(
							    dataset["""data"""],
							    k,
							    initial_centroids,
							    maxiter=4_0_0,
							    record_heterogeneity=heterogeneity,
							    verbose=True,
							)
							plot_heterogeneity(heterogeneity, k)




def SCREAMING_SNAKE_CASE_  (				__lowerCamelCase:		pd.DataFrame  ,			__lowerCamelCase:		np.ndarray  ,			__lowerCamelCase:		str=None  ):







	'''simple docstring'''



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


if __name__ == "__main__":
							import doctest

							doctest.testmod()

