The aim of clustering analysis is to group objects so that those within a cluster are much more similar than those in different clusters. Clustering has been studied extensively in the statistics, data-mining and database communities, and numerous algorithms have been proposed (Schwenkera and Trentin, 2014; Sabit et al., 2011; Yu et al., 2012; Fukunaga, 2013; Cover and Hart, 1967; Derrac et al., 2012; Santos et al., 2013). It has been widely used for data analysis in many fields, including anthropology, biology, economics, marketing, and medicine. Typical applications include disease classification, document retrieval, image processing, market segmentation, scene analysis, and web access pattern analysis (Guan et al., 2013; Li et al., 2013; Shrivastava and Tyagi, 2014; Hruschka et al., 2006; Li et al., 2006; Lingras et al., 2005; Choi et al., 2012).

Hierarchical techniques are often used in cluster analysis. They aim to establish a hierarchy of partition structure, using either bottom-up or top-down approaches. In the bottom-up approach, at initialization, each object is represented by a single cluster. Clusters are then successively merged based on their similarities until all the objects are grouped into a single cluster, or until some special stopping conditions are satisfied. In the top-down approach, on the other hand, larger clusters are successively divided to generate smaller and more compact clusters until some stopping conditions are satisfied or each cluster contains a single object. Traditionally, in the bottom-up approach, the pairwise similarity (or distance) employed for merging clusters is often calculated on a common feature space. Feature relevance or feature selection is addressed prior to the clustering process. In this research, we will investigate feature relevance with respect to individual clusters and cluster merging where each cluster may have its own relevant features. This is a very important issue in hierarchical clustering of high-dimensional data. In this paper the terms ‘feature’, ‘attribute’ and sometimes ‘dimension’ are used interchangeably.

Automatically determining the relevancy of attributes in a categorical cluster will be investigated in this paper. Conventional similarity measures, defined on the whole feature space with the assumption that features are of equal importance, are not suitable for clustering high-dimensional data in many cases. In real-world applications, different clusters may lie in different feature subspaces with different dimensions. This means the significance or relevance of an attribute is not the same to different clusters. A cluster might be related to only a few dimensions (most relevant dimensions) while the other dimensions (unimportant dimensions) contain random values. Attribute weighting is employed to deal with these issues, but most weighting methods have been designed solely for numeric data clustering (Huang et al., 2005; Lu et al., 2011). For categorical data, the main difficulty is estimating the attribute weights based on the statistics of categories in a cluster. In fact, in the existing methods (Bai et al., 2011a; Xiong et al., 2011), an attribute is weighted solely according to the mode category for that attribute. Consequently, the weights easily yield a biased indication of the relevance of attributes to clusters. To solve this problem, it is necessary to analyse the relationship between attributes and clusters.

In this paper, we propose a novel algorithm named Hierarchical Projected Clustering for Categorical Data (HPCCD). The HPCCD algorithm has been designed to deal with three main issues. The first is analysing attribute relevance based on the holo-entropy theory (Wu and Wang, 2013). The holo-entropy is defined as the sum of the entropy and the total correlation of the random vector, and can be expressed by the sum of the entropies on all attributes. It will be used to analyse the relationship between attributes and cluster structure. The second issue is how to decide to merge two clusters in the absence of an effective pairwise similarity measure. The problem arises due to the fact that different subclusters may have their own relevant subspaces. And finally, the third issue is finding the projected clusters based on the intra-class compactness. Our algorithm has two phases, based on the conventional steps in agglomerative clustering. The first is to divide the dataset into K init (the initial number of clusters) subclusters in an initialization step. And the second is to iteratively merge these small clusters to yield larger ones, until all the objects are grouped in one cluster or a desired number of clusters. Experimental results on nine UCI real-life datasets show that our algorithm performs effectively compared to state-of-the-art algorithms.

