Search

Multilevel granular structures play a fundamental role in granular computing. In this chapter, we present a general framework of granular spaces. Within the framework, we examine the granular structures and approximations in rough set analysis and knowledge spaces. Although the two theories use different types of granules, they can be unified in the proposed framework.

This article gives a capsule view of research on rough set theory and applications ongoing at universities and laboratories in China. Included in this capsule view of rough set research is a brief description of the following things: Chinese research groups on rough set with their URLs for web pages, names of principal researchers (supervisors), numbers of graduate students, and topics being investigated. Statistical summaries showing the growth in the research on rough set theory and application in China are included. In addition, an introduction summarizing the research interests of Chinese researchers is included in this article. The contribution of this article is a complete overview of the principal research directions in rough set theory and its applications in China.

In this paper, we perform Chinese text classification using n-gram text representation on TanCorp which is a new large corpus special for Chinese text classification more than 14,000 texts divided into 12 classes. We use different n-gram feature (1-, 2-grams or 1-, 2-, 3-grams) to represent documents. Different feature weights (absolute text frequency, relative text frequency, absolute n-gram frequency and relative n-gram frequency) are compared. The sparseness of "document by feature" matrices is analyzed in various cases. We use the C-SVC classifier which is the SVM algorithm designed for the multi-classification task. We perform our experiments in the TANAGRA platform. We found out that the feature selection methods based on n-gram frequency (absolute or relative) always give better results and produce denser matrices.

Decision theoretic framework has been helpful in providing a better understanding of classification models. In particular, decision theoretic interpretations of different types of the binary rough set classification model have led to the refinement of these models. This study extends the decision theoretic rough set model to supervised and unsupervised multi-category problems. The proposed framework can be used to study the multi-classification and clustering problems within the context of rough set theory.

In this paper, an algorithm is proposed for card images binarization. It is performed by three steps: coarse binarization, refined binarization, and postprocessing. Firstly, it uses the traditional global thresholding approach to separate a card image into several sub-images, which can be classified into two classes: text sub-images with clear background and text sub-images with complicated background. Secondly, the dual-thresholding is applied to regenerate or retouch the sub-images. According to the characteristics of text candidate sub-image, the thresholding method is selected and applied on it. Finally, the postprocessing is performed on the binary image. Experimental results demonstrate that this approach highly improved the performance of the card image binarization system.

As an emerging conceptual and computing paradigm of information processing, granular computing has received much attention recently. Many models and methods of granular computing have been proposed and studied. Among them was the granular computing model using information tables. In this paper, we shall demonstrate the application of this granular computing model for the study of a specific data mining problem - outlier detection. Within the granular computing model using information tables, this paper proposes a novel definition of outliers - GrC (granular computing)-based outliers. An algorithm to find such outliers is also given. And the effectiveness of GrC-based method for outlier detection is demonstrated on three publicly available databases.

Conventional clustering algorithms categorize an object into precisely one cluster. In many applications, the membership of some of the objects to a cluster can be ambiguous. Therefore, an ability to specify membership to multiple clusters can be useful in real world applications. Fuzzy clustering makes it possible to specify the degree to which a given object belongs to a cluster. In Rough set representations, an object may belong to more than one cluster, which is more flexible than the conventional crisp clusters and less verbose than the fuzzy clusters. The unsupervised nature of fuzzy and rough algorithms means that there is a choice about the level of precision depending on the choice of parameters. This paper describes how one can vary the precision of the rough set clustering and studies its effect on synthetic and real world data sets.

Due to the uncertainty in accessing Web pages, analysis of Web logs faces some challenges. Several rough k-means cluster algorithms have been proposed and successfully applied to Web usage mining. However, they did not explain why rough approximations of these cluster algorithms were introduced. This paper analyzes the characteristics of the data in the boundary areas of clusters, and then a rough k-means cluster algorithm based on a reasonable rough approximation (RKMrra) is proposed. Finally RKMrra is applied to Web access logs. In the experiments RKMrra compares to Lingras and West algorithm and Peters algorithm with respect to five characteristics. The results show that RKMrra discovers meaningful clusters of Web users and its rough approximation is more reasonable.

Granular computing is a new conceptual and computing paradigm of information processing, the idea of which is the use of granules for problem solving at different granularities. Web page classification is an important research direction for Web mining. In this paper, we propose an approach to Web page classification based on granules. Some concepts are defined firstly. Then, a Web page classification framework based on granules is built and an automatic classification algorithm is proposed. Experiment results demonstrate that the proposed approach is promising and effective.1

A great number of biclustering algorithms have been proposed for analyzing gene expression data. Many of them assume to find exclusive biclusters whose subsets of genes are co-regulated under subsets of conditions without intersection. This is not consistent with a general understanding of biological processes that many genes participate in multiple different processes. Therefore nonexclusive biclustering algorithms are required. In this paper we present a novel approach (ROB) to find potentially overlapping biclusters in the framework of generalized rough sets. Our scheme mainly consists of two phases. First, we generate a set of highly coherent seeds (original biclusters) based on two-way rough k-means clustering. And then, the seeds are iteratively adjusted (enlarged or degenerated) by adding or removing genes and conditions based on a proposed criterion. We illustrate the method on yeast gene expression data. The experiments demonstrate the effectiveness of this approach.

The quality of character image plays an important role for the performance of character recognition system. However there is no good way to measure the recognition difficulty of a given character image. For the given character image with unknown quality, it is improper that apply the single character database to recognize it by the same feature and the same classifier. This paper proposed a novel approach for multi-resolution character recognition whose feature is extracted directly from gray-scale image and classification is adaptive classification which adaptively selects the appropriate character database and classifiers by evaluating the image quality of the input character. A resolution evaluation algorithm based on gray distribution feature was proposed to decide the adaptive classification weights for the classifiers, which make the classification have the higher probability of being the correct decision. Experiment results demonstrate the proposed approach highly improved the performance of character recognition system.

