PDF de programación - Comparación de diferentes algoritmos de clustering en la estimación de coste en el desarrollo de software

Comparación de diferentes algoritmos de clustering en la

estimación de coste en el desarrollo de software

Miguel Garre1

Juán José Cuadrado1

Miguel Ángel Sicilia1

1Dept. de Ciencias de la Computación

ETS Ingeniería Informática

Universidad de Alcalá

Ctra. Barcelona km 33.6 - 28871

Alcalá de Henares, Madrid

miguel.garre,jjcg,msicilia,@uah.es

Resumen

1.

Introducción

En el presente trabajo se aplican diferentes al-
goritmos de clustering para la estimación de
costo software. Se trata de tres tipos dife-
rentes de algoritmos de clustering: COBWEB
(clustering jerárquico), k-medias (particiona-
do), y EM (probabilístico). Cada uno de ellos
se aplica sobre los proyectos de la base de da-
tos ISBSG, realizando una segmentación de los
mismos en diferentes grupos de afinidad. Es-
ta medida de afinidad es diferente, según el
algoritmo de clustering de que se trate, obte-
niéndose por tanto diferentes segmentos según
el algoritmo que se utilice. Las medidas que
se utilizarán para comparar la bondad de los
segmentos obtenidos por cada uno de los algo-
ritmos de clustering son MMRE y PRED(.3),
ámpliamente utilizadas en la literatura sobre
el tema. De los tres algoritmos utilizados des-
taca EM como el que mejor segmentación rea-
liza, a continuación k-medias y por último
COBWEB. La razón estriba en que la forma
que tiene COBWEB de obtener los segmentos
no es la más adecuada para los datos suminis-
trados al mismo, EM y k-medias ofrecen mejo-
res resultados ya que se trata de métodos de la
misma familia, y adecuados para la naturaleza
de los datos.

El llevar a cabo un proyecto software, lleva
asociado un esfuerzo de dedicación en cuan-
to a tiempo y dinero se refiere. El poder es-
timar, preferiblemente, en las primeras etapas
de construcción de software, estos valores, ayu-
da en gran medida en la consecución del pro-
yecto. Muchos han sido, desde sus inicios en los
años 40, los proyectos software que han fraca-
sado por una mala planificación en el tiempo y
coste. Es por ello por lo que desde estos prime-
ros momentos surgieron multitud de métodos
de estimación de coste software, para ayudar
en el desarrollo de los mismos.

Tantos métodos de estimación han sido
agrupados en diferentes clasificacíones, la pri-
mera se debe a Barry Boehm [6], en la que
clasifica a los métodos de estimación de coste
software en: modelos algorítmicos, juicio de ex-
pertos, analogía, parkinson, price to win, top-
down y bottom-up. A esta clasificación le si-
gue la de DeMarco [7], la de Conte [8]: mode-
los históricos-experimentales, modelos estadís-
ticos, modelos teóricos, y modelos compuestos.
Más tarde, en 1991 Kitchenham [9], clasifica en
opinión de expertos, analogía, descomposición,
y ecuaciones de estimación, los diferentes mé-
todos de estimación. Fairley [10] en 1992 ofrece
esta otra clasificación, modelos empíricos, ba-
sados en regresión, y basados en la teoría. En
1997, Walkerden y Jeffery [11] nos ofrecen otra

clasificación, modelos empíricos paramétricos,
modelos empíricos no-paramétricos, modelos
analógicos, modelos teóricos y modelos heúrís-
ticos. Recientemente, Barry Boehm [12] ofrece
otra clasificación, actualización de la realizada
en 1981, en la cual aparecen nuevas clasifica-
ciones, en total tenemos: técnicas basadas en
modelos, técnicas basadas en expertos, orien-
tados al aprendizaje, modelos dinámicos, mo-
delos basados en técnicas de regresión, y mode-
los compuestos-bayesianos. Dentro de los mé-
todos orientadas al aprendizaje, Boehm men-
ciona las redes neuronales y el estudio de casos
(originados a partir de los modelos por analo-
gía). Por último, en el año 2001, Wieczorek [13]
clasifica los métodos de estimáción en, méto-
dos basados en modelos y métodos no-basados
en modelos, dentro de los primeros tenemos
genéricos (propietarios y no propietarios) y es-
pecíficos (conducidos por los datos y compues-
tos).

Si nos centramos en los métodos orientados
al aprendizaje, según la clasificación de 2001
de Boehm, actualmente además de las redes
neuronales y el razonamiento basado en casos
(CBR) (Shepperd [16]), se están aplicando
otras
técnicas de machine learning para
intentar mejorar el proceso de estimación,
sobre los proyectos actuales, que revisten
una gran complejidad. Tales técnicas son las
de programación genética, sistemas fuzzy,
inducción de reglas, CART (Classification and
Regression Trees) y combinaciones de éstas.
Ejemplos de ello, pueden ser los artículos de
Ali Idri, en los que aplica sistemas difusos
combinados con analogías [15, 14], o los de
Dolado en los que utiliza programación gené-
tica [17, 18] para estimar el costo software.
En el caso de inducción de reglas, C. Mair
compara esta técnica con redes neuronales
y razonamiento basado en casos en [19]. L.
Briand, ha realizado diferentes análisis y
comparativas, en las que interviene CART,
[21, 20]. Y por último mencionar el artículo de
A. Lee [22], en el que se utilizan técnicas de
clustering para el entrenamiento de una red
neuronal en la estimación de coste software.

