[PT] Aprendizado de Máquina na Prática

Como usar o algoritmo KNN para Classificar Células Cancerígenas

Descrição: eu amo meus vizinhos…só se eles estiverem perto de mim

K-Nearest Neighbors

O K-Nearest Neighbors (KNN) é um algoritmo de aprendizado supervisionado utilizado para classificar novas amostras de acordo com a sua proximidade com outras amostras de um conjunto de dados de treinamento. O algoritmo assume que amostras com características semelhantes têm mais chances de pertencerem à mesma classe.

Funcionando através de um processo de três etapas:

1. Cálculo da distância entre a nova amostra e cada amostra no conjunto de dados de treinamento;
2. Seleção dos k vizinhos mais próximos com base nas distâncias calculadas
3. Classificação da nova amostra com base nas classes dos k vizinhos mais próximos. O valor de k é determinado pelo usuário e geralmente é um número ímpar para evitar empates.

O KNN pode ser utilizado para classificar amostras com múltiplas classes e características contínuas ou discretas. Embora seja fácil de implementar e compreender, o KNN pode ser computacionalmente caro, pois ele precisa calcular a distância para cada amostra no conjunto de dados de treinamento. Além disso, ele pode ser sensível a outliers e a escolha do valor de k pode ter um grande impacto na precisão da classificação.

Demonstração visual do KNN

Em geral, o KNN é um algoritmo simples e eficaz para classificação de amostras, especialmente quando o conjunto de dados é pequeno.

A base de dados utilizada

A base de dados utilizada se chama “Breast Cancer Wisconsin (Diagnostic)” e foi coletada por Dr. William H. Wolberg, do Hospital da Universidade de Wisconsin, em Madison, EUA. A base de dados contém 683 amostras de células de câncer de mama, cada uma com nove características (parâmetros) numéricas e um rótulo (classe) que indica se a célula é benigna ou maligna.

Os parâmetros das células incluem:

• Clump espessura
• Uniformidade do tamanho da célula
• Uniformidade da forma da célula
• Adesão marginal
• Tamanho único das células epiteliais
• Núcleos nus
• Cromatina branda
• Nucleólios normais
• Mitoses

Cada parâmetro é avaliado em uma escala de 1 a 10. O rótulo da classe é indicado por um valor numérico 2 ou 4, em que 2 indica que a célula é benigna e 4 indica que a célula é maligna.

O objetivo do algoritmo K-NN implementado é classificar novas amostras de células como benignas ou malignas com base nos parâmetros das amostras de células já classificadas no conjunto de dados de treinamento.

Hands-on:

A implementação do KNN consiste em alguns passos básicos:

• Carregamento dos dados: é necessário carregar o conjunto de dados que será utilizado para o treinamento e a classificação das amostras. Geralmente, esse conjunto é dividido em um conjunto de treinamento e um conjunto de teste (feito nos passos seguintes).

Click aqui para acessar os dados e fazer seu carregamento

• Criação da classe Celula: a classe Celula é utilizada para armazenar as informações das amostras do conjunto de dados.

//classe  célula
class Celula
{
 private:
  /*
  PARAMETROS USADOS NO DATASET
  1. Número do código da amostra: número de identificação
  2. Clump Espessura: 1 - 10
  3. Uniformidade do tamanho da célula: 1 - 10
  4. Uniformidade da Forma da Célula: 1 - 10
  5. Adesão Marginal: 1 a 10
  6. Tamanho Único de Células Epiteliais: 1 - 10
  7. Núcleos Nus: 1 - 10
  8. Cromatina Branda: 1 a 10
  9. Nucleoli Normal: 1 - 10
  10. Mitoses: 1 - 10
  11. Classe: (2 para benigno, 4 para maligno)
  */
  //parametros célula
  double  clump_espessura,
          uniformidade_tamanho_celula,
          uniformidade_forma_celula,
          adesao_marginal,
          tamanho_unico_celulas_epiteliais,
          nucleos,
          cromatina_branda,
          nucleoli_normal,
          mitoses;

