






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    UpperCamelCase__  (   UpperCAmelCase    ,	UpperCAmelCase    ,	UpperCAmelCase=None     )     ->		int:







							"""simple docstring"""





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

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

							return centroids






def    UpperCamelCase__  (   UpperCAmelCase    ,	UpperCAmelCase     )     ->		Any:







							"""simple docstring"""





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






def    UpperCamelCase__  (   UpperCAmelCase    ,	UpperCAmelCase     )     ->		List[str]:







							"""simple docstring"""





							_a  :    Tuple			=						centroid_pairwise_dist(UpperCAmelCase    ,	UpperCAmelCase     )

							# Compute cluster assignments for each data point:
							# Fill in the blank (RHS only)
							_a  :    Union[str, Any]			=						np.argmin(UpperCAmelCase    ,	axis=1     )

							return cluster_assignment






def    UpperCamelCase__  (   UpperCAmelCase    ,	UpperCAmelCase    ,	UpperCAmelCase     )     ->		Any:







							"""simple docstring"""





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

							return new_centroids






def    UpperCamelCase__  (   UpperCAmelCase    ,	UpperCAmelCase    ,	UpperCAmelCase    ,	UpperCAmelCase     )     ->		Any:







							"""simple docstring"""





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

							return heterogeneity






def    UpperCamelCase__  (   UpperCAmelCase    ,	UpperCAmelCase     )     ->		Any:







							"""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    UpperCamelCase__  (   UpperCAmelCase    ,	UpperCAmelCase    ,	UpperCAmelCase    ,	UpperCAmelCase=500    ,	UpperCAmelCase=None    ,	UpperCAmelCase=False     )     ->		Optional[int]:







							"""simple docstring"""





							_a  :    List[str]			=						initial_centroids[:]
							_a  :    Optional[int]			=						None

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

														# 1. Make cluster assignments using nearest centroids
														_a  :    str			=						assign_clusters(UpperCAmelCase    ,	UpperCAmelCase     )

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

														_a  :    Optional[Any]			=						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=400,
						    record_heterogeneity=heterogeneity,
						    verbose=True,
						)
						plot_heterogeneity(heterogeneity, k)






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







							"""simple docstring"""





							if fill_missing_report:
														_a  :    int			=						df.fillna(value=UpperCAmelCase     )
							_a  :    Dict			=						1
							_a  :    str			=						df.select_dtypes(np.number     ).columns
							_a  :    Dict			=						(
							    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.0_5     )),
							            ('''25%''', lambda UpperCAmelCase     : x.quantile(0.2_5     )),
							            ('''50%''', lambda UpperCAmelCase     : x.quantile(0.5_0     )),
							            ('''75%''', lambda UpperCAmelCase     : x.quantile(0.7_5     )),
							            ('''95%''', lambda UpperCAmelCase     : x.quantile(0.9_5     )),
							            ('''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)
							_a  :    int			=						report[
							    (report['''Features'''] == '''dummy''') & (report['''Type'''] == '''count''')
							].copy()  # avoid SettingWithCopyWarning
							_a  :    Any			=						(
							    '''ClusterSize'''  # rename created cluster df to match report column names
							)
							_a  :    Tuple			=						'''# of Customers'''
							_a  :    Any			=						pd.DataFrame(
							    clustersize.iloc[:, 2:].values
							    / clustersize.iloc[:, 2:].values.sum()     )
							_a  :    Optional[Any]			=						'''% of Customers'''  # rename created cluster df to match report column names
							_a  :    List[str]			=						'''ClusterProportion'''
							_a  :    Optional[Any]			=						clusterproportion.columns.tolist()
							_a  :    List[Any]			=						cols[-2:] + cols[:-2]
							_a  :    Any			=						clusterproportion[cols]  # rearrange columns to match report
							_a  :    Optional[Any]			=						report.columns
							_a  :    Union[str, Any]			=						pd.DataFrame(
							    abs(
							        report[report['''Type'''] == '''count'''].iloc[:, 2:].values
							        - clustersize.iloc[:, 2:].values     )     )  # generating df with count of nan values
							_a  :    Union[str, Any]			=						0
							_a  :    Tuple			=						'''# of nan'''
							_a  :    Union[str, Any]			=						report[
							    report['''Type'''] == '''count'''
							].Features.tolist()  # filling values in order to match report
							_a  :    Union[str, Any]			=						a.columns.tolist()
							_a  :    Optional[Any]			=						cols[-2:] + cols[:-2]
							_a  :    Dict			=						a[cols]  # rearrange columns to match report
							_a  :    Optional[int]			=						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  :    Optional[Any]			=						report['''Features'''].isin(UpperCAmelCase     )
							_a  :    Dict			=						report.columns.tolist()
							_a  :    Optional[int]			=						cols[0:2] + cols[-1:] + cols[2:-1]
							_a  :    Union[str, Any]			=						report[cols]
							_a  :    List[Any]			=						{
							    '''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 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     )
							)
							_a  :    Dict			=						''''''
							_a  :    List[str]			=						report.reset_index()
							_a  :    Tuple			=						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, Image
from datasets.packaged_modules.text.text import Text

from ..utils import require_pil






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







							"""simple docstring"""





							_a  :    Tuple			=						tmp_path / '''text.txt'''
							_a  :    Dict			=						textwrap.dedent(
							    '''\
        Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
        Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
        Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.
        Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

        Second paragraph:
        Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
        Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
        Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.
        Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
        '''     )
							with open(UpperCAmelCase    ,	'''w'''    ,	encoding='''utf-8'''     ) as f:
														f.write(UpperCAmelCase     )
							return str(UpperCAmelCase     )






@pytest.fixture
def    UpperCamelCase__  (   UpperCAmelCase    ,	UpperCAmelCase     )     ->		Optional[int]:







							"""simple docstring"""





							_a  :    List[Any]			=						tmp_path / '''text_with_image.txt'''
							with open(UpperCAmelCase    ,	'''w'''    ,	encoding='''utf-8'''     ) as f:
														f.write(UpperCAmelCase     )
							return str(UpperCAmelCase     )






@pytest.mark.parametrize('''keep_linebreaks'''    ,	[True, False]     )
def    UpperCamelCase__  (   UpperCAmelCase    ,	UpperCAmelCase     )     ->		Any:







							"""simple docstring"""





							with open(UpperCAmelCase    ,	encoding='''utf-8'''     ) as f:
														_a  :    str			=						f.read().splitlines(keepends=UpperCAmelCase     )
							_a  :    Tuple			=						Text(keep_linebreaks=UpperCAmelCase    ,	encoding='''utf-8'''     )
							_a  :    Optional[Any]			=						text._generate_tables([[text_file]]     )
							_a  :    str			=						pa.concat_tables([table for _, table in generator]     ).to_pydict()['''text''']
							assert generated_content == expected_content






@require_pil
def    UpperCamelCase__  (   UpperCAmelCase     )     ->		List[str]:







							"""simple docstring"""





							with open(UpperCAmelCase    ,	encoding='''utf-8'''     ) as f:
														_a  :    str			=						f.read().splitlines()[0]
							_a  :    Dict			=						Text(encoding='''utf-8'''    ,	features=Features({'''image''': Image()}     )     )
							_a  :    str			=						text._generate_tables([[text_file_with_image]]     )
							_a  :    int			=						pa.concat_tables([table for _, table in generator]     )
							assert pa_table.schema.field('''image'''     ).type == Image()()
							_a  :    Optional[int]			=						pa_table.to_pydict()['''image''']
							assert generated_content == [{"path": image_file, "bytes": None}]







@pytest.mark.parametrize('''sample_by'''    ,	['''line''', '''paragraph''', '''document''']     )
def    UpperCamelCase__  (   UpperCAmelCase    ,	UpperCAmelCase     )     ->		Optional[Any]:







							"""simple docstring"""





							with open(UpperCAmelCase    ,	encoding='''utf-8'''     ) as f:
														_a  :    Any			=						f.read()
							if sample_by == "line":
														_a  :    Any			=						expected_content.splitlines()
							elif sample_by == "paragraph":
														_a  :    Tuple			=						expected_content.split('''\n\n'''     )
							elif sample_by == "document":
														_a  :    Dict			=						[expected_content]
							_a  :    Dict			=						Text(sample_by=UpperCAmelCase    ,	encoding='''utf-8'''    ,	chunksize=100     )
							_a  :    Optional[int]			=						text._generate_tables([[text_file]]     )
							_a  :    List[Any]			=						pa.concat_tables([table for _, table in generator]     ).to_pydict()['''text''']
							assert generated_content == expected_content