Embedding-based Representation of Categorical Data by Hierarchical Value Coupling Learning

1 Introduction

Categorical data with finite unordered feature values is ubiquitous in real-world applications and has received increasing attention for representation and learning [Wang et al., 2015; Zhang et al., 2015]. Unlike numerical data, categorical data cannot be directly manipulated per algebraic operations; hence many popular numerical learning algorithms are not directly applicable. Accordingly, it is important to learn an expressive numerical representation of categorical data.

In general, a good representation should effectively capture the intrinsic data characteristics [Bengio et al., 2013]. One key characteristic in complex categorical data is the following hierarchical couplings (i.e., dependency or correlation) embedded in feature values. (1) On the low level, there exist strong couplings [Cao, 2015] between feature values, demonstrating the natural clusters of values. Taking census data as an example, it may be visible that the value PhD of feature Education is highly coupled with the values Scientist and Professor of feature Occupation; and these values form a semantic value cluster that characterizes one type of strong relation between education and occupation. In addition, different value clusters exist on different granularities and with different semantics [Foss and Za¨ıane, 2002]; e.g., all values belong to one super cluster at the coarsest granularity while each value is a cluster at the finest granularity. (2) On the high level, the clusters of feature values are further coupled with each other. Couplings exist between clusters of the same granularity and between clusters of different granularities.

For the above hierarchical value couplings in categorical data, existing embedding and similarity-based representation methods can capture only a part or none of these feature value couplings. Typical embedding-based representation methods transform categorical data to numerical data by encoding schemes, e.g., 0-1 encoding and Inverse Document Frequency (IDF) encoding [Aizawa, 2003; Pang et al., 2016c]. These methods are easy to implement, but do not consider the couplings between feature values since they usually treat features independently. Some recent similarity-based representation methods, e.g., in [Ahmad and Dey, 2007; Ienco et al., 2012; Wang et al., 2015; Jia et al., 2016] incorporate feature relations into similarity or kernel matrices. However, they do not capture the value clusters or the couplings between value clusters, leading to insufficient representation power in handling data with such hierarchical value couplings.

The hierarchical value couplings reflect the intrinsic data characteristics and complexities, which need to be captured in data representation. However, this is not a trivial task and, to our best knowledge, no work reported properly handles them. Accordingly, this paper aims to explicitly learn these couplings in terms of a new embedding-based representation. The main idea and contributions are as follows.

• A Coupled Unsupervised categorical data REpresentation (CURE) framework is proposed, which has a hierarchical learning structure. CURE is data-driven, which first learns the value clusters with different granularities by involving different low-level feature value couplings. It further generates an object embedding based on the concatenation of value embedding obtained by modeling couplings among the learned value clusters. In this way, CURE captures the intrinsic data characteristics and enables an effective numerical representation for categori-

cal data with sophisticated couplings.

• The CURE framework is further instantiated into a Coupled Data Embedding (CDE) method to capture two types of value couplings. CDE captures complementary feature value couplings and produces diverse sets of informative value clusters. It further models the affluent couplings among these value clusters to embed categorical data into a new space with independent dimensions and rich semantics. As a result, CDE enables algebraic operations of categorical data in the Euclidean space.

Substantial experiments show that (1) CDE significantly outperforms three popular embedding methods and three stateof-the-art coupled similarity measures in terms of F-score for clustering on 10 real-world data sets with different value coupling complexities; (2) CDE performs stably and is insensitive to its parameters.

2 RelatedWork

This section discusses three closely related work, including embedding-based representation, similarity-based representation and coupling learning.

Embedding-based Representation. Embedding-based representation constructs a numerical vector for each categorical object. Encoding methods are commonly used for categorical data representation [Cohen et al., 2013]. One popular method is the 0-1 encoding which encodes each feature value with a 0-1 indicator vector [Pang et al., 2016c]. Although 0-1 coding is reversible with the original data, it assumes that the distance among all values equal 1 which is often violated in real-world data. To alleviate the curse of dimensionality issue, dimension reduction methods, like principal component analysis (PCA) [Jolliffe, 2002], are often conducted on a 0-1 encoding matrix. Another well-known method is IDF encoding [Aizawa, 2003] which differentiates the values from the same feature according to value frequency; however, it cannot capture the couplings between values from different features.

