Coupled Attribute Analysis on Numerical Data

1 Introduction

Real-world data sets predominantly consist of quantitative attributes in diverse domains [Saria et al., 2011], such as finance and bioinformatics. The basic knowledge representation of numerical data is an information table [Kaytoue et al., 2011], which comprises columns designating "attributes" and rows denoting "objects". Each table cell thus stands for the value of a particular attribute for a particular object. This traditional representation scheme only describes each object by associated variables and assumes the independence of them.

Taking the fragment data of Iris (Table 1) as an example, six plant objects are characterized by four numerical attributes (i.e. "Sepal Length", "Sepal Width", "Petal Length", and "Petal Width"), and divided into three classes. For instance, the petal width of plant object u1 is 0.2cm, which does not reflect any interaction with other attributes. Based on this classical representation, many data mining techniques and machine learning tasks [Plant, 2012; Li and Liu, 2012] including clustering and classification have been performed. One of the critical parts in such applications is to study the pairwise distance between plant objects. A variety of distance metrics have been developed for numerical data, such as Euclidean and Minkowski metrics [Gan et al., 2007]. Since plant objects u4 and u6 have identical values of "Sepal.W" and "Petal.W", the normalized Euclidean distance between them is only 0.493, which is much smaller than that between u4, u3 (i.e. 0.950) and nearly half of that between u6, u5 (i.e. 0.982). It indicates that u4 and u6 stand a good chance to be clustered into the same group. However, in fact, u4 and u3 belong to "Versicolor", u6 and u5 are labeled as "Virginica".

The above instance shows that it is often problematic to analyze the numerical data by assuming all the continuous attributes are independent, while the traditional data representation schemes fail to capture the genuine couplings of attributes. In the real world, business and social applications such as investors in capital markets and members in social networking almost always see quantitative attributes coupled with each other [Cao et al., 2011]. It is very in demand from both practical and theoretical perspectives to develop effective representation method for analyzing continuous variables by considering the relationships among attributes. A conventional way to explore the interaction of continuous attributes is to measure the agreement of shapes between variables via Pearson's correlation coefficient [Gan et al., 2007]. Nevertheless, it only caters for the linear relationship between two variables. More often, numerical variables are associated with each other via nonlinear relationships, such as exponential and logarithmic functions. Our motivation is to consider both linear and nonlinear relationship functions, such couplings among variables are called global interactions or global dependency. In contrast, any method to study either the linear relationship or some specific nonlinear function only captures a local picture of the coupling relationships among variables, such as the Pearson's correlation. For Table 1, if we adopt the method in [Kalogeratos and Likas, 2012] by treating each correlation as the pairwise similarity entry, we then obtain the normalized Euclidean distance between u4 and u6 as 0.223, which is still smaller than that between u4 and u3 (i.e. 0.329) but only a little larger than that between u6 and u5 (i.e. 0.218). It means the coupling relationships are only partially revealed with limited improvement.

So based on the traditional information table, how to describe the global interactions with the least information loss? The idea of Taylor expansion inspires us that we can use a Taylor-like series to quantify the global dependency, since any analytic function can be approximated by its Taylor polynomials. Therefore, we propose to represent the global coupling relationships by Taylor-like expansion on attribute values, in which the Pearson's correlations between attributes and their extended powers (i.e. each extended attribute value is the power of the original one) play the role of function derivatives. From this perspective, the Pearson's correlation just reflects the first-order Taylor-like expansion of the global dependency; and the mutual information based attribute interdependency [Nazareth et al., 2007] is a special case, since function log can be expressed by its Taylor series. For Table 1, the distance between plant objects is then revised by explicitly capturing the intrinsic correlations between attributes and their powers. That is to say, the greater difference in "Petal.L" is expected to remedy the little differences in other attributes since they are correlated significantly.

Accordingly, this paper proposes a framework of the coupled attribute analysis on numerical data, shown in Figure 1, to address the aforementioned research issues. The key contributions are as follows:

• We consider both the intra-coupled interaction within an attribute, captured by the correlations between every attribute and its own powers; and the inter-coupled interaction among different attributes, quantified by the correlations between each attribute and the powers of others.
• A coupled representation scheme is introduced for quantitative objects to integrate the intra-coupled and intercoupled interactions with the original information table
• representation via Taylor-like expansion in a global way.
• The proposed coupled representation method is compared with the traditional representation approach by applying data structure analysis, clustering and classification, revealing that the couplings of continuous attributes are essential to the learning applications.

