Algoritmo C# para dendrograma VI (Datos)

Los datos para hacer pruebas los he sacado de un repositorio público de datos de la UCI: http://archive.ics.uci.edu/ml/ por mediación de la UOC: http://www.uoc.edu para hacer la práctica.

Descripción de los datos:
Title: Acute Inflammations

Abstract: The data was created by a medical expert as a data set to test
the expert system, which will perform the presumptive diagnosis of two
diseases of the urinary system.

----------------------------------------------------------------------------

Data Set Characteristics: Multivariate
Attribute Characteristics: Categorical, Integer
Associated Tasks: Classification
Number of Instances: 120
Number of Attributes: 6
Missing Values? No
Area: Life
Date Donated: 2009-02-11

----------------------------------------------------------------------------

Source:

Jacek Czerniak, Ph.D., Assistant Professor
Systems Research Institute
Polish Academy of Sciences
Laboratory of Intelligent Systems
ul. Newelska 6, Room 218
01-447 Warszawa, Poland
e-mail: jacek.czerniak 'at' ibspan.waw.pl or jczerniak 'at' ukw.edu.pl

----------------------------------------------------------------------------


Data Set Information:

The main idea of this data set is to prepare the algorithm of the expert
system, which will perform the presumptive diagnosis of two diseases of
urinary system. It will be the example of diagnosing of the acute
inflammations of urinary bladder and acute nephritises. For better
understanding of the problem let us consider definitions of both
diseases given by medics. Acute inflammation of urinary bladder is
characterised by sudden occurrence of pains in the abdomen region and
the urination in form of constant urine pushing, micturition pains and
sometimes lack of urine keeping. Temperature of the body is rising,
however most often not above 38C. The excreted urine is turbid and
sometimes bloody. At proper treatment, symptoms decay usually within
several days. However, there is inclination to returns. At persons with
acute inflammation of urinary bladder, we should expect that the illness
will turn into protracted form.

Acute nephritis of renal pelvis origin occurs considerably more often at
women than at men. It begins with sudden fever, which reaches, and
sometimes exceeds 40C. The fever is accompanied by shivers and one- or
both-side lumbar pains, which are sometimes very strong. Symptoms of
acute inflammation of urinary bladder appear very often. Quite not
infrequently there are nausea and vomiting and spread pains of whole
abdomen.

The data was created by a medical expert as a data set to test the
expert system, which will perform the presumptive diagnosis of two
diseases of urinary system. The basis for rules detection was Rough Sets
Theory. Each instance represents an potential patient.

The data is in an ASCII file. Attributes are separated by TAB. Each line
of the data file starts with a digit which tells the temperature of patient.

-- Attribute lines:
For example, '35,9 no no yes yes yes yes no'
Where:
'35,9' Temperature of patient
'no' Occurrence of nausea
'no' Lumbar pain
'yes' Urine pushing (continuous need for urination)
'yes' Micturition pains
'yes' Burning of urethra, itch, swelling of urethra outlet
'yes' decision: Inflammation of urinary bladder
'no' decision: Nephritis of renal pelvis origin

----------------------------------------------------------------------------

Attribute Information:

a1 Temperature of patient { 35C-42C }
a2 Occurrence of nausea { yes, no }
a3 Lumbar pain { yes, no }
a4 Urine pushing (continuous need for urination) { yes, no }
a5 Micturition pains { yes, no }
a6 Burning of urethra, itch, swelling of urethra outlet { yes, no }
d1 decision: Inflammation of urinary bladder { yes, no }
d2 decision: Nephritis of renal pelvis origin { yes, no }

----------------------------------------------------------------------------

Relevant Papers:

J.Czerniak, H.Zarzycki, Application of rough sets in the presumptive
diagnosis of urinary system diseases, Artifical Inteligence and Security
in Computing Systems, ACS'2002 9th International Conference Proceedings,
Kluwer Academic Publishers,2003, pp. 41-51

----------------------------------------------------------------------------

Citation Request:

Please cite:

J.Czerniak, H.Zarzycki, Application of rough sets in the presumptive
diagnosis of urinary system diseases, Artifical Inteligence and Security
in Computing Systems, ACS'2002 9th International Conference Proceedings,
Kluwer Academic Publishers,2003, pp. 41-51

Algoritmo C# para dendrograma V