ellos en los que se aplican técnicas de cluste-
ring para segmentar un conjunto de proyectos
software, y sobre éstos aplicar modelos mate-
máticos de estimación, cosa que hasta ahora
no se había experimentado. Estos artículos son
los de J. Cuadrado et al. [4, 5] y los de M. Ga-
rre et al. [1, 2, 3]. En estos trabajos se obtie-
nen una serie de grupos de proyectos, a partir
de la base de proyectos ISBSG versión 8 (In-
ternacional Software Benchmarking Standard
Group1), y sobre cada uno de ellos se aplica un
modelo matemático multiplicativo de la forma
e = asb, donde e es el esfuerzo estimado y s
alguna medida del tamaño del proyecto. Las
constantes a y b se obtienen mediante análisis
de regresión sobre los proyectos de cada grupo.
Los resultados obtenidos (respecto a MMRE
y PRED(.3)), como se muestra en los trabajos
anteriormente mencionados, mejoran los que
se consiguen al utilizar una única ecuación pa-
ra todos los proyectos.

Tras comprobar la bondad de estas técni-
cas en el proceso de estimación de costo sof-
tware, es necesario realizar una comparativa
de diferentes algoritmos de clustering, con la
intención de ver cúal o cúales de ellos se com-
portan de forma más efectiva para realizar di-
cha estimación. Se compararán tres de estos
algoritmos, COBWEB, k-medias y EM (utili-
zado en [4, 5, 1, 2, 3]), ofreciendo los resulta-
dos obtenidos. El resto del artículo se estruc-
tura de la siguiente forma: en la sección 2 se
realizará una definición de la metodología de
clustering, se mostrará una clasificación de los
diferentes algoritmos de clustering, así como
una descripción de los algoritmos COBWEB,
EM y k-medas. En la sección 3 se aplican estos
algoritmos a la base de datos ISBSG y se com-
paran los resultados ofrecidos por los mismos.
Finalmente en la sección 4 aparecen las con-
clusiones obtenidas a partir de la comparativa
realizada.

2. Clustering

El proceso de Clustering consiste en la división
de los datos en grupos de objetos similares. Pa-
ra medir la similaridad entre objetos se suelen

Este trabajo es continuación de una serie de

1http://www.isbsg.org/

utilizar diferentes formas de distancia: distan-
cia euclídea, de Manhatan, de Mahalanobis,
etc. El representar los datos por una serie de
clusters, conlleva la pérdida de detalles, pero
consigue la simplificación de los mismos. Clus-
tering es una técnica más de Machine Lear-
ning, en la que el aprendizaje realizado es no-
supervisado (unsupervised learning). Desde un
punto de vista práctico, el clustering juega un
papel muy importante en aplicaciones de data
mining, tales como exploración de datos cien-
tíficos, recuperación de la información y mine-
ría de texto, aplicaciones sobre bases de datos
espaciales (tales como GIS o datos proceden-
tes de astronomía), aplicaciones Web , marke-
ting, diagnóstico médico, análisis de ADN en
biología computacional, y muchas otras. En el
presente trabajo lo utilizaremos como comple-
mento a los modelos matemáticos, en la esti-
mación de coste software.

Una gran variedad de algoritmos de cluste-
ring han surgido en los últimos años, los cuales
se puden clasificar en:

• Métodos Jerárquicos

• Algoritmos Aglomerativos
• Algoritmos Divisivos

• Métodos de Particionado y Recolocación

• Clustering Probabilístico
• Métodos
medoids)

los

de

• Métodos de las k-medias
• Algoritmos Basados en Densidad

k-vecinos

(k-

◦ Clustering de Conectividad Ba-
sada en Densidad Density-Based
Connectivity Clustering

◦ Clustering basado en Funciones

de Densidad

• Métodos Basados en Rejillas
• Métodos Basados en la Co-Ocurrencia de

Datos Categóricos

• Clustering Basado en Restricciones
• Algoritmos para Datos de Grandes Di-

mensiones

• Clustering Subespacial
• Técnicas de Co-Clustering

A continuación veremos más en detalle los

que serán utilizados en este trabajo.

2.1. COBWEB
Se trata de un algoritmo de clustering jerárqui-
co. COBWEB [23], se caracteriza porque utili-
za aprendizaje incremental, esto es, realiza las
agrupaciones instancia a instancia. Durante la
ejecución del algoritmo se forma un árbol (ár-
bol de clasificación) donde las hojas represen-
tan los segmentos y el nodo raíz engloba por
completo el conjunto de datos de entrada. Al
principio, el árbol consiste en un único nodo
raíz. Las instancias se van añadiendo una a
una y el árbol se va actualizando en cada paso.
La actualización consiste en encontrar el me-
jor sitio donde incluir la nueva instancia, ope-
ración que puede necesitar de la reestructura-
ción de todo el árbol (incluyendo la generación
de un nuevo nodo anfitrión para la instancia
y/o la fusión/partición de nodos existentes) o
simplemente la inclusión de la instancia en un
nodo que ya existía. La clave para saber có-
mo y dónde se debe actualizar el árbol la pro-
porciona una medida denominada utilidad de
categoría, que mide la calidad general de una
partición de instancias en un segmento. La re-
estructuración que mayor utilidad de categoría
proporcione es la que s