Estimating Individual Treatment Effects (ITE) from observational data is challenging due to confounding bias. Most studies tackle this bias by balancing distributions globally, but ignore individual heterogeneity and fail to capture the local structure that represents the natural clustering among individuals, which ultimately compromises ITE estimation. While instance-level alignment methods consider heterogeneity, they similarly overlook the local structure information. To address these issues, we propose an end-to-end Multi-Prototype alignment method for ITE estimation (PITE). PITE effectively captures local structure within groups and enforces cross-group alignment, thereby achieving robust ITE estimation. Specifically, we first define prototypes as cluster centroids based on similar individuals under the same treatment. To identify local similarity and the distribution consistency, we perform instance-to-prototype matching to assign individuals to the nearest prototype within groups, and design a multi-prototype alignment strategy to encourage the matched prototypes to be close across treatment arms in the latent space. PITE not only reduces distribution shift through fine-grained, prototype-level alignment, but also preserves the local structures of treated and control groups, which provides meaningful constraints for ITE estimation. Extensive evaluations on benchmark datasets demonstrate that PITE outperforms 13 state-of-the-art methods, achieving more accurate and robust ITE estimation.

Federated causal structure learning aims to infer causal relationships from data stored on individual clients, with privacy concerns. Most existing methods assume identical variable sets across clients and present federated strategies for aggregating local updates. However, in practice, clients often observe overlapping but non-identical variable sets, and non-overlapping variables may introduce spurious dependencies. Moreover, existing strategies typically reflect only the overall quality of local graphs, ignoring the varying importance of relationships within each graph. In this paper, we study federated causal structure learning with non-identical variable sets, aiming to design an effective strategy for aggregating “correct” and “good” (non-)causal relationships across distributed datasets. Specifically, we first develop theories for detecting spurious dependencies, examining whether the learned relationships are “correct” or not. Furthermore, we define stable relationships as those that are both “correct” and “good” across multiple graphs, and finally design a two-level priority selection strategy for aggregating local updates, obtaining a global causal graph over the integrated variables. Experimental results on synthetic, benchmark and real-world data demonstrate the effectiveness of our method.

Estimating Individual Treatment Effects (ITE) from observational data is challenging due to covariate shift and counterfactual absence. While existing methods attempt to balance distributions globally, they often lack fine-grained sample-level alignment, especially in scenarios with significant individual heterogeneity. To address these issues, we reconsider counterfactual as a proxy to emulate balanced randomization. Furthermore, we derive a theoretical bound that links the expected ITE estimation error to both factual prediction errors and representation distances between factuals and counterfactuals. Building on this theoretical foundation, we propose FCCL, a novel method designed to effectively capture the nuances of potential outcomes under different treatments by (i) generating diffeomorphic counterfactuals that adhere to the data manifold while maintaining high semantic similarity to their factual counterparts, and (ii) mitigating distribution shift via sample-level alignment grounded in our derived generalization-error bound, which considers factual-counterfactual similarity and category consistency. Extensive evaluations on benchmark datasets demonstrate that FCCL outperforms 13 state-of-the-art methods, particularly in capturing individual-level heterogeneity and handling sparse boundary samples.

Many confounding-resistant domain generalization methods for image classification have been developed based on causal interventions. However, their reliance on strong assumptions limits their effectiveness in handling unobserved confounders. Although recent work introduces instrumental variables (IVs) to overcome this limitation, the reliance on manually predefined instruments, particularly in the context of visual data, may result in severe bias or invalidity when IV conditions are violated. To address these issues, we propose a novel approach to automatically learning Visual Instrumental Variables for confounding-resistant Domain Generalization (VIV-DG). We observe that certain non-causal visual attributes in image data naturally satisfy the basic conditions required for valid IVs. Motivated by this insight, we propose the visual instrumental variable, a novel concept that extends classical IV theory to the visual domain. Furthermore, we develop an automatic visual instrumental variable learner that enforces IV conditions on learned representations, enabling the automatic learning of valid visual instrumental variables from image data. Ultimately, VIV-DG inherits the strengths of classical IVs to mitigate unobserved confounding and avoids the significant bias caused by violations of IV conditions in predefined IVs. Extensive experiments on multiple benchmarks verify that VIV-DG achieves superior generalization ability.