El algoritmo por fin:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PR_IA2_2010_Clases
{
static public class Algoritmos
{
///

/// Algoritmo para el cálculo de la distancia Euclidea entre los
/// objetos a partir de los distintos atributos.
///

/// Lista de arrays de strings que representan
/// los atributos de los objetos
/// Una matriz en el intervalo [0,1] de las
/// distancias euclideas entre los objetos
static public double[,] distanciaEuclidea(List datos)
{
try
{
double[,] matriz = null;
//creamos la matriz de distancias en el intervalo [0,1]
//con la distancia media según el nº de atributos (6):
if (datos.Count>0)
{
matriz = new double[datos.Count, datos.Count];
for (int i = 0; i < datos.Count; i++)
{
for (int j= 0; j < datos.Count ; j++)
{
double suma = 0;
for (int k = 0; k < datos[i].Count() - 2; k++)
{
suma+=Math.Pow(double.Parse(datos[i][k])-double.Parse(datos[j][k]),2);
}
double result = Math.Sqrt(suma);
matriz[i, j] = 1-(result/6);
}
}
}
return matriz;
}
catch (Exception ex)
{
new Exception(ex.Message);
}
return null;
}
///

/// Algoritmo que calcula la matriz de semejanzas transitiva a partir
/// de una no transitiva.
///

/// Matriz de semejanzas no transitiva
/// Matriz de semejanzas transitiva
static public double[,] clausuraTransitiva(double[,] S)
{
try
{
double[,] R;
do
{
R = (double[,])S.Clone();
S = composicion(R, (double[,])R.Clone());
}while (!iguales(S,R));
return S;
}
catch (Exception ex)
{
new Exception(ex.Message);
}
return null;
}
///

/// composición de las semejanzas de una clausura transitiva
///

/// matriz de semejanzas
/// matriz de semejanzas
/// Una matriz de semejanzas
static private double[,] composicion(double[,] R1, double[,] R2)
{
try
{
double[,] S=new double[R1.GetLength(0),R1.GetLength(0)];
for (int x = 0; x < R1.GetLength(0); x++)
{
for (int y = 0; y < R1.GetLength(0); y++)
{
S[x,y] = 0;
for (int z = 0; z < R1.GetLength(0); z++)
{
S[x, y] = Math.Max(S[x,y], Math.Min(R1[x,z],R2[z,y]));
}
}
}
return S;
}
catch (Exception ex)
{
new Exception(ex.Message);
}
return null;
}
///

/// Determina si 2 matrices son iguales
///

///
///
///
static private bool iguales(Double[,] S, Double[,] R)
{
try
{
for (int i = 0; i < S.GetLength(0); i++)
{
for (int j = 0; j < S.GetLength(1); j++)
{
if (S[i, j] != R[i, j])
return false;
}
}
}
catch (Exception ex)
{
return false;
}
return true;
}
///

/// Crea un dendrograma a partir de una matriz de semejanzas
/// transitiva.
///

/// matriz de datos
/// Una cadena con el dendrograma
static public string dendrograma(double[,] matriz)
{
try
{
string result="";
List alfa = new List();
List emparejamientos = new List();
//añade los datos alfa de la matriz (resultados).
for (int i = 0; i < matriz.GetLength(0); i++)
{
for (int j = i; j < matriz.GetLength(1); j++)
{
if (!alfa.Contains(matriz[i,j]))
{
alfa.Add(matriz[i, j]);
}
}
}
//ordenamos los datos alfa para ver
//los objetos relacionados.
alfa.Sort();
//recorremos toda la matriz.
for (int x=alfa.Count-1;x>=0;x--)
{
for (int i = 0; i < matriz.GetLength(0); i++)
{
for (int j = i+1; j < matriz.GetLength(1); j++)
{
//Si coincide el valor de la semejanza con
//el valor alfa que estamos tratando,
//añadimos la relación a la cadena final.
if (alfa[x] == matriz[i, j])
{
string strI = "x"+ (i+1).ToString()+" ";
string strJ = "x"+ (j+1).ToString()+" ";
bool existeI = result.Contains(strI);
bool existeJ = result.Contains(strJ);
//sólo añadimos el emparejamiento si
//no existe una relación de emparejamiento
//anterior directa o derivada de otra relación
//de emparejamiento
if (!emparejamientos.Contains(strI + "," + strJ) &&
!emparejamientos.Contains(strJ+","+strI))
{
//se trabaja con 4 supuestos a continuación
//al tratar la relación entre 2 objetos:
if (!existeI && existeJ)
{
emparejamientos = anyadirEmparejamientos(emparejamientos, strI, strJ,
result.Substring(buscarLLaveAbrir(emparejamientos, result, strJ)));
if (result.IndexOf("{" + strJ) > -1)
{
result = result.Replace("{" + strJ, "{{" + strJ);
result += "," + strI + "}";
}
if (result.IndexOf(strJ + "}") > -1)
{
result = result.Insert(buscarLLaveAbrir(emparejamientos,result, strI), "{");
result += "," + strI + "}";
}
}
if (existeI && !existeJ)
{

emparejamientos = anyadirEmparejamientos(emparejamientos, strJ, strI,
result.Substring(buscarLLaveAbrir(emparejamientos,result, strI)));
result = result.Insert(buscarLLaveAbrir(emparejamientos,result, strI), "{");
result += "," + strJ + "}";
}
if (existeI && existeJ)
{
if (result.IndexOf(strI) > result.IndexOf(strJ))
{
emparejamientos = anyadirEmparejamientos(emparejamientos, strI, strJ,
result.Substring(buscarLLaveAbrir(emparejamientos, result, strJ)));
result = result.Insert(buscarLLaveAbrir(emparejamientos, result, strJ), "{");
result = result.Insert(buscarLLaveCerrar(emparejamientos, result, strJ), "}");
result = result.Insert(buscarLLaveAbriryCierreParaComa(emparejamientos, result, strJ) + 1, ",");
}
else
{
emparejamientos = anyadirEmparejamientos(emparejamientos, strI, strJ,
result.Substring(buscarLLaveAbrir(emparejamientos,result, strI)));
result = result.Insert(buscarLLaveAbrir(emparejamientos, result, strI), "{");
result = result.Insert(buscarLLaveCerrar(emparejamientos, result, strI), "}");
result = result.Insert(buscarLLaveAbriryCierreParaComa(emparejamientos, result, strI) + 1, ",");
}
}
if (!existeI && !existeJ)
{
emparejamientos.Add(strI + "," + strJ);
result += ("{" + strI + "," + strJ + "}");
}
}
}
}
}
}
return result.Replace(" ","");
}
catch (Exception ex)
{
new Exception(ex.Message);
}
return "";
}
///

/// Crea una lista de emparejamientos para no duplicar
/// los emparejamientos en el dendrograma final.
///

/// Lista de emparejamientos
/// nuevo objeto
/// objeto existente
/// cadena que engloba los objetos que se emparejan
/// con todos los objetos que se relacionan con ellos
/// Devuelve la lista de emparejamientos
static private List anyadirEmparejamientos(List emparejamientos,string nuevo, string J,
string trozo)
{
try
{
char[] caracteresDelimitadores = { '{','}',',' };
string[] filas;
filas = trozo.Split(caracteresDelimitadores, StringSplitOptions.RemoveEmptyEntries);
//mediante una array añado todos los objetos relacionados
//a lista de emparejamientos.
for (int i = 0; i < filas.Count(); i++)
{
if (!emparejamientos.Contains(nuevo+','+filas[i])
&& nuevo!=filas[i])
{
emparejamientos.Add(nuevo + ',' + filas[i]);
}
for (int j = 0; j < filas.Count(); j++)
{
if (!emparejamientos.Contains(filas[i] + ',' + filas[j])
&& !emparejamientos.Contains(filas[j] + ',' + filas[i]) &&
filas[i]!=filas[j])
{
emparejamientos.Add(filas[i] + ',' + filas[j]);
}
}
}
return emparejamientos;
}
catch (Exception ex)
{
new Exception(ex.Message);
}
return null;
}
///

/// Busca la llave de abrir para hacer un emparejamiento
///

/// Lista de emparejamientos
/// dendrograma final
/// Objeto a buscar
/// La posición de la primera llave para el
/// emparejamiento
static private int buscarLLaveAbrir(List emparejamientos,string result, string I)
{
try
{
int min = result.Length;
var lista= from e in emparejamientos
where e.IndexOf(I)>-1
select e;
//dentro de todos los emparejamientos de un objeto, obten-
//dremos el que esté en el lado más izquierdo del dendrograma
foreach (string str in lista)
{
if (result.IndexOf(str.Substring(0, str.IndexOf(","))) < min &&
result.IndexOf(str.Substring(0, str.IndexOf(","))) > -1)
min = result.IndexOf(str.Substring(0, str.IndexOf(",")));
if (result.IndexOf(str.Substring(str.IndexOf(","))) < min &&
result.IndexOf(str.Substring(str.IndexOf(","))) > -1)
min = result.IndexOf(str.Substring(str.IndexOf(","))) - str.Substring(0, str.IndexOf(",")).Length;
}
return min;
}
catch (Exception ex)
{
new Exception(ex.Message);
}
return 0;
}
///

/// Busca la llave de cerrar para hacer un emparejamiento
///

/// Lista de emparejamientos
/// dendrograma final
/// Objeto a buscar
/// La posición de la última llave para el
/// emparejamiento
static private int buscarLLaveCerrar(List emparejamientos, string result, string I)
{
try
{
int max =0;
var lista = from e in emparejamientos
where e.IndexOf(I) > -1
select e;
//dentro de todos los emparejamientos de un objeto, obten-
//dremos el que esté en el lado más derecho del dendrograma
foreach (string str in lista)
{
if (result.IndexOf(str.Substring(0,str.IndexOf(","))) > max)
max = result.IndexOf(str.Substring(0, str.IndexOf(","))) + str.Substring(0, str.IndexOf(",")).Length;
if (result.IndexOf(str.Substring(str.IndexOf(",")+1)) > max)
max = result.IndexOf(str.Substring(str.IndexOf(",") + 1)) + str.Substring(0, str.IndexOf(",")).Length;
}
return max;
}
catch (Exception ex)
{
new Exception(ex.Message);
}
return 0;
}
///

/// Dentro de cada emparejamiento, busca la posición intermedia de la
/// relación para insertar la coma de separación que deja el dendrograma
/// más claro de entender.
///

/// Lista de emparejamientos
/// dendrograma final
/// Objeto a buscar
/// La posición intermedia del emparejamiento
static private int buscarLLaveAbriryCierreParaComa(List emparejamientos, string result, string I)
{
try
{
int min = buscarLLaveAbrir(emparejamientos,result,I);
int numLlaveAbrir=1;
for (int i = min; i >= 0; i--)
{
if (result.Substring(i, 1) == "{")
numLlaveAbrir++;
else
break;
}
for (int i = min; i < result.Length; i++)
{
if (result.Substring(i, 1) == "}")
numLlaveAbrir--;
if (numLlaveAbrir == 0)
return i;
}
return min;
}
catch (Exception ex)
{
new Exception(ex.Message);
}
return 0;
}
}
}