The rest of the paper is organized as follows: Section 2 is a brief review of related work. In Section 3, we introduce the mutual information, total correlation, and holo-entropy concepts used in the paper. Section 4 describes the details of our algorithm HPCCD, with an illustrative example. In Section 5, we present experimental results, in comparison with other state-of-the-art algorithms. Finally, we conclude our paper and suggest future work in Section 6.

In this section, we briefly review major existing works related to our research. Many clustering algorithms for categorical data are based on the partition approach. The most popular of these is Huangs K-modes algorithm (Huang, 1998), which is an extension of the K-means paradigm to the categorical domain. It replaces the mean of a cluster by the mode and updates the mode based on the maximal frequency of the value of each attribute in a cluster. A number of partition-based algorithms have been developed based on the K-modes approach. In Jollois and Nadif (2002), Jollois et al. develop the Classification EM algorithm (CEM) to estimate the parameters of a mixture model based on the classification likelihood approach. In Gan et al. (2005), Gan et al. present a genetic K-modes algorithm named GKMODE. It introduces a K-modes operator in place of the normal crossover operator and finds a globally optimal partition of a given categorical dataset into a specified number of clusters. Other extensions of the K-modes algorithm include fuzzy centroids (Kim et al., 2004) using fuzzy logic, more effective initialization methods (Cao et al., 2009; Bai et al., 2011b) for the K-modes and fuzzy K-modes, attribute weighting (He et al., 2011) and the use of genetic programming techniques for fuzzy K-modes (Gan et al., 2009).

Also proposed in addition to all the K-modes algorithms is k-ANMI (He et al., 2005), a K-means-like clustering algorithm for categorical data that optimizes an objective function based on mutual information sharing. Most of the conventional algorithms (Shrivastava and Tyagi, 2014; Hruschka et al., 2006; Xiong et al., 2011; Wu and Wang, 2013) involve optimizing an objective function defined on a pairwise measure of the similarity between objects. Unfortunately, this optimization problem is usually NP-complete and requires the use of heuristic methods in practice. In such solutions, the focus is primarily on the relationship between objects and clusters, while attribute relevance within a cluster is often ignored (Barbar et al., 2002; Qin et al., 2014; Ganti et al., 1999; Greenacre and Blasius, 2006). Moreover, the lack of an intuitive method for determining the number of clusters and high time complexity are common challenges for this type of algorithm.

Projected clustering is a major technique for high-dimensional data clustering, whose aim is to discover the clusters and their relevant attributes simultaneously. A projected cluster is defined by both its data points and the relevant attributes (Bouguessa and Wang, 2009; Domeniconi et al., 2004; Parsons et al., 2004) forming its feature subspace. For example, HARP (Yip et al., 2004) is a hierarchical projected clustering algorithm based on the assumption that two data points are likely to belong to the same cluster if they are very similar to each other along many dimensions. However, when the number of relevant dimensions per cluster is much lower than the dataset dimensionality, such an assumption may not be valid, because relevant information concerning these data points in a large subspace is lost. Some projected clustering algorithms, such as PROCLUS (Aggarwal et al., 1999) and ORCLUS (Aggarwal and Yu, 2002), require the user to provide the average dimensionality of the subspaces, which is very difficult to establish in real-life applications. PCKA (Bouguessa and Wang, 2009), a distance-based projected clustering algorithm, was recently proposed to improve the quality of clustering when the dimensionalities of the clusters are much lower than that of the dataset. However, it requires users to provide values for some input parameters, such as the number of nearest neighbours of a 1D point, which may significantly affect its performance. These algorithms are dependent on pairwise similarity measures which do not take into account correlations between attributes.

