Het2Hom: Representation of Heterogeneous Attributes into Homogeneous Concept Spaces for Categorical-and-Numerical-Attribute Data Clustering

1 Introduction

Categorical values, which refer to the qualitative values without explicit numerical meanings, are quite common in machine learning and data analysis tasks [Agresti, 2003]. Given a data set, the attributes that describe the data samples using a set of categorical values are called categorical attributes. It is inevitable to process categorical-and-numerical attribute data in cluster analysis, as clustering is one of the most commonly used machine learning techniques for unsupervised data analysis. Unlike numerical attributes, categorical attribute values are infeasible for arithmetic computation and do not have a well-defined similarity space. It is therefore extremely challenging to appropriately use the information provided by categorical and numerical attributes in cluster analysis. To address this issue, the existing efforts that have been paid can be roughly divided into two types: (i) represent categorical attribute values into numerical values and treat the represented attributes as numerical ones for clustering, and (ii) directly define similarities for categorical attributes and then perform cluster analysis [Xu and Wunsch, 2005][Boriah et al., 2008][dos Santos and Z´arate, 2015].

∗Corresponding author

For the representation-based methods, one-hot encoding is the most common one, which encodes categorical values into boolean vectors. In recent years, more powerful representation-based methods [Qian et al., 2015][Jian et al., 2018b] have been proposed to encode categorical attributes by extracting and embedding more valuable information into the representations. Recently, a more advanced representation method [Zhu et al., 2022] further introduces multiple kernel functions to learn the representations. Although the above-mentioned recent progress has achieved considerable improvements in clustering performance, they are all designed for pure categorical data only and have not considered the common mixed data clustering problem.

For defining the similarities between categorical values, the conventional Hamming distance simply assigns distances 0 and 1 to identical and different values. Some other measures [Goodall, 1966][Lin, 1998][Cheung and Jia, 2013][Zhang et al., 2020] define the similarities more finely based on the occurrence probabilities of possible values. To further consider the interdependence of attributes, similarity measures [Ienco et al., 2012][Jia et al., 2016][Jian et al., 2018a][Zhang and Cheung, 2022] have been successively presented in the literature. The above-mentioned measures are usually combined with k-prototype clustering algorithm [Huang, 1997][Kacem et al., 2015], which is designed for mixed data clustering. Most recently, a similarity learning method [Zhang and Cheung, 2021] has been proposed to make the similarities learnable in clustering.

Nevertheless, as far as we know, clustering performance on mixed data is still far from satisfactory because none of the existing methods can perform representation or similarity formulation based on the establishment of a homogeneous connection between the heterogeneous categorical and numerical attributes. From the perspective of the concepts expressed by the attributes, categorical attributes and numerical attributes are in different concept hierarchies. For example, the values of a numerical attribute describe the tendencies toward two different concepts, e.g., {high, low} of attribute "income", while each possible value of a categorical attribute stands for a different concept, e.g., {professor, lawyer, doctor} of attribute "occupation", which can produce three pairs of different concepts. Obviously, with the new insight that categorical and numerical attributes are in different concept hierarchies, existing methods still leave us a considerable space for information mining.

In this paper, we propose a novel method called Het2Hom to learn the representations of categorical attributes for mixed data clustering. Het2Hom first projects all the values of an attribute into the spaces spanned by different concept pairs of this attribute, to obtain an informative homogeneous representation of categorical and numerical attributes. Accordingly, a learning mechanism is elaborately designed so that the learning of attribute representations and data objects partition can adapt to each other more appropriately. Extensive experiments show the efficacy of the proposed Het2Hom, and its main advantages are three-fold:

• Het2Hom represents categorical attributes into the form of numerical attributes while preserving the original relationship information of the possible values, thus providing an appropriate basis for mixed data learning.
• A learning mechanism has been designed to make the attribute representation and data objects partition adapt to each other during clustering, thereby somewhat avoiding sub-optimal solutions in the optimization.
• Het2Hom achieves superior clustering performance on both categorical data and mixed data. Furthermore, its representation learning process is efficient and the results are highly interpretable.

2 RelatedWork

