Conversão dos documentos em conjuntos

Criação dos conjuntos representativos

O objetivo desta primeira etapa é criar os conjuntos representativos dos documentos

• A informação relevante a reter depende obviamente do tipo de documento

Sem perda de generalidade, consideraremos documentos constituídos por palavras

• ou para sermos mais precisos, sequências de caracteres

A aplicação a outro tipo de documentos pode fazer-se adaptando o apresentado para sequências de caracteres

• Por exemplo, no caso de imagens pode considerar-se como equivalente à palavra o valor de cada pixel (valor inteiro ou triplo RGB)

Soluções

As soluções mais simples são:

1. conjunto de palavras que ocorrem no documento

2. conjunto das palavras “importantes”

Ambas sofrem do mesmo problema:

• não preservam informação sobre a ordem de ocorrência

A ordem de ocorrência pode ser tida em conta utilizando sequências de palavras (ou de caracteres), ideia na base dos

• também conhecidos por k-shingles

• ou simplesmente Shingles

Shingles

Um k-shingle (ou k-grama) para um documento é uma sequência de k símbolos que aparecem no documento

Os símbolos podem ser caracteres, palavras ou outra informação, dependendo da aplicação

Assume-se que documentos que têm muitos Shingles em comum são semelhantes

Utilizando Shingles, um documento D é representado pelo conjunto dos seus k-gramas C = S(D)

Similaridade

Representando um documento Di pelo seu conjunto de k-shingles Ci=S(D_i)

Uma medida natural de similaridade é a similaridade de Jaccard

• calculada com base nos conjuntos de Shingles representativos dos documentos

Escolha de k

A escolha de k não é trivial

Deve escolher-se k suficientemente grande para evitar que a maioria dos documentos tenha a maioria dos Shingles

• evitando desta forma que a generalidade dos documentos sejam representados pelo mesmo conjunto

Na prática:

• k = 5 é bom para documentos curtos

• k = 10 é mais adequado para documentos longos

Representação binária

Para simplificar cálculo de interseção e união, os documentos podem ser representado por um vetor de zeros e uns no espaço de kgramas (vetor binário)

Nesta representação a interseção e união são operações de bits (AND e OR)

Os vetores de um conjunto de documentos formam uma matriz