Explainable clustering has become increasingly important as it presents the clustering results in a manner that can be easily understood by the end-users. However, most existing explainable clustering approaches generate only a single explanation such as a decision tree for the given clustering result, overlooking that multiple valid interpretations may exist. To address this limitation, we propose the CME (Clustering with Multiview Explanations) algorithm. This method constructs a diverse set of candidate decision trees by retaining multiple splitting points at each node, where each splitting point is valid in a statistical sense. The tree similarity based on optimal path matches across corresponding clusters is then used to build a similarity graph. A subset of representative decision trees are selected by solving the minimum dominating set problem defined on the corresponding similarity graph. Experiments on 10 real-world categorical datasets demonstrate that CME provides multiple complementary explanations that may be missed by existing algorithms. Moreover, these additional decision trees can be more accurate and interpretable than those ones identified by baseline methods.

Sequence classification is a fundamental research issue in data mining and machine learning. However, existing sequence classification methods primarily focus on improving the prediction performance. Although a few methods attempt to enhance the interpretability, they often fail to provide intuitive model explanations and come with high computational costs. To fill this gap, we propose an interpretable sequence classification algorithm based on decision set. Each rule in the decision set is only associated with one discriminative pattern (subsequence) and the classification decision is made based on one best-matched rule. Hence, the proposed method has good interpretablility since the classification decision is solely determined by one simple intuitive rule. Experimental results on real-world data sets demonstrate that our algorithm outperforms the state-ofthe- art interpretable sequence classification methods in terms of both interpretability and classification accuracy.

Clustering validation is a fundamental task in cluster analysis. While many clustering validity indices have been proposed, most existing internal validity indices are typically defined heuristically, lacking solid statistical foundation and interpretation. To address this limitation, we introduce a new internal validity index that employs hypothesis testing to determine whether two samples belong to the same cluster and defines the index as the proportion of correctly identified sample pairs based on their cluster memberships. To demonstrate the advantages of proposed validity index, we conduct experiments on various synthetic and real-world data sets. The experimental results indicate that our validation index can beat both classic and state-of-the-art internal validation indices.

The detection of communities from a graph is a key issue in network science and graph data mining . However, existing community detection algorithms can always partition a given network/graph into different communities/subgraphs, even when no community structure exists. Obviously, it will lead to fruitless efforts and erroneous conclusions if we conduct the community detection procedure on a network without a community structure. Hence, prior to community detection, it is a must to test whether the community structure is present in the target network. Unfortunately, the community structure testing issue is still not revolved and existing solutions have some limitations. Therefore, we present a new test, which is called FCN (Frequent Common Neighbor) test to tackle the community structure testing problem . In FCN test, the number of FCN sets is employed as the test statistic, which will approximately follows a Poisson distribution when the support threshold is sufficiently large under the null hypothesis that the graph is generated according to the Erdős-Rényi model. We compare the proposed FCN test with existing community structure testing methods on both real networks and simulated networks. The experimental results demonstrate the effectiveness and advantage of our method.

Categorical data clustering is a fundamental data mining problem, which has been extensively studied during the past decades. To date, many effective clustering algorithms for categorical data are available in the literature. However, almost all existing categorical data clustering algorithms did not address the issue of the statistical significance of detected clusters. In particular, how to assess the statistical significance of a set of non-overlapping categorical clusters still remains unaddressed. In this article, we formulate the categorical data clustering problem as a multiple hypothesis testing problem, where the null hypothesis is that each attribute is independent of the given partition of clusters. Then, all individual \(p\) -values from different attributes are integrated to obtain a consensus \(p\) -value through statistical meta-analysis. Thereafter, a significance-based clustering algorithm is proposed in which the combined \(p\) -value is efficiently optimized in an indirectly and incremental manner. Experimental results on 25 real-world datasets demonstrate that our method is capable of achieving comparable performance to state-of-the-art categorical data clustering algorithms. Furthermore, our method has a good capability of determining whether there really exists a clustering structure and assessing whether a given set of clusters is statistically significant.

As one of the most important issues in data mining and network science, the community detection problem has been extensively investigated during the past decades. Despite of the success achieved by existing methods, how to directly access the statistical significance of an individual community in a weighted network remains unsolved. To address this issue, we present a new method to calculate the analytical p-value of an individual community in weighted networks. The proposed analytical p-value is able to assess the statistical significance that one target community appears in a random weighted graph in a straightforward manner. To verify the effectiveness of the proposed p-value in community evaluation, it is utilized as the objective function in a local search procedure to derive a new community detection algorithm. Experimental results show that the new algorithm is able to achieve comparable performance to those state-of-the-art algorithms for identifying communities from weighted networks. The source codes of our method are available at: https://github.com/chenwenfang/MSSC.

The community structure typically refers to the existence of a network partition in terms of a set of non-overlapping dense sub-graphs, where each sub-graph is called a community and there are few links between different communities. The detection of community structure is able to provide additional knowledge on the organization mechanism of the network and its characteristics. Despite decades of developments in community detection algorithms, how to determine whether a given community structure is true or not in a statistically sound manner still remains unresolved. In this paper, we present an analytical upper bound on thep-value of a community structure under the configuration model. To demonstrate its effectiveness on community structure validation, we further develop a community detection algorithm in which thep-value upper bound is used as the objective function. Experimental results on both real networks and simulated networks show that our algorithm outperforms prior state-of-the-art community detection methods.

Current decision trees such as C4.5 and CART are widely used in different fields due to their simplicity, accuracy and intuitive interpretation. Similar to other popular classifiers, these tree-based classification algorithms are developed for fixed-length vector data and suffer from intrinsic limitations in handling complex data such as sequences. To tackle the discrete sequence classification task, the dominant strategy is to adopt a two-step procedure: first transform the sequential dataset into a vector dataset and then apply existing tree-based classifiers on the new vector data. However, such methods are highly dependent on the feature generation procedure and some features that are critical to the tree construction may be missed. To alleviate these issues, we present a new tree-based sequence classification method, which is able to construct a concise decision tree from the feature space that is composed of all subsequences present in the training sequences. Experimental results on fourteen real datasets show that our method can achieve better performance than those state-of-the-art sequence classification algorithms. The source codes of our method are available at: https://github.com/ZiyaoWu/SeqDT.

Community detection is a key data analysis problem across different fields. During the past decades, numerous algorithms have been proposed to address this issue. However, most work on community detection does not address the issue of statistical significance. Although some research efforts have been made towards mining statistically significant communities, deriving an analytical solution of$p$-value for one community under the configuration model is still a challenging mission that remains unsolved. The configuration model is a widely used random graph model in community detection, in which the degree of each node is preserved in the generated random networks. To partially fulfill this void, we present a tight upper bound on the$p$-value of a single community under the configuration model, which can be used for quantifying the statistical significance of each community analytically. Meanwhile, we present a local search method to detect statistically significant communities in an iterative manner. Experimental results demonstrate that our method is comparable with the competing methods on detecting statistically significant communities.

Clustering is a widely used technique in data mining applications for discovering patterns in underlying data. Most traditional clustering algorithms are limited to handling datasets that contain either numeric or categorical attributes. However, datasets with mixed types of attributes are common in real life data mining applications. In this article, we present two algorithms that extend the Squeezer algorithm to domains with mixed numeric and categorical attributes. The performance of the two algorithms has been studied on real and artificially generated datasets. Comparisons with other clustering algorithms illustrate the superiority of our approaches. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 1077–1089, 2005.