<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 <p style="text-align
Step2:  1. Implementar o algoritmo K-means
Nesta etapa você irá implementar as funções que compõe o algoritmo do KMeans uma a uma. É importante entender e ler a documentação de cada função, principalmente as dimensões dos dados esperados na saída.
1.1 Inicializar os centróides
A primeira etapa do algoritmo consiste em inicializar os centróides de maneira aleatória. Essa etapa é uma das mais importantes do algoritmo e uma boa inicialização pode diminuir bastante o tempo de convergência.
Para inicializar os centróides você pode considerar o conhecimento prévio sobre os dados, mesmo sem saber a quantidade de grupos ou sua distribuição. 
Dica
Step3:  Teste a função criada e visualize os centróides que foram calculados.
Step5:  1.2 Definir os clusters
Na segunda etapa do algoritmo serão definidos o grupo de cada dado, de acordo com os centróides calculados.
1.2.1 Função de distância
Codifique a função de distância euclidiana entre dois pontos (a, b).
Definido pela equação
Step6:  Teste a função criada.
Step8:  1.2.2 Calcular o centroide mais próximo
Utilizando a função de distância codificada anteriormente, complete a função abaixo para calcular o centroid mais próximo de um ponto qualquer. 
Dica
Step9:  Teste a função criada
Step11:  1.2.3 Calcular centroid mais próximo de cada dado do dataset
Utilizando a função anterior que retorna o índice do centroid mais próximo, calcule o centroid mais próximo de cada dado do dataset.
Step12:  Teste a função criada visualizando os cluster formados.
Step14:  1.3 Métrica de avaliação
Após formar os clusters, como sabemos se o resultado gerado é bom? Para isso, precisamos definir uma métrica de avaliação.
O algoritmo K-means tem como objetivo escolher centróides que minimizem a soma quadrática das distância entre os dados de um cluster e seu centróide. Essa métrica é conhecida como inertia.
$$\sum_{i=0}^{n}\min_{c_j \in C}(||x_i - c_j||^2)$$
A inertia, ou o critério de soma dos quadrados dentro do cluster, pode ser reconhecido como uma medida de o quão internamente coerentes são os clusters, porém ela sofre de alguns inconvenientes
Step15:  Teste a função codificada executando o código abaixo.
Step17:  1.4 Atualizar os clusters
Nessa etapa, os centróides são recomputados. O novo valor de cada centróide será a media de todos os dados atribuídos ao cluster.
Step18:  Visualize os clusters formados
Step19:  Execute a função de atualização e visualize novamente os cluster formados
Step26:  2. K-means
2.1 Algoritmo completo
Utilizando as funções codificadas anteriormente, complete a classe do algoritmo K-means!
Step27:  Verifique o resultado do algoritmo abaixo!
Step28:  2.2 Comparar com algoritmo do Scikit-Learn
Use a implementação do algoritmo do scikit-learn do K-means para o mesmo conjunto de dados. Mostre o valor da inércia  e os conjuntos gerados pelo modelo. Você pode usar a mesma estrutura da célula de código anterior.
Dica
Step29:  3. Método do cotovelo
Implemete o método do cotovelo e mostre o melhor K para o conjunto de dados.
Step30:  4. Dataset Real
Exercícios
1 - Aplique o algoritmo do K-means desenvolvido por você no datatse iris [1]. Mostre os resultados obtidos utilizando pelo menos duas métricas de avaliação de clusteres [2].
[1] http
<ASSISTANT_TASK:>
Python Code:
# import libraries
import math
# linear algebra
import numpy as np 
# data processing
import pandas as pd 
# data visualization
from matplotlib import pyplot as plt 
from sklearn import cluster
# load the data with pandas
dataset = pd.read_csv('dataset.csv', header=None)
dataset = np.array(dataset)
plt.scatter(dataset[:,0], dataset[:,1], s=10)
plt.show()
Explanation: <p style="text-align: center;">Clusterização e algoritmo K-means</p>
Organizar dados em agrupamentos é um dos modos mais fundamentais de compreensão e aprendizado. Como por exemplo, os organismos em um sistema biologico são classificados em domínio, reino, filo, classe, etc. A análise de agrupamento é o estudo formal de métodos e algoritmos para agrupar objetos de acordo com medidas ou características semelhantes. A análise de cluster, em sua essência, não utiliza rótulos de categoria que marcam objetos com identificadores anteriores, ou seja, rótulos de classe. A ausência de informação de categoria distingue o agrupamento de dados (aprendizagem não supervisionada) da classificação ou análise discriminante (aprendizagem supervisionada). O objetivo da clusterização é encontrar estruturas em dados e, portanto, é de natureza exploratória. 
A técnica de Clustering tem uma longa e rica história em uma variedade de campos científicos. Um dos algoritmos de clusterização mais populares e simples, o K-means, foi publicado pela primeira vez em 1955. Apesar do K-means ter sido proposto há mais de 50 anos e milhares de algoritmos de clustering terem sido publicados desde então, o K-means é ainda amplamente utilizado.
Fonte: Anil K. Jain, Data clustering: 50 years beyond K-means, Pattern Recognition Letters, Volume 31, Issue 8, 2010
Objetivo
Implementar as funções do algoritmo KMeans passo-a-passo
Comparar a implementação com o algoritmo do Scikit-Learn
Entender e codificar o Método do Cotovelo
Utilizar o K-means em um dataset real 
Carregando os dados de teste
Carregue os dados disponibilizados, e identifique visualmente em quantos grupos os dados parecem estar distribuídos.
End of explanation
def calculate_initial_centers(dataset, k):
    
    Inicializa os centróides iniciais de maneira arbitrária 
    
    Argumentos:
    dataset -- Conjunto de dados - [m,n]
    k -- Número de centróides desejados
    
    Retornos:
    centroids -- Lista com os centróides calculados - [k,n]
    
    
    #### CODE HERE ####
    m,n = np.shape(dataset)
    minimum = np.min(dataset)
    maximum = np.max(dataset)
    
    centroids = np.random.uniform(low=minimum,high=maximum,size=(k,n))
    
    ### END OF CODE ###
    
    return centroids