Existing early and late fusion frameworks in multimodal learning are confronted with the fundamental challenge of modality imbalance, wherein disparities in representational capacities induce inter-modal competition during training. Current research methodologies primarily rely on modality-level contribution assessments to measure gaps in representational capabilities and enhance poorly learned modalities, overlooking the dynamic variations of modality contributions across individual samples. To address this, we propose a Causal-aware Modality valuation approach for Balanced multimodal learning (CMoB). We define a benefit function based on Shannon's theory of informational uncertainty to evaluate the changes in the importance of samples across different stages of multimodal training. Inspired by human cognitive science, we propose a causal-aware modality contribution quantification method from a causal perspective to capture fine-grained changes in modality contribution degrees within samples. In the iterative training of multimodal learning, we develop targeted modal enhancement strategies that dynamically select and optimize modalities based on real-time evaluation of their contribution variations across training samples. Our method enhances the discriminative ability of key modalities and the learning capacity of weak modalities while achieving fine-grained balance in multimodal learning. Extensive experiments on benchmark multimodal datasets and multimodal frameworks demonstrate the superiority of our CMoB approach for balanced multimodal learning.

Clustering is a fundamental technique widely used for exploring the inherent data structure. Many studies indicate that an appropriate feature representation can effectively improve clustering performance. However, the existing feature representation methods are based on correlation to select or extract features, which makes it hard to deal with spurious correlations. The spurious correlations mislead the correlation-based methods to consider features that have no causal relationship as being correlative, which limits the clustering performance and feature interpretability. To tackle this issue, inspired by causal learning, we propose a new joint optimization Clustering Method with Causal Feature Embedding (CM-CaFE) , which utilizes the causality of features to learn more discriminative representation for clustering. Specifically, to eliminate spurious correlations among features, we first employ any state-of-the-art Markov blanket learning method to learn an undirected causal graph. Next, we extract the maximal fully connected causal subgraphs from the learned undirected causal graph and propose an approach to merge them to generate the causal matrix. Based on the causal matrix, we present an objective function that consists of a clustering loss term and a causal matrix fitting term to learn a causal transformation matrix. The causal transformation matrix is utilized to map the original data into a new space for clustering. Finally, we comprehensively compare the proposed method with some state-of-the-art clustering approaches on several datasets to demonstrate the effectiveness and interpretability of the proposed method.

Feature weighting aims to assign different weights to features based on their importance in machine learning tasks. In clustering tasks, the existing methods learn feature importance based on the clustering results derived from the collaborative contribution of all features, which overlooks the independent effect of each feature. In fact, there are underlying causal relationships between features and the clustering results, and the features with high causal effects are always more crucial for clustering. Therefore, we propose an enhancedFeatureWeighting method viaCausalEffect forClustering, calculating the causal effect of each feature on the clustering results for obtaining the independent contribution of each feature. Specifically, we start by identifying the causal relationships among the features and utilizing the causal relationships to generate a reasonable treatment group. Next, we compare the changes in the data distribution between the treatment and control groups to determine the causal effect of each feature. Finally, the causal effects of features are used for enhancing the clustering-driven weight learning. Moreover, we present a theory of relative order consistency in causal effect. Experimental results demonstrate that utilizing causal effect in weight learning facilitates efficient convergence and achieves superior accuracy compared to state-of-the-art clustering algorithms.