Many clustering algorithms based on the hierarchical technique have been proposed. ROCK (Guha et al., 1999) is an agglomerative hierarchical clustering algorithm based on the extension of the pairwise similarity measure. It extends the Jaccard coefficient similarity measure by exploiting the concept of neighbourhood. Its performance depends heavily on the neighbour threshold and the time complexity depends on the number of neighbours. However, these parameters are difficult to estimate in real applications. Instead of using pairwise similarity measures, the K-modes algorithm (Guha et al., 1999; Zhang and Fang, 2013) defines a similarity between an individual categorical object and a set of categorical objects. When the clusters are well established, this approach has the advantage of being more meaningful. The performance of the K-modes algorithms relies heavily on the initialization of the K modes. DHCC (Xiong et al., 2011) proposes a divisive hierarchical clustering algorithm in which a meaningful object-to-clusters similarity measure is defined. DHCC is capable of discovering clusters embedded in subspaces, and is parameter-free with linear time complexity. However, DHCCPs space complexity is a limitation, as it depends on the square of the number of values of all the categorical attributes.

Information theory is also frequently used in many clustering models (Yao et al., 2000; Barbar et al., 2002). The goal of these approaches is to seek an optimum grouping of the objects such that the entropy is the smallest. An entropy-based fuzzy clustering algorithm (EFC) is proposed in Yao et al. (2000). EFC calculates entropy values and implements clustering analysis based on the degree of similarity. It requires the setting of a similarity threshold to control the similarity among the data points in a cluster. This parameter, which affects the number of clusters and the clustering accuracy, is very difficult to determine. The COOLCAT algorithm (Barbar et al., 2002) employs the notion of entropy in assigning unclustered objects. A given data object is assigned to a cluster such that the entropy of the resulting clustering is minimal. The incremental assignment terminates when every object has been placed in some cluster. The clustering quality depends heavily on the input order of the data objects. The LIMBO algorithm (Andritsos et al., 2004) is a hierarchical clustering algorithm based on the concept of an Information Bottleneck (IB) which quantifies the relevant information preserved in clustering results. It proposes a novel measurement for the similarity among subclusters by way of the Jensen–Shannon divergence.

Finally, the MGR algorithm (Qin et al., 2014) searches equivalence classes from attribute partitions to form the clustering of objects which can share the greatest possible quantity of information with the attribute partitions. First, MGR selects the clustering attribute whose partition shares the most information with the partitions defined by other attributes. Then, on the clustering attribute, the equivalence class with the highest intra-class similarity is output as a cluster, and the rest of the objects form the new current dataset. The above two steps are repeated on the new current dataset until all objects are output. In MGR, because the attributes are selected one by one, the relevancy of attributes (or combinations of attributes) is not considered sufficiently. For example, say attribute A1 has the most information, and A2 is in second place. It is not necessarily true that the combination A1, A2 has more information than some other combination A3, A4. How to select the subcluster of attributes which shares the most information with the partitions will be analysed in this paper.

In this section, we provide a brief description of information entropy, and give a more detailed explanation of the concepts of mutual information, total correlation and holo-entropy (Wu and Wang, 2013) used by the algorithm proposed in this paper.

Entropy is a measure of the uncertainty of a system state. As formulated in information theory (Shannon, 1948), the concept is often used to measure the degree of disorder or chaos of a dataset, or to describe the uncertainty of a random variable. For a given discrete random variable S = ( s 1 , s 2 , … , s m ), let the corresponding probability of appearance be { p ( s 1 ) , p ( s 2 ) , … , p ( s m ) }, where p ( s i ) satisfies ∑ i = 1 m p ( s i ) = 1. The entropy of S is defined as E ( S ) = − ∑ i = 1 m p ( s i ) ln ( p ( s i ) ). The entropy allows to assess the structure of an attribute, i.e. whether its values are distributed compactly or sparsely. Therefore, it can be used as a criterion on an attribute that expresses the degree to which an attribute is or is not characteristic for a cluster.

