Automatic Threshold Calculation for the Categorical Distance Measure ConDist

Abstract

The measurement of distances between objects described by categorical attributes is a key challenge in data mining. The unsupervised distance measure ConDist approaches this challenge based on the idea that categorical values within an attribute are similar if they occur with similar value distributions on correlated context attributes. An impact function controls the in uence of the correlated context attributes in ConDist's distance calculation process. ConDist requires a user-de ned threshold to purge context attributes whose correlations are caused by noisy, non-representative or small data sets. In this work, we propose an automatic threshold calculation method for each pair of attributes based on their value distributions and the number of objects in the data set. Further, these thresholds are also considered when applying ConDist's impact function. Experiments show that this approach is competitive with respect to well selected user-de ned thresholds and superior to poorly selected user-de ned thresholds.

Keywords

• categorical data
• distance measure
• unsupervised learning

-

Distance calculation between objects is a key requirement for many data mining tasks like clustering, classi cation or outlier detection [ 15 ]. Objects are described by a set of attributes which can be divided into continuous and categorical attributes. For continuous attributes, distance calculation is well understood and mostly uses the Minkowski distance [ 2 ]. For categorical attributes, de ning meaningful distance measures is more challenging since the values within such attributes have no inherent order [ 4 ]. However, several methods exist to address this issue. A comprehensive overview of categorical distance measures is given in [ 4 ]. Yet, more sophisticated categorical distance measures incorporate statistical information like correlations about the data [ 8,9,11,14 ]. ConDist (Context based Categorical Distance Measure) [ 14 ] is such an unsupervised categorical distance measure. For distance calculation, ConDist extracts available information from correlations between the target attribute (the attribute for which distances shall be calculated) and the correlated context attributes. ConDist uses a correlation measure based on the information gain. Each context attribute whose correlation exceeds a user-de ned threshold is used for distance calculation. This threshold must be large enough to ensure that context attributes are purged whose correlations are caused by noisy, non-representative or too small data sets. Simultaneously, the threshold must be small enough to retain context attributes with signi cant correlations.

In this paper, we propose a data-driven method for calculating ConDist's threshold. In [ 14 ], the user has to de ne a single threshold for all attributes. In contrast to this approach, the proposed method calculates an individual threshold XjY for each combination of target attribute X and context attribute Y . These thresholds XjY can be better adapted to the speci c correlation requirements of two concrete attributes than a single threshold . We consider the number of objects in the data set and the value distributions of target attribute X and context attribute Y when calculating the individual thresholds XjY . The calculated thresholds XjY are also taken into account when applying ConDist's impact function. The impact function controls the in uence of the correlated context attributes in ConDist's distance calculation process and considers the varying amount of information that can be extracted from a correlated context attribute. The proposed method for the automatic threshold calculation makes ConDist parameterless and simpli es the application of the distance measure.

The rest of the paper is organized as follows: Related work on categorical distances measures and their approaches for identifying correlated context attributes are discussed in Section 2. Section 3 gives a short description of the categorical distance measure ConDist. Section 4 introduces the proposed method for the automatic threshold calculation. Section 5 gives an experimental evaluation of the proposed automatic threshold calculation method and the results are discussed in Section 6. The last section summarizes the paper. 2

Related Work

Unsupervised categorical distance measures may be divided into distance calculation (I) without considering context attributes and (II) considering context attributes.

Boriah et al. [ 4 ] give a comprehensive overview of distances measures from category (I). These distance measures ignore information that could be extracted from context attributes. For example, the distance measure Eskin only uses the cardinality of the target attribute domain to calculate distances.

