# K-Means

### 🎯 Descrição Geral

**K-Means** é um algoritmo de **clusterização** (agrupamento) que particiona `n` observações em `k` clusters, onde cada observação pertence ao cluster com a **média mais próxima** (centróide). É um dos algoritmos de aprendizado não-supervisionado mais simples e populares.

```
Dados de Entrada (sem rótulos)
    │
    ▼
┌─────────────────────────────────────────┐
│    ●  ●    ●                            │
│  ●    ●  ●  ●                           │
│      ▲     ●    ●                       │
│    ●   ●  ●  ●  ●                       │
│       ●    ●    ●                       │
│  ●        ●   ▲    ●                    │
│    ●   ●    ●  ●  ●                     │
│       ●  ●    ●                         │
└─────────────────────────────────────────┘
    │
    ▼ Algoritmo K-Means
    │
    ▼
┌─────────────────────────────────────────┐
│  ●  ●    ●                              │
│●    ●  ●  ●   ┌─────────────┐           │
│    ▲     ●    │   ▲  ▲      │           │
│  ●   ●  ●  ●  │  ▲  ▲ ▲  ▲  │           │
│     ●    ●    │   ▲   ▲  ▲  │           │
│●        ●   ▲ │    ▲  ▲     │           │
│  ●   ●    ●  ●│  ▲   ▲   ▲  │           │
│     ●  ●    ● └─────────────┘           │
└─────────────────────────────────────────┘
(Cluster 1 = azul, Cluster 2 = verde)
```

#### Analogia

> *"K-Means é como organizar uma biblioteca: você coloca livros similares na mesma prateleira. Mas primeiro você precisa decidir quantas prateleiras (k) usar e onde colocar cada uma. O algoritmo ajusta as prateleiras até que os livros fiquem bem organizados."*

***

### ⚙️ Como Funciona

#### Algoritmo Passo a Passo

```
1. Escolher o número de clusters (k)
2. Inicializar k centróides aleatoriamente
3. REPETIR até convergir:
   a) Atribuir cada ponto ao centróide mais próximo
   b) Recalcular centróides como a média dos pontos no cluster
```

#### Visualização das Iterações

```
Iteração 1          Iteração 2          Iteração 3          Final
    │                   │                   │                 │
    ▼                   ▼                   ▼                 ▼
┌─────────┐        ┌─────────┐        ┌─────────┐        ┌─────────┐
│ ●   ●   │        │ ●   ●   │        │ ●   ●   │        │ ●   ●   │
│  ▲      │        │   ▲     │        │   ▲     │        │   ▲     │
│   ●  ▲  │        │ ●   ▲   │        │ ●   ▲   │        │ ●   ▲   │
│    ●    │   →    │   ●     │   →    │    ●    │   →    │    ●    │
│ ▲   ●   │        │  ▲  ●   │        │  ▲  ●   │        │  ▲  ●   │
│  ●      │        │ ●      ▲│        │ ●   ▲   │        │ ●   ▲   │
│    ▲    │        │    ▲    │        │    ▲    │        │    ▲    │
└─────────┘        └─────────┘        └─────────┘        └─────────┘
Centróides          Centróides         Centróides         Clusters
aleatórios          movendo            convergindo        finais
```

***

### 📝 Implementação

#### Implementação Manual