  string classe;
 public:
  //método construtor para receber os parametro
  Celula( double clump_espessura, double uniformidade_tamanho_celula,
          double uniformidade_forma_celula, double adesao_marginal,
          double tamanho_unico_celulas_epiteliais, double nucleos,
          double cromatina_branda, double nucleoli_normal,
          double mitoses, string classe)
  {
    this->clump_espessura = clump_espessura;
    this->uniformidade_tamanho_celula = uniformidade_tamanho_celula;
    this->uniformidade_forma_celula = uniformidade_forma_celula;
    this->adesao_marginal = adesao_marginal;
    this->tamanho_unico_celulas_epiteliais = tamanho_unico_celulas_epiteliais;
    this->nucleos = nucleos;
    this->cromatina_branda = cromatina_branda;
    this->nucleoli_normal = nucleoli_normal;
    this->mitoses = mitoses;
    this->classe = classe;
  }

  //métodos get para obter parâmetros
  double get_clump_espessura()
  {
   return clump_espessura;
  }

  double get_uniformidade_tamanho_celula()
  {
   return uniformidade_tamanho_celula;
  }

  double get_uniformidade_forma_celula()
  {
   return uniformidade_forma_celula;
  }

  double get_adesao_marginal()
  {
   return adesao_marginal;
  }

  double get_tamanho_unico_celulas_epiteliais()
  {
   return tamanho_unico_celulas_epiteliais;
  }

  double get_nucleos()
  {
   return nucleos;
  }

  double get_cromatina_branda()
  {
   return cromatina_branda;
  }

  double get_nucleoli_normal()
  {
   return nucleoli_normal;
  }

  double get_mitoses()
  {
   return mitoses;
  }

  string get_classe()
  {
   return classe;
  }

};

• Cálculo da distância euclidiana: a distância euclidiana é utilizada para calcular a distância entre uma amostra e as demais amostras do conjunto de treinamento. A função Distancia_euclidiana é utilizada para calcular essa distância.

//função para calcular a distancia eu clidiana
double Distancia_euclidiana(Celula celula_1, Celula celula_2 )
{

 double resultado_soma =  pow((celula_1.get_clump_espessura() - celula_2.get_clump_espessura()), 2) +
                          pow((celula_1.get_uniformidade_tamanho_celula() - celula_2.get_uniformidade_tamanho_celula()), 2) +
                          pow((celula_1.get_uniformidade_forma_celula() - celula_2.get_uniformidade_forma_celula()), 2) +
                          pow((celula_1.get_adesao_marginal() - celula_2.get_adesao_marginal()), 2) +
                          pow((celula_1.get_tamanho_unico_celulas_epiteliais() - celula_2.get_tamanho_unico_celulas_epiteliais()), 2) +
                          pow((celula_1.get_nucleos() - celula_2.get_nucleos()), 2) +
                          pow((celula_1.get_cromatina_branda() - celula_2.get_cromatina_branda()), 2) +
                          pow((celula_1.get_nucleoli_normal() - celula_2.get_nucleoli_normal()), 2) +
                          pow((celula_1.get_mitoses() - celula_2.get_mitoses()), 2);

 //retornando a raiz quadrada da soma da diferença dos quadrados
 return sqrt(resultado_soma);
}

• Classificação das amostras: a função Classificador_amostras_celulas é utilizada para classificar as amostras do conjunto de teste. Essa função recebe como parâmetros o conjunto de treinamento (vetor de objetos da classe Celula), a amostra a ser classificada (objeto da classe Celula) e o valor de k, que define quantos vizinhos mais próximos devem ser considerados na classificação.

