Aprendizado Não Supervisionado

Objetivos de aprendizagem #

• O1. Explicar por que avaliar agrupamento é qualitativamente mais difícil que avaliar classificação.
• O2. Aplicar k-means e reconhecer as premissas geométricas que ele impõe.
• O3. Usar PCA para redução de dimensionalidade e dizer o que se perde.
• O4. Escolher o número de grupos com um critério declarado, e não pelo gráfico que ficou bonito.

O problema: não há erro a minimizar #

Todos os capítulos anteriores tinham um gabarito: havia um alvo, havia um erro, e o erro dizia se você estava melhorando. Aqui não há nada disso. Sem rótulo, não existe erro a minimizar — existe um critério a inventar. Você decide o que significa "grupo bom", e só então há o que otimizar. A escolha não vem dos dados: vem de você.

A consequência é desconfortável. Quase sempre é possível encontrar grupos: rode k-means com k=4 em ruído puro e ele devolve quatro grupos, com fronteiras nítidas e centros bem definidos. O algoritmo nunca diz "não há estrutura aqui". A pergunta honesta, portanto, nunca é "existem grupos?" — é "estes grupos significam alguma coisa fora deste conjunto de dados?". O erro que este capítulo previne é o mais barato de cometer em toda a análise de dados: olhar para os grupos, achar que fazem sentido, e apresentar isso como descoberta.

De onde isto veio #

O aperto. O detalhe que reorganiza tudo: os problemas originais não eram "clustering". Eram quatro apertos em quatro campos que não conversavam entre si: amostragem estratificada (como dividir uma população em estratos para amostrar melhor), momento de inércia de um sólido (como partir um corpo heterogêneo), compressão de voz (como representar um sinal com poucos níveis) e taxonomia biológica (como classificar organismos). O mesmo procedimento foi inventado quatro vezes porque quatro pessoas tinham problemas diferentes com a mesma forma matemática.

O que se fazia antes. Classificar por julgamento do especialista. Na biologia, isso tinha nome: a classificação valia pela autoridade do taxonomista que a assinava.

A virada. Fixar um critério explícito de homogeneidade e alternar duas minimizações parciais — cada uma trivial quando a outra está congelada. Dados os centros, atribuir cada ponto ao mais próximo é imediato; dadas as atribuições, recalcular o melhor centro é uma média. O problema conjunto é duro; os dois parciais são fáceis.

A ideia reaproveitável. Quando o problema conjunto é intratável, congele metade e resolva a outra — depois inverta. Bock mostra que o k-means é um caso de otimização alternada, e essa mesma forma reaparece em EM, fuzzy c-means e k-medoids. Não é um algoritmo, é um padrão — e você vai reconhecê-lo em qualquer lugar onde duas incógnitas se determinam mutuamente.

O nome. "k-means" foi cunhado por MacQueen (1967) — para um algoritmo diferente do que hoje leva o nome: o sequencial de passagem única, não o batch que todo mundo roda.

Seis pretendentes, e quem levou o nome #

A leitura deste livro. Os capítulos II.2 (Gauss × Legendre) e III.1 (Linnainmaa × Rumelhart) contam a mesma história com dois pretendentes. Aqui há seis, em quatro campos isolados, e o nome vencedor foi cunhado para um algoritmo diferente. Os três casos, juntos, fecham a tríade e dizem o que nenhum diz sozinho: não vence quem descobre, nem quem publica primeiro, nem sequer quem descreve o método que virou padrão. Vence quem escreve a palavra que pega.

Do lado hierárquico, o aperto era político-científico. Sokal & Sneath, em Principles of Numerical Taxonomy (1963), motivaram a pesquisa mundial em clustering, no registro de Bock. O que eles propunham está resumido pelo próprio Sokal: classificar a partir de "a large number of equally weighted characters, unaffected by subjective or phylogenetic judgments", com algoritmos de agrupamento aplicados a matrizes de similaridade. O objetivo não era achar grupos: era tirar da autoridade o direito de defini-los.