Distance measures from category (II) consider context attributes in the distance calculation process [ 1,8,9,10,11,14 ]. For example, the distance measures proposed in [ 1 ] and [ 11 ] use all context attributes for distance calculation without distinguishing between correlated and uncorrelated. Conversely, the proposed distance measures in [ 8 ] and [ 9 ] use only a subset of context attributes for distance calculation. Jia and Cheung [ 9 ] use a normalized version of the mutual information (NMI) [ 3 ], whereas DILCA [ 8 ] relies on Symmetric Uncertainty (SU) [ 17 ] to determine the correlation between two attributes. For both, NMI and SU, the user has to de ne a threshold for the selection of correlated context attributes. The distance measure CBDL [ 10 ] uses the Pearson's chi-squared test 2 [ 12 ] for identifying correlated context attributes. Yet, the user needs to provide a signi cance level alpha for the Pearson's chi-squared test 2.

Like [ 9 ], ConDist [ 14 ] only uses correlated context attributes for distance calculation. It measures the correlation between attributes based on the information theoretical concept of entropy. In [ 14 ], the user has to de ne a threshold for the selection of correlated context attributes. In this work, we propose an automatic threshold calculation method for ConDist, which is based on the value distribution of the attributes and the number of objects in the data set. 3

The Distance Measure ConDist

In this section, we give a short description of the categorical distance measure ConDist [ 14 ]. The core idea is presented in Section 3.1. Since ConDist uses correlated context attributes in the distance calculation process, we explain in Section 3.2 how the set of correlated context attributes is derived. Section 3.3 describes the impact function of ConDist which accounts for the varying amount of information that can be extracted from a correlated context attribute. 3.1

ConDist

The distance between two objects A and B is calculated as the sum of distances in each attribute and de ned as follows:

ConDist(A; B) =

X wX X dX (A; B) dX;max ; (1) where wX denotes a weighting factor assigned to attribute X. Since wX is not relevant for threshold calculation, the reader is referred to [ 14 ] for further details on wX . The function dX (A; B) denotes the distance of the values AX and BX of the objects A and B in attribute X. The maximum distance between any two values x; u 2 dom(X) of attribute X is given by dX;max and is used to normalize all attribute distances to the interval [0; 1].

The distance dX (A; B) between two values AX and BX within an attribute X is calculated according to the following formula: dX (A; B) =

X Y 2contextX v u impactX (Y )u t

X ConDist uses an asymmetric function cor(XjY ) to measure the correlation between a target attribute X and a context attribute Y . The function cor(XjY ) is de ned as follows: cor(XjY ) =

IG(XjY )

H(X) ; where H(X) is the entropy of the target attribute X and IG(XjY ) is the information gain of target attribute X given context attribute Y . The information gain IG(XjY ) is the di erence between the entropy H(X) of attribute X and the conditional entropy H(XjY ) of attribute X given attribute Y : IG(XjY ) = H(X)

H(XjY ) Consequently, the function cor(XjY ) is normalized to the interval [0; 1]. The higher the value of the correlation function cor(XjY ), the higher the correlation between the two attributes. In [ 14 ], all context attributes whose correlations exceed a user-de ned threshold are added to the set of correlated context attributes contextX for target attribute X: where dom(Y ) is the domain of attribute Y , and p(yjAX ) = p(yjX = AX ) denotes the probability that value y of context attribute Y is observed under the condition that value AX of attribute X is observed in data set D. The set of correlated context attributes for a speci c target attribute X is given by contextX (see Section 3.2). The function impactX (Y ) controls the in uence of context attribute Y on target attribute X and is described in Section 3.3. 3.2

Selection of Context Attributes (3) (4) (6) contextX = fY j cor(XjY ) g (5) Note that the target attribute X itself is always in the set of correlated context attributes contextX since cor(XjX) = 1. 3.3

The Impact of Context Attributes

ConDist uses an impact function impactX (Y ) to control the in uence of a correlated context attribute Y on target attribute X in the distance calculation process. This function accounts for the fact that the varying amount of extractable information depends on the degree of correlation between the attributes X and Y . In general, the quality of the extracted information grows with the strength of the correlation. However, for highly correlated attributes, the amount of extractable information decreases. In the extreme case of a perfectly correlated context attribute Y , no further information about distinct values in target attribute X can be extracted since Y predicts the values of X. To be precise, ConDist uses the impact function as de ned as:

