# Classification of the Entities Represented by Samples from Gaussian Distribution

Authors: Amar Rebbouh
Journal: Advances in Decision Sciences
 (2016)

---

## Abstract

This paper aims to cluster entities which are described by a data matrix. Under the assumption of normality of observations contained in each table, each entity is represented by samples from Gaussian distribution, that is, a number of measurements in the data matrix, the sample mean vector, and the sample covariance. We propose a new distance based on Mahalanobis’s discriminant score to measure the similarity between objects. The present study is thought to be an important and interesting topic of research not only in the quest for an adequate model of the data representation but also in the choice of the distance index between entities that would allow justifying the homogeneity of any observed classes.


---

## Body

## 1. Introduction

One of the fundamental problems in automatic classification is the development and validation of similarity indices between the objects to be classified. These indices must adapt to classify objects and allow measuring the adequacy between an object and a class of objects. If the objects to be classified are described by matrices comprising such repeated observations of individuals for the variables that describe them over a finite period of time, we present a new distance based on Mahalanobis’s discriminant score to measure the similarity between objects.Usually, for this type of data, before the classification stage, we proceed to a reduction step. We can summarize each table by a vector, or a hyperrectangle, and we can use factorial techniques to reduce each table.Therefore, these reduction techniques require assumptions that are difficult to achieve in practice. Indeed, the first type of reduction makes sense only if the mean or another central value summarizes perfectly the observations of each individuali, and this reduction does not take into account the variability of the observations. The hyperrectangles are Cartesian products of intervals. The interval estimated depends on the variability of the observations but does not consider the possible relationship between the variables. This type of reduction requires that the variables must be uncorrelated. Several distances between interval objects have been extended to distances between hyperrectangles and remain a subject of research in automatic classification. These include the distance based on city block distance [1], Hausdorff distance between hyperrectangles, Wasserstein based distance [2], and single adaptive distance [3]. Finally, the third type of reduction leads to new uncorrelated variables but poses significant mathematical problems such as the search for compromise space and the number of observations to be used for the reduction of each entry table (see [4, 5]). If the number of observations of each variable is the same for each object, the input data can be considered as a structure of data matrices (see [6]).This paper aims to cluster entities which are described by a data matrix. Under the assumption of normality of observations contained in each table, each entity is represented by samples from Gaussian distribution, that is, a number of measurements in the data matrix, the sample mean vector, and the sample covariance. We define a new distance based on Mahalanobis’s discriminant score to measure the similarity between objects. We propose an extension of thek-means algorithm to this case. The approach can be extended to cluster objects described by variable subjects with errors of measurements.In analogy to the classical squared-error criterion and thek-means algorithm, clustering is here proceeding by defining and minimizing a joint clustering (heterogeneity) criterion for a partition (with a given number k of classes) and a set of k class prototypes, that is, the sum of the class-specific sums of dissimilarities between class elements and the corresponding class prototype.The paper is organized as follows. In Section2, we present the data structure and some references. In Section 3, we introduce the index of distance between objects and the steps of the algorithm. In Section 4, we provide a numerical example and do a comparative study with the classical approach. In Section 5, we explain how the algorithm is applied to cluster the workdays according to the degree of the traffic pollution at the most important roundabout. In combination with six weather conditions parameters measured on the same days, the resulting classes are analyzed and described in terms of six meteorological characteristics. In Section 6, we draw the corresponding conclusions.


## 2. The Data Structure

LetΩ be a set of n objects described by a set of d quantitative variables V
j
;
j
=
1
,
d.V
j is a map defined by(1)
V
j
:
Ω
⟶
R
,
i
⟶
V
j
i
=
v
i
j
∈
R
,where v
i
j is the value taken by the individual i for the variable V
j.We assume that the individuali is described by the matrix T
i
;
i
=
1
,
n
(2)
i
↪
T
i
=
x
i
1
1
⋯
x
i
1
d
⋮
⋮
x
i
N
i
1
⋯
x
i
N
i
d
.
(i)
T
i, for example, represents the medical record of the patient i for d variables made in the daytime; x
i
l
j represents, in this case, the value taken by the patient i for the variable V
j.
(ii)
T
i contains in our study the value of the seven pollution parameters for the day i for the 24 hours of the day.The input data are(3)
X
=
T
1
⋯
T
n
.


## 3. Classical Approach

(i) A standardized principal component analysis on each tableT
i leads to the construction of r
i orthogonal factor axes on which we project the N
i observations of the individual i, and we obtain new uncorrelated variables which give n systems of axes (4)
Δ
u
1
i
,
…
,
Δ
u
r
i
i
;
i
=
1
,
…
,
n
.In order to compare the objects, we must be in the same reference frame. Thus the basic problem of the search of a compromise axis system is posed. This problem also concerns other disciplines of mathematics, especially in differential geometry [5]. The proposed criteria in literature, for the search of compromise space on which we project the objects to compare them in terms of proximity, are not really justified. The proposed technics are purely heuristics [7], available online for free. Relations between tables are also analyzed with Procrustes analysis and compromise factorial axes in the context of multiple factorial analysis. One important reference can be Gardner et al. [8].Finally, the conclusion regarding Bouroche’s [4] proposal is too reductive of the large domain of research so that this reference could be removed.(ii) If the matrixT
i has the same dimension N
,
d, in [6], an algorithm of k-means type is proposed based on the Hilbert-Schmidt inner product to classify these matrix objects. If T
i does not have the same dimension, we can envisage a step of completion in order to obtain a structure of juxtaposition of data tables of the same dimension.∃
i
≠
l such that N
i
≠
N
l; we can use the following procedure to complete the tables. We assume that N
i
>
1;  ∀
i
=
1
,
n
. Let N be the least common multiple of N
i:(5)
N
=
LCM
N
i
,
i
=
1
,
n
.There existsα
i so that(6)
N
=
N
i
×
α
i
.Now, by duplicatingα
i times each table T
i, we obtain a new table T
i
^ of dimension N
×
d. So, if N
i is a large number, the least common multiple becomes necessarily large and the procedure leads to a structure of large tables. Moreover, this completion removes any chronological order of the data. It seems more reasonable to carry out the classification without processing with this completion step. It seems necessary to study the case where the tables T
i do not have the same dimension and without a reduction stage. If the hypothesis of normality of the observations in each column of table T
i is verified, this matrix T
i can then be considered as regrouping a realization of the normal random vector X whose distribution parameters μ
i
,
Σ
i should be estimated. These parameters will be estimated in an empirical way from the observations in the entry tables. The aim of the present paper is therefore to present a new approach of classification based on the k-means algorithm. This approach uses a new distance index based on the Mahalanobis discrimination scores. The proposed algorithm expands to the tables of different dimensions and is validated on real data of the traffic pollution.


