An end-to-end distance measuring for mixed data based on deep relevance learning

Abstract

Distance Measuring between two mixed data objects is the basis of many learning algorithms. The complex relevance between heterogeneous – various types/scales – attributes has a significant influence on the measured results. In this paper, we propose an End-to-End Distance Measuring method for mixed data based on deep relevance learning, called E ${}^{2}$ DM. Existing methods confuse the attributes space by mapping the discrete attribute values to new continuous values, or discretize continuous attributes values without considering the relevance. In contrast, E ${}^{2}$ DM directly manipulates on the original data with data conversion and relevance learning simultaneously to avoid information loss and attribute space confusion. E ${}^{2}$ DM firstly estimates internal relevance (i.e., relevance within the attribute) influenced distance by considering the categorical attribute value frequency and mapping numerical attribute values into multiple bins. Then it takes a wrapper approach to iteratively optimize relevance influenced distance and bin boundaries using a Frobenius-norm deviation as its objective function. Co-occurrence Mover’s Distance is proposed to explicitly explore relevance between attributes in each iteration. Finally, the distance for numerical attribute values is refined based on the original values and the fallen bin centers. Experimental results on a number of real-world datasets demonstrate that E ${}^{2}$ DM outperforms the state-of-the-art methods.

Keywords

Distance measuring mixed data deep relevance learning

1. Introduction

Measuring distance between two objects is a key embedded step of several learning algorithms, including behavior analysis [6], document analysis [25], and image analysis [29]. As the basis of these algorithms, distance metric directly influences the performance of the whole learning task. Real-world data objects are usually represented by a vector with mixed – numerical and categorical – attributes in diverse domains, including finance [7, 1] and intrusion detection [34, 13]. Therefore, it becomes a key research issue to present more appropriate distance metrics for mixed data.

Distance measures of categorical and numerical data are usually distinct. As distance measuring of numerical data is simple and accessible, many widely used distance measures are proposed, such as the commonly used Euclidean and Manhattan distances. In contrast, the distance of categorical data is not straightforward, since the different values of a categorical attribute may not be inherently ordered or comparable. Although there may be no inherent order in categorical data, other factors like matching statistics and frequency distribution exist and thus indicate distance, such as Hamming distance, the Inverse Occurrence Frequency (IOF) and Occurrence Frequency (OF). These distance measures only capture the characteristics within an attribute but ignore the relationships between attributes. The attributes cannot be analyzed in an univariate manner since they are usually related with each other. Simply combining the distance of categorical data and numerical data without considering the relevance leads to poor performance [16].

1.1 A motivating toy example

Taking a fragment of a clothes size as an example (Table 1), six people are characterized by two categorical attributes (“Gender”, “Age”) and two numerical attributes (“Height” and “Weight”). They are divided into two classes (“Size”: $L$ , $X L$ ). Each value only exhibits relevant information of its belonged attribute, but does not reflect any interaction with other variables. Suppose we simply treat the attributes independently during distance computing. Since the distance of “Age”, “Gender” and “Weight” between $p_{1}$ and $p_{2}$ is equal to that between $p_{4}$ and $p_{5}$ , and $(p_{1},p_{2})$ has larger distance in “Height” than $(p_{4},p_{5})$ , which indicates that $p_{4}$ and $p_{5}$ stand a better chance to be clustered into the same group than $p_{1}$ and $p_{2}$ . However, in fact, $p_{1}$ and $p_{2}$ belong to $L$ , $p_{4}$ and $p_{5}$ are labeled $L$ and $X L$ , respectively. Note that the “Gender” of $(p_{1},p_{2})$ and $(p_{4},p_{5})$ are respectively male and female, we need to set different distance computing manners for them from practical aspects.

Table 1
A fragment of an Asian clothes size table

Person	Age	Gender	Height	Weight	Size
$p_{1}$	Young	Male	1.68	61	$L$
$p_{2}$	Youth	Male	1.73	62	$L$
$p_{3}$	Youth	Male	1.73	63	$L$
$p_{4}$	Youth	Female	1.63	48	$L$
$p_{5}$	Youth	Female	1.66	49	$X L$
$p_{6}$	Mid-aged	Female	1.68	50	$X L$

Figure 1.

Differences between existing data transformation based distance measuring method and the proposed end-to-end distance measuring method.

The above example shows that it is problematic to measure the distance for mixed data without considering the relevance between attributes. However, heterogeneity in mixed attributes makes the relevance learning a difficult task. Heterogeneity refers to that data scales/types differ greatly among mixed attributes (e.g., “Gender” and “Height”), which indicates that mixed data cannot be directly manipulated with traditional methods like pure numerical or categorical data. Moreover, the distance measuring for categorical and numerical data are totally different. It is a significant research problem on how to integrate distinct mechanisms of distance computation while handling heterogeneity and relevance simultaneously in an unsupervised manner.

1.2 Major issues and our contributions

To learn the relevance in mixed data, existing methods usually transform the mixed data to uniform (categorical/numerical) data (shown in Fig. 1a). This includes either converting categorical values into numerical values or discretizing continuous attributes into categorical attributes. Many methods attempt to assign numerical values to categorical attributes, such as one-hot [3], if-idf [3] and CDE [22]. The basic operation of them is to transform the categorical attributes into a set of binary attributes.

In this way, the attribute spaces are totally changed and the meanings of attributes are lost, which leads to a confusion in understanding the new attributes.

An alternative idea is to discretize numerical attributes. When discretizing “Height”, 1.68 m and 1.73 m may be put in the same bin or two adjacent bins, depending on the granularity of intervals used. It will inevitably end up in different results. Thus how to set proper discretization intervals is the key step. In unsupervised learning, a variety of discretization methods have been developed for numerical data [24], such as EqualWidth [36], PKID [37] and MVD [4]. Existing methods [19, 21, 20] directly apply discretizers to mixed data without considering relevance between attributes, which leads to an information loss and poor performance. Therefore, the calculation of distance mixed data is not as intuitive as it appears and the relevance within and between attributes has to be appropriately considered.

In this paper, we propose an End-to-End Distance Measuring method for mixed data based on deep relevance learning, called E ${}^{2}$ DM. Unlike existing methods, E ${}^{2}$ DM directly manipulates on the original data with data conversion and relevance learning simultaneously to avoid information loss and attribute space confusion (shown in Fig. 1b). E ${}^{2}$ DM estimates internal relevance (i.e. relevance within the attribute) influenced distance by considering the categorical attribute value frequency and numerical values for categorical and numerical attributes, respectively.