Representation-based clustering approaches have two common procedures: (1) represent the data set based on a certain strategy, (2) perform clustering by treating the represented categorical attributes as numerical ones. The simplest onehot encoding is the most commonly used one, which encodes each possible value of an attribute into a vector by setting the bit corresponding to the possible value to 1 and the other bits to 0. Since it assigns an identical distance to any pair of unequal values, it is incapable to distinguish the different dissimilarity degrees. Space structure-based representation [Qian et al., 2015] has been proposed providing a solution for capturing the value and attribute couplings of categorical data. It encodes a target data object by concatenating the distances from it to all the objects. Later, coupling-based representations [Jian et al., 2017][Jian et al., 2018b] have also been proposed to encode the couplings of categorical data. Such methods further perform k-means [Ball and Hall, 1967] clustering and PCA to obtain a more concise representation of the couplings. Recently, a more advanced method [Zhu et al., 2022] adopting different kernel functions has been proposed to more comprehensively represent the couplings. Most recently, the deep learning-based method [Zhu et al., 2020] has also been proposed focusing on the dynamic representation of streaming data with concept-drifts. In summary, none of the above-mentioned approaches can appropriately handle the heterogeneity of mixed data.

For the approaches that directly define the similarities, the widely used Hamming distance uniformly assigns distance 1 to any pair of unequal values and assigns distance 0 to identical values, which has the same drawback as the one-hot encoding. Therefore, probability-based similarity measures [Goodall, 1966][Lin, 1998][Cheung and Jia, 2013][Zhang and Cheung, 2018][Zhang et al., 2020] have been proposed to more finely define similarities based on the occurrence probabilities of possible values. All the above-mentioned measures treat each attribute independently and ignore the valuable information provided by the inter-attribute dependence. Therefore, the measures [Ahmad and Dey, 2007][Le and Ho, 2005][Ienco et al., 2012] have been proposed to define similarities according to conditional probability distributions obtained from different attributes as given target possible values. Since these measures rely on the sole of interdependence of attributes, they will still fail when all the attributes are independent of each other. To solve this problem, the measures [Jia et al., 2016][Jian et al., 2018a][Zhang and Cheung, 2022] that simultaneously consider the intra- and inter-attribute statistical information have been proposed. For all the abovementioned measures, k-prototypes algorithm [Huang, 1997] are usually used to perform clustering. Nevertheless, since similarity measurement and clustering are performed independently, the measured similarities cannot adapt well to the clustering task. Accordingly, more advanced methods [Zhang and Cheung, 2020][Zhang and Cheung, 2021] have been proposed to interactively learn the similarities and data partitions. Although they achieve superior clustering performance, they are designed for categorical data only.

3 ProposedMethod

In this section, we first formulate the problem. Then, we present the Het2Hom with a learning algorithm. Table 1 sorts out the frequently used symbols in this paper. Specific definitions of the symbols will also be given where they first appear in the following text.

3.1 ProblemFormulation

Given a data set S = {x1, x2, ..., xn} with n data objects, each object xi = [x1i , x2i , ..., xdi ]⊤ is a d-dimensional vector taking values from the d attributes A = {a1 , a2 , ..., ad }, where a categorical attribute ar has vr possible values {or1 , or2 , ..., orvr}. For convenience but without loss of generality, we assume that the former dc attributes in A are categorical and the latter du are numerical. Clustering refers to the task that assigns the n data objects in S to k proper clusters C = {c1, c2, ..., ck}, which can be formalized as minimizing

where Q is an n×k matrix indicating the object-cluster affiliations, and the (i, l)th entry qil of Q is defined as

As we focus on the crisp clustering problem, qil satisfies ∑kl=1 qil = 1 and qil ∈ {0, 1}. Φ(xi,my) is the dissimilarity between data object xi and cluster cl described by a vector ml = [m1l ,m2l , ...,mdl ]⊤ fromM = {m1,m2, ...,mk}. The value of ml can be computed following the way of the conventional k-prototypes clustering algorithm. That is, for the numerical case (i.e. r > dc ), the value of mrl is the mean of the values from ar in cl, while for the categorical case (i.e. r ≤ dc ), the value of mrl is equal to the most frequent possible value from ar in cl. The dissimilarity can be written in a general form as

where φ(xri ,mrl ) is the distance between xi and ml in terms of their values on attribute ar , and each weight wr fromW = {w1 , w2 , ..., wd } indicates the importance of ar in clustering.

3.2 Projection-based Representation