Explanation: 1. Implementar o algoritmo K-means
Nesta etapa você irá implementar as funções que compõe o algoritmo do KMeans uma a uma. É importante entender e ler a documentação de cada função, principalmente as dimensões dos dados esperados na saída.
1.1 Inicializar os centróides
A primeira etapa do algoritmo consiste em inicializar os centróides de maneira aleatória. Essa etapa é uma das mais importantes do algoritmo e uma boa inicialização pode diminuir bastante o tempo de convergência.
Para inicializar os centróides você pode considerar o conhecimento prévio sobre os dados, mesmo sem saber a quantidade de grupos ou sua distribuição. 
Dica: https://docs.scipy.org/doc/numpy/reference/generated/numpy.random.uniform.html
End of explanation
k = 3
centroids = calculate_initial_centers(dataset, k)
#print(centroids)
plt.scatter(dataset[:,0], dataset[:,1], s=10)
plt.scatter(centroids[:,0], centroids[:,1], marker='^', c='red',s=100)
plt.show()
Explanation: Teste a função criada e visualize os centróides que foram calculados.
End of explanation
def euclidean_distance(a, b):
    
    Calcula a distância euclidiana entre os pontos a e b
    
    Argumentos:
    a -- Um ponto no espaço - [1,n]
    b -- Um ponto no espaço - [1,n]
    
    Retornos:
    distance -- Distância euclidiana entre os pontos
    
    
    #### CODE HERE ####
    
    dist = 0
    
    for ai,bi in zip(a,b):
        dist = dist + (ai - bi)**2
    distance = math.sqrt(dist)
    ### END OF CODE ###
    
    return distance
Explanation: 1.2 Definir os clusters
Na segunda etapa do algoritmo serão definidos o grupo de cada dado, de acordo com os centróides calculados.
1.2.1 Função de distância
Codifique a função de distância euclidiana entre dois pontos (a, b).
Definido pela equação:
$$ dist(a, b) = \sqrt{(a_1-b_1)^{2}+(a_2-b_2)^{2}+ ... + (a_n-b_n)^{2}} $$
$$ dist(a, b) = \sqrt{\sum_{i=1}^{n}(a_i-b_i)^{2}} $$
End of explanation
a = np.array([1, 5, 9])
b = np.array([3, 7, 8])
if (euclidean_distance(a,b) == 3):
    print("Distância calculada corretamente!")