In this paper, the main techniques of inductive machine learning are united to the knowledge reduction theory based on rough sets from the theoretical point of view. And then the Monk's problems are resolved again employing rough sets. As far as accuracy and conciseness are concerned, the learning algorithms based on rough sets have remarkable superiority to the previous methods.

As electronic commerce (EC) become more and more prevalent to people, it is very critical to provide the right information to the right customers. The EC sites are generating large amount of data on customer purchases. Data mining techniques in EC domain is currently a hot research area. This paper proposes a rough set based approach to obtaining patterns of goods and classifying associated goods into groups, which can be used by the sites to group their goods according to the customers' preference and adopt appropriate selling policies.

A new method combining correlation based clustering and rough sets attribute reduction together for gene selection from gene expression data is proposed. Correlation based clustering is used as a filter to eliminate the redundant attributes, then the minimal reduct of the filtered attribute set is reduced by rough sets . Three different classification algorithms are employed to evaluate the performance of this novel method. High classification accuracies achieved on two public gene expression data sets show that this method is successful for selecting high discriminative genes for classification task. The experimental results indicate that rough sets based method has the potential to become a useful tool in bioinformatics.

For traditional way of Web document representation in Vector Space Model, zero-valued similarity problem between vectors occurs frequently, which decreases classificatory quality when defining the relation between Web documents. In this paper, a novel Web document representation and classification approach based on rough set is proposed. Firstly, TF*IDF weighting scheme is used to assign weight values for Web document's vector. The weights of those terms which do not occur in a Web document are considered missing information. Then rough set for incomplete information is introduced to supplement loss and expand Web document representation. Through generating tolerance classes in both term space and Web document space, the missing information of Web document can be complemented by incorporating the corresponding weights of terms in tolerance classes, which extends the essential information to Web document. Finally, Web document classification algorithm is implemented. Experimental results show that the performance of the classification is greatly improved.

This paper presented a novel approach, based on an integrated use of fuzzy and rough set theories, to greatly reduce data redundancy. The information framework in rough set theory is introduced in fuzzy-rough set. Mutual information-based algorithm for attribute reduction in fuzzy-rough set is introduced and illustrated with a simple example. Experimental result shows that it is an effective technique.

In rough set theory, it has been proved that finding the minimal reduct of information systems or decision tables is a NP-complete problem. Therefore, it is hard to obtain the set of the most concise rules by existing algorithms for reduction of knowledge. In this paper, the method of finding sub-optimal reduct based on discernibility matrix is proposed. In general, our method is better than existing methods with respect to the minimal reduct. However, we find that existing minimal reduct searching algorithms are incomplete for reduction of attributes in information systems or decision tables. Through analysis, we present a conjecture about the completeness of the minimal reduct algorithm.

The theory of rough sets is an extension of the set theory, for the study of intelligent systems characterized by insufficient and incomplete information. Since proposed by Pawlak, rough sets have evoked a lot of research. Theoretic study has included algebra aspect of rough sets. In paper [1] the concept of rough group and rough subgroup was introduced, but with some deficiencies remaining. In this paper, we intend to make up for these shortages, improve definitions of rough group and rough subgroup, and prove their new properties.

Minutiae extraction is a critical step in fingerprint identification, so it is important to find a proper approach to extract minutiae In this paper, we propose a new method which extracts minutiae via principal curves At first, we get a group of principal curves which reflect the structural features of the fingerprint; then we extract minutiae of fingerprint from these principal curves From the result of experiment, we conclude that this new approach is feasible.

A geodesic distance-based approach to build the neighborhood graph for isometric embedding is proposed to deal with the highly twisted and folded manifold by Wen et al. [Using locally estimated geodesic distance to optimize neighborhood graph for isometric data embedding, Pattern Recognition 41 (2008) 2226-2236]. This comment is to identify the error in their example and the ineffectiveness of their algorithm.

Establishing a classification model for cancer recognition based on DNA microarrays is useful for cancer diagnosis. Feature selection is a key step to perform cancer classification with DNA microarrays, for there is a large number of genes from which to predict classes and a relatively small number of samples. Automatic methods must be developed for extracting relevant genes which are essential for classification. This paper proposes a novel approach for reducing data redundancy based on fuzzy rough set theory and information theory. A mutual information-based algorithm for attribute reduction is suggested. The method is applied to the problem of gene selection for cancer classification. Experimental results show that the algorithm is more effective than conventional rough sets based approaches.

Attribute reduction is one of the key issues in rough set theory. Many heuristic attribute reduction algorithms such as positive-region reduction, information entropy reduction and discernibility matrix reduction have been proposed. However, these methods are usually computationally time-consuming for large data. Moreover, a single attribute significance measure is not good for more attributes with the same greatest value. To overcome these shortcomings, we first introduce a counting sort algorithm with time complexity O(∣C∣ ∣U∣) for dealing with redundant and inconsistent data in a decision table and computing positive regions and core attributes (∣C∣ and ∣U∣ denote the cardinalities of condition attributes and objects set, respectively). Then, hybrid attribute measures are constructed which reflect the significance of an attribute in positive regions and boundary regions. Finally, hybrid approaches to attribute reduction based on indiscernibility and discernibility relation are proposed with time complexity no more than max(O(∣C∣2∣U/C∣),O(∣C∣∣U∣)), in which ∣U/C∣ denotes the cardinality of the equivalence classes set U/C. The experimental results show that these proposed hybrid algorithms are effective and feasible for large data.