//funcao de classificação de amostras
//Esta função receberá 3 parametros o primeiro sera um vetor de células, o segundo sera um novo exemplo de célula,
// e o terceiros sera uma k que determinara quantos vizinhos mais próximos.
string Classificador_amostras_celulas(vector<Celula>& celulas, Celula novo_exemplo_celula, int k)
{
 //não é recomendado que k seje par, pois pode ocorrer de ter o mesmo número de classe para a célula
 //então forçarei o k a ser impar decrementando ele, e maior que 0
 if( k % 2 == 0)
 {
  k--;
  if(k <= 0)
   k = 1;
 }

 int tamanho_vetor_de_celulas = celulas.size();

 //set de pear da distância de cada célula do conjunto de treinamento para o novo exemplo de célula
 //cada pear vai ser composto pela distância e pelo índice do vetor
 set<pair <double, int> > distancia_celulas;

 //calculando a distancia euclidiana do novo exemplo da célula, para cada amostra do conjunto de treinamento
 for(int i = 0; i < tamanho_vetor_de_celulas; i++)
 {
  double distancia = Distancia_euclidiana(celulas[i], novo_exemplo_celula);

  //enserindo no pear a distancia e o indice do vetor
  distancia_celulas.insert(make_pair(distancia,i));
 }

 //para decidir a qual classe pertence o novo exemplo de célula, basta verificar a classe mais frenquente entre os ks vizinhos mais proximos
 //do conjunto de treinamento.
 //para isso vou precisar de um set de pear iterator, e também um vetor para cada classe fazer a contagem de célula benigna ou maligna

 set<pair<double, int> >::iterator it;

 //declarando um vetor para as duas classes, posição 0 = benigna, posição 1 = maligna
 vector<int> contador_classes(2);

 int contador_k = 0;

 //percorrendo o set de pear das distancias das celulas
 for(it = distancia_celulas.begin(); it != distancia_celulas.end(); it++)
 {
  contador_k++;//incrementando o contador para chegar nos ks visinhos

  //ordem de parada quando o contador for igual ao numero de ks visiznhos
  if(contador_k == k)
   break;

  //pegando a classe da célula
  string classe = celulas[it->second].get_classe();

  //incrementando o contador da classe
  if(classe == "2")
   contador_classes[0]++;
  else if(classe == "4")
   contador_classes[1]++;
 }

 //agora vamos descobrir qual a classe mais frequente para retornar ela
 string classe_classificacao;

 //se a classe benigna for maior que a maligna, no primeiro if eu coloco igual, mas nunca irá acontecer de
 //ocorrer empate de classes pois meu k sempre será impar e só temos duas classes
 if(contador_classes[0] >= contador_classes[1])
  classe_classificacao = "2";
 else
  classe_classificacao = "4";

 //retornando a classe predominante
 return classe_classificacao;
}

