PDF de programación - Algoritmos

Algoritmos


Jordi Gironés Roig

PID_00197284

CC-BY-NC-ND • PID_00197284

Algoritmos

Los textos e imágenes publicados en esta obra están sujetos –excepto que se indique lo contrario– a una licencia de
Reconocimiento-NoComercial-SinObraDerivada (BY-NC-ND) v.3.0 España de Creative Commons. Podéis copiarlos, distribuirlos
y transmitirlos públicamente siempre que citéis el autor y la fuente (FUOC. Fundación para la Universitat Oberta de Catalunya),
no hagáis de ellos un uso comercial y ni obra derivada. La licencia completa se puede consultar en http://creativecommons.org/
licenses/by-nc-nd/3.0/es/legalcode.es

CC-BY-NC-ND • PID_00197284

Índice

Algoritmos

1.1.


Introducción...............................................................................................

1. Creación de modelos de datos........................................................
Familias de algoritmos ................................................................
1.1.1. Definición de algoritmo ................................................
1.1.2. Clasificación supervisada ...............................................
1.1.3. Clasificación no supervisada .........................................
1.1.4. Algoritmos de aprendizaje reforzado .............................
1.2. Clasificación por vecindad. K-Nearest Neighbor ........................
1.2.1. Algoritmo K-NN .............................................................
1.3. Ganancia de información ...........................................................
1.4. Árboles de decisión .....................................................................
1.4.1. Generalidades .................................................................
1.4.2. Algoritmo C4.5 ..............................................................
1.5. Redes neuronales .........................................................................
1.6.
SVM Support Vector Machines ...................................................
1.7. Clustering aglomerativo y dendrogramas ....................................
1.7.1. Clustering y segmentación .............................................
1.7.2. Dendrogramas ................................................................
1.8. Clustering o clasificador ...............................................................
1.8.1. Algoritmo k-means ........................................................
1.8.2. Canopy clustering y map reducing.....................................
PCA Análisis de componentes principales ..................................
1.9.1. Método del análisis de componentes principales ..........
1.10. Asociaciones ................................................................................
1.10.1. Especificación de transacciones, esperanza y soporte ....
1.10.2. Algoritmo Apriori ..........................................................
1.10.3. Algoritmo MS-Apriori ....................................................
1.11. Técnicas estadísticas de regresión ...............................................

1.9.


2. Visualización de datos......................................................................

3. Anexo.....................................................................................................
3.1. Distancia o similitud ...................................................................
Estadística y álgebra ....................................................................
3.2.
3.2.1.
Estadística .......................................................................
3.2.2. Álgebra ...........................................................................


Resumen.......................................................................................................

Bibliografía.................................................................................................

5

7
7
7
7
10
11
12
12
13
16
16
17
20
26
33
33
34
35
36
38
42
43
46
46
48
52
52

57

62
62
68
68
70

72

73

CC-BY-NC-ND • PID_00197284

Introducción

5

Algoritmos

Entender esquemáticamente y también en detalle cómo funcionan algunos
de los algoritmos más habituales en BA ayudará al estudiante a utilizar herra-
mientas BA, sabiendo qué pueden dar de sí y a la vez, sabiendo cuáles son los
fundamentos científicos que hay detrás de ellas.

Veréis notación y formulación matemática. Este hecho se ha tratado con má-
xima delicadeza para que el estudiante que no está acostumbrado a la misma
no tenga problemas para obviarla y seguir el contenido didáctico sin más pro-
blemas, y a la vez, que para el estudiante que sí la domina, pueda usar esta
herramienta científica para comprender mejor los conceptos expuestos.

Trabajaremos técnicas de clasificación, segmentación, predicción, jerarquiza-
ción, asociación y visualización de datos, asimismo, en el documento “Anexo”
trabajaremos conceptos estadísticos y algebraicos que constituyen la base ma-
temática de todas estas técnicas.

Es generalmente aceptada la idea de asociar habilidades sintéticas y analíticas
a las actividades más o menos científicas como BA; sin embargo, es igualmente
importante cultivar habilidades creativas para, a veces buscar y a veces encon-
trar, patrones nuevos que nos permitan convertir datos en conocimiento.

A través del estudio de los distintos algoritmos, el estudiante observará la apor-
tación creativa de distintos científicos que han contribuido muchas veces, con
soluciones sencillas, brillantes y efectivas a problemas realmente complejos a
priori.

Al finalizar este material didáctico el estudiante será capaz de desarrollar paso
a paso los siguientes algoritmos:

• Árbol de decisión

• Análisis de componentes principales