Het2Hom is proposed to represent the heterogeneous attributes into homogeneous forms, thus providing a homogeneous basis for defining Φ(xi,ml) and φ(xri ,mrl ). As discussed in Section I, our goal is to project the values of a categorical attribute into the concept spaces in the hierarchy of numerical attributes. We thus project all the values of a categorical attribute ar into the one-dimensional space spanned by a pair of possible values org and orh . Such a space is called endogenous space because it is endogenously generated by the intra-attribute possible values.

As shown in Figure 1, since all the attribute values are projected into an endogenous space, a structural representation of the distance space is thus obtained. Our goal is to obtain as many possible representations of categorical attributes as possible, and make them learnable with the clustering task, thereby achieving more flexible representations. For a categorical attribute with vr possible values, there are γ r = vr (vr -1)/2 endogenous spaces in total. Since each numerical attribute has only one endogenous space, i.e., its original space, we have γ r = 1 when r > dc . All the endogenous spaces corresponding to ar is denoted as Rr = {Rr1 ,Rr2 , ...,Rrγ r}.

To perform the above-mentioned projection, locations of all the attribute values in the original space should be known in advance. The relative locations of attribute values are indicated by their base distance

which is the total difference between Conditional Probability Distributions (CPDs) obtained from as s as given org and orh . Such a distance definition has been commonly adopted by most metrics that consider the inter-dependence of attributes, e.g., [Ienco et al., 2012] and [Jian et al., 2018a]. If the processed data set contains both nominal and ordinal attributes, the distance metric proposed in [Zhang and Cheung, 2021], which is a generalized version of the distance in Eq. (4), can be utilized instead. Based on κ(·, ·), relative location of the projected value ort can be computed as

where φ(ort , org ;Rrb ) is the distance between org and the projection point of ort in the space Rrb spanned by org and orh , and such a formula in Eq. (5) is obtained by simply applying the Pythagorean theorem as shown in the "Projection Point Computation" part of Figure 1. After the projection, since all the values are linearly arranged in Rrb , the distance between any pair of possible values ort and orf is computed by

if the projection points of ort and orf are on the same side of org in Rrb . Otherwise, the distance is computed by

Such a projection-based attributes representation is compared with the conventional methods in Figure 2. Our representation provides a homogeneous basis for connecting numerical and categorical attributes. After the representation, Numerical A� ribute Hamming Distance One-hot Encoding

Figure 2: Comparison of the represented distance spaces.

φ(xri , mrl ) ·wr in Eq. (3) can be replaced with the linear combination of the distances between xri and mrl represented by different endogenous spaces derived from ar :

where wr b is the importance of the endogenous space Rrb .

3.3 Learning Algorithm

With Eq. (8), the objective function in Eq. (1) is rewritten as

where the original W is replaced by W = {W 1 ,W 2 , ...,W d }, and W r = {wr1 ,wr2 , ...,wrγ r} stores the weights corresponding to the endogenous spaces in Rr . Optimizing under such an objective function facilitates the learning of both data object partition and space linear combination (i.e. representation). We iteratively update the partition Q, cluster descriptor M, and weights W, which can be summarized into three steps: (1) Fix W and M, compute Q; (2) Fix W and Q, compute M; (3) Repeat (1) and (2) until convergence, fix Q and M, update W. These three steps are repeated until the value of z(Q,M,W) is minimized.

We follow the conventional ways for computing Q and M as discussed in Section 3.1. The core difficulty is how to appropriately update W, because the updates of the weights in W r are highly cross-coupled due to the common attribute values shared by the spaces in Rr . More specifically, if W is directly computed using Lagrangian multiplier method or updated in a normal gradient-decent way in the abovementioned step (3), the update effect of different weights will somehow offset each other in the next step (1), which can easily lead to a corrupt results, especially when the number of endogenous spaces is large. Accordingly, a strategy is designed to select one weight from each W r in step (3). Specifically, wr b is selected out fromW r by

where ery (l) is the total error contributed by endogenous space Rry on cluster cl:

ϵry (l) and ϵrt (l) are computed through ϵry (l) = ery (l)/ ∑γ r j=1 erj (l) and ϵrt (l) = ert (l)/ ∑γ r j=1 erj (l), respectively, to ensure that the values of ∑γ r t=1 |ϵry (l) - ϵrt (l)| on different clusters cl are comparable, because clusters may have different numbers of data objects.