else:
    print("Função de distância incorreta")
Explanation: Teste a função criada.
End of explanation
def nearest_centroid(a, centroids):
    
    Calcula o índice do centroid mais próximo ao ponto a
    
    Argumentos:
    a -- Um ponto no espaço - [1,n]
    centroids -- Lista com os centróides - [k,n]
    
    Retornos:
    nearest_index -- Índice do centróide mais próximo
    
    
    #### CODE HERE ####
    distances = []
    
    
    
    r,c = np.shape(centroids)
    if r == 1:
        euc = euclidean_distance(a,centroids[0])
        distances.append(euc)
        nearest_index = 0 
        
    else:
        
        for centroid in centroids:
            euc = euclidean_distance(a,centroid)
            distances.append(euc)
        #print(distances)    
        nearest_index = np.argmin(distances)    
        ### END OF CODE ###
    
    return nearest_index
Explanation: 1.2.2 Calcular o centroide mais próximo
Utilizando a função de distância codificada anteriormente, complete a função abaixo para calcular o centroid mais próximo de um ponto qualquer. 
Dica: https://docs.scipy.org/doc/numpy/reference/generated/numpy.argmin.html
End of explanation
# Seleciona um ponto aleatório no dataset
index = np.random.randint(dataset.shape[0])
a = dataset[index,:]
# Usa a função para descobrir o centroid mais próximo
idx_nearest_centroid = nearest_centroid(a, centroids)
# Plota os dados ------------------------------------------------
plt.scatter(dataset[:,0], dataset[:,1], s=10)
# Plota o ponto aleatório escolhido em uma cor diferente
plt.scatter(a[0], a[1], c='magenta', s=30)
# Plota os centroids
plt.scatter(centroids[:,0], centroids[:,1], marker='^', c='red', s=100)
# Plota o centroid mais próximo com uma cor diferente
plt.scatter(centroids[idx_nearest_centroid,0], 
            centroids[idx_nearest_centroid,1],
            marker='^', c='springgreen', s=100)
# Cria uma linha do ponto escolhido para o centroid selecionado
plt.plot([a[0], centroids[idx_nearest_centroid,0]], 
         [a[1], centroids[idx_nearest_centroid,1]],c='orange')
plt.annotate('CENTROID', (centroids[idx_nearest_centroid,0], 
            centroids[idx_nearest_centroid,1],))
plt.show()
Explanation: Teste a função criada
End of explanation
def all_nearest_centroids(dataset, centroids):
    
    Calcula o índice do centroid mais próximo para cada 
    ponto do dataset
    
    Argumentos:
    dataset -- Conjunto de dados - [m,n]
    centroids -- Lista com os centróides - [k,n]
    
    Retornos:
    nearest_indexes -- Índices do centróides mais próximos - [m,1]
    
    
    #### CODE HERE ####
    nearest_indexes = []
    for data in dataset:
        near = nearest_centroid(data,centroids)
        nearest_indexes.append(near)
    
      
    ### END OF CODE ###
    
    return nearest_indexes
Explanation: 1.2.3 Calcular centroid mais próximo de cada dado do dataset
Utilizando a função anterior que retorna o índice do centroid mais próximo, calcule o centroid mais próximo de cada dado do dataset.
End of explanation
nearest_indexes = all_nearest_centroids(dataset, centroids)
nearest_indexes
plt.scatter(dataset[:,0], dataset[:,1], c=nearest_indexes)
plt.scatter(centroids[:,0], centroids[:,1], marker='^', c='red', s=100)
plt.show()
Explanation: Teste a função criada visualizando os cluster formados.
End of explanation
def inertia(dataset, centroids, nearest_indexes):
    
    Soma das distâncias quadradas das amostras para o 
    centro do cluster mais próximo.
    
    Argumentos:
    dataset -- Conjunto de dados - [m,n]
    centroids -- Lista com os centróides - [k,n]
    nearest_indexes -- Índices do centróides mais próximos - [m,1]
    
    Retornos:
    inertia -- Soma total do quadrado da distância entre 
    os dados de um cluster e seu centróide
    
    
    #### CODE HERE ####
    inertia = 0
    for data,index in zip(dataset, nearest_indexes):
        
        inertia = inertia + np.power(euclidean_distance(data,centroids[index]),2)
    
    #inertia = sum(np.power(nearest_indexes,2))
    print(inertia)
    ### END OF CODE ###
    
    return inertia