Algoritmo C# para dendrograma IV

La parte Datos.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PR_IA2_2010_Clases
{
static public class Datos
{
///

/// Normalizamos los datos aplicando ranging a la primera
/// columna y un valor binario a las posteriores.
///

///
/// Una lista normalizada de arrays de strings
static public List Normalizar(List datos)
{
try
{
//normalizamos los datos:
if (datos != null && datos.Count > 0)
{
//sumamos la primera fila para aplicar ranging.
float maximo = float.MinValue;
float minimo = float.MaxValue;
for (int i = 0; i < datos.Count; i++)
{
float result;
if (float.TryParse(datos[i][0].Replace('.', ','), out result))
{
if (result < minimo)
minimo = result;
if (result > maximo)
maximo = result;
}
}
foreach (string[] fila in datos)
{
//ranging a la primera columna:
float result;
if (float.TryParse(fila[0].Replace('.', ','), out result))
{
fila[0] = ((result - minimo) / (maximo - minimo)).ToString();
}
for (int i = 1; i < fila.Count(); i++)
{
//comprobamos si hay valores binarios
if (fila[i].ToUpper() == "YES" || fila[i].ToUpper() == "SÍ")
{
fila[i] = "1";
}
if (fila[i].ToUpper() == "NO")
{
fila[i] = "0";
}
}
}
}
return datos;
}
catch (Exception ex)
{
new Exception(ex.Message);
}
return null;
}
}
}