• Asociaciones

•

Regresión

Respecto de algoritmos más complejos, el estudiante habrá adquirido un nivel
de comprensión esquematizado y general sobre su funcionamiento interno.
Estos algoritmos son:

CC-BY-NC-ND • PID_00197284

6

Algoritmos

• K-NN

•

•

Redes neuronales

Support Vector Machines

• K-Means

CC-BY-NC-ND • PID_00197284

7

Algoritmos

1. Creación de modelos de datos

Si el scoring consiste en aplicar un algoritmo a un juego de datos con el ob-
jetivo de predecir una clase objetivo o encontrar un patrón desconocido, el
modelado comprende todas las tareas directamente involucradas en el proceso
de construcción y ajuste del mencionado algoritmo.

Empecemos por buscar un origen al nombre y una definición al concepto.

1.1. Familias de algoritmos

1.1.1. Definición de algoritmo

Merece la pena comentar el origen etimológico de la palabra algoritmo, por su
conexión con los orígenes de las matemáticas modernas. La palabra proviene
del nombre Al-Khwarizmi, matemático persa que vivió entre los años 750-850.
Estrictamente significa ‘nativo de Khwarez’, actual Uzbekistán.

Su libro más reconocido es Algebra, que da nombre a esta disciplina. Sin em-
bargo, el término algoritmo trasciende en la historia gracias a otra de sus obras
traducida al latín como Algoritmi de numero Indorum, que significa ‘Algoritmi
nos habla sobre los número de la India’. Esos números que despertaron la cu-
riosidad del autor son nuestro actual sistema decimal.

Durante la época medieval, algoritmo significaba ‘sistema decimal’, nada que
ver con el concepto moderno.

“Conjunto de instrucciones bien definidas, ordenadas y finitas, que permiten realizar
una actividad mediante pasos sucesivos”.

Thomas Cormen ( 2009). Introduction to algorithms. The MIT Press.

Veamos qué tipos de algoritmos podemos encontrar en BA.

1.1.2. Clasificación supervisada

La clasificación supervisada persigue la obtención de un modelo válido para
predecir casos futuros a partir del aprendizaje de casos conocidos.

Más formalmente podríamos decirlo del siguiente modo…

CC-BY-NC-ND • PID_00197284

8

Algoritmos

A partir de un conjunto de objetos descritos por un vector de características
y del que conocemos la clase a la que pertenece cada objeto, se construye un
juego de datos llamado de entrenamiento o de aprendizaje, que nos servirá
para construir un modelo o regla general que nos va a permitir clasificar obje-
tos nuevos de los que no conocemos la clase a la que pertenecen.

Si la clase a predecir o variable de salida es discreta, diremos que se trata de
un problema de clasificación, sin embargo, si la clase a predecir es continua,
diremos que se trata de un problema de regresión.

Para los algoritmos de aprendizaje supervisado, una secuencia típica de apren-
dizaje sería la siguiente:

Figura 1. Aprendizaje supervisado

Fuente: Bing Liu. Web Data Mining

Donde vemos que a partir de un juego de datos de entrenamiento se ajusta
un modelo de aprendizaje, que acaba estableciendo un modelo, cuyo nivel de
precisión es evaluado a partir de un juego de datos de prueba, distinto al de
aprendizaje.

Una de las ventajas de este tipo de clasificación es que podemos evaluar la bon-

dad del modelo a partir del cálculo de la tasa de error =

Otra herramienta para evaluar los modelos de clasificación es la matriz de con-
fusión. Esta nos plasma en una tabla una visión gráfica de los errores cometi-
dos por el modelo.

Figura 2. Matriz de confusión

Tipos de aciertos:

a = número de clasificaciones correctas en la clase C1 = verdadero positivo.

CC-BY-NC-ND • PID_00197284

9

Algoritmos

d = número de clasificaciones correctas en la clase C2 = verdadero negativo.

Tipos de errores:

b = número de clasificaciones incorrectas. Era C2, sin embargo, se clasifica C1
= Error de tipo II o falso negativo.

c = número de clasificaciones incorrectas. Era C1, sin embargo, se clasifica C2
= Error de tipo I o falso positivo.

Proporciones:

= proporción de casos que el clasificador asigna a la clase C1 = a / (a + b).

= proporción de casos que el clasificador asigna a la clase C2 = d / (c + d).

= probabilidad a priori de la clase C1.

= probabilidad a priori de la clase C2.

Precisión￿y￿recall

Supongamos que para un cliente sabemos que hace dos temporadas el 80% de
las ventas se concentraron en 10 p