Several effective embedding methods are available for textual data, such as latent semantic indexing (LSI) [Deerwester et al., 1990], latent Dirichlet allocation (LDA) [Blei et al., 2003], skip-gram [Mikolov et al., 2013a] and their variants [Hofmann, 1999; Wilson and Chew, 2010; Mikolov et al., 2013b]. However, categorical data has an explicit feature structure, which is very different from unstructured textual data. Hence, these methods do not fit our target problem.

Similarity-based Representation. Similarity-based representation approaches (including some kernel methods) represent categorical data with an object similarity matrix. Various similarity measures have been designed to capture value couplings in data: ALGO [Ahmad and Dey, 2007] first use conditional probability of two feature values to describe the value couplings; DILCA [Ienco et al., 2012] and DM [Jia et al., 2016] incorporate feature selection and feature weighting into capturing feature couplings respectively; COS [Wang et al., 2015] takes inter- and intra-feature couplings into consideration. Although these similarity measures capture the pairwise value couplings, they do not consider the value clusters and the couplings between value clusters. Meanwhile, similarity measurement is not an efficient method of representation since it must calculate and store an object similarity matrix which may limit its applications.

In addition, there are some embedding methods, e.g., in [Cox and Cox, 2000; Hinton and Roweis, 2002] which optimize the embedding representation on the similarity matrix, but their results heavily rely on the underlying similarity measures. Some other similar embeddingmethods, e.g. in [Zhang et al., 2015] require class labels to learn distance, and thus they are inapplicable for unsupervised tasks.

Coupling Learning. Coupling learning is a methodology that learns value-to-object coupling relationships to leverage feature and object couplings to empower different models, which has shown valuable and been successfully applied to various problems, e.g., behavior analysis [Cao et al., 2012; Cao, 2014], similarity learning [Wang et al., 2015] and outlier detection [Pang et al., 2016b; 2016a]. This work extends this methodology by capturing hierarchical value to value cluster couplings in categorical data representation.

3 Embedding with Hierarchical Value to Value Cluster Couplings

The proposed CURE framework learns an embedding-based representation for each feature value by modeling hierarchical value to value cluster couplings. As shown in Figure 1, CURE first constructs multiple value-value influence matrices {M1, · · · ,Mn} with different value coupling functions {φ1, · · · , φn}. These value influence matrices reflect the lowlevel data characteristics. CURE then learns the value clusters with different granularities based on value influence matrices, resulting in a set of value-cluster matrices {C1, · · · ,Cn}. These value clusters convey rich semantics and have couplings with each other. CURE further learns the couplings between value clusters and generates a |V |×r value representation matrix N, where r is the dimension in the embedding space. After this, the object embedding matrix is generated by the concatenation of value vectors.

We further instantiate the CURE framework into an embedding method called CDE. In CDE, we construct two value influence matrices to capture the complementary feature value couplings; the complementarity is theoretically proved. CDE learns the value clusters with different granularities by multiple k-means clustering with different parameter values k. By conducting PCA on value clusters, CDE learns the linear correlations between value clusters and obtains the final numerical representation of an original data set.

3.1 Preliminaries

Let a data set D consist of a number of data objects O that are described by a set of features F. D can be organized as an information table T = < O,F, V >, where O = {o1, ..., on} is composed of a non-empty finite set of data objects, F = {f1, ..., fm} is a finite set of features and V = ∪mj=1Vj consists of sets of values from all features, in which Vj is the set of values of feature fj. The value sets of each feature are distinct , i.e., Vi ∩ Vj = ∅, ∀i ̸= j. The whole value set of T is V = {v1, v2, ..., vl}, where l is the total number of values.