## 4. Proposed Approach

### 4.1. Estimating the Distribution Parametersμ
i
,
Σ
i

If thed variables are unspecified, for i
=
1
,
…
,
n, the mathematical expectations μ
i
j
;
j
=
1
,
…
,
d and the components of the estimated covariance matrix Σ
i are given by(7)
μ
i
=
μ
i
1
⋮
μ
i
d
with
μ
i
j
=
1
N
i
∑
l
=
1
N
i
x
i
l
j
,
Σ
i
j
k
=
Cov
V
i
j
,
V
i
k
=
Σ
j
k
i
=
1
N
i
-
1
∑
l
=
1
N
i
x
i
l
j
-
μ
i
j
x
i
l
k
-
μ
i
k
.These estimators are unbiased, convergent, and consistent and do not depend on the number of observations or trials.


### 4.2. Classification Algorithm

We wish to gather then individuals in K homogeneous classes. The heterogeneity of the classes is measured by a criterion of the inertia sum of the classes. This criterion is expressed by(8)
Cr
P
,
L
=
∑
k
=
1
K
∑
l
∈
P
k
j
δ
2
x
l
,
l
k
,where l
k is the prototype or the kernel of the class P
k; x
l is the observation of the individual l; and δ is an index of distance between the objects and the prototype or representative elements of the classes. This criterion expresses the adequacy between the individuals with regard to the classes where they are affected.


### 4.3. Description of Individuals

We suppose that every tableT
i groups a sample of size N
i of the Gaussian random vector of parameters μ
i
,
Σ
i. For example, in the case of data with errors of measure, the tables data groups the repeated observations about the description of the variables. These observations are the realizations of the Gaussian random vector. It is clear that these observations are not correlated and the estimated variance covariance matrix is complete and thus not singular. Each i is described by I
i
=
N
i
,
μ
i
,
Σ
i, where(i)
N
i
∈
N, where N
i is the number of observations of the individual i;
(ii)
μ
i
∈
R
d, where μ
i is the vector containing the estimated means for each variable;
(iii)
Σ
i
∈
M
d
R is the set of real symmetric positive definite matrices of order d.


### 4.4. Distance between Individuals

Leti and l be 2 individuals described, respectively, by T
i and T
l. We wish to build an index of distance which takes into account the distribution parameters. To do this, we use the notion of discriminant score. For a realization O
t
i of the individual i, the discriminant score of Mahalanobis of this observation with regard to the realizations of the individual l is given by(9)
s
c
2
O
t
i
T
l
=
μ
i
-
μ
l
Σ
i
-
1
2
,where μ
i and μ
l are the average vector of the individuals i and l, respectively. It supposes that the tth observation of the individual i is assimilate to the average vector (empirical value of the distribution of its observations), for all the realizations of the individual i:(10)
s
c
2
T
i
T
l
=
∑
i
=
1
N
i
μ
i
-
μ
l
Σ
l
-
1
2
=
N
i
×
μ
i
-
μ
l
Σ
l
-
1
2
.Similar arguments lead to(11)
s
c
2
T
l
T
i
=
∑
l
=
1
N
l
μ
i
-
μ
l
Σ
i
-
1
2
=
N
l
×
μ
i
-
μ
l
Σ
l
-
1
2
.These scores are positive quantities and perfectly express the similarity between two individuals.The mapδ is defined by(12)
N
×
R
d
×
M
d
R
×
N
×
R
d
×
M
d
R
⟶
R
,
I
1
,
I
2
⟶
δ
I
1
,
I
2
,
δ
I
1
,
I
2
=
N
1
μ
1
-
μ
2
Σ
1
-
1
2
+
N
2
μ
1
-
μ
2
Σ
2
-
1
2
N
1
+
N
2
,where δ is an index of weighted distance.Without loss of generality, we assume that all objects are observed the same number of times;N
i
=
N for all i
=
1
,
…
,
n. We assume that(1)
δ
I
1
,
I
2
=
0
⇔
i
1
=
i
2;
(2)
2
N
>
d. This hypothesis implies that the matrices Σ
1 and Σ
2 are nonsingular.


### 4.5. Criteria and Optimization Problem