Automatic Threshold Calculation Method

In this section, we propose a data-driven approach to replace the user-de ned threshold of Section 3.2. In principle, ConDist's impact function should control automatically the in uence of the context attributes without additional thresholds. However, the experiments in [ 14 ] showed that an additional threshold is necessary, especially for non-correlated data sets.

In Section 4.1, we use an example to explain the reason why an additional threshold is necessary. Based on that example, we propose a way how this threshold could be calculated from the data set in Section 4.2. The proposed automatic threshold calculation method involves an additional adjustment of ConDist's impact function which is described in Section 4.3. 4.1

Problem Description by Example

The impact function impactX (Y ) (Section 3.3) controls the in uence of context attributes in the distance calculation process and depends on the value of the correlation function cor(XjY ) (Section 3.2). We give an example when these two functions fail to control the in uence of context attributes without additional threshold .

Consider the example data set in Table 1. Let us assume, we want to calculate distances for the attribute height. In this case, sex and haircolor are the context attributes. Further, we may assume that in the considered population attributes haircolor and height are independent of each other, while attributes height and sex are correlated. When applying ConDist's correlation function cor(XjY ) and impact function impactX (Y ), we achieve the following results: cor(heightjsex) =

IG(heightjsex)

H(height) 0:108 As expected, the context attribute sex has higher impact on the target attribute height than context attribute haircolor. However, the context attribute haircolor has also a small impact on the target attribute height. Since we have also a highly correlated context attribute sex, the small impact of context attribute haircolor is almost negligible.

However, if we would have only the context attribute haircolor, the small impact factor would lead to small di erences for distinct values in target attribute height. These small di erences originate from the fact that the estimated probability density functions used in cor(XjY ) are not representative due to the small training data set. Consequently, the di erences are conceptually not intended since, given the particular population of our example, the context attribute haircolor is independent from height. In this case, it would be preferable to use only the target attribute itself for distance calculation. Therefore, a threshold is necessary to purge such context attributes. 4.2

Data-Driven Threshold Calculation

The example in Section 4.1 shows that too small data sets are problematic for the correlation function cor(XjY ). This follows from the fact that cor(XjY ) requires the information gain IG(XjY ), which in turn requires the entropy of attribute X and the conditional entropy of attribute X given attribute Y . The entropy H(X) and the conditional entropy H(XjY ) are de ned as follows: (9) (10) (11) (12) (13) where p(x) is the probability of value x and p(xjy) is the conditional probability of value x given value y in data set D. Consequently, the probability density functions p(X) and p(Y ) of the attributes X and Y are necessary for calculating H(X) and H(XjY ). These two functions can be estimated more accurately if the data set is large. Consequently, the smaller the data set, the higher the possibility of errors in the results delivered by the correlation function.

Further, two attributes X and Y are non-correlated in ConDist's correlation function cor(XjY ), if and only if the following equation holds:

H(X) = H(XjY ) Equation (13) requires that the conditional probability density functions of attribute X given a value y 2 dom(Y ) are all identical and equal to the probability density function of attribute X. The larger the cardinality of dom(X) and dom(Y ), the more objects are necessary to ful ll this requirement in the case H(X) =

X x2dom(X)

p(x) log2 p(x) and H(XjY ) =

X of non-correlated attributes since the value distributions and conditional value distributions must be estimated from the data set. Consequently, the cardinality and the distribution of dom(X) and dom(Y ) should be considered in the threshold calculation process as well. Both factors are re ected in the entropy of an attribute.

Therefore, we calculate the threshold

XjY based on these two aspects: XjY =

