The Quantile Method for Symbolic Principal Component Analysis

I. INTRODUCTION

The generalization of the principal component analysis (PCA) is an important research theme in the symbolic data analysis $[1-4]$. The main purpose of the traditional PCA is to transform a number of possibly correlated variables into a small number of uncorrelated variables called principal components. Chouakria $[5]$ proposed the extension of the PCA to interval data as vertices principal component analysis (V-PCA). Chouakria et al. $[6]$ proposed also the centers method of PCA (C-PCA) for interval data, and they presented a comparative example for the V-PCA and the C-PCA. Lauro and Palumbo $[7]$ proposed symbolic object principal component analysis (SO-PCA) as an extended PCA to any numerical data structure. Lauro et al. $[8]$ summarize various methods of SO-PCA for interval data. The author also proposed a general "Symbolic PCA" (S-PCA) based on the quantification method by using the generalized Minkowski metrics $[9,10]$. In this approach, we first transform the given symbolic data table to a usual numerical data table, and then we execute the traditional PCA on the transformed data table.

In this article, another quantification method for symbolic data tables based on the monotone structures of objects is presented. In Section 2, first we describe the case of point sequences in a d-dimensional Euclidean space. The monotone structures are characterized by the nesting of the Cartesian join regions associated with pairs of objects. If the given point sequence is monotone in the Euclidean d space, the property is also satisfied in any feature axis. In other words, a nesting structure of the given point sequence in the d space confines the orders of points in each feature axis to be similar. Therefore, we can evaluate the degree of similarity between features based on the Kendall or the Spearman's rank correlation coefficients. Then, we can execute a traditional PCA based on the correlation matrix by the selected rank correlation coefficient. Secondly, we describe the "object splitting method" for SO-PCA for interval-valued data $[11]$. This method splits each of N symbolic objects described by d interval-valued features into the two d-dimensional vertices called the "minimum sub-object" and the "maximum sub object". We should point out the fact that any interval object can be reproduced from the minimum and the maximum sub-objects. Moreover, the nesting structure of interval objects in the d space confines the orders of the minimum and the maximum sub-objects in each feature axis to be similar. Therefore, we can evaluate again the degree of similarity between features based on the Kendall or the Spearman's rank correlation coefficients on the $(2\times N)\times d$ standard numerical data table. We can execute a traditional PCA based on the correlation matrix by the selected rank correlation coefficient. As a further extension to manipulate histogram data, nominal multi-valued data, and others, we describe the "quantile method" for S-PCA [12] in Section 4.

The problem is how to obtain a common numerical representation of objects described by mixed types of features. For example, in histogram data, the numbers of subinter vals (bins) of the given histograms are mutually different in general. Therefore, we first define the cumulative distribution function for each histogram. Then, we select a common integer number m to generate the "quantiles" for all histograms. As the result, for each histogram, we have an $(m+1)$ -tuple composed of $(m-1)$ quantiles and the minimum and the maximum values of the whole interval of the histogram. Then, we split each object into $(m+1)$ sub-objects: the minimum sub-object, $(m-1)$ quantile sub objects and the maximum sub-object. By virtue of the monotonic property of the distribution function, $(m+1)$ sub-objects of an object satisfy automatically a nesting structure. Therefore, the nesting of N objects described by the minimum and the maximum sub-objects in the d space confines the orders of $N\times (m+1)$ sub-objects in each feature axis to be similar. Again, we can evaluate the degree of similarity between features by the Kendall or the Spearman's rank correlation coefficient, and then execute a traditional PCA.

Interval-valued data may be regarded as a special histogram-valued data, where only one bin organizes the histogram. Furthermore, we can also split nominal multi-valued data into $(m+1)$ sub-objects based on the distribution function associated with rank values attached to categorical values of an object. Therefore, by the quantile method we can transform a given general $N\times d$ symbolic data table to an $\{N\times (m+1)\}\times d$ standard numerical data table, and then we can execute a traditional PCA on the transformed data table. In Section 5, we describe several experimental results in order to show the effectiveness of the quantile method. Section 6 is a summary.

II. MONOTONE STRUCTURES AND OBJECT SPLITTING METHOD

In this section, we describe some properties of monotone structures for point sequence and for interval objects. Then, we describe the object splitting method for S-PCA.

2.1. Monotone Structures for Point Sequence

Let a set of N objects U be represented by $U=\{{\omega }_1,{\omega }_2,\dots ,{\omega }_N\}$. Let each object ${\omega }_i$ be described by d numerical features, i.e. a vector ${\mathit{x}}_i=(x_{i1},x_{i2},\dots ,x_{id})$ in a d-dimensional Euclidean space $R^d$.

