˜ UNIVERSIDADE FEDERAL DE SAO CARLOS CENTRO DE CIEˆNCIAS EXATAS E DE TECNOLOGIA PROGRAMA DE PO´S-GRADUAC¸A˜O EM CIEˆNCIA DA COMPUTAC¸A˜O ˜ ˜ REGRAS DE ASSOCIAC¸ AO E CORRELAC¸ AO TEMPORAL PARA POPULAR E DETECTAR ˆ INCONSISTENCIAS EM GRANDES BASES DE CONHECIMENTO RAFAEL GARCIA LEONEL MIANI ORIENTADOR: PROF. DR. ESTEVAM RAFAEL HRUSCHKA JUNIOR Sa˜o Carlos – SP Dezembro/2017 ˜ UNIVERSIDADE FEDERAL DE SAO CARLOS CENTRO DE CIEˆNCIAS EXATAS E DE TECNOLOGIA PROGRAMA DE PO´S-GRADUAC¸A˜O EM CIEˆNCIA DA COMPUTAC¸A˜O ˜ ˜ REGRAS DE ASSOCIAC¸ AO E CORRELAC¸ AO TEMPORAL PARA POPULAR E DETECTAR ˆ INCONSISTENCIAS EM GRANDES BASES DE CONHECIMENTO RAFAEL GARCIA LEONEL MIANI Tese apresentada ao Programa de Po´s-Graduac¸a˜o em Cieˆncia da Computac¸a˜o da Universidade Fe- deral de Sa˜o Carlos, como parte dos requisitos para a obtenc¸a˜o do t´ıtulo de Doutor em Cieˆncia da Computac¸a˜o,a´readeconcentrac¸a˜o: InteligeˆnciaAr- tificial Orientador: Prof. Dr. Estevam Rafael Hruschka Junior Sa˜o Carlos – SP Dezembro/2017 A Deus, a minha esposa Tha´ıs, a minha filha Marina e a minha ma˜e Lucineide. A GRADECIMENTOS Agradec¸oaDeuspelaforc¸aepersisteˆnciaquemeproporcionouduranteoprojeto. Agradec¸o a minha esposa Tha´ıs e a minha filha Marina pelo apoio e suporte para o desenvolvimento do trabalho. Ao meu orientador e aos colegas de grupo pelas dicas e sugesto˜es para o bom desen- volvimentodoprojeto. R ESUMO Grandesbasesdeconhecimentocrescenteteˆmsidouminteressantecampoemmuitaspes- quisas nos u´ltimos anos. A maioria das te´cnicas focam na construc¸a˜o de algoritmos para auxiliar a Base de Conhecimento (BC) a expandir automaticamente (ou semiautomatica- mente). Entretanto, muitas ferramentas utilizadas para a expandir as BCs podem extrair dadosincompletosouincorretos,tornandoabaseinconsistente. Dessaforma,estetrabalho possui o objetivo de expandir as grandes bases de conhecimento e detectar inconsisteˆncias nas mesmas. Para tal, sa˜o utilizadas a minerac¸a˜o de regras de associac¸a˜o e a correlac¸a˜o temporal. Ao aplicar um algoritmo de extrac¸a˜o de regras de associac¸a˜o em grandes bases deconhecimento,e´ necessa´rioconsideraroproblemadevaloresausentes,umavezqueelas crescem diariamente, na˜o possuindo todos os dados. Logo, foi criado um novo paraˆmetro pararealizaroca´lculodosuporte, denominadoMSC,paratrabalharcomvaloresausentes. Ale´mdisso,umgrandeproblemaaoutilizarregrasdeassociac¸a˜oe´oesforc¸ogastoaoavaliar cadaregraextra´ıda. Dessaforma,opresentetrabalhodesenvolveuocomponenteER,oqual elimina regras de associac¸a˜o redundantes e irrelevantes. Cada regra va´lida e´ utilizada pelo componente TARE com o objetivo de detectar inconsisteˆncias. TARE introduz o conceito deSTARs(regrasdeassociac¸a˜otemporaisespec´ıficas),asquaissa˜outilizadasparadetectar poss´ıveisinconsisteˆncias. CadaSTARconsideradarelevantee´ utilizadacomoentradapara ocomponenteTCI como intuitodeobter correlac¸o˜estemporaispara (i)detectar poss´ıveis inconsisteˆncias e (ii) auxiliar a popular a BC. Experimentos realizados demonstraram que asregrasdeassociac¸a˜oeacorrelac¸a˜otemporalsa˜ocapazesdeexpandirabasedeconheci- mento, diminuindo a quantidade de valores ausentes. Ale´m disso, ambos os componentes TAREeTCIforameficientesnoprocessoparadetectarposs´ıveisinconsisteˆnciasnabasede dados. Porfim, o componenteER reduziu emmais de 30%o nu´merode regrassemperda noprocessodepopularaBC. Palavras-chave: Regras de Associac¸a˜o, Grandes Bases de Conhecimento, Regras de Associac¸a˜o Tem- poraisEspec´ıficas,Correlac¸a˜oTemporal,Detecc¸a˜odeInconsisteˆncia,RegrasRedundantes,RegrasIrre- levantes A BSTRACT Large growing knowledge bases have been an interesting field in many researches in the past few years. Most techniques focus on constructing algorithms to help a Knowledge Base(KB)automatically(orsemiautomatically)expands. However,manytoolsusedtoex- pandtheKBscanextractincompleteorincorrectdata,turningtheKBinconsistent. Inthis way, this work has the objective to expand large knowledge bases as well as detect incon- sistenciesonthem. Toaccomplishthat,anassociationruleminingalgorithmandtemporal correlationareused. Applyinganalgorithmtoextractassociationrulesinlargeknowledge bases,themissingvalueproblemneedtobeconsidered,oncethesebasesgrowdaytoday, and do not have all of the data. Therefore, a new parameter was created to perform the supportcalculation,theMSCparameter,todealwithmissingvalues. Besides,amajorpro- blem on using association rules is the effort spent to analyze each extracted rule. Thus, thisworkdevelopedERcomponent,whicheliminatesredundantandirrelevantassociation rules. Each valid rule is used by TARE component with the purpose of detecting incon- sistencies. TARE introduces the concept of STARs (specific temporal association rules), which are used to detect possible inconsistencies. Each relevant STAR is used as an input toTCIcomponentinordertogettemporalcorrelationsto(i)detectpossibleinconsistencies and (ii) to help populating the KB. Experiments showed that the association rules and the temporal correlation are capable to expand the knowledge base, decreasing the amount of missingvalues. Moreover,bothTAREandTCIcomponentswereefficientintheprocessof detecting possible inconsistencies in the data set. Finally, the ER component reduced the numberofrulesinmorethen30%withoutanylostintheprocessofpopulatingtheKB. Keywords: AssociationRules,LargeKnowledgeBases,SpecificTemporalAssociationRules,Temporal Correlation,InconsistencyDetection,RedundantRules,IrrelevantRules L F ISTA DE IGURAS 2.1 Exemplodegerac¸a˜odeitemsetsfrequentes . . . . . . . . . . . . . . . . . . . 27 2.2 Exemplodetaxonomia-adaptadode(SRIKANT;AGRAWAL,1995) . . . . . . . 29 2.3 Reticuladoparacomparac¸a˜oentreFIsxFCIsxMFIs . . . . . . . . . . . . . . 32 3.1 ArquiteturadoNELL-adaptadade(CARLSONetal.,2010a) . . . . . . . . . . . 41 6.1 ArquiteturadoSistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 6.2 EtapasdoAlgoritmodeRegrasdeAssociac¸a˜o . . . . . . . . . . . . . . . . . . 70 6.3 RelacionamentoentreFIMVxFIxFCIxMFI . . . . . . . . . . . . . . . . . 73 6.4 ArquiteturadocomponenteTCI . . . . . . . . . . . . . . . . . . . . . . . . . 88 7.1 CategoriasdosubconjuntodaBCdoNELLutilizadasnosexperimentos . . . . 96 7.2 Comparac¸a˜oentrePrimeiraeSegundaAbordagem . . . . . . . . . . . . . . . 97 7.3 Comparac¸a˜oentreMSCxPF-growth . . . . . . . . . . . . . . . . . . . . . . . 99 7.4 RegrasRelevantes-MSCxPF-growth . . . . . . . . . . . . . . . . . . . . . . 99 7.5 Nu´merodeRegrasextra´ıdaspeloExperimento1 . . . . . . . . . . . . . . . . 101 7.6 Nu´merodeRegrasRelevantesextra´ıdaspeloExperimento1 . . . . . . . . . . 102 7.7 Nu´merodeRegrasextra´ıdaspeloExperimento2 . . . . . . . . . . . . . . . . 103 7.8 Nu´merodeRegrasExtra´ıdaspeloExperimento3 . . . . . . . . . . . . . . . . 104 7.9 NovasRegrasobtidasnosExperimentos2e3 . . . . . . . . . . . . . . . . . . 105 7.10 QuantidadedeFIMVs,FIs,FCIseMFIs . . . . . . . . . . . . . . . . . . . . . 107 7.11 Nu´merodeRegrasdeAssociac¸a˜ocomerrosdepontualidade . . . . . . . . . . 111 7.12 QuantidadedeSTARs,poss´ıveisinconsisteˆnciaspeloTAREeTCI,eCorrelac¸o˜es Temporais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 7.13 QuantidadedeinconsisteˆnciasreaisTARExTCInoExperimento1 . . . . . . 112 7.14 QuantidadedeSTARs,poss´ıveisinconsisteˆnciaspeloTAREeTCI,eCorrelac¸o˜es Temporais-Experimento2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 7.15 QuantidadedeinconsisteˆnciasreaisTARExTCInoExperimento2 . . . . . . 115 7.16 QuantidadedeSTARs,poss´ıveisinconsisteˆnciaspeloTAREeTCI,eCorrelac¸o˜es Temporais-Experimento3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.17 QuantidadedeinconsisteˆnciasreaisTARExTCInoExperimento3 . . . . . . 117 7.18 Tempogastoparaobteritemsetsfrequentes,gerarregras,eliminarregrasredun- danteseirrelevantesnoExperimento1 . . . . . . . . . . . . . . . . . . . . . 119 7.19 TempogastopeloTAREeTCInoExperimento1 . . . . . . . . . . . . . . . 120 7.20 Tempogastoparaobteritemsetsfrequentes,gerarregras,eliminarregrasredun- danteseirrelevantesnoExperimento2 . . . . . . . . . . . . . . . . . . . . . 121 7.21 Tempogastoparaobteritemsetsfrequentes,gerarregras,eliminarregrasredun- danteseirrelevantesnoExperimento3 . . . . . . . . . . . . . . . . . . . . . 122 7.22 TempogastopeloTAREeTCInoExperimento2 . . . . . . . . . . . . . . . 122 7.23 TempogastopeloTAREeTCInoExperimento3 . . . . . . . . . . . . . . . 123 L T ISTA DE ABELAS 1.1 Exemploderegrasdeassociac¸a˜oeregrasdeassociac¸a˜otemporaisespec´ıficas. . 18 2.1 ExemplodeumabasededadosamostralD . . . . . . . . . . . . . . . . . . . 26 2.2 Exemploderegrasgeradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Basededadosamostralparacomparac¸a˜oentreFIsxFCIsXMFIs . . . . . . . 32 3.1 Exemplodetabeladejogadoresdefutebol . . . . . . . . . . . . . . . . . . . . 48 4.1 ExemplodeValoresAusentesquepodemnuncaocorrer . . . . . . . . . . . . . 54 5.1 Relac¸o˜esTemporaisdeAllen . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.1 Conjuntoamostraldedados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6.2 ComparativoentreFIMVxFIxFCIxMFI . . . . . . . . . . . . . . . . . . . 72 6.3 Exemploderegrasgeradasparaoitemset(FutebolAmericano,nfl,super bowl) 74 6.4 Exemploderegrasdeassociac¸a˜oparaaTabela6.2. . . . . . . . . . . . . . . . 75 6.5 Exemploparaeliminarregrassuperantecedentes . . . . . . . . . . . . . . . . 77 6.6 RegrasFinais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.7 Conjuntoamostraldedadosatualizadocomasregrasdeassociac¸a˜o. . . . . . . 81 6.8 Exemplo de uma regra de associac¸a˜o e de suas regras de associac¸a˜o temporais espec´ıficas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.9 RegrasdeAssociac¸a˜oparapopularaBCdoNELL . . . . . . . . . . . . . . . 84 6.10 STARsutilizadasparaformarasregrasdeassociac¸a˜odatabela6.9 . . . . . . . 85 6.11 Correc¸a˜odasinstaˆnciasparaoatletaLebronJames . . . . . . . . . . . . . . . 87 6.12 IntervaloTemporaldeAllenmodificado . . . . . . . . . . . . . . . . . . . . . 90 6.13 Exemplodeinstaˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90