```python
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

class KMeans:
    def __init__(self, n_clusters=3, max_iters=100, random_state=42):
        self.n_clusters = n_clusters
        self.max_iters = max_iters
        self.random_state = random_state
        self.centroids = None
        self.labels = None
    
    def fit(self, X):
        """Executa o algoritmo K-Means"""
        np.random.seed(self.random_state)
        
        # Inicializar centróides aleatoriamente (escolher k pontos)
        n_samples = X.shape[0]
        random_indices = np.random.choice(n_samples, self.n_clusters, replace=False)
        self.centroids = X[random_indices].copy()
        
        for _ in range(self.max_iters):
            # Atribuir cada ponto ao centróide mais próximo
            distances = self._compute_distances(X)
            self.labels = np.argmin(distances, axis=1)
            
            # Calcular novos centróides
            new_centroids = np.zeros_like(self.centroids)
            for i in range(self.n_clusters):
                if np.sum(self.labels == i) > 0:
                    new_centroids[i] = X[self.labels == i].mean(axis=0)
                else:
                    new_centroids[i] = self.centroids[i]  # Manter centróide vazio
            
            # Verificar convergência
            if np.allclose(self.centroids, new_centroids):
                break
            
            self.centroids = new_centroids
        
        return self
    
    def _compute_distances(self, X):
        """Calcula distâncias euclidianas para todos os centróides"""
        distances = np.zeros((X.shape[0], self.n_clusters))
        for i, centroid in enumerate(self.centroids):
            distances[:, i] = np.linalg.norm(X - centroid, axis=1)
        return distances
    
    def predict(self, X):
        """Atribui novos pontos aos clusters existentes"""
        distances = self._compute_distances(X)
        return np.argmin(distances, axis=1)
    
    def inertia(self, X):
        """Calcula inércia (soma das distâncias intra-cluster)"""
        distances = self._compute_distances(X)
        min_distances = np.min(distances, axis=1)
        return np.sum(min_distances ** 2)

# Exemplo de uso
if __name__ == "__main__":
    # Gerar dados sintéticos
    X, y_true = make_blobs(n_samples=300, centers=3, cluster_std=0.8, random_state=42)
    
    # Treinar K-Means
    kmeans = KMeans(n_clusters=3)
    kmeans.fit(X)
    y_pred = kmeans.predict(X)
    
    print(f"Inércia final: {kmeans.inertia(X):.2f}")
    print(f"Centróides:\n{kmeans.centroids}")
```

***

### 💻 Implementação com Scikit-learn

#### K-Means Básico

```python
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

# Gerar dados
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.6, random_state=42)

# Criar e treinar modelo
kmeans = KMeans(n_clusters=4, random_state=42, n_init=10)
kmeans.fit(X)

# Resultados
print(f"Centróides:\n{kmeans.cluster_centers_}")
print(f"Rótulos: {kmeans.labels_}")
print(f"Inércia: {kmeans.inertia_:.2f}")

# Visualizar
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], c=kmeans.labels_, cmap='viridis', alpha=0.7)
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], 
            marker='X', s=200, c='red', edgecolors='black', linewidths=2)
plt.title('K-Means Clustering')
plt.show()
```

#### Método do Cotovelo (Elbow Method)

```python
# Determinar o k ótimo
inertias = []
k_range = range(1, 11)

for k in k_range:
    kmeans = KMeans(n_clusters=k, random_state=42, n_init=10)
    kmeans.fit(X)
    inertias.append(kmeans.inertia_)

# Plotar
plt.figure(figsize=(10, 6))
plt.plot(k_range, inertias, 'bo-')
plt.xlabel('Número de Clusters (k)')
plt.ylabel('Inércia')
plt.title('Método do Cotovelo para k Ótimo')
plt.grid(True)
plt.show()

# O "cotovelo" no gráfico indica o k ideal
```

#### Silhouette Score

```python
from sklearn.metrics import silhouette_score, silhouette_samples

# Calcular silhouette para diferentes k
silhouette_scores = []

for k in range(2, 11):
    kmeans = KMeans(n_clusters=k, random_state=42, n_init=10)
    labels = kmeans.fit_predict(X)
    score = silhouette_score(X, labels)
    silhouette_scores.append(score)
    print(f"k={k}: Silhouette Score = {score:.3f}")

# Melhor k é o que maximiza silhouette score
best_k = np.argmax(silhouette_scores) + 2
print(f"\nMelhor k (Silhouette): {best_k}")
```

***

### 📊 Exemplos Práticos

#### Exemplo 1: Segmentação de Clientes

