Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/35673
Type: | Dissertação |
Title: | Minerando padrões reais em tensores incertos |
Other Titles: | Mining real patterns in uncertain tensors |
Authors: | Lucas José Carneiro Maciel |
First Advisor: | Loic Pascal Gilles Cerf |
First Co-advisor: | Vinícius Fernandes dos Santos |
First Referee: | Flavio Vinicius Diniz de Figueiredo |
Second Referee: | Thiago Ferreira de Noronha |
Third Referee: | Robson Leonardo Ferreira Cordeiro |
Abstract: | Tensores incertos codificam o quanto são satisfeitos predicados n-ários. Por exemplo, o tempo que usuários gastam em diferentes sites da web em cada semana podem ser transformados em graus de interesse que os usuários (1a dimensão) tem pelos sites (2a dimensão) durante as semanas (3a dimensão). No resultante tensor incerto tridimensional, sub-tensores que são grandes e densos frequentemente são interessantes para um analista. Eles representam usuários que têm mostrado muito interesse nos mesmos sites durante as mesmas semanas. Mirkin and Kramarenko propuseram um modelo disjuntivo de box cluster (disjunctive box cluster model), que é um modelo de regressão onde os padrões são variáveis explicativas dos valores no tensor incerto. Nesta dissertação, duas abordagens são propostas de acordo com tal modelo. Fragmentos dos padrões de interesse são primeiramente providos por algoritmos completos. Estes fragmentos são então crescidos, na primeira abordagem, usando um procedimento conhecido como hillclimbing. Em cada iteração deste procedimento, um problema de programação linear inteira é resolvido para encontrar um padrão maior. Já na segunda abordagem, os fragmentos são hierárquicamente aglomerados. Em ambas abordagens, pré-processamentos são propostos para acelerar a subsequente computação. Finalmente, uma técnica de regressão gradual, forward selection, seleciona entre os padrões descobertos, um subconjunto não redundante que melhor descreve o tensor sem causar overfit. Experimentos em ambos tensores sintéticos e reais mostram que as propostas descobrem padrões de alta qualidade em tensores incertos e superam o estado da arte quando aplicados a tensores 0/1, um caso específico. |
Abstract: | Uncertain tensors encode to what extent n-ary predicates are satisfied. For instance, the times users spent on different websites week after week can be turned into degrees of interest of the users (1st dimension) for the sites (2nd dimension) during the weeks (3rd dimension). In the resulting 3-way uncertain tensor, sub-tensors that are both large and dense are often interesting to an analyst. They are users who all showed much interest for the same sites during the same weeks. Mirkin and Kramarenko proposed the disjunctive box cluster model, a regression model where such patterns are explanatory variables for the values in the uncertain tensor. In this dissertation, two approaches are proposed to fit a disjunctive box cluster model to an uncertain tensor. A complete algorithm first provides fragments of the desired patterns. In the first approach, a hill-climbing procedure individually grows them. At every iteration of that procedure, integer linear programming is used to compute the larger pattern. In the second approach, the input fragments are hierarchically agglomerated. In both cases, greedy pre-processes are proposed to speed up the subsequent computation. Finally, a stepwise regression technique, the forward selection, chooses among the discovered patterns a non-redundant subset that fits, but does not overfit, the tensor. Experiments on both synthetic and real-world tensors show the proposals discovers high-quality patterns in uncertain tensors and outperforms state-of-the-art approaches when applied to 0/1 tensors, a special case. |
Subject: | Computação — Teses. Mineração de Dados (Computação) — Teses. Programação Linear — Teses. Modelo de Regressão — Teses. Reconhecimento de Padrões — Teses. |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/35673 |
Issue Date: | 4-Apr-2018 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LucasJoséCarneiroMaciel_finalSubst.pdf | 1.28 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.