O presente trabalho propôs a análise e adaptação de um algoritmo de otimização por en- xame de abelhas de forma que ele pudesse ser aplicado na solução de problemas de agrupa- mento e classificação de dados. Mais especificamente, o projeto envolveu: 1) o estudo do al- goritmo OptBees e a proposição de duas versões desse algoritmo para aplicação em problemas de agrupamento de dados; e 2) a utilização da versão para agrupamento como um método automático de posicionamento de centros em redes neurais do tipo RBF a serem aplicadas em problemas de classificação de dados.
Na primeira etapa da pesquisa foram propostas duas versões do algoritmo OptBees para aplicação em problemas de agrupamento de dados, os algoritmos cOptBees1 (CRUZ, MAIA, et al., 2013) e cOptBees2 (CRUZ, MAIA e DE CASTRO, 2013). Os dois algoritmos apresen- tados foram avaliados utilizando bases de dados bidimensionais (base ruspini e uma base arti- ficial) e diferentes bases de dados n-dimensionais do UCI Machine Learning Repository. Os resultados obtidos pelo cOptBees foram comparados com aqueles obtidos por outros algorit- mos de agrupamento presentes na literatura. Os experimentos realizados comprovaram a ca- pacidade de ambas as versões do algoritmo cOptBees de encontrar agrupamentos ótimos em bases de dados e a sua competitividade quando comparadas com algoritmos já existentes na literatura. O algoritmo cOptBees, além do bom desempenho na tarefa de agrupamento, foi capaz de gerar e manter a diversidade das soluções, retornando diferentes soluções de agru- pamento em uma mesma execução, e apresentou, na maioria das vezes, a capacidade de en- contrar a quantidade de grupos correta para a base de dados.
A análise de sensibilidade paramétrica do algoritmo cOptBees foi realizada com o obje- tivo de investigar a influência de cada parâmetro no seu desempenho e auxiliar na escolha da configuração paramétrica adequada para cada situação. Para avaliar o impacto de cada parâ- metro no desempenho do cOptBees foram realizados experimentos com diferentes configura- ções de parâmetros, sendo que cada um foi variado individualmente enquanto os demais fo- ram mantidos fixos em valores padrões. A qualidade dos agrupamentos encontrados pelo cOptBees, baseada na medida de fitness utilizada, e o tamanho final do enxame são direta- mente proporcionais ao número de regiões promissoras encontradas, representadas pelas abe- lhas recrutadoras, e pelo esforço de forrageamento nessas regiões. O número de recrutadoras, por sua vez, é diretamente influenciado pela probabilidade mínima de uma abelha se tornar recrutadora, pmin, e pelo tamanho do raio de inibição, ρ.
Encontrar agrupamentos ótimos em bases de dados;
Determinar automaticamente a quantidade adequada de grupos para cada base; Gerar e manter a diversidade de soluções, sendo capaz de retornar diferentes ótimos
locais além da busca pelo ótimo global;
Controlar dinamicamente o tamanho do enxame e, consequentemente, o esforço computacional de acordo com as características do problema;
Ajustar o esforço da colônia para exploração das regiões promissoras (busca local) e exploração do espaço de busca (busca global).
Na segunda etapa do trabalho, o algoritmo cOptBees2 foi utilizado para definir automa- ticamente o número e a localização das funções de base radial de redes neurais do tipo RBF. A abordagem híbrida apresentada, chamada BeeRBF (CRUZ, MAIA, et al., 2014; CRUZ, MAIA, et al., 2015), realiza o ajuste dos centros das funções de base radial em uma etapa não supervisionada, na qual o algoritmo de agrupamento cOptBees2 é utilizado para agrupar os dados de treinamento e os centroides dos grupos encontrados são utilizados como centros das funções de base radial. Inicialmente, o algoritmo foi avaliado levando em consideração a su- perfície de decisão gerada para três bases de dados bidimensionais. Os resultados gráficos mostraram a capacidade do BeeRBF de determinar o número, as posições e dispersões das funções de base radial de maneira automática e gerar uma boa superfície de decisão para os dados. O algoritmo foi aplicado em diferentes problemas do UCI Machine Learning Reposi- tory e os resultados obtidos foram comparados com técnicas de seleção de centros e também com algoritmos de classificação presentes na literatura. Em ambos os casos o BeeRBF demos- trou ser competitivo quando comparado com outros algoritmos. Dentre as características do algoritmo BeeRBF destacam-se:
Determinação automática do número e posição dos centros da rede neural RBF; Dispersões dinâmicas para cada função de base radial;
Como trabalhos futuros e continuidade da pesquisa propõem-se:
Investigar o impacto de cada parâmetro do cOptBees na diversidade das soluções de agrupamento;
Utilizar uma abordagem multiobjetivo combinando acurácia e parcimônia para in- vestigar a geração de redes neurais menores (menor quantidade de centros);
A Bee-inspired Algorithm for Optimal Data Clustering
CRUZ, D. P. F. et al. A bee-inspired algorithm for optimal data clustering. 2013 IEEE Congress on Evolutionary Computation (CEC). Cancún: IEEE. 2013. p. 3140-3147.
A New Encoding Scheme for a Bee-Inspired Optimal Data Clustering Algorithm CRUZ, D. P. F.; MAIA, R. D.; DE CASTRO, L. N. A New Encoding Scheme for a Bee- Inspired Optimal Data Clustering Algorithm. 1st BRICS Countries Congress (BRICS-CCI). Recife: IEEE. 2013. p. 136 - 141.
A Bee-Inspired Data Clustering Approach to Design RBF Neural Network
CRUZ, D. P. F. et al. A Bee-Inspired Data Clustering Approach to Design RBF Neural Network Classifiers. In: Advances in Intelligent Systems and Computing. Salamanca: Springer International Publishing, 2014. p. 545-552.
Parametric Sensitivity Analysis of cOptBees Optimal Clustering Algorithm
Cruz, D. P. F., Maia, R. D., De Castro, L. N. Parametric Sensitivity Analysis of cOptBees Optimal Clustering Algorithm. 2014 Intelligent Systems Design and Applications (ISDA), 14th International Conference, Okinawa: IEEE. 2014. P. 168-173.
On the Sensitivity of a Bee-Inspired Algorithm to Its Internal Parameters
CRUZ, D. P. F.; MAIA, R. D.; DE CASTRO, L. N. On the Sensitivity of a Bee-Inspired Algorithm to Its Internal Parameters. International Journal of Computer Information Systems and Industrial Management Applications, v. 7, p. 084-093, 2015. ISSN 2150-7988.
BeeRBF: A Bee-Inspired Data Clustering Approach to Design RBF Neural Network Classifiers (Artigo aceito para publicação)
Cruz, D. P. F., Maia, R. D., Silva, L. A., De Castro, L. N. BeeRBF: A Bee-Inspired Data Clustering Approach to Design RBF Neural Network Classifiers. Neurocomputing, Elsevier. (Aceito)
REFERÊNCIAS BIBLIOGRÁFICAS
ABRAHAM, A.; DAS, S.; ROY, S. Swarm Intelligence Algorithms for Data Clustering. In:
MAIMON, O.; ROKACH, L. Soft Computing for Knowledge Discovery and Data Mining. [S.l.]: Springer US, 2008. p. 279-313.
BACHE, K.; LICHMAN, M. UCI - Machine Learning Repository, 2013. Disponivel em: <http://archive.ics.uci.edu/ml>.
BARRA, T. V.; BEZERRA, G. B.; DE CASTRO, L. N. An Immunological Density-Preserving
Approach to the Synthesis of RBF Neural Networks for Classification. International Joint
Conference on Neural Networks. Vancouver,: [s.n.]. 2006.
BERKHIN, P. A Survey of Clustering Data Mining Techniques. In: BERKHIN, P. Grouping
Multidimensional Data. [S.l.]: Springer Berlin Heidelberg, 2006. p. 25-71.
BISHOP, C. M. Pattern recognition and machine learning. New York: Springer, v. 1, 2006. BONABEAU, E.; DORIGO, M.; GUY, T. Swarm Intelligence: From Natural to Artificial Systems. New York: Oxford University Press, v. 1, 1999.
BORGES, E.; FERRARI, D. G.; DE CASTRO, N. L. Opt-aiNet: An Artificial Immune System for Optimal Clustering. Revista Mackenzie de Engenharia e Computação, São Paulo, v. 11, n. 1, p. 117-140, 2012. ISSN 2236-9813.
BROOMHEAD, D. S.; LOWE, D. Multivariable Functional Interpolation and Adaptive Networks.
Complex Systems, 2, 1988. 321-355.
CHEN, S.; COWAN, C. F. N.; GRANT, P. M. Orthogonal least squares learning algorithm for radial basis function networks. Neural Networks, v. 2, n. 2, p. 302 - 309, 1991.
CHEN, Y.; WANG, J. Z.; KROVETZ, R. Content-based image retrieval by clustering. MIR '03
Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, 2003. 193-200.
CHUN-TAO, M.; XIAO-XIA, L.; LI-YONG, Z. Radial Basis Function Neural Network Based on
Ant Colony Optimization. International Conference on Computational Intelligence and Security
Workshops. [S.l.]: [s.n.]. 2007.
COTTA, C.; MOSCATO, P. The Parameterized Complexity of Multiparent Recombination. MIC2005 6th Metaheuristics Int. Conf. Vienna: Kluwer Academic Publishers. 2005.
CRUZ, D. P. F. et al. A bee-inspired algorithm for optimal data clustering. 2013 IEEE Congress on Evolutionary Computation (CEC). Cancún: IEEE. 2013. p. 3140-3147.
CRUZ, D. P. F. et al. A Bee-Inspired Data Clustering Approach to Design RBF Neural Network Classifiers. In: KACPRZYK, J. Advances in Intelligent Systems and Computing. Salamanca: Springer International Publishing, v. 290, 2014. p. 545-552.
CRUZ, D. P. F. et al. A Bee-Inspired Data Clustering Approach to Design RBF Neural Network Classifiers. In: ______ Advances in Intelligent Systems and Computing. [S.l.]: Springer International Publishing, 2014. p. 545-552.
CRUZ, D. P. F. et al. BeeRBF: A Bee-Inspired Data Clustering Approach to Design RBF Neural Network Classifiers. Neurocomputing, 2015.
CRUZ, D. P. F.; MAIA, R. D.; DE CASTRO, L. N. A New Encoding Scheme for a Bee-Inspired
Optimal Data Clustering Algorithm. 1st BRICS Countries Congress (BRICS-CCI). Recife: IEEE.
2013. p. 136 - 141.
CRUZ, D. P. F.; MAIA, R. D.; DE CASTRO, L. N. Parametric Sensitivity Analysis of cOptBees
Optimal Clustering Algorithm. 14th International Conference Intelligent Systems Design and
Applications (ISDA). Okinawa: IEEE. 2014. p. 168-173.
CRUZ, D. P. F.; MAIA, R. D.; DE CASTRO, L. N. On the Sensitivity of a Bee-Inspired Algorithm to Its Internal Parameters. International Journal of Computer Information Systems and Industrial
Management Applications, v. 7, p. 084-093, 2015. ISSN 2150-7988.
DAS, P. Success and the dancing bee. Nature, August 1998.
DE CASTRO, L. N. Fundamentals of Natural Computing: Basic Concepts, Algorithms, and Applications. São Paulo: Chapman & Hall/CRC, 2006. ISBN 1584886439.
DE CASTRO, L. N. Fundamentals of natural computing: an overview. Physics of Life Reviews, v. 4, n. 1, p. 1-36, 2007. ISSN 1571-0645.
DE CASTRO, L. N. et al. The Grand Challenges in Natural Computing Research: The Quest for a New Science. IJNCR, 2, 2011. 17-30.
DE CASTRO, L. N.; VON ZUBEN, F. J. Automatic Determination of Radial Basis Functions: An Immunity-Based Approach. International Journal of Neural Systems (IJNS), 2002. 523-535. ENGELBRECHT, A. P. Fundamentals of Computational Swarm Intelligence. [S.l.]: John Wiley & Sons, 2006. ISBN 0470091916.
FACELI, K. et al. Validação de Algoritmos de Agrupamento. ICMC techinical reports, 2005. FAYYAD, U.; PIATETSKY-SHAPIRO, G.; SMYTH, P. From Data Mining to Knowledge Discovery in Databases. AI Magazine, v. 17, n. 3, 1996.
FERNÁNDEZ-REDONDO, M. et al. Training Radial Basis Functions by Gradient Descent. In: ______ Artificial Intelligence and Soft Computing - ICAISC 2004. [S.l.]: Springer Berlin Heidelberg, 2004. p. 184-189.
GADAU, J.; FEWELL, J. Organization of Insect Societies: From Genome to Sociocomplexity. [S.l.]: Harvard University Press, 2009. ISBN 978-0-674-03125-8.
GAN, G.; MA, C.; WU, J. Data Clustering: Theory, Algorithms, and Applications. Philadelphia: SIAM, 2007.
HALKIDI, M.; BATISTAKIS, Y.; VAZIRGIANNIS, M. Clustering algorithms and validity measures.
Thirteenth International Conference on Scientific and Statistical Database Management, 2001.
3-22.
HAN, J.; KAMBER, M. Data Mining: Concepts and Techniques. 2ª. ed. San Francisco: Elsevier, 2006.
HARPHAM, C.; DAWSON, C. W.; BROWN, M. R. A review of genetic algorithms applied to training radial basis function networks. Neural Computation & Application, 2004. 193–201. HAYKIN, S. Neural Networks – A Comprehensive Foundation. 2ª. ed. New Jersey: Pratice Hall, 1999.
HORNG, M.-H. Training Radial Basis Function Network Using the Honey Bee Mating Optimization.
Computer Modelling and New Technologies, v. 17, n. 3, p. 43–49, 2013.
HRUSCHKA, E. R.; DE CASTRO, L. N.; CAMPELLO, R. J. G. B. Evolutionary algorithms for
clustering gene-expression data. IEEE International Conference on Data Mining. Brighton: IEEE.
2004. p. 403- 406.
HWANG, Y. S.; BANG, S. Y. An Efficient Method to Construct Radial Basis Function Neural Network Classifier. Neural Network, v. 10, p. 1495-1503, 1997.
JAIN, A. K. Data clustering: 50 years beyond K-means. Pattern Recognition Letters, v. 31, n. 8, p. 651-666, Junho 2010. ISSN 01678655.
JAIN, A. K.; DUIN, R. P. W.; MAO, J. Statistical pattern recognition: a review. IEEE Transactions
on Pattern Analysis and Machine Intelligence, v. 22, n. 1, p. 4-37, January 2000.
JANE, C. et al. The use and reporting of cluster analysis in health psychology: A review. British
Journal of Health Psychology, v. 10, n. 3, p. 329-358, September 2005.
KARABOGA, D. et al. A comprehensive survey: artificial bee colony (ABC) algorithm and applications. Artificial Intelligence Review, v. 42, n. 1, p. 21-57, 2014. ISSN 0269-2821.
KARABOGA, D.; AKAY, B. Artificial bee colony (ABC), harmony search and bees algorithms on numerical optimization. Innovative Production Machines and Systems Virtual Conference, 2009. KARABOGA, D.; AKAY, B.; OZTURK, C. Artificial Bee Colony (ABC) Optimization Algorithm for Training Feed-Forward Neural Networks. Modeling Decisions for Artificial Intelligence, v. 4617, p. 318-329, 2007.
KARAYIANNIS, N. B. Gradient descent learning of radial basis neural networks. International Conference on Neural Networks. [S.l.]: [s.n.]. 1997.
KARAYIANNIS, N. B. Reformulated radial basis neural networks trained by gradient descent.
Neural Networks, v. 10, n. 3, p. 657 - 671, 1999.
KARI, L.; ROZENBERG, G. The Many Facets of Natural Computing. Commun. ACM, New York, v. 51, n. 10, p. 72-83, Outubro 2008. ISSN 0001-0782.
KURBAN, T.; BESDOK, E. A Comparison of RBF Neural Network Training Algorithms for Inertial Sensor Based Terrain Classification. Sensors, 2002. 6312–6329.
LIPPMANN, R. P. Pattern Classification Using Neural Networks. IEEE Communications
Magazine, p. 47-63, 1989.
MAIA, R. D.; DE CASTRO, L. N.; CAMINHAS, W. M. Collective Decision-Making by Bee Colonies as Model for Optimization-the OptBees Algorithm. Applied Mathematical Sciences, v. 7, n. 87, p. 4327-4351, 2013.
MARINAKI, M.; MARINAKIS, Y.; ZOPOUNIDIS, C. Honey Bees Mating Optimization algorithm for financial classification problems. Applied Soft Computing, v. 10, n. 3, p. 806-812, 2010. ISSN 1568-4946.
MICCHELLI, C. A. Interpolation of Scattered Data: Distance Matrices and Conditionally Positive Definite Functions. In: SINGH, S. P.; BURRY, J. W. H.; WATSON, B. Approximation Theory and
Spline Functions. [S.l.]: Springer Netherlands, v. 136, 1984. p. 143-145. ISBN 978-94-009-6468-6.
MICHENER, C. D. Comparative social behavior of bees. Annual review of entomology, v. 14, n. 1, p. 299-342, 1969.
MILLONAS, M. M. Swarms, phase transitions and collective intelligence. Artificial Life III, 1994. MOODY, J.; DARKEN, C. Fast Learning in Networks of Locally-Turned Processing Units. Neural
Computation, v. 1, p. 281-294, 1989.
MUÑOZ, M. A.; LÓPEZ, J. A.; CAICEDO, E. An artificial beehive algorithm for continuous optimization. International Journal of Intelligent Systems, v. 24, n. 11, p. 1080-1093, 2009.
NIROS, A. D.; E.TSEKOURAS, G. A novel training algorithm for RBF neural network using a hybrid fuzzy clustering approach. Fuzzy Sets and Systems, v. 193, p. 62-84, 2012.
PAL, N. R.; PAL, S. K. A review on image segmentation techniques. Pattern Recognition, v. 26, n. 9, p. 1277-1294, September 1993.
POGGIO, T.; GIROSI, F. Networks for Approximation and Learning. Proceedings of the IEEE. [S.l.]: [s.n.]. 1990. p. 1481-1497.
PUNJ, G.; STEWART, D. W. Cluster analysis in marketing research: review and suggestions for application. Journal of marketing research, v. 20, n. 2, p. 134-148, May 1983.
QASEM, S. N.; SHAMSUDDIN, S. M. Radial basis function network based on time variant multi- objective particle swarm optimization for medical diseases diagnosis. Applied Soft Computing, v. 11, n. 1, p. 1427–1438, 2011.
QASEM, S. N.; SHAMSUDDIN, S. M.; ZAIN, A. M. Multi-objective hybrid evolutionary algorithms for radial basis function neural network. Knowledge-Based Systems, v. 27, p. 475–497, 2012.
ROUSSEEUW, P. J. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis.
Journal of Computational and Applied Mathematics, v. 20, p. 53-65, 1987.
RUSPINI, E. H. Numerical methods for fuzzy clustering. Information Sciences, v. 2, n. 3, p. 319– 350, 1970.
SARIMVEIS, H.; ALEXANDRIDIS, A.; BAFAS, G. A fast training algorithm for RBF networks based on subtractive clustering. Neurocomputing, v. 51, p. 501 – 505, 2003.
SATO, T.; HAGIWARA, M. Bee system: finding solution by a concentrated search. IEEE
International Conference on Computational Cybernetics and Simulation, 1997. 3954-3959.
SEELEY, T. D.; CAMAZINE, S.; SNEYD, J. Collective decision-making in honey bees: how
colonies choose among nectar sources. Behavioral Ecology and Sociobiology, v. 28, n. 4, p. 277-290, 1991.
SING, J. K. et al. Improved k-means algorithm in the design of RBF neural networks. TENCON 2003. Conference on Convergent Technologies for the Asia-Pacific Region. [S.l.]: [s.n.]. 2003. p. 841- 845.
SUGANTHAN, P. N. et al. Problem definitions and evaluation criteria for the CEC 2005 special
session on real-parameter optimization. Nanyang Technological University. Singapore. 2005.
SZABO, A.; DE CASTRO, L. N.; DELGADO, M. R. FaiNet: An immune algorithm for fuzzy clustering. Prec. IEEE International Conference on Fuzzy Systems. Brisbane: IEEE. 2012. p. 1-9. TAN, P. N.; STEINBACH, M.; KUMAR, V. Introduction to Data Mining. 1ª. ed. Boston: Addison- Wesley Longman Publishing Co., Inc., 2005.
TEODOROVIC, D. Swarm intelligence systems for transportation engineering: Principles and applications. Transportation Research Part C: Emerging Technologies, v. 16, p. 651-667, Dezembro 2008. ISSN 0968090X.
TEODOROVIC, D. Bee colony optimization (BCO). Innovations in swarm intelligence, p. 39-60, 2009.
TSEKOURAS, G. E.; TSIMIKAS, J. On training RBF neural networks using input–output fuzzy Clustering and particle swarm optimization. Fuzzy Sets and Systems, 2013. 65-89.
VON FRISCH, K. The dance language and orientation of bees. [S.l.]: [s.n.], 1967.
WHITEHEAD, B. A.; CHOATE, T. D. Cooperative-Competitive Genetic Evolution of Radial
Basis Function Centers and Widths for Time Series Prediction. IEEE Trans. on Neural Networks.
[S.l.]: [s.n.]. 1996. p. 869-880.
WITTEN, I. H.; FRANK, E. Data Mining: Practical machine learning tools and techniques. 2ª. ed. San Francisco: Morgan Kaufmann, 2005.
YINGWEI, L.; SUNDARARAJAN, N.; SARATCHANDRAN, P. A sequential learning scheme for function approximation using minimal radial basis function neural networks. Neural Computation, v. 9, n. 2, p. 461-478, 15 February 1997. ISSN 10.1162/neco.1997.9.2.461.
ZHANG, L.; BAI, Y. F. Genetic algorithm-trainedrad ial basis function neural networks for modelling photovotaic panels. Engineering Applications of Artificial Intelligence, 2005. 833–844.
ZHAO, Y.; KARYPIS, G. Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering. Machine Learning, v. 55, n. 3, p. 311-331, 2004. ISSN 0885-6125.