Explanation: 1.3 Métrica de avaliação
Após formar os clusters, como sabemos se o resultado gerado é bom? Para isso, precisamos definir uma métrica de avaliação.
O algoritmo K-means tem como objetivo escolher centróides que minimizem a soma quadrática das distância entre os dados de um cluster e seu centróide. Essa métrica é conhecida como inertia.
$$\sum_{i=0}^{n}\min_{c_j \in C}(||x_i - c_j||^2)$$
A inertia, ou o critério de soma dos quadrados dentro do cluster, pode ser reconhecido como uma medida de o quão internamente coerentes são os clusters, porém ela sofre de alguns inconvenientes:
A inertia pressupõe que os clusters são convexos e isotrópicos, o que nem sempre é o caso. Desta forma, pode não representar bem em aglomerados alongados ou variedades com formas irregulares.
A inertia não é uma métrica normalizada: sabemos apenas que valores mais baixos são melhores e zero é o valor ótimo. Mas em espaços de dimensões muito altas, as distâncias euclidianas tendem a se tornar infladas (este é um exemplo da chamada “maldição da dimensionalidade”). A execução de um algoritmo de redução de dimensionalidade, como o PCA, pode aliviar esse problema e acelerar os cálculos.
Fonte: https://scikit-learn.org/stable/modules/clustering.html
Para podermos avaliar os nosso clusters, codifique a métrica da inertia abaixo, para isso você pode utilizar a função de distância euclidiana construída anteriormente.
$$inertia = \sum_{i=0}^{n}\min_{c_j \in C} (dist(x_i, c_j))^2$$
End of explanation
tmp_data = np.array([[1,2,3],[3,4,5],[4,5,6]])
tmp_centroide = np.array([[2,3,4]])
tmp_nearest_indexes = all_nearest_centroids(tmp_data, tmp_centroide)
if np.floor(inertia(tmp_data, tmp_centroide, tmp_nearest_indexes)) == 26:
    print("Inertia calculada corretamente!")
else:
    print("Função de inertia incorreta!")
# Use a função para verificar a inertia dos seus clusters
inertia(dataset, centroids, nearest_indexes)
Explanation: Teste a função codificada executando o código abaixo.
End of explanation
def update_centroids(dataset, centroids, nearest_indexes):
    
    Atualiza os centroids
    
    Argumentos:
    dataset -- Conjunto de dados - [m,n]
    centroids -- Lista com os centróides - [k,n]
    nearest_indexes -- Índices do centróides mais próximos - [m,1]
    
    Retornos:
    centroids -- Lista com centróides atualizados - [k,n]
    
    
    #### CODE HERE ####
    
    newCentroids = []
    r,c = np.shape(centroids)
    for i in range(0,r):
        newCentroids.append(0) 
    
    values, repetitions = np.unique(nearest_indexes,return_counts=True)
    
    for data,index in zip(dataset,nearest_indexes):
        i = 0
        for val in values:
            if val == index:
                indexesRepetitions = repetitions[i]
            i = i+1
                
        newCentroids[index] = newCentroids[index] + data/indexesRepetitions
        
    #print('Antigos:',centroids)
    #print('Novos:',np.asarray(newCentroids))
    centroids = np.asarray(newCentroids)
    ### END OF CODE ###
    
    return centroids
Explanation: 1.4 Atualizar os clusters
Nessa etapa, os centróides são recomputados. O novo valor de cada centróide será a media de todos os dados atribuídos ao cluster.
End of explanation
nearest_indexes = all_nearest_centroids(dataset, centroids)
# Plota os os cluster ------------------------------------------------
plt.scatter(dataset[:,0], dataset[:,1], c=nearest_indexes)
# Plota os centroids
plt.scatter(centroids[:,0], centroids[:,1], marker='^', c='red', s=100)
for index, centroid in enumerate(centroids):
    dataframe = dataset[nearest_indexes == index,:]
    for data in dataframe:
        plt.plot([centroid[0], data[0]], [centroid[1], data[1]], 
                 c='lightgray', alpha=0.3)
