K-DIJKSTRA4DOC: UMA REPRESENTAÇÃO E CLUSTERIZAÇÃO DE DOCUMENTOS USANDO GRAFO DIRECIONADO

No que se diz respeito a problemas de mineração de texto, a clusterização de documentos é um problema que consiste em encontrar grupos de documentos, dado um coleção, com características semelhantes. No trabalho, usaremos uma coleção de documentos (20 newsgroups), onde cada documento dessa coleção será representado por vértice de um grafo, e neste será aplicado a técnica de clusterização K-Means utilizando Dijkstra para encontrar a distancia entre os vértices (documentos).

Palavras-chave: clusterização, documentos, k-means, dijkstra, grafo.

Link para o trabalho acadêmico.
Autores:
– João Marcos (Linkedin)
– Alex Souza (Linkedin)

Coleta e Pré-Processamento

É umas das fases mais importantes e custosas do processo, é o alicerce para toda a análise que vem a seguir, ou seja, quanto mais tempo se investir nessas fases, menos tempo será gasto futuramente.

Para esse trabalho foi utilizado a coleção de documentos: 20 Newsgroups, é uma coleção em inglês, que contém 18.846 documentos que estão quase que uniformemente distribuídos em 20 categorias distintas.
– Exemplo: tecnologia, política, religião, esporte, entre outras. Algumas dessas categorias estão intimamente relacionadas, enquanto outras não tem relação alguma com as outras.

Ferramentas

É utilizado a ferramenta de desenvolvimento Python na versão 3 e algumas bibliotecas específicas para texto, para cálculos matriciais, para representação em grafos, entre outras. Podemos destacar:

1. NTLK (Natural Language Toolkit é um conjunto de ferramentas open source escritas em Python e para Python, para a manipulação de linguagem natural.)
2. SKLearn (É uma biblioteca de aprendizado de máquina de código aberto para a linguagem de programação Python. Ela inclui vários algoritmos de classificação, regressão e agrupamento incluindo máquinas de vetores de suporte, florestas aleatórias, gradient boosting, K-Means e DBSCAN, e é projetada para interagir com as bibliotecas Python numéricas e científicas NumPy e SciPy.)
3. Numpy (É um pacote para a linguagem Python que suporta arrays e matrizes multidimensionais, possuindo uma larga coleção de funções matemáticas para trabalhar com estas estruturas.)
4. Networkx (É uma biblioteca Python para estudo de grafos e redes)

Representação de documentos

– Utilização de TF-IDF

A frequência de um termo (tf) é uma medida utilizada que considera o número de ocorrências do termo em um documento. O valor dos termos pode ser calculado também levando em consideração, além da frequência de um termo, o fator relacionado a frequência inversa do documento (idf) favorecendo termos que aparecem em poucos documentos de uma coleção.

E resultando em uma  Matriz de Adjacência: Documento X Documento.

Explicada em detalhes no artigo.

Clusterização (Algoritmo – Não Supervisionado)

A solução desenvolvida busca encontrar grupos de documentos através de um algoritmo baseado no K-Means, utilizando o algoritmo de Dijkstra para encontrar o melhor caminho entre vértices (documentos).

K-Means

Os algoritmos de agrupamento de dados (clustering) reúnem um conjunto de objetos em subconjuntos ou clusters, que sejam coerentes internamente, mas claramente diferentes uns dos outros. Desta maneira, os objetos de um mesmo cluster devem ser o mais parecidos possíveis, e objetos de um cluster devem ser tão diferentes quanto possível dos documentos em outros clusters.

Dijkstra

O algoritmo de Dijkstra tem um conjunto de passos que permite encontrar um caminho de menor custo entre dois vértices de um grafo valorado. Não é, portanto, necessário que o caminho seja hamiltoniano, apesar de continuar sendo uma árvore. Há, dessa forma, sempre um vértice de início e um vértice final, conectados por diversos vértices intermediários.

K-Dijkstra4Doc

O K-Dijkstra4Doc é o nome dado ao método usado neste trabalho para encontrar grupos em um grafo de documentos, baseado em K-Means e usando Dijkstra para encontrar o caminho mínimo entre vértices.

Avaliação e Resultados O experimento realizado neste trabalho consistiu em avaliar o tempo de convergência do algoritmo em algumas variações (k documentos correlacionados, inicialização dos centroides), assim como uma análise das categorias definidas na coleção de documentos.

É usado 50 documentos de 3 categorias da coleção, definindo assim o número de k centroides. A Tabela 1, apresenta os resultados para a primeira estratégia de definição do centroide. A Tabela 2, apresenta os resultados da segunda estratégia. A coluna “Análise de categoria” apresenta o total de documentos agrupados corretamente de acordo com as categorias definidas na coleção.

As Figuras 4 e 5 apresentam um exemplo de um grafo extraído dos experimentos.

Os resultados obtidos foram satisfatórios, uma vez que é um método não supervisionado, que encontra grupos de documentos de forma natural, levando em conta a correlação entre documentos.

Algoritmo e Resultados (Google Colab)