


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

a__    :   int								=			'K-MEANS-CLUST/ '







def _UpperCamelCase			(	__A ,     __A ,     __A=None       )				->						Tuple:


      '''simple docstring'''



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

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

      # 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 _UpperCamelCase			(	__A ,     __A       )				->						Union[str, Any]:


      '''simple docstring'''



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







def _UpperCamelCase			(	__A ,     __A       )				->						int:


      '''simple docstring'''



      UpperCamelCase__      =							centroid_pairwise_dist(__A ,     __A       )

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

      return cluster_assignment







def _UpperCamelCase			(	__A ,     __A ,     __A       )				->						Union[str, Any]:


      '''simple docstring'''



      UpperCamelCase__      =							[]
      for i in range(__A       ):
            # 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(__A       )
      UpperCamelCase__      =							np.array(__A       )

      return new_centroids







def _UpperCamelCase			(	__A ,     __A ,     __A ,     __A       )				->						int:


      '''simple docstring'''



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

      return heterogeneity







def _UpperCamelCase			(	__A ,     __A       )				->						Tuple:


      '''simple docstring'''



      plt.figure(figsize=(7, 4)       )
      plt.plot(__A ,     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			(	__A ,     __A ,     __A ,     __A=500 ,     __A=None ,     __A=False       )				->						Union[str, Any]:


      '''simple docstring'''



      UpperCamelCase__      =							initial_centroids[:]
      UpperCamelCase__      =							None

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

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

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

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

            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__    :   int								=			ds.load_iris()
  a__    :   List[str]								=			3
  a__    :   Union[str, Any]								=			[]
  a__    :   Union[str, Any]								=			get_initial_centroids(dataset['data'], k, seed=0)
  a__					,					a__    :   int								=			kmeans(
      dataset['data'],
      k,
      initial_centroids,
      maxiter=4_0_0,
      record_heterogeneity=heterogeneity,
      verbose=True,
  )
  plot_heterogeneity(heterogeneity, k)







def _UpperCamelCase			(	__A ,     __A ,     __A=None       )				->						pd.DataFrame:


      '''simple docstring'''



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


if __name__ == "__main__":
  import doctest

  doctest.testmod()









'''simple docstring'''







from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

a__    :   Dict								=			TypeVar('T')
a__    :   Optional[Any]								=			TypeVar('U')
class    lowercase_	(       Generic[T, U]  ):


    def __init__(	self    ,   a    ,   a       ):
          UpperCamelCase__      =							key
          UpperCamelCase__      =							val
          UpperCamelCase__      =							0
          UpperCamelCase__      =							None
          UpperCamelCase__      =							None


    def __repr__(	self       ):
          return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
              self.key    ,   self.val    ,   self.freq    ,   self.next is not None    ,   self.prev is not None       )

class    lowercase_	(       Generic[T, U]  ):


    def __init__(	self       ):
          UpperCamelCase__      =							DoubleLinkedListNode(a    ,   a       )
          UpperCamelCase__      =							DoubleLinkedListNode(a    ,   a       )
          UpperCamelCase__   ,      UpperCamelCase__      =							self.rear, self.head


    def __repr__(	self       ):
          UpperCamelCase__      =							["DoubleLinkedList"]
          UpperCamelCase__      =							self.head
          while node.next is not None:
                rep.append(str(a       )       )
                UpperCamelCase__      =							node.next
          rep.append(str(self.rear       )       )
          return ",\n    ".join(a       )


    def   __a				(	self    ,   a       ):
          UpperCamelCase__      =							self.rear.prev

          # All nodes other than self.head are guaranteed to have non-None previous
          assert previous is not None

          UpperCamelCase__      =							node
          UpperCamelCase__      =							previous
          UpperCamelCase__      =							node
          UpperCamelCase__      =							self.rear
          node.freq += 1
          self._position_node(a       )


    def   __a				(	self    ,   a       ):

          while node.prev is not None and node.prev.freq > node.freq:
                # swap node with previous node
                UpperCamelCase__      =							node.prev

                UpperCamelCase__      =							previous_node.prev
                UpperCamelCase__      =							node.prev
                UpperCamelCase__      =							previous_node
                UpperCamelCase__      =							node


    def   __a				(	self    ,   a       ):

          if node.prev is None or node.next is None:
                return None

          UpperCamelCase__      =							node.next
          UpperCamelCase__      =							node.prev
          UpperCamelCase__      =							None
          UpperCamelCase__      =							None
          return node

class    lowercase_	(       Generic[T, U]  ):
    __UpperCAmelCase       =      {}


    def __init__(	self    ,   a       ):
          UpperCamelCase__      =							DoubleLinkedList()
          UpperCamelCase__      =							capacity
          UpperCamelCase__      =							0
          UpperCamelCase__      =							0
          UpperCamelCase__      =							0
          UpperCamelCase__      =							{}


    def __repr__(	self       ):
          return (
              f'''CacheInfo(hits={self.hits}, misses={self.miss}, '''
              f'''capacity={self.capacity}, current_size={self.num_keys})'''
          )


    def __contains__(	self    ,   a       ):
          return key in self.cache


    def   __a				(	self    ,   a       ):

          if key in self.cache:
                self.hits += 1
                UpperCamelCase__      =							self.cache[key]
                UpperCamelCase__      =							self.list.remove(self.cache[key]       )
                assert node == value_node

                # node is guaranteed not None because it is in self.cache
                assert node is not None
                self.list.add(a       )
                return node.val
          self.miss += 1
          return None


    def   __a				(	self    ,   a    ,   a       ):

          if key not in self.cache:
                if self.num_keys >= self.capacity:
                      # delete first node when over capacity
                      UpperCamelCase__      =							self.list.head.next

                      # guaranteed to have a non-None first node when num_keys > 0
                      # explain to type checker via assertions
                      assert first_node is not None
                      assert first_node.key is not None
                      assert self.list.remove(a       ) is not None
                      # first_node guaranteed to be in list

                      del self.cache[first_node.key]
                      self.num_keys -= 1
                UpperCamelCase__      =							DoubleLinkedListNode(a    ,   a       )
                self.list.add(self.cache[key]       )
                self.num_keys += 1

          else:
                UpperCamelCase__      =							self.list.remove(self.cache[key]       )
                assert node is not None  # node guaranteed to be in list
                UpperCamelCase__      =							value
                self.list.add(a       )


    @classmethod
    def   __a				(	cls    ,   a = 1_28       ):

          def cache_decorator_inner(a       ) -> Callable[..., U]:
                def cache_decorator_wrapper(*a       ) -> U:
                      if func not in cls.decorator_function_to_instance_map:
                            UpperCamelCase__      =							LFUCache(a       )

                      UpperCamelCase__      =							cls.decorator_function_to_instance_map[func].get(args[0]       )
                      if result is None:
                            UpperCamelCase__      =							func(*a       )
                            cls.decorator_function_to_instance_map[func].put(args[0]    ,   a       )
                      return result

                def cache_info() -> LFUCache[T, U]:
                      return cls.decorator_function_to_instance_map[func]

                setattr(a    ,   "cache_info"    ,   a       )  # noqa: B010

                return cache_decorator_wrapper

          return cache_decorator_inner


if __name__ == "__main__":
  import doctest

  doctest.testmod()





