





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

__A    :   Optional[int]          =       "K-MEANS-CLUST/ "





def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__=None			)  ->    List[str]:







			'''simple docstring'''

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

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

			return centroids





def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__			)  ->    Union[str, Any]:







			'''simple docstring'''

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





def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__			)  ->    int:







			'''simple docstring'''

			UpperCAmelCase       		=    centroid_pairwise_dist(UpperCamelCase__      ,      UpperCamelCase__			)

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

			return cluster_assignment





def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__			)  ->    Dict:







			'''simple docstring'''

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

			return new_centroids





def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__			)  ->    Union[str, Any]:







			'''simple docstring'''

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

			return heterogeneity





def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__			)  ->    str:







			'''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 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__=500      ,      UpperCamelCase__=None      ,      UpperCamelCase__=False			)  ->    Any:







			'''simple docstring'''

			UpperCAmelCase       		=    initial_centroids[:]
			UpperCAmelCase       		=    None

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

						# 1. Make cluster assignments using nearest centroids
						UpperCAmelCase       		=    assign_clusters(UpperCamelCase__      ,      UpperCamelCase__			)

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

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

				__A    :   Tuple          =       ds.load_iris()
				__A    :   Dict          =       3
				__A    :   List[str]          =       []
				__A    :   int          =       get_initial_centroids(dataset["data"], k, seed=0)
				__A   ,			__A    :   Union[str, Any]          =       kmeans(
				    dataset["data"],
				    k,
				    initial_centroids,
				    maxiter=400,
				    record_heterogeneity=heterogeneity,
				    verbose=True,
				)
				plot_heterogeneity(heterogeneity, k)





def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__=None			)  ->    pd.DataFrame:







			'''simple docstring'''

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


if __name__ == "__main__":
				import doctest

				doctest.testmod()










import textwrap

import pyarrow as pa
import pytest

from datasets import Features, Value
from datasets.packaged_modules.json.json import Json





@pytest.fixture
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__			)  ->    str:







			'''simple docstring'''

			UpperCAmelCase       		=    tmp_path / '''file.jsonl'''
			UpperCAmelCase       		=    textwrap.dedent(
			    '''\
        {"col_1": -1}
        {"col_1": 1, "col_2": 2}
        {"col_1": 10, "col_2": 20}
        '''			)
			with open(UpperCamelCase__      ,      '''w'''			) as f:
						f.write(UpperCamelCase__			)
			return str(UpperCamelCase__			)





@pytest.fixture
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__			)  ->    Union[str, Any]:







			'''simple docstring'''

			UpperCAmelCase       		=    tmp_path / '''file_utf16_encoded.jsonl'''
			UpperCAmelCase       		=    textwrap.dedent(
			    '''\
        {"col_1": -1}
        {"col_1": 1, "col_2": 2}
        {"col_1": 10, "col_2": 20}
        '''			)
			with open(UpperCamelCase__      ,      '''w'''      ,      encoding='''utf-16'''			) as f:
						f.write(UpperCamelCase__			)
			return str(UpperCamelCase__			)





@pytest.fixture
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__			)  ->    Optional[Any]:







			'''simple docstring'''

			UpperCAmelCase       		=    tmp_path / '''file_with_list_of_dicts.json'''
			UpperCAmelCase       		=    textwrap.dedent(
			    '''\
        [
            {"col_1": -1},
            {"col_1": 1, "col_2": 2},
            {"col_1": 10, "col_2": 20}
        ]
        '''			)
			with open(UpperCamelCase__      ,      '''w'''			) as f:
						f.write(UpperCamelCase__			)
			return str(UpperCamelCase__			)





@pytest.fixture
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__			)  ->    int:







			'''simple docstring'''

			UpperCAmelCase       		=    tmp_path / '''file_with_list_of_dicts_field.json'''
			UpperCAmelCase       		=    textwrap.dedent(
			    '''\
        {
            "field1": 1,
            "field2": "aabb",
            "field3": [
                {"col_1": -1},
                {"col_1": 1, "col_2": 2},
                {"col_1": 10, "col_2": 20}
            ]
        }
        '''			)
			with open(UpperCamelCase__      ,      '''w'''			) as f:
						f.write(UpperCamelCase__			)
			return str(UpperCamelCase__			)





@pytest.mark.parametrize(
    '''file_fixture, config_kwargs'''      ,      [
        ('''jsonl_file''', {}),
        ('''jsonl_file_utf16_encoded''', {'''encoding''': '''utf-16'''}),
        ('''json_file_with_list_of_dicts''', {}),
        ('''json_file_with_list_of_dicts_field''', {'''field''': '''field3'''}),
    ]      ,      )
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__			)  ->    Dict:







			'''simple docstring'''

			UpperCAmelCase       		=    Json(**UpperCamelCase__			)
			UpperCAmelCase       		=    json._generate_tables([[request.getfixturevalue(UpperCamelCase__			)]]			)
			UpperCAmelCase       		=    pa.concat_tables([table for _, table in generator]			)
			assert pa_table.to_pydict() == {"col_1": [-1, 1, 10], "col_2": [None, 2, 20]}






@pytest.mark.parametrize(
    '''file_fixture, config_kwargs'''      ,      [
        (
            '''jsonl_file''',
            {'''features''': Features({'''col_1''': Value('''int64'''			), '''col_2''': Value('''int64'''			), '''missing_col''': Value('''string'''			)}			)},
        ),
        (
            '''json_file_with_list_of_dicts''',
            {'''features''': Features({'''col_1''': Value('''int64'''			), '''col_2''': Value('''int64'''			), '''missing_col''': Value('''string'''			)}			)},
        ),
        (
            '''json_file_with_list_of_dicts_field''',
            {
                '''field''': '''field3''',
                '''features''': Features(
                    {'''col_1''': Value('''int64'''			), '''col_2''': Value('''int64'''			), '''missing_col''': Value('''string'''			)}			),
            },
        ),
    ]      ,      )
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__			)  ->    List[Any]:







			'''simple docstring'''

			UpperCAmelCase       		=    Json(**UpperCamelCase__			)
			UpperCAmelCase       		=    json._generate_tables([[request.getfixturevalue(UpperCamelCase__			)]]			)
			UpperCAmelCase       		=    pa.concat_tables([table for _, table in generator]			)
			assert pa_table.to_pydict() == {"col_1": [-1, 1, 10], "col_2": [None, 2, 20], "missing_col": [None, None, None]}