```python
import pandas as pd
from sklearn.preprocessing import StandardScaler

# Dados de clientes (fictícios)
data = pd.DataFrame({
    'idade': [25, 35, 45, 22, 50, 30, 28, 40, 55, 32, 48, 38, 29, 52, 34],
    'renda': [30, 50, 80, 20, 100, 45, 35, 60, 120, 40, 75, 55, 38, 95, 48],
    'gasto': [5, 8, 12, 3, 15, 7, 6, 10, 18, 6, 11, 9, 5, 14, 7],
    'frequencia': [2, 3, 4, 1, 5, 2, 2, 3, 5, 2, 4, 3, 2, 5, 3]
})

# Normalizar dados (importante para K-Means!)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(data)

# Encontrar k ótimo (Elbow Method)
inertias = []
for k in range(1, 8):
    kmeans = KMeans(n_clusters=k, random_state=42, n_init=10)
    kmeans.fit(X_scaled)
    inertias.append(kmeans.inertia_)

# k=3 parece ideal
kmeans = KMeans(n_clusters=3, random_state=42, n_init=10)
clusters = kmeans.fit_predict(X_scaled)

data['cluster'] = clusters

# Analisar cada cluster
print("Segmentos de Clientes:")
for i in range(3):
    cluster_data = data[data['cluster'] == i]
    print(f"\nCluster {i} ({len(cluster_data)} clientes):")
    print(f"  Idade média: {cluster_data['idade'].mean():.1f} anos")
    print(f"  Renda média: R$ {cluster_data['renda'].mean():.0f}K")
    print(f"  Gasto médio: R$ {cluster_data['gasto'].mean():.0f}K")
    print(f"  Frequência média: {cluster_data['frequencia'].mean():.1f}x/mês")
```

#### Exemplo 2: Compressão de Imagens

```python
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np

# Carregar imagem
from sklearn.datasets import load_sample_image
china = load_sample_image("china.jpg")
image = np.array(china)

print(f"Tamanho original: {image.shape}")
print(f"Cores únicas: {len(np.unique(image.reshape(-1, 3), axis=0))}")

# Reduzir cores com K-Means
def compress_image(image, n_colors=16):
    # Redimensionar para (n_pixels, 3)
    pixels = image.reshape(-1, 3)
    
    # K-Means para encontrar cores representativas
    kmeans = KMeans(n_clusters=n_colors, random_state=42, n_init=10)
    kmeans.fit(pixels)
    
    # Substituir cada pixel pela cor do centróide
    new_pixels = kmeans.cluster_centers_[kmeans.labels_]
    compressed = new_pixels.reshape(image.shape).astype(np.uint8)
    
    return compressed

# Comprimir
compressed = compress_image(image, n_colors=16)

# Visualizar
fig, axes = plt.subplots(1, 2, figsize=(12, 6))
axes[0].imshow(image)
axes[0].set_title(f'Original ({len(np.unique(image.reshape(-1, 3), axis=0))} cores)')
axes[0].axis('off')
axes[1].imshow(compressed)
axes[1].set_title(f'Comprimido (16 cores)')
axes[1].axis('off')
plt.show()
```

#### Exemplo 3: Análise de Documentos (Textos)

```python
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.cluster import KMeans

# Documentos de exemplo
documentos = [
    "Inteligência artificial e machine learning são áreas da computação",
    "Redes neurais profundas (deep learning) são usadas em visão computacional",
    "O mercado financeiro está volátil devido às incertezas econômicas",
    "Investimentos em ações e renda variável exigem análise de risco",
    "Python e R são linguagens populares para ciência de dados",
    "Data science utiliza estatística e programação para análise",
    "Futebol é o esporte mais popular do Brasil",
    "O Flamengo venceu o campeonato brasileiro de futebol"
]

# Vetorizar textos (TF-IDF)
vectorizer = TfidfVectorizer(stop_words='english', max_features=100)
X = vectorizer.fit_transform(documentos)

# Clusterizar
kmeans = KMeans(n_clusters=3, random_state=42, n_init=10)
clusters = kmeans.fit_predict(X)

# Resultados
for i, (doc, cluster) in enumerate(zip(documentos, clusters)):
    print(f"Documento {i+1} (Cluster {cluster}): {doc[:50]}...")
```

