A abordagem de clusterização Lingo inverte a ordem tradicional de descoberta de clusters. Em vez de calcular a proximidade entre documentos e, em seguida, rotular os grupos descobertos, primeiramente tenta-se encontrar rótulos de agrupamentos (clusters) adequados e conceitualmente variados e, em seguida, atribuir documentos para os rótulos para formar grupos (OSINSKI; WEISS, 2005).
14 Que formam ângulos retos.
Na abordagem “descrição-vem-primeiro” de Lingo, a seleção cuidadosa dos candidatos a rótulo é crucial. O algoritmo deve assegurar que os rótulos são significativamente diferentes quando cobre a maioria dos tópicos nos snippets (fragmentos) de entrada. Para encontrar os candidatos a rótulo é usado Modelo de Espaço Vetorial (Vector Space Model - VSM) e Decomposição de Valores Singulares (Single Value Decomposition -SVD), sendo este último o construto matemático essencial que fundamenta a técnica Latente Semantic Index (LSI) (BERRY; DUMAIS; O´’BRIEN, 1994).
VSM é um método de recuperação de informação que utiliza operações de álgebra linear para comparar dados textuais. VSM associa um único vetor multidimensional com cada documento da coleção, e cada componente desse vetor reflete uma determinada palavra-chave ou termo relacionado com o documento. Usa-se "termo" para uma única palavra e "frase" para se referir a uma sequência de termos. Isso permite a representação de um conjunto de documentos, organizando seus vetores em uma matriz “termo-documento”. O valor de um único componente da matriz “termo-documento” depende da força do relacionamento entre o seu termo associado e o respectivo documento.
Ao contrário do VSM, LSI objetiva representar a coleção de entrada usando conceitos encontrados nos documentos, em vez dos termos literais que aparecem neles. Para fazer isso, LSI aproxima a matriz “termo-documento” original utilizando um número limitado de fatores ortogonais.
Esses fatores representam um conjunto de conceitos abstratos, cada um transmitindo alguma ideia comum a um subconjunto do conjunto de entrada.
Para o Lingo, estes conceitos são candidatos adequados a rótulos de clusters. Entretanto, sua representação matricial é difícil para o entendimento humano. Para obter rótulos concisos e informativos, precisa-se extrair o significado verbal por trás da representação vetorial dos conceitos abstratos derivados da LSI.
Entre todas as coocorrências de termos em uma coleção de documentos, frases que aparecem pelo menos um certo número de vezes na coleção de entrada, parecem ser mais significativas para os usuários, e ao mesmo tempo são relativamente fáceis de se encontrar. Eles são muitas vezes colocações (“collocations”) ou nomes próprios, tornando- os ao mesmo tempo informativo e conciso. Logo, utiliza-se eles para aproximar o significado verbal dos conceitos abstratos derivados do SVD. Lingo usa essas frases frequentes como rótulos de clusters. Uma
vez que se tenha descoberto um conjunto diversificado de rótulos, atribuem-se os documentos mais relevantes a estas usando VSM padrão. A Figura 16 apresenta uma visão geral das fases do algoritmo Lingo, que serão apresentadas na sequência.
Figura 16 - Visão geral das fases do algoritmo Lingo
Fonte: Osinski e Weiss (2005)
Pré-processamento (Preprocessing)
Nesta fase, usa-se uma combinação de três métodos comuns de pré-processamento de texto, sendo: a) stemming, uma técnica para encontrar uma representação semântica de uma palavra flexionada (geralmente um lema) para diminuir o impacto da sintaxe de uma língua; b) ignorar stop-word, para lidar com termos que ocorrem com frequência, mas que não têm nenhum significado (conjunções, artigos, etc.); e c) heurísticas de segmentação de texto, para dividir o texto em palavras e frases.
Lingo reconhece a linguagem de cada snippet separadamente e aplica o pré-processamento adequado a ele. A maioria dos algoritmos remove stop-words inteiramente. Lingo somente marca as stop-words,
porque elas podem ajudar os usuários a entender o significado de frases longas (por exemplo, "Câmara Comércio" versus "Câmara de Comércio").
Extração de frase (Phrase extraction)
A fase de extração de frase visa descobrir frases e termos individuais que poderiam potencialmente explicar os significados verbais por trás dos conceitos abstratos derivados da SVD.
Lingo requer que os rótulos de cluster apareçam no fragmento de entrada (snippet), pelo menos, um número especificado de vezes; não cruzem limites da sentença - marcadores de sentença indicam uma mudança de tópico, portanto, uma frase que se estende para além de uma sentença é improvável que seja significativa; ser uma frase frequente completa - mais longa possível, frases completas permitem descrições mais claras de clusters; não começar e nem terminar com uma stop- word.
Indução de rótulo de cluster (Cluster-label induction)
Durante a fase de indução de rótulo de cluster, Lingo identifica os conceitos abstratos que melhor descrevem a coleção de snippets de entrada e usa frases frequentes para construir uma representação legível desses conceitos. Isto produz um conjunto de rótulos, cada um dos quais determinará o conteúdo e descrição de um cluster.
Para ilustrar os conceitos apresentados nesta fase, exemplifica-se como Lingo manipula uma coleção exemplo de d = 7 títulos de documentos (Figura 17a), em que t = 5 termos (Figura 17b) e p = 2 frases (Figura 17c) aparecem mais do que uma vez e, portanto, são tratados como frequentes.
Primeiramente, Lingo constrói uma matriz termo-documento a partir dos snippets (fragmentos) de entrada. Em tal matriz, um vetor coluna representa cada trecho, e vetores de linha denotam termos selecionados para representar características dos documentos. No exemplo mostrado na Figura 18, a primeira linha representa a palavra "information", a segunda linha representa "singular", e assim por diante através dos termos na Figura 17b. Do mesmo modo, a coluna 1 representa D1 na figura Figura 17a, "large-scale singular value computations”, a coluna 2 representa D2, "software for the sparse singular value decomposition”, e assim por diante.
Nesta fase, desconsidera-se termos marcados como stop-words e termos que não aparecem mais do que um certo número de vezes (como
"software" na Figura 17a). Isto aumenta não só significativamente a eficiência de tempo do algoritmo, mas também reduz ruído entre os rótulos de clusters.
Usa-se o esquema de ponderação de peso de termos tfidf de Salton, Wong e Yang (1975) para eliminar vieses fortes. Calcula-se os valores na matriz A (Figura 17) usando tfidf e depois normaliza-se cada comprimento do vetor coluna.
Figura 17 - Dados de entrada na fase de indução de rótulo: (a) documentos, d = 7; (b) termos, t = 5; e (c) frases, p = 2
Fonte: Osinski e Weiss (2005)
Fonte: Osinski e Weiss (2005)
O processo de descobrir conceitos abstratos baseia-se no SVD da matriz termo-documento A, que a divide em três matrizes (U, S e V) tal que A = USVT.
Uma das propriedades da SVD é que as primeiras r colunas de U (onde r é o ranking de A) formam uma base ortogonal para o espaço de termos da matriz de entrada. Em álgebra linear, vetores de base de espaço linear podem servir como blocos de construção para a criação de vetores sobre aquele espaço. Seguindo esta intuição, cada bloco de construção deve carregar uma das ideias referidas na coleção de entrada. Assim, para o Lingo, os vetores de base (isto é, as colunas do vetor em U) são exatamente o que ele configurou encontrar: uma representação vetorial dos conceitos abstratos dos snippets.
Na maioria das situações, considerando todos os r vetores base como conceitos abstratos resultaria em um número não gerenciável de clusters - normalmente próximo ao número de snippets. Portanto, Lingo utiliza os valores singulares da matriz A (encontram-se na diagonal da matriz S da SVD) para calcular quantas colunas de U devem avançar para a próxima fase do algoritmo.
Suponha que o cálculo resulte em k = 2, sendo definido como o número desejado de clusters do exemplo. Consequentemente, nos processamentos seguintes utiliza-se Uk que consiste nas primeiras k
colunas de U (mostrada na Figura 19a).
Figura 19 - Matrizes na fase de indução de rótulo: (a) matriz de conceitos abstratos U, (b) matriz dos candidatos a rótulo de cluster P, e (c) matriz dos candidatos a rótulo de cluster (conceito abstrato) M.
Fonte: Osinski e Weiss (2005)
Duas características dos vetores base são importantes aqui. Em primeiro lugar, os vetores são pares ortogonais, o que deve resultar em uma rica diversidade entre os conceitos abstratos descobertos. Em segundo lugar, os vetores base são expressos no espaço de termos da matriz A e assim, podem ser frases frequentes descobertas na fase anterior. Lingo usa a medida de distância clássica do cosseno para comparar os vetores e calcular qual frase ou palavra será a melhor representação verbal do conceito abstrato.
Considera-se termos individuais, nesta fase, porque é possível que nenhuma das frases frequentes descreva um conceito abstrato melhor do que um único termo.
Para cada frase frequente e um único termo frequente, Lingo cria um vetor coluna sobre o espaço de termos da matriz A. Quando montados conjuntamente, estes vetores formam uma matriz termo- documento P de frases e termos frequentes (Figura 19b). No exemplo, a coluna 1 corresponde a frase "singular value," a coluna dois corresponde a "information retrieval", a coluna 3 corresponde a "information" (termo único), assim por diante.
Assumindo vetores de coluna de ambas U e P normalizados pelo comprimento, como no exemplo, o problema do calcular a distância cosseno entre cada par conceito abstrato – frase-ou-termo fica reduzido a uma simples multiplicação de matriz.
As linhas da matriz resultante M (Figura 19c) representam conceitos abstratos, suas colunas representam frases e termos individuais, e os valores individuais são as similaridades calculadas através do cosseno. Assim, em uma única linha, o máximo componente
indica a frase ou termo único que melhor se aproxima do conceito abstrato correspondente.
No exemplo, o primeiro conceito abstrato está relacionado com a "singular value", enquanto o segundo está relacionado com "information retrieval". Como os valores na matriz M variam de 0,0 (nenhuma relação) a 1,0 (combinação perfeita), o Lingo também usa os componentes máximos componentes como pontuações rótulo de cluster. Alocação do conteúdo do cluster (Cluster-content allocation)
O processo de alocação de conteúdo ao cluster assemelha-se a recuperação de documentos baseada em VSM, só que em vez de uma consulta, Lingo combina cada snippet (trecho) de entrada contra uma série de queries, cada uma das quais é um único rótulo de cluster. Assim, para um determinado rótulo de consulta, se a similaridade entre um snippet e o rótulo exceder um limiar pré-definido, Lingo aloca o snippet ao cluster correspondente.
As atribuições de valores limiares variam entre 0,0 e 1,0. Valores limiares mais elevados resultam em mais documentos sendo colocados em clusters, o que pode diminuir a precisão da atribuição. Valores menores conduzem a grupos menores com maior precisão de atribuição, mas com recall menor. A atribuição do valor limiar é uma questão de preferência do usuário. Verifica-se que os limiares entre 0,15 e 0,30 produzem os melhores resultados.
A última operação da fase de alocação é calcular a pontuação do grupo como um produto da pontuação do rótulo e do número de snippets do grupo. A Figura 20 mostra os resultados para o exemplo.
Figura 20 - Resultado final da alocação de conteúdo ao cluster16