The value from feature f in object o is denoted by vf o and the feature which the value vi belongs to is denoted by f i . We assume that the probability p(v) of a value can be represented by its frequency. The joint probability of two values vi and

We use normalized mutual information [Est´evez et al., 2009] ψ to reflect the relation between two features, which is defined as follows:

where h(fa) = ∑vi∈Vfa p(vi)log(p(vi)) is the marginal entropy of feature fa.

3.2 Learning Complementary Value Couplings

We construct two value influence matrices to capture the value couplings from occurrence and co-occurrence perspectives whose complementarity is proved in Section 4.

Definition 1 (Occurrence-based Value Influence Matrix). The occurrence-based value influence matrix Mo is defined as follows:

where the coupling function φo(vi, vj) = ψ(f i , f j ) × p(vj) p(vi) indicates the occurrence influence on value vi from value vj.

The coupling function φo captures the difference between the marginal probabilities of values within their own feature. The mutual information which reflects the feature relation is incorporated as weight on value couplings. .

Definition 2 (Co-occurrence-based Value Influence Matrix). The co-occurrence-based value influence matrix Mc is defined as follows:

where the coupling function φc(vi, vj) = p(vi,vj) p(vi) indicates the co-occurrence influence on value vi from value vj .

The coupling function φc captures the difference between two values by conditional probabilities across different features. Accordingly, Mc is asymmetric which means the influence on vi from vj is different from the influence on vj from vi. The φc value of two values from the same feature always equals 0 since they never co-occur in the same object.

3.3 Clustering Values with Different Granularities

Based on the above matrices, we can learn the value clusters with different granularities which represent different semantics and well reflect the data characteristics. To learn the value clusters with different granularities, here we conduct clustering on the value matrices with different cluster numbers.

We conduct k-means clustering on Mo with different k, i.e., {k1, k2, ..., ko}, and on Mc with {k1, k2, ..., kc}. The clustering results are represented by a cluster membership indicator matrix, where the entry is one if a value is contained in a value cluster and zero otherwise. So we obtain two indicator matrices. We further concatenate these two indicator matrices and obtain a l ×(∑oi=1 ki + ∑cj=1 kj ) indicator matrix I. The choice of k is discussed in Section 3.5.

k-means clustering is chosen for two major reasons as follows: (1) The value influence matrices are numerical and the Euclidean distance fed in k-means clustering captures the global relation between values. (2) k-means clustering is linear w.r.t. the size of the input matrix, which enables CDE to efficiently learn value clusters with different size.

3.4 Embedding Values with Linear Couplings between Value Clusters

The indicator matrix I conveys rich couplings between the value clusters obtained using different granularities on two value influence matrices. For simplicity and the consideration of common scenarios, we assume that couplings between value clusters are linear correlations, and apply PCA on the indicator matrix to learn the linear correlations between value clusters to obtain a vector embedding for each value. PCA is chosen because (1) it reduces the data complexity with little loss of information by converting a matrix with linearly correlated variables to a new matrix with linearly uncorrelated components, and (2) it substantially reduces the dimensionality of the value embedding, which enables us to represent an object in a considerably lower-dimensional embedding space.

We first calculate the centralized matrix X of the indicator matrix I by subtracting the mean of each column and further derive a covariance matrix S from X. The value embedding N is obtained by the following matrix decomposition:

where V is the principal component matrix derived from singular value decomposition results of S, i.e., S = UΣV.

After the transformation of PCA, the dimensions of value embedding N are independent of each other so that the algebraic operations in the Euclidean space can be used on the embedded matrix.

Algorithm 1 Value Embedding (D, α, β)

Input: D - data set, α - proportion factor, β - dimension reducing factor

Output: N - the numerical representation of all values

