Fundamenta Informaticae

Clustering with pairwise constraints has received much attention in the clustering community recently. Particularly, must-link and cannot-link constraints between a given pair of instances in the data set are common prior knowledge incorporated in many clustering algorithms today. This approach has been shown to be successful in guiding a number of famous clustering algorithms towards more accurate results. However, recent work has also shown that the incorporation of must-link and cannot-link constraints makes clustering algorithms too much sensitive to “the assignment order of instances” and therefore results in consequent constraint violation. The major contributions of this paper are two folds. One is to address the issue of constraint violation in Cop-Kmeans by emphasizing a sequenced assignment of cannot-link instances after conducting a Breadth-First Search of the cannot-link set. The other is to reduce the computational complexity of Cop-Kmeans for massive data sets by adopting a MapReduce Framework. Experimental results show that our approach performs well on massive data sets while may overcome the problem of constraint violation.

Clustering is a very important technique in knowledge discovery. It has been widely used in data mining, image processing, machine learning, bioinformatics, marketing and other fields. Clustering discern the objects into groups called clusters, based on certain criteria. The similarity of objects is high within the clusters, but low between the clusters. In this work, we investigate a hybridization of the gravitational search algorithm (GSA) and big bang-big crunch algorithm (BB-BC) on data clustering. In the proposed approach, namely GSA-BB, GSA is used to explore the search space for finding the optimal locations of the clusters centroids. Whenever GSA loses its exploration, BB-BC algorithm is used to diversify the population. The performance of the proposed method is compared with GSA, BB-BC and K-means algorithms using six standard and real datasets taken from the UCI machine learning repository. Experimental results indicate that there is significant improvement in the quality of the clusters obtained by the proposed hybrid method over the non-hybrid methods.

In the paper, a computer tool called ROSECON, used for modeling and analyzing systems of concurrent processes, is described. A special attention is focused on synthesis and verification of concurrent systems specified by information systems. Two kinds of models, synchronous and asynchronous, are considered. In the first approach, all processes included in the modeled system are synchronized globally whereas in the second one, each process is synchronized individually. The presented tool allows generating automatically an appropriate model of a system of concurrent processes, in the form of colored Petri nets, from the specification given by an information system. Analysis of the model behaviors enables users to verify the correctness and/or optimality of the obtained models and to provide some modification procedures to get correct and/or more optimal solutions. Examples of selected well known problems in concurrency, in the paper, emphasize usefulness of the tool in the designing systems of concurrent processes.

Decision-theoretic rough sets in two kinds of incomplete information systems are discussed in this paper. One is for the classical decision attribute and the other for the fuzzy decision attribute. In complete information system, the universe is partitioned with the equivalence relation. Given a concept, we get a pair of approximations of the concept using rough set theory, and the universe can be partitioned into three regions for making a decision. An incomplete information table can be expressed as a family of complete information tables. The universe is partitioned by the equivalence relation for each complete information table. The probability of each object belonging to the concept can be calculated in a completion from incomplete information system, and then the total probability of the object belonging to the concept can be obtained. Decision rules are derived using total probability instead of conditional probability in decision-theoretic rough sets. Finally, the universe is divided into three regions according to the total probability. A similar approach to fuzzy incomplete information system is examined and the universe is also divided into three regions.

In order to handle inconsistencies in ordinal and monotonic information systems, several relaxed versions of the Dominance-based Rough Set Approach (DRSA) have been proposed, e.g., VC-DRSA. These versions use special consistency measures to admit some inconsistent objects in the lower approximations. The minimal consistency level that has to be attained by objects included in the lower approximations is defined using a prior knowledge or a trial-and-error procedure. In order to avoid dependence on prior knowledge, an alternative way of handling inconsistencies is to iteratively eliminate the most inconsistent objects (according to some measure) until the information system becomes consistent. This idea is a base of a new method of handling inconsistencies presented in this paper and called TIPStoC. The TIPStoC algorithm is illustrated by an example from the area of telecommunication and the efficiency of the new method is proved by a computational experiment.

Attribute reduction is one basic issue in knowledge discovery of information systems. In this paper, based on the object oriented concept lattice and classical concept lattice, the approach of attribute reduction for formal contexts is investigated. We consider attribute reduction and attribute characteristics from the perspective of linear dependence of vectors. We first introduce the notion of context matrix and the operations of corresponding column vectors, then present some judgment theorems of attribute reduction for formal contexts. Furthermore, we propose a new method to reducing formal context and show corresponding reduction algorithms. Compared with previous reduction approaches which employ discernibility matrix and discernibility function to determine all reducts, the proposed approach is more simpler and easier to implement.

For most attribute reduction in Pawlak rough set model (PRS), monotonicity is a basic property for the quantitative measure of an attribute set. Based on the monotonicity, a series of attribute reductions in Pawlak rough set model such as positive-region-preserved reductions and condition entropy-preserved reductions are defined and the corresponding heuristic algorithms are proposed in previous rough sets research. However, some quantitative measures of attribute set may be non-monotonic in probabilistic rough set model such as decision-theoretic rough set (DTRS), and the non-monotonic definition of the attribute reduction should be reinvestigated and the heuristic algorithm should be reconsidered. In this paper, the monotonicity of the positive region in PRS and DTRS are comparatively discussed. Theoretic analysis shows that the positive region in DTRS model may be expanded with the decrease of the attributes, which is essentially different from that in PRS model. Hereby, a new non-monotonic attribute reduction is presented for the DTRS model in this paper, and a heuristic algorithm for searching the newly defined attribute reduction is proposed, in which the positive region is allowed to be expanded instead of remaining unchanged in the process of attribute reduction. Experimental analysis is included to validate the theoretic analysis and quantify the effectiveness of the proposed attribute reduction algorithm.

This paper considers the nearness of sets in local descriptive admissible covers of nonempty sets and the problem of quantifying the nearness of such sets. A brief review of descriptive Efremovič spaces as well descriptive intersection and union provides a foundation for the study of descriptive admissible covers. Descriptively near sets in admissible covers contain sequences of points with members having similar descriptions. The motivation for this approach stems from the need to consider fine-grained neighbourhoods of points in admissible covers that facilitate highly accurate measures of nearness of tiny parts of sets of objects of interest. A practical application of local admissible covers is given in terms of micropalaeontology and the detection of minute similarities and differences in microfossils, useful in the study of climate change, mineral and fossil fuel exploration.