Inicio 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  16 17 18 19 20 21 22 23 24 25  

 

Algoritmo de clasificación jerárquica ascendente

La construcción de un árbol que representa a una jerarquía indexada, con el algoritmo de clasificación jerárquica ascendente (CJA), es un proceso recursivo que comienza con:

a)
la lista $\{1,2,\ldots,n\}$ de enteros o símbolos con los cuales se representan los elementos de $\Omega $, y la representación por lista de los nodos de la partición en los conjuntos unitarios de $\Omega $;

b)
una matriz de disimilitudes $d$ entre los objetos de $\Omega $; y

c)
un criterio de agregación $\delta$,
y produce en cada paso una nueva partición de $\Omega $, por unión de las clases más cercanas de la partición anterior:
Paso 1
(Inicialización)
  1. $k:=0$
  2. $P_0 = \{1,2,\ldots,n\}$ es la lista de los nodos que representan a las clases de la partición inicial {{1},{2},...,{n}}.
  3. $d_0 = \begin{array}[t]{r} \{\{d(1,2),d(1,3),d(1,4), \ldots , d(1,p)\}, \\ \{d... ...\\ \ddots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \\ \{d(n-1,p)\}\} \end{array}.$

  4. $\delta$ es una función de agregación.

Paso 2
Para $k = 1$ hasta $n-1$:

  1. Se determina $(i_0,j_0)$ tal que $d(i_0,j_0) = \min\{d_{k-1}(i,j)\vert i=1,\ldots,n-k,j=i+1,\ldots,n-k+1\}$.

  2. Se crea una nueva lista de los nodos $P_k$, eliminando de $P_{k-1}$ los nodos $P_{k-1}[i_0]$ y $P_{k-1}[j_0]$ y añadiendo el nodo $\{d(i_0,j_0)+ kI,P_{k-1}[i_0], P_{k-1}[j_0]\}$.
  3. Se crea una nueva matriz de disimilitudes $d_k$, eliminando de $d_{k-1}$, las disimilitudes que corresponden a las clases eliminadas y añadiendo las disimilitudes entre la clase que viene de ser creada y las clases restantes.

 

Revista Virtual Matemática, Educación e Internet

Derechos Reservados