As a promising strategy to achieve generalizable graph learning tasks, graph invariant learning emphasizes identifying invariant subgraphs for stable predictions on biased unknown distribution by selecting the important edges/nodes based on their contributions to the predictive tasks (i.e., subgraph predictivity). However, the existing approaches solely relying on subgraph predictivity face a challenge: the learned invariant subgraph often contains numerous spurious nodes and shows poor connectivity, undermining the generalization power of Graph Neural Networks (GNNs). To tackle this issue, we propose a summary graph-induced Invariant Learning (SIL) model that innovatively adopts a summary graph to leverage both the subgraph connectivity and predictivity for learning strong connected and accurate invariant subgraphs. Specifically, SIL first learns a summary graph containing multiple strongly connected supernodes while maintaining structure consistency with the original graph. Second, the learned summary graph is disentangled into an invariant supernode and spurious counterparts to eliminate the interference of highly predictive edges and nodes. Finally, SIL identifies a potential invariant subgraph from the invariant supernode to accomplish generalization tasks. Additionally, we provide a theoretical analysis of the summary graph learning mechanism, guaranteeing that the learned summary graph is consistent with the original graph. Experimental results validate the effectiveness of the SIL model.

As the interdependence between arbitrary objects in the real world grows, it becomes gradually important to use chain graphs containing directed and undirected edges to learn the structure among objects. However, independence among some variables corresponds to multiple structures and the direction of edges among variables cannot be uniquely determined. This limitation restricts existing chain graphs structure learning algorithms to only learning their Markov equivalence class. To alleviate this limitation, we de ne the block domain knowledge and propose a block domain knowledge-driven learning chain graphs structure algorithm (KDLCG). The KDLCG algorithm learns the adjacencies and spouses of all variables, which are utilized to directly construct the skeleton and orient the edges of the complexes, thereby learning the Markov equivalence class of the chain graphs. Subsequently, the KDLCG algorithm then updates some edges with Meek rules, guided by block domain knowledge. Finally, the KDLCG algorithm directs some edges by estimating causal effects between two variables, driven by block domain knowledge. Meanwhile, we conduct theoretical analysis to prove the correctness of our algorithm and compare it with the LCD algorithm and MBLWF algorithm on synthetic and real-world datasets. The experimental results validate the effectiveness of our algorithm.

Causal chain graphs model the dependency structure between individuals when the assumption of individual independence in causal inference is violated. However, causal chain graphs are often unknown in practice and require learning from data. Existing learning algorithms have certain limitations. Specifically, learning local information requires multiple subset searches, building the skeleton requires additional conditional independence testing, and directing the edges requires obtaining local information from the skeleton again. To remedy these problems, we propose a novel algorithm for learning causal chain graph structure. The algorithm alternately learns the adjacencies and spouses of each variable as local information and doubly prunes them to obtain more accurate local information, which reduces subset searches, improves its accuracy, and facilitates subsequent learning. It then directly constructs the chain graphs skeleton using the learned adjacencies without conditional independence testing. Finally, it directs the edges of complexes using the learned adjacencies and spouses to learn chain graphs without reacquiring local information, further improving its efficiency. We conduct theoretical analysis to prove the correctness of our algorithm and compare it with the state-of-the-art algorithms on synthetic and real-world datasets. The experimental results demonstrate our algorithm is more reliable than its rivals.

Improving the generalization performance of classifiers from data pre-processing perspective has recently received considerable attention in the machine learning community. Although many methods have been proposed in the past decades, most of them lack theoretical foundations and cannot guarantee better generalization performance of classifiers on processed datasets. To overcome this flaw, in this paper, we propose a method, which is supported by Bayesian decision theory and percolation theory, to improve generalization performance by removing Bayesian confusing samples (abbr. BCS). Specifically, for a training set, we define the samples that misclassified by the Bayesian optimal classifier as BCS and prove that a classifier trained on the training set after removing BCS can obtain better generalization performance. To find out BCS, we indicate that BCS can be identified according to the size of global homogeneous cluster, a set of samples with the same labels, based on percolation theory. Based on these analysis, we propose a method to construct global homogeneous clusters and remove BCS from the training set. Extensive experiments show that the proposed method is effective for a number of classical and state-of-the-art classifiers.