Distances between attribute values are to some degree semantically meaningful, which indicates that relevance analysis only based on co-occurrence frequency is too limited. We first map the numeric values into several intervals through a set of cut points for numeric attributes. Then we calculate the external relevance (i.e. the relevance between attributes) influenced distance based on the divergence between co-occurrence distributions. The co-occurrence distribution is represented as a weighted point cloud of attribute values. The distance between two co-occurrence distribution A and B, which we call the Co-occurrence Mover’s Distance (CMD), is the minimum cumulative distance that attribute values from A need to travel to match the point cloud of B. An iterative computing process based on CMD is conducted to capture the deep relevance. Simultaneously, we rectify the cut points by using a Frobenius-norm deviation measure as its objective function. Finally, the distance for numerical attribute values is refined based on the original values and fallen bin centers. The whole learning process is based on the given data without any domain knowledge.

To summarize, we make the following major contributions:

•
We propose a novel distance measuring method E ${}^{2}$ DM for mixed data. In contrast with existing solutions, E ${}^{2}$ DM directly manipulates on the original data without data conversion to avoid information loss and attribute space confusion. It iteratively optimizes its relevance learning based on CMD, which enables its distance calculation to produce a much more reliable metric.
•
We prove that our algorithm converges and the proposed distance satisfies the axioms of a metric, which allows that it can be used in multiple application scenarios theoretically and practically.

Substantial experiments on a number of real-world datasets across various domains show that E ${}^{2}$ DM (i) obtains better performance by combining with clustering method than several state-of-the-art methods; (ii) achieves better structure than other distance measures; (iii) better handles the heterogeneity than traditional methods; (iv) achieves an acceptable convergence speed.

The remainder of the paper is organized as follows. In Section 2, we discuss the related work. The problem is specified in Section 3. Section 4 introduces the details of E ${}^{2}$ DM. The convergence analysis and proof of metric properties are given in Section 5. We demonstrate the E ${}^{2}$ DM effectiveness and efficiency by experiments and analysis in Section 6. Lastly, conclusions and future work are discussed in Section 7.
2. Related work

Some methods simply combine distance measures computed separately on numerical and categorical attributes, such as k-prototypes [17, 18], K-means-mixed [2], CAVE [15], and INTEGRATE [5]. k-prototypes [17, 18] is an extension of k-means combining the Euclidean Distance on numerical attributes and matching distance on categorical attributes. K-means-mixed [2] is also based on the k-means paradigm and combines distance measures computed separately on numeric attributes and categorical attributes. Unlike k-prototypes, kmeans-mixed does not assume a binary or a discrete measure between two distinct categorical attribute values but computes the distance as a function of their overall distribution and co-occurrence with other categorical attributes. CAVE [15] uses variance to measure the similarity of the numeric part of the data and computes the similarity of the categorical part based on entropy weighted distances in the hierarchies. INTEGRATE [5] applies ideas from information theory to implement the k-means paradigm. It models both numerical and categorical attributes with their probability distributions and minimizes a cost function based on the Minimum Description Length principle for clustering. This kind of independent computing mechanism fails to capture the relevance between attributes and leads to poor performance.

For relevance learning on mixed data, a few methods make a data transformation and then learn attribute relevance on the transformed data. Embedding methods first attempt to transform the categorical attributes into a set of numerical attributes, i.e., one-hot [3] or if-idf [3]. Then the numerical vectors can be directly manipulated per algebraic operations to capture the relevance between attributes. For example, CoupledMC [32] first convert the categorical value to (0, 1) vector by one-hot encoding and learn the relevance based on Pearson Correlation analysis. In this way, the attributes are totally changed and the meaning of attribute is lost, which leads to a confusion in understanding the new attributes. Other methods are proposed based on the discretization process [19, 21, 20], which is another classic method for transforming mixed data [14]. For example, SpectralCAT [20] discretizes numerical features before spectral clustering using an adaptive Gaussian kernel. Fuzzy centroid is adopted in [19] to represent the prototype of a cluster and a new measure is proposed to evaluate the distance between data objects. The distance measure is calculated from a probabilistic perspective in [21]. These methods only focus on the frequency and the semantic distance between attribute values is ignored. Most of them consider the relevance between categorical and numerical features based on the co-occurrence frequency between discretized numerical and categorical attributes. The data transformation process and relevance learning are handled independently.

There are also some clustering methods specially designed for mixed data without distance measuring, including AL [26], EGMCM [30]. AL learns affinities between data points and exploit the learned affinities for clustering. EGMCM models a wide range of dependencies beyond Gaussian mixture copulas captured by meta-Gaussian distributions. These methods have totally different goals with our method.

3. Preliminaries and problem statement

A set of mixed objects is organized as an information table $T=<O,A,V,G>$ . ${O}=\{o_{1},o_{2},\ldots,o_{n}\}$ is composed of a non-empty finite set of data objects. ${A}=\{a_{1},a_{2},\ldots,a_{m}\}$ consists of $m$ finite attributes. ${V}=\cup_{i=1}^{m}{V_{i}}$ is a set of all attribute values, in which ${V_{i}}$ is the set of attribute values of $a_{i}$ . ${G}=\cup_{i=1}^{m}{g_{i}}({g_{i}}:{O}\to{V_{i}})$ is a set of information functions, $g_{i}(o)$ denotes the value of attribute $a_{i}$ in $o$ .

Definition 1. (Occurrence Information Function). The Occurrence Information Function (OIF) sets are defined as $\mathscr{F}=\cup_{i=1}^{m}{f_{i}}({f_{i}}:{V}_{i}\to 2^{\mathscr{O}})$ :

$\displaystyle{f_{i}}(v_{i}^{x})=\{o|{g_{i}}(o)=v_{i}^{x}\}$ (1)

these OIFs describe attribute values occurrence frequency. For instance, in Table 1, the Occurrence Information Function for value $\textit{Male}\in V_{2}$ and $\textit{Female}\in V_{2}$ are $f_{2}(\textit{Male})=3$ , $f_{2}(\textit{Female})=3$ , respectively.

Definition 2. (Co-occurrence Information Function). The Co-occurrence Information Function(CIF) set is defined as $\mathscr{H}=\cup_{i=1}^{m}{H_{i}}$ , here ${H_{i}}=\cup_{j=1}^{m}h_{i\to j}(h_{i\to j}:{V}\to\chi)$ :

$\displaystyle h_{i\to j}(v_{i}^{x})=\chi\sim fr(z)=|\{o|{g_{j}}(o)=z,{g_{i}}(o% )=v_{i}^{x}\}|$ (2)

where $z\in V_{j}$ , $\chi$ is a distribution with frequency function $f r$ , $|\cdot|$ denotes the number of elements in the contained set. The CIF function describes the value distribution of attribute $a_{j}$ within the objects whose $i$ th attribute value is $v_{i}^{x}$ , which captures relevance between attributes on the co-occurrence level. For example, in Table 1, $h_{2\to 1}(\textit{Female})=\chi\sim fr(\textit{Youth})=2,fr(\textit{Mid-aged}% )=1$ .

Accordingly, our goal can be described as: to evaluate the distance between two objects $o_{x},o_{y}\in\mathscr{O}$ , which is built on top of the distance within attribute values $v_{i}^{x},v_{i}^{y}\in{V_{i}}$ for all the attributes $a_{i}(i=1,2,\ldots,m)$ .