The paper is organized as follows. In Section 2, we briefly review the related work. Section 3 specifies the coupled interactions of numerical attributes. We formalize the coupled representation for objects in Section 4. The effectiveness of coupled representation is demonstrated in Section 5 with extensive experiments. Finally, we end this paper in Section 6.

2 RelatedWork

An increasing number of researchers point out that the independence assumption on attributes often leads to a mass of information loss, and several papers have addressed the issue of attribute interactions. In addition to the basic Pearson's correlation [Gan et al., 2007], Jakulin and Bratko analyzed the attribute dependency by information gain [Jakulin and Bratko, 2003], but they involve the label information which is only eligible in supervised learning. While a rank-correlated measure [Calders et al., 2006] has been proposed to mine frequent patterns, it only considers the pairwise relationship in a local way and works on nonintuitive ranks rather than attribute values. More recently, Wang et al. put forward the coupled nominal similarity in unsupervised learning [Wang et al., 2011], but only for categorical data. A relational classifier was investigated by using multiple source relations [Bollegala et al., 2011], which yet merely contributes to classification tasks. Plant presented the dependency clustering by mapping objects and attributes in a cluster-specific low-dimension space [Plant, 2012], however, the interaction mechanism is embedded in the modeling process of clustering and not explicitly defined. Despite the current research progress, no work has been reported that systematically takes into account the global relationships among continuous attributes.

3 Coupled Interactions of Attributes

The couplings of continuous attributes are proposed in terms of both intra-coupled and inter-coupled interactions. Below, the intra-coupled and inter-coupled relationships, as well as the integrated coupling, are formalized and exemplified.

The usual way to represent data is to use an information table S =< U, A, V, f >, where universe U = {u1, · · · , um} consists of finite data objects; A = {a1, · · · , an} is a finite set of continuous attributes; V = ⋃nj=1 Vj is a collection of attribute value sets, in which Vj = {aj.v1, · · · , aj.vtj } is the set of tj attribute values from attribute aj(1 ≤ j ≤ n); and f = ⋃nj=1 fj, fj : U → Vj is an information function which assigns a particular value of attribute aj to each object. For instance, Table 1 is an information table composed of six objects {u1, · · · , u6} and four attributes {a1, a2, a3, a4}, the attribute value of object u1 on attribute a4 is f4(u1) = 0.2.

Based on S, we aim to capture the interactive relationships within a numerical attribute (intra-coupled) and among different continuous attributes (inter-coupled). A common method to explore the relationship between continuous attributes is to calculate the Pearson's correlation coefficient [Gan et al., 2007], which measures the agreement of shapes between variables. In detail, the Pearson's product-moment correlation coefficient between attributes aj and ak is formalized as

where μj , μk are the respective mean values of aj , ak.

However, the Pearson's correlation coefficient only describes the linear relationship between two variables. It is insufficient if we consider this coefficient just between each pair of continuous attributes. So we expect to expand the numerical space spanned by n continuous attributes with more dimensions, and then expose the coupling relationships of continuous attributes by exploring the correlation between every two updated attributes. The idea of increasing dimensionality is also consistent with [Li and Liu, 2012], which extends attribute information but lacks the dependency therein.

Firstly, we lodge some more attributes to the original continuous space. Each attribute aj is accompanied with L - 1 more attributes: 〈aj〉2 , 〈aj 〉3 , · · · , 〈aj〉L. The attribute value of 〈aj〉p (1 ≤ p ≤ L) is the p-th power of the corresponding value of attribute aj. That is to say, 〈aj〉p .vt = (aj.vt)p for all the attribute values aj.vt ∈ Vj. For example, the values of 〈aj〉2 and 〈aj〉3 are the square and cube of the attribute values in Vj , respectively. In this way, data can then be represented as an m × L · n extended information table, in which the (L · (j - 1) + p)-th column corresponds to the updated attribute 〈aj〉p . Here, the denotations aj and 〈aj〉1 are equivalent. For instance, Table 2 is an extended information table of the original Table 1 if we set L = 2 for simplicity.

Next, the correlation between each pair of the updated L · n attributes is calculated. It reflects the global coupling relationships of continuous attributes from both the linear and nonlinear aspects, based on the modeling of variables. Below, we actually use the revised correlation coefficient by taking into account the p-values for testing the hypothesis of no correlation between attributes. Each p-value is the probability of getting a correlation as large as the observed value by random chance, when the true correlation is zero. If p-value is small, say less than 0.05, then the correlation Cor(aj, ak) is significant. Thus, the revised correlation coefficient is defined as