DEFINITION 1: Rectangular region spanned by $x_i$ and $x_j$.

Let $J({\omega }_i,{\omega }_j)$ be a rectangular region in $R^d$ spanned by the vectors $x_i$ and $x_j$, and be defined by the following Cartesian product of d closed intervals.

where $min(a,b)$ and $max(a,b)$ are the operators to take the minimum value and the maximum value from a and b, respectively.

(b) Monotone decreasing.

In the following, we call $\mathit{J}({\omega }_i,{\omega }_j)$ as the Cartesian join (region) of objects ${\omega }_i$ and ${\omega }_j[9,10,13]$.

DEFINITION 2: Nesting structure

If a series of objects ${\omega }_1$, ${\omega }_2$,..., ${\omega }_N$ satisfies the nesting property

the series is called a "nesting structure with the starting point ${\omega }_1$ and the ending point ${\omega }_N$ ".

In Fig. 1, (a) is a monotone increasing series, and (b) is a monotone decreasing series of objects. It should be noted that the two series of objects show the same nesting structures with starting point ${\omega }_1$ and ending point ${\omega }_5$.

PROPOSITION 1: If a series of objects ${\omega }_1,{\omega }_2,\dots ,{\omega }_N$ is a nesting structure with the starting point ${\omega }_1$ and the ending point ${\omega }_N$ in the space $R^d$, the series satisfies the same structure in each feature (axis) of the space $R^d$.

Proof: From the definition of rectangular region as in Eq. (1), we have

and

186 Statistical Analysis and Data Mining, Vol. 4 (2011) {"image_source":{"path":"images/41137a1fdbe4c18c3489d5c1e6ce082b9507144a96551790b192d3d3ab1ecac6.jpg"},"content":"","chart_caption":[{"type":"text","content":"(a) Monotone increasing."}],"chart_footnote":[]}

{"image_source":{"path":"images/3f16846068bb440353b1528ffa525510300bbb5ee9a0d2d9fd6cbd1c74f84747.jpg"},"content":"","chart_caption":[{"type":"text","content":"Fig. 1: Monotone structures of point sequence."}],"chart_footnote":[]}

Therefore, the relations of the Cartesian join regions $\mathit{J}({\omega }_1,{\omega }_k)\subseteq \mathit{J}({\omega }_1,{\omega }_{k+1}),k=1,2,\dots ,N-1$, in Definition 2, require the following relations for each feature, i.e. for each $j(=1,2,\dots ,d)$,

Although, there exist several ways to define the mono tone sequences of objects, i.e. monotone structures, we use the following definition.

DEFINITION 3: Monotone structure of a series of points.

A series of objects ${\omega }_1,{\omega }_2,\dots ,{\omega }_N$ is called a monotone structure, if the series satisfies the nesting structure of Definition 2.

Since, for a pair of features, we can evaluate the degree of similarity between two sets of orders of objects for the same object set $\mathbf{U}$ by using the Kendall or the Spearman's rank correlation coefficient, we have Proposition 2.

PROPOSITION 2: Correlation matrix S.

If a series of objects ${\omega }_1,{\omega }_2,\dots ,{\omega }_N$ is a monotone structure in the space $R{R}^d$, the absolute value of each off diagonal element of the $d\times d$ correlation matrix $SS$ takes the maximum value one in the sense of the Kendall or the Spearman's rank correlation coefficient.

Proof: From Definition 3, any monotone structure must satisfy the nesting property of Definition 2. Then, from Proposition 1, the given series of objects has the identical nesting structure for each feature. This property exactly restricts the order of objects for each feature to be the same way or the reverse way according to the series of objects is monotone increasing or monotone decreasing. Therefore, if a series of objects is a monotone structure in ${\mathbf{R}}^d$, the absolute value of the correlation coefficient for each pair of features takes the maximum value one in the sense of the Kendall or the Spearman's rank correlation coefficient.

From Proposition 2, if many off-diagonal elements of S take highly correlated values, we can expect the existence of a large eigenvalue of S, and that the corresponding eigenvector reproduces well the original nesting property of the set of objects in the space $R^d$.

EXAMPLE 1: As an intuitive example, suppose that the given set of objects in $R^d$ organizes an approximate monotone structure which is monotone increasing along each of d features, and the degrees of similarity between two features are the same for all possible pairs. Therefore, all off-diagonal elements of S take an identical value $\rho$, . Then, it is known [14] that d eigenvalues of S become

and the eigenvector for ${\lambda }_1$ is