LetP
K be the set of partitions with K clusters and let L
K
=
N
×
R
d
×
M
d
R
K be the set of K prototypes of the classes. For k
=
1
,
…
,
K
,
l
k
=
N
^
k
,
μ
^
k
,
Σ
^
k
. The criterion C
r writes(13)
Cr
P
,
L
=
∑
k
=
1
K
∑
i
∈
P
k
δ
2
I
i
,
l
k
=
∑
k
=
1
K
∑
i
∈
P
k
N
μ
i
-
μ
^
k
Σ
i
-
1
2
+
N
^
k
μ
i
-
μ
^
k
Σ
^
k
-
1
2
N
+
N
^
kfor P
=
P
1
,
…
,
P
K
∈
P
K and L
=
l
1
,
…
,
l
K
∈
L
K.We searchP
∗
,
L
∗ which realizes(14)
min
P
∈
P
K
L
∈
L
K
⁡
C
r
P
,
L
.The algorithms used to solve such problems are of k-means type. These algorithms are based on the definition of the function of representation g and the function of affectation f which will be used alternatively to decrease the criterion. The representation function satisfies the following procedure:(15)
g
:
P
K
⟶
L
K
,
P
=
P
1
,
…
,
P
K
⟶
g
P
=
l
1
,
…
,
l
K
,
g
must  verify
min
L
∈
L
K
⁡
C
r
P
,
L
=
Cr
P
,
g
P
.


### 4.6. Characterization of a Class of Individuals

We seek for the kernel from each of the classes generated by the algorithm. Let1
,
…
,
n
k be the n
k individuals of the class P
k and let φ be the map defined by, without loss of generality,(16)
φ
:
N
×
R
d
×
M
d
R
⟶
R
+
,
N
,
μ
,
Σ
⟶
φ
N
,
μ
,
Σ
,
φ
N
,
μ
,
Σ
=
∑
l
=
1
n
k
N
l
N
l
+
N
μ
l
-
μ
Σ
l
-
1
2
+
N
N
l
+
N
μ
l
-
μ
Σ
-
1
2
.Proposition 1.
μ
∗ and Σ
∗ which minimize φ are given by(17)
μ
∗
=
Γ
-
1
∑
l
=
1
n
k
Σ
l
-
1
μ
l
w
i
t
h
Γ
=
∑
l
=
1
n
k
Σ
l
-
1
,
Σ
=
0
,
N
∗
=
N
.Proof.
We focus on the case where, for alli
=
1
,
n, N
i
=
N.
We researchμ
∗ and Σ
∗ which minimize φ
N. We put μ
=
x,  μ
i
=
x
i, and Σ
=
S. We have(18)
φ
N
x
,
S
=
φ
x
,
S
=
∑
l
=
1
n
k
N
l
N
l
+
N
μ
l
-
x
Σ
l
-
1
2
+
N
N
l
+
N
μ
l
-
x
Σ
-
1
2
=
1
2
∑
l
=
1
n
k
μ
i
-
x
Σ
i
-
1
2
+
μ
i
-
x
S
-
1
2
if
N
l
=
N
,
min
x
′
,
S
⁡
φ
x
,
S
.
The necessary condition is written as(19)
∂
φ
∂
x
=
0
a
,
∂
φ
∂
S
=
0
b
.
(a) One has∂
φ
/
∂
x
=
0; then ∑
i
=
1
k
x
i
-
x
′
S
i
-
1
+
S
-
1
=
0
⇔
(20)
∑
i
=
1
k
x
i
-
x
′
S
i
-
1
+
∑
i
=
1
k
x
i
-
x
′
S
-
1
=
0
.We note that the first expression of φ does not depend on S. We put(21)
Φ
S
=
∑
i
=
1
k
x
i
-
x
S
-
1
2
.Then(22)
Φ
S
+
H
-
Φ
S
=
∑
i
=
1
k
x
i
-
x
′
S
+
H
-
1
x
i
-
x
-
∑
i
=
1
k
x
i
-
x
′
S
-
1
x
i
-
xand also(23)
S
+
H
-
1
=
S
I
+
S
-
1
H
-
1
=
I
+
S
-
1
H
-
1
S
-
1
.The expansion of I
+
S
-
1
H
-
1 gives(24)
I
+
S
-
1
H
-
1
=
I
-
S
-
1
H
+
⋯
⟹
S
+
H
-
1
=
I
-
S
-
1
H
+
⋯
S
-
1
⟹
Φ
S
+
H
-
Φ
S
=
∑
i
=
1
k
x
i
-
x
′
S
-
1
·
H
·
S
-
1
x
i
-
x
+
⋯
+
=
∑
i
=
1
K
S
-
1
x
i
-
x
′
H
S
x
i
-
x
+
⋯
⁡
+
=
∑
i
=
1
k
S
-
1
x
i
-
x
H
2
+
⋯
.
(b)∂
φ
/
∂
S
=
0 implies that ∑
i
=
1
k
S
-
1
x
i
-
x
H
2
=
0; then(25)
S
-
1
x
i
-
x
=
0
∀
i
⟹
S
-
1
=
0
because
x
i
≠
x
.
Finally (1) ⇔
∑
i
=
1
k
x
i
-
x
′
S
i
-
1
=
0
⇒
x
′
∑
i
=
1
k
S
i
-
1
=
∑
i
=
1
k
x
i
′
S
i
-
1
⇒
(26)
x
=
Γ
-
1
∑
i
=
1
k
S
i
-
1
x
i
,
Γ
=
∑
i
=
1
k
S
i
-
1
.Remark 2.
In the case of measuring errors on the obtained classes, characterization is not flawed and is given exactly. This seems quite natural.


#### 4.6.1. The Distance between Individual and a Class