H(X) H(Y ) n ; (14) where n is the number of objects in the data set. This threshold decreases with an increasing number of objects and increases with increasing attribute entropies H(X) and H(Y ). The threshold XjY may be viewed as an estimate of the portion of correlation that is due to estimating the probability density functions p(X) and p(Y ) from the data set. The calculation of XjY is easy and no userde ned parameter is necessary.

If we apply the automatic calculation of the threshold XjY to the example in the Section 4.1, we can observe the following results: heightjsex =

H(height) H(sex) n The correlation value of attribute sex (see Equation (7)) exceeds the calculated threshold heightjsex, whereas the correlation value of attribute haircolor (see Equation (8)) does not exceed the threshold heightjhaircolor. Applying the proposed context-sensitive threshold XjY would imply that only the attribute sex would be added to the set of correlated context attributes contextheight for target attribute height. In Section 4.2, we interpreted the threshold XjY as the amount of correlation which is caused by estimating probability density functions from the data set. Consequently, this amount of correlation should also be considered in the impact function impactX (Y ). To that end, we adjust ConDist's impact function impactX (Y ) as follows: impactX (Y ) = 8 <0 :cor (XjY ) 1 12 cor (XjY ) 2 if cor(XjY ) if cor(XjY ) >

XjY XjY where cor (XjY ) is the adjusted correlation value rescaled to the interval [0; 1]: cor (XjY ) = cor(XjY ) 1

XjY

XjY : ; (17)

(18) If we apply the new impact function to the example in the Section 4.1, we can observe the following results: cor (heightjsex) Using the proposed approach, only the context attribute sex has an impact on target attribute height. This section presents an experimental evaluation of the automatic calculation of the threshold XjY (Section 4). We compare our new approach with the userde ned threshold method presented in [ 14 ] and with the categorical distance measure DILCA [ 8 ], which is the most serious competitor in [ 14 ]. For DILCA, we used the non-parametric approach DILCARR as described in [ 8 ]. We evaluate the di erent threshold calculation methods for ConDist in the context of classi cation. A k-Nearest-Neighbor classi er is used to compare the di erent categorical distance measures (DILCA and ConDist ) and the di erent methods for threshold calculation in ConDist. For simpli cation, we do not try to optimize the selection of the parameter k of the k-Nearest-Neighbor classi er. Instead we x the number of neighbors k = 7 in all tests in order to create an equal base for the di erent con gurations. We evaluate by 10-fold-cross validation and use the classi cation accuracy as evaluation measure. To reduce confounding e ects of the generated subsets, 10-fold cross-validation is repeated 100 times with di erent subsets for each data set.

For evaluation, the multivariate categorical data sets for classi cation from the UCI machine learning repository [ 13 ] are chosen. We exclude data sets with less than 25 objects (e.g., Balloons ) or mainly binary attributes (e.g., Chess). Furthermore, we include some multivariate mixed data sets for classi cation from [ 13 ] which mainly consist of categorical attributes and some integer attributes with a small set of distinct values (e.g. an integer attribute that contains the number of students in a course): Teaching Assistant Evaluation, Breast Cancer Wisconsin, Dermatology and Post-Operative Patient. All integer attributes are treated as categorical. The nal set of data sets is given in Table 2. The column Correlation contains the average correlation between each distinct pair of attributes, calculated by the function cor(XjY ), see Equation (3). The value ranges from 0 if no correlation exists to 1 if all attributes are perfectly correlated. The data sets are separated in two groups: correlated (Correlation > 0) and non-correlated (Correlation = 0). This experiment compares the automatic calculated threshold XjY with various user-de ned thresholds in ConDist and with the categorical distance measure DILCA. The threshold expresses the minimum value of the function cor(XjY ) that a context attribute Y has to achieve in order to be selected as correlated context attribute for the target attribute X. The higher the threshold , the fewer context attributes are used. In the extreme case of = 0, all context attributes are used for distance calculation. The automatic calculated threshold XjY follows the approach of Section 4. The results of this experiment are summarized in Table 3, where each column contains the average classi cation accuracies for a particular threshold.