plt.show()
Explanation: Visualize os clusters formados
End of explanation
centroids_new = update_centroids(dataset, centroids, nearest_indexes)
plt.scatter(dataset[:,0], dataset[:,1], s=10)
plt.scatter(centroids_new[:,0], centroids_new[:,1], marker='^', c='red',s=100)
plt.show()
Explanation: Execute a função de atualização e visualize novamente os cluster formados
End of explanation
class KMeans():
    
    def __init__(self, n_clusters=8, max_iter=300):
        self.n_clusters = n_clusters
        self.max_iter = max_iter
    
    def fit(self,X):
        dataset = np.array(X)
        # Inicializa os centróides
        self.cluster_centers_ = calculate_initial_centers(X, self.n_clusters)
        
        # Computa o cluster de cada amostra
        self.labels_ = [None]
        
            # Calcula a inércia inicial
        old_inertia = [None]
        self.inertia_ = [None]
        
        for index in range(0,self.max_iter):
            nearest_indexes = all_nearest_centroids(dataset, self.cluster_centers_)
            old_inertia = inertia(dataset, self.cluster_centers_, nearest_indexes)
            self.cluster_centers_ = update_centroids(dataset, self.cluster_centers_, nearest_indexes)
            
            # Plota os os cluster ------------------------------------------------
            centroids = self.cluster_centers_
            plt.scatter(dataset[:,0], dataset[:,1], c=nearest_indexes)
            # Plota os centroids
            plt.scatter(centroids[:,0], centroids[:,1], marker='^', c='red', s=100)
            for index, centroid in enumerate(centroids):
                dataframe = dataset[nearest_indexes == index,:]
                for data in dataframe:
                    plt.plot([centroid[0], data[0]], [centroid[1], data[1]], 
                             c='lightgray', alpha=0.3)
            plt.show()
        
        self.inertia_ = old_inertia
            #### CODE HERE ####
    def calculate_initial_centers(dataset, k):
        
        Inicializa os centróides iniciais de maneira arbitrária 
        Argumentos:
        dataset -- Conjunto de dados - [m,n]
        k -- Número de centróides desejados
        Retornos:
        centroids -- Lista com os centróides calculados - [k,n]
        
        
        m,n = np.shape(dataset)
        minimum = np.min(dataset)
        maximum = np.max(dataset)
        centroids = np.random.uniform(low=minimum,high=maximum,size=(k,n))
        return centroids
    def euclidean_distance(a, b):
        
        Calcula a distância euclidiana entre os pontos a e b
        Argumentos:
        a -- Um ponto no espaço - [1,n]
        b -- Um ponto no espaço - [1,n]
        Retornos:
        distance -- Distância euclidiana entre os pontos
        
        dist = 0
        for ai,bi in zip(a,b):
            dist = dist + (ai - bi)**2
        distance = math.sqrt(dist)
        return distance
            ### END OF CODE ###
                    
        return self
    
    def nearest_centroid(a, centroids):
        
        Calcula o índice do centroid mais próximo ao ponto a
        Argumentos:
        a -- Um ponto no espaço - [1,n]
        centroids -- Lista com os centróides - [k,n]
        Retornos:
        nearest_index -- Índice do centróide mais próximo
        
        distances = []
        r,c = np.shape(centroids)
        if r == 1:
            euc = euclidean_distance(a,centroids[0])
            distances.append(euc)
            nearest_index = 0 
        else:
            for centroid in centroids:
                euc = euclidean_distance(a,centroid)
                distances.append(euc)
            #print(distances)    
            nearest_index = np.argmin(distances)    
        return nearest_index
    
    def all_nearest_centroids(dataset, centroids):
        
        Calcula o índice do centroid mais próximo para cada 
        ponto do dataset
        Argumentos:
        dataset -- Conjunto de dados - [m,n]
        centroids -- Lista com os centróides - [k,n]
        Retornos:
        nearest_indexes -- Índices do centróides mais próximos - [m,1]
        
        nearest_indexes = []
        for data in dataset:
            near = nearest_centroid(data,centroids)
            nearest_indexes.append(near)
        return nearest_indexes
    
    def inertia(dataset, centroids, nearest_indexes):
        
        Soma das distâncias quadradas das amostras para o 
        centro do cluster mais próximo.
        Argumentos:
        dataset -- Conjunto de dados - [m,n]
        centroids -- Lista com os centróides - [k,n]
        nearest_indexes -- Índices do centróides mais próximos - [m,1]
        Retornos:
        inertia -- Soma total do quadrado da distância entre 
        os dados de um cluster e seu centróide
        
        inertia = 0
        for data,index in zip(dataset, nearest_indexes):
            inertia = inertia + np.power(euclidean_distance(data,centroids[index]),2)
        return inertia
    
    def update_centroids(dataset, centroids, nearest_indexes):
        
        Atualiza os centroids
        Argumentos:
        dataset -- Conjunto de dados - [m,n]
        centroids -- Lista com os centróides - [k,n]
        nearest_indexes -- Índices do centróides mais próximos - [m,1]
        Retornos:
        centroids -- Lista com centróides atualizados - [k,n]
        
        newCentroids = []
        r,c = np.shape(centroids)
        for i in range(0,r):
            newCentroids.append(0) 
        values, repetitions = np.unique(nearest_indexes,return_counts=True)
        for data,index in zip(dataset,nearest_indexes):
            i = 0
            for val in values:
                if val == index:
                    indexesRepetitions = repetitions[i]
                i = i+1
            newCentroids[index] = newCentroids[index] + data/indexesRepetitions
        centroids = np.asarray(newCentroids)
        return centroids
    
    
    ####################################
    def predict(self, X):
        
        return [None]
