Amostragem e medidas de qualidade de shapelets
CAVALCANTE, L. S. Amostragem e medidas de qualidade de shapelets. 2016. 81 f. Dissertacao (Mestrado em Ciencias Ciencias de Computacao e Matematica Computacional) Instituto de Ciencias Matematicas e de Computacao (ICMC/USP) Sao Carlos SP. A time series is a time ordered sequence of real values. Given that numerous daily phenomena that can be described by time series, there is a great interest on its data mining, specially on the task of classification. Recently it was introduced a new time series primitive called shapelets, that is a subsequence that allows the classification of time series by local patterns. On the shapelet transformation these subsequences turn into attributes in a distance matrix that measures the dissimilarity between these attributes and the time series. To obtain the shapelet transformation it is required to choose some shapelets among all of the possible ones, be it to avoid overfitting or because it is too computationally expensive to obtain everyone. Thus, some shapelet quality measurements were created. Traditionally the information gain has been used as the default measurement, however, recently it was proposed to use the f statistic instead, and in this work we propose a new one called in class transitions. On our experiments it is shown that usually the in class transitions achieves the best accuracy, specially when few attributes are used. Moreover, we propose the use of random sampling of shapelets as a way to reduce the search space and to speed up the process of obtaining the shapelet transformation. We contrast this approach with one that explores only shapelets that have a specific length. Our experiments show that random sampling is faster and requires fewer shapelets to be computed. In fact, we got the best results when we sampled 5% of the shapelets, but even at a rate of 0.05% it was not possible to detect a significant degradation of the accuracy. Key words: Time series classification, Shapelet transformation, Quality measurements, Random sampling. LISTA DE ILUSTRACOES Figura 1 Ilustracao da necessidade de z normalizacao. 31 Figura 2 Ilustracao de alinhamento pela Dynamic Time Warping. 33 Figura 3 Ilustracao do processo de simbolizarao do SAX. 35 Figura 4 Ilustracao de classificacao pelo algoritmo kNN. 41 Figura 5 Ilustracao do calculo de ganho de informacao. 42 Figura 6 Ilustracao de classificacao pelo algoritmo de arvore de decisao. 44 Figura 7 Ilustracao de classificacao pelo algoritmo Random Forest. 45 Figura 8 Ilustracao do plano separador. 46 Figura 9 Ilustracao de classificacao pelo algoritmo SVM. 49 Figura 10 Exemplo de classificacao pela arvore de decisao shapelets. 53 Figura 11 Ilustracao da poda no calculo do ganho de informacao. 54 Figura 12 Ilustracao da medida de qualidade in class transitions. 57 Figura 13 Ilustracao de dois shapelets similares. 59 Figura 14 Media da acuracia em todos os conjuntos de dados com variacao da quantidade de atributos por quantidade de classes. 66 Figura 15 Media do average rank em todos os conjuntos de dados com variacao da quantidade de atributos por quantidade de classes. 68 Figura 16 Conjunto de Dados ToeSegmentation2 possui baixa acuracia para algumas medidas de qualidades em alguns niveis de amostragem. 69 Figura 17 Efeito da amostragem aleatoria de shapelets na acuracia dos classificadores. 70 Figura 18 Avaliacao de como as tecnicas de reducao do espaco de busca dos shapelets por amostragem aleatoria ou execucao do Algoritmo 5 de estimacao de min e max afetam a acuracia. 72 Figura 19 Comparacao entre o modelo Estado da Arte (usando como medida de qualidade o ganho de informacao) e o nosso modelo proposto. 74 Figura 20 Comparacao entre o modelo Estado da Arte (usando como medida de qualidade a f statistic) e o nosso modelo proposto. 75