Many high-dimensional data clustering approaches are based on the attribute independence hypothesis (Barbar et al., 2002; Ganti et al., 1999; Greenacre and Blasius, 2006). Such a hypothesis not only ignores the degree of correlation among attributes, but also fails to consider attribute relevance and heterogeneity in the data. Methods derived from these approaches do not satisfy the requirements of many practical applications. The holo-entropy (Wu and Wang, 2013) is a compactness measure that incorporates not only the distribution of individual attributes but also correlations between attributes. It has been effectively used in evaluating the likelihood of a data object being an outlier. There is as yet no reported work on how holo-entropy can contribute to high-dimensional categorical data clustering. Our hypothesis in this work is that the holo-entropy may contribute to relevant subspace detection and compactness measurement in cluster analysis. Actually, the goal of subspace detection is to find a set of attributes on which the data of a cluster are distributed compactly. This attribute set expresses the features of the cluster.

In this paper, we develop a new method that utilizes the holo-entropy for hierarchical clustering. Based on the analysis of the intrinsic relevance of features and objects in subclusters, we develop a principled approach for selecting clusters to merge and determining the feature subspace of the merged cluster. The holo-entropy is used to measure the intrinsic relevance. The main idea is that the holo-entropy of two subclusters originating from the same class should be much smaller than if the two subclusters originate from different classes. Therefore, the two subclusters with minimal holo-entropy are selected to merge in the hierarchical clustering. In order to describe our algorithm, the following notation and definitions are introduced.

We use X = { x 1 , x 2 , … , x n } to represent the dataset with n samples, where each  x i has m categorical attributes. The m attributes [ A 1 , A 2 , … , A m ] T are also represented by the attribute vector A. Each attribute A i has a value domain defined by [ a i , 1 , a i , 2 , … , a i , n i ] ( 1 ⩽ i ⩽ m ), where n i is the number of distinct values in attribute  A i . From the information-theoretic perspective, A i is considered a random variable, and A = [ A 1 , A 2 , A 3 , … , A m ] T is considered a random vector. The entropy E ( A ) of the random vector A on the set X is defined, according to the chain rule for the entropy (Cover and Thomas, 2012), by: (1) E ( A ) = E ( A 1 , A 2 , … , A m ) = ∑ i = 1 m E ( A i ∣ A i − 1 , … , A 1 ) = E ( A 1 ) + H ( A 2 ∣ A 1 ) + ⋯ + E ( A m ∣ A m − 1 , … , A 1 ) , where E ( A i ∣ A i − 1 , … , A 1 ) = − ∑ A i , A i − 1 , … , A 1 p ( A i , A i − 1 , … , A 1 ) ln p ( A i ∣ A i − 1 , … , A 1 ) and the probability functions p ( ) are estimated from X.

Based on Wu and Wang (2013), the definition of holo-entropy is as follows: The holo-entropy H L ( A ) is defined as the sum of the entropy and the total correlation of the random vector A, and can be expressed by the sum of the entropies on all attributes. (5) H L ( A ) = E ( A ) + C ( A ) = ∑ i = 1 m E ( A i ) .

Moreover, H L ( A ) = E ( A ) holds if and only if all the attributes are independent. From what has been discussed above, the holo-entropy can be used to measure the compactness of a dataset or a cluster more effectively, since it evaluates not only the disorder of the objects in the dataset but also correlation between variables. In fact, the values of H L ( ) calculated on subsets of attributes and/or on subsets (groups) of data reveal cluster structures hidden in the data. As a simple example, let us look at a dataset (Dataset1) shown in Table 1. Intuitively, this dataset has two classes (or clusters), one comprising objects { 1 , 2 , 3 , 4 } and the other objects { 5 , 6 , 7 , 8 }. We can also easily observe that the subspace { A 1 , A 2 } more strongly reflects an intrinsic cluster structure with objects { 1 , 2 , 3 , 4 } than do other attribute combinations. Indeed, the holo-entropies on the three non-single-dimensional subspaces are respectively HL ( A 1 , A 2 ) = 0.5623, HL ( A 1 , A 3 ) = 1.0397, HL ( A 2 , A 3 ) = 1.6021 and HL ( A 1 , A 2 , A 3 ) = 1.6021. These indicate clearly that { A 1 , A 2 } is the subspace of choice, given that the holo-entropy on it is the smallest. On the other hand, if we calculate the holo-entropy on different data subsets such as H L { 1 , 2 , 3 , 4 } ( A 1 , A 2 , A 3 ) = 1.6021, H L { 3 , 4 , 5 , 6 } ( A 1 , A 2 , A 3 ) = 2.0794, H L { 1 , 2 , 3 , 4 , 5 , 6 } ( A 1 , A 2 , A 3 ) = 2.9776, we also observe that the subset { 1 , 2 , 3 , 4 } is clearly a much better cluster candidate than other subsets.

