Ninguno

ESCOM-IPN (Sistemas Operativos II - Practica 02) Prof. Edgardo Adrián Franco Martínez Página 1 de 6

INSTITUTO POLITÉCNICO NACIONAL
ESCUELA SUPERIOR DE CÓMPUTO
Practica 02 de Sistemas Operativos II
Profr. Edgardo Adrián Franco Martínez
http://computacion.cs.cinvestav.mx/~efranco Septiembre 2010

Practica 02 “Clustering de datos con hilos bajo UNIX”
Objetivo
Construir una aplicaciónparalela basada en procesos ligeros (hilos), capaz de agrupar un conjunto cuantioso de datos de manera eficiente. Para lograrlo se deberá dominar el concepto y manejo de los llamados procesos ligeros (hilos) en UNIX, logrando con ello comprender la importancia de utilizarlos para problemas donde es necesario reducir el tiempo de cómputo significativamente, aprovechando las capacidades multinúcleo delos equipos de computo modernos.

Introducción
Un algoritmo de agrupamiento (clustering) es un procedimiento de agrupación de una serie de vectores de acuerdo con un criterio de cercanía. Esta cercanía se define en términos de una determinada función de distancia, como la euclídea, aunque existen otras más robustas o que permiten extenderla a variables discretas. Generalmente, los vectores de unmismo grupo (o clústers) comparten propiedades comunes. El conocimiento de los grupos puede permitir una descripción sintética de un conjunto de datos multidimensional complejo. De ahí el uso de algoritmos de agrupamiento en minería de datos. Esta descripción sintética se consigue sustituyendo la descripción de todos los elementos de un grupo por la de un representante característico del mismo.Existen diversas técnicas de agrupamiento. Se dividen en dos grandes categorías:   Jerárquicas, que construyen una jerarquía de grupos escindiéndolos iterativamente. De particionamiento, en los que el número de grupos se determina de antemano y las observaciones se van asignando a los grupos en función de su cercanía.

Existen diversas implementaciones de algoritmos concretos. Por ejemplo, elde las k-medias, de particionamiento. Es uno de los más antiguos pero uso extendido a pesar de sus carencias y falta de robustez.

Agrupación con k-medias
El algoritmo de k-medias en clustering es el referente principal entre los diversos métodos para seleccionar grupos representativos entre los datos. Dado un conjunto finito de patrones X, el problema de agrupamiento en X consiste en asignaretiquetas a los patrones que identifiquen subgrupos naturales en el conjunto. Debido a que los

ESCOM-IPN (Sistemas Operativos II - Practica 02) Prof. Edgardo Adrián Franco Martínez Página 2 de 6

patrones no están inicialmente etiquetados, este problema es frecuentemente conocido como aprendizaje no supervisado, con la palabra aprendizaje significando la búsqueda de etiquetas que formen“buenos” clusters. El objetivo es partir X en un cierto número K de subconjuntos naturales y homogéneos, donde los elementos de cada conjunto son tan similares como sea posible entre ellos y que, al mismo tiempo, sean lo más distintos posibles a los demás integrantes de X. El número K puede ser fijado de antemano o puede ser obtenido por medio de restricciones físicas o matemáticas. El algoritmo dek-medias es sencillo, pero muy eficiente, siempre que el número de clases se conozca a priori con exactitud. Existen una serie matrices que constituyen el fundamento para la implementación de este algoritmo. Matriz de datos de entrenamiento : Matriz de distancias ⃗⃗⃗⃗ ⃗⃗⃗⃗ ⃗⃗⃗⃗ Matriz de centros: Matriz de pertenencias ⃗⃗⃗⃗ ⃗⃗⃗⃗ ⃗⃗⃗⃗ y del conjunto de elementos de la ⃗⃗⃗⃗ ⃗⃗⃗⃗ ⃗⃗⃗⃗

Partiendo de lamatriz de datos a clasificar clase j
{⃗| ⃗ ⃗⃗⃗⃗

} el algoritmo de k-medias, realiza las siguientes operaciones.

1.- Inicialización: En el tiempo t=0, elija el número de clases K y sus respectivos centros ⃗⃗⃗⃗ . 2.- Distribución de los datos de entrenamiento: ⃗⃗⃗⃗ ⃗⃗⃗⃗ ⃗⃗⃗ 3.- Cálculo de nuevos centros: ⃗⃗⃗⃗ 4.- Verificación de convergencia: si ⃗⃗⃗⃗ ∑ ⃗⃗⃗⃗ si ⃗⃗⃗⃗ ⃗⃗⃗⃗

⃗⃗⃗⃗ con parar,...