The individuali is described by μ
i
,
Σ
i and the class C
k which contains n
k individuals is characterized by l
k
∈
R
d given by(27)
l
k
=
Γ
k
-
1
∑
i
=
1
n
k
Σ
i
-
1
μ
i
∈
R
d
,where Γ
k
=
∑
i
=
1
n
k
Σ
i
-
1. The distance between the individual i and the class C
k is given by(28)
δ
2
I
i
,
C
k
=
1
2
μ
i
-
l
k
Σ
i
-
1
2
.The affectation function is given by(29)
f
:
L
K
⟶
P
K
,
L
=
l
1
,
…
,
l
K
⟶
f
L
=
P
1
,
…
,
P
K
,
f
must  verify
min
P
∈
P
K
⁡
C
r
P
,
L
=
C
r
f
L
,
L
.The minimum is obtained by(30)
P
k
=
i
∈
Ω
such  that
δ
I
i
,
l
k
≤
δ
I
i
,
l
t
;
∀
t
≠
k
,
k
<
t
if  equality
.


#### 4.6.2. Classification Algorithm

We chooseL
0 and in all cases we alternatively use the functions f and g. The algorithm runs as follows:(31)
L
0
⟶
f
P
1
⟶
g
L
1
⟶
f
P
2
⟶
g
⋯
⟶
f
P
n
⟼
g
L
n
⟼
⋯
P
∗
⟼
g
L
∗
.The algorithm stops as soon as the partition does not change. We build two sequencesV
n and U
n.Proposition 3.
The sequenceU
n
=
C
r
P
n
,
L
n is decreasing and converges.Proof.
We haveU
n
+
1
=
C
r
P
n
+
1
,
L
n
+
1
=
C
r
P
n
+
1
,
g
P
n
+
1
≤
C
r
P
n
+
1
,
L
n by definition of g; then U
n
+
1
≤
C
r
P
n
+
1
,
L
n
=
C
r
f
L
n
,
L
n
≤
C
r
P
n
,
L
n
=
U
n by definition of f.Proposition 4.
The sequenceV
n
=
P
n
,
L
n is stationary for a given rank.Proof.
We putU
n
=
C
r
P
n
,
L
n, U
∗
=
C
r
P
∗
,
L
∗
⇒
N
ϵ exists; n
≥
N
ϵ
⇒
U
n
-
U
∗
≤
ϵ
⇒
N
ϵ exists;n
≥
N
ϵ
⇒
P
n
≃
P
∗; L
n
≃
L
∗
⇒
V
n
≃
V
∗.


## 4.1. Estimating the Distribution Parametersμ
i
,
Σ
i

If thed variables are unspecified, for i
=
1
,
…
,
n, the mathematical expectations μ
i
j
;
j
=
1
,
…
,
d and the components of the estimated covariance matrix Σ
i are given by(7)
μ
i
=
μ
i
1
⋮
μ
i
d
with
μ
i
j
=
1
N
i
∑
l
=
1
N
i
x
i
l
j
,
Σ
i
j
k
=
Cov
V
i
j
,
V
i
k
=
Σ
j
k
i
=
1
N
i
-
1
∑
l
=
1
N
i
x
i
l
j
-
μ
i
j
x
i
l
k
-
μ
i
k
.These estimators are unbiased, convergent, and consistent and do not depend on the number of observations or trials.


## 4.2. Classification Algorithm

We wish to gather then individuals in K homogeneous classes. The heterogeneity of the classes is measured by a criterion of the inertia sum of the classes. This criterion is expressed by(8)
Cr
P
,
L
=
∑
k
=
1
K
∑
l
∈
P
k
j
δ
2
x
l
,
l
k
,where l
k is the prototype or the kernel of the class P
k; x
l is the observation of the individual l; and δ is an index of distance between the objects and the prototype or representative elements of the classes. This criterion expresses the adequacy between the individuals with regard to the classes where they are affected.


## 4.3. Description of Individuals

We suppose that every tableT
i groups a sample of size N
i of the Gaussian random vector of parameters μ
i
,
Σ
i. For example, in the case of data with errors of measure, the tables data groups the repeated observations about the description of the variables. These observations are the realizations of the Gaussian random vector. It is clear that these observations are not correlated and the estimated variance covariance matrix is complete and thus not singular. Each i is described by I
i
=
N
i
,
μ
i
,
Σ
i, where(i)
N
i
∈
N, where N
i is the number of observations of the individual i;
(ii)
μ
i
∈
R
d, where μ
i is the vector containing the estimated means for each variable;
(iii)
Σ
i
∈
M
d
R is the set of real symmetric positive definite matrices of order d.


## 4.4. Distance between Individuals

Leti and l be 2 individuals described, respectively, by T
i and T
l. We wish to build an index of distance which takes into account the distribution parameters. To do this, we use the notion of discriminant score. For a realization O
t
i of the individual i, the discriminant score of Mahalanobis of this observation with regard to the realizations of the individual l is given by(9)
s
c
2
O
t
i
T
l
=
μ
i
-
μ
l
Σ
i
-
1
2
,where μ
i and μ
l are the average vector of the individuals i and l, respectively. It supposes that the tth observation of the individual i is assimilate to the average vector (empirical value of the distribution of its observations), for all the realizations of the individual i:(10)
s
c
2
T
i
T
l
=
∑
i
=
1
N
i
μ
i
-
μ
l
Σ
l
-
1
2
=
N
i
×
μ
i
-
μ
l
Σ
l
-
1
2
.Similar arguments lead to(11)
s
c
2
T
l
T
i
=
∑
l
=
1
N
l
μ
i
-
μ
l
Σ
i
-
1
2
=
N
l
×
μ
i
-
μ
l
Σ
l
-
1
2
.These scores are positive quantities and perfectly express the similarity between two individuals.The mapδ is defined by(12)
N
×
R
d
×
M
d
R
×
N
×
R
d
×
M
d
R
⟶
R
,
I
1
,
I
2
⟶
δ
I
1
,
I
2
,
δ
I
1
,
I
2
=
N
1
μ
1
-
μ
2
Σ
1
-
1
2
+
N
2
μ
1
-
μ
2
Σ
2
-
1
2
N
1
+
N
2
,where δ is an index of weighted distance.Without loss of generality, we assume that all objects are observed the same number of times;N
i
=
N for all i
=
1
,
…
,
n. We assume that(1)
δ
I
1
,
I
2
=
0
⇔
i
1
=
i
2;
(2)
2
N
>
d. This hypothesis implies that the matrices Σ
1 and Σ
2 are nonsingular.