Therefore, the given monotone structure of objects in $R^d$ is approximately reproduced around the eigenvector $a_1$. As a particular case, when $\rho =1$, the given set of objects organizes a complete monotone structure in the space $R^d$. Then, the eigenvalue ${\lambda }_1$ becomes d, i.e. its contribution ratio is 100%, and the order of the given object sequence in the space $R^d$ is exactly reproduced on the eigenvector $a_1$.

In the above, we characterized monotone structures by the nesting property, and obtain the correlation matrix $S$. The monotone structures include any linear structure as a special case. On the other hand, a monotone structure may be approximated well by an appropriately selected linear structure. This suggests that we can use also the Pearson correlation coefficient to evaluate the degree of similarity between two features instead of the Kendall and the Spearman's rank correlation coefficients.

2.2. Monotone Structures for Interval Objects

Let each object be described by d interval-valued features. Then, an object ${\omega }_k\in U$ becomes a hyper rectangle in $R^d$, i.e. the Cartesian product of d closed intervals:

where each interval $I_{kp}$ is given by

Then, we can define the minimum vertex ${\mathit{x}}_{k(min)}$ and the maximum vertex ${\mathit{x}}_{k(max)}$ by

DEFINITION 4: The minimum sub-object and the max imum sub-object

Let the minimum vertex ${\mathit{x}}_{k(min)}$ and the maximum vertex ${\mathit{x}}_{k(max)}$ for each object ${\omega }_k\in U$ be called the minimum sub object and the maximum sub-object, and be denoted by ${\omega }_{k(min)}$ and ${\omega }_{k(max)}$, respectively.

EXAMPLE 2: In Table 1, the minimum and the maxi mum sub-objects of Linseed oil under the first four inter val features are represented by the vertices ${\mathit{x}}_{\text{Linseed(min)}}=(0.930,-27,170,118)$ and ${\mathit{x}}_{\text{Linseed(max)}}=(0.935,-18,204,196)$, respectively.

PROPOSITION 3: From Definition 1, any interval object ${\omega }_k\in U$ is represented in the space $R^d$ by the Cartesian join region $J({\omega }_{k(min)},{\omega }_{k(max)})$.

Proof: From Eq. (1) in Definition 1 and (8–10), we see that

From Eq. (8), d respective intervals for ${\omega }_i$ and ${\omega }_j$ are

Thus the closed interval $I_{ijp}$ generated from two intervals $I_{ip}$ and $I_{jp}$ becomes

DEFINITION 5: We define the Cartesian join region $\mathit{J}({\omega }_i,{\omega }_j)$ based on Eq. (12) by

In this definition, we should note that, for each k, $\mathit{J}({\omega }_k,{\omega }_k)$ is equivalent to $\mathit{J}({\omega }_{k(min)},{\omega }_{k(max)})$. Furthermore,

$L=$ linoleic acid, $Ln=$ linolenic acid, $O=$ oleic acid, $P=$ palmitic acid, $M=$ myristic acid, $S=$ searic acid, $A=$ arachic acid, $C=$ capric acid, $Lu=$ lauric acid.

$J({\omega }_{k(min)},{\omega }_{k(min)})$ and $J({\omega }_{k(max)},{\omega }_{k(max)})$ are reduced to the minimum vertex $x_{k(min)}$ and the maximum vertex $x_{k(max)}$ in Eq. (10), respectively.

DEFINITION 6: Nesting structure for interval objects If a series of interval objects ${\omega }_1,{\omega }_2,\dots ,{\omega }_N$ satisfies the nesting property

the series is called a "nesting structure with the starting object ${\omega }_1$ and the ending object ${\omega }_N$ ".

Fig. 2 shows a series of five interval objects. It should be noted that the nesting order of objects in each feature axis is the same as that in the two-dimensional space.

PROPOSITION 4: If a series of interval objects ${\omega }_1,{\omega }_2,\dots ,{\omega }_N$ is a nesting structure with the starting object ${\omega }_1$ and the ending object ${\omega }_N$ in the space $R^d$, the series has the same nesting in each feature (axis) of the space $R^d$.

Proof: From the definition of the Cartesian join region as seen in Eq. (13), we have

{"image_source":{"path":"images/fbd73eecd40f2bc888c0a8961e9be9155655ef4de7a2b691941a2a01ce989224.jpg"},"content":"","chart_caption":[{"type":"text","content":"Fig. 2: A monotone structure of interval objects."}],"chart_footnote":[]} and

Therefore, the relations of the Cartesian join regions $\mathit{J}({\omega }_1,{\omega }_k)\subseteq \mathit{J}({\omega }_1,{\omega }_{k+1}),k=1,2,\dots ,N-1$, in Definition 5, require the following relations for each feature, i.e. for each $j(=1,2,\dots ,d)$,