Det disiplinerande samfunn

No contexto de aprendizado de máquina, uma amostra corresponde a uma ins- tância dos dados, geralmente representada por um vetor, cujos valores de cada posição correspondem às características da amostra (atributos) (MOHRI; ROSTAMIZADEH; TALWALKAR, 2012). O número de atributos determina a dimensionalidade da base de dados, portanto, uma base de dados pode ser denominada como unidimensional, bidimensi- onal ou multidimensional, de acordo com o número de atributos utilizados para representar cada amostra.

Em problemas de classificação de dados, além dos atributos, cada amostra também possui um rótulo, que representa uma classe ou categoria na qual a amostra está inserida. Um método de classificação, portanto, é um método capaz de identificar as características mais significativas de um conjunto de amostras e construir uma hipótese de classificação, de modo que, dada uma nova amostra, ela seja capaz de identificar a qual classe ela pertence.

1.1

Classificação linear

Um classificador linear é uma das ferramentas mais simples que podem ser utilizadas para classificar as amostras de um conjunto de dados. O objetivo de um método de classificação linear é encontrar uma função linear capaz de separar as amostras em suas respectivas classes, de acordo com as suas características, construindo assim, o classificador. Considerando, por exemplo, uma base de dados bidimensional e com duas classes linearmente separáveis, como na Figura 2(a), é possível encontrar uma reta que divida as amostras em duas classes. Portanto, um método de classificação linear, aplicado sobre essa base de dados, encontraria uma função linear capaz de produzir essa reta. No caso da Figura 2(b), uma base de dados tridimensional, com duas classes, foi utilizada demonstrando que a classificação linear também pode ser feita através de um hiperplano que separa as amostras no espaço.

Existem diversos métodos que podem ser utilizados para encontrar um classificador linear: Bernoulli Naïve Bayes (LANGLEY; IBA; THOMPSON, 1992; MCCALLUM; NIGAM, 1998), Regressão Logística (FACELI et al., 2011;CRAMER, 2002), SVM (com

kernel linear) (VAPNIK; LERNER, 1963; CORTES; VAPNIK,1995; BOSER; GUYON;

VAPNIK, 1992). Embora esses métodos utilizem abordagens diferentes, todos possuem um mesmo objetivo: encontrar uma função linear que separe as amostras em suas classes, com a menor taxa de erro possível. Normalmente, essa taxa de erro é calculada por uma função denominada função de custo, cujo valor resultante corresponde ao erro quadrático

6 Capítulo 1. Classificadores lineares e não-lineares

Figura 2: Classificadores lineares em duas bases de dados: (a) bidimensional – uma reta separa as amostras e (b) tridimensional ou multidimensional – um hiperplano separa as amostras

médio da distância entre os pontos calculados pela função linear e as amostras utilizadas para o treinamento. O algoritmo de classificação calcula a função linear iterativamente, durante a etapa de treinamento, variando os coeficientes dessa função, visando minimizar o valor resultante da função de custo a cada iteração.

1.2

Classificação não-linear

Embora os métodos de classificação lineares consigam obter bons resultados em diversos cenários, é importante notar que caso a base de dados possua amostras de classes que não sejam linearmente separáveis, um classificador linear não conseguirá realizar a classificação de forma eficaz. Além disso, observando os trabalhos publicados ao longo dos anos, é possível notar que a maior parte das bases de dados reais, utilizadas em problemas de classificação, não possuem classes linearmente separáveis (WOODS; KEGELMEYER; BOWYER,1997;BRITTO; SABOURIN; OLIVEIRA,2014;LOCHTER; ZANETTI; ALMEIDA, 2015). A necessidade da criação de métodos de classificação mais robustos tornou-se cada vez mais evidente e, a partir disso, começaram a surgir métodos de classificação não-lineares, capazes de gerar hipóteses mais complexas que oferecem melhor separação entre as classes. São exemplos de métodos não-lineares: SVM com kernel radial e polinomial (VAPNIK; LERNER, 1963; CORTES; VAPNIK, 1995; BOSER; GUYON; VAPNIK, 1992).