Remark 1. Given an attribute ar , the numerator of Eq. (10) quantifies the overall difference between ϵry (l) yielded by Rry and the rest ϵrt (l)s yielded by their corresponding Rrt s from the perspective of error contribution to z(Q,M,W). Therefore, a smaller numerator reflects that the space Rry is more representative among all the γ r endogenous spaces of ar , and updating the corresponding weight wry is expected to yield a more effective reduction on z(Q,M,W).

Remark 2. Given an attribute ar , the denominator of Eq. (10) computes the total error contributed by Rry to z(Q,M,W), which reflects the expected effectiveness of updating wry in reducing z(Q,M,W). Therefore, wry corresponding to a larger ∑kl=1 ery (l) is preferred for updating to achieve a more effective reduction on z(Q,M,W).

All the selected weights are updated by a small step by:

where η is the learning rate.

Remark 3. To facilitate a stable learning process, the total weight is always fixed to 1 by ∑dr=1 ∑γ r b=1 wr b = 1. Since numerical attributes are with well-defined distance space, the weight of each numerical attribute is fixed at 1/d. Accordingly, the weights of the endogenous spaces derived from the categorical attributes are uniformly initialized by wr b = dc /(d ∑dc r=1 γ r ), where ∑dc r=1 γ r is the total number of the derived endogenous spaces of categorical attributes.

The whole Het2Hom learning algorithm is summarized in Algorithm 1. The measure yielded by Het2Hom learning is a metric, and the learning algorithm is computationally efficient. The corresponding theoretical analysis has been provided in the Supplementary Material 1 .

4 Experiments

Experiments have been designed to evaluate the performance of the proposed Het2Hom. Detailed experimental settings and complementary experimental results are provided in the Supplementary Material 1 .

4.1 Experimental Settings

Experimental settings are briefly introduced below.

4 + 2 Experiments have been conducted. The four core experiments presented in this paper are (1) clustering performance evaluation, (2) significance study, (3) ablation study,

1 https://drive.google.com/file/d/ 1SKNYxutdftgEfDK9CxzZLYkzYet4Jzf8/view?usp=sharing

Algorithm 1 Het2Hom learning for mixed data clustering

Input: Dataset S, number of sought clusters k, learning rate

• η, stop threshold β Output: Partition Q, weights W 1: Project all the values of categorical attributes according to Eq. (4) and (5) 2: InitializeM by randomly selecting k objects fromS, initialize Q by setting all its values to 0, initialize W according to Remark 3, set θ → 0 and is conv = 0 3: while is conv = 0 do 4: FixW andM, compute Q(new) 5: if Q(new) ̸= Q then 6: Fix W and Q, compute M (new) 7: else 8: Fix Q and M, compute W(new) according to Eq. (10)-(12) 9: if |z(Q,M,W) - θ|/θ < β then 10: Set is conv = 1 11: else 12: Set θ = z(Q,M,W) 13: end if 14: end if 15: end while

and (4) visualization of cluster discrimination ability. The two complementary experiments provided in the Supplementary Material 1 are (i) evaluation of convergence and execution time, and (ii) study of the parameter (i.e., η and β) effects.

9 Counterparts have been compared. One-Hot Encoding (OHE) combined with k-means is chosen because it is a common practical solution for mixed data clustering. Six other counterparts proposed in recent years, including Structure-Based Categorical data encoding (SBC) [Qian et al., 2015], Jia's Distance Metric (JDM) [Jia et al., 2016], Coupled Metric Similarity (CMS) [Jian et al., 2018a], Unified Distance Metric (UDM) [Zhang and Cheung, 2022], and Homogeneous Distance Metric (HDM) [Zhang and Cheung, 2021] combined with k-modes (KMD) [Huang, 1998] and k-prototypes (KPT) [Huang, 1997] according to the attribute composition of data sets, and Object-Cluster Iterative Learning (OCIL) [Cheung and Jia, 2013], have been selected, where CMS, UDM and HDM are the state-of-the-arts. Two conventional clustering algorithms, i.e., the original versions of KMD and KPT, are also compared.

17 Real Data Sets have been utilized for the experiments, and their statistics are shown in Table 2. All the data sets are obtained from the UCI machine learning repository, except FT from [Zhang and Cheung, 2022] and AE from [Zhang and Cheung, 2021].