A origem do programa é bem mais prosaica que o programa. Sokal conta que num almoço de laboratório em Kansas, em 1953, fez a "brash claim" de que classificaria organismos melhor por meios estatísticos do que pela "traditional subjective approach"; Earl A. Bell apostou uma caixa de seis cervejas que não daria certo, e Charles D. Michener forneceu os dados de um grupo de abelhas. E há uma linha do mesmo texto que fecha com a tríade acima. Ao explicar por que o livro é tão citado, Sokal escreve: "in fact, we coined the name 'numerical taxonomy'."

Do lado da redução de dimensionalidade, dois problemas diferentes, 32 anos, a mesma decomposição: Pearson (1901) chegou por geometria, com a reta ou o plano de melhor ajuste a uma nuvem de pontos; Hotelling (1933) chegou por álgebra, com motivação psicométrica, e é dele o nome "componentes principais".

Procedência das afirmações desta seção:

Fundamentos: inventar o critério, depois alternar #

O k-means declara o critério antes de tudo: a soma das distâncias quadradas de cada ponto ao centro do seu grupo (a inércia). Grupo bom = grupo compacto. Escolhido isso, o algoritmo é a alternância descrita acima — sorteie k centros, atribua, recalcule, repita até parar de mudar. Três consequências que ninguém avisa:

Ele sempre converge, e quase nunca para o ótimo. A inércia cai a cada passo, então o algoritmo para — num mínimo local, que depende do sorteio inicial. Rodar de novo com outra semente pode dar outra resposta; por isso as bibliotecas rodam várias inicializações e ficam com a melhor. Duas partições diferentes do mesmo dado não são bug: são a natureza do método.

Ele só enxerga grupos esféricos e de tamanho parecido. Isso está no critério, não no código. Minimizar distância quadrada ao centro premia bolas compactas; um grupo alongado será cortado ao meio, e um grupo grande será dividido para "pagar" a fusão de dois pequenos. Nenhum valor de k conserta isso.

Distância depende de escala. Uma coluna em reais e outra em anos não são comparáveis: quem tem números maiores domina a distância e decide os grupos sozinha. Normalizar não é higiene, é parte da definição do critério — ver capítulo I.6.

Quando você não quer fixar k: o dendrograma #

O agrupamento hierárquico inverte a pergunta. Em vez de escolher k antes, ele constrói toda a hierarquia: começa com cada ponto sozinho e funde os dois grupos mais próximos, até sobrar um. O resultado é o dendrograma — uma árvore em que a altura de cada fusão é a distância em que ela ocorreu. Você decide o k depois, cortando a árvore na altura que quiser, e vê a estrutura em todas as escalas ao mesmo tempo.

O preço: a fusão é irreversível (um erro no início se propaga até o fim) e o custo cresce rápido com o número de pontos. E há uma escolha escondida que muda tudo — o que significa "distância entre dois grupos": o par mais próximo, o mais distante, a média. Trocar essa definição troca a árvore.

PCA: variância como critério, e o que se perde #

A análise de componentes principais (PCA) resolve o problema de Pearson: achar as direções em que os dados mais variam e reescrevê-los nelas, em ordem. Ficar com as primeiras é reduzir a dimensionalidade — menos colunas, quase a mesma dispersão.

O que se perde tem três nomes. Variância, e você sabe quanto: é o número que a biblioteca informa. Interpretabilidade, porque cada componente é uma mistura de todas as variáveis originais, e "0,4 × renda − 0,3 × idade + …" não é um conceito que se leve a uma reunião. E o mais traiçoeiro: variância não é o mesmo que informação útil. A direção que mais varia pode ser justamente a que menos separa o que importa; PCA não sabe qual é o seu problema, porque ninguém contou a ele. PCA é uma decisão de representação, e vale para ela tudo o que o capítulo I.6 diz — inclusive a sensibilidade à escala.