## 4.5. Criteria and Optimization Problem

LetP
K be the set of partitions with K clusters and let L
K
=
N
×
R
d
×
M
d
R
K be the set of K prototypes of the classes. For k
=
1
,
…
,
K
,
l
k
=
N
^
k
,
μ
^
k
,
Σ
^
k
. The criterion C
r writes(13)
Cr
P
,
L
=
∑
k
=
1
K
∑
i
∈
P
k
δ
2
I
i
,
l
k
=
∑
k
=
1
K
∑
i
∈
P
k
N
μ
i
-
μ
^
k
Σ
i
-
1
2
+
N
^
k
μ
i
-
μ
^
k
Σ
^
k
-
1
2
N
+
N
^
kfor P
=
P
1
,
…
,
P
K
∈
P
K and L
=
l
1
,
…
,
l
K
∈
L
K.We searchP
∗
,
L
∗ which realizes(14)
min
P
∈
P
K
L
∈
L
K
⁡
C
r
P
,
L
.The algorithms used to solve such problems are of k-means type. These algorithms are based on the definition of the function of representation g and the function of affectation f which will be used alternatively to decrease the criterion. The representation function satisfies the following procedure:(15)
g
:
P
K
⟶
L
K
,
P
=
P
1
,
…
,
P
K
⟶
g
P
=
l
1
,
…
,
l
K
,
g
must  verify
min
L
∈
L
K
⁡
C
r
P
,
L
=
Cr
P
,
g
P
.


## 4.6. Characterization of a Class of Individuals

We seek for the kernel from each of the classes generated by the algorithm. Let1
,
…
,
n
k be the n
k individuals of the class P
k and let φ be the map defined by, without loss of generality,(16)
φ
:
N
×
R
d
×
M
d
R
⟶
R
+
,
N
,
μ
,
Σ
⟶
φ
N
,
μ
,
Σ
,
φ
N
,
μ
,
Σ
=
∑
l
=
1
n
k
N
l
N
l
+
N
μ
l
-
μ
Σ
l
-
1
2
+
N
N
l
+
N
μ
l
-
μ
Σ
-
1
2
.Proposition 1.
μ
∗ and Σ
∗ which minimize φ are given by(17)
μ
∗
=
Γ
-
1
∑
l
=
1
n
k
Σ
l
-
1
μ
l
w
i
t
h
Γ
=
∑
l
=
1
n
k
Σ
l
-
1
,
Σ
=
0
,
N
∗
=
N
.Proof.
We focus on the case where, for alli
=
1
,
n, N
i
=
N.
We researchμ
∗ and Σ
∗ which minimize φ
N. We put μ
=
x,  μ
i
=
x
i, and Σ
=
S. We have(18)
φ
N
x
,
S
=
φ
x
,
S
=
∑
l
=
1
n
k
N
l
N
l
+
N
μ
l
-
x
Σ
l
-
1
2
+
N
N
l
+
N
μ
l
-
x
Σ
-
1
2
=
1
2
∑
l
=
1
n
k
μ
i
-
x
Σ
i
-
1
2
+
μ
i
-
x
S
-
1
2
if
N
l
=
N
,
min
x
′
,
S
⁡
φ
x
,
S
.
The necessary condition is written as(19)
∂
φ
∂
x
=
0
a
,
∂
φ
∂
S
=
0
b
.
(a) One has∂
φ
/
∂
x
=
0; then ∑
i
=
1
k
x
i
-
x
′
S
i
-
1
+
S
-
1
=
0
⇔
(20)
∑
i
=
1
k
x
i
-
x
′
S
i
-
1
+
∑
i
=
1
k
x
i
-
x
′
S
-
1
=
0
.We note that the first expression of φ does not depend on S. We put(21)
Φ
S
=
∑
i
=
1
k
x
i
-
x
S
-
1
2
.Then(22)
Φ
S
+
H
-
Φ
S
=
∑
i
=
1
k
x
i
-
x
′
S
+
H
-
1
x
i
-
x
-
∑
i
=
1
k
x
i
-
x
′
S
-
1
x
i
-
xand also(23)
S
+
H
-
1
=
S
I
+
S
-
1
H
-
1
=
I
+
S
-
1
H
-
1
S
-
1
.The expansion of I
+
S
-
1
H
-
1 gives(24)
I
+
S
-
1
H
-
1
=
I
-
S
-
1
H
+
⋯
⟹
S
+
H
-
1
=
I
-
S
-
1
H
+
⋯
S
-
1
⟹
Φ
S
+
H
-
Φ
S
=
∑
i
=
1
k
x
i
-
x
′
S
-
1
·
H
·
S
-
1
x
i
-
x
+
⋯
+
=
∑
i
=
1
K
S
-
1
x
i
-
x
′
H
S
x
i
-
x
+
⋯
⁡
+
=
∑
i
=
1
k
S
-
1
x
i
-
x
H
2
+
⋯
.
(b)∂
φ
/
∂
S
=
0 implies that ∑
i
=
1
k
S
-
1
x
i
-
x
H
2
=
0; then(25)
S
-
1
x
i
-
x
=
0
∀
i
⟹
S
-
1
=
0
because
x
i
≠
x
.
Finally (1) ⇔
∑
i
=
1
k
x
i
-
x
′
S
i
-
1
=
0
⇒
x
′
∑
i
=
1
k
S
i
-
1
=
∑
i
=
1
k
x
i
′
S
i
-
1
⇒
(26)
x
=
Γ
-
1
∑
i
=
1
k
S
i
-
1
x
i
,
Γ
=
∑
i
=
1
k
S
i
-
1
.Remark 2.
In the case of measuring errors on the obtained classes, characterization is not flawed and is given exactly. This seems quite natural.