In this way, the revised correlation is endowed with the statistical significance, which makes the correlation between variables more reasonable and reliable. That is to say, we only consider those significant coupling relationships of attributes rather than simply involving all of them. The reason is that in the latter case, the over-fitting problem on modeling the coupling relationships may arise, which will inevitably violate the inherent interaction mechanism of attributes. Based on this revised correlation, we propose the intra-coupled interaction and inter-coupled interaction of continuous attributes. Below, L is the maximal power, 1 ≤ p, q ≤ L, aj = 〈aj〉1 .

On one hand, the intra-coupled interaction is quantified as the correlations between attribute aj and its powers 〈aj〉p .

Definition 3.1 The Intra-coupled Interaction within numerical attribute aj is represented as an L×L matrix RIa (aj), in which the (p, q) entry describes the correlation between the updated attributes 〈aj〉p and 〈aj〉q . Specifically,

where θpq(j) = R Cor(〈aj 〉p , 〈aj〉q ) is the Pearson's correlation coefficient between 〈aj〉p and 〈aj〉q .

Based on Table 1, for attribute a4, we then have RIa (a4) = ( 1 0.989 0.989 1 ) as the intra-coupled interaction within a4. It means the correlation coefficient between the attribute "Petal.W" and its seconder power is as high as 0.989, which signifies that they are rather closely related.

On the other hand, the inter-coupled interaction captures the correlations between each attribute aj and all the powers of other attributes ak (k ̸= j). Accordingly, we have

Definition 3.2 The Inter-coupled Interaction between attribute aj and other attributes ak (k ̸= j) is quantified as an L × L · (n - 1) matrix RIe (aj |{ak}k̸=j ), in which the (p, (i - 1) · L + q) entry represents the correlation of the updated attributes 〈aj〉p and 〈aki 〉q . Specifically,

where {ak}k̸=j= {ak1 , · · · .akn-1 } is the set of attributes other than aj, and ηpq(j|ki) = R Cor(〈aj 〉p , 〈aki 〉q ) is the Pearson's correlation coefficient between 〈aj〉p and 〈aki 〉q .

For instance, in Table 1, we have the inter-coupled interaction of attribute a4 with others (i.e. a1, a2, and a3) to be

Thus, we capture the hidden relationship that "Petal.W" has negative correlation with "Sepal.W", but is positively and closely related with "Sepal.L" and "Petal.L" as well as their second powers, which are consistent with our intuition. In particular, there is no significant correlation between the second power of "Petal.W" and "Sepal.W", indicating the relevant p-value must be at least as large as 0.05. This shows that the involvement of both the intra-coupled interaction and the inter-coupled interaction largely enriches the global coupling than the correlation coefficient which only considers every pair of the original attributes.

4 Coupled Representation for Objects

In this section, a coupled representation scheme for numerical objects is proposed by integrating the intra-coupled and intercoupled interactions of continuous attributes.

˜

In the extended information table S, each quantitative object is described by L · n updated variables ˜ A = {〈a1〉1 , · · · , 〈a1〉L, · · · , 〈an〉1 , · · · , 〈an〉L}. The updated information function ˜ f p j (u) assigns the corresponding value of attribute 〈aj〉p to object u. The attribute values of aj and its powers for u are presented as a vector ˜u(aj) = [ ˜ f 1 j (u), · · · , ˜ f L j (u)], while the attribute values of other attributes and their powers for u are summarized in another vector ˜u({ak}k̸=j ) = [ ˜ f 1 k1 (u), · · · , ˜ f L k1 (u), · · · , ˜ f 1 kn-1 (u), · · · , ˜ f L kn-1 (u)]. For instance, in Table 2, ˜ u1(a4) = [0.20, 0.04], ˜ u1({a1, a2, a3}) = [5.50, 30.25, 4.20, 17.64, 1.40, 1.96].

Further, the coupled interactions are incorporated into a new object representation scheme reflecting the couplings within and between numerical attributes.

Definition 4.1 The Coupled Representation for numerical object u on the continuous attribute aj is a 1 × L vector uc (aj | ˜ A, L), in which the (1, p) component corresponds to the updated attribute 〈aj〉p . Specifically,

where w = [1/(1!), 1/(2!), · · · , 1/(L!)] is a constant 1 × L vector, [w,w, · · · ,w] is a 1× L · (n -1) vector concatenated by n - 1 constant vectors w. "⊙" denotes the Hadamard product 1 , and "⊗" represents the matrix multiplication.

