Arquivo de Inteligência Artificial - Página 144 de 165

Categorias

Anteriormente discutimos as diversas aplicações dos Support Vector Machines. Similarmente, é crucial compreender a complexidade computacional associada a esses algoritmos, pois isso impacta diretamente sua escalabilidade e aplicabilidade prática.

Complexidade Computacional dos SVM

Primordialmente, a complexidade dos algoritmos SVM no scikit-learn varia conforme a implementação específica e o tipo de problema. Decerto, o treinamento de máquinas de vetores de suporte envolve resolver problemas de otimização quadrática que podem ser computacionalmente intensivos.

Complexidade por Implementação

Conforme a documentação, as principais implementações possuem as seguintes características de complexidade:

libsvm e liblinear: Complexidade entre \(O(n_{features} \times n_{samples}^2)\) e \(O(n_{features} \times n_{samples}^3)\)
SVC e NuSVC: Baseados no libsvm, com complexidade quadrática no número de amostras
LinearSVC: Implementado no liblinear, com complexidade mais linear \(O(n_{features} \times n_{samples})\)
SVR: Complexidade similar ao SVC para problemas de regressão

Fatores que Influenciam a Complexidade

Inegavelmente, diversos fatores impactam o tempo de treinamento e predição:

Número de amostras (n_samples): O fator mais significativo para a complexidade
Número de características (n_features): Afeta principalmente a fase de predição
Número de vetores de suporte: Determina a complexidade da fase de predição
Tipo de kernel: Kernels não-lineares são mais computacionalmente custosos
Parâmetros de regularização: Valores de C e γ influenciam o número de vetores de suporte

Complexidade de Predição

Embora o treinamento possa ser intensivo, a predição é geralmente mais eficiente. Similarmente a outros algoritmos, a complexidade de predição para SVM é \(O(n_{features} \times n_{support\_vectors})\). Portanto, modelos com muitos vetores de suporte terão predições mais lentas.

Recomendações para Grande Volume de Dados

Para conjuntos de dados muito grandes, algumas estratégias são recomendadas:

Utilizar LinearSVC ou SGDClassifier com loss=’hinge’
Reduzir dimensionalidade com PCA ou seleção de features
Utilizar amostragem ou mini-batch learning
Considerar kernels lineares quando possível
Ajustar os parâmetros C e γ para controlar o número de vetores de suporte

Exemplo Prático: Análise de Complexidade

Ademais, vejamos um exemplo que demonstra como a complexidade varia com o tamanho do dataset:

'''
Análise de Complexidade de Diferentes Implementações SVM
Este exemplo compara o tempo de treinamento para diferentes
tamanhos de dataset e implementações SVM
'''

import time
import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC, LinearSVC
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split

# Configurações do experimento
sizes = [100, 500, 1000, 2000, 5000]
n_features = 20
results_svc = []
results_linear = []

print("Comparação de Complexidade: SVC vs LinearSVC")
print("=" * 50)

for size in sizes:
    # Gerar dados de classificação
    X, y = make_classification(n_samples=size, n_features=n_features, 
                              n_redundant=2, n_informative=10,
                              random_state=42)
    
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, 
                                                        random_state=42)
    
    # Medir tempo SVC (kernel RBF)
    start_time = time.time()
    svc = SVC(kernel='rbf', random_state=42)
    svc.fit(X_train, y_train)
    svc_time = time.time() - start_time
    results_svc.append(svc_time)
    
    # Medir tempo LinearSVC
    start_time = time.time()
    linear_svc = LinearSVC(random_state=42, max_iter=1000)
    linear_svc.fit(X_train, y_train)
    linear_time = time.time() - start_time
    results_linear.append(linear_time)
    
    print(f"Tamanho: {size:4d} | SVC: {svc_time:.3f}s | LinearSVC: {linear_time:.3f}s")

# Visualização dos resultados
plt.figure(figsize=(10, 6))
plt.plot(sizes, results_svc, 'o-', label='SVC (RBF)', linewidth=2)
plt.plot(sizes, results_linear, 's-', label='LinearSVC', linewidth=2)
plt.xlabel('Número de Amostras')
plt.ylabel('Tempo de Treinamento (segundos)')
plt.title('Complexidade Computacional: SVC vs LinearSVC')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()

# Análise adicional de vetores de suporte
print("\nAnálise de Vetores de Suporte:")
X, y = make_classification(n_samples=1000, n_features=20, random_state=42)
svc = SVC(kernel='rbf', random_state=42)
svc.fit(X, y)
print(f"Número de vetores de suporte: {len(svc.support_)}")
print(f"Percentual de vetores de suporte: {len(svc.support_)/len(X)*100:.1f}%")

'''

Análise de Complexidade de Diferentes Implementações SVM

Este exemplo compara o tempo de treinamento para diferentes

tamanhos de dataset e implementações SVM

'''

import time

import numpy as np

import matplotlib.pyplot as plt

from sklearn.svm import SVC, LinearSVC

from sklearn.datasets import make_classification

from sklearn.model_selection import train_test_split