### 4.6.1. The Distance between Individual and a Class

The individuali is described by μ
i
,
Σ
i and the class C
k which contains n
k individuals is characterized by l
k
∈
R
d given by(27)
l
k
=
Γ
k
-
1
∑
i
=
1
n
k
Σ
i
-
1
μ
i
∈
R
d
,where Γ
k
=
∑
i
=
1
n
k
Σ
i
-
1. The distance between the individual i and the class C
k is given by(28)
δ
2
I
i
,
C
k
=
1
2
μ
i
-
l
k
Σ
i
-
1
2
.The affectation function is given by(29)
f
:
L
K
⟶
P
K
,
L
=
l
1
,
…
,
l
K
⟶
f
L
=
P
1
,
…
,
P
K
,
f
must  verify
min
P
∈
P
K
⁡
C
r
P
,
L
=
C
r
f
L
,
L
.The minimum is obtained by(30)
P
k
=
i
∈
Ω
such  that
δ
I
i
,
l
k
≤
δ
I
i
,
l
t
;
∀
t
≠
k
,
k
<
t
if  equality
.


### 4.6.2. Classification Algorithm

We chooseL
0 and in all cases we alternatively use the functions f and g. The algorithm runs as follows:(31)
L
0
⟶
f
P
1
⟶
g
L
1
⟶
f
P
2
⟶
g
⋯
⟶
f
P
n
⟼
g
L
n
⟼
⋯
P
∗
⟼
g
L
∗
.The algorithm stops as soon as the partition does not change. We build two sequencesV
n and U
n.Proposition 3.
The sequenceU
n
=
C
r
P
n
,
L
n is decreasing and converges.Proof.
We haveU
n
+
1
=
C
r
P
n
+
1
,
L
n
+
1
=
C
r
P
n
+
1
,
g
P
n
+
1
≤
C
r
P
n
+
1
,
L
n by definition of g; then U
n
+
1
≤
C
r
P
n
+
1
,
L
n
=
C
r
f
L
n
,
L
n
≤
C
r
P
n
,
L
n
=
U
n by definition of f.Proposition 4.
The sequenceV
n
=
P
n
,
L
n is stationary for a given rank.Proof.
We putU
n
=
C
r
P
n
,
L
n, U
∗
=
C
r
P
∗
,
L
∗
⇒
N
ϵ exists; n
≥
N
ϵ
⇒
U
n
-
U
∗
≤
ϵ
⇒
N
ϵ exists;n
≥
N
ϵ
⇒
P
n
≃
P
∗; L
n
≃
L
∗
⇒
V
n
≃
V
∗.


## 4.6.1. The Distance between Individual and a Class

The individuali is described by μ
i
,
Σ
i and the class C
k which contains n
k individuals is characterized by l
k
∈
R
d given by(27)
l
k
=
Γ
k
-
1
∑
i
=
1
n
k
Σ
i
-
1
μ
i
∈
R
d
,where Γ
k
=
∑
i
=
1
n
k
Σ
i
-
1. The distance between the individual i and the class C
k is given by(28)
δ
2
I
i
,
C
k
=
1
2
μ
i
-
l
k
Σ
i
-
1
2
.The affectation function is given by(29)
f
:
L
K
⟶
P
K
,
L
=
l
1
,
…
,
l
K
⟶
f
L
=
P
1
,
…
,
P
K
,
f
must  verify
min
P
∈
P
K
⁡
C
r
P
,
L
=
C
r
f
L
,
L
.The minimum is obtained by(30)
P
k
=
i
∈
Ω
such  that
δ
I
i
,
l
k
≤
δ
I
i
,
l
t
;
∀
t
≠
k
,
k
<
t
if  equality
.


## 4.6.2. Classification Algorithm

We chooseL
0 and in all cases we alternatively use the functions f and g. The algorithm runs as follows:(31)
L
0
⟶
f
P
1
⟶
g
L
1
⟶
f
P
2
⟶
g
⋯
⟶
f
P
n
⟼
g
L
n
⟼
⋯
P
∗
⟼
g
L
∗
.The algorithm stops as soon as the partition does not change. We build two sequencesV
n and U
n.Proposition 3.
The sequenceU
n
=
C
r
P
n
,
L
n is decreasing and converges.Proof.
We haveU
n
+
1
=
C
r
P
n
+
1
,
L
n
+
1
=
C
r
P
n
+
1
,
g
P
n
+
1
≤
C
r
P
n
+
1
,
L
n by definition of g; then U
n
+
1
≤
C
r
P
n
+
1
,
L
n
=
C
r
f
L
n
,
L
n
≤
C
r
P
n
,
L
n
=
U
n by definition of f.Proposition 4.
The sequenceV
n
=
P
n
,
L
n is stationary for a given rank.Proof.
We putU
n
=
C
r
P
n
,
L
n, U
∗
=
C
r
P
∗
,
L
∗
⇒
N
ϵ exists; n
≥
N
ϵ
⇒
U
n
-
U
∗
≤
ϵ
⇒
N
ϵ exists;n
≥
N
ϵ
⇒
P
n
≃
P
∗; L
n
≃
L
∗
⇒
V
n
≃
V
∗.