Figure 2.

The E ${}^{2}$ DM framework.

4. The E

{}^{\textbf{2}}

DM algorithm

The proposed E ${}^{2}$ DM algorithm learns an effective distance measuring for mixed data by iteratively learning complex relevance. As shown in Fig. 2, E ${}^{2}$ DM starts with two operations: calculating attribute values distance matrix produced by internal relevance learning and mapping numerical values into bins. Then E ${}^{2}$ DM updates the distance matrix by learning external relevance, which is built on our proposed metric, i.e., Co-occurrence Mover’s Distance (CMD). Based on the newly updated distance matrix, the bin centers are refined to minimize the max attribute value distance matrix Frobenius-norm deviation error. These two steps are iteratively performed until the attribute values distance matrices (alternatively the data bin boundaries) remain stable. Finally, the distance for numerical attribute values is rectified based on the original values and fallen bin centers. Essentially, E ${}^{2}$ DM unifies the distance measuring and data discretization with the attribute relevance into one objective function and makes a joint optimization.

The internal relevance learning captures the intrinsic interactions between the values of each attribute, which enables a proper estimation of the value distance in data. As the attributes are relevant with each other, external relevance is thus learned by evaluating the co-occurrence distribution divergence. Dynamic numerical data mapping builds a bridge between discrete and continuous attributes with relevance considered. Such learning process aggregates the complex relevance and offers an effective distance measuring.

4.1 Learning internal relevance

The internal relevance learning process focuses on the influence within the attribute itself. For each numerical attribute $a_{i}$ , considering that the numerical value space is sparse and irregular, we first map the numerical attribute value into $l_{i}$ bins $T_{i}=\{t_{i1},t_{i2},\ldots,t_{il_{i}}\}$ , where $t_{ij}=(b_{i(j-1)},b_{ij}](j=1,2,\ldots,l_{i},b_{i(j-1)}<b_{ij})$ . $b_{i0}$ and $b_{il_{i}}$ are respectively the minimal and maximal value of attribute $a_{i}$ . The initial distance between bins is calculated with bin centers as follows:

$\displaystyle n\odot\textit{dis}(t_{ix},t_{iy})=|c_{ix}-c_{iy}|$ (3)

where ${C_{i}}=\{{c_{ij}}\}(j=1,2,\ldots,{l_{i}})$ , and ${c_{ij}}=({b_{ij}}+{b_{i(j-1)}})/2$ .

In the following relevance learning process, values for numerical attribute are assigned as the bin that the original numerical value falls into. That is to say, $V_{i}=T_{i}$ for each numerical attribute $a_{i}$ . Specially, we finally rectify distance for numerical attributes based on original values and the bins they fall into.

In 1998, Lin [27] presented a powerful distance theorem, which points that the distance between $A$ and $B$ is measured by the difference between the amount of information needed to state the commonality of A and B and the information needed to fully describe what $A$ and $B$ are:

$\displaystyle\textit{dis}(A,B)=I(\textit{desp}(A,B))-I(\textit{common}(A,B))$ (4)

According to [12, 33], the discrepancy in attribute value occurrence times reflects the value distance in term of frequency distribution. It reveals that smaller distance is assigned to the attribute value pair which approximately owns equal frequencies. The higher these frequencies are, the closer the two values are. Inspired by these, we propose Internal Relevance Influenced Distance to satisfy the above principles.

Definition 3. (Internal Relevance Influenced Distance). The Internal Relevance Influenced Distance between value $v_{i}^{x}$ and $v_{i}^{y}$ within a categorical attribute $a_{i}$ is:

$\displaystyle c\odot\textit{dis}(v_{i}^{x},v_{i}^{y})=-\log({p_{i}}(v_{i}^{x})% )-\log({p_{i}}(v_{i}^{y}))+2\cdot\log({p_{i}}(v_{i}^{x})+{p_{i}}(v_{i}^{y}))-\epsilon$ (5) $\displaystyle p_{i}(v_{i}^{z})=|{f_{i}}(v_{i}^{z})|/n(z=x,y)$

The above equation is an instance of Eq. (4). Here we define the commonality as “the value of attribute $a_{i}$ is between $\{v_{i}^{x},v_{i}^{y}\}$ ”, then the probability is $(p(a)+p(b))^{2}$ . We use self-information ( $I(x)=-\log(p(x))$ ) to materialize the definition. And $\epsilon=2\log 2$ is for normalization. Take $L$ and $X L$ in Table 1 as an example, the internal relevance between them is $c\odot\textit{dis}(\textit{Youth},\textit{Mid-aged})=-\log(1/6)-\log(5/6)+2% \log(1/6+5/6)-2\log 2=0.588$ .

Then we construct the internal relevance influenced value distance matrix ${D}_{i}^{in}$ for each attribute $a_{i}$ as follows:

$\displaystyle{D}_{i}^{in}=\left[{\begin{array}[]{*{20}{c}}{\varphi^{in}\left(v% _{i}^{1},v_{i}^{1}\right)}&\cdots&{\varphi^{in}\left(v_{i}^{1},v_{i}^{{|V_{i}|% }}\right)}\\ \vdots&\ddots&\vdots\\ {\varphi^{in}\left(v_{i}^{{|V_{i}|}},v_{i}^{1}\right)}&\cdots&{\varphi^{in}% \left(v_{i}^{{|V_{i}|}},v_{i}^{{|V_{i}|}}\right)}\\ \end{array}}\right]$ (6)

where