Table 3 shows that the automatic calculation of the threshold XjY achieves the best average classi cation accuracy. The user-de ned thresholds = 0:01 and = 0:02 achieve similar good results. Without any threshold = 0, a decreasing classi cation accuracy can be observed for non-correlated data sets. For too high user-de ned thresholds , the average classi cation accuracies decrease. Compared with DILCA, the proposed approach XjY is comparable for highly correlated data sets and superior for weakly- and non-correlated data sets. Statistical Signi cance Test. This test aims at examining if the di erences in Table 3 are statistically signi cant. Demsar [ 5 ] deals with the statistical comparison of classi ers over multiple data sets. They recommend the Wilcoxon SignedRanks Test [ 16 ] for the comparison of two classi ers and the Friedman-Test [ 6,7 ] for the comparison of multiple classi ers. Following this line, we use the FriedmanTest to compare all di erent con gurations and the Wilcoxon Signed-Ranks Test for post-hoc tests. The Friedman-Test is signi cant for p < 0:05; thus we can reject the null hypothesis that all threshold calculation methods in ConDist and DILCA are equivalent. Subsequently, we applied the Wilcoxon Signed-Ranks Test with = 0:05 on the classi cation accuracies of Table 3.

Table 4 shows signi cant di erences between XjY and DILCA and between XjY and the user-de ned thresholds = 0:1, = 0:2 and = 1:0. For the remaining user-de ned thresholds , the Wilcoxon Signed-Ranks Test shows no statistically signi cant di erences. 6

Discussion

For correlated data sets, high user-de ned thresholds lead to decreasing results, e.g. = 0:1, = 0:2 or = 1:0 for the data sets Teaching Assistant Evaluation and Lymphography. For these thresholds, many useful correlated context attributes are discarded. The same observation can be made for weakly-correlated data sets at lower thresholds. Consider the decreasing classi cation accuracy for the data set TicTacToe at threshold = 0:05. For non-correlated data sets, nearly all threshold methods achieve the same results. Only the absence of any threshold ( = 0) leads to inferior results. In this case, non-correlated context attributes are added to the set of context attributes contextX , which may contribute noise to the distance calculation process.

The proposed automatic calculation of the threshold XjY achieves good results for correlated and non-correlated data sets. As a consequence, the proposed method achieves the best average classi cation accuracy. The average classi cation accuracies for user-de ned thresholds = 0:01, = 0:02 and = 0:05 are marginally worse. The Wilcoxon-Signed Ranks Test con rms that there are no statistical signi cant di erences between them. In contrast to this, statistically signi cant di erences can be observed for too high user-de ned thresholds.

These observations indicate that the proposed automatic calculation of the threshold XjY is superior to poorly selected user-de ned thresholds and competitive to well selected user-de ned thresholds. Consequently, XjY is preferable to the user-de ned approach in [ 14 ], since the user-de ned parameter is omitted and the quality of results does not deteriorate.

For highly correlated data sets, the results of the proposed approach XjY and DILCA are comparable. For weakly- and non-correlated data sets, DILCA achieves inferior results in comparison to ConDist. This is because DILCA uses only context attributes for distance calculation which results in random distances if all context attributes are non-correlated. 7

Summary

Categorical distance calculation is a key requirement for many data mining tasks. In this paper, we propose an extension for the unsupervised categorical distance measure ConDist [ 14 ]. ConDist uses the correlation between attributes to extract available information for distance calculation. In [ 14 ], the user has to de ne a threshold for the selection of correlated context attributes. This threshold has to purge context attributes whose correlations are caused by noisy, nonrepresentative or too small data sets.