• 1: GenerateMo andMc
• 2: Initialize I = ∅
• 3: forM∈ {Mo,Mc} do
• 4: Initialize k = 2
• 5: rm= ∅
• 6: repeat
• 7: I = [I; kmeans(M, k)]
• 8: Remove the cluster with only one value and store the remove cluster in rm
• 9: k+ = 1
• 10: until length(rm) ≥ ⌈ kα ⌉
• 11: end for
• 12: X= I -mean(I)
• 13: Calculate the covariance matrix S of X
• 14: [U, Σ, V] = SVD (S)
• 15: N=XVT
• 16: Remove the columns whose maximum Euclidean distance of any two elements is less than β fromN
• 17: return N

3.5 The CDEMethod

Algorithm 1 presents the main procedures of CDE. The first step is to generate the value influence matrices Mo and Mc according to Definitions (1) and (2).

k is the clustering parameter which decides the granularity of value clusters. Instead of giving a fixed value, we use another proportion factor α to decide the maximum cluster number as shown in Steps (3-11) of Algorithm 1. We remove those tiny clusters with only one value from the indicator matrix. When the number of removed clusters is larger than kα , we stop increasing k, whose initial value is 2. The final indicator matrix is the concatenation of all clustering results with different k fromMo andMc.

After conducting PCA on the indicator matrix to learn the correlations between value clusters, we remove those columns whose maximum pairwise Euclidean distance is less than β from N. Finally, we calculate the object embedding by concatenating embedding vectors of its values fromN.

We can scan the original data set and generate Mo and Mc with the complexity of O(nm2 ). Clustering on the value matrix has complexity O(kmaxl), where kmax is the number of times for clustering on one value matrix which is less than value number l. PCA has O(l3 ). With the numerical representation of values, generating the embedding matrix of objects has O(nm). Correspondingly, the time complexity of CDE is O(nm2 + l3 ).

4 Theoretical Analysis of CDE

CDE obtains the value clusters by k-means clustering which is based on the Euclidean distance matrices of Mo and Mc. The distance matrix in k-means clustering decides the quality of value clusters. By proving the complementarity of the two distance matrices, we can observe that the two value couplings are complementary.

The occurrence distance between values vi and vj is defined as follows:

where φo(vi, vh) is the occurrence coupling function defined in Definition 1 and l is the number of values.

The co-occurrence distance between values vi and vj is defined below:

where φc(vi, vh) is the co-occurrence coupling function defined in Definition 2. If any two distinct values can be distinguished by do or dc, then do and dc are complementary.

Theorem 1 (Distance Complementarity). For any two values vi ̸= vj , do(vi, vj) ̸= 0 or dc(vi, vj) ̸= 0.

Proof. To prove the above theorem, we prove that vi ̸= vj and do(vi, vj) = 0 satisfy dc(vi, vj) ̸= 0 for all cases. If dc(vi, vj) = 0, then ∀vh ∈ V, φc(vi, vh) = φc(vj, vh). To prove dc(vi, vj) ̸= 0, we only need to prove ∃vh ∈ V, φc(vi, vh) ̸= φc(vj, vh). Then we prove the theorem by considering the following cases.

(1) vi and vj belong to the same feature, which means ψ(f i , f h ) = ψ(f j , f h ): then do(vi, vj) = 0 if and only if p(vi) = p(vj). Let vh = vi, then φc(vi, vh) = 1 and φc(vj, vh) = 0 since vi, vj belong to the same feature. Hence, dc(vi, vj) ̸= 0 when vi and vj from the same feature.

(2) vi and vj belong to different features: do(vi, vj) = 0 if and only if ∀vh ∈ V, ψ(f i , f h ) p(vh) p(vi) = ψ(f j , f h ) p(vh) p(vj) . When ψ(f i , f h ) ̸= ψ(f j , f h ) and p(vi) ̸= p(vj) (suppose p(vi) < p(vj)), then p(vi, vj) < p(vj). Let vh = vi, then φc(vi, vh) = 1 and φc(vj, vh) > 0. Accordingly, dc(vi, vj) ̸= 0 when p(vi) ̸= p(vj). When ψ(f i , f h ) = ψ(f j , f h ) and p(vi) = p(vj), ∃vh in feature f i and p(vj, vh) > 0, but p(vi, vh) = 0, then φc(vj, vh) ̸= φc(vi, vh). Therefore, dc(vi, vj) ̸= 0 when vi and vj belong to different features.