• Teste e avaliação da precisão: após a classificação das amostras do conjunto de teste, é necessário avaliar a precisão do algoritmo. Para isso, é calculado o número de acertos e o número total de amostras do conjunto de teste. A precisão é dada pela razão entre o número de acertos e o número total de amostras do conjunto de teste.

 //declarando um vetor de células
 vector<Celula> celulas;

 //k que determinara a quantidade de vizinhos proximos
 int k = 5;

 //variável para mostrar a precisão do teste
 float precisao = 0;

 //variavel do tamanho do conjunto de dados de treinamento
 //normalmente é colocado 75 % do conjunto de dados para treinamento e os outros 25% para testes
 int tamanho_treinamento = 511;

 //o processo de treinamento consiste em armazenar o conjunto de dados de treinamento
 //e é o que vamos fazer agora
 for(int i = 0; i < tamanho_treinamento; i++)
 {
  //declarando as variaveis
  double  clump_espessura,
          uniformidade_tamanho_celula,
          uniformidade_forma_celula,
          adesao_marginal,
          tamanho_unico_celulas_epiteliais,
          nucleos,
          cromatina_branda,
          nucleoli_normal,
          mitoses;

  string classe;

  //fazendo a entrada de dados
  cin  >> clump_espessura
       >> uniformidade_tamanho_celula
       >> uniformidade_forma_celula
       >> adesao_marginal
       >> tamanho_unico_celulas_epiteliais
       >> nucleos
       >> cromatina_branda
       >> nucleoli_normal
       >> mitoses
       >> classe;

   //inserindo no do vetor os paramentros de entrada
   celulas.push_back(Celula(  clump_espessura,
                              uniformidade_tamanho_celula,
                              uniformidade_forma_celula,
                              adesao_marginal,
                              tamanho_unico_celulas_epiteliais,
                              nucleos,
                              cromatina_branda,
                              nucleoli_normal,
                              mitoses,
                              classe));
 }

 //numeros de acertos
 int acertos = 0;

 //variável do tamanho do conjunto de dados de teste 25% , 683 representa o total de amostras que tenho no dataset
 int tamanho_teste = 683 - tamanho_treinamento ;

 //muito importante salientar que esses dados de teste não foram usados nos dados de treinamento, eles são exlusívos

 //agora fazeremos o processo de classificação desses teste
 for(int i = 0; i < tamanho_teste; i++)
 {
  //declarando as variaveis
  double  clump_espessura,
          uniformidade_tamanho_celula,
          uniformidade_forma_celula,
          adesao_marginal,
          tamanho_unico_celulas_epiteliais,
          nucleos,
          cromatina_branda,
          nucleoli_normal,
          mitoses;
  string classe;

  //fazendo a entrada de dados
  cin  >> clump_espessura
       >> uniformidade_tamanho_celula
       >> uniformidade_forma_celula
       >> adesao_marginal
       >> tamanho_unico_celulas_epiteliais
       >> nucleos
       >> cromatina_branda
       >> nucleoli_normal
       >> mitoses
       >> classe;

  //classe celula_teste recebendo os parametros de entrada
  Celula celula_teste( clump_espessura,
                       uniformidade_tamanho_celula,
                       uniformidade_forma_celula,
                       adesao_marginal,
                       tamanho_unico_celulas_epiteliais,
                       nucleos,
                       cromatina_branda,
                       nucleoli_normal,
                       mitoses,
                       classe);

  string classe_obtida = Classificador_amostras_celulas(celulas, celula_teste, k);

  //mostrando classe espera e classe obtida
  //cout << i <<"° - " << classe <<" -> " << classe_obtida << "\n";

  //fazendo a contagem de acertos
  if(classe == classe_obtida)
  {
   cout << i <<"° - " << classe <<" -> " << classe_obtida << " *\n";
   acertos++;
  }
  else
      cout << i <<"° - " << classe <<" -> " << classe_obtida << " x\n";
  }

 cout <<"----------------------------------------------------------------------------";
 //mostrando total de acertos e o total de testes feitos
 cout << "\n" <<acertos << " acertos de um total de " << tamanho_teste << " testes!\n";

 //calculando precisão do teste
 float aux;
 aux = acertos;
 precisao = ((aux/tamanho_teste)*100);

 //mostrando a porcentagem da precisão dos testes feitos
 cout << "A precisão de acertos foi de : "<< precisao << "%\n";
 cout <<"----------------------------------------------------------------------------\n";

Por fim, é importante ressaltar que, para uma implementação eficiente do KNN, é necessário considerar a escolha adequada do valor de k e a seleção de características relevantes para a classificação das amostras.

Espero que tenham gostado desse passo-a-passo da implementação do KNN não sendo uma black box e entendendo melhor os conceitos do algoritmo e da ideia do Machine Learning.

Para acessar o código completo click no link abaixo:

GitHub - goismarcos/cancerMama_knn: Classificação de nódulos mamarios com KNN

Base de dados original:

1. https://archive.ics.uci.edu/ml/datasets/breast+cancer+wisconsin+(diagnostic)