




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

snake_case__          =						"""K-MEANS-CLUST/ """




def 						snake_case__    ( lowerCamelCase__				:   int			,		lowerCamelCase__				:   Optional[Any]			,		lowerCamelCase__				:   int=None			)   ->   List[str]:
					if seed is not None:  # useful for obtaining consistent results
										np.random.seed(__lowerCamelCase			)
					A_ :     int =							data.shape[0]  # number of data points

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

					return centroids




def 						snake_case__    ( lowerCamelCase__				:   List[str]			,		lowerCamelCase__				:   int			)   ->   Optional[int]:
					return pairwise_distances(__lowerCamelCase			,		__lowerCamelCase			,		metric='''euclidean'''			)




def 						snake_case__    ( lowerCamelCase__				:   int			,		lowerCamelCase__				:   int			)   ->   str:
					A_ :     Optional[Any] =							centroid_pairwise_dist(__lowerCamelCase			,		__lowerCamelCase			)

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

					return cluster_assignment




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

					return new_centroids




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

					return heterogeneity




def 						snake_case__    ( lowerCamelCase__				:   Any			,		lowerCamelCase__				:   Tuple			)   ->   Optional[Any]:
					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''': 1_6}			)
					plt.show()




def 						snake_case__    ( lowerCamelCase__				:   int			,		lowerCamelCase__				:   int			,		lowerCamelCase__				:   Tuple			,		lowerCamelCase__				:   Optional[Any]=5_0_0			,		lowerCamelCase__				:   Union[str, Any]=None			,		lowerCamelCase__				:   Tuple=False			)   ->   Union[str, Any]:
					A_ :     Tuple =							initial_centroids[:]
					A_ :     Union[str, Any] =							None

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

										# 1. Make cluster assignments using nearest centroids
										A_ :     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.
										A_ :     Any =							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:
															A_ :     Tuple =							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_ :     str =							compute_heterogeneity(__lowerCamelCase			,		__lowerCamelCase			,		__lowerCamelCase			,		__lowerCamelCase			)
															record_heterogeneity.append(__lowerCamelCase			)

										A_ :     str =							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

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




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


if __name__ == "__main__":
							import doctest

							doctest.testmod()









'''simple docstring'''




from __future__ import annotations

snake_case__          =						[2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]






class     UpperCamelCase_     :







						"""simple docstring"""


						def __init__(     self      :       Dict							, _lowerCamelCase      :       int    ):





											"""simple docstring"""







											A_ :     int =							-1
											A_ :     int =							-1
											A_ :     list[int] =							[-1] * length
											A_ :     Node | None =							None
											A_ :     Node | None =							None







						def __repr__(     self      :       List[str]    ):





											"""simple docstring"""







											return f'Node(min_value={self.minn} max_value={self.maxx})'






def 						snake_case__    ( lowerCamelCase__				:   list[int]			)   ->   Node | None:
					A_ :     Optional[Any] =							Node(len(lowerCamelCase__			)			)
					A_ ,A_ :     str =							min(lowerCamelCase__			), max(lowerCamelCase__			)
					# Leaf node case where the node contains only one unique value
					if root.minn == root.maxx:
										return root
					A_ :     Optional[int] =							(root.minn + root.maxx) // 2

					A_ :     list[int] =							[]
					A_ :     list[int] =							[]

					for index, num in enumerate(lowerCamelCase__			):
										if num <= pivot:
															left_arr.append(lowerCamelCase__			)
										else:
															right_arr.append(lowerCamelCase__			)
										A_ :     Union[str, Any] =							len(lowerCamelCase__			)
					A_ :     Optional[int] =							build_tree(lowerCamelCase__			)
					A_ :     Optional[int] =							build_tree(lowerCamelCase__			)
					return root




def 						snake_case__    ( lowerCamelCase__				:   Node | None			,		lowerCamelCase__				:   int			,		lowerCamelCase__				:   int			)   ->   int:
					if index < 0 or node is None:
										return 0
					# Leaf node cases
					if node.minn == node.maxx:
										return index + 1 if node.minn == num else 0
					A_ :     List[Any] =							(node.minn + node.maxx) // 2
					if num <= pivot:
										# go the left subtree and map index to the left subtree
										return rank_till_index(node.left			,		lowerCamelCase__			,		node.map_left[index] - 1			)
					else:
										# go to the right subtree and map index to the right subtree
										return rank_till_index(node.right			,		lowerCamelCase__			,		index - node.map_left[index]			)




def 						snake_case__    ( lowerCamelCase__				:   Node | None			,		lowerCamelCase__				:   int			,		lowerCamelCase__				:   int			,		lowerCamelCase__				:   int			)   ->   int:
					if start > end:
										return 0
					A_ :     Union[str, Any] =							rank_till_index(lowerCamelCase__			,		lowerCamelCase__			,		lowerCamelCase__			)
					A_ :     Union[str, Any] =							rank_till_index(lowerCamelCase__			,		lowerCamelCase__			,		start - 1			)
					return rank_till_end - rank_before_start




def 						snake_case__    ( lowerCamelCase__				:   Node | None			,		lowerCamelCase__				:   int			,		lowerCamelCase__				:   int			,		lowerCamelCase__				:   int			)   ->   int:
					if index > (end - start) or start > end or node is None:
										return -1
					# Leaf node case
					if node.minn == node.maxx:
										return node.minn
					# Number of elements in the left subtree in interval [start, end]
					A_ :     List[str] =							node.map_left[end] - (
					    node.map_left[start - 1] if start else 0
					)
					if num_elements_in_left_tree > index:
										return quantile(
										    node.left			,		lowerCamelCase__			,		(node.map_left[start - 1] if start else 0)			,		node.map_left[end] - 1			,		)
					else:
										return quantile(
										    node.right			,		index - num_elements_in_left_tree			,		start - (node.map_left[start - 1] if start else 0)			,		end - node.map_left[end]			,		)




def 						snake_case__    ( lowerCamelCase__				:   Node | None			,		lowerCamelCase__				:   int			,		lowerCamelCase__				:   int			,		lowerCamelCase__				:   int			,		lowerCamelCase__				:   int			)   ->   int:
					if (
					    start > end
					    or node is None
					    or start_num > end_num
					    or node.minn > end_num
					    or node.maxx < start_num
					):
										return 0
					if start_num <= node.minn and node.maxx <= end_num:
										return end - start + 1
					A_ :     int =							range_counting(
					    node.left			,		(node.map_left[start - 1] if start else 0)			,		node.map_left[end] - 1			,		lowerCamelCase__			,		lowerCamelCase__			,		)
					A_ :     List[str] =							range_counting(
					    node.right			,		start - (node.map_left[start - 1] if start else 0)			,		end - node.map_left[end]			,		lowerCamelCase__			,		lowerCamelCase__			,		)
					return left + right


if __name__ == "__main__":
							import doctest

							doctest.testmod()



