Técnicas de Optimización para la Minería de Datos

Usted está aquí

Créditos
6
Tipos
Complementaria de especialidad (Ciencia de los Datos)
Requisitos
Esta asignatura no tiene requisitos, pero tiene capacidades previas
Departamento
EIO
The course introduces the basic concepts of optimization and the different types of optimization problems, the iterative algorithms to solve these problems, and their properties. The practice of optimization using modeling languages to describe a problem and commercial and publicly available solvers is also emphasized.

Profesores

Responsable

  • Jordi Castro Pérez ( )

Otros

  • F. Javier Heredia Cervera ( )

Horas semanales

Teoría
3.2
Problemas
0
Laboratorio
0
Aprendizaje dirigido
0.77
Aprendizaje autónomo
0

Competencias

Competencias Técnicas de cada especialidad

Advanced computing

  • CEE3.2 - Capacidad para utilizar un espectro amplio y variado de recursos algorítmicos para resolver problemas de alta dificultad algorítmica.
  • CEE3.3 - Capacidad para entender las necesidades computacionales de problemas de disciplinas distintas de la informática y efectuar contribuciones significativas en equipos multidisciplinares que usen la computación.

Service engineering

  • CEE5.3 - Capacidad para trabajar en equipos interdisciplinarios de ingeniería de servicios y, disponiendo de la experiencia de dominio necesaria, capacidad para trabajar autónomamente en sistemas de servicios concretos.

Específicas comunes

  • CEC1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CEC2 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.

Competencias Técnicas Genéricas

Genéricas

  • CG1 - Capacidad para aplicar el método científico en el estudio y análisis de fenómenos y sistemas en cualquier ámbito de la Informática, así como en la concepción, diseño e implantación de soluciones informáticas innovadoras y originales.
  • CG3 - Capacidad para el modelado matemático, cálculo y diseño experimental en centros tecnológicos y de ingeniería de empresa, particularmente en tareas de investigación e innovación en todos los ámbitos de la Informática.

Competencias Transversales

Sostenibilidad y compromiso social

  • CTR2 - Conocer y comprender la complejidad de los fenómenos económicos y sociales típicos de la sociedad del bienestar. Ser capaz de analizar y valorar el impacto social y medioambiental

Razonamiento

  • CTR6 - Capacidad de razonamiento crítico, lógico y matemático. Capacidad para resolver problemas dentro de su área de estudio. Capacidad de abstracción: capacidad de crear y utilizar modelos que reflejen situaciones reales. Capacidad de diseñar y realizar experimentos sencillos, y analizar e interpretar sus resultados. Capacidad de análisis, síntesis y evaluación.

Básicas

  • CB9 - Que los estudiantes posean las habilidades de aprendizaje que les permitan continuar estudiando de un modo que habrá de ser en gran medida autodirigido o autónomo.

Objetivos

  1. Discerning what is an optimization problem and its type and having a basic knowledge of optimization algorithms
    Competencias relacionadas: CEE5.3, CEE3.2, CTR2, CTR6,
  2. Formulating optimization problems and representing them through a modeling language
    Competencias relacionadas: CEE5.3, CG1, CG3, CEE3.2, CEE3.3, CB9, CEC1, CEC2,
  3. Choosing an adequate solver type for a given problem
    Competencias relacionadas: CEE5.3, CEE3.2, CEE3.3,
  4. Using publicly available and commercial solvers. Interpreting results from solvers and communicating in writing results from optimization
    Competencias relacionadas: CEE5.3, CTR6,

Contenidos

  1. Unconstrained Optimization
    Optimality conditions. Convexity. Descent directions.
    Line search. Acceptability of step sizes.
    General minimization algorithm.
    Gradient method. Rate of convergence.
    Newton's method. Factorizations to ensure convergence.
    Weighted least squares.
    Introduction to AMPL. The Neos solver site.
  2. Constrained Optimization and Support Vector Machines.
    - Introduction to Support Vector Macines (SVM)
    - KKT Optimality conditions of constrained optimization. Optimality conditions of SVM.
    - Duality in Optimization. The dual of the SVM.
  3. Integer Programming
    - Modelling problems with binary variables.
    - The branch and bound algorithm for integer programming
    - Gomory's cutting planes algorithm.
    - Minimal spanning tree problem and algorithms of Kruskal and Prim.

Actividades

Actividad Acto evaluativo


Unconstrained Optimization

Optimality conditions. Convexity. Descent directions. Line search. Acceptability of step sizes. General minimization algorithm. Gradient method. Rate of convergence. Newton's method. Factorizations to ensure convergence. Weighted least squares. Introduction to AMPL. The Neos solver site.
Objetivos: 1 2 3 4
Teoría
17.3h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
35h

Constrained Optimization and Support Vector Machines

- Introduction to Support Vector Macines (SVM) - KKT Optimality conditions of constrained optimization. Optimality conditions of SVM. - Duality in Optimization. The dual of the SVM.
Objetivos: 1 2 3 4
Teoría
17.4h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
35h

Integer Programming

- Modelling problems with binary variables. - The branch and bound algorithm for integer programming - Gomory's cutting planes algorithm. - Minimal spanning tree problem and algorithms of Kruskal and Prim
Objetivos: 1 2 3 4
Teoría
17.3h
Problemas
0h
Laboratorio
0h
Aprendizaje dirigido
0h
Aprendizaje autónomo
35h

Metodología docente

The students will have available all the course material.

About two thirds of lecture time will be devoted to optimization algorithms and their properties, and the rest will be for presenting and solving exercises and problems

Lab sessions (using AMPL) will be devoted to the solution of some data mining applications.

Método de evaluación

- Theory (40%). There will be a short midterm exam based on practical questions for the first two parts of the course, and some individual numerical exercises for the third (and last) part.

- Practical assigments (60%). There will be 3 lab assignments, one for each part of the course, all of them with the same weight on the final mark.

Additional exercises provided during the lectures may be taken into consideration to decide or to boost the final mark.

Bibliografía

Básica:

  • Numerical Optimization - J. Nocedal and S.J. Wright., Springer, 1999.
  • Linear and Nonlinear Programming - D.G. Luenberger and Y. Ye, Springer, 2008.
  • Integer Programming - L.A. Wolsey, Wiley, 1998.
  • AMPL A modeling language for mathematical programming - . Fourer, D.M. Gay, B.W. Kernighan, Thomson Brooks/Cole, 2003.
  • An introduction to support vector machines : and other kermel-based learning methods - Cristianini, Nello; Shawe-Taylor, John, Cambridge University Press, 2000. ISBN: 0521780195
    http://cataleg.upc.edu/record=b1165003~S1*cat

Web links

Capacidades previas

Basic background in linear algebra, calculus, and programming languages is needed for the course.