# Clustering Objects Described by Juxtaposition of Binary Data Tables

Authors: Amar Rebbouh
Journal: Journal of Applied Mathematics and Decision Sciences
 (2008)

---

## Abstract

This paper seeks to develop an allocation of 0/1 data matrices to physical
systems upon a Kullback-Leibler distance between probability distributions.
The distributions are estimated from the contents of the data matrices. We
discuss an ascending hierarchical classification method, a numerical example and
mention an application with survey data concerning the level of development of
the departments of a given territory of a country.


---

## Body

## 1. Introduction

The automatic
classification of the components of a structure of multiple tables remains a
vast field of research and investigation. The components are matrix objects,
and the difficulty lies in the definition and the delicate choice of an index
of distance between these objects (see Lerman and Tallur [1]). If the matrix objects are
tables of measurements of the same dimension, we introduced in Rebbouh [2] an index of distance based on the inner product of
Hilbert Schmidt and built a classification algorithm of k-means type. In this
paper, we are interested by the case when matrix objects are tables gathering the
description of the individuals by nominal variables. These objects are
transformed into complete disjunctive tables containing 0/1 data (see Agresti
[3]). It is thus a
particular structure of multiple data tables frequently encountered in practice
each time one is led to carry out several observations on the individuals whom
one wishes to classify (see [4, 5]). We quote for example
the case when we wish to classify administrative departments according
to indices measuring the level of economic idE and human development idH which are weighted averages
calculated starting from measurements of selected parameters. Each department i gathers a number Li of subregions classified as rural or urban.
Each department is thus described by a
matrix with 2 columns and Li lines of positive numbers ranging between 0 and 1.
But the fact that the values of the
indices do not have the same sense according to the geographical position of
the subregion, and its urban or rural specificity led the specialists to be
interested in the membership of the
subregion to quintile intervals. Thus, each department will be described by a
matrix object with 10 columns and Li lines. This matrix object is thus a juxtaposition
of 2 tables of the same dimension containing only
one 1 on each line which corresponds to the class
where the subregion is affected and the remainder are 0.
The use of conventional statistical techniques to analyze this kind of data
requires a reduction step. Several criteria of good reduction exist. The
criterion that gives results easily usable and interpretable is undoubtedly the
least squares criterion (see, e.g., [6]). These summarize each table of data describing each
object for each variable in a vector or in subspace. Several mathematical
problems arise at this stage:(1)
the choice of the value which summarizes the
various observations of the individual for each variable, do we take the most
frequent value or another value, for example an interval [7]; why this choice? and which
links exist between variables,(2)
the second problem concerns the use ofhomogeneity
analysis or multiple correspondence analysis (MCA) to reduce the
data tables. We make an MCA for each of the n data tables describing, respectively, the n individuals. We get n factorial axis systems. To compare elements of
the structure, we must seek a common system or compromise system of the n ones. This issue concerns other mathematical
discipline such as differential geometry (see [8]). The proposed criteria for the choice of the common
space are hardly justified (see Bouroche [9]). This problem is not
fully resolved,(3)
the problem of the number of observations that
may vary from one individual to another. We can use the following procedure to
complete the tables. We assume thatLi>1, for all i=1,…,n, Li is the number of observation of the individual ωi and define L as the least common multiple of Li. Hence, there exists ri such that L=Li×ri.
Now, we duplicate each table T,
ri times, we
obtain a new table Ti∗ of dimension L×d, d is the number of variables. But if Li is large, the least common multiple becomes
large itself, and the procedure leads to the structure of large tables.
Moreover, this completion removes any chronological appearance of data. This
cannot be a good process of completion, and it seems more reasonable to carry
out the classification without the process of completion.To overcome all these difficulties with the proposed
solutions which are not rigorously justified, we introduce a formalism borrowed
from the theory of signal and communication see (Shannon [10]) and which is used to
classify the elements of the data structure [11]. Our approach is based on simple statistical tools and
on techniques used in information theory (physical system, entropy, conditional
entropy, etc.) and requires the introduction of the concept of discrete
physical systems as models for the observations of each individual for the
variables which describe them. If we consider that an observation is a
realization of a random vector, it appears reasonable to consider that each
value of the variable or the random vector represents a state of the system
which can be characterized by its frequency or its probability. If the variable
is discrete, the number of states is finite, each state will be measured by its
frequency or its probability. This approach gives a new version and in the same time an explanation of the
distance introduced by Kullback [12]. This index makes it possible to build an indexed
hierarchy on the elements of the structure and can be used if the matrix objects
do not have the same dimension.In Section2,
we introduce an adapted formalism and the notion of physical random system as a
model of description of the objects. We define in Section 3 a distance between the elements of the
structure. The numerical example and an application are presented in Section 4.
Concluding remarks are made in Section  5.


