Embed Size (px)
Citation preview
Classificação de conteúdo em blogsEvelin Amorim e Vitor DantasAprendizado de MáquinaDepto. de InformáticaPUC-Rio
Definição do Problema•Páginas web contém, além do seu conteúdo
principal:▫ Barras de menu, banners, links de anunciantes,
links de auxílio à navegação etc.
•A correta identificação do conteúdo relevante é importante para diversas aplicações:▫ Detecção de páginas duplicadas, classificação
do conteúdo, mineração de dados
Objetivo
•Dada uma página web (um blog), classificar cada elemento em uma de três classes:▫Título▫Post▫Lixo
<html><body><a href="home.html">home page</a><p>text about something</p><hr></body></html>
<html><body><a href="home.html">home page</a><p>something different</p></body></html>
<html><body><a href="home.html">home page</a><br><p>another text</p></body></html>
Árvore DOM
Abordagens utilizadas
•Heurística (INF2914 – Máquinas de busca)
•TBL▫fnTBL: Ferramenta open source orientada
a tarefas relacionadas a linguagem natural.
•SVM▫LIBSVM: biblioteca para SVM direcionada
a usuários de outras áreas.
Montagem do Corpus
•71 blogs coletados da web▫Árvores DOM geradas: 15 mil nós
•Etiquetagem manual▫Para cada blog, dois arquivos texto
contendo: IDs dos nós da classe “POST” IDs dos nós da classe “TITLE”
Features extraídas de cada nó (1/2)• Número de palavras no nó / na sub-árvore
• Número de dígitos no nó / na sub-árvore
• Número de links no nó / na sub-árvore
• Razão do número de links pelo número de palavras
• Razão do número de dígitos pelo número de palavras
Features extraídas de cada nó (2/2)•Distância de para um nó com bastante
conteúdo▫ mínimo de 150 caracteres
•Número de filhos
•Número de irmãos
•Se é uma tag HTML header▫<h1>, <h2> etc.
TBL – Tratamento de Features
•As categorias das features são determinadas por um limiar pré-definido e o valor da feature em relação ao nó.
•Categoria ‘>’.•Categoria ‘<’ .•Em alguns casos a categoria ‘eq’.
TBL – Tratamento de Features
•Por exemplo, os limiares para número de palavras são 0, 15 e 100. Exemplos de como as categorias são aplicadas: >15<100 , eq0, >0<15, >100,etc.
TBL – Predição Inicial
•Todos os nós classificados como NONE.
•Classificação dada pela Heurística desenvolvida em INF2914 – Máquinas de busca
TBL – Templates de regrasnumwords numlinks disttocontentsize150 digitsperword
linksperword => CHUNKnumchildren numlinks numwords isheader => CHUNKnumwords numdigits isheader linksperword => CHUNKnumlinks numdigitssubtree digitsperword => CHUNKnumchildren numsiblings digitsperword linksperword numwords
=> CHUNKnumchildren numsiblings digitsperword linksperword numwords
isheader disttocontentsize150 => CHUNK
TBL - Implementação
•Os arquivos para o fnTBL foram gerados a partir de um módulo Python.
•De acordo com os parâmetros gerava o arquivo para um tipo predição .
•Gera-se um corpo para o treinamento e um outro para o teste.
SVM – Pré-processamento
•Conversão de features categóricas▫ is_header [yes, no]:
is header [0, 1]▫ color [red, green, blue]:
red [0, 1]; green [0, 1]; blue [0, 1]
•Normalização dos valores▫ [0, 1] vs. [-1, 1]
SVM – Ajuste de parâmetros (1/2)•Função objetivo do problema de otimização
•Kernel RBF
•Encontrar melhores valores para
l
ii
T
bwCww
1,, 2
1min
)exp(),(2
jiji xxxxK
,C
SVM – Ajuste de parâmetros (2/2)•Busca em grid:
•Parametrosencontrados:
31315
1535
2,,2,2
2,,2,2
C
3
13
2
2
C
SVM - Implementação•Binding para Python do LIBSVM
•Utilizada a mesma representação do corpus em memória para as 3 abordagens
• Inclusão de funções:▫ Pré-processamento do corpus▫ Geração do corpus em arquivo (para grid-
search)▫ Treinamento e testes usando validação cruzada
Experimentos
•Validação cruzada com 5-folds
•Métricas utilizadas:▫ precision:
predições corretas / predições▫ recall:
predições corretas / total da classe▫ f-measure:
2 × (precision × recall) / (precision + recall)
Comparação das estratégias (1/3)
Comparação das estratégias (2/3)
Comparação das abordagens (3/3)•Uso da informação da heurística
•Necessidade de especialista no dominío
•Modelo inteligível
•Performance do treinamento/classificação
Trabalhos futuros
•Mudança para um parser melhor
•Testar o TBL com diferentes limiares•Fragmentar mais as categorias no TBL•Usar nós vizinho também na classificação
•Usar resposta da heurística para o SVM•Análise de relevância das features no
SVM
Referências[CKP07] Deepayan Chakrabarti, Ravi Kumar, and Kunal Punera. Pagelevel template detection via
isotonic smoothing. WWW '07: Proceedings of the 16th international conference on World WideWeb, pages 6170, New York, NY, USA, 2007. ACM Press.
[CYWM03] Deng Cai, Shipeng Yu, Ji-Rong Wen, and Wei-Ying Ma. Vips: a vision-based page segmentation algorithm. Technical Report MSRTR-2003-79, 2003.
[DMG05] Sandip Debnath, Prasenjit Mitra, and C. Lee Giles. Automatic extraction of informative blocks from webpages. In SAC '05: Proceedings of the 2005 ACM symposium on Applied computing, pages 17221726, New York, NY, USA, 2005. ACM Press.
[GPT05] David Gibson, Kunal Punera, and Andrew Tomkins. The volume and evolution of web page templates. InWWW '05: Special interest tracks and posters of the 14th international conference on World Wide Web, pages 830839, New York, NY, USA, 2005. ACM Press.
[LH02] Shian-Hua Lin and Jan-Ming Ho. Discovering informative content blocks from web documents. In KDD '02: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 588593, New York, NY, USA, 2002. ACM Press.
[VdSP+06] Karane Vieira, Altigran S. da Silva, Nick Pinto, Edleno S de Moura, ao M. B. Cavalcanti Jo and Juliana Freire. A fast and robust method for web page template detection and removal. In CIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge management, pages 258267, New York, NY, USA, 2006. ACM Press.
[YLL03] Lan Yi, Bing Liu, and Xiaoli Li. Eliminating noisy information in web pages for data mining. In KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 296305, New York, NY, USA, 2003. ACMPress.