## 5. Numerical Illustrative Example

We wish to cluster the six objects1
,
…
,
6 into 2 clusters. Each object is described by three variables V
1, V
2, and V
3. The three variables are unspecified and we assume that the condition of normality of these observations is verified. The artificial input data is as follows:Data Input
(32)
3
5
6
7
9
10
-
5
2
0
3
1
-
1
3
5
2
︸
1
⟶
T
1
2
-
1
0
3
5
11
-
2
3
4
6
7
8
︸
2
⟶
T
2
4.1
2.6
-
1
2.4
0.5
4
5
6
7
2
0.1
7
︸
3
⟶
T
3
3
3.6
4
-
1
17
0
10
3
12
13
0
11
︸
4
⟶
T
4
4
-
1
2
3
2
6
2
3
7
3
5
-
11
1
0.2
3
0.4
7
2
︸
5
⟶
T
5
2
7
2.5
-
1
3
1.5
2
5
0
1
3
1
︸
6
⟶
T
6In (32)   T
1
,
…
,
T
6 are not in the same dimension.


### 5.1. Classical Approach

Usually, we summarize observations of each individual by a central value that can be the mean. This method of data reduction can lead to erroneous results. This is shown in this numerical example.(i)
The mean value of each variable and the coordinate of final centers of clusters is obtained by using thek-means algorithm: (33)
X
=
μ
i
1
2.6
2.25
3.83
6.25
2.23
2.6
μ
i
2
4.2
3.5
3.03
5.9
2.7
3.24
μ
i
3
3.4
5.75
3.33
6.75
1.5
4.2
⟶
Ker
⁡
=
c
l
a
s
s
1
c
l
a
s
s
2
V
1
2.7
6.25
V
2
3.3
5.0
V
3
3.64
6.75
.


### 5.2. The Proposed Approach

(i)
The meansμ
i are given as follows:(34)
μ
1
μ
2
μ
3
μ
4
μ
5
μ
6
V
1
2.6
2.25
3.83
6.25
2.23
2.60
V
2
4.2
3.50
3.03
5.90
2.70
3.24
V
3
3.4
5.75
3.33
6.75
1.50
4.20
(ii)
The matrixΣ
i
-
1 is given as(35)
.
01
·
·
-
.
06
1.07
·
-
.
02
-
.
65
.
48
.
12
·
·
-
.
06
.
37
·
-
.
00
.
33
.
17
5.66
·
·
-
1.77
1.68
·
1.25
-
.
33
.
36
,
.
19
·
·
.
08
.
06
·
-
.
23
-
.
08
.
34
.
94
·
·
.
28
.
21
·
.
08
.
04
.
03
2.09
·
·
-
1.47
1.36
·
2.13
1.45
2.13
.


### 5.3. The Final Partition Obtained and the Distance between Each Object and the Prototype of the Class Where It Is Assigned in the Case of Reduction and with Proposed Approach

Distances between objects and kernel of the class in the classical approach, after reduction step, are as follows:(36)
num.ind
c
l
u
s
t
e
r
d
i
s
t
a
n
c
e
1
1
.
90305
2
1
2.16773
3
1
1.20818
4
2
.
00000
5
1
2.27794
6
1
.
58051Final partition is as follows:(37)
C
1
=
1,2
,
3,5
,
6
,
C
2
=
4
.Distances between objects and kernel of the class in the proposed approach are as follows:(38)
c
a
s
e
n
u
m
b
e
r
c
l
u
s
t
e
r
d
i
s
t
a
n
c
e
1
1
4.201
2
2
8.040
3
1
3.598
4
2
8.040
5
1
3.324
6
1
3.411Final partition is as follows:(39)
C
1
=
2,4
,
C
2
=
1,3
,
5,6
.Taking into account the variations that have resulted in errors of measurement and drop of thek-means algorithm with the weighted Mahalanobis distance it appeared that individuals 2 and 4 must be in the same class which has not been reported with the precedent procedure. In the case where the variability of observations plays an important part in the description of the individuals, the classification, made without taking into account these variabilities, leads to incorrect results compared with the reality of the data.


## 5.1. Classical Approach

Usually, we summarize observations of each individual by a central value that can be the mean. This method of data reduction can lead to erroneous results. This is shown in this numerical example.(i)
The mean value of each variable and the coordinate of final centers of clusters is obtained by using thek-means algorithm: (33)
X
=
μ
i
1
2.6
2.25
3.83
6.25
2.23
2.6
μ
i
2
4.2
3.5
3.03
5.9
2.7
3.24
μ
i
3
3.4
5.75
3.33
6.75
1.5
4.2
⟶
Ker
⁡
=
c
l
a
s
s
1
c
l
a
s
s
2
V
1
2.7
6.25
V
2
3.3
5.0
V
3
3.64
6.75
.


## 5.2. The Proposed Approach

(i)
The meansμ
i are given as follows:(34)
μ
1
μ
2
μ
3
μ
4
μ
5
μ
6
V
1
2.6
2.25
3.83
6.25
2.23
2.60
V
2
4.2
3.50
3.03
5.90
2.70
3.24
V
3
3.4
5.75
3.33
6.75
1.50
4.20
(ii)
The matrixΣ
i
-
1 is given as(35)
.
01
·
·
-
.
06
1.07
·
-
.
02
-
.
65
.
48
.
12
·
·
-
.
06
.
37
·
-
.
00
.
33
.
17
5.66
·
·
-
1.77
1.68
·
1.25
-
.
33
.
36
,
.
19
·
·
.
08
.
06
·
-
.
23
-
.
08
.
34
.
94
·
·
.
28
.
21
·
.
08
.
04
.
03
2.09
·
·
-
1.47
1.36
·
2.13
1.45
2.13
.


