Mining real patterns in uncertain tensors
| Autor: | Lucas José Carneiro Maciel |
|---|---|
| Přispěvatelé: | Loic Pascal Gilles Cerf, Vinícius Fernandes dos Santos, Flavio Vinicius Diniz de Figueiredo, Thiago Ferreira de Noronha, Robson Leonardo Ferreira Cordeiro |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Aglomeração hierárquica
Hill-climbing Modelo de Regressão — Teses Programação linear inteira Tensores incertos Computação — Teses Reconhecimento de Padrões — Teses Mineração de Dados (Computação) — Teses Programação Linear — Teses Algoritmos de seleção Mineração de padrões Disjunctive box cluster model |
| Zdroj: | Repositório Institucional da UFMG Universidade Federal de Minas Gerais (UFMG) instacron:UFMG |
| Popis: | 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. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|