4 Validity Indices have been chosen, including Clustering Accuracy (CA) [He et al., 2005], the more discriminative Adjusted Rand Index (ARI) [Gates and Ahn, 2017] (value range [-1,1]), and the Normalized Mutual Information (NMI) [Est´evez et al., 2009]. For all these three indices, a larger value indicates better clustering performance. Bonferroni-Dunn (BD) test with computed Critical Difference (CD) interval [Demˇsar, 2006] is utilized for significance test. NMI results are provided in the Supplementary Material 1 .

4.2 Clustering Performance Evaluation

Clustering performance evaluated by CA and ARI has been reported in Table 3 and 4, respectively. Results of KMD for categorical data and KPT for mixed data are combined into the same column for compactness. The observations are: (1) Het2Hom performs the best on almost all the data sets, which indicates its superiority in clustering. (2) Although Het2Hom does not significantly outperform the second-best approaches on TT, AE, and AP data sets, the second-best one differs on these data sets while Het2Hom always performs the best on them. (3) On some data sets, e.g., VT and AA, Het2Hom does not perform the best, but the gaps between Het2Hom and the best-performing counterparts are always tiny (less than 0.01 for both CA and ARI) on these data sets, which still demonstrates the competitiveness of Het2Hom.

4.3 Significance Study

Results of the two-tailed BD test [Demˇsar, 2006] at confidence intervals 0.95 (α = 0.05) and 0.9 (α = 0.1) are shown in Figure 3 and 4. According to [Demˇsar, 2006], performance of Het2Hom is considered to be significantly better than that of all the counterparts outside the right bound of CD intervals. It can be observed from Figure 3 and 4 that Het2Hom performs significantly better than all nine counterparts.

4.4 Ablation Study

To explicitly illustrate the effectiveness of the core components of Het2Hom, several variants of Het2Hom are formed for comparison. The version of Het2Hom that only conducts the Projection-Based Representation (PBR) without representation learning is formed. The version further removes the PBR module and only adopts the Difference of CPDs (DCPDs) defined by Eq. (4) for clustering is also compared.

Performance of the original KMD/KPT is also reported for completeness. It can be observed from the last sub-figure in Figure 5 that the average performance ranks of KMD/KPT, DCPDs, PBR, and Het2Hom are around 4, 3, 2, and 1, respectively, which intuitively verifies the effectiveness of the core components of Het2Hom. More specifically, the superiority of Het2Hom over PBR indicates the correctness of the learning strategy proposed in Section 3.3. PBR outperforms DCPDs, which proves the effectiveness of the projection mechanism presented in Section 3.2. DCPDs performs better than KMD/KPT, which indicates the reasonableness of adopting the distance defined by Eq. (4) as the base distance for conducting the PBR.

4.5 Visualization

In Figure. 6, t-SNE [Maaten and Hinton, 2008] is utilized to demonstrate the cluster discrimination ability of Het2Hom.

We first encode the attributes of the MR data set using OHE, PBR, and Het2Hom. Then the encoded data set is processed by t-SNE into two-dimensional, and visualized by marking the true labels of objects in different colors. It can be observed that the cluster discrimination ability of Het2Hom is obviously stronger than that of PBR and OHE.

5 Conclusion

In this paper, we have proposed Het2Hom, which is composed of a projection-based representation mechanism and a representation learning module, for mixed data clustering. It projects values of categorical attributes onto all the possible endogenous spaces to produce informative representations. Since these elaborately obtained representations are homogeneous with the numerical attributes, attribute representations and the partition of data objects can thus be learned to more appropriately adapt to each other. It turns out that Het2Hom exploits the information more sufficiently based on the established connection between categorical and numerical attributes, and thus achieves a more accurate clustering. Moreover, the intuitive but novel geometry-based projection makes the represented data highly interpretable. Extensive experiments have shown the efficacy of Het2Hom.

Acknowledgements

This work was supported in part by the NSFC under grant 62102097, NSFC/RGC Joint Research Scheme under grant N HKBU214/21, RGC General Research Fund under grant 12201321, HKBU grants: RC-FNRA-IG/18-19/SCI/03 and RC-IRCMs/18-19/SCI/01, the Key-Area R&D Program of Guangdong Province under grant 2021B0101220006, the Guangdong Basic and Applied Basic Research Foundation under grants: 2022A1515011592 and 2021A1515012300, and the Science and Technology Planning Project of Guangdong Province under grant 2019A050510041.