Anlisis de secuencias discretas para la deteccin de Patrones de Diseo de Software

Alumno: Juan Francisco Silva Logroo

Director: Luis Sebastin BerdnCo-director: Marcelo Gabriel Armentano

Deteccin de Patrones de Diseo de Software con Modelos de Markov de Orden Variable

Tesis de Grado de Ingeniera de SistemasTandil, Marzo de 2012.-

1AgendaIntroduccinTrabajos relacionadosTrabajo realizadoMarco TericoModelos de MarkovMaterializacinExperimentosConclusiones

2Introduccin

Actuar en funcin del comportamientodel usuarioUsuario/LectorAgenteAplicacin de Diseo (CASE)Interaccin inicial MixtaObserva e ImitaManipulacin directa

3Trabajos RelacionadosDos enfoques predominantesIngeniera ReversaDeteccin dinmica del Patrn objetivo

Trabajo realizadoDeteccin temprana del Patrn de Diseo objetivoAgente de Interfaz Deteccin dinmica Plan RecognitionObjetivo + Acciones + DominioBiblioteca de Planes: Modelos de Markov de Orden Variable (VOMM)3 enfoquesGeneracin computacional del Plan Corpus: Planning

Actividades realizadas a lo largo del trabajo5AgendaIntroduccinTrabajos relacionadosTrabajo realizadoMarco TericoModelos de MarkovMaterializacinExperimentosConclusiones

6Modelos de MarkovUna cadena de Markov es un proceso estocstico con la propiedad Markoviana

Modelos de Markov (2)Modelos de Markov de orden m (m-gramas)

P(|s), and sm ,|s|=m Unigramas, Bigramas, Problemas?

Modelos de Markov de Orden VariableEl numero de variables aleatorias que condicionan la distribucin de probabilidades depende del contexto bajo observacinReduccin en el numero de parmetros que condicionan al modeloP(|s), , sm, |s|mProbabilistic Suffix Automata (PSA)Modela el conjunto mnimo de sub secuencias (de longitud variable) necesarias para modelar a la fuente de informacin estadsticaConstruccin mediante PBE o PBD

Probabilistic Suffix Automata

Probabilistic Suffix AutomataPara cada accin observada, cada PSA realizar la correspondiente transicin de estado y calculara la probabilidad para la secuencia de acciones observada hasta el momento

Exponential Moving Average (EMA)

11AgendaIntroduccinTrabajos relacionadosTrabajo realizadoMarco TericoModelos de MarkovMaterializacinExperimentosConclusiones

12Enfoque I: VOMM no parametrizadoDefinicin del Alfabeto

OperacinDescripcinClasesagregarInterfazAgrega una Interfaz al diagramaagregarClassAbsAgrega una Clase abstracta al diagramaagregarClassAgrega una clase concreta al diagramaRelacionesdefAgregacionEstablece una relacin de agregacindefComposicionEstablece una relacin de composicindefGeneralizacionEstablece una relacin de generalizacindefAsociacionEstablece una relacin de asociacindefDependenciaEstablece una relacin de dependenciadefImplementacionEstablece una relacin de implementacin

Enfoque I (2)Patrn Composite

agregarClass;agregarClassAbs;defDependencia;agregarClass;defGeneralizacion;agregarClass;defGeneralizacion;defComposicionagregarClass;agregarClassAbs;agregarClass;agregarClass;defGeneralizacion;defGeneralizacion;defComposicion;defDependenciaagregarClassAbs;agregarClass;defDependencia;agregarClass;defComposicion;defGeneralizacion;agregarClass;defGeneralizacion

PSA para el Patrn Composite s = agregarClass;agregarClassAbs;defDependencia;agregarClass;defGeneralizacion;agregarClass;defGeneralizacion;defComposicion

Enfoque II: VOMM parametrizadoDefinicin del Alfabeto

Alfabeto para el Enfoque IParmetros que se incorporan para el Enfoque IIClasesagregarInterfaz ([nombre_interfaz])agregarClassAbs([nombre_Clase_Abstracta])agregarClass([nombre_Clase])RelacionesdefAgregacion([nombre_C_CA_I(1) ], [nombre_C_CA_I (2)])defComposicion([nombre_C_CA_I(1) ], [nombre_C_CA_I (2)])defGeneralizacion([nombre_C_CA_I(1) ], [nombre_C_CA_I (2)])defAsociacion([nombre_C_CA_I(1) ], [nombre_C_CA_I (2)])defDependencia([nombre_C_CA_I(1) ], [nombre_C_CA_I (2)])defImplementacion([nombre_C_CA_I], [nombre _Interfaz])