5 Experiments and Evaluation

5.1 Baseline Methods and Parameter Settings

To test the embedding performance, CDE is compared with three popular unsupervised categorical data embedding methods: 0-1 embedding (noted as 0-1), 0-1 embedding with PCA (0-1P), and inverse document frequency embedding (IDF). 0-1 embedding keeps the most complete information in the original data. 0-1 embedding with PCA incorporates feature correlations into the embedding. The IDF embedding differentiates values w.r.t. frequency.

To the best of our knowledge, no existing embedding methods capture the value couplings in categorical data as in CDE.

To test the CDE-based learning performance, we transform CDE to similarity measure and compare it with three typical and well-performed similarity measures which involve feature relation: COS [Wang et al., 2015], DILCA [Ienco et al., 2012] and ALGO [Ahmad and Dey, 2007] 1 .

In Table 2, |C| is the number of ground-truth classes in data, which is used for the clustering evaluation. We set parameter α = 10 in CDE and parameter β = 10-10 in PCA used by CDE and 0-1P. In COS, DILCA and ALGO, we use the default parameters in their original papers.

5.2 Performance EvaluationMethods

K-means clustering is used to test the performance of CDE against other embedding methods. The embedding methods transform categorical data into numerical data, hence kmeans clustering can efficiently cluster objects without computing the pairwise object similarity matrix.

To make a fair comparison with similarity-based representation methods, we perform the Gaussian similarity measure on CDE to obtain a object similarity matrix. Spectral clustering is used to evaluate the performance of this object similarity matrix against other object similarity matrices obtained by COS, DILCA and ALGO.

F-score and NMI [Powers, 2011] are two of the most popular clustering evaluation methods. Since we fix the cluster number to the number of classes in each data set, NMI performs similarly as F-score. Here we only report the results of F-score. Higher F-score indicates better clustering accuracy driven by a better embedding method or similarity measure. The p-value results are based on the paired two-tailed t-test using the null hypothesis that the clustering results of CDE and other methods come from distributions with equal means. For each data set, the F-score is the average over 50 validations of clustering with distinct starting points due to the instability of k-means clustering.

5.3 Data Sets and Data Factors

We use ten real-world UCI data sets from different domains for the experiments. Various data factors are used to measure the underlying characteristics of data sets, which are associated with the learning performance of embedding methods. Two key data factors are defined below, and their results of the data sets are reported in Table 1 and Table 2.

• The feature correlation index (FCI) measures the average correlation strength between features:

SU measures the correlation between features fi and fj by the symmetric uncertainty [Yu and Liu, 2003]. Larger FCI indicates stronger correlation between features.

• The value cluster index (VCI) is the average of the maximum non-overlapping ratio between value sets con-

1 Our experiments show DM [Jia et al., 2016] underperforms DILCA and ALGO, so its results are thus omitted due to space limit.

tained in different classes for each feature:

where V hCi is the value set in class Ci for feature fh and m is the number of features. Larger VCI indicates the higher discriminative ability of the value sets.

5.4 Results and Observations

CDE is first compared with three embedding methods, followed by a comparison with three similarity measures. We then examine the parameter sensitivity of CDE. 2

Comparison with Embedding Methods

F-score of CDE compared with 0-1, 0-1P and IDF are shown in Table 1. CDE obtains the best F-score on seven data sets; and on average, it demonstrates an approximate 9%, 5% and 19% improvement over 0-1, 0-1P and IDF, respectively. The significance test results show that CDE significantly outperforms other embedding methods at the 95% confidence level.