In this work, we proposed an automatic threshold calculation method for the distance measure ConDist. This approach calculates for each pair of target attribute X and context attribute Y an individual threshold instead of using a single user-de ned threshold . The calculated thresholds XjY depend on the number of objects in the data set and the entropies of the attributes. Consequently, these individual thresholds can be better adapted to the speci c correlation requirements of each pair of attributes. Further, additional adjustments were made to ConDist's impact function impactX (Y ).

The proposed extension makes ConDist parameterless and simpli es the application of the distance measure. Our experiments show that the automatic threshold calculation method is competitive to well selected user-de ned threshAcknowledgements This work is funded by the Bavarian Ministry for Economic A airs through the WISENT project (grant no. IUK 452/002) and by the DFG through the PoSTs II project (grant no. HO 2586/2-2).

References

1. Ahmad , A. , Dey , L. : A method to compute distance between two categorical values of same attribute in unsupervised learning for categorical data set . Pattern Recognition Letters 28 ( 1 ), 110 { 118 ( 2007 )

2. Alamuri , M. , Surampudi , B.R. , Negi , A. : A survey of distance/similarity measures for categorical data . In: Proc. of IJCNN . pp. 1907 { 1914 . IEEE ( 2014 )

3. Au , W.H. , Chan , K.C. , Wong , A.K. , Wang , Y. : Attribute clustering for grouping, selection, and classi cation of gene expression data . IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 2 ( 2 ), 83 { 101 ( 2005 )

4. Boriah , S. , Chandola , V. , Kumar , V. : Similarity measures for categorical data: A comparative evaluation . In: Proc. SIAM Int. Conference on Data Mining . pp. 243 { 254 ( 2008 )

5. Demsar , J.: Statistical comparisons of classi ers over multiple data sets . The Journal of Machine Learning Research 7 , 1 { 30 ( 2006 )

6. Friedman , M.: The use of ranks to avoid the assumption of normality implicit in the analysis of variance . Journal of the American Statistical Association 32 ( 200 ), 675 { 701 ( 1937 )

7. Friedman , M.: A comparison of alternative tests of signi cance for the problem of m rankings . The Annals of Mathematical Statistics 11 ( 1 ), 86 { 92 ( 1940 )

8. Ienco , D. , Pensa , R.G. , Meo , R.: Context-based distance learning for categorical data clustering . In: Advances in Intelligent Data Analysis VIII , pp. 83 { 94 . Springer ( 2009 )

9. Jia , H. , Cheung , Y.M.: A new distance metric for unsupervised learning of categorical data . In: Proc. of IJCNN . pp. 1893 { 1899 . IEEE ( 2014 )

10. Khorshidpour , Z. , Hashemi , S. , Hamzeh , A. : Cbdl: Context-based distance learning for categorical attributes . Int. J. Intell. Syst . 26 ( 11 ), 1076 { 1100 ( 2011 )

11. Le , S.Q. , Ho , T.B. : An association-based dissimilarity measure for categorical data . Pattern Recognition Letters 26 ( 16 ), 2549 { 2557 ( 2005 )

12. Lehmann , E. , Romano , J.: Testing Statistical Hypotheses . Springer Texts in Statistics, Springer ( 2005 )

13. M. Lichman: Uci machine learning repository ( 2013 ), http://archive.ics.uci. edu/ml

14. Ring , M. , Otto , F. , Becker , M. , Niebler , T. , Landes , D. , Hotho , A. : Condist: A context-driven categorical distance measure . In: Machine Learning and Knowledge Discovery in Databases . pp. 251 { 266 . Springer ( 2015 )

15. Tan , P.N. , Steinbach , M. , Kumar , V. : Introduction to data mining . Pearson Addison Wesley Boston ( 2006 )

16. Wilcoxon , F. : Individual comparisons by ranking methods . Biometrics bulletin 1(6) , 80 { 83 ( 1945 )

17. Yu , L. , Liu , H.: Feature selection for high-dimensional data: A fast correlationbased lter solution . In: ICML . vol. 3 , pp. 856 { 863 ( 2003 )