Enfoque II (2)Patrn CompositeagregarClass(Cliente); agregarClassAbs(Grafico); defDependencia(Cliente, Grafico); agregarClass(Sing); defGeneralizacion(Sing, Grafico); agregarClass(Comp); defGeneralizacion(Comp, Grafico); defComposicion(Comp, Grafico)Que cambio?Explosin del Universo de tareas Smbolos nicosCantidad de posibles transiciones en cada nodoAdministracin de parmetros

Administracin de parmetros

TamaoSubconjuntos1 (4){Cliente}; {Grafico}; {Sing}; {Comp}2 (12){Cliente, Grafico}; {Cliente, Sing}; {Cliente, Comp};{Grafico,Cliente}; {Grafico, Sing}; {Grafico, Comp};{Sing, Cliente}; ;{Comp, Grafico}; {Comp, Sing}3 (12){Cliente, Grafico, Sing}; {Cliente, Grafico, Comp}; {Cliente, Sing, Grafico}; ;{Grafico, Sing, Comp}; {Grafico,Comp, Cliente}; {Grafico, Comp, Sing};4 (){Cliente, Grafico, Sing, Comp}; {Cliente, Sing, Grafico, Comp}; {Cliente, Sing, Comp, Grafico}; ... ; {Comp, Sing, Grafico, Cliente}

Administracin de parmetros (2)

Enfoque III: VOMM con Ventana Deslizante

AgendaIntroduccinTrabajos relacionadosTrabajo realizadoMarco TericoModelos de MarkovMaterializacinExperimentosConclusiones

21Resultado ExperimentalesConstruccin del Data-SetCategoraPatrnCantidad de Acciones por SecuenciaCantidad de Acciones distintasCantidad de Clases (concretas, abstractas e interfaces)Planes GeneradosE II y E IIIE ICreacionalesFactory Method (FM)1337852211Prototype (Prot)74419385EstructuralesAdapter (Adap)644192118Bridge (Brid)114617021Composite (Comp)844837382Decorator (Deco)1246857338ComportamentalesCommand (Comm)1477880664Iterator (Ite)1557842323Mediator (Med)112486815Observer (Obs)115417865

Resultados Experimentales: MtricasOn Line Accuracy

Convergencia

Presicion Experimento IObjetivo: Obtener el valor de mas adecuado para cada enfoqueMetodologa:Leave One Out Cross Validation (LOOCV)Promediado de las mtricas Experimento I: Resultados

MediaDesviacin EstndarExperimento I: Resultados (2)

Experimento IIObjetivo: medir la cantidad de veces que un modelo se encuentra dentro de los n mejores resultados predichosMetodologa:LOOCVUmbral de confianza Modificacin sobre mtrica:

Experimento II: Resultados

Experimento IIIObjetivo: Medir la confusin entre los patrones estudiadosMetodologa:LOOCVMtrica On Line AccuracyEjemplo: Composite 200 cadenasAdapBridCommCompDecoFMIteMedObsProtComposite1616365004224358AdapBridCommCompDecoFMIteMedObsProtComposite881825021121,52,54Experimento III: ResultadosAdapBridCommCompDecoFMIteMedObsProtAdapter67,807,6316,952,544,240,85Bridge85,7114,29Command100,00Composite1,050,7922,2523,0447,384,451,05Decorator98,521,48F. Method100,00Iterator4,0295,670,31Mediator100,00Observer100,00Prototype17,652,3520,0015,292,3542,35Precisin promedio (E I)81,23Experimento III: Resultados (2)Precisin promedio (E III) 70,25AdapBridCommCompDecoFMIteMedObsProtAdapter54,177,291,042,603,6511,4619,79Bridge90,595,883,53Command14,0983,180,681,590,45Composite17,688,0016,6116,9712,4327,001,31Decorator8,056,653,7377,950,233,38F. Method1,172,930,3594,011,53Iterator0,2499,76Mediator100Observer100Prototype9,8426,421,045,7033,6810,3611,921,04Precisin promedio (E II)71,73Experimento IVObjetivo: Evaluar el rendimiento de los enfoques en presencia de ruidoMetodologa: Construccin de Corpus Ruidoso: 20 y 40%Experimento I Leave One Out

