Recuperação de Dados por Interpolação para Algoritmos On-Line de Descoberta de Padrões Flock

• Vitor Bezerra Universidade Estadual de Londrina
• Denis Sanches Universidade Estadual de Londrina
• Daniel Kaster Universidade Estadual de Londrina

DOI: https://doi.org/10.5753/sbsi.2017.6079

Resumo

A partir da análise de dados espaço-temporais pode-se identificar padrões de movimentação de grupos de objetos, como o padrão flock. Este padrão pode ser definido como um número mínimo de entidades dentro de um espaço delimitado por um disco de diâmetro definido que se deslocam juntos por um certo intervalo de tempo. No entanto, enquanto as trajetórias dos diferentes objetos são coletadas, elas podem apresentar irregularidades por problemas, como falha de sistema, falha por passagem em túneis, etc., gerando perdas nas trajetórias coletadas. Uma solução para este problema é a interpolação de pontos, técnica que geometricamente gera pontos correspondentes a pontos faltantes a partir de dados já coletados. Nesse sentido, o objetivo deste trabalho é incluir técnicas de interpolação em algoritmos on-line para o padrão flock para o tratamento de streams de dados espaço-temporais com perdas com tamanho configurável de memória temporária. A abordagem proposta permite utilizar diferentes métodos de interpolação com baixo overhead e bons resultados em termos de precisão. Comparando os resultados utilizando as streams originais e as streams interpoladas, os experimentos mostraram bons resultados na busca por padrões flock, atingindo até 80% de recuperação de respostas perdidas, sem impactar significativamente no custo de execução dos algoritmos.

Palavras-chave: Bancos de dados espaço-temporais, padrão flock, detecção de padrões, interpolação de trajetória

Referências

C. C. Aggarwal. Data classification: algorithms and applications. CRC Press, 2014.

E. Alpaydin. Introduction to Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2004.

S.-A. Bahrainian and A. Dengel. Sentiment analysis and summarization of twitter data. In Computational Science and Engineering (CSE), 2013 IEEE 16th International Conference on, pages 227–234. IEEE, 2013.

L. Breiman. Random forests. Mach. Learn., 45(1):5–32, Oct. 2001.

J. G. Carbonell, R. S. Michalski, and T. M. Mitchell. An overview of machine learning. In Machine learning, pages 3–23. Springer, 1983.

T. Chen and C. Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pages 785–794, New York, NY, USA, 2016. ACM.

Z. Chu, S. Gianvecchio, H. Wang, and S. Jajodia. Who is tweeting on twitter: Human, bot, or cyborg? In Proceedings of the 26th Annual Computer Security Applications Conference, ACSAC ’10, pages 21–30, New York, NY, USA, 2010. ACM.

T. Cover and P. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1):21–27, January 1967.

G. Dougherty. Pattern recognition and classification: an introduction. Springer Science & Business Media, 2012.

J. H. Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29:1189–1232, 2000.

S. Ghosh, G. Korlam, and N. Ganguly. Spammers’ networks within online social networks: A case-study on twitter. In Proceedings of the 20th International Conference Companion on World Wide Web, WWW ’11, pages 41–42, New York, NY, USA, 2011. ACM.

A. Hassan, A. Abbasi, and D. Zeng. Twitter sentiment analysis: A bootstrap ensemble framework. In Social Computing (SocialCom), 2013 International Conference on, pages 357–364. IEEE, 2013.

L.-C. Hsieh, C.-W. Lee, T.-H. Chiu, and W. Hsu. Live semantic sport highlight detection based on analyzing tweets of twitter. In Multimedia and Expo (ICME), 2012 IEEE International Conference on, pages 949–954. IEEE, 2012.

R. A. Igawa, S. B. Jr, K. C. S. Paulo, G. S. Kido, R. C. Guido, M. L. P. J´unior, and I. N. da Silva. Account classification in online social networks with {LBCA} and wavelets. Information Sciences, 332:72 – 83, 2016.

G. James, D. Witten, T. Hastie, and R. Tibshirani. An Introduction to Statistical Learning: With Applications in R. Springer Publishing Company, Incorporated, 2014.

K. Molugaram and G. S. Rao. Chapter 9 - chi-square distribution. In K. Molugaram and G. S. Rao, editors, Statistical Techniques for Transportation Engineering, pages 383 – 413. Butterworth-Heinemann, 2017.

M. M. Mostafa. More than words: Social networks’ text mining for consumer brand sentiments. Expert Systems with Applications, 40(10):4241–4251, 2013.

K. Thomas, C. Grier, D. Song, and V. Paxson. Suspended accounts in retrospect: An analysis of twitter spam. In Proceedings of the 2011 ACM SIGCOMM Conference on Internet Measurement Conference, IMC ’11, pages 243–258, New York, NY, USA, 2011. ACM.

V. N. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag New York, Inc., New York, NY, USA, 1995.

R. Wald, T. M. Khoshgoftaar, A. Napolitano, and C. Sumner. Predicting susceptibility to social bots on twitter. In 2013 IEEE 14th International Conference on Information Reuse Integration (IRI), pages 6–13, Aug 2013.

S. J. Yu. The dynamic competitive recommendation algorithm in social network services. Information Sciences, 187:1–14, 2012.

M. Zappavigna. Ambient aliation: A linguistic perspective on twitter. New Media & Society, 13(5):788–806, 2011.