Minerando padrões reais em tensores incertos

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.