Algoritmo C# para dendrograma III

Aquí la parte de código de IO.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PR_IA2_2010_Clases
{
static public class IO
{
///

/// Lectura de los datos de un fichero dado de tipo CVS que
/// transforma en una lista de arrays de tipo string.
///

/// fichero
/// Devuelve una lista de arrays de tipo string
static public List leerDatos(string fichero)
{
string texto;
string[] filas;
List datos=null;
try
{
System.IO.StreamReader sr =
new System.IO.StreamReader(fichero, System.Text.Encoding.Default, true);
texto = sr.ReadToEnd();
string[] caracteresDelimitadores = {"\r\n"};
//Creamos un lista de arrys de una forma rápida para
//tener cada dato por separado para su posterior tratamiento.
filas=texto.Split(caracteresDelimitadores,StringSplitOptions.RemoveEmptyEntries);
if (filas.Count()>0)
{
datos=new List();
for (int i = 0;i< filas.Count(); i++)
{
datos.Add(filas[i].Split(','));
}
}
sr.Close();
return datos;
}
catch (System.IO.IOException ex)
{
throw new Exception(ex.Message);
}
catch (System.Exception ex)
{
throw new Exception(ex.Message);
}
return null;
}
}
}

Algoritmo C# para dendrograma II

//El código del proceso principal para testear los algoritmos:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using PR_IA2_2010_Clases;