Inferring causal structures from experimentation is a challenging task in many fields. Most causal structure learning algorithms with unknown interventions are proposed to discover causal relationships over an identical variable set. However, often due to privacy, ethical, financial, and practical concerns, the variable sets observed by multiple sources or domains are not entirely identical. While a few algorithms are proposed to handle the partially overlapping variable sets, they focus on the case of known intervention targets. Therefore, to be close to the real-world environment, we consider discovering causal relationships over overlapping variable sets under the unknown intervention setting and exploring a scenario where a problem is studied across multiple domains. Here, we propose an algorithm for discovering the causal relationships over the integrated set of variables from unknown interventions, mainly handling the entangled inconsistencies caused by the incomplete observation of variables and unknown intervention targets. Specifically, we first distinguish two types of inconsistencies and then deal with respectively them by presenting some lemmas. Finally, we construct a fusion rule to combine learned structures of multiple domains, obtaining the final structures over the integrated set of variables. Theoretical analysis and experimental results on synthetic, benchmark, and real-world datasets have verified the effectiveness of the proposed algorithm.

Causal structure learning (CSL) from observational data is a crucial objective in various machine learning applications. Recent advances in CSL have focused on local-to-global learning, which offers improved efficiency and accuracy. The local-to-global CSL algorithms first learn the local skeleton of each variable in a dataset, then construct the global skeleton by combining these local skeletons, and finally orient edges to infer causality. However, data quality issues such as noise and small samples often result in the presence of problematicasymmetric edgesduring global skeleton construction, hindering the creation of a high-quality global skeleton. To address this challenge, we propose a novel local-to-global CSL algorithm with a progressive enhancement strategy and make the following novel contributions: 1) To construct an accurate global skeleton, we design a novel strategy to iteratively correctasymmetric edgesand progressively improve the accuracy of the global skeleton. 2) Based on the learned accurate global skeleton, we design an integrated global skeleton orientation strategy to infer the correct directions of edges for obtaining an accurate and reliable causal structure. Extensive experiments demonstrate that our method achieves better performance than the existing CSL methods.

Causal feature selection methods aim to identify a Markov boundary (MB) of a class variable, and almost all the existing causal feature selection algorithms use conditional independence (CI) tests to learn the MB. However, in real-world applications, due to data issues (e.g., noisy or small samples), CI tests can be unreliable; thus, causal feature selection algorithms relying on CI tests encounter two types of errors: false positives (i.e., selecting false MB features) and false negatives (i.e., discarding true MB features). Existing algorithms only tackle either false positives or false negatives, and they cannot deal with both types of errors at the same time, leading to unsatisfactory results. To address this issue, we propose a dual-correction-strategy-based MB learning (DCMB) algorithm to correct the two types of errors simultaneously. Specifically, DCMB selectively removes false positives from the MB features currently selected, while selectively retrieving false negatives from the features currently discarded. To automatically determine the optimal number of selected features for the selective removal and retrieval in the dual correction strategy, we design the simulated-annealing-based DCMB (SA-DCMB) algorithm. Using benchmark Bayesian network (BN) datasets, the experimental results demonstrate that DCMB achieves substantial improvements on the MB learning accuracy compared with the existing MB learning methods. Empirical studies in real-world datasets validate the effectiveness of SA-DCMB for classification against state-of-the-art causal and traditional feature selection algorithms.

For a classification task, we usually select an appropriate classifier via model selection. How to evaluate whether the chosen classifier is optimal? One can answer this question via Bayes error rate (BER). Unfortunately, estimating BER is a fundamental conundrum. Most existing BER estimators focus on giving the upper and lower bounds of the BER. However, evaluating whether the selected classifier is optimal based on these bounds is hard. In this article, we aim to learn the exact BER instead of bounds on BER. The core of our method is to transform the BER calculation problem into a noise recognition problem. Specifically, we define a type of noise called Bayes noise and prove that the proportion of Bayes noisy samples in a data set is statistically consistent with the BER of the data set. To recognize the Bayes noisy samples, we present a method consisting of two parts: selecting reliable samples based on percolation theory and then employing a label propagation algorithm to recognize the Bayes noisy samples based on the selected reliable samples. The superiority of the proposed method compared to the existing BER estimators is verified on extensive synthetic, benchmark, and image data sets.