Regras de associação — e a lenda que quebrou #

Regras de associação nasceram de um aperto comercial concreto: o que os itens de uma cesta de compras dizem uns sobre os outros (Agrawal, Imieliński & Swami, SIGMOD 1993; o algoritmo Apriori vem no ano seguinte, com Agrawal & Srikant, VLDB 1994). Uma regra {A} → {B} tem três números, e o terceiro é o que importa:

• suporte — em que fração das cestas A e B aparecem juntos. Mede se a regra é frequente o bastante para ligar.
• confiança — entre as cestas que têm A, em quantas aparece B. Parece a métrica principal. Não é.
• lift — a confiança dividida pela frequência de B em geral. Responde a pergunta certa: ter A muda a chance de ter B? Lift 1 significa nenhuma relação.

A armadilha é confiança alta com lift 1. Se 60% de todas as cestas têm pão, uma regra {leite} → {pão} com 60% de confiança parece forte e não descobriu nada: pão está em 60% das cestas de qualquer maneira. Confiança alta mede a popularidade de B, não a relação entre os dois. É a versão de mercearia da linha de base do capítulo II.1.

Cerveja e fraldas: verdadeira até a descoberta, inventada a partir da ação #

Todo curso conta esta história. Vale separar o que se sustenta do que não se sustenta, e a fratura está num ponto exato. O estudo existe. Em 1992, Thomas Blischok, que dirigia um grupo de consultoria de varejo na Teradata (divisão da NCR), analisou com a equipe as cestas da Osco Drug. Ele descreve o material nas próprias palavras: "We took over 1.2 million market baskets [...] And these represented transactions from about 25 stores." A correlação foi achada, e também está na fala dele: "we did discover that between 5:00 and 7:00 p.m. that consumers bought beer and diapers."

A parte que todo mundo ensina é falsa. "Puseram a cerveja ao lado das fraldas e as vendas subiram": isto não aconteceu. Quem nega é o próprio Blischok, na mesma fala: "in reality they never did anything with beer and diapers relationships." Power fecha a apuração dizendo que os gerentes da Osco "did NOT exploit the beer and diapers relationship by moving the products closer together on the shelves". A lenda nasceu no discurso de vendas. John Earle, que diz ter trabalhado na Teradata e nesse projeto, registra que Blischok, ao falar com prospects e com a imprensa, "didn't distinguish between the actual affinities tested and our hypotheses", e acrescenta a frase que explica o mecanismo: "Our job was to sell the value of systems. Sometimes in selling, fact blurred with folklore."

E a cadeia de evidência é mais frouxa do que a história merecia. Vale olhar como esses fatos chegaram até aqui, porque o próprio Power abre a última seção da apuração com "Does everyone agree with the above account? YES and NO!". Três coisas que o texto dele deixa explícitas e que quase nunca são repetidas junto com os números:

• Power não entrevistou ninguém. Ele não pôde assistir ao evento ao vivo, viu a gravação de um webcast de 31 de julho de 2002 e recebeu a transcrição por e-mail da moderadora, Holly Michael, da Teradata.
• O webcast era da empresa que fez o estudo, celebrando os dez anos da própria lenda. A versão canônica do "fato" chega por uma peça de comunicação da parte interessada.
• A descoberta em si é contestada. Tom Fawcett, relatando em terceira mão, sustenta que Blischok inventou o exemplo e que ele "was never supported in any data that they analyzed". Ronny Kohavi diz ter chegado à pessoa que rodou as consultas (K. Heath, self joins em SQL, 1990, "50 stores over a day period") e registra que ela não achava o padrão significativo. Esses números não batem com os de Blischok: 50 lojas em um dia contra 1,2 milhão de cestas de cerca de 25 lojas.