According to the data factor FCI, the F-score performance of CDE, 0-1 and 0-1P has a downward trend with the decrease of FCI. Since CDE and 0-1P are able to capture the correlation between features according to the data factor FCI, for most data sets with higher FCI, e.g., Wisconsin, Soybeansmall, Mammographic, Zoo, Dermatology, CDE outperforms the other embedding methods and 0-1P obtains better performance than 0-1. On the other hand, FCI only reflects the pairwise correlation between features, while CDE captures the couplings beyond such feature correlation. So CDE also performs well on data sets with lower FCI, e.g., Adult, Primarytumor. IDF obtains better results on the data sets with weak couplings, especially when the clustering division is consistent with feature-value frequency, e.g., Lymphography.

Comparison with Similarity Measures

The CDE-based Gaussian similarity (denoted by CDE-G) is compared with three well-performing similarity measures:

2 CDE runs one order of magnitude slower than other embedding methods and much faster than other similarity measures. Due to space limitations, we do not show the detailed efficiency results here.

COS, DILCA and ALGO. As shown in Table 2, CDE-G remains the best performer on half of the data sets. CDE-G obtains about 8%, 3% and 5% improvement over COS, DILCA and ALGO respectively in terms of F-score. The significance test results show that CDE-G significantly outperforms the other similarity measures at 90% confidence level. Note that COS, DILCA and ALGO on Adult run out of memory since calculation of object similarity needs a large amount of memory. This shows that it is more efficient to represent categorical data with an embedding matrix than a similarity matrix.

In Table 2, the data sets are sorted in the descending order of VCI which reflects the discriminative ability of the value clusters in object classes. The class number |C| is also a factor to describe the complexity of data clustering, which is consistent with VCI according to Table 2. Since CDE-G makes use of the value clusters with different granularities, on most data sets with larger VCI and larger |C|, CDE-G achieves better performance than the other similarity measures. Since CDE-G, COS, DILCA and ALGO are able to capture the pairwise correlation between features, all methods achieve good performance on data sets with higher FCI.

Sensitivity Test w.r.t. Parameters α and β

There are two parameters in CDE: α controls the dimension of value embedding before PCA and β controls the dimension of value embedding after PCA. Since all results have a similar trend, we demonstrate the results of four data sets: Adult, Dermatology, Wisconsin, Primarytumor, which have the largest |O|, |V |, FCI and VCI respectively.

Figure 2 shows the dimension of value embedding before PCA and the clustering performance with different α. α directly influences the value of k in Algorithm 1. k determines the granularity of value clusters which consist of the original value embedding. Since we only drop the clusters with only one value, the clustering performance is stable with parameter α, and we can choose the parameter value which is associated with the low dimension of embedding. According to Figure 2, the dimension is stable when α ≥ 10.

Figure 3 shows the dimension of the final value embedding and the clustering performance w.r.t. β.

It shows that the performance of the clustering is stable with β. When β ≥ 10-15 , the dimension of value embedding vectors decreases with the increase of β on all data sets.

According to Figures 2 and 3, the clustering performance is not sensitive to parameters α and β. These two parameters can influence the dimension of value embedding. The dimension is stable when α ≥ 10 and β ≥ 10-15 .

6 Conclusions

Different from existing encoding-based embedding and feature correlation-based similarity measures, a novel unsupervised representation framework (CURE) and its instantiation (CDE) are introduced in this paper, which model hierarchical value couplings in terms of feature interactions and value clustering. Extensive experiments show that CDE significantly outperforms typical embedding methods and similarity measures in capturing feature value interactions. In addition, two proposed data factors further indicate the feature value couplings and value clusters in data sets. Our future work is to model selective value couplings and instantiate the framework into other instances to suit different applications.

Acknowledgments

This work is partially supported by The National Key Research and Development Program of China (No.2016YFB0200401), by program for New Century Excellent Talents in University, by NSF China 61402492, 61402486, 61379146, by the laboratory pre-reseach fund (9140C810106150C81001) and by the Australian Research Council Discovery Grant (DP130102691).