Causal structure learning has been extensively studied and widely used in machine learning and various applications. To achieve an ideal performance, existing causal structure learning algorithms often need to centralize a large amount of data from multiple data sources. However, in the privacy-preserving setting, it is impossible to centralize data from all sources and put them together as a single dataset. To preserve data privacy, federated learning as a new learning paradigm has attached much attention in machine learning in recent years. In this paper, we study a privacy-aware causal structure learning problem in the federated setting and propose a novel federated PC (FedPC) algorithm with two new strategies for preserving data privacy without centralizing data. Specifically, we first propose a novel layer-wise aggregation strategy for a seamless adaptation of the PC algorithm into the federated learning paradigm for federated skeleton learning, then we design an effective strategy for learning consistent separation sets for federated edge orientation. The extensive experiments validate that FedPC is effective for causal structure learning in federated learning setting.

In this study, we investigate a challenging problem, namely, robust domain adaptation, where data from only a single well-labeled source domain are available in the training phase. To address this problem, assuming that the causal relationships between the features and the class variable are robust across domains, we propose a novel causal autoencoder (CAE), which integrates a deep autoencoder and a causal structure learning model to learn causal representations using data from a single source domain. Specifically, a deep autoencoder model is adopted to learn the low-dimensional representations, and a causal structure learning model is designed to separate the low-dimensional representations into two groups: causal representations and task-irrelevant representations. Using three real-world datasets, the experiments have validated the effectiveness of CAE, in comparison with eleven state-of-the-art methods.

We consider the problem of distinguishing direct causes from direct effects of a target variable of interest from multiple manipulated datasets with unknown manipulated variables and nonidentical data distributions. Recent studies have shown that datasets attained from manipulated experiments (i.e., manipulated data) contain richer causal information than observational data for causal structure learning. Thus, in this article, we propose a new algorithm, which makes full use of the interventional properties of a causal model to discover the direct causes and direct effects of a target variable from multiple datasets with different manipulations. It is more suited to real-world cases and is also a challenge to be addressed in this article. First, we apply the backward framework to learn parents and children (PC) of a given target from multiple manipulated datasets. Second, we orient some edges connected to the target in advance through the assumption that the target variable is not manipulated and then orient the remaining undirected edges by finding invariant V-structures from multiple datasets. Third, we analyze the correctness of the proposed algorithm. To the best of our knowledge, the proposed algorithm is the first that can identify the local causal structure of a given target from multiple manipulated datasets with unknown manipulated variables. Experimental results on standard Bayesian networks validate the effectiveness of our algorithm.

In this paper, we consider the problem of lacking theoretical foundation and low execution efficiency of the instance selection methods based on the k-nearest neighbour rule when processing large-scale data. We point out that the core idea of these methods can be explained from the perspective of Bayesian decision theory, that is, to find which instances are reducible, irreducible, and deleterious. Then, based on the percolation theory, we establish the relationship between these three types of instances and local homogeneous cluster (i.e., a set of instances with the same labels). Finally, we propose a method based on an accelerated k-means algorithm to construct local homogeneous clusters and remove the superfluous instances. The performance of our method is studied on extensive synthetic and benchmark data sets. Our proposed method can handle large-scale data more effectively than the state-of-the-art instance selection methods. All code and data results are available at https://github.com/CQQXY161120/Instance-Selection.

We consider the problem of reducing the false discovery rate in multiple high-dimensional interventional datasets under unknown targets. Traditional algorithms merged directly multiple causal graphs learned, which ignores the contradictions of different datasets, leading to lots of inconsistent directions of edges. For reducing the contradictory information, we propose a new algorithm, which first learns an interventional Markov equivalence class (I-MEC) before merging multiple graphs. It utilizes the full power of the constraints available in interventional data and combines ideas from local learning, intervention, and search-and-score techniques in a principled and effective way in different intervention experiments. Specifically, local learning on multiple datasets is used to build a causal skeleton. Perfect intervention destroys some possible triangles, leading to the identification of more possible V-structures. And then a theoretically correct I-MEC is learned. Search and scoring techniques based on the learned I-MEC further identify the remaining unoriented edges. Both theoretical analysis and experiments on benchmark Bayesian networks with the number of variables from 20 to 724 validate that the effectiveness of our algorithm in reducing the false discovery rate in high-dimensional interventional data.

