Conversão simbólica de sinais digitais por meio da Teoria de Extremos Relativos

Abstract

O objetivo deste trabalho é o desenvolvimento de uma nova técnica para conversão simbólica de sinais digitais, denominada Quantização Baseada em Extremos Relativos (QBER). Esta técnica pode converter sinais digitais unidimensionais em cadeias. A técnica QBER, formalizada nesta proposta, utiliza-se da Teoria de Extremos Relativos (TER) e de funções de similaridade para sinais, como a métrica Distância de Edição com Penalidade Real (Edit Distance with Real Penalty) (ERP). Além disso, utiliza o algoritmo de clusterização PAM-SLIM, que emprega a abordagem k-medianas, amplamente discutida na literatura. A TER é também uma contribuição deste trabalho, extendendo a Teoria dos Extremos Importantes (TEI) com o acréscimo dos conceitos prevalência, monte, Representação Baseada em Extremos Relativos (RBER) e RBERQ. Para se avaliar a utilidade da QBER desenvolveu-se um sistema de classificação de padrões de referência, baseado no classificador k-Vizinhos mais Próximos (k-Nearest Neighbor) (kNN). Esta implementação de referência possui as fases de pré-processamento e reconhecimento. Na fase de pré-processamento, utiliza-se a QBER para converter os objetos de treinamento do kNN em representações simbólicas. Como o classificador kNN utiliza o aprendizado baseado em instâncias (instance-based learning) a fase de treinamento é inexistente, sendo toda classificação baseada nos objetos de treinamento. Na fase de pré-processamento um objeto a ser avaliado também é convertido para a representação simbólica utilizada, antes de ser utilizado como entrada para o classificador kNN, na fase de reconhecimento. Com vistas a avaliar a utilidade da técnica desenvolvida são feitas comparações de seu emprego em um problema de classificação, a geração de recomendações de compra de ações. O classificador kNN implementado é então avaliado com e sem o emprego da QBER, observando-se utilidade no emprego da técnica desenvolvida, pela performance superior no tempo de preparação do classificador e na rentabilidade anual obtida.

The goal is to develop a new technique for symbolic conversion of digital signals, called Quantization based on Relative Extrema (QBER). This technique can convert unidimensional digital signals into strings. The technique QBER, formalized in this proposal, uses Relative Extrema Theory (TER ) and signal’s similarity functions, as metric Edit Distance with Real Penalty (ERP). In addition, also uses the clustering algorithm PAMSLIM, which employs k-medoid approach, widely discussed in the literature. The TER is also other contribution of this work, as an extension of Important Extrema Theory, increasing concepts of prevalence, mount, Relative Extrema based Representation (RBER) and Quantized Relative Extrema based Representation (RBERQ). To evaluate the usefulness of QBER, has developed a classification system of reference patterns, based on the KNN classifier. This reference implementation has the pre-processing and recognition phases. In pre-processing, QBER is used to convert training objects of KNN in symbolic representations. As the k-Nearest Neighbor (kNN) classifier uses instance based learning, a training phase is inexistent, all classification is based on the training objects. In pre-processing phase also an object in analysis is converted to RBERQ symbolic representation, before serving as input for the classifier KNN. In order to evaluate the usefulness of the technique developed, are made comparisons in a problem of classification - generation of recommendations for the purchase of shares. The kNN classifier implemented is evaluated with and without the use of QBER, being useful in the employment by superior performance (of QBER) considering aspects of preparation time and annual return obtained.