$\displaystyle\varphi^{in}(v_{i}^{x},v_{i}^{y})=\left\{\begin{array}[]{ll}c% \odot\textit{dis}(v_{i}^{x},v_{i}^{y}),&\textit{if}\;{a_{i}}\;\textit{is % categorical}\\ n\odot\textit{dis}(v_{i}^{x},v_{i}^{y}),&\textit{otherwise}.\\ \end{array}\right.$

4.2 Learning external relevance

Since the internal relevance learning does not involve the relevance between attributes when calculating the value distance for each attribute, the external relevance learning aims to capture the interactions with other attributes. We regard this interaction between attributes as external relevance influenced distance in terms of the distribution comparisons. For this, we discuss how the relevance influences the value distance by proposing Co-occurrence Mover’s Distance (CMD).

When calculating the influence of attribute $a_{j}(j\neq i)$ on value distance of $a_{i}$ , we are provided with two co-occurrence distributions $h_{i\to j}(v_{i}^{x}),h_{i\to j}(v_{i}^{y})\in R^{|V_{j}|}$ ( $\chi(x),\chi(y)$ for short) for attribute values $v_{i}^{x}$ and $v_{i}^{y}$ (e.g., Male and Female in Table 1) based on another attribute $a_{j}$ (e.g., “Height” in Table 1). The $k$ th element, $e_{k}\in\chi(z)(z=x,y)$ , represents the co-occurrence frequency between $k$ th value in $V_{j}$ and attribute value $v_{i}^{z}$ in $V_{i}$ .

Value travel cost. The goal is to incorporate the semantic distance between individual values pairs (e.g., Male and Female) into the co-occurrence distribution distance. Specially, the value cost matrix ${D}$ here is also the value distance matrix of attribute $a_{j}$ we are obtaining. It is initialized by the internal relevance learning process and updated with this external relevance learning process in each iteration.

Co-occurrence distribution distance. The “travel cost” between two attribute values is a natural building block to create a distance between two co-occurrence distribution. First, we allow each value in $\chi(x)$ to be transformed into any value in $\chi(y)$ . Let $T\in N^{|V_{j}|*|V_{j}|}$ be a flow matrix where $T_{pq}\geqslant 0$ denotes how much of $p$ th value in $\chi(x)$ travels to $q$ th value in $\chi(y)$ . To transform $\chi(x)$ into $\chi(y)$ we ensure that the entire outgoing flow from $p$ th value is no more than $\chi(x)_{p}$ , i.e. $\sum\nolimits_{q}T_{pq}\leqslant\chi(x)_{p}$ . Further, we have $\sum\nolimits_{p}T_{pq}\leqslant\chi(y)_{q}$ . Then we can define the distance between the two co-occurrence distribution as the minimum cumulative cost required to move all values from $\chi(x)$ to $\chi(y)$ , i.e., $\sum\nolimits_{p,q}T_{pq}{D}_{pq}$ . Additionally, the frequency of $v_{i}^{x}$ may not be equal to that of $v_{i}^{y}$ , which indicates that the total flow of $\chi(x)$ does not match that of $\chi(y)$ . For generality and simplicity, we treat the unit cost of excess flow as the average cost of the maximum and minimum cost in the matrix.

Transportation problem. Formally, the minimum cumulative cost of moving $\chi(x)$ to $\chi(y)$ given the constraints is provided by the solution to the following linear program:

$\displaystyle\textit{cmd}(\chi(x),\chi(y),{D})=\frac{\min\limits_{T\geqslant 0% }\sum\limits_{p,q}T_{pq}{D}_{pq}+\textit{avg}({D})*e}{\max\left(\sum\limits_{p% }\chi(x)_{p},\sum\limits_{p}\chi(y)_{p}\right)}$ $\displaystyle\textbf{{s.t.}}:\;\;\;\;\;\;\sum\limits_{q}T_{pq}\leqslant\chi(x)% _{p},\sum\limits_{p}T_{pq}\leqslant\chi(y)_{q}$ $\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\textit{avg}({D})=(\max({D})+\min({% D}))/2$ (7) $\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;e=\sum\limits_{p}\chi(x)_{p}-\sum% \limits_{p}\chi(y)_{p}$ $\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{p,q}T_{pq}=\min\left(% \sum\limits_{p}\chi(x)_{p},\sum\limits_{p}\chi(y)_{p}\right)$

The above optimization is a variant of the earth mover’s distance metric (EMD) [31], a well studied optimal transportation problem for which specialized solvers have been developed [25, 23]. According the properties of EMD, it can be proved that CMD is a true metric (Section Theoretical Analysis).

We use normalized mutual information [11] $\tau$ to reflect the relation between two attributes. And $w_{ij}=\tau({a_{i}},{a_{j}})/\sum\nolimits_{j=1}^{m}\tau({a_{i}},{a_{j}})(1% \leqslant i,j\leqslant m)$ is normalized attribute weight ( $\tau({a_{i}},{a_{i}})=1$ ). Based on these, we propose External Relevance Influenced Distance to update the value distance matrix.

Definition 4. (External Relevance Influenced Distance). The External Relevance Influenced Distance between value $v_{i}^{x}$ and $v_{i}^{y}$ within attribute $a_{i}$ is the sum of influenced distance by other attributes:

$\displaystyle{\varphi^{ex}}(v_{i}^{x},v_{i}^{y})=\left(1-\beta\sum\limits_{j=1% ,j\neq i}^{m}w_{ij}\right)\varphi^{ex}(v_{i}^{x},v_{i}^{y})+\beta\sum\limits_{% j=1,j\neq i}^{m}w_{ij}*\textit{cmd}(\chi(x),\chi(y),{D}_{j}^{ex})$ (8)

where $\chi(x)={h_{i\to j}}(v_{i}^{x}),\chi(y)={h_{i\to j}}(v_{i}^{y})$ . And $\beta$ denotes the influence factor which is decreasing at a constant rate (e.g., $\beta=\beta*0.95$ ). This is in accordance with theoretical analysis: the influence gets weaker with transit length among attributes (the iteration depth) growing. We still take the distance between $L$ and $X L$ in Table 1 for example, $\varphi^{ex}(\textit{Youth},\textit{Mid-aged})=(1-0.5*0.738)*0.589+0.5*(0.318*% 0.497+0.225*0.657+0.195*0.524)=0.576$ .

Thus we can update our external distance matrix:

$\displaystyle{D}_{i}^{ex}{\rm{=}}\left[{\begin{array}[]{*{20}{c}}{\varphi^{ex}% \left(v_{i}^{1},v_{i}^{1}\right)}&\cdots&{\varphi^{ex}\left(v_{i}^{1},v_{i}^{{% |V_{i}|}}\right)}\\ \vdots&\ddots&\vdots\\ {\varphi^{ex}\left(v_{i}^{{|V_{i}|}},v_{i}^{1}\right)}&\cdots&{\varphi^{ex}% \left(v_{i}^{{|V_{i}|}},v_{i}^{{|V_{i}|}}\right)}\\ \end{array}}\right]$ (9)

CMD has several intriguing properties: (i) it is highly interpretable as the distance between two co-occurrence distribution takes the difference of attribute values into account; (ii) it gets optimized as the value distance updates, this iterative computing process can mine high-order relevance among multiple attributes; (iii) it is hyper-parameter free and straight-forward to understand and use; (iv) it naturally incorporates the properties in EMD and leads to a true distance metric.

4.3 Dynamic numerical data mapping

In the mapping process, the gaps for bin centers are calculated by provided distance. As the external relevance learning process updates the attribute value distance matrix ${D}_{i}^{ex}$ for each attribute $a_{i}$ . The gaps for bin centers need to be accordingly recalculated. The goal is to approximate bin center distance matrix to the newly learned distance matrix. We use the Frobenius-norm on matrix to estimate the deviation:

$\displaystyle C_{i}=\mathop{\arg\min}\limits_{{C_{i}}}||c\odot\textit{dis}(a_{% i})-{D}_{i}^{ex}||_{F}$ $\displaystyle\textbf{{s.t.}}:2\sum\limits_{k=1}^{l_{i}}(-1)^{(l_{i}-k)}c_{ik}+% (-1)^{l_{i}}b_{i0}=b_{il_{i}}$ (10) $\displaystyle 2\sum\limits_{k=1}^{p}(-1)^{(p-k)}c_{ik}+(-1)^{p}b_{i0}>c_{p}(1% \leqslant p\leqslant l_{i})$

The two constraint inequations are the conditions that valid intervals boundaries need to be satisfied. It is a quadratic function and can be easily solved. Accordingly, we obtain the new interval cut points with the new bin boundaries as follows:

$\displaystyle b_{ik}=2c_{ik}-b_{i(k-1)}(k=1,2,\ldots,l_{i}-1)$ (11)

here $b_{i0},b_{il_{i}}$ are fixed. Thus the bin boundaries of each numerical attribute change so that the bin value is also updated. The new values are fed into the external relevance learning process until convergence.

4.4 Deep relevance learning algorithm

Algorithm 1 presents the main procedures of the whole learning process. The first step is to generate the initialized bin boundaries with EqualWidth. For each attribute $a_{i}$ , steps (2–5) are performed to generate the internal relevance influenced distance matrix ${{D}}_{i}^{in}$ . Specially, considering that the data scales/types are different, we normalized the distance matrix to initialize the external relevance influenced distance matrix ${{D}}_{i}^{ex}$ . As shown in steps (6–12), we obtain the co-occurrence distribution and update ${{D}}_{i}^{ex}$ based on CMD computing. Lastly, the discretization interval is refined to adapt to the new distance matrix. The learning process is repeated until convergence.

Iterative relevance learning algorithm[1] Information Table $\mathscr{T}$ ; Value Distance Matrices ${{D}_{i}}(1\leqslant i\leqslant m)$ ; initialize bin boundaries for each numerical attribute; map numerical value into bins to get new Information Table; $i=1$ to $m$ compute ${{D}}_{i}^{in}$ with Eq. (6); initialize ${{D}}_{i}^{ex}=\eta({{D}}_{i}^{in})$ ; $i=1$ to $m$ obtain $H_{i}$ ; update ${{D}}_{i}^{ex}$ with Eq. (8); $\beta=\beta*0.95$ ; rectify discretization scheme with Eq. (4.3); convergence, e.g., $\mathop{\max}\limits_{i}||{{D}}^{ex}_{i}(t)-{{D}}^{ex}_{i}(t-1)|{|^{2}}<10^{-3}$ or reach the maximum iteration $I_{\max}=100$ ; ${{D}}^{ex}_{i}(1\leqslant i\leqslant m)$ ;

After this whole learning process, we get the iterative relevance influenced distance for categorical attributes values and numerical bin values. Considering that the original numerical values are different with the bin values, we refine the distance numerical values based on original values and the bin value they fall into for each numerical attribute $a_{i}$ :

$\displaystyle\varphi^{ex}(v_{i}^{x},v_{i}^{y})=\varphi^{ex}(\textit{map}(v_{i}% ^{x}),\textit{map}(v_{i}^{y}))*\frac{|v_{i}^{x}-v_{i}^{y}|}{\varphi^{in}(% \textit{map}(v_{i}^{x}),\textit{map}(v_{i}^{y}))}$ (12)

here $\textit{map}(v_{i}^{z})$ denotes the bin that $v_{i}^{z}$ falls into.

Finally, we can define iterative relevance influenced distance between objects as follows:

Definition 5. (Deep Relevance Influenced Distance). The Deep Relevance Influenced Distance between objects $o_{x}$ and $o_{y}$ is the sum of all attributes values distance:

$\displaystyle{\Psi^{D}(o_{x},o_{y})}=\sum\limits_{i=1}^{m}{{\alpha_{i}}}{% \varphi^{ex}}({g_{i}}({o_{x}}),{g_{i}}({o_{y}}))$ (13)

Specially, this calculating process is based on the original values for all the numerical values. Considering that the relevance between attributes has been taken account into the learning process, we can assume that external relevance influenced distances are independent with each other. Therefore, we set $\alpha_{i}=1/m$ for each attribute $a_{i}(1\leqslant i\leqslant m)$ . At last, we take the distance between $p_{1}$ and $p_{6}$ for as an example, $\Psi^{D}(o_{x},o_{y})=0.25*0.576+0.25*0+0.25*0.137+0.25*0.167=0.22$ .

5. Theoretical analysis

Considering that the convergence of the algorithm can guarantee that the proposed method works and a true distance metric would be much more meaningful in real world applications, we give both the proofs in the following.

5.1 Convergence proof

Theorem 1. Deep relevance learning algorithm converges.

Based on Eq. (8), the variance for external relevance influenced distance between $v_{i}^{x}$ and $v_{i}^{y}$ in $t$ tn iteration is:

$\displaystyle\Delta({\varphi^{ex}}(v_{i}^{x},v_{i}^{y}),t)=|{\varphi^{ex}}(v_{% i}^{x},v_{i}^{y})(t)-{\varphi^{ex}}(v_{i}^{x},v_{i}^{y})(t-1)|$ $\displaystyle=\left|\beta\sum\limits_{j=1,j\neq i}^{m}w_{ij}(\varphi^{ex}(v_{i% }^{x},v_{i}^{y})(t-1)-\textit{cmd}(\chi(x),\chi(y),{D}_{j}^{ex}(t-1)))\right|$ $\displaystyle\leqslant\beta\sum\limits_{j=1,j\neq i}^{m}w_{ij}(|(\varphi^{ex}(% v_{i}^{x},v_{i}^{y})(t-1)|+\textit{cmd}(\chi(x),\chi(y),{D}_{j}^{ex}(t-1))))$ $\displaystyle\leqslant 2\beta*\sum\limits_{j=1,j\neq i}^{m}w_{ij}\max({D}_{j}^% {ex}(t-1))$

As ${D}_{j}^{ex}$ is a normalized matrix and $\beta$ is decreasing at a constant rate, we have:

$\displaystyle\Delta({\varphi^{ex}}(v_{i}^{x},v_{i}^{y}),t)\leqslant 2\beta% \buildrel{t\to\infty}\over{\longrightarrow}0$

5.2 True metric proof

Lemma 1. Let $A, B, C$ be three distributions (vectors) in $(N)^{n}$ and ${D}={d_{ij}}\in(R)^{n*n}$ be the distance metric matrix, then:

$\displaystyle\textit{cmd}(A,B,{{D}})+\textit{cmd}(B,C,{{D}})\geqslant\textit{% cmd}(A,C,{{D}})$

Let $\widetilde{{D}}=\widetilde{d}_{ij}$ be an $(n+1)*(n+1)$ distance matrix such that:

$\displaystyle{\widetilde{{D}}_{ij}}=\left[{\begin{array}[]{*{20}{c}}{{d_{11}}}% &\cdots&{{d_{1n}}}&{{m}}\\ \vdots&\ddots&\vdots&\vdots\\ {{d_{n1}}}&\cdots&{{d_{nn}}}&{{m}}\\ {{m}}&\cdots&{{m}}&0\\ \end{array}}\right]$

where $m=\textit{avg}({D})$ is average value of ${D}$ .

Let $K=\max(\sum\nolimits_{i=1}^{n}{{A_{i}}},\sum\nolimits_{i=1}^{n}{{B_{i}}},\sum% \nolimits_{i=1}^{n}{{C_{i}}})$ , then we define three vectors in $(N)^{n+1}$ :

$\displaystyle\widetilde{A}=\left[A,K-\sum\limits_{i=1}^{n}{{A_{i}}}\right]$ $\displaystyle\widetilde{B}=\left[B,K-\sum\limits_{i=1}^{n}{{B_{i}}}\right]$ $\displaystyle\widetilde{C}=\left[C,K-\sum\limits_{i=1}^{n}{{C_{i}}}\right]$

The sum of each of the three vectors equals $K$ . In addition:

$\displaystyle\textit{cmd}(A,B,{{D}})=\textit{emd}(\widetilde{A},\widetilde{B},% \widetilde{{D}})*K$ $\displaystyle\textit{cmd}(B,C,{{D}})=\textit{emd}(\widetilde{B},\widetilde{C},% \widetilde{{D}})*K$ $\displaystyle\textit{cmd}(A,C,{{D}})=\textit{emd}(\widetilde{A},\widetilde{C},% \widetilde{{D}})*K$

Rubner et al. [31] proved that the triangle inequality holds for EMD when the ground distance is a metric and the histograms are normalized. $\widetilde{A}$ , $\widetilde{B}$ , $\widetilde{C}$ are normalized histograms and $\widetilde{{D}}_{j}$ is a distance matrix (an enumeration of all cases proves this). Thus we get:

$\displaystyle\textit{emd}(\widetilde{A},\widetilde{B},\widetilde{{D}})+\textit% {emd}(\widetilde{B},\widetilde{C},\widetilde{{D}})\geqslant\textit{emd}(% \widetilde{A},\widetilde{C},\widetilde{{D}})$ $\displaystyle\textit{cmd}(A,B,{{D}})+\textit{cmd}(B,C,{{D}})\geqslant\textit{% cmd}(A,C,{{D}})$

Theorem 2. The iterative relevance influenced distance is a true metric.

To prove the above theorem, we should prove that $\Psi^{D}$ satisfies the following axioms:

(1)
$\Psi^{D}(o_{x},o_{y})\geqslant 0$ ;
(2)
$\Psi^{D}(o_{x},o_{y})=0$ if and only if $o_{x}=o_{y}$ ;
(3)
$\Psi^{D}(o_{x},o_{y})=\Psi^{D}(o_{y},o_{x})$ ;
(4)
$\Psi^{D}(o_{x},o_{y})+\Psi^{D}(o_{y},o_{z})\geqslant\Psi^{D}(o_{x},o_{z})$ ;

It can be easily derived that the internal relevance distance satisfies conditions (1)–(3), we only need to prove that it satisfies condition (4), which can be proved with mathematical induction. For each attribute $a_{j}$ :

i)
According to the constructing process of internal relevance influence distance, we can obtain that $\varphi^{in}(v_{j}^{x},v_{j}^{y})+\varphi^{in}(v_{j}^{y},v_{j}^{z})\geqslant% \varphi^{in}(v_{j}^{x},v_{j}^{z})$ ;
ii)
According to Lemma 1, we have:

$\displaystyle\varphi^{ex}(v_{j}^{x},v_{j}^{y})+\varphi^{ex}(v_{j}^{y},v_{j}^{z% })\geqslant\varphi^{ex}(v_{j}^{x},v_{j}^{z})$

Based on Eq. (13), we can easily obtain the theorem.
6. Experiment and evaluation

6.1 Experiments settings

6.1.1 Datasets

Eight datasets obtained from the UCI repository are used to evaluate the performance. The detailed information of these data sets is summarized in Table 2.

6.1.2 Parameters settings

Two parameters need to be specified for the experiments: the mapping bin number $l_{i}$ and influence factor $\beta$ . For fairness with categorical, $l_{i}$ is assigned as the average number of values in categorical attributes. $\beta$ is assigned as 0.5 for the trade-off between internal and external relevance.

Table 2
The detailed information of data sets

Data	Name	$n$	$m_{c}$	$m_{d}$	$L$
A	Zoo	101	1	16	7
B	Echocardiogram	131	8	2	2
C	Teach	151	1	4	3
D	Hepatitis	270	6	13	2
E	Heart desease	303	5	8	2
F	Credit	663	6	9	2
G	Contraceptive	1473	2	7	3
H	Abalone	4168	7	1	21

$n$ : number of objects, $m_{c}$ : number of numerical attributes, $m_{d}$ : number of categorical attributes, $L$ : number of classes.