Explanation: 2. K-means
2.1 Algoritmo completo
Utilizando as funções codificadas anteriormente, complete a classe do algoritmo K-means!
End of explanation
# load the data with pandas
dataset = pd.read_csv('dataset.csv', header=None)
kmeans = KMeans(n_clusters=3,max_iter=10)
kmeans.fit(dataset)
print("Inércia = ", kmeans.inertia_)
Explanation: Verifique o resultado do algoritmo abaixo!
End of explanation
# load the data with pandas
dataset = pd.read_csv('dataset.csv', header=None)
dataset = np.array(dataset)
kmeans = cluster.KMeans(n_clusters=3, random_state=0)
kmeans.fit(dataset)
print('Inertia:',kmeans.inertia_)
plt.scatter(dataset[:,0], dataset[:,1], c=kmeans.labels_)
plt.scatter(kmeans.cluster_centers_[:,0], 
            kmeans.cluster_centers_[:,1], marker='^', c='red', s=100)
plt.show()
Explanation: 2.2 Comparar com algoritmo do Scikit-Learn
Use a implementação do algoritmo do scikit-learn do K-means para o mesmo conjunto de dados. Mostre o valor da inércia  e os conjuntos gerados pelo modelo. Você pode usar a mesma estrutura da célula de código anterior.
Dica: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans
End of explanation
#### CODE HERE ####
Explanation: 3. Método do cotovelo
Implemete o método do cotovelo e mostre o melhor K para o conjunto de dados.
End of explanation
#### CODE HERE ####
Explanation: 4. Dataset Real
Exercícios
1 - Aplique o algoritmo do K-means desenvolvido por você no datatse iris [1]. Mostre os resultados obtidos utilizando pelo menos duas métricas de avaliação de clusteres [2].
[1] http://archive.ics.uci.edu/ml/datasets/iris
[2] http://scikit-learn.org/stable/modules/clustering.html#clustering-evaluation
Dica: você pode utilizar as métricas completeness e homogeneity.
2 - Tente melhorar o resultado obtido na questão anterior utilizando uma técnica de mineração de dados. Explique a diferença obtida. 
Dica: você pode tentar normalizar os dados [3].
- [3] https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.normalize.html
3 - Qual o número de clusteres (K) você escolheu na questão anterior? Desenvolva o Método do Cotovelo sem usar biblioteca e descubra o valor de K mais adequado. Após descobrir, utilize o valor obtido no algoritmo do K-means.
4 - Utilizando os resultados da questão anterior, refaça o cálculo das métricas e comente os resultados obtidos. Houve uma melhoria? Explique.
End of explanation
<END_TASK>