***

### 🎯 Vantagens e Desvantagens

#### Vantagens

| Vantagem               | Descrição                          |
| ---------------------- | ---------------------------------- |
| **Simplicidade**       | Fácil de entender e implementar    |
| **Velocidade**         | O(n × k × i) - linear nos dados    |
| **Escalabilidade**     | Funciona bem para grandes datasets |
| **Interpretabilidade** | Centróides são fáceis de explicar  |

#### Desvantagens

| Desvantagem                | Descrição                           | Solução                                    |
| -------------------------- | ----------------------------------- | ------------------------------------------ |
| **k precisa ser definido** | Não sabe automaticamente            | Elbow Method, Silhouette                   |
| **Inicialização sensível** | Resultados podem variar             | K-Means++ (padrão sklearn)                 |
| **Clusters esféricos**     | Assume clusters circulares          | K-Means não funciona para formas complexas |
| **Outliers**               | Sensível a pontos extremos          | Remover outliers, usar K-Medians           |
| **Diferentes tamanhos**    | Assume clusters com mesma variância | Usar GMM (Gaussian Mixture Models)         |

***

### 🔧 Inicialização: K-Means++

O K-Means++ melhora a inicialização, aumentando a chance de encontrar a solução ótima.

```python
from sklearn.cluster import KMeans

# Padrão (random)
kmeans_random = KMeans(n_clusters=3, init='random', n_init=1, random_state=42)

# K-Means++ (recomendado, padrão do sklearn)
kmeans_plus = KMeans(n_clusters=3, init='k-means++', n_init=10, random_state=42)

# Diferença: K-Means++ distribui os centróides iniciais de forma mais inteligente
```

#### Como funciona o K-Means++

```
1. Escolher primeiro centróide aleatoriamente
2. Para cada ponto, calcular distância ao centróide mais próximo (D(x))
3. Escolher próximo centróide com probabilidade ∝ D(x)²
4. Repetir até ter k centróides
```

***

### 📊 Métricas de Avaliação

#### Inércia (Within-Cluster Sum of Squares)

```
Inércia = Σ (distância do ponto ao centróide)²
```

| Valor | Significado               |
| ----- | ------------------------- |
| Baixo | Clusters compactos (bom)  |
| Alto  | Clusters dispersos (ruim) |

#### Silhouette Score

```
Silhouette = (b - a) / max(a, b)
Onde:
a = distância média intra-cluster
b = distância média inter-cluster
```

| Valor | Significado                        |
| ----- | ---------------------------------- |
| +1    | Muito bom (clusters bem separados) |
| 0     | Sobreposição (clusters próximos)   |
| -1    | Ruim (pontos no cluster errado)    |

#### Davies-Bouldin Index

```
DB = (1/k) × Σ max((σ_i + σ_j) / d(c_i, c_j))
```

| Valor | Significado                     |
| ----- | ------------------------------- |
| 0     | Melhor (clusters perfeitos)     |
| ↑     | Pior (clusters menos separados) |

***

### 🔗 Links Úteis

* [Scikit-learn K-Means](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html)
* [K-Means++ Paper](https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf)
* [Visual K-Means Demo](https://www.naftaliharris.com/blog/visualizing-k-means-clustering/)

***

### 📚 Livros Recomendados

| Livro                         | Autor                 | Foco          |
| ----------------------------- | --------------------- | ------------- |
| Introduction to Data Mining   | Tan, Steinbach, Kumar | Clusterização |
| Pattern Recognition and ML    | Christopher Bishop    | Teoria        |
| Hands-On ML with Scikit-Learn | Aurélien Géron        | Prático       |


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xmorte.gitbook.io/bibliadopentestbr/conceitos/algoritmos/aprendizado-de-maquina-machine-learning/k-means.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.