6.2 Performance evaluation methods

To investigate the effectiveness of the unsupervised distance metric for the mixed data proposed in this paper, four different kinds of experiments have been conducted as follows.

•
To evaluate its performance in clustering, we feed E ${}^{2}$ DM into spectral-clustering (SC) and compare it with existing clustering methods.
•
To investigate its effectiveness in cluster structure analysis, we specify the internal data structure of different distance measures with given labels.
•
To test the ability in handling heterogeneity, we compare clustering performance of E ${}^{2}$ DM and the combination of deep relevance learning (DRL for short) and other traditional data discretization methods.
•
To examine the efficiency of E ${}^{2}$ DM, we make a convergence test by tracking the maximal distance matrix deviation.

Table 3
Clustering performance of algorithms SpectralCAT, CoupledMC, EGMCM and E ${}^{2}$ DM; UCI datasets details in Table 2. The best two results for each dataset (highest AMI, ARI) in bold

Data Metric SpectralCAT CoupledMC EGMCM E ${}^{2}$ DM

A AMI 0.03 0.02 0.06 0.09

ARI 0.01 0.04 0.01 0.04

B AMI 0.02 0.05 0.04 0.14

ARI 0.09 0.18 0.14 0.23

C AMI 0 0.02 0.04 0.06

ARI 0 0.02 0.03 0.03

D AMI 0.05 0.10 0.16 0.19

ARI 0.09 0.12 0.18 0.21

E AMI 0.13 0.15 0.23 0.35

ARI 0.15 0.16 0.12 0.23

F AMI 0.01 0.05 0.03 0.10

ARI 0.03 0.04 0.03 0.07

G AMI 0 0.01 0.04 0.04

ARI 0 0.01 0.05 0.05

H AMI 0.08 0.14 0.16 0.19

ARI 0.06 0.06 0.16 0.15

6.3 Results and findings

Data	Metric	SpectralCAT	CoupledMC	EGMCM	E ${}^{2}$ DM
A	AMI	0.03	0.02	0.06	0.09
	ARI	0.01	0.04	0.01	0.04
B	AMI	0.02	0.05	0.04	0.14
	ARI	0.09	0.18	0.14	0.23
C	AMI	0	0.02	0.04	0.06
	ARI	0	0.02	0.03	0.03
D	AMI	0.05	0.10	0.16	0.19
	ARI	0.09	0.12	0.18	0.21