Experimento IV: Resultados

AgendaIntroduccinTrabajos relacionadosTrabajo realizadoMarco TericoModelos de MarkovMaterializacinExperimentosConclusiones

34ConclusionesModelado de los Patrones de Diseo de Software con Modelos de Markov: 3 EnfoquesSin parmetrosCon parmetros Utilizando una ventana deslizanteFuncin de suavizado de datos estadsticos: EMA

Limitaciones:El crecimiento del alfabeto perjudica a los VOMMAumento en los estados necesarios para representar a cada patrnComplejidad poco practica del Enfoque IIDisminucin en las observaciones a analizar en el Enfoque III

ConclusionesTrabajos futurosExtensin del alfabeto utilizado por cada enfoqueMtodos y VariablesDiagramas de SecuenciaDeteccin de Anti-Patrones de DiseoConclusionesPublicacionesSILVA LOGROO, J.F., L.S. BERDUN, M. G. ARMENTANO, y A.A. AMANDI. 2011. Discrete Sequences Analysis for Detecting Software Design Patterns. In: Proceedings of the 2nd International Conference on Advances in New Technologies, Interactive Interfaces and Communicability (ADNTIIC 2011). Huerta Grande, Crdoba: ALAIPO & AINCI, pp.243 - 253.

SILVA LOGROO, J.F., L.S. BERDUN, M. G. ARMENTANO, y A.A. AMANDI. 2011. Un enfoque para la generacin de Plan Corpus con un Algoritmo de Planning. In: Proceedings del 12 Simposio Argentino de Inteligencia Artificial (ASAI 2011), 40 JAIIO.. Cordoba, Argentina

SILVA LOGROO, J.F., L.S. BERDUN, M. G. ARMENTANO, y A.A. AMANDI. 2010. Anlisis de secuencias discretas para la deteccin de Patrones de Diseo de Software. In: 11 Simposio Argentino de Inteligencia Artificial (ASAI 2010), 39 JAIIO. Buenos Aires, Argentina

Preguntas

38Generacin del Plan CorpusGeneracin Manual Generacin AutomticaAlgoritmo de PlanningPermite obtener un conjunto de acciones, que cuando son ejecutadas en orden permiten alcanzar un objetivo

Algoritmo de Planning41Algoritmo de Planning (2)Ejemplo de Estado Final:

clase(cliente),clase(grafico),tipo(grafico,abst),clase(comp),generalizacion(comp,grafico),clase(sing),generalizacion(sing,grafico),composicion(comp,grafico),dependencia(cliente,grafico)

42Patrones de Diseo de SoftwareConjunto de clases y objetos donde cada uno de sus elementos fue especificado con las caractersticas necesarias para solucionar un problema de diseo general en un contexto particularMediante ellos se busca abstraer soluciones a problemas comunes y lograr as repetirlas ante un problema similar las veces que sean necesariasCategoraCreacionalEstructuralComportamentalPatronesAbstract Factory, Builder, Factory Method, Prototype, Singleton Adapter, Bridge, Composite, Decorator, Facade, Flyweight, ProxyChain of Responsability, Command, Interpreter, Iterator, Mediator, Memento, Observer, State, Strategy, Template Method, VisitorE. Gamma, R. Helm, R. Johnson y J. Vlissides, 1994Plan Recognition inferir los objetivos de un sujeto basndose en las acciones que este haya realizado en un determinado dominio Entrada:Un conjunto de objetivos que el agente espera que el usuario intente realizar en el dominio bajo estudioUn conjunto de modelos describiendo la forma en que el usuario puede alcanzar cada uno de los objetivos Una accin observada por el agente Salida:Predecir el objetivo del usuario y determinar como la accin observada contribuye para lograrlo

Bibliotecas de PlanesModelos de Markov

Probabilistic Suffix AutomataLa probabilidad emprica de una secuencia s con longitud l

Probabilidad emprica condicional de observar una accin luego de una secuencia s

donde

45