|
|
DEPARTAMENTO
DE ENGENHARIA DA ELECTRÓNICA Projecto
Final de Curso (Ano lectivo 2004/2005) |
Classificação de Conteúdos
Aluno: António Serra
Orientador:
Artur Ferreira
Resumo
Neste trabalho trata-se
a classificação de conteúdos, em formato de texto com base no algoritmo de
compressão de Lempel e Ziv. O método consiste na concatenação do texto a
classificar com os textos de referência das classes a analisar. Em seguida,
realiza-se compressão sobre estes textos e usa-se a dimensão do texto
comprimido como característica de classificação. O método é aplicado à
classificação de língua, autor, assunto e
E-Mail SPAM.
Realizam-se dois
classificadores. O primeiro, escrito em linguagem ‘C’, com base na biblioteca
de compressão ZLib, e o segundo que consiste numa optimização sobre o primeiro,
é escrito em linguagem C#, sobre a biblioteca SharpZipLib.
Nos testes realizados,
conclui-se que a classificação de língua obtém 100% de acerto, mesmo nas
situações que envolvem línguas de origem comum. A classificação de autor
apresenta erros derivados da dificuldade de definir um estilo literário, bem
como do facto de o mesmo autor poder usar estilos de escrita distintos. Verifica-se
que o pré-carregamento e a ordenação das palavras do dicionário por frequência
de ocorrência melhoram os resultados de classificação.
Na classificação de SPAM
tem-se em conta a ocorrência de falsos positivos, ou seja, a situação em que
uma mensagem legítima é classificada como SPAM, dado que esta situação é mais
gravosa do que a contrária. O filtro de SPAM, designado por LZSPAMFilter, é
integrado no cliente de E-Mail Microsoft Outlook através do Outlook Object Model (OOM).
Conclui-se que o LZSPAMFilter
tem baixa complexidade e desempenho aceitável em termos de tempo de execução,
percentagem de acerto e falsos positivos através da comparação com outro filtro
de SPAM. Constata-se que o tempo de classificação médio por mensagem é de cerca
de 20 mS e que se atingem situações nas quais a ocorrência de falsos positivos
se situa na ordem dos 8 %.
Classificação baseada em compressão
O classificador segue
o método BCL proposto por Benedetto, Caglioti e Loreto. Este baseia-se na taxa
de compressão, obtida pelo codificador Lempel-Ziv 77, usando como dicionário um
texto de referência previamente escolhido. A figura 1 ilustra o funcionamento
deste codificador.
Figura
1 – Codificador Lempel-Ziv 77 (LZ77).
A característica de classificação é a Divergência de Kullback-Leibler, a
qual é estimada através de taxas de compressão. O texto a classificar é concatenado, sucessivamente,
com cada um dos textos de referência de cada classe, sendo comprimido de
seguida. Registam-se os comprimentos da descrição com compressão para cada
referência e para as referências concatenadas com o texto a classificar. Sejam 
os textos de
referência e 
o texto a
classificar; B é classificado como pertencente
à classe 
tal que
,
ou seja, a classe de B é a mesma do texto Ai que verifica a expressão acima. A
figura 2 ilustra o funcionamento do método BCL. O dicionário é estabelecido a
partir do texto de referência Ai e o
texto B é codificado com esse dicionário. Caso Ai e B sejam textos semelhantes, teremos uma taxa de compressão
elevada; caso contrário, a taxa de compressão será baixa.
Figura
2 – Ilustração do método BCL.
O algoritmo seguido para a classificação
é o seguinte:
Entradas:
·
Vector de textos de classes conhecidas (Ai), 
·
Texto de classe desconhecida (B)
Saída:
·
Classe de B
Prólogo:
·
Comprimir
isoladamente cada texto de referência Ai e registar a dimensão da sua
descrição com compressão
Ciclo:
Para
todos os Ai:
·
concatenar
Ai com B obtendo (Ai+B)
·
comprimir
Ai+B e registar a dimensão da sua descrição com compressão
Epílogo:
·
Seleccionar
a menor descrição com compressão de Ai+B: 
,
·
Retornar: B é da classe de Ai
Resultados obtidos
Classificação de Língua
Aplicando o algoritmo anterior, obtiveram-se os resultados para a
classificação de Língua, apresentados na tabela 1.
|
|
CS |
DA |
DE |
EN |
ES |
ET |
FR |
HR |
IT |
LT |
PL |
PT |
RU |
|
CS |
12816 |
13879 |
13785 |
13569 |
14105 |
14016 |
12798 |
13554 |
13023 |
13020 |
13455 |
13435 |
16506 |
|
DA |
14094 |
12676 |
13662 |
13498 |
14107 |
13988 |
12728 |
13685 |
12987 |
12983 |
13568 |
13424 |
16504 |
|
DE |
14197 |
13733 |
12294 |
13443 |
14132 |
14015 |
12718 |
13725 |
13039 |
12982 |
13466 |
13384 |
16495 |
|
EN |
14204 |
13762 |
13609 |
12254 |
13973 |
13964 |
12643 |
13669 |
12878 |
12783 |
13456 |
13270 |
16523 |
|
ES |
14205 |
13822 |
13770 |
13468 |
12814 |
13980 |
12602 |
13623 |
12819 |
12825 |
13566 |
13070 |
16493 |
|
ET |
14206 |
13822 |
13776 |
13542 |
14101 |
12652 |
12749 |
13586 |
12969 |
12968 |
13492 |
13416 |
16500 |
|
FR |
14219 |
13795 |
13661 |
13450 |
13928 |
13986 |
11397 |
13664 |
12851 |
12885 |
13537 |
13278 |
16502 |
|
HR |
14230 |
13861 |
13766 |
13560 |
14065 |
13958 |
12745 |
12119 |
12973 |
12976 |
13485 |
13391 |
16517 |
|
IT |
14232 |
13795 |
13712 |
13437 |
13867 |
13919 |
12572 |
13579 |
11720 |
12758 |
13516 |
13193 |
16506 |
|
LT |
14233 |
13792 |
13653 |
13328 |
13847 |
13931 |
12623 |
13626 |
12774 |
11678 |
13518 |
13236 |
16530 |
|
PL |
14254 |
13887 |
13738 |
13500 |
14168 |
14020 |
12802 |
13632 |
13070 |
13055 |
12055 |
13482 |
16500 |
|
PT |
14299 |
13824 |
13690 |
13472 |
13752 |
13964 |
12620 |
13632 |
12838 |
12832 |
13516 |
11380 |
16466 |
|
RU |
14697 |
14356 |
14219 |
14079 |
14590 |
14444 |
13268 |
14158 |
13533 |
13538 |
14023 |
13895 |
14508 |
Tabela
1 – Valores obtidos para L(Ai+B) – L(Ai),
com textos de diferentes línguas.
Destacam-se,
ainda da tabela 1, os valores sublinhados que, representam a segunda
classificação possível para o texto B,
ou seja, a língua mais próxima daquela na qual o texto foi classificado. No
caso do Português, verifica-se que a língua mais próxima é o Espanhol, e
reciprocamente, a língua mais próxima do Espanhol é o Português. Estes
resultados verificam-se pela análise da penúltima linha e penúltima coluna da
tabela 1.
Classificação de Autor
Usando um dicionário de 512 Bytes, foram
realizados testes com 5 textos de cada um dos seguintes autores portugueses:
Luís de Camões, Eça de Queiroz e José Saramago. Também se realizaram testes com
10 textos, escritos em inglês, dos autores William Shakespeare, Mark Twain e
Júlio Verne. Os resultados dos testes são apresentados sob a forma de matriz de
confusão nas tabelas 2 e 3; as linhas representam a classe correcta e as
colunas a saída do classificador.
|
|
Eça |
Camões |
Saramago |
|
Eça |
0,800 |
0,000 |
0,200 |
|
Camões |
0,000 |
0,800 |
0,200 |
|
Saramago |
0,200 |
0,000 |
0,800 |
Tabela 2 – Matriz de Confusão da classificação de autores
portugueses.
|
|
Twain |
Verne |
Shakespeare |
|
Twain |
0,300 |
0,700 |
0,000 |
|
Verne |
0,000 |
1,000 |
0,000 |
|
Shakespeare |
0,000 |
0,000 |
1,000 |
Tabela 3 – Matriz de Confusão da
classificação de autores em língua inglesa.
As probabilidades de erro de
classificação para estes dois casos foram de 
e 
, para os autores de língua portuguesa e de língua inglesa,
respectivamente. Note-se que não existem erros na classificação dos textos de
Verne e de Shakespeare.
Dos resultados obtidos verifica-se
que o classificador erra na classificação por autor, ao contrário da
classificação por língua. Este facto deve-se a ser mais difícil distinguir
estilos literários, através deste método, comparativamente com a distinção da
língua. Por outro lado, o mesmo autor pode escrever em diferentes estilos.
Verifica-se que o método é mais sensível à língua na qual o texto está escrito,
do que aos detalhes relativos ao estilo de escrita.
Classificação de Assunto
Para os testes de classificação por
assunto usaram-se textos de notícias da agência noticiosa Reuters. Estes textos
foram previamente classificados, sendo que alguns são multi-categoria, tendo a
particularidade de ser de menor dimensão quando comparados com os textos
utilizados no teste anterior.
Os resultados foram
obtidos com e sem pré-carregamento de dicionário. A tabela 4 mostra a matriz de
confusão sem pré-carregamento de dicionário e a tabela 5 mostra a matriz de
confusão com pré-carregamento de dicionário. A dimensão do dicionário usado foi
de 512 Bytes.
|
|
Crude |
Earn |
Grain |
Interest |
|
Crude |
0,893 |
0,053 |
0,046 |
0,008 |
|
Earn |
0,053 |
0,924 |
0,008 |
0,015 |
|
Grain |
0,092 |
0,015 |
0,885 |
0,008 |
|
Interest |
0,145 |
0,046 |
0,092 |
0,718 |
Tabela 4 – Matriz de confusão sem pré-carregamento de
dicionário.
|
|
Crude |
Earn |
Grain |
Interest |
|
Crude |
0,924 |
0,046 |
0,023 |
0,008 |
|
Earn |
0,053 |
0,924 |
0,008 |
0,015 |
|
Grain |
0,092 |
0,015 |
0,893 |
0,000 |
|
Interest |
0,176 |
0,008 |
0,084 |
0,733 |
Tabela 5 – Matriz de confusão com pré-carregamento de
dicionário.
As probabilidades de erro de
classificação são 
e 
, respectivamente. Pelos valores das probabilidades
de
erro
pode-se
concluir
que
o
pré-carregamento do dicionário melhora o acerto de classificação. Verifica-se
que existem melhorias na classificação dos textos das classes Crude, Grain e
Interest. Para textos de dimensão reduzida verifica-se que o pré-carregamento
do dicionário é vantajoso, conseguindo elevada taxa de compressão, no início da
codificação, caso o texto carregado seja semelhante ao texto a codificar.
Classificação de SPAM com e sem pré-carregamento do dicionário não
ordenado
Para os testes de
classificação de SPAM usaram-se textos das 4 categorias do conjunto de textos
da agência noticiosa Reuters, com dicionário de 512 Bytes. Estes textos (da
classe Não-SPAM) têm dimensão semelhante
às mensagens típicas de SPAM, cerca de 3 KBytes. Os textos de SPAM foram
previamente classificados como tal pelo IPLnet (através do método SpamAssassin)
e verificados individualmente. Estes dois conjuntos perfazem 260 textos.
Os resultados da classificação
de SPAM, sem pré-carregamento e com pré-carregamento, apresentam-se nas tabelas
6 e 7, respectivamente.
|
|
Não-SPAM |
SPAM |
|
Não-SPAM |
0,385 |
0,615 |
|
SPAM |
0,000 |
1,000 |
Tabela 6 – Matriz de confusão da classificação por SPAM
sem pré-carregamento de dicionário.
|
|
Não-SPAM |
SPAM |
|
Não-SPAM |
0,815 |
0,185 |
|
SPAM |
0,000 |
1,000 |
Tabela 7 – Matriz de confusão da classificação por SPAM
com pré-carregamento de dicionário.
As probabilidades de erro de
classificação são 
e 
respectivamente. Pelos
valores das probabilidades de erro conclui-se que o pré-carregamento do
dicionário melhora o acerto na classificação. Também no caso dos Falsos
Positivos (FP), ou seja, mensagens legítimas classificadas como SPAM, se
verifica a vantagem do pré-carregamento do dicionário: FP=61,5% e FP=18,5%, sem
e com pré-carregamento de dicionário, respectivamente. Neste caso o conteúdo do
dicionário usado não estava ordenado por frequência de ocorrência.
Classificação de SPAM com
e sem pré-carregamento do dicionário ordenado
A figura 3 mostra um
exemplo da ordenação do dicionário. Como exemplo, foram escolhidas as dez
palavras mais frequentes do dicionário de SPAM compilado pelo autor do
trabalho. Em a) o dicionário é pré-carregado desordenado, ou seja, as palavras
seguem a ordem pela qual foram recolhidas. Em b) o dicionário é pré-carregado
ordenado, ou seja, as palavras foram ordenadas pela frequência de ocorrência,
destacando-se a posição junto do LAB da palavra mais frequente “FONT”, com o
objectivo, já referido anteriormente, de aumentar o seu tempo de permanência no
dicionário.
Figura 3
– Exemplo da ordenação do dicionário: a) o dicionário é pré-carregado com as
palavras desordenadas; b) o dicionário é pré-carregado com as palavras
ordenadas por frequência de ocorrência, sendo a mais frequente a que se
encontra mais próxima do LAB.
Na
tabela 8 mostram-se os resultados obtidos na classificação sem pré-carregamento
de dicionário ordenado, salientando a melhoria do valor de FP face ao
apresentado na tabela 6. A probabilidade de erro de classificação é 
e FP=20,8%.
|
|
Não-SPAM |
SPAM |
|
Não-SPAM |
0,792 |
0,208 |
|
SPAM |
0,008 |
0,992 |
|
|
|
|
Tabela 8 – Matriz de confusão da classificação de SPAM sem
pré-carregamento do dicionário e desordenado.
A
tabela 9 apresenta os resultados obtidos na classificação com pré-carregamento
do dicionário ordenado. Aqui é de salientar também o melhor resultado nos FP
face aos resultados apresentados na tabela 7. A probabilidade de erro de
classificação é 
e FP=6,9%.
|
|
Não-SPAM |
SPAM |
|
Não-SPAM |
0,931 |
0,069 |
|
SPAM |
0,015 |
0,985 |
Tabela 9 – Matriz de confusão da classificação de SPAM com
o dicionário pré-carregado e ordenado.
A partir destes resultados, conclui-se
que o pré-carregamento do dicionário bem como a sua ordenação melhora a 
e os FP. O valor de FP=0,069, traduzido para número de
mensagens corresponde a 0,069*130=9 mensagens, ou seja, em 130 mensagens não
SPAM, 9 delas são classificadas erradamente como SPAM.
Integração
com cliente de E-Mail Microsoft Outlook
A figura 4 ilustra a
integração entre as entidades cliente de E-Mail e classificador. As
funcionalidades do classificador, as quais existem de forma autónoma das do
cliente de E-Mail, são adicionadas a este último através do seu modelo de
objectos, o qual define uma API (Application Programming Interface). Através
desta API executam-se acções tais como o pré-carregamento dos dicionários, a
sua actualização e a classificação. O cliente de E-Mail, no caso da integração,
chama os métodos da API do classificador sempre que pretenda realizar a
classificação das mensagens: caso o
cliente de E-Mail disponibilize o
registo em eventos, a classificação ocorre de forma automática.
Figura 4
– Integração do classificador com o cliente de E-Mail.
Modelo de Objectos do MS
Outlook
O MSOutlook exporta as suas
funcionalidades ao programador através do OOM (Outlook Object Model). Através
deste modelo, tem-se acesso a mensagens de correio, contactos, calendário,
notas, tarefas e à interface gráfica da aplicação. No âmbito deste trabalho
será abordada a interacção com os objectos que manipulam as mensagens de
correio. A hierarquia de objectos do MSOutlook, muito simplificada, está
representada na figura 5. As mensagens de E-Mail são manipuladas através destes
objectos.
Figura 5 – Modelo de objectos do
Outlook 2003 (parcial).
O OOM caracteriza-se por
ser extenso, dado o elevado número de entidades que o compõem. Contudo, segue
uma organização lógica assente em padrões de desenho (design patterns) conhecidos,
tais como iterador e composição. Por exemplo, manipular a lista de contactos é
semelhante ao acesso às mensagens de correio. Desta forma, logo que se aprenda
a manipular a lista de contactos, manipular mensagens de correio é bastante
semelhante. Para ter acesso ao OOM no desenvolvimento de aplicações é
necessário instalar o MSOutlook Primary Interoperability Assembly (PIA),
disponibilizado na instalação do Microsoft Office 2003, o qual não é instalado
por omissão. O PIA é disponibilizado, após a instalação personalizada do
Microsoft Office 2003 e a selecção do suporte para desenvolvimento de
aplicações em .NET.
COM Add-ins
O Microsoft Office 2003
suporta uma arquitectura uniforme para a implementação de novas funcionalidades,
através de componentes designados de COM (Component Object Model) Add-ins.O COM
Add-in é uma aplicação servidora, compilada no formato dll, que se executa no
espaço de endereçamento da aplicação anfitriã. O formato dll do Add-in tem a
ver com desempenho. Pelo facto de se executar no espaço de endereçamento da
aplicação anfitriã não usa comunicação entre processos evitando o peso
computacional associado. Contudo a codificação do Add-in deve ser tal que não
degrade o desempenho da aplicação anfitriã ou provoque erros no seu
funcionamento.
As aplicações Microsoft
Office, e em particular o MSOutlook, tomam conhecimento dos Add-in existentes
através do registo do sistema (Windows Registry). No registo do sistema
encontra-se a informação através da qual a aplicação anfitriã obtém o modo como
o Add-in é posto em execução bem como quais os utilizadores com acesso.
Para que a comunicação entre o Add-in e a sua aplicação
anfitriã seja possível, este tem de implementar a interface IDTExtensibility2,
em particular os métodos: OnConnection, OnDisconnection, OnAddInsUpdate, OnStartupComplete
e OnBeginShutdown.
Implementação
O classificador
implementado para os testes de classificação de SPAM serviu de base à
implementação da dll que realiza a classificação no Add-in. Este classificador
tem por base a biblioteca SharpZipLib escrita na linguagem C#. Desta biblioteca
usaram-se os métodos do espaço de nomes ICSharpCode.SharpZipLib.Zip.Compression,
que contém uma implementação do LZ77.
A implementação do
Add-in foi realizada através do “Assistente de Add-ins” do Microsoft Visual
Studio .NET 2003, sendo necessário redefinir os métodos referidos na secção
anterior. A implementação do Add-in assenta no padrão de desenho observador, o Add-in
regista-se no evento NewMailEvent disponibilizado pelo OOM e sempre que este
ocorre realiza a classificação das mensagens recebidas. Caso a mensagem seja
classificada como SPAM, esta é movida para a pasta JunkMail, sendo-lhe
concatenada a palavra SPAM no campo assunto, tal como apresentado na figura 6.
|
private void applicationObject_NewMail() { Outlook.NameSpace
OlNameSpace=
applicationObject.GetNamespace("MAPI"); Outlook.MAPIFolder inbox= OlNameSpace.GetDefaultFolder(Outlook.OlDefaultFolders.olFolderInbox); Outlook.MAPIFolder junk= OlNameSpace.GetDefaultFolder(Outlook.OlDefaultFolders.olFolderJunk); Outlook.Items items=inbox.Items; string
result; foreach(Outlook.MailItem
message in items) { if(message.UnRead) { result=filter.classify(message.Body); if(result=="SPAM") { message.Subject=result+"
:"+message.Subject; message.Move(junk); } } } } |
Figura 6
– Invocação do classificador no MSOutlook
Resultados
A tabela 10 mostra os resultados
obtidos na classificação das mensagens do conjunto de teste.
|
|
Não-SPAM |
SPAM |
|
Não-SPAM |
0,915 |
0,085 |
|
SPAM |
0,174 |
0,826 |
Tabela 10 – Matriz de confusão da
classificação de SPAM pelo LZSPAMFilter.
O valor obtido da probabilidade de
erro foi 
. O valor de FP=8,5%, traduzido para número de mensagens
corresponde a 0,085*47=4 mensagens no total de 47 mensagens Não-SPAM (apenas 4
delas são classificadas erradamente como SPAM).
Características
·
Filtro
anti-SPAM com baixa complexidade.
·
Dicionário
de 512 bytes ordenado e pré-carregado.
·
Tempo
de classificação aproximado de 20 mS por mensagem.
·
Taxa
de acerto superior a 80%.
·
Taxa
de FP aceitável, para mensagens de pequena dimensão (300 bytes) - Erra 4
mensagens em 47.
·
Desenvolvido
de forma independente do cliente de E-Mail, mas facilmente integrável neste ou
noutros.
Documentação
de Projecto