˜

For instance, in Table 1, we calculate that uc1 (a4| A, 2) = [10.92, 14.50], where 10.92 and 14.50 are the respective values of 〈a4〉1 and 〈a4〉2 . Below, the reason to choose such a coupled representation method is clarified. If the above Equation (4.1) is expanded, for instance, we obtain the (1, p) element (corresponds to 〈aj〉p ) of the vector uc (aj| ˜ A, L) as

1 Hadamard product is a binary operation that takes two row vectors of the same size, and produces another vector where each (1, i) element is the product of the (1, i) elements of the original vectors.

which resembles the Taylor expansion [Jia and Zhang, 2008] of functions. The right side of the above Equation (4.2) is expected to accurately exhibit the intrinsic complete coupled representation uc (aj | ˜ A) for object u on the updated attribute 〈aj〉p , when the maximal power L tends to infinity, i.e.

Further, it is a common practice to approximate a function by using a finite number of terms of its Taylor series. Thus, we intend to approximate the intrinsic complete coupled representation by fixing a positive integer L to largely capture the global interactions of attributes with a tolerable residual error. In the empirical study followed, the maximal power L is evaluated according to the clustering accuracy.

Finally, when all the n original attributes are considered, we obtain the global coupled representation for numerical object u to be a concatenated vector:

Therefore, each object is now represented as a 1 × L · n numerical vector incorporated with the couplings of continuous attributes. We then obtain an m × L · n coupled information table Sc when all the objects in universe U follow the above steps. For instance, based on Table 1, the coupled information table shown in Table 3, is the new representation.

So far, we have obtained the global coupled representation Sc for continuous data. The coupled representation for numerical objects reflects the mutual influence and interactions of attributes, and reserves far more coupling relationships from continuous data than the original representation. Back to the case discussed in Section 1, we obtain that the normalized Euclidean distance between u4 and u6 is 0.448 based on Sc , larger than both the normalized distances between u4, u3 (i.e. 0.354) and between u6, u5 (i.e. 0.419). Similarly, the normalized distance between u3, u5 (i.e. 0.830) is also greater than them. It means that u4, u6 and u3, u5 are unlikely to be clustered together, which is consistent with the real situation and verifies that our proposed coupled representation is effective in capturing the implicit relationships.

5 Empirical Study

In this section, several experiments are performed on 13 UCI data sets (i.e. Table 4) to show the effectiveness of our proposed coupled representation scheme for numerical objects. Two data representation schemes are considered and compared: the original representation as an information table S and the coupled representation as a coupled information table Sc . Each column of S and Sc is normalized to have zero mean and standard deviation as one, so as to eliminate value differences in the order of magnitudes.

The experiments are divided into two categories: parameter estimation and learning applications. Note that the number of runs is set to be 100 to obtain the corresponding average results with their sample standard deviations. The number of clusters is fixed to be the number of real classes.

5.1 Parameter Estimation

As indicated in Equation (4.2), the proposed coupled representation for numerical objects is strongly dependent on the maximal power L. Here, we conduct several experiments to study the performance of L with regard to the clustering accuracy of k-means. The maximal power L is set to range from L = 1 to L = 10 since L! becomes extremely large when L grows, which means L = 10 is probably large enough to obtain most of the information in Equation (4.2).

Figure 2 shows the performance of L on six data sets. It is clear that the clustering accuracy of coupled representation generally reaches to a stable point when L takes the value 3 or 4, which means that L = 3 or L = 4 is empirically large enough to capture the global couplings of attributes. As a general trend, the accuracy goes up when L increases. Only except Blood and Telescope, the correlation coefficients between the accuracy and L are significantly around 0.75 for the rest data. But the increasing rate of accuracy gets smaller as L grows. This is consistent with Equation (4.2), since a large value of L! acting as the denominator makes the corresponding item rather small. In the experiments followed, we fix L to be 3 or 4 and report the better results between them.

Another important observation is k-means based on the coupled representation always outperforms that built on the original representation when L ≥ 2, though a small deviation exists. That is to say, our proposed representation is useful and effective to discover the coupled relationships embedded in the continuous attributes. In addition, the null hypothesis that k-means with the coupled representation is better than the original k-means in terms of the accuracy is accepted. However, we can see that our coupled method does not perform stably well when L = 1. The reason is the case of L = 1 just reflects the linear relationship among attributes and only captures a local picture of the global interactions.

5.2 Learning Applications

In this part, three groups of experiments are conducted on extensive data sets for machine learning applications.