Não conserte a lenda: olhe para a fratura. Ela é o exemplo mais barato de três coisas que o mercado trata como uma só — correlação achada ≠ decisão tomada ≠ efeito medido. O estudo, tal como Blischok o conta, produziu a primeira; a segunda nunca ocorreu; a terceira, portanto, não existe — e é justamente ela que todo mundo repete como resultado. É o mesmo padrão do capítulo II.6, onde a categoria "OLAP" também foi fabricada pelo marketing: a técnica era boa, a embalagem é que não se sustenta.

Validar sem gabarito #

Aqui está a dificuldade que separa este capítulo de todos os anteriores. Na classificação, a validação é externa: existe uma resposta certa que você não usou para treinar. No agrupamento, os candidatos a métrica são internos — calculados sobre os mesmos dados, com a mesma noção de distância que produziu os grupos. Eles medem se a partição é coerente com o critério, não se ela é verdadeira. Duas ferramentas, e o que cada uma não faz:

Silhueta. Para cada ponto, compara a distância média aos vizinhos do próprio grupo com a distância média ao grupo mais próximo. Perto de 1, bem alocado; perto de 0, na fronteira; negativo, provavelmente no grupo errado. É útil e tem um limite duro: premia a mesma geometria compacta que o k-means persegue. Silhueta alta com clusters esféricos não é confirmação independente — é o critério se elogiando.

Método do cotovelo. Plote a inércia contra k e procure onde a curva "dobra". Funciona quando a dobra é óbvia; na maioria dos dados reais ela não é, e "o cotovelo é aqui" vira leitura pessoal do gráfico — que muda de analista para analista e, pior, muda depois de você já ter uma hipótese.

E o alerta principal: "os clusters fazem sentido" é a forma mais fácil de se enganar em análise de dados. Você reconhece histórias em grupos aleatórios com uma facilidade constrangedora — dê nomes a quatro grupos de ruído e o quarto vira "os clientes de alto potencial ainda não ativados". O antídoto é declarar o critério antes e testá-lo fora: os grupos se mantêm numa amostra separada? Eles predizem alguma variável que não entrou no agrupamento (churn, receita futura, retorno de campanha)? Um critério externo vale mais que cotovelo e silhueta somados, porque é o único que pode dar errado.

Síntese — o que levar #

• Sem rótulo não há erro a minimizar: há um critério a inventar. Quem escolhe o critério decide o resultado, e a escolha não está nos dados.
• O algoritmo nunca diz "não há grupos". A pergunta é se os grupos existem fora deste conjunto de dados.
• Congele metade, resolva a outra, inverta. O k-means é um caso de otimização alternada — o padrão vale para EM, fuzzy c-means, k-medoids e para qualquer problema com duas incógnitas que se determinam mutuamente.
• k-means só enxerga grupos esféricos e de tamanho parecido, e isso está no critério, não no código. Nenhum k nem nenhuma semente conserta forma errada. E distância depende de escala: normalizar faz parte da definição do critério, não da faxina.
• PCA troca colunas por variância — e perde interpretabilidade e, às vezes, exatamente a direção que importava.
• Em regras de associação, confiança alta sem lift alto é a popularidade do item disfarçada de descoberta.
• Métricas internas (silhueta, cotovelo) medem coerência com o critério, não verdade. Critério externo vale mais que as duas somadas, porque é o único que pode dar errado.
• "Os clusters fazem sentido" não é evidência. Teste em dados embaralhados antes de acreditar em você mesmo.
• Da tríade 05–08–18: crédito não segue descoberta nem publicação. Vence quem escreve a palavra que pega.

Verificação #

1. Um colega diz que agrupamento é "classificação sem rótulo, só um pouco mais difícil". Explique por que a diferença é de natureza, e não de grau.
2. Sua diretoria quer saber quantos segmentos de cliente existem. Descreva o critério que você declararia antes de rodar qualquer algoritmo, e como você defenderia esse número se ele fosse contestado.

Estas duas não são corrigidas, e a omissão é deliberada: a segunda se ganha defendendo o critério diante de quem o contesta, que é exatamente o que uma resposta escrita não simula.