E	AMI	0.13	0.15	0.23	0.35
	ARI	0.15	0.16	0.12	0.23
F	AMI	0.01	0.05	0.03	0.10
	ARI	0.03	0.04	0.03	0.07
G	AMI	0	0.01	0.04	0.04
	ARI	0	0.01	0.05	0.05
H	AMI	0.08	0.14	0.16	0.19
	ARI	0.06	0.06	0.16	0.15

6.3.1 Obtaining better performance by combining with clustering methods

We use three state-of-the-art algorithms on mixed data, i.e., SpectralCAT [9], CoupledMC [32] and EGMCM [30], as comparisons. SpectralCAT is chosen as the representative method of simply combining discretizing and co-occurrence analysis. CoupleMC is a state-of-the-art embedding method which is based on one-hot conversation. And EGMCM is a state-of-the-art clustering method for mixed data.

Adjusted Rand Index (ARI) and Adjusted Mutual Information (AMI) [10] are used for evaluation, whose higher values indicate better clustering performance. Table 3 reports the results. The two highest measure scores of each experimental setting are highlighted in boldface. It is interesting to note that almost every method performs better than at least one of other methods on one or two datasets. This reflects the difficulty in effectively capturing the intrinsic data characteristics in mixed data and the significant challenge in designing appropriate and generalized distance measures for mixed data. This table shows that E ${}^{2}$ DM is always in the first two positions; it outperforms significantly better than the other methods.

Table 4
Clustering performance of algorithms DRL $+$ EqualWidth, DRL $+$ EqualFrequency, DRL $+$ PKID (D $+$ EW, D $+$ EF, D $+$ P for short, respectively) and E ${}^{2}$ DM; UCI datasets details in Table 2

Data	Metric	D $+$ EW	D $+$ EF	D $+$ P	E ${}^{2}$ DM
A	AMI	0.03	0.02	0.03	0.09
	ARI	0.01	0.02	0.01	0.04
B	AMI	0.02	0.05	0.09	0.14
	ARI	0	0.18	0.14	0.23
C	AMI	0.03	0.02	0.04	0.06
	ARI	0.03	0.02	0.03	0.03
D	AMI	0.15	0.21	0.16	0.19
	ARI	0.19	0.24	0.18	0.21
E	AMI	0.13	0.15	0.27	0.35
	ARI	0.15	0.06	0.16	0.23
F	AMI	0.02	0.04	0.02	0.10
	ARI	0	0.03	0.03	0.07
G	AMI	0	0.01	0	0.04
	ARI	0	0.01	0.01	0.05
H	AMI	0.11	0.08	0.06	0.19
	ARI	0.13	0.07	0.06	0.15

Figure 3.

Data structure index comparisons on 8 data sets.

6.3.2 Achieving better cluster structure than other distance measures

It is known that a cluster partition on a data set is to ensure that the distances between objects in the same cluster are low while the distances between objects in different clusters are high. Relative Distance (RD), Davies-Bouldin Index (DBI), Dunn Index (DI) are three of the most popular evaluation measures [32, 38]. Since internal criteria seek clusters with low intra-cluster distance and high inter-cluster distance, distance metrics that produce clusters with high RD or DI and low DBI are more desirable. During the experiments, we find that there are several noise objects in the datasets, which refers to that two objects with almost identical attributes values have different labels. This leads to a poor judgment of DI. Here we only report the results of RD and DBI.

Our method is evaluated against three methods: original objects as the baseline, one-hot encoding and coupledMC. The cluster structures produced on 8 data sets are shown in Fig. 3. With the exception of only a few items, E ${}^{2}$ DM has larger RD and smaller DBI than the others. It shows our proposed distance metric, which effectively captures the complex relevance within and between mixed attributes, is superior to the others in terms of differentiating objects in distinct clusters.

Figure 4.

Convergence test on datasets zoo and abalone.

6.3.3 Better handling the heterogeneity than traditional methods

To test the ability in handing the heterogeneity, we combine iterative relevance learning with three outlying data discretization methods, i.e., EqualWidth, EqualFrequency and PKID, as competitors. We apply the distance metric obtained by E ${}^{2}$ DM and other three competitors in spectral clustering. The results in Table 4 show that E ${}^{2}$ DM obtains significantly better performance than the competitors, which supports the superiority of E ${}^{2}$ DM in handling the heterogeneity.

6.3.4 Achieving an acceptable convergence speed

The maximal distance matrix deviation among all the attributes varies with representations from each iteration. Here, we report the convergence speed of the maximal distance matrix deviation on datasets zoo and abalone. Similar results can be obtained on other datasets. As Fig. 4 shows, the clustering performance converges within 20 iterations.

7. Conclusion and future work

We have proposed E ${}^{2}$ DM, an effective distance measuring for mixed data by simultaneously learning deep relevance and rectifying data discretization. E ${}^{2}$ DM successfully captures the complex relevance between heterogeneous attributes, which includes internal and external relevance, based on iterative CMD computing. Simultaneously, a dynamic numerical data mapping is conducted to update distance matrices in each iteration. Finally, the distance for numerical attribute values is refined based on the original values and fallen bin centers. Experimental results on a number of datasets demonstrate that the E ${}^{2}$ DM is effective for mixed data distance measuring and outperforms state-of-the-art methods.

A limitation of CMD is that it is computationally challenging just like EMD. Thus several optimization methods are proposed on EMD. We are planning to immigrate these method into E ${}^{2}$ DM. Considering that leaning the relevance between heterogeneous attributes is a difficult task and also a key influence factor in many data mining tasks, we are currently applying the E ${}^{2}$ DM to feature selection, outlier detection and sequential data analysis in mixed data [35].

Footnotes

Acknowledgments

This work was supported by the National Key Research and Development Program of China (2016 YFB1000101), the National Natural Science Foundation of China (Grant No. 61379052), the Natural Science Foundation for Distinguished Young Scholars of Hunan Province (Grant No. 14JJ1026), the Science Foundation of Ministry of Education of China (Grant No. 2018A02002).

References

Wang

et al., A survey of queries over uncertain data, Knowledge and Information Systems 37(3) (2013), 485–530.

Ahmad

and Dey

, A k-mean clustering algorithm for mixed numeric and categorical data, Data & Knowledge Engineering 63(2) (2007), 503–527.

Aizawa

, An information-theoretic perspective of tf-idf measures, Information Processing & Management 39(1) (2003), 45–65.

Bay

S.D.

, Multivariate discretization for set mining, Knowledge and Information Systems 3(4) (2001), 491–512.

Bohm

et al., Integrative parameter-free clustering of data with mixed type attributes, in: Pacific-asia Conference on Knowledge Discovery and Data Mining, Springer, 2010, pp. 38–47.

Cao

and Yu

P.S.

, Coupled behavior analysis with applications, IEEE Transactions on Knowledge and Data Engineering 24(8) (2012), 1378–1392.

Cao