## 2. Adapted Formalism

LetΩ={ω1,…,ωn} be a finite set of n elementary objects, {V1,…,Vd} be d discrete variables defined over Ω and taking a finite number of values in D1,…,Dd,
respectively, Dj={m1j,…,mrjj} and mtj is the tth modality or value taken by Vj. We suppose that the observations of the
individual ωi for the variable Vj are given in the table (2.1)Eij=[Vj(1)Vj(2)⋮Vj(l)⋮Vj(Li)]Vj,l=1,…,Li, and Li represents the number of the observations of
the individual ωi, Vj(l)=mtj if the lth observation of the individual ωi for the the variable Vj is mtj where t=1,…,rj. Eij is the vector with Li components corresponding to the different
observations of ωi for Vj.The structure of a juxtaposition of categorical data
tables is(2.2)E=[E1,…,En]withEi=[Ei1,…,Eid],Ei is a matrix of order Li×d.
For the sake of simplicity, we transform each vector Eij in a 0/1 data matrix Δij:(2.3)Δij=m1jm2j⋯mtj⋯mrjj12⋮l⋮Li[01⋯0⋯010⋯0⋯0⋮⋮⋮⋮⋯(Zij)lt⋯⋮⋮⋮00⋯0⋯1],(Zij)lt={1,ifatthelthobservationωitakesthemodalitymtj,0,otherwise.The structure of a juxtaposition of0/1 data tables is(2.4)Δ=[Δ1,…,Δn]withΔi=[Δi1,…,Δid],Δi is a matrix of order L×M where M=∑j=1drj.pitj=Pr(Vj=mtj) is estimated by the relative frequency of
the value 1 observed in the tth column of the matrix Δij.LetSij be the random single physical system associated
to ωi for Vj:(2.5)Sij=⋀t=1r{(S)⇝mtj;Pr[(S)⇝mtj]=pitj},where the symbol (S)⇝mt means that the system lies in the state mt,
and ⋀ is the conjunction between events.In the multidimensional case, the associated multiple
random physical systemS is (2.6)S=⋀l1=1r1…⋀ld=1rd{(S)⇝(ml11,…,mldd);Pr[(S)⇝(ml11,…,mldd)=pl1,…,ld]},
where(2.7)∑l1=1r1…∑ld=1rdpl1,…,ld=1. The multiple random physical system associated to the
marginal distributions is(2.8)S^=⋀dj=1Sj, where ⋀ is the conjunction between single physical
systems, and {Sj,j=1,…,d} are the single random physical systems given
by(2.9)∀j=1,…,d;Sj=⋀t=1rj[(S)⇝mtj;Pr[(S)⇝mtj]=ptj],(2.10)plj=Pr[(S)⇝mlj]=∑l1=1r1⋯∑lj−1=1rj−1∑lj+1=1rj+1⋯∑ld=1rdpl1,…,ld.


## 3. Distance between Multiple Random Physical Systems

## 3.1. Entropy as a Measure of Uncertainty of States of a Physical System

For measuring the degree of uncertainty of states of a
physical system or a discrete random variable, we use the entropy which is a
special characteristic and is widely used in information theory.


## 3.1.1. Shannon's [10] Formula for the Entropy

The entropy of the system is the positive quantity:(3.1)H(S)=−∑t=1rptlog2(pt).The functionH has some elementary properties which justify
its use as a characteristic for measuring the uncertainty of a system.(1)
If one of the states is certain(∃l∈{1,…,r} such that pt=Pr[(S)⇝mt]=1),
then H(S)=0.(2)
The entropy of a physical system with a finite
number of states(m1,…,mr) is maximal if all its states are equiprobable: for all t∈{1,…,r};pt=Pr[(S)⇝mt]=1/r.
We have also 0≤H(S)≤log2(r).The characteristic of the entropy function expresses
the fact that probability distribution with the maximum of entropy is the more
biased and the more consistent with the information specified by the
constraints [10].


## 3.2. Entropy of a Multiple Random Physical System

LetS be a multiple
random physical system given by (2.6).
If the single physical systems (Sj;j=1,…,d) given by (2.9) are independent, then
(3.2)H(S)=∑j=1dH(Sj).The conditional random physical systemS1/[(S2)⇝ml2] is given by(3.3)S1/[(S2)⇝ml2]=⋀j=1r1[(S1)⇝mj1/(S2)⇝ml2;Pr[(S1)⇝mj1/(S2)⇝ml2]=pj/l],where pj/l is a conditional probability.The entropy of this system is(3.4)H(S1/[(S2)⇝ml2])=−∑j=1r1pj/llog2(pj/l).The multiple random physical system(S1/S2) is written by(3.5)(S1/S2)=⋀l=1r2[⋀t=1r1[(S1)⇝mt1/(S2)⇝ml2;Pr[(S1)⇝mt1/(S2)⇝ml2]=pt/l]],
which
implies(3.6)H(S1/S2)=−∑l=1r2[∑j=1r1pj/llog2(pj/l)].
Hence,(3.7)H(S)=H(S1)+H(S2/S1)+H(S3/S1⋀S2)+⋯+H(Sd/S1⋀S2⋀⋯⋀Sd−1).
The quantity(3.8)K(P,Q)=−∑i=1rpilog2(qi/pi)
is nonnegative. We have
(3.9)K(P,Q)=K(Q,P)⟺P=Q⁢almostsurely.It is clear thatK(⋅,⋅) is not a symmetric function, thus it is not a
distance in the classical sense but characterizes (from a statistical point of
view) the deviation between the distributions P and Q.
It should be noted that K(P,Q)+K(Q,P) is symmetrical.Kullback [12] explains that the quantity K(P,Q) evaluates the average lost information if we
use the distribution P while the actual distribution is Q.LetSΠd be a set of random physical systems with ∏j=1drj states(3.10)S∈SΠd⟹S=⋀r1l1=1⋯⋀ld=1rd[(S)⇝(ml1,…,mldi);pl1⋯ld].Let dist be the application defined by(3.11)dist:SΠd×SΠd⟶ℝ+[(S1),(S2)]⟶dist(S1,S2)=[Kd(P1,P2)+Kd(P2,P1)]−[H(S1)+H(S2)].P1 and P2 are the multivariate distributions of order d governing, respectively, the random physical
systems S1 and S2. Kd is defined as follows:
(3.12)Kd(P1,P2)=−∑I1r1⋯∑IdrdpI1⋯Id(1)log2(pI1⋯Id(2)).
dist verifies (1)
dist(S1,S2)≥0,(2)
dist(S1,S2)=0⇔S1=S2,(3)
dist(S1,S2)=dist(S2,S1)(symmetry).We admit thatdist(S1,S2)=0⇔S1=S2⇔ω1=ω2.dist measures the similarity between physical
systems. The smaller the value of dist is, the larger the uncertainty of the systems
is. dist represents the lost quantity of average
information if we use the distributionP1 (P2) to manage the system while the other
distribution is true. dist is nothing else than the Kullback-Leibler
distance between the multivariate distributions P1 and P2. Indeed, the Kullback-Leibler distance between P1 and P2 is given by
(3.13)Ku(P1,P2)=∑I1r1⋯∑Idrd(pI1⋯Id(1)−pI1⋯Id(2))log2(pI1⋯Id(1)/pI1⋯Id(2)).Developing this expression will give dist.


## 4. Numerical Application

## 4.1. Procedure to Estimate the Joint Distribution

In the case where all variables involved in the
description of the individuals are discrete, we give a procedure taken from
classical techniques of factor analysis to estimate the joint distribution and
derive the entropy of the multiple physical system.LetΔi=[Δi1,…,Δid] be a juxtaposition of d0/1 data tables. For ωi∈Ω fixed, we have
(4.1)pl1⋯ld(i)=Pr[(S)⇝(ml11,…,mldd)]=1LiN(i)(l1,…,ld).N(i)(⋅) is the number of simultaneous occurrences of
the modalities ml11,…,mldd:
(4.2)∑l1=1r1⋯∑ld=1rdpl1⋯ld(i)=1.


## 4.2. Algorithm

We use an algorithm for ascending hierarchical
classification [13]. We
call points either the objects to be classified or the clusters of objects
generated by the algorithm.Step 1.
There aren points to classify (which are the n objects).Step 2.
We find the two pointsx and y that are closest to one another according to
distance dist and clustered in a new artificial point h.Step 3.
We calculate the distances between the new
point and the remaining points using the single linkage of Sneath and Sokal [14] D defined by(4.3)D(ω,h)=Min{dist(ω,x),dist(ω,y)},ω≠x,y.
We return to Step1 with only (n−1) points to classify.Step 4.
We again find the two closest points and
aggregate them. We calculate the new distances and repeat the process until
there is only one point remaining.In the case of single linkage, the algorithm uses
distances in terms of the inequalities between them.


## 4.3. Numerical Example

Consider 6 individuals described by 2 qualitative variables with, respectively, 2 and 3 modalities. 10 observations for each individual, the observations are grouped in Table1.Table 1
Juxtaposition
of the disjunctive data tables describing the 6 objects.
ω1ω2ω3V1V2V1V2V1V2m11m21m12m22m32m11m21m12m22m32m11m21m12m22m32101001001010100010010100101001100100110010010011000110001010011001001001100100010110010001010100100110100100101001001010100100101001100101001000110010ω4ω5ω6V1V2V1V2V1V2m11m21m12m22m32m11m21m12m22m32m11m21m12m22m32101001001010100010100110010001100011000101010011001001010100010100101001001100101001001001100100100101100100011001010100010011001010010101001010010100


## 4.3.1. Procedure to Build a Hierarchy on these Objects

The empirical distributions which represent the
individuals are given by Table2.Table 2(m11,m12)(m11,m22)(m11,m32)(m21,m12)(m21,m22)(m21,m32)F10.20.30.10.20.10.1F20.10.20.10.30.10.1F30.20.20.10.20.20.1F40.20.20.20.10.20.1F50.10.40.20.10.10.1F60.40.10.10.10.10.1The program is carried out on this numerical example.
We obtain the following results (Table3).Table 3
Entropy of
the conditional random physical systems associated to the 6 objects.
S1S2S3S4S5S6S12,44642,60492,52192,62192,62192,8219S22,60492,44642,62192,82192,82192,9219S32,60492,70492,52192,62192,82192,8219S42,70492,86342,62192,52192,72192,8219S52,48792,66342,62192,52192,32193,0219S62,66342,86342,62192,62193,02192,3219Step 1.
From the similarity matrix, using the single
linkage of Sneath (4.3), we obtain(4.4)minl≠t;l,t=1,…,5{dist(Sl,St)}=dist(S1,S3)=0,1585.Then, the objects ω1 and ω3 are aggregated into the artificial object ω7 which is placed at the last line, and the rows
and columns corresponding to the objects ω1 and ω3 are removed in the similarity matrix.Step 2.
From the new similarity matrix, we
obtain(4.5)minl≠t;l,t=2,4,5,6{dist(Sl,St)}=dist(S2,S7)=0,317.The objects ω2 and ω7 are aggregated into the artificial object ω8.Step 3.
(4.6)minl≠t;l,t=4,5,6{dist(Sl,St)}=dist(S4,S8)=1,268.
The objects ω4 and ω8 are aggregated into the artificial object ω9.Step 4.
(4.7)minl≠t;l,t=5,6,9{dist(Sl,St)}=dist(S5,S9)=2,732.
The objects ω5 and ω9 are clustered in the new object ω10. The object ω6 is aggregated with the object ω10 and dist(S6,S10)=4,8.
(see Figure 1)Figure 1
Dendogram
of the produced hierarchy.In Figure1 it can be seen that two separated classes appear in
the graph by simply cutting the hierarchy on the landing above the individual ω2.
In this algorithm, we started by incorporating the two closest objects using
the index of distance between corresponding physical systems. The higher the
construction of the hierarchy is, the more dubious
the obtained states of the mixed system are. The example shows that the index
of Kullback-Leibler and the index of aggregation of the minimum bound (single
linkage) lead to the construction of a system with a maximum of entropy, and
thus lead to a system for which all the states are equiprobable.If the total number of modalities of the various
criteria is large compared with the number of observations, the frequency of
choosing a set of modalities becomes small, and a lot of frequencies are zero.
The set of modalities whose frequency is zero will be disregarded and does not
intervene in the calculation of the distances. This can lead to the
impossibility of comparing the systems.


## 4.3.2. Classification of the Six Objects after Reduction

If each object is described by the highest frequencies
“mode,” we obtain the following table:(4.8)ω1ω2ω3ω4ω5ω6[m11m22m21m32m11m12m11m12m11m22m11m22].V1V2This table contradicts the fact that in our procedure,
the objectsω1 and ω2 are very close while ω1 and ω5 are not the same. This shows that the
classification after reduction, for this type of data, can lead to
contradictory results.


## 4.4. Application

The data come from a survey concerning the level of
development ofn departments E1,E2,…,En of a country. The aim is to search the less
developed subregions in order to establish programs of adequate development.
Every department Ei is constituted of Li subregions C1i,C2i,…,CLii.
For every i=1,…,n and l=1,…,Li,
we measured the composite economic development index idE and the composite human development index idH. These two composite indices are weighted means
of variables measuring the degree of economic and human development, developed
by experts of the program of development of the United Nations for ranking
countries. These indices depend on the geographical situation and on the
specificity of the subregions.For everyi=1,…,n,l=1,…,Li,0≤idE(Cli)≤1,
and 0≤idH(Cli)≤1. The closer to 1 the value of the index is, the more the
economic or human development is judged to be satisfactory. However, these
indices are not calculated in the same manner. They depend on whether the
subregions are classified as farming or urban zone. The ordering of the
subregions according to each of the indices do not have sense anymore. The structure of data in entry is for every i=1,…,n:(4.9)Ei(Li,2)⟼idE⁢idHCi1Ci2⋮CiLi[idE(Ci1)idH(Ci1)idE(Ci2)idH(Ci2)⋮⋮idE(CiLi)idH(CiLi)].The structure is not exploitable in this form. It is
therefore necessary to transform the tables in a more tractable form. The
specialists of the programs of development cut the observations of each index
in quintile intervals and affect each of the subregions to the corresponding
quintile. We thus determine for then series of observations of the two indices the
various corresponding quintiles:(4.10)idE⟶qi11,qi21,…,qi51,idH⟶qi12,qi22,…,qi52.The quintile intervals
are(4.11)Ii11,Ii21,…,Ii51,Ii12,Ii22,…,Ii52.For every i=1,…,n,
the table Ei is transformed into a table of 0/1 data.The problem is to build a hierarchy on all departments
of the territory in order to observe the level of development of each of the
subregions according to the two indices and thus to make comparisons. The
observations are summarized in tablesΔ1,Δ2,…,Δn which constitute a structure of juxtaposition of 0/1 data matrices. These data presented are from a
study of 1541 municipalities involved in Algeria. The
municipalities are gathered in 48 departments. The departments do not have the
same number of municipalities which have not the same specificities: size,
rural, urban, and the municipalities
do not have the same locations: mountain, plain,
costal, and so forth. We have to build typologies
of departments according to their economic level and human development according to the United
Nations Organization standards.The result of the study made it possible to gather the
great departments (cities) which have large and old universities and the
municipalities which have a long existence. Another group emerged which
includes enough new departments of the last administrative cutting and develops
activities and services of small and middle companies. The other groups are
distinguished by great disparities between municipalities in their economic
level and human development and according to surface and importance.


## 5. Conclusion

In this paper, the definition of the entropy is that
stated by Shannon [10]. This definition is still used in the theory of
signal and information. The suggested formalism gives an explanation and a
practical use of the distance of Kullback-Leibler as an index of distance
between representative elements of a structure of tables of categorical data.
It is possible to extend these results to the case of a structure of data
tables of measurements and to adapt an algorithm of classification to the case
of functional data.



---

*Source: 125797-2009-01-14.xml*