A Figura3ilustra uma base de dados com classes cujas amostras não são linearmente separáveis. Na Figura3(a) é possível observar a aplicação de um método de classificação linear sobre esses dados, indicando que este é capaz de classificar corretamente cerca de metade das amostras. Por outro lado, o classificador não-linear, ilustrado na Figura3(b),

1.3. Comparação entre métodos lineares e não-lineares 7

é capaz de classificar corretamente quase todas as amostras através de uma fronteira de decisão não-linear.

A principal diferença entre um método linear e um não-linear está na função de classificação produzida durante a etapa de treinamento. Em uma base de dados bidimensional, como a que foi utilizada, um classificador linear tenta encontrar uma função linear que produza uma reta capaz de separar as amostras em suas classes (Figura 3(a)). Por outro lado, um classificador não-linear busca encontrar uma função não-linear para classificar as amostras e, desse modo, consegue produzir curvas que representam, com maior precisão, a estrutura das classes das amostras contidas na base (Figura 3(b)). Figura 3: Base de dados bidimensional com classes não separáveis linearmente. Observa-se

que em (a) o classificador linear não consegue separar as amostras corretamente, mas em (b) o classificador não-linear é capaz de separar as amostras de cada classe com maior precisão.

1.3

Comparação entre métodos lineares e não-lineares

A partir da descrição das seções anteriores, é possível destacar as características dos métodos e estabelecer uma comparação entre suas principais vantagens e desvantagens, sintetizadas na Tabela 1.

Os métodos de classificação não-lineares são capazes de produzir soluções mais robustas, uma vez que as funções não-lineares conseguem descrever as características dos dados com maior precisão. Entretanto, a complexidade da implementação desses métodos pode tornar o seu uso inviável em bases de dados muito grandes e com muitos atributos visto que, nestes casos, o tempo de processamento, durante a etapa de treinamento, pode ser muito grande. Assim, torna-se necessário avaliar a relação de custo-benefício da utilização desses métodos de acordo com o problema de classificação a ser resolvido.

Os métodos de classificação lineares possuem um baixo custo computacional e, geralmente, demandam pouco tempo de processamento devido a sua simplicidade de

8 Capítulo 1. Classificadores lineares e não-lineares

Tabela 1: Principais características dos classificadores lineares e não-lineares

Lineares Não-lineares

Implementação simples Implementação complexa Baixo custo computacional na etapa de treina-

mento

Alto custo computacional na etapa de treina- mento

Tende a produzir um classificador com maior capacidade de generalização

Maior chance de produzir um classificador com

overfitting

Pode ter bom desempenho em bases com mui- tos atributos

Pode ser computacionalmente custoso em bases com muitos atributos

Pode ser útil em problemas de larga escala, devido ao baixo custo computacional

Em bases de dados muito grandes, pode ser inviável devido ao tempo de processamento Ineficaz em bases cujas classes não são linear-

mente separáveis

Produz soluções robustas para bases de dados complexas

Podem ser combinados para produzir soluções robustas e computacionalmente eficientes

A combinação de métodos não-lineares pode ser muito custosa computacionalmente

implementação (YUAN; HO; LIN,2012). Alguns trabalhos demonstram que eles apresentam resultados promissores em bases de dados com muitos atributos como, por exemplo, bases de texto (YUAN; HO; LIN,2012;LOCHTER; ZANETTI; ALMEIDA,2015). Além disso, por causa da sua alta eficiência computacional, vários autores identificaram que a combinação desses métodos pode obter resultados promissores em bases de dados complexas, com desempenho semelhante à dos métodos não-lineares (DIETTERICH, 2000; BRITTO; SABOURIN; OLIVEIRA, 2014; LOCHTER; ZANETTI; ALMEIDA,2015).

9

2 Combinando agrupamento e classificação