From this example, we can see that the holo-entropy of two merged subclusters from the same (homogeneous) class is much smaller than that of merged subclusters from different (heterogeneous) classes. This indicates that holo-entropy is an effective measurement for the compactness of a subspace in a cluster. In what follows, we will use the holo-entropy for subspace detection. Moreover, we will employ the soft clustering method (Domeniconi et al., 2004; Gan and Wu, 2004; Nemalhabib and Shiri, 2006) and the properties of holo-entropy for merging subclusters in the hierarchical clustering.

In this section, we present our Hierarchical Projected Clustering algorithm for Categorical Data (HPCCD) in detail. To illustrate the ideas underlying the algorithm, we also provide a working example with 11 objects from the dataset Soybean, as shown in Table 2. The process of HPCCD draws on a conventional hierarchical clustering approach for its major steps, including initially grouping the data into small clusters and iterating between searching for the closest pair of subclusters and merging the pair. Our contribution is the design of new methods based on holo-entropy for detecting the relevant subspace of each subcluster and evaluating the structure compactness of a pair of subclusters in order to select the most similar subclusters to merge. Our algorithm is described as follows:

Algorithm HPCCD

Input: Dataset X, threshold r and the terminal condition K init which is the

 desired number of clusters;

Output: clusters of Dataset X.

Begin

Initialization (Grouping the data into subclusters C);

For each subcluster in set C

 A: relevant subspace selection

  A1: Detect the relevant subspace of each subcluster of C;

  A2: Assign weights to the attributes in the relevant subspace;

 B: compactness calculation (calculate compactness binding weight with

  holo-entropy);

Choose the most compact pair of subclusters to merge and update set C;

End

until satisfaction of the termination condition of K desired clusters.

The details of each step will be described in the following sub-sections.

In this section, we report experimental results of HPCCD on nine datasets from UCI Machine Learning Repository and comparison with four state-of-the-art algorithms. We will first describe the experimental design (Section 5.1) and evaluation criteria (Section 5.2). Then, we will present the performance results in terms of clustering accuracy (Section 5.3) and analyse the feature relevance (Section 5.4).

Most hierarchical clustering algorithms tend to be based on similarity measures computed on a common feature space, which is not effective for clustering high-dimensional data. In this paper, we have proposed a new way of exploring information entropy, holo-entropy, attribute selection and attribute weighting to extract the feature subspace and merge clusters that have different feature subspaces. The new algorithm differs from existing mainstream hierarchical clustering algorithms in its use of a weighted holo-entropy to replace the pairwise-similarity-based measures for merging two subclusters. The advantages of our algorithm are as follows: first, it takes interrelationships of the attributes into account and avoids the conditional independence hypothesis, which is an implicit hypothesis made by most existing hierarchical clustering algorithms. Secondly, it employs the entropy and holo-entropy to detect the relevant subspace, and find the principal feature space and the core feature space from the whole feature space of corresponding subclusters. Thirdly, it uses intra-class compactness as a standard for merging subclusters rather than the traditional similarity measurement. We performed experiments that demonstrate the effectiveness of the new algorithm in terms of clustering accuracy and analysis of the relevant subspaces obtained.