jetivo do processo. Estas tarefas podem ser preditivas ou descritivas (Conrado et al., 2009).
• Tarefas Preditivas: consistem na generalização de exemplos ou experi- encias passadas com respostas conhecidas. Essas tarefas aplicam os chamados modelos de aprendizado de máquina supervisionado, devido a que as categorias são sempre pré-conhecidas e disponíveis junto aos dados. Esses modelos podem ser divididos em tarefas de classificação ou regressão.
• Tarefas Descritivas: consistem na identificação de comportamentos in- trínsecos da coleção de textos, sendo que esses dados são exemplos não rotulados. Nessas tarefas são usados modelos de aprendizado de má- quina não-supervisionado, e as principais tarefas são regras de associa- ção, agrupamento de dados (clustering), sumarização e visualização. Em tarefas de agrupamento, o objetivo é organizar um conjunto de obje- tos em grupos, baseados em uma medida de proximidade, na qual objetos de um mesmo grupo são altamente similares entre si, mas dissimilares em relação aos objetos de outros grupos (Everitt et al., 2001). Em outras pa- lavras, o agrupamento é baseado no princípio de maximizar a similaridade interna dos grupos e minimizar a similaridade externa dos grupos. Este mé- todo de agrupamento, pertence aos métodos de aprendizado de máquina não- supervisionados. A diferença deste método com os algoritmos de classificação é que este não possui classes ou rótulos predefinidos para treinamento de um modelo (Jain et al., 1999), (Han e Kamber,2006).
O processo de agrupamento depende de dois fatores principais: (1) uma medida de proximidade e (2) uma estratégia de agrupamento. As medidas de proximidade determinam como a similaridade entre dois objetos é calculada. Sua escolha influencia a forma como os grupos são obtidos e depende dos tipos de variáveis ou atributos que representam os objetos. As estratégias de agrupamento são métodos e algoritmos para definição dos grupos. Em geral, pode-se classificar os algoritmos de agrupamento em métodos particionais e métodos hierárquicos.
Medidas de Proximidade
A escolha da medida de proximidade para calcular quão similares são dois objetos é fundamental para aplicar técnicas de classificação, agrupamento, entre outros. Essa escolha depende das características do conjunto de da- dos, principalmente dos tipos e escala dos dados. As medidas de proximi- dade podem calcular tanto a similaridade quanto a dissimilaridade (ou distân- cia) entre objetos. A seguir, é descrita a medida de similaridade comumente utilizada em dados textuais: Cosseno. Para tal, considere dois documentos xi = (xi1, xi2, ..., xim) e xj = (xj1, xj2, ...xjm), representados no espaço vetorial m-
dimensional, no qual cada termo da coleção representa uma dessas dimen- sões.
A medida de similaridade Cosseno é definida de acordo com o ângulo cos- seno formado entre os vetores de dois documentos, conforme mostrado na Equação2.1 (Tan et al.,2005;Feldman e Sanger, 2006).
cosseno(xi, xj) = xi · xj |xi||xj| = Pm l=1xilxjl pPm l=1x2il q Pm l=1x2jl (2.1) O valor da medida está no intervalo [0,1]. Assim, se o valor da medida de similaridade Cosseno é 0, o ângulo entre xi e xj é 90◦, ou seja, os documentos
não compartilham nenhum termo. Por outro lado, se o valor da similaridade for próximo a 1, o ângulo entre xi e xj é próximo de 0◦, indicando que os
documentos compartilham termos e são similares.
Pode-se encontrar uma variedade de medidas de proximidades na litera- tura. Nessa seção, foi apresentada a medida de cosseno que está relacionada com este projeto. Uma revisão mais extensa está disponível nos trabalhos de
Everitt et al.(2001) e Tan et al.(2005). Estratégias de Agrupamento
Os métodos de agrupamento podem ser classificados considerando diferen- tes aspectos. Em geral, as estratégias de agrupamento podem ser organizadas em dois tipos: (1) agrupamento particional e (2) agrupamento hierárquico. No agrupamento particional a coleção de documentos é dividida em uma partição simples de k grupos, como ilustrado na Figura 2.4. Enquanto no agrupa- mento hierárquico é produzido uma sequência de partições aninhadas, ou seja, a coleção textual é organizada em grupos e subgrupos de documentos, como ilustrado na Figura 2.5(Feldman e Sanger,2006).
Figura 2.4: Exemplo de agrupamento de documentos particional (Rossi,2011)
Figura 2.5: Exemplo de um dendrograma obtido por um agrupamento de do- cumentos hierárquico (Rossi,2011)
SegundoZhao e Karypis(2002), as hierarquias de grupos obtidas utilizando algoritmos de agrupamento hierárquicos provêm uma visão dos documentos em diferentes níveis de granularidade, o que facilita a visualização e a intera- ção ao explorar uma grande quantidade de documentos.
Os algoritmos de agrupamento hierárquicos podem ser divididos em aglo- merativos ou divisivos. Nos algoritmos de agrupamento hierárquico divisivos, inicialmente todos os objetos estão contidos em um único grupo, e então, são realizadas sucessivas divisões nas partições até que se tenha um objeto por grupo ou até que um critério de parada seja atingido. Já os algoritmos de agrupamento hierárquicos aglomerativos, inicialmente cada objeto corres- ponde a um grupo. A partir disso, são aglomerados pares de grupos con- forme algum critério de parada seja atingido. O resultado de um algoritmo de agrupamento hierárquico aglomerativo é uma representação denominada den- drograma, como a apresentada na Figura 2.5. Essa representação mostra os grupos e subgrupos obtidos pelo algoritmo de agrupamento, e a similaridade entre os grupos da hierarquia (Rossi,2011).
A diferença principal entre os algoritmos de agrupamento hierárquico aglo- merativo está no critério de seleção do par de grupos mais próximo. Os três critérios mais conhecidos são:
• Single-Link (Everitt et al., 2001; Sneath, 1957): utiliza o critério de vizi- nho mais próximo, no qual a distância entre dois grupos é determinada pela distância do par de documentos mais próximos, sendo cada docu- mento pertencente a um desses grupos.
• Complete-link (Everitt et al., 2001; Sorensen, 1948): utiliza o critério de vizinho mais distante, ao contrário do Single-Link, e a distância entre dois grupos é a maior distância entre um par de documentos, sendo cada documento pertencente a um grupo distinto.
• Average-Link (Everitt et al., 2001; Sokal e Michener, 1958): a distância entre dois grupos é definida como a média das distâncias entre todos os pares de documentos em cada grupo, cada par é composto por um documento de cada grupo.