

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






def 					_SCREAMING_SNAKE_CASE		(						snake_case_							,       snake_case_							,       snake_case_=None	):
	if seed is not None:  # useful for obtaining consistent results
		np.random.seed(snake_case_	)
	_lowercase							=     data.shape[0]  # number of data points

	# Pick K indices from range [0, N).
	_lowercase							=     np.random.randint(0							,       snake_case_							,       snake_case_	)

	# 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		(						snake_case_							,       snake_case_	):
	return pairwise_distances(snake_case_							,       snake_case_							,       metric="""euclidean"""	)






def 					_SCREAMING_SNAKE_CASE		(						snake_case_							,       snake_case_	):
	# Compute distances between each data point and the set of centroids:
	# Fill in the blank (RHS only)
	_lowercase							=     centroid_pairwise_dist(snake_case_							,       snake_case_	)

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

	return cluster_assignment






def 					_SCREAMING_SNAKE_CASE		(						snake_case_							,       snake_case_							,       snake_case_	):
	_lowercase							=     []
	for i in range(snake_case_	):
		# 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(snake_case_	)
	_lowercase							=     np.array(snake_case_	)

	return new_centroids






def 					_SCREAMING_SNAKE_CASE		(						snake_case_							,       snake_case_							,       snake_case_							,       snake_case_	):
	_lowercase							=     0.0
	for i in range(snake_case_	):
		# 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(
			    snake_case_							,       [centroids[i]]							,       metric="""euclidean"""	)
			_lowercase							=     distances**2
			heterogeneity += np.sum(snake_case_	)

	return heterogeneity






def 					_SCREAMING_SNAKE_CASE		(						snake_case_							,       snake_case_	):
	plt.figure(figsize=(7, 4)	)
	plt.plot(snake_case_							,       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		(						snake_case_							,       snake_case_							,       snake_case_							,       snake_case_=500							,       snake_case_=None							,       snake_case_=False	):
	_lowercase							=     initial_centroids[:]
	_lowercase							=     None

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

		# 1. Make cluster assignments using nearest centroids
		_lowercase							=     assign_clusters(snake_case_							,       snake_case_	)

		# 2. Compute a new centroid for each of the k clusters, averaging all data
		#    points assigned to that cluster.
		_lowercase							=     revise_centroids(snake_case_							,       snake_case_							,       snake_case_	)

		# 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(snake_case_							,       snake_case_							,       snake_case_							,       snake_case_	)
			record_heterogeneity.append(snake_case_	)

		_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

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






def 					_SCREAMING_SNAKE_CASE		(						snake_case_							,       snake_case_							,       snake_case_=None	):
	# Fill missing values with given rules
	if fill_missing_report:
		_lowercase							=     df.fillna(value=snake_case_	)
	_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 snake_case_	: np.mean(np.nan_to_num(snake_case_	)	)),
	            ("""mean_without_zeros""", lambda snake_case_	: x.replace(0							,       np.NaN	).mean()),
	            (
	                """mean_25-75""",
	                lambda snake_case_	: np.mean(
	                    np.nan_to_num(
	                        sorted(snake_case_	)[
	                            round(len(snake_case_	) * 25 / 100	) : round(len(snake_case_	) * 75 / 100	)
	                        ]	)	),
	            ),
	            ("""mean_with_na""", np.mean),
	            ("""min""", lambda snake_case_	: x.min()),
	            ("""5%""", lambda snake_case_	: x.quantile(0.05	)),
	            ("""25%""", lambda snake_case_	: x.quantile(0.25	)),
	            ("""50%""", lambda snake_case_	: x.quantile(0.50	)),
	            ("""75%""", lambda snake_case_	: x.quantile(0.75	)),
	            ("""95%""", lambda snake_case_	: x.quantile(0.95	)),
	            ("""max""", lambda snake_case_	: x.max()),
	            ("""count""", lambda snake_case_	: x.count()),
	            ("""stdev""", lambda snake_case_	: x.std()),
	            ("""mode""", lambda snake_case_	: x.mode()[0]),
	            ("""median""", lambda snake_case_	: x.median()),
	            ("""# > 0""", lambda snake_case_	: (x > 0).sum()),
	        ]	)
	    .T.reset_index()
	    .rename(index=snake_case_							,       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(snake_case_	)
	_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 snake_case_	: x.Type.map(snake_case_	)							,       Sortera=lambda snake_case_	: list(reversed(range(len(snake_case_	)	)	)	)							,       )
	    .sort_values(["""Sorter1""", """Mark""", """Sorter2"""]							,       ascending=snake_case_	)
	    .drop(["""Sorter1""", """Sorter2"""]							,       axis=1	)
	)
	_lowercase							=     """"""
	_lowercase							=     report.reset_index()
	_lowercase							=     report.drop(columns=["""index"""]	)
	return report


if __name__ == "__main__":
							import doctest

							doctest.testmod()







'''simple docstring'''







from __future__ import annotations

import math
import random






def 					_SCREAMING_SNAKE_CASE		(						snake_case_							,       snake_case_							,       snake_case_	):
	_lowercase							=     d * e - 1
	_lowercase							=     0
	_lowercase							=     0
	while p == 0:
		_lowercase							=     random.randint(2							,       n - 1	)
		_lowercase							=     k
		while True:
			if t % 2 == 0:
				_lowercase							=     t // 2
				_lowercase							=     (g**t) % n
				_lowercase							=     math.gcd(x - 1							,       snake_case_	)
				if x > 1 and y > 1:
					_lowercase							=     y
					_lowercase							=     n // y
					break  # find the correct factors
			else:
				break  # t is not divisible by 2, break and choose another g
	return sorted([p, q]	)


if __name__ == "__main__":
							import doctest

							doctest.testmod()