## 5.3. The Final Partition Obtained and the Distance between Each Object and the Prototype of the Class Where It Is Assigned in the Case of Reduction and with Proposed Approach

Distances between objects and kernel of the class in the classical approach, after reduction step, are as follows:(36)
num.ind
c
l
u
s
t
e
r
d
i
s
t
a
n
c
e
1
1
.
90305
2
1
2.16773
3
1
1.20818
4
2
.
00000
5
1
2.27794
6
1
.
58051Final partition is as follows:(37)
C
1
=
1,2
,
3,5
,
6
,
C
2
=
4
.Distances between objects and kernel of the class in the proposed approach are as follows:(38)
c
a
s
e
n
u
m
b
e
r
c
l
u
s
t
e
r
d
i
s
t
a
n
c
e
1
1
4.201
2
2
8.040
3
1
3.598
4
2
8.040
5
1
3.324
6
1
3.411Final partition is as follows:(39)
C
1
=
2,4
,
C
2
=
1,3
,
5,6
.Taking into account the variations that have resulted in errors of measurement and drop of thek-means algorithm with the weighted Mahalanobis distance it appeared that individuals 2 and 4 must be in the same class which has not been reported with the precedent procedure. In the case where the variability of observations plays an important part in the description of the individuals, the classification, made without taking into account these variabilities, leads to incorrect results compared with the reality of the data.


## 6. Application

Two files were used. The first file contains the observations of the seven parameters measuring the pollution caused by gases emitted by cars at a major intersection center of a city. The seven measured pollutants arecarbon monoxide,nitrogen monoxide,nitrogen dioxide,PM10 dust,sulfur dioxide,volatile organic compounds, andozone. These pollutants were measured each hour for each day. These observations concerned 420 days without gaps over the past three years. This file contains 420 tables of dimension 24
×
7 each. For these 420 days, we build up another file by measuring the daily average of 6 meteorological parameters:temperature,rainfall,atmospheric pressure,humidity,wind speed, andhours of sunshine. This table is of dimension 420
×
6. The interest is on the possible relationships between the variables measuring pollution and meteorological variables. We classify the days in three classes according to the degree of pollution and explained them using meteorological variables. Each day i is described by 7 curves corresponding to the 7 pollutants; the proposed algorithm, written in Matlab, brought together the 420 days in 3 classes without reduction step:class 1 “low-pollution days,”class 2 “days of average pollution,” andclass 3 “days of high pollution.” The results are convincing; the profile of each class was explained by meteorological variables.As a result of this, many questions arise, and we want to study the relationship between the pollution variable and the weather conditions variables. We also need to explain the classes in connection with the weather conditions variables and determine the profile of each class in connection with these weather conditions variables.The first approach to this study has consisted in summarizing the pollution file (420 tables of dimension24
×
7) in a table of dimension 420
×
7 by measuring the daily average for each pollutant. The variability effect of the measures is removed. We have studied the relationship between the 2 groups of variables “pollution and weather conditions.” We are not interested in this approach.The results are conclusive; the profile of each class has been explained by the weather conditions variables.Table1 shows the discriminating variables of each table. It describes the classes of pollution obtained according to the weather conditions parameters.Table 1
Classes
Temp
Rain
Bar-pres
Humd
Wind speed
Shine
Class 1
Mean
18.73
2.99
1015.55
70.82
3.47
5.79
Standard deviation
5.60
7.46
4.92
10.60
1.62
3.64
Class 2
Mean
19.25
1.32
1015.80
70.99
2.39
5.99
Standard deviation
4.79
4.33
6.30
11.50
1.04
3.55
Class 3
Mean
20.78
687⋅10−2
1016.00
67.73
1.85
7.60
Standard deviation
2.97
0.38
4.25
9.76
0.82
3.62Characterization of the pollution classes by the weather conditions parameters at the station is as follows.Class 1 is characterized by low temperatures, an important amount of rain, and strong winds with a minimum of sunshine. This corresponds to the class of weather disturbances.Class 2 is characterized by the category of days with intermediary weather conditions between the stable situation and the weather disturbances situation.Class 3 is characterized by high temperatures, light rainfalls, and a lot of sunshine. This represents the anticyclonic situation.According to Table1, we notice that the pressure is not a discriminating variable; that is, it does not help us differentiate between classes. Conversely temperature, rainfalls, humidity, wind speed, and sunshine do show the difference especially between the low-pollution class and the high-pollution class.According to Şen et al. (2006) [9], the pollution episodes in large cities are often related to high atmospheric pressure situations. The latter represent the ideal conditions for the gathering of pollutants in the air.Since nowadays we can predict the weather conditions 2 days ahead, we can therefore take action and make such recommendations as to regulate the road traffic at the roundabout cited above and prevent it from falling in the high-pollution class.


## 7. Conclusion

In several scientific disciplines and particularity in medicine, the variability of the observations plays an important part. The proposed approach permits classifying objects by taking into account variability of the observations. The approach can be extended to the classification of matrix objects even of different dimensions and to functional data and this can integrate variability in the distribution which describes the object for each variable. Thus, each object will be described by a multidimensional distribution. This extension will be developed in future work.



---

*Source: 7546963-2016-09-29.xml*