Search

Clustering is a Data Mining technique which has been widely used in many practical applications. In some of these applications like, medical diagnosis, categorization of digital libraries, topic detection and others, the objects could belong to more than one cluster. However, most of the clustering algorithms generate disjoint clusters. Moreover, processing additions, deletions and modifications of objects in the clustering built so far, without having to rebuild the clustering from the beginning is an issue that has been little studied. In this paper, we introduce DCS, a clustering algorithm which includes a new graph-cover strategy for building a set of clusters that could overlap, and a strategy for dynamically updating the clustering, managing multiple additions and/or deletions of objects. The experimental evaluation conducted over different collections demonstrates the good performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Overlapping clustering algorithms have shown to be effective for clustering documents. However, the current overlapping document clustering algorithms produce a big number of clusters, which make them little useful for the user. Therefore, in this paper, we propose a k-means based method for overlapping document clustering, which allows to specify by the user the number of groups to be built. Our experiments with different corpora show that our proposal allows obtaining better results in terms of FBcubed than other recent works for overlapping document clustering reported in the literature. [ABSTRACT FROM AUTHOR]

In supervised classification if one of the classes has fewer objects than the other, we have a class imbalance problem. One of the most common solutions to address class imbalance problems is oversampling, and SMOTE is the most referenced and well-known oversampling method. However, SMOTE creates synthetic objects in a random way, therefore it produces a different result each time it is applied, and in practice the user has to apply SMOTE several times for choosing the best of all the generated balanced datasets. For this reason, in this paper, we present SMOTE-D, a deterministic version of SMOTE, and propose new deterministic SMOTE-D-based versions of some of the most recent and successful SMOTE-based methods. In our experiments, we show that all proposed deterministic methods produce as good results as random methods but our proposals need to be applied just once. This is very important from a practical point of view since our proposals save time by avoiding multiple applications of them as SMOTE does and they provide one unique result. [ABSTRACT FROM AUTHOR]

In Associative Classification, building a classifier based on Class Association Rules (CARs) consists in finding an ordered CAR list by applying a rule ordering strategy, and selecting a satisfaction mechanism to determine the class of unseen transactions. In this paper, we introduce four novel hybrid rule ordering strategies; the first three combine the Netconf measure with different Support-Confidence based rule ordering strategies. The fourth strategy combines the Netconf measure with a rule ordering strategy based on the CAR's size. Additionally, we combine the proposed strategies with a novel "Dynamic K" satisfaction mechanism. Experiments over several datasets show that the proposed rule ordering strategies jointly with the "Dynamic K" satisfaction mechanism allow improving the performance of CAR-based classifiers. [ABSTRACT FROM AUTHOR]

Measuring the quality of a contrast pattern is an active and relevant area of pattern recognition and data mining. Quality measures are important tools in very different scenarios like supervised classification, pattern based clustering, and association rule mining. Consequently, and due to the large collection of available measures, it is important to perform comparative studies for each particular context. Most published studies comparing quality measures are theoretical and in the context of association rule evaluation. In this paper, we present an empirical comparison of the behavior of 33 quality measures in the context of supervised classification and contrast pattern filtering. A comprehensive experimentation using several databases compares the behavior of these measures in three different contexts: as aggregation value, as pattern evaluation for classification, and as pattern evaluation for filtering. Experiments also show that top-accurate quality measures for classification have a deceptive performance for pattern filtering, because they cannot distinguish among patterns with zero support in the negative class. [ABSTRACT FROM AUTHOR]

In this paper, an accurate classifier based on Class Association Rules (CARs), called CAR-NF, is proposed. CAR-NF introduces a new strategy for computing CARs, using the Netconf as measure of interest, that allows to prune the CAR search space for building specific rules with high Netconf. Moreover, we propose and prove a proposition that supports the use of a Netconf threshold value equal to 0.5 for mining the CARs. Additionally, a new way for ordering the set of CARs based on their rule sizes and Netconf values is introduced in CAR-NF. The ordering strategy together with the "Best K rules" satisfaction mechanism allows CAR-NF to have better accuracy than CBA, CMAR, CPAR, TFPC and HARMONY classifiers, the best classifiers based on CARs reported in the literature. [ABSTRACT FROM AUTHOR]

Feature selection is a crucial aspect in classification problems, especially in domains such as text classification, where usually there is a large number of features. Recently, a two-stage feature selection method for text classification which combines class-based and corpus-based feature selection, was introduced. Based on their experiments, the authors conclude what parameter values for both, corpus-based and class-based approaches, allow a feature selection which improves the traditional methods in text classification. In this paper, we revisit this two-stage feature selection method and based on several experiments we come to a different conclusion: the parameters suggested by the original work do not necessarily provide the best results. Based on our experiments, we conclude that by combining the best parameter value for each stage, for the specific corpus under study, the two stage selection method based on coverage policies provides a subset of features which allows to get statistically significant increase over the traditional methods in the success rates of the classifier. [ABSTRACT FROM AUTHOR]

Support calculation and duplicate detection are the most challenging and unavoidable subtasks in frequent connected subgraph (FCS) mining. The most successful FCS mining algorithms have focused on optimizing these subtasks since the existing solutions for both subtasks have high computational complexity. In this paper, we propose two novel properties that allow removing all duplicate candidates before support calculation. Besides, we introduce a fast support calculation strategy based on embedding structures. Both properties and the new embedding structure are used for designing two new algorithms: gdFil for mining all FCSs; and gdClosed for mining all closed FCSs. The experimental results show that our proposed algorithms get the best performance in comparison with other well known algorithms. [ABSTRACT FROM AUTHOR]

In this paper, two algorithms for mining frequent itemsets in large sparse datasets are proposed. The first one, named Compressed Arrays (CA), allows to process datasets that do not change along the time (static datasets) while the second one, based on the ideas of the former and named Dynamic Compressed Arrays (DCA), processes datasets that change along the time by adding/deleting transactions (dynamic datasets). Both algorithms introduce a novel way to use equivalence classes of itemsets by performing a breadth first search through them and by storing the class prefix support in compressed arrays, which allows fast itemset support computing. On the other hand, unlike previous algorithms for dynamic datasets that store the full dataset in main memory without reusing the current frequent itemsets, DCA algorithm stores the current frequent itemsets in binary files, grouped in equivalence classes, and reuses them to calculate the new frequent itemsets. [ABSTRACT FROM AUTHOR]

Most of the Frequent Connected Subgraph Mining (FCSM) algorithms have been focused on detecting duplicate candidates using canonical form (CF) tests. CF tests have high computational complexity, which affects the efficiency of graph miners. In this paper, we introduce novel properties of the canonical adjacency matrices for reducing the number of CF tests in FCSM. Based on these properties, a new algorithm for frequent connected subgraph mining called grCAM is proposed. The experiments on real world datasets show the impact of the proposed properties in FCSM. Besides, the performance of our algorithm is compared against some other reported algorithms. [ABSTRACT FROM AUTHOR]