Local causal structure learning aims to discover and distinguish direct causes (parents) and direct effects (children) of a variable of interest from data. While emerging successes have been made, existing methods need to search a large space to distinguish direct causes from direct effects of a target variable T. To tackle this issue, we propose a novel Efficient Local Causal Structure learning algorithm, named ELCS. Specifically, we first propose the concept of N-structures, then design an efficient Markov Blanket (MB) discovery subroutine to integrate MB learning with N-structures to learn the MB of T and simultaneously distinguish direct causes from direct effects of T. With the proposed MB subroutine, ELCS starts from the target variable, sequentially finds MBs of variables connected to the target variable and simultaneously constructs local causal structures over MBs until the direct causes and direct effects of the target variable have been distinguished. Using eight Bayesian networks the extensive experiments have validated that ELCS achieves better accuracy and efficiency than the state-of-the-art algorithms.

Domain adaptation aims to facilitate the learning task in an unlabeled target domain by leveraging the auxiliary knowledge in a well-labeled source domain from a different distribution. Almost existing autoencoder-based domain adaptation approaches focus on learning domain-invariant representations to reduce the distribution discrepancy between source and target domains. However, there is still a weakness existing in these approaches: the class-discriminative information of the two domains may be damaged while aligning the distributions of the source and target domains, which makes the samples with different classes close to each other, leading to performance degradation. To tackle this issue, we propose a novel dual-representation autoencoder (DRAE) to learn dual-domain-invariant representations for domain adaptation. Specifically, DRAE consists of three learning phases. First, DRAE learns global representations of all source and target data to maximize the interclass distance in each domain and minimize the marginal distribution and conditional distribution of both domains simultaneously. Second, DRAE extracts local representations of instances sharing the same label in both domains to maintain class-discriminative information in each class. Finally, DRAE constructs dual representations by aligning the global and local representations with different weights. Using three text and two image datasets and 12 state-of-the-art domain adaptation methods, the extensive experiments have demonstrated the effectiveness of DRAE.

Semi-supervised clustering is one of important research topics in cluster analysis, which uses pre-given knowledge as constraints to improve the clustering performance. While clustering a data set, people often get prior constraints from different information sources, which may have different representations and contents, to guide clustering process. However, most of existing semi-supervised clustering algorithms are based on single-source constraints and rarely consider to integrate multi-source constraints to enhance the clustering quality. To solve the problem, we analyze the relations among different types of constraints and propose an uniform representation for them. Based it, we propose a new semi-supervised clustering algorithm to find out a clustering that has good cluster structure and high consensus of all the sources of constraints. In the algorithm, we construct an optimization objective model and its solution method to achieve the aim. This algorithm can integrate multi-source constraints well to reduce the effect of incorrect constraints from single sources and find out a high-quality clustering. By the experimental studies on several benchmark data sets, we illustrate the effectiveness of the proposed algorithm, compared to other semi-supervised clustering algorithms.

Clustering by jointly exploiting information from multiple views can yield better performance than clustering on one single view. Some existing multi-view clustering methods aim at learning a weight for each view to determine its contribution to the final solution. However, the view-weighted scheme can only indicate the overall importance of a view, which fails to recognize the importance of each inner cluster of a view. A view with higher weight cannot guarantee all clusters in this view have higher importance than them in other views. In this paper, we propose a cluster-weighted kernel k-means method for multi-view clustering. Each inner cluster of each view is assigned a weight, which is learned based on the intra-cluster similarity of the cluster compared with all its corresponding clusters in different views, to make the cluster with higher intra-cluster similarity have a higher weight among the corresponding clusters. The cluster labels are learned simultaneously with the cluster weights in an alternative updating way, by minimizing the weighted sum-of-squared errors of the kernel k-means. Compared with the view-weighted scheme, the cluster-weighted scheme enhances the interpretability for the clustering results. Experimental results on both synthetic and real data sets demonstrate the effectiveness of the proposed method.