# Configurações do experimento

sizes = [100, 500, 1000, 2000, 5000]

n_features = 20

results_svc = []

results_linear = []

print("Comparação de Complexidade: SVC vs LinearSVC")

print("=" * 50)

for size in sizes:

# Gerar dados de classificação

X, y = make_classification(n_samples=size, n_features=n_features,

n_redundant=2, n_informative=10,

random_state=42)

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3,

random_state=42)

# Medir tempo SVC (kernel RBF)

start_time = time.time()

svc = SVC(kernel='rbf', random_state=42)

svc.fit(X_train, y_train)

svc_time = time.time() - start_time

results_svc.append(svc_time)

# Medir tempo LinearSVC

start_time = time.time()

linear_svc = LinearSVC(random_state=42, max_iter=1000)

linear_svc.fit(X_train, y_train)

linear_time = time.time() - start_time

results_linear.append(linear_time)

print(f"Tamanho: {size:4d} | SVC: {svc_time:.3f}s | LinearSVC: {linear_time:.3f}s")

# Visualização dos resultados

plt.figure(figsize=(10, 6))

plt.plot(sizes, results_svc, 'o-', label='SVC (RBF)', linewidth=2)

plt.plot(sizes, results_linear, 's-', label='LinearSVC', linewidth=2)

plt.xlabel('Número de Amostras')

plt.ylabel('Tempo de Treinamento (segundos)')

plt.title('Complexidade Computacional: SVC vs LinearSVC')

plt.legend()

plt.grid(True, alpha=0.3)

plt.show()

# Análise adicional de vetores de suporte

print("\nAnálise de Vetores de Suporte:")

X, y = make_classification(n_samples=1000, n_features=20, random_state=42)

svc = SVC(kernel='rbf', random_state=42)

svc.fit(X, y)

print(f"Número de vetores de suporte: {len(svc.support_)}")

print(f"Percentual de vetores de suporte: {len(svc.support_)/len(X)*100:.1f}%")

Considerações de Escalabilidade

Embora os SVM sejam algoritmos poderosos, sua escalabilidade requer atenção:

Para datasets com mais de 50.000 amostras, considere LinearSVC ou SGDClassifier
O consumo de memória pode ser limitante devido à matriz kernel
Em problemas multi-classe, a complexidade aumenta com o número de classes
A predição online é eficiente uma vez o modelo treinado

Dicas de Otimização

Para melhorar o desempenho dos SVM na prática:

Utilize StandardScaler para normalizar os dados
Experimente diferentes kernels e ajuste os hiperparâmetros
Considere cache_size para datasets que cabem na memória
Para problemas lineares, prefira LinearSVC
Utilize RandomizedSearchCV para busca de hiperparâmetros em datasets grandes

Enfim, compreender a complexidade dos SVM é essencial para tomar decisões informadas sobre quando e como utilizá-los em projetos de machine learning.

Referência: https://scikit-learn.org/0.21/modules/svm.html#complexity

Anteriormente exploramos os Support Vector Machines (SVM) para problemas supervisionados. Analogamente, o scikit-learn oferece implementações para problemas não supervisionados através do One-Class SVM, focando em estimativa de densidade e detecção de novidades.

Conceito Fundamental do One-Class SVM

Primordialmente, o One-Class SVM é uma técnica que aprende um limite de decisão para englobar os dados normais de treinamento. Similarmente aos SVM tradicionais, este método busca encontrar um hiperplano que maximize a margem em relação à origem no espaço de características.

Conforme a documentação, o OneClassSVM é particularmente útil quando temos muitos exemplos da classe “normal” e poucos ou nenhum exemplo de anomalias durante o treinamento. Decerto, esta característica o torna ideal para cenários de detecção de novidades onde as anomalias são raras ou desconhecidas.

Formulação Matemática

O objetivo do One-Class SVM pode ser expresso pela seguinte formulação:

\(\min_{w,\xi,\rho} \frac{1}{2}||w||^2 + \frac{1}{\nu n}\sum_{i=1}^n \xi_i – \rho\)

Sujeito a:

\((w \cdot \phi(x_i)) \geq \rho – \xi_i, \quad \xi_i \geq 0\)

Onde:

w é o vetor de pesos do hiperplano
φ(xᵢ) representa a transformação para o espaço de características
ξᵢ são variáveis de folga
ν é o parâmetro crucial que controla a fração de outliers
ρ é o termo de bias

Interpretação do Parâmetro ν

Inegavelmente, o parâmetro ν merece atenção especial. Conquanto possa parecer complexo inicialmente, sua interpretação é fundamental:

ν representa um limite superior para a fração de outliers de treinamento
Simultaneamente, é um limite inferior para a fração de vetores de suporte
Valores típicos variam entre 0.01 e 0.5

Portanto, ao definir ν=0.1, estamos instruindo o modelo a considerar que aproximadamente 10% dos dados de treinamento podem ser outliers.

Aplicações Práticas

Atualmente, as aplicações do One-Class SVM são vastas:

