Versión de HTML Básico
Jaime Fernández
Analítika, Revista de análisis estadístico, (2016), Vol. 11
156
3. Utilizando el procedimiento de testeo de relaciones entre nodos explicado anteriormen-
te, se define a
{
Π
l
}
L
l
=1
como la partici´on m´as gruesa de
Y
tal que para cada subconjunto
Π
l
(con
|
Π
l
| ≥
2), cualquier par de nodos en Π
l
son o bien nodos hermanos que son
nodos terminales, o tienen una relaci´on antecesor-sucesor. Notar que para alguno
l
, Π
l
podr´ıa contener un solo nodo. Empezar a construir el nuevo conjunto activo agregando
nodos en estas particiones que contienen un solo nodo, como sigue:
Y
N
←−
l
:
|
P i
l
|
=1
Π
l
4. Para cada
l
= 1
, ..., L
con
|
Π
l
| ≥
2, si Π
l
contiene un nodo predecesor
u
, actualizar
Y
N
←−
Y
N
∪ {
u
}
. De lo contrario, introducir un nuevo nodo oculto (variable latente)
h
, y luego conectar
h
(como un antecesor) a cada nodo contenido en Π
l
, y actualizar
Y
N
←−
Y
N
∪ {
h
}
.
5. Actualizar el conjunto activo:
Y
A
←−
Y
y
Y
←−
Y
N
.
6. Para cada nodo oculto
h
∈
Y
, calcular las distancias
d
hl
, para todo
l
∈
Y
, utilizando
las ecuaciones 12 y 13.
7. Si
|
Y
| ≥
3, regresar al paso 2. Caso contrario, si
|
Y
|
= 2, conectar los dos nodos
restantes en
Y
con una arista y parar. Si
|
Y
|
= 1, parar.
Sean
i, j
∈
C
(
h
) dos nodos sucesores de
h
y sea
k
∈
Y
A
\{
i, j
}
cualquier otro nodo
en el conjunto activo previo. Del lema presentado anteriormente, se tiene que
d
ih
−
d
jh
=
d
ik
−
d
jk
= Φ
ijk
y
d
ih
+
d
jh
=
d
ij
.Con estos antecedentes,se puede calcular la distancia entre
un nodo previamente activo
i
∈
Y
A
y su nuevo nodo predecesor oculto
h
∈
Y
como sigue:
d
ih
=
1
2
(
d
ij
+ Φ
ijk
)
(12)
Para cualquier otro nodo activo
l
∈
Y
, se puede calcular
d
hl
utilizando un nodo sucesor
i
∈
C
(
h
) de la siguiente manera:
d
hl
=
d
il
−
d
ih
si
l
∈
Y
A
d
ik
−
d
jh
−
d
lk
si
l
∈
Y
A
(13)
Algoritmo de agrupamiento de Chow-Liu con uni´on de vecinos
El algoritmo de agrupamiento de Chow-Liu con uni´on de vecinos involucra dos etapas:
en primer lugar, se construye el ´arbol de Chow-Liu sin variables latentes (Chow y Liu, 1968),
notado
MST
(
V
;
D
), donde
D
corresponde a la matriz de distancias. En segundo lugar, se
aplica el m´etodo de uni´on de vecinos (Saitou y Nei, 1987) para reconstruir un sub´arbol
latente sobre los vecinos cerrados
11
para cada nodo interno en
MST
(
V
;
D
).
Con esta introducci´on, el algoritmo de agrupamiento de Chow-Liu con uni´on de vecinos
sigue los siguientes pasos:
11
Ver m´as detalles en Choi
et al.
(2011) P.19
46