In data mining, objects are often represented by a set of features, where each feature of an object has only one value. However, in reality, some features can take on multiple values, for instance, a person with several job titles, hobbies, and email addresses. These features can be referred to as set-valued features and are often treated with dummy features when using existing data mining algorithms to analyze data with set-valued features. In this paper, we propose an SV- $k$ -modes algorithm that clusters categorical data with set-valued features. In this algorithm, a distance function is defined between two objects with set-valued features, and a set-valued mode representation of cluster centers is proposed. We develop a heuristic method to update cluster centers in the iterative clustering process and an initialization algorithm to select the initial cluster centers. The convergence and complexity of the SV- $k$ -modes algorithm are analyzed. Experiments are conducted on both synthetic data and real data from five different applications. The experimental results have shown that the SV- $k$ -modes algorithm performs better when clustering real data than do three other categorical clustering algorithms and that the algorithm is scalable to large data.

As a leading partitional clustering technique, k-modes is one of the most computationally efficient clustering methods for categorical data. In the k-modes, a cluster is represented by a "mode," which is composed of the attribute value that occurs most frequently in each attribute domain of the cluster, whereas, in real applications, using only one attribute value in each attribute to represent a cluster may not be adequate as it could in turn affect the accuracy of data analysis. To get rid of this deficiency, several modified clustering algorithms were developed by assigning appropriate weights to several attribute values in each attribute. Although these modified algorithms are quite effective, their convergence proofs are lacking. In this paper, we analyze their convergence property and prove that they cannot guarantee to converge under their optimization frameworks unless they degrade to the original k-modes type algorithms. Furthermore, we propose two different modified algorithms with weighted cluster prototypes to overcome the shortcomings of these existing algorithms. We rigorously derive updating formulas for the proposed algorithms and prove the convergence of the proposed algorithms. The experimental studies show that the proposed algorithms are effective and efficient for large categorical datasets.

$K$-means is a partitional clustering technique that is well-known and widely used for its low computational cost. The representative algorithms include the hard$k$-means and the fuzzy$k$-means. However, the performance of these algorithms tends to be affected by skewed data distributions, i.e., imbalanced data. They often produce clusters of relatively uniform sizes, even if input data have varied cluster sizes, which is called the “uniform effect.” In this paper, we analyze the causes of this effect and illustrate that it probably occurs more in the fuzzy$k$-means clustering process than the hard$k$-means clustering process. As the fuzzy index$m$increases, the “uniform effect” becomes evident. To prevent the effect of the “uniform effect,” we propose a multicenter clustering algorithm in which multicenters are used to represent each cluster, instead of one single center. The proposed algorithm consists of the three subalgorithms: the fast global fuzzy$k$-means, Best M-Plot, and grouping multicenter algorithms. They will be, respectively, used to address the three important problems: 1) How are the reliable cluster centers from a dataset obtained? 2) How are the number of clusters which these obtained cluster centers represent determined? 3) How is it judged as to which cluster centers represent the same clusters? The experimental studies on both synthetic and real datasets illustrate the effectiveness of the proposed clustering algorithm in clustering balanced and imbalanced data.

A fundamental assumption often made in unsupervised learning is that the problem is static, i.e., the description of the classes does not change with time. However, many practical clustering tasks involve changing environments. It is hence recognized that the methods and techniques to analyze the evolving trends for changing environments are of increasing interest and importance. Although the problem of clustering numerical time-evolving data is well-explored, the problem of clustering categorical time-evolving data remains as a challenging issue. In this paper, we propose a generalized clustering framework for categorical time-evolving data, which is composed of three algorithms: a drifting-concept detecting algorithm that detects the difference between the current sliding window and the last sliding window, a data-labeling algorithm that decides the most-appropriate cluster label for each object of the current sliding window based on the clustering results of the last sliding window, and a cluster-relationship-analysis algorithm that analyzes the relationship between clustering results at different time stamps. The time-complexity analysis indicates that these proposed algorithms are effective for large datasets. Experiments on a real dataset show that the proposed framework not only accurately detects the drifting concepts but also attains clustering results of better quality. Furthermore, compared with the other framework, the proposed one needs fewer parameters, which is favorable for specific applications.