Detecção de fraude: Identificação de transações financeiras anômalas
Monitoramento industrial: Detecção de falhas em equipamentos
Qualidade de produtos: Identificação de itens defeituosos
Segurança cibernética: Detecção de intrusões em redes

Exemplo Prático em Python

Ademais, vejamos uma implementação prática utilizando o scikit-learn:

'''
Exemplo de Detecção de Novidades usando OneClassSVM
Este exemplo demonstra a aplicação do One-Class SVM
para identificar observações anômalas
'''

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

# Gerar dados de exemplo
X, y = make_blobs(n_samples=300, centers=1, cluster_std=0.60, random_state=42)

# Adicionar outliers para simular dados anômalos
rng = np.random.RandomState(42)
X_outliers = rng.uniform(low=-6, high=6, size=(20, 2))
X_combined = np.vstack([X, X_outliers])

# Configurar e treinar o modelo OneClassSVM
nu_value = 0.1  # Parâmetro nu controla tolerância a outliers
clf = svm.OneClassSVM(nu=nu_value, kernel='rbf', gamma=0.1)
clf.fit(X_combined)

# Fazer previsões (1 = inlier, -1 = outlier)
y_pred = clf.predict(X_combined)

# Identificar os outliers detectados
outlier_indices = np.where(y_pred == -1)[0]

# Visualização dos resultados
plt.figure(figsize=(10, 8))

# Plotar os inliers (dados normais)
plt.scatter(X_combined[y_pred == 1, 0], X_combined[y_pred == 1, 1], 
           c='white', s=20, edgecolor='k', label='Inliers')

# Plotar os outliers detectados
plt.scatter(X_combined[y_pred == -1, 0], X_combined[y_pred == -1, 1], 
           c='red', s=50, edgecolor='k', label='Outliers Detectados')

plt.legend()
plt.title(f'Detecção de Novidades com One-Class SVM (nu={nu_value})')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.grid(True, alpha=0.3)
plt.show()

# Estatísticas do modelo
n_outliers_detected = len(outlier_indices)
total_samples = len(X_combined)
print(f'Total de amostras: {total_samples}')
print(f'Outliers detectados: {n_outliers_detected}')
print(f'Percentual de outliers: {(n_outliers_detected/total_samples)*100:.2f}%')

'''

Exemplo de Detecção de Novidades usando OneClassSVM

Este exemplo demonstra a aplicação do One-Class SVM

para identificar observações anômalas

'''

import numpy as np

import matplotlib.pyplot as plt

from sklearn import svm

from sklearn.datasets import make_blobs

# Gerar dados de exemplo

X, y = make_blobs(n_samples=300, centers=1, cluster_std=0.60, random_state=42)

# Adicionar outliers para simular dados anômalos

rng = np.random.RandomState(42)

X_outliers = rng.uniform(low=-6, high=6, size=(20, 2))

X_combined = np.vstack([X, X_outliers])

# Configurar e treinar o modelo OneClassSVM

nu_value = 0.1 # Parâmetro nu controla tolerância a outliers

clf = svm.OneClassSVM(nu=nu_value, kernel='rbf', gamma=0.1)

clf.fit(X_combined)

# Fazer previsões (1 = inlier, -1 = outlier)

y_pred = clf.predict(X_combined)

# Identificar os outliers detectados

outlier_indices = np.where(y_pred == -1)[0]

# Visualização dos resultados

plt.figure(figsize=(10, 8))

# Plotar os inliers (dados normais)

plt.scatter(X_combined[y_pred == 1, 0], X_combined[y_pred == 1, 1],

c='white', s=20, edgecolor='k', label='Inliers')

# Plotar os outliers detectados

plt.scatter(X_combined[y_pred == -1, 0], X_combined[y_pred == -1, 1],

c='red', s=50, edgecolor='k', label='Outliers Detectados')

plt.legend()

plt.title(f'Detecção de Novidades com One-Class SVM (nu={nu_value})')

plt.xlabel('Feature 1')

plt.ylabel('Feature 2')

plt.grid(True, alpha=0.3)

plt.show()

# Estatísticas do modelo

n_outliers_detected = len(outlier_indices)

total_samples = len(X_combined)

print(f'Total de amostras: {total_samples}')

print(f'Outliers detectados: {n_outliers_detected}')

print(f'Percentual de outliers: {(n_outliers_detected/total_samples)*100:.2f}%')

Considerações Importantes

Embora o One-Class SVM seja poderoso, algumas considerações são essenciais:

O modelo assume que a maioria dos dados de treinamento representa comportamento “normal”
A escolha do kernel e dos hiperparâmetros é crítica para o desempenho
O escalonamento dos dados é recomendado
Para datasets muito grandes, a complexidade computacional pode ser limitante

Enfim, compreender a estimativa de densidade e detecção de novidades com SVM complementa nosso conhecimento sobre as capacidades versáteis desta família de algoritmos no scikit-learn.

Referência: https://scikit-learn.org/0.21/modules/svm.html#estimating-the-density-and-detecting-novelties

Máquinas de Vetores de Suporte: Complexidade