namespace PR_IA2_2010
{
class Program
{
static void Main(string[] args)
{
List datos;
if (args.Count() == 0)
{
//sin parámetros
Console.WriteLine("Por defecto se analiza diagnosis3.csv");
Console.WriteLine("Si quiere otro fichero debe escribir:");
Console.WriteLine("PR_IA2_2010.EXE nombre_fichero_con_datos");
datos =
IO.leerDatos("diagnosis3.csv");
}
else
{
//Si ponemos un parémetro es el nombre del fichero.
datos =
IO.leerDatos(args[0]);
}
DateTime tiempoInicio = DateTime.Now;
//normalizamos:
datos = Datos.Normalizar(datos);
//calculamos la media de las distancia euclidea entre
//los objetos
double[,] R = Algoritmos.distanciaEuclidea(datos);
//Calculamos la semejanza entre ellos
double[,] semejanza = Algoritmos.clausuraTransitiva(R);
Console.WriteLine("El resultado es: ");
//creamos el dendrograma con el resultado obtenido.
Console.WriteLine(Algoritmos.dendrograma(semejanza));
Console.WriteLine("Tiempo= " + DateTime.Now.Subtract(tiempoInicio));
Console.ReadKey();
}
}
}

Algoritmo C# para dendrograma I

He creado un algoritmo para el cálculo de dendrogramas según el método de clausura transitiva para la asignatura de Inteligencia Artificial II de la carrera de Ingeniería Informática en el Universitat Oberta de Catalunya. Como no me gusta quedármelo para mí solo y supongo que los profes no se mosquearán, aquí os escribo una serie de artículos dónde expongo una breve explicación: artículo I y los fuentes: artículos siguientes.

Tanto el algoritmo como el programa de prueba lo he realizado con C# y Framework 3.5 con el entorno de desarrollo Visual Studio 2008.

Para realizar el algoritmo y probarlo he creado 2 proyectos diferentes englobados en una solución que me permite probar , ejecutar y modificar el código.

Los proyectos son:
• PR_IA2_2010
Proyecto de inicio que usa la librería PR_IA2_2010_Clases para el cálculo del problema propuesto. Este proyecto presenta el resultado final:
o Program.cs: es el módulo principal donde se encuentra Main. Desde este módulo se llaman a los distintos algoritmos para la resolución del problema.

• y PR_IA2_2010_Clases
Conjunto de clases dónde se encuentran los algoritmos desarrollados para la resolución del problema. He creados 3 partes distintas entre sí para que la lectura del código se más clara.
o IO.cs: Tiene los métodos de lectura de los datos.
static public List leerDatos(string fichero)
Lectura de los datos de un fichero dado de tipo CVS que transforma los atributos de los objetos en una lista de arrays de tipo string
o Datos.cs: Tiene los métodos de transformación de los datos (normalización)
static public List Normalizar(List datos)
Normalización de lso datos aplicando ranging a la primera columna y un valor binario a los posteriores atributos.
o Algoritmos.cs: Algoritmos de la aplicación.
static public double[,] distanciaEuclidea(List datos)
Algoritmo para el cálculo de la distancia Euclidea entre los objetos a partir de los distintos atributos.
static public double[,] clausuraTransitiva(double[,] S)
Algoritmo que calcula la matriz de semejanzas transitiva a partir de una matriz no transitiva.
static private double[,] composicion(double[,] R1, double[,] R2)
Composición de las semejanzas de una clausura transitiva.
static private bool iguales(Double[,] S, Double[,] R)
Determina si 2 matrices de semejanzas son iguales.
static public string dendrograma(double[,] matriz)
Crea un dendrograma a partir de una matriz de semejanzas transitiva.
static private List anyadirEmparejamientos(List emparejamientos,string nuevo, string J, string trozo)
Crea una lista de emparejamientos para no duplicar los emparejamientos en el dendrograma final.
static private int buscarLLaveAbrir(List emparejamientos,string result, string I)
Busca la llave de abrir para hacer un emparejamiento.
static private int buscarLLaveCerrar(List emparejamientos, string result, string I)
Busca la llave de cerrar para hacer un emparejamiento
static private int buscarLLaveAbriryCierreParaComa(List emparejamientos, string result, string I)
Dentro de cada emparejamiento, busca la posición intermedia de la relación para insertar la coma de separación que deja el dendrograma más claro de entender.

En el próximo artículo empezaré a mostrar el código.