Cluster Structure Analysis

Experiments are performed to explicitly specify the internal structures for the labeled numerical data. The data representation methods are evaluated with the given labels and the clustering internal descriptors: Relative Distance (RD), DaviesBouldin Index (DBI) [Davies and Bouldin, 1979], Dunn Index (DI) [Dunn, 1974], and Sum-Distance (SD). In detail, RD is the ratio of average inter-cluster distance upon average intra-cluster distance; SD is the sum of object distances within all the clusters. Since the internal criteria seek the clusters with a high intra-cluster similarity and a low inter-cluster similarity, larger RD, larger DI, smaller DBI, and smaller SD indicate the stronger cluster differentiation capability, which corresponds to a superior representation scheme.

The cluster structures produced by different representation schemes are analyzed on nine data sets. The normalized results are shown in Figure 3, which shows that, with the exception of only one item (i.e. Vowel on DI), the corresponding RD and DI indexes for the coupled representation are larger than those for the original representation; while the associated DBI and SD indexes for the former are always smaller than those for the latter. It shows that our proposed coupled representation, which effectively captures the global interactions of attributes, is superior to the original method in terms of differentiating objects in distinct clusters.

Data Clustering Evaluation

Two classical clustering approaches are single linkage algorithm (LC) [Ackerman and Ben-David, 2011] and spectral clustering (SC) [Luxburg, 2007]. These two methods are evaluated when incorporating the original (LC-OR, SC-OR) and coupled (LC-CR, SC-CR) representation schemes. The external clustering quality measures include Accuracy and Normalized Mutual Information (NMI). As described in [Cai et al., 2005], the larger these indexes, the better the clustering.

Table 5 reports the results of the four approaches on six data sets in terms of external measures. The higher scores are highlighted in boldface, when LC-CR compared with LCOR and SC-CR compared with SC-OR. This table indicates LC-CR and SC-CR respectively outperform their baseline algorithms LC-OR and SC-OR on both measures for almost all the data, except only one italic bold value. The maximal average improvement rate across all the data is 95.67%, while the minimal is 12.35%. Statistical testing also supports the results that LC-CR performs better than LC-OR and SC-CR outperforms SC-OR, at 95% significance level. Another interesting observation is that SC is mostly superior to LC, which also agrees with such a statement in [Luxburg, 2007].

Data Classification Evaluation

To further verify the superiority of our proposed coupled method, we use the k-nearest neighbor (KNN) algorithm [Figueiredo et al., 2011] to compare the classification quality. KNN is a type of instance-based learning, classifying objects based on the closest training examples in the attribute space. We carry out experiments on six data sets. As we know, a better data representation approach corresponds to a better classification result, i.e. higher Accuracy, higher Precision, higher Recall, and higher Specificity [Figueiredo et al., 2011]. We use the 10-fold cross-validation with K = 4.

The results of KNN based on distinct representations are shown in Figure 4. KNN upon the coupled representation remarkably outperforms the original KNN for all the data sets in terms of all the evaluation measures. The maximal relative improvement rate across all the data sets is 138.89%, while the minimal rate is 5.51%. All the results are supported by a statistical significant test at 95% significance level. Similar results can also be observed by KNN when K takes other integers, which again suggests the effectiveness and superiority of our proposed coupled method.

It is also noted that the improvement on Patient is relatively small with respect to all the measures. The reason is the coupled interactions among the attributes of Patient is weak. Only around 45% pairs of attributes and their powers have significant coupling relationships, compared to the average percentage of around 78% on other data sets.

6 Conclusion

We have proposed a coupled representation scheme for objects via teasing out the interactions of numerical attributes. Those interactions are quantified as the intra-coupled relationship described by the Pearson's correlations between attributes and their own powers, and the inter-coupled relationship characterized by the correlations between attributes and the powers of others. Both interactions are integrated to form the Taylor-like expansion based coupled representation for quantitative objects in a global way. The selection of the maximal power is empirically studied, reporting that L = 3 or 4 is large enough to capture the global coupling relationships. Substantial experiments have verified that the coupled representation outperforms the original on data structure, data clustering and classification, supported by statistical analysis.

We are currently enriching this framework of the coupled attribute analysis on numerical data by also addressing the coupling relationships for objects and clusters. In the future, we will work on modeling the coupling relationships for mixed data with both numerical and categorical attributes.

Acknowledgments

This work is sponsored in part by Australian Research Council Discovery Grant (DP1096218) and Australian Research Council Linkage Grant (LP100200774).