Os resultados da Tabela 9 mostram o valor médio das medidas de interesse das regras extraí- das pelos algoritmos Apriori, eGA, CLONALG e CLONALR para o valor de minsup igual a 0,5%. As técnicas estocásticas utilizaram a função de fitness Tomando-se como base os resultados anteriores, o eGA empregou cruzamento de um ponto e seleção por Ranking. Per- cebe-se que a principal vantagem das técnicas estocásticas em comparação ao Apriori está relacionada ao custo computacional. Para a técnica determinística o número de regras é o fator de maior impacto no quadro comparativo, já que esta é capaz de extrair todas as regras com valores de suporte maiores do que o mínimo estabelecido pelo usuário.
Tabela 9: Comparação entre algoritmos para as bases de dados.
Apriori eGA CLONALG CLONALR
BD1 S 0,005 0,017 0,005 (0,011; 0,024) 0,005 0,001 (0,003; 0,008) 0,0050,0008 (0,004; 0,007) C 0,737 0,605 0,173 (0,360; 0,830) 1,000 0,000 (1,000; 1,000) 1,000 0,000 (1,000; 1,000) C1 0,654 0,500 0,000 (0,500; 0,500) 0,439 0,132 (0,250; 0,665) 0,4210,096 (0,340; 0,623) C2 0,012 0,010 0,000 (0,010; 0,010) 0,012 0,004 (0,010; 0,020) 0,012 0,002 (0,010; 0,017) I 0,351 0,370 0,143 (0,160; 0,520) 0,688 0,314 (0,210; 0,990) 0,636 0,256 (0,304; 0,964) NR 1.776 1,600 1,074 (1,000; 4,000) 4,600 7,676 (1,000; 26,00) 12,90 8,006 (3,000; 29,00) T 653.129 80,02 1,610 (77,86; 81,97) 109,4 3,538 (103,6; 112,8) 97,43 1,653 (94,75; 99,68) BD2 S 0,007 0,038 0,011 (0,024; 0,060) 0,003 0,001 (0,002; 0,005) 0,003 0,001 (0,002; 0,004) C 0,344 0,364 0,097 (0,220; 0,480) 1,000 0,000 (1,000; 1,000) 1,000 0,000 (1,000; 1,000) C1 0,580 0,491 0,026 (0,415; 0,500) 0,367 0,092 (0,250; 0,500) 0,381 0,068 (0,252; 0,507) C2 0,012 0,010 0,000 (0,010; 0,010) 0,015 0,011 (0,010; 0,046) 0,016 0,009 (0,010; 0,043) I 0,094 0,117 0,036 (0,060; 0,150) 0,457 0,395 (0,040; 1,000) 0,515 0,253 (0,182; 0,986) NR 843 1,100 0,316 (1,000; 2,000) 3,800 7,828 (1,00; 26,00) 11,70 7,118 (4,000; 25,00) T 291.164 93,62 3,529 (89,17; 100,2) 126,5 5,613 (120,4; 136,4) 110,4 4,003 (107,5; 120,9) BD3 S 0,006 0,068 0,020 (0,045; 0,097) 0,005 0,002 (0,003; 0,008) 0,005 0,002 (0,003; 0,007) C 0,707 0,592 0,191 (0,330; 0,850) 1,000 0,000 (1,000; 1,000) 1,000 0,000 (1,000; 1,000) C1 0,725 0,512 0,123 (0,330; 0,710) 0,382 0,096 (0,250; 0,582) 0,359 0,086 (0,228; 0,497) C2 0,027 0,013 0,005 (0,010; 0,025) 0,024 0,025 (0,010; 0,093) 0,029 0,016 (0,012; 0,060) I 0,173 0,280 0,069 (0,145; 0,340) 0,418 0,344 (0,090; 0,990) 0,434 0,235 (0,182; 0,735) NR 13.554 1,200 0,421 (1,000; 2,000) 7,700 13,64 (1,000; 39,00) 17,60 13,41 (6,000; 40,00) T 2.975.454 49,54 1,669 (47,80; 52,96) 68,42 1,527 (66,91; 70,80) 63,65 1,861 (61,05; 67,64)
Nota-se que o algoritmo Apriori é capaz de extrair a maior quantidade de regras dentre os algoritmos observados, pois ele verifica todas as combinações possíveis entre os itens da base de dados. Contudo, o custo computacional dele é o maior e inviável para uma aplicação que demande velocidade de resposta. O eGA gerou os maiores valores para o suporte dentre todos os algoritmos avaliados e demandou menor tempo para isto. Contudo, o número de so- luções encontradas foi o menor dentre os observados. O CLONALG e o CLONALR obtive- ram os melhores resultados para os valores de confiança. O CLONALR gerou os maiores va- lores para o grau de interesse em duas das três bases usadas para estudo comparativo.
No contexto de recomendações em comércio eletrônico a utilização de técnicas bioinspiradas está fortemente fundamentada no problema do tempo de processamento, ou esforço computacional, para efetuar recomendações de produtos de interesse do consumidor,
o usuário do site. Porém, os resultados mostram que, apesar do eGA ter valores médios de suporte superiores aos apresentados pelas outras técnicas, estes valores foram obtidos por um conjunto menor de regras.
A maior limitação para a aplicação prática das técnicas bioinspiradas está relacionada ao número total de regras geradas. Entretanto, é necessário ressaltar que este conjunto final é obtido a partir de populações com tamanho fixo ao longo do processo evolutivo. Trabalhar com populações dinâmicas pode contribuir para que este conjunto final de soluções aumente. Contudo, esta dinâmica populacional tem impacto direto no custo computacional dos algorit- mos.
Esta limitação do número de regras pode inviabilizar o uso dos algoritmos bioinspira- dos para uma aplicação prática em comércio eletrônico, pois um sistema de recomendação que recomenda uma quantidade pequena de produtos pode não atender as necessidades dos clientes ou até mesmo irritá-lo durante a navegação pelo portal. Por fim, ao utilizar as técnicas bioinspiradas o maior benefício é a parcimônia computacional com que as robustas regras de associação são geradas e aplicadas ao sistema de recomendação.
6 CONCLUSÕES E TRABALHOS FUTUROS
Desde o advento da Web, a Internet vem progressivamente ampliando sua ação nas empresas, transformando-se na interface predominantemente integradora de ambientes de sistemas de informação corporativos. As Intranets expandem-se integrando em um mesmo padrão de acesso todos os serviços intra- e extracorporativos. Externamente às organizações, a Internet transforma-se numa plataforma privilegiada de serviços, oferecendo aos clientes a possibili- dade de interatividade e autoatendimento, além das aplicações voltadas ao atendimento perso- nalizado. Se por um lado a Internet facilitou a efetuação de transações, nos fornecendo inúme- ras possibilidades de realização de negócios, por outro a enorme quantidade de opções nos obriga a investir um tempo considerável filtrando e selecionando qual informação, produto ou serviço melhor atenderá nossas expectativas.
Sistemas de recomendação podem ter utilidades distintas, por exemplo, podem servir como ferramentas de auxílio à identificação de conteúdo sobre o qual tecer comentários, co- mo ferramentas para ajudar na identificação de novos produtos ou serviços a serem vistos e até mesmo adquiridos ou como ferramentas para o auxílio de equipes de vendas. Entretanto, a principal aplicação dos sistemas de recomendação é como ferramenta de personalização da web com foco no apoio à decisão de compra ou locação de algum produto ou serviço, como livros, filmes, pacotes de viagem, CDs e muitos outros. Em sua grande maioria eles estão in- corporados a sites de comércio eletrônico.
Para que um sistema de recomendação seja eficaz no comércio eletrônico, é necessária a construção de regras de associação entre itens, ou seja, regras que indiquem quais itens são os de maior interesse para cada usuário em cada um de seus momentos de busca por um pro- duto na Web. O elemento central desse processo é denominado de algoritmo de recomenda- ção, sendo o mais clássico de todos o algoritmo Apriori, caracterizado por uma busca iterativa e determinística por regras de associação. Além dele, algoritmos inspirados na biologia tam- bém vêm sendo amplamente aplicados nesse contexto, como algoritmos evolutivos e imuno- lógicos. O objetivo dessa dissertação foi exatamente o de investigar o uso de algoritmos bioinspirados para a mineração de regras de associação e compará-los ao algoritmo clássico Apriori. Foram feitas investigações envolvendo diferentes mecanismos de seleção e recombi- nação para o algoritmo evolutivo, assim como o uso de seleção probabilística para o algoritmo imunológico. Além disso, foi feita uma comparação geral dos mecanismos e algoritmos sele- cionados em bases de dados reais extraídas de lojas de comércio eletrônico brasileiras.
Os resultados permitiram identificar uma combinação adequada de mecanismo de se- leção e recombinação para o algoritmo evolutivo e o impacto da seleção probabilística no algoritmo imunológico. Estes algoritmos bioinspirados também foram comparados com o Apriori e os benefícios do uso de cada um deles discutidos.
Os resultados apresentados nesta pesquisa servem como uma primeira etapa para a aplicação de algoritmos bioinspirados para recomendação de produtos em comércio eletrôni- co. Contudo, para uma aplicabilidade prática desses algoritmos nestas empresas é recomendá- vel que outras medidas sejam utilizadas para a avaliação das regras, ou seja, a função de fit- ness.
Dentre os trabalhos futuros destacam-se:
Comparação dos algoritmos investigados com outras técnicas, determinísticas e probabilísticas, da literatura;
Avaliação dos algoritmos em outras bases de dados, para que se possa fazer uma comparação direta com os resultados da literatura. Aqui merece destaque o fato de que boa parte dos trabalhos da literatura não disponibiliza as bases usadas por questões de confidencialidade; e
7 REFERÊNCIAS BIBLIOGRÁFICAS
ADOMAVICIUS, G.; TUZHILIN, A. Toward the Next Generation of Recommender
Systems: A Survey of the State-of-the-Art and Possible Extensions. IEEE Trans. on Knowl.
and Data Eng. Piscataway, v. 17, p. 734--749, 2005.
AGRAWAL, R.; IMIELINSKI, T.; SWAMI, A. Mining association rules between sets of items in large databases. SIGMOD '93 Proceedings of the 1993 ACM SIGMOD
international conference on Management of data. New York, v. 22, n. 2, p. 207--216,
1993.
AGRAWAL, R.; SRIKANT, R. Fast Algorithms for Mining Association Rules. Proc 20th
Int Conf Very Large Data Bases VLDB., 1994. 487--499.
ALBERTIN, A. L. Comércio Eletrônico: Modelo, Aspectos e Contribuições de sua
Aplicação. São Paulo: Atlas, 2001.
ANGEHRN, A. Designing mature internet business strategies: The ICDTmodel. European
Management Journal. v. 15, p. 361-369, 1997.
ANSARI, A.; ESSEGAIER, S.; KOHLI, R. Internet Recommendation Systems. Journal of
Marketing Research. p. 363--375, 2000.
BÄCK, T.; FOGEL, D. B.; MICHALEWICZ, T. Evolutionary Computation 1: Basic
Algorithms and Operators. [S.l.]: Taylor & Francis, 2000.
BALABANOVIC, M.; SHOHAM, Y. Fab: content-based, collaborative recommendation.
Commun. ACM. Nova York, v. 40, n. 3, p. 66--72, 1997.
BALLARD, D. H. An introduction to Natural Computing. [S.l.]: MIT Press, 1999. BLICKLE, T. Theory of Evolutionary Algorithms and Application to System Synthesis. Tese (Doutorado), Swiss Federal Institute of Technology, Zurique, 1996.
BLOCH, M.; PIGNEUR, Y.; SEGEV, A. On The Road of Electronic Commerce: A Business Value Framework, Gaining Competitive Advantage and Some Research Issue. CITM
BOOKER, L. B.; GOLDBERG, D. E.; HOLLAND, J. H. Classifier systems and genetic algorithms. Artificial Intelligence. v. 40, p. 235--282, 1989.
BROWNLEE, J. Clever Algorithms: Nature-inspired Programming Recipes. 1ª. [S.l.]: LuLu, 2011.
BURKE, R. Knowledge-based recommender systems. Encyclopedia of Library and
Information Systems. v. 69, p. 175-186, 2000.
BURKE, R. Hybrid Recommender Systems: Survey and Experiments. User Modeling and
User-Adapted Interaction. Hingham, v. 12, n. 4, p. 331--370, 2002.
CAMERON, D. Eletronic commerce: the new business platform of the Internet. [S.l.]: Computer Technology Research, 1997.
CARVALHO, A. P. L. F. et al. Computação bioinspirada. Apostila de minicurso XXIII JAI
- Jornada de Atualização em Informática. Salvador, Agosto/2004. p. 50.
CARVALHO, D. R. Data Mining através de indução de Regras e Algoritmos Genéticos. Dissertação (Mestrado), Pontífia Universidade Católica do Paraná, Curitiba, 1999.
CAZELLA, S. C.; NUNES, M.; REATEGUI, E. Recomendação, A Ciência da Opinião: Estado da arte em Sistemas de. CSBC XXX Congresso da SBC Jornada de Atualização de
Informática (JAI). p. 161--216, 2010.
CIOS, K. J. et al. Data Mining: A Knowledge Discovery Approach. [S.l.]: Springer, v. XV, 2007.
CORDÓN, O. et al. Genetic Fuzzy Systems: Evolutionary Tuning and Learning of Fuzzy Knowledge Bases. Fuzzy Sets and Systems. Singapura, v. 141, p. 161--162, 2004. CUNHA, D. S.; DE CASTRO, L. N. The Influence of Selection and Crossover in an
Evolutionary Algorithm for Association Rule Mining. Advances in Information Technology
and Applied Computing., 2012a. 170-174.
CUNHA, D. S.; DE CASTRO, L. N. Evolutionary and Immune Algorithms Applied to Association Rule Mining. Swarm, Evolutionary and Memetic Computing Conference. Bhubaneswar, v. 7677, p. 628-635, 2012b.
DARWIN, C. On the Origin of Species by Means of Natural Selection, or, the
Preservation of Favoured Races in the Struggle for Life. London: [s.n.], 1959.
DE CASTRO, L. N. Fundamentals of Natural Computing: Basic Concepts, Algorithms
and Applications. [S.l.]: CRC Press LLC, 2006.
DE CASTRO, L. N. D.; ZUBEN, F. J. V. Learning and optimization using the clonal selection principle. IEEE Transactions on Evolutionary Computation. p. 239-251, 2002. DE CASTRO, L. N.; KNIDEL, H. Vendendo para Pessoas e não para Computadores. Revista
E-CommerceBrasil. v. 2, n. 7, p. 10-13, 2012.
DE CASTRO, L. N.; TIMMIS, J. Artificial Immune Systems: A New Computational
Approach. [S.l.]: Springer-Verlag, 2002. 357 p.
DE CASTRO, L. N.; VON ZUBEN, F. J. The Clonal Selection Algorithm with Engineering Applications. Genetic and Evolutionary Computation Conference., 2000. 36-37.
DE CASTRO, L. N.; VON ZUBEN, F. J.; DE DEUS, G. A. The Construction of a Boolean Competitive Neural Networks Using Ideas from Immunology. Neurocomputing. p. 51-85, 2003.
DE CASTRO, L. N.; ZUBEN, F. V. Recent Developments in Biologically Inspired
Computing. [S.l.]: IGI Publishing, 2004.
DE JONG, K. A. Evolutionary computation: A unified approach. [S.l.]: MIT Press, 2006. Disponível em: <http://www.cs.gmu.edu/~eclab/projects/ec_courseware/>. Acessado em: 12 nov. 2011.
DEB, K. Multi-objective optimization using evolutionary algorithms. Generations Journal
Of The American Society On Aging. p. 63--74, 2001.
DEHURI, S. et al. Multiobjective genetic algorithm for association rule mining using a homogeneous dedicated cluster of workstations. American Journal of Applied Sciences. v. 3, p. 2086–2095, 2006.
DEL JESUS, M. J. et al. On the discovery of association rules by means of evolutionary algorithms. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. 1, Fevereiro/2011. 397--415.
DONG, X.; LI, X. An Immune Based Relational Database Intrusion Detection Algorithm.
Proceedings of the 2009 Ninth Internacional Conference on Hybrid Intelligent Systems. IEEE Computer Society. v. III, p. 295-300, 2009.
DUBOIS, D.; PRADE, H.; SUDKAMP, T. On the representation, measurement, and
discovery of fuzzy associations. Fuzzy Systems, IEEE Transactions on. v. 13, p. 250--262, 2005.
FAYYAD, U.; SHAPIRO, G.; SMYTH, P. From Data Mining to Knowledge Discovery in Databases: An Overview. Advances in knowledge discovery and data mining. p. 1--34, 1996.
FREITAS, A. A. Datamining and knowledge discovery with evolutionary algorithms. Berlin: Springer. 2002.
FUKUDA, T. et al. Data mining using two-dimensional optimized association rules for
numeric data: scheme, algorithms, visualization. Proceedings of the ACM SIGMOD
International Conference on Management of Data. Montreal: [s.n.]. 1996. p. 13-23. GENG, L.; HAMILTON, H. J. Interestingness measures for data mining: A survey. ACM
Computing Surveys. v. 38, p. 9--es, 2006.
GHOSH, A.; NATH, B. Multi-objective rule mining using genetic algorithms. Information
Sciences. v. 163, p. 123--133, 2004.
GOLDBERG, D. E. Genetic Algorithms in Search, Optimization and Machine Learning.
AddisonWesley. p. 432, 1989.
GONZALEZ, G. .; DE LA ROSA, J. L.; MONTANER, M. Embedding Emotional Context
in Recommender Systems. Proceedings of the 2007 IEEE 23rd International Conference on
Data Engineering Workshop. [S.l.]: IEEE Computer Society. 2007. p. 845--852.
GUTTMAN, R. H.; MOUKAS, A. G.; MAES, P. Agent-mediated electronic commerce: a survey. The Knowledge Engineering Review. New York, v. 13, n. 2, p. 147--159, 1998. GYARA, F.; SACHDEV, T. Win in the flat world. White paper - Infosys Technologies Disponível em: <http://www.infosys.com/offerings/it-
services/informationmanagement/white-papers/documents/personalizing-portals.pdf>. Acessado em: 10/Novembro/2011.
HAN, J.; KAMBER, M. Data Mining - Concepts and Techniques. 2ª. Nova York: Morgan Kaufmann, 2006.
HERLOCKER, J. L. Understanding and Improving Automated Collaborative. Tese (Doutorado), Universidade de Minnesota, Minnesota, 2000.
HERRERA, F. Genetic fuzzy systems: taxonomy, current research trends and prospects.
Evolutionary Intelligence. v. 1, p. 27--46, 2008.
HOLLAND, J. H. Adaptive in Natural and Artificial Systems. [S.l.]: University of Michigan Press. 1975.
HOLSHEIMER, M. et al. A perspective on database and data mining. Proceedings of the First International Conference of Knowledge Discovery and Data Mining. Montreal: [s.n.]. 1996.
HU, Y. C. Determining membership functions and minimum fuzzy support in finding fuzzy association rules for classification problems. Knowledge-Based Systems. v. 19, p. 57--66, 2006.
KAYA, M.; ALHAJJ, R. Utilizing Genetic Algorithms to Optimize Membership Functions for Fuzzy Weighted Association Rules Mining. Applied Intelligence. v. 24, p. 7--15, 2006. KWASNICKA H., S. K. Discovery of association rules from medical data - classical and evolutionary approaches. Annales, Informatica. v. IV, p. 153--157, 2006.
LEI, Z.; REN-HOU, L. An Algorithm for Mining Fuzzy Association Rules Based on Immune Principles. Proceedings of the 7th IEEE Internacional Conference. Bioinformatics and
Bioengineering. p. 1285-1289, 2007.
LINDEN, R. Algoritmos Genéticos. 3ª Edição. Rio de Janeiro: Ciência Moderna Ltda., 2012. LIU, B. Web Data Mining: Exploring Hyperlinks, contents & usage data (Data centric
systems & applications). [S.l.]: Springer, 2006. 480 p.
LIU, B. et al. Finding interesting patterns using user expectations. IEEE Transactions on
Knowledge and Data Engineering. v. XI, p. 817--832, 1999.
LIU, T. An Immune Based Association Rule Algorithm. Innovative Computing,
MANGE, D.; TOMASSINI, M. Bio-inspired computing machines: towards novel
computational architectures. [S.l.]: PPUR presses polytechniques, 1998. 372 p.
MANILLA, H. Finding Interesting Rules From Large Sets of Discovered Association
Rules. 3rd International Conference on Information and Knowledge Management. [S.l.]:
[s.n.]. 1994.
MATA, J.; ÁLVAREZ, J.; RIQUELME, J. Discovering numeric association. PAKDD ’02: the 6th Pacific-Asia Conference on Advances in Knowledge. Berlin Heildelberg: Springer- Verlag. 2002. p. 40--51.
MICHALEWICZ, Z. Evolutionary Algorithms in Engineering Applications. 1ª. New York: Springer-Verlag, 1997.
MONTANER, M.; LÓPEZ, B.; DE LA ROSA, J. L. A Taxonomy of Recommender Agents on the Internet. Artificial Intelligence Review. v. 19, n. 4, p. 285--330, 2003.
NUNES, M. A. S. N.; MACHADO, G. J. C.; SCHNEIDER, H. N. Repensando os ambientes
virtuais de aprendizagem: o caso da UFS. XX Simpósio Brasileiro de Informática na
Educação - II Workshop sobre Modelos Pedagógicos em Educação a. Florianópolis: XX SBIE-SBC. 2009.
PACHECO, M. A. C. Algoritmos Genéticos: Princípios e Aplicações. p. 9 Apostila, Pontifícia Universidade Católica do Rio de Janeiro, Rio de Janeiro, 1999.
RESNICK, P.; VARIAN, H. R. Recommender systems. Commun. ACM. Nova Iorque, v. 40, p. 56--58, 1997.
RIDLEY, M. Evolution. [S.l.]: Oxford University Press, 1997.
RUSSELL, S.; NORVIG, P. Artificial Intelligence – A Modern Approach. 2ª Edição. [S.l.]:
Prentice-Hall, 2003.
SARWAR, B. et al. Item-based collaborative filtering recommendation algorithms.
Proceedings of the 10th international conference on World Wide Web. Hong Kong, 2001.
285--295.
SCHAFER, J. B.; KONSTAN, J. A.; RIEDL, J. Recommender Systems in E-Commerce.
SCHAFER, J. B.; KONSTAN, J. A.; RIEDL, J. E-Commerce Recommender Applications.
Data Mining and Knowledge Discovery. v. 5, n. 1/2, p. 115-153, 2001.
SHENOY, P. D. et al. Evolutionary approach for mining association rules on dynamic
databases. PAKDD ’03: Proceedings of the 7th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Berlin Heildelberg: Springer-Verlag. 2003. p. 325-- 336.
SHENOY, P. D. et al. Dynamic association rule mining using genetic algorithms. Intelligent
Data Analysis. v. 9, n. 5, p. 439--453, 2005.
SMITH, S. F. A learning system based on genetic adaptive algorithms. Tese (Doutorado), Universidade de Pittsburgh, Pittsburgh, 1980.
SU, Y.; GU, X.; LI, Z. Incremental updating Algorithm Based on Artificial Immune System For Mining Association Rules. The IEEE International Conference on e-Business
Engineering., 2006. 541-544.
TANOMARU, J. Motivação, Fundamentos e Aplicações de Algoritmos Genéticos. II Congresso Brasileiro de Redes Neurais - III Escola de Redes Neurais. Curitiba: [s.n.]. 1995. TURBAN, E. et al. Electronic Commerce: A Managerial Perspective. [S.l.]: Prentice Hall, 1999.
WAKABI-WAISWA, P. P.; BARYAMUREEBA, V. Extraction of interesting association rules using genetic algorithms. International Journal of Computing and ICT Research. v. 2, p. 26--33, 2008.
WANG, W.; BRIDGES, S. M. Genetic Algorithm Optimization of Membership Functions for Mining Fuzzy Association Rules. System. v. 22, p. 2--5, 2000.
YANG, G. Mining Association Rules from Data with Hybrid Attributes Based on Immune Genetic Algorithm. Fuzzy Systems and Knowledge Discovery (FSKD). p. 1446-1449, 2010.
ZHANG, Y.; BU, S. Association Rules Mining Based on Simulated Annealing Immune Programming Algorithm. Computer Engineering and Technology., 2009. 424-427.
ZHANG, Y.; BU, S.; ZHANG, Y. Association Rules Mining Based on the Improved Immune Algorithm. Intelligent Information Technology Application., 2009. 453-456.