et al., Detecting abnormal coupled sequences and sequence changes in group-based manipulative trading behaviors, in: International Conference on Knowledge Discovery and Data Mining, ACM, 2010, pp. 85–94.

Cheung

Y.M.

and Jia

, Categorical-and-numerical-attribute data clustering based on a unified similarity metric without knowing cluster number, Pattern Recognition 46(8) (2013), 2228–2238.

David

and Averbuch

, SpectralCAT: categorical spectral clustering of numerical and nominal data, Pattern Recognition 45(1) (2012), 416–433.

10.

Davies

D.L.

and Bouldin

D.W.

, A cluster separation measure, IEEE Transactions on Pattern Analysis and Machine Intelligence 2 (1979), 224–227.

11.

Estévez

P.A.

et al., Normalized mutual information feature selection, IEEE Transactions on Neural Networks 20(2) (2009), 189–201.

12.

Gan

and Wu

, Data clustering: theory, algorithms, and applications, Siam, 2007.

13.

Wang

and Ma

, A general scalable and elastic content-based publish/subscribe service, IEEE Transactions on Parallel and Distributed Systems 26(8) (2015), 2100–2113.

14.

Garcia

et al., A survey of discretization techniques: taxonomy and empirical analysis in supervised learning, IEEE Transactions on Knowledge and Data Engineering 25(4) (2013), 734–750.

15.

Hsu

C.C.

and Chen

Y.C.

, Mining of mixed data with application to catalog marketing, Expert Systems with Applications 32(1) (2007), 12–23.

16.

Wang

et al., Ta-update: an adaptive update scheme with tree-structured transmission in erasure-coded storage systems, IEEE Transactions on Parallel and Distributed Systems 29(8) (2018), 1893–1906.

17.

Huang

, Clustering large data sets with mixed numeric and categorical values, in: Pacific-asia Conference on Knowledge Discovery and Data Mining, ACM, 1997, pp. 21–34.

18.

Huang

, Extensions to the k-means algorithm for clustering large data sets with categorical values, Data Mining and Knowledge Discovery 2(3) (1998), 283–304.

19.

et al., A fuzzy k-prototype clustering algorithm for mixed numeric and categorical data, Knowledge-Based Systems 30 (2012), 129–135.

20.

Jia

and Cheung

Y.M.

, Subspace clustering of categorical and numerical data with an unknown number of clusters, IEEE Transactions on Neural Networks and Learning Systems 29(8) (2018), 3308–3325.

21.

Jia

Cheung

and Liu

, A new distance metric for unsupervised learning of categorical data, IEEE Transactions on Neural Networks and Learning Systems 27(5) (2016), 1065–1079.

22.

Jian

et al., Embedding-based representation of categorical data by hierarchical value coupling learning, in: International Joint Conference on Artificial Intelligence, AAAI, 2017, pp. 1937–1943.

23.

Kumar

Chakrabarti

and Roy

, Earth Mover’s Distance Pooling over Siamese LSTMs for Automatic Short Answer Grading, in: International Joint Conference on Artificial Intelligence, AAAI, 2017, pp. 2046–2052.

24.

Kurgan

L.A.

and Cios

K.J.

, CAIM discretization algorithm, IEEE Transactions on Knowledge and Data Engineering 16(2) (2004), 145–153.

25.

Kusner

et al., From word embeddings to document distances, in: International Conference on Machine Learning, MIT, 2015, pp. 957–966.

26.

and Latecki

L.J.

, Affinity learning for mixed data clustering, in: International Joint Conference on Artificial Intelligence, AAAI, 2017, pp. 2173–2179.

27.

Lin

, An information-theoretic definition of similarity, in: International Conference on Machine Learning, MIT, 1998, pp. 296–304.

28.

Luo

Kong

and Li

, Clustering mixed data based on evidence accumulation, in: International Conference on Advanced Data Mining and Applications, Springer, 2006, pp. 348–355.

29.

Pele

and Werman

, A linear time histogram metric for improved sift matching, in: European Conference on Computer Vision, Springer, 2008, pp. 495–508.

30.

Rajan

and Bhattacharya

, Dependency Clustering of Mixed Data with Gaussian Mixture Copulas, in: International Joint Conference on Artificial Intelligence, AAAI, 2016, pp. 1967–1973.

31.

Rubner

Tomasi

and Guibas

L.J.

, The earth mover’s distance as a metric for image retrieval, International Journal of Computer Vision 40(2) (2000), 99–121.

32.

Wang

et al., Coupled Interdependent Attribute Analysis on Mixed Data, in: AAAI Conference on Artificial Intelligence, AAAI, 2015, pp. 1861–1867.

33.

Wang

et al., Coupled attribute similarity learning on categorical data, IEEE Transactions on Neural Networks and Learning Systems 26(4) (2015), 781–797.

34.

Weller-Fahy

D.J.

Borghetti

B.J.

and Sodemann

A.A.

, A survey of distance and similarity measures used within network intrusion anomaly detection, IEEE Communications Surveys & Tutorials 17(1) (2015), 70–91.

35.

Wang

and Li

, Research and performance evaluation of data replication technology in distributed storage systems, Computers & Mathematics with Applications 51(11) (2006), 1625–1632.

36.

Wong

A.K.C

and Chiu

D.K.Y

, Synthesizing statistical knowledge from incomplete mixed-mode data, IEEE transactions on Pattern Analysis and Machine Intelligence, 6 (1987).

37.

Yang

and Webb

G.I.

, Discretization for naive-Bayes learning: managing discretization bias and variance, Machine Learning 74(1) (2009), 39–74.

38.

Zhu

et al., Heterogeneous metric learning of categorical data with hierarchical couplings, IEEE Transactions on Knowledge and Data Engineering 30(7) (2018), 1254–1267.

An end-to-end distance measuring for mixed data based on deep relevance learning

Abstract

Keywords

1. Introduction

1.1 A motivating toy example

Table 1 A fragment of an Asian clothes size table

3. Preliminaries and problem statement

4.1 Learning internal relevance

5.1 Convergence proof

5.2 True metric proof

6.1 Experiments settings

6.1.1 Datasets

6.1.2 Parameters settings

Table 2 The detailed information of data sets

6.3.1 Obtaining better performance by combining with clustering methods

Table 4 Clustering performance of algorithms DRL + EqualWidth, DRL + EqualFrequency, DRL + PKID (D + EW, D + EF, D + P for short, respectively) and E 2 DM; UCI datasets details in Table 2

6.3.4 Achieving an acceptable convergence speed

7. Conclusion and future work

Footnotes

Acknowledgments

References

Table 1
A fragment of an Asian clothes size table

Table 2
The detailed information of data sets

Table 4
Clustering performance of algorithms DRL $+$ EqualWidth, DRL $+$ EqualFrequency, DRL $+$ PKID (D $+$ EW, D $+$ EF, D $+$ P for short, respectively) and E ${}^{2}$ DM; UCI datasets details in Table 2